hashtests.cs

C#写的类似于STL的集合类,首先是C#编写,可以用于.net变程.

//******************************
// Written by Peter Golde
// Copyright (c) 2004-2005, Wintellect
//
// Use and restribution of this code is subject to the license agreement 
// contained in the file "License.txt" accompanying this file.
//******************************

using System;
using System.Collections.Generic;
using NUnit.Framework;

namespace Wintellect.PowerCollections.Tests
{
    // A class for testing the "Hash" class.
    [TestFixture]
    public class HashTests
    {
        internal Hash<TestItem> hash;

        internal class DataComparer : System.Collections.Generic.IEqualityComparer<TestItem>
        {
            public bool Equals(TestItem x, TestItem y)
            {
                return string.Equals(x.key, y.key);
            }

            public int GetHashCode(TestItem obj)
            {
                return obj.key.GetHashCode();
            }
        }

        /// <summary>
        /// Insert a key and print/validate the hash.
        /// </summary>
        /// <param name="key"></param>
        private void InsertPrintValidate(string key)
        {
            InsertPrintValidate(key, 0, true);
        }

        private void InsertPrintValidate(string key, int data)
        {
            InsertPrintValidate(key, data, true);
        }

        private void InsertPrintValidate(string key, int data, bool replaceOnDuplicate)
        {
            TestItem oldData;
            hash.Insert(new TestItem(key, data), replaceOnDuplicate, out oldData);
#if DEBUG
            hash.Print();
            hash.Validate();
#endif //DEBUG
        }

        private void InsertPrintValidate(string key, int data, bool replaceOnDuplicate, int expectedoldData)
        {
            TestItem oldData;
            hash.Insert(new TestItem(key, data), replaceOnDuplicate, out oldData);
#if DEBUG
            hash.Print();
            hash.Validate();
#endif //DEBUG
            Assert.AreEqual(expectedoldData, oldData.data);
        }

        /// <summary>
        /// Insert a key and validate the hash.
        /// </summary>
        /// <param name="key"></param>
        private void InsertValidate(string key)
        {
            InsertValidate(key, 0, true);
        }

        private void InsertValidate(string key, int data)
        {
            InsertValidate(key, data, true);
        }

        private void InsertValidate(string key, int data, bool replaceOnDuplicate)
        {
            TestItem oldData;
            hash.Insert(new TestItem(key, data), replaceOnDuplicate, out oldData);
#if DEBUG
            hash.Validate();
#endif //DEBUG
        }

        private void InsertValidate(string key, int data, bool replaceOnDuplicate, int expectedOldData)
        {
            TestItem oldData;
            hash.Insert(new TestItem(key, data), replaceOnDuplicate, out oldData);
#if DEBUG
            hash.Validate();
#endif //DEBUG
            Assert.AreEqual(expectedOldData, oldData.data);
        }

        /// <summary>
        /// Delete a key, check the data in the deleted key, print and validate.
        /// </summary>
        /// <param name="key">Key to delete.</param>
        /// <param name="data">Expected data in the deleted key.</param>
        private void DeletePrintValidate(string key, int data)
        {
            TestItem itemFound;
            int countBefore = hash.ElementCount;
            bool success = hash.Delete(new TestItem(key), out itemFound);
#if DEBUG
            hash.Print();
#endif //DEBUG
            Assert.IsTrue(success, "Key to delete wasn't found");
            Assert.AreEqual(data, itemFound.data, "Data in deleted key was incorrect.");
            int countAfter = hash.ElementCount;
            Assert.AreEqual(countBefore - 1, countAfter, "Count of elements incorrect after deletion");
#if DEBUG
            hash.Validate();
#endif //DEBUG
        }

        private void FindKey(string key, int value)
        {
            TestItem itemFound;
            bool found = hash.Find(new TestItem(key), false, out itemFound);
            Assert.IsTrue(found, "Key was not found in the hash");
            Assert.AreEqual(value, itemFound.data, "Wrong value found in the hash");
        }

        private bool FindReplaceKey(string key, int newValue, int expectedOldValue)
        {
            TestItem itemFound;
            bool found = hash.Find(new TestItem(key, newValue), true, out itemFound);
            Assert.AreEqual(expectedOldValue, itemFound.data);
            return found;
        }

        /// <summary>
        /// Test creation of the hash.
        /// </summary>
        [Test]
        public void Create()
        {
            hash = new Hash<TestItem>(new DataComparer());
#if DEBUG
            hash.Print();
            hash.Validate();
#endif //DEBUG
        }

