nxt.container.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

key in set is bool for set-case
key in map returns non-null value pointer when key is stored in map

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

ordered access of aggregate types

Test: dmd -version=show -preview=dip1000 -preview=in -vcolumns -preview=in -debug -g -unittest -checkaction=context -allinst -main -unittest -I../.. -i -run trie.d

Members

Aliases

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.
Ix alias Ix = Mod!(radix, ubyte): Radix Modulo Index Restricted index type avoids range checking in array indexing below.
Ix alias Ix = ubyte: Undocumented in source.
Ixs alias Ixs = Array!(Ix, Mallocator): Undocumented in source.
IxsN alias IxsN(uint capacity, uint elementLength) = StaticModArray!(capacity, elementLength, 8, useModuloFlag): Undocumented in source.
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.
RadixTreeMap alias RadixTreeMap = RadixTree: Undocumented in source.
UIx alias UIx = Mod!(radix, size_t): Radix Modulo Index Restricted index type avoids range checking in array indexing below.
UIx alias UIx = size_t: Undocumented in source.
UKey alias UKey = Key!span: Undocumented in source.
isFixedTrieableKeyType alias isFixedTrieableKeyType = isIntegralBijectableType: Undocumented in source.

Enums

ModStatus enum ModStatus: Results of attempt at modification sub.
isScalarTrieableKeyType eponymoustemplate isScalarTrieableKeyType(T)

Functions

empty bool empty(UKey ukey): Undocumented in source. Be warned that the author may not have intended to support it.
firstIx UIx firstIx(Leaf1!Value curr)
freeNode void freeNode(A alloc, NodeType nt): Undocumented in source. Be warned that the author may not have intended to support it.
makeFixedSizeNodePointer auto makeFixedSizeNodePointer(A alloc, Args args): Allocate and Construct a Node-type of value type NodeType using constructor arguments args of Args.
makeFixedSizeNodeValue auto makeFixedSizeNodeValue(Args args): Construct a Node-type of value type NodeType using constructor arguments args of Args.
print void print(RadixTree!(Key, Value, A) tree): Print tree.
showStatistics void showStatistics(RT tree): Calculate and print statistics of tree.
testEqual bool testEqual(T x, U y): Undocumented in source. Be warned that the author may not have intended to support it.
testScalar auto testScalar(): Undocumented in source. Be warned that the author may not have intended to support it.
testString auto testString(size_t count, uint lengthMax): 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, Ixs 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.

Manifest constants

keySeparator enum keySeparator;: Undocumented in source.
useModuloFlag enum useModuloFlag;: Undocumented in source.
useModuloFlag enum useModuloFlag;: Undocumented in source.

Structs

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, A = Mallocator): 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.

Templates

RadixTreeSet template RadixTreeSet(K, A = Mallocator): Undocumented in source.
RawRadixTree template RawRadixTree(Value = void, A_): Adaptive radix tree/trie (ART) container storing untyped (raw) keys.
iota template iota(size_t from, size_t to): Static Iota.
isTrieableKeyType template isTrieableKeyType(T)