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 16:23:29 +0100 Message-ID: <87y3xnnvri.fsf@fastmail.com> References: <87d1jylv43.fsf@fastmail.com> <87fujv64mn.fsf@hochschule-trier.de> <87fujvpkzc.fsf@fastmail.com> <87vasr5tqd.fsf@hochschule-trier.de> <877f57pdne.fsf@fastmail.com> <87fujv5ncv.fsf@hochschule-trier.de> NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: text/plain X-Trace: blaine.gmane.org 1486135548 19422 195.159.176.226 (3 Feb 2017 15:25:48 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Fri, 3 Feb 2017 15:25:48 +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 16:25:45 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 1cZfk8-0004um-M9 for ged-emacs-devel@m.gmane.org; Fri, 03 Feb 2017 16:25:44 +0100 Original-Received: from localhost ([::1]:35299 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1cZfkE-0004Yj-BV for ged-emacs-devel@m.gmane.org; Fri, 03 Feb 2017 10:25:50 -0500 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:58376) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1cZfi4-0003Fe-Gj for emacs-devel@gnu.org; Fri, 03 Feb 2017 10:23:37 -0500 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1cZfi1-0005Al-9Y for emacs-devel@gnu.org; Fri, 03 Feb 2017 10:23:36 -0500 Original-Received: from out1-smtp.messagingengine.com ([66.111.4.25]:51974) by eggs.gnu.org with esmtps (TLS1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1cZfi1-0005A0-2d for emacs-devel@gnu.org; Fri, 03 Feb 2017 10:23:33 -0500 Original-Received: from compute4.internal (compute4.nyi.internal [10.202.2.44]) by mailout.nyi.internal (Postfix) with ESMTP id 387F2207D4; Fri, 3 Feb 2017 10:23:32 -0500 (EST) Original-Received: from frontend2 ([10.202.2.161]) by compute4.internal (MEProxy); Fri, 03 Feb 2017 10:23:32 -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=pwiNDvHNoLvK8ycy8v8dkOU4XAU=; b=BjzUzQ O8QMqxa3mzQbhY8qMSDF2QX3gpaGWshy5vdCajSESjn9MDuxnIk57XuuI3OjAB5v 4QlPp0sYc8eGoK3CPyVopF4mBWM7aS6WGi/y+BQ/E0Vd9ML1iNpsV/nPSA02kWVi QWXvhT9Va4K4jvNwREs26dmZdHTscQNWg4Ykw= 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=pwiNDvHNoLvK8y cy8v8dkOU4XAU=; b=pPPKmodnhQdiE+D0cqYOJmlIRUO2/k8nuP8gbmvZGXU/1v vlSHwUHNSa9A5MLiT8mPVZrdMYdilZC3t3hdZ1qqam2/i2BN3xTgii+dkxwPRfxE psObgXOKY/RL0xBz4I2XqdH1MvsjJBrkXdPq+MgpYZLxkBb1VtA3IyGqm5m4M= X-ME-Sender: X-Sasl-enc: peE+WrLIXrodUtIl4cBfAeH6uFf+8AD2TNrQMGUwKYzx 1486135411 Original-Received: from genserv (unknown [5.150.202.248]) by mail.messagingengine.com (Postfix) with ESMTPA id 88320245D4; Fri, 3 Feb 2017 10:23:31 -0500 (EST) In-Reply-To: <87fujv5ncv.fsf@hochschule-trier.de> (Andreas Politz's message of "Fri, 03 Feb 2017 16:02:24 +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:211933 Archived-At: Andreas Politz writes: > Joakim Jalap writes: > >> Hm, that is true... I think I actually started like that, but then got >> stuck in the mindset of having a total ordering. > > No you're right, the comparison function needs to implement a total > ordering, but this just means, simply put, that any pair of nodes x, y > needs to be comparable, i.e. x <= y OR y <= x . But this does not > exclude the case where both these statements are true, i.e. x = y. Hm, OK. I interpreted total ordering as always being able to sort the nodes unambiguously. >> So, will there be a linked list in each node for the overlays, or how >> will it work? > > Well, imagine your AA-Tree, with <= as relation and where you keep > inserting 1s and nothing else. How will it look ? It will be a bunch of 1s, but balanced, I think... :) The problem is when we need to delete one of those nodes which has 1 as key. How do we find it? When we're at the root (which also has key 1), do we go to the right or to the left? In the tree I have now, we can find the right node, since even if every overlay starts and ends at 1, they will still be sorted according to their address. Well that was the plan anyway, turns out it wasn't so easy to keep this ordering. So I think (but obviously most of my thinking so far has been wrong :)) that it might be easiest to keep a linked list of overlays which start at that position in the node. In the example above, there would then only be one node, containing a linked list of all the overlays.