From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Alin Soare Newsgroups: gmane.emacs.devel Subject: line buffer as Red Black Trees instead of linear Date: Thu, 15 May 2014 17:33:33 +0300 Message-ID: NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: multipart/alternative; boundary=047d7b2e12db7b11be04f9712efe X-Trace: ger.gmane.org 1400164427 3557 80.91.229.3 (15 May 2014 14:33:47 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Thu, 15 May 2014 14:33:47 +0000 (UTC) To: emacs-devel@gnu.org Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Thu May 15 16:33:40 2014 Return-path: Envelope-to: ged-emacs-devel@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 1Wkwj5-0003oD-R5 for ged-emacs-devel@m.gmane.org; Thu, 15 May 2014 16:33:40 +0200 Original-Received: from localhost ([::1]:58503 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Wkwj5-0006rU-EQ for ged-emacs-devel@m.gmane.org; Thu, 15 May 2014 10:33:39 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:59010) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Wkwj1-0006rM-OS for emacs-devel@gnu.org; Thu, 15 May 2014 10:33:36 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1Wkwj0-0000c2-BC for emacs-devel@gnu.org; Thu, 15 May 2014 10:33:35 -0400 Original-Received: from mail-ig0-x22c.google.com ([2607:f8b0:4001:c05::22c]:46053) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Wkwj0-0000b6-40 for emacs-devel@gnu.org; Thu, 15 May 2014 10:33:34 -0400 Original-Received: by mail-ig0-f172.google.com with SMTP id uy17so7988179igb.5 for ; Thu, 15 May 2014 07:33:33 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:date:message-id:subject:from:to:content-type; bh=GrLrYACPp6+o3qffIlyWj4YcKBJdnyWP4vV1Dbc6/VA=; b=IHEjQa4OCXQfqcTniOIBkvdY74VuDZXGXF1fPK30iPbcEBwGe2lqvcGbOdfYp/kDa9 KvzjnDT+osRoVpDF/SmJDySlnzKz1/7w+FVfHP5CyOCn5loE4cKRUW8uOgB35HpqbO9r NNsyMjM2Za+Z8SaxYMFEf1oL4ofex+n1pLQT9MMzV93LKsUtZOHSbjkGzW2/XwwOL6Ux kV4viQBmoo2PB5pRiHU/etY4tArlA+v6WZ1sYF1wpi7i8AeLGuyFiebBgvMGi+iWWSGW +eJUkxJ7/X2X+DxLrLU3AcB7l+E8C1NntJHSymL+ORIWrK0JBCfywoOiGyc3rRibeGY0 U/Hg== X-Received: by 10.50.131.138 with SMTP id om10mr46004388igb.25.1400164413264; Thu, 15 May 2014 07:33:33 -0700 (PDT) Original-Received: by 10.43.142.70 with HTTP; Thu, 15 May 2014 07:33:33 -0700 (PDT) X-detected-operating-system: by eggs.gnu.org: Error: Malformed IPv6 address (bad octet value). X-Received-From: 2607:f8b0:4001:c05::22c X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Original-Sender: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.devel:171853 Archived-At: --047d7b2e12db7b11be04f9712efe Content-Type: text/plain; charset=UTF-8 Hi, I am writing a tutorial about red-black trees, in which I present an recursive formula that I deduced for left leaning red-black trees . I implemented it in java. In emacs the red-black trees are already used in this moment for keeping the memory segments of lisp symbols. An application of red-black trees in emacs, which would drastically improve the redisplay system, would be to keep the text of each line as a rbt. I give a rough explanation of the basic operations, without having studied recently the details of buffer implementation. In emacs the buffers text contents is kept in memory linearly at the address buffer_text->beg. One could keep as well the text from each line of the buffer into a red-black tree. Each node will contain * a buffer with a part of the text (for gap an empty text) * a pointer to the next node, such that the search operation to be done in constant time * the number of characters of text are on the nodes at left of the current node The speed of the basic operations will be so: 1. search for text (remain the same) -- it will remain linear as it is now. 2. seach for a given offset into a line (almost no change) -- this will be logarithmic , logarithm of the length of the line -- in this moment I think it's constant time, so no visible change 3. insert a new gap (major improvement) -- this will be logarithmic in time, and no need to move memory segments. To insert a new gap at offset X of a line, we start at the root, if X > number of characters at the left of root we go to right, ifnot, we either move to left or insert a new node and move the current node to the left of the new node. 4. insert a new text into the buffer. (the same) -- This will insert into the gap from the point, and when the gap is filled, a new gap is created. 5. remove text. -- this supposes a lot of things, like re-checking the values of all values of properties at the left and right, so many changes, but it will remain as fast as in this moment. 6. merging 2 lines means to combine the text from 2 red-black trees, and this is done in constant time, with no need to move memory segments. The text properties, overlays, markers, etc will remain almost the same as now. Or they can be moved on the node of a corresponding text. In this moment these are kept into lists, but one can move the given properties into the node that keeps the corresponding text. The whole buffer would be encoded as a list of lines, and each line is encoded as a red-black tree, as I described. This will make fast operations involving the gap, the red-black trees are quite easy to implement, but I cannot see now the bad side effects involved by such a change. The major improvement would be the redisplay. --047d7b2e12db7b11be04f9712efe Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
Hi,

I am writing a tutorial about red-b= lack trees, in which I present an recursive formula that I deduced for left= leaning red-black trees . I implemented it in java. In emacs the red-black= trees are already used in this moment for keeping the=C2=A0=C2=A0memory se= gments of lisp symbols.

An application of red-black trees in emacs, which would= drastically improve the redisplay system, would be to keep the text of eac= h line as a rbt.

I give a rough explanation of the= basic operations, without having studied recently the details of buffer im= plementation.

In emacs the buffers text contents is kept in memory linearly at the addres= s=C2=A0buffer_text->beg.

One could keep as well the text from each line of the b= uffer into a red-black tree.

Each node will contai= n

* a buffer with a part of the text (for gap an e= mpty text)
* a pointer to the next node, such that the search operation to be don= e in constant time
* the number of characters of text are on the = nodes at left of the current node


The speed of the basic operations will be so:

1. search for text (remain the same)
=C2=A0 = =C2=A0-- it will remain linear as it is now.

2. se= ach for a given offset into a line (almost no change)
=C2=A0 =C2= =A0-- this will be logarithmic , logarithm of the length of the line
=C2=A0 =C2=A0-- in this moment I think it's constant time, so no v= isible change

3. insert a new gap (major improveme= nt)
=C2=A0 =C2=A0-- this will be logarithmic in time, and no need= to move memory segments. To insert a new gap at offset X of a line, we sta= rt at the root, if X > number of characters at the left of root we go to= right, ifnot, we either move to left or insert a new node and move the cur= rent node to the left of the new node.

4. insert a new text into the buffer. (the same)
<= div>=C2=A0 =C2=A0-- This will insert into the gap from the point, and when = the gap is filled, a new gap is created.

5. remove= text.
=C2=A0 =C2=A0-- this supposes a lot of things, like re-checking the va= lues of all values of properties at the left and right, so many changes, bu= t it will remain as fast as in this moment.

6. mer= ging 2 lines means to combine the text from 2 red-black trees, and this is = done in constant time, with no need to move memory segments.

The text properties, overlays, markers, etc = will remain almost the same as now. Or they can be moved on the node of a c= orresponding text. In this moment these are kept into lists, but one can mo= ve the given properties into the node that keeps the corresponding text.

The whole buffer would be encoded as a list of li= nes, and each line is encoded as a red-black tree, as I described.

This will make fast operations involving the gap, the r= ed-black trees are quite easy to implement, but I cannot see now the bad si= de effects involved by such a change. The major improvement would be the re= display.





=




--047d7b2e12db7b11be04f9712efe--