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

Last change on this file since 33040 was 33040, checked in by svnwiki, 6 years ago

Anonymous wiki edit for IP [85.179.86.184]: Update to version 0.3.1

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