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
|
/*
Module: treemap
A key,value store that works on anything.
This works using a binary search tree. In the first version, it's a
very naive algorithm, but it will probably be updated to be a
red-black tree or something else.
*/
import core::option;
import option::{some, none};
import option = option::t;
export treemap;
export init;
export insert;
export find;
export traverse;
/* Section: Types */
/*
Type: treemap
*/
type treemap<K, V> = @mutable tree_node<K, V>;
/*
Tag: tree_node
*/
tag tree_node<K, V> { empty; node(@K, @V, treemap<K, V>, treemap<K, V>); }
/* Section: Operations */
/*
Function: init
Create a treemap
*/
fn init<K, V>() -> treemap<K, V> { @mutable empty }
/*
Function: insert
Insert a value into the map
*/
fn insert<copy K, copy V>(m: treemap<K, V>, k: K, v: V) {
alt m {
@empty. { *m = node(@k, @v, @mutable empty, @mutable empty); }
@node(@kk, _, _, _) {
// We have to name left and right individually, because
// otherwise the alias checker complains.
if k < kk {
alt m { @node(_, _, left, _) { insert(left, k, v); } }
} else { alt m { @node(_, _, _, right) { insert(right, k, v); } } }
}
}
}
/*
Function: find
Find a value based on the key
*/
fn find<copy K, copy V>(m: treemap<K, V>, k: K) -> option<V> {
alt *m {
empty. { none }
node(@kk, @v, _, _) {
if k == kk {
some(v)
} else if k < kk {
// Again, ugliness to unpack left and right individually.
alt *m { node(_, _, left, _) { find(left, k) } }
} else { alt *m { node(_, _, _, right) { find(right, k) } } }
}
}
}
/*
Function: traverse
Visit all pairs in the map in order.
*/
fn traverse<K, V>(m: treemap<K, V>, f: block(K, V)) {
alt *m {
empty. { }
node(k, v, _, _) {
let k1 = k, v1 = v;
alt *m { node(_, _, left, _) { traverse(left, f); } }
f(*k1, *v1);
alt *m { node(_, _, _, right) { traverse(right, f); } }
}
}
}
|
