1 ;;; rtree.el --- functions for manipulating range trees
2 ;; Copyright (C) 2010 Free Software Foundation, Inc.
4 ;; Author: Lars Magne Ingebrigtsen <larsi@gnus.org>
6 ;; This file is part of GNU Emacs.
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)
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.
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.
25 ;; A "range tree" is a binary tree that stores ranges. They are
26 ;; similar to interval trees, but do not allow overlapping intervals.
28 ;; A range is an ordered list of number intervals, like this:
30 ;; ((10 . 25) 56 78 (98 . 201))
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).
36 ;; The rtrees are quite simple. The structure of each node is
38 ;; (cons (cons low high) (cons left right))
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.
50 (defmacro rtree-make-node ()
51 `(list (list nil) nil))
53 (defmacro rtree-set-left (node left)
54 `(setcar (cdr ,node) ,left))
56 (defmacro rtree-set-right (node right)
57 `(setcdr (cdr ,node) ,right))
59 (defmacro rtree-set-range (node range)
60 `(setcar ,node ,range))
62 (defmacro rtree-low (node)
65 (defmacro rtree-high (node)
68 (defmacro rtree-set-low (node number)
69 `(setcar (car ,node) ,number))
71 (defmacro rtree-set-high (node number)
72 `(setcdr (car ,node) ,number))
74 (defmacro rtree-left (node)
77 (defmacro rtree-right (node)
80 (defmacro rtree-range (node)
83 (defsubst rtree-normalise-range (range)
85 (setq range (cons range range)))
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)))
95 (defun rtree-make-1 (range length)
96 (let ((mid (/ length 2))
97 (node (rtree-make-node)))
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))))
106 (defun rtree-memq (tree number)
107 "Return non-nil if NUMBER is present in TREE."
109 (not (and (>= number (rtree-low tree))
110 (<= number (rtree-high tree)))))
112 (if (< number (rtree-low tree))
114 (rtree-right tree))))
117 (defun rtree-add (tree number)
118 "Add NUMBER to TREE."
121 ;; It's already present, so we don't have to do anything.
122 ((and (>= number (rtree-low tree))
123 (<= number (rtree-high tree)))
125 ((< number (rtree-low tree))
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))))
139 ;; Descend further to the left.
141 (setq tree (rtree-left tree)))
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)
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))))
163 ;; Descend further to the right.
165 (setq tree (rtree-right tree)))
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))))))))
174 (defun rtree-delq (tree number)
175 "Remove NUMBER from TREE destructively. Returns the new tree."
180 ((< number (rtree-low tree))
182 tree (rtree-left tree)))
183 ((> number (rtree-high tree))
185 tree (rtree-right tree)))
186 ;; The number is in this node.
189 ;; The only entry; delete the node.
190 ((= (rtree-low tree) (rtree-high tree))
192 ;; Two children. Replace with successor value.
193 ((and (rtree-left tree) (rtree-right 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))))
204 (let ((rest (or (rtree-left tree)
205 (rtree-right tree))))
206 ;; One or zero children. Remove the node.
210 ((eq (rtree-left prev) tree)
211 (rtree-set-left prev rest))
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.
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))
227 ;; Two children; insert the new node as the predecessor
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)))
235 (rtree-set-right new-node tree)
236 (rtree-set-left new-node (rtree-left tree))
237 (rtree-set-left tree nil)
240 (setq result new-node))
241 ((eq (rtree-left prev) tree)
242 (rtree-set-left prev new-node))
244 (rtree-set-right prev new-node))))
246 (rtree-set-left tree new-node))))))
250 (defun rtree-extract (tree)
251 "Convert TREE to range form."
258 (setq tree (rtree-right tree)))
259 (setq tree (pop stack))
260 (push (if (= (rtree-low tree)
265 (setq tree (rtree-left tree))))
270 ;;; rtree.el ends here