source: project/wiki/eggref/5/rb-tree @ 36458

Last change on this file since 36458 was 36458, checked in by iraikov, 11 months ago

rb-tree version history and doc update

File size: 5.8 KB
Line 
1[[tags:egg]]
2[[toc:]]
3
4== rb-tree
5
6Sorted dictionary data structures based on red-black trees.
7
8
9== Documentation
10
11The {{rb-tree}} library is based on the SML/NJ library implementation
12of red-black trees, which is in turn based on Chris Okasaki's
13implementation of red-black trees.  The delete function is based on
14the description in Cormen, Leiserson, and Rivest.
15
16The present implementation code defines a persistent map [[yasos|yasos object]]
17that implements an ordered dictionary mapping of keys to values.
18
19Looking up an arbitrary or the min/max keys, and deleting the min/max
20keys require no more key comparisons than the depth of the tree, which
21is {{O(log n)}} where {{n}} is the total number of keys in the tree.
22
23=== Procedures
24
25The persistent map instance is created by procedure {{rb-tree-map}}:
26
27<procedure>rb-tree-map:: KEY-COMPARE-PROC -> persistent-map</procedure>
28
29where KEY-COMPARE-PROC is a user-supplied function that takes two keys
30and returns a negative, positive, or zero number depending on how the
31first key compares to the second.
32
33The {{persistent-map}} object contains the following operations:
34
35; {{empty? TREE}} : returns {{#t}} if the given tree is empty
36; {{get TREE}} : returns a procedure of the form {{(LAMBDA KEY . DEFAULT-CLAUSE}} which searches the given tree for an association with a given {{KEY}}, and returns a (key . value) pair of the found association. If an association with {{KEY}} cannot be located in the  tree, the procedure returns the result of evaluating the {{DEFAULT-CLAUSE}}. If the default clause is omitted, an error is signalled. {{KEY}} must be comparable to the keys in the  tree by a key-compare predicate (which has been specified when the  tree was created)
37; {{get-value TREE}} : returns a procedure of the form {{(LAMBDA KEY . DEFAULT-CLAUSE}} which searches the tree for an association with a given {{KEY}}, and returns the value of (key . value) pair of the found association. If an association with {{KEY}} cannot be located in the  tree, the procedure returns the result of evaluating the {{DEFAULT-CLAUSE}}. If the default clause is omitted, an error is signalled. {{KEY}} must be comparable to the keys in the  tree by a key-compare predicate (which has been specified when the  tree was created)
38; {{get-min TREE}} : returns a (key . value) pair for an association in the tree with the smallest key. If the  tree is empty, an error is signalled.
39; {{get-max TREE}} : returns a (key . value) pair for an association in the tree with the largest key. If the tree is empty, an error is signalled.
40; {{size TREE}} : returns the size (the number of associations) in the tree
41; {{put TREE KEY VALUE}} : returns a new  tree object that contains the given association
42; {{delete TREE KEY . DEFAULT-CLAUSE}} : if the specified key is found, it returns a new tree object that no longer contains the association specified by that key, while the original tree object is unmodified. If the key is not found, the procedure returns the result of evaluating {{DEFAULT-CLAUSE}}
43; {{for-each-ascending TREE}} : returns a procedure {{LAMBDA PROC}} that will apply the given procedure PROC to each (key . value) association of the tree, from the one with the smallest key all the way to the one with the max key, in an ascending order of keys.
44; {{for-each-descending TREE}} : returns a procedure {{LAMBDA PROC}} that will apply the given procedure {{PROC}}to each (key . value) association of the tree, in the descending order of keys.
45
46
47== Examples
48
49<enscript highlight="scheme">
50 (import rb-tree)
51 
52 (define (++ x) (fx+ 1 x))
53 (define (-- x) (fx- x 1))
54 
55 (let ((m (rb-tree-map (lambda (x y) (- x y)))))
56     
57      (let* ((compute-assoc (lambda (key) (cons key (++ key))))
58             (min-key -1) (max-key 10)
59             (t (let recur  ((m m) (i min-key))
60                (let ((t1 (put m i (cdr (compute-assoc i)))))
61                  (if (< i max-key) (recur t1 (++ i)) t1))))
62             )
63           
64       (print (get m (++ min-key)))
65 
66       (print (get m (-- min-key) 'notfound))
67 
68       ;; checking traversing in ascending order
69       (let ((expected-key min-key))
70        ((for-each-ascending m)
71         (lambda (association)
72           (print (equal? association (compute-assoc expected-key)))
73          (set! expected-key (++ expected-key)))))
74  )
75 )
76</enscript>
77
78== About this egg
79
80
81=== Author
82
83[[/users/ivan-raikov|Ivan Raikov]]
84
85=== Version history
86
87; 6.0 : Refactored to use yasos-based object interface and support for the operations defined by yasos-collections
88; 5.3 : Ported to CHICKEN 5
89; 5.0 : Using typeclass interface, discarded ephemeral map
90; 4.2 : Ensure test script returns proper exit status
91; 4.0 : Divided API in persistent and ephemeral maps
92; 3.1 : Added get-value operation
93; 3.0 : Ability to specify different predicates for lookup, insert, delete operations
94; 2.9 : Documentation converted to wiki format
95; 2.8 : Added matchable as dependency
96; 2.7 : Bug fix in dispatch-on-key
97; 2.6 : Ported to Chicken 4
98; 2.5 : Fixes to for-each-ascending/descending
99; 2.3 : Build script updated for better cross-platform compatibility
100; 2.2 : Added fold-limit procedures
101; 2.1 : Added fold-partial procedures
102; 2.0 : Added side-effect-free put and delete procedures
103; 1.0 : Initial release
104
105=== License
106
107
108 Copyright 2007-2018 Ivan Raikov.
109 
110 This program is free software: you can redistribute it and/or modify
111 it under the terms of the GNU General Public License as published by
112 the Free Software Foundation, either version 3 of the License, or (at
113 your option) any later version.
114 
115 This program is distributed in the hope that it will be useful, but
116 WITHOUT ANY WARRANTY; without even the implied warranty of
117 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
118 General Public License for more details.
119 
120 A full copy of the GPL license can be found at
121 <http://www.gnu.org/licenses/>.
122
Note: See TracBrowser for help on using the repository browser.