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;
    using System.IO;
    using System.Xml.Serialization;

    /// <summary>
    /// 
    /// </summary>
    public class GuidFileTree<TVal> : GuidTreeBase<TVal>
    {
        #region Data
        private readonly string fileValueName = "Value.xml";
        private readonly string TempGuidLocation = "GuidTreeLoc";
        String dir;
        #endregion

        #region Constructors
        /// <summary>
        /// A new node of type 'Array' is created
        /// </summary>
        public GuidFileTree(String dir)
        {
            this.dir = dir + Path.DirectorySeparatorChar + TempGuidLocation;
            Directory.CreateDirectory(this.dir);
        }

        /// <summary>
        /// A new node of type 'Value' is created
        /// </summary>
        /// <param name="val"></param>
        private GuidFileTree(String dir, TVal val)
        {
            this.dir = dir;
            File.WriteAllText(dir + Path.DirectorySeparatorChar + "Value", val.ToString());
        }
        #endregion

        /// <summary>
        /// Add key, value pair to dictionary
        /// </summary>
        public override bool Add(Guid key, TVal val)
        {
            bool newValueAdded = false;
            string currDir = dir;

            byte[] digits = GiudToByteArray(key);
            string child = dir;
            foreach (byte digit in GiudToByteArray(key))
            {
                child = child + Path.DirectorySeparatorChar + digit.ToString();
            }

            if (!Directory.Exists(child))
            {
                Directory.CreateDirectory(child);
            }

            string valuePath = child + Path.DirectorySeparatorChar + fileValueName;
            if (File.Exists(valuePath))
            {
                if (OverwriteValues == false)
                {
                    throw new InvalidOperationException("value already exists for Guid");
                }
                else
                {
                    File.Delete(valuePath);
                }
            }
            else
            {
                // New value added
                newValueAdded = true;
            }

            // Serialize object to file
            using (StreamWriter myWriter = new StreamWriter(valuePath))
            {
                XmlSerializer mySerializer = new XmlSerializer(typeof(TVal));
                mySerializer.Serialize(myWriter, val);
            }

            return newValueAdded;
        }

        /// <summary>
        /// Try to get the value
        /// </summary>
        /// <returns>True if vlue exists, false othervise</returns>
        public override bool TryGetValue(Guid key, out TVal val)
        {
            val = default(TVal);
            string currDir = dir;

            byte[] digits = GiudToByteArray(key);
            string child = dir;
            foreach (byte digit in GiudToByteArray(key))
            {
                child = child + Path.DirectorySeparatorChar + digit;
                if (!Directory.Exists(child))
                {
                    return false;
                }
            }

            string valuePath = child + Path.DirectorySeparatorChar + fileValueName;
            if (!File.Exists(valuePath))
            {
                return false;
            }

            // Get object
            using (FileStream myFileStream = new FileStream(valuePath, FileMode.Open))
            {
                // return value
                XmlSerializer mySerializer = new XmlSerializer(typeof(TVal));
                val = (TVal)mySerializer.Deserialize(myFileStream);
            }

            return true;
        }

        /// <summary>
        /// A time-consuming process
        /// </summary>
        public override void Clear()
        {
            Directory.Delete(dir, true);
            Directory.CreateDirectory(dir);
            base.count = 0;
        }

        /// <summary>
        /// Remove item corresponding to the key
        /// </summary>
        /// <returns>true if value removed</returns>
        public override bool Remove(Guid key)
        {
            byte[] digits = GiudToByteArray(key);
            return RecursiveRemove(dir, digits, 0);
        }

        /// <summary>
        /// Index into collection
        /// </summary>
        public override TreeType NodeType
        {
            get
            {
                if (Directory.Exists(dir))
                {
                    return TreeType.Branch;
                }
                else
                {
                    return TreeType.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(dir))
            {
                yield return theValue;
            }
        }

        #region Private methods
        private IEnumerable<TVal> GetTheEnumerator(string baseDir)
        {
            foreach (string childDir in Directory.EnumerateDirectories(baseDir))
            {
                string valuePath = childDir + Path.DirectorySeparatorChar + fileValueName;
                if (File.Exists(valuePath))
                {
                    FileStream myFileStream = new FileStream(valuePath, FileMode.Open);
                    XmlSerializer mySerializer = new XmlSerializer(typeof(TVal));
                    yield return (TVal)mySerializer.Deserialize(myFileStream);
                }
                else
                {
                    foreach (TVal theValue in GetTheEnumerator(childDir))
                    {
                        yield return theValue;
                    }
                }
            }
        }


        private bool RecursiveRemove(string dir, byte[] digits, int index)
        {
            byte nodeIndex = digits[index];
            String currDir = dir + Path.DirectorySeparatorChar + nodeIndex;

            if (index < ValueIndex)
            {
                bool res = RecursiveRemove(currDir, digits, ++index);

                if (Directory.GetDirectories(currDir).Length == 0)
                {
                    Directory.Delete(currDir);
                }

                return res;
            }
            else
            {
                string valuePath = currDir + Path.DirectorySeparatorChar + fileValueName;
                if (!File.Exists(valuePath))
                {
                    return false;
                }
                else
                {
                    File.Delete(valuePath);
                    return true;
                }
            }
        }
        #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 | Mobile
Web04 | 2.8.141022.1 | Last Updated 14 Feb 2013
Article Copyright 2013 by TrevyBurgess
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid