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

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

Anonymous wiki edit for IP [85.179.51.213]: Initial page.

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