Changeset 36458 in project


Ignore:
Timestamp:
08/28/18 06:06:19 (3 weeks ago)
Author:
iraikov
Message:

rb-tree version history and doc update

File:
1 edited

Legend:

Unmodified
Added
Removed
  • wiki/eggref/5/rb-tree

    r36325 r36458  
    1414the description in Cormen, Leiserson, and Rivest.
    1515
    16 The present implementation code defines a persistent map [[typeclass]]
     16The present implementation code defines a persistent map [[yasos|yasos object]]
    1717that implements an ordered dictionary mapping of keys to values.
    1818
     
    2525The persistent map instance is created by procedure {{rb-tree-map}}:
    2626
    27 <procedure>rb-tree-map:: KEY-COMPARE-PROC [insdel-key-compare: KEY-COMPARE-PROC]  -> <PersistentMap></procedure>
     27<procedure>rb-tree-map:: KEY-COMPARE-PROC  -> persistent-map</procedure>
    2828
    2929where KEY-COMPARE-PROC is a user-supplied function that takes two keys
     
    3131first key compares to the second.
    3232
    33 Optional keyword argument {{insdel-key-compare}} can be used to
    34 specify different key comparison predicates for the insertion and
    35 deletion operations.
     33The {{persistent-map}} object contains the following operations:
    3634
    37 The {{<PersistentMap>}} typeclass contains the following operations:
    38 
    39 ; {{empty}} : returns a new empty tree
    4035; {{empty? TREE}} : returns {{#t}} if the given tree is empty
    4136; {{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)
     
    4843; {{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.
    4944; {{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.
    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: {{(key-n . value-n) ... (key-2 . value-2) (key-1 . value-1) }} the procedure returns the result of the successive function applications {{(PROC value-1 (PROC value-2 ... (PROC value-n 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: {{(key-n . value-n) ... (key-2 . value-2) (key-1 . value-1) }} the procedure returns the result of the successive function applications {{(PROC key-1 value-1 (PROC key-2 value-2 ... (PROC key-n value-n INITIAL)}}.
    54 ; {{fold-right TREE}} : returns a procedure {{LAMBDA PROC INITIAL}} such that, given the associations in the tree ordered by the ascending order of keys: {{(key-1 . value-1) (key-2 . value-2) ... (key-n . value-n) }} the procedure returns the result of the successive function applications {{(PROC value-n ... (PROC value-2 (PROC value-1 INITIAL)}}.
    55 ; {{foldi-right TREE}} : returns a procedure {{LAMBDA PROC INITIAL}} such that, given the associations in the tree ordered by the ascending order of keys: {{(key-1 . value-1) (key-2 . value-2) ... (key-n . value-n) }} the procedure returns the result of the successive function applications {{(PROC key-n value-n ... (PROC key-2 value-2 (PROC key-1 value-1 INITIAL)}}.
    56 ; {{fold-partial TREE}} : returns a procedure {{LAMBDA PRED PROC INITIAL}} such that, given the associations in the tree ordered by the descending order of keys: {{(key-n . value-n) ... (key-2 . value-2) (key-1 . value-1) }} the procedure returns the result of the successive function applications {{(PROC value-i ... (PROC value-n INITIAL)}}, where {{i <= n}} and {{(PRED x)}} holds true for all {{x = (value-n) ... (value-i)}}. 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 ; {{foldi-partial TREE}} : returns a procedure {{LAMBDA PRED PROC INITIAL}} such that, given the associations in the tree ordered by the descending order of keys: {{(key-n . value-n) ... (key-2 . value-2) (key-1 . value-1) }} the procedure returns the result of the successive function applications {{(PROC key-i value-i ... (PROC key-n value-n INITIAL)}}, where {{i <= n}} and {{(PRED xk x)}} holds true for all {{x = (value-n) ... (value-i)}} and {{xk = (key-n) ... (key-i)}}. In other words, this function acts like {{foldi}} on the ordered subset of the key-value pairs {{(k . x)}} in the tree such that {{(PRED k x)}} is true.
    58 ; {{fold-right-partial TREE}} : returns a procedure {{LAMBDA PRED PROC INITIAL}} such that, given the associations in the tree ordered by the ascending order of keys: {{(key-1 . value-1) (key-2 . value-2) ... (key-n . value-n) }} the procedure returns the result of the successive function applications {{(PROC value-1 ... (PROC value-i INITIAL)}}, where {{i <= n}} and {{(PRED x)}} holds true for all {{x = (value-1) ... (value-i)}}. In other words, this function acts like {{fold-right}} on the ordered subset of the values {{x}} in the tree such that {{(PRED x)}} is true.
    59 ; {{foldi-right-partial TREE}} : returns a procedure {{LAMBDA PRED PROC INITIAL}} such that, given the associations in the tree ordered by the descending order of keys: {{(key-1 . value-1) (key-2 . value-2) ... (key-1 . value-1) }} the procedure returns the result of the successive function applications {{(PROC key-1 value-1 ... (PROC key-i value-i INITIAL)}}, where {{i <= n}} and {{(PRED xk x)}} holds true for all {{x = (value-1) ... (value-i)}} and {{xk = (key-1) ... (key-i)}}. In other words, this function acts like {{foldi-right}} on the ordered subset of the key-value pairs {{(k . x)}} in the tree such that {{(PRED k x)}} is true.
    60 ; {{fold-limit TREE}} : returns a procedure {{LAMBDA PRED PROC INITIAL}} such that, given the associations in the tree ordered by the descending order of keys: {{(key-n . value-n) ... (key-2 . value-2) (key-1 . value-1) }} the procedure returns the result of the successive function applications {{(PROC value-i ... (PROC value-n INITIAL)}}, where {{i <= n}} and {{(PRED x)}} does not hold true for all {{x = (PROC value-n INITIAL)  ... (PROC (value-i) (PROC value-(i-1)...}}.
    61 ; {{fold-right-limit TREE}} : returns a procedure {{LAMBDA PRED PROC INITIAL}} such that, given the associations in the tree ordered by the descending order of keys: {{(key-1 . value-1) (key-2 . value-2) ... (key-i . value-1) }} the procedure returns the result of the successive function applications {{(PROC value-i ... (PROC value-1 INITIAL)}}, where {{i <= n}} and {{(PRED x)}} does not hold true for all {{x = (PROC value-1 INITIAL)  ... (PROC (value-i) (PROC value-(i-1)...}}.
    6245
    6346
    6447== Examples
    6548
    66  (import typeclass rb-tree)
     49<enscript highlight="scheme">
     50 (import rb-tree)
    6751 
    68  (define (++ x) (+ 1 x))
    69  (define (-- x) (- x 1))
     52 (define (++ x) (fx+ 1 x))
     53 (define (-- x) (fx- x 1))
    7054 
    7155 (let ((m (rb-tree-map (lambda (x y) (- x y)))))
    72     (with-instance ((<PersistentMap> m))
    7356     
    7457      (let* ((compute-assoc (lambda (key) (cons key (++ key))))
    7558             (min-key -1) (max-key 10)
    76              (t
    77               (let recur  ((t (empty)) (i min-key))
    78                 (let ((t1 (put t i (cdr (compute-assoc i)))))
     59             (t (let recur  ((m m) (i min-key))
     60                (let ((t1 (put m i (cdr (compute-assoc i)))))
    7961                  (if (< i max-key) (recur t1 (++ i)) t1))))
    8062             )
    8163           
    82        (print ((get t) (++ min-key)))
     64       (print (get m (++ min-key)))
    8365 
    84        (print ((get t) (-- min-key) 'notfound))
     66       (print (get m (-- min-key) 'notfound))
    8567 
    8668       ;; checking traversing in ascending order
    8769       (let ((expected-key min-key))
    88         ((for-each-ascending t)
     70        ((for-each-ascending m)
    8971         (lambda (association)
    9072           (print (equal? association (compute-assoc expected-key)))
    9173          (set! expected-key (++ expected-key)))))
    9274  )
    93  ))
     75 )
     76</enscript>
    9477
    9578== About this egg
     
    10285=== Version history
    10386
     87; 6.0 : Refactored to use yasos-based object interface and support for the operations defined by yasos-collections
    10488; 5.3 : Ported to CHICKEN 5
    10589; 5.0 : Using typeclass interface, discarded ephemeral map
Note: See TracChangeset for help on using the changeset viewer.