- GuidArrayTree.zip
- GuidArrayTree
- GuidArrayTree.sln
- GuidArrayTree.suo
- GuidArrayTree
- GuidArrayTree_UnitTests
- Local.testsettings
- TraceAndTestImpact.testsettings
- TrevyLibrary.vsmdi
|
// Author: Trevy
//
namespace TrevyCo.Tools
{
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Runtime.Serialization;
/// <summary>
/// A node for the Guid Array Tree.
/// Contains 16 child nodes to represent the 16 possible values of a hexidecimal number
/// </summary>
public class GuidArrayTree<TVal> : GuidTreeBase<TVal>
{
#region Data
private GuidArrayTree<TVal>[] arr = null;
private TVal theValue;
#endregion
#region Constructors
/// <summary>
/// A new node of type 'Array' is created
/// </summary>
public GuidArrayTree()
{
arr = new GuidArrayTree<TVal>[16];
}
/// <summary>
/// A new node of type 'Value' is created
/// </summary>
/// <param name="val"></param>
private GuidArrayTree(TVal val)
{
theValue = val;
count = 1;
}
#endregion
#region Public methods
/// <summary>
/// Add key, value pair to dictionary
/// </summary>
public override bool Add(Guid key, TVal val)
{
GuidArrayTree<TVal> currArr = this;
byte i = 0;
byte[] digits = GiudToByteArray(key);
for (; i < ValueIndex; i++)
{
byte digit = digits[i];
currArr = currArr.AddNode(digit);
}
if (currArr.GetNode(digits[ValueIndex]) == null)
{
// Number of values have increased
currArr.AddValue(digits[ValueIndex], val);
return true;
}
else if (OverwriteValues)
{
// Number of values are the same
currArr.AddValue(digits[ValueIndex], val);
return false;
}
else
{
throw new InvalidOperationException("Value already exists for Guid");
}
}
/// <summary>
/// Try to get the value
/// </summary>
/// <returns>True if vlue exists, false othervise</returns>
public override bool TryGetValue(Guid key, out TVal val)
{
GuidArrayTree<TVal> currArr = this;
byte i = 0;
byte[] digits = GiudToByteArray(key);
for (; i < digits.Length; i++)
{
byte digit = digits[i];
currArr = currArr.GetNode(digit);
if (currArr == null)
{
val = default(TVal);
return false;
}
}
val = currArr.theValue;
return true;
}
/// <summary>
/// Can be time-consuming
/// </summary>
public override void Clear()
{
arr = new GuidArrayTree<TVal>[16];
GC.Collect();
}
/// <summary>
/// Remove item corresponding to the key
/// </summary>
/// <returns>true if value removed</returns>
public override bool Remove(Guid key)
{
if (arr == null)
{
return false;
}
else
{
GuidArrayTree<TVal> currArr = this;
byte[] digits = GiudToByteArray(key);
return RecursiveRemove(currArr, digits, 0);
}
}
/// <summary>
/// Index into collection
/// </summary>
public override TreeType NodeType
{
get
{
if (arr != null)
{
return TreeType.Branch;
}
else if (theValue != null)
{
return TreeType.Leaf;
}
else
{
throw new Exception("Neither branch nor leaf");
}
}
}
/// <summary>
/// Check if key exists
/// </summary>
/// <returns>true if key exists, false otherwise</returns>
public override bool ContainsKey(Guid key)
{
TVal val;
return TryGetValue(key, out val);
}
/// <summary>
/// Gets the enummerator
/// </summary>
/// <returns>Enumerator</returns>
public override IEnumerable<TVal> GetEnumerator()
{
foreach (TVal theValue in GetTheEnumerator(arr))
{
yield return theValue;
}
}
#endregion
#region Private methods
private void AddValue(byte index, TVal theValue)
{
if (arr[index] == null)
{
count++;
}
arr[index] = new GuidArrayTree<TVal>(theValue);
}
private GuidArrayTree<TVal> AddNode(byte index)
{
if (arr == null) throw new InvalidOperationException("GuidArrayNode of type Leaf doesn't have child elements");
if (arr[index] == null)
{
arr[index] = new GuidArrayTree<TVal>();
count++;
}
return arr[index];
}
private GuidArrayTree<TVal> GetNode(byte index)
{
if (arr == null) throw new InvalidOperationException("GuidArrayNode of type Leaf doesn't have child elements");
return arr[index];
}
private bool RecursiveRemove(GuidArrayTree<TVal> theArray, byte[] digits, int index)
{
if (theArray.Count == 0)
{
// Nothing to delete
return false;
}
else
{
byte nodeIndex = digits[index];
GuidArrayTree<TVal> child = theArray.GetNode(nodeIndex);
if (index < ValueIndex)
{
bool res = RecursiveRemove(child, digits, ++index);
if (child.Count == 0)
{
// Delete child if it has no children
theArray.DeleteNode(nodeIndex);
}
return res;
}
else
{
theArray.DeleteNode(nodeIndex);
return true;
}
}
}
private void DeleteNode(byte index)
{
if (arr[index] != null)
{
arr[index] = null;
count--;
}
}
private IEnumerable<TVal> GetTheEnumerator(GuidArrayTree<TVal>[] treeAttay)
{
foreach (GuidArrayTree<TVal> tree in treeAttay)
{
if (tree == null)
{
continue;
}
else if (tree.NodeType == TreeType.Leaf)
{
yield return tree.theValue;
}
else
{
foreach (TVal theValue in GetTheEnumerator(tree.arr))
{
yield return theValue;
}
}
}
}
#endregion
}
}
|
By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.
If a file you wish to view isn't highlighted, and is a text file (not binary), please
let us know and we'll add colourisation support for it.
I’ve been a software developer for the last 11 years.
My language of choice is C#.
My strength lies in windows based programming as an SDET.
Strengths include:
• Object Oriented Programming
• Design Patterns
• Data Structures, Algorithms
• Windows Automation
Principle technologies include:
• Visual Studios 2010 (Ultimate, TFS, Test Manager)
• C# 4.0, XML, WPF, SQL Server
Education includes:
• BSEE - Concordia University, Quebec, Canada
• Programmer Analyst Certificate - John Abbott College, Qc, Canada
• Certified Scrum Master Training - Danube, Bellevue, WA
• Windows Azure Training - Wintellect, Bellevue, WA
Certification:
• Microsoft Certified Solution Developer for the MS.NET Platform