Click here to Skip to main content
15,867,835 members
Articles / Programming Languages / C#

GUID Tree Data Structure

Rate me:
Please Sign up or sign in to vote.
5.00/5 (4 votes)
14 Feb 2013CPOL2 min read 13.2K   176   4  
Data structure designed to store billions of items using GUID as a key.
// Author: Trevy
//
namespace TrevyCo.Tools
{
    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;

    public abstract class GuidTreeBase<TVal>
    {
        #region Data
        /// <summary>
        /// Number of hexadecimal digits in the Guid
        /// </summary>
        protected readonly byte NumOfDigits = 32;

        /// <summary>
        /// Index of the value being stored
        /// </summary>
        protected readonly byte ValueIndex = 31;

        /// <summary>
        /// Set weather we can overwrite existing values
        /// </summary>
        public bool OverwriteValues
        {
            get
            {
                return overwriteValues;
            }
            set
            {
                overwriteValues = value;
            }
        }
        private bool overwriteValues = false;

        protected byte count = 0;

        /// <summary>
        /// Define the type of node this is.
        /// </summary>
        public enum TreeType
        {
            /// <summary>
            /// 
            /// </summary>
            Branch,

            /// <summary>
            /// 
            /// </summary>
            Leaf
        }
        #endregion
        
        #region Public methods
        /// <summary>
        /// Add key, value pair to dictionary
        /// </summary>
        public abstract bool Add(Guid key, TVal val);

        /// <summary>
        /// Try to get the value
        /// </summary>
        /// <returns>True if vlue exists, false othervise</returns>
        public abstract bool TryGetValue(Guid key, out TVal val);

        /// <summary>
        /// Can be time-consuming
        /// </summary>
        public abstract void Clear();

        /// <summary>
        /// Remove item corresponding to the key
        /// </summary>
        /// <returns>true if value removed</returns>
        public abstract bool Remove(Guid key);

        /// <summary>
        /// Index into collection
        /// </summary>
        public abstract TreeType NodeType { get; }

        /// <summary>
        /// Check if key exists
        /// </summary>
        /// <returns>true if key exists, false otherwise</returns>
        public abstract bool ContainsKey(Guid key);

        /// <summary>
        /// Gets the enummerator
        /// </summary>
        /// <returns>Enumerator</returns>
        public abstract IEnumerable<TVal> GetEnumerator();

        /// <summary>
        /// Return number of child items in this node
        /// </summary>
        public byte Count
        {
            get
            {
                return count;
            }
        }
        #endregion

        #region Protected methods

        /// <summary>
        /// Parse the Guid into its 32 hexadecimal digits
        /// </summary>
        protected byte[] GiudToByteArray(Guid key)
        {
            byte[] arr = new byte[NumOfDigits];

            byte[] keyArr = key.ToByteArray();
            for (int i = 0; i < 16; i++)
            {
                // Get left 4 bits
                arr[i * 2] = (byte)(keyArr[i] >> 4);

                // Get right 4 digits
                arr[i * 2 + 1] = (byte)(keyArr[i] << 4);
                arr[i * 2 + 1] = (byte)(arr[i * 2 + 1] >> 4);
            }

            return arr;
        } 
        #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)


Written By
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

Comments and Discussions