Click here to Skip to main content
15,896,118 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.4K   176   4  
Data structure designed to store billions of items using GUID as a key.
// Author: Trevy
//
namespace TrevyCo.Tools.UnitTests
{
    using Microsoft.VisualStudio.TestTools.UnitTesting;
    using System;
    using System.Collections.Generic;
    using System.IO;

    /// <summary>
    ///This is a test class for GuidCollectionTest and is intended
    ///to contain all GuidCollectionTest Unit Tests
    ///</summary>
    [TestClass()]
    public class GuidCollectionTest
    {
        /// <summary>
        ///Gets or sets the test context which provides
        ///information about and functionality for the current test run.
        ///</summary>
        public TestContext TestContext
        {
            get
            {
                return testContextInstance;
            }
            set
            {
                testContextInstance = value;
            }
        }
        private TestContext testContextInstance;

        private static string guidBaseLocation = "C:\\Guid_Test_Loc";
        private static GuidCollection<int> guidArrayTree;
        private static GuidCollection<Guid> guidFileTree;
        private static List<Guid> initialGuidList;

        #region Additional test attributes
        [ClassInitialize()]
        public static void MyClassInitialize(TestContext testContext)
        {
            if (!Directory.Exists(guidBaseLocation))
            {
                Directory.CreateDirectory(guidBaseLocation);
            }

            PopulateTrees();
        }

        public static void PopulateTrees()
        {
            // In memory Guid collection
            if (guidArrayTree == null || guidArrayTree.Count == 0)
            {
                initialGuidList = new List<Guid>(1100);

                guidArrayTree = new GuidCollection<int>();
                for (int i = 0; i < 1000; i++)
                {
                    Guid newGuid = Guid.NewGuid();
                    initialGuidList.Add(newGuid);
                    guidArrayTree.Add(newGuid, i);
                }
            }

            // File system Guid collection
            if (guidFileTree == null || guidFileTree.Count == 0)
            {
                guidFileTree = new GuidCollection<Guid>(guidBaseLocation);
                foreach (Guid guid in initialGuidList)
                {
                    guidFileTree.Add(guid, guid);
                }
            }
        }

        [ClassCleanup()]
        public static void MyClassCleanup()
        {
            // Get rid of unnecessry files
            Directory.Delete(guidBaseLocation, true);
        }

        //[TestInitialize()]
        //public void MyTestInitialize()
        //{
        //}
        //
        //[TestCleanup()]
        //public void MyTestCleanup()
        //{
        //}
        #endregion

        [TestMethod()]
        [TestCategory("MemoryBased")]
        [TestCategory("KeyDoesNotExist")]
        [Description("Add value")]
        public void Memory_Add_Test()
        {
            long expectedVal = guidArrayTree.Count + 1;
            Guid newGuid = Guid.NewGuid();

            // Test:
            guidArrayTree.Add(newGuid, 5);

            // Verify results
            Assert.AreEqual<long>(expectedVal, guidArrayTree.Count);
        }

        [TestMethod()]
        [TestCategory("FileBased")]
        [TestCategory("KeyDoesNotExist")]
        [Description("Add value")]
        public void File_Add_Test()
        {
            long expectedVal = guidArrayTree.Count + 1;
            Guid newGuid = Guid.NewGuid();

            // Test:
            guidFileTree.Add(newGuid, newGuid);

            // Verify results
            Assert.AreEqual<long>(expectedVal, guidFileTree.Count);
        }

        [TestMethod()]
        [TestCategory("MemoryBased")]
        [TestCategory("KeyExists")]
        [Description("Test OverwriteValues")]
        public void Memory_OverwriteValues_True_Test()
        {
            // Add Guid to be removed later
            Guid newGuid = Guid.NewGuid();
            guidArrayTree.Add(newGuid, 5);

            guidArrayTree.OverwriteValues = true;

            // Test:
            int newValue = 10;
            guidArrayTree.Add(newGuid, newValue);

            // Retrive value
            int retrivedValue;
            guidArrayTree.TryGetValue(newGuid, out retrivedValue);

            // Verify results
            Assert.AreEqual<long>(newValue, retrivedValue);
        }

