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
|
use core::vec;
// A generic tree datatype.
//
// TODO: Use traits.
pub type Tree<T> = {
mut parent: Option<T>,
mut first_child: Option<T>,
mut last_child: Option<T>,
mut prev_sibling: Option<T>,
mut next_sibling: Option<T>
};
pub trait ReadMethods<T> {
fn with_tree_fields<R>(&T, f: fn(&Tree<T>) -> R) -> R;
}
pub trait WriteMethods<T> {
fn with_tree_fields<R>(&T, f: fn(&Tree<T>) -> R) -> R;
}
pub fn each_child<T:Copy,O:ReadMethods<T>>(ops: &O, node: &T, f: fn(&T) -> bool) {
let mut p = ops.with_tree_fields(node, |f| f.first_child);
loop {
match copy p {
None => { return; }
Some(ref c) => {
if !f(c) { return; }
p = ops.with_tree_fields(c, |f| f.next_sibling);
}
}
}
}
pub fn empty<T>() -> Tree<T> {
{mut parent: None,
mut first_child: None,
mut last_child: None,
mut prev_sibling: None,
mut next_sibling: None}
}
pub fn add_child<T:Copy,O:WriteMethods<T>>(ops: &O, parent: T, child: T) {
ops.with_tree_fields(&child, |child_tf| {
match child_tf.parent {
Some(_) => { fail ~"Already has a parent"; }
None => { child_tf.parent = Some(parent); }
}
assert child_tf.prev_sibling.is_none();
assert child_tf.next_sibling.is_none();
ops.with_tree_fields(&parent, |parent_tf| {
match copy parent_tf.last_child {
None => {
parent_tf.first_child = Some(child);
}
Some(lc) => {
let lc = lc; // satisfy alias checker
ops.with_tree_fields(&lc, |lc_tf| {
assert lc_tf.next_sibling.is_none();
lc_tf.next_sibling = Some(child);
});
child_tf.prev_sibling = Some(lc);
}
}
parent_tf.last_child = Some(child);
});
});
}
pub fn get_parent<T:Copy,O:ReadMethods<T>>(ops: &O, node: &T) -> Option<T> {
ops.with_tree_fields(node, |tf| tf.parent)
}
#[cfg(test)]
mod test {
enum dummy = @{
fields: Tree<dummy>,
value: uint
};
enum dtree { dtree }
impl dtree : ReadMethods<dummy> {
fn with_tree_fields<R>(d: &dummy, f: fn(&Tree<dummy>) -> R) -> R {
f(&d.fields)
}
}
impl dtree : WriteMethods<dummy> {
fn with_tree_fields<R>(d: &dummy, f: fn(&Tree<dummy>) -> R) -> R {
f(&d.fields)
}
}
fn new_dummy(v: uint) -> dummy {
dummy(@{fields: empty(), value: v})
}
fn parent_with_3_children() -> {p: dummy, children: ~[dummy]} {
let children = ~[new_dummy(0u),
new_dummy(1u),
new_dummy(2u)];
let p = new_dummy(3u);
for vec::each(children) |c| {
add_child(&dtree, p, *c);
}
return {p: p, children: children};
}
#[test]
fn add_child_0() {
let {p, children} = parent_with_3_children();
let mut i = 0u;
for each_child(&dtree, &p) |c| {
assert c.value == i;
i += 1u;
}
assert i == children.len();
}
#[test]
fn add_child_break() {
let {p, _} = parent_with_3_children();
let mut i = 0u;
for each_child(&dtree, &p) |_c| {
i += 1u;
break;
}
assert i == 1u;
}
}
|
