# HG changeset patch
# User Thien-Thi Nguyen <ttn@gnuvola.org>
# Date 1188181883 0
# Node ID 0ff5cfe8966308053468b11ff33d0b898047c5f1
# Parent  f0fad697d0aa9c076444ab775394f014f5cc61cb
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.

diff -r f0fad697d0aa -r 0ff5cfe89663 lisp/emacs-lisp/avl-tree.el
--- 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)