RadixTree

Radix-Tree with key of type K and value of type V (if non-void).

Radix-tree is also called a patricia trie, radix trie or compact prefix tree.

struct RadixTree (

K

V

A = Mallocator

) if (

isTrieableKeyType!(K) &&

isAllocator!A

) {

import std.experimental.allocator.common : stateSize;;

alias KeyType = K;

alias MK = const(Unqual!(U))[];

alias MK = K;

alias ValueType = V;

alias ElementType = E;

static if(RawTree.hasValue)

V opIndex(MK key);

static if(RawTree.hasValue)

auto opIndexAssign(V value, MK key);

static if(RawTree.hasValue)

bool insert(ElementType e);

static if(RawTree.hasValue)

bool insert(MK key, V value);

static if(RawTree.hasValue)

inout(V*) contains(MK key);

static if(RawTree.hasValue)

Range byKeyValue();

alias ElementType = K;

static if(!(RawTree.hasValue))

bool insert(MK key);

static if(!(RawTree.hasValue))

bool contains(MK key);

static if(!(RawTree.hasValue))

Range byKey();

auto opBinaryRight(MK key);

Range opSlice();

auto prefix(MK keyPrefix);

auto upperBound(MK key);

typeof(this) dup();

}

Constructors

this this(): Undocumented in source.
this this(A alloc): Use the given allocator for allocations.

Alias This

Members

Aliases

ElementType alias ElementType = E: Undocumented in source.
ElementType alias ElementType = K: Undocumented in source.
KeyType alias KeyType = K: Undocumented in source.
MK alias MK = const(Unqual!(U))[]: 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.
MK alias MK = K: Undocumented in source.
ValueType alias ValueType = V: Undocumented in source.

Functions

byKey Range byKey(): AA-style key range.
byKeyValue Range byKeyValue(): AA-style key-value range.
contains inout(V*) contains(MK key)
contains bool contains(MK key)
dup typeof(this) dup(): Returns a duplicate of this tree. Shallowly duplicates the values in the map case.
insert bool insert(ElementType e): Insert element elt.
insert bool insert(MK key, V value): Insert key with value.
insert bool insert(MK key): Insert key.
opBinaryRight auto opBinaryRight(MK key): Supports K in this syntax.
opIndex V opIndex(MK key): Undocumented in source. Be warned that the author may not have intended to support it.
opIndexAssign auto opIndexAssign(V value, MK key): Undocumented in source. Be warned that the author may not have intended to support it.
opSlice Range opSlice(): Undocumented in source. Be warned that the author may not have intended to support it.
prefix auto prefix(MK keyPrefix): Get range over elements whose key starts with keyPrefix. The element equal to keyPrefix is return as an empty instance of the type.
upperBound auto upperBound(MK key): This function searches with policy sp to find the largest right subrange on which pred(value, x) is true for all x (e.g., if pred is "less than", returns the portion of the range with elements strictly greater than value).

Structs

E struct E: Element type.

Meta

Source

See Implementation

nxt container trie aliases

enums

functions

manifest constants

structs

templates