Associative Array that Supports upper/lower Ranges
Vijay Nayar
madric at gmail.com
Mon Jun 25 22:01:24 UTC 2018
I was in need of an associative array / dictionary object that
could also support getting ranges of entries with keys below or
above a given value. I couldn't find anything that would do
this, and ended up using the RedBlackTree to store key/value
pairs, and then wrap the relevant functions with key lookups.
I feel that there was probably an easier way to do this, but I
didn't find one. Regardless, if anyone else has this kind of
problem, you can get around it like this:
```
module rbtree_map;
import std.container.rbtree;
import std.algorithm : map;
import std.functional : binaryFun;
import std.meta : allSatisfy;
import std.range : ElementType, isInputRange;
import std.traits : isDynamicArray, isImplicitlyConvertible;
/**
* A dictionary or associative array backed by a Red-Black tree.
*/
unittest {
auto rbTreeMap = new RBTreeMap!(string, int)();
rbTreeMap["a"] = 4;
rbTreeMap["b"] = 2;
rbTreeMap["c"] = 3;
rbTreeMap["d"] = 1;
rbTreeMap["e"] = 5;
assert(rbTreeMap.length() == 5);
assert("c" in rbTreeMap);
rbTreeMap.removeKey("c");
assert("c" !in rbTreeMap);
rbTreeMap.lowerBound("c"); // Range of ("a", 4), ("b", 2)
rbTreeMap.upperBound("c"); // Range of ("d", 1), ("e", 5)
}
final class RBTreeMap(KeyT, ValueT, alias KeyLessF = "a < b",
bool allowDuplicates = false) {
public:
static struct Pair {
KeyT key;
ValueT value;
}
alias keyLess = binaryFun!KeyLessF;
alias RedBlackTreeT =
RedBlackTree!(Pair, (pair1, pair2) => keyLess(pair1.key,
pair2.key), allowDuplicates);
RedBlackTreeT rbTree;
// Forward compatible methods like: empty(), length(),
opSlice(), etc.
alias rbTree this;
this() {
rbTree = new RedBlackTreeT();
}
this(Pair[] elems...) {
rbTree = new RedBlackTreeT(elems);
}
this(PairRange)(PairRange pairRange)
if (isInputRange!PairRange &&
isImplicitlyConvertible!(ElementType!PairRange, Pair)) {
rbTree = new RedBlackTreeT(pairRange);
}
override
bool opEquals(Object rhs) {
RBTreeMap that = cast(RBTreeMap) rhs;
if (that is null) return false;
return rbTree == that.rbTree;
}
/// Insertion
size_t stableInsert(K, V)(K key, V value)
if (isImplicitlyConvertible!(K, KeyT) &&
isImplicitlyConvertible!(V, ValueT)) {
return rbTree.stableInsert(Pair(key, value));
}
alias insert = stableInsert;
ValueT opIndexAssign(ValueT value, KeyT key) {
rbTree.stableInsert(Pair(key, value));
return value;
}
/// Membership
bool opBinaryRight(string op)(KeyT key) const
if (op == "in") {
return Pair(key) in rbTree;
}
/// Removal
size_t removeKey(K...)(K keys)
if (allSatisfy!(isImplicitlyConvertibleToKey, K)) {
KeyT[K.length] toRemove = [keys];
return removeKey(toRemove[]);
}
//Helper for removeKey.
private template isImplicitlyConvertibleToKey(K)
{
enum isImplicitlyConvertibleToKey =
isImplicitlyConvertible!(K, KeyT);
}
size_t removeKey(K)(K[] keys)
if (isImplicitlyConvertible!(K, KeyT)) {
auto keyPairs = keys.map!(key => Pair(key));
return rbTree.removeKey(keyPairs);
}
size_t removeKey(KeyRange)(KeyRange keyRange)
if (isInputRange!KeyRange
&& isImplicitlyConvertible!(ElementType!KeyRange, KeyT)
&& !isDynamicArray!KeyRange) {
auto keyPairs = keys.map(key => Pair(key));
return rbTree.removeKey(keyPairs);
}
/// Ranges
RedBlackTreeT.Range upperBound(KeyT key) {
return rbTree.upperBound(Pair(key));
}
RedBlackTreeT.ConstRange upperBound(KeyT key) const {
return rbTree.upperBound(Pair(key));
}
RedBlackTreeT.ImmutableRange upperBound(KeyT key) immutable {
return rbTree.upperBound(Pair(key));
}
RedBlackTreeT.Range lowerBound(KeyT key) {
return rbTree.lowerBound(Pair(key));
}
RedBlackTreeT.ConstRange lowerBound(KeyT key) const {
return rbTree.lowerBound(Pair(key));
}
RedBlackTreeT.ImmutableRange lowerBound(KeyT key) immutable {
return rbTree.lowerBound(Pair(key));
}
auto equalRange(KeyT key) {
return rbTree.equalRange(Pair(key));
}
}
```
More information about the Digitalmars-d
mailing list