Mercurial > emacs
annotate lisp/emacs-lisp/avl-tree.el @ 82892:8ce807303185
Move provide form to end; nfc.
author | Thien-Thi Nguyen <ttn@gnuvola.org> |
---|---|
date | Mon, 27 Aug 2007 01:29:41 +0000 |
parents | fb6442527160 |
children | 2321b585ebdd |
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 (eval-when-compile (require 'cl)) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
101 (defun elib-stack-create () (list)) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
102 (defmacro elib-stack-push (stack object) `(push ,object ,stack)) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
103 (defmacro elib-stack-pop (stack) `(pop ,stack)) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
104 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
105 ;;; ================================================================ |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
106 ;;; 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
|
107 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
108 (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
|
109 ;; 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
|
110 (` (vector (, left) (, right) (, data) (, balance)))) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
111 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
112 (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
|
113 ;; 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
|
114 (` (aref (, node) 3))) |
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 (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
|
117 ;; 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
|
118 (` (aset (, node) 3 (, newbal)))) |
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 |
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 ;;; 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
|
123 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
124 ;;; |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
125 ;;; 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
|
126 ;;; |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
127 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
128 (defmacro elib-avl-root (tree) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
129 ;; 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
|
130 (` (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
|
131 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
132 (defmacro elib-avl-dummyroot (tree) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
133 ;; 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
|
134 (` (car (cdr (, tree))))) |
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 (defmacro elib-avl-cmpfun (tree) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
137 ;; 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
|
138 (` (cdr (cdr (, tree))))) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
139 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
140 ;; ---------------------------------------------------------------- |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
141 ;; Deleting data |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
142 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
143 (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
|
144 ;; 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
|
145 (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
|
146 p1 |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
147 b1 |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
148 p2 |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
149 b2 |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
150 result) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
151 (cond |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
152 ((< (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
|
153 (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
|
154 t) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
155 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
156 ((= (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
|
157 (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
|
158 nil) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
159 |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
160 (t |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
161 ;; Rebalance. |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
162 (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
|
163 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
|
164 (if (>= b1 0) |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
165 ;; Single RR rotation. |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
166 (progn |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
167 (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
|
168 (elib-node-set-left p1 br) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
169 (if (= 0 b1) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
170 (progn |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
171 (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
|
172 (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
|
173 (setq result nil)) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
174 (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
|
175 (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
|
176 (setq result t)) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
177 (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
|
178 result) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
179 |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
180 ;; Double RL rotation. |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
181 (setq p2 (elib-node-left p1) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
182 b2 (elib-avl-node-balance p2)) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
183 (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
|
184 (elib-node-set-right p2 p1) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
185 (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
|
186 (elib-node-set-left p2 br) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
187 (if (> b2 0) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
188 (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
|
189 (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
|
190 (if (< b2 0) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
191 (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
|
192 (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
|
193 (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
|
194 (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
|
195 t))))) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
196 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
197 (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
|
198 (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
|
199 p1 |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
200 b1 |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
201 p2 |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
202 b2 |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
203 result) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
204 (cond |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
205 ((> (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
|
206 (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
|
207 t) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
208 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
209 ((= (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
|
210 (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
|
211 nil) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
212 |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
213 (t |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
214 ;; Rebalance. |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
215 (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
|
216 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
|
217 (if (<= b1 0) |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
218 ;; Single LL rotation. |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
219 (progn |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
220 (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
|
221 (elib-node-set-right p1 br) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
222 (if (= 0 b1) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
223 (progn |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
224 (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
|
225 (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
|
226 (setq result nil)) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
227 (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
|
228 (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
|
229 (setq result t)) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
230 (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
|
231 result) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
232 |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
233 ;; Double LR rotation. |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
234 (setq p2 (elib-node-right p1) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
235 b2 (elib-avl-node-balance p2)) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
236 (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
|
237 (elib-node-set-left p2 p1) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
238 (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
|
239 (elib-node-set-right p2 br) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
240 (if (< b2 0) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
241 (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
|
242 (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
|
243 (if (> b2 0) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
244 (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
|
245 (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
|
246 (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
|
247 (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
|
248 t))))) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
249 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
250 (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
|
251 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
252 (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
|
253 (if (elib-node-right br) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
254 (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
|
255 (elib-avl-del-balance2 node branch)) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
256 (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
|
257 (elib-node-set-branch node branch |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
258 (elib-node-left br)) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
259 t))) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
260 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
261 (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
|
262 ;; 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
|
263 (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
|
264 (cond |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
265 ((null br) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
266 nil) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
267 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
268 ((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
|
269 (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
|
270 (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
|
271 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
272 ((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
|
273 (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
|
274 (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
|
275 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
276 (t |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
277 ;; 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
|
278 (cond |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
279 ((null (elib-node-right br)) |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
280 (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
|
281 t) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
282 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
283 ((null (elib-node-left br)) |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
284 (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
|
285 t) |
82890
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 (t |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
288 (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
|
289 (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
|
290 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
291 ;; ---------------------------------------------------------------- |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
292 ;; Entering data |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
293 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
294 (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
|
295 ;; 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
|
296 (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
|
297 p1 |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
298 p2 |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
299 b2 |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
300 result) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
301 (cond |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
302 ((< (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
|
303 (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
|
304 nil) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
305 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
306 ((= (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
|
307 (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
|
308 t) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
309 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
310 (t |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
311 ;; Tree has grown => Rebalance. |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
312 (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
|
313 (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
|
314 ;; Single RR rotation. |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
315 (progn |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
316 (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
|
317 (elib-node-set-left p1 br) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
318 (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
|
319 (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
|
320 |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
321 ;; Double RL rotation. |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
322 (setq p2 (elib-node-left p1) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
323 b2 (elib-avl-node-balance p2)) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
324 (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
|
325 (elib-node-set-right p2 p1) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
326 (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
|
327 (elib-node-set-left p2 br) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
328 (if (> b2 0) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
329 (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
|
330 (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
|
331 (if (< b2 0) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
332 (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
|
333 (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
|
334 (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
|
335 (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
|
336 nil)))) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
337 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
338 (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
|
339 ;; 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
|
340 (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
|
341 p1 |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
342 p2 |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
343 b2) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
344 (cond |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
345 ((> (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
|
346 (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
|
347 nil) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
348 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
349 ((= (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
|
350 (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
|
351 t) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
352 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
353 (t |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
354 ;; Balance was -1 => Rebalance. |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
355 (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
|
356 (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
|
357 ;; Single LL rotation. |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
358 (progn |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
359 (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
|
360 (elib-node-set-right p1 br) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
361 (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
|
362 (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
|
363 |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
364 ;; Double LR rotation. |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
365 (setq p2 (elib-node-right p1) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
366 b2 (elib-avl-node-balance p2)) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
367 (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
|
368 (elib-node-set-left p2 p1) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
369 (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
|
370 (elib-node-set-right p2 br) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
371 (if (< b2 0) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
372 (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
|
373 (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
|
374 (if (> b2 0) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
375 (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
|
376 (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
|
377 (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
|
378 (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
|
379 nil)))) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
380 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
381 (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
|
382 ;; 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
|
383 (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
|
384 (cond |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
385 ((null br) |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
386 ;; 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
|
387 (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
|
388 (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
|
389 t) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
390 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
391 ((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
|
392 (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
|
393 br |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
394 0 data) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
395 (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
|
396 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
397 ((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
|
398 (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
|
399 br |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
400 1 data) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
401 (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
|
402 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
403 (t |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
404 (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
|
405 nil)))) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
406 |
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 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
409 (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
|
410 ;; 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
|
411 ;; 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
|
412 ;; |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
413 ;; 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
|
414 ;; INTERNAL USE ONLY. |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
415 (let ((node root) |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
416 (stack (elib-stack-create)) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
417 (go-left t)) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
418 (elib-stack-push stack nil) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
419 (while node |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
420 (if (and go-left |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
421 (elib-node-left node)) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
422 ;; Do the left subtree first. |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
423 (progn |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
424 (elib-stack-push stack node) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
425 (setq node (elib-node-left node))) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
426 ;; Apply the function... |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
427 (funcall map-function node) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
428 ;; and do the right subtree. |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
429 (if (elib-node-right node) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
430 (setq node (elib-node-right node) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
431 go-left t) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
432 (setq node (elib-stack-pop stack) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
433 go-left nil)))))) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
434 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
435 (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
|
436 ;; 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
|
437 ;; Highly recursive. INTERNAL USE ONLY. |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
438 (if (null root) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
439 nil |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
440 (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
|
441 (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
|
442 (elib-node-data root) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
443 (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
|
444 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
445 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
446 ;;; ================================================================ |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
447 ;;; 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
|
448 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
449 (defun avltree-create (compare-function) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
450 "Create an empty avl tree. |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
451 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
|
452 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
|
453 (cons 'AVLTREE |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
454 (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
|
455 compare-function))) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
456 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
457 (defun avltree-p (obj) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
458 "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
|
459 (eq (car-safe obj) 'AVLTREE)) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
460 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
461 (defun avltree-compare-function (tree) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
462 "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
|
463 (elib-avl-cmpfun tree)) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
464 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
465 (defun avltree-empty (tree) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
466 "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
|
467 (null (elib-avl-root tree))) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
468 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
469 (defun avltree-enter (tree data) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
470 "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
|
471 Return DATA." |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
472 (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
|
473 (elib-avl-dummyroot tree) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
474 0 |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
475 data) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
476 data) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
477 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
478 (defun avltree-delete (tree data) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
479 "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
|
480 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
|
481 (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
|
482 (elib-avl-dummyroot tree) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
483 0 |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
484 data)) |
82890
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 (defun avltree-member (tree data) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
487 "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
|
488 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
|
489 when TREE was created. |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
490 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
491 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
|
492 (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
|
493 (compare-function (elib-avl-cmpfun tree)) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
494 found) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
495 (while (and node |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
496 (not found)) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
497 (cond |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
498 ((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
|
499 (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
|
500 ((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
|
501 (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
|
502 (t |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
503 (setq found t)))) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
504 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
505 (if node |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
506 (elib-node-data node) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
507 nil))) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
508 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
509 (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
|
510 "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
|
511 (elib-avl-mapc |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
512 (function (lambda (node) |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
513 (elib-node-set-data node |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
514 (funcall __map-function__ |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
515 (elib-node-data node))))) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
516 (elib-avl-root tree))) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
517 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
518 (defun avltree-first (tree) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
519 "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
|
520 (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
|
521 (if node |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
522 (progn |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
523 (while (elib-node-left node) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
524 (setq node (elib-node-left node))) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
525 (elib-node-data node)) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
526 nil))) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
527 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
528 (defun avltree-last (tree) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
529 "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
|
530 (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
|
531 (if node |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
532 (progn |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
533 (while (elib-node-right node) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
534 (setq node (elib-node-right node))) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
535 (elib-node-data node)) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
536 nil))) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
537 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
538 (defun avltree-copy (tree) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
539 "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
|
540 (let ((new-tree (avltree-create |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
541 (elib-avl-cmpfun tree)))) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
542 (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
|
543 (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
|
544 new-tree)) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
545 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
546 (defun avltree-flatten (tree) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
547 "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
|
548 (nreverse |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
549 (let ((treelist nil)) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
550 (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
|
551 (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
|
552 treelist)))) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
553 (elib-avl-root tree)) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
554 treelist))) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
555 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
556 (defun avltree-size (tree) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
557 "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
|
558 (let ((treesize 0)) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
559 (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
|
560 (setq treesize (1+ treesize)) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
561 data)) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
562 (elib-avl-root tree)) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
563 treesize)) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
564 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
565 (defun avltree-clear (tree) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
566 "Clear the avl tree TREE." |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
567 (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
|
568 |
82892
8ce807303185
Move provide form to end; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82891
diff
changeset
|
569 (provide 'avl-tree) |
8ce807303185
Move provide form to end; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82891
diff
changeset
|
570 |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
571 ;;; avltree.el ends here |