1 ;;; rtree.el --- functions for manipulating range trees
3 ;; Copyright (C) 2010-2016 Free Software Foundation, Inc.
5 ;; Author: Lars Magne Ingebrigtsen <larsi@gnus.org>
7 ;; This file is part of GNU Emacs.
9 ;; GNU Emacs is free software: you can redistribute it and/or modify
10 ;; it under the terms of the GNU General Public License as published by
11 ;; the Free Software Foundation, either version 3 of the License, or
12 ;; (at your option) any later version.
14 ;; GNU Emacs is distributed in the hope that it will be useful,
15 ;; but WITHOUT ANY WARRANTY; without even the implied warranty of
16 ;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 ;; GNU General Public License for more details.
19 ;; You should have received a copy of the GNU General Public License
20 ;; along with GNU Emacs. If not, see <http://www.gnu.org/licenses/>.
24 ;; A "range tree" is a binary tree that stores ranges. They are
25 ;; similar to interval trees, but do not allow overlapping intervals.
27 ;; A range is an ordered list of number intervals, like this:
29 ;; ((10 . 25) 56 78 (98 . 201))
31 ;; Common operations, like lookup, deletion and insertion are O(n) in
32 ;; a range, but an rtree is O(log n) in all these operations.
33 ;; Transformation between a range and an rtree is O(n).
35 ;; The rtrees are quite simple. The structure of each node is
37 ;; (cons (cons low high) (cons left right))
39 ;; That is, they are three cons cells, where the car of the top cell
40 ;; is the actual range, and the cdr has the left and right child. The
41 ;; rtrees aren't automatically balanced, but are balanced when
42 ;; created, and can be rebalanced when deemed necessary.
49 (defmacro rtree-make-node ()
50 `(list (list nil) nil))
52 (defmacro rtree-set-left (node left)
53 `(setcar (cdr ,node) ,left))
55 (defmacro rtree-set-right (node right)
56 `(setcdr (cdr ,node) ,right))
58 (defmacro rtree-set-range (node range)
59 `(setcar ,node ,range))
61 (defmacro rtree-low (node)
64 (defmacro rtree-high (node)
67 (defmacro rtree-set-low (node number)
68 `(setcar (car ,node) ,number))
70 (defmacro rtree-set-high (node number)
71 `(setcdr (car ,node) ,number))
73 (defmacro rtree-left (node)
76 (defmacro rtree-right (node)
79 (defmacro rtree-range (node)
82 (defsubst rtree-normalize-range (range)
84 (setq range (cons range range)))
87 (define-obsolete-function-alias 'rtree-normalise-range
88 'rtree-normalize-range "25.1")
90 (defun rtree-make (range)
91 "Make an rtree from RANGE."
92 ;; Normalize the range.
93 (unless (listp (cdr-safe range))
94 (setq range (list range)))
95 (rtree-make-1 (cons nil range) (length range)))
97 (defun rtree-make-1 (range length)
98 (let ((mid (/ length 2))
99 (node (rtree-make-node)))
101 (rtree-set-left node (rtree-make-1 range mid)))
102 (rtree-set-range node (rtree-normalize-range (cadr range)))
103 (setcdr range (cddr range))
104 (when (> (- length mid 1) 0)
105 (rtree-set-right node (rtree-make-1 range (- length mid 1))))
108 (defun rtree-memq (tree number)
109 "Return non-nil if NUMBER is present in TREE."
111 (not (and (>= number (rtree-low tree))
112 (<= number (rtree-high tree)))))
114 (if (< number (rtree-low tree))
116 (rtree-right tree))))
119 (defun rtree-add (tree number)
120 "Add NUMBER to TREE."
123 ;; It's already present, so we don't have to do anything.
124 ((and (>= number (rtree-low tree))
125 (<= number (rtree-high tree)))
127 ((< number (rtree-low tree))
129 ;; Extend the low range.
130 ((= number (1- (rtree-low tree)))
131 (rtree-set-low tree number)
132 ;; Check whether we need to merge this node with the child.
133 (when (and (rtree-left tree)
134 (= (rtree-high (rtree-left tree)) (1- number)))
135 ;; Extend the range to the low from the child.
136 (rtree-set-low tree (rtree-low (rtree-left tree)))
137 ;; The child can't have a right child, so just transplant the
138 ;; child's left tree to our left tree.
139 (rtree-set-left tree (rtree-left (rtree-left tree))))
141 ;; Descend further to the left.
143 (setq tree (rtree-left tree)))
146 (let ((new-node (rtree-make-node)))
147 (rtree-set-low new-node number)
148 (rtree-set-high new-node number)
149 (rtree-set-left tree new-node)
153 ;; Extend the high range.
154 ((= number (1+ (rtree-high tree)))
155 (rtree-set-high tree number)
156 ;; Check whether we need to merge this node with the child.
157 (when (and (rtree-right tree)
158 (= (rtree-low (rtree-right tree)) (1+ number)))
159 ;; Extend the range to the high from the child.
160 (rtree-set-high tree (rtree-high (rtree-right tree)))
161 ;; The child can't have a left child, so just transplant the
162 ;; child's left right to our right tree.
163 (rtree-set-right tree (rtree-right (rtree-right tree))))
165 ;; Descend further to the right.
167 (setq tree (rtree-right tree)))
170 (let ((new-node (rtree-make-node)))
171 (rtree-set-low new-node number)
172 (rtree-set-high new-node number)
173 (rtree-set-right tree new-node)
174 (setq tree nil))))))))
176 (defun rtree-delq (tree number)
177 "Remove NUMBER from TREE destructively. Returns the new tree."
182 ((< number (rtree-low tree))
184 tree (rtree-left tree)))
185 ((> number (rtree-high tree))
187 tree (rtree-right tree)))
188 ;; The number is in this node.
191 ;; The only entry; delete the node.
192 ((= (rtree-low tree) (rtree-high tree))
194 ;; Two children. Replace with successor value.
195 ((and (rtree-left tree) (rtree-right tree))
197 (successor (rtree-right tree)))
198 (while (rtree-left successor)
199 (setq parent successor
200 successor (rtree-left successor)))
201 ;; We now have the leftmost child of our right child.
202 (rtree-set-range tree (rtree-range successor))
203 ;; Transplant the child (if any) to the parent.
204 (rtree-set-left parent (rtree-right successor))))
206 (let ((rest (or (rtree-left tree)
207 (rtree-right tree))))
208 ;; One or zero children. Remove the node.
212 ((eq (rtree-left prev) tree)
213 (rtree-set-left prev rest))
215 (rtree-set-right prev rest)))))))
216 ;; The lowest in the range; just adjust.
217 ((= number (rtree-low tree))
218 (rtree-set-low tree (1+ number)))
219 ;; The highest in the range; just adjust.
220 ((= number (rtree-high tree))
221 (rtree-set-high tree (1- number)))
222 ;; We have to split this range.
224 (let ((new-node (rtree-make-node)))
225 (rtree-set-low new-node (rtree-low tree))
226 (rtree-set-high new-node (1- number))
227 (rtree-set-low tree (1+ number))
229 ;; Two children; insert the new node as the predecessor
231 ((and (rtree-left tree) (rtree-right tree))
232 (let ((predecessor (rtree-left tree)))
233 (while (rtree-right predecessor)
234 (setq predecessor (rtree-right predecessor)))
235 (rtree-set-right predecessor new-node)))
237 (rtree-set-right new-node tree)
238 (rtree-set-left new-node (rtree-left tree))
239 (rtree-set-left tree nil)
242 (setq result new-node))
243 ((eq (rtree-left prev) tree)
244 (rtree-set-left prev new-node))
246 (rtree-set-right prev new-node))))
248 (rtree-set-left tree new-node))))))
252 (defun rtree-extract (tree)
253 "Convert TREE to range form."
260 (setq tree (rtree-right tree)))
261 (setq tree (pop stack))
262 (push (if (= (rtree-low tree)
267 (setq tree (rtree-left tree))))
270 (defun rtree-length (tree)
271 "Return the number of numbers stored in TREE."
274 (+ (rtree-length (rtree-left tree))
275 (1+ (- (rtree-high tree)
277 (rtree-length (rtree-right tree)))))
281 ;;; rtree.el ends here