* bug#5012: avl-tree.el enhancements
@ 2009-11-23 0:01 Toby Cubitt
2009-11-23 3:44 ` bug#5015: " Stefan Monnier
0 siblings, 1 reply; 7+ messages in thread
From: Toby Cubitt @ 2009-11-23 0:01 UTC (permalink / raw)
To: Stefan Monnier, bug-gnu-emacs
[-- Attachment #1: Type: text/plain, Size: 1559 bytes --]
Attached is a sequence of two patches for avl-tree.el, implementing the
enhancements to that library that I posted a while ago to the
gnu-emacs-sources list.
The first patch, avl-tree.el.1.diff, simplifies some of the avl-tree.el
functions, reducing code redundancy. These changes also make it natural
to add an optional argument to `avl-tree-map' specifying the order in
which to map over the tree.
The second patch, avl-tree.el.2.diff, contains the feature
enhancements. It adds optional arguments to a number of functions, and
adds a number of new functions. The new optional argument to
`avl-tree-member' allows it to distinguish a non-existence element from
an element of the tree with null data. The new optional argument to
`avl-tree-enter' allows data in the tree to be updated without having to
first search for it and then enter the new data (a factor of 2 difference
in efficiency). Similarly, the new optional argument to `avl-tree-delete'
allows data to be deleted if it satisfies some predicate (another factor
of 2 in efficiency). The patch also adds new mapping functions, and new
functions for accessing the tree elements as though they were a stack
(which for some purposes can be more efficient than mapping over the tree
of flattening it).
Note that, as the only changes to the existing function interfaces are
additional optional arguments, any code using avl-tree.el will remain
compatible with the modified version.
I've initiated the copyright paperwork process, so hopefully you should
have everything you need soon.
Toby Cubitt
[-- Attachment #2: avl-tree.el.1.diff --]
[-- Type: text/plain, Size: 23649 bytes --]
--- avl-tree.el 2009-11-22 22:10:09.000000000 +0000
+++ avl-tree1.el 2009-11-22 22:15:47.000000000 +0000
@@ -3,11 +3,13 @@
;; Copyright (C) 1995, 2007, 2008, 2009 Free Software Foundation, Inc.
;; Author: Per Cederqvist <ceder@lysator.liu.se>
-;; Inge Wallin <inge@lysator.liu.se>
-;; Thomas Bellman <bellman@lysator.liu.se>
+;; Inge Wallin <inge@lysator.liu.se>
+;; Thomas Bellman <bellman@lysator.liu.se>
+;; modified by Toby Cubitt <toby-predictive@dr-qubit.org>
+;; Version: 0.1
;; Maintainer: FSF
;; Created: 10 May 1991
-;; Keywords: extensions, data structures
+;; Keywords: extensions, data structures, AVL, tree
;; This file is part of GNU Emacs.
@@ -22,176 +24,191 @@
;; GNU General Public License for more details.
;; You should have received a copy of the GNU General Public License
-;; along with GNU Emacs. If not, see <http://www.gnu.org/licenses/>.
+;; along with GNU Emacs. If not, see <http://www.gnu.org/licenses/>.
-;;; Commentary:
-;; An AVL tree is a nearly-perfect balanced binary tree. A tree consists of
-;; two elements, the root node and the compare function. The actual tree
-;; has a dummy node as its root with the real root in the left pointer.
+;;; Commentary:
+;;
+;; An AVL tree is a self-balancing binary tree. As such, inserting,
+;; deleting, and retrieving data from an AVL tree containing n elements
+;; is O(log n). It is somewhat more rigidly balanced than other
+;; self-balancing binary trees (such as red-black trees and AA trees),
+;; making insertion slighty slower, deletion somewhat slower, and
+;; retrieval somewhat faster (the asymptotic scaling is of course the
+;; same for all types). Thus it may be a good choice when the tree will
+;; be relatively static, i.e. data will be retrieved more often than
+;; they are modified.
+;;
+;; Internally, a tree consists of two elements, the root node and the
+;; comparison function. The actual tree has a dummy node as its root
+;; with the real root in the left pointer, which allows the root node to
+;; be treated on a par with all other nodes.
;;
;; Each node of the tree consists of one data element, one left
-;; sub-tree and one right sub-tree. Each node also has a balance
-;; count, which is the difference in depth of the left and right
-;; sub-trees.
+;; sub-tree, one right sub-tree, and a balance count. The latter is the
+;; difference in depth of the left and right sub-trees.
;;
;; The functions with names of the form "avl-tree--" are intended for
;; internal use only.
+
+;;; Change log:
+;;
+;; Version 0.1
+;; * simplified rebalancing code
+;; * added optional direction argument to `avl-tree-map'
+
+
;;; Code:
(eval-when-compile (require 'cl))
-;; ================================================================
-;;; Functions and macros handling an AVL tree node.
-(defstruct (avl-tree--node
- ;; We force a representation without tag so it matches the
- ;; pre-defstruct representation. Also we use the underlying
- ;; representation in the implementation of avl-tree--node-branch.
- (:type vector)
- (:constructor nil)
- (:constructor avl-tree--node-create (left right data balance))
- (:copier nil))
- left right data balance)
-(defalias 'avl-tree--node-branch 'aref
- ;; This implementation is efficient but breaks the defstruct abstraction.
- ;; An alternative could be
- ;; (funcall (aref [avl-tree-left avl-tree-right avl-tree-data] branch) node)
- "Get value of a branch of a node.
+;; ================================================================
+;;; Internal functions and macros for use in the AVL tree package
-NODE is the node, and BRANCH is the branch.
-0 for left pointer, 1 for right pointer and 2 for the data.\"
-\(fn node branch)")
-;; The funcall/aref trick doesn't work for the setf method, unless we try
-;; and access the underlying setter function, but this wouldn't be
-;; portable either.
-(defsetf avl-tree--node-branch aset)
-\f
-;; ================================================================
-;;; Internal functions for use in the AVL tree package
+;; ----------------------------------------------------------------
+;; Functions and macros handling an AVL tree.
(defstruct (avl-tree-
;; A tagged list is the pre-defstruct representation.
;; (:type list)
:named
(:constructor nil)
- (:constructor avl-tree-create (cmpfun))
+ (:constructor avl-tree--create (cmpfun))
(:predicate avl-tree-p)
(:copier nil))
(dummyroot (avl-tree--node-create nil nil nil 0))
cmpfun)
+
(defmacro avl-tree--root (tree)
;; Return the root node for an avl-tree. INTERNAL USE ONLY.
- `(avl-tree--node-left (avl-tree--dummyroot tree)))
+ `(avl-tree--node-left (avl-tree--dummyroot ,tree)))
+
+
(defsetf avl-tree--root (tree) (node)
`(setf (avl-tree--node-left (avl-tree--dummyroot ,tree)) ,node))
+
+
;; ----------------------------------------------------------------
-;; Deleting data
+;; Functions and macros handling an AVL tree node.
-(defun avl-tree--del-balance1 (node branch)
- ;; Rebalance a tree and return t if the height of the tree has shrunk.
- (let ((br (avl-tree--node-branch node branch))
- p1 b1 p2 b2 result)
- (cond
- ((< (avl-tree--node-balance br) 0)
- (setf (avl-tree--node-balance br) 0)
- t)
+(defstruct (avl-tree--node
+ ;; We force a representation without tag so it matches the
+ ;; pre-defstruct representation. Also we use the underlying
+ ;; representation in the implementation of
+ ;; avl-tree--node-branch.
+ (:type vector)
+ (:constructor nil)
+ (:constructor avl-tree--node-create (left right data balance))
+ (:copier nil))
+ left right data balance)
- ((= (avl-tree--node-balance br) 0)
- (setf (avl-tree--node-balance br) +1)
- nil)
- (t
- ;; Rebalance.
- (setq p1 (avl-tree--node-right br)
- b1 (avl-tree--node-balance p1))
- (if (>= b1 0)
- ;; Single RR rotation.
- (progn
- (setf (avl-tree--node-right br) (avl-tree--node-left p1))
- (setf (avl-tree--node-left p1) br)
- (if (= 0 b1)
- (progn
- (setf (avl-tree--node-balance br) +1)
- (setf (avl-tree--node-balance p1) -1)
- (setq result nil))
- (setf (avl-tree--node-balance br) 0)
- (setf (avl-tree--node-balance p1) 0)
- (setq result t))
- (setf (avl-tree--node-branch node branch) p1)
- result)
-
- ;; Double RL rotation.
- (setq p2 (avl-tree--node-left p1)
- b2 (avl-tree--node-balance p2))
- (setf (avl-tree--node-left p1) (avl-tree--node-right p2))
- (setf (avl-tree--node-right p2) p1)
- (setf (avl-tree--node-right br) (avl-tree--node-left p2))
- (setf (avl-tree--node-left p2) br)
- (setf (avl-tree--node-balance br) (if (> b2 0) -1 0))
- (setf (avl-tree--node-balance p1) (if (< b2 0) +1 0))
- (setf (avl-tree--node-branch node branch) p2)
- (setf (avl-tree--node-balance p2) 0)
- t)))))
+(defalias 'avl-tree--node-branch 'aref
+ ;; This implementation is efficient but breaks the defstruct
+ ;; abstraction. An alternative could be (funcall (aref [avl-tree-left
+ ;; avl-tree-right avl-tree-data] branch) node)
+ "Get value of a branch of a node.
+NODE is the node, and BRANCH is the branch.
+0 for left pointer, 1 for right pointer and 2 for the data.")
+
+
+;; The funcall/aref trick wouldn't work for the setf method, unless we
+;; tried to access the underlying setter function, but this wouldn't be
+;; portable either.
+(defsetf avl-tree--node-branch aset)
+
-(defun avl-tree--del-balance2 (node branch)
+
+;; ----------------------------------------------------------------
+;; Convenience macros
+
+(defmacro avl-tree--switch-dir (dir)
+ ;; Return opposite direction to DIR (0 = left, 1 = right).
+ `(- 1 ,dir))
+
+(defmacro avl-tree--dir-to-sign (dir)
+ ;; Convert direction (0,1) to sign factor (-1,+1)
+ `(1- (* 2 ,dir)))
+
+(defmacro avl-tree--sign-to-dir (dir)
+ ;; Convert sign factor (-x,+x) to direction (0,1)
+ `(if (< ,dir 0) 0 1))
+
+
+;; ----------------------------------------------------------------
+;; Deleting data
+
+(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.
(let ((br (avl-tree--node-branch node branch))
- p1 b1 p2 b2 result)
+ ;; opposite direction: 0,1 -> 1,0
+ (opp (avl-tree--switch-dir dir))
+ ;; direction 0,1 -> sign factor -1,+1
+ (sgn (avl-tree--dir-to-sign dir))
+ p1 b1 p2 b2)
(cond
- ((> (avl-tree--node-balance br) 0)
+ ((> (* sgn (avl-tree--node-balance br)) 0)
(setf (avl-tree--node-balance br) 0)
t)
((= (avl-tree--node-balance br) 0)
- (setf (avl-tree--node-balance br) -1)
+ (setf (avl-tree--node-balance br) (- sgn))
nil)
(t
;; Rebalance.
- (setq p1 (avl-tree--node-left br)
+ (setq p1 (avl-tree--node-branch br opp)
b1 (avl-tree--node-balance p1))
- (if (<= b1 0)
- ;; Single LL rotation.
+ (if (<= (* sgn b1) 0)
+ ;; Single rotation.
(progn
- (setf (avl-tree--node-left br) (avl-tree--node-right p1))
- (setf (avl-tree--node-right p1) br)
+ (setf (avl-tree--node-branch br opp)
+ (avl-tree--node-branch p1 dir)
+ (avl-tree--node-branch p1 dir) br
+ (avl-tree--node-branch node branch) p1)
(if (= 0 b1)
(progn
- (setf (avl-tree--node-balance br) -1)
- (setf (avl-tree--node-balance p1) +1)
- (setq result nil))
+ (setf (avl-tree--node-balance br) (- sgn)
+ (avl-tree--node-balance p1) sgn)
+ nil) ; height hasn't changed
(setf (avl-tree--node-balance br) 0)
(setf (avl-tree--node-balance p1) 0)
- (setq result t))
- (setf (avl-tree--node-branch node branch) p1)
- result)
-
- ;; Double LR rotation.
- (setq p2 (avl-tree--node-right p1)
- b2 (avl-tree--node-balance p2))
- (setf (avl-tree--node-right p1) (avl-tree--node-left p2))
- (setf (avl-tree--node-left p2) p1)
- (setf (avl-tree--node-left br) (avl-tree--node-right p2))
- (setf (avl-tree--node-right p2) br)
- (setf (avl-tree--node-balance br) (if (< b2 0) +1 0))
- (setf (avl-tree--node-balance p1) (if (> b2 0) -1 0))
- (setf (avl-tree--node-branch node branch) p2)
- (setf (avl-tree--node-balance p2) 0)
+ t)) ; height has changed
+
+ ;; Double rotation.
+ (setf p2 (avl-tree--node-branch p1 dir)
+ b2 (avl-tree--node-balance p2)
+ (avl-tree--node-branch p1 dir)
+ (avl-tree--node-branch p2 opp)
+ (avl-tree--node-branch p2 opp) p1
+ (avl-tree--node-branch br opp)
+ (avl-tree--node-branch p2 dir)
+ (avl-tree--node-branch p2 dir) br
+ (avl-tree--node-balance br)
+ (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 p2) 0)
t)))))
(defun avl-tree--do-del-internal (node branch q)
(let ((br (avl-tree--node-branch node branch)))
(if (avl-tree--node-right br)
- (if (avl-tree--do-del-internal br +1 q)
- (avl-tree--del-balance2 node branch))
- (setf (avl-tree--node-data q) (avl-tree--node-data br))
- (setf (avl-tree--node-branch node branch)
- (avl-tree--node-left br))
+ (if (avl-tree--do-del-internal br 1 q)
+ (avl-tree--del-balance node branch 1))
+ (setf (avl-tree--node-data q) (avl-tree--node-data br)
+ (avl-tree--node-branch node branch)
+ (avl-tree--node-left br))
t)))
(defun avl-tree--do-delete (cmpfun root branch data)
@@ -203,102 +220,79 @@
((funcall cmpfun data (avl-tree--node-data br))
(if (avl-tree--do-delete cmpfun br 0 data)
- (avl-tree--del-balance1 root branch)))
+ (avl-tree--del-balance root branch 0)))
((funcall cmpfun (avl-tree--node-data br) data)
(if (avl-tree--do-delete cmpfun br 1 data)
- (avl-tree--del-balance2 root branch)))
+ (avl-tree--del-balance root branch 1)))
(t
;; Found it. Let's delete it.
(cond
((null (avl-tree--node-right br))
- (setf (avl-tree--node-branch root branch) (avl-tree--node-left br))
- t)
+ (setf (avl-tree--node-branch root branch) (avl-tree--node-left br))
+ t)
((null (avl-tree--node-left br))
- (setf (avl-tree--node-branch root branch) (avl-tree--node-right br))
- t)
+ (setf (avl-tree--node-branch root branch)
+ (avl-tree--node-right br))
+ t)
(t
- (if (avl-tree--do-del-internal br 0 br)
- (avl-tree--del-balance1 root branch))))))))
+ (if (avl-tree--do-del-internal br 0 br)
+ (avl-tree--del-balance root branch 0))))))))
;; ----------------------------------------------------------------
;; Entering data
-(defun avl-tree--enter-balance1 (node branch)
- ;; Rebalance a tree and return t if the height of the tree has grown.
+(defun avl-tree--enter-balance (node branch dir)
+ ;; Rebalance tree at the left (BRANCH=0) or right (BRANCH=1) child of
+ ;; NODE after an insertion into the left (DIR=0) or right (DIR=1)
+ ;; sub-tree of that child. Return t if the height of the tree has
+ ;; grown.
(let ((br (avl-tree--node-branch node branch))
+ ;; opposite direction: 0,1 -> 1,0
+ (opp (avl-tree--switch-dir dir))
+ ;; direction 0,1 -> sign factor -1,+1
+ (sgn (avl-tree--dir-to-sign dir))
p1 p2 b2 result)
(cond
- ((< (avl-tree--node-balance br) 0)
+ ((< (* sgn (avl-tree--node-balance br)) 0)
(setf (avl-tree--node-balance br) 0)
nil)
((= (avl-tree--node-balance br) 0)
- (setf (avl-tree--node-balance br) +1)
+ (setf (avl-tree--node-balance br) sgn)
t)
(t
;; Tree has grown => Rebalance.
- (setq p1 (avl-tree--node-right br))
- (if (> (avl-tree--node-balance p1) 0)
- ;; Single RR rotation.
+ (setq p1 (avl-tree--node-branch br dir))
+ (if (> (* sgn (avl-tree--node-balance p1)) 0)
+ ;; Single rotation.
(progn
- (setf (avl-tree--node-right br) (avl-tree--node-left p1))
- (setf (avl-tree--node-left p1) br)
+ (setf (avl-tree--node-branch br dir)
+ (avl-tree--node-branch p1 opp))
+ (setf (avl-tree--node-branch p1 opp) br)
(setf (avl-tree--node-balance br) 0)
(setf (avl-tree--node-branch node branch) p1))
- ;; Double RL rotation.
- (setq p2 (avl-tree--node-left p1)
- b2 (avl-tree--node-balance p2))
- (setf (avl-tree--node-left p1) (avl-tree--node-right p2))
- (setf (avl-tree--node-right p2) p1)
- (setf (avl-tree--node-right br) (avl-tree--node-left p2))
- (setf (avl-tree--node-left p2) br)
- (setf (avl-tree--node-balance br) (if (> b2 0) -1 0))
- (setf (avl-tree--node-balance p1) (if (< b2 0) +1 0))
- (setf (avl-tree--node-branch node branch) p2))
- (setf (avl-tree--node-balance (avl-tree--node-branch node branch)) 0)
- nil))))
-
-(defun avl-tree--enter-balance2 (node branch)
- ;; Return t if the tree has grown.
- (let ((br (avl-tree--node-branch node branch))
- p1 p2 b2)
- (cond
- ((> (avl-tree--node-balance br) 0)
- (setf (avl-tree--node-balance br) 0)
- nil)
-
- ((= (avl-tree--node-balance br) 0)
- (setf (avl-tree--node-balance br) -1)
- t)
-
- (t
- ;; Balance was -1 => Rebalance.
- (setq p1 (avl-tree--node-left br))
- (if (< (avl-tree--node-balance p1) 0)
- ;; Single LL rotation.
- (progn
- (setf (avl-tree--node-left br) (avl-tree--node-right p1))
- (setf (avl-tree--node-right p1) br)
- (setf (avl-tree--node-balance br) 0)
- (setf (avl-tree--node-branch node branch) p1))
-
- ;; Double LR rotation.
- (setq p2 (avl-tree--node-right p1)
- b2 (avl-tree--node-balance p2))
- (setf (avl-tree--node-right p1) (avl-tree--node-left p2))
- (setf (avl-tree--node-left p2) p1)
- (setf (avl-tree--node-left br) (avl-tree--node-right p2))
- (setf (avl-tree--node-right p2) br)
- (setf (avl-tree--node-balance br) (if (< b2 0) +1 0))
- (setf (avl-tree--node-balance p1) (if (> b2 0) -1 0))
- (setf (avl-tree--node-branch node branch) p2))
- (setf (avl-tree--node-balance (avl-tree--node-branch node branch)) 0)
+ ;; Double rotation.
+ (setf p2 (avl-tree--node-branch p1 opp)
+ b2 (avl-tree--node-balance p2)
+ (avl-tree--node-branch p1 opp)
+ (avl-tree--node-branch p2 dir)
+ (avl-tree--node-branch p2 dir) p1
+ (avl-tree--node-branch br dir)
+ (avl-tree--node-branch p2 opp)
+ (avl-tree--node-branch p2 opp) br
+ (avl-tree--node-balance br)
+ (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))
nil))))
(defun avl-tree--do-enter (cmpfun root branch data)
@@ -313,11 +307,11 @@
((funcall cmpfun data (avl-tree--node-data br))
(and (avl-tree--do-enter cmpfun br 0 data)
- (avl-tree--enter-balance2 root branch)))
+ (avl-tree--enter-balance root branch 0)))
((funcall cmpfun (avl-tree--node-data br) data)
(and (avl-tree--do-enter cmpfun br 1 data)
- (avl-tree--enter-balance1 root branch)))
+ (avl-tree--enter-balance root branch 1)))
(t
(setf (avl-tree--node-data br) data)
@@ -325,28 +319,31 @@
;; ----------------------------------------------------------------
-(defun avl-tree--mapc (map-function root)
+(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.
(let ((node root)
(stack nil)
- (go-left t))
+ (go-dir t))
(push nil stack)
(while node
- (if (and go-left
- (avl-tree--node-left node))
- ;; Do the left subtree first.
+ (if (and go-dir
+ (avl-tree--node-branch node dir))
+ ;; Do the DIR subtree first.
(progn
(push node stack)
- (setq node (avl-tree--node-left node)))
+ (setq node (avl-tree--node-branch node dir)))
;; Apply the function...
(funcall map-function node)
- ;; and do the right subtree.
- (setq node (if (setq go-left (avl-tree--node-right node))
- (avl-tree--node-right node)
+ ;; and do the opposite subtree.
+ (setq node (if (setq go-dir (avl-tree--node-branch
+ node (avl-tree--switch-dir dir)))
+ (avl-tree--node-branch
+ node (avl-tree--switch-dir dir))
(pop stack)))))))
(defun avl-tree--do-copy (root)
@@ -360,14 +357,19 @@
(avl-tree--node-data root)
(avl-tree--node-balance root))))
-\f
+
;; ================================================================
;;; The public functions which operate on AVL trees.
-(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.")
(defun avl-tree-empty (tree)
"Return t if avl tree TREE is emtpy, otherwise return nil."
@@ -377,9 +379,9 @@
"In the avl tree TREE insert DATA.
Return DATA."
(avl-tree--do-enter (avl-tree--cmpfun tree)
- (avl-tree--dummyroot tree)
- 0
- data)
+ (avl-tree--dummyroot tree)
+ 0
+ data)
data)
(defun avl-tree-delete (tree data)
@@ -397,29 +399,33 @@
`avl-tree-create' when TREE was created.
If there is no such element in the tree, the value is nil."
- (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)))
-(defun avl-tree-map (__map-function__ tree)
- "Apply __MAP-FUNCTION__ to all elements in the avl tree TREE."
+(defun avl-tree-map (__map-function__ tree &optional reverse)
+ "Modify all elements in the avl tree TREE by applying FUNCTION.
+
+Each element is replaced by the return value of FUNCTION applied
+to that element.
+
+FUNCTION is applied to the elements in ascending order, or
+descending order if REVERSE is non-nil."
(avl-tree--mapc
(lambda (node)
(setf (avl-tree--node-data node)
(funcall __map-function__ (avl-tree--node-data node))))
- (avl-tree--root tree)))
+ (avl-tree--root tree)
+ (if reverse 1 0)))
(defun avl-tree-first (tree)
"Return the first element in TREE, or nil if TREE is empty."
@@ -445,19 +451,18 @@
(defun avl-tree-flatten (tree)
"Return a sorted list containing all elements of TREE."
- (nreverse
(let ((treelist nil))
(avl-tree--mapc
(lambda (node) (push (avl-tree--node-data node) treelist))
- (avl-tree--root tree))
- treelist)))
+ (avl-tree--root tree) 1)
+ treelist))
(defun avl-tree-size (tree)
"Return the number of elements in TREE."
(let ((treesize 0))
(avl-tree--mapc
(lambda (data) (setq treesize (1+ treesize)))
- (avl-tree--root tree))
+ (avl-tree--root tree) 0)
treesize))
(defun avl-tree-clear (tree)
[-- Attachment #3: avl-tree.el.2.diff --]
[-- Type: text/plain, Size: 13773 bytes --]
--- avl-tree1.el 2009-11-22 22:15:16.000000000 +0000
+++ avl-tree2.el 2009-11-22 22:15:20.000000000 +0000
@@ -6,7 +6,7 @@
;; Inge Wallin <inge@lysator.liu.se>
;; Thomas Bellman <bellman@lysator.liu.se>
;; modified by Toby Cubitt <toby-predictive@dr-qubit.org>
-;; Version: 0.1
+;; Version: 0.2
;; Maintainer: FSF
;; Created: 10 May 1991
;; Keywords: extensions, data structures, AVL, tree
@@ -54,6 +54,13 @@
;;; Change log:
;;
+;; Version 0.2
+;; * added new optional arguments to `avl-tree-member', `avl-tree-enter'
+;; and `avl-tree-delete'
+;; * added `avl-tree-member-p', `avl-tree-mapc', `avl-tree-mapcar',
+;; `avl-tree-mapf', `avl-tree-stack', `avl-tree-stack-pop' and
+;; `avl-tree-stack-first' functions
+;;
;; Version 0.1
;; * simplified rebalancing code
;; * added optional direction argument to `avl-tree-map'
@@ -211,36 +218,49 @@
(avl-tree--node-left br))
t)))
-(defun avl-tree--do-delete (cmpfun root branch data)
- ;; Return t if the height of the tree has shrunk.
+(defun avl-tree--do-delete (cmpfun root branch data test nilflag)
+ ;; Return (<shrunk> . <data>), where <shrunk> is t if the height of
+ ;; the tree has shrunk and nil otherwise, and <data> is the releted
+ ;; data.
(let ((br (avl-tree--node-branch root branch)))
(cond
+ ;; DATA not in tree.
((null br)
- nil)
+ (cons nil nilflag))
((funcall cmpfun data (avl-tree--node-data br))
- (if (avl-tree--do-delete cmpfun br 0 data)
- (avl-tree--del-balance root branch 0)))
+ (let ((ret (avl-tree--do-delete cmpfun br 0 data test nilflag)))
+ (cons (if (car ret) (avl-tree--del-balance root branch 0))
+ (cdr ret))))
((funcall cmpfun (avl-tree--node-data br) data)
- (if (avl-tree--do-delete cmpfun br 1 data)
- (avl-tree--del-balance root branch 1)))
+ (let ((ret (avl-tree--do-delete cmpfun br 1 data test nilflag)))
+ (cons (if (car ret) (avl-tree--del-balance root branch 1))
+ (cdr ret))))
+
+ (t ; Found it.
+ ;; if it fails TEST, do nothing
+ (if (and test (not (funcall test (avl-tree--node-data br))))
+ (cons nil nilflag)
+ (cond
+ ((null (avl-tree--node-right br))
+ (setf (avl-tree--node-branch root branch)
+ (avl-tree--node-left br))
+ (cons t (avl-tree--node-data br)))
+
+ ((null (avl-tree--node-left br))
+ (setf (avl-tree--node-branch root branch)
+ (avl-tree--node-right br))
+ (cons t (avl-tree--node-data br)))
+
+ (t
+ (if (avl-tree--do-del-internal br 0 br)
+ (cons (avl-tree--del-balance root branch 0)
+ (avl-tree--node-data br))
+ (cons nil (avl-tree--node-data br))))
+ ))))))
+
- (t
- ;; Found it. Let's delete it.
- (cond
- ((null (avl-tree--node-right br))
- (setf (avl-tree--node-branch root branch) (avl-tree--node-left br))
- t)
-
- ((null (avl-tree--node-left br))
- (setf (avl-tree--node-branch root branch)
- (avl-tree--node-right br))
- t)
-
- (t
- (if (avl-tree--do-del-internal br 0 br)
- (avl-tree--del-balance root branch 0))))))))
;; ----------------------------------------------------------------
;; Entering data
@@ -295,27 +315,42 @@
(avl-tree--node-branch node branch)) 0))
nil))))
-(defun avl-tree--do-enter (cmpfun root branch data)
- ;; Return t if height of tree ROOT has grown. INTERNAL USE ONLY.
+(defun avl-tree--do-enter (cmpfun root branch data &optional updatefun)
+ ;; Return cons cell (<grew> . <data>), where <grew> is t if height of
+ ;; tree ROOT has grown and nil otherwise, and <data> is the inserted
+ ;; data.
(let ((br (avl-tree--node-branch root branch)))
(cond
((null br)
;; Data not in tree, insert it.
(setf (avl-tree--node-branch root branch)
(avl-tree--node-create nil nil data 0))
- t)
+ (cons t data))
((funcall cmpfun data (avl-tree--node-data br))
- (and (avl-tree--do-enter cmpfun br 0 data)
- (avl-tree--enter-balance root branch 0)))
+ (let ((ret (avl-tree--do-enter cmpfun br 0 data updatefun)))
+ (cons (and (car ret) (avl-tree--enter-balance root branch 0))
+ (cdr ret))))
((funcall cmpfun (avl-tree--node-data br) data)
- (and (avl-tree--do-enter cmpfun br 1 data)
- (avl-tree--enter-balance root branch 1)))
+ (let ((ret (avl-tree--do-enter cmpfun br 1 data updatefun)))
+ (cons (and (car ret) (avl-tree--enter-balance root branch 1))
+ (cdr ret))))
+ ;; Data already in tree, update it.
(t
- (setf (avl-tree--node-data br) data)
- nil))))
+ (let ((newdata
+ (if updatefun
+ (funcall updatefun data (avl-tree--node-data br))
+ data)))
+ (if (or (funcall cmpfun newdata data)
+ (funcall cmpfun data newdata))
+ (error "avl-tree-enter:\
+ updated data does not match existing data"))
+ (setf (avl-tree--node-data br) newdata)
+ (cons nil newdata)) ; return value
+ ))))
+
;; ----------------------------------------------------------------
@@ -357,6 +392,30 @@
(avl-tree--node-data root)
(avl-tree--node-balance root))))
+(defstruct (avl-tree--stack
+ (:constructor nil)
+ (:constructor avl-tree--stack-create
+ (tree &optional reverse
+ &aux
+ (store
+ (if (avl-tree-empty tree)
+ nil
+ (list (avl-tree--root tree))))))
+ (:copier nil))
+ reverse store)
+
+(defalias 'avl-tree-stack-p 'avl-tree--stack-p
+ "Return t if argument is an avl-tree-stack, nil otherwise.")
+
+(defun avl-tree--stack-repopulate (stack)
+ ;; Recursively push children of the node at the head of STACK onto the
+ ;; front of the STACK, until a leaf is reached.
+ (let ((node (car (avl-tree--stack-store stack)))
+ (dir (if (avl-tree--stack-reverse stack) 1 0)))
+ (when node ; check for emtpy stack
+ (while (setq node (avl-tree--node-branch node dir))
+ (push node (avl-tree--stack-store stack))))))
+
;; ================================================================
;;; The public functions which operate on AVL trees.
@@ -375,30 +434,56 @@
"Return t if avl tree TREE is emtpy, otherwise return nil."
(null (avl-tree--root tree)))
-(defun avl-tree-enter (tree data)
- "In the avl tree TREE insert DATA.
-Return DATA."
- (avl-tree--do-enter (avl-tree--cmpfun tree)
- (avl-tree--dummyroot tree)
- 0
- data)
- data)
-
-(defun avl-tree-delete (tree data)
- "From the avl tree TREE, delete DATA.
-Return the element in TREE which matched DATA,
-nil if no element matched."
- (avl-tree--do-delete (avl-tree--cmpfun tree)
- (avl-tree--dummyroot tree)
- 0
- data))
+(defun avl-tree-enter (tree data &optional updatefun)
+ "Insert DATA into the avl tree TREE.
+
+If an element that matches DATA (according to the tree's
+comparison function, see `avl-tree-create') already exists in
+TREE, it will be replaced by DATA by default.
+
+If UPDATEFUN is supplied and an element matching DATA already
+exists in TREE, UPDATEFUN is called with two arguments: DATA, and
+the matching element. Its return value replaces the existing
+element. This value *must* itself match DATA (and hence the
+pre-existing data), or an error will occur.
+
+Returns the new data."
+ (cdr (avl-tree--do-enter (avl-tree--cmpfun tree)
+ (avl-tree--dummyroot tree)
+ 0 data updatefun)))
+
+(defun avl-tree-delete (tree data &optional test nilflag)
+ "Delete the element matching DATA from the avl tree TREE.
+Matching uses the comparison function previously specified in
+`avl-tree-create' when TREE was created.
+
+Returns the deleted element, or nil if no matching element was
+found.
+
+Optional argument NILFLAG specifies a value to return instead of
+nil if nothing was deleted, so that this case can be
+distinguished from the case of a successfully deleted null
+element.
+
+If supplied, TEST specifies a test that a matching element must
+pass before it is deleted. If a matching element is found, it is
+passed as an argument to TEST, and is deleted only if the return
+value is non-nil."
+ (cdr (avl-tree--do-delete (avl-tree--cmpfun tree)
+ (avl-tree--dummyroot tree)
+ 0 data test nilflag)))
-(defun avl-tree-member (tree data)
+
+(defun avl-tree-member (tree data &optional nilflag)
"Return the element in the avl tree TREE which matches DATA.
-Matching uses the compare function previously specified in
+Matching uses the comparison function previously specified in
`avl-tree-create' when TREE was created.
-If there is no such element in the tree, the value is nil."
+If there is no such element in the tree, nil is
+returned. Optional argument NILFLAG specifies a value to return
+instead of nil in this case. This allows non-existent elements to
+be distinguished from a null element. (See also
+`avl-tree-member-p', which does this for you.)"
(let ((node (avl-tree--root tree)))
(catch 'found
(while node
@@ -410,7 +495,16 @@
(avl-tree--node-data node) data)
(setq node (avl-tree--node-right node)))
(t (throw 'found (avl-tree--node-data node)))))
- nil)))
+ nilflag)))
+
+
+(defun avl-tree-member-p (tree data)
+ "Return t if an element matching DATA exists in the avl tree TREE,
+otherwise return nil. Matching uses the comparison function
+previously specified in `avl-tree-create' when TREE was created."
+ (let ((flag '(nil)))
+ (not (eq (avl-tree-member tree data flag) flag))))
+
(defun avl-tree-map (__map-function__ tree &optional reverse)
"Modify all elements in the avl tree TREE by applying FUNCTION.
@@ -427,6 +521,57 @@
(avl-tree--root tree)
(if reverse 1 0)))
+
+(defun avl-tree-mapc (__map-function__ tree &optional reverse)
+ "Apply FUNCTION to all elements in avl tree TREE,
+for side-effect only.
+
+FUNCTION is applied to the elements in ascending order, or
+descending order if REVERSE is non-nil."
+ (avl-tree--mapc
+ (lambda (node)
+ (funcall __map-function__ (avl-tree--node-data node)))
+ (avl-tree--root tree)
+ (if reverse 1 0)))
+
+
+(defun avl-tree-mapf
+ (__map-function__ combinator tree &optional reverse)
+ "Apply FUNCTION to all elements in avl tree TREE,
+and combine the results using COMBINATOR.
+
+The FUNCTION is applied and the results are combined in ascending
+order, or descending order if REVERSE is non-nil."
+ (let (avl-tree-mapf--accumulate)
+ (avl-tree--mapc
+ (lambda (node)
+ (setq avl-tree-mapf--accumulate
+ (funcall combinator
+ (funcall __map-function__
+ (avl-tree--node-data node))
+ avl-tree-mapf--accumulate)))
+ (avl-tree--root tree)
+ (if reverse 0 1))
+ (nreverse avl-tree-mapf--accumulate)))
+
+
+(defun avl-tree-mapcar (__map-function__ tree &optional reverse)
+ "Apply FUNCTION to all elements in avl tree TREE,
+and make a list of the results.
+
+The FUNCTION is applied and the list constructed in ascending
+order, or descending order if REVERSE is non-nil.
+
+Note that if you don't care about the order in which FUNCTION is
+applied, just that the resulting list is in the correct order,
+then
+
+ (avl-tree-mapf function 'cons tree (not reverse))
+
+is more efficient."
+ (nreverse (avl-tree-mapf __map-function__ 'cons tree reverse)))
+
+
(defun avl-tree-first (tree)
"Return the first element in TREE, or nil if TREE is empty."
(let ((node (avl-tree--root tree)))
@@ -469,6 +614,65 @@
"Clear the avl tree TREE."
(setf (avl-tree--root tree) nil))
+
+(defun avl-tree-stack (tree &optional reverse)
+ "Return an object that behaves like a sorted stack
+of all elements of TREE.
+
+If REVERSE is non-nil, the stack is sorted in reverse order.
+\(See also `avl-tree-stack-pop'\).
+
+Note that any modification to TREE *immediately* invalidates all
+avl-tree-stacks created before the modification (in particular,
+calling `avl-tree-stack-pop' will give unpredictable results).
+
+Operations on these objects are significantly more efficient than
+constructing a real stack with `avl-tree-flatten' and using
+standard stack functions. As such, they can be useful in
+implementing efficient algorithms of AVL trees. However, in cases
+where mapping functions `avl-tree-mapc', `avl-tree-mapcar' or
+`avl-tree-mapf' would be sufficient, it is better to use one of
+those instead."
+ (let ((stack (avl-tree--stack-create tree reverse)))
+ (avl-tree--stack-repopulate stack)
+ stack))
+
+
+(defun avl-tree-stack-pop (avl-tree-stack &optional nilflag)
+ "Pop the first element from AVL-TREE-STACK.
+\(See also `avl-tree-stack'\).
+
+Returns nil if the stack is empty, or NILFLAG if specified. (The
+latter allows an empty stack to be distinguished from a null
+element stored in the AVL tree.)"
+ (let (node next)
+ (if (not (setq node (pop (avl-tree--stack-store avl-tree-stack))))
+ nilflag
+ (when (setq next
+ (avl-tree--node-branch
+ node
+ (if (avl-tree--stack-reverse avl-tree-stack) 0 1)))
+ (push next (avl-tree--stack-store avl-tree-stack))
+ (avl-tree--stack-repopulate avl-tree-stack))
+ (avl-tree--node-data node))))
+
+
+(defun avl-tree-stack-first (avl-tree-stack &optional nilflag)
+ "Return the first element of AVL-TREE-STACK, without removing it
+from the stack.
+
+Returns nil if the stack is empty, or NILFLAG if specified. (The
+latter allows an empty stack to be distinguished from a null
+element stored in the AVL tree.)"
+ (or (car (avl-tree--stack-store avl-tree-stack))
+ nilflag))
+
+
+(defun avl-tree-stack-empty-p (avl-tree-stack)
+ "Return t if AVL-TREE-STACK is empty, nil otherwise."
+ (null (avl-tree--stack-store avl-tree-stack)))
+
+
(provide 'avl-tree)
;; arch-tag: 47e26701-43c9-4222-bd79-739eac6357a9
^ permalink raw reply [flat|nested] 7+ messages in thread
* bug#5015: avl-tree.el enhancements
2009-11-23 0:01 bug#5012: avl-tree.el enhancements Toby Cubitt
@ 2009-11-23 3:44 ` Stefan Monnier
2009-11-23 9:44 ` bug#5016: " Toby Cubitt
0 siblings, 1 reply; 7+ messages in thread
From: Stefan Monnier @ 2009-11-23 3:44 UTC (permalink / raw)
To: Toby Cubitt; +Cc: bug-gnu-emacs
> 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
^ permalink raw reply [flat|nested] 7+ messages in thread
* bug#5016: avl-tree.el enhancements
2009-11-23 3:44 ` bug#5015: " Stefan Monnier
@ 2009-11-23 9:44 ` Toby Cubitt
2009-11-23 14:58 ` bug#5021: " Stefan Monnier
0 siblings, 1 reply; 7+ messages in thread
From: Toby Cubitt @ 2009-11-23 9:44 UTC (permalink / raw)
To: Stefan Monnier; +Cc: bug-gnu-emacs
[-- Attachment #1: Type: text/plain, Size: 6313 bytes --]
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
[-- Attachment #2: avl-tree.el.1.diff --]
[-- Type: text/plain, Size: 23467 bytes --]
--- avl-tree.el 2009-11-22 22:10:09.000000000 +0000
+++ avl-tree1.el 2009-11-23 09:37:10.000000000 +0000
@@ -3,11 +3,13 @@
;; Copyright (C) 1995, 2007, 2008, 2009 Free Software Foundation, Inc.
;; Author: Per Cederqvist <ceder@lysator.liu.se>
-;; Inge Wallin <inge@lysator.liu.se>
-;; Thomas Bellman <bellman@lysator.liu.se>
+;; Inge Wallin <inge@lysator.liu.se>
+;; Thomas Bellman <bellman@lysator.liu.se>
+;; modified by Toby Cubitt <toby-predictive@dr-qubit.org>
+;; Version: 0.1
;; Maintainer: FSF
;; Created: 10 May 1991
-;; Keywords: extensions, data structures
+;; Keywords: extensions, data structures, AVL, tree
;; This file is part of GNU Emacs.
@@ -24,174 +26,189 @@
;; You should have received a copy of the GNU General Public License
;; along with GNU Emacs. If not, see <http://www.gnu.org/licenses/>.
-;;; Commentary:
-;; An AVL tree is a nearly-perfect balanced binary tree. A tree consists of
-;; two elements, the root node and the compare function. The actual tree
-;; has a dummy node as its root with the real root in the left pointer.
+;;; Commentary:
+;;
+;; An AVL tree is a self-balancing binary tree. As such, inserting,
+;; deleting, and retrieving data from an AVL tree containing n elements
+;; is O(log n). It is somewhat more rigidly balanced than other
+;; self-balancing binary trees (such as red-black trees and AA trees),
+;; making insertion slighty slower, deletion somewhat slower, and
+;; retrieval somewhat faster (the asymptotic scaling is of course the
+;; same for all types). Thus it may be a good choice when the tree will
+;; be relatively static, i.e. data will be retrieved more often than
+;; they are modified.
+;;
+;; Internally, a tree consists of two elements, the root node and the
+;; comparison function. The actual tree has a dummy node as its root
+;; with the real root in the left pointer, which allows the root node to
+;; be treated on a par with all other nodes.
;;
;; Each node of the tree consists of one data element, one left
-;; sub-tree and one right sub-tree. Each node also has a balance
-;; count, which is the difference in depth of the left and right
-;; sub-trees.
+;; sub-tree, one right sub-tree, and a balance count. The latter is the
+;; difference in depth of the left and right sub-trees.
;;
;; The functions with names of the form "avl-tree--" are intended for
;; internal use only.
+
+;;; Change log:
+;;
+;; Version 0.1
+;; * simplified rebalancing code
+;; * added optional direction argument to `avl-tree-map'
+
+
;;; Code:
(eval-when-compile (require 'cl))
-;; ================================================================
-;;; Functions and macros handling an AVL tree node.
-(defstruct (avl-tree--node
- ;; We force a representation without tag so it matches the
- ;; pre-defstruct representation. Also we use the underlying
- ;; representation in the implementation of avl-tree--node-branch.
- (:type vector)
- (:constructor nil)
- (:constructor avl-tree--node-create (left right data balance))
- (:copier nil))
- left right data balance)
-(defalias 'avl-tree--node-branch 'aref
- ;; This implementation is efficient but breaks the defstruct abstraction.
- ;; An alternative could be
- ;; (funcall (aref [avl-tree-left avl-tree-right avl-tree-data] branch) node)
- "Get value of a branch of a node.
+;; ================================================================
+;;; Internal functions and macros for use in the AVL tree package
-NODE is the node, and BRANCH is the branch.
-0 for left pointer, 1 for right pointer and 2 for the data.\"
-\(fn node branch)")
-;; The funcall/aref trick doesn't work for the setf method, unless we try
-;; and access the underlying setter function, but this wouldn't be
-;; portable either.
-(defsetf avl-tree--node-branch aset)
-\f
-;; ================================================================
-;;; Internal functions for use in the AVL tree package
+;; ----------------------------------------------------------------
+;; Functions and macros handling an AVL tree.
(defstruct (avl-tree-
;; A tagged list is the pre-defstruct representation.
;; (:type list)
:named
(:constructor nil)
- (:constructor avl-tree-create (cmpfun))
+ (:constructor avl-tree--create (cmpfun))
(:predicate avl-tree-p)
(:copier nil))
(dummyroot (avl-tree--node-create nil nil nil 0))
cmpfun)
+
(defmacro avl-tree--root (tree)
;; Return the root node for an avl-tree. INTERNAL USE ONLY.
- `(avl-tree--node-left (avl-tree--dummyroot tree)))
+ `(avl-tree--node-left (avl-tree--dummyroot ,tree)))
+
+
(defsetf avl-tree--root (tree) (node)
`(setf (avl-tree--node-left (avl-tree--dummyroot ,tree)) ,node))
+
+
;; ----------------------------------------------------------------
-;; Deleting data
+;; Functions and macros handling an AVL tree node.
-(defun avl-tree--del-balance1 (node branch)
- ;; Rebalance a tree and return t if the height of the tree has shrunk.
- (let ((br (avl-tree--node-branch node branch))
- p1 b1 p2 b2 result)
- (cond
- ((< (avl-tree--node-balance br) 0)
- (setf (avl-tree--node-balance br) 0)
- t)
+(defstruct (avl-tree--node
+ ;; We force a representation without tag so it matches the
+ ;; pre-defstruct representation. Also we use the underlying
+ ;; representation in the implementation of
+ ;; avl-tree--node-branch.
+ (:type vector)
+ (:constructor nil)
+ (:constructor avl-tree--node-create (left right data balance))
+ (:copier nil))
+ left right data balance)
- ((= (avl-tree--node-balance br) 0)
- (setf (avl-tree--node-balance br) +1)
- nil)
- (t
- ;; Rebalance.
- (setq p1 (avl-tree--node-right br)
- b1 (avl-tree--node-balance p1))
- (if (>= b1 0)
- ;; Single RR rotation.
- (progn
- (setf (avl-tree--node-right br) (avl-tree--node-left p1))
- (setf (avl-tree--node-left p1) br)
- (if (= 0 b1)
- (progn
- (setf (avl-tree--node-balance br) +1)
- (setf (avl-tree--node-balance p1) -1)
- (setq result nil))
- (setf (avl-tree--node-balance br) 0)
- (setf (avl-tree--node-balance p1) 0)
- (setq result t))
- (setf (avl-tree--node-branch node branch) p1)
- result)
-
- ;; Double RL rotation.
- (setq p2 (avl-tree--node-left p1)
- b2 (avl-tree--node-balance p2))
- (setf (avl-tree--node-left p1) (avl-tree--node-right p2))
- (setf (avl-tree--node-right p2) p1)
- (setf (avl-tree--node-right br) (avl-tree--node-left p2))
- (setf (avl-tree--node-left p2) br)
- (setf (avl-tree--node-balance br) (if (> b2 0) -1 0))
- (setf (avl-tree--node-balance p1) (if (< b2 0) +1 0))
- (setf (avl-tree--node-branch node branch) p2)
- (setf (avl-tree--node-balance p2) 0)
- t)))))
+(defalias 'avl-tree--node-branch 'aref
+ ;; This implementation is efficient but breaks the defstruct
+ ;; abstraction. An alternative could be (funcall (aref [avl-tree-left
+ ;; avl-tree-right avl-tree-data] branch) node)
+ "Get value of a branch of a node.
+NODE is the node, and BRANCH is the branch.
+0 for left pointer, 1 for right pointer and 2 for the data.")
+
+
+;; The funcall/aref trick wouldn't work for the setf method, unless we
+;; tried to access the underlying setter function, but this wouldn't be
+;; portable either.
+(defsetf avl-tree--node-branch aset)
-(defun avl-tree--del-balance2 (node branch)
+
+
+;; ----------------------------------------------------------------
+;; Convenience macros
+
+(defmacro avl-tree--switch-dir (dir)
+ ;; Return opposite direction to DIR (0 = left, 1 = right).
+ `(- 1 ,dir))
+
+(defmacro avl-tree--dir-to-sign (dir)
+ ;; Convert direction (0,1) to sign factor (-1,+1)
+ `(1- (* 2 ,dir)))
+
+(defmacro avl-tree--sign-to-dir (dir)
+ ;; Convert sign factor (-x,+x) to direction (0,1)
+ `(if (< ,dir 0) 0 1))
+
+
+;; ----------------------------------------------------------------
+;; Deleting data
+
+(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.
(let ((br (avl-tree--node-branch node branch))
- p1 b1 p2 b2 result)
+ ;; opposite direction: 0,1 -> 1,0
+ (opp (avl-tree--switch-dir dir))
+ ;; direction 0,1 -> sign factor -1,+1
+ (sgn (avl-tree--dir-to-sign dir))
+ p1 b1 p2 b2)
(cond
- ((> (avl-tree--node-balance br) 0)
+ ((> (* sgn (avl-tree--node-balance br)) 0)
(setf (avl-tree--node-balance br) 0)
t)
((= (avl-tree--node-balance br) 0)
- (setf (avl-tree--node-balance br) -1)
+ (setf (avl-tree--node-balance br) (- sgn))
nil)
(t
;; Rebalance.
- (setq p1 (avl-tree--node-left br)
+ (setq p1 (avl-tree--node-branch br opp)
b1 (avl-tree--node-balance p1))
- (if (<= b1 0)
- ;; Single LL rotation.
+ (if (<= (* sgn b1) 0)
+ ;; Single rotation.
(progn
- (setf (avl-tree--node-left br) (avl-tree--node-right p1))
- (setf (avl-tree--node-right p1) br)
+ (setf (avl-tree--node-branch br opp)
+ (avl-tree--node-branch p1 dir)
+ (avl-tree--node-branch p1 dir) br
+ (avl-tree--node-branch node branch) p1)
(if (= 0 b1)
(progn
- (setf (avl-tree--node-balance br) -1)
- (setf (avl-tree--node-balance p1) +1)
- (setq result nil))
+ (setf (avl-tree--node-balance br) (- sgn)
+ (avl-tree--node-balance p1) sgn)
+ nil) ; height hasn't changed
(setf (avl-tree--node-balance br) 0)
(setf (avl-tree--node-balance p1) 0)
- (setq result t))
- (setf (avl-tree--node-branch node branch) p1)
- result)
-
- ;; Double LR rotation.
- (setq p2 (avl-tree--node-right p1)
- b2 (avl-tree--node-balance p2))
- (setf (avl-tree--node-right p1) (avl-tree--node-left p2))
- (setf (avl-tree--node-left p2) p1)
- (setf (avl-tree--node-left br) (avl-tree--node-right p2))
- (setf (avl-tree--node-right p2) br)
- (setf (avl-tree--node-balance br) (if (< b2 0) +1 0))
- (setf (avl-tree--node-balance p1) (if (> b2 0) -1 0))
- (setf (avl-tree--node-branch node branch) p2)
- (setf (avl-tree--node-balance p2) 0)
+ t)) ; height has changed
+
+ ;; Double rotation.
+ (setf p2 (avl-tree--node-branch p1 dir)
+ b2 (avl-tree--node-balance p2)
+ (avl-tree--node-branch p1 dir)
+ (avl-tree--node-branch p2 opp)
+ (avl-tree--node-branch p2 opp) p1
+ (avl-tree--node-branch br opp)
+ (avl-tree--node-branch p2 dir)
+ (avl-tree--node-branch p2 dir) br
+ (avl-tree--node-balance br)
+ (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 p2) 0)
t)))))
(defun avl-tree--do-del-internal (node branch q)
(let ((br (avl-tree--node-branch node branch)))
(if (avl-tree--node-right br)
- (if (avl-tree--do-del-internal br +1 q)
- (avl-tree--del-balance2 node branch))
- (setf (avl-tree--node-data q) (avl-tree--node-data br))
- (setf (avl-tree--node-branch node branch)
- (avl-tree--node-left br))
+ (if (avl-tree--do-del-internal br 1 q)
+ (avl-tree--del-balance node branch 1))
+ (setf (avl-tree--node-data q) (avl-tree--node-data br)
+ (avl-tree--node-branch node branch)
+ (avl-tree--node-left br))
t)))
(defun avl-tree--do-delete (cmpfun root branch data)
@@ -203,102 +220,79 @@
((funcall cmpfun data (avl-tree--node-data br))
(if (avl-tree--do-delete cmpfun br 0 data)
- (avl-tree--del-balance1 root branch)))
+ (avl-tree--del-balance root branch 0)))
((funcall cmpfun (avl-tree--node-data br) data)
(if (avl-tree--do-delete cmpfun br 1 data)
- (avl-tree--del-balance2 root branch)))
+ (avl-tree--del-balance root branch 1)))
(t
;; Found it. Let's delete it.
(cond
((null (avl-tree--node-right br))
- (setf (avl-tree--node-branch root branch) (avl-tree--node-left br))
- t)
+ (setf (avl-tree--node-branch root branch) (avl-tree--node-left br))
+ t)
((null (avl-tree--node-left br))
- (setf (avl-tree--node-branch root branch) (avl-tree--node-right br))
- t)
+ (setf (avl-tree--node-branch root branch)
+ (avl-tree--node-right br))
+ t)
(t
- (if (avl-tree--do-del-internal br 0 br)
- (avl-tree--del-balance1 root branch))))))))
+ (if (avl-tree--do-del-internal br 0 br)
+ (avl-tree--del-balance root branch 0))))))))
;; ----------------------------------------------------------------
;; Entering data
-(defun avl-tree--enter-balance1 (node branch)
- ;; Rebalance a tree and return t if the height of the tree has grown.
+(defun avl-tree--enter-balance (node branch dir)
+ ;; Rebalance tree at the left (BRANCH=0) or right (BRANCH=1) child of
+ ;; NODE after an insertion into the left (DIR=0) or right (DIR=1)
+ ;; sub-tree of that child. Return t if the height of the tree has
+ ;; grown.
(let ((br (avl-tree--node-branch node branch))
+ ;; opposite direction: 0,1 -> 1,0
+ (opp (avl-tree--switch-dir dir))
+ ;; direction 0,1 -> sign factor -1,+1
+ (sgn (avl-tree--dir-to-sign dir))
p1 p2 b2 result)
(cond
- ((< (avl-tree--node-balance br) 0)
+ ((< (* sgn (avl-tree--node-balance br)) 0)
(setf (avl-tree--node-balance br) 0)
nil)
((= (avl-tree--node-balance br) 0)
- (setf (avl-tree--node-balance br) +1)
+ (setf (avl-tree--node-balance br) sgn)
t)
(t
;; Tree has grown => Rebalance.
- (setq p1 (avl-tree--node-right br))
- (if (> (avl-tree--node-balance p1) 0)
- ;; Single RR rotation.
+ (setq p1 (avl-tree--node-branch br dir))
+ (if (> (* sgn (avl-tree--node-balance p1)) 0)
+ ;; Single rotation.
(progn
- (setf (avl-tree--node-right br) (avl-tree--node-left p1))
- (setf (avl-tree--node-left p1) br)
+ (setf (avl-tree--node-branch br dir)
+ (avl-tree--node-branch p1 opp))
+ (setf (avl-tree--node-branch p1 opp) br)
(setf (avl-tree--node-balance br) 0)
(setf (avl-tree--node-branch node branch) p1))
- ;; Double RL rotation.
- (setq p2 (avl-tree--node-left p1)
- b2 (avl-tree--node-balance p2))
- (setf (avl-tree--node-left p1) (avl-tree--node-right p2))
- (setf (avl-tree--node-right p2) p1)
- (setf (avl-tree--node-right br) (avl-tree--node-left p2))
- (setf (avl-tree--node-left p2) br)
- (setf (avl-tree--node-balance br) (if (> b2 0) -1 0))
- (setf (avl-tree--node-balance p1) (if (< b2 0) +1 0))
- (setf (avl-tree--node-branch node branch) p2))
- (setf (avl-tree--node-balance (avl-tree--node-branch node branch)) 0)
- nil))))
-
-(defun avl-tree--enter-balance2 (node branch)
- ;; Return t if the tree has grown.
- (let ((br (avl-tree--node-branch node branch))
- p1 p2 b2)
- (cond
- ((> (avl-tree--node-balance br) 0)
- (setf (avl-tree--node-balance br) 0)
- nil)
-
- ((= (avl-tree--node-balance br) 0)
- (setf (avl-tree--node-balance br) -1)
- t)
-
- (t
- ;; Balance was -1 => Rebalance.
- (setq p1 (avl-tree--node-left br))
- (if (< (avl-tree--node-balance p1) 0)
- ;; Single LL rotation.
- (progn
- (setf (avl-tree--node-left br) (avl-tree--node-right p1))
- (setf (avl-tree--node-right p1) br)
- (setf (avl-tree--node-balance br) 0)
- (setf (avl-tree--node-branch node branch) p1))
-
- ;; Double LR rotation.
- (setq p2 (avl-tree--node-right p1)
- b2 (avl-tree--node-balance p2))
- (setf (avl-tree--node-right p1) (avl-tree--node-left p2))
- (setf (avl-tree--node-left p2) p1)
- (setf (avl-tree--node-left br) (avl-tree--node-right p2))
- (setf (avl-tree--node-right p2) br)
- (setf (avl-tree--node-balance br) (if (< b2 0) +1 0))
- (setf (avl-tree--node-balance p1) (if (> b2 0) -1 0))
- (setf (avl-tree--node-branch node branch) p2))
- (setf (avl-tree--node-balance (avl-tree--node-branch node branch)) 0)
+ ;; Double rotation.
+ (setf p2 (avl-tree--node-branch p1 opp)
+ b2 (avl-tree--node-balance p2)
+ (avl-tree--node-branch p1 opp)
+ (avl-tree--node-branch p2 dir)
+ (avl-tree--node-branch p2 dir) p1
+ (avl-tree--node-branch br dir)
+ (avl-tree--node-branch p2 opp)
+ (avl-tree--node-branch p2 opp) br
+ (avl-tree--node-balance br)
+ (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))
nil))))
(defun avl-tree--do-enter (cmpfun root branch data)
@@ -313,11 +307,11 @@
((funcall cmpfun data (avl-tree--node-data br))
(and (avl-tree--do-enter cmpfun br 0 data)
- (avl-tree--enter-balance2 root branch)))
+ (avl-tree--enter-balance root branch 0)))
((funcall cmpfun (avl-tree--node-data br) data)
(and (avl-tree--do-enter cmpfun br 1 data)
- (avl-tree--enter-balance1 root branch)))
+ (avl-tree--enter-balance root branch 1)))
(t
(setf (avl-tree--node-data br) data)
@@ -325,28 +319,31 @@
;; ----------------------------------------------------------------
-(defun avl-tree--mapc (map-function root)
+(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.
(let ((node root)
(stack nil)
- (go-left t))
+ (go-dir t))
(push nil stack)
(while node
- (if (and go-left
- (avl-tree--node-left node))
- ;; Do the left subtree first.
+ (if (and go-dir
+ (avl-tree--node-branch node dir))
+ ;; Do the DIR subtree first.
(progn
(push node stack)
- (setq node (avl-tree--node-left node)))
+ (setq node (avl-tree--node-branch node dir)))
;; Apply the function...
(funcall map-function node)
- ;; and do the right subtree.
- (setq node (if (setq go-left (avl-tree--node-right node))
- (avl-tree--node-right node)
+ ;; and do the opposite subtree.
+ (setq node (if (setq go-dir (avl-tree--node-branch
+ node (avl-tree--switch-dir dir)))
+ (avl-tree--node-branch
+ node (avl-tree--switch-dir dir))
(pop stack)))))))
(defun avl-tree--do-copy (root)
@@ -360,14 +357,19 @@
(avl-tree--node-data root)
(avl-tree--node-balance root))))
-\f
+
;; ================================================================
;;; The public functions which operate on AVL trees.
-(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.")
(defun avl-tree-empty (tree)
"Return t if avl tree TREE is emtpy, otherwise return nil."
@@ -377,9 +379,9 @@
"In the avl tree TREE insert DATA.
Return DATA."
(avl-tree--do-enter (avl-tree--cmpfun tree)
- (avl-tree--dummyroot tree)
- 0
- data)
+ (avl-tree--dummyroot tree)
+ 0
+ data)
data)
(defun avl-tree-delete (tree data)
@@ -398,28 +400,31 @@
If there is no such element in the tree, the value is nil."
(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)
+ (compare-function (avl-tree--cmpfun tree)))
+ (catch 'found
+ (while node
+ (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 (throw 'found (avl-tree--node-data node)))))
nil)))
-(defun avl-tree-map (__map-function__ tree)
- "Apply __MAP-FUNCTION__ to all elements in the avl tree TREE."
+(defun avl-tree-map (__map-function__ tree &optional reverse)
+ "Modify all elements in the avl tree TREE by applying FUNCTION.
+
+Each element is replaced by the return value of FUNCTION applied
+to that element.
+
+FUNCTION is applied to the elements in ascending order, or
+descending order if REVERSE is non-nil."
(avl-tree--mapc
(lambda (node)
(setf (avl-tree--node-data node)
(funcall __map-function__ (avl-tree--node-data node))))
- (avl-tree--root tree)))
+ (avl-tree--root tree)
+ (if reverse 1 0)))
(defun avl-tree-first (tree)
"Return the first element in TREE, or nil if TREE is empty."
@@ -445,19 +450,18 @@
(defun avl-tree-flatten (tree)
"Return a sorted list containing all elements of TREE."
- (nreverse
(let ((treelist nil))
(avl-tree--mapc
(lambda (node) (push (avl-tree--node-data node) treelist))
- (avl-tree--root tree))
- treelist)))
+ (avl-tree--root tree) 1)
+ treelist))
(defun avl-tree-size (tree)
"Return the number of elements in TREE."
(let ((treesize 0))
(avl-tree--mapc
(lambda (data) (setq treesize (1+ treesize)))
- (avl-tree--root tree))
+ (avl-tree--root tree) 0)
treesize))
(defun avl-tree-clear (tree)
[-- Attachment #3: avl-tree.el.2.diff --]
[-- Type: text/plain, Size: 13823 bytes --]
--- avl-tree1.el 2009-11-23 09:37:10.000000000 +0000
+++ avl-tree2.el 2009-11-23 09:37:10.000000000 +0000
@@ -6,7 +6,7 @@
;; Inge Wallin <inge@lysator.liu.se>
;; Thomas Bellman <bellman@lysator.liu.se>
;; modified by Toby Cubitt <toby-predictive@dr-qubit.org>
-;; Version: 0.1
+;; Version: 0.2
;; Maintainer: FSF
;; Created: 10 May 1991
;; Keywords: extensions, data structures, AVL, tree
@@ -54,6 +54,13 @@
;;; Change log:
;;
+;; Version 0.2
+;; * added new optional arguments to `avl-tree-member', `avl-tree-enter'
+;; and `avl-tree-delete'
+;; * added `avl-tree-member-p', `avl-tree-mapc', `avl-tree-mapcar',
+;; `avl-tree-mapf', `avl-tree-stack', `avl-tree-stack-pop' and
+;; `avl-tree-stack-first' functions
+;;
;; Version 0.1
;; * simplified rebalancing code
;; * added optional direction argument to `avl-tree-map'
@@ -211,36 +218,49 @@
(avl-tree--node-left br))
t)))
-(defun avl-tree--do-delete (cmpfun root branch data)
- ;; Return t if the height of the tree has shrunk.
+(defun avl-tree--do-delete (cmpfun root branch data test nilflag)
+ ;; Return (<shrunk> . <data>), where <shrunk> is t if the height of
+ ;; the tree has shrunk and nil otherwise, and <data> is the releted
+ ;; data.
(let ((br (avl-tree--node-branch root branch)))
(cond
+ ;; DATA not in tree.
((null br)
- nil)
+ (cons nil nilflag))
((funcall cmpfun data (avl-tree--node-data br))
- (if (avl-tree--do-delete cmpfun br 0 data)
- (avl-tree--del-balance root branch 0)))
+ (let ((ret (avl-tree--do-delete cmpfun br 0 data test nilflag)))
+ (cons (if (car ret) (avl-tree--del-balance root branch 0))
+ (cdr ret))))
((funcall cmpfun (avl-tree--node-data br) data)
- (if (avl-tree--do-delete cmpfun br 1 data)
- (avl-tree--del-balance root branch 1)))
+ (let ((ret (avl-tree--do-delete cmpfun br 1 data test nilflag)))
+ (cons (if (car ret) (avl-tree--del-balance root branch 1))
+ (cdr ret))))
+
+ (t ; Found it.
+ ;; if it fails TEST, do nothing
+ (if (and test (not (funcall test (avl-tree--node-data br))))
+ (cons nil nilflag)
+ (cond
+ ((null (avl-tree--node-right br))
+ (setf (avl-tree--node-branch root branch)
+ (avl-tree--node-left br))
+ (cons t (avl-tree--node-data br)))
+
+ ((null (avl-tree--node-left br))
+ (setf (avl-tree--node-branch root branch)
+ (avl-tree--node-right br))
+ (cons t (avl-tree--node-data br)))
+
+ (t
+ (if (avl-tree--do-del-internal br 0 br)
+ (cons (avl-tree--del-balance root branch 0)
+ (avl-tree--node-data br))
+ (cons nil (avl-tree--node-data br))))
+ ))))))
+
- (t
- ;; Found it. Let's delete it.
- (cond
- ((null (avl-tree--node-right br))
- (setf (avl-tree--node-branch root branch) (avl-tree--node-left br))
- t)
-
- ((null (avl-tree--node-left br))
- (setf (avl-tree--node-branch root branch)
- (avl-tree--node-right br))
- t)
-
- (t
- (if (avl-tree--do-del-internal br 0 br)
- (avl-tree--del-balance root branch 0))))))))
;; ----------------------------------------------------------------
;; Entering data
@@ -295,27 +315,42 @@
(avl-tree--node-branch node branch)) 0))
nil))))
-(defun avl-tree--do-enter (cmpfun root branch data)
- ;; Return t if height of tree ROOT has grown. INTERNAL USE ONLY.
+(defun avl-tree--do-enter (cmpfun root branch data &optional updatefun)
+ ;; Return cons cell (<grew> . <data>), where <grew> is t if height of
+ ;; tree ROOT has grown and nil otherwise, and <data> is the inserted
+ ;; data.
(let ((br (avl-tree--node-branch root branch)))
(cond
((null br)
;; Data not in tree, insert it.
(setf (avl-tree--node-branch root branch)
(avl-tree--node-create nil nil data 0))
- t)
+ (cons t data))
((funcall cmpfun data (avl-tree--node-data br))
- (and (avl-tree--do-enter cmpfun br 0 data)
- (avl-tree--enter-balance root branch 0)))
+ (let ((ret (avl-tree--do-enter cmpfun br 0 data updatefun)))
+ (cons (and (car ret) (avl-tree--enter-balance root branch 0))
+ (cdr ret))))
((funcall cmpfun (avl-tree--node-data br) data)
- (and (avl-tree--do-enter cmpfun br 1 data)
- (avl-tree--enter-balance root branch 1)))
+ (let ((ret (avl-tree--do-enter cmpfun br 1 data updatefun)))
+ (cons (and (car ret) (avl-tree--enter-balance root branch 1))
+ (cdr ret))))
+ ;; Data already in tree, update it.
(t
- (setf (avl-tree--node-data br) data)
- nil))))
+ (let ((newdata
+ (if updatefun
+ (funcall updatefun data (avl-tree--node-data br))
+ data)))
+ (if (or (funcall cmpfun newdata data)
+ (funcall cmpfun data newdata))
+ (error "avl-tree-enter:\
+ updated data does not match existing data"))
+ (setf (avl-tree--node-data br) newdata)
+ (cons nil newdata)) ; return value
+ ))))
+
;; ----------------------------------------------------------------
@@ -357,6 +392,30 @@
(avl-tree--node-data root)
(avl-tree--node-balance root))))
+(defstruct (avl-tree--stack
+ (:constructor nil)
+ (:constructor avl-tree--stack-create
+ (tree &optional reverse
+ &aux
+ (store
+ (if (avl-tree-empty tree)
+ nil
+ (list (avl-tree--root tree))))))
+ (:copier nil))
+ reverse store)
+
+(defalias 'avl-tree-stack-p 'avl-tree--stack-p
+ "Return t if argument is an avl-tree-stack, nil otherwise.")
+
+(defun avl-tree--stack-repopulate (stack)
+ ;; Recursively push children of the node at the head of STACK onto the
+ ;; front of the STACK, until a leaf is reached.
+ (let ((node (car (avl-tree--stack-store stack)))
+ (dir (if (avl-tree--stack-reverse stack) 1 0)))
+ (when node ; check for emtpy stack
+ (while (setq node (avl-tree--node-branch node dir))
+ (push node (avl-tree--stack-store stack))))))
+
;; ================================================================
;;; The public functions which operate on AVL trees.
@@ -375,30 +434,56 @@
"Return t if avl tree TREE is emtpy, otherwise return nil."
(null (avl-tree--root tree)))
-(defun avl-tree-enter (tree data)
- "In the avl tree TREE insert DATA.
-Return DATA."
- (avl-tree--do-enter (avl-tree--cmpfun tree)
- (avl-tree--dummyroot tree)
- 0
- data)
- data)
-
-(defun avl-tree-delete (tree data)
- "From the avl tree TREE, delete DATA.
-Return the element in TREE which matched DATA,
-nil if no element matched."
- (avl-tree--do-delete (avl-tree--cmpfun tree)
- (avl-tree--dummyroot tree)
- 0
- data))
+(defun avl-tree-enter (tree data &optional updatefun)
+ "Insert DATA into the avl tree TREE.
+
+If an element that matches DATA (according to the tree's
+comparison function, see `avl-tree-create') already exists in
+TREE, it will be replaced by DATA by default.
+
+If UPDATEFUN is supplied and an element matching DATA already
+exists in TREE, UPDATEFUN is called with two arguments: DATA, and
+the matching element. Its return value replaces the existing
+element. This value *must* itself match DATA (and hence the
+pre-existing data), or an error will occur.
+
+Returns the new data."
+ (cdr (avl-tree--do-enter (avl-tree--cmpfun tree)
+ (avl-tree--dummyroot tree)
+ 0 data updatefun)))
+
+(defun avl-tree-delete (tree data &optional test nilflag)
+ "Delete the element matching DATA from the avl tree TREE.
+Matching uses the comparison function previously specified in
+`avl-tree-create' when TREE was created.
+
+Returns the deleted element, or nil if no matching element was
+found.
+
+Optional argument NILFLAG specifies a value to return instead of
+nil if nothing was deleted, so that this case can be
+distinguished from the case of a successfully deleted null
+element.
+
+If supplied, TEST specifies a test that a matching element must
+pass before it is deleted. If a matching element is found, it is
+passed as an argument to TEST, and is deleted only if the return
+value is non-nil."
+ (cdr (avl-tree--do-delete (avl-tree--cmpfun tree)
+ (avl-tree--dummyroot tree)
+ 0 data test nilflag)))
-(defun avl-tree-member (tree data)
+
+(defun avl-tree-member (tree data &optional nilflag)
"Return the element in the avl tree TREE which matches DATA.
-Matching uses the compare function previously specified in
+Matching uses the comparison function previously specified in
`avl-tree-create' when TREE was created.
-If there is no such element in the tree, the value is nil."
+If there is no such element in the tree, nil is
+returned. Optional argument NILFLAG specifies a value to return
+instead of nil in this case. This allows non-existent elements to
+be distinguished from a null element. (See also
+`avl-tree-member-p', which does this for you.)"
(let ((node (avl-tree--root tree))
(compare-function (avl-tree--cmpfun tree)))
(catch 'found
@@ -409,7 +494,16 @@
((funcall compare-function (avl-tree--node-data node) data)
(setq node (avl-tree--node-right node)))
(t (throw 'found (avl-tree--node-data node)))))
- nil)))
+ nilflag)))
+
+
+(defun avl-tree-member-p (tree data)
+ "Return t if an element matching DATA exists in the avl tree TREE,
+otherwise return nil. Matching uses the comparison function
+previously specified in `avl-tree-create' when TREE was created."
+ (let ((flag '(nil)))
+ (not (eq (avl-tree-member tree data flag) flag))))
+
(defun avl-tree-map (__map-function__ tree &optional reverse)
"Modify all elements in the avl tree TREE by applying FUNCTION.
@@ -426,6 +520,57 @@
(avl-tree--root tree)
(if reverse 1 0)))
+
+(defun avl-tree-mapc (__map-function__ tree &optional reverse)
+ "Apply FUNCTION to all elements in avl tree TREE,
+for side-effect only.
+
+FUNCTION is applied to the elements in ascending order, or
+descending order if REVERSE is non-nil."
+ (avl-tree--mapc
+ (lambda (node)
+ (funcall __map-function__ (avl-tree--node-data node)))
+ (avl-tree--root tree)
+ (if reverse 1 0)))
+
+
+(defun avl-tree-mapf
+ (__map-function__ combinator tree &optional reverse)
+ "Apply FUNCTION to all elements in avl tree TREE,
+and combine the results using COMBINATOR.
+
+The FUNCTION is applied and the results are combined in ascending
+order, or descending order if REVERSE is non-nil."
+ (let (avl-tree-mapf--accumulate)
+ (avl-tree--mapc
+ (lambda (node)
+ (setq avl-tree-mapf--accumulate
+ (funcall combinator
+ (funcall __map-function__
+ (avl-tree--node-data node))
+ avl-tree-mapf--accumulate)))
+ (avl-tree--root tree)
+ (if reverse 0 1))
+ (nreverse avl-tree-mapf--accumulate)))
+
+
+(defun avl-tree-mapcar (__map-function__ tree &optional reverse)
+ "Apply FUNCTION to all elements in avl tree TREE,
+and make a list of the results.
+
+The FUNCTION is applied and the list constructed in ascending
+order, or descending order if REVERSE is non-nil.
+
+Note that if you don't care about the order in which FUNCTION is
+applied, just that the resulting list is in the correct order,
+then
+
+ (avl-tree-mapf function 'cons tree (not reverse))
+
+is more efficient."
+ (nreverse (avl-tree-mapf __map-function__ 'cons tree reverse)))
+
+
(defun avl-tree-first (tree)
"Return the first element in TREE, or nil if TREE is empty."
(let ((node (avl-tree--root tree)))
@@ -468,6 +613,65 @@
"Clear the avl tree TREE."
(setf (avl-tree--root tree) nil))
+
+(defun avl-tree-stack (tree &optional reverse)
+ "Return an object that behaves like a sorted stack
+of all elements of TREE.
+
+If REVERSE is non-nil, the stack is sorted in reverse order.
+\(See also `avl-tree-stack-pop'\).
+
+Note that any modification to TREE *immediately* invalidates all
+avl-tree-stacks created before the modification (in particular,
+calling `avl-tree-stack-pop' will give unpredictable results).
+
+Operations on these objects are significantly more efficient than
+constructing a real stack with `avl-tree-flatten' and using
+standard stack functions. As such, they can be useful in
+implementing efficient algorithms of AVL trees. However, in cases
+where mapping functions `avl-tree-mapc', `avl-tree-mapcar' or
+`avl-tree-mapf' would be sufficient, it is better to use one of
+those instead."
+ (let ((stack (avl-tree--stack-create tree reverse)))
+ (avl-tree--stack-repopulate stack)
+ stack))
+
+
+(defun avl-tree-stack-pop (avl-tree-stack &optional nilflag)
+ "Pop the first element from AVL-TREE-STACK.
+\(See also `avl-tree-stack'\).
+
+Returns nil if the stack is empty, or NILFLAG if specified. (The
+latter allows an empty stack to be distinguished from a null
+element stored in the AVL tree.)"
+ (let (node next)
+ (if (not (setq node (pop (avl-tree--stack-store avl-tree-stack))))
+ nilflag
+ (when (setq next
+ (avl-tree--node-branch
+ node
+ (if (avl-tree--stack-reverse avl-tree-stack) 0 1)))
+ (push next (avl-tree--stack-store avl-tree-stack))
+ (avl-tree--stack-repopulate avl-tree-stack))
+ (avl-tree--node-data node))))
+
+
+(defun avl-tree-stack-first (avl-tree-stack &optional nilflag)
+ "Return the first element of AVL-TREE-STACK, without removing it
+from the stack.
+
+Returns nil if the stack is empty, or NILFLAG if specified. (The
+latter allows an empty stack to be distinguished from a null
+element stored in the AVL tree.)"
+ (or (car (avl-tree--stack-store avl-tree-stack))
+ nilflag))
+
+
+(defun avl-tree-stack-empty-p (avl-tree-stack)
+ "Return t if AVL-TREE-STACK is empty, nil otherwise."
+ (null (avl-tree--stack-store avl-tree-stack)))
+
+
(provide 'avl-tree)
;; arch-tag: 47e26701-43c9-4222-bd79-739eac6357a9
^ permalink raw reply [flat|nested] 7+ messages in thread
* bug#5021: avl-tree.el enhancements
2009-11-23 9:44 ` bug#5016: " Toby Cubitt
@ 2009-11-23 14:58 ` Stefan Monnier
2009-11-23 16:59 ` bug#5024: " Toby Cubitt
2009-11-23 17:16 ` bug#5012: " Glenn Morris
0 siblings, 2 replies; 7+ messages in thread
From: Stefan Monnier @ 2009-11-23 14:58 UTC (permalink / raw)
To: Toby Cubitt; +Cc: bug-gnu-emacs
>> 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.
I know. I wrote the comment ;-)
>> > +(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.
Maybe I'll do it at some point, but at least when changing code, the new
code should use docstrings rather than comments.
It used to be the case that docstrings were costly (in terms of memory
use), but that was fixed around Emacs-19 so docstrings are not kept in
memory any more. There is still a fair bit of code written before that
time which still avoids using docstrings for that reason. While I don't
think it's important to go back and fix all that old code, I think it's
worthwhile to fix it when we touch such code.
> 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.
That's what the "--" is for in avl-tree--del-balance. It's also much
better because you don't need to check "does this function have
a docstring" to figure out whether it's internal or not.
> 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.
Some people follow this kind of convention, but the Emacs project
doesn't. We only drop the docstring when we're lazy or when we don't
know what to put in it.
> If you still insist on making one or other or both of these into
> docstrings, I'll make the necessary changes to the patches.
Please do, thank you.
>> 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.
It's a trick that can be used to *change* the calling
convention displayed. So it's not used/needed often. But here, for
example, it's used to change (avl-tree-compare-function CL-X) into
(avl-tree-compare-function TREE), so the docstring (which refers to
TREE) makes more sense.
Sometimes it's used to hide some internal arguments.
It's also used systematically in autoloaded definitions so as to provide
the calling convention before the function is loaded.
>> 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! :)
No, an entry in the format used by the ChangeLog file.
See http://www.gnu.org/prep/standards/standards.html#Change-Logs
Stefan
^ permalink raw reply [flat|nested] 7+ messages in thread
* bug#5024: avl-tree.el enhancements
2009-11-23 14:58 ` bug#5021: " Stefan Monnier
@ 2009-11-23 16:59 ` Toby Cubitt
2009-11-23 17:16 ` bug#5012: " Glenn Morris
1 sibling, 0 replies; 7+ messages in thread
From: Toby Cubitt @ 2009-11-23 16:59 UTC (permalink / raw)
To: Stefan Monnier; +Cc: bug-gnu-emacs
[-- Attachment #1: Type: text/plain, Size: 3142 bytes --]
On Mon, Nov 23, 2009 at 09:58:08AM -0500, Stefan Monnier wrote:
> >> 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.
>
> I know. I wrote the comment ;-)
:-)
> > 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.
>
> That's what the "--" is for in avl-tree--del-balance. It's also much
> better because you don't need to check "does this function have
> a docstring" to figure out whether it's internal or not.
I see. I wasn't aware that the "--" convention was widely followed for
internal library functions (at least, widely enough to be understood). In
that case, you're of course right.
Is this convention documented anywhere? Should it be? I can't find it
mentioned anywhere in Appendix D of Emacs Lisp Manual...
> > If you still insist on making one or other or both of these into
> > docstrings, I'll make the necessary changes to the patches.
>
> Please do, thank you.
I've fixed this in the new versions of the patches (attached). Since my
changes touch a lot of functions in avl-tree.el, I've gone through and
changed as many comments to docstrings as I can (I think I've caught all
of them, in fact).
> >> 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.
>
> It's a trick that can be used to *change* the calling
> convention displayed. So it's not used/needed often. But here, for
> example, it's used to change (avl-tree-compare-function CL-X) into
> (avl-tree-compare-function TREE), so the docstring (which refers to
> TREE) makes more sense.
> Sometimes it's used to hide some internal arguments.
> It's also used systematically in autoloaded definitions so as to provide
> the calling convention before the function is loaded.
Always good to learn something new about Emacs :) I've reverted this
change in the attached patches. Now I'll have to go back through my other
Elisp code to see if this trick would be useful!
> >> 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! :)
>
> No, an entry in the format used by the ChangeLog file.
> See http://www.gnu.org/prep/standards/standards.html#Change-Logs
Ah, OK. I've attached a ChangeLog file with the entries for these
changes. I've tried to follow the guidelines in the link, but you'd
better check and let me know if they're OK.
Toby
[-- Attachment #2: avl-tree.el_ChangeLog --]
[-- Type: text/plain, Size: 1235 bytes --]
2009-11-23 <toby-predictive@dr-qubit.org>
* avl-tree.el (avl-tree--switch-dir, avl-tree--dir-to-sign)
(avl-tree--sign-to-dir): New functions
* avl-tree.el (avl-tree--del-balance1, avl-tree--del-balance2):
Replaced with avl-tree--del-balance
* avl-tree.el (avl-tree--del-balance): New function
* avl-tree.el (avl-tree--do-del-internal): Use
avl-tree--del-balance
* avl-tree.el (avl-tree--do-delete, avl-tree-delete): New args
TEST and NILFLAG
* avl-tree.el (avl-tree--enter-balance1)
(avl-tree--enter-balance2): Replaced with avl-tree--enter-balance
* avl-tree.el (avl-tree--enter-balance): New function
* avl-tree.el (avl-tree--do-enter, avl-tree-enter): New arg
UPDATEFUN
* avl-tree.el (avl-tree-member): New arg NILFLAG
* avl-tree.el (avl-tree-member-p): New function
* avl-tree.el (avl-tree--mapc): New arg DIR; modified all callers
* avl-tree.el (avl-tree-map): Use DIR arg of avl-tree--mapc
* avl-tree.el (avl-tree-mapc, avl-tree-mapf, avl-tree-mapcar): New
functions
* avl-tree.el (avl-tree--stack): New struct
* avl-tree.el (avl-tree-stack, avl-tree-stack-p)
(avl-tree-stack-pop, avl-tree-stack-first, avl-tree-stack-empty-p)
(avl-tree--stack-create, avl-tree--stack-repopulate): New
functions
[-- Attachment #3: avl-tree.el.1.diff --]
[-- Type: text/plain, Size: 23584 bytes --]
--- avl-tree.el 2009-11-23 15:47:52.000000000 +0000
+++ avl-tree1.el 2009-11-23 15:42:54.000000000 +0000
@@ -3,11 +3,13 @@
;; Copyright (C) 1995, 2007, 2008, 2009 Free Software Foundation, Inc.
;; Author: Per Cederqvist <ceder@lysator.liu.se>
-;; Inge Wallin <inge@lysator.liu.se>
-;; Thomas Bellman <bellman@lysator.liu.se>
+;; Inge Wallin <inge@lysator.liu.se>
+;; Thomas Bellman <bellman@lysator.liu.se>
+;; modified by Toby Cubitt <toby-predictive@dr-qubit.org>
+;; Version: 0.1
;; Maintainer: FSF
;; Created: 10 May 1991
-;; Keywords: extensions, data structures
+;; Keywords: extensions, data structures, AVL, tree
;; This file is part of GNU Emacs.
@@ -24,174 +26,190 @@
;; You should have received a copy of the GNU General Public License
;; along with GNU Emacs. If not, see <http://www.gnu.org/licenses/>.
-;;; Commentary:
-;; An AVL tree is a nearly-perfect balanced binary tree. A tree consists of
-;; two elements, the root node and the compare function. The actual tree
-;; has a dummy node as its root with the real root in the left pointer.
+;;; Commentary:
+;;
+;; An AVL tree is a self-balancing binary tree. As such, inserting,
+;; deleting, and retrieving data from an AVL tree containing n elements
+;; is O(log n). It is somewhat more rigidly balanced than other
+;; self-balancing binary trees (such as red-black trees and AA trees),
+;; making insertion slighty slower, deletion somewhat slower, and
+;; retrieval somewhat faster (the asymptotic scaling is of course the
+;; same for all types). Thus it may be a good choice when the tree will
+;; be relatively static, i.e. data will be retrieved more often than
+;; they are modified.
+;;
+;; Internally, a tree consists of two elements, the root node and the
+;; comparison function. The actual tree has a dummy node as its root
+;; with the real root in the left pointer, which allows the root node to
+;; be treated on a par with all other nodes.
;;
;; Each node of the tree consists of one data element, one left
-;; sub-tree and one right sub-tree. Each node also has a balance
-;; count, which is the difference in depth of the left and right
-;; sub-trees.
+;; sub-tree, one right sub-tree, and a balance count. The latter is the
+;; difference in depth of the left and right sub-trees.
;;
;; The functions with names of the form "avl-tree--" are intended for
;; internal use only.
+
+;;; Change log:
+;;
+;; Version 0.1
+;; * simplified rebalancing code
+;; * added optional direction argument to `avl-tree-map'
+
+
;;; Code:
(eval-when-compile (require 'cl))
-;; ================================================================
-;;; Functions and macros handling an AVL tree node.
-(defstruct (avl-tree--node
- ;; We force a representation without tag so it matches the
- ;; pre-defstruct representation. Also we use the underlying
- ;; representation in the implementation of avl-tree--node-branch.
- (:type vector)
- (:constructor nil)
- (:constructor avl-tree--node-create (left right data balance))
- (:copier nil))
- left right data balance)
-(defalias 'avl-tree--node-branch 'aref
- ;; This implementation is efficient but breaks the defstruct abstraction.
- ;; An alternative could be
- ;; (funcall (aref [avl-tree-left avl-tree-right avl-tree-data] branch) node)
- "Get value of a branch of a node.
+;; ================================================================
+;;; Internal functions and macros for use in the AVL tree package
-NODE is the node, and BRANCH is the branch.
-0 for left pointer, 1 for right pointer and 2 for the data.\"
-\(fn node branch)")
-;; The funcall/aref trick doesn't work for the setf method, unless we try
-;; and access the underlying setter function, but this wouldn't be
-;; portable either.
-(defsetf avl-tree--node-branch aset)
-\f
-;; ================================================================
-;;; Internal functions for use in the AVL tree package
+;; ----------------------------------------------------------------
+;; Functions and macros handling an AVL tree.
(defstruct (avl-tree-
;; A tagged list is the pre-defstruct representation.
;; (:type list)
:named
(:constructor nil)
- (:constructor avl-tree-create (cmpfun))
+ (:constructor avl-tree--create (cmpfun))
(:predicate avl-tree-p)
(:copier nil))
(dummyroot (avl-tree--node-create nil nil nil 0))
cmpfun)
+
(defmacro avl-tree--root (tree)
;; Return the root node for an avl-tree. INTERNAL USE ONLY.
- `(avl-tree--node-left (avl-tree--dummyroot tree)))
+ `(avl-tree--node-left (avl-tree--dummyroot ,tree)))
+
+
(defsetf avl-tree--root (tree) (node)
`(setf (avl-tree--node-left (avl-tree--dummyroot ,tree)) ,node))
+
+
;; ----------------------------------------------------------------
-;; Deleting data
+;; Functions and macros handling an AVL tree node.
-(defun avl-tree--del-balance1 (node branch)
- ;; Rebalance a tree and return t if the height of the tree has shrunk.
- (let ((br (avl-tree--node-branch node branch))
- p1 b1 p2 b2 result)
- (cond
- ((< (avl-tree--node-balance br) 0)
- (setf (avl-tree--node-balance br) 0)
- t)
+(defstruct (avl-tree--node
+ ;; We force a representation without tag so it matches the
+ ;; pre-defstruct representation. Also we use the underlying
+ ;; representation in the implementation of
+ ;; avl-tree--node-branch.
+ (:type vector)
+ (:constructor nil)
+ (:constructor avl-tree--node-create (left right data balance))
+ (:copier nil))
+ left right data balance)
- ((= (avl-tree--node-balance br) 0)
- (setf (avl-tree--node-balance br) +1)
- nil)
- (t
- ;; Rebalance.
- (setq p1 (avl-tree--node-right br)
- b1 (avl-tree--node-balance p1))
- (if (>= b1 0)
- ;; Single RR rotation.
- (progn
- (setf (avl-tree--node-right br) (avl-tree--node-left p1))
- (setf (avl-tree--node-left p1) br)
- (if (= 0 b1)
- (progn
- (setf (avl-tree--node-balance br) +1)
- (setf (avl-tree--node-balance p1) -1)
- (setq result nil))
- (setf (avl-tree--node-balance br) 0)
- (setf (avl-tree--node-balance p1) 0)
- (setq result t))
- (setf (avl-tree--node-branch node branch) p1)
- result)
-
- ;; Double RL rotation.
- (setq p2 (avl-tree--node-left p1)
- b2 (avl-tree--node-balance p2))
- (setf (avl-tree--node-left p1) (avl-tree--node-right p2))
- (setf (avl-tree--node-right p2) p1)
- (setf (avl-tree--node-right br) (avl-tree--node-left p2))
- (setf (avl-tree--node-left p2) br)
- (setf (avl-tree--node-balance br) (if (> b2 0) -1 0))
- (setf (avl-tree--node-balance p1) (if (< b2 0) +1 0))
- (setf (avl-tree--node-branch node branch) p2)
- (setf (avl-tree--node-balance p2) 0)
- t)))))
+(defalias 'avl-tree--node-branch 'aref
+ ;; This implementation is efficient but breaks the defstruct
+ ;; abstraction. An alternative could be (funcall (aref [avl-tree-left
+ ;; avl-tree-right avl-tree-data] branch) node)
+ "Get value of a branch of a node.
+NODE is the node, and BRANCH is the branch.
+0 for left pointer, 1 for right pointer and 2 for the data.")
+
+
+;; The funcall/aref trick wouldn't work for the setf method, unless we
+;; tried to access the underlying setter function, but this wouldn't be
+;; portable either.
+(defsetf avl-tree--node-branch aset)
+
-(defun avl-tree--del-balance2 (node branch)
+
+;; ----------------------------------------------------------------
+;; Convenience macros
+
+(defmacro avl-tree--switch-dir (dir)
+ "Return opposite direction to DIR (0 = left, 1 = right)."
+ `(- 1 ,dir))
+
+(defmacro avl-tree--dir-to-sign (dir)
+ "Convert direction (0,1) to sign factor (-1,+1)."
+ `(1- (* 2 ,dir)))
+
+(defmacro avl-tree--sign-to-dir (dir)
+ "Convert sign factor (-x,+x) to direction (0,1)."
+ `(if (< ,dir 0) 0 1))
+
+
+;; ----------------------------------------------------------------
+;; Deleting data
+
+(defun avl-tree--del-balance (node branch dir)
+ "Rebalance a tree after deleting
+from the left (DIR=0) or right (DIR=1) sub-tree of the
+left (BRANCH=0) or right (BRANCH=1) child of NODE.
+Return t if the height of the tree has shrunk."
+;;; (or is it vice-versa for BRANCH?)
(let ((br (avl-tree--node-branch node branch))
- p1 b1 p2 b2 result)
+ ;; opposite direction: 0,1 -> 1,0
+ (opp (avl-tree--switch-dir dir))
+ ;; direction 0,1 -> sign factor -1,+1
+ (sgn (avl-tree--dir-to-sign dir))
+ p1 b1 p2 b2)
(cond
- ((> (avl-tree--node-balance br) 0)
+ ((> (* sgn (avl-tree--node-balance br)) 0)
(setf (avl-tree--node-balance br) 0)
t)
((= (avl-tree--node-balance br) 0)
- (setf (avl-tree--node-balance br) -1)
+ (setf (avl-tree--node-balance br) (- sgn))
nil)
(t
;; Rebalance.
- (setq p1 (avl-tree--node-left br)
+ (setq p1 (avl-tree--node-branch br opp)
b1 (avl-tree--node-balance p1))
- (if (<= b1 0)
- ;; Single LL rotation.
+ (if (<= (* sgn b1) 0)
+ ;; Single rotation.
(progn
- (setf (avl-tree--node-left br) (avl-tree--node-right p1))
- (setf (avl-tree--node-right p1) br)
+ (setf (avl-tree--node-branch br opp)
+ (avl-tree--node-branch p1 dir)
+ (avl-tree--node-branch p1 dir) br
+ (avl-tree--node-branch node branch) p1)
(if (= 0 b1)
(progn
- (setf (avl-tree--node-balance br) -1)
- (setf (avl-tree--node-balance p1) +1)
- (setq result nil))
+ (setf (avl-tree--node-balance br) (- sgn)
+ (avl-tree--node-balance p1) sgn)
+ nil) ; height hasn't changed
(setf (avl-tree--node-balance br) 0)
(setf (avl-tree--node-balance p1) 0)
- (setq result t))
- (setf (avl-tree--node-branch node branch) p1)
- result)
-
- ;; Double LR rotation.
- (setq p2 (avl-tree--node-right p1)
- b2 (avl-tree--node-balance p2))
- (setf (avl-tree--node-right p1) (avl-tree--node-left p2))
- (setf (avl-tree--node-left p2) p1)
- (setf (avl-tree--node-left br) (avl-tree--node-right p2))
- (setf (avl-tree--node-right p2) br)
- (setf (avl-tree--node-balance br) (if (< b2 0) +1 0))
- (setf (avl-tree--node-balance p1) (if (> b2 0) -1 0))
- (setf (avl-tree--node-branch node branch) p2)
- (setf (avl-tree--node-balance p2) 0)
+ t)) ; height has changed
+
+ ;; Double rotation.
+ (setf p2 (avl-tree--node-branch p1 dir)
+ b2 (avl-tree--node-balance p2)
+ (avl-tree--node-branch p1 dir)
+ (avl-tree--node-branch p2 opp)
+ (avl-tree--node-branch p2 opp) p1
+ (avl-tree--node-branch br opp)
+ (avl-tree--node-branch p2 dir)
+ (avl-tree--node-branch p2 dir) br
+ (avl-tree--node-balance br)
+ (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 p2) 0)
t)))))
(defun avl-tree--do-del-internal (node branch q)
(let ((br (avl-tree--node-branch node branch)))
(if (avl-tree--node-right br)
- (if (avl-tree--do-del-internal br +1 q)
- (avl-tree--del-balance2 node branch))
- (setf (avl-tree--node-data q) (avl-tree--node-data br))
- (setf (avl-tree--node-branch node branch)
- (avl-tree--node-left br))
+ (if (avl-tree--do-del-internal br 1 q)
+ (avl-tree--del-balance node branch 1))
+ (setf (avl-tree--node-data q) (avl-tree--node-data br)
+ (avl-tree--node-branch node branch)
+ (avl-tree--node-left br))
t)))
(defun avl-tree--do-delete (cmpfun root branch data)
@@ -203,102 +221,79 @@
((funcall cmpfun data (avl-tree--node-data br))
(if (avl-tree--do-delete cmpfun br 0 data)
- (avl-tree--del-balance1 root branch)))
+ (avl-tree--del-balance root branch 0)))
((funcall cmpfun (avl-tree--node-data br) data)
(if (avl-tree--do-delete cmpfun br 1 data)
- (avl-tree--del-balance2 root branch)))
+ (avl-tree--del-balance root branch 1)))
(t
;; Found it. Let's delete it.
(cond
((null (avl-tree--node-right br))
- (setf (avl-tree--node-branch root branch) (avl-tree--node-left br))
- t)
+ (setf (avl-tree--node-branch root branch) (avl-tree--node-left br))
+ t)
((null (avl-tree--node-left br))
- (setf (avl-tree--node-branch root branch) (avl-tree--node-right br))
- t)
+ (setf (avl-tree--node-branch root branch)
+ (avl-tree--node-right br))
+ t)
(t
- (if (avl-tree--do-del-internal br 0 br)
- (avl-tree--del-balance1 root branch))))))))
+ (if (avl-tree--do-del-internal br 0 br)
+ (avl-tree--del-balance root branch 0))))))))
;; ----------------------------------------------------------------
;; Entering data
-(defun avl-tree--enter-balance1 (node branch)
- ;; Rebalance a tree and return t if the height of the tree has grown.
+(defun avl-tree--enter-balance (node branch dir)
+ "Rebalance tree after an insertion
+into the left (DIR=0) or right (DIR=1) sub-tree of the
+left (BRANCH=0) or right (BRANCH=1) child of NODE.
+Return t if the height of the tree has grown."
(let ((br (avl-tree--node-branch node branch))
+ ;; opposite direction: 0,1 -> 1,0
+ (opp (avl-tree--switch-dir dir))
+ ;; direction 0,1 -> sign factor -1,+1
+ (sgn (avl-tree--dir-to-sign dir))
p1 p2 b2 result)
(cond
- ((< (avl-tree--node-balance br) 0)
+ ((< (* sgn (avl-tree--node-balance br)) 0)
(setf (avl-tree--node-balance br) 0)
nil)
((= (avl-tree--node-balance br) 0)
- (setf (avl-tree--node-balance br) +1)
+ (setf (avl-tree--node-balance br) sgn)
t)
(t
;; Tree has grown => Rebalance.
- (setq p1 (avl-tree--node-right br))
- (if (> (avl-tree--node-balance p1) 0)
- ;; Single RR rotation.
+ (setq p1 (avl-tree--node-branch br dir))
+ (if (> (* sgn (avl-tree--node-balance p1)) 0)
+ ;; Single rotation.
(progn
- (setf (avl-tree--node-right br) (avl-tree--node-left p1))
- (setf (avl-tree--node-left p1) br)
+ (setf (avl-tree--node-branch br dir)
+ (avl-tree--node-branch p1 opp))
+ (setf (avl-tree--node-branch p1 opp) br)
(setf (avl-tree--node-balance br) 0)
(setf (avl-tree--node-branch node branch) p1))
- ;; Double RL rotation.
- (setq p2 (avl-tree--node-left p1)
- b2 (avl-tree--node-balance p2))
- (setf (avl-tree--node-left p1) (avl-tree--node-right p2))
- (setf (avl-tree--node-right p2) p1)
- (setf (avl-tree--node-right br) (avl-tree--node-left p2))
- (setf (avl-tree--node-left p2) br)
- (setf (avl-tree--node-balance br) (if (> b2 0) -1 0))
- (setf (avl-tree--node-balance p1) (if (< b2 0) +1 0))
- (setf (avl-tree--node-branch node branch) p2))
- (setf (avl-tree--node-balance (avl-tree--node-branch node branch)) 0)
- nil))))
-
-(defun avl-tree--enter-balance2 (node branch)
- ;; Return t if the tree has grown.
- (let ((br (avl-tree--node-branch node branch))
- p1 p2 b2)
- (cond
- ((> (avl-tree--node-balance br) 0)
- (setf (avl-tree--node-balance br) 0)
- nil)
-
- ((= (avl-tree--node-balance br) 0)
- (setf (avl-tree--node-balance br) -1)
- t)
-
- (t
- ;; Balance was -1 => Rebalance.
- (setq p1 (avl-tree--node-left br))
- (if (< (avl-tree--node-balance p1) 0)
- ;; Single LL rotation.
- (progn
- (setf (avl-tree--node-left br) (avl-tree--node-right p1))
- (setf (avl-tree--node-right p1) br)
- (setf (avl-tree--node-balance br) 0)
- (setf (avl-tree--node-branch node branch) p1))
-
- ;; Double LR rotation.
- (setq p2 (avl-tree--node-right p1)
- b2 (avl-tree--node-balance p2))
- (setf (avl-tree--node-right p1) (avl-tree--node-left p2))
- (setf (avl-tree--node-left p2) p1)
- (setf (avl-tree--node-left br) (avl-tree--node-right p2))
- (setf (avl-tree--node-right p2) br)
- (setf (avl-tree--node-balance br) (if (< b2 0) +1 0))
- (setf (avl-tree--node-balance p1) (if (> b2 0) -1 0))
- (setf (avl-tree--node-branch node branch) p2))
- (setf (avl-tree--node-balance (avl-tree--node-branch node branch)) 0)
+ ;; Double rotation.
+ (setf p2 (avl-tree--node-branch p1 opp)
+ b2 (avl-tree--node-balance p2)
+ (avl-tree--node-branch p1 opp)
+ (avl-tree--node-branch p2 dir)
+ (avl-tree--node-branch p2 dir) p1
+ (avl-tree--node-branch br dir)
+ (avl-tree--node-branch p2 opp)
+ (avl-tree--node-branch p2 opp) br
+ (avl-tree--node-balance br)
+ (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))
nil))))
(defun avl-tree--do-enter (cmpfun root branch data)
@@ -313,11 +308,11 @@
((funcall cmpfun data (avl-tree--node-data br))
(and (avl-tree--do-enter cmpfun br 0 data)
- (avl-tree--enter-balance2 root branch)))
+ (avl-tree--enter-balance root branch 0)))
((funcall cmpfun (avl-tree--node-data br) data)
(and (avl-tree--do-enter cmpfun br 1 data)
- (avl-tree--enter-balance1 root branch)))
+ (avl-tree--enter-balance root branch 1)))
(t
(setf (avl-tree--node-data br) data)
@@ -325,33 +320,38 @@
;; ----------------------------------------------------------------
-(defun avl-tree--mapc (map-function root)
- ;; Apply MAP-FUNCTION to all nodes in the tree starting with ROOT.
- ;; The function is applied in-order.
- ;;
- ;; Note: MAP-FUNCTION is applied to the node and not to the data itself.
- ;; INTERNAL USE ONLY.
+
+;;; INTERNAL USE ONLY
+(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, either ascending (DIR=0) or
+descending (DIR=1).
+
+Note: MAP-FUNCTION is applied to the node and not to the data
+itself."
(let ((node root)
(stack nil)
- (go-left t))
+ (go-dir t))
(push nil stack)
(while node
- (if (and go-left
- (avl-tree--node-left node))
- ;; Do the left subtree first.
+ (if (and go-dir
+ (avl-tree--node-branch node dir))
+ ;; Do the DIR subtree first.
(progn
(push node stack)
- (setq node (avl-tree--node-left node)))
+ (setq node (avl-tree--node-branch node dir)))
;; Apply the function...
(funcall map-function node)
- ;; and do the right subtree.
- (setq node (if (setq go-left (avl-tree--node-right node))
- (avl-tree--node-right node)
+ ;; and do the opposite subtree.
+ (setq node (if (setq go-dir (avl-tree--node-branch
+ node (avl-tree--switch-dir dir)))
+ (avl-tree--node-branch
+ node (avl-tree--switch-dir dir))
(pop stack)))))))
+;;; INTERNAL USE ONLY
(defun avl-tree--do-copy (root)
- ;; Copy the avl tree with ROOT as root.
- ;; Highly recursive. INTERNAL USE ONLY.
+ "Copy the avl tree with ROOT as root. Highly recursive."
(if (null root)
nil
(avl-tree--node-create
@@ -360,10 +360,17 @@
(avl-tree--node-data root)
(avl-tree--node-balance root))))
-\f
+
;; ================================================================
;;; The public functions which operate on AVL trees.
+;; 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.")
+
+
(defalias 'avl-tree-compare-function 'avl-tree--cmpfun
"Return the comparison function for the avl tree TREE.
@@ -377,9 +384,9 @@
"In the avl tree TREE insert DATA.
Return DATA."
(avl-tree--do-enter (avl-tree--cmpfun tree)
- (avl-tree--dummyroot tree)
- 0
- data)
+ (avl-tree--dummyroot tree)
+ 0
+ data)
data)
(defun avl-tree-delete (tree data)
@@ -398,28 +405,31 @@
If there is no such element in the tree, the value is nil."
(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)
+ (compare-function (avl-tree--cmpfun tree)))
+ (catch 'found
+ (while node
+ (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 (throw 'found (avl-tree--node-data node)))))
nil)))
-(defun avl-tree-map (__map-function__ tree)
- "Apply __MAP-FUNCTION__ to all elements in the avl tree TREE."
+(defun avl-tree-map (__map-function__ tree &optional reverse)
+ "Modify all elements in the avl tree TREE by applying FUNCTION.
+
+Each element is replaced by the return value of FUNCTION applied
+to that element.
+
+FUNCTION is applied to the elements in ascending order, or
+descending order if REVERSE is non-nil."
(avl-tree--mapc
(lambda (node)
(setf (avl-tree--node-data node)
(funcall __map-function__ (avl-tree--node-data node))))
- (avl-tree--root tree)))
+ (avl-tree--root tree)
+ (if reverse 1 0)))
(defun avl-tree-first (tree)
"Return the first element in TREE, or nil if TREE is empty."
@@ -445,19 +455,18 @@
(defun avl-tree-flatten (tree)
"Return a sorted list containing all elements of TREE."
- (nreverse
(let ((treelist nil))
(avl-tree--mapc
(lambda (node) (push (avl-tree--node-data node) treelist))
- (avl-tree--root tree))
- treelist)))
+ (avl-tree--root tree) 1)
+ treelist))
(defun avl-tree-size (tree)
"Return the number of elements in TREE."
(let ((treesize 0))
(avl-tree--mapc
(lambda (data) (setq treesize (1+ treesize)))
- (avl-tree--root tree))
+ (avl-tree--root tree) 0)
treesize))
(defun avl-tree-clear (tree)
[-- Attachment #4: avl-tree.el.2.diff --]
[-- Type: text/plain, Size: 14117 bytes --]
--- avl-tree1.el 2009-11-23 15:42:54.000000000 +0000
+++ avl-tree2.el 2009-11-23 15:54:52.000000000 +0000
@@ -6,7 +6,7 @@
;; Inge Wallin <inge@lysator.liu.se>
;; Thomas Bellman <bellman@lysator.liu.se>
;; modified by Toby Cubitt <toby-predictive@dr-qubit.org>
-;; Version: 0.1
+;; Version: 0.2
;; Maintainer: FSF
;; Created: 10 May 1991
;; Keywords: extensions, data structures, AVL, tree
@@ -54,6 +54,13 @@
;;; Change log:
;;
+;; Version 0.2
+;; * added new optional arguments to `avl-tree-member', `avl-tree-enter'
+;; and `avl-tree-delete'
+;; * added `avl-tree-member-p', `avl-tree-mapc', `avl-tree-mapcar',
+;; `avl-tree-mapf', `avl-tree-stack', `avl-tree-stack-pop' and
+;; `avl-tree-stack-first' functions
+;;
;; Version 0.1
;; * simplified rebalancing code
;; * added optional direction argument to `avl-tree-map'
@@ -212,36 +219,52 @@
(avl-tree--node-left br))
t)))
-(defun avl-tree--do-delete (cmpfun root branch data)
- ;; Return t if the height of the tree has shrunk.
+(defun avl-tree--do-delete (cmpfun root branch data test nilflag)
+ "Delete DATA from BRANCH of node ROOT.
+\(See `avl-tree-delete' for TEST and NILFLAG).
+
+Return cons cell (<shrunk> . <data>), where <shrunk> is t if the
+height of the tree has shrunk and nil otherwise, and <data> is
+the releted data."
(let ((br (avl-tree--node-branch root branch)))
(cond
+ ;; DATA not in tree.
((null br)
- nil)
+ (cons nil nilflag))
((funcall cmpfun data (avl-tree--node-data br))
- (if (avl-tree--do-delete cmpfun br 0 data)
- (avl-tree--del-balance root branch 0)))
+ (let ((ret (avl-tree--do-delete cmpfun br 0 data test nilflag)))
+ (cons (if (car ret) (avl-tree--del-balance root branch 0))
+ (cdr ret))))
((funcall cmpfun (avl-tree--node-data br) data)
- (if (avl-tree--do-delete cmpfun br 1 data)
- (avl-tree--del-balance root branch 1)))
+ (let ((ret (avl-tree--do-delete cmpfun br 1 data test nilflag)))
+ (cons (if (car ret) (avl-tree--del-balance root branch 1))
+ (cdr ret))))
+
+ (t ; Found it.
+ ;; if it fails TEST, do nothing
+ (if (and test (not (funcall test (avl-tree--node-data br))))
+ (cons nil nilflag)
+ (cond
+ ((null (avl-tree--node-right br))
+ (setf (avl-tree--node-branch root branch)
+ (avl-tree--node-left br))
+ (cons t (avl-tree--node-data br)))
+
+ ((null (avl-tree--node-left br))
+ (setf (avl-tree--node-branch root branch)
+ (avl-tree--node-right br))
+ (cons t (avl-tree--node-data br)))
+
+ (t
+ (if (avl-tree--do-del-internal br 0 br)
+ (cons (avl-tree--del-balance root branch 0)
+ (avl-tree--node-data br))
+ (cons nil (avl-tree--node-data br))))
+ ))))))
+
- (t
- ;; Found it. Let's delete it.
- (cond
- ((null (avl-tree--node-right br))
- (setf (avl-tree--node-branch root branch) (avl-tree--node-left br))
- t)
-
- ((null (avl-tree--node-left br))
- (setf (avl-tree--node-branch root branch)
- (avl-tree--node-right br))
- t)
-
- (t
- (if (avl-tree--do-del-internal br 0 br)
- (avl-tree--del-balance root branch 0))))))))
;; ----------------------------------------------------------------
;; Entering data
@@ -296,30 +319,47 @@
(avl-tree--node-branch node branch)) 0))
nil))))
-(defun avl-tree--do-enter (cmpfun root branch data)
- ;; Return t if height of tree ROOT has grown. INTERNAL USE ONLY.
+(defun avl-tree--do-enter (cmpfun root branch data &optional updatefun)
+ "Enter DATA in BRANCH of ROOT node.
+\(See `avl-tree-enter' for UPDATEFUN).
+
+Return cons cell (<grew> . <data>), where <grew> is t if height
+of tree ROOT has grown and nil otherwise, and <data> is the
+inserted data."
(let ((br (avl-tree--node-branch root branch)))
(cond
((null br)
;; Data not in tree, insert it.
(setf (avl-tree--node-branch root branch)
(avl-tree--node-create nil nil data 0))
- t)
+ (cons t data))
((funcall cmpfun data (avl-tree--node-data br))
- (and (avl-tree--do-enter cmpfun br 0 data)
- (avl-tree--enter-balance root branch 0)))
+ (let ((ret (avl-tree--do-enter cmpfun br 0 data updatefun)))
+ (cons (and (car ret) (avl-tree--enter-balance root branch 0))
+ (cdr ret))))
((funcall cmpfun (avl-tree--node-data br) data)
- (and (avl-tree--do-enter cmpfun br 1 data)
- (avl-tree--enter-balance root branch 1)))
+ (let ((ret (avl-tree--do-enter cmpfun br 1 data updatefun)))
+ (cons (and (car ret) (avl-tree--enter-balance root branch 1))
+ (cdr ret))))
+ ;; Data already in tree, update it.
(t
- (setf (avl-tree--node-data br) data)
- nil))))
+ (let ((newdata
+ (if updatefun
+ (funcall updatefun data (avl-tree--node-data br))
+ data)))
+ (if (or (funcall cmpfun newdata data)
+ (funcall cmpfun data newdata))
+ (error "avl-tree-enter:\
+ updated data does not match existing data"))
+ (setf (avl-tree--node-data br) newdata)
+ (cons nil newdata)) ; return value
+ ))))
-;; ----------------------------------------------------------------
+;; ----------------------------------------------------------------
;;; INTERNAL USE ONLY
(defun avl-tree--mapc (map-function root dir)
@@ -360,6 +400,30 @@
(avl-tree--node-data root)
(avl-tree--node-balance root))))
+(defstruct (avl-tree--stack
+ (:constructor nil)
+ (:constructor avl-tree--stack-create
+ (tree &optional reverse
+ &aux
+ (store
+ (if (avl-tree-empty tree)
+ nil
+ (list (avl-tree--root tree))))))
+ (:copier nil))
+ reverse store)
+
+(defalias 'avl-tree-stack-p 'avl-tree--stack-p
+ "Return t if argument is an avl-tree-stack, nil otherwise.")
+
+(defun avl-tree--stack-repopulate (stack)
+ ;; Recursively push children of the node at the head of STACK onto the
+ ;; front of the STACK, until a leaf is reached.
+ (let ((node (car (avl-tree--stack-store stack)))
+ (dir (if (avl-tree--stack-reverse stack) 1 0)))
+ (when node ; check for emtpy stack
+ (while (setq node (avl-tree--node-branch node dir))
+ (push node (avl-tree--stack-store stack))))))
+
;; ================================================================
;;; The public functions which operate on AVL trees.
@@ -380,30 +444,56 @@
"Return t if avl tree TREE is emtpy, otherwise return nil."
(null (avl-tree--root tree)))
-(defun avl-tree-enter (tree data)
- "In the avl tree TREE insert DATA.
-Return DATA."
- (avl-tree--do-enter (avl-tree--cmpfun tree)
- (avl-tree--dummyroot tree)
- 0
- data)
- data)
-
-(defun avl-tree-delete (tree data)
- "From the avl tree TREE, delete DATA.
-Return the element in TREE which matched DATA,
-nil if no element matched."
- (avl-tree--do-delete (avl-tree--cmpfun tree)
- (avl-tree--dummyroot tree)
- 0
- data))
+(defun avl-tree-enter (tree data &optional updatefun)
+ "Insert DATA into the avl tree TREE.
-(defun avl-tree-member (tree data)
+If an element that matches DATA (according to the tree's
+comparison function, see `avl-tree-create') already exists in
+TREE, it will be replaced by DATA by default.
+
+If UPDATEFUN is supplied and an element matching DATA already
+exists in TREE, UPDATEFUN is called with two arguments: DATA, and
+the matching element. Its return value replaces the existing
+element. This value *must* itself match DATA (and hence the
+pre-existing data), or an error will occur.
+
+Returns the new data."
+ (cdr (avl-tree--do-enter (avl-tree--cmpfun tree)
+ (avl-tree--dummyroot tree)
+ 0 data updatefun)))
+
+(defun avl-tree-delete (tree data &optional test nilflag)
+ "Delete the element matching DATA from the avl tree TREE.
+Matching uses the comparison function previously specified in
+`avl-tree-create' when TREE was created.
+
+Returns the deleted element, or nil if no matching element was
+found.
+
+Optional argument NILFLAG specifies a value to return instead of
+nil if nothing was deleted, so that this case can be
+distinguished from the case of a successfully deleted null
+element.
+
+If supplied, TEST specifies a test that a matching element must
+pass before it is deleted. If a matching element is found, it is
+passed as an argument to TEST, and is deleted only if the return
+value is non-nil."
+ (cdr (avl-tree--do-delete (avl-tree--cmpfun tree)
+ (avl-tree--dummyroot tree)
+ 0 data test nilflag)))
+
+
+(defun avl-tree-member (tree data &optional nilflag)
"Return the element in the avl tree TREE which matches DATA.
-Matching uses the compare function previously specified in
+Matching uses the comparison function previously specified in
`avl-tree-create' when TREE was created.
-If there is no such element in the tree, the value is nil."
+If there is no such element in the tree, nil is
+returned. Optional argument NILFLAG specifies a value to return
+instead of nil in this case. This allows non-existent elements to
+be distinguished from a null element. (See also
+`avl-tree-member-p', which does this for you.)"
(let ((node (avl-tree--root tree))
(compare-function (avl-tree--cmpfun tree)))
(catch 'found
@@ -414,7 +504,16 @@
((funcall compare-function (avl-tree--node-data node) data)
(setq node (avl-tree--node-right node)))
(t (throw 'found (avl-tree--node-data node)))))
- nil)))
+ nilflag)))
+
+
+(defun avl-tree-member-p (tree data)
+ "Return t if an element matching DATA exists in the avl tree TREE,
+otherwise return nil. Matching uses the comparison function
+previously specified in `avl-tree-create' when TREE was created."
+ (let ((flag '(nil)))
+ (not (eq (avl-tree-member tree data flag) flag))))
+
(defun avl-tree-map (__map-function__ tree &optional reverse)
"Modify all elements in the avl tree TREE by applying FUNCTION.
@@ -431,6 +530,57 @@
(avl-tree--root tree)
(if reverse 1 0)))
+
+(defun avl-tree-mapc (__map-function__ tree &optional reverse)
+ "Apply FUNCTION to all elements in avl tree TREE,
+for side-effect only.
+
+FUNCTION is applied to the elements in ascending order, or
+descending order if REVERSE is non-nil."
+ (avl-tree--mapc
+ (lambda (node)
+ (funcall __map-function__ (avl-tree--node-data node)))
+ (avl-tree--root tree)
+ (if reverse 1 0)))
+
+
+(defun avl-tree-mapf
+ (__map-function__ combinator tree &optional reverse)
+ "Apply FUNCTION to all elements in avl tree TREE,
+and combine the results using COMBINATOR.
+
+The FUNCTION is applied and the results are combined in ascending
+order, or descending order if REVERSE is non-nil."
+ (let (avl-tree-mapf--accumulate)
+ (avl-tree--mapc
+ (lambda (node)
+ (setq avl-tree-mapf--accumulate
+ (funcall combinator
+ (funcall __map-function__
+ (avl-tree--node-data node))
+ avl-tree-mapf--accumulate)))
+ (avl-tree--root tree)
+ (if reverse 0 1))
+ (nreverse avl-tree-mapf--accumulate)))
+
+
+(defun avl-tree-mapcar (__map-function__ tree &optional reverse)
+ "Apply FUNCTION to all elements in avl tree TREE,
+and make a list of the results.
+
+The FUNCTION is applied and the list constructed in ascending
+order, or descending order if REVERSE is non-nil.
+
+Note that if you don't care about the order in which FUNCTION is
+applied, just that the resulting list is in the correct order,
+then
+
+ (avl-tree-mapf function 'cons tree (not reverse))
+
+is more efficient."
+ (nreverse (avl-tree-mapf __map-function__ 'cons tree reverse)))
+
+
(defun avl-tree-first (tree)
"Return the first element in TREE, or nil if TREE is empty."
(let ((node (avl-tree--root tree)))
@@ -473,6 +623,65 @@
"Clear the avl tree TREE."
(setf (avl-tree--root tree) nil))
+
+(defun avl-tree-stack (tree &optional reverse)
+ "Return an object that behaves like a sorted stack
+of all elements of TREE.
+
+If REVERSE is non-nil, the stack is sorted in reverse order.
+\(See also `avl-tree-stack-pop'\).
+
+Note that any modification to TREE *immediately* invalidates all
+avl-tree-stacks created before the modification (in particular,
+calling `avl-tree-stack-pop' will give unpredictable results).
+
+Operations on these objects are significantly more efficient than
+constructing a real stack with `avl-tree-flatten' and using
+standard stack functions. As such, they can be useful in
+implementing efficient algorithms of AVL trees. However, in cases
+where mapping functions `avl-tree-mapc', `avl-tree-mapcar' or
+`avl-tree-mapf' would be sufficient, it is better to use one of
+those instead."
+ (let ((stack (avl-tree--stack-create tree reverse)))
+ (avl-tree--stack-repopulate stack)
+ stack))
+
+
+(defun avl-tree-stack-pop (avl-tree-stack &optional nilflag)
+ "Pop the first element from AVL-TREE-STACK.
+\(See also `avl-tree-stack'\).
+
+Returns nil if the stack is empty, or NILFLAG if specified. (The
+latter allows an empty stack to be distinguished from a null
+element stored in the AVL tree.)"
+ (let (node next)
+ (if (not (setq node (pop (avl-tree--stack-store avl-tree-stack))))
+ nilflag
+ (when (setq next
+ (avl-tree--node-branch
+ node
+ (if (avl-tree--stack-reverse avl-tree-stack) 0 1)))
+ (push next (avl-tree--stack-store avl-tree-stack))
+ (avl-tree--stack-repopulate avl-tree-stack))
+ (avl-tree--node-data node))))
+
+
+(defun avl-tree-stack-first (avl-tree-stack &optional nilflag)
+ "Return the first element of AVL-TREE-STACK, without removing it
+from the stack.
+
+Returns nil if the stack is empty, or NILFLAG if specified. (The
+latter allows an empty stack to be distinguished from a null
+element stored in the AVL tree.)"
+ (or (car (avl-tree--stack-store avl-tree-stack))
+ nilflag))
+
+
+(defun avl-tree-stack-empty-p (avl-tree-stack)
+ "Return t if AVL-TREE-STACK is empty, nil otherwise."
+ (null (avl-tree--stack-store avl-tree-stack)))
+
+
(provide 'avl-tree)
;; arch-tag: 47e26701-43c9-4222-bd79-739eac6357a9
^ permalink raw reply [flat|nested] 7+ messages in thread
* bug#5012: avl-tree.el enhancements
2009-11-23 14:58 ` bug#5021: " Stefan Monnier
2009-11-23 16:59 ` bug#5024: " Toby Cubitt
@ 2009-11-23 17:16 ` Glenn Morris
2012-02-23 19:51 ` Glenn Morris
1 sibling, 1 reply; 7+ messages in thread
From: Glenn Morris @ 2009-11-23 17:16 UTC (permalink / raw)
To: 5012
Please stop cc'ing bug-gnu-emacs.
Instead, use 5012@emacsbugs.donarmstrong.com.
Otherwise every reply creates a new bug number.
To avoid this in future, use X-Debbugs-Cc rather than Cc when
first reporting a new bug.
Thanks.
^ permalink raw reply [flat|nested] 7+ messages in thread
* bug#5012: avl-tree.el enhancements
2009-11-23 17:16 ` bug#5012: " Glenn Morris
@ 2012-02-23 19:51 ` Glenn Morris
0 siblings, 0 replies; 7+ messages in thread
From: Glenn Morris @ 2012-02-23 19:51 UTC (permalink / raw)
To: 5012-done
Version: 24.1
Installed 2011-05-27.
^ permalink raw reply [flat|nested] 7+ messages in thread
end of thread, other threads:[~2012-02-23 19:51 UTC | newest]
Thread overview: 7+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2009-11-23 0:01 bug#5012: avl-tree.el enhancements Toby Cubitt
2009-11-23 3:44 ` bug#5015: " Stefan Monnier
2009-11-23 9:44 ` bug#5016: " Toby Cubitt
2009-11-23 14:58 ` bug#5021: " Stefan Monnier
2009-11-23 16:59 ` bug#5024: " Toby Cubitt
2009-11-23 17:16 ` bug#5012: " Glenn Morris
2012-02-23 19:51 ` Glenn Morris
Code repositories for project(s) associated with this public inbox
https://git.savannah.gnu.org/cgit/emacs.git
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).