From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Helmut Eller Newsgroups: gmane.emacs.help Subject: Re: About intervals Date: Tue, 19 Mar 2013 16:17:02 +0100 Message-ID: References: NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain X-Trace: ger.gmane.org 1363717928 16816 80.91.229.3 (19 Mar 2013 18:32:08 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Tue, 19 Mar 2013 18:32:08 +0000 (UTC) To: help-gnu-emacs@gnu.org Original-X-From: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane.org@gnu.org Tue Mar 19 19:32:34 2013 Return-path: Envelope-to: geh-help-gnu-emacs@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1UI1Kr-0008U5-KL for geh-help-gnu-emacs@m.gmane.org; Tue, 19 Mar 2013 19:32:33 +0100 Original-Received: from localhost ([::1]:58199 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1UI1KU-0006UP-Fp for geh-help-gnu-emacs@m.gmane.org; Tue, 19 Mar 2013 14:32:10 -0400 X-Received: by 10.180.19.132 with SMTP id f4mr829274wie.2.1363706247117; Tue, 19 Mar 2013 08:17:27 -0700 (PDT) Original-Path: usenet.stanford.edu!19no10712535wij.1!news-out.google.com!g1ni75364wig.0!nntp.google.com!feeder1.cambriumusenet.nl!82.197.223.108.MISMATCH!feeder2.cambriumusenet.nl!feed.tweaknews.nl!217.188.199.168.MISMATCH!takemy.news.telefonica.de!feedme.news.telefonica.de!telefonica.de!newsfeeder.ewetel.de!border3.nntp.ams.giganews.com!Xl.tags.giganews.com!border1.nntp.ams.giganews.com!nntp.giganews.com!local2.nntp.ams.giganews.com!nntp.kpnqwest.it!news.kpnqwest.it.POSTED!not-for-mail Original-NNTP-Posting-Date: Tue, 19 Mar 2013 10:17:01 -0500 Original-Newsgroups: gnu.emacs.help User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.3.50 (gnu/linux) Cancel-Lock: sha1:2uz+Wy4wmVfz1zRUPy3h6+MJmtc= Original-Lines: 34 X-Usenet-Provider: http://www.giganews.com Original-NNTP-Posting-Host: 212.46.172.127 Original-X-Trace: sv3-iYByhPjYFdAYJoH6nomNEq1WObLuIf5OSl1xbFk2o0Ugm06USSeFARP8E4mdSY/ArSj9id8e+imP0Ca!15/lmmwZKGf1SmF0Zy7ixKv802MAJXiXW532+c9c6EYEXk4eT8JP3DKlR2VEhtc= X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly X-Postfilter: 1.3.40 X-Original-Bytes: 2591 Original-Xref: usenet.stanford.edu gnu.emacs.help:197317 X-Mailman-Approved-At: Tue, 19 Mar 2013 14:31:53 -0400 X-BeenThere: help-gnu-emacs@gnu.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: Users list for the GNU Emacs text editor List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane.org@gnu.org Original-Sender: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.help:89596 Archived-At: 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