Re: Interval tree

["Stefan Monnier" <monnier+gnu/emacs@rum.cs.yale.edu>]

> I am trying to understand how are text organized in emacs,
> I come across this data structure call interval tree, which
> is built on top of a buffer, can anyone point me to any paper
> which talks about what an interval tree is and how this interval
> concepts is used in emacs? thanks

Please don't use HTML for such email (and complain to the author of
the software you use that it should not use HTML if the text doesn't
use any attribute annotation).

As for the actual question: I don't think there's any paper about it.
It's just a balanced binary tree used to implement text-properties
(which associate with each buffer location a set of properties).
Since text-properties tend to stay the same over several consecutive
chars, the mapping only records the place where those properties
change: each node of the tree corresponds to an interval that starts
at a particular position and spans some number of chars.


	Stefan