diff options
Diffstat (limited to 'lisp/gnus/rtree.el')
| -rw-r--r-- | lisp/gnus/rtree.el | 281 |
1 files changed, 0 insertions, 281 deletions
diff --git a/lisp/gnus/rtree.el b/lisp/gnus/rtree.el deleted file mode 100644 index 662e043669a..00000000000 --- a/lisp/gnus/rtree.el +++ /dev/null @@ -1,281 +0,0 @@ -;;; rtree.el --- functions for manipulating range trees - -;; Copyright (C) 2010-2016 Free Software Foundation, Inc. - -;; Author: Lars Magne Ingebrigtsen <larsi@gnus.org> - -;; This file is part of GNU Emacs. - -;; GNU Emacs is free software: you can redistribute it and/or modify -;; it under the terms of the GNU General Public License as published by -;; the Free Software Foundation, either version 3 of the License, or -;; (at your option) any later version. - -;; GNU Emacs is distributed in the hope that it will be useful, -;; but WITHOUT ANY WARRANTY; without even the implied warranty of -;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the -;; GNU General Public License for more details. - -;; You should have received a copy of the GNU General Public License -;; along with GNU Emacs. If not, see <http://www.gnu.org/licenses/>. - -;;; Commentary: - -;; A "range tree" is a binary tree that stores ranges. They are -;; similar to interval trees, but do not allow overlapping intervals. - -;; A range is an ordered list of number intervals, like this: - -;; ((10 . 25) 56 78 (98 . 201)) - -;; Common operations, like lookup, deletion and insertion are O(n) in -;; a range, but an rtree is O(log n) in all these operations. -;; Transformation between a range and an rtree is O(n). - -;; The rtrees are quite simple. The structure of each node is - -;; (cons (cons low high) (cons left right)) - -;; That is, they are three cons cells, where the car of the top cell -;; is the actual range, and the cdr has the left and right child. The -;; rtrees aren't automatically balanced, but are balanced when -;; created, and can be rebalanced when deemed necessary. - -;;; Code: - -(eval-when-compile - (require 'cl)) - -(defmacro rtree-make-node () - `(list (list nil) nil)) - -(defmacro rtree-set-left (node left) - `(setcar (cdr ,node) ,left)) - -(defmacro rtree-set-right (node right) - `(setcdr (cdr ,node) ,right)) - -(defmacro rtree-set-range (node range) - `(setcar ,node ,range)) - -(defmacro rtree-low (node) - `(caar ,node)) - -(defmacro rtree-high (node) - `(cdar ,node)) - -(defmacro rtree-set-low (node number) - `(setcar (car ,node) ,number)) - -(defmacro rtree-set-high (node number) - `(setcdr (car ,node) ,number)) - -(defmacro rtree-left (node) - `(cadr ,node)) - -(defmacro rtree-right (node) - `(cddr ,node)) - -(defmacro rtree-range (node) - `(car ,node)) - -(defsubst rtree-normalize-range (range) - (when (numberp range) - (setq range (cons range range))) - range) - -(define-obsolete-function-alias 'rtree-normalise-range - 'rtree-normalize-range "25.1") - -(defun rtree-make (range) - "Make an rtree from RANGE." - ;; Normalize the range. - (unless (listp (cdr-safe range)) - (setq range (list range))) - (rtree-make-1 (cons nil range) (length range))) - -(defun rtree-make-1 (range length) - (let ((mid (/ length 2)) - (node (rtree-make-node))) - (when (> mid 0) - (rtree-set-left node (rtree-make-1 range mid))) - (rtree-set-range node (rtree-normalize-range (cadr range))) - (setcdr range (cddr range)) - (when (> (- length mid 1) 0) - (rtree-set-right node (rtree-make-1 range (- length mid 1)))) - node)) - -(defun rtree-memq (tree number) - "Return non-nil if NUMBER is present in TREE." - (while (and tree - (not (and (>= number (rtree-low tree)) - (<= number (rtree-high tree))))) - (setq tree - (if (< number (rtree-low tree)) - (rtree-left tree) - (rtree-right tree)))) - tree) - -(defun rtree-add (tree number) - "Add NUMBER to TREE." - (while tree - (cond - ;; It's already present, so we don't have to do anything. - ((and (>= number (rtree-low tree)) - (<= number (rtree-high tree))) - (setq tree nil)) - ((< number (rtree-low tree)) - (cond - ;; Extend the low range. - ((= number (1- (rtree-low tree))) - (rtree-set-low tree number) - ;; Check whether we need to merge this node with the child. - (when (and (rtree-left tree) - (= (rtree-high (rtree-left tree)) (1- number))) - ;; Extend the range to the low from the child. - (rtree-set-low tree (rtree-low (rtree-left tree))) - ;; The child can't have a right child, so just transplant the - ;; child's left tree to our left tree. - (rtree-set-left tree (rtree-left (rtree-left tree)))) - (setq tree nil)) - ;; Descend further to the left. - ((rtree-left tree) - (setq tree (rtree-left tree))) - ;; Add a new node. - (t - (let ((new-node (rtree-make-node))) - (rtree-set-low new-node number) - (rtree-set-high new-node number) - (rtree-set-left tree new-node) - (setq tree nil))))) - (t - (cond - ;; Extend the high range. - ((= number (1+ (rtree-high tree))) - (rtree-set-high tree number) - ;; Check whether we need to merge this node with the child. - (when (and (rtree-right tree) - (= (rtree-low (rtree-right tree)) (1+ number))) - ;; Extend the range to the high from the child. - (rtree-set-high tree (rtree-high (rtree-right tree))) - ;; The child can't have a left child, so just transplant the - ;; child's left right to our right tree. - (rtree-set-right tree (rtree-right (rtree-right tree)))) - (setq tree nil)) - ;; Descend further to the right. - ((rtree-right tree) - (setq tree (rtree-right tree))) - ;; Add a new node. - (t - (let ((new-node (rtree-make-node))) - (rtree-set-low new-node number) - (rtree-set-high new-node number) - (rtree-set-right tree new-node) - (setq tree nil)))))))) - -(defun rtree-delq (tree number) - "Remove NUMBER from TREE destructively. Returns the new tree." - (let ((result tree) - prev) - (while tree - (cond - ((< number (rtree-low tree)) - (setq prev tree - tree (rtree-left tree))) - ((> number (rtree-high tree)) - (setq prev tree - tree (rtree-right tree))) - ;; The number is in this node. - (t - (cond - ;; The only entry; delete the node. - ((= (rtree-low tree) (rtree-high tree)) - (cond - ;; Two children. Replace with successor value. - ((and (rtree-left tree) (rtree-right tree)) - (let ((parent tree) - (successor (rtree-right tree))) - (while (rtree-left successor) - (setq parent successor - successor (rtree-left successor))) - ;; We now have the leftmost child of our right child. - (rtree-set-range tree (rtree-range successor)) - ;; Transplant the child (if any) to the parent. - (rtree-set-left parent (rtree-right successor)))) - (t - (let ((rest (or (rtree-left tree) - (rtree-right tree)))) - ;; One or zero children. Remove the node. - (cond - ((null prev) - (setq result rest)) - ((eq (rtree-left prev) tree) - (rtree-set-left prev rest)) - (t - (rtree-set-right prev rest))))))) - ;; The lowest in the range; just adjust. - ((= number (rtree-low tree)) - (rtree-set-low tree (1+ number))) - ;; The highest in the range; just adjust. - ((= number (rtree-high tree)) - (rtree-set-high tree (1- number))) - ;; We have to split this range. - (t - (let ((new-node (rtree-make-node))) - (rtree-set-low new-node (rtree-low tree)) - (rtree-set-high new-node (1- number)) - (rtree-set-low tree (1+ number)) - (cond - ;; Two children; insert the new node as the predecessor - ;; node. - ((and (rtree-left tree) (rtree-right tree)) - (let ((predecessor (rtree-left tree))) - (while (rtree-right predecessor) - (setq predecessor (rtree-right predecessor))) - (rtree-set-right predecessor new-node))) - ((rtree-left tree) - (rtree-set-right new-node tree) - (rtree-set-left new-node (rtree-left tree)) - (rtree-set-left tree nil) - (cond - ((null prev) - (setq result new-node)) - ((eq (rtree-left prev) tree) - (rtree-set-left prev new-node)) - (t - (rtree-set-right prev new-node)))) - (t - (rtree-set-left tree new-node)))))) - (setq tree nil)))) - result)) - -(defun rtree-extract (tree) - "Convert TREE to range form." - (let (stack result) - (while (or stack - tree) - (if tree - (progn - (push tree stack) - (setq tree (rtree-right tree))) - (setq tree (pop stack)) - (push (if (= (rtree-low tree) - (rtree-high tree)) - (rtree-low tree) - (rtree-range tree)) - result) - (setq tree (rtree-left tree)))) - result)) - -(defun rtree-length (tree) - "Return the number of numbers stored in TREE." - (if (null tree) - 0 - (+ (rtree-length (rtree-left tree)) - (1+ (- (rtree-high tree) - (rtree-low tree))) - (rtree-length (rtree-right tree))))) - -(provide 'rtree) - -;;; rtree.el ends here |