Mercurial > emacs
changeset 82900:0ff5cfe89663
Do s/elib-node-/avl-tree-node-/g. Resulting changed macro names:
avl-tree-node-left, avl-tree-node-right, avl-tree-node-data,
avl-tree-node-set-left, avl-tree-node-set-right, avl-tree-node-set-data,
avl-tree-node-branch, avl-tree-node-set-branch.
| author | Thien-Thi Nguyen <ttn@gnuvola.org> |
|---|---|
| date | Mon, 27 Aug 2007 02:31:23 +0000 |
| parents | f0fad697d0aa |
| children | 18391b91e11f |
| files | lisp/emacs-lisp/avl-tree.el |
| diffstat | 1 files changed, 95 insertions(+), 95 deletions(-) [+] |
line wrap: on
line diff
--- a/lisp/emacs-lisp/avl-tree.el Mon Aug 27 02:22:57 2007 +0000 +++ b/lisp/emacs-lisp/avl-tree.el Mon Aug 27 02:31:23 2007 +0000 @@ -54,38 +54,38 @@ ;;; Code: -(defmacro elib-node-left (node) +(defmacro avl-tree-node-left (node) ;; Return the left pointer of NODE. `(aref ,node 0)) -(defmacro elib-node-right (node) +(defmacro avl-tree-node-right (node) ;; Return the right pointer of NODE. `(aref ,node 1)) -(defmacro elib-node-data (node) +(defmacro avl-tree-node-data (node) ;; Return the data of NODE. `(aref ,node 2)) -(defmacro elib-node-set-left (node newleft) +(defmacro avl-tree-node-set-left (node newleft) ;; Set the left pointer of NODE to NEWLEFT. `(aset ,node 0 ,newleft)) -(defmacro elib-node-set-right (node newright) +(defmacro avl-tree-node-set-right (node newright) ;; Set the right pointer of NODE to NEWRIGHT. `(aset ,node 1 ,newright)) -(defmacro elib-node-set-data (node newdata) +(defmacro avl-tree-node-set-data (node newdata) ;; Set the data of NODE to NEWDATA. `(aset ,node 2 ,newdata)) -(defmacro elib-node-branch (node branch) +(defmacro avl-tree-node-branch (node branch) ;; 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." `(aref ,node ,branch)) -(defmacro elib-node-set-branch (node branch newval) +(defmacro avl-tree-node-set-branch (node branch newval) ;; Set value of a branch of a node. ;; ;; NODE is the node, and BRANCH is the branch. @@ -114,7 +114,7 @@ (defmacro avl-tree-root (tree) ;; Return the root node for an avl-tree. INTERNAL USE ONLY. - `(elib-node-left (car (cdr ,tree)))) + `(avl-tree-node-left (car (cdr ,tree)))) (defmacro avl-tree-dummyroot (tree) ;; Return the dummy node of an avl-tree. INTERNAL USE ONLY. @@ -129,7 +129,7 @@ (defun avl-tree-del-balance1 (node branch) ;; Rebalance a tree and return t if the height of the tree has shrunk. - (let* ((br (elib-node-branch node branch)) + (let* ((br (avl-tree-node-branch node branch)) p1 b1 p2 @@ -146,13 +146,13 @@ (t ;; Rebalance. - (setq p1 (elib-node-right br) + (setq p1 (avl-tree-node-right br) b1 (avl-tree-node-balance p1)) (if (>= b1 0) ;; Single RR rotation. (progn - (elib-node-set-right br (elib-node-left p1)) - (elib-node-set-left p1 br) + (avl-tree-node-set-right br (avl-tree-node-left p1)) + (avl-tree-node-set-left p1 br) (if (= 0 b1) (progn (avl-tree-node-set-balance br +1) @@ -161,28 +161,28 @@ (avl-tree-node-set-balance br 0) (avl-tree-node-set-balance p1 0) (setq result t)) - (elib-node-set-branch node branch p1) + (avl-tree-node-set-branch node branch p1) result) ;; Double RL rotation. - (setq p2 (elib-node-left p1) + (setq p2 (avl-tree-node-left p1) b2 (avl-tree-node-balance p2)) - (elib-node-set-left p1 (elib-node-right p2)) - (elib-node-set-right p2 p1) - (elib-node-set-right br (elib-node-left p2)) - (elib-node-set-left p2 br) + (avl-tree-node-set-left p1 (avl-tree-node-right p2)) + (avl-tree-node-set-right p2 p1) + (avl-tree-node-set-right br (avl-tree-node-left p2)) + (avl-tree-node-set-left p2 br) (if (> b2 0) (avl-tree-node-set-balance br -1) (avl-tree-node-set-balance br 0)) (if (< b2 0) (avl-tree-node-set-balance p1 +1) (avl-tree-node-set-balance p1 0)) - (elib-node-set-branch node branch p2) + (avl-tree-node-set-branch node branch p2) (avl-tree-node-set-balance p2 0) t))))) (defun avl-tree-del-balance2 (node branch) - (let* ((br (elib-node-branch node branch)) + (let* ((br (avl-tree-node-branch node branch)) p1 b1 p2 @@ -199,13 +199,13 @@ (t ;; Rebalance. - (setq p1 (elib-node-left br) + (setq p1 (avl-tree-node-left br) b1 (avl-tree-node-balance p1)) (if (<= b1 0) ;; Single LL rotation. (progn - (elib-node-set-left br (elib-node-right p1)) - (elib-node-set-right p1 br) + (avl-tree-node-set-left br (avl-tree-node-right p1)) + (avl-tree-node-set-right p1 br) (if (= 0 b1) (progn (avl-tree-node-set-balance br -1) @@ -214,61 +214,61 @@ (avl-tree-node-set-balance br 0) (avl-tree-node-set-balance p1 0) (setq result t)) - (elib-node-set-branch node branch p1) + (avl-tree-node-set-branch node branch p1) result) ;; Double LR rotation. - (setq p2 (elib-node-right p1) + (setq p2 (avl-tree-node-right p1) b2 (avl-tree-node-balance p2)) - (elib-node-set-right p1 (elib-node-left p2)) - (elib-node-set-left p2 p1) - (elib-node-set-left br (elib-node-right p2)) - (elib-node-set-right p2 br) + (avl-tree-node-set-right p1 (avl-tree-node-left p2)) + (avl-tree-node-set-left p2 p1) + (avl-tree-node-set-left br (avl-tree-node-right p2)) + (avl-tree-node-set-right p2 br) (if (< b2 0) (avl-tree-node-set-balance br +1) (avl-tree-node-set-balance br 0)) (if (> b2 0) (avl-tree-node-set-balance p1 -1) (avl-tree-node-set-balance p1 0)) - (elib-node-set-branch node branch p2) + (avl-tree-node-set-branch node branch p2) (avl-tree-node-set-balance p2 0) t))))) (defun avl-tree-do-del-internal (node branch q) - (let* ((br (elib-node-branch node branch))) - (if (elib-node-right br) + (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)) - (elib-node-set-data q (elib-node-data br)) - (elib-node-set-branch node branch - (elib-node-left br)) + (avl-tree-node-set-data q (avl-tree-node-data br)) + (avl-tree-node-set-branch node branch + (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. - (let* ((br (elib-node-branch root branch))) + (let* ((br (avl-tree-node-branch root branch))) (cond ((null br) nil) - ((funcall cmpfun data (elib-node-data br)) + ((funcall cmpfun data (avl-tree-node-data br)) (if (avl-tree-do-delete cmpfun br 0 data) (avl-tree-del-balance1 root branch))) - ((funcall cmpfun (elib-node-data br) data) + ((funcall cmpfun (avl-tree-node-data br) data) (if (avl-tree-do-delete cmpfun br 1 data) (avl-tree-del-balance2 root branch))) (t ;; Found it. Let's delete it. (cond - ((null (elib-node-right br)) - (elib-node-set-branch root branch (elib-node-left br)) + ((null (avl-tree-node-right br)) + (avl-tree-node-set-branch root branch (avl-tree-node-left br)) t) - ((null (elib-node-left br)) - (elib-node-set-branch root branch (elib-node-right br)) + ((null (avl-tree-node-left br)) + (avl-tree-node-set-branch root branch (avl-tree-node-right br)) t) (t @@ -280,7 +280,7 @@ (defun avl-tree-enter-balance1 (node branch) ;; Rebalance a tree and return t if the height of the tree has grown. - (let* ((br (elib-node-branch node branch)) + (let* ((br (avl-tree-node-branch node branch)) p1 p2 b2 @@ -296,35 +296,35 @@ (t ;; Tree has grown => Rebalance. - (setq p1 (elib-node-right br)) + (setq p1 (avl-tree-node-right br)) (if (> (avl-tree-node-balance p1) 0) ;; Single RR rotation. (progn - (elib-node-set-right br (elib-node-left p1)) - (elib-node-set-left p1 br) + (avl-tree-node-set-right br (avl-tree-node-left p1)) + (avl-tree-node-set-left p1 br) (avl-tree-node-set-balance br 0) - (elib-node-set-branch node branch p1)) + (avl-tree-node-set-branch node branch p1)) ;; Double RL rotation. - (setq p2 (elib-node-left p1) + (setq p2 (avl-tree-node-left p1) b2 (avl-tree-node-balance p2)) - (elib-node-set-left p1 (elib-node-right p2)) - (elib-node-set-right p2 p1) - (elib-node-set-right br (elib-node-left p2)) - (elib-node-set-left p2 br) + (avl-tree-node-set-left p1 (avl-tree-node-right p2)) + (avl-tree-node-set-right p2 p1) + (avl-tree-node-set-right br (avl-tree-node-left p2)) + (avl-tree-node-set-left p2 br) (if (> b2 0) (avl-tree-node-set-balance br -1) (avl-tree-node-set-balance br 0)) (if (< b2 0) (avl-tree-node-set-balance p1 +1) (avl-tree-node-set-balance p1 0)) - (elib-node-set-branch node branch p2)) - (avl-tree-node-set-balance (elib-node-branch node branch) 0) + (avl-tree-node-set-branch node branch p2)) + (avl-tree-node-set-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 (elib-node-branch node branch)) + (let* ((br (avl-tree-node-branch node branch)) p1 p2 b2) @@ -339,56 +339,56 @@ (t ;; Balance was -1 => Rebalance. - (setq p1 (elib-node-left br)) + (setq p1 (avl-tree-node-left br)) (if (< (avl-tree-node-balance p1) 0) ;; Single LL rotation. (progn - (elib-node-set-left br (elib-node-right p1)) - (elib-node-set-right p1 br) + (avl-tree-node-set-left br (avl-tree-node-right p1)) + (avl-tree-node-set-right p1 br) (avl-tree-node-set-balance br 0) - (elib-node-set-branch node branch p1)) + (avl-tree-node-set-branch node branch p1)) ;; Double LR rotation. - (setq p2 (elib-node-right p1) + (setq p2 (avl-tree-node-right p1) b2 (avl-tree-node-balance p2)) - (elib-node-set-right p1 (elib-node-left p2)) - (elib-node-set-left p2 p1) - (elib-node-set-left br (elib-node-right p2)) - (elib-node-set-right p2 br) + (avl-tree-node-set-right p1 (avl-tree-node-left p2)) + (avl-tree-node-set-left p2 p1) + (avl-tree-node-set-left br (avl-tree-node-right p2)) + (avl-tree-node-set-right p2 br) (if (< b2 0) (avl-tree-node-set-balance br +1) (avl-tree-node-set-balance br 0)) (if (> b2 0) (avl-tree-node-set-balance p1 -1) (avl-tree-node-set-balance p1 0)) - (elib-node-set-branch node branch p2)) - (avl-tree-node-set-balance (elib-node-branch node branch) 0) + (avl-tree-node-set-branch node branch p2)) + (avl-tree-node-set-balance (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. - (let ((br (elib-node-branch root branch))) + (let ((br (avl-tree-node-branch root branch))) (cond ((null br) ;; Data not in tree, insert it. - (elib-node-set-branch root branch + (avl-tree-node-set-branch root branch (avl-tree-node-create nil nil data 0)) t) - ((funcall cmpfun data (elib-node-data br)) + ((funcall cmpfun data (avl-tree-node-data br)) (and (avl-tree-do-enter cmpfun br 0 data) (avl-tree-enter-balance2 root branch))) - ((funcall cmpfun (elib-node-data br) data) + ((funcall cmpfun (avl-tree-node-data br) data) (and (avl-tree-do-enter cmpfun br 1 data) (avl-tree-enter-balance1 root branch))) (t - (elib-node-set-data br data) + (avl-tree-node-set-data br data) nil)))) ;; ---------------------------------------------------------------- @@ -405,16 +405,16 @@ (push nil stack) (while node (if (and go-left - (elib-node-left node)) + (avl-tree-node-left node)) ;; Do the left subtree first. (progn (push node stack) - (setq node (elib-node-left node))) + (setq node (avl-tree-node-left node))) ;; Apply the function... (funcall map-function node) ;; and do the right subtree. - (if (elib-node-right node) - (setq node (elib-node-right node) + (if (avl-tree-node-right node) + (setq node (avl-tree-node-right node) go-left t) (setq node (pop stack) go-left nil)))))) @@ -424,9 +424,9 @@ ;; Highly recursive. INTERNAL USE ONLY. (if (null root) nil - (avl-tree-node-create (avl-tree-do-copy (elib-node-left root)) - (avl-tree-do-copy (elib-node-right root)) - (elib-node-data root) + (avl-tree-node-create (avl-tree-do-copy (avl-tree-node-left root)) + (avl-tree-do-copy (avl-tree-node-right root)) + (avl-tree-node-data root) (avl-tree-node-balance root)))) @@ -482,24 +482,24 @@ (while (and node (not found)) (cond - ((funcall compare-function data (elib-node-data node)) - (setq node (elib-node-left node))) - ((funcall compare-function (elib-node-data node) data) - (setq node (elib-node-right node))) + ((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 - (elib-node-data node) + (avl-tree-node-data node) nil))) (defun avl-tree-map (__map-function__ tree) "Apply MAP-FUNCTION to all elements in the avl tree TREE." (avl-tree-mapc (function (lambda (node) - (elib-node-set-data node + (avl-tree-node-set-data node (funcall __map-function__ - (elib-node-data node))))) + (avl-tree-node-data node))))) (avl-tree-root tree))) (defun avl-tree-first (tree) @@ -507,9 +507,9 @@ (let ((node (avl-tree-root tree))) (if node (progn - (while (elib-node-left node) - (setq node (elib-node-left node))) - (elib-node-data node)) + (while (avl-tree-node-left node) + (setq node (avl-tree-node-left node))) + (avl-tree-node-data node)) nil))) (defun avl-tree-last (tree) @@ -517,16 +517,16 @@ (let ((node (avl-tree-root tree))) (if node (progn - (while (elib-node-right node) - (setq node (elib-node-right node))) - (elib-node-data node)) + (while (avl-tree-node-right node) + (setq node (avl-tree-node-right node))) + (avl-tree-node-data node)) nil))) (defun avl-tree-copy (tree) "Return a copy of the avl tree TREE." (let ((new-tree (avl-tree-create (avl-tree-cmpfun tree)))) - (elib-node-set-left (avl-tree-dummyroot new-tree) + (avl-tree-node-set-left (avl-tree-dummyroot new-tree) (avl-tree-do-copy (avl-tree-root tree))) new-tree)) @@ -535,7 +535,7 @@ (nreverse (let ((treelist nil)) (avl-tree-mapc (function (lambda (node) - (setq treelist (cons (elib-node-data node) + (setq treelist (cons (avl-tree-node-data node) treelist)))) (avl-tree-root tree)) treelist))) @@ -551,7 +551,7 @@ (defun avl-tree-clear (tree) "Clear the avl tree TREE." - (elib-node-set-left (avl-tree-dummyroot tree) nil)) + (avl-tree-node-set-left (avl-tree-dummyroot tree) nil)) (provide 'avl-tree)