Mercurial > emacs
annotate lisp/emacs-lisp/avl-tree.el @ 92409:8171649adf8a
(Quniscribe, QCformat): New symbols.
(syms_of_w32font): Define them.
(w32font_has_char): Indicate uncertainty.
(w32font_encode_char): Encode as glyph point. Make static.
(recompute_cached_metrics): New function.
(w32font_open_internal): Use it. Set font to use glyph points
initially. Set format based on type of font.
(w32font_text_extents, w32font_draw): Optionally use glyph points.
(w32_enumfont_pattern_entity): Accept backend arg. Set type based
on it. Set format based on information available here.
(add_font_entity_to_list): Identify backend based on opentype_only.
author | Jason Rumney <jasonr@gnu.org> |
---|---|
date | Mon, 03 Mar 2008 00:31:18 +0000 |
parents | b9e8ab94c460 |
children | 90a2847062be |
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 |
87665 | 3 ;; Copyright (C) 1995, 2007, 2008 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 |
83827
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
31 ;; An AVL tree is a nearly-perfect balanced binary tree. A tree consists of |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
32 ;; two elements, the root node and the compare function. The actual tree |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
33 ;; has a dummy node as its root with the real root in the left pointer. |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
34 ;; |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
35 ;; 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
|
36 ;; 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
|
37 ;; 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
|
38 ;; sub-trees. |
82903
7224e10a56f5
Commentary and docstring munging; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82902
diff
changeset
|
39 ;; |
83827
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
40 ;; The functions with names of the form "avl-tree--" are intended for |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
41 ;; internal use only. |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
42 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
43 ;;; Code: |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
44 |
83827
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
45 (eval-when-compile (require 'cl)) |
82901
18391b91e11f
Move things around; munge whitespace, indentation; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82900
diff
changeset
|
46 |
83827
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
47 ;; ================================================================ |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
48 ;;; Functions and macros handling an AVL tree node. |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
49 |
83827
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
50 (defstruct (avl-tree--node |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
51 ;; We force a representation without tag so it matches the |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
52 ;; pre-defstruct representation. Also we use the underlying |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
53 ;; representation in the implementation of avl-tree--node-branch. |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
54 (:type vector) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
55 (:constructor nil) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
56 (:constructor avl-tree--node-create (left right data balance)) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
57 (:copier nil)) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
58 left right data balance) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
59 |
83827
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
60 (defalias 'avl-tree--node-branch 'aref |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
61 ;; This implementation is efficient but breaks the defstruct abstraction. |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
62 ;; An alternative could be |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
63 ;; (funcall (aref [avl-tree-left avl-tree-right avl-tree-data] branch) node) |
82903
7224e10a56f5
Commentary and docstring munging; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82902
diff
changeset
|
64 "Get value of a branch of a node. |
7224e10a56f5
Commentary and docstring munging; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82902
diff
changeset
|
65 |
7224e10a56f5
Commentary and docstring munging; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82902
diff
changeset
|
66 NODE is the node, and BRANCH is the branch. |
83827
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
67 0 for left pointer, 1 for right pointer and 2 for the data.\" |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
68 \(fn node branch)") |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
69 ;; The funcall/aref trick doesn't work for the setf method, unless we try |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
70 ;; and access the underlying setter function, but this wouldn't be |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
71 ;; portable either. |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
72 (defsetf avl-tree--node-branch aset) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
73 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
74 |
83827
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
75 ;; ================================================================ |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
76 ;;; Internal functions for use in the AVL tree package |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
77 |
83827
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
78 (defstruct (avl-tree- |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
79 ;; A tagged list is the pre-defstruct representation. |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
80 ;; (:type list) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
81 :named |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
82 (:constructor nil) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
83 (:constructor avl-tree-create (cmpfun)) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
84 (:predicate avl-tree-p) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
85 (:copier nil)) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
86 (dummyroot (avl-tree--node-create nil nil nil 0)) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
87 cmpfun) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
88 |
83827
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
89 (defmacro avl-tree--root (tree) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
90 ;; Return the root node for an avl-tree. INTERNAL USE ONLY. |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
91 `(avl-tree--node-left (avl-tree--dummyroot tree))) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
92 (defsetf avl-tree--root (tree) (node) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
93 `(setf (avl-tree--node-left (avl-tree--dummyroot ,tree)) ,node)) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
94 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
95 ;; ---------------------------------------------------------------- |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
96 ;; Deleting data |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
97 |
83827
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
98 (defun avl-tree--del-balance1 (node branch) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
99 ;; Rebalance a tree and return t if the height of the tree has shrunk. |
83827
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
100 (let ((br (avl-tree--node-branch node branch)) |
82902
c27b2ab395b6
(avl-tree-del-balance1, avl-tree-del-balance2)
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82901
diff
changeset
|
101 p1 b1 p2 b2 result) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
102 (cond |
83827
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
103 ((< (avl-tree--node-balance br) 0) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
104 (setf (avl-tree--node-balance br) 0) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
105 t) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
106 |
83827
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
107 ((= (avl-tree--node-balance br) 0) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
108 (setf (avl-tree--node-balance br) +1) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
109 nil) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
110 |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
111 (t |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
112 ;; Rebalance. |
83827
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
113 (setq p1 (avl-tree--node-right br) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
114 b1 (avl-tree--node-balance p1)) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
115 (if (>= b1 0) |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
116 ;; Single RR rotation. |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
117 (progn |
83827
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
118 (setf (avl-tree--node-right br) (avl-tree--node-left p1)) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
119 (setf (avl-tree--node-left p1) br) |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
120 (if (= 0 b1) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
121 (progn |
83827
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
122 (setf (avl-tree--node-balance br) +1) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
123 (setf (avl-tree--node-balance p1) -1) |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
124 (setq result nil)) |
83827
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
125 (setf (avl-tree--node-balance br) 0) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
126 (setf (avl-tree--node-balance p1) 0) |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
127 (setq result t)) |
83827
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
128 (setf (avl-tree--node-branch node branch) p1) |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
129 result) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
130 |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
131 ;; Double RL rotation. |
83827
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
132 (setq p2 (avl-tree--node-left p1) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
133 b2 (avl-tree--node-balance p2)) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
134 (setf (avl-tree--node-left p1) (avl-tree--node-right p2)) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
135 (setf (avl-tree--node-right p2) p1) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
136 (setf (avl-tree--node-right br) (avl-tree--node-left p2)) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
137 (setf (avl-tree--node-left p2) br) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
138 (setf (avl-tree--node-balance br) (if (> b2 0) -1 0)) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
139 (setf (avl-tree--node-balance p1) (if (< b2 0) +1 0)) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
140 (setf (avl-tree--node-branch node branch) p2) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
141 (setf (avl-tree--node-balance p2) 0) |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
142 t))))) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
143 |
83827
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
144 (defun avl-tree--del-balance2 (node branch) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
145 (let ((br (avl-tree--node-branch node branch)) |
82902
c27b2ab395b6
(avl-tree-del-balance1, avl-tree-del-balance2)
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82901
diff
changeset
|
146 p1 b1 p2 b2 result) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
147 (cond |
83827
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
148 ((> (avl-tree--node-balance br) 0) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
149 (setf (avl-tree--node-balance br) 0) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
150 t) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
151 |
83827
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
152 ((= (avl-tree--node-balance br) 0) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
153 (setf (avl-tree--node-balance br) -1) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
154 nil) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
155 |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
156 (t |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
157 ;; Rebalance. |
83827
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
158 (setq p1 (avl-tree--node-left br) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
159 b1 (avl-tree--node-balance p1)) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
160 (if (<= b1 0) |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
161 ;; Single LL rotation. |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
162 (progn |
83827
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
163 (setf (avl-tree--node-left br) (avl-tree--node-right p1)) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
164 (setf (avl-tree--node-right p1) br) |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
165 (if (= 0 b1) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
166 (progn |
83827
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
167 (setf (avl-tree--node-balance br) -1) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
168 (setf (avl-tree--node-balance p1) +1) |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
169 (setq result nil)) |
83827
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
170 (setf (avl-tree--node-balance br) 0) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
171 (setf (avl-tree--node-balance p1) 0) |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
172 (setq result t)) |
83827
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
173 (setf (avl-tree--node-branch node branch) p1) |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
174 result) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
175 |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
176 ;; Double LR rotation. |
83827
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
177 (setq p2 (avl-tree--node-right p1) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
178 b2 (avl-tree--node-balance p2)) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
179 (setf (avl-tree--node-right p1) (avl-tree--node-left p2)) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
180 (setf (avl-tree--node-left p2) p1) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
181 (setf (avl-tree--node-left br) (avl-tree--node-right p2)) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
182 (setf (avl-tree--node-right p2) br) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
183 (setf (avl-tree--node-balance br) (if (< b2 0) +1 0)) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
184 (setf (avl-tree--node-balance p1) (if (> b2 0) -1 0)) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
185 (setf (avl-tree--node-branch node branch) p2) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
186 (setf (avl-tree--node-balance p2) 0) |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
187 t))))) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
188 |
83827
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
189 (defun avl-tree--do-del-internal (node branch q) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
190 (let ((br (avl-tree--node-branch node branch))) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
191 (if (avl-tree--node-right br) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
192 (if (avl-tree--do-del-internal br +1 q) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
193 (avl-tree--del-balance2 node branch)) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
194 (setf (avl-tree--node-data q) (avl-tree--node-data br)) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
195 (setf (avl-tree--node-branch node branch) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
196 (avl-tree--node-left br)) |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
197 t))) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
198 |
83827
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
199 (defun avl-tree--do-delete (cmpfun root branch data) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
200 ;; Return t if the height of the tree has shrunk. |
83827
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
201 (let ((br (avl-tree--node-branch root branch))) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
202 (cond |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
203 ((null br) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
204 nil) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
205 |
83827
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
206 ((funcall cmpfun data (avl-tree--node-data br)) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
207 (if (avl-tree--do-delete cmpfun br 0 data) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
208 (avl-tree--del-balance1 root branch))) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
209 |
83827
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
210 ((funcall cmpfun (avl-tree--node-data br) data) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
211 (if (avl-tree--do-delete cmpfun br 1 data) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
212 (avl-tree--del-balance2 root branch))) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
213 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
214 (t |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
215 ;; 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
|
216 (cond |
83827
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
217 ((null (avl-tree--node-right br)) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
218 (setf (avl-tree--node-branch root branch) (avl-tree--node-left br)) |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
219 t) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
220 |
83827
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
221 ((null (avl-tree--node-left br)) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
222 (setf (avl-tree--node-branch root branch) (avl-tree--node-right br)) |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
223 t) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
224 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
225 (t |
83827
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
226 (if (avl-tree--do-del-internal br 0 br) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
227 (avl-tree--del-balance1 root branch)))))))) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
228 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
229 ;; ---------------------------------------------------------------- |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
230 ;; Entering data |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
231 |
83827
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
232 (defun avl-tree--enter-balance1 (node branch) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
233 ;; Rebalance a tree and return t if the height of the tree has grown. |
83827
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
234 (let ((br (avl-tree--node-branch node branch)) |
82902
c27b2ab395b6
(avl-tree-del-balance1, avl-tree-del-balance2)
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82901
diff
changeset
|
235 p1 p2 b2 result) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
236 (cond |
83827
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
237 ((< (avl-tree--node-balance br) 0) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
238 (setf (avl-tree--node-balance br) 0) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
239 nil) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
240 |
83827
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
241 ((= (avl-tree--node-balance br) 0) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
242 (setf (avl-tree--node-balance br) +1) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
243 t) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
244 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
245 (t |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
246 ;; Tree has grown => Rebalance. |
83827
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
247 (setq p1 (avl-tree--node-right br)) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
248 (if (> (avl-tree--node-balance p1) 0) |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
249 ;; Single RR rotation. |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
250 (progn |
83827
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
251 (setf (avl-tree--node-right br) (avl-tree--node-left p1)) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
252 (setf (avl-tree--node-left p1) br) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
253 (setf (avl-tree--node-balance br) 0) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
254 (setf (avl-tree--node-branch node branch) p1)) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
255 |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
256 ;; Double RL rotation. |
83827
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
257 (setq p2 (avl-tree--node-left p1) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
258 b2 (avl-tree--node-balance p2)) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
259 (setf (avl-tree--node-left p1) (avl-tree--node-right p2)) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
260 (setf (avl-tree--node-right p2) p1) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
261 (setf (avl-tree--node-right br) (avl-tree--node-left p2)) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
262 (setf (avl-tree--node-left p2) br) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
263 (setf (avl-tree--node-balance br) (if (> b2 0) -1 0)) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
264 (setf (avl-tree--node-balance p1) (if (< b2 0) +1 0)) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
265 (setf (avl-tree--node-branch node branch) p2)) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
266 (setf (avl-tree--node-balance (avl-tree--node-branch node branch)) 0) |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
267 nil)))) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
268 |
83827
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
269 (defun avl-tree--enter-balance2 (node branch) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
270 ;; Return t if the tree has grown. |
83827
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
271 (let ((br (avl-tree--node-branch node branch)) |
82902
c27b2ab395b6
(avl-tree-del-balance1, avl-tree-del-balance2)
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82901
diff
changeset
|
272 p1 p2 b2) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
273 (cond |
83827
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
274 ((> (avl-tree--node-balance br) 0) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
275 (setf (avl-tree--node-balance br) 0) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
276 nil) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
277 |
83827
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
278 ((= (avl-tree--node-balance br) 0) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
279 (setf (avl-tree--node-balance br) -1) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
280 t) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
281 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
282 (t |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
283 ;; Balance was -1 => Rebalance. |
83827
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
284 (setq p1 (avl-tree--node-left br)) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
285 (if (< (avl-tree--node-balance p1) 0) |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
286 ;; Single LL rotation. |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
287 (progn |
83827
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
288 (setf (avl-tree--node-left br) (avl-tree--node-right p1)) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
289 (setf (avl-tree--node-right p1) br) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
290 (setf (avl-tree--node-balance br) 0) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
291 (setf (avl-tree--node-branch node branch) p1)) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
292 |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
293 ;; Double LR rotation. |
83827
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
294 (setq p2 (avl-tree--node-right p1) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
295 b2 (avl-tree--node-balance p2)) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
296 (setf (avl-tree--node-right p1) (avl-tree--node-left p2)) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
297 (setf (avl-tree--node-left p2) p1) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
298 (setf (avl-tree--node-left br) (avl-tree--node-right p2)) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
299 (setf (avl-tree--node-right p2) br) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
300 (setf (avl-tree--node-balance br) (if (< b2 0) +1 0)) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
301 (setf (avl-tree--node-balance p1) (if (> b2 0) -1 0)) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
302 (setf (avl-tree--node-branch node branch) p2)) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
303 (setf (avl-tree--node-balance (avl-tree--node-branch node branch)) 0) |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
304 nil)))) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
305 |
83827
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
306 (defun avl-tree--do-enter (cmpfun root branch data) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
307 ;; Return t if height of tree ROOT has grown. INTERNAL USE ONLY. |
83827
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
308 (let ((br (avl-tree--node-branch root branch))) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
309 (cond |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
310 ((null br) |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
311 ;; Data not in tree, insert it. |
83827
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
312 (setf (avl-tree--node-branch root branch) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
313 (avl-tree--node-create nil nil data 0)) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
314 t) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
315 |
83827
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
316 ((funcall cmpfun data (avl-tree--node-data br)) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
317 (and (avl-tree--do-enter cmpfun br 0 data) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
318 (avl-tree--enter-balance2 root branch))) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
319 |
83827
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
320 ((funcall cmpfun (avl-tree--node-data br) data) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
321 (and (avl-tree--do-enter cmpfun br 1 data) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
322 (avl-tree--enter-balance1 root branch))) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
323 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
324 (t |
83827
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
325 (setf (avl-tree--node-data br) data) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
326 nil)))) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
327 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
328 ;; ---------------------------------------------------------------- |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
329 |
83827
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
330 (defun avl-tree--mapc (map-function root) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
331 ;; 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
|
332 ;; 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
|
333 ;; |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
334 ;; 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
|
335 ;; INTERNAL USE ONLY. |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
336 (let ((node root) |
82893 | 337 (stack nil) |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
338 (go-left t)) |
82893 | 339 (push nil stack) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
340 (while node |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
341 (if (and go-left |
83827
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
342 (avl-tree--node-left node)) |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
343 ;; Do the left subtree first. |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
344 (progn |
82893 | 345 (push node stack) |
83827
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
346 (setq node (avl-tree--node-left node))) |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
347 ;; Apply the function... |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
348 (funcall map-function node) |
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
349 ;; and do the right subtree. |
83827
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
350 (setq node (if (setq go-left (avl-tree--node-right node)) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
351 (avl-tree--node-right node) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
352 (pop stack))))))) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
353 |
83827
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
354 (defun avl-tree--do-copy (root) |
82903
7224e10a56f5
Commentary and docstring munging; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82902
diff
changeset
|
355 ;; Copy the avl tree with ROOT as root. |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
356 ;; Highly recursive. INTERNAL USE ONLY. |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
357 (if (null root) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
358 nil |
83827
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
359 (avl-tree--node-create |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
360 (avl-tree--do-copy (avl-tree--node-left root)) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
361 (avl-tree--do-copy (avl-tree--node-right root)) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
362 (avl-tree--node-data root) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
363 (avl-tree--node-balance root)))) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
364 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
365 |
83827
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
366 ;; ================================================================ |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
367 ;;; The public functions which operate on AVL trees. |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
368 |
83827
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
369 (defalias 'avl-tree-compare-function 'avl-tree--cmpfun |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
370 "Return the comparison function for the avl tree TREE. |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
371 |
83827
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
372 \(fn TREE)") |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
373 |
82895
3b4dacb1e48c
Do s/avltree/avl-tree/g. Resulting changed function names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82894
diff
changeset
|
374 (defun avl-tree-empty (tree) |
82903
7224e10a56f5
Commentary and docstring munging; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82902
diff
changeset
|
375 "Return t if avl tree TREE is emtpy, otherwise return nil." |
83827
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
376 (null (avl-tree--root tree))) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
377 |
82895
3b4dacb1e48c
Do s/avltree/avl-tree/g. Resulting changed function names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82894
diff
changeset
|
378 (defun avl-tree-enter (tree data) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
379 "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
|
380 Return DATA." |
83827
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
381 (avl-tree--do-enter (avl-tree--cmpfun tree) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
382 (avl-tree--dummyroot tree) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
383 0 |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
384 data) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
385 data) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
386 |
82895
3b4dacb1e48c
Do s/avltree/avl-tree/g. Resulting changed function names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82894
diff
changeset
|
387 (defun avl-tree-delete (tree data) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
388 "From the avl tree TREE, delete DATA. |
82903
7224e10a56f5
Commentary and docstring munging; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82902
diff
changeset
|
389 Return the element in TREE which matched DATA, |
7224e10a56f5
Commentary and docstring munging; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82902
diff
changeset
|
390 nil if no element matched." |
83827
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
391 (avl-tree--do-delete (avl-tree--cmpfun tree) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
392 (avl-tree--dummyroot tree) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
393 0 |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
394 data)) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
395 |
82895
3b4dacb1e48c
Do s/avltree/avl-tree/g. Resulting changed function names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82894
diff
changeset
|
396 (defun avl-tree-member (tree data) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
397 "Return the element in the avl tree TREE which matches DATA. |
82903
7224e10a56f5
Commentary and docstring munging; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82902
diff
changeset
|
398 Matching uses the compare function previously specified in |
7224e10a56f5
Commentary and docstring munging; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82902
diff
changeset
|
399 `avl-tree-create' when TREE was created. |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
400 |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
401 If there is no such element in the tree, the value is nil." |
83827
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
402 (let ((node (avl-tree--root tree)) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
403 (compare-function (avl-tree--cmpfun tree)) |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
404 found) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
405 (while (and node |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
406 (not found)) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
407 (cond |
83827
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
408 ((funcall compare-function data (avl-tree--node-data node)) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
409 (setq node (avl-tree--node-left node))) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
410 ((funcall compare-function (avl-tree--node-data node) data) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
411 (setq node (avl-tree--node-right node))) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
412 (t |
82891
fb6442527160
Munge comments, whitespace, indentation, hanging parens; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82890
diff
changeset
|
413 (setq found t)))) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
414 (if node |
83827
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
415 (avl-tree--node-data node) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
416 nil))) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
417 |
82895
3b4dacb1e48c
Do s/avltree/avl-tree/g. Resulting changed function names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82894
diff
changeset
|
418 (defun avl-tree-map (__map-function__ tree) |
82903
7224e10a56f5
Commentary and docstring munging; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82902
diff
changeset
|
419 "Apply __MAP-FUNCTION__ to all elements in the avl tree TREE." |
83827
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
420 (avl-tree--mapc |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
421 (lambda (node) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
422 (setf (avl-tree--node-data node) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
423 (funcall __map-function__ (avl-tree--node-data node)))) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
424 (avl-tree--root tree))) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
425 |
82895
3b4dacb1e48c
Do s/avltree/avl-tree/g. Resulting changed function names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82894
diff
changeset
|
426 (defun avl-tree-first (tree) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
427 "Return the first element in TREE, or nil if TREE is empty." |
83827
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
428 (let ((node (avl-tree--root tree))) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
429 (when node |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
430 (while (avl-tree--node-left node) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
431 (setq node (avl-tree--node-left node))) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
432 (avl-tree--node-data node)))) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
433 |
82895
3b4dacb1e48c
Do s/avltree/avl-tree/g. Resulting changed function names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82894
diff
changeset
|
434 (defun avl-tree-last (tree) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
435 "Return the last element in TREE, or nil if TREE is empty." |
83827
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
436 (let ((node (avl-tree--root tree))) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
437 (when node |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
438 (while (avl-tree--node-right node) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
439 (setq node (avl-tree--node-right node))) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
440 (avl-tree--node-data node)))) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
441 |
82895
3b4dacb1e48c
Do s/avltree/avl-tree/g. Resulting changed function names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82894
diff
changeset
|
442 (defun avl-tree-copy (tree) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
443 "Return a copy of the avl tree TREE." |
83827
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
444 (let ((new-tree (avl-tree-create (avl-tree--cmpfun tree)))) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
445 (setf (avl-tree--root new-tree) (avl-tree--do-copy (avl-tree--root tree))) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
446 new-tree)) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
447 |
82895
3b4dacb1e48c
Do s/avltree/avl-tree/g. Resulting changed function names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82894
diff
changeset
|
448 (defun avl-tree-flatten (tree) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
449 "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
|
450 (nreverse |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
451 (let ((treelist nil)) |
83827
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
452 (avl-tree--mapc |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
453 (lambda (node) (push (avl-tree--node-data node) treelist)) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
454 (avl-tree--root tree)) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
455 treelist))) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
456 |
82895
3b4dacb1e48c
Do s/avltree/avl-tree/g. Resulting changed function names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82894
diff
changeset
|
457 (defun avl-tree-size (tree) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
458 "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
|
459 (let ((treesize 0)) |
83827
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
460 (avl-tree--mapc |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
461 (lambda (data) (setq treesize (1+ treesize))) |
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
462 (avl-tree--root tree)) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
463 treesize)) |
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
464 |
82895
3b4dacb1e48c
Do s/avltree/avl-tree/g. Resulting changed function names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82894
diff
changeset
|
465 (defun avl-tree-clear (tree) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
466 "Clear the avl tree TREE." |
83827
17a8beea7b8c
Use defstruct rather than macros.
Stefan Monnier <monnier@iro.umontreal.ca>
parents:
82903
diff
changeset
|
467 (setf (avl-tree--root tree) nil)) |
82890
03c151908dc7
Initial revision, comprising elib-node.el and avltree.el,
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
diff
changeset
|
468 |
82892
8ce807303185
Move provide form to end; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82891
diff
changeset
|
469 (provide 'avl-tree) |
8ce807303185
Move provide form to end; nfc.
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82891
diff
changeset
|
470 |
82894 | 471 ;; arch-tag: 47e26701-43c9-4222-bd79-739eac6357a9 |
82895
3b4dacb1e48c
Do s/avltree/avl-tree/g. Resulting changed function names:
Thien-Thi Nguyen <ttn@gnuvola.org>
parents:
82894
diff
changeset
|
472 ;;; avl-tree.el ends here |