hashtests.cs

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

#endif //DEBUG

            b = t.Delete(int.MinValue, out d);
            Assert.IsFalse(b);
#if DEBUG
            t.Print();
            t.Validate();
#endif //DEBUG

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

            b = t.Delete(3, out d);
            Assert.IsFalse(b);
#if DEBUG
            t.Print();
            t.Validate();
#endif //DEBUG
        }

        /// <summary>
        /// Insert values into tree and enumerate then to test enumeration.
		/// </summary>
        [Test]
        public void Enumerate()
        {
            hash = new Hash<TestItem>(new DataComparer());
            InsertValidate("m");
            InsertValidate("b");
            InsertValidate("t");
            InsertValidate("o");
            InsertValidate("p");
            InsertValidate("g");
            InsertValidate("a5");
            InsertValidate("c");
            InsertValidate("a2");
            InsertValidate("a7");
            InsertValidate("i");
            InsertValidate("h");
            InsertValidate("o");
            InsertValidate("l");
            InsertValidate("k");
            InsertValidate("c");

            string[] keys = new string[] { "a2", "a5", "a7", "b", "c", "g", "h", "i", "k", "l", "m", "o", "p", "t" };
            foreach (TestItem item in hash) {
                int index;
                index = Array.IndexOf(keys, item.key);
                Assert.IsTrue(index >= 0, "key not found in array");
                keys[index] = null;
            }
        }

        const int LENGTH = 500;			// length of each random array of values.
        const int ITERATIONS = 30;		    // number of iterations


        /// <summary>
        /// Create a random array of values.
        /// </summary>
        /// <param name="seed">Seed for random number generators</param>
        /// <param name="length">Length of array</param>
        /// <param name="max">Maximum value of number. Should be much 
        /// greater than length.</param>
        /// <param name="allowDups">Whether to allow duplicate elements.</param>
        /// <returns></returns>
        private int[] CreateRandomArray(int seed, int length, int max, bool allowDups)
        {
            Random rand = new Random(seed);

            int[] a = new int[length];
            for (int i = 0; i < a.Length; ++i)
                a[i] = -1;

            for (int el = 0; el < a.Length; ++el) {
                int value;
                do {
                    value = rand.Next(max);
                } while (!allowDups && Array.IndexOf(a, value) >= 0);
                a[el] = value;
            }

            return a;
        }

        /// <summary>
        /// Insert all the elements of an integer array into the tree. The
        /// values in the tree are the indexes of the array.
        /// </summary>
        /// <param name="a">Array of values to insert.</param>
        private void InsertArray(int[] a)
        {
            TestItem dummy;
            for (int i = 0; i < a.Length; ++i) {
                string s = StringFromInt(a[i]);
                hash.Insert(new TestItem(s, i), true, out dummy);
#if DEBUG
                if (i % 50 == 0)
                    hash.Validate();
#endif //DEBUG
            }
#if DEBUG
            hash.Validate();
#endif //DEBUG
        }

        private string StringFromInt(int i)
        {
            return string.Format("e{0}", i);
        }

        /// <summary>
        /// Insert LENGTH items in random order into the tree and validate
        /// it. Do this ITER times.
        /// </summary>
        [Test]
        public void InsertRandom()
        {
            for (int iter = 0; iter < ITERATIONS; ++iter) {
                hash = new Hash<TestItem>(new DataComparer());
                int[] a = CreateRandomArray(iter, LENGTH, LENGTH * 10, false);
                InsertArray(a);
#if DEBUG
                hash.Validate();
#endif //DEBUG
                Assert.AreEqual(LENGTH, hash.ElementCount, "Wrong number of items in the tree.");
            }
        }

        /// <summary>
        /// Insert LENGTH items in random order into the tree and then find them all
        /// Do this ITER times.
        /// </summary>
        [Test]
        public void FindRandom()
        {
            for (int iter = 0; iter < ITERATIONS; ++iter) {
                hash = new Hash<TestItem>(new DataComparer());
                int[] a = CreateRandomArray(iter + 1000, LENGTH, LENGTH * 10, false);

                InsertArray(a);
#if DEBUG
                hash.Validate();
#endif //DEBUG
                Assert.AreEqual(LENGTH, hash.ElementCount, "Wrong number of items in the hash.");

                for (int el = 0; el < a.Length; ++el) {
                    FindKey(StringFromInt(a[el]), el);
                }
            }
        }


        /// <summary>
        /// Insert LENGTH items in random order into the tree and then enumerate them.
        /// Do this ITER times.
        /// </summary>
        [Test]
        public void EnumerateRandom()
        {
            for (int iter = 0; iter < ITERATIONS / 10; ++iter) {
                hash = new Hash<TestItem>(new DataComparer());
                int[] a = CreateRandomArray(iter + 1000, LENGTH, LENGTH * 10, false);

                InsertArray(a);
#if DEBUG
                hash.Validate();
#endif //DEBUG
                Assert.AreEqual(LENGTH, hash.ElementCount, "Wrong number of items in the hash.");

                foreach (TestItem item in hash) {
                    int index = -1;
                    for (int i = 0; i < a.Length; ++i)
                        if (StringFromInt(a[i]) == item.key)
                            index = i;

                    Assert.IsTrue(index >= 0);
                    Assert.IsTrue(index == item.data);
                    a[index] = -1;
                }
                foreach (int i in a)
                    Assert.AreEqual(-1, i);
            }
        }

        /// <summary>
        /// Insert and delete items from the tree at random, finally removing all
        /// the items that are in the tree. Validate the tree after each step.
        /// </summary>
        [Test]
        public void DeleteRandom()
        {
            for (int iter = 0; iter < ITERATIONS / 10; ++iter) {
                hash = new Hash<TestItem>(new DataComparer());
                bool[] a = new bool[LENGTH];
                int[] value = new int[LENGTH];
                Random rand = new Random(iter + 5000);
                TestItem itemFound;

                for (int i = 0; i < LENGTH * 10; ++i) {
                    int v = rand.Next(LENGTH);
                    string key = StringFromInt(v);
                    if (a[v] && rand.Next(4) != 0) {
                        // Already in the hash. Make sure we can find it, then delete it.
                        bool b = hash.Find(new TestItem(key), false, out itemFound);
                        Assert.IsTrue(b, "Couldn't find key in hash");
                        Assert.AreEqual(value[v], itemFound.data, "Data is incorrect");
                        b = hash.Delete(new TestItem(key), out itemFound);
                        Assert.IsTrue(b, "Couldn't delete key in hash");
                        Assert.AreEqual(value[v], itemFound.data, "Data is incorrect");
#if DEBUG
                        if (i % 50 == 0)
                            hash.Validate();
#endif //DEBUG
                        a[v] = false;
                        value[v] = 0;
                    }
                    else if (i < LENGTH * 7) {
                        // Add it.
                        value[v] = rand.Next(10000) + 1;
                        bool b = hash.Find(new TestItem(key), false, out itemFound);
                        Assert.AreEqual(a[v], b);
                        TestItem dummy;
                        b = hash.Insert(new TestItem(key, value[v]), true, out dummy);
                        Assert.AreEqual(a[v], ! b);
#if DEBUG
                        if (i % 50 == 0)
                            hash.Validate();
#endif //DEBUG
                        a[v] = true;
                    }
                }

                for (int v = 0; v < LENGTH; ++v) {
                    string key = StringFromInt(v);
                    if (a[v]) {
                        // Already in the hash. Make sure we can find it, then delete it.
                        bool b = hash.Find(new TestItem(key), false, out itemFound);
                        Assert.IsTrue(b, "Couldn't find key in hash");
                        Assert.AreEqual(value[v], itemFound.data, "Data is incorrect");
                        b = hash.Delete(new TestItem(key), out itemFound);
                        Assert.IsTrue(b, "Couldn't delete key in hash");
                        Assert.AreEqual(value[v], itemFound.data, "Data is incorrect");
#if DEBUG
                        if (v % 50 == 0)
                            hash.Validate();
#endif //DEBUG
                        a[v] = false;
                    }
                }
            }

#if DEBUG
            hash.Validate();
#endif //DEBUG
        }

        [Test]
        public void Clone()
        {
            hash = new Hash<TestItem>(new DataComparer());

            InsertValidate("foo", 3);
            InsertValidate("bar", 4);
            InsertValidate("bingo", 5);
            InsertValidate("biff", 6);
            InsertValidate("zip", 7);
            InsertValidate("zap", 8);

            Hash<TestItem> clone = hash.Clone(null);
#if DEBUG
            clone.Validate();
#endif //DEBUG

            InsertValidate("a", 51);
            InsertValidate("b", 52);
            InsertValidate("c", 53);
            InsertValidate("d", 54);

#if DEBUG
            clone.Validate();
#endif //DEBUG
            Assert.AreEqual(6, clone.ElementCount);

            string[] s_array = { "bar", "biff", "bingo", "foo", "zap", "zip" };
            int i = 0;
            foreach (TestItem item in clone) {
                int index = Array.IndexOf(s_array, item.key);
                Assert.IsTrue(index >= 0);
                Assert.AreEqual(s_array[index], item.key);
                s_array[index] = null;
                ++i;
            }
            Assert.AreEqual(6, i);

            hash = new Hash<TestItem>(new DataComparer());
            clone = hash.Clone(null);
            Assert.IsTrue(hash.ElementCount == 0 && clone.ElementCount == 0);
#if DEBUG
            clone.Validate();
#endif //DEBUG
        }

        [Test]
        public void GrowShrink()
        {
            Hash<double> hash1 = new Hash<double>(EqualityComparer<double>.Default);
            double dummy;

            Random r = new Random(13);

            for (int i = 0; i < 1000; ++i) {
                bool b = hash1.Insert(r.NextDouble(), true, out dummy);
                Assert.IsTrue(b);
            }

#if DEBUG
            hash1.PrintStats();
            hash1.Validate();
#endif //DEBUG
            Assert.IsTrue(hash1.SlotCount == 2048);

            r = new Random(13);

            for (int i = 0; i < 600; ++i) {
                bool b = hash1.Delete(r.NextDouble(), out dummy);
                Assert.IsTrue(b);
            }

#if DEBUG
            hash1.PrintStats();
            hash1.Validate();
#endif //DEBUG
            Assert.IsTrue(hash1.SlotCount == 1024);

            for (int i = 0; i < 380; ++i) {
                bool b = hash1.Delete(r.NextDouble(), out dummy);
                Assert.IsTrue(b);
            }

#if DEBUG
            hash1.PrintStats();
            hash1.Validate();
#endif //DEBUG
            Assert.IsTrue(hash1.SlotCount == 64);

            for (int i = 0; i < 20; ++i) {
                bool b = hash1.Delete(r.NextDouble(), out dummy);
                Assert.IsTrue(b);
            }

#if DEBUG
            hash1.PrintStats();
            hash1.Validate();
#endif //DEBUG
            Assert.IsTrue(hash1.SlotCount == 0);

            hash1.Insert(4.5, true, out dummy);

#if DEBUG
            hash1.PrintStats();
            hash1.Validate();
#endif //DEBUG
            Assert.IsTrue(hash1.SlotCount == 16);
        }

        [Test]
        public void LoadFactor()
        {
            Hash<double> hash1 = new Hash<double>(EqualityComparer<double>.Default);
            double dummy;

            Random r = new Random(13);

            for (int i = 0; i < 600; ++i) {
                bool b = hash1.Insert(r.NextDouble(), true, out dummy);
                Assert.IsTrue(b);
            }

#if DEBUG
            hash1.PrintStats();
            hash1.Validate();
#endif //DEBUG
            Assert.IsTrue(hash1.SlotCount == 1024);

            hash1.LoadFactor = 0.55F;
            Assert.AreEqual(0.55F, hash1.LoadFactor);
#if DEBUG
            hash1.PrintStats();
            hash1.Validate();
#endif //DEBUG
            Assert.IsTrue(hash1.SlotCount == 2048);

            hash1.LoadFactor = 0.9F;
            Assert.AreEqual(0.9F, hash1.LoadFactor);
#if DEBUG
            hash1.PrintStats();
            hash1.Validate();
#endif //DEBUG
            Assert.IsTrue(hash1.SlotCount == 1024);
        }
    }
}