From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!.POSTED!not-for-mail From: Joakim Jalap Newsgroups: gmane.emacs.devel Subject: Re: Overlays as an AA-tree Date: Fri, 03 Feb 2017 15:11:49 +0100 Message-ID: <877f57pdne.fsf@fastmail.com> References: <87d1jylv43.fsf@fastmail.com> <87fujv64mn.fsf@hochschule-trier.de> <87fujvpkzc.fsf@fastmail.com> <87vasr5tqd.fsf@hochschule-trier.de> NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: text/plain X-Trace: blaine.gmane.org 1486131164 31006 195.159.176.226 (3 Feb 2017 14:12:44 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Fri, 3 Feb 2017 14:12:44 +0000 (UTC) User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/26.0.50 (berkeley-unix) Cc: emacs-devel@gnu.org To: Andreas Politz Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Fri Feb 03 15:12:40 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 1cZebM-0007kL-LR for ged-emacs-devel@m.gmane.org; Fri, 03 Feb 2017 15:12:36 +0100 Original-Received: from localhost ([::1]:34964 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1cZebS-0004Mv-8p for ged-emacs-devel@m.gmane.org; Fri, 03 Feb 2017 09:12:42 -0500 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:34057) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1cZeah-0004LI-Po for emacs-devel@gnu.org; Fri, 03 Feb 2017 09:11:57 -0500 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1cZead-0006uE-Qr for emacs-devel@gnu.org; Fri, 03 Feb 2017 09:11:55 -0500 Original-Received: from out1-smtp.messagingengine.com ([66.111.4.25]:48175) by eggs.gnu.org with esmtps (TLS1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1cZead-0006tQ-L2 for emacs-devel@gnu.org; Fri, 03 Feb 2017 09:11:51 -0500 Original-Received: from compute4.internal (compute4.nyi.internal [10.202.2.44]) by mailout.nyi.internal (Postfix) with ESMTP id E65112078C; Fri, 3 Feb 2017 09:11:50 -0500 (EST) Original-Received: from frontend1 ([10.202.2.160]) by compute4.internal (MEProxy); Fri, 03 Feb 2017 09:11:50 -0500 DKIM-Signature: v=1; a=rsa-sha1; c=relaxed/relaxed; d=fastmail.com; h=cc :content-type:date:from:in-reply-to:message-id:mime-version :references:subject:to:x-me-sender:x-me-sender:x-sasl-enc :x-sasl-enc; s=mesmtp; bh=tKROo1YVi7sKfZiCdn8I1LXAxJY=; b=ynG/Lz EnbylvoWcvYyJQxGg/n43T3CWpuPB8TfOrbWUqBl+ldT65jkYtroVENxdt7WY5xY Ec10ffGZGu0CKWiJvfJgWKQJ4FPw0Sz2fY3p31wyUMdhCRmvJlcxhIUB+F4sgPhM Z4rE2yqf9iuu6UM9I0yCWS4Dt0741dxsDDZnA= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed/relaxed; d= messagingengine.com; h=cc:content-type:date:from:in-reply-to :message-id:mime-version:references:subject:to:x-me-sender :x-me-sender:x-sasl-enc:x-sasl-enc; s=smtpout; bh=tKROo1YVi7sKfZ iCdn8I1LXAxJY=; b=PyxnMMGFac2MR1zxswKsMpoTFJwIDQJ5EK0P4VF8dIeF9v GEfcIrRYyNex90GH9oNLo0gF1S8aXC1zJk8pBapUfPyHbJHWPqbchcZo9lIabGtL 1/0a8E+2FOxn0AwPPzL+Cn/h/WqbMDxgprBOvbLP84BjgRyGhkD7lQo+Pfebc= X-ME-Sender: X-Sasl-enc: 13NGx5TUmuYaOwOm6uVQdZMd9E+i2O5cYd4gN4I1rnz8 1486131110 Original-Received: from genserv (unknown [5.150.202.248]) by mail.messagingengine.com (Postfix) with ESMTPA id 40DA07E06B; Fri, 3 Feb 2017 09:11:50 -0500 (EST) In-Reply-To: <87vasr5tqd.fsf@hochschule-trier.de> (Andreas Politz's message of "Fri, 03 Feb 2017 13:44:42 +0100") X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] [fuzzy] X-Received-From: 66.111.4.25 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:211930 Archived-At: Andreas Politz writes: > >>> 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). Hm, that is true... I think I actually started like that, but then got stuck in the mindset of having a total ordering. So, will there be a linked list in each node for the overlays, or how will it work? > 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. I can confirm that we never need it :) >> 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. Sounds like a good idea.