source: project/wiki/eggref/4/llrb-tree @ 37623

Last change on this file since 37623 was 37623, checked in by wasamasa, 5 months ago

Fix link

File size: 9.5 KB
Line 
1[[tag: eggs]]
2== llrb-tree
3
4Left–leaning red–black trees.  A general version and some customized
5to the key types "fixnum", "string" and "symbol" are provided.
6
7== Overview
8
9A left-leaning red–black (LLRB) tree is a type of self-balancing binary search tree.
10It is a variant of the red–black tree and guarantees the same asymptotic complexity for operations.
11
12This egg implements an API to LLRB-trees (mostly) compatible to srfi-69 Hashtables
13plus some procedures resembling the API of assoc-Lists.
14
15Note that this egg is mainly intended to used to replace assoc-Lists.
16
17Future versions will provide a (subset of) [[https://srfi.schemers.org/srfi-146/srfi-146.html|srfi-146]].
18
19== API
20
21<procedure>(make-llrb-treetype COMPARATOR)</procedure>
22
23Define a treetype of keys matching COMPARATOR (from SRFI-128).
24
25<procedure>(make-llrb-treetype KEY? EQUAL LESS)</procedure>
26
27Define a treetype of keys matching the KEY? predicate using EQUAL as
28equivalence predicate and LESS as ordering predicate.
29
30<procedure>(llrb-treetype? X)</procedure>
31
32Test X to be an llrb-treetype.
33
34The procedures "*{{binding-set}}*" have ananologous definitions
35specialized to the key type.  Those specialized procedure names are
36prefixed by the key type (i.e. {{fixnum-}}, {{string-}} and
37{{symbol-}}).
38
39Procedures prefixed with {{symbol-}}, {{fixnum-}}, {{string-}} are
40defined for most of the following.  Those are specialized to the
41respective key type.
42
43<procedure>(string-empty-binding-set)</procedure>
44<procedure>(fixnum-empty-binding-set)</procedure>
45<procedure>(symbol-empty-binding-set)</procedure>
46<procedure>(empty-binding-set type)</procedure>
47
48Return an empty binding set.
49
50<procedure>(make-binding-set TYPE . pairs)</procedure>
51
52Undocumented (API pending review, i.e. SHOULD become {{mapping}} as in [[https://srfi.schemers.org/srfi-146/srfi-146.html#Constructors|srfi-146]]).
53
54Create an empty set of bindings of TYPE populate it with bindings from
55`pairs`.
56
57
58<procedure>(binding-set-empty? set)</procedure>
59
60Test whether or not the set has no associations.
61
62<procedure>(binding-set-ref/default set key default)</procedure>
63
64Returns the value bound to {{key}} in {{set}} or {{default}} value if
65not found.
66
67<procedure>(binding-set-ref set key [failure] [success])</procedure>
68
69Extracts the value associated to key in "binding-set", invokes the
70procedure {{success}} on it, and returns its result; if {{success}} is
71not provided, then the value itself is returned. If key is not
72contained in {{set}} and {{failure}} is supplied, then {{failure}} is
73invoked on no arguments and its result is returned. Otherwise, it is
74an error.
75
76<procedure>(binding-set-insert set key value)</procedure>
77
78Extend {{set}} with a binding {{key}}-{{value}}, return the extended
79set.
80
81<procedure>(binding-set-delete key set)</procedure>
82
83Deletes association from {{set}} with given {{key}}, return the new set.
84
85<procedure>(binding-set-update set key update default)</procedure>
86
87Return a set with the binding of {{key}} replaced. {{update}} and
88{{default}} are procedures with the same semantics and in hash-table-update!.
89
90<procedure>(binding-set-cons key value set)</procedure>
91
92Same as {{binding-set-insert}} with API as alist-cons (srfi-1).
93
94<procedure>(binding-set-fold proc nil set)</procedure>
95
96{{Proc}} must be a procedure of three arguments.  It is invoked for
97each element with the key, value and the accumulated value (nil for
98the first element).
99
100<procedure>(binding-set-union inner outer)</procedure>
101
102Return a merged set.  All bindings in {{inner}} shadow those in
103{{outer}}.
104
105
106
107<procedure>(make-table type)</procedure>
108
109Create a table with an empty set of bindings according to {{type}}.
110
111<procedure>(string-make-table)</procedure>
112<procedure>(fixnum-make-table)</procedure>
113<procedure>(symbol-make-table)</procedure>
114
115Create a table with an empty set of bindings.  Specialized to the key
116type.
117
118<procedure>(table? x)</procedure>
119
120Test whether or not the object is a LLRB-table.
121
122<procedure>(table-empty? table)</procedure>
123
124Test {{table}} to have no bidings.
125
126<procedure>(table-copy table)</procedure>
127
128Create a copy of {{table}} initially sharing all bindings.
129
130<procedure>(table-delete! table key)</procedure>
131
132Delete the binding for {{key}} from the bindings in the table.
133
134<procedure>(table-set! table key value)</procedure>
135
136Set the {{value}} for {{key}} in {{table}}.
137
138<procedure>(table-ref/default table key default)</procedure>
139
140Returns the value associated to key in {{table}}, or the {{default}}
141when the {{key}} is missing.
142
143<procedure>(table-ref table key [failure] [success])</procedure>
144
145Extracts the value associated to key in {{table}}, invokes the
146procedure {{success}} on it, and returns its result; if {{success}} is
147not provided, then the value itself is returned. If key is not
148contained in {{set}} and {{failure}} is supplied, then {{failure}} is
149invoked on no arguments and its result is returned. Otherwise, it is
150an error.
151
152<procedure>(table-update! table key update . default)</procedure>
153
154Note: procedures {{update}} and {{default}} should have no side
155effects.  They may be called multiple times.  (This can happen if
156those procedures allow other continuations/threads to update the table
157before they return.  As a consequence those procedures must especially
158not update the table, since this will result in an endless loop.)
159
160<procedure>(table-fold table proc nil)</procedure>
161<procedure>(table-for-each table proc)</procedure>
162
163Intentionally minimum related operations are NOT available for
164{{symbol}}, since those are supposedly unordered.
165
166<procedure>(table-min table thunk)</procedure>
167
168Return two values the minimal key and associated value in table.
169If the table is empty {{thunk}} is invoked instead.
170
171((FIXME: will be in constant time with little change to the
172source, at the moment O(log n).))
173
174<procedure>(table-delete-min! table)</procedure>
175
176Delete the entry with the smalles key and return two values, the key
177and associated value in table.  In case table is empty returns two
178false values.
179
180=== Auxillaries
181
182Note: These procedures are obsolete for chicken version >= 4.10.1 at
183least (they provide no more performance benefit) and will be removed
184in future versions of this egg.
185
186<procedure>(wrap-one-string-arg PROC)</procedure>
187
188Returns a procedure caching PROC.  PROC must accept exactly one
189argument, a string.
190
191<procedure>(str2sym string)</procedure>
192
193Calls {{string->symbol}} and caches the result.  (Surprisingly this is
194faster on lookup than {{string->symbol}} itself, at least for large
195numbers.)
196
197== Examples
198
199    #;1> (use llrb-tree)
200    #;2> (define y (fixnum-make-table))
201    #;3> (fixnum-table-update! y 23 add1 (lambda () 41))
202    42
203    #;4> (define numttype (make-llrb-treetype number? = <))
204    #;5> (define nt (make-table numttype))
205    #;6> (table-update! nt 42.23 add1 (lambda () 22))
206    23
207    #;7> (define clsttype (make-llrb-treetype
208          number?
209          (lambda (a b) (let ((delta (- a b))) (and (< delta 1) (> delta 0))))
210          <))
211    #;8> (define ct (make-table clsttype))
212    #;9> (table-set! ct 1 '(one))
213    #;10> (table-set! ct 2 '(two))
214    #;11> (table-set! ct 3 '(three))
215    #;12> (define (classify n) (table-update! ct n (lambda (v) `(,(car v) ,n . ,(cdr v)))))
216    #;13> (classify 1.1)
217    (one 1.1)
218    #;14>  (classify 1.2)
219    (one 1.2 1.1)
220    #;15> (classify 2.1)
221    (two 2.1)
222    #;16> (classify 2.4)
223    (two 2.4 2.1)
224    #;17> (classify 3.5)
225    (three 3.5)
226    #;18> (table-fold ct (lambda (k v i) `((,k . ,v) . ,i)) '())
227    ((1 one 1.2 1.1) (2 two 2.4 2.1) (3 three 3.5))
228    #;19> (define (string-binding-set-find set proc) ;; This is not the most efficient implementation.
229      (call-with-current-continuation
230       (lambda (return)
231         (or
232          (string-binding-set-fold
233           (lambda (k v i)
234             (let ((hit (proc k v)))
235               (if hit (return hit) i)))
236           #f
237           set)
238          (error "no match")))))
239    #;20> (string-binding-set-find (string-binding-set-cons "a" 'A (string-empty-binding-set)) (lambda (k v) (equal? k "a")))
240    #t
241
242== About this egg
243
244=== Author
245
246Jörg F. Wittenberger
247
248=== Version History
249
2500.3.1.2 -- Minor fix: install llrb-tree.import.so instead of .scm file.
251
2520.3.1 -- Enable srfi-128 comparators, add tests, documentation update.
253
2540.3 -- Fixed dependency.
255
2560.2 -- Changed API to match srfi-125
257
2580.1 -- initial release
259
260=== License
261
262Redistribution and use in source and binary forms, with or without
263modification, are permitted provided that the following conditions are
264met:
265
266Redistributions of source code must retain the above copyright
267notice, this list of conditions and the following disclaimer.
268
269Redistributions in binary form must reproduce the above copyright
270notice, this list of conditions and the following disclaimer in the
271documentation and/or other materials provided with the distribution.
272
273Neither the name of the author nor the names of its contributors may
274be used to endorse or promote products derived from this software
275without specific prior written permission.
276
277THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
278"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
279LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
280FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
281COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
282INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
283(INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
284SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
285HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
286STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
287ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
288OF THE POSSIBILITY OF SUCH DAMAGE.
Note: See TracBrowser for help on using the repository browser.