About intervals

About intervals

[Xue Fuqiao]

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.

-- 
Xue Fuqiao
http://www.gnu.org/software/emacs/

Re: About intervals

[Helmut Eller]

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

Re: About intervals

[Eli Zaretskii]

> Date: Tue, 19 Mar 2013 19:18:05 +0800
> From: Xue Fuqiao <xfq.free@gmail.com>
> 
> 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.

Why do you expect the Emacs manual describe "other editors"? ;-)

Anyway, I think it is alluding to XEmacs's "extents".  If you want to
know what that is, read XEmacs manuals.

Re: About intervals

[Xue Fuqiao]

Ah, I see.  Thank you, Eli and Helmut.

-- 
Happy birthday, GNU Emacs!
1985-2013

Re: About intervals

[Stefan Monnier]

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

I think the reason is related but different:
while text-properties are implemented with a balanced tree whose
name in the C code is "interval", the manual's reference to intervals is
for things like overlays and extents, whereas from that point of view
text-properties do not behave like intervals:

When you use put-text-property, you just add that property to each
char in the specified range.  Whereas when you use an overlay or an
extent you put the property on the interval that contains those chars.

That looks very similar, but if you later insert a char somewhere in the
middle, this char will necessarily be part of the interval, whereas it
will not have the text-property that was set to the surrounding chars
(unless you specifically ask to inherit those properties, e.g. via
insert-and-inherit).

Other differences are that you can query the set of intervals (extents,
or overlays) that cover a particular position in the buffer, but that
same question is meaningless for text-properties.  At best you can find
the neighboring chars whose property has the same value.


        Stefan

Re: About intervals

[Xue Fuqiao]

On Tue, 19 Mar 2013 20:24:08 -0400
Stefan Monnier <monnier@iro.umontreal.ca> wrote:

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

> I think the reason is related but different:

I think so, too.

> while text-properties are implemented with a balanced tree whose
> name in the C code is "interval", the manual's reference to intervals is
> for things like overlays and extents, whereas from that point of view
> text-properties do not behave like intervals:

The manual's references to intervals are both concepts.  See:
(info "(elisp) Garbage Collection")
(info "(elisp) Memory Usage")
(info "(elisp) Buffer Internals")

But AFAIK there are not any disambiguation about these two meanings in
Emacs manuals.

> When you use put-text-property, you just add that property to each
> char in the specified range.  Whereas when you use an overlay or an
> extent you put the property on the interval that contains those chars.
> 
> That looks very similar, but if you later insert a char somewhere in the
> middle, this char will necessarily be part of the interval, whereas it
> will not have the text-property that was set to the surrounding chars
> (unless you specifically ask to inherit those properties, e.g. via
> insert-and-inherit).
> 
> Other differences are that you can query the set of intervals (extents,
> or overlays) that cover a particular position in the buffer, but that
> same question is meaningless for text-properties.  At best you can find
> the neighboring chars whose property has the same value.

I think overlays often cause some problems (although they are minor).
E.g.,
http://lists.gnu.org/archive/html/emacs-devel/2005-11/msg01346.html

So I don't use it much, anyway.

-- 
Happy birthday, GNU Emacs!
1985-2013