Re: About intervals

[Helmut Eller <eller.helmut@gmail.com>]

On Tue, Mar 19 2013, Xue Fuqiao wrote:

> In (info "(elisp) Not Intervals"), it says that some editors let the
> user specify "intervals" within the text.  But it doesn't explain what
> "intervals" are.  I'm new to this concept.
>
> I searched "interval and property" and "editor interval" in the list
> archives and web but didn't get anything that looked promising.
>
> Can I get a pointer to information on this concept?  Sorry if it's off
> topic here.

Intervals are used to represent text-properties.  A buffer or string
that has text-properties also carries an non-empty interval tree.  An
interval describes a region in the buffer and the text-properties (a
plist) for that region.  A naive implementation could use two markers to
represent an interval but that would not scale to large numbers of
intervals because each insert or delete operation needs to update all
markers.  Emacs uses an interval tree (a kind of balanced tree that
exploits the ordering of intervals, see Wikipedia article for "Interval
tree") that scales much better.

The function text-properties-at traverses the interval tree to find the
interval that covers that position and returns the intervals plist.  The
function add-text-properties creates new intervals or splits existing
intervals and possibly rebalances the tree.

AFAIK overlays are actually implemented with a pair of markers.

I think RMS had some dispute with Lucid people whether the interval tree
is good idea; it was one reason why XEmacs was forked and I think it's
the reason why this is mentioned in the manual at all.

Helmut