Commit | Line | Data |
---|---|---|
ed797193 G |
1 | ;;; rtree.el --- functions for manipulating range trees |
2 | ;; Copyright (C) 2010 Free Software Foundation, Inc. | |
3 | ||
4 | ;; Author: Lars Magne Ingebrigtsen <larsi@gnus.org> | |
5 | ||
6 | ;; This file is part of GNU Emacs. | |
7 | ||
8 | ;; GNU Emacs is free software; you can redistribute it and/or modify | |
9 | ;; it under the terms of the GNU General Public License as published by | |
10 | ;; the Free Software Foundation; either version 3, or (at your option) | |
11 | ;; any later version. | |
12 | ||
13 | ;; GNU Emacs is distributed in the hope that it will be useful, | |
14 | ;; but WITHOUT ANY WARRANTY; without even the implied warranty of | |
15 | ;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
16 | ;; GNU General Public License for more details. | |
17 | ||
18 | ;; You should have received a copy of the GNU General Public License | |
19 | ;; along with GNU Emacs; see the file COPYING. If not, write to the | |
20 | ;; Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, | |
21 | ;; Boston, MA 02110-1301, USA. | |
22 | ||
23 | ;;; Commentary: | |
24 | ||
25 | ;; A "range tree" is a binary tree that stores ranges. They are | |
26 | ;; similar to interval trees, but do not allow overlapping intervals. | |
27 | ||
28 | ;; A range is an ordered list of number intervals, like this: | |
29 | ||
30 | ;; ((10 . 25) 56 78 (98 . 201)) | |
31 | ||
32 | ;; Common operations, like lookup, deletion and insertion are O(n) in | |
33 | ;; a range, but an rtree is O(log n) in all these operations. | |
34 | ;; Transformation between a range and an rtree is O(n). | |
35 | ||
36 | ;; The rtrees are quite simple. The structure of each node is | |
37 | ||
38 | ;; (cons (cons low high) (cons left right)) | |
39 | ||
40 | ;; That is, they are three cons cells, where the car of the top cell | |
41 | ;; is the actual range, and the cdr has the left and right child. The | |
42 | ;; rtrees aren't automatically balanced, but are balanced when | |
43 | ;; created, and can be rebalanced when deemed necessary. | |
44 | ||
45 | ;;; Code: | |
46 | ||
47 | (eval-when-compile | |
48 | (require 'cl)) | |
49 | ||
50 | (defmacro rtree-make-node () | |
51 | `(list (list nil) nil)) | |
52 | ||
53 | (defmacro rtree-set-left (node left) | |
54 | `(setcar (cdr ,node) ,left)) | |
55 | ||
56 | (defmacro rtree-set-right (node right) | |
57 | `(setcdr (cdr ,node) ,right)) | |
58 | ||
59 | (defmacro rtree-set-range (node range) | |
60 | `(setcar ,node ,range)) | |
61 | ||
62 | (defmacro rtree-low (node) | |
63 | `(caar ,node)) | |
64 | ||
65 | (defmacro rtree-high (node) | |
66 | `(cdar ,node)) | |
67 | ||
68 | (defmacro rtree-set-low (node number) | |
69 | `(setcar (car ,node) ,number)) | |
70 | ||
71 | (defmacro rtree-set-high (node number) | |
72 | `(setcdr (car ,node) ,number)) | |
73 | ||
74 | (defmacro rtree-left (node) | |
75 | `(cadr ,node)) | |
76 | ||
77 | (defmacro rtree-right (node) | |
78 | `(cddr ,node)) | |
79 | ||
80 | (defmacro rtree-range (node) | |
81 | `(car ,node)) | |
82 | ||
83 | (defsubst rtree-normalise-range (range) | |
84 | (when (numberp range) | |
85 | (setq range (cons range range))) | |
86 | range) | |
87 | ||
88 | (defun rtree-make (range) | |
89 | "Make an rtree from RANGE." | |
90 | ;; Normalize the range. | |
91 | (unless (listp (cdr-safe range)) | |
92 | (setq range (list range))) | |
93 | (rtree-make-1 (cons nil range) (length range))) | |
94 | ||
95 | (defun rtree-make-1 (range length) | |
96 | (let ((mid (/ length 2)) | |
97 | (node (rtree-make-node))) | |
98 | (when (> mid 0) | |
99 | (rtree-set-left node (rtree-make-1 range mid))) | |
100 | (rtree-set-range node (rtree-normalise-range (cadr range))) | |
101 | (setcdr range (cddr range)) | |
102 | (when (> (- length mid 1) 0) | |
103 | (rtree-set-right node (rtree-make-1 range (- length mid 1)))) | |
104 | node)) | |
105 | ||
106 | (defun rtree-memq (tree number) | |
107 | "Return non-nil if NUMBER is present in TREE." | |
108 | (while (and tree | |
109 | (not (and (>= number (rtree-low tree)) | |
110 | (<= number (rtree-high tree))))) | |
111 | (setq tree | |
112 | (if (< number (rtree-low tree)) | |
113 | (rtree-left tree) | |
114 | (rtree-right tree)))) | |
115 | tree) | |
116 | ||
117 | (defun rtree-add (tree number) | |
118 | "Add NUMBER to TREE." | |
119 | (while tree | |
120 | (cond | |
121 | ;; It's already present, so we don't have to do anything. | |
122 | ((and (>= number (rtree-low tree)) | |
123 | (<= number (rtree-high tree))) | |
124 | (setq tree nil)) | |
125 | ((< number (rtree-low tree)) | |
126 | (cond | |
127 | ;; Extend the low range. | |
128 | ((= number (1- (rtree-low tree))) | |
129 | (rtree-set-low tree number) | |
130 | ;; Check whether we need to merge this node with the child. | |
131 | (when (and (rtree-left tree) | |
132 | (= (rtree-high (rtree-left tree)) (1- number))) | |
133 | ;; Extend the range to the low from the child. | |
134 | (rtree-set-low tree (rtree-low (rtree-left tree))) | |
135 | ;; The child can't have a right child, so just transplant the | |
136 | ;; child's left tree to our left tree. | |
137 | (rtree-set-left tree (rtree-left (rtree-left tree)))) | |
138 | (setq tree nil)) | |
139 | ;; Descend further to the left. | |
140 | ((rtree-left tree) | |
141 | (setq tree (rtree-left tree))) | |
142 | ;; Add a new node. | |
143 | (t | |
144 | (let ((new-node (rtree-make-node))) | |
145 | (rtree-set-low new-node number) | |
146 | (rtree-set-high new-node number) | |
147 | (rtree-set-left tree new-node) | |
148 | (setq tree nil))))) | |
149 | (t | |
150 | (cond | |
151 | ;; Extend the high range. | |
152 | ((= number (1+ (rtree-high tree))) | |
153 | (rtree-set-high tree number) | |
154 | ;; Check whether we need to merge this node with the child. | |
155 | (when (and (rtree-right tree) | |
156 | (= (rtree-low (rtree-right tree)) (1+ number))) | |
157 | ;; Extend the range to the high from the child. | |
158 | (rtree-set-high tree (rtree-high (rtree-right tree))) | |
159 | ;; The child can't have a left child, so just transplant the | |
160 | ;; child's left right to our right tree. | |
161 | (rtree-set-right tree (rtree-right (rtree-right tree)))) | |
162 | (setq tree nil)) | |
163 | ;; Descend further to the right. | |
164 | ((rtree-right tree) | |
165 | (setq tree (rtree-right tree))) | |
166 | ;; Add a new node. | |
167 | (t | |
168 | (let ((new-node (rtree-make-node))) | |
169 | (rtree-set-low new-node number) | |
170 | (rtree-set-high new-node number) | |
171 | (rtree-set-right tree new-node) | |
172 | (setq tree nil)))))))) | |
173 | ||
174 | (defun rtree-delq (tree number) | |
175 | "Remove NUMBER from TREE destructively. Returns the new tree." | |
176 | (let ((result tree) | |
177 | prev) | |
178 | (while tree | |
179 | (cond | |
180 | ((< number (rtree-low tree)) | |
181 | (setq prev tree | |
182 | tree (rtree-left tree))) | |
183 | ((> number (rtree-high tree)) | |
184 | (setq prev tree | |
185 | tree (rtree-right tree))) | |
186 | ;; The number is in this node. | |
187 | (t | |
188 | (cond | |
189 | ;; The only entry; delete the node. | |
190 | ((= (rtree-low tree) (rtree-high tree)) | |
191 | (cond | |
192 | ;; Two children. Replace with successor value. | |
193 | ((and (rtree-left tree) (rtree-right tree)) | |
194 | (let ((parent tree) | |
195 | (successor (rtree-right tree))) | |
196 | (while (rtree-left successor) | |
197 | (setq parent successor | |
198 | successor (rtree-left successor))) | |
199 | ;; We now have the leftmost child of our right child. | |
200 | (rtree-set-range tree (rtree-range successor)) | |
201 | ;; Transplant the child (if any) to the parent. | |
202 | (rtree-set-left parent (rtree-right successor)))) | |
203 | (t | |
204 | (let ((rest (or (rtree-left tree) | |
205 | (rtree-right tree)))) | |
206 | ;; One or zero children. Remove the node. | |
207 | (cond | |
208 | ((null prev) | |
209 | (setq result rest)) | |
210 | ((eq (rtree-left prev) tree) | |
211 | (rtree-set-left prev rest)) | |
212 | (t | |
213 | (rtree-set-right prev rest))))))) | |
214 | ;; The lowest in the range; just adjust. | |
215 | ((= number (rtree-low tree)) | |
216 | (rtree-set-low tree (1+ number))) | |
217 | ;; The highest in the range; just adjust. | |
218 | ((= number (rtree-high tree)) | |
219 | (rtree-set-high tree (1- number))) | |
220 | ;; We have to split this range. | |
221 | (t | |
222 | (let ((new-node (rtree-make-node))) | |
223 | (rtree-set-low new-node (rtree-low tree)) | |
224 | (rtree-set-high new-node (1- number)) | |
225 | (rtree-set-low tree (1+ number)) | |
226 | (cond | |
227 | ;; Two children; insert the new node as the predecessor | |
228 | ;; node. | |
229 | ((and (rtree-left tree) (rtree-right tree)) | |
230 | (let ((predecessor (rtree-left tree))) | |
231 | (while (rtree-right predecessor) | |
232 | (setq predecessor (rtree-right predecessor))) | |
233 | (rtree-set-right predecessor new-node))) | |
234 | ((rtree-left tree) | |
235 | (rtree-set-right new-node tree) | |
236 | (rtree-set-left new-node (rtree-left tree)) | |
237 | (rtree-set-left tree nil) | |
238 | (cond | |
239 | ((null prev) | |
240 | (setq result new-node)) | |
241 | ((eq (rtree-left prev) tree) | |
242 | (rtree-set-left prev new-node)) | |
243 | (t | |
244 | (rtree-set-right prev new-node)))) | |
245 | (t | |
246 | (rtree-set-left tree new-node)))))) | |
247 | (setq tree nil)))) | |
248 | result)) | |
249 | ||
250 | (defun rtree-extract (tree) | |
251 | "Convert TREE to range form." | |
252 | (let (stack result) | |
253 | (while (or stack | |
254 | tree) | |
255 | (if tree | |
256 | (progn | |
257 | (push tree stack) | |
258 | (setq tree (rtree-right tree))) | |
259 | (setq tree (pop stack)) | |
260 | (push (if (= (rtree-low tree) | |
261 | (rtree-high tree)) | |
262 | (rtree-low tree) | |
263 | (rtree-range tree)) | |
264 | result) | |
265 | (setq tree (rtree-left tree)))) | |
266 | result)) | |
267 | ||
268 | (defun rtree-length (tree) | |
269 | "Return the number of numbers stored in TREE." | |
270 | (if (null tree) | |
271 | 0 | |
272 | (+ (rtree-length (rtree-left tree)) | |
273 | (1+ (- (rtree-high tree) | |
274 | (rtree-low tree))) | |
275 | (rtree-length (rtree-right tree))))) | |
276 | ||
277 | (provide 'rtree) | |
278 | ||
279 | ;;; rtree.el ends here |