From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Stefan Monnier Newsgroups: gmane.emacs.bugs Subject: bug#5015: avl-tree.el enhancements Date: Sun, 22 Nov 2009 22:44:22 -0500 Message-ID: References: <20091123000123.GA7647@c3po> Reply-To: Stefan Monnier , 5015@emacsbugs.donarmstrong.com NNTP-Posting-Host: lo.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Trace: ger.gmane.org 1258949283 22538 80.91.229.12 (23 Nov 2009 04:08:03 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Mon, 23 Nov 2009 04:08:03 +0000 (UTC) Cc: bug-gnu-emacs@gnu.org To: Toby Cubitt Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane.org@gnu.org Mon Nov 23 05:07:56 2009 Return-path: Envelope-to: geb-bug-gnu-emacs@m.gmane.org Original-Received: from lists.gnu.org ([199.232.76.165]) by lo.gmane.org with esmtp (Exim 4.50) id 1NCQDT-0007pC-MM for geb-bug-gnu-emacs@m.gmane.org; Mon, 23 Nov 2009 05:07:56 +0100 Original-Received: from localhost ([127.0.0.1]:35609 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1NCQDT-0002Lq-93 for geb-bug-gnu-emacs@m.gmane.org; Sun, 22 Nov 2009 23:07:55 -0500 Original-Received: from mailman by lists.gnu.org with tmda-scanned (Exim 4.43) id 1NCQD4-0002Ci-Do for bug-gnu-emacs@gnu.org; Sun, 22 Nov 2009 23:07:30 -0500 Original-Received: from exim by lists.gnu.org with spam-scanned (Exim 4.43) id 1NCQCz-0002BN-DV for bug-gnu-emacs@gnu.org; Sun, 22 Nov 2009 23:07:29 -0500 Original-Received: from [199.232.76.173] (port=38909 helo=monty-python.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1NCQCy-0002BD-W9 for bug-gnu-emacs@gnu.org; Sun, 22 Nov 2009 23:07:25 -0500 Original-Received: from rzlab.ucr.edu ([138.23.92.77]:50225) by monty-python.gnu.org with esmtps (TLS-1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.60) (envelope-from ) id 1NCQCy-0003q3-76 for bug-gnu-emacs@gnu.org; Sun, 22 Nov 2009 23:07:24 -0500 Original-Received: from rzlab.ucr.edu (rzlab.ucr.edu [127.0.0.1]) by rzlab.ucr.edu (8.14.3/8.14.3/Debian-5) with ESMTP id nAN47LTS013218; Sun, 22 Nov 2009 20:07:22 -0800 Original-Received: (from debbugs@localhost) by rzlab.ucr.edu (8.14.3/8.14.3/Submit) id nAN3o45q010952; Sun, 22 Nov 2009 19:50:04 -0800 Resent-Date: Sun, 22 Nov 2009 19:50:04 -0800 X-Loop: owner@emacsbugs.donarmstrong.com Resent-From: Stefan Monnier Resent-To: bug-submit-list@donarmstrong.com Resent-CC: Emacs Bugs 2Resent-Date: Mon, 23 Nov 2009 03:50:04 +0000 Resent-Message-ID: Resent-Sender: owner@emacsbugs.donarmstrong.com X-Emacs-PR-Message: report 5015 X-Emacs-PR-Package: emacs X-Emacs-PR-Keywords: Original-Received: via spool by submit@emacsbugs.donarmstrong.com id=B.125894787210394 (code B ref -1); Mon, 23 Nov 2009 03:50:04 +0000 Original-Received: (at submit) by emacsbugs.donarmstrong.com; 23 Nov 2009 03:44:32 +0000 X-Spam-Bayes: score:0.5 Bayes not run. spammytokens:Tokens not available. hammytokens:Tokens not available. Original-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 Original-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 Original-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 Original-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 Original-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" Original-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 Original-Received: by ceviche.home (Postfix, from userid 20848) id E1B17B40C9; Sun, 22 Nov 2009 22:44:22 -0500 (EST) 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) X-detected-operating-system: by monty-python.gnu.org: Genre and OS details not recognized. X-detected-operating-system: by monty-python.gnu.org: GNU/Linux 2.6 (newer, 2) Resent-Date: Sun, 22 Nov 2009 23:07:29 -0500 X-BeenThere: bug-gnu-emacs@gnu.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: "Bug reports for GNU Emacs, the Swiss army knife of text editors" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Original-Sender: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane.org@gnu.org Errors-To: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.bugs:32828 Archived-At: > 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