home *** CD-ROM | disk | FTP | other *** search
/ Fresh Fish 4 / FreshFish_May-June1994.bin / bbs / gnu / emacs-18.59-bin.lha / lib / emacs / 18.59 / etc / INTERVAL.IDEAS < prev    next >
Text File  |  1990-07-29  |  2KB  |  31 lines
  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.
  31.