s2.util.container.btree_map source code

1 module s2.util.container.btree_map;
2 
3 import s2.util.container.btree;
4 
5 import std.algorithm : map;
6 import std.functional : binaryFun;
7 import std.meta : allSatisfy;
8 import std.range : ElementType, isInputRange;
9 import std.traits : isDynamicArray, isImplicitlyConvertible;
10 
11 /**
12  * An associative-array or map implementation based upon a B-Tree.
13  */
14 final class BTreeMap(KeyT, ValueT, size_t NodeSizeV = 256, alias KeyLessF = "a < b") {
15 public:
16   static struct Pair {
17     KeyT key;
18     ValueT value;
19   }
20 
21   alias _isKeyLess = binaryFun!KeyLessF;
22 
23   alias BTreeT = BTree!(Pair, NodeSizeV, (pair1, pair2) => _isKeyLess(pair1.key, pair2.key));
24 
25   BTreeT bTree;
26 
27   // Forward compatible methods like: empty(), length(), opSlice(), etc.
28   alias bTree this;
29 
30   this() {
31     bTree = new BTreeT();
32   }
33 
34   /// Insertion
35   void insert(K, V)(K key, V value)
36   if (isImplicitlyConvertible!(K, KeyT) && isImplicitlyConvertible!(V, ValueT)) {
37     return bTree.insert(Pair(key, value));
38   }
39 
40   ValueT opIndexAssign(ValueT value, KeyT key) {
41     bTree.insert(Pair(key, value));
42     return value;
43   }
44 
45   /// Membership
46   bool opBinaryRight(string op)(KeyT key)
47   if (op == "in") {
48     return Pair(key) in bTree;
49   }
50 
51   /// Removal
52   void remove(KeyT key) {
53     bTree.remove(Pair(key));
54   }
55 
56   /// Ranges
57   BTreeT.Range upperRange(KeyT key) {
58     return bTree.upperRange(Pair(key));
59   }
60 
61   BTreeT.Range lowerRange(KeyT key) {
62     return bTree.lowerRange(Pair(key));
63   }
64 
65   BTreeT.Range equalRange(KeyT key) {
66     return bTree.equalRange(Pair(key));
67   }
68 }