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

📄 redblacktests.cs

📁 C#写的类似于STL的集合类,首先是C#编写,可以用于.net变程.
💻 CS
📖 第 1 页 / 共 4 页
字号:
🔍
1234 
            t.Insert(1, DuplicatePolicy.ReplaceFirst, out dummy);
            t.Insert(5, DuplicatePolicy.ReplaceFirst, out dummy);
            t.Insert(3, DuplicatePolicy.ReplaceFirst, out dummy);
            t.Insert(2, DuplicatePolicy.ReplaceFirst, out dummy);
            t.Insert(2, DuplicatePolicy.ReplaceFirst, out dummy);
            t.Insert(3, DuplicatePolicy.ReplaceFirst, out dummy);
            t.Insert(4, DuplicatePolicy.ReplaceFirst, out dummy);

            bool b;
			int d;

#if DEBUG
			t.Print();
#endif //DEBUG

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

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

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

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

			b = t.Delete(3, true, 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()
		{
			tree = new RedBlackTree<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("c");

			string[] keys = new string[] {"a2", "a5", "a7",	"b",	"c",	"c", "g",	"h",	"i", "m",	"o", "o", "p", "t" };
			int i = 0;
			foreach (TestItem item in tree)
			{
				Assert.AreEqual(item.key, keys[i], "Keys weren't enumerated in order");
				++i;
			}

			i = 0;

			foreach (TestItem item in tree.EnumerateRangeReversed(tree.EntireRangeTester))
			{
				Assert.AreEqual(item.key, keys[tree.ElementCount - i - 1], "Keys weren't enumerated in reverse order");
				++i;
			}
		
		}

        private void CheckEnumerateRange(RedBlackTree<TestItem> tree, bool useFirst, string first, bool useLast, string last, string[] keys)
        {
            int i = 0;
            TestItem firstItem, lastItem;

            foreach (TestItem item in tree.EnumerateRange(tree.BoundedRangeTester(useFirst, new TestItem(first), useLast, new TestItem(last)))) {
                Assert.AreEqual(item.key, keys[i], "Keys weren't enumerated in order");
                ++i;
            }

            i = 0;
            foreach (TestItem item in tree.EnumerateRangeReversed(tree.BoundedRangeTester(useFirst, new TestItem(first), useLast, new TestItem(last)))) {
                Assert.AreEqual(item.key, keys[keys.Length - i - 1], "Keys weren't enumerated in reverse order");
                ++i;
            }

            if (i != 0) {
                int foundFirst = tree.FirstItemInRange(tree.BoundedRangeTester(useFirst, new TestItem(first), useLast, new TestItem(last)), out firstItem);
                Assert.IsTrue(foundFirst >= 0);
                Assert.AreEqual(keys[0], firstItem.key);
                Assert.AreEqual(keys[0], tree.GetItemByIndex(foundFirst).key);
                int foundLast = tree.LastItemInRange(tree.BoundedRangeTester(useFirst, new TestItem(first), useLast, new TestItem(last)), out lastItem);
                Assert.IsTrue(foundLast >= 0);
                Assert.AreEqual(keys[i-1], lastItem.key);
                Assert.AreEqual(keys[i-1], tree.GetItemByIndex(foundLast).key);
                Assert.AreEqual(i, foundLast - foundFirst + 1);
            }
            else {
                Assert.IsTrue(tree.FirstItemInRange(tree.BoundedRangeTester(useFirst, new TestItem(first), useLast, new TestItem(last)), out firstItem) < 0);
                Assert.IsTrue(tree.LastItemInRange(tree.BoundedRangeTester(useFirst, new TestItem(first), useLast, new TestItem(last)), out lastItem) < 0);
            }

            Assert.AreEqual(keys.Length, tree.CountRange(tree.BoundedRangeTester(useFirst, new TestItem(first), useLast, new TestItem(last))));
        }

        [Test]
        public void EnumerateAndCountRange()
        {
            tree = new RedBlackTree<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("c");

            CheckEnumerateRange(tree, true, "a7", true, "o", new string[] { "a7", "b", "c", "c", "g", "h", "i", "m" });
            CheckEnumerateRange(tree, true, "c", true, "c", new string[] { });
            CheckEnumerateRange(tree, true, "c", true, "c1", new string[] { "c", "c" });
            CheckEnumerateRange(tree, true, "a", true, "a1", new string[0] { });
            CheckEnumerateRange(tree, true, "j", true, "k", new string[0] { });
            CheckEnumerateRange(tree, true, "z", true, "a", new string[0] { });
            CheckEnumerateRange(tree, true, "h5", true, "z", new string[] { "i", "m", "o", "o", "p", "t" });
            CheckEnumerateRange(tree, true, "a3", true, "a8", new string[] { "a5", "a7" });
            CheckEnumerateRange(tree, true, "a", true, "z", new string[] { "a2", "a5", "a7", "b", "c", "c", "g", "h", "i", "m", "o", "o", "p", "t" });
            CheckEnumerateRange(tree, false, "m", false, "n", new string[] { "a2", "a5", "a7", "b", "c", "c", "g", "h", "i", "m", "o", "o", "p", "t" });
            CheckEnumerateRange(tree, true, "c", false, "n", new string[] { "c", "c", "g", "h", "i", "m", "o", "o", "p", "t" });
            CheckEnumerateRange(tree, true, "c1", false, "n", new string[] { "g", "h", "i", "m", "o", "o", "p", "t" });
            CheckEnumerateRange(tree, false, "m", true, "o", new string[] { "a2", "a5", "a7", "b", "c", "c", "g", "h", "i", "m" });
            CheckEnumerateRange(tree, false, "m", true, "o3", new string[] { "a2", "a5", "a7", "b", "c", "c", "g", "h", "i", "m", "o", "o"});
        }

        private void CheckEnumerateRange2(RedBlackTree<TestItem> tree, bool firstInclusive, string first, bool lastInclusive, string last, System.Collections.Generic.IList<string> keys)
        {
            int i = 0;
            TestItem firstItem, lastItem;

            foreach (TestItem item in tree.EnumerateRange(tree.DoubleBoundedRangeTester(new TestItem(first), firstInclusive, new TestItem(last), lastInclusive))) {
                Assert.AreEqual(item.key, keys[i], "Keys weren't enumerated in order");
                ++i;
            }

            i = 0;
            foreach (TestItem item in tree.EnumerateRangeReversed(tree.DoubleBoundedRangeTester(new TestItem(first), firstInclusive, new TestItem(last), lastInclusive))) {
                Assert.AreEqual(item.key, keys[keys.Count - i - 1], "Keys weren't enumerated in reverse order");
                ++i;
            }

            if (i != 0) {
                int foundFirst = tree.FirstItemInRange(tree.DoubleBoundedRangeTester(new TestItem(first), firstInclusive, new TestItem(last), lastInclusive), out firstItem);
                Assert.IsTrue(foundFirst >= 0);
                Assert.AreEqual(keys[0], firstItem.key);
                Assert.AreEqual(keys[0], tree.GetItemByIndex(foundFirst).key);
                int foundLast = tree.LastItemInRange(tree.DoubleBoundedRangeTester(new TestItem(first), firstInclusive, new TestItem(last), lastInclusive), out lastItem);
                Assert.IsTrue(foundLast >= 0);
                Assert.AreEqual(keys[i - 1], lastItem.key);
                Assert.AreEqual(keys[i - 1], tree.GetItemByIndex(foundLast).key);
                Assert.AreEqual(i, foundLast - foundFirst + 1);
            }
            else {
                Assert.IsTrue(tree.FirstItemInRange(tree.DoubleBoundedRangeTester(new TestItem(first), firstInclusive, new TestItem(last), lastInclusive), out firstItem) < 0);
                Assert.IsTrue(tree.LastItemInRange(tree.DoubleBoundedRangeTester(new TestItem(first), firstInclusive, new TestItem(last), lastInclusive), out lastItem) < 0);
            }

            Assert.AreEqual(keys.Count, tree.CountRange(tree.DoubleBoundedRangeTester(new TestItem(first), firstInclusive, new TestItem(last), lastInclusive)));
        }

        [Test]
        public void EnumerateAndCountRange2()
        {
            Random rand = new Random(112);
            for (int iter = 0; iter < ITERATIONS; ++iter) {
                tree = new RedBlackTree<TestItem>(new DataComparer());
                int[] a = CreateRandomArray(iter, LENGTH, LENGTH * 10, false);
                InsertArray(a, DuplicatePolicy.InsertLast);

                string[] strs = Array.ConvertAll<int, string>(a, StringFromInt);
                Array.Sort(strs);

                for (int k = 0; k < 10; ++k) {
                    string lower, upper;
                    do {
                        lower = StringFromInt(rand.Next(LENGTH * 10));
                        upper = StringFromInt(rand.Next(LENGTH * 10));
                    } while (string.Compare(lower, upper) >= 0);

                    bool lowerInclusive = (rand.Next(2) == 0);
                    bool upperInclusive = (rand.Next(2) == 0);

                    int lowerIndex, upperIndex;
                    if (lowerInclusive)
                        lowerIndex = Algorithms.FindFirstIndexWhere(strs, delegate(string x) { return string.Compare(x, lower) >= 0; });
                    else
                        lowerIndex = Algorithms.FindFirstIndexWhere(strs, delegate(string x) { return string.Compare(x, lower) > 0; });
                    if (upperInclusive)
                        upperIndex = Algorithms.FindLastIndexWhere(strs, delegate(string x) { return string.Compare(x, upper) <= 0; });
                    else
                        upperIndex = Algorithms.FindLastIndexWhere(strs, delegate(string x) { return string.Compare(x, upper) < 0; });

                    CheckEnumerateRange2(tree, lowerInclusive, lower, upperInclusive, upper, Algorithms.Range(strs, lowerIndex, upperIndex - lowerIndex + 1));
                }
            }
        }

        private void CheckDeleteRange(RedBlackTree<TestItem> tree, bool useFirst, string first, bool useLast, string last, string[] keys)
        {
            int i = 0;
            int count = tree.ElementCount;
            int deletedCount = tree.DeleteRange(tree.BoundedRangeTester(useFirst, new TestItem(first), useLast, new TestItem(last)));
            Assert.AreEqual(keys.Length, count - deletedCount);

            foreach (TestItem item in tree) {
                Assert.AreEqual(item.key, keys[i], "Keys weren't enumerated in order");
                ++i;
            }
        }

        [Test]
        public void DeleteRange()
        {
            tree = new RedBlackTree<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("c");

            CheckDeleteRange(tree.Clone(), true, "a7", true, "o", new string[] { "a2", "a5", "o", "o", "p", "t" });
            CheckDeleteRange(tree.Clone(), true, "c", true, "c", new string[] { "a2", "a5", "a7", "b", "c", "c", "g", "h", "i", "m", "o", "o", "p", "t" });
            CheckDeleteRange(tree.Clone(), true, "c", true, "c1", new string[] { "a2", "a5", "a7", "b", "g", "h", "i", "m", "o", "o", "p", "t" });
            CheckDeleteRange(tree.Clone(), true, "a", true, "a1", new string[] { "a2", "a5", "a7", "b", "c", "c", "g", "h", "i", "m", "o", "o", "p", "t" });
            CheckDeleteRange(tree.Clone(), true, "j", true, "k", new string[] { "a2", "a5", "a7", "b", "c", "c", "g", "h", "i", "m", "o", "o", "p", "t" });
            CheckDeleteRange(tree.Clone(), true, "z", true, "a", new string[] { "a2", "a5", "a7", "b", "c", "c", "g", "h", "i", "m", "o", "o", "p", "t" });
            CheckDeleteRange(tree.Clone(), true, "h5", true, "z", new string[] { "a2", "a5", "a7", "b", "c", "c", "g", "h" });
            CheckDeleteRange(tree.Clone(), true, "a3", true, "a8", new string[] { "a2", "b", "c", "c", "g", "h", "i", "m", "o", "o", "p", "t" });
            CheckDeleteRange(tree.Clone(), true, "a", true, "z", new string[] { });
            CheckDeleteRange(tree.Clone(), false, "m", false, "n", new string[] { });
            CheckDeleteRange(tree.Clone(), true, "c", false, "n", new string[] { "a2", "a5", "a7", "b" });
            CheckDeleteRange(tree.Clone(), true, "c1", false, "n", new string[] { "a2", "a5", "a7", "b", "c", "c" });
            CheckDeleteRange(tree.Clone(), false, "m", true, "o", new string[] { "o", "o", "p", "t" });
            CheckDeleteRange(tree.Clone(), false, "m", true, "o3", new string[] { "p", "t" });
        }

        [Test]
        public void CountEqual()
        {
            tree = new RedBlackTree<TestItem>(new DataComparer());
            InsertValidate("m");
            InsertValidate("c");
            InsertValidate("b");
            InsertValidate("c");
            InsertValidate("t");
            InsertValidate("o");
            InsertValidate("z");
            InsertValidate("g");
            InsertValidate("a5");
            InsertValidate("c");
            InsertValidate("a2");
            InsertValidate("a7");
            InsertValidate("c");
            InsertValidate("i");
            InsertValidate("h");
            InsertValidate("o");
            InsertValidate("c");

            Assert.AreEqual(5, tree.CountRange(tree.EqualRangeTester(new TestItem("c"))));
            Assert.AreEqual(2, tree.CountRange(tree.EqualRangeTester(new TestItem("o"))));
            Assert.AreEqual(1, tree.CountRange(tree.EqualRangeTester(new TestItem("z"))));
            Assert.AreEqual(1, tree.CountRange(tree.EqualRangeTester(new TestItem("m"))));
            Assert.AreEqual(1, tree.CountRange(tree.EqualRangeTester(new TestItem("a2"))));
            Assert.AreEqual(0, tree.CountRange(tree.EqualRangeTester(new TestItem("e"))));
        }

        [Test]
        public void EnumerateEqual()
        {
            tree = new RedBlackTree<TestItem>(new DataComparer());
            InsertValidate("m", 1);
            InsertValidate("c", 2);
            InsertValidate("b", 3);
            InsertValidate("c", 4);
            InsertValidate("t", 5);
            InsertValidate("o", 6);
            InsertValidate("z", 7);
            InsertValidate("g", 8);
            InsertValidate("a5", 9);
            InsertValidate("c", 10);
            InsertValidate("a2", 11);
            InsertValidate("a7", 12);
            InsertValidate("c", 13);
            InsertValidate("i", 14);
            InsertValidate("h", 15);
            InsertValidate("o", 16);
            InsertValidate("c", 17);

            InterfaceTests.TestEnumerableElements(tree.EnumerateRange(tree.EqualRangeTester(new TestItem("c", 0))),
                new TestItem[] { new TestItem("c", 2), new TestItem("c", 4), new TestItem("c", 10), new TestItem("c", 13), new TestItem("c", 17) });
            InterfaceTests.TestEnumerableElements(tree.EnumerateRange(tree.EqualRangeTester(new TestItem("o", 0))),
                new TestItem[] { new TestItem("o", 6), new TestItem("o", 16)});
            InterfaceTests.TestEnumerableElements(tree.EnumerateRange(tree.EqualRangeTester(new TestItem("g", 0))),
                new TestItem[] { new TestItem("g", 8) });
            InterfaceTests.TestEnumerableElements(tree.EnumerateRange(tree.EqualRangeTester(new TestItem("qqq", 0))),
                new TestItem[] {  });
        }

        [Test]
        public void FindIndex()
        {
            tree = new RedBlackTree<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("c");

            int index;

            index = tree.FindIndex(new TestItem("a7"), true);
            Assert.AreEqual(2, index);
            index = tree.FindIndex(new TestItem("a7"), false);
            Assert.AreEqual(2, index);

            index = tree.FindIndex(new TestItem("a2"), true);
            Assert.AreEqual(0, index);
            index = tree.FindIndex(new TestItem("a2"), false);
            Assert.AreEqual(0, index);

            index = tree.FindIndex(new TestItem("t"), true);
            Assert.AreEqual(13, index);
            index = tree.FindIndex(new TestItem("t"), false);
            Assert.AreEqual(13, index);

            index = tree.FindIndex(new TestItem("n"), true);
            Assert.AreEqual(-1, index);
            index = tree.FindIndex(new TestItem("n"), false);
            Assert.AreEqual(-1, index);

            index = tree.FindIndex(new TestItem("o"), true);
            Assert.AreEqual(10, index);
            index = tree.FindIndex(new TestItem("o"), false);
1234

⌨️ 快捷键说明

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