Mercurial > emacs
annotate lisp/emacs-lisp/avl-tree.el @ 82894:dbd7c4bc480e
Add arch tagline
author | Miles Bader <miles@gnu.org> |
---|---|
date | Mon, 27 Aug 2007 01:42:03 +0000 |
parents | 2321b585ebdd |
children | 3b4dacb1e48c |
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 |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
46 ;; 'AVLTREE in the car cell, and the second one having the tree |
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 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
57 (defmacro elib-node-create (left right data) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
58 ;; Create a tree node from LEFT, RIGHT and DATA. |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
59 (` (vector (, left) (, right) (, data)))) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
60 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
61 (defmacro elib-node-left (node) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
62 ;; Return the left pointer of NODE. |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
63 (` (aref (, node) 0))) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
64 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
65 (defmacro elib-node-right (node) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
66 ;; Return the right pointer of NODE. |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
67 (` (aref (, node) 1))) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
68 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
69 (defmacro elib-node-data (node) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
70 ;; Return the data of NODE. |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
71 (` (aref (, node) 2))) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
72 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
73 (defmacro elib-node-set-left (node newleft) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
74 ;; Set the left pointer of NODE to NEWLEFT. |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
75 (` (aset (, node) 0 (, newleft)))) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
76 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
77 (defmacro elib-node-set-right (node newright) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
78 ;; Set the right pointer of NODE to NEWRIGHT. |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
79 (` (aset (, node) 1 (, newright)))) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
80 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
81 (defmacro elib-node-set-data (node newdata) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
82 ;; Set the data of NODE to NEWDATA. |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
83 (` (aset (, node) 2 (, newdata)))) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
84 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
85 (defmacro elib-node-branch (node branch) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
86 ;; 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
|
87 ;; |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
88 ;; 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
|
89 ;; 0 for left pointer, 1 for 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
|
90 (` (aref (, node) (, branch)))) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
91 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
92 (defmacro elib-node-set-branch (node branch newval) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
93 ;; 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
|
94 ;; |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
95 ;; 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
|
96 ;; 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
|
97 ;; NEWVAL is new value of the branch." |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
98 (` (aset (, node) (, branch) (, newval)))) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
99 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
100 ;;; ================================================================ |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
101 ;;; Functions and macros handling an AVL tree node. |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
102 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
103 (defmacro elib-avl-node-create (left right data balance) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
104 ;; Create and return an avl-tree node. |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
105 (` (vector (, left) (, right) (, data) (, balance)))) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
106 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
107 (defmacro elib-avl-node-balance (node) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
108 ;; Return the balance field of a node. |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
109 (` (aref (, node) 3))) |
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 (defmacro elib-avl-node-set-balance (node newbal) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
112 ;; Set the balance field of a node. |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
113 (` (aset (, node) 3 (, newbal)))) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
114 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
115 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
116 ;;; ================================================================ |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
117 ;;; 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
|
118 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
119 ;;; |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
120 ;;; The functions and macros in this section all start with `elib-avl-'. |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
121 ;;; |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
122 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
123 (defmacro elib-avl-root (tree) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
124 ;; Return the root node for an avl-tree. INTERNAL USE ONLY. |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
125 (` (elib-node-left (car (cdr (, tree)))))) |
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 (defmacro elib-avl-dummyroot (tree) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
128 ;; Return the dummy node of an avl-tree. INTERNAL USE ONLY. |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
129 (` (car (cdr (, tree))))) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
130 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
131 (defmacro elib-avl-cmpfun (tree) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
132 ;; Return the compare function of AVL tree TREE. INTERNAL USE ONLY. |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
133 (` (cdr (cdr (, tree))))) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
134 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
135 ;; ---------------------------------------------------------------- |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
136 ;; Deleting data |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
137 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
138 (defun elib-avl-del-balance1 (node branch) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
139 ;; Rebalance a tree and return t if the height of the tree has shrunk. |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
140 (let* ((br (elib-node-branch node branch)) |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
141 p1 |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
142 b1 |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
143 p2 |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
144 b2 |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
145 result) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
146 (cond |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
147 ((< (elib-avl-node-balance br) 0) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
148 (elib-avl-node-set-balance br 0) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
149 t) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
150 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
151 ((= (elib-avl-node-balance br) 0) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
152 (elib-avl-node-set-balance br +1) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
153 nil) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
154 |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
155 (t |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
156 ;; Rebalance. |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
157 (setq p1 (elib-node-right br) |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
158 b1 (elib-avl-node-balance p1)) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
159 (if (>= b1 0) |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
160 ;; Single RR rotation. |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
161 (progn |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
162 (elib-node-set-right br (elib-node-left p1)) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
163 (elib-node-set-left p1 br) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
164 (if (= 0 b1) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
165 (progn |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
166 (elib-avl-node-set-balance br +1) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
167 (elib-avl-node-set-balance p1 -1) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
168 (setq result nil)) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
169 (elib-avl-node-set-balance br 0) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
170 (elib-avl-node-set-balance p1 0) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
171 (setq result t)) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
172 (elib-node-set-branch node branch p1) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
173 result) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
174 |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
175 ;; Double RL rotation. |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
176 (setq p2 (elib-node-left p1) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
177 b2 (elib-avl-node-balance p2)) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
178 (elib-node-set-left p1 (elib-node-right p2)) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
179 (elib-node-set-right p2 p1) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
180 (elib-node-set-right br (elib-node-left p2)) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
181 (elib-node-set-left p2 br) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
182 (if (> b2 0) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
183 (elib-avl-node-set-balance br -1) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
184 (elib-avl-node-set-balance br 0)) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
185 (if (< b2 0) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
186 (elib-avl-node-set-balance p1 +1) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
187 (elib-avl-node-set-balance p1 0)) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
188 (elib-node-set-branch node branch p2) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
189 (elib-avl-node-set-balance p2 0) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
190 t))))) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
191 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
192 (defun elib-avl-del-balance2 (node branch) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
193 (let* ((br (elib-node-branch node branch)) |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
194 p1 |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
195 b1 |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
196 p2 |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
197 b2 |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
198 result) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
199 (cond |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
200 ((> (elib-avl-node-balance br) 0) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
201 (elib-avl-node-set-balance br 0) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
202 t) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
203 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
204 ((= (elib-avl-node-balance br) 0) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
205 (elib-avl-node-set-balance br -1) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
206 nil) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
207 |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
208 (t |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
209 ;; Rebalance. |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
210 (setq p1 (elib-node-left br) |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
211 b1 (elib-avl-node-balance p1)) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
212 (if (<= b1 0) |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
213 ;; Single LL rotation. |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
214 (progn |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
215 (elib-node-set-left br (elib-node-right p1)) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
216 (elib-node-set-right p1 br) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
217 (if (= 0 b1) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
218 (progn |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
219 (elib-avl-node-set-balance br -1) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
220 (elib-avl-node-set-balance p1 +1) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
221 (setq result nil)) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
222 (elib-avl-node-set-balance br 0) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
223 (elib-avl-node-set-balance p1 0) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
224 (setq result t)) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
225 (elib-node-set-branch node branch p1) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
226 result) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
227 |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
228 ;; Double LR rotation. |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
229 (setq p2 (elib-node-right p1) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
230 b2 (elib-avl-node-balance p2)) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
231 (elib-node-set-right p1 (elib-node-left p2)) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
232 (elib-node-set-left p2 p1) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
233 (elib-node-set-left br (elib-node-right p2)) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
234 (elib-node-set-right p2 br) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
235 (if (< b2 0) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
236 (elib-avl-node-set-balance br +1) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
237 (elib-avl-node-set-balance br 0)) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
238 (if (> b2 0) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
239 (elib-avl-node-set-balance p1 -1) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
240 (elib-avl-node-set-balance p1 0)) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
241 (elib-node-set-branch node branch p2) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
242 (elib-avl-node-set-balance p2 0) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
243 t))))) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
244 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
245 (defun elib-avl-do-del-internal (node branch q) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
246 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
247 (let* ((br (elib-node-branch node branch))) |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
248 (if (elib-node-right br) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
249 (if (elib-avl-do-del-internal br +1 q) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
250 (elib-avl-del-balance2 node branch)) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
251 (elib-node-set-data q (elib-node-data br)) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
252 (elib-node-set-branch node branch |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
253 (elib-node-left br)) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
254 t))) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
255 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
256 (defun elib-avl-do-delete (cmpfun root branch data) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
257 ;; Return t if the height of the tree has shrunk. |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
258 (let* ((br (elib-node-branch root branch))) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
259 (cond |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
260 ((null br) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
261 nil) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
262 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
263 ((funcall cmpfun data (elib-node-data br)) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
264 (if (elib-avl-do-delete cmpfun br 0 data) |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
265 (elib-avl-del-balance1 root branch))) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
266 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
267 ((funcall cmpfun (elib-node-data br) data) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
268 (if (elib-avl-do-delete cmpfun br 1 data) |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
269 (elib-avl-del-balance2 root branch))) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
270 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
271 (t |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
272 ;; 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
|
273 (cond |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
274 ((null (elib-node-right br)) |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
275 (elib-node-set-branch root branch (elib-node-left br)) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
276 t) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
277 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
278 ((null (elib-node-left br)) |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
279 (elib-node-set-branch root branch (elib-node-right br)) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
280 t) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
281 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
282 (t |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
283 (if (elib-avl-do-del-internal br 0 br) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
284 (elib-avl-del-balance1 root branch)))))))) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
285 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
286 ;; ---------------------------------------------------------------- |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
287 ;; Entering data |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
288 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
289 (defun elib-avl-enter-balance1 (node branch) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
290 ;; Rebalance a tree and return t if the height of the tree has grown. |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
291 (let* ((br (elib-node-branch node branch)) |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
292 p1 |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
293 p2 |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
294 b2 |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
295 result) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
296 (cond |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
297 ((< (elib-avl-node-balance br) 0) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
298 (elib-avl-node-set-balance br 0) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
299 nil) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
300 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
301 ((= (elib-avl-node-balance br) 0) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
302 (elib-avl-node-set-balance br +1) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
303 t) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
304 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
305 (t |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
306 ;; Tree has grown => Rebalance. |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
307 (setq p1 (elib-node-right br)) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
308 (if (> (elib-avl-node-balance p1) 0) |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
309 ;; Single RR rotation. |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
310 (progn |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
311 (elib-node-set-right br (elib-node-left p1)) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
312 (elib-node-set-left p1 br) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
313 (elib-avl-node-set-balance br 0) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
314 (elib-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
|
315 |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
316 ;; Double RL rotation. |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
317 (setq p2 (elib-node-left p1) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
318 b2 (elib-avl-node-balance p2)) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
319 (elib-node-set-left p1 (elib-node-right p2)) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
320 (elib-node-set-right p2 p1) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
321 (elib-node-set-right br (elib-node-left p2)) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
322 (elib-node-set-left p2 br) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
323 (if (> b2 0) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
324 (elib-avl-node-set-balance br -1) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
325 (elib-avl-node-set-balance br 0)) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
326 (if (< b2 0) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
327 (elib-avl-node-set-balance p1 +1) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
328 (elib-avl-node-set-balance p1 0)) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
329 (elib-node-set-branch node branch p2)) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
330 (elib-avl-node-set-balance (elib-node-branch node branch) 0) |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
331 nil)))) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
332 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
333 (defun elib-avl-enter-balance2 (node branch) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
334 ;; Return t if the tree has grown. |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
335 (let* ((br (elib-node-branch node branch)) |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
336 p1 |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
337 p2 |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
338 b2) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
339 (cond |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
340 ((> (elib-avl-node-balance br) 0) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
341 (elib-avl-node-set-balance br 0) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
342 nil) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
343 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
344 ((= (elib-avl-node-balance br) 0) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
345 (elib-avl-node-set-balance br -1) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
346 t) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
347 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
348 (t |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
349 ;; Balance was -1 => Rebalance. |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
350 (setq p1 (elib-node-left br)) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
351 (if (< (elib-avl-node-balance p1) 0) |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
352 ;; Single LL rotation. |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
353 (progn |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
354 (elib-node-set-left br (elib-node-right p1)) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
355 (elib-node-set-right p1 br) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
356 (elib-avl-node-set-balance br 0) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
357 (elib-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
|
358 |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
359 ;; Double LR rotation. |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
360 (setq p2 (elib-node-right p1) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
361 b2 (elib-avl-node-balance p2)) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
362 (elib-node-set-right p1 (elib-node-left p2)) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
363 (elib-node-set-left p2 p1) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
364 (elib-node-set-left br (elib-node-right p2)) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
365 (elib-node-set-right p2 br) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
366 (if (< b2 0) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
367 (elib-avl-node-set-balance br +1) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
368 (elib-avl-node-set-balance br 0)) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
369 (if (> b2 0) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
370 (elib-avl-node-set-balance p1 -1) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
371 (elib-avl-node-set-balance p1 0)) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
372 (elib-node-set-branch node branch p2)) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
373 (elib-avl-node-set-balance (elib-node-branch node branch) 0) |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
374 nil)))) |
82890
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 (defun elib-avl-do-enter (cmpfun root branch data) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
377 ;; Return t if height of tree ROOT has grown. INTERNAL USE ONLY. |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
378 (let ((br (elib-node-branch root branch))) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
379 (cond |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
380 ((null br) |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
381 ;; Data not in tree, insert it. |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
382 (elib-node-set-branch root branch |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
383 (elib-avl-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
|
384 t) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
385 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
386 ((funcall cmpfun data (elib-node-data br)) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
387 (and (elib-avl-do-enter cmpfun |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
388 br |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
389 0 data) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
390 (elib-avl-enter-balance2 root branch))) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
391 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
392 ((funcall cmpfun (elib-node-data br) data) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
393 (and (elib-avl-do-enter cmpfun |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
394 br |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
395 1 data) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
396 (elib-avl-enter-balance1 root branch))) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
397 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
398 (t |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
399 (elib-node-set-data br data) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
400 nil)))) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
401 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
402 ;; ---------------------------------------------------------------- |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
403 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
404 (defun elib-avl-mapc (map-function root) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
405 ;; 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
|
406 ;; 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
|
407 ;; |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
408 ;; 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
|
409 ;; INTERNAL USE ONLY. |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
410 (let ((node root) |
82893 | 411 (stack nil) |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
412 (go-left t)) |
82893 | 413 (push nil stack) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
414 (while node |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
415 (if (and go-left |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
416 (elib-node-left node)) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
417 ;; Do the left subtree first. |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
418 (progn |
82893 | 419 (push node stack) |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
420 (setq node (elib-node-left node))) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
421 ;; Apply the function... |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
422 (funcall map-function node) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
423 ;; and do the right subtree. |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
424 (if (elib-node-right node) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
425 (setq node (elib-node-right node) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
426 go-left t) |
82893 | 427 (setq node (pop stack) |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
428 go-left nil)))))) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
429 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
430 (defun elib-avl-do-copy (root) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
431 ;; 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
|
432 ;; Highly recursive. INTERNAL USE ONLY. |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
433 (if (null root) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
434 nil |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
435 (elib-avl-node-create (elib-avl-do-copy (elib-node-left root)) |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
436 (elib-avl-do-copy (elib-node-right root)) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
437 (elib-node-data root) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
438 (elib-avl-node-balance root)))) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
439 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
440 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
441 ;;; ================================================================ |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
442 ;;; 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
|
443 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
444 (defun avltree-create (compare-function) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
445 "Create an empty avl tree. |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
446 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
|
447 and returns non-nil if A is less than B, and nil otherwise." |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
448 (cons 'AVLTREE |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
449 (cons (elib-avl-node-create nil nil nil 0) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
450 compare-function))) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
451 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
452 (defun avltree-p (obj) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
453 "Return t if OBJ is an avl tree, nil otherwise." |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
454 (eq (car-safe obj) 'AVLTREE)) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
455 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
456 (defun avltree-compare-function (tree) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
457 "Return the comparision function for the avl tree TREE." |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
458 (elib-avl-cmpfun tree)) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
459 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
460 (defun avltree-empty (tree) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
461 "Return t if TREE is emtpy, otherwise return nil." |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
462 (null (elib-avl-root tree))) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
463 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
464 (defun avltree-enter (tree data) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
465 "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
|
466 Return DATA." |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
467 (elib-avl-do-enter (elib-avl-cmpfun tree) |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
468 (elib-avl-dummyroot tree) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
469 0 |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
470 data) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
471 data) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
472 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
473 (defun avltree-delete (tree data) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
474 "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
|
475 Return the element in TREE which matched DATA, nil if no element matched." |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
476 (elib-avl-do-delete (elib-avl-cmpfun tree) |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
477 (elib-avl-dummyroot tree) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
478 0 |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
479 data)) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
480 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
481 (defun avltree-member (tree data) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
482 "Return the element in the avl tree TREE which matches DATA. |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
483 Matching uses the compare function previously specified in `avltree-create' |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
484 when TREE was created. |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
485 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
486 If there is no such element in the tree, the value is nil." |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
487 (let ((node (elib-avl-root tree)) |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
488 (compare-function (elib-avl-cmpfun tree)) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
489 found) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
490 (while (and node |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
491 (not found)) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
492 (cond |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
493 ((funcall compare-function data (elib-node-data node)) |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
494 (setq node (elib-node-left node))) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
495 ((funcall compare-function (elib-node-data node) data) |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
496 (setq node (elib-node-right node))) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
497 (t |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
498 (setq found t)))) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
499 |
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 (elib-node-data node) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
502 nil))) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
503 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
504 (defun avltree-map (__map-function__ tree) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
505 "Apply MAP-FUNCTION to all elements in the avl tree TREE." |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
506 (elib-avl-mapc |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
507 (function (lambda (node) |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
508 (elib-node-set-data node |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
509 (funcall __map-function__ |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
510 (elib-node-data node))))) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
511 (elib-avl-root tree))) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
512 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
513 (defun avltree-first (tree) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
514 "Return the first element in TREE, or nil if TREE is empty." |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
515 (let ((node (elib-avl-root tree))) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
516 (if node |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
517 (progn |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
518 (while (elib-node-left node) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
519 (setq node (elib-node-left node))) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
520 (elib-node-data node)) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
521 nil))) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
522 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
523 (defun avltree-last (tree) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
524 "Return the last element in TREE, or nil if TREE is empty." |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
525 (let ((node (elib-avl-root tree))) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
526 (if node |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
527 (progn |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
528 (while (elib-node-right node) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
529 (setq node (elib-node-right node))) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
530 (elib-node-data node)) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
531 nil))) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
532 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
533 (defun avltree-copy (tree) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
534 "Return a copy of the avl tree TREE." |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
535 (let ((new-tree (avltree-create |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
536 (elib-avl-cmpfun tree)))) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
537 (elib-node-set-left (elib-avl-dummyroot new-tree) |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
538 (elib-avl-do-copy (elib-avl-root tree))) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
539 new-tree)) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
540 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
541 (defun avltree-flatten (tree) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
542 "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
|
543 (nreverse |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
544 (let ((treelist nil)) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
545 (elib-avl-mapc (function (lambda (node) |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
546 (setq treelist (cons (elib-node-data node) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
547 treelist)))) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
548 (elib-avl-root tree)) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
549 treelist))) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
550 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
551 (defun avltree-size (tree) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
552 "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
|
553 (let ((treesize 0)) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
554 (elib-avl-mapc (function (lambda (data) |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
555 (setq treesize (1+ treesize)) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
556 data)) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
557 (elib-avl-root tree)) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
558 treesize)) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
559 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
560 (defun avltree-clear (tree) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
561 "Clear the avl tree TREE." |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
562 (elib-node-set-left (elib-avl-dummyroot tree) nil)) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
563 |
82892
8ce807303185
Move provide form to end; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82891
diff
changeset
|
564 (provide 'avl-tree) |
8ce807303185
Move provide form to end; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82891
diff
changeset
|
565 |
82894 | 566 ;; arch-tag: 47e26701-43c9-4222-bd79-739eac6357a9 |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
567 ;;; avltree.el ends here |