bug#5016: avl-tree.el enhancements

[Toby Cubitt]

On Sun, Nov 22, 2009 at 10:44:22PM -0500, Stefan Monnier wrote:
> > 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.

Ah, sorry. That was unintentional. I'll fix it.

> > -  `(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...

Exactly -- it stems from avl-tree--node-branch (which isn't my code). The
comment after its definition (also not mine) explains the reason for
it. I can't think of an efficient way to avoid this.

> > +(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.

I've followed the existing convention in avl-tree.el, which doesn't
provide docstrings for internal functions. If you want to change all the
comments to docstrings throughout, that's up to you, but I disagree. I
personally find the fact that internal library functions aren't
documented to be a useful form of documentation in itself: it tells me
that the function definitely shouldn't be used outside of the
library. Since Elisp doesn't have modules or private functions, that's
the closest one can get to an internal library function. Emacs abounds
with functions lacking docstrings, many of them apparently for this
reason.

In the case of this function, it's particularly important that it never
be used outside of avl-tree.el, as it should only ever be called after
deleting a node. There's no conceivable circumstance in which it could
legitimately be called outside of avl-tree-delete.

> > +(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.

Again, this was a comment in the original avl-tree.el. I've just followed
the original. This one's slightly less clear-cut than
avl-tree--del-balance, but the intention of the original avl-tree.el
author was no doubt the same: given the lack of private functions,
indicate by the lack of docstring that this function shouldn't be used
externally. It's dangerous to use this function externally because it
operates directly on nodes; unless MAP-FUNCTION is carefully crafted, it
will corrupt the tree. Also, other libraries shouldn't rely on the
function interface being set in stone (they shouldn't use the function at
all!), as the interface might need to change. As you can see, I've
modified it myself in these changes.

If you still insist on making one or other or both of these into
docstrings, I'll make the necessary changes to the patches.

> > -(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?

It seemed to be a strange documentation convention followed only by
avl-tree.el, and inconsistently at that. It's redundant, and as far as I
know isn't used anywhere else in Emacs, because "C-h f <function>"
already automatically shows the function's calling convention.

> > -  (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?

I'm not sure why a did this! (It's a while ago...) I'll revert this.

> Overall, looks good.  Please provide a ChangeLog entry for it as well.

Errrmmmm...do you mean a ChangeLog entry in the avl-tree.el file itself?
If so, I already did! :)

I've attached new versions of the two patches that fix the whitespace and
avl-tree--cmpfun issues.

Toby

avl-tree.el.1.diff
Description: Text document

avl-tree.el.2.diff
Description: Text document