redblacktests.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 NUnit.Framework;
using System.Runtime.InteropServices;

namespace Wintellect.PowerCollections.Tests {
	
	/// <summary>
	/// An item type used when testing the RedBlackTree.
	/// </summary>
	struct TestItem
	{
		public TestItem(string key)
		{
			this.key = key;
			this.data = 0;
		}
		public TestItem(string key, int data)
		{
			this.key = key;
			this.data = data;
		}
		public string key;
		public int data;

		public override string ToString()
		{
			return string.Format("Key:{0} Data:{1}", key, data);
		}

	}

	/// <summary>
	/// Tests for testing the RedBlackTree class, using NUnit.
	/// </summary>
	[TestFixture]
	public class RedBlackTreeTests
	{
		internal RedBlackTree<TestItem> tree;

        internal class DataComparer : System.Collections.Generic.IComparer<TestItem>
        {
            public int Compare(TestItem x, TestItem y)
            {
                return string.Compare(x.key, y.key);
            }

            public bool Equals(TestItem x, TestItem y)
            {
                throw new NotSupportedException();
            }

            public int GetHashCode(TestItem obj)
            {
                throw new NotSupportedException();
            }
        }

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

		private void InsertPrintValidate(string key, int data) {
			InsertPrintValidate(key, data, DuplicatePolicy.ReplaceFirst);
		}

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

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

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

		private void InsertValidate(string key, int data) {
			InsertValidate(key, data, DuplicatePolicy.InsertLast);
		}

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

        private void InsertValidate(string key, int data, DuplicatePolicy dupPolicy, int expectedOldData)
		{
            TestItem oldData;
            tree.Insert(new TestItem(key, data), dupPolicy, out oldData);
#if DEBUG
			tree.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) {
			DeletePrintValidate(key, data, true);
		}

		private void DeletePrintValidate(string key, int data, bool first) {
			TestItem itemFound;
			int countBefore = tree.ElementCount;
			bool success = tree.Delete(new TestItem(key), 
				                                 first ? true : false, 
				                                 out itemFound);
#if DEBUG
			tree.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 = tree.ElementCount;
			Assert.AreEqual(countBefore - 1, countAfter, "Count of elements incorrect after deletion");
#if DEBUG
			tree.Validate();
#endif //DEBUG
		}

        private void GlobalDeletePrintValidate(string key, int data, bool first)
        {
            TestItem itemFound;
            int countBefore = tree.ElementCount;
            bool success = tree.DeleteItemFromRange(tree.EntireRangeTester, first, out itemFound);
#if DEBUG
            tree.Print();
#endif //DEBUG
            Assert.IsTrue(success, "Key to delete wasn't found");
            Assert.AreEqual(key, itemFound.key, "Key in deleted key was incorrect.");
            Assert.AreEqual(data, itemFound.data, "Data in deleted key was incorrect.");
            int countAfter = tree.ElementCount;
            Assert.AreEqual(countBefore - 1, countAfter, "Count of elements incorrect after deletion");
#if DEBUG
            tree.Validate();
#endif //DEBUG
        }

        private void FindFirstKey(string key, int value)
        {
            TestItem itemFound;
			bool found = tree.Find(new TestItem(key), true, false, out itemFound);
			Assert.IsTrue(found, "Key was not found in the tree");
			Assert.AreEqual(value, itemFound.data, "Wrong value found in the tree");
            int foundIndex = tree.FindIndex(new TestItem(key), true);
            Assert.IsTrue(foundIndex >= 0);
            Assert.AreEqual(value, tree.GetItemByIndex(foundIndex).data);
		}

		private void FindLastKey(string key, int value) {
			TestItem itemFound;
			bool found = tree.Find(new TestItem(key), false, false, out itemFound);
			Assert.IsTrue(found, "Key was not found in the tree");
			Assert.AreEqual(value, itemFound.data, "Wrong value found in the tree");
            int foundIndex = tree.FindIndex(new TestItem(key), false);
            Assert.IsTrue(foundIndex >= 0);
            Assert.AreEqual(value, tree.GetItemByIndex(foundIndex).data);
        }

		private void FindOnlyKey(string key, int value) {
			FindFirstKey(key, value);
			FindLastKey(key, value);
		}

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

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

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

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

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

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

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

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

        /// <summary>
        /// Test find with the replace option..
        /// </summary>
        [Test]
        public void FindReplace()
        {
            bool b;
            tree = new RedBlackTree<TestItem>(new DataComparer());

            InsertValidate("m", 101);
            FindOnlyKey("m", 101);
            InsertValidate("b", 102);
            InsertValidate("t", 103);
            b = FindReplaceKey("b", 202, 102); Assert.IsTrue(b);
            FindOnlyKey("t", 103);
            InsertValidate("o", 104);
            FindOnlyKey("b", 202);
            InsertValidate("z", 105);
            InsertValidate("g", 106);
            FindOnlyKey("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("a2", 9);
            FindOnlyKey("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);

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

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

        /// <summary>
        /// Check that deletion works.
		/// </summary>
		[Test] public void Delete() {
			tree = new RedBlackTree<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);		

			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("a7", 10);
			DeletePrintValidate("i", 11);
		}

		/// <summary>
		/// Test that deleting a non-present value works right.  A bug was found where the root isn't
		/// colored black in this case.
		/// </summary>
		[Test]
		public void DeleteNotPresent()
		{
            int dummy;
            RedBlackTree<int> t = new RedBlackTree<int>(Comparers.DefaultComparer<int>());

			t.Insert(3, DuplicatePolicy.ReplaceFirst, out dummy);