annotate lisp/emacs-lisp/avl-tree.el @ 104232:23230e6cbc19

*** empty log message ***
author Dmitry Dzhus <dima@sphinx.net.ru>
date Tue, 11 Aug 2009 10:48:56 +0000
parents a9dc0e7c3f2b
children 1d1d5d9bd884
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
82891
fb6442527160 Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82890
diff changeset
1 ;;; avl-tree.el --- balanced binary trees, AVL-trees
82890
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
2
100908
a9dc0e7c3f2b Add 2009 to copyright years.
Glenn Morris <rgm@gnu.org>
parents: 94655
diff changeset
3 ;; Copyright (C) 1995, 2007, 2008, 2009 Free Software Foundation, Inc.
82890
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
4
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
5 ;; Author: Per Cederqvist <ceder@lysator.liu.se>
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
6 ;; Inge Wallin <inge@lysator.liu.se>
82891
fb6442527160 Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82890
diff changeset
7 ;; Thomas Bellman <bellman@lysator.liu.se>
fb6442527160 Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82890
diff changeset
8 ;; Maintainer: FSF
fb6442527160 Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82890
diff changeset
9 ;; Created: 10 May 1991
fb6442527160 Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82890
diff changeset
10 ;; Keywords: extensions, data structures
fb6442527160 Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82890
diff changeset
11
fb6442527160 Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82890
diff changeset
12 ;; This file is part of GNU Emacs.
82890
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
13
94655
90a2847062be Switch to recommended form of GPLv3 permissions notice.
Glenn Morris <rgm@gnu.org>
parents: 87665
diff changeset
14 ;; GNU Emacs is free software: you can redistribute it and/or modify
82891
fb6442527160 Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82890
diff changeset
15 ;; it under the terms of the GNU General Public License as published by
94655
90a2847062be Switch to recommended form of GPLv3 permissions notice.
Glenn Morris <rgm@gnu.org>
parents: 87665
diff changeset
16 ;; the Free Software Foundation, either version 3 of the License, or
90a2847062be Switch to recommended form of GPLv3 permissions notice.
Glenn Morris <rgm@gnu.org>
parents: 87665
diff changeset
17 ;; (at your option) any later version.
82891
fb6442527160 Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82890
diff changeset
18
fb6442527160 Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82890
diff changeset
19 ;; GNU Emacs is distributed in the hope that it will be useful,
fb6442527160 Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82890
diff changeset
20 ;; but WITHOUT ANY WARRANTY; without even the implied warranty of
fb6442527160 Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82890
diff changeset
21 ;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
fb6442527160 Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82890
diff changeset
22 ;; GNU General Public License for more details.
fb6442527160 Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82890
diff changeset
23
fb6442527160 Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82890
diff changeset
24 ;; You should have received a copy of the GNU General Public License
94655
90a2847062be Switch to recommended form of GPLv3 permissions notice.
Glenn Morris <rgm@gnu.org>
parents: 87665
diff changeset
25 ;; along with GNU Emacs. If not, see <http://www.gnu.org/licenses/>.
82890
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
26
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
27 ;;; Commentary:
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
28
83827
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
29 ;; An AVL tree is a nearly-perfect balanced binary tree. A tree consists of
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
30 ;; two elements, the root node and the compare function. The actual tree
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
31 ;; has a dummy node as its root with the real root in the left pointer.
82891
fb6442527160 Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82890
diff changeset
32 ;;
fb6442527160 Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82890
diff changeset
33 ;; Each node of the tree consists of one data element, one left
fb6442527160 Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82890
diff changeset
34 ;; sub-tree and one right sub-tree. Each node also has a balance
fb6442527160 Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82890
diff changeset
35 ;; count, which is the difference in depth of the left and right
fb6442527160 Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82890
diff changeset
36 ;; sub-trees.
82903
7224e10a56f5 Commentary and docstring munging; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82902
diff changeset
37 ;;
83827
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
38 ;; The functions with names of the form "avl-tree--" are intended for
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
39 ;; internal use only.
82890
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
40
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
41 ;;; Code:
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
42
83827
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
43 (eval-when-compile (require 'cl))
82901
18391b91e11f Move things around; munge whitespace, indentation; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82900
diff changeset
44
83827
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
45 ;; ================================================================
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
46 ;;; Functions and macros handling an AVL tree node.
82890
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
47
83827
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
48 (defstruct (avl-tree--node
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
49 ;; We force a representation without tag so it matches the
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
50 ;; pre-defstruct representation. Also we use the underlying
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
51 ;; representation in the implementation of avl-tree--node-branch.
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
52 (:type vector)
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
53 (:constructor nil)
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
54 (:constructor avl-tree--node-create (left right data balance))
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
55 (:copier nil))
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
56 left right data balance)
82890
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
57
83827
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
58 (defalias 'avl-tree--node-branch 'aref
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
59 ;; This implementation is efficient but breaks the defstruct abstraction.
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
60 ;; An alternative could be
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
61 ;; (funcall (aref [avl-tree-left avl-tree-right avl-tree-data] branch) node)
82903
7224e10a56f5 Commentary and docstring munging; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82902
diff changeset
62 "Get value of a branch of a node.
7224e10a56f5 Commentary and docstring munging; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82902
diff changeset
63
7224e10a56f5 Commentary and docstring munging; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82902
diff changeset
64 NODE is the node, and BRANCH is the branch.
83827
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
65 0 for left pointer, 1 for right pointer and 2 for the data.\"
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
66 \(fn node branch)")
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
67 ;; The funcall/aref trick doesn't work for the setf method, unless we try
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
68 ;; and access the underlying setter function, but this wouldn't be
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
69 ;; portable either.
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
70 (defsetf avl-tree--node-branch aset)
82890
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
71
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
72
83827
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
73 ;; ================================================================
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
74 ;;; Internal functions for use in the AVL tree package
82890
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
75
83827
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
76 (defstruct (avl-tree-
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
77 ;; A tagged list is the pre-defstruct representation.
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
78 ;; (:type list)
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
79 :named
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
80 (:constructor nil)
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
81 (:constructor avl-tree-create (cmpfun))
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
82 (:predicate avl-tree-p)
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
83 (:copier nil))
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
84 (dummyroot (avl-tree--node-create nil nil nil 0))
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
85 cmpfun)
82890
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
86
83827
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
87 (defmacro avl-tree--root (tree)
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
88 ;; Return the root node for an avl-tree. INTERNAL USE ONLY.
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
89 `(avl-tree--node-left (avl-tree--dummyroot tree)))
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
90 (defsetf avl-tree--root (tree) (node)
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
91 `(setf (avl-tree--node-left (avl-tree--dummyroot ,tree)) ,node))
82890
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
92
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
93 ;; ----------------------------------------------------------------
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
94 ;; Deleting data
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
95
83827
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
96 (defun avl-tree--del-balance1 (node branch)
82890
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
97 ;; Rebalance a tree and return t if the height of the tree has shrunk.
83827
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
98 (let ((br (avl-tree--node-branch node branch))
82902
c27b2ab395b6 (avl-tree-del-balance1, avl-tree-del-balance2)
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82901
diff changeset
99 p1 b1 p2 b2 result)
82890
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
100 (cond
83827
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
101 ((< (avl-tree--node-balance br) 0)
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
102 (setf (avl-tree--node-balance br) 0)
82890
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
103 t)
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
104
83827
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
105 ((= (avl-tree--node-balance br) 0)
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
106 (setf (avl-tree--node-balance br) +1)
82890
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
107 nil)
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
108
82891
fb6442527160 Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82890
diff changeset
109 (t
fb6442527160 Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82890
diff changeset
110 ;; Rebalance.
83827
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
111 (setq p1 (avl-tree--node-right br)
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
112 b1 (avl-tree--node-balance p1))
82890
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
113 (if (>= b1 0)
82891
fb6442527160 Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82890
diff changeset
114 ;; Single RR rotation.
fb6442527160 Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82890
diff changeset
115 (progn
83827
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
116 (setf (avl-tree--node-right br) (avl-tree--node-left p1))
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
117 (setf (avl-tree--node-left p1) br)
82891
fb6442527160 Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82890
diff changeset
118 (if (= 0 b1)
fb6442527160 Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82890
diff changeset
119 (progn
83827
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
120 (setf (avl-tree--node-balance br) +1)
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
121 (setf (avl-tree--node-balance p1) -1)
82891
fb6442527160 Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82890
diff changeset
122 (setq result nil))
83827
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
123 (setf (avl-tree--node-balance br) 0)
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
124 (setf (avl-tree--node-balance p1) 0)
82891
fb6442527160 Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82890
diff changeset
125 (setq result t))
83827
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
126 (setf (avl-tree--node-branch node branch) p1)
82891
fb6442527160 Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82890
diff changeset
127 result)
82890
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
128
82891
fb6442527160 Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82890
diff changeset
129 ;; Double RL rotation.
83827
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
130 (setq p2 (avl-tree--node-left p1)
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
131 b2 (avl-tree--node-balance p2))
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
132 (setf (avl-tree--node-left p1) (avl-tree--node-right p2))
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
133 (setf (avl-tree--node-right p2) p1)
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
134 (setf (avl-tree--node-right br) (avl-tree--node-left p2))
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
135 (setf (avl-tree--node-left p2) br)
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
136 (setf (avl-tree--node-balance br) (if (> b2 0) -1 0))
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
137 (setf (avl-tree--node-balance p1) (if (< b2 0) +1 0))
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
138 (setf (avl-tree--node-branch node branch) p2)
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
139 (setf (avl-tree--node-balance p2) 0)
82891
fb6442527160 Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82890
diff changeset
140 t)))))
82890
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
141
83827
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
142 (defun avl-tree--del-balance2 (node branch)
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
143 (let ((br (avl-tree--node-branch node branch))
82902
c27b2ab395b6 (avl-tree-del-balance1, avl-tree-del-balance2)
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82901
diff changeset
144 p1 b1 p2 b2 result)
82890
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
145 (cond
83827
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
146 ((> (avl-tree--node-balance br) 0)
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
147 (setf (avl-tree--node-balance br) 0)
82890
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
148 t)
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
149
83827
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
150 ((= (avl-tree--node-balance br) 0)
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
151 (setf (avl-tree--node-balance br) -1)
82890
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
152 nil)
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
153
82891
fb6442527160 Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82890
diff changeset
154 (t
fb6442527160 Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82890
diff changeset
155 ;; Rebalance.
83827
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
156 (setq p1 (avl-tree--node-left br)
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
157 b1 (avl-tree--node-balance p1))
82890
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
158 (if (<= b1 0)
82891
fb6442527160 Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82890
diff changeset
159 ;; Single LL rotation.
fb6442527160 Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82890
diff changeset
160 (progn
83827
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
161 (setf (avl-tree--node-left br) (avl-tree--node-right p1))
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
162 (setf (avl-tree--node-right p1) br)
82891
fb6442527160 Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82890
diff changeset
163 (if (= 0 b1)
fb6442527160 Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82890
diff changeset
164 (progn
83827
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
165 (setf (avl-tree--node-balance br) -1)
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
166 (setf (avl-tree--node-balance p1) +1)
82891
fb6442527160 Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82890
diff changeset
167 (setq result nil))
83827
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
168 (setf (avl-tree--node-balance br) 0)
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
169 (setf (avl-tree--node-balance p1) 0)
82891
fb6442527160 Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82890
diff changeset
170 (setq result t))
83827
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
171 (setf (avl-tree--node-branch node branch) p1)
82891
fb6442527160 Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82890
diff changeset
172 result)
82890
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
173
82891
fb6442527160 Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82890
diff changeset
174 ;; Double LR rotation.
83827
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
175 (setq p2 (avl-tree--node-right p1)
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
176 b2 (avl-tree--node-balance p2))
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
177 (setf (avl-tree--node-right p1) (avl-tree--node-left p2))
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
178 (setf (avl-tree--node-left p2) p1)
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
179 (setf (avl-tree--node-left br) (avl-tree--node-right p2))
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
180 (setf (avl-tree--node-right p2) br)
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
181 (setf (avl-tree--node-balance br) (if (< b2 0) +1 0))
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
182 (setf (avl-tree--node-balance p1) (if (> b2 0) -1 0))
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
183 (setf (avl-tree--node-branch node branch) p2)
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
184 (setf (avl-tree--node-balance p2) 0)
82891
fb6442527160 Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82890
diff changeset
185 t)))))
82890
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
186
83827
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
187 (defun avl-tree--do-del-internal (node branch q)
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
188 (let ((br (avl-tree--node-branch node branch)))
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
189 (if (avl-tree--node-right br)
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
190 (if (avl-tree--do-del-internal br +1 q)
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
191 (avl-tree--del-balance2 node branch))
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
192 (setf (avl-tree--node-data q) (avl-tree--node-data br))
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
193 (setf (avl-tree--node-branch node branch)
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
194 (avl-tree--node-left br))
82891
fb6442527160 Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82890
diff changeset
195 t)))
82890
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
196
83827
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
197 (defun avl-tree--do-delete (cmpfun root branch data)
82890
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
198 ;; Return t if the height of the tree has shrunk.
83827
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
199 (let ((br (avl-tree--node-branch root branch)))
82890
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
200 (cond
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
201 ((null br)
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
202 nil)
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
203
83827
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
204 ((funcall cmpfun data (avl-tree--node-data br))
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
205 (if (avl-tree--do-delete cmpfun br 0 data)
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
206 (avl-tree--del-balance1 root branch)))
82890
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
207
83827
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
208 ((funcall cmpfun (avl-tree--node-data br) data)
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
209 (if (avl-tree--do-delete cmpfun br 1 data)
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
210 (avl-tree--del-balance2 root branch)))
82890
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
211
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
212 (t
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
213 ;; Found it. Let's delete it.
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
214 (cond
83827
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
215 ((null (avl-tree--node-right br))
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
216 (setf (avl-tree--node-branch root branch) (avl-tree--node-left br))
82891
fb6442527160 Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82890
diff changeset
217 t)
82890
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
218
83827
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
219 ((null (avl-tree--node-left br))
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
220 (setf (avl-tree--node-branch root branch) (avl-tree--node-right br))
82891
fb6442527160 Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82890
diff changeset
221 t)
82890
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
222
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
223 (t
83827
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
224 (if (avl-tree--do-del-internal br 0 br)
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
225 (avl-tree--del-balance1 root branch))))))))
82890
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
226
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
227 ;; ----------------------------------------------------------------
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
228 ;; Entering data
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
229
83827
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
230 (defun avl-tree--enter-balance1 (node branch)
82890
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
231 ;; Rebalance a tree and return t if the height of the tree has grown.
83827
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
232 (let ((br (avl-tree--node-branch node branch))
82902
c27b2ab395b6 (avl-tree-del-balance1, avl-tree-del-balance2)
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82901
diff changeset
233 p1 p2 b2 result)
82890
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
234 (cond
83827
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
235 ((< (avl-tree--node-balance br) 0)
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
236 (setf (avl-tree--node-balance br) 0)
82890
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
237 nil)
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
238
83827
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
239 ((= (avl-tree--node-balance br) 0)
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
240 (setf (avl-tree--node-balance br) +1)
82890
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
241 t)
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
242
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
243 (t
82891
fb6442527160 Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82890
diff changeset
244 ;; Tree has grown => Rebalance.
83827
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
245 (setq p1 (avl-tree--node-right br))
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
246 (if (> (avl-tree--node-balance p1) 0)
82891
fb6442527160 Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82890
diff changeset
247 ;; Single RR rotation.
fb6442527160 Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82890
diff changeset
248 (progn
83827
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
249 (setf (avl-tree--node-right br) (avl-tree--node-left p1))
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
250 (setf (avl-tree--node-left p1) br)
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
251 (setf (avl-tree--node-balance br) 0)
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
252 (setf (avl-tree--node-branch node branch) p1))
82890
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
253
82891
fb6442527160 Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82890
diff changeset
254 ;; Double RL rotation.
83827
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
255 (setq p2 (avl-tree--node-left p1)
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
256 b2 (avl-tree--node-balance p2))
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
257 (setf (avl-tree--node-left p1) (avl-tree--node-right p2))
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
258 (setf (avl-tree--node-right p2) p1)
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
259 (setf (avl-tree--node-right br) (avl-tree--node-left p2))
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
260 (setf (avl-tree--node-left p2) br)
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
261 (setf (avl-tree--node-balance br) (if (> b2 0) -1 0))
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
262 (setf (avl-tree--node-balance p1) (if (< b2 0) +1 0))
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
263 (setf (avl-tree--node-branch node branch) p2))
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
264 (setf (avl-tree--node-balance (avl-tree--node-branch node branch)) 0)
82891
fb6442527160 Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82890
diff changeset
265 nil))))
82890
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
266
83827
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
267 (defun avl-tree--enter-balance2 (node branch)
82890
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
268 ;; Return t if the tree has grown.
83827
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
269 (let ((br (avl-tree--node-branch node branch))
82902
c27b2ab395b6 (avl-tree-del-balance1, avl-tree-del-balance2)
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82901
diff changeset
270 p1 p2 b2)
82890
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
271 (cond
83827
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
272 ((> (avl-tree--node-balance br) 0)
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
273 (setf (avl-tree--node-balance br) 0)
82890
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
274 nil)
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
275
83827
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
276 ((= (avl-tree--node-balance br) 0)
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
277 (setf (avl-tree--node-balance br) -1)
82890
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
278 t)
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
279
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
280 (t
82891
fb6442527160 Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82890
diff changeset
281 ;; Balance was -1 => Rebalance.
83827
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
282 (setq p1 (avl-tree--node-left br))
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
283 (if (< (avl-tree--node-balance p1) 0)
82891
fb6442527160 Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82890
diff changeset
284 ;; Single LL rotation.
fb6442527160 Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82890
diff changeset
285 (progn
83827
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
286 (setf (avl-tree--node-left br) (avl-tree--node-right p1))
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
287 (setf (avl-tree--node-right p1) br)
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
288 (setf (avl-tree--node-balance br) 0)
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
289 (setf (avl-tree--node-branch node branch) p1))
82890
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
290
82891
fb6442527160 Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82890
diff changeset
291 ;; Double LR rotation.
83827
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
292 (setq p2 (avl-tree--node-right p1)
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
293 b2 (avl-tree--node-balance p2))
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
294 (setf (avl-tree--node-right p1) (avl-tree--node-left p2))
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
295 (setf (avl-tree--node-left p2) p1)
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
296 (setf (avl-tree--node-left br) (avl-tree--node-right p2))
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
297 (setf (avl-tree--node-right p2) br)
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
298 (setf (avl-tree--node-balance br) (if (< b2 0) +1 0))
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
299 (setf (avl-tree--node-balance p1) (if (> b2 0) -1 0))
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
300 (setf (avl-tree--node-branch node branch) p2))
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
301 (setf (avl-tree--node-balance (avl-tree--node-branch node branch)) 0)
82891
fb6442527160 Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82890
diff changeset
302 nil))))
82890
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
303
83827
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
304 (defun avl-tree--do-enter (cmpfun root branch data)
82890
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
305 ;; Return t if height of tree ROOT has grown. INTERNAL USE ONLY.
83827
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
306 (let ((br (avl-tree--node-branch root branch)))
82890
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
307 (cond
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
308 ((null br)
82891
fb6442527160 Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82890
diff changeset
309 ;; Data not in tree, insert it.
83827
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
310 (setf (avl-tree--node-branch root branch)
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
311 (avl-tree--node-create nil nil data 0))
82890
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
312 t)
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
313
83827
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
314 ((funcall cmpfun data (avl-tree--node-data br))
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
315 (and (avl-tree--do-enter cmpfun br 0 data)
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
316 (avl-tree--enter-balance2 root branch)))
82890
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
317
83827
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
318 ((funcall cmpfun (avl-tree--node-data br) data)
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
319 (and (avl-tree--do-enter cmpfun br 1 data)
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
320 (avl-tree--enter-balance1 root branch)))
82890
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
321
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
322 (t
83827
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
323 (setf (avl-tree--node-data br) data)
82890
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
324 nil))))
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
325
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
326 ;; ----------------------------------------------------------------
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
327
83827
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
328 (defun avl-tree--mapc (map-function root)
82890
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
329 ;; Apply MAP-FUNCTION to all nodes in the tree starting with ROOT.
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
330 ;; The function is applied in-order.
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
331 ;;
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
332 ;; Note: MAP-FUNCTION is applied to the node and not to the data itself.
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
333 ;; INTERNAL USE ONLY.
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
334 (let ((node root)
82893
2321b585ebdd Don't require `cl'.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82892
diff changeset
335 (stack nil)
82891
fb6442527160 Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82890
diff changeset
336 (go-left t))
82893
2321b585ebdd Don't require `cl'.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82892
diff changeset
337 (push nil stack)
82890
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
338 (while node
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
339 (if (and go-left
83827
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
340 (avl-tree--node-left node))
82891
fb6442527160 Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82890
diff changeset
341 ;; Do the left subtree first.
fb6442527160 Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82890
diff changeset
342 (progn
82893
2321b585ebdd Don't require `cl'.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82892
diff changeset
343 (push node stack)
83827
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
344 (setq node (avl-tree--node-left node)))
82891
fb6442527160 Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82890
diff changeset
345 ;; Apply the function...
fb6442527160 Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82890
diff changeset
346 (funcall map-function node)
fb6442527160 Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82890
diff changeset
347 ;; and do the right subtree.
83827
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
348 (setq node (if (setq go-left (avl-tree--node-right node))
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
349 (avl-tree--node-right node)
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
350 (pop stack)))))))
82890
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
351
83827
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
352 (defun avl-tree--do-copy (root)
82903
7224e10a56f5 Commentary and docstring munging; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82902
diff changeset
353 ;; Copy the avl tree with ROOT as root.
82890
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
354 ;; Highly recursive. INTERNAL USE ONLY.
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
355 (if (null root)
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
356 nil
83827
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
357 (avl-tree--node-create
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
358 (avl-tree--do-copy (avl-tree--node-left root))
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
359 (avl-tree--do-copy (avl-tree--node-right root))
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
360 (avl-tree--node-data root)
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
361 (avl-tree--node-balance root))))
82890
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
362
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
363
83827
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
364 ;; ================================================================
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
365 ;;; The public functions which operate on AVL trees.
82890
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
366
83827
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
367 (defalias 'avl-tree-compare-function 'avl-tree--cmpfun
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
368 "Return the comparison function for the avl tree TREE.
82890
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
369
83827
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
370 \(fn TREE)")
82890
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
371
82895
3b4dacb1e48c Do s/avltree/avl-tree/g. Resulting changed function names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82894
diff changeset
372 (defun avl-tree-empty (tree)
82903
7224e10a56f5 Commentary and docstring munging; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82902
diff changeset
373 "Return t if avl tree TREE is emtpy, otherwise return nil."
83827
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
374 (null (avl-tree--root tree)))
82890
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
375
82895
3b4dacb1e48c Do s/avltree/avl-tree/g. Resulting changed function names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82894
diff changeset
376 (defun avl-tree-enter (tree data)
82890
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
377 "In the avl tree TREE insert DATA.
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
378 Return DATA."
83827
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
379 (avl-tree--do-enter (avl-tree--cmpfun tree)
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
380 (avl-tree--dummyroot tree)
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
381 0
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
382 data)
82890
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
383 data)
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
384
82895
3b4dacb1e48c Do s/avltree/avl-tree/g. Resulting changed function names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82894
diff changeset
385 (defun avl-tree-delete (tree data)
82890
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
386 "From the avl tree TREE, delete DATA.
82903
7224e10a56f5 Commentary and docstring munging; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82902
diff changeset
387 Return the element in TREE which matched DATA,
7224e10a56f5 Commentary and docstring munging; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82902
diff changeset
388 nil if no element matched."
83827
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
389 (avl-tree--do-delete (avl-tree--cmpfun tree)
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
390 (avl-tree--dummyroot tree)
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
391 0
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
392 data))
82890
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
393
82895
3b4dacb1e48c Do s/avltree/avl-tree/g. Resulting changed function names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82894
diff changeset
394 (defun avl-tree-member (tree data)
82890
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
395 "Return the element in the avl tree TREE which matches DATA.
82903
7224e10a56f5 Commentary and docstring munging; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82902
diff changeset
396 Matching uses the compare function previously specified in
7224e10a56f5 Commentary and docstring munging; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82902
diff changeset
397 `avl-tree-create' when TREE was created.
82890
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
398
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
399 If there is no such element in the tree, the value is nil."
83827
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
400 (let ((node (avl-tree--root tree))
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
401 (compare-function (avl-tree--cmpfun tree))
82891
fb6442527160 Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82890
diff changeset
402 found)
82890
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
403 (while (and node
82891
fb6442527160 Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82890
diff changeset
404 (not found))
82890
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
405 (cond
83827
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
406 ((funcall compare-function data (avl-tree--node-data node))
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
407 (setq node (avl-tree--node-left node)))
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
408 ((funcall compare-function (avl-tree--node-data node) data)
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
409 (setq node (avl-tree--node-right node)))
82890
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
410 (t
82891
fb6442527160 Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82890
diff changeset
411 (setq found t))))
82890
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
412 (if node
83827
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
413 (avl-tree--node-data node)
82890
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
414 nil)))
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
415
82895
3b4dacb1e48c Do s/avltree/avl-tree/g. Resulting changed function names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82894
diff changeset
416 (defun avl-tree-map (__map-function__ tree)
82903
7224e10a56f5 Commentary and docstring munging; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82902
diff changeset
417 "Apply __MAP-FUNCTION__ to all elements in the avl tree TREE."
83827
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
418 (avl-tree--mapc
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
419 (lambda (node)
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
420 (setf (avl-tree--node-data node)
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
421 (funcall __map-function__ (avl-tree--node-data node))))
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
422 (avl-tree--root tree)))
82890
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
423
82895
3b4dacb1e48c Do s/avltree/avl-tree/g. Resulting changed function names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82894
diff changeset
424 (defun avl-tree-first (tree)
82890
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
425 "Return the first element in TREE, or nil if TREE is empty."
83827
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
426 (let ((node (avl-tree--root tree)))
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
427 (when node
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
428 (while (avl-tree--node-left node)
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
429 (setq node (avl-tree--node-left node)))
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
430 (avl-tree--node-data node))))
82890
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
431
82895
3b4dacb1e48c Do s/avltree/avl-tree/g. Resulting changed function names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82894
diff changeset
432 (defun avl-tree-last (tree)
82890
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
433 "Return the last element in TREE, or nil if TREE is empty."
83827
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
434 (let ((node (avl-tree--root tree)))
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
435 (when node
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
436 (while (avl-tree--node-right node)
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
437 (setq node (avl-tree--node-right node)))
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
438 (avl-tree--node-data node))))
82890
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
439
82895
3b4dacb1e48c Do s/avltree/avl-tree/g. Resulting changed function names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82894
diff changeset
440 (defun avl-tree-copy (tree)
82890
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
441 "Return a copy of the avl tree TREE."
83827
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
442 (let ((new-tree (avl-tree-create (avl-tree--cmpfun tree))))
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
443 (setf (avl-tree--root new-tree) (avl-tree--do-copy (avl-tree--root tree)))
82890
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
444 new-tree))
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
445
82895
3b4dacb1e48c Do s/avltree/avl-tree/g. Resulting changed function names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82894
diff changeset
446 (defun avl-tree-flatten (tree)
82890
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
447 "Return a sorted list containing all elements of TREE."
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
448 (nreverse
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
449 (let ((treelist nil))
83827
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
450 (avl-tree--mapc
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
451 (lambda (node) (push (avl-tree--node-data node) treelist))
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
452 (avl-tree--root tree))
82890
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
453 treelist)))
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
454
82895
3b4dacb1e48c Do s/avltree/avl-tree/g. Resulting changed function names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82894
diff changeset
455 (defun avl-tree-size (tree)
82890
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
456 "Return the number of elements in TREE."
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
457 (let ((treesize 0))
83827
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
458 (avl-tree--mapc
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
459 (lambda (data) (setq treesize (1+ treesize)))
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
460 (avl-tree--root tree))
82890
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
461 treesize))
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
462
82895
3b4dacb1e48c Do s/avltree/avl-tree/g. Resulting changed function names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82894
diff changeset
463 (defun avl-tree-clear (tree)
82890
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
464 "Clear the avl tree TREE."
83827
17a8beea7b8c Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents: 82903
diff changeset
465 (setf (avl-tree--root tree) nil))
82890
03c151908dc7 Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff changeset
466
82892
8ce807303185 Move provide form to end; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82891
diff changeset
467 (provide 'avl-tree)
8ce807303185 Move provide form to end; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82891
diff changeset
468
82894
dbd7c4bc480e Add arch tagline
Miles Bader <miles@gnu.org>
parents: 82893
diff changeset
469 ;; arch-tag: 47e26701-43c9-4222-bd79-739eac6357a9
82895
3b4dacb1e48c Do s/avltree/avl-tree/g. Resulting changed function names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents: 82894
diff changeset
470 ;;; avl-tree.el ends here