        [TestMethod()]
        [TestCategory("FileBased")]
        [TestCategory("KeyExists")]
        [Description("Test OverwriteValues")]
        public void File_OverwriteValues_True_Test()
        {
            // Add Guid to be removed later
            Guid newGuid = Guid.NewGuid();
            guidFileTree.Add(newGuid, newGuid);

            guidFileTree.OverwriteValues = true;

            // Test:
            Guid guid2 = Guid.NewGuid();
            guidFileTree.Add(newGuid, guid2);

            // Retrive value
            Guid retrivedValue;
            guidFileTree.TryGetValue(newGuid, out retrivedValue);

            // Verify results
            Assert.AreEqual<Guid>(guid2, retrivedValue);
        }

        [TestMethod()]
        [TestCategory("MemoryBased")]
        [TestCategory("KeyExists")]
        [Description("Test OverwriteValues")]
        [ExpectedException(typeof(InvalidOperationException))]
        public void Memory_OverwriteValues_False_Test()
        {
            // Add Guid to be removed later
            Guid newGuid = Guid.NewGuid();
            guidArrayTree.Add(newGuid, 5);

            guidArrayTree.OverwriteValues = false;

            // Test:
            guidArrayTree.Add(newGuid, 10);
        }

        [TestMethod()]
        [TestCategory("FileBased")]
        [TestCategory("KeyExists")]
        [Description("Test OverwriteValues")]
        [ExpectedException(typeof(InvalidOperationException))]
        public void File_OverwriteValues_False_Test()
        {
            // Add Guid to be removed later
            Guid newGuid = Guid.NewGuid();
            guidArrayTree.Add(newGuid, 5);

            guidArrayTree.OverwriteValues = false;

            // Test:
            guidArrayTree.Add(newGuid, 10);
        }

        [TestMethod()]
        [TestCategory("MemoryBased")]
        [TestCategory("KeyExists")]
        [Description("Check if key exists")]
        public void Memory_ContainsKey_HadValue_Test()
        {
            Guid newGuid = Guid.NewGuid();
            guidArrayTree.Add(newGuid, 5);

            // Test:
            bool res = guidArrayTree.ContainsKey(newGuid);

            Assert.IsTrue(res);
        }

        [TestMethod()]
        [TestCategory("FileBased")]
        [TestCategory("KeyExists")]
        [Description("Check if key exists")]
        public void File_ContainsKey_HasValue_Test()
        {
            Guid newGuid = Guid.NewGuid();
            guidFileTree.Add(newGuid, newGuid);

            // Test:
            bool res = guidFileTree.ContainsKey(newGuid);

            Assert.IsTrue(res);
        }

        [TestMethod()]
        [TestCategory("MemoryBased")]
        [TestCategory("KeyDoesNotExist")]
        [Description("Check if key exists")]
        public void Memory_ContainsKey_HasNoKey_Test()
        {
            Guid newGuid = Guid.NewGuid();

            // Test:
            bool res = guidArrayTree.ContainsKey(newGuid);

            Assert.IsFalse(res);
        }

        [TestMethod()]
        [TestCategory("FileBased")]
        [TestCategory("KeyDoesNotExist")]
        [Description("Check if key exists")]
        public void File_ContainsKey_HasNoKey_Test()
        {
            Guid newGuid = Guid.NewGuid();

            // Test:
            bool res = guidFileTree.ContainsKey(newGuid);

            Assert.IsFalse(res);
        }

        [TestMethod()]
        [TestCategory("MemoryBased")]
        [TestCategory("KeyExists")]
        [Description("Remove value where key exists")]
        public void Memory_Remove_HasKey_Test()
        {
            Guid newGuid = Guid.NewGuid();
            guidArrayTree.Add(newGuid, 5);

            // Test:
            guidArrayTree.Remove(newGuid);

            Assert.IsFalse(guidArrayTree.ContainsKey(newGuid));
        }

