Return to INTERVAL.IDEAS CVS log

Up to [Apple XNU] / GNUtools / emacs / etc

Annotation of GNUtools/emacs/etc/INTERVAL.IDEAS, revision 1.1.1.1

1.1       root        1: This idea comes from Andrew.  The basic part is to represent a division
                      2: of the buffer into disjoint intervals by means of a binary tree.  Each
                      3: interval has one node.  The tree has the effect of a large ordered
                      4: collection of markers, but no Lisp_Marker objects appear in the tree.
                      5: 
                      6: Each node has two subnodes, a left and a right, each of which can be
                      7: nil instead.  The subnodes' intervals are disjoint from their parent's
                      8: interval--the tree structure is for binary searching.
                      9: 
                     10: Each node in the tree is implicitly associated with a region of the
                     11: buffer, but I don't think it actually stores the positions; I think it
                     12: has the length of that node, or perhaps its own length and separately
                     13: the length of it plus all its subnodes.
                     14: 
                     15: I forget the details of this, but the idea is that you can figure out
                     16: the position of a node, or find the node containing a position, by
                     17: examining just its superiors in the tree, and you can also update the
                     18: tree for changes in the buffer by tracing just one path down the tree.
                     19: So the amount of work for nearly any operation goes with the log of
                     20: the number of intervals.
                     21: 
                     22: If it is desirable to be able to subdivide the intervals, each interval
                     23: can have another such tree dividing it into disjoint subintervals.  And
                     24: subintervals can have trees, too.  So it becomes a tree of trees.
                     25: 
                     26: The idea is to associate an alist with each interval or subinterval.
                     27: The complete alist associated with any spot is the append of the
                     28: alists of the containing intervals at all levels of subdivision,
                     29: smallest ones first.  It would also be useful to get the bounds of the
                     30: innermost interval.

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.