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 13:44:42 +0100 Message-ID: <87vasr5tqd.fsf@hochschule-trier.de> References: <87d1jylv43.fsf@fastmail.com> <87fujv64mn.fsf@hochschule-trier.de> <87fujvpkzc.fsf@fastmail.com> NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: text/plain X-Trace: blaine.gmane.org 1486125922 31198 195.159.176.226 (3 Feb 2017 12:45:22 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Fri, 3 Feb 2017 12:45:22 +0000 (UTC) User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/25.1 (gnu/linux) Cc: emacs-devel@gnu.org To: Joakim Jalap Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Fri Feb 03 13:45:15 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 1cZdEo-0007kA-Ns for ged-emacs-devel@m.gmane.org; Fri, 03 Feb 2017 13:45:14 +0100 Original-Received: from localhost ([::1]:34250 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1cZdEr-0002in-5m for ged-emacs-devel@m.gmane.org; Fri, 03 Feb 2017 07:45:17 -0500 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:37729) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1cZdEe-0002cw-1x for emacs-devel@gnu.org; Fri, 03 Feb 2017 07:45:06 -0500 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1cZdEY-000396-GH for emacs-devel@gnu.org; Fri, 03 Feb 2017 07:45:04 -0500 Original-Received: from gateway-a.fh-trier.de ([143.93.54.181]:57505) by eggs.gnu.org with esmtps (TLS1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1cZdEX-00035w-Vq for emacs-devel@gnu.org; Fri, 03 Feb 2017 07:44:58 -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 D8EC2179ABCC; Fri, 3 Feb 2017 13:44:42 +0100 (CET) DKIM-Signature: v=1; a=rsa-sha1; c=simple/simple; d=hochschule-trier.de; s=default; t=1486125883; bh=49bgmhy+/MkbgbWadRBBoxV6GfU=; h=From:To:Cc:Subject:References:Date:In-Reply-To:Message-ID: MIME-Version:Content-Type; b=KXILE0LefUyLoqLOvMo4O/xDP0+tTp9vfmr4td3tn5WJBCOqn4fjgwyYxNHWkpbMC 4B7DYROcTECiRR1N5+C5SBa9Ct77JKjNWt0CSJqZgDx/tqeopU1dc5TWu1E8gNyz2N fXUoYqIkSotN1LBKRlgBSaThhBbeLue9u4yfDLcU= In-Reply-To: <87fujvpkzc.fsf@fastmail.com> (Joakim Jalap's message of "Fri, 03 Feb 2017 12:33:27 +0100") 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:211927 Archived-At: Joakim Jalap writes: > I thought I might chime in since I've been bashing my head againt this > for a while now :) Much appreciated. > There is also the case of a replace, [...] > >> [...] occasionally we may have B > E. How does this happen ? > > I think it happens in case 2 above [...] See also the comments at > adjust_markers_for_insert in [...] That's useful information. >> I think if a tree is sorted by begin only [...] the tree can't possibly become >> disordered [...] > > But if the tree is sorted by begin only we can have multiple overlays in > the same position, how does that work? [...] Why should that be a problem ? A search-tree may contain some key multiple times. The question is whether this is useful. I don't think it is in this case, because including end in the comparison does not help with finding all overlays intersecting some position or interval (i.e. it does not allow pruning some sub-trees). It would be useful, e.g. if we were going to search for an overlay starting at B1 and ending at E1, but I don't see were we needed this. > > [...] but then almost all the buffer text is deleted > so that every overlay ends up being from 6 to 6! No problem. Simply write a NEWS entry and declare it a new feature. >> This suggests using two trees [...] > > Hm I don't understand this. How would we use two trees? If I'm right, we *could* use one tree for front-advance overlays and one for non-front-advance ones, such that these tree won't ever become unordered by insertion/deletion of text. > [...] it only affects those overlays with an endpoint exactly at the > point of insertion... [...] Whether it'll mess with the order depends on the comparison function ;-) . -ap