cgit.sxemacs.org Git - gnus/blob - lisp/rtree.el

   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-left (node)
  69   `(cadr ,node))
  70
  71 (defmacro rtree-right (node)
  72   `(cddr ,node))
  73
  74 (defsubst rtree-normalise-range (range)
  75   (when (numberp range)
  76     (setq range (cons range range)))
  77   range)
  78
  79 (defun rtree-make (range)
  80   "Make an rtree from RANGE."
  81   ;; Normalize the range.
  82   (unless (listp (cdr-safe range))
  83     (setq range (list range)))
  84   (rtree-make-1 (cons nil range) (length range)))
  85
  86 (defun rtree-make-1 (range length)
  87   (let ((mid (/ length 2))
  88         (node (rtree-make-node)))
  89     (when (> mid 0)
  90       (rtree-set-left node (rtree-make-1 range mid)))
  91     (rtree-set-range node (rtree-normalise-range (cadr range)))
  92     (setcdr range (cddr range))
  93     (when (> (- length mid 1) 0)
  94       (rtree-set-right node (rtree-make-1 range (- length mid 1))))
  95     node))
  96
  97 (defun rtree-memq (tree number)
  98   (cond
  99    ((and (>= number (rtree-low tree))
 100          (<= number (rtree-high tree)))
 101     t)
 102    ((< number (rtree-low tree))
 103     (and (rtree-left tree)
 104          (rtree-memq (rtree-left tree) number)))
 105    (t
 106     (and (rtree-right tree)
 107          (rtree-memq (rtree-right tree) number)))))
 108
 109 (provide 'rtree)
 110
 111 ;;; rtree.el ends here