Manual

Purpose

The purpose of this library is to provide the Trie class which allows the user to map strings to values (of a generic type). The important feature of this data structure is that it allows the user to search for values based on prefixes of the strings (front part of the string). For example, you can get all the values that are associated with strings that start with "Ja".

Example

Here is an example of how to use the Trie class on the strings "John", "James", "Jack", and "Paul". Notice that the trie has a Matcher property which provides methods to match strings.

Trie<int> trie = new Trie<int> (); //Create a trie whose values are of type int
trie ["John"] = 1;
trie ["James"] = 2;
trie ["Jack"] = 3;
trie ["Paul"] = 4;

trie.Matcher.Next('J');
trie.Matcher.IsMatch(); //false
trie.Matcher.PrefixMatched; //"J"
trie.Matcher.Last; //'J'
trie.Matcher.PossibleNext(); //[ 'a', 'o' ]
trie.Matcher.StringValues(); //[ ("John", 1), ("James", 2), ("Jack", 3) ]

trie.Matcher.Next('a');
trie.Matcher.IsMatch(); //false
trie.Matcher.PrefixMatched; //"Ja"
trie.Matcher.Last; //'a'
trie.Matcher.PossibleNext(); //[ 'm', 'c' ]
trie.Matcher.StringValues(); //[ ("James", 2), ("Jack", 3) ]

trie.Matcher.Next("ck");
trie.Matcher.IsMatch(); //true
trie.Matcher.PrefixMatched; //"Jack"
trie.Matcher.Last; //'k'
trie.Matcher.PossibleNext(); //[ ]
trie.Matcher.StringValues(); //[ ("Jack", 3) ]
trie.Matcher.GetExactMatch(); //3

trie.Matcher.Back();
trie.Matcher.IsMatch(); //false
trie.Matcher.PrefixMatched; //"Jac"
trie.Matcher.Last; //'c'
trie.Matcher.PossibleNext(); //[ 'k' ]
trie.Matcher.StringValues(); //[ ("Jack", 3) ]

API

Trie

Method/Property	Description
Trie ()	Initializes a new empty instance of the Trie class.
void Add (string key, V value)	Add the specified key and associated value to the trie. If the key already exists in the trie, the value will be overwritten.
bool Remove (string key)	Remove the key and associated value from the trie. Resets the current prefix matched in Matcher.
void Clear ()	Clear all data from the trie.
bool ContainsKey (string key)	Determines whether the current instance contains an entry with the specified key.
bool Contains (KeyValuePair< string, V > item)	Determines whether the current collection contains a specific key value pair.
bool TryGetValue (string key, out V value)	Try to get the value associated with the specified key.
void Add (KeyValuePair< string, V > item)	Add the specified key value pair to the trie.
void CopyTo (KeyValuePair< string, V >[] array, int arrayIndex)	Copies the items of the trie to an array, starting at a particular array index.
bool Remove (KeyValuePair< string, V > item)	Remove the specified key value pair from the trie.
IEnumerator< KeyValuePair< string, V > > GetEnumerator ()	Returns an enumerator that iterates through the items of the trie.
void GetObjectData (SerializationInfo info, StreamingContext context)	Populates a SerializationInfo object with the data needed to serialize the trie.
override string ToString ()	Returns a string that represents the current trie.
int Count [get]	Gets the number of items in the trie.
IMatcher < V > Matcher [get]	Matcher object to search for strings by prefix.
V this[string key] [get, set]	Gets or sets the value associated with the specified key.
ICollection< string > Keys [get]	Get a collection of all the keys in the trie.
ICollection< V > Values [get]	Get a collection of all the values in the trie.
bool IsReadOnly [get]	Gets a value indicating whether the trie is read-only.

Matcher

Method/Property	Description
void Reset ()	Clear the currently entered prefix.
bool IsPrefixEmpty ()	Determines whether the prefix is an empty string.
void Back ()	Remove the last character of the currently entered prefix.
bool HasNext (char next)	Check if a particular character can be added to the current prefix such that the new prefix is an existing one.
IEnumerable< char > PossibleNext ()	Get all the next possible characters the can follow from the current prefix.
void Next (char next)	Add another character to the end of the prefix. Throws a KeyNotFoundException if new prefix is not a prefix to any string in the trie.
void Next (string next)	Add a string to the end of the prefix. Throws a KeyNotFoundException if new prefix is not a prefix to any string in the trie.
IEnumerable< V > Values ()	Get all the corresponding values of the keys which have a prefix corresponding to the currently entered prefix.
IEnumerable< string > Strings ()	Get the complete strings which have a prefix corresponding to the currently entered prefix.
IEnumerable< KeyValuePair< string, V > > StringValues ()	Get the strings which have a prefix corresponding to the currently entered prefix.
bool IsMatch ()	Check if the currently entered prefix is an existing string in the trie.
V GetExactMatch ()	Get the value mapped by the currently entered prefix.
string PrefixMatched [get]	Get the prefix matched thus far.
char Last [get]	Get the last character of the currently entered prefix.