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     ! 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.