From 1e38b8ffcda998f58be1d33dc35ec83e75ff9749 Mon Sep 17 00:00:00 2001 From: Thien-Thi Nguyen Date: Mon, 27 Aug 2007 01:05:44 +0000 Subject: Initial revision, comprising elib-node.el and avltree.el, with minimum modifications for standalone-compilation. --- lisp/emacs-lisp/avl-tree.el | 715 ++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 715 insertions(+) create mode 100644 lisp/emacs-lisp/avl-tree.el (limited to 'lisp/emacs-lisp/avl-tree.el') diff --git a/lisp/emacs-lisp/avl-tree.el b/lisp/emacs-lisp/avl-tree.el new file mode 100644 index 00000000000..59ce6f891ce --- /dev/null +++ b/lisp/emacs-lisp/avl-tree.el @@ -0,0 +1,715 @@ +;;;; $Id: elib-node.el,v 0.8 1995/12/11 00:11:19 ceder Exp $ +;;;; Nodes used in binary trees and doubly linked lists. + +;; Copyright (C) 1991-1995 Free Software Foundation + +;; Author: Per Cederqvist +;; Inge Wallin +;; Maintainer: elib-maintainers@lysator.liu.se +;; Created: 20 May 1991 +;; Keywords: extensions, lisp + +;;;; This file is part of the GNU Emacs lisp library, Elib. +;;;; +;;;; GNU Elib is free software; you can redistribute it and/or modify +;;;; it under the terms of the GNU General Public License as published by +;;;; the Free Software Foundation; either version 2, or (at your option) +;;;; any later version. +;;;; +;;;; GNU Elib is distributed in the hope that it will be useful, +;;;; but WITHOUT ANY WARRANTY; without even the implied warranty of +;;;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +;;;; GNU General Public License for more details. +;;;; +;;;; You should have received a copy of the GNU General Public License +;;;; along with GNU Elib; see the file COPYING. If not, write to +;;;; the Free Software Foundation, Inc., 59 Temple Place - Suite 330, +;;;; Boston, MA 02111-1307, USA +;;;; +;;;; Author: Inge Wallin +;;;; + +;;; Commentary: + +;;; A node is implemented as an array with three elements, using +;;; (elt node 0) as the left pointer +;;; (elt node 1) as the right pointer +;;; (elt node 2) as the data +;;; +;;; Some types of trees, e.g. AVL trees, need bigger nodes, but +;;; as long as the first three parts are the left pointer, the +;;; right pointer and the data field, these macros can be used. +;;; + +;;; Code: + +;;; Begin HACKS to make avl-tree.el standalone. +;;; +;;; 0/ Don't do this. +;;; (provide 'elib-node) +;;; +;;; End HACKS to make avl-tree.el standalone. + + +(defmacro elib-node-create (left right data) + + ;; Create a tree node from LEFT, RIGHT and DATA. + (` (vector (, left) (, right) (, data)))) + + +(defmacro elib-node-left (node) + + ;; Return the left pointer of NODE. + (` (aref (, node) 0))) + + +(defmacro elib-node-right (node) + + ;; Return the right pointer of NODE. + (` (aref (, node) 1))) + + +(defmacro elib-node-data (node) + + ;; Return the data of NODE. + (` (aref (, node) 2))) + + +(defmacro elib-node-set-left (node newleft) + + ;; Set the left pointer of NODE to NEWLEFT. + (` (aset (, node) 0 (, newleft)))) + + +(defmacro elib-node-set-right (node newright) + + ;; Set the right pointer of NODE to NEWRIGHT. + (` (aset (, node) 1 (, newright)))) + + +(defmacro elib-node-set-data (node newdata) + ;; Set the data of NODE to NEWDATA. + (` (aset (, node) 2 (, newdata)))) + + + +(defmacro elib-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) + + ;; Set value of a branch of a node. + ;; + ;; NODE is the node, and BRANCH is the branch. + ;; 0 for left pointer, 1 for the right pointer and 2 for the data. + ;; NEWVAL is new value of the branch." + (` (aset (, node) (, branch) (, newval)))) + +;;; elib-node.el ends here. +;;;; $Id: avltree.el,v 0.8 1995/12/11 00:10:54 ceder Exp $ +;;;; This file implements balanced binary trees, AVL-trees. + +;; Copyright (C) 1991-1995 Free Software Foundation + +;; Author: Inge Wallin +;; Thomas Bellman +;; Maintainer: elib-maintainers@lysator.liu.se +;; Created: 10 May 1991 +;; Keywords: extensions, lisp + +;;;; This file is part of the GNU Emacs lisp library, Elib. +;;;; +;;;; GNU Elib is free software; you can redistribute it and/or modify +;;;; it under the terms of the GNU General Public License as published by +;;;; the Free Software Foundation; either version 2, or (at your option) +;;;; any later version. +;;;; +;;;; GNU Elib is distributed in the hope that it will be useful, +;;;; but WITHOUT ANY WARRANTY; without even the implied warranty of +;;;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +;;;; GNU General Public License for more details. +;;;; +;;;; You should have received a copy of the GNU General Public License +;;;; along with GNU Elib; see the file COPYING. If not, write to +;;;; the Free Software Foundation, Inc., 59 Temple Place - Suite 330, +;;;; Boston, MA 02111-1307, USA +;;;; +;;;; Initial author: Thomas Bellman +;;;; Lysator Computer Club +;;;; Linkoping University +;;;; Sweden +;;;; +;;;; Bugfixes and completion: Inge Wallin +;;;; + + +;;; Commentary: +;;; +;;; An AVL tree is a nearly-perfect balanced binary tree. A tree +;;; consists of two cons cells, the first one holding the tag +;;; 'AVLTREE in the car cell, and the second one having the tree +;;; in the car and the compare function in the cdr cell. The tree has +;;; a dummy node as its root with the real tree in the left pointer. +;;; +;;; 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. +;;; + +;;; Code: + +;;; Begin HACKS to make avl-tree.el standalone. +;;; +;;; 1/ See above for inlined elib-node.el. +;;; (require 'elib-node) +;;; +;;; 2/ This requirement has been replaced w/ new code. +;;; (require 'stack-m) +;;; +;;; 3/ New code: +(eval-when-compile (require 'cl)) +(defun elib-stack-create () (list)) +(defmacro elib-stack-push (stack object) `(push ,object ,stack)) +(defmacro elib-stack-pop (stack) `(pop ,stack)) +;;; +;;; 4/ Provide `avl-tree' instead of `avltree'. +(provide 'avl-tree) +;;; +;;; End HACKS to make avl-tree.el standalone. + + +;;; ================================================================ +;;; Functions and macros handling an AVL tree node. + +;; +;; The rest of the functions needed here can be found in +;; elib-node.el. +;; + + +(defmacro elib-avl-node-create (left right data balance) + + ;; Create and return an avl-tree node. + (` (vector (, left) (, right) (, data) (, balance)))) + + +(defmacro elib-avl-node-balance (node) + + ;; Return the balance field of a node. + (` (aref (, node) 3))) + + +(defmacro elib-avl-node-set-balance (node newbal) + + ;; Set the balance field of a node. + (` (aset (, node) 3 (, newbal)))) + + + +;;; ================================================================ +;;; Internal functions for use in the AVL tree package + +;;; +;;; The functions and macros in this section all start with `elib-avl-'. +;;; + + +(defmacro elib-avl-root (tree) + + ;; Return the root node for an avl-tree. INTERNAL USE ONLY. + (` (elib-node-left (car (cdr (, tree)))))) + + +(defmacro elib-avl-dummyroot (tree) + + ;; Return the dummy node of an avl-tree. INTERNAL USE ONLY. + + (` (car (cdr (, tree))))) + + +(defmacro elib-avl-cmpfun (tree) + + ;; Return the compare function of AVL tree TREE. INTERNAL USE ONLY. + (` (cdr (cdr (, tree))))) + + +;; ---------------------------------------------------------------- +;; Deleting data + + +(defun elib-avl-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)) + p1 + b1 + p2 + b2 + result) + (cond + ((< (elib-avl-node-balance br) 0) + (elib-avl-node-set-balance br 0) + t) + + ((= (elib-avl-node-balance br) 0) + (elib-avl-node-set-balance br +1) + nil) + + (t ; Rebalance + (setq p1 (elib-node-right br) + b1 (elib-avl-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) + (if (= 0 b1) + (progn + (elib-avl-node-set-balance br +1) + (elib-avl-node-set-balance p1 -1) + (setq result nil)) + (elib-avl-node-set-balance br 0) + (elib-avl-node-set-balance p1 0) + (setq result t)) + (elib-node-set-branch node branch p1) + result) + + ;; Double RL rotation + (setq p2 (elib-node-left p1) + b2 (elib-avl-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) + (if (> b2 0) + (elib-avl-node-set-balance br -1) + (elib-avl-node-set-balance br 0)) + (if (< b2 0) + (elib-avl-node-set-balance p1 +1) + (elib-avl-node-set-balance p1 0)) + (elib-node-set-branch node branch p2) + (elib-avl-node-set-balance p2 0) + t) + )) + )) + + +(defun elib-avl-del-balance2 (node branch) + + (let* ((br (elib-node-branch node branch)) + p1 + b1 + p2 + b2 + result) + (cond + ((> (elib-avl-node-balance br) 0) + (elib-avl-node-set-balance br 0) + t) + + ((= (elib-avl-node-balance br) 0) + (elib-avl-node-set-balance br -1) + nil) + + (t ; Rebalance + (setq p1 (elib-node-left br) + b1 (elib-avl-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) + (if (= 0 b1) + (progn + (elib-avl-node-set-balance br -1) + (elib-avl-node-set-balance p1 +1) + (setq result nil)) + (elib-avl-node-set-balance br 0) + (elib-avl-node-set-balance p1 0) + (setq result t)) + (elib-node-set-branch node branch p1) + result) + + ;; Double LR rotation + (setq p2 (elib-node-right p1) + b2 (elib-avl-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) + (if (< b2 0) + (elib-avl-node-set-balance br +1) + (elib-avl-node-set-balance br 0)) + (if (> b2 0) + (elib-avl-node-set-balance p1 -1) + (elib-avl-node-set-balance p1 0)) + (elib-node-set-branch node branch p2) + (elib-avl-node-set-balance p2 0) + t) + )) + )) + + +(defun elib-avl-do-del-internal (node branch q) + + (let* ((br (elib-node-branch node branch))) + (if (elib-node-right br) + (if (elib-avl-do-del-internal br +1 q) + (elib-avl-del-balance2 node branch)) + (elib-node-set-data q (elib-node-data br)) + (elib-node-set-branch node branch + (elib-node-left br)) + t))) + + + +(defun elib-avl-do-delete (cmpfun root branch data) + + ;; Return t if the height of the tree has shrunk. + (let* ((br (elib-node-branch root branch))) + (cond + ((null br) + nil) + + ((funcall cmpfun data (elib-node-data br)) + (if (elib-avl-do-delete cmpfun br 0 data) + (elib-avl-del-balance1 root branch))) + + ((funcall cmpfun (elib-node-data br) data) + (if (elib-avl-do-delete cmpfun br 1 data) + (elib-avl-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)) + t) + + ((null (elib-node-left br)) + (elib-node-set-branch root branch (elib-node-right br)) + t) + + (t + (if (elib-avl-do-del-internal br 0 br) + (elib-avl-del-balance1 root branch))))) + ))) + + +;; ---------------------------------------------------------------- +;; Entering data + + + +(defun elib-avl-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)) + p1 + p2 + b2 + result) + (cond + ((< (elib-avl-node-balance br) 0) + (elib-avl-node-set-balance br 0) + nil) + + ((= (elib-avl-node-balance br) 0) + (elib-avl-node-set-balance br +1) + t) + + (t + ;; Tree has grown => Rebalance + (setq p1 (elib-node-right br)) + (if (> (elib-avl-node-balance p1) 0) + ;; Single RR rotation + (progn + (elib-node-set-right br (elib-node-left p1)) + (elib-node-set-left p1 br) + (elib-avl-node-set-balance br 0) + (elib-node-set-branch node branch p1)) + + ;; Double RL rotation + (setq p2 (elib-node-left p1) + b2 (elib-avl-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) + (if (> b2 0) + (elib-avl-node-set-balance br -1) + (elib-avl-node-set-balance br 0)) + (if (< b2 0) + (elib-avl-node-set-balance p1 +1) + (elib-avl-node-set-balance p1 0)) + (elib-node-set-branch node branch p2)) + (elib-avl-node-set-balance (elib-node-branch node branch) 0) + nil)) + )) + + +(defun elib-avl-enter-balance2 (node branch) + + ;; Return t if the tree has grown. + (let* ((br (elib-node-branch node branch)) + p1 + p2 + b2) + (cond + ((> (elib-avl-node-balance br) 0) + (elib-avl-node-set-balance br 0) + nil) + + ((= (elib-avl-node-balance br) 0) + (elib-avl-node-set-balance br -1) + t) + + (t + ;; Balance was -1 => Rebalance + (setq p1 (elib-node-left br)) + (if (< (elib-avl-node-balance p1) 0) + ;; Single LL rotation + (progn + (elib-node-set-left br (elib-node-right p1)) + (elib-node-set-right p1 br) + (elib-avl-node-set-balance br 0) + (elib-node-set-branch node branch p1)) + + ;; Double LR rotation + (setq p2 (elib-node-right p1) + b2 (elib-avl-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) + (if (< b2 0) + (elib-avl-node-set-balance br +1) + (elib-avl-node-set-balance br 0)) + (if (> b2 0) + (elib-avl-node-set-balance p1 -1) + (elib-avl-node-set-balance p1 0)) + (elib-node-set-branch node branch p2)) + (elib-avl-node-set-balance (elib-node-branch node branch) 0) + nil)) + )) + + +(defun elib-avl-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))) + (cond + ((null br) + ;; Data not in tree, insert it + (elib-node-set-branch root branch + (elib-avl-node-create nil nil data 0)) + t) + + ((funcall cmpfun data (elib-node-data br)) + (and (elib-avl-do-enter cmpfun + br + 0 data) + (elib-avl-enter-balance2 root branch))) + + ((funcall cmpfun (elib-node-data br) data) + (and (elib-avl-do-enter cmpfun + br + 1 data) + (elib-avl-enter-balance1 root branch))) + + (t + (elib-node-set-data br data) + nil)))) + + +;; ---------------------------------------------------------------- + + +(defun elib-avl-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. + + (let ((node root) + (stack (elib-stack-create)) + (go-left t)) + (elib-stack-push stack nil) + (while node + (if (and go-left + (elib-node-left node)) + (progn ; Do the left subtree first. + (elib-stack-push stack node) + (setq node (elib-node-left node))) + (funcall map-function node) ; Apply the function... + (if (elib-node-right node) ; and do the right subtree. + (setq node (elib-node-right node) + go-left t) + (setq node (elib-stack-pop stack) + go-left nil)))))) + + +(defun elib-avl-do-copy (root) + ;; Copy the tree with ROOT as root. + ;; Highly recursive. INTERNAL USE ONLY. + (if (null root) + nil + (elib-avl-node-create (elib-avl-do-copy (elib-node-left root)) + (elib-avl-do-copy (elib-node-right root)) + (elib-node-data root) + (elib-avl-node-balance root)))) + + + +;;; ================================================================ +;;; The public functions which operate on AVL trees. + + +(defun avltree-create (compare-function) + "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." + (cons 'AVLTREE + (cons (elib-avl-node-create nil nil nil 0) + compare-function))) + + +(defun avltree-p (obj) + "Return t if OBJ is an avl tree, nil otherwise." + (eq (car-safe obj) 'AVLTREE)) + + +(defun avltree-compare-function (tree) + "Return the comparision function for the avl tree TREE." + (elib-avl-cmpfun tree)) + + +(defun avltree-empty (tree) + "Return t if TREE is emtpy, otherwise return nil." + (null (elib-avl-root tree))) + + +(defun avltree-enter (tree data) + "In the avl tree TREE insert DATA. +Return DATA." + + (elib-avl-do-enter (elib-avl-cmpfun tree) + (elib-avl-dummyroot tree) + 0 + data) + data) + + +(defun avltree-delete (tree data) + "From the avl tree TREE, delete DATA. +Return the element in TREE which matched DATA, nil if no element matched." + + (elib-avl-do-delete (elib-avl-cmpfun tree) + (elib-avl-dummyroot tree) + 0 + data)) + + +(defun avltree-member (tree data) + "Return the element in the avl tree TREE which matches DATA. +Matching uses the compare function previously specified in `avltree-create' +when TREE was created. + +If there is no such element in the tree, the value is nil." + + (let ((node (elib-avl-root tree)) + (compare-function (elib-avl-cmpfun tree)) + found) + (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))) + (t + (setq found t)))) + + (if node + (elib-node-data node) + nil))) + + + +(defun avltree-map (__map-function__ tree) + "Apply MAP-FUNCTION to all elements in the avl tree TREE." + (elib-avl-mapc + (function (lambda (node) + (elib-node-set-data node + (funcall __map-function__ + (elib-node-data node))))) + (elib-avl-root tree))) + + + +(defun avltree-first (tree) + "Return the first element in TREE, or nil if TREE is empty." + + (let ((node (elib-avl-root tree))) + (if node + (progn + (while (elib-node-left node) + (setq node (elib-node-left node))) + (elib-node-data node)) + nil))) + + +(defun avltree-last (tree) + "Return the last element in TREE, or nil if TREE is empty." + (let ((node (elib-avl-root tree))) + (if node + (progn + (while (elib-node-right node) + (setq node (elib-node-right node))) + (elib-node-data node)) + nil))) + + +(defun avltree-copy (tree) + "Return a copy of the avl tree TREE." + (let ((new-tree (avltree-create + (elib-avl-cmpfun tree)))) + (elib-node-set-left (elib-avl-dummyroot new-tree) + (elib-avl-do-copy (elib-avl-root tree))) + new-tree)) + + +(defun avltree-flatten (tree) + "Return a sorted list containing all elements of TREE." + (nreverse + (let ((treelist nil)) + (elib-avl-mapc (function (lambda (node) + (setq treelist (cons (elib-node-data node) + treelist)))) + (elib-avl-root tree)) + treelist))) + + +(defun avltree-size (tree) + "Return the number of elements in TREE." + (let ((treesize 0)) + (elib-avl-mapc (function (lambda (data) + (setq treesize (1+ treesize)) + data)) + (elib-avl-root tree)) + treesize)) + + +(defun avltree-clear (tree) + "Clear the avl tree TREE." + (elib-node-set-left (elib-avl-dummyroot tree) nil)) + +;;; avltree.el ends here -- cgit v1.2.3 From b74e26bbe218674e310249a3cd233dcf4a84850a Mon Sep 17 00:00:00 2001 From: Thien-Thi Nguyen Date: Mon, 27 Aug 2007 01:28:07 +0000 Subject: Munge comments, whitespace, indentation, hanging parens; nfc. --- lisp/emacs-lisp/avl-tree.el | 649 +++++++++++++++++--------------------------- 1 file changed, 252 insertions(+), 397 deletions(-) (limited to 'lisp/emacs-lisp/avl-tree.el') diff --git a/lisp/emacs-lisp/avl-tree.el b/lisp/emacs-lisp/avl-tree.el index 59ce6f891ce..75ec86c0d0e 100644 --- a/lisp/emacs-lisp/avl-tree.el +++ b/lisp/emacs-lisp/avl-tree.el @@ -1,109 +1,95 @@ -;;;; $Id: elib-node.el,v 0.8 1995/12/11 00:11:19 ceder Exp $ -;;;; Nodes used in binary trees and doubly linked lists. +;;; avl-tree.el --- balanced binary trees, AVL-trees -;; Copyright (C) 1991-1995 Free Software Foundation +;; Copyright (C) 1995, 2007 Free Software Foundation, Inc. ;; Author: Per Cederqvist ;; Inge Wallin -;; Maintainer: elib-maintainers@lysator.liu.se -;; Created: 20 May 1991 -;; Keywords: extensions, lisp - -;;;; This file is part of the GNU Emacs lisp library, Elib. -;;;; -;;;; GNU Elib is free software; you can redistribute it and/or modify -;;;; it under the terms of the GNU General Public License as published by -;;;; the Free Software Foundation; either version 2, or (at your option) -;;;; any later version. -;;;; -;;;; GNU Elib is distributed in the hope that it will be useful, -;;;; but WITHOUT ANY WARRANTY; without even the implied warranty of -;;;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the -;;;; GNU General Public License for more details. -;;;; -;;;; You should have received a copy of the GNU General Public License -;;;; along with GNU Elib; see the file COPYING. If not, write to -;;;; the Free Software Foundation, Inc., 59 Temple Place - Suite 330, -;;;; Boston, MA 02111-1307, USA -;;;; -;;;; Author: Inge Wallin -;;;; +;; Thomas Bellman +;; Maintainer: FSF +;; Created: 10 May 1991 +;; Keywords: extensions, data structures -;;; Commentary: +;; This file is part of GNU Emacs. -;;; A node is implemented as an array with three elements, using -;;; (elt node 0) as the left pointer -;;; (elt node 1) as the right pointer -;;; (elt node 2) as the data -;;; -;;; Some types of trees, e.g. AVL trees, need bigger nodes, but -;;; as long as the first three parts are the left pointer, the -;;; right pointer and the data field, these macros can be used. -;;; +;; GNU Emacs is free software; you can redistribute it and/or modify +;; it under the terms of the GNU General Public License as published by +;; the Free Software Foundation; either version 3, or (at your option) +;; any later version. -;;; Code: +;; GNU Emacs is distributed in the hope that it will be useful, +;; but WITHOUT ANY WARRANTY; without even the implied warranty of +;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +;; GNU General Public License for more details. -;;; Begin HACKS to make avl-tree.el standalone. -;;; -;;; 0/ Don't do this. -;;; (provide 'elib-node) -;;; -;;; End HACKS to make avl-tree.el standalone. +;; You should have received a copy of the GNU General Public License +;; along with GNU Emacs; see the file COPYING. If not, write to the +;; Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, +;; Boston, MA 02110-1301, USA. +;;; Commentary: -(defmacro elib-node-create (left right data) +;; This file combines elib-node.el and avltree.el from Elib. +;; +;; * Comments from elib-node.el +;; A node is implemented as an array with three elements, using +;; (elt node 0) as the left pointer +;; (elt node 1) as the right pointer +;; (elt node 2) as the data +;; +;; Some types of trees, e.g. AVL trees, need bigger nodes, but +;; as long as the first three parts are the left pointer, the +;; right pointer and the data field, these macros can be used. +;; +;; * Comments from avltree.el +;; An AVL tree is a nearly-perfect balanced binary tree. A tree +;; consists of two cons cells, the first one holding the tag +;; 'AVLTREE in the car cell, and the second one having the tree +;; in the car and the compare function in the cdr cell. The tree has +;; a dummy node as its root with the real tree in the left pointer. +;; +;; 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. +;;; Code: + +(defmacro elib-node-create (left right data) ;; Create a tree node from LEFT, RIGHT and DATA. (` (vector (, left) (, right) (, data)))) - (defmacro elib-node-left (node) - ;; Return the left pointer of NODE. (` (aref (, node) 0))) - (defmacro elib-node-right (node) - ;; Return the right pointer of NODE. (` (aref (, node) 1))) - (defmacro elib-node-data (node) - ;; Return the data of NODE. (` (aref (, node) 2))) - (defmacro elib-node-set-left (node newleft) - ;; Set the left pointer of NODE to NEWLEFT. (` (aset (, node) 0 (, newleft)))) - (defmacro elib-node-set-right (node newright) - ;; Set the right pointer of NODE to NEWRIGHT. (` (aset (, node) 1 (, newright)))) - (defmacro elib-node-set-data (node newdata) ;; Set the data of NODE to NEWDATA. (` (aset (, node) 2 (, newdata)))) - - (defmacro elib-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) - ;; Set value of a branch of a node. ;; ;; NODE is the node, and BRANCH is the branch. @@ -111,107 +97,27 @@ ;; NEWVAL is new value of the branch." (` (aset (, node) (, branch) (, newval)))) -;;; elib-node.el ends here. -;;;; $Id: avltree.el,v 0.8 1995/12/11 00:10:54 ceder Exp $ -;;;; This file implements balanced binary trees, AVL-trees. - -;; Copyright (C) 1991-1995 Free Software Foundation - -;; Author: Inge Wallin -;; Thomas Bellman -;; Maintainer: elib-maintainers@lysator.liu.se -;; Created: 10 May 1991 -;; Keywords: extensions, lisp - -;;;; This file is part of the GNU Emacs lisp library, Elib. -;;;; -;;;; GNU Elib is free software; you can redistribute it and/or modify -;;;; it under the terms of the GNU General Public License as published by -;;;; the Free Software Foundation; either version 2, or (at your option) -;;;; any later version. -;;;; -;;;; GNU Elib is distributed in the hope that it will be useful, -;;;; but WITHOUT ANY WARRANTY; without even the implied warranty of -;;;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the -;;;; GNU General Public License for more details. -;;;; -;;;; You should have received a copy of the GNU General Public License -;;;; along with GNU Elib; see the file COPYING. If not, write to -;;;; the Free Software Foundation, Inc., 59 Temple Place - Suite 330, -;;;; Boston, MA 02111-1307, USA -;;;; -;;;; Initial author: Thomas Bellman -;;;; Lysator Computer Club -;;;; Linkoping University -;;;; Sweden -;;;; -;;;; Bugfixes and completion: Inge Wallin -;;;; - - -;;; Commentary: -;;; -;;; An AVL tree is a nearly-perfect balanced binary tree. A tree -;;; consists of two cons cells, the first one holding the tag -;;; 'AVLTREE in the car cell, and the second one having the tree -;;; in the car and the compare function in the cdr cell. The tree has -;;; a dummy node as its root with the real tree in the left pointer. -;;; -;;; 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. -;;; - -;;; Code: - -;;; Begin HACKS to make avl-tree.el standalone. -;;; -;;; 1/ See above for inlined elib-node.el. -;;; (require 'elib-node) -;;; -;;; 2/ This requirement has been replaced w/ new code. -;;; (require 'stack-m) -;;; -;;; 3/ New code: (eval-when-compile (require 'cl)) (defun elib-stack-create () (list)) (defmacro elib-stack-push (stack object) `(push ,object ,stack)) (defmacro elib-stack-pop (stack) `(pop ,stack)) -;;; -;;; 4/ Provide `avl-tree' instead of `avltree'. (provide 'avl-tree) -;;; -;;; End HACKS to make avl-tree.el standalone. - ;;; ================================================================ ;;; Functions and macros handling an AVL tree node. -;; -;; The rest of the functions needed here can be found in -;; elib-node.el. -;; - - (defmacro elib-avl-node-create (left right data balance) - ;; Create and return an avl-tree node. (` (vector (, left) (, right) (, data) (, balance)))) - (defmacro elib-avl-node-balance (node) - ;; Return the balance field of a node. (` (aref (, node) 3))) - (defmacro elib-avl-node-set-balance (node newbal) - ;; Set the balance field of a node. (` (aset (, node) 3 (, newbal)))) - ;;; ================================================================ ;;; Internal functions for use in the AVL tree package @@ -220,39 +126,29 @@ ;;; The functions and macros in this section all start with `elib-avl-'. ;;; - (defmacro elib-avl-root (tree) - ;; Return the root node for an avl-tree. INTERNAL USE ONLY. (` (elib-node-left (car (cdr (, tree)))))) - (defmacro elib-avl-dummyroot (tree) - ;; Return the dummy node of an avl-tree. INTERNAL USE ONLY. - (` (car (cdr (, tree))))) - (defmacro elib-avl-cmpfun (tree) - ;; Return the compare function of AVL tree TREE. INTERNAL USE ONLY. (` (cdr (cdr (, tree))))) - ;; ---------------------------------------------------------------- ;; Deleting data - (defun elib-avl-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)) - p1 - b1 - p2 - b2 - result) + p1 + b1 + p2 + b2 + result) (cond ((< (elib-avl-node-balance br) 0) (elib-avl-node-set-balance br 0) @@ -262,53 +158,50 @@ (elib-avl-node-set-balance br +1) nil) - (t ; Rebalance + (t + ;; Rebalance. (setq p1 (elib-node-right br) - b1 (elib-avl-node-balance p1)) + b1 (elib-avl-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) - (if (= 0 b1) - (progn - (elib-avl-node-set-balance br +1) - (elib-avl-node-set-balance p1 -1) - (setq result nil)) - (elib-avl-node-set-balance br 0) - (elib-avl-node-set-balance p1 0) - (setq result t)) - (elib-node-set-branch node branch p1) - result) - - ;; Double RL rotation - (setq p2 (elib-node-left p1) - b2 (elib-avl-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) - (if (> b2 0) - (elib-avl-node-set-balance br -1) - (elib-avl-node-set-balance br 0)) - (if (< b2 0) - (elib-avl-node-set-balance p1 +1) - (elib-avl-node-set-balance p1 0)) - (elib-node-set-branch node branch p2) - (elib-avl-node-set-balance p2 0) - t) - )) - )) - + ;; Single RR rotation. + (progn + (elib-node-set-right br (elib-node-left p1)) + (elib-node-set-left p1 br) + (if (= 0 b1) + (progn + (elib-avl-node-set-balance br +1) + (elib-avl-node-set-balance p1 -1) + (setq result nil)) + (elib-avl-node-set-balance br 0) + (elib-avl-node-set-balance p1 0) + (setq result t)) + (elib-node-set-branch node branch p1) + result) + + ;; Double RL rotation. + (setq p2 (elib-node-left p1) + b2 (elib-avl-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) + (if (> b2 0) + (elib-avl-node-set-balance br -1) + (elib-avl-node-set-balance br 0)) + (if (< b2 0) + (elib-avl-node-set-balance p1 +1) + (elib-avl-node-set-balance p1 0)) + (elib-node-set-branch node branch p2) + (elib-avl-node-set-balance p2 0) + t))))) (defun elib-avl-del-balance2 (node branch) - (let* ((br (elib-node-branch node branch)) - p1 - b1 - p2 - b2 - result) + p1 + b1 + p2 + b2 + result) (cond ((> (elib-avl-node-balance br) 0) (elib-avl-node-set-balance br 0) @@ -318,60 +211,55 @@ (elib-avl-node-set-balance br -1) nil) - (t ; Rebalance + (t + ;; Rebalance. (setq p1 (elib-node-left br) - b1 (elib-avl-node-balance p1)) + b1 (elib-avl-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) - (if (= 0 b1) - (progn - (elib-avl-node-set-balance br -1) - (elib-avl-node-set-balance p1 +1) - (setq result nil)) - (elib-avl-node-set-balance br 0) - (elib-avl-node-set-balance p1 0) - (setq result t)) - (elib-node-set-branch node branch p1) - result) - - ;; Double LR rotation - (setq p2 (elib-node-right p1) - b2 (elib-avl-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) - (if (< b2 0) - (elib-avl-node-set-balance br +1) - (elib-avl-node-set-balance br 0)) - (if (> b2 0) - (elib-avl-node-set-balance p1 -1) - (elib-avl-node-set-balance p1 0)) - (elib-node-set-branch node branch p2) - (elib-avl-node-set-balance p2 0) - t) - )) - )) - + ;; Single LL rotation. + (progn + (elib-node-set-left br (elib-node-right p1)) + (elib-node-set-right p1 br) + (if (= 0 b1) + (progn + (elib-avl-node-set-balance br -1) + (elib-avl-node-set-balance p1 +1) + (setq result nil)) + (elib-avl-node-set-balance br 0) + (elib-avl-node-set-balance p1 0) + (setq result t)) + (elib-node-set-branch node branch p1) + result) + + ;; Double LR rotation. + (setq p2 (elib-node-right p1) + b2 (elib-avl-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) + (if (< b2 0) + (elib-avl-node-set-balance br +1) + (elib-avl-node-set-balance br 0)) + (if (> b2 0) + (elib-avl-node-set-balance p1 -1) + (elib-avl-node-set-balance p1 0)) + (elib-node-set-branch node branch p2) + (elib-avl-node-set-balance p2 0) + t))))) (defun elib-avl-do-del-internal (node branch q) (let* ((br (elib-node-branch node branch))) - (if (elib-node-right br) - (if (elib-avl-do-del-internal br +1 q) - (elib-avl-del-balance2 node branch)) - (elib-node-set-data q (elib-node-data br)) - (elib-node-set-branch node branch - (elib-node-left br)) - t))) - - + (if (elib-node-right br) + (if (elib-avl-do-del-internal br +1 q) + (elib-avl-del-balance2 node branch)) + (elib-node-set-data q (elib-node-data br)) + (elib-node-set-branch node branch + (elib-node-left br)) + t))) (defun elib-avl-do-delete (cmpfun root branch data) - ;; Return t if the height of the tree has shrunk. (let* ((br (elib-node-branch root branch))) (cond @@ -380,42 +268,37 @@ ((funcall cmpfun data (elib-node-data br)) (if (elib-avl-do-delete cmpfun br 0 data) - (elib-avl-del-balance1 root branch))) + (elib-avl-del-balance1 root branch))) ((funcall cmpfun (elib-node-data br) data) (if (elib-avl-do-delete cmpfun br 1 data) - (elib-avl-del-balance2 root branch))) + (elib-avl-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)) - t) + (elib-node-set-branch root branch (elib-node-left br)) + t) ((null (elib-node-left br)) - (elib-node-set-branch root branch (elib-node-right br)) - t) + (elib-node-set-branch root branch (elib-node-right br)) + t) (t - (if (elib-avl-do-del-internal br 0 br) - (elib-avl-del-balance1 root branch))))) - ))) - + (if (elib-avl-do-del-internal br 0 br) + (elib-avl-del-balance1 root branch)))))))) ;; ---------------------------------------------------------------- ;; Entering data - - (defun elib-avl-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)) - p1 - p2 - b2 - result) + p1 + p2 + b2 + result) (cond ((< (elib-avl-node-balance br) 0) (elib-avl-node-set-balance br 0) @@ -426,42 +309,39 @@ t) (t - ;; Tree has grown => Rebalance + ;; Tree has grown => Rebalance. (setq p1 (elib-node-right br)) (if (> (elib-avl-node-balance p1) 0) - ;; Single RR rotation - (progn - (elib-node-set-right br (elib-node-left p1)) - (elib-node-set-left p1 br) - (elib-avl-node-set-balance br 0) - (elib-node-set-branch node branch p1)) - - ;; Double RL rotation - (setq p2 (elib-node-left p1) - b2 (elib-avl-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) - (if (> b2 0) - (elib-avl-node-set-balance br -1) - (elib-avl-node-set-balance br 0)) - (if (< b2 0) - (elib-avl-node-set-balance p1 +1) - (elib-avl-node-set-balance p1 0)) - (elib-node-set-branch node branch p2)) + ;; Single RR rotation. + (progn + (elib-node-set-right br (elib-node-left p1)) + (elib-node-set-left p1 br) + (elib-avl-node-set-balance br 0) + (elib-node-set-branch node branch p1)) + + ;; Double RL rotation. + (setq p2 (elib-node-left p1) + b2 (elib-avl-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) + (if (> b2 0) + (elib-avl-node-set-balance br -1) + (elib-avl-node-set-balance br 0)) + (if (< b2 0) + (elib-avl-node-set-balance p1 +1) + (elib-avl-node-set-balance p1 0)) + (elib-node-set-branch node branch p2)) (elib-avl-node-set-balance (elib-node-branch node branch) 0) - nil)) - )) - + nil)))) (defun elib-avl-enter-balance2 (node branch) - ;; Return t if the tree has grown. (let* ((br (elib-node-branch node branch)) - p1 - p2 - b2) + p1 + p2 + b2) (cond ((> (elib-avl-node-balance br) 0) (elib-avl-node-set-balance br 0) @@ -472,90 +352,86 @@ t) (t - ;; Balance was -1 => Rebalance + ;; Balance was -1 => Rebalance. (setq p1 (elib-node-left br)) (if (< (elib-avl-node-balance p1) 0) - ;; Single LL rotation - (progn - (elib-node-set-left br (elib-node-right p1)) - (elib-node-set-right p1 br) - (elib-avl-node-set-balance br 0) - (elib-node-set-branch node branch p1)) - - ;; Double LR rotation - (setq p2 (elib-node-right p1) - b2 (elib-avl-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) - (if (< b2 0) - (elib-avl-node-set-balance br +1) - (elib-avl-node-set-balance br 0)) - (if (> b2 0) - (elib-avl-node-set-balance p1 -1) - (elib-avl-node-set-balance p1 0)) - (elib-node-set-branch node branch p2)) + ;; Single LL rotation. + (progn + (elib-node-set-left br (elib-node-right p1)) + (elib-node-set-right p1 br) + (elib-avl-node-set-balance br 0) + (elib-node-set-branch node branch p1)) + + ;; Double LR rotation. + (setq p2 (elib-node-right p1) + b2 (elib-avl-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) + (if (< b2 0) + (elib-avl-node-set-balance br +1) + (elib-avl-node-set-balance br 0)) + (if (> b2 0) + (elib-avl-node-set-balance p1 -1) + (elib-avl-node-set-balance p1 0)) + (elib-node-set-branch node branch p2)) (elib-avl-node-set-balance (elib-node-branch node branch) 0) - nil)) - )) - + nil)))) (defun elib-avl-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))) (cond ((null br) - ;; Data not in tree, insert it + ;; Data not in tree, insert it. (elib-node-set-branch root branch - (elib-avl-node-create nil nil data 0)) + (elib-avl-node-create nil nil data 0)) t) ((funcall cmpfun data (elib-node-data br)) (and (elib-avl-do-enter cmpfun - br - 0 data) - (elib-avl-enter-balance2 root branch))) + br + 0 data) + (elib-avl-enter-balance2 root branch))) ((funcall cmpfun (elib-node-data br) data) (and (elib-avl-do-enter cmpfun - br - 1 data) - (elib-avl-enter-balance1 root branch))) + br + 1 data) + (elib-avl-enter-balance1 root branch))) (t (elib-node-set-data br data) nil)))) - ;; ---------------------------------------------------------------- - (defun elib-avl-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. - (let ((node root) - (stack (elib-stack-create)) - (go-left t)) + (stack (elib-stack-create)) + (go-left t)) (elib-stack-push stack nil) (while node (if (and go-left - (elib-node-left node)) - (progn ; Do the left subtree first. - (elib-stack-push stack node) - (setq node (elib-node-left node))) - (funcall map-function node) ; Apply the function... - (if (elib-node-right node) ; and do the right subtree. - (setq node (elib-node-right node) - go-left t) - (setq node (elib-stack-pop stack) - go-left nil)))))) - + (elib-node-left node)) + ;; Do the left subtree first. + (progn + (elib-stack-push stack node) + (setq node (elib-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) + go-left t) + (setq node (elib-stack-pop stack) + go-left nil)))))) (defun elib-avl-do-copy (root) ;; Copy the tree with ROOT as root. @@ -563,60 +439,50 @@ (if (null root) nil (elib-avl-node-create (elib-avl-do-copy (elib-node-left root)) - (elib-avl-do-copy (elib-node-right root)) - (elib-node-data root) - (elib-avl-node-balance root)))) - + (elib-avl-do-copy (elib-node-right root)) + (elib-node-data root) + (elib-avl-node-balance root)))) ;;; ================================================================ ;;; The public functions which operate on AVL trees. - (defun avltree-create (compare-function) "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." (cons 'AVLTREE - (cons (elib-avl-node-create nil nil nil 0) - compare-function))) - + (cons (elib-avl-node-create nil nil nil 0) + compare-function))) (defun avltree-p (obj) "Return t if OBJ is an avl tree, nil otherwise." (eq (car-safe obj) 'AVLTREE)) - (defun avltree-compare-function (tree) "Return the comparision function for the avl tree TREE." (elib-avl-cmpfun tree)) - (defun avltree-empty (tree) "Return t if TREE is emtpy, otherwise return nil." (null (elib-avl-root tree))) - (defun avltree-enter (tree data) "In the avl tree TREE insert DATA. Return DATA." - (elib-avl-do-enter (elib-avl-cmpfun tree) - (elib-avl-dummyroot tree) - 0 - data) + (elib-avl-dummyroot tree) + 0 + data) data) - (defun avltree-delete (tree data) "From the avl tree TREE, delete DATA. Return the element in TREE which matched DATA, nil if no element matched." - (elib-avl-do-delete (elib-avl-cmpfun tree) - (elib-avl-dummyroot tree) - 0 - data)) - + (elib-avl-dummyroot tree) + 0 + data)) (defun avltree-member (tree data) "Return the element in the avl tree TREE which matches DATA. @@ -624,90 +490,79 @@ Matching uses the compare function previously specified in `avltree-create' when TREE was created. If there is no such element in the tree, the value is nil." - (let ((node (elib-avl-root tree)) - (compare-function (elib-avl-cmpfun tree)) - found) + (compare-function (elib-avl-cmpfun tree)) + found) (while (and node - (not found)) + (not found)) (cond ((funcall compare-function data (elib-node-data node)) - (setq node (elib-node-left node))) + (setq node (elib-node-left node))) ((funcall compare-function (elib-node-data node) data) - (setq node (elib-node-right node))) + (setq node (elib-node-right node))) (t - (setq found t)))) + (setq found t)))) (if node - (elib-node-data node) + (elib-node-data node) nil))) - - (defun avltree-map (__map-function__ tree) "Apply MAP-FUNCTION to all elements in the avl tree TREE." (elib-avl-mapc (function (lambda (node) - (elib-node-set-data node - (funcall __map-function__ - (elib-node-data node))))) + (elib-node-set-data node + (funcall __map-function__ + (elib-node-data node))))) (elib-avl-root tree))) - - (defun avltree-first (tree) "Return the first element in TREE, or nil if TREE is empty." - (let ((node (elib-avl-root tree))) (if node - (progn - (while (elib-node-left node) - (setq node (elib-node-left node))) - (elib-node-data node)) + (progn + (while (elib-node-left node) + (setq node (elib-node-left node))) + (elib-node-data node)) nil))) - (defun avltree-last (tree) "Return the last element in TREE, or nil if TREE is empty." (let ((node (elib-avl-root tree))) (if node - (progn - (while (elib-node-right node) - (setq node (elib-node-right node))) - (elib-node-data node)) + (progn + (while (elib-node-right node) + (setq node (elib-node-right node))) + (elib-node-data node)) nil))) - (defun avltree-copy (tree) "Return a copy of the avl tree TREE." (let ((new-tree (avltree-create - (elib-avl-cmpfun tree)))) + (elib-avl-cmpfun tree)))) (elib-node-set-left (elib-avl-dummyroot new-tree) - (elib-avl-do-copy (elib-avl-root tree))) + (elib-avl-do-copy (elib-avl-root tree))) new-tree)) - (defun avltree-flatten (tree) "Return a sorted list containing all elements of TREE." (nreverse (let ((treelist nil)) (elib-avl-mapc (function (lambda (node) - (setq treelist (cons (elib-node-data node) - treelist)))) - (elib-avl-root tree)) + (setq treelist (cons (elib-node-data node) + treelist)))) + (elib-avl-root tree)) treelist))) - (defun avltree-size (tree) "Return the number of elements in TREE." (let ((treesize 0)) (elib-avl-mapc (function (lambda (data) - (setq treesize (1+ treesize)) - data)) - (elib-avl-root tree)) + (setq treesize (1+ treesize)) + data)) + (elib-avl-root tree)) treesize)) - (defun avltree-clear (tree) "Clear the avl tree TREE." (elib-node-set-left (elib-avl-dummyroot tree) nil)) -- cgit v1.2.3 From fb5da2db3e0b8d52337682ce59f397a5ae88869f Mon Sep 17 00:00:00 2001 From: Thien-Thi Nguyen Date: Mon, 27 Aug 2007 01:29:41 +0000 Subject: Move provide form to end; nfc. --- lisp/emacs-lisp/avl-tree.el | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) (limited to 'lisp/emacs-lisp/avl-tree.el') diff --git a/lisp/emacs-lisp/avl-tree.el b/lisp/emacs-lisp/avl-tree.el index 75ec86c0d0e..604147f618e 100644 --- a/lisp/emacs-lisp/avl-tree.el +++ b/lisp/emacs-lisp/avl-tree.el @@ -101,7 +101,6 @@ (defun elib-stack-create () (list)) (defmacro elib-stack-push (stack object) `(push ,object ,stack)) (defmacro elib-stack-pop (stack) `(pop ,stack)) -(provide 'avl-tree) ;;; ================================================================ ;;; Functions and macros handling an AVL tree node. @@ -567,4 +566,6 @@ If there is no such element in the tree, the value is nil." "Clear the avl tree TREE." (elib-node-set-left (elib-avl-dummyroot tree) nil)) +(provide 'avl-tree) + ;;; avltree.el ends here -- cgit v1.2.3 From 25e32569d41466ef97acf433a062c5d02a3601cf Mon Sep 17 00:00:00 2001 From: Thien-Thi Nguyen Date: Mon, 27 Aug 2007 01:35:41 +0000 Subject: Don't require `cl'. (elib-stack-create, elib-stack-push, elib-stack-pop): Delete funcs. (elib-avl-mapc): Use `nil' for new stack, and `push' and `pop' directly. --- lisp/emacs-lisp/avl-tree.el | 13 ++++--------- 1 file changed, 4 insertions(+), 9 deletions(-) (limited to 'lisp/emacs-lisp/avl-tree.el') diff --git a/lisp/emacs-lisp/avl-tree.el b/lisp/emacs-lisp/avl-tree.el index 604147f618e..b68ebc47de3 100644 --- a/lisp/emacs-lisp/avl-tree.el +++ b/lisp/emacs-lisp/avl-tree.el @@ -97,11 +97,6 @@ ;; NEWVAL is new value of the branch." (` (aset (, node) (, branch) (, newval)))) -(eval-when-compile (require 'cl)) -(defun elib-stack-create () (list)) -(defmacro elib-stack-push (stack object) `(push ,object ,stack)) -(defmacro elib-stack-pop (stack) `(pop ,stack)) - ;;; ================================================================ ;;; Functions and macros handling an AVL tree node. @@ -413,15 +408,15 @@ ;; Note: MAP-FUNCTION is applied to the node and not to the data itself. ;; INTERNAL USE ONLY. (let ((node root) - (stack (elib-stack-create)) + (stack nil) (go-left t)) - (elib-stack-push stack nil) + (push nil stack) (while node (if (and go-left (elib-node-left node)) ;; Do the left subtree first. (progn - (elib-stack-push stack node) + (push node stack) (setq node (elib-node-left node))) ;; Apply the function... (funcall map-function node) @@ -429,7 +424,7 @@ (if (elib-node-right node) (setq node (elib-node-right node) go-left t) - (setq node (elib-stack-pop stack) + (setq node (pop stack) go-left nil)))))) (defun elib-avl-do-copy (root) -- cgit v1.2.3 From 37840380aa33f0aa3f4a5bec772586a6e72741c4 Mon Sep 17 00:00:00 2001 From: Miles Bader Date: Mon, 27 Aug 2007 01:42:03 +0000 Subject: Add arch tagline --- etc/refcards/pdflayout.sty | 2 ++ lisp/emacs-lisp/avl-tree.el | 1 + 2 files changed, 3 insertions(+) (limited to 'lisp/emacs-lisp/avl-tree.el') diff --git a/etc/refcards/pdflayout.sty b/etc/refcards/pdflayout.sty index 12b31239bb8..187ffee867b 100644 --- a/etc/refcards/pdflayout.sty +++ b/etc/refcards/pdflayout.sty @@ -45,3 +45,5 @@ \fi % archtag: 63c938a5-cc78-4964-962d-603c90d34afc + +% arch-tag: 3464d27c-1439-473a-bc47-a7c501e8c156 diff --git a/lisp/emacs-lisp/avl-tree.el b/lisp/emacs-lisp/avl-tree.el index b68ebc47de3..c0408e2dbd2 100644 --- a/lisp/emacs-lisp/avl-tree.el +++ b/lisp/emacs-lisp/avl-tree.el @@ -563,4 +563,5 @@ If there is no such element in the tree, the value is nil." (provide 'avl-tree) +;; arch-tag: 47e26701-43c9-4222-bd79-739eac6357a9 ;;; avltree.el ends here -- cgit v1.2.3 From 85718043eeddf211a3e5b18cc7d31d9a2dd325ad Mon Sep 17 00:00:00 2001 From: Thien-Thi Nguyen Date: Mon, 27 Aug 2007 01:44:37 +0000 Subject: Do s/avltree/avl-tree/g. Resulting changed function names: avl-tree-create, avl-tree-p, avl-tree-compare-function, avl-tree-empty, avl-tree-enter, avl-tree-delete, avl-tree-member, avl-tree-map, avl-tree-first, avl-tree-last, avl-tree-copy, avl-tree-flatten, avl-tree-size, avl-tree-clear. Make the symbol used for avl-tree-p `AVL-TREE', as well. --- lisp/emacs-lisp/avl-tree.el | 40 ++++++++++++++++++++-------------------- 1 file changed, 20 insertions(+), 20 deletions(-) (limited to 'lisp/emacs-lisp/avl-tree.el') diff --git a/lisp/emacs-lisp/avl-tree.el b/lisp/emacs-lisp/avl-tree.el index c0408e2dbd2..58708f77a14 100644 --- a/lisp/emacs-lisp/avl-tree.el +++ b/lisp/emacs-lisp/avl-tree.el @@ -43,7 +43,7 @@ ;; * Comments from avltree.el ;; An AVL tree is a nearly-perfect balanced binary tree. A tree ;; consists of two cons cells, the first one holding the tag -;; 'AVLTREE in the car cell, and the second one having the tree +;; 'AVL-TREE in the car cell, and the second one having the tree ;; in the car and the compare function in the cdr cell. The tree has ;; a dummy node as its root with the real tree in the left pointer. ;; @@ -441,27 +441,27 @@ ;;; ================================================================ ;;; The public functions which operate on AVL trees. -(defun avltree-create (compare-function) +(defun avl-tree-create (compare-function) "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." - (cons 'AVLTREE + (cons 'AVL-TREE (cons (elib-avl-node-create nil nil nil 0) compare-function))) -(defun avltree-p (obj) +(defun avl-tree-p (obj) "Return t if OBJ is an avl tree, nil otherwise." - (eq (car-safe obj) 'AVLTREE)) + (eq (car-safe obj) 'AVL-TREE)) -(defun avltree-compare-function (tree) +(defun avl-tree-compare-function (tree) "Return the comparision function for the avl tree TREE." (elib-avl-cmpfun tree)) -(defun avltree-empty (tree) +(defun avl-tree-empty (tree) "Return t if TREE is emtpy, otherwise return nil." (null (elib-avl-root tree))) -(defun avltree-enter (tree data) +(defun avl-tree-enter (tree data) "In the avl tree TREE insert DATA. Return DATA." (elib-avl-do-enter (elib-avl-cmpfun tree) @@ -470,7 +470,7 @@ Return DATA." data) data) -(defun avltree-delete (tree 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." (elib-avl-do-delete (elib-avl-cmpfun tree) @@ -478,9 +478,9 @@ Return the element in TREE which matched DATA, nil if no element matched." 0 data)) -(defun avltree-member (tree data) +(defun avl-tree-member (tree data) "Return the element in the avl tree TREE which matches DATA. -Matching uses the compare function previously specified in `avltree-create' +Matching uses the compare function previously specified in `avl-tree-create' when TREE was created. If there is no such element in the tree, the value is nil." @@ -501,7 +501,7 @@ If there is no such element in the tree, the value is nil." (elib-node-data node) nil))) -(defun avltree-map (__map-function__ tree) +(defun avl-tree-map (__map-function__ tree) "Apply MAP-FUNCTION to all elements in the avl tree TREE." (elib-avl-mapc (function (lambda (node) @@ -510,7 +510,7 @@ If there is no such element in the tree, the value is nil." (elib-node-data node))))) (elib-avl-root tree))) -(defun avltree-first (tree) +(defun avl-tree-first (tree) "Return the first element in TREE, or nil if TREE is empty." (let ((node (elib-avl-root tree))) (if node @@ -520,7 +520,7 @@ If there is no such element in the tree, the value is nil." (elib-node-data node)) nil))) -(defun avltree-last (tree) +(defun avl-tree-last (tree) "Return the last element in TREE, or nil if TREE is empty." (let ((node (elib-avl-root tree))) (if node @@ -530,15 +530,15 @@ If there is no such element in the tree, the value is nil." (elib-node-data node)) nil))) -(defun avltree-copy (tree) +(defun avl-tree-copy (tree) "Return a copy of the avl tree TREE." - (let ((new-tree (avltree-create + (let ((new-tree (avl-tree-create (elib-avl-cmpfun tree)))) (elib-node-set-left (elib-avl-dummyroot new-tree) (elib-avl-do-copy (elib-avl-root tree))) new-tree)) -(defun avltree-flatten (tree) +(defun avl-tree-flatten (tree) "Return a sorted list containing all elements of TREE." (nreverse (let ((treelist nil)) @@ -548,7 +548,7 @@ If there is no such element in the tree, the value is nil." (elib-avl-root tree)) treelist))) -(defun avltree-size (tree) +(defun avl-tree-size (tree) "Return the number of elements in TREE." (let ((treesize 0)) (elib-avl-mapc (function (lambda (data) @@ -557,11 +557,11 @@ If there is no such element in the tree, the value is nil." (elib-avl-root tree)) treesize)) -(defun avltree-clear (tree) +(defun avl-tree-clear (tree) "Clear the avl tree TREE." (elib-node-set-left (elib-avl-dummyroot tree) nil)) (provide 'avl-tree) ;; arch-tag: 47e26701-43c9-4222-bd79-739eac6357a9 -;;; avltree.el ends here +;;; avl-tree.el ends here -- cgit v1.2.3 From 923135482e88d3a9296270856e6d9f5e41dd00f8 Mon Sep 17 00:00:00 2001 From: Thien-Thi Nguyen Date: Mon, 27 Aug 2007 02:00:45 +0000 Subject: Reduce nesting: Use modern backquote syntax. --- lisp/emacs-lisp/avl-tree.el | 30 +++++++++++++++--------------- 1 file changed, 15 insertions(+), 15 deletions(-) (limited to 'lisp/emacs-lisp/avl-tree.el') diff --git a/lisp/emacs-lisp/avl-tree.el b/lisp/emacs-lisp/avl-tree.el index 58708f77a14..86e8c75d6b2 100644 --- a/lisp/emacs-lisp/avl-tree.el +++ b/lisp/emacs-lisp/avl-tree.el @@ -56,38 +56,38 @@ (defmacro elib-node-create (left right data) ;; Create a tree node from LEFT, RIGHT and DATA. - (` (vector (, left) (, right) (, data)))) + `(vector ,left ,right ,data)) (defmacro elib-node-left (node) ;; Return the left pointer of NODE. - (` (aref (, node) 0))) + `(aref ,node 0)) (defmacro elib-node-right (node) ;; Return the right pointer of NODE. - (` (aref (, node) 1))) + `(aref ,node 1)) (defmacro elib-node-data (node) ;; Return the data of NODE. - (` (aref (, node) 2))) + `(aref ,node 2)) (defmacro elib-node-set-left (node newleft) ;; Set the left pointer of NODE to NEWLEFT. - (` (aset (, node) 0 (, newleft)))) + `(aset ,node 0 ,newleft)) (defmacro elib-node-set-right (node newright) ;; Set the right pointer of NODE to NEWRIGHT. - (` (aset (, node) 1 (, newright)))) + `(aset ,node 1 ,newright)) (defmacro elib-node-set-data (node newdata) ;; Set the data of NODE to NEWDATA. - (` (aset (, node) 2 (, newdata)))) + `(aset ,node 2 ,newdata)) (defmacro elib-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)))) + `(aref ,node ,branch)) (defmacro elib-node-set-branch (node branch newval) ;; Set value of a branch of a node. @@ -95,22 +95,22 @@ ;; NODE is the node, and BRANCH is the branch. ;; 0 for left pointer, 1 for the right pointer and 2 for the data. ;; NEWVAL is new value of the branch." - (` (aset (, node) (, branch) (, newval)))) + `(aset ,node ,branch ,newval)) ;;; ================================================================ ;;; Functions and macros handling an AVL tree node. (defmacro elib-avl-node-create (left right data balance) ;; Create and return an avl-tree node. - (` (vector (, left) (, right) (, data) (, balance)))) + `(vector ,left ,right ,data ,balance)) (defmacro elib-avl-node-balance (node) ;; Return the balance field of a node. - (` (aref (, node) 3))) + `(aref ,node 3)) (defmacro elib-avl-node-set-balance (node newbal) ;; Set the balance field of a node. - (` (aset (, node) 3 (, newbal)))) + `(aset ,node 3 ,newbal)) ;;; ================================================================ @@ -122,15 +122,15 @@ (defmacro elib-avl-root (tree) ;; Return the root node for an avl-tree. INTERNAL USE ONLY. - (` (elib-node-left (car (cdr (, tree)))))) + `(elib-node-left (car (cdr ,tree)))) (defmacro elib-avl-dummyroot (tree) ;; Return the dummy node of an avl-tree. INTERNAL USE ONLY. - (` (car (cdr (, tree))))) + `(car (cdr ,tree))) (defmacro elib-avl-cmpfun (tree) ;; Return the compare function of AVL tree TREE. INTERNAL USE ONLY. - (` (cdr (cdr (, tree))))) + `(cdr (cdr ,tree))) ;; ---------------------------------------------------------------- ;; Deleting data -- cgit v1.2.3 From 329dfe6ae7cb3813599290da97f84ee68340e20f Mon Sep 17 00:00:00 2001 From: Thien-Thi Nguyen Date: Mon, 27 Aug 2007 02:05:22 +0000 Subject: (elib-node-create): Delete unused macro. --- lisp/emacs-lisp/avl-tree.el | 4 ---- 1 file changed, 4 deletions(-) (limited to 'lisp/emacs-lisp/avl-tree.el') diff --git a/lisp/emacs-lisp/avl-tree.el b/lisp/emacs-lisp/avl-tree.el index 86e8c75d6b2..f5d6abc2226 100644 --- a/lisp/emacs-lisp/avl-tree.el +++ b/lisp/emacs-lisp/avl-tree.el @@ -54,10 +54,6 @@ ;;; Code: -(defmacro elib-node-create (left right data) - ;; Create a tree node from LEFT, RIGHT and DATA. - `(vector ,left ,right ,data)) - (defmacro elib-node-left (node) ;; Return the left pointer of NODE. `(aref ,node 0)) -- cgit v1.2.3 From dfd4af17e447929c26534bc232333eec7b74a6b4 Mon Sep 17 00:00:00 2001 From: Thien-Thi Nguyen Date: Mon, 27 Aug 2007 02:11:12 +0000 Subject: Do s/elib-avl-node/avl-tree-node/g. Resulting changed macro names: avl-tree-node-create, avl-tree-node-balance, avl-tree-node-set-balance. --- lisp/emacs-lisp/avl-tree.el | 122 ++++++++++++++++++++++---------------------- 1 file changed, 61 insertions(+), 61 deletions(-) (limited to 'lisp/emacs-lisp/avl-tree.el') diff --git a/lisp/emacs-lisp/avl-tree.el b/lisp/emacs-lisp/avl-tree.el index f5d6abc2226..a86fdc60f57 100644 --- a/lisp/emacs-lisp/avl-tree.el +++ b/lisp/emacs-lisp/avl-tree.el @@ -96,15 +96,15 @@ ;;; ================================================================ ;;; Functions and macros handling an AVL tree node. -(defmacro elib-avl-node-create (left right data balance) +(defmacro avl-tree-node-create (left right data balance) ;; Create and return an avl-tree node. `(vector ,left ,right ,data ,balance)) -(defmacro elib-avl-node-balance (node) +(defmacro avl-tree-node-balance (node) ;; Return the balance field of a node. `(aref ,node 3)) -(defmacro elib-avl-node-set-balance (node newbal) +(defmacro avl-tree-node-set-balance (node newbal) ;; Set the balance field of a node. `(aset ,node 3 ,newbal)) @@ -140,18 +140,18 @@ b2 result) (cond - ((< (elib-avl-node-balance br) 0) - (elib-avl-node-set-balance br 0) + ((< (avl-tree-node-balance br) 0) + (avl-tree-node-set-balance br 0) t) - ((= (elib-avl-node-balance br) 0) - (elib-avl-node-set-balance br +1) + ((= (avl-tree-node-balance br) 0) + (avl-tree-node-set-balance br +1) nil) (t ;; Rebalance. (setq p1 (elib-node-right br) - b1 (elib-avl-node-balance p1)) + b1 (avl-tree-node-balance p1)) (if (>= b1 0) ;; Single RR rotation. (progn @@ -159,30 +159,30 @@ (elib-node-set-left p1 br) (if (= 0 b1) (progn - (elib-avl-node-set-balance br +1) - (elib-avl-node-set-balance p1 -1) + (avl-tree-node-set-balance br +1) + (avl-tree-node-set-balance p1 -1) (setq result nil)) - (elib-avl-node-set-balance br 0) - (elib-avl-node-set-balance p1 0) + (avl-tree-node-set-balance br 0) + (avl-tree-node-set-balance p1 0) (setq result t)) (elib-node-set-branch node branch p1) result) ;; Double RL rotation. (setq p2 (elib-node-left p1) - b2 (elib-avl-node-balance p2)) + 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) (if (> b2 0) - (elib-avl-node-set-balance br -1) - (elib-avl-node-set-balance br 0)) + (avl-tree-node-set-balance br -1) + (avl-tree-node-set-balance br 0)) (if (< b2 0) - (elib-avl-node-set-balance p1 +1) - (elib-avl-node-set-balance p1 0)) + (avl-tree-node-set-balance p1 +1) + (avl-tree-node-set-balance p1 0)) (elib-node-set-branch node branch p2) - (elib-avl-node-set-balance p2 0) + (avl-tree-node-set-balance p2 0) t))))) (defun elib-avl-del-balance2 (node branch) @@ -193,18 +193,18 @@ b2 result) (cond - ((> (elib-avl-node-balance br) 0) - (elib-avl-node-set-balance br 0) + ((> (avl-tree-node-balance br) 0) + (avl-tree-node-set-balance br 0) t) - ((= (elib-avl-node-balance br) 0) - (elib-avl-node-set-balance br -1) + ((= (avl-tree-node-balance br) 0) + (avl-tree-node-set-balance br -1) nil) (t ;; Rebalance. (setq p1 (elib-node-left br) - b1 (elib-avl-node-balance p1)) + b1 (avl-tree-node-balance p1)) (if (<= b1 0) ;; Single LL rotation. (progn @@ -212,30 +212,30 @@ (elib-node-set-right p1 br) (if (= 0 b1) (progn - (elib-avl-node-set-balance br -1) - (elib-avl-node-set-balance p1 +1) + (avl-tree-node-set-balance br -1) + (avl-tree-node-set-balance p1 +1) (setq result nil)) - (elib-avl-node-set-balance br 0) - (elib-avl-node-set-balance p1 0) + (avl-tree-node-set-balance br 0) + (avl-tree-node-set-balance p1 0) (setq result t)) (elib-node-set-branch node branch p1) result) ;; Double LR rotation. (setq p2 (elib-node-right p1) - b2 (elib-avl-node-balance p2)) + 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) (if (< b2 0) - (elib-avl-node-set-balance br +1) - (elib-avl-node-set-balance br 0)) + (avl-tree-node-set-balance br +1) + (avl-tree-node-set-balance br 0)) (if (> b2 0) - (elib-avl-node-set-balance p1 -1) - (elib-avl-node-set-balance p1 0)) + (avl-tree-node-set-balance p1 -1) + (avl-tree-node-set-balance p1 0)) (elib-node-set-branch node branch p2) - (elib-avl-node-set-balance p2 0) + (avl-tree-node-set-balance p2 0) t))))) (defun elib-avl-do-del-internal (node branch q) @@ -290,40 +290,40 @@ b2 result) (cond - ((< (elib-avl-node-balance br) 0) - (elib-avl-node-set-balance br 0) + ((< (avl-tree-node-balance br) 0) + (avl-tree-node-set-balance br 0) nil) - ((= (elib-avl-node-balance br) 0) - (elib-avl-node-set-balance br +1) + ((= (avl-tree-node-balance br) 0) + (avl-tree-node-set-balance br +1) t) (t ;; Tree has grown => Rebalance. (setq p1 (elib-node-right br)) - (if (> (elib-avl-node-balance p1) 0) + (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) - (elib-avl-node-set-balance br 0) + (avl-tree-node-set-balance br 0) (elib-node-set-branch node branch p1)) ;; Double RL rotation. (setq p2 (elib-node-left p1) - b2 (elib-avl-node-balance p2)) + 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) (if (> b2 0) - (elib-avl-node-set-balance br -1) - (elib-avl-node-set-balance br 0)) + (avl-tree-node-set-balance br -1) + (avl-tree-node-set-balance br 0)) (if (< b2 0) - (elib-avl-node-set-balance p1 +1) - (elib-avl-node-set-balance p1 0)) + (avl-tree-node-set-balance p1 +1) + (avl-tree-node-set-balance p1 0)) (elib-node-set-branch node branch p2)) - (elib-avl-node-set-balance (elib-node-branch node branch) 0) + (avl-tree-node-set-balance (elib-node-branch node branch) 0) nil)))) (defun elib-avl-enter-balance2 (node branch) @@ -333,40 +333,40 @@ p2 b2) (cond - ((> (elib-avl-node-balance br) 0) - (elib-avl-node-set-balance br 0) + ((> (avl-tree-node-balance br) 0) + (avl-tree-node-set-balance br 0) nil) - ((= (elib-avl-node-balance br) 0) - (elib-avl-node-set-balance br -1) + ((= (avl-tree-node-balance br) 0) + (avl-tree-node-set-balance br -1) t) (t ;; Balance was -1 => Rebalance. (setq p1 (elib-node-left br)) - (if (< (elib-avl-node-balance p1) 0) + (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) - (elib-avl-node-set-balance br 0) + (avl-tree-node-set-balance br 0) (elib-node-set-branch node branch p1)) ;; Double LR rotation. (setq p2 (elib-node-right p1) - b2 (elib-avl-node-balance p2)) + 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) (if (< b2 0) - (elib-avl-node-set-balance br +1) - (elib-avl-node-set-balance br 0)) + (avl-tree-node-set-balance br +1) + (avl-tree-node-set-balance br 0)) (if (> b2 0) - (elib-avl-node-set-balance p1 -1) - (elib-avl-node-set-balance p1 0)) + (avl-tree-node-set-balance p1 -1) + (avl-tree-node-set-balance p1 0)) (elib-node-set-branch node branch p2)) - (elib-avl-node-set-balance (elib-node-branch node branch) 0) + (avl-tree-node-set-balance (elib-node-branch node branch) 0) nil)))) (defun elib-avl-do-enter (cmpfun root branch data) @@ -376,7 +376,7 @@ ((null br) ;; Data not in tree, insert it. (elib-node-set-branch root branch - (elib-avl-node-create nil nil data 0)) + (avl-tree-node-create nil nil data 0)) t) ((funcall cmpfun data (elib-node-data br)) @@ -428,10 +428,10 @@ ;; Highly recursive. INTERNAL USE ONLY. (if (null root) nil - (elib-avl-node-create (elib-avl-do-copy (elib-node-left root)) + (avl-tree-node-create (elib-avl-do-copy (elib-node-left root)) (elib-avl-do-copy (elib-node-right root)) (elib-node-data root) - (elib-avl-node-balance root)))) + (avl-tree-node-balance root)))) ;;; ================================================================ @@ -442,7 +442,7 @@ 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." (cons 'AVL-TREE - (cons (elib-avl-node-create nil nil nil 0) + (cons (avl-tree-node-create nil nil nil 0) compare-function))) (defun avl-tree-p (obj) -- cgit v1.2.3 From 5afb301bee960583ddd66044367ac08155ff9be8 Mon Sep 17 00:00:00 2001 From: Thien-Thi Nguyen Date: Mon, 27 Aug 2007 02:22:57 +0000 Subject: Do s/elib-avl-/avl-tree-/g. Resulting changed macro and function names: avl-tree-root, avl-tree-dummyroot, avl-tree-cmpfun, avl-tree-del-balance1, avl-tree-do-del-internal, avl-tree-del-balance2, avl-tree-do-delete, avl-tree-enter-balance1, avl-tree-enter-balance2, avl-tree-do-enter, avl-tree-mapc, avl-tree-do-copy. --- lisp/emacs-lisp/avl-tree.el | 96 ++++++++++++++++++++++----------------------- 1 file changed, 46 insertions(+), 50 deletions(-) (limited to 'lisp/emacs-lisp/avl-tree.el') diff --git a/lisp/emacs-lisp/avl-tree.el b/lisp/emacs-lisp/avl-tree.el index a86fdc60f57..63e88ac21f9 100644 --- a/lisp/emacs-lisp/avl-tree.el +++ b/lisp/emacs-lisp/avl-tree.el @@ -112,26 +112,22 @@ ;;; ================================================================ ;;; Internal functions for use in the AVL tree package -;;; -;;; The functions and macros in this section all start with `elib-avl-'. -;;; - -(defmacro elib-avl-root (tree) +(defmacro avl-tree-root (tree) ;; Return the root node for an avl-tree. INTERNAL USE ONLY. `(elib-node-left (car (cdr ,tree)))) -(defmacro elib-avl-dummyroot (tree) +(defmacro avl-tree-dummyroot (tree) ;; Return the dummy node of an avl-tree. INTERNAL USE ONLY. `(car (cdr ,tree))) -(defmacro elib-avl-cmpfun (tree) +(defmacro avl-tree-cmpfun (tree) ;; Return the compare function of AVL tree TREE. INTERNAL USE ONLY. `(cdr (cdr ,tree))) ;; ---------------------------------------------------------------- ;; Deleting data -(defun elib-avl-del-balance1 (node branch) +(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)) p1 @@ -185,7 +181,7 @@ (avl-tree-node-set-balance p2 0) t))))) -(defun elib-avl-del-balance2 (node branch) +(defun avl-tree-del-balance2 (node branch) (let* ((br (elib-node-branch node branch)) p1 b1 @@ -238,18 +234,18 @@ (avl-tree-node-set-balance p2 0) t))))) -(defun elib-avl-do-del-internal (node branch q) +(defun avl-tree-do-del-internal (node branch q) (let* ((br (elib-node-branch node branch))) (if (elib-node-right br) - (if (elib-avl-do-del-internal br +1 q) - (elib-avl-del-balance2 node branch)) + (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)) t))) -(defun elib-avl-do-delete (cmpfun root branch data) +(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))) (cond @@ -257,12 +253,12 @@ nil) ((funcall cmpfun data (elib-node-data br)) - (if (elib-avl-do-delete cmpfun br 0 data) - (elib-avl-del-balance1 root branch))) + (if (avl-tree-do-delete cmpfun br 0 data) + (avl-tree-del-balance1 root branch))) ((funcall cmpfun (elib-node-data br) data) - (if (elib-avl-do-delete cmpfun br 1 data) - (elib-avl-del-balance2 root branch))) + (if (avl-tree-do-delete cmpfun br 1 data) + (avl-tree-del-balance2 root branch))) (t ;; Found it. Let's delete it. @@ -276,13 +272,13 @@ t) (t - (if (elib-avl-do-del-internal br 0 br) - (elib-avl-del-balance1 root branch)))))))) + (if (avl-tree-do-del-internal br 0 br) + (avl-tree-del-balance1 root branch)))))))) ;; ---------------------------------------------------------------- ;; Entering data -(defun elib-avl-enter-balance1 (node branch) +(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)) p1 @@ -326,7 +322,7 @@ (avl-tree-node-set-balance (elib-node-branch node branch) 0) nil)))) -(defun elib-avl-enter-balance2 (node branch) +(defun avl-tree-enter-balance2 (node branch) ;; Return t if the tree has grown. (let* ((br (elib-node-branch node branch)) p1 @@ -369,7 +365,7 @@ (avl-tree-node-set-balance (elib-node-branch node branch) 0) nil)))) -(defun elib-avl-do-enter (cmpfun root branch data) +(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))) (cond @@ -380,16 +376,16 @@ t) ((funcall cmpfun data (elib-node-data br)) - (and (elib-avl-do-enter cmpfun + (and (avl-tree-do-enter cmpfun br 0 data) - (elib-avl-enter-balance2 root branch))) + (avl-tree-enter-balance2 root branch))) ((funcall cmpfun (elib-node-data br) data) - (and (elib-avl-do-enter cmpfun + (and (avl-tree-do-enter cmpfun br 1 data) - (elib-avl-enter-balance1 root branch))) + (avl-tree-enter-balance1 root branch))) (t (elib-node-set-data br data) @@ -397,7 +393,7 @@ ;; ---------------------------------------------------------------- -(defun elib-avl-mapc (map-function root) +(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. ;; @@ -423,13 +419,13 @@ (setq node (pop stack) go-left nil)))))) -(defun elib-avl-do-copy (root) +(defun avl-tree-do-copy (root) ;; Copy the tree with ROOT as root. ;; Highly recursive. INTERNAL USE ONLY. (if (null root) nil - (avl-tree-node-create (elib-avl-do-copy (elib-node-left root)) - (elib-avl-do-copy (elib-node-right root)) + (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-balance root)))) @@ -451,17 +447,17 @@ and returns non-nil if A is less than B, and nil otherwise." (defun avl-tree-compare-function (tree) "Return the comparision function for the avl tree TREE." - (elib-avl-cmpfun tree)) + (avl-tree-cmpfun tree)) (defun avl-tree-empty (tree) "Return t if TREE is emtpy, otherwise return nil." - (null (elib-avl-root tree))) + (null (avl-tree-root tree))) (defun avl-tree-enter (tree data) "In the avl tree TREE insert DATA. Return DATA." - (elib-avl-do-enter (elib-avl-cmpfun tree) - (elib-avl-dummyroot tree) + (avl-tree-do-enter (avl-tree-cmpfun tree) + (avl-tree-dummyroot tree) 0 data) data) @@ -469,8 +465,8 @@ Return 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." - (elib-avl-do-delete (elib-avl-cmpfun tree) - (elib-avl-dummyroot tree) + (avl-tree-do-delete (avl-tree-cmpfun tree) + (avl-tree-dummyroot tree) 0 data)) @@ -480,8 +476,8 @@ Matching uses the compare function previously specified in `avl-tree-create' when TREE was created. If there is no such element in the tree, the value is nil." - (let ((node (elib-avl-root tree)) - (compare-function (elib-avl-cmpfun tree)) + (let ((node (avl-tree-root tree)) + (compare-function (avl-tree-cmpfun tree)) found) (while (and node (not found)) @@ -499,16 +495,16 @@ If there is no such element in the tree, the value is nil." (defun avl-tree-map (__map-function__ tree) "Apply MAP-FUNCTION to all elements in the avl tree TREE." - (elib-avl-mapc + (avl-tree-mapc (function (lambda (node) (elib-node-set-data node (funcall __map-function__ (elib-node-data node))))) - (elib-avl-root tree))) + (avl-tree-root tree))) (defun avl-tree-first (tree) "Return the first element in TREE, or nil if TREE is empty." - (let ((node (elib-avl-root tree))) + (let ((node (avl-tree-root tree))) (if node (progn (while (elib-node-left node) @@ -518,7 +514,7 @@ If there is no such element in the tree, the value is nil." (defun avl-tree-last (tree) "Return the last element in TREE, or nil if TREE is empty." - (let ((node (elib-avl-root tree))) + (let ((node (avl-tree-root tree))) (if node (progn (while (elib-node-right node) @@ -529,33 +525,33 @@ If there is no such element in the tree, the value is nil." (defun avl-tree-copy (tree) "Return a copy of the avl tree TREE." (let ((new-tree (avl-tree-create - (elib-avl-cmpfun tree)))) - (elib-node-set-left (elib-avl-dummyroot new-tree) - (elib-avl-do-copy (elib-avl-root tree))) + (avl-tree-cmpfun tree)))) + (elib-node-set-left (avl-tree-dummyroot new-tree) + (avl-tree-do-copy (avl-tree-root tree))) new-tree)) (defun avl-tree-flatten (tree) "Return a sorted list containing all elements of TREE." (nreverse (let ((treelist nil)) - (elib-avl-mapc (function (lambda (node) + (avl-tree-mapc (function (lambda (node) (setq treelist (cons (elib-node-data node) treelist)))) - (elib-avl-root tree)) + (avl-tree-root tree)) treelist))) (defun avl-tree-size (tree) "Return the number of elements in TREE." (let ((treesize 0)) - (elib-avl-mapc (function (lambda (data) + (avl-tree-mapc (function (lambda (data) (setq treesize (1+ treesize)) data)) - (elib-avl-root tree)) + (avl-tree-root tree)) treesize)) (defun avl-tree-clear (tree) "Clear the avl tree TREE." - (elib-node-set-left (elib-avl-dummyroot tree) nil)) + (elib-node-set-left (avl-tree-dummyroot tree) nil)) (provide 'avl-tree) -- cgit v1.2.3 From bdf0a828423d27d8a0ea956da4eda1754631dc3b Mon Sep 17 00:00:00 2001 From: Thien-Thi Nguyen Date: Mon, 27 Aug 2007 02:31:23 +0000 Subject: 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. --- lisp/emacs-lisp/avl-tree.el | 190 ++++++++++++++++++++++---------------------- 1 file changed, 95 insertions(+), 95 deletions(-) (limited to 'lisp/emacs-lisp/avl-tree.el') diff --git a/lisp/emacs-lisp/avl-tree.el b/lisp/emacs-lisp/avl-tree.el index 63e88ac21f9..0e37e718250 100644 --- a/lisp/emacs-lisp/avl-tree.el +++ b/lisp/emacs-lisp/avl-tree.el @@ -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 @@ If there is no such element in the tree, the value is nil." (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 @@ If there is no such element in the tree, the value is nil." (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 @@ If there is no such element in the tree, the value is nil." (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 @@ If there is no such element in the tree, the value is nil." (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 @@ If there is no such element in the tree, the value is nil." (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) -- cgit v1.2.3 From 5fa11cc28db07e1ac0c06ad10fc45ed7caddb315 Mon Sep 17 00:00:00 2001 From: Thien-Thi Nguyen Date: Mon, 27 Aug 2007 02:40:25 +0000 Subject: Move things around; munge whitespace, indentation; nfc. --- lisp/emacs-lisp/avl-tree.el | 89 ++++++++++++++++++--------------------------- 1 file changed, 36 insertions(+), 53 deletions(-) (limited to 'lisp/emacs-lisp/avl-tree.el') diff --git a/lisp/emacs-lisp/avl-tree.el b/lisp/emacs-lisp/avl-tree.el index 0e37e718250..7dd4d18da7c 100644 --- a/lisp/emacs-lisp/avl-tree.el +++ b/lisp/emacs-lisp/avl-tree.el @@ -54,6 +54,13 @@ ;;; Code: +;;; ================================================================ +;;; Functions and macros handling an AVL tree node. + +(defmacro avl-tree-node-create (left right data balance) + ;; Create and return an avl-tree node. + `(vector ,left ,right ,data ,balance)) + (defmacro avl-tree-node-left (node) ;; Return the left pointer of NODE. `(aref ,node 0)) @@ -93,13 +100,6 @@ ;; NEWVAL is new value of the branch." `(aset ,node ,branch ,newval)) -;;; ================================================================ -;;; Functions and macros handling an AVL tree node. - -(defmacro avl-tree-node-create (left right data balance) - ;; Create and return an avl-tree node. - `(vector ,left ,right ,data ,balance)) - (defmacro avl-tree-node-balance (node) ;; Return the balance field of a node. `(aref ,node 3)) @@ -130,11 +130,7 @@ (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) + p1 b1 p2 b2 result) (cond ((< (avl-tree-node-balance br) 0) (avl-tree-node-set-balance br 0) @@ -183,11 +179,7 @@ (defun avl-tree-del-balance2 (node branch) (let* ((br (avl-tree-node-branch node branch)) - p1 - b1 - p2 - b2 - result) + p1 b1 p2 b2 result) (cond ((> (avl-tree-node-balance br) 0) (avl-tree-node-set-balance br 0) @@ -235,14 +227,13 @@ 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)) (avl-tree-node-set-data q (avl-tree-node-data br)) (avl-tree-node-set-branch node branch - (avl-tree-node-left br)) + (avl-tree-node-left br)) t))) (defun avl-tree-do-delete (cmpfun root branch data) @@ -281,10 +272,7 @@ (defun avl-tree-enter-balance1 (node branch) ;; Rebalance a tree and return t if the height of the tree has grown. (let* ((br (avl-tree-node-branch node branch)) - p1 - p2 - b2 - result) + p1 p2 b2 result) (cond ((< (avl-tree-node-balance br) 0) (avl-tree-node-set-balance br 0) @@ -325,9 +313,7 @@ (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) + p1 p2 b2) (cond ((> (avl-tree-node-balance br) 0) (avl-tree-node-set-balance br 0) @@ -371,20 +357,16 @@ (cond ((null br) ;; Data not in tree, insert it. - (avl-tree-node-set-branch root branch - (avl-tree-node-create nil nil data 0)) + (avl-tree-node-set-branch + root branch (avl-tree-node-create nil nil data 0)) t) ((funcall cmpfun data (avl-tree-node-data br)) - (and (avl-tree-do-enter cmpfun - br - 0 data) + (and (avl-tree-do-enter cmpfun br 0 data) (avl-tree-enter-balance2 root branch))) ((funcall cmpfun (avl-tree-node-data br) data) - (and (avl-tree-do-enter cmpfun - br - 1 data) + (and (avl-tree-do-enter cmpfun br 1 data) (avl-tree-enter-balance1 root branch))) (t @@ -424,10 +406,11 @@ ;; Highly recursive. INTERNAL USE ONLY. (if (null root) nil - (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)))) + (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)))) ;;; ================================================================ @@ -488,7 +471,6 @@ If there is no such element in the tree, the value is nil." (setq node (avl-tree-node-right node))) (t (setq found t)))) - (if node (avl-tree-node-data node) nil))) @@ -497,9 +479,9 @@ If there is no such element in the tree, the value is nil." "Apply MAP-FUNCTION to all elements in the avl tree TREE." (avl-tree-mapc (function (lambda (node) - (avl-tree-node-set-data node - (funcall __map-function__ - (avl-tree-node-data node))))) + (avl-tree-node-set-data + node (funcall __map-function__ + (avl-tree-node-data node))))) (avl-tree-root tree))) (defun avl-tree-first (tree) @@ -524,29 +506,30 @@ If there is no such element in the tree, the value is nil." (defun avl-tree-copy (tree) "Return a copy of the avl tree TREE." - (let ((new-tree (avl-tree-create - (avl-tree-cmpfun tree)))) + (let ((new-tree (avl-tree-create (avl-tree-cmpfun tree)))) (avl-tree-node-set-left (avl-tree-dummyroot new-tree) - (avl-tree-do-copy (avl-tree-root tree))) + (avl-tree-do-copy (avl-tree-root tree))) new-tree)) (defun avl-tree-flatten (tree) "Return a sorted list containing all elements of TREE." (nreverse (let ((treelist nil)) - (avl-tree-mapc (function (lambda (node) - (setq treelist (cons (avl-tree-node-data node) - treelist)))) - (avl-tree-root tree)) + (avl-tree-mapc + (function (lambda (node) + (setq treelist (cons (avl-tree-node-data node) + treelist)))) + (avl-tree-root tree)) treelist))) (defun avl-tree-size (tree) "Return the number of elements in TREE." (let ((treesize 0)) - (avl-tree-mapc (function (lambda (data) - (setq treesize (1+ treesize)) - data)) - (avl-tree-root tree)) + (avl-tree-mapc + (function (lambda (data) + (setq treesize (1+ treesize)) + data)) + (avl-tree-root tree)) treesize)) (defun avl-tree-clear (tree) -- cgit v1.2.3 From 8fa134424913ad16f2b95f1d1cb2992d3fd17059 Mon Sep 17 00:00:00 2001 From: Thien-Thi Nguyen Date: Mon, 27 Aug 2007 02:49:40 +0000 Subject: (avl-tree-del-balance1, avl-tree-del-balance2) (avl-tree-do-del-internal, avl-tree-do-delete) (avl-tree-enter-balance1, avl-tree-enter-balance2): Use plain `let'. --- lisp/emacs-lisp/avl-tree.el | 20 ++++++++++---------- 1 file changed, 10 insertions(+), 10 deletions(-) (limited to 'lisp/emacs-lisp/avl-tree.el') diff --git a/lisp/emacs-lisp/avl-tree.el b/lisp/emacs-lisp/avl-tree.el index 7dd4d18da7c..074f8e7c772 100644 --- a/lisp/emacs-lisp/avl-tree.el +++ b/lisp/emacs-lisp/avl-tree.el @@ -129,8 +129,8 @@ (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) + (let ((br (avl-tree-node-branch node branch)) + p1 b1 p2 b2 result) (cond ((< (avl-tree-node-balance br) 0) (avl-tree-node-set-balance br 0) @@ -178,8 +178,8 @@ t))))) (defun avl-tree-del-balance2 (node branch) - (let* ((br (avl-tree-node-branch node branch)) - p1 b1 p2 b2 result) + (let ((br (avl-tree-node-branch node branch)) + p1 b1 p2 b2 result) (cond ((> (avl-tree-node-balance br) 0) (avl-tree-node-set-balance br 0) @@ -227,7 +227,7 @@ t))))) (defun avl-tree-do-del-internal (node branch q) - (let* ((br (avl-tree-node-branch node branch))) + (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)) @@ -238,7 +238,7 @@ (defun avl-tree-do-delete (cmpfun root branch data) ;; Return t if the height of the tree has shrunk. - (let* ((br (avl-tree-node-branch root branch))) + (let ((br (avl-tree-node-branch root branch))) (cond ((null br) nil) @@ -271,8 +271,8 @@ (defun avl-tree-enter-balance1 (node branch) ;; Rebalance a tree and return t if the height of the tree has grown. - (let* ((br (avl-tree-node-branch node branch)) - p1 p2 b2 result) + (let ((br (avl-tree-node-branch node branch)) + p1 p2 b2 result) (cond ((< (avl-tree-node-balance br) 0) (avl-tree-node-set-balance br 0) @@ -312,8 +312,8 @@ (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) + (let ((br (avl-tree-node-branch node branch)) + p1 p2 b2) (cond ((> (avl-tree-node-balance br) 0) (avl-tree-node-set-balance br 0) -- cgit v1.2.3 From d385b030e7924a8ef5d7df63b25ce12e3fbd6311 Mon Sep 17 00:00:00 2001 From: Thien-Thi Nguyen Date: Mon, 27 Aug 2007 03:09:15 +0000 Subject: Commentary and docstring munging; nfc. --- lisp/emacs-lisp/avl-tree.el | 52 +++++++++++++++++++-------------------------- 1 file changed, 22 insertions(+), 30 deletions(-) (limited to 'lisp/emacs-lisp/avl-tree.el') diff --git a/lisp/emacs-lisp/avl-tree.el b/lisp/emacs-lisp/avl-tree.el index 074f8e7c772..ffac825acac 100644 --- a/lisp/emacs-lisp/avl-tree.el +++ b/lisp/emacs-lisp/avl-tree.el @@ -28,19 +28,6 @@ ;;; Commentary: -;; This file combines elib-node.el and avltree.el from Elib. -;; -;; * Comments from elib-node.el -;; A node is implemented as an array with three elements, using -;; (elt node 0) as the left pointer -;; (elt node 1) as the right pointer -;; (elt node 2) as the data -;; -;; Some types of trees, e.g. AVL trees, need bigger nodes, but -;; as long as the first three parts are the left pointer, the -;; right pointer and the data field, these macros can be used. -;; -;; * Comments from avltree.el ;; An AVL tree is a nearly-perfect balanced binary tree. A tree ;; consists of two cons cells, the first one holding the tag ;; 'AVL-TREE in the car cell, and the second one having the tree @@ -51,6 +38,10 @@ ;; 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. +;; +;; The "public" functions (prefixed with "avl-tree") are: +;; -create, -p, -compare-function, -empty, -enter, -delete, +;; -member, -map, -first, -last, -copy, -flatten, -size, -clear. ;;; Code: @@ -86,18 +77,18 @@ `(aset ,node 2 ,newdata)) (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." + "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 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. - ;; 0 for left pointer, 1 for the right pointer and 2 for the data. - ;; NEWVAL is new value of the branch." + "Set value of a branch of a node. + +NODE is the node, and BRANCH is the branch. +0 for left pointer, 1 for the right pointer and 2 for the data. +NEWVAL is new value of the branch.\"" `(aset ,node ,branch ,newval)) (defmacro avl-tree-node-balance (node) @@ -402,7 +393,7 @@ go-left nil)))))) (defun avl-tree-do-copy (root) - ;; Copy the tree with ROOT as root. + ;; Copy the avl tree with ROOT as root. ;; Highly recursive. INTERNAL USE ONLY. (if (null root) nil @@ -417,7 +408,7 @@ ;;; The public functions which operate on AVL trees. (defun avl-tree-create (compare-function) - "Create an empty avl tree. + "Create a new empty avl tree and return it. 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." (cons 'AVL-TREE @@ -429,11 +420,11 @@ and returns non-nil if A is less than B, and nil otherwise." (eq (car-safe obj) 'AVL-TREE)) (defun avl-tree-compare-function (tree) - "Return the comparision function for the avl tree TREE." + "Return the comparison function for the avl tree TREE." (avl-tree-cmpfun tree)) (defun avl-tree-empty (tree) - "Return t if TREE is emtpy, otherwise return nil." + "Return t if avl tree TREE is emtpy, otherwise return nil." (null (avl-tree-root tree))) (defun avl-tree-enter (tree data) @@ -447,7 +438,8 @@ Return 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." +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 @@ -455,8 +447,8 @@ Return the element in TREE which matched DATA, nil if no element matched." (defun avl-tree-member (tree data) "Return the element in the avl tree TREE which matches DATA. -Matching uses the compare function previously specified in `avl-tree-create' -when TREE was created. +Matching uses the compare function previously specified in +`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)) @@ -476,7 +468,7 @@ If there is no such element in the tree, the value is nil." nil))) (defun avl-tree-map (__map-function__ tree) - "Apply MAP-FUNCTION to all elements in the avl tree TREE." + "Apply __MAP-FUNCTION__ to all elements in the avl tree TREE." (avl-tree-mapc (function (lambda (node) (avl-tree-node-set-data -- cgit v1.2.3