AceInfinity
Emeritus, Contributor
So I needed some implementation that would allow me to lookup string values and branch results off based on what I was looking for. Typically this is the appropriate job for what is called a Trie or otherwise a Prefix Tree. You may look up "A" then "AB" then "ABC" and with each additional character typed out, you would traverse a treelike structure that would provide you with the remainder of characters associated with all the possible strings contained in the structure.
I ended up writing my own implementation, and as long as an object has a named value as a contract, this can be applied to more than just strings but larger pieces of data as well. This was the implementation that I'm currently using within my debugger that I'm actually writing for a side-project for work, where I may have up to 1,000,000 named objects stored in memory, and I need to associate to them very quickly.
Implementation that each internal contained type must implement in order to use it as a node within the datastructure:
You'll notice that my node class implements IEnumerable<T> so you can easily use it within a foreach loop construct for looping over your results.
And lastly the tree datastructure itself with some constraints that force the contract of what types you can use with it:
The usage is rather easy, it's all self-contained for common functionality like foreach looping, among extracting and adding objects to the tree. Hope somebody else finds this useful too!
I ended up writing my own implementation, and as long as an object has a named value as a contract, this can be applied to more than just strings but larger pieces of data as well. This was the implementation that I'm currently using within my debugger that I'm actually writing for a side-project for work, where I may have up to 1,000,000 named objects stored in memory, and I need to associate to them very quickly.
Implementation that each internal contained type must implement in order to use it as a node within the datastructure:
Code:
[NO-PARSE]/// <summary>
/// Interface for all objects that have associated names.
/// </summary>
public interface INamedObject
{
/// <summary>
/// Name associated with the object
/// </summary>
string Name { get; }
}[/NO-PARSE]You'll notice that my node class implements IEnumerable<T> so you can easily use it within a foreach loop construct for looping over your results.
Code:
[NO-PARSE]/// <summary>
/// Represents a generic node class for a single node in a trie.
/// </summary>
/// <typeparam name="T"></typeparam>
/// <summary>
/// Represents a generic node class for a single node in a trie.
/// </summary>
/// <typeparam name="T">Internal contained type.</typeparam>
[DebuggerDisplay("{" + nameof(DebuggerDisplay) + ",nq}")]
internal class SignalTreeNode<T> : IEnumerable<T>
{
public char Index { get; }
public T Value { get; }
public int Depth { get; }
public SignalTreeNode<T> Parent { get; }
public List<SignalTreeNode<T>> Children { get; }
public bool IsLeaf => Children.Count == 0;
/// <summary>
/// Constructs a new tree node.
/// </summary>
/// <param name="value">Node object</param>
/// <param name="index">Character index</param>
/// <param name="depth">Node depth</param>
/// <param name="parent">Parent node reference</param>
public SignalTreeNode(T value, char index, int depth, SignalTreeNode<T> parent)
{
Index = index;
Value = value;
Depth = depth;
Parent = parent;
Children = new List<SignalTreeNode<T>>();
}
/// <summary>
/// Find a child node with the specified index.
/// </summary>
/// <param name="index">Index character</param>
/// <returns>A trie node child found by the specified index, otherwise null.</returns>
public SignalTreeNode<T> FindChildNode(char index)
{
foreach (var child in Children)
if (child.Index == index)
return child;
return null;
}
/// <summary>
/// Delete a child node with the specified index.
/// </summary>
/// <param name="index">Index character</param>
public void DeleteChildNode(char index)
{
for (var i = 0; i < Children.Count; ++i)
if (Children[i].Index == index)
Children.RemoveAt(i);
}
/// <summary>
/// Returns all children node values recursively from the current parent node.
/// </summary>
/// <param name="parent">Parent node</param>
/// <returns>IEnumerable<T/> of each child node's value</returns>
public IEnumerable<T> GetChildren(SignalTreeNode<T> parent)
{
foreach (var child in parent.Children)
{
if (child.IsLeaf)
{
yield return child.Value;
continue;
}
foreach (var innerChild in GetChildren(child))
yield return innerChild;
}
}
public IEnumerator<T> GetEnumerator() => GetChildren(this).GetEnumerator();
IEnumerator IEnumerable.GetEnumerator() { yield return GetChildren(this); }
private string DebuggerDisplay => $"Index = {Index}, Value = {Value}";
}
[/NO-PARSE]And lastly the tree datastructure itself with some constraints that force the contract of what types you can use with it:
Code:
[NO-PARSE]/// <summary>
/// Represents the tree which deals with the collection of trie nodes.
/// </summary>
/// <typeparam name="T">Node object type.</typeparam>
internal class SignalTree<T>
where T : class, INamedObject
{
private SignalTreeNode<T> _rootNode;
private const char EndDataMarker = '\xFF';
/// <summary>
/// Constructs a new prefix tree with all items cleared.
/// </summary>
public SignalTree()
{
Clear();
}
/// <summary>
/// Looks for a prefix noce within the tree.
/// </summary>
/// <param name="prefix">Prefix to search for.</param>
/// <returns>Trie node result</returns>
public SignalTreeNode<T> LookupPrefixNode(string prefix)
{
var currentNode = _rootNode;
var result = currentNode;
foreach (var ch in prefix)
{
currentNode = currentNode.FindChildNode(ch);
if (currentNode == null) { break; }
result = currentNode;
}
return result;
}
/// <summary>
/// Looks for the node object that matches exactly.
/// </summary>
/// <param name="prefix">Prefix to search for.</param>
/// <param name="result">Node object result</param>
/// <returns>True if a match was found, otherwise false.</returns>
public bool TrySearch(string prefix, out T result)
{
result = null;
SignalTreeNode<T> node = LookupPrefixNode(prefix);
if (node.Depth == prefix.Length && (node = node.FindChildNode(EndDataMarker)) != null)
{
result = node.Value;
return true;
}
return false;
}
/// <summary>
/// Inserts a range of node objects into the tree.
/// </summary>
/// <param name="items">Enumerable of node object items.</param>
public void InsertRange(IEnumerable<T> items)
{
foreach (var item in items) { Insert(item); }
}
/// <summary>
/// Inserts a single node object into the tree.
/// </summary>
/// <param name="obj">Node object</param>
public void Insert(T obj)
{
var current = LookupPrefixNode(obj.Name);
for (var i = current.Depth; i < obj.Name.Length; ++i)
{
var newNode = new SignalTreeNode<T>(obj, obj.Name[i], current.Depth + 1, current);
current.Children.Add(newNode);
current = newNode;
}
current.Children.Add(new SignalTreeNode<T>(obj, EndDataMarker, current.Depth + 1, current));
}
/// <summary>
/// Deletes an object from the prefix tree by prefix.
/// </summary>
/// <param name="prefix"></param>
public void Delete(string prefix)
{
if (TrySearch(prefix, out T _))
{
var node = LookupPrefixNode(prefix).FindChildNode(EndDataMarker);
while (node.IsLeaf)
{
var parent = node.Parent;
parent.DeleteChildNode(node.Index);
node = parent;
}
}
}
/// <summary>
/// Clears the prefix tree.
/// </summary>
public void Clear()
{
_rootNode = new SignalTreeNode<T>(null, '\0', 0, null);
}
}[/NO-PARSE]The usage is rather easy, it's all self-contained for common functionality like foreach looping, among extracting and adding objects to the tree. Hope somebody else finds this useful too!
