blob: 8baf5e7dfda71667ca5ec989e786fcf872cb5cb9 (
plain) (
blame)
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
|
(((name . "wb-tree-node?")
(signature lambda (x) => boolean?)
(desc "Returns true if `x` is a node in a weight-balanced tree."))
((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)) => wb-tree-node?)
(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 (wb-tree-node? left) (wb-tree-node? right))
=> non-null-wb-tree-node?)
(desc "
* It is an error if `left` or `right` are not balanced.
* 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 ((wb-tree-node? left) (wb-tree-node? right))
=> wb-tree-node?)
(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) (wb-tree-node? tree) key (procedure? default))
=> (values wb-tree-node? * wb-tree-node?))
"
* 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.
* It is an error if `default` is not a thunk.
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 ((((wb-tree-node? tree) (comparator? cmp) key) *)
(((wb-tree-node? tree) (comparator? cmp) key (procedure? default)) *)))
(desc "
* It is an error if `cmp` does not order `key` and all elements in `tree`.
* It is an error if `default` is not a thunk.
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`.")))
|