        /// <summary>
        /// Insert values into hash to test the basic insertion algorithm. Validate
        /// and print the hash after each step.
        /// </summary>
        [Test]
        public void NormalInsert()
        {
            hash = new Hash<TestItem>(new DataComparer());

            InsertPrintValidate("m");
            InsertPrintValidate("b");
            InsertPrintValidate("t");
            InsertPrintValidate("o");
            InsertPrintValidate("z");
            InsertPrintValidate("k");
            InsertPrintValidate("g");
            InsertPrintValidate("a5");
            InsertPrintValidate("c");
            InsertPrintValidate("a2");
            InsertPrintValidate("a7");
            InsertPrintValidate("i");
            InsertPrintValidate("h");
            Assert.AreEqual(13, hash.ElementCount, "Wrong number of items in the hash.");
        }

        /// <summary>
        /// Insert values into hash and then find values in the hash.
        /// </summary>
        [Test]
        public void NormalFind()
        {
            hash = new Hash<TestItem>(new DataComparer());

            InsertValidate("m", 101);
            FindKey("m", 101);
            InsertValidate("b", 102);
            InsertValidate("t", 103);
            FindKey("b", 102);
            FindKey("t", 103);
            InsertValidate("o", 104);
            FindKey("b", 102);
            InsertValidate("z", 105);
            InsertValidate("g", 106);
            FindKey("g", 106);
            InsertValidate("a5", 107);
            InsertValidate("c", 8);
            InsertValidate("a2", 9);
            FindKey("z", 105);
            InsertValidate("a7", 10);
            InsertValidate("i", 11);
            InsertValidate("h", 112);
            InsertValidate("k", 113);

            Assert.AreEqual(13, hash.ElementCount, "Wrong number of items in the hash.");

            FindKey("m", 101);
            FindKey("b", 102);
            FindKey("t", 103);
            FindKey("o", 104);
            FindKey("z", 105);
            FindKey("g", 106);
            FindKey("a5", 107);
            FindKey("c", 8);
            FindKey("a2", 9);
            FindKey("a7", 10);
            FindKey("i", 11);
            FindKey("h", 112);
            FindKey("k", 113);
        }
        /// <summary>
        /// Test find with the replace option..
        /// </summary>
        [Test]
        public void FindReplace()
        {
            bool b;
            hash = new Hash<TestItem>(new DataComparer());

            InsertValidate("m", 101);
            FindKey("m", 101);
            InsertValidate("b", 102);
            InsertValidate("t", 103);
            b = FindReplaceKey("b", 202, 102); Assert.IsTrue(b);
            FindKey("t", 103);
            InsertValidate("o", 104);
            FindKey("b", 202);
            InsertValidate("z", 105);
            InsertValidate("g", 106);
            FindKey("g", 106);
            b = FindReplaceKey("a5", 77, 0); Assert.IsFalse(b);
            b = FindReplaceKey("a5", 134, 0); Assert.IsFalse(b);
            b = FindReplaceKey("m", 201, 101); Assert.IsTrue(b);
            InsertValidate("a5", 107);
            InsertValidate("c", 8);
            InsertValidate("k", 313);
            InsertValidate("a2", 9);
            FindKey("z", 105);
            b = FindReplaceKey("m", 301, 201); Assert.IsTrue(b);
            InsertValidate("a7", 10);
            b = FindReplaceKey("a5", 207, 107); Assert.IsTrue(b);
            InsertValidate("i", 11);
            InsertValidate("h", 112);
            b = FindReplaceKey("z", 205, 105); Assert.IsTrue(b);
            b = FindReplaceKey("g", 206, 106); Assert.IsTrue(b);
            b = FindReplaceKey("g", 306, 206); Assert.IsTrue(b);
            b = FindReplaceKey("k", 513, 313);

            Assert.AreEqual(13, hash.ElementCount, "Wrong number of items in the hash.");

            FindKey("m", 301);
            FindKey("b", 202);
            FindKey("t", 103);
            FindKey("o", 104);
            FindKey("z", 205);
            FindKey("g", 306);
            FindKey("a5", 207);
            FindKey("c", 8);
            FindKey("a2", 9);
            FindKey("a7", 10);
            FindKey("i", 11);
            FindKey("h", 112);
            FindKey("k", 513);
        }

