std.container.rbtree

1 import std.algorithm.comparison : equal;
2 import std.container.rbtree;
3 
4 auto rbt = redBlackTree(3, 1, 4, 2, 5);
5 assert(rbt.front == 1);
6 assert(equal(rbt[], [1, 2, 3, 4, 5]));
7 
8 rbt.removeKey(1, 4);
9 assert(equal(rbt[], [2, 3, 5]));
10 
11 rbt.removeFront();
12 assert(equal(rbt[], [3, 5]));
13 
14 rbt.insert([1, 2, 4]);
15 assert(equal(rbt[], [1, 2, 3, 4, 5]));
16 
17 // Query bounds in O(log(n))
18 assert(rbt.lowerBound(3).equal([1, 2]));
19 assert(rbt.equalRange(3).equal([3]));
20 assert(rbt.upperBound(3).equal([4, 5]));
21 
22 // A Red Black tree with the highest element at front:
23 import std.range : iota;
24 auto maxTree = redBlackTree!"a > b"(iota(5));
25 assert(equal(maxTree[], [4, 3, 2, 1, 0]));
26 
27 // adding duplicates will not add them, but return 0
28 auto rbt2 = redBlackTree(1, 3);
29 assert(rbt2.insert(1) == 0);
30 assert(equal(rbt2[], [1, 3]));
31 assert(rbt2.insert(2) == 1);
32 
33 // however you can allow duplicates
34 auto ubt = redBlackTree!true([0, 1, 0, 1]);
35 assert(equal(ubt[], [0, 0, 1, 1]));