⭐ 欢迎来到虫虫下载站！ | 📦 资源下载 📁 资源专辑 ℹ️ 关于我们
⭐ 虫虫下载站
📤 上传资源

📄 redblacktests.cs

📁 C#写的类似于STL的集合类,首先是C#编写,可以用于.net变程.
💻 CS
📖 第 1 页 / 共 4 页
字号:
🔍
1234 
            Assert.AreEqual(11, index);
        }

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

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

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

			FindOnlyKey("m", 201);
			FindOnlyKey("b", 202);
			FindOnlyKey("t", 203);
			FindOnlyKey("o", 104);
			FindOnlyKey("z", 205);
			FindOnlyKey("g", 206);
			FindOnlyKey("a5", 107);
			FindOnlyKey("c", 208);
			FindOnlyKey("a2", 209);
			FindOnlyKey("a7", 10);
			FindOnlyKey("i", 211);
			FindOnlyKey("h", 212);
		}	

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

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

            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>
		/// Insert values into tree using insert-first policy and then find values in the tree.
		/// </summary>
		[Test] public void InsertFirstFind() {
			tree = new RedBlackTree<TestItem>(new DataComparer());

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

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

			FindLastKey("m", 101);
			FindLastKey("b", 102);
			FindLastKey("t", 103);
			FindLastKey("o", 104);
			FindLastKey("z", 105);
			FindLastKey("g", 106);
			FindLastKey("a5", 107);
			FindLastKey("c", 8);
			FindLastKey("a2", 9);
			FindLastKey("a7", 10);
			FindLastKey("i", 11);
			FindLastKey("h", 112);
			
			FindFirstKey("m", 201);
			FindFirstKey("b", 202);
			FindFirstKey("t", 203);
			FindFirstKey("o", 104);
			FindFirstKey("z", 205);
			FindFirstKey("g", 206);
			FindFirstKey("a5", 107);
			FindFirstKey("c", 208);
			FindFirstKey("a2", 209);
			FindFirstKey("a7", 10);
			FindFirstKey("i", 211);
			FindFirstKey("h", 212);

            CheckAllIndices();
		}
	
		/// <summary>
		/// Insert values into tree using insert-last policy and then find values in the tree.
		/// </summary>
		[Test] public void InsertLastFind() {
			tree = new RedBlackTree<TestItem>(new DataComparer());

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

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

			FindFirstKey("m", 101);
			FindFirstKey("b", 102);
			FindFirstKey("t", 103);
			FindFirstKey("o", 104);
			FindFirstKey("z", 105);
			FindFirstKey("g", 106);
			FindFirstKey("a5", 107);
			FindFirstKey("c", 8);
			FindFirstKey("a2", 9);
			FindFirstKey("a7", 10);
			FindFirstKey("i", 11);
			FindFirstKey("h", 112);
			
			FindLastKey("m", 201);
			FindLastKey("b", 202);
			FindLastKey("t", 203);
			FindLastKey("o", 104);
			FindLastKey("z", 205);
			FindLastKey("g", 206);
			FindLastKey("a5", 107);
			FindLastKey("c", 208);
			FindLastKey("a2", 209);
			FindLastKey("a7", 10);
			FindLastKey("i", 211);
			FindLastKey("h", 212);
        
            CheckAllIndices();
        }
	
		/// <summary>
		/// Insert values into tree delete values in the tree, making sure first/last works.
		/// </summary>
		[Test] public void DeleteFirstLast() {
			tree = new RedBlackTree<TestItem>(new DataComparer());

			InsertValidate("m", 101, DuplicatePolicy.InsertFirst);
			InsertValidate("b", 102, DuplicatePolicy.InsertFirst);
			InsertValidate("t", 103, DuplicatePolicy.InsertFirst);
			InsertValidate("m", 201, DuplicatePolicy.InsertFirst);
			InsertValidate("o", 104, DuplicatePolicy.InsertFirst);
			InsertValidate("z", 105, DuplicatePolicy.InsertFirst);
			InsertValidate("g", 106, DuplicatePolicy.InsertFirst);
			InsertValidate("b", 202, DuplicatePolicy.InsertFirst);
			InsertValidate("g", 206, DuplicatePolicy.InsertFirst);
			InsertValidate("m", 301, DuplicatePolicy.InsertFirst);
			InsertValidate("a5", 107, DuplicatePolicy.InsertFirst);
			InsertValidate("t", 203, DuplicatePolicy.InsertFirst);
			InsertValidate("c", 8, DuplicatePolicy.InsertFirst);
			InsertValidate("a2", 9, DuplicatePolicy.InsertFirst);
			InsertValidate("a7", 10, DuplicatePolicy.InsertFirst);
			InsertValidate("i", 11, DuplicatePolicy.InsertFirst);
			InsertValidate("h", 112, DuplicatePolicy.InsertFirst);
			InsertValidate("m", 401, DuplicatePolicy.InsertFirst);
			InsertValidate("z", 205, DuplicatePolicy.InsertFirst);
			InsertValidate("a2", 209, DuplicatePolicy.InsertFirst);
			InsertValidate("c", 208, DuplicatePolicy.InsertFirst);
			InsertValidate("m", 501, DuplicatePolicy.InsertFirst);
			InsertValidate("i", 211, DuplicatePolicy.InsertFirst);
			InsertValidate("h", 212, DuplicatePolicy.InsertFirst);
			InsertValidate("z", 305, DuplicatePolicy.InsertFirst);

#if DEBUG
			tree.Print();
#endif //DEBUG
			DeletePrintValidate("m", 101, false);
			DeletePrintValidate("m", 501, true);
			DeletePrintValidate("m", 201, false);
			FindFirstKey("m", 401);
			FindLastKey("m", 301);
			DeletePrintValidate("m", 401, true);
			DeletePrintValidate("m", 301, true);

			DeletePrintValidate("z", 305, true);
			DeletePrintValidate("z", 205, true);
			DeletePrintValidate("z", 105, true);
        
            CheckAllIndices();
        }

        /// <summary>
        /// Delete values in the tree, making sure global first/last works.
        /// </summary>
        [Test]
        public void GlobalDeleteFirstLast()
        {
            tree = new RedBlackTree<TestItem>(new DataComparer());

            InsertValidate("a", 101, DuplicatePolicy.InsertLast);
            InsertValidate("b", 102, DuplicatePolicy.InsertLast);
            InsertValidate("t", 103, DuplicatePolicy.InsertLast);
            InsertValidate("a", 201, DuplicatePolicy.InsertLast);
            InsertValidate("o", 104, DuplicatePolicy.InsertLast);
            InsertValidate("z", 105, DuplicatePolicy.InsertLast);
            InsertValidate("g", 106, DuplicatePolicy.InsertLast);
            InsertValidate("b", 202, DuplicatePolicy.InsertLast);
            InsertValidate("g", 206, DuplicatePolicy.InsertLast);
            InsertValidate("a", 301, DuplicatePolicy.InsertLast);
            InsertValidate("a5", 107, DuplicatePolicy.InsertLast);
            InsertValidate("t", 203, DuplicatePolicy.InsertLast);
            InsertValidate("c", 8, DuplicatePolicy.InsertLast);
            InsertValidate("a2", 9, DuplicatePolicy.InsertLast);
            InsertValidate("a7", 10, DuplicatePolicy.InsertLast);
            InsertValidate("i", 11, DuplicatePolicy.InsertLast);
            InsertValidate("h", 112, DuplicatePolicy.InsertLast);
            InsertValidate("a", 401, DuplicatePolicy.InsertLast);
            InsertValidate("z", 205, DuplicatePolicy.InsertLast);
            InsertValidate("a2", 209, DuplicatePolicy.InsertLast);
            InsertValidate("c", 208, DuplicatePolicy.InsertLast);
            InsertValidate("a", 501, DuplicatePolicy.InsertLast);
            InsertValidate("i", 211, DuplicatePolicy.InsertLast);
            InsertValidate("h", 212, DuplicatePolicy.InsertLast);
            InsertValidate("z", 305, DuplicatePolicy.InsertLast);

            GlobalDeletePrintValidate("a", 101, true);
            TestItem firstItem;
            Assert.IsTrue(tree.FirstItemInRange(tree.EntireRangeTester, out firstItem) == 0);
            Assert.AreEqual("a", firstItem.key);
            Assert.AreEqual(201, firstItem.data);
            GlobalDeletePrintValidate("a", 201, true);
            FindFirstKey("a", 301);
            GlobalDeletePrintValidate("a", 301, true);

            DeletePrintValidate("z", 305, false);
            FindLastKey("z", 205);
            DeletePrintValidate("z", 205, false);
            TestItem lastItem;
            Assert.IsTrue(tree.LastItemInRange(tree.EntireRangeTester, out lastItem) == tree.ElementCount - 1);
            Assert.AreEqual("z", lastItem.key);
            Assert.AreEqual(105, lastItem.data);
            DeletePrintValidate("z", 105, false);

            CheckAllIndices();
        }

        private void CheckAllIndices()
        {
#if DEBUG
            tree.Validate();
#endif //DEBUG

            TestItem[] items = new TestItem[tree.ElementCount];

            int i = 0;
            foreach (TestItem item in tree)
                items[i++] = item;

            for (i = tree.ElementCount - 1; i >= 0; i -= 2) {
                TestItem item = tree.GetItemByIndex(i);
                Assert.AreEqual(item.key, items[i].key);
                Assert.AreEqual(item.data, items[i].data);
            }

            for (i = tree.ElementCount - 2; i >= 0; i -= 2) {
                TestItem item = tree.GetItemByIndex(i);
                Assert.AreEqual(item.key, items[i].key);
                Assert.AreEqual(item.data, items[i].data);
            }

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

        const int LENGTH = 400;			// 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;
1234

⌨️ 快捷键说明

复制代码 Ctrl + C
搜索代码 Ctrl + F
全屏模式 F11
切换主题 Ctrl + Shift + D
显示快捷键 ?
增大字号 Ctrl + =
减小字号 Ctrl + -