source: project/release/3/rb-tree/trunk/rb-tree-eggdoc.scm @ 12430

Last change on this file since 12430 was 12430, checked in by Ivan Raikov, 11 years ago

Version set to 2.5.

File size: 15.0 KB
Line 
1
2(use eggdoc)
3
4(define doc
5  `((eggdoc:begin
6     (name "rb-tree")
7     (description "A sorted dictionary data structure based on red-black trees.")
8     (author (url "http://chicken.wiki.br/ivan raikov" "Ivan Raikov"))
9
10     (history 
11      (version "2.5" "Fixes to for-each-ascending/descending")
12      (version "2.3" "Build script updated for better cross-platform compatibility")
13      (version "2.2" "Added fold-limit procedures")
14      (version "2.1" "Added fold-partial procedures")
15      (version "2.0" "Added side-effect-free put and delete procedures")
16      (version "1.0" "Initial release"))
17
18     (requires (url "datatype.html" "datatype"))
19
20     (usage "(require-extension rb-tree)")
21
22     (download "rb-tree.egg")
23
24     (documentation
25     
26      (p "The " (tt "rb-tree") " library is based on the SML/NJ "
27         "library implementation of red-black trees, which is in turn "
28         "based on Chris Okasaki's implementation of red-black trees.  "
29         "The delete function is based on the description in Cormen, "
30         "Leiserson, and Rivest.")
31
32      (p "The present implementation code defines a red-black tree object that "
33         "implements an ordered dictionary mapping of keys to "
34         "values. The object responds to a variety of query and update "
35         "messages, including methods for finding the minimum and "
36         "maximum keys and their associated values as well as "
37         "traversing the tree in an ascending or descending order of "
38         "keys. Looking up an arbitrary or the min/max keys, and "
39         "deleting the min/max keys require no more key comparisons "
40         "than the depth of the tree, which is O(log n) where n is the "
41         "total number of keys in the tree.")
42
43      (p "The rb-tree object is created by procedure " (tt "make-rb-tree") 
44         ", the only user-visible procedure defined in this egg: "
45         
46         (procedure "make-rb-tree:: KEY-COMPARE-PROC -> SELECTOR"
47                    (p "where KEY-COMPARE-PROC is a user-supplied function "
48                       "that takes two keys and returns a "
49                       "negative, positive, or zero number "
50                       "depending on how the first key compares to "
51                       "the second. ")
52                    (p "The returned selector procedure can take one of the following arguments: "
53                       (symbol-table 
54
55                        (describe "'get" 
56                                  ("returns a procedure " (tt "LAMBDA KEY . DEFAULT-CLAUSE") 
57                                   " which searches the red-black tree for an association with a given "
58                                   (tt "KEY") ", and returns a (key . value) pair of the found association. "
59                                   "If an association with " (tt "KEY") " cannot be located in the red-black tree, "
60                                   "the PROC returns the result of evaluating the " (tt "DEFAULT-CLAUSE") ". "
61                                   "If the default clause is omitted, an error is signalled. "
62                                   (tt "KEY") " must be comparable to the keys in the red-black tree "
63                                   "by a key-compare predicate (which has been specified "
64                                   "when the red-black tree was created)"))
65                       
66                        (describe "'get-min"
67                                      ("returns a (key . value) pair for an association in the "
68                                       "red-black tree with the smallest key. If the red-black tree is empty, an error "
69                                       "is signalled."))
70                       
71                        (describe "'delete-min!"
72                                  ("removes the min key and the corresponding association "
73                                   "from the red-black tree. Returns a (key . value) pair of the "
74                                   "removed association. If the red-black tree is empty, an error "
75                                   "is signalled. "))
76                       
77                        (describe "'get-max"
78                                  ("returns a (key . value) pair for an association in the "
79                                   "red-black tree with the largest key. If the red-black tree is empty, an error "
80                                   "is signalled."))
81                       
82                        (describe "'delete-max!"
83                                  ("removes the max key and the corresponding association "
84                                   "from the red-black tree. Returns a (key . value) pair of the "
85                                   "removed association. If the red-black tree is empty, an error is signalled.")) 
86                       
87                        (describe "'empty?"
88                                  ("returns " (tt "#t") " if the red-black tree is empty"))
89                       
90                        (describe "'size"
91                                  ("returns the size (the number of associations) in the red-black tree"))
92                       
93                       
94                        (describe "'depth"
95                                  ("returns the depth of the tree. It requires "
96                                   "the complete traversal of the tree, so use sparingly"))
97                       
98                       
99                        (describe "'clear!"
100                                  ("removes all associations from the red-black tree (thus making it empty)"))
101                       
102                        (describe "'put!"
103                                  ("returns a procedure " (tt "LAMBDA KEY VALUE") 
104                                   " which, given a " (tt "KEY") " and a " (tt "VALUE") 
105                                   ", adds the corresponding association to the red-black tree. "
106                                   "If an association with the same " (tt "KEY") 
107                                   " already exists, its value is replaced with the "
108                                   (tt "VALUE") " (and the old (key . value) association is returned). "
109                                   "Otherwise, the return value is " (tt "#f") "."))
110                       
111                        (describe "'put"
112                                  ("pure variant of " (tt "PUT!") "; it returns a new red-black tree "
113                                   "object that contains the given association, while the original "
114                                   "red-black tree object is unmodified. "))
115                       
116                        (describe "'delete!"
117                                  ("returns a procedure " (tt "LAMBDA KEY . DEFAULT-CLAUSE")
118                                   " which searches the red-black tree for an association with a given "
119                                   (tt "KEY") ", deletes it, and returns a (key . value) pair of the found "
120                                   "and deleted association. If an association with the KEY cannot be located "
121                                   "in the red-black tree, the " (tt "PROC") " returns the result of evaluating "
122                                   (tt "DEFAULT-CLAUSE") ". " 
123                                   "If the default clause is omitted, an error is signalled. "))
124
125                        (describe "'delete"
126                                  ("pure variant of " (tt "DELETE!") "; if the specified key is found, "
127                                   "it returns a new red-black tree object that no longer contains the "
128                                   "association specified by that key, while the original "
129                                   "red-black tree object is unmodified. If the key is not found, "
130                                   "the behavior of this procedure is identical to " (tt "DELETE!") ". "))
131                       
132                        (describe "'for-each-ascending"
133                                  ("returns a procedure " (tt "LAMBDA PROC") 
134                                   " that will apply the given procedure PROC to each (key . value) "
135                                   "association of the red-black tree, from the one with the smallest key "
136                                   "all the way to the one with the max key, in an ascending order "
137                                   "of keys. "))
138                       
139                        (describe "'for-each-descending"
140                                  ("returns a procedure " (tt "LAMBDA PROC") " that will apply the given "
141                                   "procedure " (tt "PROC") "to each (key . value) association of the red-black tree, "
142                                   "in the descending order of keys. "))
143                       
144                        (describe "'map"
145                                  ("returns a procedure " (tt "LAMBDA PROC") " that will apply the given "
146                                   "procedure " (tt "PROC") "to the value component of each association in "
147                                   "the red-black tree, in the ascending order of keys, "
148                                   "and will construct a copy of the tree that contains the values "
149                                   "returned by that procedure." ))
150                       
151                        (describe "'mapi"
152                                  ("returns a procedure " (tt "LAMBDA PROC") " that will apply the given "
153                                   "procedure " (tt "PROC") "to each (key . value) association in "
154                                   "the red-black tree, in the ascending order of keys, "
155                                   "and will construct a copy of the tree that contains the values "
156                                   "returned by that procedure." ))
157                       
158                        (describe "'fold"
159                                  ("returns a procedure " (tt "LAMBDA PROC INITIAL") " such that, "
160                                   "given the associations in the tree ordered by the descending order of keys: "
161                                   (tt "(key-n . value-n) ... (key-2 . value-2) (key-1 . value-1) ") " "
162                                   "the procedure returns the result of the successive function applications "
163                                   (tt "(PROC value-1 (PROC value-2 ... (PROC value-n INITIAL)") ". "))
164                       
165                        (describe "'foldi"
166                                  ("returns a procedure " (tt "LAMBDA PROC INITIAL") " such that, "
167                                   "given the associations in the tree ordered by the descending order of keys: "
168                                   (tt "(key-n . value-n) ... (key-2 . value-2) (key-1 . value-1) ") " "
169                                   "the procedure returns the result of the successive function applications "
170                                   (tt "(PROC key-1 value-1 (PROC key-2 value-2 ... (PROC key-n value-n INITIAL)") ". "))
171
172                        (describe "'fold-right"
173                                  ("returns a procedure " (tt "LAMBDA PROC INITIAL") " such that, "
174                                   "given the associations in the tree ordered by the ascending order of keys: "
175                                   (tt "(key-1 . value-1) (key-2 . value-2) ... (key-n . value-n) ") " "
176                                   "the procedure returns the result of the successive function applications "
177                                   (tt "(PROC value-n ... (PROC value-2 (PROC value-1 INITIAL)") ". "))
178                       
179                        (describe "'foldi-right"
180                                  ("returns a procedure " (tt "LAMBDA PROC INITIAL") " such that, "
181                                   "given the associations in the tree ordered by the ascending order of keys: "
182                                   (tt "(key-1 . value-1) (key-2 . value-2) ... (key-n . value-n) ") " "
183                                   "the procedure returns the result of the successive function applications "
184                                   (tt "(PROC key-n value-n ... (PROC key-2 value-2 (PROC key-1 value-1 INITIAL)") ". "))
185
186                        (describe "'fold-partial"
187                                  ("returns a procedure " (tt "LAMBDA PRED PROC INITIAL") " such that, "
188                                   "given the associations in the tree ordered by the descending order of keys: "
189                                   (tt "(key-n . value-n) ... (key-2 . value-2) (key-1 . value-1) ") " "
190                                   "the procedure returns the result of the successive function applications "
191                                   (tt "(PROC value-i ... (PROC value-n INITIAL)") ", "
192                                   "where " (tt "i <= n") " and " (tt "(PRED x)") " holds true for all " 
193                                   (tt "x = (value-n) ... (value-i)") ". "
194                                   "In other words, this function acts like " (tt "fold") " on the ordered subset "
195                                   "of the values " (tt "x") " in the tree such that " (tt "(PRED x)") " is true. "))
196
197                        (describe "'foldi-partial"
198                                  ("returns a procedure " (tt "LAMBDA PRED PROC INITIAL") " such that, "
199                                   "given the associations in the tree ordered by the descending order of keys: "
200                                   (tt "(key-n . value-n) ... (key-2 . value-2) (key-1 . value-1) ") " "
201                                   "the procedure returns the result of the successive function applications "
202                                   (tt "(PROC key-i value-i ... (PROC key-n value-n INITIAL)") ", "
203                                   "where " (tt "i <= n") " and " (tt "(PRED xk x)") " holds true for all " 
204                                   (tt "x = (value-n) ... (value-i)") " and "  (tt "xk = (key-n) ... (key-i)") ". "
205                                   "In other words, this function acts like " (tt "foldi") " on the ordered subset "
206                                   "of the key-value pairs " (tt "(k . x)") " in the tree such that " 
207                                   (tt "(PRED k x)") " is true. "))
208
209                        (describe "'fold-right-partial"
210                                  ("returns a procedure " (tt "LAMBDA PRED PROC INITIAL") " such that, "
211                                   "given the associations in the tree ordered by the ascending order of keys: "
212                                   (tt "(key-1 . value-1) (key-2 . value-2) ... (key-n . value-n) ") " "
213                                   "the procedure returns the result of the successive function applications "
214                                   (tt "(PROC value-1 ... (PROC value-i INITIAL)") ", "
215                                   "where " (tt "i <= n") " and " (tt "(PRED x)") " holds true for all " 
216                                   (tt "x = (value-1) ... (value-i)") ". "
217                                   "In other words, this function acts like " (tt "fold-right") " on the ordered subset "
218                                   "of the values " (tt "x") " in the tree such that " (tt "(PRED x)") " is true. "))
219
220                        (describe "'foldi-right-partial"
221                                  ("returns a procedure " (tt "LAMBDA PRED PROC INITIAL") " such that, "
222                                   "given the associations in the tree ordered by the descending order of keys: "
223                                   (tt "(key-1 . value-1) (key-2 . value-2) ... (key-1 . value-1) ") " "
224                                   "the procedure returns the result of the successive function applications "
225                                   (tt "(PROC key-1 value-1 ... (PROC key-i value-i INITIAL)") ", "
226                                   "where " (tt "i <= n") " and " (tt "(PRED xk x)") " holds true for all " 
227                                   (tt "x = (value-1) ... (value-i)") " and "  (tt "xk = (key-1) ... (key-i)") ". "
228                                   "In other words, this function acts like " (tt "foldi-right") " on the ordered subset "
229                                   "of the key-value pairs " (tt "(k . x)") " in the tree such that " 
230                                   (tt "(PRED k x)") " is true. "))
231
232                        (describe "'fold-limit"
233                                  ("returns a procedure " (tt "LAMBDA PRED PROC INITIAL") " such that, "
234                                   "given the associations in the tree ordered by the descending order of keys: "
235                                   (tt "(key-n . value-n) ... (key-2 . value-2) (key-1 . value-1) ") " "
236                                   "the procedure returns the result of the successive function applications "
237                                   (tt "(PROC value-i ... (PROC value-n INITIAL)") ", "
238                                   "where " (tt "i <= n") " and " (tt "(PRED x)") " does not hold true for all " 
239                                   (tt "x = (PROC value-n INITIAL)  ... (PROC (value-i) (PROC value-(i-1)...") ". "))
240
241                        (describe "'fold-right-limit"
242                                  ("returns a procedure " (tt "LAMBDA PRED PROC INITIAL") " such that, "
243                                   "given the associations in the tree ordered by the descending order of keys: "
244                                   (tt "(key-1 . value-1) (key-2 . value-2) ... (key-i . value-1) ") " "
245                                   "the procedure returns the result of the successive function applications "
246                                   (tt "(PROC value-i ... (PROC value-1 INITIAL)") ", "
247                                   "where " (tt "i <= n") " and " (tt "(PRED x)") " does not hold true for all " 
248                                   (tt "x = (PROC value-1 INITIAL)  ... (PROC (value-i) (PROC value-(i-1)...") ". "))
249                        )))))
250
251     (examples (pre #<<EOF
252;; "--> Sorting of a set of numbers via a red-black tree"
253
254(define-macro (++! x) `(set! ,x (fx+ 1 ,x)))
255(define-macro (++ x) `(fx+ 1 ,x))
256(define-macro (--! x) `(set! ,x (fx- ,x 1)))
257(define-macro (-- x) `(fx- ,x 1))
258
259(let
260  ((min-key -1) (max-key 10)
261   (rb-tree (make-rb-tree (lambda (x y) (- x y))))
262   ;; a hard-wired association between a key and a value
263   (compute-assoc (lambda (key) (cons key (++ key)))))
264
265  ;; loading a sequence [min-key .. max-key] in ascending order
266  (do ((i min-key (++ i))) ((> i max-key))
267    ((rb-tree 'put!) i (cdr (compute-assoc i))))
268
269  (print "the tree depth is " (rb-tree 'depth) "\n")
270
271  (print ((rb-tree 'get) (++ min-key)))
272
273  (print ((rb-tree 'get) (++ min-key) 'notfound))
274
275  ;; checking traversing in ascending order
276  (let ((expected-key min-key))
277    ((rb-tree 'for-each-ascending)
278      (lambda (association)
279        (print (equal? association (compute-assoc expected-key)))
280        (++! expected-key))))
281
282  ;; clearing the rb-tree and reloading the same sequence in
283  ;; descending order
284  (rb-tree 'clear!)
285  (do ((i max-key (-- i))) ((< i min-key))
286     ((rb-tree 'put!) i (cdr (compute-assoc i))))
287
288  (print "the tree depth is " (rb-tree 'depth) "\n")
289
290  ;; checking traversing in descending order
291  (let ((expected-key max-key))
292    ((rb-tree 'for-each-descending)
293      (lambda (association)
294        (print (equal? association (compute-assoc expected-key)))
295        (--! expected-key)))))
296EOF
297))
298     (license
299      "Copyright Ivan Raikov and the Okinawa Institute of Science and Technology.
300
301This program is free software: you can redistribute it and/or modify
302it under the terms of the GNU General Public License as published by
303the Free Software Foundation, either version 3 of the License, or (at
304your option) any later version.
305
306This program is distributed in the hope that it will be useful, but
307WITHOUT ANY WARRANTY; without even the implied warranty of
308MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
309General Public License for more details.
310
311A full copy of the GPL license can be found at
312<http://www.gnu.org/licenses/>."))))
313
314(if (eggdoc->html doc) (void))
Note: See TracBrowser for help on using the repository browser.