1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
|
(((name . "wb-tree-node?")
(signature lambda (x) => boolean?)
(desc "Returns true if `x` is a node in a weight-balanced tree.
This porcedure does not check that the node itself is balanced: see `balanced?`."))
((name . "non-null-wb-tree-node?")
(signature lambda (x) => boolean?)
(desc "Returns true if `x` is a node with data and children."))
((name . "get-data")
(signature lambda ((non-null-wb-tree-node? x)) => *)
(desc "Returns the data in the tree node."))
((name . "get-left")
(signature lambda ((non-null-wb-tree-node? x)) => wb-tree-node?)
(desc "Returns the left child in the node."))
((name . "get-right")
(signature lambda ((non-null-wb-tree-node? x)) => wb-tree-node?)
(desc "Returns the right child in the node."))
((name . "get-size")
(signature lambda ((wb-tree-node? x)) => integer?)
(desc "Returns the number of elements in this tree."))
((name . "balanced?")
(signature lambda ((wb-tree-node? x)) => boolean?)
(desc "Recursively traverses `x` and checks if it is weight balanced."))
((name . "in-order-vector->node")
(signature lambda ((vector? x)) => balanced?)
(desc "
* It is an error if `x` is not in order.
Returns a weight-balanced tree where the elements of the tree are the
elements of `x`."))
((name . "node->in-order-list")
(signature lambda ((wb-tree-node? x)) => list?)
(desc "Returns a list of all elements of `x` in order."))
((name . "join")
(signature lambda (data (balanced? left) (balanced? right)) balanced?)
(desc "
* It is an error if any element of `left` is greater than or equal to
any element in `right`.
* It is an error if `data` is less than or equal to any element in
`left`.
* It is an error if `data` is greater than or equal to any element in
`right`.
Returns a balanced tree containing all elements of `left` and `right`
with `data`."))
((name . "join2")
(signature lambda ((balanced? left) (balanced? right)) balanced?)
(desc "
* It is an error if any element in `left` is greater than or equal to any
element in `right`.
Returns a new tree with the elements of `left` and `right`."))
((name . "split")
(signature lambda ((comparator? cmp) (balanced? tree) key (procedure? default))
=> (values balanced? * balanced?))
(subsigs (default lambda (() *)))
"
* It is an error if any element of `tree` is not comparable by `cmp`.
* It is an error if `key` is not comparable by `cmp`.
* It is an error if `cmp` does not have an order.
Returns two trees, one of all values to the left of `key`, and one with
all values to the right of `key`.
If a value that compares equal to `key` is found, that value is returned.
Otherwise the result of calling `default` with no arguments is returned.")
((name . "search")
(signature case-lambda ((((comparator? cmp) key (balanced? tree)) *)
(((comparator? cmp) key (balanced? tree) (procedure? default)) *)))
(subsigs (default (lambda () *)))
(desc "
* It is an error if `cmp` does not order `key` and all elements in `tree`.
Searches `tree` for `key` using `cmp`. If a node contains data that compares equal
to `key`, return that data. Otherwise, tail call `default.` If `default` is not
supplied, the function returns `#f`."))
((name . "union")
(signature lambda ((comparator? cmp) (balanced? left) (balanced? right)) balanced?)
(desc "
* It is an error if `cmp` does not order the elements in `left` and `right`.
Return a weight-balanced tree with the elements of `left` and `right`. If
there is an element in `left` that compares equal to an element in `right`,
then the element in `left` is kept and the element in `right` is discarded.
"))
((name . "intersection")
(signature lambda ((comparator? cmp) (balanced? left) (balanced? right)) balanced?)
(desc "
* It is an error if `cmp` does not order the elements in `left` and `right`.
Return a weight-balanced tree with only the elements of `left` that compare
equal to an element of `right`.
"))
((name . "difference")
(signature lambda ((comparator? cmp) (balanced? left) (balanced? right)) balanced?)
(desc "
* It is an error if `cmp` does not order the elements in `left` and `right`.
Return a weight-balanced tree with only the elements of `left` that do not
compare equal to an element of `right`.
"))
((name . "xor")
(signature
lambda ((comparator? cmp) (balanced? left) (balanced? right) balanced?))
(desc "
* It is an error if `cmp` does not order the elements of `left` and `right`.
Return a weight-balanced tree with the exclusive or of the elements of `left`
with the elements of `right`: that is, all elements of `left` and `right` that
are not both elements of `left` and `right`."))
((name . "update")
(signature
lambda ((comparator? cmp) (balanced? set) to-search (procedure? on-found) (procedure? on-not-found)) balanced?)
(subsigs
(on-not-found lambda () balanced?)
(on-found lambda (*) *))
(desc "
* It is an error if `cmp` does not order the elements of `set`, the
elements of the tree returned from `on-found`, and the element
returned from `on-not-found`.
Search `set` for an element that compares equal to `to-search`. If an
element `E` is found that compares equal to `to-search`, then
`(on-found E)` is evaluated and the resulting value is placed into the
tree. If no element is found, then `(on-not-found)` is evaluated and the
resulting node is inserted into the tree.
"))
((name . "delete")
(signature
lambda ((comparator? cmp) (balanced? set) element) balanced?)
(desc "
* It is an error if `cmp` does not order the elements of `set` and the
value `element`.
Search `set` for an element `E` that compares equal to `element`. If `E`
is found, the returned tree does not have `E`. Otherwise the returned
tree has the same number of elements."))
((name . "insert")
(signature
lambda ((comparator? cmp) (balanced? set) element) balanced?)
(desc "
* It is an error if `cmp` does not order the elements of `set` and the
value `element`.
Search `set` for an element `E` that compares equal to `element`. If `E`
is found, the return tree element will have `E` replaced with `element`.
Otherwise, the returned tree will have `element` in addition to the rest
of the values in the tree."))
((name . "every")
(signature
lambda ((procedure? predicate?) (wb-tree-node? tree)) *)
(subsigs
(predicate? lambda (*) *))
(desc "
Calls `predicate?` on each element of `tree` in an arbitrary order. If all
calls return a truthy value, return a truthy value. Otherwise return `#f`."))
((name . "node->generator")
(signature
lambda ((generator? node)) procedure?)
(subsigs
(return lambda () *))
(desc "
Returns a generator (see SRFI-158) that generates the elements of `node`
in arbitrary order."))
((name . "generator->node")
(signature
lambda ((comparator? cmp) (generator? generator)) balanced?)
(desc "
* It is an error if `generator` is not finite.
* It is an error if the values generated by `generator` are not comparable
by `cmp`.
Returns a weight balanced tree whose elements are all of the elements
of `generator`."))
((name . "node->in-order-generator")
(signature
lambda ((balanced? node)) generator?)
(desc "
Returns a generator (see SRFI-158) that generates the elements of `node`
in increasing order."))
((name . "node->reverse-order-generator")
(signature
lambda ((balanced? node)) generator?)
(desc "
Returns a generator (see SRFI-158) that generates the elements of `node`
in decreasing order.")))
|
