diff options
| author | Stefan Monnier <monnier@iro.umontreal.ca> | 2012-03-27 16:43:09 -0400 |
|---|---|---|
| committer | Stefan Monnier <monnier@iro.umontreal.ca> | 2012-03-27 16:43:09 -0400 |
| commit | b973155e956eec4de5128effca7cc749897c1a45 (patch) | |
| tree | d32509bfce107caeb7f09ad906348cd746c71225 | |
| parent | 5d956bc22e57b78f47312001272f2e6643f31334 (diff) | |
| download | emacs-b973155e956eec4de5128effca7cc749897c1a45.tar.gz | |
* lisp/emacs-lisp/avl-tree.el (avl-tree--enter-balance): Fix paren typo.
(avl-tree--check, avl-tree--check-node): New funs.
Fixes: debbugs:11077
| -rw-r--r-- | lisp/ChangeLog | 13 | ||||
| -rw-r--r-- | lisp/emacs-lisp/avl-tree.el | 16 |
2 files changed, 22 insertions, 7 deletions
diff --git a/lisp/ChangeLog b/lisp/ChangeLog index 7d81bbb46b5..65018db7e4d 100644 --- a/lisp/ChangeLog +++ b/lisp/ChangeLog @@ -1,8 +1,14 @@ +2012-03-27 Stefan Monnier <monnier@iro.umontreal.ca> + + * emacs-lisp/avl-tree.el (avl-tree--enter-balance): Fix paren typo + (bug#11077). + (avl-tree--check, avl-tree--check-node): New funs. + 2012-03-27 Martin Rudalics <rudalics@gmx.at> * window.el (switch-to-visible-buffer): New option. - (switch-to-prev-buffer, switch-to-next-buffer): Observe - switch-to-visible-buffer. Make sure that checking for a window + (switch-to-prev-buffer, switch-to-next-buffer): + Observe switch-to-visible-buffer. Make sure that checking for a window showing a buffer already is done on the same frame. 2012-03-27 Glenn Morris <rgm@gnu.org> @@ -28,8 +34,7 @@ 2012-03-25 Eli Zaretskii <eliz@gnu.org> * makefile.w32-in (install): Use $(DIRNAME)_same-dir.tst instead - of same-dir.tst, to avoid stepping on other (parallel) Make job's - toes. + of same-dir.tst, to avoid stepping on other (parallel) Make job's toes. 2012-03-25 Chong Yidong <cyd@gnu.org> diff --git a/lisp/emacs-lisp/avl-tree.el b/lisp/emacs-lisp/avl-tree.el index cb5ea048999..9f348767478 100644 --- a/lisp/emacs-lisp/avl-tree.el +++ b/lisp/emacs-lisp/avl-tree.el @@ -295,9 +295,9 @@ Return t if the height of the tree has grown." (if (> (* sgn b2) 0) (- sgn) 0) (avl-tree--node-balance p1) (if (< (* sgn b2) 0) sgn 0) - (avl-tree--node-branch node branch) p2 - (avl-tree--node-balance - (avl-tree--node-branch node branch)) 0)) + (avl-tree--node-branch node branch) p2)) + (setf (avl-tree--node-balance + (avl-tree--node-branch node branch)) 0) nil)))) (defun avl-tree--do-enter (cmpfun root branch data &optional updatefun) @@ -339,6 +339,16 @@ inserted data." (cons nil newdata)) ; return value )))) +(defun avl-tree--check (tree) + "Check the tree's balance." + (avl-tree--check-node (avl-tree--root tree))) +(defun avl-tree--check-node (node) + (if (null node) 0 + (let ((dl (avl-tree--check-node (avl-tree--node-left node))) + (dr (avl-tree--check-node (avl-tree--node-right node)))) + (assert (= (- dr dl) (avl-tree--node-balance node))) + (1+ (max dl dr))))) + ;; ---------------------------------------------------------------- |