        [TestMethod()]
        [TestCategory("FileBased")]
        [TestCategory("KeyExists")]
        [Description("Remove value where key exists")]
        public void File_Remove_HasKey_Test()
        {
            Guid newGuid = Guid.NewGuid();
            guidFileTree.Add(newGuid, newGuid);

            // Test:
            guidFileTree.Remove(newGuid);

            Assert.IsFalse(guidFileTree.ContainsKey(newGuid));
        }
        
        [TestMethod()]
        [TestCategory("MemoryBased")]
        [TestCategory("KeyDoesNotExist")]
        [Description("Remove value")]
        public void Memory_Remove_HasNoKey_Test()
        {
            Guid newGuid = Guid.NewGuid();
            guidArrayTree.Add(newGuid, 5);

            // Test:
            guidArrayTree.Remove(newGuid);

            Assert.IsFalse(guidArrayTree.ContainsKey(newGuid));
        }

        [TestMethod()]
        [TestCategory("FileBased")]
        [TestCategory("KeyDoesNotExist")]
        [Description("Remove value where key exists")]
        public void File_Remove_HasNoKey_Test()
        {
            Guid newGuid = Guid.NewGuid();
            guidFileTree.Add(newGuid, newGuid);

            // Test:
            guidFileTree.Remove(newGuid);

            Assert.IsFalse(guidFileTree.ContainsKey(newGuid));
        }

        [TestMethod()]
        [TestCategory("MemoryBased")]
        [TestCategory("KeyExists")]
        [Description("Retrive value")]
        public void Memory_TryGetValue_HasKey_Test()
        {
            Guid newGuid = Guid.NewGuid();
            int newVal = 5;
            guidArrayTree.Add(newGuid, newVal);

            // Test:
            int retrivedValue;
            guidArrayTree.TryGetValue(newGuid, out retrivedValue);

            Assert.AreEqual<int>(newVal, retrivedValue);
        }

        [TestMethod()]
        [TestCategory("FileBased")]
        [TestCategory("KeyExists")]
        [Description("Retrive value")]
        public void File_TryGetValue_HasKey_Test()
        {
            Guid newGuid = Guid.NewGuid();
            guidFileTree.Add(newGuid, newGuid);

            //Test:
            Guid retrivedValue;
            guidFileTree.TryGetValue(newGuid, out retrivedValue);

            Assert.AreEqual<Guid>(newGuid, retrivedValue);
        }

        [TestMethod()]
        [TestCategory("MemoryBased")]
        [TestCategory("KeyDoesNotExist")]
        [Description("Retrive value")]
        public void Memory_TryGetValue_HasNoKey__Test()
        {
            Guid newGuid = Guid.NewGuid();

            // Test:
            int retrivedValue;
            bool res = guidArrayTree.TryGetValue(newGuid, out retrivedValue);

            Assert.IsFalse(res);
        }

        [TestMethod()]
        [TestCategory("FileBased")]
        [TestCategory("KeyDoesNotExist")]
        [Description("Retrive value")]
        public void File_TryGetValue_HasNoKey_Test()
        {
            Guid newGuid = Guid.NewGuid();

            // Test:
            Guid retrivedValue;
            bool res = guidFileTree.TryGetValue(newGuid, out retrivedValue);

            Assert.IsFalse(res);
        }
        
        [TestMethod()]
        [TestCategory("MemoryBased")]
        [TestCategory("KeyExists")]
        [Description("test indexer")]
        public void Memory_Item_HasKey_Test()
        {
            // Add new value
            Guid newGuid = Guid.NewGuid();
            int expectedValue = 5;
            guidArrayTree[newGuid] = expectedValue;

            // Retrive value
            int returnedValue = guidArrayTree[newGuid];

            bool res = guidArrayTree.ContainsKey(newGuid);
            Assert.IsTrue(res);
            Assert.AreEqual<int>(expectedValue, returnedValue);
        }

