redblacktests.cs

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

			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>
		/// <param name="dupPolicy">The DuplicatePolicy to use when inserting.</param>
		private void InsertArray(int[] a, DuplicatePolicy dupPolicy)
		{
            TestItem dummy;
            for (int i = 0; i < a.Length; ++i) {
				string s = StringFromInt(a[i]);
				tree.Insert(new TestItem(s, i), dupPolicy, out dummy);
#if DEBUG
				tree.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) {
				tree = new RedBlackTree<TestItem>(new DataComparer());
				int[] a = CreateRandomArray(iter, LENGTH, LENGTH * 10, true);
				InsertArray(a, DuplicatePolicy.InsertLast);
#if DEBUG
				tree.Validate();
#endif //DEBUG
                CheckAllIndices();

                Assert.AreEqual(LENGTH, tree.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) {
				tree = new RedBlackTree<TestItem>(new DataComparer());
				int[] a = CreateRandomArray(iter + 1000, LENGTH, LENGTH * 10, false);

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

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

		/// <summary>
		/// Insert LENGTH items in random order into the tree using the "replace" policy, 
		/// and then find them all.
		/// Do this ITER times.
		/// </summary>
		[Test] public void ReplaceFindRandom() {
			for (int iter = 0; iter < ITERATIONS; ++iter) {
				tree = new RedBlackTree<TestItem>(new DataComparer());
				int[] a = CreateRandomArray(iter + 2000, LENGTH, LENGTH / 5, true);

				InsertArray(a, DuplicatePolicy.ReplaceFirst);
#if DEBUG
				tree.Validate();
#endif //DEBUG
                CheckAllIndices();

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

		/// <summary>
		/// Insert LENGTH items in random order into the tree using the "replace" policy, 
		/// and then find them all.
		/// Do this ITER times.
		/// </summary>
		[Test] public void DoNothingFindRandom() {

            for (int iter = 0; iter < ITERATIONS; ++iter) {
				tree = new RedBlackTree<TestItem>(new DataComparer());
				int[] a = CreateRandomArray(iter + 3000, LENGTH, LENGTH / 5, true);

				InsertArray(a, DuplicatePolicy.DoNothing);
#if DEBUG
				tree.Validate();
#endif //DEBUG
                CheckAllIndices();

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

		/// <summary>
		/// Insert LENGTH items in random order into the tree using the "replace" policy, 
		/// and then find them all.
		/// Do this ITER times.
		/// </summary>
		[Test] public void InsertFirstFindRandom() {
			for (int iter = 0; iter < ITERATIONS; ++iter) {
				tree = new RedBlackTree<TestItem>(new DataComparer());
				int[] a = CreateRandomArray(iter + 3000, LENGTH, LENGTH / 5, true);

				InsertArray(a, DuplicatePolicy.InsertFirst);
#if DEBUG
				tree.Validate();
#endif //DEBUG
                CheckAllIndices();
                Assert.AreEqual(LENGTH, tree.ElementCount, "Element count is wrong.");

				for (int el = 0; el < a.Length; ++el) {
					FindFirstKey(StringFromInt(a[el]), Array.LastIndexOf(a, a[el]));
					FindLastKey(StringFromInt(a[el]), Array.IndexOf(a, a[el]));
				}
			}
		}		

		/// <summary>
		/// Insert LENGTH items in random order into the tree using the "replace" policy, 
		/// and then find them all.
		/// Do this ITER times.
		/// </summary>
		[Test] public void InsertLastFindRandom() {
			for (int iter = 0; iter < ITERATIONS; ++iter) {
				tree = new RedBlackTree<TestItem>(new DataComparer());
				int[] a = CreateRandomArray(iter + 4000, LENGTH, LENGTH / 5, true);

				InsertArray(a, DuplicatePolicy.InsertLast);
#if DEBUG
				tree.Validate();
#endif //DEBUG
                CheckAllIndices();
                Assert.AreEqual(LENGTH, tree.ElementCount, "Element count is wrong.");

				for (int el = 0; el < a.Length; ++el) {
					FindFirstKey(StringFromInt(a[el]), Array.IndexOf(a, a[el]));
					FindLastKey(StringFromInt(a[el]), Array.LastIndexOf(a, a[el]));
				}
			}
		}
		
		/// <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) {
				tree = new RedBlackTree<TestItem>(new DataComparer());
				bool[] a = new bool[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]) {
						// Already in the tree. Make sure we can find it, then delete it.
						bool b = tree.Find(new TestItem(key), true, false, out itemFound);
						Assert.IsTrue(b, "Couldn't find key in tree");
						Assert.AreEqual(v, itemFound.data, "Data is incorrect");
						b = tree.Delete(new TestItem(key), true, out itemFound);
						Assert.IsTrue(b, "Couldn't delete key in tree");
						Assert.AreEqual(v, itemFound.data, "Data is incorrect");
#if DEBUG
						tree.Validate();
#endif //DEBUG
                        CheckAllIndices();
                        a[v] = false;
					}
					else if (i < LENGTH * 7) {
						// Not in tree. Try to find and delete it. Then Add it.
                        bool b = tree.Find(new TestItem(key), true, false, out itemFound);
                        Assert.IsFalse(b, "Key shouldn't be in tree");
                        b = tree.Delete(new TestItem(key), true, out itemFound);
                        Assert.IsFalse(b);
                        TestItem dummy;
                        b = tree.Insert(new TestItem(key, v), DuplicatePolicy.ReplaceFirst, out dummy);
                        Assert.IsTrue(b, "Key shouldn't be in tree");
#if DEBUG
                        tree.Validate();
#endif //DEBUG
                        CheckAllIndices();
                        a[v] = true;
					}
				}

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

        [Test]
        public void ChangeDuringEnumerate()
        {
            TestItem dummy;
            tree = new RedBlackTree<TestItem>(new DataComparer());

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

            int i = 0;
            try {
                foreach (TestItem item in tree) {
                    ++i;
                    if (i == 4)
                        InsertValidate("hello", 23);
                }
                Assert.Fail("Should have thrown exception");
            }
            catch (Exception e) {
                Assert.IsTrue(e is InvalidOperationException);
            }

            Assert.AreEqual(4, i);     // should have stopped right away.
            Assert.AreEqual(7, tree.ElementCount);   // element should have been found.
            FindOnlyKey("hello", 23);  // element should have been inserted.
#if DEBUG
            tree.Validate();
#endif //DEBUG

            i = 0;
            try {
                foreach (TestItem item in tree.EnumerateRangeReversed(tree.BoundedRangeTester(true, new TestItem("biff", 0), true, new TestItem("zap", 0)))) {
                    ++i;
                    if (i == 3)
                        DeletePrintValidate("hello", 23);
                }
                Assert.Fail("Should have thrown exception");
            }
            catch (Exception e) {
                Assert.IsTrue(e is InvalidOperationException);
            }

            Assert.AreEqual(3, i);     // should have stopped right away.
            Assert.AreEqual(6, tree.ElementCount);   // element should have been deleted.
            Assert.IsFalse(tree.Find(new TestItem("hello", 0), true, false, out dummy));
#if DEBUG
            tree.Validate();
#endif //DEBUG
        }

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

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

            RedBlackTree<TestItem> clone = tree.Clone();
#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) {
                Assert.AreEqual(s_array[i], item.key);
                ++i;
            }

            tree = new RedBlackTree<TestItem>(new DataComparer());

            clone = tree.Clone();
            Assert.AreEqual(0, clone.ElementCount);
#if DEBUG
            clone.Validate();
#endif //DEBUG
        }

        [Test]
        public void GetByIndexExceptions()
        {
            tree = new RedBlackTree<TestItem>(new DataComparer());

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

            try {
                TestItem item = tree.GetItemByIndex(-1);
                Assert.Fail("should throw");
            }
            catch (Exception e) {
                Assert.IsTrue(e is ArgumentOutOfRangeException);
            }

            try {
                TestItem item = tree.GetItemByIndex(6);
                Assert.Fail("should throw");
            }
            catch (Exception e) {
                Assert.IsTrue(e is ArgumentOutOfRangeException);
            }

            try {
                TestItem item = tree.GetItemByIndex(Int32.MaxValue);
                Assert.Fail("should throw");
            }
            catch (Exception e) {
                Assert.IsTrue(e is ArgumentOutOfRangeException);
            }

            try {
                TestItem item = tree.GetItemByIndex(Int32.MinValue);
                Assert.Fail("should throw");
            }
            catch (Exception e) {
                Assert.IsTrue(e is ArgumentOutOfRangeException);
            }

            tree = new RedBlackTree<TestItem>(new DataComparer());

            try {
                TestItem item = tree.GetItemByIndex(0);
                Assert.Fail("should throw");
            }
            catch (Exception e) {
                Assert.IsTrue(e is ArgumentOutOfRangeException);
            }
        }

    }

}