compiler/
lib/
examples/
std/
arch/
rv64/
tests/
abi.sizes.rad
3.4 KiB
aggregate.return.rad
4.0 KiB
arith.assignment.rad
580 B
arith.basic.rad
176 B
arith.modulo.rad
96 B
arith.subword.rad
3.8 KiB
arith.sum.rad
177 B
arith.w64.rad
4.1 KiB
array.assign.rad
221 B
array.bounds.check.rad
321 B
array.index.assign.rad
367 B
array.index.rad
249 B
array.length.rad
262 B
array.math.rad
1.2 KiB
array.nested.assign.rad
319 B
array.nested.rad
325 B
array.record.elements.rad
1.7 KiB
array.repeat.edge.rad
548 B
array.repeat.rad
828 B
array.return.rad
330 B
array.slice.empty.rad
108 B
array.slice.gen.end.rad
126 B
array.slice.gen.index.rad
139 B
array.slice.gen.open.rad
125 B
array.slice.gen.start.end.rad
127 B
array.slice.gen.start.rad
126 B
array.slice.rad
759 B
as.precedence.rad
212 B
assert.basic.rad
387 B
assert.fail.rad
138 B
assert.false.rad
140 B
assert.true.rad
100 B
assign.mutable.rad
6.1 KiB
assign.rad
129 B
assign.shadow.mutable.rad
461 B
binop.bitwise.rad
1.2 KiB
binop.cmp.rad
426 B
bool.comparison.array.rad
688 B
bool.comparison.nested.gen.rad
1.0 KiB
bool.comparison.opt.rad
905 B
bool.comparison.record.gen.rad
1.0 KiB
bool.comparison.record.rad
1.1 KiB
bool.comparison.slice.gen.rad
157 B
bool.comparison.slice.rad
4.1 KiB
bool.comparison.slice.record.gen.rad
2.0 KiB
bool.comparison.slice.union.gen.rad
2.5 KiB
bool.comparison.union.ctor.rad
690 B
bool.comparison.union.gen.rad
1.2 KiB
bool.comparison.union.record.gen.rad
1.5 KiB
bool.comparison.union.simple.gen.rad
281 B
bool.operators.complex.rad
384 B
bool.operators.rad
831 B
bool.short.circuit.rad
2.3 KiB
bool.simple.rad
194 B
bool.values.rad
772 B
builtin.size.align.rad
1.3 KiB
builtin.sliceof.mut.rad
606 B
builtin.sliceof.rad
505 B
call.arg.clobber.rad
717 B
call.basic.rad
241 B
call.clobber.rad
462 B
cast.same.size.rad
1.0 KiB
casting.numbers.rad
1.5 KiB
char.literal.rad
165 B
compound.assign.field.rad
285 B
compound.assign.rad
1.1 KiB
cond.assign.rad
723 B
cond.expr.aggregate.rad
1.1 KiB
cond.expr.rad
1.8 KiB
cond.for.else.break.rad
326 B
cond.for.indexed.rad
238 B
cond.for.rad
165 B
cond.for.range.indexed.rad
526 B
cond.for.range.rad
171 B
cond.for.unsigned.range.rad
644 B
cond.forever.break.continue.rad
182 B
cond.forever.break.rad
232 B
cond.fused.rad
926 B
cond.if.case.rad
2.2 KiB
cond.if.else.min.rad
143 B
cond.if.else.rad
225 B
cond.if.elseif.rad
420 B
cond.if.noelse.rad
120 B
cond.if.rad
865 B
cond.match.fallthrough.rad
369 B
cond.match.guard.rad
1.4 KiB
cond.match.guard.regalloc.rad
1.3 KiB
cond.while.else.break.rad
282 B
cond.while.rad
119 B
const.array.copy.mutate.rad
386 B
const.array.rad
195 B
const.basic.rad
325 B
const.char.rad
159 B
const.fn.array.rad
664 B
const.record.array.rad
1.2 KiB
const.record.array.simple.rad
523 B
const.record.ctor.rad
170 B
const.record.fn.rad
353 B
const.record.rad
182 B
const.slice.param.rad
333 B
const.union.payload.ctor.rad
349 B
const.union.record.literal.rad
359 B
data.array.rad
767 B
data.bool.rad
216 B
data.i16.rad
261 B
data.i32.rad
281 B
data.i8.rad
248 B
data.record.rad
561 B
data.simple.rad
436 B
data.u16.rad
220 B
data.u32.rad
240 B
data.u8.rad
208 B
data.union.rad
886 B
debug.tag.rad
557 B
edge.cases.2.rad
337 B
edge.cases.3.rad
594 B
edge.cases.4.rad
1.2 KiB
edge.cases.5.rad
1.0 KiB
edge.cases.6.rad
2.6 KiB
edge.cases.7.addr.bug.rad
224 B
edge.cases.8.bug.rad
508 B
edge.cases.rad
223 B
error.basic.rad
159 B
error.catch.rad
1.6 KiB
error.division.zero.rad
164 B
error.modulo.zero.rad
162 B
error.multi.basic.rad
672 B
error.multi.catch.rad
772 B
error.multi.catch.typed.binding.rad
791 B
error.multi.catch.typed.catchall.rad
1.0 KiB
error.multi.catch.typed.rad
1.1 KiB
error.multi.propagate.multi.rad
953 B
error.multi.propagate.rad
825 B
error.multi.try.optional.rad
507 B
error.slice.bounds.rad
219 B
error.try.bang.success.rad
370 B
error.try.catch.binding.rad
2.0 KiB
error.try.optional.rad
1.8 KiB
error.try.rad
4.0 KiB
fn.block.scope.rad
508 B
fn.callback.nested.rad
1.2 KiB
fn.default.rad
131 B
fn.local.rad
140 B
fn.recursion.2.rad
239 B
fn.void.rad
150 B
for.else.continue.rad
1.1 KiB
frame.large.rad
567 B
if-let-mut.rad
1.1 KiB
iflet.shadow.leak.rad
317 B
integer.bitwise.basic.rad
693 B
integer.overflow.rad
1.8 KiB
large.blit.store.rad
2.1 KiB
let.guard.rad
1.9 KiB
literal.w64.rad
1.7 KiB
loc.addr.offset.bug.rad
410 B
loc.addr.opt.to.opt.rad
433 B
loc.addr.optional.assign.rad
408 B
loc.addr.record.assign.rad
443 B
loop.complex.flow.rad
1007 B
loop.sealblock.rad
911 B
match.array.rad
3.4 KiB
match.char.rad
1.6 KiB
match.multi.seal.rad
987 B
match.multi.survive.rad
1.6 KiB
match.mutref.push.rad
1.0 KiB
match.mutref.union.rad
662 B
match.nested.call.rad
1.7 KiB
match.nested.deep.rad
2.2 KiB
match.nested.deref.rad
3.7 KiB
match.nested.guard.rad
1.6 KiB
match.nested.iflet.guard.rad
1.6 KiB
match.nested.iflet.rad
1.4 KiB
match.nested.letelse.rad
813 B
match.nested.letelse.union.rad
1.3 KiB
match.nested.literal.rad
3.1 KiB
match.nested.multi.rad
2.4 KiB
match.nested.pattern.rad
5.2 KiB
match.nested.record.rad
2.0 KiB
match.nested.union.rad
2.3 KiB
match.nested.whilelet.rad
2.4 KiB
match.string.rad
1.8 KiB
match.value.copy.rad
2.0 KiB
match.void.then.or.rad
1.6 KiB
memzero.result.bug.rad
806 B
memzero.union.bug.rad
576 B
mutref.loop.bug.rad
1.8 KiB
opt.assignment.bug.rad
1.3 KiB
opt.bug.test.rad
1.4 KiB
opt.if.let.complex.rad
6.2 KiB
opt.if.let.guard.rad
809 B
opt.if.let.rad
956 B
opt.nil.check.rad
1.5 KiB
opt.record.eq.rad
842 B
opt.record.rad
655 B
opt.return.array.rad
289 B
opt.return.nested.rad
797 B
opt.return.record.rad
344 B
opt.slice.npo.rad
2.8 KiB
opt.type.rad
200 B
opt.while.let.complex.rad
404 B
panic.rad
111 B
placeholder.basic.rad
133 B
placeholder.comprehensive.rad
562 B
pointer.copy.edge.case.rad
1.3 KiB
pointer.slice.index.rad
269 B
pointer.slice.store.rad
881 B
prog.ackermann.rad
5.0 KiB
prog.bignum.rad
9.4 KiB
prog.binsearch.rad
2.4 KiB
prog.bubblesort.rad
2.0 KiB
prog.cordic.rad
6.9 KiB
prog.crc32.rad
2.7 KiB
prog.dijkstra.rad
7.7 KiB
prog.eval.rad
6.2 KiB
prog.hanoi.rad
3.8 KiB
prog.huffman.rad
9.3 KiB
prog.hybridsort.rad
3.0 KiB
prog.linkedlist.rad
5.8 KiB
prog.lzw.rad
6.7 KiB
prog.matmul.rad
2.9 KiB
prog.mersenne.rad
5.2 KiB
prog.nqueens.rad
3.4 KiB
prog.rbtree.rad
8.2 KiB
prog.regex.rad
10.2 KiB
prog.sha256.rad
7.0 KiB
prog.sieve.rad
2.8 KiB
prog.symtab.rad
10.1 KiB
prog.tokenizer.rad
13.8 KiB
prog.vm.rad
17.4 KiB
ptr.assign.rad
137 B
ptr.deref.rad
622 B
ptr.eq.rad
966 B
ptr.mutate.rad
244 B
ptr.opaque.rad
1.4 KiB
record.access.rad
285 B
record.alignment.rad
179 B
record.array.elements.rad
1.7 KiB
record.copy.rad
2.0 KiB
record.field.assign.rad
184 B
record.nested.calls.2.rad
612 B
record.nested.calls.3.rad
734 B
record.param.lit.rad
353 B
record.ptr.access.rad
227 B
record.ptr.mutate.rad
243 B
record.shorthand.rad
1.5 KiB
record.unlabeled.rad
407 B
ref.if.bug.rad
519 B
ref.immut.loop.bug.rad
670 B
ref.mut.ptr.rad
261 B
regalloc.callee.save.rad
1.5 KiB
regalloc.spill.reuse.rad
473 B
reserve.loop.rad
392 B
result.void.success.rad
716 B
slice.alloc.loop.rad
788 B
slice.append.rad
3.3 KiB
slice.cap.rad
941 B
slice.delete.rad
971 B
slice.of.rad
460 B
slice.subslice.rad
1.4 KiB
spill.blockarg.clobber.rad
3.5 KiB
spill.loop.rad
1.6 KiB
stack.local.corrupt.rad
320 B
static.array.mutate.rad
387 B
static.basic.rad
327 B
static.fn.array.rad
628 B
static.record.array.rad
503 B
static.slice.index.assign.rad
408 B
static.slice.offset.rad
668 B
string.basic.rad
149 B
string.escape.rad
349 B
string.index.rad
116 B
switch.blockargs.clobber.rad
1.3 KiB
trait.aggregate.ret.rad
1.5 KiB
trait.array.optional.rad
1.7 KiB
trait.basic.rad
565 B
trait.control.flow.rad
1.1 KiB
trait.fn.param.rad
1.6 KiB
trait.multiple.methods.rad
1.2 KiB
trait.multiple.traits.rad
1.2 KiB
trait.multiple.types.rad
1.3 KiB
trait.supertrait.rad
2.5 KiB
trait.throws.rad
1.0 KiB
trait.writer.rad
2.6 KiB
type.unify.rad
4.5 KiB
undefined.rad
417 B
union-tag.rad
911 B
union.bitfield.rad
1.2 KiB
union.discriminant.cast.rad
389 B
union.edge.case.2.rad
679 B
union.edge.case.3.rad
608 B
union.mixed.assign.rad
977 B
union.payload.mutref.rad
1.4 KiB
union.payload.rad
580 B
union.record.forward.rad
1.3 KiB
union.void.match.rad
403 B
union.void.rad
824 B
unsigned.compare.rad
1.9 KiB
var.align.rad
1013 B
var.infer.rad
549 B
decode.rad
14.6 KiB
emit.rad
24.4 KiB
encode.rad
19.9 KiB
isel.rad
41.1 KiB
printer.rad
13.0 KiB
tests.rad
15.7 KiB
rv64.rad
13.0 KiB
collections/
lang/
sys/
arch.rad
65 B
collections.rad
36 B
fmt.rad
3.8 KiB
intrinsics.rad
206 B
io.rad
1.2 KiB
lang.rad
222 B
mem.rad
2.2 KiB
sys.rad
167 B
testing.rad
2.4 KiB
tests.rad
11.6 KiB
vec.rad
3.1 KiB
std.rad
231 B
scripts/
seed/
test/
vim/
.gitignore
353 B
.gitsigners
112 B
LICENSE
1.1 KiB
Makefile
3.1 KiB
README
2.5 KiB
std.lib
987 B
std.lib.test
252 B
lib/std/arch/rv64/tests/prog.rbtree.rad
raw
| 1 | //! Red-black tree. |
| 2 | //! Implement a red-black tree (balanced BST) using a stack-allocated node pool. |
| 3 | |
| 4 | const POOL_SIZE: u32 = 128; |
| 5 | const NIL: u32 = 0; |
| 6 | |
| 7 | const RED: u32 = 0; |
| 8 | const BLACK: u32 = 1; |
| 9 | |
| 10 | record RBNode { |
| 11 | key: i32, |
| 12 | color: u32, |
| 13 | left: u32, |
| 14 | right: u32, |
| 15 | parent: u32, |
| 16 | } |
| 17 | |
| 18 | record RBTree { |
| 19 | pool: *mut [RBNode], |
| 20 | poolNext: u32, |
| 21 | root: u32, |
| 22 | inorder: *mut [i32], |
| 23 | inorderCount: u32, |
| 24 | } |
| 25 | |
| 26 | fn allocNode(t: *mut RBTree, key: i32) -> u32 { |
| 27 | let idx: u32 = t.poolNext; |
| 28 | t.poolNext += 1; |
| 29 | t.pool[idx] = RBNode { key, color: RED, left: NIL, right: NIL, parent: NIL }; |
| 30 | return idx; |
| 31 | } |
| 32 | |
| 33 | fn rotateLeft(t: *mut RBTree, x: u32) { |
| 34 | let y: u32 = t.pool[x].right; |
| 35 | t.pool[x].right = t.pool[y].left; |
| 36 | if t.pool[y].left != NIL { |
| 37 | t.pool[t.pool[y].left].parent = x; |
| 38 | } |
| 39 | t.pool[y].parent = t.pool[x].parent; |
| 40 | if t.pool[x].parent == NIL { |
| 41 | t.root = y; |
| 42 | } else if x == t.pool[t.pool[x].parent].left { |
| 43 | t.pool[t.pool[x].parent].left = y; |
| 44 | } else { |
| 45 | t.pool[t.pool[x].parent].right = y; |
| 46 | } |
| 47 | t.pool[y].left = x; |
| 48 | t.pool[x].parent = y; |
| 49 | } |
| 50 | |
| 51 | fn rotateRight(t: *mut RBTree, x: u32) { |
| 52 | let y: u32 = t.pool[x].left; |
| 53 | t.pool[x].left = t.pool[y].right; |
| 54 | if t.pool[y].right != NIL { |
| 55 | t.pool[t.pool[y].right].parent = x; |
| 56 | } |
| 57 | t.pool[y].parent = t.pool[x].parent; |
| 58 | if t.pool[x].parent == NIL { |
| 59 | t.root = y; |
| 60 | } else if x == t.pool[t.pool[x].parent].right { |
| 61 | t.pool[t.pool[x].parent].right = y; |
| 62 | } else { |
| 63 | t.pool[t.pool[x].parent].left = y; |
| 64 | } |
| 65 | t.pool[y].right = x; |
| 66 | t.pool[x].parent = y; |
| 67 | } |
| 68 | |
| 69 | fn insertFixup(t: *mut RBTree, zArg: u32) { |
| 70 | let mut z: u32 = zArg; |
| 71 | while t.pool[t.pool[z].parent].color == RED { |
| 72 | if t.pool[z].parent == t.pool[t.pool[t.pool[z].parent].parent].left { |
| 73 | let y: u32 = t.pool[t.pool[t.pool[z].parent].parent].right; |
| 74 | if t.pool[y].color == RED { |
| 75 | t.pool[t.pool[z].parent].color = BLACK; |
| 76 | t.pool[y].color = BLACK; |
| 77 | t.pool[t.pool[t.pool[z].parent].parent].color = RED; |
| 78 | z = t.pool[t.pool[z].parent].parent; |
| 79 | } else { |
| 80 | if z == t.pool[t.pool[z].parent].right { |
| 81 | z = t.pool[z].parent; |
| 82 | rotateLeft(t, z); |
| 83 | } |
| 84 | t.pool[t.pool[z].parent].color = BLACK; |
| 85 | t.pool[t.pool[t.pool[z].parent].parent].color = RED; |
| 86 | rotateRight(t, t.pool[t.pool[z].parent].parent); |
| 87 | } |
| 88 | } else { |
| 89 | let y: u32 = t.pool[t.pool[t.pool[z].parent].parent].left; |
| 90 | if t.pool[y].color == RED { |
| 91 | t.pool[t.pool[z].parent].color = BLACK; |
| 92 | t.pool[y].color = BLACK; |
| 93 | t.pool[t.pool[t.pool[z].parent].parent].color = RED; |
| 94 | z = t.pool[t.pool[z].parent].parent; |
| 95 | } else { |
| 96 | if z == t.pool[t.pool[z].parent].left { |
| 97 | z = t.pool[z].parent; |
| 98 | rotateRight(t, z); |
| 99 | } |
| 100 | t.pool[t.pool[z].parent].color = BLACK; |
| 101 | t.pool[t.pool[t.pool[z].parent].parent].color = RED; |
| 102 | rotateLeft(t, t.pool[t.pool[z].parent].parent); |
| 103 | } |
| 104 | } |
| 105 | } |
| 106 | t.pool[t.root].color = BLACK; |
| 107 | } |
| 108 | |
| 109 | fn insert(t: *mut RBTree, key: i32) { |
| 110 | let z: u32 = allocNode(t, key); |
| 111 | let mut y: u32 = NIL; |
| 112 | let mut x: u32 = t.root; |
| 113 | |
| 114 | while x != NIL { |
| 115 | y = x; |
| 116 | if key < t.pool[x].key { |
| 117 | x = t.pool[x].left; |
| 118 | } else { |
| 119 | x = t.pool[x].right; |
| 120 | } |
| 121 | } |
| 122 | |
| 123 | t.pool[z].parent = y; |
| 124 | if y == NIL { |
| 125 | t.root = z; |
| 126 | } else if key < t.pool[y].key { |
| 127 | t.pool[y].left = z; |
| 128 | } else { |
| 129 | t.pool[y].right = z; |
| 130 | } |
| 131 | |
| 132 | insertFixup(t, z); |
| 133 | } |
| 134 | |
| 135 | fn search(t: *RBTree, key: i32) -> bool { |
| 136 | let mut x: u32 = t.root; |
| 137 | while x != NIL { |
| 138 | if key == t.pool[x].key { |
| 139 | return true; |
| 140 | } else if key < t.pool[x].key { |
| 141 | x = t.pool[x].left; |
| 142 | } else { |
| 143 | x = t.pool[x].right; |
| 144 | } |
| 145 | } |
| 146 | return false; |
| 147 | } |
| 148 | |
| 149 | fn inorderWalk(t: *mut RBTree, x: u32) { |
| 150 | if x == NIL { |
| 151 | return; |
| 152 | } |
| 153 | inorderWalk(t, t.pool[x].left); |
| 154 | t.inorder[t.inorderCount] = t.pool[x].key; |
| 155 | t.inorderCount += 1; |
| 156 | inorderWalk(t, t.pool[x].right); |
| 157 | } |
| 158 | |
| 159 | fn countNodes(t: *RBTree, x: u32) -> u32 { |
| 160 | if x == NIL { |
| 161 | return 0; |
| 162 | } |
| 163 | return 1 + countNodes(t, t.pool[x].left) + countNodes(t, t.pool[x].right); |
| 164 | } |
| 165 | |
| 166 | fn blackHeight(t: *RBTree, x: u32) -> i32 { |
| 167 | if x == NIL { |
| 168 | return 1; |
| 169 | } |
| 170 | let leftBH: i32 = blackHeight(t, t.pool[x].left); |
| 171 | let rightBH: i32 = blackHeight(t, t.pool[x].right); |
| 172 | |
| 173 | if leftBH == -1 or rightBH == -1 { |
| 174 | return -1; |
| 175 | } |
| 176 | if leftBH != rightBH { |
| 177 | return -1; |
| 178 | } |
| 179 | |
| 180 | if t.pool[x].color == BLACK { |
| 181 | return leftBH + 1; |
| 182 | } |
| 183 | return leftBH; |
| 184 | } |
| 185 | |
| 186 | fn noRedRed(t: *RBTree, x: u32) -> bool { |
| 187 | if x == NIL { |
| 188 | return true; |
| 189 | } |
| 190 | if t.pool[x].color == RED { |
| 191 | if t.pool[t.pool[x].left].color == RED { |
| 192 | return false; |
| 193 | } |
| 194 | if t.pool[t.pool[x].right].color == RED { |
| 195 | return false; |
| 196 | } |
| 197 | } |
| 198 | if not noRedRed(t, t.pool[x].left) { |
| 199 | return false; |
| 200 | } |
| 201 | return noRedRed(t, t.pool[x].right); |
| 202 | } |
| 203 | |
| 204 | fn resetTree(t: *mut RBTree) { |
| 205 | let mut i: u32 = 0; |
| 206 | while i < POOL_SIZE { |
| 207 | t.pool[i] = RBNode { key: 0, color: BLACK, left: NIL, right: NIL, parent: NIL }; |
| 208 | i += 1; |
| 209 | } |
| 210 | t.poolNext = 1; |
| 211 | t.root = NIL; |
| 212 | t.inorderCount = 0; |
| 213 | } |
| 214 | |
| 215 | fn testAscending(t: *mut RBTree) -> i32 { |
| 216 | resetTree(t); |
| 217 | |
| 218 | let mut i: i32 = 0; |
| 219 | while i < 32 { |
| 220 | insert(t, i); |
| 221 | i += 1; |
| 222 | } |
| 223 | |
| 224 | assert countNodes(t, t.root) == 32; |
| 225 | assert t.pool[t.root].color == BLACK; |
| 226 | |
| 227 | let bh: i32 = blackHeight(t, t.root); |
| 228 | assert bh != -1; |
| 229 | |
| 230 | assert noRedRed(t, t.root); |
| 231 | |
| 232 | t.inorderCount = 0; |
| 233 | inorderWalk(t, t.root); |
| 234 | assert t.inorderCount == 32; |
| 235 | let mut j: u32 = 0; |
| 236 | while j < 32 { |
| 237 | assert t.inorder[j] == j as i32; |
| 238 | j += 1; |
| 239 | } |
| 240 | |
| 241 | return 0; |
| 242 | } |
| 243 | |
| 244 | fn testDescending(t: *mut RBTree) -> i32 { |
| 245 | resetTree(t); |
| 246 | |
| 247 | let mut i: i32 = 31; |
| 248 | while i >= 0 { |
| 249 | insert(t, i); |
| 250 | if i == 0 { |
| 251 | break; |
| 252 | } |
| 253 | i -= 1; |
| 254 | } |
| 255 | |
| 256 | assert countNodes(t, t.root) == 32; |
| 257 | assert blackHeight(t, t.root) != -1; |
| 258 | assert noRedRed(t, t.root); |
| 259 | |
| 260 | t.inorderCount = 0; |
| 261 | inorderWalk(t, t.root); |
| 262 | let mut j: u32 = 0; |
| 263 | while j < 32 { |
| 264 | assert t.inorder[j] == j as i32; |
| 265 | j += 1; |
| 266 | } |
| 267 | |
| 268 | return 0; |
| 269 | } |
| 270 | |
| 271 | fn testRandom(t: *mut RBTree) -> i32 { |
| 272 | resetTree(t); |
| 273 | |
| 274 | let mut inserted: [bool; 48] = [false; 48]; |
| 275 | let mut seed: u32 = 42; |
| 276 | let mut count: u32 = 0; |
| 277 | |
| 278 | while count < 48 { |
| 279 | seed = (seed * 1103515245 + 12345) & 0x7FFFFFFF; |
| 280 | let val: u32 = seed % 48; |
| 281 | if not inserted[val] { |
| 282 | insert(t, val as i32); |
| 283 | inserted[val] = true; |
| 284 | count += 1; |
| 285 | } |
| 286 | } |
| 287 | |
| 288 | assert countNodes(t, t.root) == 48; |
| 289 | assert blackHeight(t, t.root) != -1; |
| 290 | assert noRedRed(t, t.root); |
| 291 | |
| 292 | let mut i: i32 = 0; |
| 293 | while i < 48 { |
| 294 | assert search(t, i); |
| 295 | i += 1; |
| 296 | } |
| 297 | |
| 298 | assert not search(t, -1); |
| 299 | assert not search(t, 48); |
| 300 | assert not search(t, 100); |
| 301 | |
| 302 | t.inorderCount = 0; |
| 303 | inorderWalk(t, t.root); |
| 304 | assert t.inorderCount == 48; |
| 305 | let mut j: u32 = 0; |
| 306 | while j < 48 { |
| 307 | assert t.inorder[j] == j as i32; |
| 308 | j += 1; |
| 309 | } |
| 310 | |
| 311 | return 0; |
| 312 | } |
| 313 | |
| 314 | fn testHeight(t: *mut RBTree) -> i32 { |
| 315 | resetTree(t); |
| 316 | |
| 317 | let mut i: i32 = 0; |
| 318 | while i < 63 { |
| 319 | insert(t, i); |
| 320 | i += 1; |
| 321 | } |
| 322 | |
| 323 | let bh: i32 = blackHeight(t, t.root); |
| 324 | assert bh >= 3; |
| 325 | assert bh <= 7; |
| 326 | |
| 327 | return 0; |
| 328 | } |
| 329 | |
| 330 | @default fn main() -> i32 { |
| 331 | let mut pool: [RBNode; 128] = [RBNode { key: 0, color: 1, left: 0, right: 0, parent: 0 }; 128]; |
| 332 | let mut inorder: [i32; 128] = [0; 128]; |
| 333 | |
| 334 | let mut t: RBTree = RBTree { |
| 335 | pool: &mut pool[..], |
| 336 | poolNext: 1, |
| 337 | root: NIL, |
| 338 | inorder: &mut inorder[..], |
| 339 | inorderCount: 0, |
| 340 | }; |
| 341 | |
| 342 | let r1: i32 = testAscending(&mut t); |
| 343 | if r1 != 0 { return 10 + r1; } |
| 344 | |
| 345 | let r2: i32 = testDescending(&mut t); |
| 346 | if r2 != 0 { return 20 + r2; } |
| 347 | |
| 348 | let r3: i32 = testRandom(&mut t); |
| 349 | if r3 != 0 { return 30 + r3; } |
| 350 | |
| 351 | let r4: i32 = testHeight(&mut t); |
| 352 | if r4 != 0 { return 50 + r4; } |
| 353 | |
| 354 | return 0; |
| 355 | } |