From unknown Sat Jun 14 19:06:04 2025 X-Loop: owner@emacsbugs.donarmstrong.com Subject: bug#5015: avl-tree.el enhancements Reply-To: Stefan Monnier , 5015@debbugs.gnu.org Resent-From: Stefan Monnier Resent-To: bug-submit-list@lists.donarmstrong.com Resent-CC: Emacs Bugs 2Resent-Date: Mon, 23 Nov 2009 03:50:04 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-Emacs-PR-Message: report 5015 X-Emacs-PR-Package: emacs X-Emacs-PR-Keywords: Received: via spool by submit@emacsbugs.donarmstrong.com id=B.125894787210394 (code B ref -1); Mon, 23 Nov 2009 03:50:04 +0000 Received: (at submit) by emacsbugs.donarmstrong.com; 23 Nov 2009 03:44:32 +0000 X-Spam-Checker-Version: SpamAssassin 3.2.5-bugs.debian.org_2005_01_02 (2008-06-10) on rzlab.ucr.edu X-Spam-Level: X-Spam-Bayes: score:0.5 Bayes not run. spammytokens:Tokens not available. hammytokens:Tokens not available. X-Spam-Status: No, score=-2.0 required=4.0 tests=AWL,FOURLA,MURPHY_DRUGS_REL8 autolearn=no version=3.2.5-bugs.debian.org_2005_01_02 Received: from lists.gnu.org (lists.gnu.org [199.232.76.165]) by rzlab.ucr.edu (8.14.3/8.14.3/Debian-5) with ESMTP id nAN3iUX8010390 for ; Sun, 22 Nov 2009 19:44:32 -0800 Received: from mailman by lists.gnu.org with tmda-scanned (Exim 4.43) id 1NCPqo-0000od-94 for bug-gnu-emacs@gnu.org; Sun, 22 Nov 2009 22:44:30 -0500 Received: from exim by lists.gnu.org with spam-scanned (Exim 4.43) id 1NCPqi-0000oB-Oq for bug-gnu-emacs@gnu.org; Sun, 22 Nov 2009 22:44:29 -0500 Received: from [199.232.76.173] (port=52243 helo=monty-python.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1NCPqi-0000o8-JB for bug-gnu-emacs@gnu.org; Sun, 22 Nov 2009 22:44:24 -0500 Received: from ironport2-out.teksavvy.com ([206.248.154.183]:39875 helo=ironport2-out.pppoe.ca) by monty-python.gnu.org with esmtp (Exim 4.60) (envelope-from ) id 1NCPqi-0000ha-76 for bug-gnu-emacs@gnu.org; Sun, 22 Nov 2009 22:44:24 -0500 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: ApsEAJOTCUvO+IIa/2dsb2JhbACBTdF7hDwEigI X-IronPort-AV: E=Sophos;i="4.47,268,1257138000"; d="scan'208";a="49825601" Received: from 206-248-130-26.dsl.teksavvy.com (HELO ceviche.home) ([206.248.130.26]) by ironport2-out.pppoe.ca with ESMTP; 22 Nov 2009 22:44:23 -0500 Received: by ceviche.home (Postfix, from userid 20848) id E1B17B40C9; Sun, 22 Nov 2009 22:44:22 -0500 (EST) From: Stefan Monnier To: Toby Cubitt Cc: bug-gnu-emacs@gnu.org Message-ID: References: <20091123000123.GA7647@c3po> Date: Sun, 22 Nov 2009 22:44:22 -0500 In-Reply-To: <20091123000123.GA7647@c3po> (Toby Cubitt's message of "Mon, 23 Nov 2009 00:01:23 +0000") User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/23.1.50 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-detected-operating-system: by monty-python.gnu.org: Genre and OS details not recognized. > I've initiated the copyright paperwork process, so hopefully you should > have everything you need soon. Great. In the mean time, here's some comment about the first patch. > -;; along with GNU Emacs. If not, see . > +;; along with GNU Emacs. If not, see . This change is wrong. Our convention is to use two spaces after a full stop. See sentence-end-double-space. Please try to follow the same convention in the text you contribute. > - `(avl-tree--node-left (avl-tree--dummyroot tree))) > + `(avl-tree--node-left (avl-tree--dummyroot ,tree))) Good catch, thanks. > +;; ---------------------------------------------------------------- > +;; Convenience macros > + > +(defmacro avl-tree--switch-dir (dir) > + ;; Return opposite direction to DIR (0 = left, 1 = right). > + `(- 1 ,dir)) Hmm... using integers for "direction" isn't pretty. I see it mostly comes from its use in avl-tree--node-branch. I guess we'll have to live with it for now... > +(defun avl-tree--del-balance (node branch dir) > + ;; Rebalance a tree at the left (BRANCH=0) or right (BRANCH=1) child > + ;; of NODE after deleting from the left (DIR=0) or right (DIR=1) > + ;; sub-tree of that child [or is it vice-versa?]. Return t if the > + ;; height of the tree has shrunk. This comment should be a docstring instead. > +(defun avl-tree--mapc (map-function root dir) > ;; Apply MAP-FUNCTION to all nodes in the tree starting with ROOT. > - ;; The function is applied in-order. > + ;; The function is applied in-order, either ascending (DIR=0) or > + ;; descending (DIR=1). > ;; > ;; Note: MAP-FUNCTION is applied to the node and not to the data itself. > ;; INTERNAL USE ONLY. Same here: this should be a docstring, rather than a comment. > -(defalias 'avl-tree-compare-function 'avl-tree--cmpfun > - "Return the comparison function for the avl tree TREE. > +;; define public alias for constructors so that we can set docstring > +(defalias 'avl-tree-create 'avl-tree--create > + "Create an empty avl tree. > +COMPARE-FUNCTION is a function which takes two arguments, A and B, > +and returns non-nil if A is less than B, and nil otherwise.") > + > -\(fn TREE)") > +(defalias 'avl-tree-compare-function 'avl-tree--cmpfun > + "Return the comparison function for the avl tree TREE.") Why exactly do you remove the \(fn TREE) thingy at the end? > - (let ((node (avl-tree--root tree)) > - (compare-function (avl-tree--cmpfun tree)) > - found) > - (while (and node > - (not found)) > - (cond > - ((funcall compare-function data (avl-tree--node-data node)) > - (setq node (avl-tree--node-left node))) > - ((funcall compare-function (avl-tree--node-data node) data) > - (setq node (avl-tree--node-right node))) > - (t > - (setq found t)))) > - (if node > - (avl-tree--node-data node) > + (let ((node (avl-tree--root tree))) > + (catch 'found > + (while node > + (cond > + ((funcall (avl-tree--cmpfun tree) > + data (avl-tree--node-data node)) > + (setq node (avl-tree--node-left node))) > + ((funcall (avl-tree--cmpfun tree) > + (avl-tree--node-data node) data) > + (setq node (avl-tree--node-right node))) > + (t (throw 'found (avl-tree--node-data node))))) > nil))) Why do you move the (avl-tree--cmpfun tree) back into the loop? Have you found it to be paradoxically more efficient? Overall, looks good. Please provide a ChangeLog entry for it as well. Stefan From rgm@gnu.org Mon Nov 23 09:14:01 2009 Received: (at control) by emacsbugs.donarmstrong.com; 23 Nov 2009 17:14:01 +0000 X-Spam-Checker-Version: SpamAssassin 3.2.5-bugs.debian.org_2005_01_02 (2008-06-10) on rzlab.ucr.edu X-Spam-Level: X-Spam-Bayes: score:0.5 Bayes not run. spammytokens:Tokens not available. hammytokens:Tokens not available. X-Spam-Status: No, score=-4.2 required=4.0 tests=AWL,ONEWORD,X_DEBBUGS_NO_ACK autolearn=ham version=3.2.5-bugs.debian.org_2005_01_02 Received: from fencepost.gnu.org (fencepost.gnu.org [140.186.70.10]) by rzlab.ucr.edu (8.14.3/8.14.3/Debian-5) with ESMTP id nANHDxiC032527 for ; Mon, 23 Nov 2009 09:14:00 -0800 Received: from rgm by fencepost.gnu.org with local (Exim 4.67) (envelope-from ) id 1NCcUA-00028I-Tb; Mon, 23 Nov 2009 12:13:58 -0500 MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Message-ID: <19210.49878.866098.678133@fencepost.gnu.org> Date: Mon, 23 Nov 2009 12:13:58 -0500 From: Glenn Morris To: control Subject: control X-Attribution: GM X-Mailer: VM (www.wonderworks.com/vm), GNU Emacs (www.gnu.org/software/emacs) X-Hue: red X-Ran: .O'-;D_0!TDb.OFgXqr|QA;I3S]42v*9ky4*b!=n(~ X-Debbugs-No-Ack: yes merge 5012 5015 5016 5021 5024 severity 5012 wishlist severity 5018 wishlist reassign 5017 spam reassign 5023 spam close 4898 From rgm@gnu.org Tue Nov 24 15:25:33 2009 Received: (at control) by emacsbugs.donarmstrong.com; 24 Nov 2009 23:25:33 +0000 X-Spam-Checker-Version: SpamAssassin 3.2.5-bugs.debian.org_2005_01_02 (2008-06-10) on rzlab.ucr.edu X-Spam-Level: X-Spam-Bayes: score:0.5 Bayes not run. spammytokens:Tokens not available. hammytokens:Tokens not available. X-Spam-Status: No, score=-3.7 required=4.0 tests=AWL,MURPHY_DRUGS_REL8,ONEWORD, VALID_BTS_CONTROL autolearn=no version=3.2.5-bugs.debian.org_2005_01_02 Received: from fencepost.gnu.org (fencepost.gnu.org [140.186.70.10]) by rzlab.ucr.edu (8.14.3/8.14.3/Debian-5) with ESMTP id nAONPWKh003549 for ; Tue, 24 Nov 2009 15:25:33 -0800 Received: from rgm by fencepost.gnu.org with local (Exim 4.67) (envelope-from ) id 1ND4lH-0003ZM-AD; Tue, 24 Nov 2009 18:25:31 -0500 MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Message-ID: <19212.27499.290533.841289@fencepost.gnu.org> Date: Tue, 24 Nov 2009 18:25:31 -0500 From: Glenn Morris To: control Subject: control tags 4944 = close 4977 forcemerge 4977 4978 reassign 4893 emacs,ns reassign 5028 spam reassign 5034 spam reassign 5035 spam tags 5012 patch