ArrayTernaryTrie

A Ternary Trie string lookup data structure. This Trie is of a fixed size and cannot grow (which can be a good thing with regards to DOS when used as a cache). The Trie is stored in 3 arrays: <dl> <dt>char[] _tree</dt><dd>This is semantically 2 dimensional array flattened into a 1 dimensional char array. The second dimension is that every 4 sequential elements represents a row of: character; hi index; eq index; low index, used to build a ternary trie of key strings.</dd> <dt>string[] _key</dt><dd>An array of key values where each element matches a row in the _tree array. A non zero key element indicates that the _tree row is a complete key rather than an intermediate character of a longer key.</dd> <dt>V[] _value</dt><dd>An array of values corresponding to the _key array</dd> </dl> The lookup of a value will iterate through the _tree array matching characters. If the equal tree branch is followed, then the _key array is looked up to see if this is a complete match. If a match is found then the _value array is looked up to return the matching value. This Trie may be instantiated either as case sensitive or insensitive. This Trie is not Threadsafe and contains no mutual exclusion or deliberate memory barriers. It is intended for an ArrayTrie to be built by a single thread and then used concurrently by multiple threads and not mutated during that access. If concurrent mutations of the Trie is required external locks need to be applied.

@param (V) the Entry type

class ArrayTernaryTrie : AbstractTrie!(V)(

) {

this();

this(bool insensitive);

this(int capacity);

this(bool insensitive, int capacity);

this(ArrayTernaryTrie!(V) trie, double factor);

void clear();

bool put(string s, V v);

V get(string s, int offset, int len);

V get(ByteBuffer b, int offset, int len);

V getBest(string s);

V getBest(string s, int offset, int length);

V getBest(ByteBuffer b, int offset, int len);

string toString();

Set!(string) keySet();

int size();

bool isEmpty();

bool isFull();

static int hilo(int diff);

void dump();

}

Constructors

this this(): Create a case insensitive Trie of default capacity.
this this(bool insensitive): Create a Trie of default capacity
this this(int capacity): Create a case insensitive Trie
this this(bool insensitive, int capacity): Create a Trie
this this(ArrayTernaryTrie!(V) trie, double factor): Copy Trie and change capacity by a factor

Members

Functions

clear void clear(): Undocumented in source. Be warned that the author may not have intended to support it.
dump void dump(): Undocumented in source. Be warned that the author may not have intended to support it.
get V get(string s, int offset, int len): Undocumented in source. Be warned that the author may not have intended to support it.
get V get(ByteBuffer b, int offset, int len): Undocumented in source. Be warned that the author may not have intended to support it.
getBest V getBest(string s): Undocumented in source. Be warned that the author may not have intended to support it.
getBest V getBest(string s, int offset, int length): Undocumented in source. Be warned that the author may not have intended to support it.
getBest V getBest(ByteBuffer b, int offset, int len): Undocumented in source. Be warned that the author may not have intended to support it.
isEmpty bool isEmpty(): Undocumented in source. Be warned that the author may not have intended to support it.
isFull bool isFull(): Undocumented in source. Be warned that the author may not have intended to support it.
keySet Set!(string) keySet(): Undocumented in source. Be warned that the author may not have intended to support it.
put bool put(string s, V v): Undocumented in source. Be warned that the author may not have intended to support it.
size int size(): Undocumented in source. Be warned that the author may not have intended to support it.
toString string toString(): Undocumented in source. Be warned that the author may not have intended to support it.

Static functions

hilo int hilo(int diff): Undocumented in source. Be warned that the author may not have intended to support it.

ArrayTernaryTrie

Constructors

Members

Functions

Static functions

Meta

Source