nxt.trie

Tries and Prefix Trees.

Implementation is layered:

RawRadixTree stores its untyped keys as variable length ubyte-strings (UKey)
On top of that RadixTree implements typed-key access via its template parameter Key.

Both layers currently support

template parameterization on the Value-type in the map case (when Value is non-void)
@nogc and, when possible, @safe pure nothrow
insertion with returned modifications status: auto newKeyWasInserted = set.insert(Key key)
AA-style in-operator

AA-style iteration of map keys: map.byKey()
AA-style iteration of map values: map.byValue()
SortedRange-style iteration over elements sorted by key: assert(set[].isSorted)
containment checking: bool contains(in Key key)
element indexing and element index assignment for map case via opIndex and opIndexAssign
key-prefix Completion (returning a Range over all set/map-elements that match a key prefix): prefix(Key keyPrefix)

Typed layer supports

Members

FixedKeyLeafN alias FixedKeyLeafN = WordVariant!(OneLeafMax7, TwoLeaf3, TriLeaf2): Fixed-Length leaf Key-only Node.
IKey alias IKey(size_t span) = immutable(Mod!(2^^span))[]: Immutable RawTree Key.
IKey alias IKey(size_t span) = immutable(ubyte)[]: Immutable RawTree Key.
Key alias Key(size_t span) = Mod!(2^^span)[]: Mutable RawTree Key.
Key alias Key(size_t span) = ubyte[]: Mutable RawTree Key.
KeyN alias KeyN(size_t span, size_t N) = Mod!(2^^span)[N]: Fixed-Length RawTree Key.
KeyN alias KeyN(size_t span, size_t N) = ubyte[N]: Fixed-Length RawTree Key.
Leaf1 alias Leaf1(Value) = WordVariant!(HeptLeaf1, SparseLeaf1!Value*, DenseLeaf1!Value*): Mutable leaf node of 1-Ix leaves.

checkNumeric auto checkNumeric(): Check correctness when span is span and for each Key in Keys.
constructFixedSizeNode auto constructFixedSizeNode(Args args): Allocate (if pointer) and Construct a Node-type of value type NodeType using constructor arguments args of Args.
firstIx UIx firstIx(Leaf1!Value curr)
print void print(RadixTree!(Key, Value) tree): Print tree.
radixTreeMap RadixTree!(MutableKey!Key, Value) radixTreeMap(): Instantiator for the map-version of RadixTree where value-type is Value.
radixTreeSet RadixTree!(MutableKey!Key, void) radixTreeSet(): Instantiator for the set-version of RadixTree where value-type is void (unused).
showStatistics void showStatistics(RT tree): Calculate and print statistics of tree.
testString auto testString(size_t count, uint maxLength): Check string types in Keys.
toFixedRawKey UKey toFixedRawKey(TypedKey typedKey, UKey preallocatedFixedUKey): Remap fixed-length typed key typedKey to raw (untyped) key of type UKey. TODO: DIP-1000 scope
toRawKey UKey toRawKey(TypedKey typedKey, Array!Ix rawUKey): Remap typed key typedKey to raw (untyped) key of type UKey.
toTypedKey inout(TypedKey) toTypedKey(inout(Ix)[] ukey): Remap raw untyped key ukey to typed key of type TypedKey.
tryNextIx bool tryNextIx(Leaf1!Value curr, UIx ix, Ix nextIx): Try to iterate leaf index ix to index, either sparse or dense and put result in nextIx.

HeptLeaf1 struct HeptLeaf1: Hepa/7-Key Leaf with key-length 1.
OneLeafMax7 struct OneLeafMax7: Single/1-Key Leaf with maximum key-length 7.
RadixTree struct RadixTree(K, V): Radix-Tree with key of type K and value of type V (if non-void).
TriLeaf2 struct TriLeaf2: Ternary/3-Key Leaf with key-length 2.
TwoLeaf3 struct TwoLeaf3: Binary/2-Key Leaf with key-length 3.

MutableKey template MutableKey(Key): Keys are stored in a way that they can't be accessed by reference so we allow array (and string) keys to be of mutable type.
RawRadixTree template RawRadixTree(Value = void): Adaptive radix tree (ART) container storing untyped (raw) keys.
iota template iota(size_t from, size_t to): Static Iota.
isTrieableKeyType template isTrieableKeyType(T)