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-left (node)
71 (defmacro rtree-right (node)
74 (defmacro rtree-range (node)
77 (defsubst rtree-normalise-range (range)
79 (setq range (cons range range)))
82 (defun rtree-make (range)
83 "Make an rtree from RANGE."
84 ;; Normalize the range.
85 (unless (listp (cdr-safe range))
86 (setq range (list range)))
87 (rtree-make-1 (cons nil range) (length range)))
89 (defun rtree-make-1 (range length)
90 (let ((mid (/ length 2))
91 (node (rtree-make-node)))
93 (rtree-set-left node (rtree-make-1 range mid)))
94 (rtree-set-range node (rtree-normalise-range (cadr range)))
95 (setcdr range (cddr range))
96 (when (> (- length mid 1) 0)
97 (rtree-set-right node (rtree-make-1 range (- length mid 1))))
100 (defun rtree-memq (tree number)
101 "Return non-nil if NUMBER is present in TREE."
103 (not (and (>= number (rtree-low tree))
104 (<= number (rtree-high tree)))))
106 (if (< number (rtree-low tree))
108 (rtree-right tree))))
111 (defun rtree-extract (tree)
112 "Convert TREE to range form."
119 (setq tree (rtree-right tree)))
120 (setq tree (pop stack))
121 (push (if (= (rtree-low tree)
126 (setq tree (rtree-left tree))))
131 ;;; rtree.el ends here