Mercurial > emacs
annotate lisp/emacs-lisp/avl-tree.el @ 102929:6be674ea734e
* vc-dir.el (vc-dir): Dox fix.
author | Richard M. Stallman <rms@gnu.org> |
---|---|
date | Fri, 10 Apr 2009 14:19:12 +0000 |
parents | a9dc0e7c3f2b |
children | 1d1d5d9bd884 |
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 | 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 | 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 | 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 | 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 | 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 |