bug#5015: avl-tree.el enhancements

[Stefan Monnier <monnier@iro.umontreal.ca>]

> 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