[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: line buffer as Red Black Trees instead of linear

From: Alin Soare
Subject: Re: line buffer as Red Black Trees instead of linear
Date: Thu, 15 May 2014 20:15:14 +0300

The whole buffer would be encoded as a list of lines, and each line is encoded as a red-black tree, as I described.

This will make fast operations involving the gap, the red-black trees are quite easy to implement, but I cannot see now the bad side effects involved by such a change. The major improvement would be the redisplay.

As a completion, I want to add that the whole text of a buffer can be kept in a single rbt, and at each node one can add an integer attribute that keeps the number of lines at the left of the node, such that searching for a particular line offset to be done in logarithmic time.

All the operations would be in constant or logarithmic time, but the major improvement are the operations on buffer gap, which avoids memory move.



reply via email to

[Prev in Thread] Current Thread [Next in Thread]