source: project/wiki/eggref/5/llrb-syntax @ 36405

Last change on this file since 36405 was 36405, checked in by svnwiki, 20 months ago

Anonymous wiki edit for IP [217.182.74.145]: Moved to chicken 5

File size: 1.6 KB
Line 
1[[tags: egg]]
2== llrb-syntax
3
4A syntax-rules macro expanding into left-leaning red-black tree code.
5Pure and mutating versions.
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[wikipedia].
12
13The macro is independent of data structures used to implement nodes of
14the trees.  Users must pass accessors and a syntax or procedure to
15update an existing node (for the mutating version) respectively create a fresh node
16as well as names for the procedures to be defined.
17
18== Examples
19
20See the llrb-tree egg.
21
22== API
23
24<syntax>
25    define-llrbtree/positional
26    (FEATURES)
27    UPDATE
28    init-root-node!             ;; defined
29    t-lookup            ;; defined
30    t-min                       ;; defined
31    t-fold                      ;; defined
32    t-for-each          ;; defined
33    t-insert            ;; defined
34    t-delete            ;; defined
35    t-delete-min                ;; defined
36    t-empty?            ;; defined
37
38    ;; These syntax is used expand to code for comparision
39    ;; expressions.
40    t-k-eq?                     ;; key<>node-key "equal"
41    t-eq?                       ;; node-key<>node-key "equal"
42    t-k-<?                      ;; key<>node-key "less then"
43    t-<?                        ;; node<>node "less then"
44    ;; Accessors to the elements of the tree.
45    left
46    right
47    color
48</syntax>
49
50FEATURES: {ordered, pure, leftmost} – configures the generated code.
51
52UPDATE
53
54The "update*" syntax must accept a node structure and
55key-value pairs.  Keys are color:, left: and right:
56
57"update" : If feature "pure" is set, "update" must expand
58to a newly allocated node, otherwise is MUST expand to a
59side effect full update of the original node.
Note: See TracBrowser for help on using the repository browser.