Click here to Skip to main content
11,709,393 members (49,746 online)
Click here to Skip to main content
Add your own
alternative version

Tagged as

GUID Tree Data Structure

, 14 Feb 2013 CPOL 4.4K 93 4
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;

    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)

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

You may also be interested in...

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