unofficial mirror of help-gnu-emacs@gnu.org
 help / color / mirror / Atom feed
* About intervals
@ 2013-03-19 11:18 Xue Fuqiao
  2013-03-19 17:04 ` Eli Zaretskii
  0 siblings, 1 reply; 6+ messages in thread
From: Xue Fuqiao @ 2013-03-19 11:18 UTC (permalink / raw)
  To: help-gnu-emacs

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/



^ permalink raw reply	[flat|nested] 6+ messages in thread

* Re: About intervals
       [not found] <mailman.22454.1363691901.855.help-gnu-emacs@gnu.org>
@ 2013-03-19 15:17 ` Helmut Eller
  2013-03-19 22:41   ` Xue Fuqiao
  2013-03-20  0:24   ` Stefan Monnier
  0 siblings, 2 replies; 6+ messages in thread
From: Helmut Eller @ 2013-03-19 15:17 UTC (permalink / raw)
  To: help-gnu-emacs

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


^ permalink raw reply	[flat|nested] 6+ messages in thread

* Re: About intervals
  2013-03-19 11:18 About intervals Xue Fuqiao
@ 2013-03-19 17:04 ` Eli Zaretskii
  0 siblings, 0 replies; 6+ messages in thread
From: Eli Zaretskii @ 2013-03-19 17:04 UTC (permalink / raw)
  To: help-gnu-emacs

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



^ permalink raw reply	[flat|nested] 6+ messages in thread

* Re: About intervals
  2013-03-19 15:17 ` Helmut Eller
@ 2013-03-19 22:41   ` Xue Fuqiao
  2013-03-20  0:24   ` Stefan Monnier
  1 sibling, 0 replies; 6+ messages in thread
From: Xue Fuqiao @ 2013-03-19 22:41 UTC (permalink / raw)
  To: help-gnu-emacs

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

-- 
Happy birthday, GNU Emacs!
1985-2013



^ permalink raw reply	[flat|nested] 6+ messages in thread

* Re: About intervals
  2013-03-19 15:17 ` Helmut Eller
  2013-03-19 22:41   ` Xue Fuqiao
@ 2013-03-20  0:24   ` Stefan Monnier
  2013-03-20 10:25     ` Xue Fuqiao
  1 sibling, 1 reply; 6+ messages in thread
From: Stefan Monnier @ 2013-03-20  0:24 UTC (permalink / raw)
  To: help-gnu-emacs

> 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




^ permalink raw reply	[flat|nested] 6+ messages in thread

* Re: About intervals
  2013-03-20  0:24   ` Stefan Monnier
@ 2013-03-20 10:25     ` Xue Fuqiao
  0 siblings, 0 replies; 6+ messages in thread
From: Xue Fuqiao @ 2013-03-20 10:25 UTC (permalink / raw)
  To: help-gnu-emacs

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



^ permalink raw reply	[flat|nested] 6+ messages in thread

end of thread, other threads:[~2013-03-20 10:25 UTC | newest]

Thread overview: 6+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2013-03-19 11:18 About intervals Xue Fuqiao
2013-03-19 17:04 ` Eli Zaretskii
     [not found] <mailman.22454.1363691901.855.help-gnu-emacs@gnu.org>
2013-03-19 15:17 ` Helmut Eller
2013-03-19 22:41   ` Xue Fuqiao
2013-03-20  0:24   ` Stefan Monnier
2013-03-20 10:25     ` Xue Fuqiao

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).