From mboxrd@z Thu Jan 1 00:00:00 1970 Path: main.gmane.org!not-for-mail From: "Stefan Monnier" Newsgroups: gmane.emacs.devel Subject: Re: Interval tree Date: Wed, 17 Jul 2002 09:13:17 -0400 Sender: emacs-devel-admin@gnu.org Message-ID: <200207171313.g6HDDHY02385@rum.cs.yale.edu> References: NNTP-Posting-Host: localhost.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Trace: main.gmane.org 1026911791 26826 127.0.0.1 (17 Jul 2002 13:16:31 GMT) X-Complaints-To: usenet@main.gmane.org NNTP-Posting-Date: Wed, 17 Jul 2002 13:16:31 +0000 (UTC) Cc: emacs-devel@gnu.org Return-path: Original-Received: from quimby.gnus.org ([80.91.224.244]) by main.gmane.org with esmtp (Exim 3.33 #1 (Debian)) id 17UofO-0006yZ-00 for ; Wed, 17 Jul 2002 15:16:30 +0200 Original-Received: from fencepost.gnu.org ([199.232.76.164]) by quimby.gnus.org with esmtp (Exim 3.12 #1 (Debian)) id 17Uoqo-00064t-00 for ; Wed, 17 Jul 2002 15:28:18 +0200 Original-Received: from localhost ([127.0.0.1] helo=fencepost.gnu.org) by fencepost.gnu.org with esmtp (Exim 3.35 #1 (Debian)) id 17UodG-0004Dk-00; Wed, 17 Jul 2002 09:14:18 -0400 Original-Received: from rum.cs.yale.edu ([128.36.229.169]) by fencepost.gnu.org with esmtp (Exim 3.35 #1 (Debian)) id 17UocK-0004Cx-00 for ; Wed, 17 Jul 2002 09:13:20 -0400 Original-Received: (from monnier@localhost) by rum.cs.yale.edu (8.11.6/8.11.6) id g6HDDHY02385; Wed, 17 Jul 2002 09:13:17 -0400 X-Mailer: exmh version 2.4 06/23/2000 with nmh-1.0.4 Original-To: "Freddy Chik" Errors-To: emacs-devel-admin@gnu.org X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.0.11 Precedence: bulk List-Help: List-Post: List-Subscribe: , List-Id: Emacs development discussions. List-Unsubscribe: , List-Archive: Xref: main.gmane.org gmane.emacs.devel:5829 X-Report-Spam: http://spam.gmane.org/gmane.emacs.devel:5829 > 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