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
|
import {RBTree, Iterator, rbtree_shallow_copy} from '/src/rbtree.ts'
function cmpInt(a: int, b: int){
return a - b;
}
function getIteratorEls<T>(itr: Iterator<T>): T[]{
let els: T[] = [];
if (itr.data() != null){
els.push(itr.data());
}
let el: T | null;
while ((el = itr.next()) != null){
els.push(el);
}
return els;
}
function getIteratorElsRev<T>(itr: Iterator<T>): T[]{
let els: T[] = [];
if (itr.data() != null){
els.push(itr.data());
}
let el: T | null;
while ((el = itr.prev()) != null){
els.push(el);
}
return els;
}
test('insert and remove', () => {
let tree = new RBTree(cmpInt);
expect(tree.insert(10)).toBe(true);
expect(tree.insert(10)).toBe(false);
expect(tree.insert(20)).toBe(true);
expect(tree.insert(-1)).toBe(true);
//
expect(tree.remove(100)).toBe(false);
expect(tree.remove(10)).toBe(true);
//
expect(tree.size).toBe(2);
expect(tree.min()).toBe(-1);
expect(tree.max()).toBe(20);
});
test('iteration', () => {
let vals = [10, 10, 20, 5, -1];
let tree = new RBTree(cmpInt);
for (let v of vals){
tree.insert(v);
}
let sorted = Array.from(new Set(vals)).sort(cmpInt);
expect(getIteratorEls(tree.iterator())).toEqual(sorted);
sorted.reverse()
expect(getIteratorElsRev(tree.iterator())).toEqual(sorted);
});
test('find', () => {
let tree = new RBTree(cmpInt);
tree.insert(1);
tree.insert(10);
tree.insert(50);
tree.insert(100);
//
expect(tree.find(40)).toBe(null);
expect(tree.find(50)).toBe(50);
expect(getIteratorEls(tree.lowerBound(10))).toEqual([10, 50, 100]);
expect(getIteratorEls(tree.upperBound(10))).toEqual([50, 100]);
});
|
