Mercurial > emacs
annotate lisp/emacs-lisp/avl-tree.el @ 82901:18391b91e11f
Move things around; munge whitespace, indentation; nfc.
author | Thien-Thi Nguyen <ttn@gnuvola.org> |
---|---|
date | Mon, 27 Aug 2007 02:40:25 +0000 |
parents | 0ff5cfe89663 |
children | c27b2ab395b6 |
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 |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
3 ;; Copyright (C) 1995, 2007 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 |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
14 ;; GNU Emacs is free software; you can redistribute it and/or modify |
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 |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
16 ;; the Free Software Foundation; either version 3, or (at your option) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
17 ;; any later version. |
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 |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
25 ;; along with GNU Emacs; see the file COPYING. If not, write to the |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
26 ;; Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
27 ;; Boston, MA 02110-1301, USA. |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
28 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
29 ;;; Commentary: |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
30 |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
31 ;; This file combines elib-node.el and avltree.el from Elib. |
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 ;; * Comments from elib-node.el |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
34 ;; A node is implemented as an array with three elements, using |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
35 ;; (elt node 0) as the left pointer |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
36 ;; (elt node 1) as the right pointer |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
37 ;; (elt node 2) as the data |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
38 ;; |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
39 ;; Some types of trees, e.g. AVL trees, need bigger nodes, but |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
40 ;; as long as the first three parts are the left pointer, the |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
41 ;; right pointer and the data field, these macros can be used. |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
42 ;; |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
43 ;; * Comments from avltree.el |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
44 ;; An AVL tree is a nearly-perfect balanced binary tree. A tree |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
45 ;; consists of two cons cells, the first one holding the tag |
82895
3b4dacb1e48c
Do s/avltree/avl-tree/g. Resulting changed function names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82894
diff
changeset
|
46 ;; 'AVL-TREE in the car cell, and the second one having the tree |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
47 ;; in the car and the compare function in the cdr cell. The tree has |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
48 ;; a dummy node as its root with the real tree in the left pointer. |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
49 ;; |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
50 ;; 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
|
51 ;; 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
|
52 ;; 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
|
53 ;; sub-trees. |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
54 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
55 ;;; Code: |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
56 |
82901
18391b91e11f
Move things around; munge whitespace, indentation; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82900
diff
changeset
|
57 ;;; ================================================================ |
18391b91e11f
Move things around; munge whitespace, indentation; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82900
diff
changeset
|
58 ;;; Functions and macros handling an AVL tree node. |
18391b91e11f
Move things around; munge whitespace, indentation; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82900
diff
changeset
|
59 |
18391b91e11f
Move things around; munge whitespace, indentation; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82900
diff
changeset
|
60 (defmacro avl-tree-node-create (left right data balance) |
18391b91e11f
Move things around; munge whitespace, indentation; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82900
diff
changeset
|
61 ;; Create and return an avl-tree node. |
18391b91e11f
Move things around; munge whitespace, indentation; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82900
diff
changeset
|
62 `(vector ,left ,right ,data ,balance)) |
18391b91e11f
Move things around; munge whitespace, indentation; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82900
diff
changeset
|
63 |
82900
0ff5cfe89663
Do s/elib-node-/avl-tree-node-/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82899
diff
changeset
|
64 (defmacro avl-tree-node-left (node) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
65 ;; Return the left pointer of NODE. |
82896
f064de4f7268
Reduce nesting: Use modern backquote syntax.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82895
diff
changeset
|
66 `(aref ,node 0)) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
67 |
82900
0ff5cfe89663
Do s/elib-node-/avl-tree-node-/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82899
diff
changeset
|
68 (defmacro 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
|
69 ;; Return the right pointer of NODE. |
82896
f064de4f7268
Reduce nesting: Use modern backquote syntax.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82895
diff
changeset
|
70 `(aref ,node 1)) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
71 |
82900
0ff5cfe89663
Do s/elib-node-/avl-tree-node-/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82899
diff
changeset
|
72 (defmacro 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
|
73 ;; Return the data of NODE. |
82896
f064de4f7268
Reduce nesting: Use modern backquote syntax.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82895
diff
changeset
|
74 `(aref ,node 2)) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
75 |
82900
0ff5cfe89663
Do s/elib-node-/avl-tree-node-/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82899
diff
changeset
|
76 (defmacro avl-tree-node-set-left (node newleft) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
77 ;; Set the left pointer of NODE to NEWLEFT. |
82896
f064de4f7268
Reduce nesting: Use modern backquote syntax.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82895
diff
changeset
|
78 `(aset ,node 0 ,newleft)) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
79 |
82900
0ff5cfe89663
Do s/elib-node-/avl-tree-node-/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82899
diff
changeset
|
80 (defmacro avl-tree-node-set-right (node newright) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
81 ;; Set the right pointer of NODE to NEWRIGHT. |
82896
f064de4f7268
Reduce nesting: Use modern backquote syntax.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82895
diff
changeset
|
82 `(aset ,node 1 ,newright)) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
83 |
82900
0ff5cfe89663
Do s/elib-node-/avl-tree-node-/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82899
diff
changeset
|
84 (defmacro avl-tree-node-set-data (node newdata) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
85 ;; Set the data of NODE to NEWDATA. |
82896
f064de4f7268
Reduce nesting: Use modern backquote syntax.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82895
diff
changeset
|
86 `(aset ,node 2 ,newdata)) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
87 |
82900
0ff5cfe89663
Do s/elib-node-/avl-tree-node-/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82899
diff
changeset
|
88 (defmacro avl-tree-node-branch (node branch) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
89 ;; Get value of a branch of a node. |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
90 ;; |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
91 ;; NODE is the node, and BRANCH is the branch. |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
92 ;; 0 for left pointer, 1 for right pointer and 2 for the data." |
82896
f064de4f7268
Reduce nesting: Use modern backquote syntax.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82895
diff
changeset
|
93 `(aref ,node ,branch)) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
94 |
82900
0ff5cfe89663
Do s/elib-node-/avl-tree-node-/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82899
diff
changeset
|
95 (defmacro avl-tree-node-set-branch (node branch newval) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
96 ;; Set value of a branch of a node. |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
97 ;; |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
98 ;; NODE is the node, and BRANCH is the branch. |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
99 ;; 0 for left pointer, 1 for the right pointer and 2 for the data. |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
100 ;; NEWVAL is new value of the branch." |
82896
f064de4f7268
Reduce nesting: Use modern backquote syntax.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82895
diff
changeset
|
101 `(aset ,node ,branch ,newval)) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
102 |
82898
e26bae3c1724
Do s/elib-avl-node/avl-tree-node/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82897
diff
changeset
|
103 (defmacro avl-tree-node-balance (node) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
104 ;; Return the balance field of a node. |
82896
f064de4f7268
Reduce nesting: Use modern backquote syntax.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82895
diff
changeset
|
105 `(aref ,node 3)) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
106 |
82898
e26bae3c1724
Do s/elib-avl-node/avl-tree-node/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82897
diff
changeset
|
107 (defmacro avl-tree-node-set-balance (node newbal) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
108 ;; Set the balance field of a node. |
82896
f064de4f7268
Reduce nesting: Use modern backquote syntax.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82895
diff
changeset
|
109 `(aset ,node 3 ,newbal)) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
110 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
111 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
112 ;;; ================================================================ |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
113 ;;; Internal functions for use in the AVL tree package |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
114 |
82899
f0fad697d0aa
Do s/elib-avl-/avl-tree-/g. Resulting changed macro and function names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82898
diff
changeset
|
115 (defmacro avl-tree-root (tree) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
116 ;; Return the root node for an avl-tree. INTERNAL USE ONLY. |
82900
0ff5cfe89663
Do s/elib-node-/avl-tree-node-/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82899
diff
changeset
|
117 `(avl-tree-node-left (car (cdr ,tree)))) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
118 |
82899
f0fad697d0aa
Do s/elib-avl-/avl-tree-/g. Resulting changed macro and function names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82898
diff
changeset
|
119 (defmacro avl-tree-dummyroot (tree) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
120 ;; Return the dummy node of an avl-tree. INTERNAL USE ONLY. |
82896
f064de4f7268
Reduce nesting: Use modern backquote syntax.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82895
diff
changeset
|
121 `(car (cdr ,tree))) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
122 |
82899
f0fad697d0aa
Do s/elib-avl-/avl-tree-/g. Resulting changed macro and function names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82898
diff
changeset
|
123 (defmacro avl-tree-cmpfun (tree) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
124 ;; Return the compare function of AVL tree TREE. INTERNAL USE ONLY. |
82896
f064de4f7268
Reduce nesting: Use modern backquote syntax.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82895
diff
changeset
|
125 `(cdr (cdr ,tree))) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
126 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
127 ;; ---------------------------------------------------------------- |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
128 ;; Deleting data |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
129 |
82899
f0fad697d0aa
Do s/elib-avl-/avl-tree-/g. Resulting changed macro and function names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82898
diff
changeset
|
130 (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
|
131 ;; Rebalance a tree and return t if the height of the tree has shrunk. |
82900
0ff5cfe89663
Do s/elib-node-/avl-tree-node-/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82899
diff
changeset
|
132 (let* ((br (avl-tree-node-branch node branch)) |
82901
18391b91e11f
Move things around; munge whitespace, indentation; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82900
diff
changeset
|
133 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
|
134 (cond |
82898
e26bae3c1724
Do s/elib-avl-node/avl-tree-node/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82897
diff
changeset
|
135 ((< (avl-tree-node-balance br) 0) |
e26bae3c1724
Do s/elib-avl-node/avl-tree-node/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82897
diff
changeset
|
136 (avl-tree-node-set-balance br 0) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
137 t) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
138 |
82898
e26bae3c1724
Do s/elib-avl-node/avl-tree-node/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82897
diff
changeset
|
139 ((= (avl-tree-node-balance br) 0) |
e26bae3c1724
Do s/elib-avl-node/avl-tree-node/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82897
diff
changeset
|
140 (avl-tree-node-set-balance br +1) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
141 nil) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
142 |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
143 (t |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
144 ;; Rebalance. |
82900
0ff5cfe89663
Do s/elib-node-/avl-tree-node-/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82899
diff
changeset
|
145 (setq p1 (avl-tree-node-right br) |
82898
e26bae3c1724
Do s/elib-avl-node/avl-tree-node/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82897
diff
changeset
|
146 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
|
147 (if (>= b1 0) |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
148 ;; Single RR rotation. |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
149 (progn |
82900
0ff5cfe89663
Do s/elib-node-/avl-tree-node-/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82899
diff
changeset
|
150 (avl-tree-node-set-right br (avl-tree-node-left p1)) |
0ff5cfe89663
Do s/elib-node-/avl-tree-node-/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82899
diff
changeset
|
151 (avl-tree-node-set-left p1 br) |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
152 (if (= 0 b1) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
153 (progn |
82898
e26bae3c1724
Do s/elib-avl-node/avl-tree-node/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82897
diff
changeset
|
154 (avl-tree-node-set-balance br +1) |
e26bae3c1724
Do s/elib-avl-node/avl-tree-node/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82897
diff
changeset
|
155 (avl-tree-node-set-balance p1 -1) |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
156 (setq result nil)) |
82898
e26bae3c1724
Do s/elib-avl-node/avl-tree-node/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82897
diff
changeset
|
157 (avl-tree-node-set-balance br 0) |
e26bae3c1724
Do s/elib-avl-node/avl-tree-node/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82897
diff
changeset
|
158 (avl-tree-node-set-balance p1 0) |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
159 (setq result t)) |
82900
0ff5cfe89663
Do s/elib-node-/avl-tree-node-/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82899
diff
changeset
|
160 (avl-tree-node-set-branch node branch p1) |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
161 result) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
162 |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
163 ;; Double RL rotation. |
82900
0ff5cfe89663
Do s/elib-node-/avl-tree-node-/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82899
diff
changeset
|
164 (setq p2 (avl-tree-node-left p1) |
82898
e26bae3c1724
Do s/elib-avl-node/avl-tree-node/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82897
diff
changeset
|
165 b2 (avl-tree-node-balance p2)) |
82900
0ff5cfe89663
Do s/elib-node-/avl-tree-node-/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82899
diff
changeset
|
166 (avl-tree-node-set-left p1 (avl-tree-node-right p2)) |
0ff5cfe89663
Do s/elib-node-/avl-tree-node-/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82899
diff
changeset
|
167 (avl-tree-node-set-right p2 p1) |
0ff5cfe89663
Do s/elib-node-/avl-tree-node-/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82899
diff
changeset
|
168 (avl-tree-node-set-right br (avl-tree-node-left p2)) |
0ff5cfe89663
Do s/elib-node-/avl-tree-node-/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82899
diff
changeset
|
169 (avl-tree-node-set-left p2 br) |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
170 (if (> b2 0) |
82898
e26bae3c1724
Do s/elib-avl-node/avl-tree-node/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82897
diff
changeset
|
171 (avl-tree-node-set-balance br -1) |
e26bae3c1724
Do s/elib-avl-node/avl-tree-node/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82897
diff
changeset
|
172 (avl-tree-node-set-balance br 0)) |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
173 (if (< b2 0) |
82898
e26bae3c1724
Do s/elib-avl-node/avl-tree-node/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82897
diff
changeset
|
174 (avl-tree-node-set-balance p1 +1) |
e26bae3c1724
Do s/elib-avl-node/avl-tree-node/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82897
diff
changeset
|
175 (avl-tree-node-set-balance p1 0)) |
82900
0ff5cfe89663
Do s/elib-node-/avl-tree-node-/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82899
diff
changeset
|
176 (avl-tree-node-set-branch node branch p2) |
82898
e26bae3c1724
Do s/elib-avl-node/avl-tree-node/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82897
diff
changeset
|
177 (avl-tree-node-set-balance p2 0) |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
178 t))))) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
179 |
82899
f0fad697d0aa
Do s/elib-avl-/avl-tree-/g. Resulting changed macro and function names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82898
diff
changeset
|
180 (defun avl-tree-del-balance2 (node branch) |
82900
0ff5cfe89663
Do s/elib-node-/avl-tree-node-/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82899
diff
changeset
|
181 (let* ((br (avl-tree-node-branch node branch)) |
82901
18391b91e11f
Move things around; munge whitespace, indentation; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82900
diff
changeset
|
182 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
|
183 (cond |
82898
e26bae3c1724
Do s/elib-avl-node/avl-tree-node/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82897
diff
changeset
|
184 ((> (avl-tree-node-balance br) 0) |
e26bae3c1724
Do s/elib-avl-node/avl-tree-node/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82897
diff
changeset
|
185 (avl-tree-node-set-balance br 0) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
186 t) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
187 |
82898
e26bae3c1724
Do s/elib-avl-node/avl-tree-node/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82897
diff
changeset
|
188 ((= (avl-tree-node-balance br) 0) |
e26bae3c1724
Do s/elib-avl-node/avl-tree-node/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82897
diff
changeset
|
189 (avl-tree-node-set-balance br -1) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
190 nil) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
191 |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
192 (t |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
193 ;; Rebalance. |
82900
0ff5cfe89663
Do s/elib-node-/avl-tree-node-/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82899
diff
changeset
|
194 (setq p1 (avl-tree-node-left br) |
82898
e26bae3c1724
Do s/elib-avl-node/avl-tree-node/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82897
diff
changeset
|
195 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
|
196 (if (<= b1 0) |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
197 ;; Single LL rotation. |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
198 (progn |
82900
0ff5cfe89663
Do s/elib-node-/avl-tree-node-/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82899
diff
changeset
|
199 (avl-tree-node-set-left br (avl-tree-node-right p1)) |
0ff5cfe89663
Do s/elib-node-/avl-tree-node-/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82899
diff
changeset
|
200 (avl-tree-node-set-right p1 br) |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
201 (if (= 0 b1) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
202 (progn |
82898
e26bae3c1724
Do s/elib-avl-node/avl-tree-node/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82897
diff
changeset
|
203 (avl-tree-node-set-balance br -1) |
e26bae3c1724
Do s/elib-avl-node/avl-tree-node/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82897
diff
changeset
|
204 (avl-tree-node-set-balance p1 +1) |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
205 (setq result nil)) |
82898
e26bae3c1724
Do s/elib-avl-node/avl-tree-node/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82897
diff
changeset
|
206 (avl-tree-node-set-balance br 0) |
e26bae3c1724
Do s/elib-avl-node/avl-tree-node/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82897
diff
changeset
|
207 (avl-tree-node-set-balance p1 0) |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
208 (setq result t)) |
82900
0ff5cfe89663
Do s/elib-node-/avl-tree-node-/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82899
diff
changeset
|
209 (avl-tree-node-set-branch node branch p1) |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
210 result) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
211 |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
212 ;; Double LR rotation. |
82900
0ff5cfe89663
Do s/elib-node-/avl-tree-node-/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82899
diff
changeset
|
213 (setq p2 (avl-tree-node-right p1) |
82898
e26bae3c1724
Do s/elib-avl-node/avl-tree-node/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82897
diff
changeset
|
214 b2 (avl-tree-node-balance p2)) |
82900
0ff5cfe89663
Do s/elib-node-/avl-tree-node-/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82899
diff
changeset
|
215 (avl-tree-node-set-right p1 (avl-tree-node-left p2)) |
0ff5cfe89663
Do s/elib-node-/avl-tree-node-/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82899
diff
changeset
|
216 (avl-tree-node-set-left p2 p1) |
0ff5cfe89663
Do s/elib-node-/avl-tree-node-/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82899
diff
changeset
|
217 (avl-tree-node-set-left br (avl-tree-node-right p2)) |
0ff5cfe89663
Do s/elib-node-/avl-tree-node-/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82899
diff
changeset
|
218 (avl-tree-node-set-right p2 br) |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
219 (if (< b2 0) |
82898
e26bae3c1724
Do s/elib-avl-node/avl-tree-node/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82897
diff
changeset
|
220 (avl-tree-node-set-balance br +1) |
e26bae3c1724
Do s/elib-avl-node/avl-tree-node/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82897
diff
changeset
|
221 (avl-tree-node-set-balance br 0)) |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
222 (if (> b2 0) |
82898
e26bae3c1724
Do s/elib-avl-node/avl-tree-node/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82897
diff
changeset
|
223 (avl-tree-node-set-balance p1 -1) |
e26bae3c1724
Do s/elib-avl-node/avl-tree-node/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82897
diff
changeset
|
224 (avl-tree-node-set-balance p1 0)) |
82900
0ff5cfe89663
Do s/elib-node-/avl-tree-node-/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82899
diff
changeset
|
225 (avl-tree-node-set-branch node branch p2) |
82898
e26bae3c1724
Do s/elib-avl-node/avl-tree-node/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82897
diff
changeset
|
226 (avl-tree-node-set-balance p2 0) |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
227 t))))) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
228 |
82899
f0fad697d0aa
Do s/elib-avl-/avl-tree-/g. Resulting changed macro and function names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82898
diff
changeset
|
229 (defun avl-tree-do-del-internal (node branch q) |
82900
0ff5cfe89663
Do s/elib-node-/avl-tree-node-/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82899
diff
changeset
|
230 (let* ((br (avl-tree-node-branch node branch))) |
0ff5cfe89663
Do s/elib-node-/avl-tree-node-/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82899
diff
changeset
|
231 (if (avl-tree-node-right br) |
82899
f0fad697d0aa
Do s/elib-avl-/avl-tree-/g. Resulting changed macro and function names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82898
diff
changeset
|
232 (if (avl-tree-do-del-internal br +1 q) |
f0fad697d0aa
Do s/elib-avl-/avl-tree-/g. Resulting changed macro and function names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82898
diff
changeset
|
233 (avl-tree-del-balance2 node branch)) |
82900
0ff5cfe89663
Do s/elib-node-/avl-tree-node-/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82899
diff
changeset
|
234 (avl-tree-node-set-data q (avl-tree-node-data br)) |
0ff5cfe89663
Do s/elib-node-/avl-tree-node-/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82899
diff
changeset
|
235 (avl-tree-node-set-branch node branch |
82901
18391b91e11f
Move things around; munge whitespace, indentation; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82900
diff
changeset
|
236 (avl-tree-node-left br)) |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
237 t))) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
238 |
82899
f0fad697d0aa
Do s/elib-avl-/avl-tree-/g. Resulting changed macro and function names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82898
diff
changeset
|
239 (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
|
240 ;; Return t if the height of the tree has shrunk. |
82900
0ff5cfe89663
Do s/elib-node-/avl-tree-node-/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82899
diff
changeset
|
241 (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
|
242 (cond |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
243 ((null br) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
244 nil) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
245 |
82900
0ff5cfe89663
Do s/elib-node-/avl-tree-node-/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82899
diff
changeset
|
246 ((funcall cmpfun data (avl-tree-node-data br)) |
82899
f0fad697d0aa
Do s/elib-avl-/avl-tree-/g. Resulting changed macro and function names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82898
diff
changeset
|
247 (if (avl-tree-do-delete cmpfun br 0 data) |
f0fad697d0aa
Do s/elib-avl-/avl-tree-/g. Resulting changed macro and function names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82898
diff
changeset
|
248 (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
|
249 |
82900
0ff5cfe89663
Do s/elib-node-/avl-tree-node-/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82899
diff
changeset
|
250 ((funcall cmpfun (avl-tree-node-data br) data) |
82899
f0fad697d0aa
Do s/elib-avl-/avl-tree-/g. Resulting changed macro and function names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82898
diff
changeset
|
251 (if (avl-tree-do-delete cmpfun br 1 data) |
f0fad697d0aa
Do s/elib-avl-/avl-tree-/g. Resulting changed macro and function names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82898
diff
changeset
|
252 (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
|
253 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
254 (t |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
255 ;; 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
|
256 (cond |
82900
0ff5cfe89663
Do s/elib-node-/avl-tree-node-/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82899
diff
changeset
|
257 ((null (avl-tree-node-right br)) |
0ff5cfe89663
Do s/elib-node-/avl-tree-node-/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82899
diff
changeset
|
258 (avl-tree-node-set-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
|
259 t) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
260 |
82900
0ff5cfe89663
Do s/elib-node-/avl-tree-node-/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82899
diff
changeset
|
261 ((null (avl-tree-node-left br)) |
0ff5cfe89663
Do s/elib-node-/avl-tree-node-/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82899
diff
changeset
|
262 (avl-tree-node-set-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
|
263 t) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
264 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
265 (t |
82899
f0fad697d0aa
Do s/elib-avl-/avl-tree-/g. Resulting changed macro and function names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82898
diff
changeset
|
266 (if (avl-tree-do-del-internal br 0 br) |
f0fad697d0aa
Do s/elib-avl-/avl-tree-/g. Resulting changed macro and function names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82898
diff
changeset
|
267 (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
|
268 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
269 ;; ---------------------------------------------------------------- |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
270 ;; Entering data |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
271 |
82899
f0fad697d0aa
Do s/elib-avl-/avl-tree-/g. Resulting changed macro and function names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82898
diff
changeset
|
272 (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
|
273 ;; Rebalance a tree and return t if the height of the tree has grown. |
82900
0ff5cfe89663
Do s/elib-node-/avl-tree-node-/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82899
diff
changeset
|
274 (let* ((br (avl-tree-node-branch node branch)) |
82901
18391b91e11f
Move things around; munge whitespace, indentation; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82900
diff
changeset
|
275 p1 p2 b2 result) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
276 (cond |
82898
e26bae3c1724
Do s/elib-avl-node/avl-tree-node/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82897
diff
changeset
|
277 ((< (avl-tree-node-balance br) 0) |
e26bae3c1724
Do s/elib-avl-node/avl-tree-node/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82897
diff
changeset
|
278 (avl-tree-node-set-balance br 0) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
279 nil) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
280 |
82898
e26bae3c1724
Do s/elib-avl-node/avl-tree-node/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82897
diff
changeset
|
281 ((= (avl-tree-node-balance br) 0) |
e26bae3c1724
Do s/elib-avl-node/avl-tree-node/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82897
diff
changeset
|
282 (avl-tree-node-set-balance br +1) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
283 t) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
284 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
285 (t |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
286 ;; Tree has grown => Rebalance. |
82900
0ff5cfe89663
Do s/elib-node-/avl-tree-node-/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82899
diff
changeset
|
287 (setq p1 (avl-tree-node-right br)) |
82898
e26bae3c1724
Do s/elib-avl-node/avl-tree-node/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82897
diff
changeset
|
288 (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
|
289 ;; Single RR rotation. |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
290 (progn |
82900
0ff5cfe89663
Do s/elib-node-/avl-tree-node-/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82899
diff
changeset
|
291 (avl-tree-node-set-right br (avl-tree-node-left p1)) |
0ff5cfe89663
Do s/elib-node-/avl-tree-node-/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82899
diff
changeset
|
292 (avl-tree-node-set-left p1 br) |
82898
e26bae3c1724
Do s/elib-avl-node/avl-tree-node/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82897
diff
changeset
|
293 (avl-tree-node-set-balance br 0) |
82900
0ff5cfe89663
Do s/elib-node-/avl-tree-node-/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82899
diff
changeset
|
294 (avl-tree-node-set-branch node branch p1)) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
295 |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
296 ;; Double RL rotation. |
82900
0ff5cfe89663
Do s/elib-node-/avl-tree-node-/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82899
diff
changeset
|
297 (setq p2 (avl-tree-node-left p1) |
82898
e26bae3c1724
Do s/elib-avl-node/avl-tree-node/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82897
diff
changeset
|
298 b2 (avl-tree-node-balance p2)) |
82900
0ff5cfe89663
Do s/elib-node-/avl-tree-node-/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82899
diff
changeset
|
299 (avl-tree-node-set-left p1 (avl-tree-node-right p2)) |
0ff5cfe89663
Do s/elib-node-/avl-tree-node-/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82899
diff
changeset
|
300 (avl-tree-node-set-right p2 p1) |
0ff5cfe89663
Do s/elib-node-/avl-tree-node-/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82899
diff
changeset
|
301 (avl-tree-node-set-right br (avl-tree-node-left p2)) |
0ff5cfe89663
Do s/elib-node-/avl-tree-node-/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82899
diff
changeset
|
302 (avl-tree-node-set-left p2 br) |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
303 (if (> b2 0) |
82898
e26bae3c1724
Do s/elib-avl-node/avl-tree-node/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82897
diff
changeset
|
304 (avl-tree-node-set-balance br -1) |
e26bae3c1724
Do s/elib-avl-node/avl-tree-node/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82897
diff
changeset
|
305 (avl-tree-node-set-balance br 0)) |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
306 (if (< b2 0) |
82898
e26bae3c1724
Do s/elib-avl-node/avl-tree-node/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82897
diff
changeset
|
307 (avl-tree-node-set-balance p1 +1) |
e26bae3c1724
Do s/elib-avl-node/avl-tree-node/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82897
diff
changeset
|
308 (avl-tree-node-set-balance p1 0)) |
82900
0ff5cfe89663
Do s/elib-node-/avl-tree-node-/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82899
diff
changeset
|
309 (avl-tree-node-set-branch node branch p2)) |
0ff5cfe89663
Do s/elib-node-/avl-tree-node-/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82899
diff
changeset
|
310 (avl-tree-node-set-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
|
311 nil)))) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
312 |
82899
f0fad697d0aa
Do s/elib-avl-/avl-tree-/g. Resulting changed macro and function names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82898
diff
changeset
|
313 (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
|
314 ;; Return t if the tree has grown. |
82900
0ff5cfe89663
Do s/elib-node-/avl-tree-node-/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82899
diff
changeset
|
315 (let* ((br (avl-tree-node-branch node branch)) |
82901
18391b91e11f
Move things around; munge whitespace, indentation; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82900
diff
changeset
|
316 p1 p2 b2) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
317 (cond |
82898
e26bae3c1724
Do s/elib-avl-node/avl-tree-node/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82897
diff
changeset
|
318 ((> (avl-tree-node-balance br) 0) |
e26bae3c1724
Do s/elib-avl-node/avl-tree-node/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82897
diff
changeset
|
319 (avl-tree-node-set-balance br 0) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
320 nil) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
321 |
82898
e26bae3c1724
Do s/elib-avl-node/avl-tree-node/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82897
diff
changeset
|
322 ((= (avl-tree-node-balance br) 0) |
e26bae3c1724
Do s/elib-avl-node/avl-tree-node/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82897
diff
changeset
|
323 (avl-tree-node-set-balance br -1) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
324 t) |
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 (t |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
327 ;; Balance was -1 => Rebalance. |
82900
0ff5cfe89663
Do s/elib-node-/avl-tree-node-/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82899
diff
changeset
|
328 (setq p1 (avl-tree-node-left br)) |
82898
e26bae3c1724
Do s/elib-avl-node/avl-tree-node/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82897
diff
changeset
|
329 (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
|
330 ;; Single LL rotation. |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
331 (progn |
82900
0ff5cfe89663
Do s/elib-node-/avl-tree-node-/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82899
diff
changeset
|
332 (avl-tree-node-set-left br (avl-tree-node-right p1)) |
0ff5cfe89663
Do s/elib-node-/avl-tree-node-/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82899
diff
changeset
|
333 (avl-tree-node-set-right p1 br) |
82898
e26bae3c1724
Do s/elib-avl-node/avl-tree-node/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82897
diff
changeset
|
334 (avl-tree-node-set-balance br 0) |
82900
0ff5cfe89663
Do s/elib-node-/avl-tree-node-/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82899
diff
changeset
|
335 (avl-tree-node-set-branch node branch p1)) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
336 |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
337 ;; Double LR rotation. |
82900
0ff5cfe89663
Do s/elib-node-/avl-tree-node-/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82899
diff
changeset
|
338 (setq p2 (avl-tree-node-right p1) |
82898
e26bae3c1724
Do s/elib-avl-node/avl-tree-node/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82897
diff
changeset
|
339 b2 (avl-tree-node-balance p2)) |
82900
0ff5cfe89663
Do s/elib-node-/avl-tree-node-/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82899
diff
changeset
|
340 (avl-tree-node-set-right p1 (avl-tree-node-left p2)) |
0ff5cfe89663
Do s/elib-node-/avl-tree-node-/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82899
diff
changeset
|
341 (avl-tree-node-set-left p2 p1) |
0ff5cfe89663
Do s/elib-node-/avl-tree-node-/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82899
diff
changeset
|
342 (avl-tree-node-set-left br (avl-tree-node-right p2)) |
0ff5cfe89663
Do s/elib-node-/avl-tree-node-/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82899
diff
changeset
|
343 (avl-tree-node-set-right p2 br) |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
344 (if (< b2 0) |
82898
e26bae3c1724
Do s/elib-avl-node/avl-tree-node/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82897
diff
changeset
|
345 (avl-tree-node-set-balance br +1) |
e26bae3c1724
Do s/elib-avl-node/avl-tree-node/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82897
diff
changeset
|
346 (avl-tree-node-set-balance br 0)) |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
347 (if (> b2 0) |
82898
e26bae3c1724
Do s/elib-avl-node/avl-tree-node/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82897
diff
changeset
|
348 (avl-tree-node-set-balance p1 -1) |
e26bae3c1724
Do s/elib-avl-node/avl-tree-node/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82897
diff
changeset
|
349 (avl-tree-node-set-balance p1 0)) |
82900
0ff5cfe89663
Do s/elib-node-/avl-tree-node-/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82899
diff
changeset
|
350 (avl-tree-node-set-branch node branch p2)) |
0ff5cfe89663
Do s/elib-node-/avl-tree-node-/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82899
diff
changeset
|
351 (avl-tree-node-set-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
|
352 nil)))) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
353 |
82899
f0fad697d0aa
Do s/elib-avl-/avl-tree-/g. Resulting changed macro and function names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82898
diff
changeset
|
354 (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
|
355 ;; Return t if height of tree ROOT has grown. INTERNAL USE ONLY. |
82900
0ff5cfe89663
Do s/elib-node-/avl-tree-node-/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82899
diff
changeset
|
356 (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
|
357 (cond |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
358 ((null br) |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
359 ;; Data not in tree, insert it. |
82901
18391b91e11f
Move things around; munge whitespace, indentation; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82900
diff
changeset
|
360 (avl-tree-node-set-branch |
18391b91e11f
Move things around; munge whitespace, indentation; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82900
diff
changeset
|
361 root branch (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
|
362 t) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
363 |
82900
0ff5cfe89663
Do s/elib-node-/avl-tree-node-/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82899
diff
changeset
|
364 ((funcall cmpfun data (avl-tree-node-data br)) |
82901
18391b91e11f
Move things around; munge whitespace, indentation; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82900
diff
changeset
|
365 (and (avl-tree-do-enter cmpfun br 0 data) |
82899
f0fad697d0aa
Do s/elib-avl-/avl-tree-/g. Resulting changed macro and function names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82898
diff
changeset
|
366 (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
|
367 |
82900
0ff5cfe89663
Do s/elib-node-/avl-tree-node-/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82899
diff
changeset
|
368 ((funcall cmpfun (avl-tree-node-data br) data) |
82901
18391b91e11f
Move things around; munge whitespace, indentation; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82900
diff
changeset
|
369 (and (avl-tree-do-enter cmpfun br 1 data) |
82899
f0fad697d0aa
Do s/elib-avl-/avl-tree-/g. Resulting changed macro and function names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82898
diff
changeset
|
370 (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
|
371 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
372 (t |
82900
0ff5cfe89663
Do s/elib-node-/avl-tree-node-/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82899
diff
changeset
|
373 (avl-tree-node-set-data br data) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
374 nil)))) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
375 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
376 ;; ---------------------------------------------------------------- |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
377 |
82899
f0fad697d0aa
Do s/elib-avl-/avl-tree-/g. Resulting changed macro and function names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82898
diff
changeset
|
378 (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
|
379 ;; 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
|
380 ;; 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
|
381 ;; |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
382 ;; 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
|
383 ;; INTERNAL USE ONLY. |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
384 (let ((node root) |
82893 | 385 (stack nil) |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
386 (go-left t)) |
82893 | 387 (push nil stack) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
388 (while node |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
389 (if (and go-left |
82900
0ff5cfe89663
Do s/elib-node-/avl-tree-node-/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82899
diff
changeset
|
390 (avl-tree-node-left node)) |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
391 ;; Do the left subtree first. |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
392 (progn |
82893 | 393 (push node stack) |
82900
0ff5cfe89663
Do s/elib-node-/avl-tree-node-/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82899
diff
changeset
|
394 (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
|
395 ;; Apply the function... |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
396 (funcall map-function node) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
397 ;; and do the right subtree. |
82900
0ff5cfe89663
Do s/elib-node-/avl-tree-node-/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82899
diff
changeset
|
398 (if (avl-tree-node-right node) |
0ff5cfe89663
Do s/elib-node-/avl-tree-node-/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82899
diff
changeset
|
399 (setq node (avl-tree-node-right node) |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
400 go-left t) |
82893 | 401 (setq node (pop stack) |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
402 go-left nil)))))) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
403 |
82899
f0fad697d0aa
Do s/elib-avl-/avl-tree-/g. Resulting changed macro and function names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82898
diff
changeset
|
404 (defun avl-tree-do-copy (root) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
405 ;; Copy the tree with ROOT as root. |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
406 ;; Highly recursive. INTERNAL USE ONLY. |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
407 (if (null root) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
408 nil |
82901
18391b91e11f
Move things around; munge whitespace, indentation; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82900
diff
changeset
|
409 (avl-tree-node-create |
18391b91e11f
Move things around; munge whitespace, indentation; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82900
diff
changeset
|
410 (avl-tree-do-copy (avl-tree-node-left root)) |
18391b91e11f
Move things around; munge whitespace, indentation; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82900
diff
changeset
|
411 (avl-tree-do-copy (avl-tree-node-right root)) |
18391b91e11f
Move things around; munge whitespace, indentation; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82900
diff
changeset
|
412 (avl-tree-node-data root) |
18391b91e11f
Move things around; munge whitespace, indentation; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82900
diff
changeset
|
413 (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
|
414 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
415 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
416 ;;; ================================================================ |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
417 ;;; The public functions which operate on AVL trees. |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
418 |
82895
3b4dacb1e48c
Do s/avltree/avl-tree/g. Resulting changed function names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82894
diff
changeset
|
419 (defun avl-tree-create (compare-function) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
420 "Create an empty avl tree. |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
421 COMPARE-FUNCTION is a function which takes two arguments, A and B, |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
422 and returns non-nil if A is less than B, and nil otherwise." |
82895
3b4dacb1e48c
Do s/avltree/avl-tree/g. Resulting changed function names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82894
diff
changeset
|
423 (cons 'AVL-TREE |
82898
e26bae3c1724
Do s/elib-avl-node/avl-tree-node/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82897
diff
changeset
|
424 (cons (avl-tree-node-create nil nil nil 0) |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
425 compare-function))) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
426 |
82895
3b4dacb1e48c
Do s/avltree/avl-tree/g. Resulting changed function names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82894
diff
changeset
|
427 (defun avl-tree-p (obj) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
428 "Return t if OBJ is an avl tree, nil otherwise." |
82895
3b4dacb1e48c
Do s/avltree/avl-tree/g. Resulting changed function names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82894
diff
changeset
|
429 (eq (car-safe obj) 'AVL-TREE)) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
430 |
82895
3b4dacb1e48c
Do s/avltree/avl-tree/g. Resulting changed function names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82894
diff
changeset
|
431 (defun avl-tree-compare-function (tree) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
432 "Return the comparision function for the avl tree TREE." |
82899
f0fad697d0aa
Do s/elib-avl-/avl-tree-/g. Resulting changed macro and function names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82898
diff
changeset
|
433 (avl-tree-cmpfun tree)) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
434 |
82895
3b4dacb1e48c
Do s/avltree/avl-tree/g. Resulting changed function names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82894
diff
changeset
|
435 (defun avl-tree-empty (tree) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
436 "Return t if TREE is emtpy, otherwise return nil." |
82899
f0fad697d0aa
Do s/elib-avl-/avl-tree-/g. Resulting changed macro and function names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82898
diff
changeset
|
437 (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
|
438 |
82895
3b4dacb1e48c
Do s/avltree/avl-tree/g. Resulting changed function names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82894
diff
changeset
|
439 (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
|
440 "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
|
441 Return DATA." |
82899
f0fad697d0aa
Do s/elib-avl-/avl-tree-/g. Resulting changed macro and function names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82898
diff
changeset
|
442 (avl-tree-do-enter (avl-tree-cmpfun tree) |
f0fad697d0aa
Do s/elib-avl-/avl-tree-/g. Resulting changed macro and function names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82898
diff
changeset
|
443 (avl-tree-dummyroot tree) |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
444 0 |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
445 data) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
446 data) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
447 |
82895
3b4dacb1e48c
Do s/avltree/avl-tree/g. Resulting changed function names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82894
diff
changeset
|
448 (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
|
449 "From the avl tree TREE, delete DATA. |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
450 Return the element in TREE which matched DATA, nil if no element matched." |
82899
f0fad697d0aa
Do s/elib-avl-/avl-tree-/g. Resulting changed macro and function names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82898
diff
changeset
|
451 (avl-tree-do-delete (avl-tree-cmpfun tree) |
f0fad697d0aa
Do s/elib-avl-/avl-tree-/g. Resulting changed macro and function names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82898
diff
changeset
|
452 (avl-tree-dummyroot tree) |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
453 0 |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
454 data)) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
455 |
82895
3b4dacb1e48c
Do s/avltree/avl-tree/g. Resulting changed function names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82894
diff
changeset
|
456 (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
|
457 "Return the element in the avl tree TREE which matches DATA. |
82895
3b4dacb1e48c
Do s/avltree/avl-tree/g. Resulting changed function names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82894
diff
changeset
|
458 Matching uses the compare function previously specified in `avl-tree-create' |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
459 when TREE was created. |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
460 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
461 If there is no such element in the tree, the value is nil." |
82899
f0fad697d0aa
Do s/elib-avl-/avl-tree-/g. Resulting changed macro and function names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82898
diff
changeset
|
462 (let ((node (avl-tree-root tree)) |
f0fad697d0aa
Do s/elib-avl-/avl-tree-/g. Resulting changed macro and function names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82898
diff
changeset
|
463 (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
|
464 found) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
465 (while (and node |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
466 (not found)) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
467 (cond |
82900
0ff5cfe89663
Do s/elib-node-/avl-tree-node-/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82899
diff
changeset
|
468 ((funcall compare-function data (avl-tree-node-data node)) |
0ff5cfe89663
Do s/elib-node-/avl-tree-node-/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82899
diff
changeset
|
469 (setq node (avl-tree-node-left node))) |
0ff5cfe89663
Do s/elib-node-/avl-tree-node-/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82899
diff
changeset
|
470 ((funcall compare-function (avl-tree-node-data node) data) |
0ff5cfe89663
Do s/elib-node-/avl-tree-node-/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82899
diff
changeset
|
471 (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
|
472 (t |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
473 (setq found t)))) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
474 (if node |
82900
0ff5cfe89663
Do s/elib-node-/avl-tree-node-/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82899
diff
changeset
|
475 (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
|
476 nil))) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
477 |
82895
3b4dacb1e48c
Do s/avltree/avl-tree/g. Resulting changed function names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82894
diff
changeset
|
478 (defun avl-tree-map (__map-function__ tree) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
479 "Apply MAP-FUNCTION to all elements in the avl tree TREE." |
82899
f0fad697d0aa
Do s/elib-avl-/avl-tree-/g. Resulting changed macro and function names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82898
diff
changeset
|
480 (avl-tree-mapc |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
481 (function (lambda (node) |
82901
18391b91e11f
Move things around; munge whitespace, indentation; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82900
diff
changeset
|
482 (avl-tree-node-set-data |
18391b91e11f
Move things around; munge whitespace, indentation; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82900
diff
changeset
|
483 node (funcall __map-function__ |
18391b91e11f
Move things around; munge whitespace, indentation; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82900
diff
changeset
|
484 (avl-tree-node-data node))))) |
82899
f0fad697d0aa
Do s/elib-avl-/avl-tree-/g. Resulting changed macro and function names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82898
diff
changeset
|
485 (avl-tree-root tree))) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
486 |
82895
3b4dacb1e48c
Do s/avltree/avl-tree/g. Resulting changed function names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82894
diff
changeset
|
487 (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
|
488 "Return the first element in TREE, or nil if TREE is empty." |
82899
f0fad697d0aa
Do s/elib-avl-/avl-tree-/g. Resulting changed macro and function names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82898
diff
changeset
|
489 (let ((node (avl-tree-root tree))) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
490 (if node |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
491 (progn |
82900
0ff5cfe89663
Do s/elib-node-/avl-tree-node-/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82899
diff
changeset
|
492 (while (avl-tree-node-left node) |
0ff5cfe89663
Do s/elib-node-/avl-tree-node-/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82899
diff
changeset
|
493 (setq node (avl-tree-node-left node))) |
0ff5cfe89663
Do s/elib-node-/avl-tree-node-/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82899
diff
changeset
|
494 (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
|
495 nil))) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
496 |
82895
3b4dacb1e48c
Do s/avltree/avl-tree/g. Resulting changed function names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82894
diff
changeset
|
497 (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
|
498 "Return the last element in TREE, or nil if TREE is empty." |
82899
f0fad697d0aa
Do s/elib-avl-/avl-tree-/g. Resulting changed macro and function names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82898
diff
changeset
|
499 (let ((node (avl-tree-root tree))) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
500 (if node |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
501 (progn |
82900
0ff5cfe89663
Do s/elib-node-/avl-tree-node-/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82899
diff
changeset
|
502 (while (avl-tree-node-right node) |
0ff5cfe89663
Do s/elib-node-/avl-tree-node-/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82899
diff
changeset
|
503 (setq node (avl-tree-node-right node))) |
0ff5cfe89663
Do s/elib-node-/avl-tree-node-/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82899
diff
changeset
|
504 (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
|
505 nil))) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
506 |
82895
3b4dacb1e48c
Do s/avltree/avl-tree/g. Resulting changed function names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82894
diff
changeset
|
507 (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
|
508 "Return a copy of the avl tree TREE." |
82901
18391b91e11f
Move things around; munge whitespace, indentation; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82900
diff
changeset
|
509 (let ((new-tree (avl-tree-create (avl-tree-cmpfun tree)))) |
82900
0ff5cfe89663
Do s/elib-node-/avl-tree-node-/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82899
diff
changeset
|
510 (avl-tree-node-set-left (avl-tree-dummyroot new-tree) |
82901
18391b91e11f
Move things around; munge whitespace, indentation; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82900
diff
changeset
|
511 (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
|
512 new-tree)) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
513 |
82895
3b4dacb1e48c
Do s/avltree/avl-tree/g. Resulting changed function names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82894
diff
changeset
|
514 (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
|
515 "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
|
516 (nreverse |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
517 (let ((treelist nil)) |
82901
18391b91e11f
Move things around; munge whitespace, indentation; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82900
diff
changeset
|
518 (avl-tree-mapc |
18391b91e11f
Move things around; munge whitespace, indentation; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82900
diff
changeset
|
519 (function (lambda (node) |
18391b91e11f
Move things around; munge whitespace, indentation; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82900
diff
changeset
|
520 (setq treelist (cons (avl-tree-node-data node) |
18391b91e11f
Move things around; munge whitespace, indentation; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82900
diff
changeset
|
521 treelist)))) |
18391b91e11f
Move things around; munge whitespace, indentation; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82900
diff
changeset
|
522 (avl-tree-root tree)) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
523 treelist))) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
524 |
82895
3b4dacb1e48c
Do s/avltree/avl-tree/g. Resulting changed function names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82894
diff
changeset
|
525 (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
|
526 "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
|
527 (let ((treesize 0)) |
82901
18391b91e11f
Move things around; munge whitespace, indentation; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82900
diff
changeset
|
528 (avl-tree-mapc |
18391b91e11f
Move things around; munge whitespace, indentation; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82900
diff
changeset
|
529 (function (lambda (data) |
18391b91e11f
Move things around; munge whitespace, indentation; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82900
diff
changeset
|
530 (setq treesize (1+ treesize)) |
18391b91e11f
Move things around; munge whitespace, indentation; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82900
diff
changeset
|
531 data)) |
18391b91e11f
Move things around; munge whitespace, indentation; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82900
diff
changeset
|
532 (avl-tree-root tree)) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
533 treesize)) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
534 |
82895
3b4dacb1e48c
Do s/avltree/avl-tree/g. Resulting changed function names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82894
diff
changeset
|
535 (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
|
536 "Clear the avl tree TREE." |
82900
0ff5cfe89663
Do s/elib-node-/avl-tree-node-/g. Resulting changed macro names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82899
diff
changeset
|
537 (avl-tree-node-set-left (avl-tree-dummyroot tree) nil)) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
538 |
82892
8ce807303185
Move provide form to end; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82891
diff
changeset
|
539 (provide 'avl-tree) |
8ce807303185
Move provide form to end; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82891
diff
changeset
|
540 |
82894 | 541 ;; 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
|
542 ;;; avl-tree.el ends here |