From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!.POSTED!not-for-mail From: Andreas Politz Newsgroups: gmane.emacs.devel Subject: Re: Overlays as an AA-tree Date: Fri, 03 Feb 2017 09:49:20 +0100 Message-ID: <87fujv64mn.fsf@hochschule-trier.de> References: <87d1jylv43.fsf@fastmail.com> NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: text/plain X-Trace: blaine.gmane.org 1486111897 3967 195.159.176.226 (3 Feb 2017 08:51:37 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Fri, 3 Feb 2017 08:51:37 +0000 (UTC) User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/25.1 (gnu/linux) To: emacs-devel@gnu.org Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Fri Feb 03 09:51:34 2017 Return-path: Envelope-to: ged-emacs-devel@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by blaine.gmane.org with esmtp (Exim 4.84_2) (envelope-from ) id 1cZZaf-0000uN-SQ for ged-emacs-devel@m.gmane.org; Fri, 03 Feb 2017 09:51:33 +0100 Original-Received: from localhost ([::1]:60900 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1cZZal-0003l8-Cv for ged-emacs-devel@m.gmane.org; Fri, 03 Feb 2017 03:51:39 -0500 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:36966) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1cZZZY-0003jL-Fu for emacs-devel@gnu.org; Fri, 03 Feb 2017 03:50:26 -0500 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1cZZZV-00082v-FK for emacs-devel@gnu.org; Fri, 03 Feb 2017 03:50:24 -0500 Original-Received: from gateway-a.fh-trier.de ([143.93.54.181]:45819) by eggs.gnu.org with esmtps (TLS1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1cZZZV-00080p-83 for emacs-devel@gnu.org; Fri, 03 Feb 2017 03:50:21 -0500 X-Virus-Scanned: by Amavisd-new + McAfee uvscan + ClamAV [Rechenzentrum Hochschule Trier (RZ/HT)] Original-Received: from localhost (ip5f5bdfbc.dynamic.kabel-deutschland.de [95.91.223.188]) (using TLSv1 with cipher AES256-SHA (256/256 bits)) (No client certificate requested) (Authenticated sender: politza) by gateway-a.fh-trier.de (Postfix) with ESMTPSA id 2FA60179AC21 for ; Fri, 3 Feb 2017 09:49:21 +0100 (CET) DKIM-Signature: v=1; a=rsa-sha1; c=simple/simple; d=hochschule-trier.de; s=default; t=1486111761; bh=OczwDxrRYkTGT7V4DNlj3dshiBc=; h=From:To:Subject:References:Date:In-Reply-To:Message-ID: MIME-Version:Content-Type; b=rFfU1/84f0Hckn4OR/MH4go9gRjmVuZpP+bUlg0PhI1EJ+8slbPbdB+csK+enzuqR ZVaJu7r2ve/ISnHLAhMd/PAGNT0NV0K5SN44ecZ7fJ35XZl3Vqm/4xV6bVmpFqoHN/ X5Gs50VHL5ivriEcXGaeptYsdkawm8vLcX3Zpw6o= In-Reply-To: <87d1jylv43.fsf@fastmail.com> (Joakim Jalap's message of "Tue, 20 Sep 2016 12:32:28 +0200") X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6.x [fuzzy] X-Received-From: 143.93.54.181 X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.21 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" Xref: news.gmane.org gmane.emacs.devel:211918 Archived-At: Hi, I'm interested in this problem as well. I want to clarify something: Overlays have begin B and end E positions each with a flag (front-advance resp. rear-advance). These positions may change in one of 3 ways: 1. move-overlay is called 2. Text of length L is inserted at position P. Here the flags decide whether begin B resp. end E will move or not in the literal border-cases P = B resp. P = E . 3. Text of length L is deleted beginning at position P. Is this the correct model ? Someone mentioned in a different thread, that occasionally we may have B > E. How does this happen ? --- I think if a tree is sorted by begin only and the front-advance of every node is either true or false, the tree can't possibly become disordered by insertion/deletion operations. Further the disorder exists at most for nodes having the same begin but different front-advances after an insert at begin was performed. This suggests using two trees or at least limits the amount of nodes having to be reinserted after a change. --- Anyway, my attempt is to use the RB-tree from alloc.c and add some node-attributes: 1. max_end :: Holds the maximum E value of this node's sub-tree and bounds the complexity of queries in terms of their result, i.e. number of intervals. (The so called ,,Augmented Tree'' approach to Interval Trees (which is actually just an example for how to augment a tree in the book).) 2. offset :: The amount of shift of this node's sub-tree relative to its parent and applying to all position values (begin,end,max_end). This should limit the time it takes to modify the tree after an insertion/deletion in terms of intersecting intervals. 3. modified_tick :: Essentially just a flag, indicating that all parent offsets have been applied to this node. This would allow for constant time access on B/E for repeated accesses. I'm essentially building an overlay model and if it works, will try to plug it into the Editor. -ap