From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Stefan Monnier via "Bug reports for GNU Emacs, the Swiss army knife of text editors" Newsgroups: gmane.emacs.bugs Subject: bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful Date: Sat, 01 Oct 2022 09:54:36 -0400 Message-ID: References: <83h70qhez0.fsf@gnu.org> <83edvuhaby.fsf@gnu.org> <831qruh67o.fsf@gnu.org> <83y1u2foli.fsf@gnu.org> Reply-To: Stefan Monnier Mime-Version: 1.0 Content-Type: text/plain Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="33229"; mail-complaints-to="usenet@ciao.gmane.io" User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/29.0.50 (gnu/linux) Cc: Eli Zaretskii , Andreas Politz , 58158@debbugs.gnu.org To: Gerd =?UTF-8?Q?M=C3=B6llmann?= Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane-mx.org@gnu.org Sat Oct 01 15:55:26 2022 Return-path: Envelope-to: geb-bug-gnu-emacs@m.gmane-mx.org Original-Received: from lists.gnu.org ([209.51.188.17]) by ciao.gmane.io with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1oecxh-0008UO-Nt for geb-bug-gnu-emacs@m.gmane-mx.org; Sat, 01 Oct 2022 15:55:25 +0200 Original-Received: from localhost ([::1]:57392 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1oecxg-0002Vz-Aw for geb-bug-gnu-emacs@m.gmane-mx.org; Sat, 01 Oct 2022 09:55:24 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:56452) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1oecxL-0002VK-4k for bug-gnu-emacs@gnu.org; Sat, 01 Oct 2022 09:55:03 -0400 Original-Received: from debbugs.gnu.org ([209.51.188.43]:44973) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1oecxK-0001lN-T0 for bug-gnu-emacs@gnu.org; Sat, 01 Oct 2022 09:55:02 -0400 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84_2) (envelope-from ) id 1oecxK-0005wF-OW for bug-gnu-emacs@gnu.org; Sat, 01 Oct 2022 09:55:02 -0400 X-Loop: help-debbugs@gnu.org Resent-From: Stefan Monnier Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Sat, 01 Oct 2022 13:55:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 58158 X-GNU-PR-Package: emacs Original-Received: via spool by 58158-submit@debbugs.gnu.org id=B58158.166463249422792 (code B ref 58158); Sat, 01 Oct 2022 13:55:02 +0000 Original-Received: (at 58158) by debbugs.gnu.org; 1 Oct 2022 13:54:54 +0000 Original-Received: from localhost ([127.0.0.1]:44048 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1oecxB-0005vY-Oc for submit@debbugs.gnu.org; Sat, 01 Oct 2022 09:54:54 -0400 Original-Received: from mailscanner.iro.umontreal.ca ([132.204.25.50]:41687) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1oecx9-0005vI-S4 for 58158@debbugs.gnu.org; Sat, 01 Oct 2022 09:54:52 -0400 Original-Received: from pmg1.iro.umontreal.ca (localhost.localdomain [127.0.0.1]) by pmg1.iro.umontreal.ca (Proxmox) with ESMTP id 191DA100121; Sat, 1 Oct 2022 09:54:46 -0400 (EDT) Original-Received: from mail01.iro.umontreal.ca (unknown [172.31.2.1]) by pmg1.iro.umontreal.ca (Proxmox) with ESMTP id 8FA601000DF; Sat, 1 Oct 2022 09:54:44 -0400 (EDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=iro.umontreal.ca; s=mail; t=1664632484; bh=Rv05Biz8FSRw63tFlyG6CXwRDHnELMoSJUzLK9ytav4=; h=From:To:Cc:Subject:In-Reply-To:References:Date:From; b=buujRDAZI7N7OHu+BM8qdi+wQw2GYFFdUlck3v2a4WtoSf3xE9pOrLJep4844R2WL mD0hu0usU42nPQf5TFwyT5rd2T5wgliblzIRyJ18KGGaGw2bfS+SqDv6FcBf/x0xZA JsJc8GTa4IrYVMepLWpV7SOHZ9Du1RXHO11jlprQXeZ5yRkDK3BgPsa6mbp7BpOdVZ N1HdSg2yEqxq5CXbS1b+9eM/UeGJi9TSY6bt7BpL5Eh/vwltLyPGtY38Z5LkGT8zdT I3GDLuHOwkmuvxZxCvnNT9GMmkncz1l8ypSZTwmTeYL1K5/hm7kmDPF9de06u0rSdV T/8FoFUzyOBXA== Original-Received: from pastel (65-110-220-202.cpe.pppoe.ca [65.110.220.202]) by mail01.iro.umontreal.ca (Postfix) with ESMTPSA id 54766120513; Sat, 1 Oct 2022 09:54:44 -0400 (EDT) In-Reply-To: ("Gerd =?UTF-8?Q?M=C3=B6llmann?="'s message of "Sat, 01 Oct 2022 07:06:50 +0200") X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list X-BeenThere: bug-gnu-emacs@gnu.org List-Id: "Bug reports for GNU Emacs, the Swiss army knife of text editors" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane-mx.org@gnu.org Original-Sender: "bug-gnu-emacs" Xref: news.gmane.io gmane.emacs.bugs:244131 Archived-At: >> The following code in `interval_tree_insert`: [...] >> suggests that N->left are <= and N->right are > but my reading of the >> comment is that the only thing we can rely on is that N-> N->right is >= > > Phew. I'm not sure but I get the feeling that makes implementing a > successor function, let's say, challenging. I don't think it makes any difference in that respect, no. The notion of "successor" is just "the successor in the in-order traversal of the tree" and while rotations change the initial property that "N->right are >", they don't change the in-order traversal output (they don't re-order nodes w.r.t in-order traversal (or in reverse order for that matter)). As alluded to at the end of my previous email, while RB trees are typically used for your usual binary tree which comes with some notion of ordering that makes lookup O(log N), the RB trees ensure balance without relying on any notion of ordering since the rotations just blindly preserve the order as a side effect but they don't themselves need to call the ordering function to decide how to do their job. Stefan