annotate lisp/gnus/rtree.el @ 112451:98ad7c9e56a3

gnus-html.el (gnus-html-image-fetched): Don't kill the temporary buffer after being called. It's apparently being killed by url.el, and killing it made point move to end-of-buffer in a random buffer. shr.el (shr-image-fetched): Ditto. shr.el (shr-image-fetched): Avoid having point move in the article buffer. gnus-html.el (gnus-html-image-fetched): Kill the buffer anyway, and fix the bug in url-http.el instead. shr.el (shr-image-fetched): Ditto. gravatar.el (gravatar-retrieve): Be silent when retrieving. gnus-gravatar.el (gnus-gravatar-insert): Don't move point around in the article buffer. (gnus-gravatar-insert): Use blank space from the current buffer to avoid breaking text properties. This makes X-Sent updating work again. gnus-art.el (gnus-article-read-summary-keys): Don't call disabled commands.
author Katsumi Yamaoka <yamaoka@jpl.org>
date Mon, 24 Jan 2011 04:10:19 +0000
parents b1eac6d41a93
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
111789
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
1 ;;; rtree.el --- functions for manipulating range trees
111795
5deef9141286 Standardize license notices in new files.
Glenn Morris <rgm@gnu.org>
parents: 111789
diff changeset
2
112235
b1eac6d41a93 [Gnus] Update copyright years.
Katsumi Yamaoka <yamaoka@jpl.org>
parents: 111795
diff changeset
3 ;; Copyright (C) 2010, 2011 Free Software Foundation, Inc.
111789
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
4
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
5 ;; Author: Lars Magne Ingebrigtsen <larsi@gnus.org>
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
6
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
7 ;; This file is part of GNU Emacs.
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
8
111795
5deef9141286 Standardize license notices in new files.
Glenn Morris <rgm@gnu.org>
parents: 111789
diff changeset
9 ;; GNU Emacs is free software: you can redistribute it and/or modify
111789
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
10 ;; it under the terms of the GNU General Public License as published by
111795
5deef9141286 Standardize license notices in new files.
Glenn Morris <rgm@gnu.org>
parents: 111789
diff changeset
11 ;; the Free Software Foundation, either version 3 of the License, or
5deef9141286 Standardize license notices in new files.
Glenn Morris <rgm@gnu.org>
parents: 111789
diff changeset
12 ;; (at your option) any later version.
111789
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
13
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
14 ;; GNU Emacs is distributed in the hope that it will be useful,
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
15 ;; but WITHOUT ANY WARRANTY; without even the implied warranty of
111795
5deef9141286 Standardize license notices in new files.
Glenn Morris <rgm@gnu.org>
parents: 111789
diff changeset
16 ;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
111789
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
17 ;; GNU General Public License for more details.
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
18
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
19 ;; You should have received a copy of the GNU General Public License
111795
5deef9141286 Standardize license notices in new files.
Glenn Morris <rgm@gnu.org>
parents: 111789
diff changeset
20 ;; along with GNU Emacs. If not, see <http://www.gnu.org/licenses/>.
111789
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
21
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
22 ;;; Commentary:
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
23
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
24 ;; A "range tree" is a binary tree that stores ranges. They are
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
25 ;; similar to interval trees, but do not allow overlapping intervals.
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
26
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
27 ;; A range is an ordered list of number intervals, like this:
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
28
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
29 ;; ((10 . 25) 56 78 (98 . 201))
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
30
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
31 ;; Common operations, like lookup, deletion and insertion are O(n) in
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
32 ;; a range, but an rtree is O(log n) in all these operations.
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
33 ;; Transformation between a range and an rtree is O(n).
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
34
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
35 ;; The rtrees are quite simple. The structure of each node is
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
36
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
37 ;; (cons (cons low high) (cons left right))
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
38
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
39 ;; That is, they are three cons cells, where the car of the top cell
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
40 ;; is the actual range, and the cdr has the left and right child. The
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
41 ;; rtrees aren't automatically balanced, but are balanced when
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
42 ;; created, and can be rebalanced when deemed necessary.
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
43
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
44 ;;; Code:
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
45
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
46 (eval-when-compile
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
47 (require 'cl))
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
48
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
49 (defmacro rtree-make-node ()
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
50 `(list (list nil) nil))
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
51
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
52 (defmacro rtree-set-left (node left)
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
53 `(setcar (cdr ,node) ,left))
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
54
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
55 (defmacro rtree-set-right (node right)
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
56 `(setcdr (cdr ,node) ,right))
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
57
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
58 (defmacro rtree-set-range (node range)
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
59 `(setcar ,node ,range))
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
60
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
61 (defmacro rtree-low (node)
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
62 `(caar ,node))
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
63
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
64 (defmacro rtree-high (node)
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
65 `(cdar ,node))
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
66
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
67 (defmacro rtree-set-low (node number)
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
68 `(setcar (car ,node) ,number))
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
69
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
70 (defmacro rtree-set-high (node number)
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
71 `(setcdr (car ,node) ,number))
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
72
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
73 (defmacro rtree-left (node)
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
74 `(cadr ,node))
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
75
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
76 (defmacro rtree-right (node)
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
77 `(cddr ,node))
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
78
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
79 (defmacro rtree-range (node)
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
80 `(car ,node))
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
81
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
82 (defsubst rtree-normalise-range (range)
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
83 (when (numberp range)
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
84 (setq range (cons range range)))
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
85 range)
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
86
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
87 (defun rtree-make (range)
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
88 "Make an rtree from RANGE."
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
89 ;; Normalize the range.
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
90 (unless (listp (cdr-safe range))
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
91 (setq range (list range)))
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
92 (rtree-make-1 (cons nil range) (length range)))
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
93
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
94 (defun rtree-make-1 (range length)
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
95 (let ((mid (/ length 2))
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
96 (node (rtree-make-node)))
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
97 (when (> mid 0)
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
98 (rtree-set-left node (rtree-make-1 range mid)))
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
99 (rtree-set-range node (rtree-normalise-range (cadr range)))
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
100 (setcdr range (cddr range))
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
101 (when (> (- length mid 1) 0)
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
102 (rtree-set-right node (rtree-make-1 range (- length mid 1))))
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
103 node))
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
104
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
105 (defun rtree-memq (tree number)
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
106 "Return non-nil if NUMBER is present in TREE."
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
107 (while (and tree
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
108 (not (and (>= number (rtree-low tree))
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
109 (<= number (rtree-high tree)))))
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
110 (setq tree
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
111 (if (< number (rtree-low tree))
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
112 (rtree-left tree)
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
113 (rtree-right tree))))
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
114 tree)
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
115
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
116 (defun rtree-add (tree number)
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
117 "Add NUMBER to TREE."
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
118 (while tree
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
119 (cond
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
120 ;; It's already present, so we don't have to do anything.
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
121 ((and (>= number (rtree-low tree))
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
122 (<= number (rtree-high tree)))
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
123 (setq tree nil))
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
124 ((< number (rtree-low tree))
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
125 (cond
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
126 ;; Extend the low range.
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
127 ((= number (1- (rtree-low tree)))
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
128 (rtree-set-low tree number)
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
129 ;; Check whether we need to merge this node with the child.
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
130 (when (and (rtree-left tree)
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
131 (= (rtree-high (rtree-left tree)) (1- number)))
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
132 ;; Extend the range to the low from the child.
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
133 (rtree-set-low tree (rtree-low (rtree-left tree)))
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
134 ;; The child can't have a right child, so just transplant the
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
135 ;; child's left tree to our left tree.
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
136 (rtree-set-left tree (rtree-left (rtree-left tree))))
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
137 (setq tree nil))
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
138 ;; Descend further to the left.
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
139 ((rtree-left tree)
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
140 (setq tree (rtree-left tree)))
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
141 ;; Add a new node.
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
142 (t
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
143 (let ((new-node (rtree-make-node)))
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
144 (rtree-set-low new-node number)
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
145 (rtree-set-high new-node number)
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
146 (rtree-set-left tree new-node)
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
147 (setq tree nil)))))
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
148 (t
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
149 (cond
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
150 ;; Extend the high range.
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
151 ((= number (1+ (rtree-high tree)))
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
152 (rtree-set-high tree number)
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
153 ;; Check whether we need to merge this node with the child.
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
154 (when (and (rtree-right tree)
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
155 (= (rtree-low (rtree-right tree)) (1+ number)))
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
156 ;; Extend the range to the high from the child.
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
157 (rtree-set-high tree (rtree-high (rtree-right tree)))
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
158 ;; The child can't have a left child, so just transplant the
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
159 ;; child's left right to our right tree.
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
160 (rtree-set-right tree (rtree-right (rtree-right tree))))
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
161 (setq tree nil))
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
162 ;; Descend further to the right.
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
163 ((rtree-right tree)
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
164 (setq tree (rtree-right tree)))
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
165 ;; Add a new node.
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
166 (t
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
167 (let ((new-node (rtree-make-node)))
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
168 (rtree-set-low new-node number)
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
169 (rtree-set-high new-node number)
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
170 (rtree-set-right tree new-node)
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
171 (setq tree nil))))))))
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
172
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
173 (defun rtree-delq (tree number)
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
174 "Remove NUMBER from TREE destructively. Returns the new tree."
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
175 (let ((result tree)
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
176 prev)
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
177 (while tree
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
178 (cond
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
179 ((< number (rtree-low tree))
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
180 (setq prev tree
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
181 tree (rtree-left tree)))
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
182 ((> number (rtree-high tree))
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
183 (setq prev tree
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
184 tree (rtree-right tree)))
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
185 ;; The number is in this node.
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
186 (t
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
187 (cond
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
188 ;; The only entry; delete the node.
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
189 ((= (rtree-low tree) (rtree-high tree))
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
190 (cond
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
191 ;; Two children. Replace with successor value.
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
192 ((and (rtree-left tree) (rtree-right tree))
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
193 (let ((parent tree)
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
194 (successor (rtree-right tree)))
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
195 (while (rtree-left successor)
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
196 (setq parent successor
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
197 successor (rtree-left successor)))
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
198 ;; We now have the leftmost child of our right child.
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
199 (rtree-set-range tree (rtree-range successor))
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
200 ;; Transplant the child (if any) to the parent.
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
201 (rtree-set-left parent (rtree-right successor))))
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
202 (t
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
203 (let ((rest (or (rtree-left tree)
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
204 (rtree-right tree))))
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
205 ;; One or zero children. Remove the node.
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
206 (cond
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
207 ((null prev)
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
208 (setq result rest))
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
209 ((eq (rtree-left prev) tree)
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
210 (rtree-set-left prev rest))
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
211 (t
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
212 (rtree-set-right prev rest)))))))
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
213 ;; The lowest in the range; just adjust.
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
214 ((= number (rtree-low tree))
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
215 (rtree-set-low tree (1+ number)))
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
216 ;; The highest in the range; just adjust.
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
217 ((= number (rtree-high tree))
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
218 (rtree-set-high tree (1- number)))
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
219 ;; We have to split this range.
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
220 (t
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
221 (let ((new-node (rtree-make-node)))
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
222 (rtree-set-low new-node (rtree-low tree))
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
223 (rtree-set-high new-node (1- number))
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
224 (rtree-set-low tree (1+ number))
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
225 (cond
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
226 ;; Two children; insert the new node as the predecessor
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
227 ;; node.
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
228 ((and (rtree-left tree) (rtree-right tree))
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
229 (let ((predecessor (rtree-left tree)))
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
230 (while (rtree-right predecessor)
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
231 (setq predecessor (rtree-right predecessor)))
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
232 (rtree-set-right predecessor new-node)))
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
233 ((rtree-left tree)
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
234 (rtree-set-right new-node tree)
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
235 (rtree-set-left new-node (rtree-left tree))
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
236 (rtree-set-left tree nil)
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
237 (cond
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
238 ((null prev)
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
239 (setq result new-node))
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
240 ((eq (rtree-left prev) tree)
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
241 (rtree-set-left prev new-node))
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
242 (t
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
243 (rtree-set-right prev new-node))))
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
244 (t
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
245 (rtree-set-left tree new-node))))))
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
246 (setq tree nil))))
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
247 result))
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
248
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
249 (defun rtree-extract (tree)
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
250 "Convert TREE to range form."
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
251 (let (stack result)
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
252 (while (or stack
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
253 tree)
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
254 (if tree
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
255 (progn
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
256 (push tree stack)
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
257 (setq tree (rtree-right tree)))
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
258 (setq tree (pop stack))
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
259 (push (if (= (rtree-low tree)
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
260 (rtree-high tree))
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
261 (rtree-low tree)
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
262 (rtree-range tree))
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
263 result)
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
264 (setq tree (rtree-left tree))))
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
265 result))
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
266
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
267 (defun rtree-length (tree)
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
268 "Return the number of numbers stored in TREE."
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
269 (if (null tree)
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
270 0
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
271 (+ (rtree-length (rtree-left tree))
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
272 (1+ (- (rtree-high tree)
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
273 (rtree-low tree)))
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
274 (rtree-length (rtree-right tree)))))
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
275
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
276 (provide 'rtree)
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
277
f97704487fb3 Merge changes made in Gnus trunk.
Katsumi Yamaoka <yamaoka@jpl.org>
parents:
diff changeset
278 ;;; rtree.el ends here