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
|
@safe pure unittest
{
import std.container.rbtree;
import std.algorithm.comparison : equal;
import std.container.rbtree;
auto rbt = redBlackTree(3, 1, 4, 2, 5);
assert(rbt.front == 1);
assert(equal(rbt[], [1, 2, 3, 4, 5]));
rbt.removeKey(1, 4);
assert(equal(rbt[], [2, 3, 5]));
rbt.removeFront();
assert(equal(rbt[], [3, 5]));
rbt.insert([1, 2, 4]);
assert(equal(rbt[], [1, 2, 3, 4, 5]));
// Query bounds in O(log(n))
assert(rbt.lowerBound(3).equal([1, 2]));
assert(rbt.equalRange(3).equal([3]));
assert(rbt.upperBound(3).equal([4, 5]));
// A Red Black tree with the highest element at front:
import std.range : iota;
auto maxTree = redBlackTree!"a > b"(iota(5));
assert(equal(maxTree[], [4, 3, 2, 1, 0]));
// adding duplicates will not add them, but return 0
auto rbt2 = redBlackTree(1, 3);
assert(rbt2.insert(1) == 0);
assert(equal(rbt2[], [1, 3]));
assert(rbt2.insert(2) == 1);
// however you can allow duplicates
auto ubt = redBlackTree!true([0, 1, 0, 1]);
assert(equal(ubt[], [0, 0, 1, 1]));
}
@safe pure unittest
{
import std.container.rbtree;
import std.range : iota;
auto rbt1 = redBlackTree(0, 1, 5, 7);
auto rbt2 = redBlackTree!string("hello", "world");
auto rbt3 = redBlackTree!true(0, 1, 5, 7, 5);
auto rbt4 = redBlackTree!"a > b"(0, 1, 5, 7);
auto rbt5 = redBlackTree!("a > b", true)(0.1, 1.3, 5.9, 7.2, 5.9);
// also works with ranges
auto rbt6 = redBlackTree(iota(3));
auto rbt7 = redBlackTree!true(iota(3));
auto rbt8 = redBlackTree!"a > b"(iota(3));
auto rbt9 = redBlackTree!("a > b", true)(iota(3));
}
|