        [TestMethod()]
        [TestCategory("FileBased")]
        [TestCategory("KeyExists")]
        [Description("test indexer")]
        public void File_Item_HasKey_Test()
        {
            // Add new value
            Guid newGuid = Guid.NewGuid();
            guidFileTree[newGuid] = newGuid;

            // Retrive value
            Guid returnedValue = guidFileTree[newGuid];
            bool res = guidFileTree.ContainsKey(newGuid);
            
            Assert.IsTrue(res);
            Assert.AreEqual<Guid>(newGuid, returnedValue);
        }
        
        [TestMethod()]
        [TestCategory("MemoryBased")]
        [TestCategory("KeyDoesNotExist")]
        [Description("test indexer")]
        [ExpectedException(typeof(InvalidOperationException))]
        public void Memory_Item_HasNoKey_Test()
        {
            // Add new value
            Guid newGuid = Guid.NewGuid();

            // Test:
            int returnedValue = guidArrayTree[newGuid];

            Assert.IsTrue(guidArrayTree.ContainsKey(newGuid));
            Assert.AreEqual<int>(5, returnedValue);
        }

        [TestMethod()]
        [TestCategory("FileBased")]
        [TestCategory("KeyDoesNotExist")]
        [Description("test indexer")]
        [ExpectedException(typeof(InvalidOperationException))]
        public void File_Item_HasNoKey_Test()
        {
            // Add new value
            Guid newGuid = Guid.NewGuid();

            // Test:
            Guid returnedValue = guidFileTree[newGuid];
        }

        // ==================================

        [TestMethod()]
        [TestCategory("MemoryBased")]
        [Description("Get number of values")]
        public void Memory_Count_Test()
        {
            long expectedVal = guidArrayTree.Count + 1;

            // Add Guid to be removed later
            Guid newGuid = Guid.NewGuid();
            guidArrayTree.Add(newGuid, 5);

            // Verify results
            Assert.AreEqual<long>(expectedVal, guidArrayTree.Count);
        }

        [TestMethod()]
        [TestCategory("FileBased")]
        [Description("Get number of values")]
        public void File_Count_Test()
        {
            long expectedVal = guidFileTree.Count + 1;

            // Add Guid to be removed later
            Guid newGuid = Guid.NewGuid();
            guidFileTree.Add(newGuid, newGuid);

            // Verify results
            Assert.AreEqual<long>(expectedVal, guidFileTree.Count);
        }

        [TestMethod()]
        [TestCategory("MemoryBased")]
        [Description("Clear all values")]
        public void Memory_Clear_Test()
        {
            PopulateTrees();

            // Test:
            guidArrayTree.Clear();
            Assert.AreEqual<long>(0, guidArrayTree.Count);

            // For other tests
            PopulateTrees();
        }

        [TestMethod()]
        [TestCategory("FileBased")]
        [Description("Clear all values")]
        public void File_Clear_Test()
        {
            PopulateTrees();

            // Test:
            guidFileTree.Clear();
            Assert.AreEqual<long>(0, guidFileTree.Count);

            // For other tests
            PopulateTrees();
        }
        
        [TestMethod()]
        [TestCategory("MemoryBased")]
        [Description("Get the enumerator")]
        public void Memory_GetEnumerator_Test()
        {
            List<int> intList = new List<int>(1100);

            // Test:
            foreach (int intVal in guidArrayTree.GetEnumerator())
            {
                intList.Add(intVal);
            }

            Assert.AreEqual<long>(intList.Count, guidFileTree.Count);
        }

        [TestMethod()]
        [TestCategory("FileBased")]
        [Description("Get the enumerator")]
        public void File_GetEnumerator_Test()
        {
            List<Guid> guidList = new List<Guid>(1100);

            // Test:
            foreach (Guid guid in guidFileTree.GetEnumerator())
            {
                guidList.Add(guid);
            }

            Assert.AreEqual<long>(guidList.Count, guidFileTree.Count);
        }
    }
}

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