GNU bug report logs - #5015
avl-tree.el enhancements

Previous Next

To add a comment to this bug, you must first unarchive it, by sending
a message to control AT debbugs.gnu.org, with unarchive 5015 in the body.
You can then email your comments to 5015 AT debbugs.gnu.org in the normal way.

Toggle the display of automated, internal messages from the tracker.

Message #5 received at submit <at> emacsbugs.donarmstrong.com (full text, mbox):

From: Stefan Monnier <monnier <at> iro.umontreal.ca>
To: Toby Cubitt <tsc25 <at> cantab.net>
Cc: bug-gnu-emacs <at> gnu.org
Subject: Re: avl-tree.el enhancements
Date: Sun, 22 Nov 2009 22:44:22 -0500

> 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 <http://www.gnu.org/licenses/>.
> +;; along with GNU Emacs. If not, see <http://www.gnu.org/licenses/>.

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

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.