        /// <summary>
        /// Insert values into tree using "do-nothing" policy and then find values in the tree.
        /// </summary>
        [Test]
        public void DoNothingFind()
        {
            hash = new Hash<TestItem>(new DataComparer());

            InsertValidate("m", 101, false, 0);
            FindKey("m", 101);
            InsertValidate("b", 102, false, 0);
            InsertValidate("t", 103, false, 0);
            InsertValidate("m", 201, false, 101);
            FindKey("b", 102);
            FindKey("t", 103);
            InsertValidate("o", 104, false, 0);
            FindKey("b", 102);
            InsertValidate("z", 105, false, 0);
            InsertValidate("g", 106, false, 0);
            InsertValidate("b", 202, false, 102);
            FindKey("g", 106);
            InsertValidate("g", 206, false, 106);
            InsertValidate("a5", 107, false, 0);
            InsertValidate("t", 203, false, 103);
            InsertValidate("c", 8, false, 0);
            InsertValidate("a2", 9, false, 0);
            FindKey("z", 105);
            InsertValidate("a7", 10, false, 0);
            InsertValidate("i", 11, false, 0);
            InsertValidate("h", 112, false, 0);
            InsertValidate("z", 205, false, 105);
            InsertValidate("a2", 209, false, 9);
            InsertValidate("c", 208, false, 8);
            InsertValidate("i", 211, false, 11);
            InsertValidate("h", 212, false, 112);
            InsertValidate("k", 113, false, 0);
            InsertValidate("m", 401, false, 101);
            InsertValidate("k", 213, false, 113);

            Assert.AreEqual(13, hash.ElementCount, "Wrong number of items in the tree.");

            FindKey("m", 101);
            FindKey("b", 102);
            FindKey("t", 103);
            FindKey("o", 104);
            FindKey("z", 105);
            FindKey("g", 106);
            FindKey("a5", 107);
            FindKey("c", 8);
            FindKey("a2", 9);
            FindKey("a7", 10);
            FindKey("i", 11);
            FindKey("h", 112);
            FindKey("k", 113);
        }

        /// <summary>
        /// Check that deletion works.
        /// </summary>
        [Test]
        public void Delete()
        {
            hash = new Hash<TestItem>(new DataComparer());

            InsertPrintValidate("m", 101);
            DeletePrintValidate("m", 101);

            InsertPrintValidate("m", 101);
            InsertPrintValidate("b", 102);
            InsertPrintValidate("t", 103);
            DeletePrintValidate("b", 102);
            DeletePrintValidate("m", 101);
            DeletePrintValidate("t", 103);

            InsertPrintValidate("m", 101);
            InsertPrintValidate("b", 102);
            InsertPrintValidate("t", 103);
            InsertPrintValidate("o", 104);
            InsertPrintValidate("z", 105);
            InsertPrintValidate("g", 106);
            InsertPrintValidate("a5", 107);
            InsertPrintValidate("c", 8);
            InsertPrintValidate("a2", 9);
            InsertPrintValidate("a7", 10);
            InsertPrintValidate("i", 11);
            InsertPrintValidate("h", 112);
            InsertPrintValidate("k", 113);

            DeletePrintValidate("m", 101);
            DeletePrintValidate("b", 102);
            DeletePrintValidate("t", 103);
            DeletePrintValidate("o", 104);
            DeletePrintValidate("z", 105);
            DeletePrintValidate("h", 112);
            DeletePrintValidate("g", 106);
            DeletePrintValidate("a5", 107);
            DeletePrintValidate("c", 8);
            DeletePrintValidate("a2", 9);
            DeletePrintValidate("k", 113);
            DeletePrintValidate("a7", 10);
            DeletePrintValidate("i", 11);
        }

        [Test]
        public void DeleteNotPresent()
        {
            int dummy;
            Hash<int> t = new Hash<int>(EqualityComparer<int>.Default);

            t.Insert(3, true, out dummy);
            t.Insert(1, true, out dummy);
            t.Insert(5, true, out dummy);
            t.Insert(3, true, out dummy);
            t.Insert(2, true, out dummy);
            t.Insert(2, true, out dummy);
            t.Insert(3, true, out dummy);
            t.Insert(4, true, out dummy);

            bool b;
            int d;

            b = t.Delete(1, out d);
            Assert.IsTrue(b);
#if DEBUG
            t.Print();
            t.Validate();
#endif //DEBUG

            b = t.Delete(1, out d);
            Assert.IsFalse(b);
#if DEBUG
            t.Print();
            t.Validate();