Interval tree

Interval tree

[Freddy Chik]

[-- Attachment #1: Type: text/plain, Size: 783 bytes --]

Hi guys

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

Yu Fai Freddy Chik 
4A Computer Science / Combinatorics and Optimization
University of Waterloo
Waterloo, ON
------------------------------------------------------------ 
-- Computer Science is the study of algorithmic processes --
-- that limit the amount of time one has to perform daily --
----- activities such as sleeping, eating, exercising, ----- 
---- bathing, dating and improving ones social skills. ----- 
------------------------------------------------------------ 

[-- Attachment #2: Type: text/html, Size: 1283 bytes --]

Re: Interval tree

[Stefan Monnier]

> 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

Re: Interval tree

[Freddy Chik]

it sounds like text properties are things like fonts?

I jumped into places such as lisp.h, buffer.h, textprop.c, hoping to find a
definition for this thing, but all I got is a Lisp_Object plist (even for
functions that adds to the property list or removes from it), where is this
mysterious text property structure described?

Yu Fai Freddy Chik
4A Computer Science / Combinatorics and Optimization
University of Waterloo
Waterloo, ON
------------------------------------------------------------
-- Computer Science is the study of algorithmic processes --
-- that limit the amount of time one has to perform daily --
----- activities such as sleeping, eating, exercising, -----
---- bathing, dating and improving ones social skills. -----
------------------------------------------------------------
----- Original Message -----
From: "Stefan Monnier" <monnier+gnu/emacs@rum.cs.yale.edu>
To: "Freddy Chik" <yffchik_ura@hotmail.com>
Cc: <emacs-devel@gnu.org>
Sent: Wednesday, July 17, 2002 9:13 AM
Subject: Re: Interval tree


> > 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
>
>
> _______________________________________________
> Emacs-devel mailing list
> Emacs-devel@gnu.org
> http://mail.gnu.org/mailman/listinfo/emacs-devel
>

Re: Interval tree

[Richard Stallman]

    it sounds like text properties are things like fonts?

We store many kinds of things on text properties, including font
specifications.

    I jumped into places such as lisp.h, buffer.h, textprop.c, hoping to find a
    definition for this thing, but all I got is a Lisp_Object plist (even for
    functions that adds to the property list or removes from it), where is this
    mysterious text property structure described?

The interval data structure is not precisely defined anywhere, but don't
worry about it--you don't need to do anything at that low a level.
You can do all this work at one level up, where the text property list
is just a standard plist (property value property value...).

Re: Interval tree

[Freddy Chik]

I am trying to put in another data structure to make line searching faster,
which must be maintained during every insert/delete operation.  It looks
like interval tree is not something I should touch.  It looks like all those
functions (e.g. scan_newline) in search.c and insert functions in insdel.c
are things I should take a deeper look at, does that sound right?

Yu Fai Freddy Chik
4A Computer Science / Combinatorics and Optimization
University of Waterloo
Waterloo, ON
------------------------------------------------------------
-- Computer Science is the study of algorithmic processes --
-- that limit the amount of time one has to perform daily --
----- activities such as sleeping, eating, exercising, -----
---- bathing, dating and improving ones social skills. -----
------------------------------------------------------------
----- Original Message -----
From: "Richard Stallman" <rms@gnu.org>
To: <yffchik_ura@hotmail.com>
Cc: <monnier+gnu/emacs@rum.cs.yale.edu>; <emacs-devel@gnu.org>
Sent: Thursday, July 18, 2002 5:13 PM
Subject: Re: Interval tree


>     it sounds like text properties are things like fonts?
>
> We store many kinds of things on text properties, including font
> specifications.
>
>     I jumped into places such as lisp.h, buffer.h, textprop.c, hoping to
find a
>     definition for this thing, but all I got is a Lisp_Object plist (even
for
>     functions that adds to the property list or removes from it), where is
this
>     mysterious text property structure described?
>
> The interval data structure is not precisely defined anywhere, but don't
> worry about it--you don't need to do anything at that low a level.
> You can do all this work at one level up, where the text property list
> is just a standard plist (property value property value...).
>
> _______________________________________________
> Emacs-devel mailing list
> Emacs-devel@gnu.org
> http://mail.gnu.org/mailman/listinfo/emacs-devel
>

Re: Interval tree

[Richard Stallman]

    I am trying to put in another data structure to make line searching faster,
    which must be maintained during every insert/delete operation.

This sounds like a lot of complexity.  Is it worth while?
I doubt we would want to install it.  Searching is pretty fast nowadays.

Re: Interval tree

[Thien-Thi Nguyen]

Richard Stallman <rms@gnu.org> writes:

       I am trying to put in another data structure to make line searching faster,
       which must be maintained during every insert/delete operation.

   This sounds like a lot of complexity.  Is it worth while?
   I doubt we would want to install it.  Searching is pretty fast nowadays.

what in the line is being searched?

thi