[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
bug#5015: avl-tree.el enhancements
From: |
Stefan Monnier |
Subject: |
bug#5015: avl-tree.el enhancements |
Date: |
Sun, 22 Nov 2009 22:44:22 -0500 |
User-agent: |
Gnus/5.13 (Gnus v5.13) Emacs/23.1.50 (gnu/linux) |
> 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