[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, 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]