Changeset 36458 in project
 Timestamp:
 08/28/18 06:06:19 (3 weeks ago)
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

wiki/eggref/5/rbtree
r36325 r36458 14 14 the description in Cormen, Leiserson, and Rivest. 15 15 16 The present implementation code defines a persistent map [[ typeclass]]16 The present implementation code defines a persistent map [[yasosyasos object]] 17 17 that implements an ordered dictionary mapping of keys to values. 18 18 … … 25 25 The persistent map instance is created by procedure {{rbtreemap}}: 26 26 27 <procedure>rbtreemap:: KEYCOMPAREPROC [insdelkeycompare: KEYCOMPAREPROC] > <PersistentMap></procedure>27 <procedure>rbtreemap:: KEYCOMPAREPROC > persistentmap</procedure> 28 28 29 29 where KEYCOMPAREPROC is a usersupplied function that takes two keys … … 31 31 first key compares to the second. 32 32 33 Optional keyword argument {{insdelkeycompare}} can be used to 34 specify different key comparison predicates for the insertion and 35 deletion operations. 33 The {{persistentmap}} object contains the following operations: 36 34 37 The {{<PersistentMap>}} typeclass contains the following operations:38 39 ; {{empty}} : returns a new empty tree40 35 ; {{empty? TREE}} : returns {{#t}} if the given tree is empty 41 36 ; {{get TREE}} : returns a procedure of the form {{(LAMBDA KEY . DEFAULTCLAUSE}} 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 {{DEFAULTCLAUSE}}. If the default clause is omitted, an error is signalled. {{KEY}} must be comparable to the keys in the tree by a keycompare predicate (which has been specified when the tree was created) … … 48 43 ; {{foreachascending 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. 49 44 ; {{foreachdescending 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. 50 ; {{map TREE}} : returns a procedure {{LAMBDA PROC}} that will apply the given procedure {{PROC}}to the value component of each association in the tree, in the ascending order of keys, and will construct a copy of the tree that contains the values returned by that procedure.51 ; {{mapi TREE}} : returns a procedure {{LAMBDA PROC}} that will apply the given procedure {{PROC}}to each (key . value) association in the tree, in the ascending order of keys, and will construct a copy of the tree that contains the values returned by that procedure.52 ; {{fold TREE}} : returns a procedure {{LAMBDA PROC INITIAL}} such that, given the associations in the tree ordered by the descending order of keys: {{(keyn . valuen) ... (key2 . value2) (key1 . value1) }} the procedure returns the result of the successive function applications {{(PROC value1 (PROC value2 ... (PROC valuen INITIAL)}}.53 ; {{foldi TREE}} : returns a procedure {{LAMBDA PROC INITIAL}} such that, given the associations in the tree ordered by the descending order of keys: {{(keyn . valuen) ... (key2 . value2) (key1 . value1) }} the procedure returns the result of the successive function applications {{(PROC key1 value1 (PROC key2 value2 ... (PROC keyn valuen INITIAL)}}.54 ; {{foldright TREE}} : returns a procedure {{LAMBDA PROC INITIAL}} such that, given the associations in the tree ordered by the ascending order of keys: {{(key1 . value1) (key2 . value2) ... (keyn . valuen) }} the procedure returns the result of the successive function applications {{(PROC valuen ... (PROC value2 (PROC value1 INITIAL)}}.55 ; {{foldiright TREE}} : returns a procedure {{LAMBDA PROC INITIAL}} such that, given the associations in the tree ordered by the ascending order of keys: {{(key1 . value1) (key2 . value2) ... (keyn . valuen) }} the procedure returns the result of the successive function applications {{(PROC keyn valuen ... (PROC key2 value2 (PROC key1 value1 INITIAL)}}.56 ; {{foldpartial TREE}} : returns a procedure {{LAMBDA PRED PROC INITIAL}} such that, given the associations in the tree ordered by the descending order of keys: {{(keyn . valuen) ... (key2 . value2) (key1 . value1) }} the procedure returns the result of the successive function applications {{(PROC valuei ... (PROC valuen INITIAL)}}, where {{i <= n}} and {{(PRED x)}} holds true for all {{x = (valuen) ... (valuei)}}. In other words, this function acts like {{fold}} on the ordered subset of the values {{x}} in the tree such that {{(PRED x)}} is true.57 ; {{foldipartial TREE}} : returns a procedure {{LAMBDA PRED PROC INITIAL}} such that, given the associations in the tree ordered by the descending order of keys: {{(keyn . valuen) ... (key2 . value2) (key1 . value1) }} the procedure returns the result of the successive function applications {{(PROC keyi valuei ... (PROC keyn valuen INITIAL)}}, where {{i <= n}} and {{(PRED xk x)}} holds true for all {{x = (valuen) ... (valuei)}} and {{xk = (keyn) ... (keyi)}}. In other words, this function acts like {{foldi}} on the ordered subset of the keyvalue pairs {{(k . x)}} in the tree such that {{(PRED k x)}} is true.58 ; {{foldrightpartial TREE}} : returns a procedure {{LAMBDA PRED PROC INITIAL}} such that, given the associations in the tree ordered by the ascending order of keys: {{(key1 . value1) (key2 . value2) ... (keyn . valuen) }} the procedure returns the result of the successive function applications {{(PROC value1 ... (PROC valuei INITIAL)}}, where {{i <= n}} and {{(PRED x)}} holds true for all {{x = (value1) ... (valuei)}}. In other words, this function acts like {{foldright}} on the ordered subset of the values {{x}} in the tree such that {{(PRED x)}} is true.59 ; {{foldirightpartial TREE}} : returns a procedure {{LAMBDA PRED PROC INITIAL}} such that, given the associations in the tree ordered by the descending order of keys: {{(key1 . value1) (key2 . value2) ... (key1 . value1) }} the procedure returns the result of the successive function applications {{(PROC key1 value1 ... (PROC keyi valuei INITIAL)}}, where {{i <= n}} and {{(PRED xk x)}} holds true for all {{x = (value1) ... (valuei)}} and {{xk = (key1) ... (keyi)}}. In other words, this function acts like {{foldiright}} on the ordered subset of the keyvalue pairs {{(k . x)}} in the tree such that {{(PRED k x)}} is true.60 ; {{foldlimit TREE}} : returns a procedure {{LAMBDA PRED PROC INITIAL}} such that, given the associations in the tree ordered by the descending order of keys: {{(keyn . valuen) ... (key2 . value2) (key1 . value1) }} the procedure returns the result of the successive function applications {{(PROC valuei ... (PROC valuen INITIAL)}}, where {{i <= n}} and {{(PRED x)}} does not hold true for all {{x = (PROC valuen INITIAL) ... (PROC (valuei) (PROC value(i1)...}}.61 ; {{foldrightlimit TREE}} : returns a procedure {{LAMBDA PRED PROC INITIAL}} such that, given the associations in the tree ordered by the descending order of keys: {{(key1 . value1) (key2 . value2) ... (keyi . value1) }} the procedure returns the result of the successive function applications {{(PROC valuei ... (PROC value1 INITIAL)}}, where {{i <= n}} and {{(PRED x)}} does not hold true for all {{x = (PROC value1 INITIAL) ... (PROC (valuei) (PROC value(i1)...}}.62 45 63 46 64 47 == Examples 65 48 66 (import typeclass rbtree) 49 <enscript highlight="scheme"> 50 (import rbtree) 67 51 68 (define (++ x) ( + 1 x))69 (define ( x) (  x 1))52 (define (++ x) (fx+ 1 x)) 53 (define ( x) (fx x 1)) 70 54 71 55 (let ((m (rbtreemap (lambda (x y) ( x y))))) 72 (withinstance ((<PersistentMap> m))73 56 74 57 (let* ((computeassoc (lambda (key) (cons key (++ key)))) 75 58 (minkey 1) (maxkey 10) 76 (t 77 (let recur ((t (empty)) (i minkey)) 78 (let ((t1 (put t i (cdr (computeassoc i))))) 59 (t (let recur ((m m) (i minkey)) 60 (let ((t1 (put m i (cdr (computeassoc i))))) 79 61 (if (< i maxkey) (recur t1 (++ i)) t1)))) 80 62 ) 81 63 82 (print ( (get t)(++ minkey)))64 (print (get m (++ minkey))) 83 65 84 (print ( (get t)( minkey) 'notfound))66 (print (get m ( minkey) 'notfound)) 85 67 86 68 ;; checking traversing in ascending order 87 69 (let ((expectedkey minkey)) 88 ((foreachascending t)70 ((foreachascending m) 89 71 (lambda (association) 90 72 (print (equal? association (computeassoc expectedkey))) 91 73 (set! expectedkey (++ expectedkey))))) 92 74 ) 93 )) 75 ) 76 </enscript> 94 77 95 78 == About this egg … … 102 85 === Version history 103 86 87 ; 6.0 : Refactored to use yasosbased object interface and support for the operations defined by yasoscollections 104 88 ; 5.3 : Ported to CHICKEN 5 105 89 ; 5.0 : Using typeclass interface, discarded ephemeral map
Note: See TracChangeset
for help on using the changeset viewer.