Click here to Skip to main content
Click here to Skip to main content
Add your own
alternative version

Tagged as

GUID Tree Data Structure

, 14 Feb 2013 CPOL
Data structure designed to store billions of items using GUID as a key.
GuidArrayTree.zip
GuidArrayTree
GuidArrayTree.suo
GuidArrayTree
Properties
GuidArrayTree_UnitTests
Properties
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.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

TrevyBurgess
Software Developer
United States United States
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
Follow on   Twitter

| Advertise | Privacy | Terms of Use | Mobile
Web02 | 2.8.141223.1 | Last Updated 14 Feb 2013
Article Copyright 2013 by TrevyBurgess
Everything else Copyright © CodeProject, 1999-2014
Layout: fixed | fluid