From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!.POSTED!not-for-mail From: Stefan Monnier Newsgroups: gmane.emacs.devel Subject: Re: Overlays as an AA-tree Date: Thu, 22 Sep 2016 21:29:19 -0400 Message-ID: References: <87d1jylv43.fsf@fastmail.com> <87a8f0p69w.fsf@fastmail.com> <878tujlmp0.fsf@fastmail.com> NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: text/plain X-Trace: blaine.gmane.org 1474594214 26334 195.159.176.226 (23 Sep 2016 01:30:14 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Fri, 23 Sep 2016 01:30:14 +0000 (UTC) User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/25.1.50 (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 Sep 23 03:30:11 2016 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 1bnFJV-0005ev-CR for ged-emacs-devel@m.gmane.org; Fri, 23 Sep 2016 03:30:05 +0200 Original-Received: from localhost ([::1]:37554 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1bnFJW-0007Wo-5C for ged-emacs-devel@m.gmane.org; Thu, 22 Sep 2016 21:30:06 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:53219) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1bnFIm-0007VL-58 for emacs-devel@gnu.org; Thu, 22 Sep 2016 21:29:21 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1bnFIi-00073q-0q for emacs-devel@gnu.org; Thu, 22 Sep 2016 21:29:19 -0400 Original-Received: from ironport2-out.teksavvy.com ([206.248.154.181]:2669) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1bnFIh-00073A-SA for emacs-devel@gnu.org; Thu, 22 Sep 2016 21:29:15 -0400 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: A0DeBQALW9BX/63kr2xdGwEBAQMBAQGDLQEBAQEBHoRNhVCxeYYWBAICgWk8EQECAQEBAQEBAV4nhGIBAQMBJy8jBQsLNBIUGA0kiFUIvFUBCyWKfYQQhgwBBIYTk0aJJIJ7hQyHYoYLhnOIGoE+NCCEbCCDXIIuAQEB X-IPAS-Result: A0DeBQALW9BX/63kr2xdGwEBAQMBAQGDLQEBAQEBHoRNhVCxeYYWBAICgWk8EQECAQEBAQEBAV4nhGIBAQMBJy8jBQsLNBIUGA0kiFUIvFUBCyWKfYQQhgwBBIYTk0aJJIJ7hQyHYoYLhnOIGoE+NCCEbCCDXIIuAQEB X-IronPort-AV: E=Sophos;i="5.30,296,1470715200"; d="scan'208";a="273337151" Original-Received: from 108-175-228-173.dsl.teksavvy.com (HELO fmsmemgm.homelinux.net) ([108.175.228.173]) by smtp.teksavvy.com with ESMTP/TLS/DHE-RSA-AES256-SHA; 22 Sep 2016 21:29:14 -0400 Original-Received: by fmsmemgm.homelinux.net (Postfix, from userid 20848) id CDDA1AE123; Thu, 22 Sep 2016 21:29:19 -0400 (EDT) In-Reply-To: <878tujlmp0.fsf@fastmail.com> (Joakim Jalap's message of "Thu, 22 Sep 2016 22:11:07 +0200") X-detected-operating-system: by eggs.gnu.org: Genre and OS details not recognized. X-Received-From: 206.248.154.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:207719 Archived-At: >> Not much, no. Do note that in compare_overlays, we do need a total ordering >> (this is used for sort_overlays). Your sorting and that of >> compare_overlays can't be identical (compare_overlays has to obey the >> `priority` property, whereas yours shouldn't pay attention to it), but >> you can still use the same idea: i.e. when start and end are equal, just >> use the overlays's memory addresses to decide which comes first. > Do you mean when a->char_start == b->char_start && a->char_end == > b-> char_end? Yes. > Does it even matter what char_end is? I have a feeling it's ok to just > return true if a->char_start == b->char_end. Things are easier if you make the comparison a total order, so o1==o2 only if o1 and o2 are actually one and the same overlay. >>>> Some tricky parts: >>>> - because of the insertion_type, two overlays may start with end1>>> and finish with end1>end2 without any call to move-overlay. >>> Hm, ok. I will have to look into this further. > Actually, this sounds like it could be quite complicated... I'm not sure > how to handle that in the tree. After an insertion/deletion, you'll need to update the char positions. While doing it should be fairly easy to check that the adjustments don't break the tree's consistency. When an inconsistency is detected, you can either try to adjust things locally or just remove and re-insert the overlay. > Hm, I don't really understand this. Do you mean how LENGTH(i) is > computed from TOTAL_LENGTH(i->left) and TOTAL_LENGTH(i->right)? Not exactly, tho it's related. I was referring to the `position` field of `struct interval`. > Hm, how could I do that in the AA-tree? Haven't thought about it yet. > Store the position in the root and then an offset from the parent in > every child node? Something like that, I guess, yes. > But doing it like I do it now (updating all the char-positions after the > modification) shouldn't be slower than updating the positions of all > markers, right? Indeed, it's no worse than what we have, but it reduces the algorithmic benefit of the change. IOW we can keep this for later. Stefan