-#if NET_2_0\r
/*\r
- Copyright (c) 2003-2004 Niels Kokholm <kokholm@itu.dk> and Peter Sestoft <sestoft@dina.kvl.dk>\r
+ Copyright (c) 2003-2006 Niels Kokholm and Peter Sestoft\r
Permission is hereby granted, free of charge, to any person obtaining a copy\r
of this software and associated documentation files (the "Software"), to deal\r
in the Software without restriction, including without limitation the rights\r
using System;\r
using C5;\r
using NUnit.Framework;\r
-using MSG=System.Collections.Generic;\r
+using SCG = System.Collections.Generic;\r
\r
\r
-namespace nunit.trees.TreeBag\r
+namespace C5UnitTests.trees.TreeBag\r
{\r
- [TestFixture]\r
- public class Combined\r
- {\r
- private IIndexedSorted<KeyValuePair<int,int>> lst;\r
-\r
-\r
- [SetUp]\r
- public void Init()\r
- {\r
- lst = new TreeBag<KeyValuePair<int,int>>(new KeyValuePairComparer<int,int>(new IC()));\r
- for (int i = 0; i < 10; i++)\r
- lst.Add(new KeyValuePair<int,int>(i, i + 30));\r
- }\r
-\r
-\r
- [TearDown]\r
- public void Dispose() { lst = null; }\r
-\r
-\r
- [Test]\r
- public void Find()\r
- {\r
- KeyValuePair<int,int> p = new KeyValuePair<int,int>(3, 78);\r
-\r
- Assert.IsTrue(lst.Find(ref p));\r
- Assert.AreEqual(3, p.key);\r
- Assert.AreEqual(33, p.value);\r
- p = new KeyValuePair<int,int>(13, 78);\r
- Assert.IsFalse(lst.Find(ref p));\r
- }\r
-\r
-\r
- [Test] \r
- public void FindOrAdd()\r
- {\r
- KeyValuePair<int,int> p = new KeyValuePair<int,int>(3, 78);\r
-\r
- Assert.IsTrue(lst.FindOrAdd(ref p));\r
- Assert.AreEqual(3, p.key);\r
- Assert.AreEqual(33, p.value);\r
- p = new KeyValuePair<int,int>(13, 79);\r
- Assert.IsFalse(lst.FindOrAdd(ref p));\r
- Assert.AreEqual(13, lst[11].key);\r
- Assert.AreEqual(79, lst[11].value);\r
- }\r
-\r
-\r
- [Test]\r
- public void Update()\r
- {\r
- KeyValuePair<int,int> p = new KeyValuePair<int,int>(3, 78);\r
-\r
- Assert.IsTrue(lst.Update(p));\r
- Assert.AreEqual(3, lst[3].key);\r
- Assert.AreEqual(78, lst[3].value);\r
- p = new KeyValuePair<int,int>(13, 78);\r
- Assert.IsFalse(lst.Update(p));\r
- }\r
-\r
-\r
- [Test]\r
- public void UpdateOrAdd()\r
- {\r
- KeyValuePair<int,int> p = new KeyValuePair<int,int>(3, 78);\r
-\r
- Assert.IsTrue(lst.UpdateOrAdd(p));\r
- Assert.AreEqual(3, lst[3].key);\r
- Assert.AreEqual(78, lst[3].value);\r
- p = new KeyValuePair<int,int>(13, 79);\r
- Assert.IsFalse(lst.UpdateOrAdd(p));\r
- Assert.AreEqual(13, lst[11].key);\r
- Assert.AreEqual(79, lst[11].value);\r
- }\r
-\r
-\r
- [Test]\r
- public void RemoveWithReturn()\r
- {\r
- KeyValuePair<int,int> p = new KeyValuePair<int,int>(3, 78);\r
-\r
- Assert.IsTrue(lst.RemoveWithReturn(ref p));\r
- Assert.AreEqual(3, p.key);\r
- Assert.AreEqual(33, p.value);\r
- Assert.AreEqual(4, lst[3].key);\r
- Assert.AreEqual(34, lst[3].value);\r
- p = new KeyValuePair<int,int>(13, 78);\r
- Assert.IsFalse(lst.RemoveWithReturn(ref p));\r
- }\r
- }\r
-\r
-\r
- [TestFixture]\r
- public class Simple\r
- {\r
- private TreeBag<string> bag;\r
-\r
-\r
- [SetUp]\r
- public void Init()\r
- {\r
- bag = new TreeBag<string>(new SC());\r
- }\r
-\r
-\r
- [TearDown]\r
- public void Dispose()\r
- {\r
- bag = null;\r
- }\r
-\r
- [Test]\r
- public void Initial()\r
- {\r
- bool res;\r
-\r
- Assert.IsFalse(bag.IsReadOnly);\r
- Assert.AreEqual(0, bag.Count, "new bag should be empty");\r
- Assert.AreEqual(0, bag.ContainsCount("A"));\r
- Assert.AreEqual(0, bag.ContainsCount("B"));\r
- Assert.AreEqual(0, bag.ContainsCount("C"));\r
- Assert.IsFalse(bag.Contains("A"));\r
- Assert.IsFalse(bag.Contains("B"));\r
- Assert.IsFalse(bag.Contains("C"));\r
- bag.Add("A");\r
- Assert.AreEqual(1, bag.Count);\r
- Assert.AreEqual(1, bag.ContainsCount("A"));\r
- Assert.AreEqual(0, bag.ContainsCount("B"));\r
- Assert.AreEqual(0, bag.ContainsCount("C"));\r
- Assert.IsTrue(bag.Contains("A"));\r
- Assert.IsFalse(bag.Contains("B"));\r
- Assert.IsFalse(bag.Contains("C"));\r
- bag.Add("C");\r
- Assert.AreEqual(2, bag.Count);\r
- Assert.AreEqual(1, bag.ContainsCount("A"));\r
- Assert.AreEqual(0, bag.ContainsCount("B"));\r
- Assert.AreEqual(1, bag.ContainsCount("C"));\r
- Assert.IsTrue(bag.Contains("A"));\r
- Assert.IsFalse(bag.Contains("B"));\r
- Assert.IsTrue(bag.Contains("C"));\r
- bag.Add("C");\r
- Assert.AreEqual(3, bag.Count);\r
- Assert.AreEqual(1, bag.ContainsCount("A"));\r
- Assert.AreEqual(0, bag.ContainsCount("B"));\r
- Assert.AreEqual(2, bag.ContainsCount("C"));\r
- Assert.IsTrue(bag.Contains("A"));\r
- Assert.IsFalse(bag.Contains("B"));\r
- Assert.IsTrue(bag.Contains("C"));\r
- bag.Add("B");\r
- bag.Add("C");\r
- Assert.AreEqual(5, bag.Count);\r
- Assert.AreEqual(1, bag.ContainsCount("A"));\r
- Assert.AreEqual(1, bag.ContainsCount("B"));\r
- Assert.AreEqual(3, bag.ContainsCount("C"));\r
- Assert.IsTrue(bag.Contains("A"));\r
- Assert.IsTrue(bag.Contains("B"));\r
- Assert.IsTrue(bag.Contains("C"));\r
- res = bag.Remove("C");\r
- Assert.AreEqual(4, bag.Count);\r
- Assert.AreEqual(1, bag.ContainsCount("A"));\r
- Assert.AreEqual(1, bag.ContainsCount("B"));\r
- Assert.AreEqual(2, bag.ContainsCount("C"));\r
- Assert.IsTrue(bag.Contains("A"));\r
- Assert.IsTrue(bag.Contains("B"));\r
- Assert.IsTrue(bag.Contains("C"));\r
- res = bag.Remove("A");\r
- Assert.AreEqual(3, bag.Count);\r
- Assert.AreEqual(0, bag.ContainsCount("A"));\r
- Assert.AreEqual(1, bag.ContainsCount("B"));\r
- Assert.AreEqual(2, bag.ContainsCount("C"));\r
- Assert.IsFalse(bag.Contains("A"));\r
- Assert.IsTrue(bag.Contains("B"));\r
- Assert.IsTrue(bag.Contains("C"));\r
- bag.RemoveAllCopies("C");\r
- Assert.AreEqual(1, bag.Count);\r
- Assert.AreEqual(0, bag.ContainsCount("A"));\r
- Assert.AreEqual(1, bag.ContainsCount("B"));\r
- Assert.AreEqual(0, bag.ContainsCount("C"));\r
- Assert.IsFalse(bag.Contains("A"));\r
- Assert.IsTrue(bag.Contains("B"));\r
- Assert.IsFalse(bag.Contains("C"));\r
- Assert.IsFalse(bag.Contains("Z"));\r
- Assert.IsFalse(bag.Remove("Z"));\r
- bag.RemoveAllCopies("Z");\r
- Assert.AreEqual(1, bag.Count);\r
- Assert.AreEqual(0, bag.ContainsCount("A"));\r
- Assert.AreEqual(1, bag.ContainsCount("B"));\r
- Assert.AreEqual(0, bag.ContainsCount("C"));\r
- Assert.IsFalse(bag.Contains("A"));\r
- Assert.IsTrue(bag.Contains("B"));\r
- Assert.IsFalse(bag.Contains("C"));\r
- Assert.IsFalse(bag.Contains("Z"));\r
- }\r
- }\r
-\r
- [TestFixture]\r
- public class FindOrAdd\r
- {\r
- private TreeBag<KeyValuePair<int,string>> bag;\r
-\r
-\r
- [SetUp]\r
- public void Init()\r
- {\r
- bag = new TreeBag<KeyValuePair<int,string>>(new KeyValuePairComparer<int,string>(new IC()));\r
- }\r
-\r
-\r
- [TearDown]\r
- public void Dispose()\r
- {\r
- bag = null;\r
- }\r
-\r
-\r
- [Test]\r
- public void Test()\r
- {\r
- KeyValuePair<int,string> p = new KeyValuePair<int,string>(3,"tre");\r
- Assert.IsFalse(bag.FindOrAdd(ref p));\r
- p.value = "drei";\r
- Assert.IsTrue(bag.FindOrAdd(ref p));\r
- Assert.AreEqual("tre", p.value);\r
- p.value = "three";\r
- Assert.AreEqual(2, bag.ContainsCount(p));\r
- Assert.AreEqual("tre", bag[0].value);\r
- }\r
- }\r
-\r
-\r
- [TestFixture]\r
- public class Enumerators\r
- {\r
- private TreeBag<string> bag;\r
-\r
- private MSG.IEnumerator<string> bagenum;\r
-\r
-\r
- [SetUp]\r
- public void Init()\r
- {\r
- bag = new TreeBag<string>(new SC());\r
- foreach (string s in new string[] { "A", "B", "A", "A", "B", "C", "D", "B" })\r
- bag.Add(s);\r
-\r
- bagenum = bag.GetEnumerator();\r
- }\r
-\r
-\r
- [TearDown]\r
- public void Dispose()\r
- {\r
- bagenum = null;\r
- bag = null;\r
- }\r
-\r
-\r
- [Test]\r
- [ExpectedException(typeof(InvalidOperationException))]\r
- public void MoveNextOnModified()\r
- {\r
- //TODO: also problem before first MoveNext!!!!!!!!!!\r
- bagenum.MoveNext();\r
- bag.Add("T");\r
- bagenum.MoveNext();\r
- }\r
-\r
-\r
- [Test]\r
- public void NormalUse()\r
- {\r
- Assert.IsTrue(bagenum.MoveNext());\r
- Assert.AreEqual(bagenum.Current, "A");\r
- Assert.IsTrue(bagenum.MoveNext());\r
- Assert.AreEqual(bagenum.Current, "A");\r
- Assert.IsTrue(bagenum.MoveNext());\r
- Assert.AreEqual(bagenum.Current, "A");\r
- Assert.IsTrue(bagenum.MoveNext());\r
- Assert.AreEqual(bagenum.Current, "B");\r
- Assert.IsTrue(bagenum.MoveNext());\r
- Assert.AreEqual(bagenum.Current, "B");\r
- Assert.IsTrue(bagenum.MoveNext());\r
- Assert.AreEqual(bagenum.Current, "B");\r
- Assert.IsTrue(bagenum.MoveNext());\r
- Assert.AreEqual(bagenum.Current, "C");\r
- Assert.IsTrue(bagenum.MoveNext());\r
- Assert.AreEqual(bagenum.Current, "D");\r
- Assert.IsFalse(bagenum.MoveNext());\r
- }\r
- }\r
-\r
- [TestFixture]\r
- public class Ranges\r
- {\r
- private TreeBag<int> tree;\r
-\r
- private IComparer<int> c;\r
-\r
-\r
- [SetUp]\r
- public void Init()\r
- {\r
- c = new IC();\r
- tree = new TreeBag<int>(c);\r
- for (int i = 1; i <= 10; i++)\r
- {\r
- tree.Add(i * 2);tree.Add(i);\r
- }\r
- }\r
-\r
-\r
- [Test]\r
- public void Enumerator()\r
- {\r
- MSG.IEnumerator<int> e = tree.RangeFromTo(5, 17).GetEnumerator();\r
- int i = 0;\r
- int[] all = new int[] { 5, 6, 6, 7, 8, 8, 9, 10, 10, 12, 14, 16 };\r
- while (e.MoveNext())\r
- {\r
- Assert.AreEqual(all[i++], e.Current);\r
- }\r
-\r
- Assert.AreEqual(12, i);\r
- }\r
-\r
-\r
- [Test]\r
- [ExpectedException(typeof(InvalidOperationException))]\r
- public void Enumerator2()\r
- {\r
- MSG.IEnumerator<int> e = tree.RangeFromTo(5, 17).GetEnumerator();\r
- int i = e.Current;\r
- }\r
-\r
-\r
- [Test]\r
- [ExpectedException(typeof(InvalidOperationException))]\r
- public void Enumerator3()\r
- {\r
- MSG.IEnumerator<int> e = tree.RangeFromTo(5, 17).GetEnumerator();\r
-\r
- while (e.MoveNext());\r
-\r
- int i = e.Current;\r
- }\r
-\r
-\r
- [Test]\r
- public void Remove()\r
- {\r
- int[] all = new int[] { 1, 2, 2, 3, 4, 4, 5, 6, 6, 7, 8, 8, 9, 10, 10, 12, 14, 16, 18, 20 };\r
-\r
- tree.RemoveRangeFrom(18);\r
- Assert.IsTrue(IC.eq(tree, new int[] { 1, 2, 2, 3, 4, 4, 5, 6, 6, 7, 8, 8, 9, 10, 10, 12, 14, 16 }));\r
- tree.RemoveRangeFrom(28);\r
- Assert.IsTrue(IC.eq(tree, new int[] { 1, 2, 2, 3, 4, 4, 5, 6, 6, 7, 8, 8, 9, 10, 10, 12, 14, 16 }));\r
- tree.RemoveRangeFrom(1);\r
- Assert.IsTrue(IC.eq(tree));\r
- foreach (int i in all) tree.Add(i);\r
-\r
- tree.RemoveRangeTo(10);\r
- Assert.IsTrue(IC.eq(tree, new int[] { 10, 10, 12, 14, 16, 18, 20 }));\r
- tree.RemoveRangeTo(2);\r
- Assert.IsTrue(IC.eq(tree, new int[] { 10, 10, 12, 14, 16, 18, 20 }));\r
- tree.RemoveRangeTo(21);\r
- Assert.IsTrue(IC.eq(tree));\r
- foreach (int i in all) tree.Add(i);\r
-\r
- tree.RemoveRangeFromTo(4, 8);\r
- Assert.IsTrue(IC.eq(tree, 1, 2, 2, 3, 8, 8, 9, 10, 10, 12, 14, 16, 18, 20));\r
- tree.RemoveRangeFromTo(14, 28);\r
- Assert.IsTrue(IC.eq(tree, 1, 2, 2, 3, 8, 8, 9, 10, 10, 12));\r
- tree.RemoveRangeFromTo(0, 9);\r
- Assert.IsTrue(IC.eq(tree, 9, 10, 10, 12));\r
- tree.RemoveRangeFromTo(0, 81);\r
- Assert.IsTrue(IC.eq(tree));\r
- }\r
-\r
-\r
- [Test]\r
- public void Normal()\r
- {\r
- int[] all = new int[] { 1, 2, 2, 3, 4, 4, 5, 6, 6, 7, 8, 8, 9, 10, 10, 12, 14, 16, 18, 20 };\r
-\r
- Assert.IsTrue(IC.eq(tree, all));\r
- Assert.IsTrue(IC.eq(tree.RangeAll(), all));\r
- Assert.AreEqual(20, tree.RangeAll().Count);\r
- Assert.IsTrue(IC.eq(tree.RangeFrom(11), new int[] { 12, 14, 16, 18, 20 }));\r
- Assert.AreEqual(5, tree.RangeFrom(11).Count);\r
- Assert.IsTrue(IC.eq(tree.RangeFrom(12), new int[] { 12, 14, 16, 18, 20 }));\r
- Assert.IsTrue(IC.eq(tree.RangeFrom(1), all));\r
- Assert.IsTrue(IC.eq(tree.RangeFrom(0), all));\r
- Assert.IsTrue(IC.eq(tree.RangeFrom(21), new int[] { }));\r
- Assert.IsTrue(IC.eq(tree.RangeFrom(20), new int[] { 20 }));\r
- Assert.IsTrue(IC.eq(tree.RangeTo(8), new int[] { 1, 2, 2, 3, 4, 4, 5, 6, 6, 7 }));\r
- Assert.IsTrue(IC.eq(tree.RangeTo(7), new int[] { 1, 2, 2, 3, 4, 4, 5, 6, 6 }));\r
- Assert.AreEqual(9, tree.RangeTo(7).Count);\r
- Assert.IsTrue(IC.eq(tree.RangeTo(1), new int[] { }));\r
- Assert.IsTrue(IC.eq(tree.RangeTo(0), new int[] { }));\r
- Assert.IsTrue(IC.eq(tree.RangeTo(3), new int[] { 1, 2,2 }));\r
- Assert.IsTrue(IC.eq(tree.RangeTo(20), new int[] { 1, 2, 2, 3, 4, 4, 5, 6, 6, 7, 8, 8, 9, 10, 10, 12, 14, 16, 18 }));\r
- Assert.IsTrue(IC.eq(tree.RangeTo(21), all));\r
- Assert.IsTrue(IC.eq(tree.RangeFromTo(7, 12), new int[] { 7, 8, 8, 9, 10, 10 }));\r
- Assert.IsTrue(IC.eq(tree.RangeFromTo(6, 11), new int[] { 6, 6, 7, 8, 8, 9, 10, 10 }));\r
- Assert.IsTrue(IC.eq(tree.RangeFromTo(1, 12), new int[] { 1, 2, 2, 3, 4, 4, 5, 6, 6, 7, 8, 8, 9, 10, 10 }));\r
- Assert.AreEqual(15, tree.RangeFromTo(1, 12).Count);\r
- Assert.IsTrue(IC.eq(tree.RangeFromTo(2, 12), new int[] { 2, 2, 3, 4, 4, 5, 6, 6, 7, 8, 8, 9, 10, 10 }));\r
- Assert.IsTrue(IC.eq(tree.RangeFromTo(6, 21), new int[] { 6, 6, 7, 8, 8, 9, 10, 10, 12, 14, 16, 18, 20 }));\r
- Assert.IsTrue(IC.eq(tree.RangeFromTo(6, 20), new int[] { 6, 6, 7, 8, 8, 9, 10, 10, 12, 14, 16, 18 }));\r
- }\r
-\r
-\r
- [Test]\r
- public void Backwards()\r
- {\r
- int[] all = new int[] { 1, 2, 2, 3, 4, 4, 5, 6, 6, 7, 8, 8, 9, 10, 10, 12, 14, 16, 18, 20 };\r
- int[] lla = new int[] { 20, 18, 16, 14, 12, 10, 10, 9, 8, 8, 7, 6, 6, 5, 4, 4, 3, 2, 2, 1 };\r
-\r
- Assert.IsTrue(IC.eq(tree, all));\r
- Assert.IsTrue(IC.eq(tree.RangeAll().Backwards(), lla));\r
- Assert.IsTrue(IC.eq(tree.RangeFrom(11).Backwards(), new int[] { 20, 18, 16, 14, 12 }));\r
- Assert.IsTrue(IC.eq(tree.RangeFrom(12).Backwards(), new int[] { 20, 18, 16, 14, 12 }));\r
- Assert.IsTrue(IC.eq(tree.RangeFrom(1).Backwards(), lla));\r
- Assert.IsTrue(IC.eq(tree.RangeFrom(0).Backwards(), lla));\r
- Assert.IsTrue(IC.eq(tree.RangeFrom(21).Backwards(), new int[] { }));\r
- Assert.IsTrue(IC.eq(tree.RangeFrom(20).Backwards(), new int[] { 20 }));\r
- Assert.IsTrue(IC.eq(tree.RangeTo(8).Backwards(), new int[] { 7, 6, 6, 5, 4, 4, 3, 2, 2, 1 }));\r
- Assert.IsTrue(IC.eq(tree.RangeTo(7).Backwards(), new int[] { 6, 6, 5, 4, 4, 3, 2, 2, 1 }));\r
- Assert.IsTrue(IC.eq(tree.RangeTo(1).Backwards(), new int[] { }));\r
- Assert.IsTrue(IC.eq(tree.RangeTo(0).Backwards(), new int[] { }));\r
- Assert.IsTrue(IC.eq(tree.RangeTo(3).Backwards(), new int[] { 2, 2, 1 }));\r
- Assert.IsTrue(IC.eq(tree.RangeTo(20).Backwards(), new int[] { 18, 16, 14, 12, 10, 10, 9, 8, 8, 7, 6, 6, 5, 4, 4, 3, 2, 2, 1 }));\r
- Assert.IsTrue(IC.eq(tree.RangeTo(21).Backwards(), lla));\r
- Assert.IsTrue(IC.eq(tree.RangeFromTo(7, 12).Backwards(), new int[] { 10, 10, 9, 8, 8, 7 }));\r
- Assert.IsTrue(IC.eq(tree.RangeFromTo(6, 11).Backwards(), new int[] { 10, 10, 9, 8, 8, 7, 6, 6 }));\r
- Assert.IsTrue(IC.eq(tree.RangeFromTo(0, 12).Backwards(), new int[] { 10, 10, 9, 8, 8, 7, 6, 6, 5, 4, 4, 3, 2, 2, 1 }));\r
- Assert.IsTrue(IC.eq(tree.RangeFromTo(1, 12).Backwards(), new int[] { 10, 10, 9, 8, 8, 7, 6, 6, 5, 4, 4, 3, 2, 2, 1 }));\r
- Assert.IsTrue(IC.eq(tree.RangeFromTo(6, 21).Backwards(), new int[] { 20, 18, 16, 14, 12, 10, 10, 9, 8, 8, 7, 6, 6 }));\r
- Assert.IsTrue(IC.eq(tree.RangeFromTo(6, 20).Backwards(), new int[] { 18, 16, 14, 12, 10, 10, 9, 8, 8, 7, 6, 6 }));\r
- }\r
-\r
-\r
- [Test]\r
- public void Direction()\r
- {\r
- Assert.AreEqual(EnumerationDirection.Forwards, tree.Direction);\r
- Assert.AreEqual(EnumerationDirection.Forwards, tree.RangeFrom(20).Direction);\r
- Assert.AreEqual(EnumerationDirection.Forwards, tree.RangeTo(7).Direction);\r
- Assert.AreEqual(EnumerationDirection.Forwards, tree.RangeFromTo(1, 12).Direction);\r
- Assert.AreEqual(EnumerationDirection.Forwards, tree.RangeAll().Direction);\r
- Assert.AreEqual(EnumerationDirection.Backwards, tree.Backwards().Direction);\r
- Assert.AreEqual(EnumerationDirection.Backwards, tree.RangeFrom(20).Backwards().Direction);\r
- Assert.AreEqual(EnumerationDirection.Backwards, tree.RangeTo(7).Backwards().Direction);\r
- Assert.AreEqual(EnumerationDirection.Backwards, tree.RangeFromTo(1, 12).Backwards().Direction);\r
- Assert.AreEqual(EnumerationDirection.Backwards, tree.RangeAll().Backwards().Direction);\r
- }\r
-\r
-\r
- [TearDown]\r
- public void Dispose()\r
- {\r
- tree = null;\r
- c = null;\r
- }\r
- }\r
-\r
-\r
-\r
- [TestFixture]\r
- public class BagItf\r
- {\r
- private TreeBag<int> tree;\r
-\r
-\r
- [SetUp]\r
- public void Init()\r
- {\r
- tree = new TreeBag<int>(new IC());\r
- for (int i = 10; i < 20; i++)\r
- {\r
- tree.Add(i);\r
- tree.Add(i + 5);\r
- }\r
- }\r
-\r
-\r
- [Test]\r
- public void Both()\r
- {\r
- Assert.AreEqual(0, tree.ContainsCount(7));\r
- Assert.AreEqual(1, tree.ContainsCount(10));\r
- Assert.AreEqual(2, tree.ContainsCount(17));\r
- tree.RemoveAllCopies(17);\r
- Assert.AreEqual(0, tree.ContainsCount(17));\r
- tree.RemoveAllCopies(7);\r
- }\r
-\r
-\r
- [TearDown]\r
- public void Dispose()\r
- {\r
- tree = null;\r
- }\r
- }\r
-\r
-\r
-\r
- [TestFixture]\r
- public class Div\r
- {\r
- private TreeBag<int> tree;\r
-\r
-\r
- [SetUp]\r
- public void Init()\r
- {\r
- tree = new TreeBag<int>(new IC());\r
- }\r
-\r
-\r
- private void loadup()\r
- {\r
- for (int i = 10; i < 20; i++)\r
- {\r
- tree.Add(i);\r
- tree.Add(i + 5);\r
- }\r
- }\r
-\r
-\r
- [Test]\r
- public void NoDuplicates()\r
- {\r
- Assert.IsTrue(tree.AllowsDuplicates);\r
- loadup();\r
- Assert.IsTrue(tree.AllowsDuplicates);\r
- }\r
-\r
-\r
- [Test]\r
- public void Add()\r
- {\r
- Assert.IsTrue(tree.Add(17));\r
- Assert.IsTrue(tree.Add(17));\r
- Assert.IsTrue(tree.Add(18));\r
- Assert.IsTrue(tree.Add(18));\r
- Assert.AreEqual(4, tree.Count);\r
- Assert.IsTrue(IC.eq(tree, 17, 17, 18, 18));\r
- }\r
-\r
-\r
- [TearDown]\r
- public void Dispose()\r
- {\r
- tree = null;\r
- }\r
- }\r
-\r
-\r
-\r
- [TestFixture]\r
- public class ArrayTest\r
- {\r
- private TreeBag<int> tree;\r
-\r
- int[] a;\r
-\r
-\r
- [SetUp]\r
- public void Init()\r
- {\r
- tree = new TreeBag<int>(new IC());\r
- a = new int[10];\r
- for (int i = 0; i < 10; i++)\r
- a[i] = 1000 + i;\r
- }\r
-\r
-\r
- [TearDown]\r
- public void Dispose() { tree = null; }\r
-\r
-\r
- private string aeq(int[] a, params int[] b)\r
- {\r
- if (a.Length != b.Length)\r
- return "Lengths differ: " + a.Length + " != " + b.Length;\r
-\r
- for (int i = 0; i < a.Length; i++)\r
- if (a[i] != b[i])\r
- return String.Format("{0}'th elements differ: {1} != {2}", i, a[i], b[i]);\r
-\r
- return "Alles klar";\r
- }\r
-\r
-\r
- [Test]\r
- public void ToArray()\r
- {\r
- Assert.AreEqual("Alles klar", aeq(tree.ToArray()));\r
- tree.Add(4);\r
- tree.Add(7);\r
- tree.Add(4);\r
- Assert.AreEqual("Alles klar", aeq(tree.ToArray(), 4, 4, 7));\r
- }\r
-\r
-\r
- [Test]\r
- public void CopyTo()\r
- {\r
- tree.CopyTo(a, 1);\r
- Assert.AreEqual("Alles klar", aeq(a, 1000, 1001, 1002, 1003, 1004, 1005, 1006, 1007, 1008, 1009));\r
- tree.Add(6);\r
- tree.Add(6);\r
- tree.CopyTo(a, 2);\r
- Assert.AreEqual("Alles klar", aeq(a, 1000, 1001, 6, 6, 1004, 1005, 1006, 1007, 1008, 1009));\r
- tree.Add(4);\r
- tree.Add(9);\r
- tree.CopyTo(a, 4);\r
- Assert.AreEqual("Alles klar", aeq(a, 1000, 1001, 6, 6, 4, 6, 6, 9, 1008, 1009));\r
- tree.Clear();\r
- tree.Add(7);\r
- tree.CopyTo(a, 9);\r
- Assert.AreEqual("Alles klar", aeq(a, 1000, 1001, 6, 6, 4, 6, 6, 9, 1008, 7));\r
- }\r
-\r
-\r
- [Test]\r
- [ExpectedException(typeof(ArgumentException))]\r
- public void CopyToBad()\r
- {\r
- tree.Add(3);\r
- tree.CopyTo(a, 10);\r
- }\r
-\r
-\r
- [Test]\r
- [ExpectedException(typeof(ArgumentOutOfRangeException))]\r
- public void CopyToBad2()\r
- {\r
- tree.CopyTo(a, -1);\r
- }\r
-\r
-\r
- [Test]\r
- [ExpectedException(typeof(ArgumentException))]\r
- public void CopyToTooFar()\r
- {\r
- tree.Add(3);\r
- tree.Add(4);\r
- tree.CopyTo(a, 9);\r
- }\r
- }\r
-\r
-\r
-\r
- [TestFixture]\r
- public class Remove\r
- {\r
- private TreeBag<int> tree;\r
-\r
-\r
- [SetUp]\r
- public void Init()\r
- {\r
- tree = new TreeBag<int>(new IC());\r
- for (int i = 10; i < 20; i++)\r
- {\r
- tree.Add(i);\r
- tree.Add(i + 5);\r
- }\r
- //10,11,12,13,14,15,15,16,16,17,17,18,18,19,19,20,21,22,23,24\r
- }\r
-\r
-\r
- [Test]\r
- public void SmallTrees()\r
- {\r
- tree.Clear();\r
- tree.Add(9);\r
- tree.Add(7);\r
- tree.Add(9);\r
- Assert.IsTrue(tree.Remove(7));\r
- Assert.IsTrue(tree.Check(""));\r
- }\r
-\r
-\r
- [Test]\r
- public void ByIndex()\r
- {\r
- //Remove root!\r
- int n = tree.Count;\r
- int i = tree[10];\r
-\r
- Assert.AreEqual(17,tree.RemoveAt(10));\r
- Assert.IsTrue(tree.Check(""));\r
- Assert.IsTrue(tree.Contains(i));\r
- Assert.AreEqual(n - 1, tree.Count);\r
- Assert.AreEqual(17, tree.RemoveAt(9));\r
- Assert.IsTrue(tree.Check(""));\r
- Assert.IsFalse(tree.Contains(i));\r
- Assert.AreEqual(n - 2, tree.Count);\r
-\r
- //Low end\r
- i = tree.FindMin();\r
- tree.RemoveAt(0);\r
- Assert.IsTrue(tree.Check(""));\r
- Assert.IsFalse(tree.Contains(i));\r
- Assert.AreEqual(n - 3, tree.Count);\r
-\r
- //high end\r
- i = tree.FindMax();\r
- tree.RemoveAt(tree.Count - 1);\r
- Assert.IsTrue(tree.Check(""));\r
- Assert.IsFalse(tree.Contains(i));\r
- Assert.AreEqual(n - 4, tree.Count);\r
-\r
- //Some leaf\r
- //tree.dump();\r
- i = 18;\r
- Assert.AreEqual(i, tree.RemoveAt(9));\r
- Assert.IsTrue(tree.Check(""));\r
- Assert.AreEqual(i, tree.RemoveAt(8));\r
- Assert.IsTrue(tree.Check(""));\r
- Assert.IsFalse(tree.Contains(i));\r
- Assert.AreEqual(n - 6, tree.Count);\r
- }\r
-\r
-\r
- [Test]\r
- public void AlmostEmpty()\r
- {\r
- //Almost empty\r
- tree.Clear();\r
- tree.Add(3);\r
- tree.RemoveAt(0);\r
- Assert.IsTrue(tree.Check(""));\r
- Assert.IsFalse(tree.Contains(3));\r
- Assert.AreEqual(0, tree.Count);\r
- }\r
-\r
-\r
- [Test]\r
- [ExpectedException(typeof(IndexOutOfRangeException), "Index out of range for sequenced collection")]\r
- public void Empty()\r
- {\r
- tree.Clear();\r
- tree.RemoveAt(0);\r
- }\r
-\r
-\r
- [Test]\r
- [ExpectedException(typeof(IndexOutOfRangeException), "Index out of range for sequenced collection")]\r
- public void HighIndex()\r
- {\r
- tree.RemoveAt(tree.Count);\r
- }\r
-\r
-\r
- [Test]\r
- [ExpectedException(typeof(IndexOutOfRangeException), "Index out of range for sequenced collection")]\r
- public void LowIndex()\r
- {\r
- tree.RemoveAt(-1);\r
- }\r
-\r
-\r
- [Test]\r
- public void Normal()\r
- {\r
- //Note: ids does not match for bag\r
- Assert.IsFalse(tree.Remove(-20));\r
-\r
- //1b\r
- Assert.IsTrue(tree.Remove(20));\r
- Assert.IsTrue(tree.Check("T1"));\r
- Assert.IsFalse(tree.Remove(20));\r
-\r
- //1b\r
- Assert.IsTrue(tree.Remove(10));\r
- Assert.IsTrue(tree.Check("Normal test 1"), "Bad tree");\r
-\r
- //case 1c\r
- Assert.IsTrue(tree.Remove(24));\r
- Assert.IsTrue(tree.Check("Normal test 1"), "Bad tree");\r
-\r
- //1a (terminating)\r
- Assert.IsTrue(tree.Remove(16));\r
- Assert.IsTrue(tree.Remove(16));\r
- Assert.IsTrue(tree.Check("Normal test 1"), "Bad tree");\r
-\r
- //2\r
- Assert.IsTrue(tree.Remove(18));\r
- Assert.IsTrue(tree.Remove(17));\r
- Assert.IsTrue(tree.Remove(18));\r
- Assert.IsTrue(tree.Remove(17));\r
- Assert.IsTrue(tree.Check("Normal test 1"), "Bad tree");\r
-\r
- //2+1b\r
- Assert.IsTrue(tree.Remove(15));\r
- Assert.IsTrue(tree.Remove(15));\r
- for (int i = 0; i < 5; i++) tree.Add(17 + i);\r
- Assert.IsTrue(tree.Remove(23));\r
- Assert.IsTrue(tree.Check("Normal test 1"), "Bad tree");\r
-\r
- //1a+1b\r
- Assert.IsTrue(tree.Remove(11));\r
- Assert.IsTrue(tree.Check("Normal test 1"), "Bad tree");\r
-\r
- //2+1c\r
- for (int i = 0; i < 10; i++)\r
- tree.Add(50 - 2 * i);\r
-\r
- Assert.IsTrue(tree.Remove(42));\r
- Assert.IsTrue(tree.Remove(38));\r
- Assert.IsTrue(tree.Remove(22));\r
- Assert.IsTrue(tree.Remove(40));\r
-\r
- //\r
- for (int i = 0; i < 48; i++)\r
- tree.Remove(i);\r
-\r
- //Almost empty tree:*\r
- Assert.IsFalse(tree.Remove(26));\r
- Assert.IsTrue(tree.Remove(48));\r
- Assert.IsTrue(tree.Check("Normal test 1"), "Bad tree");\r
-\r
- //Empty tree:*\r
- Assert.IsFalse(tree.Remove(26));\r
- Assert.IsTrue(tree.Check("Normal test 1"), "Bad tree");\r
- }\r
-\r
-\r
- [TearDown]\r
- public void Dispose()\r
- {\r
- tree = null;\r
- }\r
- }\r
-\r
-\r
-\r
- [TestFixture]\r
- public class PredecessorStructure\r
- {\r
- private TreeBag<int> tree;\r
-\r
-\r
- [SetUp]\r
- public void Init()\r
- {\r
- tree = new TreeBag<int>(new IC());\r
- }\r
-\r
-\r
- private void loadup()\r
- {\r
- for (int i = 0; i < 20; i++) \r
- tree.Add(2 * i);\r
- for (int i = 0; i < 10; i++)\r
- tree.Add(4 * i);\r
- }\r
-\r
-\r
- [Test]\r
- public void Predecessor()\r
- {\r
- loadup();\r
- Assert.AreEqual(6, tree.Predecessor(7));\r
- Assert.AreEqual(6, tree.Predecessor(8));\r
-\r
- //The bottom\r
- Assert.AreEqual(0, tree.Predecessor(1));\r
-\r
- //The top\r
- Assert.AreEqual(38, tree.Predecessor(39));\r
- }\r
-\r
-\r
- [Test]\r
- [ExpectedException(typeof(ArgumentOutOfRangeException))]\r
- public void PredecessorTooLow1()\r
- {\r
- tree.Predecessor(-2);\r
- }\r
-\r
-\r
- [Test]\r
- [ExpectedException(typeof(ArgumentOutOfRangeException))]\r
- public void PredecessorTooLow2()\r
- {\r
- tree.Predecessor(0);\r
- }\r
-\r
-\r
- [Test]\r
- public void WeakPredecessor()\r
- {\r
- loadup();\r
- Assert.AreEqual(6, tree.WeakPredecessor(7));\r
- Assert.AreEqual(8, tree.WeakPredecessor(8));\r
+ using CollectionOfInt = TreeBag<int>;\r
+\r
+ [TestFixture]\r
+ public class GenericTesters\r
+ {\r
+ [Test]\r
+ public void TestEvents()\r
+ {\r
+ Fun<CollectionOfInt> factory = delegate() { return new CollectionOfInt(TenEqualityComparer.Default); };\r
+ new C5UnitTests.Templates.Events.SortedIndexedTester<CollectionOfInt>().Test(factory);\r
+ }\r
+\r
+ [Test]\r
+ public void Extensible()\r
+ {\r
+ C5UnitTests.Templates.Extensible.Clone.Tester<CollectionOfInt>();\r
+ C5UnitTests.Templates.Extensible.Serialization.Tester<CollectionOfInt>();\r
+ }\r
+ }\r
+\r
+ static class Factory\r
+ {\r
+ public static ICollection<T> New<T>() { return new TreeBag<T>(); }\r
+ }\r
+\r
+\r
+ [TestFixture]\r
+ public class Formatting\r
+ {\r
+ ICollection<int> coll;\r
+ IFormatProvider rad16;\r
+ [SetUp]\r
+ public void Init() { coll = Factory.New<int>(); rad16 = new RadixFormatProvider(16); }\r
+ [TearDown]\r
+ public void Dispose() { coll = null; rad16 = null; }\r
+ [Test]\r
+ public void Format()\r
+ {\r
+ Assert.AreEqual("{{ }}", coll.ToString());\r
+ coll.AddAll<int>(new int[] { -4, 28, 129, 65530, -4, 28 });\r
+ Assert.AreEqual("{{ -4(*2), 28(*2), 129(*1), 65530(*1) }}", coll.ToString());\r
+ Assert.AreEqual("{{ -4(*2), 1C(*2), 81(*1), FFFA(*1) }}", coll.ToString(null, rad16));\r
+ Assert.AreEqual("{{ -4(*2), 28(*2)... }}", coll.ToString("L18", null));\r
+ Assert.AreEqual("{{ -4(*2), 1C(*2)... }}", coll.ToString("L18", rad16));\r
+ }\r
+ }\r
+\r
+ [TestFixture]\r
+ public class Combined\r
+ {\r
+ private IIndexedSorted<KeyValuePair<int, int>> lst;\r
+\r
+\r
+ [SetUp]\r
+ public void Init()\r
+ {\r
+ lst = new TreeBag<KeyValuePair<int, int>>(new KeyValuePairComparer<int, int>(new IC()));\r
+ for (int i = 0; i < 10; i++)\r
+ lst.Add(new KeyValuePair<int, int>(i, i + 30));\r
+ }\r
+\r
+\r
+ [TearDown]\r
+ public void Dispose() { lst = null; }\r
+\r
+\r
+ [Test]\r
+ public void Find()\r
+ {\r
+ KeyValuePair<int, int> p = new KeyValuePair<int, int>(3, 78);\r
+\r
+ Assert.IsTrue(lst.Find(ref p));\r
+ Assert.AreEqual(3, p.Key);\r
+ Assert.AreEqual(33, p.Value);\r
+ p = new KeyValuePair<int, int>(13, 78);\r
+ Assert.IsFalse(lst.Find(ref p));\r
+ }\r
+\r
+\r
+ [Test]\r
+ public void FindOrAdd()\r
+ {\r
+ KeyValuePair<int, int> p = new KeyValuePair<int, int>(3, 78);\r
+\r
+ Assert.IsTrue(lst.FindOrAdd(ref p));\r
+ Assert.AreEqual(3, p.Key);\r
+ Assert.AreEqual(33, p.Value);\r
+ p = new KeyValuePair<int, int>(13, 79);\r
+ Assert.IsFalse(lst.FindOrAdd(ref p));\r
+ Assert.AreEqual(13, lst[11].Key);\r
+ Assert.AreEqual(79, lst[11].Value);\r
+ }\r
+\r
+\r
+ [Test]\r
+ public void Update()\r
+ {\r
+ KeyValuePair<int, int> p = new KeyValuePair<int, int>(3, 78);\r
+\r
+ Assert.IsTrue(lst.Update(p));\r
+ Assert.AreEqual(3, lst[3].Key);\r
+ Assert.AreEqual(78, lst[3].Value);\r
+ p = new KeyValuePair<int, int>(13, 78);\r
+ Assert.IsFalse(lst.Update(p));\r
+ }\r
+\r
+\r
+ [Test]\r
+ public void UpdateOrAdd()\r
+ {\r
+ KeyValuePair<int, int> p = new KeyValuePair<int, int>(3, 78);\r
+\r
+ Assert.IsTrue(lst.UpdateOrAdd(p));\r
+ Assert.AreEqual(3, lst[3].Key);\r
+ Assert.AreEqual(78, lst[3].Value);\r
+ p = new KeyValuePair<int, int>(13, 79);\r
+ Assert.IsFalse(lst.UpdateOrAdd(p));\r
+ Assert.AreEqual(13, lst[10].Key);\r
+ Assert.AreEqual(79, lst[10].Value);\r
+ }\r
+\r
+\r
+ [Test]\r
+ public void RemoveWithReturn()\r
+ {\r
+ KeyValuePair<int, int> p = new KeyValuePair<int, int>(3, 78);\r
+\r
+ Assert.IsTrue(lst.Remove(p, out p));\r
+ Assert.AreEqual(3, p.Key);\r
+ Assert.AreEqual(33, p.Value);\r
+ Assert.AreEqual(4, lst[3].Key);\r
+ Assert.AreEqual(34, lst[3].Value);\r
+ p = new KeyValuePair<int, int>(13, 78);\r
+ Assert.IsFalse(lst.Remove(p, out p));\r
+ }\r
+ }\r
+\r
+\r
+ [TestFixture]\r
+ public class Simple\r
+ {\r
+ private TreeBag<string> bag;\r
+\r
+\r
+ [SetUp]\r
+ public void Init()\r
+ {\r
+ bag = new TreeBag<string>(new SC());\r
+ }\r
+\r
+\r
+ [TearDown]\r
+ public void Dispose()\r
+ {\r
+ bag = null;\r
+ }\r
+\r
+ [Test]\r
+ public void Initial()\r
+ {\r
+ bool res;\r
+\r
+ Assert.IsFalse(bag.IsReadOnly);\r
+ Assert.AreEqual(0, bag.Count, "new bag should be empty");\r
+ Assert.AreEqual(0, bag.ContainsCount("A"));\r
+ Assert.AreEqual(0, bag.ContainsCount("B"));\r
+ Assert.AreEqual(0, bag.ContainsCount("C"));\r
+ Assert.IsFalse(bag.Contains("A"));\r
+ Assert.IsFalse(bag.Contains("B"));\r
+ Assert.IsFalse(bag.Contains("C"));\r
+ bag.Add("A");\r
+ Assert.AreEqual(1, bag.Count);\r
+ Assert.AreEqual(1, bag.ContainsCount("A"));\r
+ Assert.AreEqual(0, bag.ContainsCount("B"));\r
+ Assert.AreEqual(0, bag.ContainsCount("C"));\r
+ Assert.IsTrue(bag.Contains("A"));\r
+ Assert.IsFalse(bag.Contains("B"));\r
+ Assert.IsFalse(bag.Contains("C"));\r
+ bag.Add("C");\r
+ Assert.AreEqual(2, bag.Count);\r
+ Assert.AreEqual(1, bag.ContainsCount("A"));\r
+ Assert.AreEqual(0, bag.ContainsCount("B"));\r
+ Assert.AreEqual(1, bag.ContainsCount("C"));\r
+ Assert.IsTrue(bag.Contains("A"));\r
+ Assert.IsFalse(bag.Contains("B"));\r
+ Assert.IsTrue(bag.Contains("C"));\r
+ bag.Add("C");\r
+ Assert.AreEqual(3, bag.Count);\r
+ Assert.AreEqual(1, bag.ContainsCount("A"));\r
+ Assert.AreEqual(0, bag.ContainsCount("B"));\r
+ Assert.AreEqual(2, bag.ContainsCount("C"));\r
+ Assert.IsTrue(bag.Contains("A"));\r
+ Assert.IsFalse(bag.Contains("B"));\r
+ Assert.IsTrue(bag.Contains("C"));\r
+ bag.Add("B");\r
+ bag.Add("C");\r
+ Assert.AreEqual(5, bag.Count);\r
+ Assert.AreEqual(1, bag.ContainsCount("A"));\r
+ Assert.AreEqual(1, bag.ContainsCount("B"));\r
+ Assert.AreEqual(3, bag.ContainsCount("C"));\r
+ Assert.IsTrue(bag.Contains("A"));\r
+ Assert.IsTrue(bag.Contains("B"));\r
+ Assert.IsTrue(bag.Contains("C"));\r
+ res = bag.Remove("C");\r
+ Assert.AreEqual(4, bag.Count);\r
+ Assert.AreEqual(1, bag.ContainsCount("A"));\r
+ Assert.AreEqual(1, bag.ContainsCount("B"));\r
+ Assert.AreEqual(2, bag.ContainsCount("C"));\r
+ Assert.IsTrue(bag.Contains("A"));\r
+ Assert.IsTrue(bag.Contains("B"));\r
+ Assert.IsTrue(bag.Contains("C"));\r
+ res = bag.Remove("A");\r
+ Assert.AreEqual(3, bag.Count);\r
+ Assert.AreEqual(0, bag.ContainsCount("A"));\r
+ Assert.AreEqual(1, bag.ContainsCount("B"));\r
+ Assert.AreEqual(2, bag.ContainsCount("C"));\r
+ Assert.IsFalse(bag.Contains("A"));\r
+ Assert.IsTrue(bag.Contains("B"));\r
+ Assert.IsTrue(bag.Contains("C"));\r
+ bag.RemoveAllCopies("C");\r
+ Assert.AreEqual(1, bag.Count);\r
+ Assert.AreEqual(0, bag.ContainsCount("A"));\r
+ Assert.AreEqual(1, bag.ContainsCount("B"));\r
+ Assert.AreEqual(0, bag.ContainsCount("C"));\r
+ Assert.IsFalse(bag.Contains("A"));\r
+ Assert.IsTrue(bag.Contains("B"));\r
+ Assert.IsFalse(bag.Contains("C"));\r
+ Assert.IsFalse(bag.Contains("Z"));\r
+ Assert.IsFalse(bag.Remove("Z"));\r
+ bag.RemoveAllCopies("Z");\r
+ Assert.AreEqual(1, bag.Count);\r
+ Assert.AreEqual(0, bag.ContainsCount("A"));\r
+ Assert.AreEqual(1, bag.ContainsCount("B"));\r
+ Assert.AreEqual(0, bag.ContainsCount("C"));\r
+ Assert.IsFalse(bag.Contains("A"));\r
+ Assert.IsTrue(bag.Contains("B"));\r
+ Assert.IsFalse(bag.Contains("C"));\r
+ Assert.IsFalse(bag.Contains("Z"));\r
+ }\r
+ }\r
+\r
+ [TestFixture]\r
+ public class FindOrAdd\r
+ {\r
+ private TreeBag<KeyValuePair<int, string>> bag;\r
+\r
+\r
+ [SetUp]\r
+ public void Init()\r
+ {\r
+ bag = new TreeBag<KeyValuePair<int, string>>(new KeyValuePairComparer<int, string>(new IC()));\r
+ }\r
+\r
+\r
+ [TearDown]\r
+ public void Dispose()\r
+ {\r
+ bag = null;\r
+ }\r
+\r
+\r
+ [Test]\r
+ public void Test()\r
+ {\r
+ KeyValuePair<int, string> p = new KeyValuePair<int, string>(3, "tre");\r
+ Assert.IsFalse(bag.FindOrAdd(ref p));\r
+ p.Value = "drei";\r
+ Assert.IsTrue(bag.FindOrAdd(ref p));\r
+ Assert.AreEqual("tre", p.Value);\r
+ p.Value = "three";\r
+ Assert.AreEqual(2, bag.ContainsCount(p));\r
+ Assert.AreEqual("tre", bag[0].Value);\r
+ }\r
+ }\r
+\r
+\r
+ [TestFixture]\r
+ public class Enumerators\r
+ {\r
+ private TreeBag<string> bag;\r
+\r
+ private SCG.IEnumerator<string> bagenum;\r
+\r
+\r
+ [SetUp]\r
+ public void Init()\r
+ {\r
+ bag = new TreeBag<string>(new SC());\r
+ foreach (string s in new string[] { "A", "B", "A", "A", "B", "C", "D", "B" })\r
+ bag.Add(s);\r
+\r
+ bagenum = bag.GetEnumerator();\r
+ }\r
+\r
+\r
+ [TearDown]\r
+ public void Dispose()\r
+ {\r
+ bagenum = null;\r
+ bag = null;\r
+ }\r
+\r
+\r
+ [Test]\r
+ [ExpectedException(typeof(CollectionModifiedException))]\r
+ public void MoveNextOnModified()\r
+ {\r
+ //TODO: also problem before first MoveNext!!!!!!!!!!\r
+ bagenum.MoveNext();\r
+ bag.Add("T");\r
+ bagenum.MoveNext();\r
+ }\r
+\r
+\r
+ [Test]\r
+ public void NormalUse()\r
+ {\r
+ Assert.IsTrue(bagenum.MoveNext());\r
+ Assert.AreEqual(bagenum.Current, "A");\r
+ Assert.IsTrue(bagenum.MoveNext());\r
+ Assert.AreEqual(bagenum.Current, "A");\r
+ Assert.IsTrue(bagenum.MoveNext());\r
+ Assert.AreEqual(bagenum.Current, "A");\r
+ Assert.IsTrue(bagenum.MoveNext());\r
+ Assert.AreEqual(bagenum.Current, "B");\r
+ Assert.IsTrue(bagenum.MoveNext());\r
+ Assert.AreEqual(bagenum.Current, "B");\r
+ Assert.IsTrue(bagenum.MoveNext());\r
+ Assert.AreEqual(bagenum.Current, "B");\r
+ Assert.IsTrue(bagenum.MoveNext());\r
+ Assert.AreEqual(bagenum.Current, "C");\r
+ Assert.IsTrue(bagenum.MoveNext());\r
+ Assert.AreEqual(bagenum.Current, "D");\r
+ Assert.IsFalse(bagenum.MoveNext());\r
+ }\r
+ }\r
+\r
+ [TestFixture]\r
+ public class Ranges\r
+ {\r
+ private TreeBag<int> tree;\r
+\r
+ private SCG.IComparer<int> c;\r
+\r
+\r
+ [SetUp]\r
+ public void Init()\r
+ {\r
+ c = new IC();\r
+ tree = new TreeBag<int>(c);\r
+ for (int i = 1; i <= 10; i++)\r
+ {\r
+ tree.Add(i * 2); tree.Add(i);\r
+ }\r
+ }\r
+\r
+\r
+ [Test]\r
+ public void Enumerator()\r
+ {\r
+ SCG.IEnumerator<int> e = tree.RangeFromTo(5, 17).GetEnumerator();\r
+ int i = 0;\r
+ int[] all = new int[] { 5, 6, 6, 7, 8, 8, 9, 10, 10, 12, 14, 16 };\r
+ while (e.MoveNext())\r
+ {\r
+ Assert.AreEqual(all[i++], e.Current);\r
+ }\r
+\r
+ Assert.AreEqual(12, i);\r
+ }\r
+\r
+\r
+ [Test]\r
+ [ExpectedException(typeof(InvalidOperationException))]\r
+ public void Enumerator2()\r
+ {\r
+ SCG.IEnumerator<int> e = tree.RangeFromTo(5, 17).GetEnumerator();\r
+ int i = e.Current;\r
+ }\r
+\r
+\r
+ [Test]\r
+ [ExpectedException(typeof(InvalidOperationException))]\r
+ public void Enumerator3()\r
+ {\r
+ SCG.IEnumerator<int> e = tree.RangeFromTo(5, 17).GetEnumerator();\r
+\r
+ while (e.MoveNext()) ;\r
+\r
+ int i = e.Current;\r
+ }\r
+\r
+\r
+ [Test]\r
+ public void Remove()\r
+ {\r
+ int[] all = new int[] { 1, 2, 2, 3, 4, 4, 5, 6, 6, 7, 8, 8, 9, 10, 10, 12, 14, 16, 18, 20 };\r
+\r
+ tree.RemoveRangeFrom(18);\r
+ Assert.IsTrue(IC.eq(tree, new int[] { 1, 2, 2, 3, 4, 4, 5, 6, 6, 7, 8, 8, 9, 10, 10, 12, 14, 16 }));\r
+ tree.RemoveRangeFrom(28);\r
+ Assert.IsTrue(IC.eq(tree, new int[] { 1, 2, 2, 3, 4, 4, 5, 6, 6, 7, 8, 8, 9, 10, 10, 12, 14, 16 }));\r
+ tree.RemoveRangeFrom(1);\r
+ Assert.IsTrue(IC.eq(tree));\r
+ foreach (int i in all) tree.Add(i);\r
+\r
+ tree.RemoveRangeTo(10);\r
+ Assert.IsTrue(IC.eq(tree, new int[] { 10, 10, 12, 14, 16, 18, 20 }));\r
+ tree.RemoveRangeTo(2);\r
+ Assert.IsTrue(IC.eq(tree, new int[] { 10, 10, 12, 14, 16, 18, 20 }));\r
+ tree.RemoveRangeTo(21);\r
+ Assert.IsTrue(IC.eq(tree));\r
+ foreach (int i in all) tree.Add(i);\r
+\r
+ tree.RemoveRangeFromTo(4, 8);\r
+ Assert.IsTrue(IC.eq(tree, 1, 2, 2, 3, 8, 8, 9, 10, 10, 12, 14, 16, 18, 20));\r
+ tree.RemoveRangeFromTo(14, 28);\r
+ Assert.IsTrue(IC.eq(tree, 1, 2, 2, 3, 8, 8, 9, 10, 10, 12));\r
+ tree.RemoveRangeFromTo(0, 9);\r
+ Assert.IsTrue(IC.eq(tree, 9, 10, 10, 12));\r
+ tree.RemoveRangeFromTo(0, 81);\r
+ Assert.IsTrue(IC.eq(tree));\r
+ }\r
+\r
+\r
+ [Test]\r
+ public void Normal()\r
+ {\r
+ int[] all = new int[] { 1, 2, 2, 3, 4, 4, 5, 6, 6, 7, 8, 8, 9, 10, 10, 12, 14, 16, 18, 20 };\r
+\r
+ Assert.IsTrue(IC.eq(tree, all));\r
+ Assert.IsTrue(IC.eq(tree.RangeAll(), all));\r
+ Assert.AreEqual(20, tree.RangeAll().Count);\r
+ Assert.IsTrue(IC.eq(tree.RangeFrom(11), new int[] { 12, 14, 16, 18, 20 }));\r
+ Assert.AreEqual(5, tree.RangeFrom(11).Count);\r
+ Assert.IsTrue(IC.eq(tree.RangeFrom(12), new int[] { 12, 14, 16, 18, 20 }));\r
+ Assert.IsTrue(IC.eq(tree.RangeFrom(1), all));\r
+ Assert.IsTrue(IC.eq(tree.RangeFrom(0), all));\r
+ Assert.IsTrue(IC.eq(tree.RangeFrom(21), new int[] { }));\r
+ Assert.IsTrue(IC.eq(tree.RangeFrom(20), new int[] { 20 }));\r
+ Assert.IsTrue(IC.eq(tree.RangeTo(8), new int[] { 1, 2, 2, 3, 4, 4, 5, 6, 6, 7 }));\r
+ Assert.IsTrue(IC.eq(tree.RangeTo(7), new int[] { 1, 2, 2, 3, 4, 4, 5, 6, 6 }));\r
+ Assert.AreEqual(9, tree.RangeTo(7).Count);\r
+ Assert.IsTrue(IC.eq(tree.RangeTo(1), new int[] { }));\r
+ Assert.IsTrue(IC.eq(tree.RangeTo(0), new int[] { }));\r
+ Assert.IsTrue(IC.eq(tree.RangeTo(3), new int[] { 1, 2, 2 }));\r
+ Assert.IsTrue(IC.eq(tree.RangeTo(20), new int[] { 1, 2, 2, 3, 4, 4, 5, 6, 6, 7, 8, 8, 9, 10, 10, 12, 14, 16, 18 }));\r
+ Assert.IsTrue(IC.eq(tree.RangeTo(21), all));\r
+ Assert.IsTrue(IC.eq(tree.RangeFromTo(7, 12), new int[] { 7, 8, 8, 9, 10, 10 }));\r
+ Assert.IsTrue(IC.eq(tree.RangeFromTo(6, 11), new int[] { 6, 6, 7, 8, 8, 9, 10, 10 }));\r
+ Assert.IsTrue(IC.eq(tree.RangeFromTo(1, 12), new int[] { 1, 2, 2, 3, 4, 4, 5, 6, 6, 7, 8, 8, 9, 10, 10 }));\r
+ Assert.AreEqual(15, tree.RangeFromTo(1, 12).Count);\r
+ Assert.IsTrue(IC.eq(tree.RangeFromTo(2, 12), new int[] { 2, 2, 3, 4, 4, 5, 6, 6, 7, 8, 8, 9, 10, 10 }));\r
+ Assert.IsTrue(IC.eq(tree.RangeFromTo(6, 21), new int[] { 6, 6, 7, 8, 8, 9, 10, 10, 12, 14, 16, 18, 20 }));\r
+ Assert.IsTrue(IC.eq(tree.RangeFromTo(6, 20), new int[] { 6, 6, 7, 8, 8, 9, 10, 10, 12, 14, 16, 18 }));\r
+ }\r
+\r
+\r
+ [Test]\r
+ public void Backwards()\r
+ {\r
+ int[] all = new int[] { 1, 2, 2, 3, 4, 4, 5, 6, 6, 7, 8, 8, 9, 10, 10, 12, 14, 16, 18, 20 };\r
+ int[] lla = new int[] { 20, 18, 16, 14, 12, 10, 10, 9, 8, 8, 7, 6, 6, 5, 4, 4, 3, 2, 2, 1 };\r
+\r
+ Assert.IsTrue(IC.eq(tree, all));\r
+ Assert.IsTrue(IC.eq(tree.RangeAll().Backwards(), lla));\r
+ Assert.IsTrue(IC.eq(tree.RangeFrom(11).Backwards(), new int[] { 20, 18, 16, 14, 12 }));\r
+ Assert.IsTrue(IC.eq(tree.RangeFrom(12).Backwards(), new int[] { 20, 18, 16, 14, 12 }));\r
+ Assert.IsTrue(IC.eq(tree.RangeFrom(1).Backwards(), lla));\r
+ Assert.IsTrue(IC.eq(tree.RangeFrom(0).Backwards(), lla));\r
+ Assert.IsTrue(IC.eq(tree.RangeFrom(21).Backwards(), new int[] { }));\r
+ Assert.IsTrue(IC.eq(tree.RangeFrom(20).Backwards(), new int[] { 20 }));\r
+ Assert.IsTrue(IC.eq(tree.RangeTo(8).Backwards(), new int[] { 7, 6, 6, 5, 4, 4, 3, 2, 2, 1 }));\r
+ Assert.IsTrue(IC.eq(tree.RangeTo(7).Backwards(), new int[] { 6, 6, 5, 4, 4, 3, 2, 2, 1 }));\r
+ Assert.IsTrue(IC.eq(tree.RangeTo(1).Backwards(), new int[] { }));\r
+ Assert.IsTrue(IC.eq(tree.RangeTo(0).Backwards(), new int[] { }));\r
+ Assert.IsTrue(IC.eq(tree.RangeTo(3).Backwards(), new int[] { 2, 2, 1 }));\r
+ Assert.IsTrue(IC.eq(tree.RangeTo(20).Backwards(), new int[] { 18, 16, 14, 12, 10, 10, 9, 8, 8, 7, 6, 6, 5, 4, 4, 3, 2, 2, 1 }));\r
+ Assert.IsTrue(IC.eq(tree.RangeTo(21).Backwards(), lla));\r
+ Assert.IsTrue(IC.eq(tree.RangeFromTo(7, 12).Backwards(), new int[] { 10, 10, 9, 8, 8, 7 }));\r
+ Assert.IsTrue(IC.eq(tree.RangeFromTo(6, 11).Backwards(), new int[] { 10, 10, 9, 8, 8, 7, 6, 6 }));\r
+ Assert.IsTrue(IC.eq(tree.RangeFromTo(0, 12).Backwards(), new int[] { 10, 10, 9, 8, 8, 7, 6, 6, 5, 4, 4, 3, 2, 2, 1 }));\r
+ Assert.IsTrue(IC.eq(tree.RangeFromTo(1, 12).Backwards(), new int[] { 10, 10, 9, 8, 8, 7, 6, 6, 5, 4, 4, 3, 2, 2, 1 }));\r
+ Assert.IsTrue(IC.eq(tree.RangeFromTo(6, 21).Backwards(), new int[] { 20, 18, 16, 14, 12, 10, 10, 9, 8, 8, 7, 6, 6 }));\r
+ Assert.IsTrue(IC.eq(tree.RangeFromTo(6, 20).Backwards(), new int[] { 18, 16, 14, 12, 10, 10, 9, 8, 8, 7, 6, 6 }));\r
+ }\r
+\r
+\r
+ [Test]\r
+ public void Direction()\r
+ {\r
+ Assert.AreEqual(EnumerationDirection.Forwards, tree.Direction);\r
+ Assert.AreEqual(EnumerationDirection.Forwards, tree.RangeFrom(20).Direction);\r
+ Assert.AreEqual(EnumerationDirection.Forwards, tree.RangeTo(7).Direction);\r
+ Assert.AreEqual(EnumerationDirection.Forwards, tree.RangeFromTo(1, 12).Direction);\r
+ Assert.AreEqual(EnumerationDirection.Forwards, tree.RangeAll().Direction);\r
+ Assert.AreEqual(EnumerationDirection.Backwards, tree.Backwards().Direction);\r
+ Assert.AreEqual(EnumerationDirection.Backwards, tree.RangeFrom(20).Backwards().Direction);\r
+ Assert.AreEqual(EnumerationDirection.Backwards, tree.RangeTo(7).Backwards().Direction);\r
+ Assert.AreEqual(EnumerationDirection.Backwards, tree.RangeFromTo(1, 12).Backwards().Direction);\r
+ Assert.AreEqual(EnumerationDirection.Backwards, tree.RangeAll().Backwards().Direction);\r
+ }\r
+\r
+\r
+ [TearDown]\r
+ public void Dispose()\r
+ {\r
+ tree = null;\r
+ c = null;\r
+ }\r
+ }\r
+\r
+\r
+\r
+ [TestFixture]\r
+ public class BagItf\r
+ {\r
+ private TreeBag<int> tree;\r
+\r
+\r
+ [SetUp]\r
+ public void Init()\r
+ {\r
+ tree = new TreeBag<int>(new IC());\r
+ for (int i = 10; i < 20; i++)\r
+ {\r
+ tree.Add(i);\r
+ tree.Add(i + 5);\r
+ }\r
+ }\r
+\r
+\r
+ [Test]\r
+ public void Both()\r
+ {\r
+ Assert.AreEqual(0, tree.ContainsCount(7));\r
+ Assert.AreEqual(1, tree.ContainsCount(10));\r
+ Assert.AreEqual(2, tree.ContainsCount(17));\r
+ tree.RemoveAllCopies(17);\r
+ Assert.AreEqual(0, tree.ContainsCount(17));\r
+ tree.RemoveAllCopies(7);\r
+ }\r
+\r
+\r
+ [TearDown]\r
+ public void Dispose()\r
+ {\r
+ tree = null;\r
+ }\r
+ }\r
+\r
+\r
+\r
+ [TestFixture]\r
+ public class Div\r
+ {\r
+ private TreeBag<int> tree;\r
+\r
+\r
+ [SetUp]\r
+ public void Init()\r
+ {\r
+ tree = new TreeBag<int>(new IC());\r
+ }\r
+\r
+\r
+ private void loadup()\r
+ {\r
+ for (int i = 10; i < 20; i++)\r
+ {\r
+ tree.Add(i);\r
+ tree.Add(i + 5);\r
+ }\r
+ }\r
+\r
+ [Test]\r
+ [ExpectedException(typeof(NullReferenceException))]\r
+ public void NullEqualityComparerinConstructor1()\r
+ {\r
+ new TreeBag<int>(null);\r
+ }\r
+\r
+ [Test]\r
+ [ExpectedException(typeof(NullReferenceException))]\r
+ public void NullEqualityComparerinConstructor3()\r
+ {\r
+ new TreeBag<int>(null, EqualityComparer<int>.Default);\r
+ }\r
+\r
+ [Test]\r
+ [ExpectedException(typeof(NullReferenceException))]\r
+ public void NullEqualityComparerinConstructor4()\r
+ {\r
+ new TreeBag<int>(Comparer<int>.Default, null);\r
+ }\r
+\r
+ [Test]\r
+ [ExpectedException(typeof(NullReferenceException))]\r
+ public void NullEqualityComparerinConstructor5()\r
+ {\r
+ new TreeBag<int>(null, null);\r
+ }\r
+\r
+ [Test]\r
+ public void Choose()\r
+ {\r
+ tree.Add(7);\r
+ Assert.AreEqual(7, tree.Choose());\r
+ }\r
+\r
+ [Test]\r
+ [ExpectedException(typeof(NoSuchItemException))]\r
+ public void BadChoose()\r
+ {\r
+ tree.Choose();\r
+ }\r
+\r
+\r
+ [Test]\r
+ public void NoDuplicates()\r
+ {\r
+ Assert.IsTrue(tree.AllowsDuplicates);\r
+ loadup();\r
+ Assert.IsTrue(tree.AllowsDuplicates);\r
+ }\r
+\r
+\r
+ [Test]\r
+ public void Add()\r
+ {\r
+ Assert.IsTrue(tree.Add(17));\r
+ Assert.IsTrue(tree.Add(17));\r
+ Assert.IsTrue(tree.Add(18));\r
+ Assert.IsTrue(tree.Add(18));\r
+ Assert.AreEqual(4, tree.Count);\r
+ Assert.IsTrue(IC.eq(tree, 17, 17, 18, 18));\r
+ }\r
+\r
+\r
+ [TearDown]\r
+ public void Dispose()\r
+ {\r
+ tree = null;\r
+ }\r
+ }\r
+\r
+ [TestFixture]\r
+ public class FindPredicate\r
+ {\r
+ private TreeBag<int> list;\r
+ Fun<int, bool> pred;\r
+\r
+ [SetUp]\r
+ public void Init()\r
+ {\r
+ list = new TreeBag<int>(TenEqualityComparer.Default);\r
+ pred = delegate(int i) { return i % 5 == 0; };\r
+ }\r
+\r
+ [TearDown]\r
+ public void Dispose() { list = null; }\r
+\r
+ [Test]\r
+ public void Find()\r
+ {\r
+ int i;\r
+ Assert.IsFalse(list.Find(pred, out i));\r
+ list.AddAll<int>(new int[] { 4, 22, 67, 37 });\r
+ Assert.IsFalse(list.Find(pred, out i));\r
+ list.AddAll<int>(new int[] { 45, 122, 675, 137 });\r
+ Assert.IsTrue(list.Find(pred, out i));\r
+ Assert.AreEqual(45, i);\r
+ }\r
+\r
+ [Test]\r
+ public void FindLast()\r
+ {\r
+ int i;\r
+ Assert.IsFalse(list.FindLast(pred, out i));\r
+ list.AddAll<int>(new int[] { 4, 22, 67, 37 });\r
+ Assert.IsFalse(list.FindLast(pred, out i));\r
+ list.AddAll<int>(new int[] { 45, 122, 675, 137 });\r
+ Assert.IsTrue(list.FindLast(pred, out i));\r
+ Assert.AreEqual(675, i);\r
+ }\r
+\r
+ [Test]\r
+ public void FindIndex()\r
+ {\r
+ Assert.IsFalse(0 <= list.FindIndex(pred));\r
+ list.AddAll<int>(new int[] { 4, 22, 67, 37 });\r
+ Assert.IsFalse(0 <= list.FindIndex(pred));\r
+ list.AddAll<int>(new int[] { 45, 122, 675, 137 });\r
+ Assert.AreEqual(3, list.FindIndex(pred));\r
+ }\r
+\r
+ [Test]\r
+ public void FindLastIndex()\r
+ {\r
+ Assert.IsFalse(0 <= list.FindLastIndex(pred));\r
+ list.AddAll<int>(new int[] { 4, 22, 67, 37 });\r
+ Assert.IsFalse(0 <= list.FindLastIndex(pred));\r
+ list.AddAll<int>(new int[] { 45, 122, 675, 137 });\r
+ Assert.AreEqual(7, list.FindLastIndex(pred));\r
+ }\r
+ }\r
+\r
+ [TestFixture]\r
+ public class UniqueItems\r
+ {\r
+ private TreeBag<int> list;\r
+\r
+ [SetUp]\r
+ public void Init() { list = new TreeBag<int>(); }\r
+\r
+ [TearDown]\r
+ public void Dispose() { list = null; }\r
+\r
+ [Test]\r
+ public void Test()\r
+ {\r
+ Assert.IsTrue(IC.seteq(list.UniqueItems()));\r
+ Assert.IsTrue(IC.seteq(list.ItemMultiplicities()));\r
+ list.AddAll<int>(new int[] { 7, 9, 7 });\r
+ Assert.IsTrue(IC.seteq(list.UniqueItems(), 7, 9));\r
+ Assert.IsTrue(IC.seteq(list.ItemMultiplicities(), 7, 2, 9, 1));\r
+ }\r
+ }\r
+\r
+ [TestFixture]\r
+ public class ArrayTest\r
+ {\r
+ private TreeBag<int> tree;\r
+\r
+ int[] a;\r
+\r
+\r
+ [SetUp]\r
+ public void Init()\r
+ {\r
+ tree = new TreeBag<int>(new IC());\r
+ a = new int[10];\r
+ for (int i = 0; i < 10; i++)\r
+ a[i] = 1000 + i;\r
+ }\r
+\r
+\r
+ [TearDown]\r
+ public void Dispose() { tree = null; }\r
+\r
+\r
+ private string aeq(int[] a, params int[] b)\r
+ {\r
+ if (a.Length != b.Length)\r
+ return "Lengths differ: " + a.Length + " != " + b.Length;\r
+\r
+ for (int i = 0; i < a.Length; i++)\r
+ if (a[i] != b[i])\r
+ return String.Format("{0}'th elements differ: {1} != {2}", i, a[i], b[i]);\r
+\r
+ return "Alles klar";\r
+ }\r
+\r
+\r
+ [Test]\r
+ public void ToArray()\r
+ {\r
+ Assert.AreEqual("Alles klar", aeq(tree.ToArray()));\r
+ tree.Add(4);\r
+ tree.Add(7);\r
+ tree.Add(4);\r
+ Assert.AreEqual("Alles klar", aeq(tree.ToArray(), 4, 4, 7));\r
+ }\r
+\r
+\r
+ [Test]\r
+ public void CopyTo()\r
+ {\r
+ tree.CopyTo(a, 1);\r
+ Assert.AreEqual("Alles klar", aeq(a, 1000, 1001, 1002, 1003, 1004, 1005, 1006, 1007, 1008, 1009));\r
+ tree.Add(6);\r
+ tree.Add(6);\r
+ tree.CopyTo(a, 2);\r
+ Assert.AreEqual("Alles klar", aeq(a, 1000, 1001, 6, 6, 1004, 1005, 1006, 1007, 1008, 1009));\r
+ tree.Add(4);\r
+ tree.Add(9);\r
+ tree.CopyTo(a, 4);\r
+ Assert.AreEqual("Alles klar", aeq(a, 1000, 1001, 6, 6, 4, 6, 6, 9, 1008, 1009));\r
+ tree.Clear();\r
+ tree.Add(7);\r
+ tree.CopyTo(a, 9);\r
+ Assert.AreEqual("Alles klar", aeq(a, 1000, 1001, 6, 6, 4, 6, 6, 9, 1008, 7));\r
+ }\r
+\r
+\r
+ [Test]\r
+ [ExpectedException(typeof(ArgumentOutOfRangeException))]\r
+ public void CopyToBad()\r
+ {\r
+ tree.CopyTo(a, 11);\r
+ }\r
+\r
+\r
+ [Test]\r
+ [ExpectedException(typeof(ArgumentOutOfRangeException))]\r
+ public void CopyToBad2()\r
+ {\r
+ tree.CopyTo(a, -1);\r
+ }\r
+\r
+\r
+ [Test]\r
+ [ExpectedException(typeof(ArgumentOutOfRangeException))]\r
+ public void CopyToTooFar()\r
+ {\r
+ tree.Add(3);\r
+ tree.Add(4);\r
+ tree.CopyTo(a, 9);\r
+ }\r
+ }\r
+\r
+\r
+\r
+ [TestFixture]\r
+ public class Remove\r
+ {\r
+ private TreeBag<int> tree;\r
+\r
+\r
+ [SetUp]\r
+ public void Init()\r
+ {\r
+ tree = new TreeBag<int>(new IC());\r
+ for (int i = 10; i < 20; i++)\r
+ {\r
+ tree.Add(i);\r
+ tree.Add(i + 5);\r
+ }\r
+ //10,11,12,13,14,15,15,16,16,17,17,18,18,19,19,20,21,22,23,24\r
+ }\r
+\r
+\r
+ [Test]\r
+ public void SmallTrees()\r
+ {\r
+ tree.Clear();\r
+ tree.Add(9);\r
+ tree.Add(7);\r
+ tree.Add(9);\r
+ Assert.IsTrue(tree.Remove(7));\r
+ Assert.IsTrue(tree.Check(""));\r
+ }\r
+\r
+\r
+ [Test]\r
+ public void ByIndex()\r
+ {\r
+ //Remove root!\r
+ int n = tree.Count;\r
+ int i = tree[10];\r
+\r
+ Assert.AreEqual(17, tree.RemoveAt(10));\r
+ Assert.IsTrue(tree.Check(""));\r
+ Assert.IsTrue(tree.Contains(i));\r
+ Assert.AreEqual(n - 1, tree.Count);\r
+ Assert.AreEqual(17, tree.RemoveAt(9));\r
+ Assert.IsTrue(tree.Check(""));\r
+ Assert.IsFalse(tree.Contains(i));\r
+ Assert.AreEqual(n - 2, tree.Count);\r
+\r
+ //Low end\r
+ i = tree.FindMin();\r
+ tree.RemoveAt(0);\r
+ Assert.IsTrue(tree.Check(""));\r
+ Assert.IsFalse(tree.Contains(i));\r
+ Assert.AreEqual(n - 3, tree.Count);\r
+\r
+ //high end\r
+ i = tree.FindMax();\r
+ tree.RemoveAt(tree.Count - 1);\r
+ Assert.IsTrue(tree.Check(""));\r
+ Assert.IsFalse(tree.Contains(i));\r
+ Assert.AreEqual(n - 4, tree.Count);\r
+\r
+ //Some leaf\r
+ //tree.dump();\r
+ i = 18;\r
+ Assert.AreEqual(i, tree.RemoveAt(9));\r
+ Assert.IsTrue(tree.Check(""));\r
+ Assert.AreEqual(i, tree.RemoveAt(8));\r
+ Assert.IsTrue(tree.Check(""));\r
+ Assert.IsFalse(tree.Contains(i));\r
+ Assert.AreEqual(n - 6, tree.Count);\r
+ }\r
+\r
+\r
+ [Test]\r
+ public void AlmostEmpty()\r
+ {\r
+ //Almost empty\r
+ tree.Clear();\r
+ tree.Add(3);\r
+ tree.RemoveAt(0);\r
+ Assert.IsTrue(tree.Check(""));\r
+ Assert.IsFalse(tree.Contains(3));\r
+ Assert.AreEqual(0, tree.Count);\r
+ }\r
+\r
+\r
+ [Test]\r
+ [ExpectedException(typeof(IndexOutOfRangeException), "Index out of range for sequenced collectionvalue")]\r
+ public void Empty()\r
+ {\r
+ tree.Clear();\r
+ tree.RemoveAt(0);\r
+ }\r
+\r
+\r
+ [Test]\r
+ [ExpectedException(typeof(IndexOutOfRangeException), "Index out of range for sequenced collectionvalue")]\r
+ public void HighIndex()\r
+ {\r
+ tree.RemoveAt(tree.Count);\r
+ }\r
+\r
+\r
+ [Test]\r
+ [ExpectedException(typeof(IndexOutOfRangeException), "Index out of range for sequenced collectionvalue")]\r
+ public void LowIndex()\r
+ {\r
+ tree.RemoveAt(-1);\r
+ }\r
+\r
+\r
+ [Test]\r
+ public void Normal()\r
+ {\r
+ //Note: ids does not match for bag\r
+ Assert.IsFalse(tree.Remove(-20));\r
+\r
+ //1b\r
+ Assert.IsTrue(tree.Remove(20));\r
+ Assert.IsTrue(tree.Check("T1"));\r
+ Assert.IsFalse(tree.Remove(20));\r
+\r
+ //1b\r
+ Assert.IsTrue(tree.Remove(10));\r
+ Assert.IsTrue(tree.Check("Normal test 1"), "Bad tree");\r
+\r
+ //case 1c\r
+ Assert.IsTrue(tree.Remove(24));\r
+ Assert.IsTrue(tree.Check("Normal test 1"), "Bad tree");\r
+\r
+ //1a (terminating)\r
+ Assert.IsTrue(tree.Remove(16));\r
+ Assert.IsTrue(tree.Remove(16));\r
+ Assert.IsTrue(tree.Check("Normal test 1"), "Bad tree");\r
+\r
+ //2\r
+ Assert.IsTrue(tree.Remove(18));\r
+ Assert.IsTrue(tree.Remove(17));\r
+ Assert.IsTrue(tree.Remove(18));\r
+ Assert.IsTrue(tree.Remove(17));\r
+ Assert.IsTrue(tree.Check("Normal test 1"), "Bad tree");\r
+\r
+ //2+1b\r
+ Assert.IsTrue(tree.Remove(15));\r
+ Assert.IsTrue(tree.Remove(15));\r
+ for (int i = 0; i < 5; i++) tree.Add(17 + i);\r
+ Assert.IsTrue(tree.Remove(23));\r
+ Assert.IsTrue(tree.Check("Normal test 1"), "Bad tree");\r
+\r
+ //1a+1b\r
+ Assert.IsTrue(tree.Remove(11));\r
+ Assert.IsTrue(tree.Check("Normal test 1"), "Bad tree");\r
+\r
+ //2+1c\r
+ for (int i = 0; i < 10; i++)\r
+ tree.Add(50 - 2 * i);\r
+\r
+ Assert.IsTrue(tree.Remove(42));\r
+ Assert.IsTrue(tree.Remove(38));\r
+ Assert.IsTrue(tree.Remove(22));\r
+ Assert.IsTrue(tree.Remove(40));\r
+\r
+ //\r
+ for (int i = 0; i < 48; i++)\r
+ tree.Remove(i);\r
+\r
+ //Almost empty tree:*\r
+ Assert.IsFalse(tree.Remove(26));\r
+ Assert.IsTrue(tree.Remove(48));\r
+ Assert.IsTrue(tree.Check("Normal test 1"), "Bad tree");\r
+\r
+ //Empty tree:*\r
+ Assert.IsFalse(tree.Remove(26));\r
+ Assert.IsTrue(tree.Check("Normal test 1"), "Bad tree");\r
+ }\r
+\r
+\r
+ [TearDown]\r
+ public void Dispose()\r
+ {\r
+ tree = null;\r
+ }\r
+ }\r
+\r
+\r
+\r
+ [TestFixture]\r
+ public class PredecessorStructure\r
+ {\r
+ private TreeBag<int> tree;\r
+\r
+\r
+ [SetUp]\r
+ public void Init()\r
+ {\r
+ tree = new TreeBag<int>(new IC());\r
+ }\r
+\r
+\r
+ private void loadup()\r
+ {\r
+ for (int i = 0; i < 20; i++)\r
+ tree.Add(2 * i);\r
+ for (int i = 0; i < 10; i++)\r
+ tree.Add(4 * i);\r
+ }\r
+\r
+\r
+ [Test]\r
+ public void Predecessor()\r
+ {\r
+ loadup();\r
+ Assert.AreEqual(6, tree.Predecessor(7));\r
+ Assert.AreEqual(6, tree.Predecessor(8));\r
+\r
+ //The bottom\r
+ Assert.AreEqual(0, tree.Predecessor(1));\r
+\r
+ //The top\r
+ Assert.AreEqual(38, tree.Predecessor(39));\r
+ }\r
\r
- //The bottom\r
- Assert.AreEqual(0, tree.WeakPredecessor(1));\r
- Assert.AreEqual(0, tree.WeakPredecessor(0));\r
\r
- //The top\r
- Assert.AreEqual(38, tree.WeakPredecessor(39));\r
- Assert.AreEqual(38, tree.WeakPredecessor(38));\r
- }\r
+ [Test]\r
+ [ExpectedException(typeof(NoSuchItemException))]\r
+ public void PredecessorTooLow1()\r
+ {\r
+ tree.Predecessor(-2);\r
+ }\r
+\r
\r
+ [Test]\r
+ [ExpectedException(typeof(NoSuchItemException))]\r
+ public void PredecessorTooLow2()\r
+ {\r
+ tree.Predecessor(0);\r
+ }\r
\r
- [Test]\r
- [ExpectedException(typeof(ArgumentOutOfRangeException))]\r
- public void WeakPredecessorTooLow1()\r
- {\r
- tree.WeakPredecessor(-2);\r
- }\r
\r
+ [Test]\r
+ public void WeakPredecessor()\r
+ {\r
+ loadup();\r
+ Assert.AreEqual(6, tree.WeakPredecessor(7));\r
+ Assert.AreEqual(8, tree.WeakPredecessor(8));\r
\r
- [Test]\r
- public void Successor()\r
- {\r
- loadup();\r
- Assert.AreEqual(8, tree.Successor(7));\r
- Assert.AreEqual(10, tree.Successor(8));\r
+ //The bottom\r
+ Assert.AreEqual(0, tree.WeakPredecessor(1));\r
+ Assert.AreEqual(0, tree.WeakPredecessor(0));\r
\r
- //The bottom\r
- Assert.AreEqual(2, tree.Successor(0));\r
- Assert.AreEqual(0, tree.Successor(-1));\r
+ //The top\r
+ Assert.AreEqual(38, tree.WeakPredecessor(39));\r
+ Assert.AreEqual(38, tree.WeakPredecessor(38));\r
+ }\r
\r
- //The top\r
- Assert.AreEqual(38, tree.Successor(37));\r
- }\r
\r
+ [Test]\r
+ [ExpectedException(typeof(NoSuchItemException))]\r
+ public void WeakPredecessorTooLow1()\r
+ {\r
+ tree.WeakPredecessor(-2);\r
+ }\r
\r
- [Test]\r
- [ExpectedException(typeof(ArgumentOutOfRangeException))]\r
- public void SuccessorTooHigh1()\r
- {\r
- tree.Successor(38);\r
- }\r
-\r
-\r
- [Test]\r
- [ExpectedException(typeof(ArgumentOutOfRangeException))]\r
- public void SuccessorTooHigh2()\r
- {\r
- tree.Successor(39);\r
- }\r
-\r
-\r
- [Test]\r
- public void WeakSuccessor()\r
- {\r
- loadup();\r
- Assert.AreEqual(6, tree.WeakSuccessor(6));\r
- Assert.AreEqual(8, tree.WeakSuccessor(7));\r
-\r
- //The bottom\r
- Assert.AreEqual(0, tree.WeakSuccessor(-1));\r
- Assert.AreEqual(0, tree.WeakSuccessor(0));\r
-\r
- //The top\r
- Assert.AreEqual(38, tree.WeakSuccessor(37));\r
- Assert.AreEqual(38, tree.WeakSuccessor(38));\r
- }\r
\r
+ [Test]\r
+ public void Successor()\r
+ {\r
+ loadup();\r
+ Assert.AreEqual(8, tree.Successor(7));\r
+ Assert.AreEqual(10, tree.Successor(8));\r
\r
- [Test]\r
- [ExpectedException(typeof(ArgumentOutOfRangeException))]\r
- public void WeakSuccessorTooHigh1()\r
- {\r
- tree.WeakSuccessor(39);\r
- }\r
+ //The bottom\r
+ Assert.AreEqual(2, tree.Successor(0));\r
+ Assert.AreEqual(0, tree.Successor(-1));\r
\r
+ //The top\r
+ Assert.AreEqual(38, tree.Successor(37));\r
+ }\r
\r
- [TearDown]\r
- public void Dispose()\r
- {\r
- tree = null;\r
- }\r
- }\r
\r
+ [Test]\r
+ [ExpectedException(typeof(NoSuchItemException))]\r
+ public void SuccessorTooHigh1()\r
+ {\r
+ tree.Successor(38);\r
+ }\r
+\r
+\r
+ [Test]\r
+ [ExpectedException(typeof(NoSuchItemException))]\r
+ public void SuccessorTooHigh2()\r
+ {\r
+ tree.Successor(39);\r
+ }\r
+\r
+\r
+ [Test]\r
+ public void WeakSuccessor()\r
+ {\r
+ loadup();\r
+ Assert.AreEqual(6, tree.WeakSuccessor(6));\r
+ Assert.AreEqual(8, tree.WeakSuccessor(7));\r
+\r
+ //The bottom\r
+ Assert.AreEqual(0, tree.WeakSuccessor(-1));\r
+ Assert.AreEqual(0, tree.WeakSuccessor(0));\r
+\r
+ //The top\r
+ Assert.AreEqual(38, tree.WeakSuccessor(37));\r
+ Assert.AreEqual(38, tree.WeakSuccessor(38));\r
+ }\r
\r
\r
- [TestFixture]\r
- public class PriorityQueue\r
- {\r
- private TreeBag<int> tree;\r
+ [Test]\r
+ [ExpectedException(typeof(NoSuchItemException))]\r
+ public void WeakSuccessorTooHigh1()\r
+ {\r
+ tree.WeakSuccessor(39);\r
+ }\r
\r
\r
- [SetUp]\r
- public void Init()\r
- {\r
- tree = new TreeBag<int>(new IC());\r
- }\r
+ [TearDown]\r
+ public void Dispose()\r
+ {\r
+ tree = null;\r
+ }\r
+ }\r
\r
\r
- private void loadup()\r
- {\r
- foreach (int i in new int[] { 1, 2, 3, 4 })\r
- tree.Add(i);\r
- tree.Add(1);\r
- tree.Add(3);\r
- }\r
\r
+ [TestFixture]\r
+ public class PriorityQueue\r
+ {\r
+ private TreeBag<int> tree;\r
\r
- [Test]\r
- public void Normal()\r
- {\r
- loadup();\r
- Assert.AreEqual(1, tree.FindMin());\r
- Assert.AreEqual(4, tree.FindMax());\r
- Assert.AreEqual(1, tree.DeleteMin());\r
- Assert.AreEqual(4, tree.DeleteMax());\r
- Assert.IsTrue(tree.Check("Normal test 1"), "Bad tree");\r
- Assert.AreEqual(1, tree.FindMin());\r
- Assert.AreEqual(3, tree.FindMax());\r
- Assert.AreEqual(1, tree.DeleteMin());\r
- Assert.AreEqual(3, tree.DeleteMax());\r
- Assert.IsTrue(tree.Check("Normal test 2"), "Bad tree");\r
- }\r
-\r
-\r
- [Test]\r
- [ExpectedException(typeof(InvalidOperationException), "Priority queue is empty")]\r
- public void Empty1()\r
- {\r
- tree.FindMin();\r
- }\r
-\r
-\r
- [Test]\r
- [ExpectedException(typeof(InvalidOperationException), "Priority queue is empty")]\r
- public void Empty2()\r
- {\r
- tree.FindMax();\r
- }\r
-\r
-\r
- [Test]\r
- [ExpectedException(typeof(InvalidOperationException), "Priority queue is empty")]\r
- public void Empty3()\r
- {\r
- tree.DeleteMin();\r
- }\r
-\r
-\r
- [Test]\r
- [ExpectedException(typeof(InvalidOperationException), "Priority queue is empty")]\r
- public void Empty4()\r
- {\r
- tree.DeleteMax();\r
- }\r
-\r
-\r
- [TearDown]\r
- public void Dispose()\r
- {\r
- tree = null;\r
- }\r
- }\r
-\r
-\r
-\r
- [TestFixture]\r
- public class IndexingAndCounting\r
- {\r
- private TreeBag<int> tree;\r
-\r
-\r
- [SetUp]\r
- public void Init()\r
- {\r
- tree = new TreeBag<int>(new IC());\r
- }\r
-\r
-\r
- private void populate()\r
- {\r
- tree.Add(30);\r
- tree.Add(30);\r
- tree.Add(50);\r
- tree.Add(10);\r
- tree.Add(70);\r
- tree.Add(70);\r
- }\r
-\r
-\r
- [Test]\r
- public void ToArray()\r
- {\r
- populate();\r
-\r
- int[] a = tree.ToArray();\r
-\r
- Assert.AreEqual(6, a.Length);\r
- Assert.AreEqual(10, a[0]);\r
- Assert.AreEqual(30, a[1]);\r
- Assert.AreEqual(30, a[2]);\r
- Assert.AreEqual(50, a[3]);\r
- Assert.AreEqual(70, a[4]);\r
- Assert.AreEqual(70, a[5]);\r
- }\r
-\r
-\r
- [Test]\r
- public void GoodIndex()\r
- {\r
- Assert.AreEqual(-1, tree.IndexOf(20));\r
- Assert.AreEqual(-1, tree.LastIndexOf(20));\r
- populate();\r
- Assert.AreEqual(10, tree[0]);\r
- Assert.AreEqual(30, tree[1]);\r
- Assert.AreEqual(30, tree[2]);\r
- Assert.AreEqual(50, tree[3]);\r
- Assert.AreEqual(70, tree[4]);\r
- Assert.AreEqual(70, tree[5]);\r
- Assert.AreEqual(0, tree.IndexOf(10));\r
- Assert.AreEqual(1, tree.IndexOf(30));\r
- Assert.AreEqual(3, tree.IndexOf(50));\r
- Assert.AreEqual(4, tree.IndexOf(70));\r
- Assert.AreEqual(-1, tree.IndexOf(20));\r
- Assert.AreEqual(-1, tree.IndexOf(0));\r
- Assert.AreEqual(-1, tree.IndexOf(90));\r
- Assert.AreEqual(0, tree.LastIndexOf(10));\r
- Assert.AreEqual(2, tree.LastIndexOf(30));\r
- Assert.AreEqual(3, tree.LastIndexOf(50));\r
- Assert.AreEqual(5, tree.LastIndexOf(70));\r
- Assert.AreEqual(-1, tree.LastIndexOf(20));\r
- Assert.AreEqual(-1, tree.LastIndexOf(0));\r
- Assert.AreEqual(-1, tree.LastIndexOf(90));\r
- }\r
-\r
-\r
- [Test]\r
- [ExpectedException(typeof(IndexOutOfRangeException))]\r
- public void IndexTooLarge()\r
- {\r
- populate();\r
- Console.WriteLine(tree[6]);\r
- }\r
-\r
-\r
- [Test]\r
- [ExpectedException(typeof(IndexOutOfRangeException))]\r
- public void IndexTooSmall()\r
- {\r
- populate();\r
- Console.WriteLine(tree[-1]);\r
- }\r
-\r
-\r
- [Test]\r
- public void FilledTreeOutsideInput()\r
- {\r
- populate();\r
- Assert.AreEqual(0, tree.CountFrom(90));\r
- Assert.AreEqual(0, tree.CountFromTo(-20, 0));\r
- Assert.AreEqual(0, tree.CountFromTo(80, 100));\r
- Assert.AreEqual(0, tree.CountTo(0));\r
- Assert.AreEqual(6, tree.CountTo(90));\r
- Assert.AreEqual(6, tree.CountFromTo(-20, 90));\r
- Assert.AreEqual(6, tree.CountFrom(0));\r
- }\r
-\r
-\r
- [Test]\r
- public void FilledTreeIntermediateInput()\r
- {\r
- populate();\r
- Assert.AreEqual(5, tree.CountFrom(20));\r
- Assert.AreEqual(2, tree.CountFromTo(20, 40));\r
- Assert.AreEqual(3, tree.CountTo(40));\r
- }\r
-\r
-\r
- [Test]\r
- public void FilledTreeMatchingInput()\r
- {\r
- populate();\r
- Assert.AreEqual(5, tree.CountFrom(30));\r
- Assert.AreEqual(3, tree.CountFromTo(30, 70));\r
- Assert.AreEqual(0, tree.CountFromTo(50, 30));\r
- Assert.AreEqual(0, tree.CountFromTo(50, 50));\r
- Assert.AreEqual(0, tree.CountTo(10));\r
- Assert.AreEqual(3, tree.CountTo(50));\r
- }\r
-\r
-\r
- [Test]\r
- public void CountEmptyTree()\r
- {\r
- Assert.AreEqual(0, tree.CountFrom(20));\r
- Assert.AreEqual(0, tree.CountFromTo(20, 40));\r
- Assert.AreEqual(0, tree.CountTo(40));\r
- }\r
-\r
-\r
- [TearDown]\r
- public void Dispose()\r
- {\r
- tree = null;\r
- }\r
- }\r
-\r
-\r
-\r
-\r
- namespace ModificationCheck\r
- {\r
- [TestFixture]\r
- public class Enumerator\r
- {\r
- private TreeBag<int> tree;\r
-\r
- private MSG.IEnumerator<int> e;\r
-\r
-\r
- [SetUp]\r
- public void Init()\r
- {\r
- tree = new TreeBag<int>(new IC());\r
- for (int i = 0; i < 10; i++)\r
- tree.Add(i);\r
- tree.Add(3); \r
- tree.Add(7);\r
- e = tree.GetEnumerator();\r
- }\r
-\r
-\r
- [Test]\r
- public void CurrentAfterModification()\r
- {\r
- e.MoveNext();\r
- tree.Add(34);\r
- Assert.AreEqual(0, e.Current);\r
- }\r
-\r
-\r
- [Test]\r
- [ExpectedException(typeof(InvalidOperationException), "Collection was modified")]\r
- public void MoveNextAfterAdd()\r
- {\r
- tree.Add(34);\r
- e.MoveNext();\r
- }\r
-\r
-\r
- [Test]\r
- [ExpectedException(typeof(InvalidOperationException), "Collection was modified")]\r
- public void MoveNextAfterRemove()\r
- {\r
- tree.Remove(34);\r
- e.MoveNext();\r
- }\r
-\r
-\r
- [Test]\r
- [ExpectedException(typeof(InvalidOperationException), "Collection was modified")]\r
- public void MoveNextAfterClear()\r
- {\r
- tree.Clear();\r
- e.MoveNext();\r
- }\r
-\r
-\r
- [TearDown]\r
- public void Dispose()\r
- {\r
- tree = null;\r
- e = null;\r
- }\r
- }\r
\r
+ [SetUp]\r
+ public void Init()\r
+ {\r
+ tree = new TreeBag<int>(new IC());\r
+ }\r
\r
\r
- [TestFixture]\r
- public class RangeEnumerator\r
- {\r
- private TreeBag<int> tree;\r
+ private void loadup()\r
+ {\r
+ foreach (int i in new int[] { 1, 2, 3, 4 })\r
+ tree.Add(i);\r
+ tree.Add(1);\r
+ tree.Add(3);\r
+ }\r
\r
- private MSG.IEnumerator<int> e;\r
\r
+ [Test]\r
+ public void Normal()\r
+ {\r
+ loadup();\r
+ Assert.AreEqual(1, tree.FindMin());\r
+ Assert.AreEqual(4, tree.FindMax());\r
+ Assert.AreEqual(1, tree.DeleteMin());\r
+ Assert.AreEqual(4, tree.DeleteMax());\r
+ Assert.IsTrue(tree.Check("Normal test 1"), "Bad tree");\r
+ Assert.AreEqual(1, tree.FindMin());\r
+ Assert.AreEqual(3, tree.FindMax());\r
+ Assert.AreEqual(1, tree.DeleteMin());\r
+ Assert.AreEqual(3, tree.DeleteMax());\r
+ Assert.IsTrue(tree.Check("Normal test 2"), "Bad tree");\r
+ }\r
+\r
+\r
+ [Test]\r
+ [ExpectedException(typeof(NoSuchItemException))]\r
+ public void Empty1()\r
+ {\r
+ tree.FindMin();\r
+ }\r
+\r
+\r
+ [Test]\r
+ [ExpectedException(typeof(NoSuchItemException))]\r
+ public void Empty2()\r
+ {\r
+ tree.FindMax();\r
+ }\r
+\r
+\r
+ [Test]\r
+ [ExpectedException(typeof(NoSuchItemException))]\r
+ public void Empty3()\r
+ {\r
+ tree.DeleteMin();\r
+ }\r
+\r
+\r
+ [Test]\r
+ [ExpectedException(typeof(NoSuchItemException))]\r
+ public void Empty4()\r
+ {\r
+ tree.DeleteMax();\r
+ }\r
+\r
+\r
+ [TearDown]\r
+ public void Dispose()\r
+ {\r
+ tree = null;\r
+ }\r
+ }\r
+\r
+\r
+\r
+ [TestFixture]\r
+ public class IndexingAndCounting\r
+ {\r
+ private TreeBag<int> tree;\r
+\r
+\r
+ [SetUp]\r
+ public void Init()\r
+ {\r
+ tree = new TreeBag<int>(new IC());\r
+ }\r
+\r
+\r
+ private void populate()\r
+ {\r
+ tree.Add(30);\r
+ tree.Add(30);\r
+ tree.Add(50);\r
+ tree.Add(10);\r
+ tree.Add(70);\r
+ tree.Add(70);\r
+ }\r
+\r
+\r
+ [Test]\r
+ public void ToArray()\r
+ {\r
+ populate();\r
+\r
+ int[] a = tree.ToArray();\r
+\r
+ Assert.AreEqual(6, a.Length);\r
+ Assert.AreEqual(10, a[0]);\r
+ Assert.AreEqual(30, a[1]);\r
+ Assert.AreEqual(30, a[2]);\r
+ Assert.AreEqual(50, a[3]);\r
+ Assert.AreEqual(70, a[4]);\r
+ Assert.AreEqual(70, a[5]);\r
+ }\r
+\r
+\r
+ [Test]\r
+ public void GoodIndex()\r
+ {\r
+ Assert.AreEqual(-1, tree.IndexOf(20));\r
+ Assert.AreEqual(-1, tree.LastIndexOf(20));\r
+ populate();\r
+ Assert.AreEqual(10, tree[0]);\r
+ Assert.AreEqual(30, tree[1]);\r
+ Assert.AreEqual(30, tree[2]);\r
+ Assert.AreEqual(50, tree[3]);\r
+ Assert.AreEqual(70, tree[4]);\r
+ Assert.AreEqual(70, tree[5]);\r
+ Assert.AreEqual(0, tree.IndexOf(10));\r
+ Assert.AreEqual(1, tree.IndexOf(30));\r
+ Assert.AreEqual(3, tree.IndexOf(50));\r
+ Assert.AreEqual(4, tree.IndexOf(70));\r
+ Assert.AreEqual(~1, tree.IndexOf(20));\r
+ Assert.AreEqual(~0, tree.IndexOf(0));\r
+ Assert.AreEqual(~6, tree.IndexOf(90));\r
+ Assert.AreEqual(0, tree.LastIndexOf(10));\r
+ Assert.AreEqual(2, tree.LastIndexOf(30));\r
+ Assert.AreEqual(3, tree.LastIndexOf(50));\r
+ Assert.AreEqual(5, tree.LastIndexOf(70));\r
+ Assert.AreEqual(~1, tree.LastIndexOf(20));\r
+ Assert.AreEqual(~0, tree.LastIndexOf(0));\r
+ Assert.AreEqual(~6, tree.LastIndexOf(90));\r
+ }\r
+\r
+\r
+ [Test]\r
+ [ExpectedException(typeof(IndexOutOfRangeException))]\r
+ public void IndexTooLarge()\r
+ {\r
+ populate();\r
+ Console.WriteLine(tree[6]);\r
+ }\r
+\r
+\r
+ [Test]\r
+ [ExpectedException(typeof(IndexOutOfRangeException))]\r
+ public void IndexTooSmall()\r
+ {\r
+ populate();\r
+ Console.WriteLine(tree[-1]);\r
+ }\r
+\r
+\r
+ [Test]\r
+ public void FilledTreeOutsideInput()\r
+ {\r
+ populate();\r
+ Assert.AreEqual(0, tree.CountFrom(90));\r
+ Assert.AreEqual(0, tree.CountFromTo(-20, 0));\r
+ Assert.AreEqual(0, tree.CountFromTo(80, 100));\r
+ Assert.AreEqual(0, tree.CountTo(0));\r
+ Assert.AreEqual(6, tree.CountTo(90));\r
+ Assert.AreEqual(6, tree.CountFromTo(-20, 90));\r
+ Assert.AreEqual(6, tree.CountFrom(0));\r
+ }\r
+\r
+\r
+ [Test]\r
+ public void FilledTreeIntermediateInput()\r
+ {\r
+ populate();\r
+ Assert.AreEqual(5, tree.CountFrom(20));\r
+ Assert.AreEqual(2, tree.CountFromTo(20, 40));\r
+ Assert.AreEqual(3, tree.CountTo(40));\r
+ }\r
+\r
+\r
+ [Test]\r
+ public void FilledTreeMatchingInput()\r
+ {\r
+ populate();\r
+ Assert.AreEqual(5, tree.CountFrom(30));\r
+ Assert.AreEqual(3, tree.CountFromTo(30, 70));\r
+ Assert.AreEqual(0, tree.CountFromTo(50, 30));\r
+ Assert.AreEqual(0, tree.CountFromTo(50, 50));\r
+ Assert.AreEqual(0, tree.CountTo(10));\r
+ Assert.AreEqual(3, tree.CountTo(50));\r
+ }\r
+\r
+\r
+ [Test]\r
+ public void CountEmptyTree()\r
+ {\r
+ Assert.AreEqual(0, tree.CountFrom(20));\r
+ Assert.AreEqual(0, tree.CountFromTo(20, 40));\r
+ Assert.AreEqual(0, tree.CountTo(40));\r
+ }\r
+\r
+\r
+ [TearDown]\r
+ public void Dispose()\r
+ {\r
+ tree = null;\r
+ }\r
+ }\r
+\r
+\r
+\r
+\r
+ namespace ModificationCheck\r
+ {\r
+ [TestFixture]\r
+ public class Enumerator\r
+ {\r
+ private TreeBag<int> tree;\r
+\r
+ private SCG.IEnumerator<int> e;\r
+\r
+\r
+ [SetUp]\r
+ public void Init()\r
+ {\r
+ tree = new TreeBag<int>(new IC());\r
+ for (int i = 0; i < 10; i++)\r
+ tree.Add(i);\r
+ tree.Add(3);\r
+ tree.Add(7);\r
+ e = tree.GetEnumerator();\r
+ }\r
+\r
+\r
+ [Test]\r
+ public void CurrentAfterModification()\r
+ {\r
+ e.MoveNext();\r
+ tree.Add(34);\r
+ Assert.AreEqual(0, e.Current);\r
+ }\r
+\r
+\r
+ [Test]\r
+ [ExpectedException(typeof(CollectionModifiedException))]\r
+ public void MoveNextAfterAdd()\r
+ {\r
+ tree.Add(34);\r
+ e.MoveNext();\r
+ }\r
+\r
+\r
+ [Test]\r
+ [ExpectedException(typeof(CollectionModifiedException))]\r
+ public void MoveNextAfterRemove()\r
+ {\r
+ tree.Remove(34);\r
+ e.MoveNext();\r
+ }\r
+\r
+\r
+ [Test]\r
+ [ExpectedException(typeof(CollectionModifiedException))]\r
+ public void MoveNextAfterClear()\r
+ {\r
+ tree.Clear();\r
+ e.MoveNext();\r
+ }\r
+\r
+\r
+ [TearDown]\r
+ public void Dispose()\r
+ {\r
+ tree = null;\r
+ e = null;\r
+ }\r
+ }\r
\r
- [SetUp]\r
- public void Init()\r
- {\r
- tree = new TreeBag<int>(new IC());\r
- for (int i = 0; i < 10; i++)\r
- tree.Add(i);\r
\r
- e = tree.RangeFromTo(3, 7).GetEnumerator();\r
- }\r
\r
+ [TestFixture]\r
+ public class RangeEnumerator\r
+ {\r
+ private TreeBag<int> tree;\r
\r
- [Test]\r
- public void CurrentAfterModification()\r
- {\r
- e.MoveNext();\r
- tree.Add(34);\r
- Assert.AreEqual(3, e.Current);\r
- }\r
+ private SCG.IEnumerator<int> e;\r
\r
\r
- [Test]\r
- [ExpectedException(typeof(InvalidOperationException), "Collection was modified")]\r
- public void MoveNextAfterAdd()\r
- {\r
- tree.Add(34);\r
- e.MoveNext();\r
- }\r
-\r
-\r
- [Test]\r
- [ExpectedException(typeof(InvalidOperationException), "Collection was modified")]\r
- public void MoveNextAfterRemove()\r
- {\r
- tree.Remove(34);\r
- e.MoveNext();\r
- }\r
-\r
-\r
- [Test]\r
- [ExpectedException(typeof(InvalidOperationException), "Collection was modified")]\r
- public void MoveNextAfterClear()\r
- {\r
- tree.Clear();\r
- e.MoveNext();\r
- }\r
-\r
-\r
- [TearDown]\r
- public void Dispose()\r
- {\r
- tree = null;\r
- e = null;\r
- }\r
- }\r
- }\r
-\r
-\r
-\r
-\r
- namespace PathcopyPersistence\r
- {\r
- [TestFixture]\r
- public class Navigation\r
- {\r
- private TreeBag<int> tree, snap;\r
-\r
- private IComparer<int> ic;\r
-\r
-\r
- [SetUp]\r
- public void Init()\r
- {\r
- ic = new IC();\r
- tree = new TreeBag<int>(ic);\r
- for (int i = 0; i <= 20; i++)\r
- tree.Add(2 * i + 1);\r
- tree.Add(13);\r
- snap = (TreeBag<int>)tree.Snapshot();\r
- for (int i = 0; i <= 10; i++)\r
- tree.Remove(4 * i + 1);\r
- }\r
-\r
-\r
- private bool twomodeleven(int i)\r
- {\r
- return i % 11 == 2;\r
- }\r
-\r
-\r
- [Test]\r
- public void InternalEnum()\r
- {\r
- Assert.IsTrue(IC.eq(snap.FindAll(new Filter<int>(twomodeleven)), 13, 13, 35));\r
- }\r
-\r
-\r
- public void MoreCut()\r
- {\r
- //TODO: Assert.Fail("more tests of Cut needed");\r
- }\r
-\r
-\r
- [Test]\r
- public void Cut()\r
- {\r
- int lo, hi;\r
- bool lv, hv;\r
-\r
- Assert.IsFalse(snap.Cut(new HigherOrder.CubeRoot(64), out lo, out lv, out hi, out hv));\r
- Assert.IsTrue(lv && hv);\r
- Assert.AreEqual(5, hi);\r
- Assert.AreEqual(3, lo);\r
- Assert.IsTrue(snap.Cut(new HigherOrder.CubeRoot(125), out lo, out lv, out hi, out hv));\r
- Assert.IsTrue(lv && hv);\r
- Assert.AreEqual(7, hi);\r
- Assert.AreEqual(3, lo);\r
- Assert.IsFalse(snap.Cut(new HigherOrder.CubeRoot(125000), out lo, out lv, out hi, out hv));\r
- Assert.IsTrue(lv && !hv);\r
- Assert.AreEqual(41, lo);\r
- Assert.IsFalse(snap.Cut(new HigherOrder.CubeRoot(-27), out lo, out lv, out hi, out hv));\r
- Assert.IsTrue(!lv && hv);\r
- Assert.AreEqual(1, hi);\r
- }\r
-\r
-\r
- [Test]\r
- public void Range()\r
- {\r
- Assert.IsTrue(IC.eq(snap.RangeFromTo(5, 16), 5, 7, 9, 11,13, 13, 15));\r
- Assert.IsTrue(IC.eq(snap.RangeFromTo(5, 17), 5, 7, 9, 11,13, 13, 15));\r
- Assert.IsTrue(IC.eq(snap.RangeFromTo(6, 16), 7, 9, 11,13, 13, 15));\r
- }\r
-\r
-\r
- [Test]\r
- public void Contains()\r
- {\r
- Assert.IsTrue(snap.Contains(5));\r
- Assert.IsTrue(snap.Contains(13));\r
- Assert.AreEqual(1, snap.ContainsCount(5));\r
- Assert.AreEqual(2, snap.ContainsCount(13));\r
- }\r
-\r
-\r
- [Test]\r
- public void FindMin()\r
- {\r
- Assert.AreEqual(1, snap.FindMin());\r
- }\r
-\r
-\r
- [Test]\r
- public void FindMax()\r
- {\r
- Assert.AreEqual(41, snap.FindMax());\r
- }\r
-\r
-\r
- [Test]\r
- public void Predecessor()\r
- {\r
- Assert.AreEqual(13, snap.Predecessor(15));\r
- Assert.AreEqual(15, snap.Predecessor(16));\r
- Assert.AreEqual(15, snap.Predecessor(17));\r
- Assert.AreEqual(17, snap.Predecessor(18));\r
- }\r
-\r
-\r
- [Test]\r
- public void Successor()\r
- {\r
- Assert.AreEqual(17, snap.Successor(15));\r
- Assert.AreEqual(17, snap.Successor(16));\r
- Assert.AreEqual(19, snap.Successor(17));\r
- Assert.AreEqual(19, snap.Successor(18));\r
- }\r
-\r
-\r
- [Test]\r
- public void WeakPredecessor()\r
- {\r
- Assert.AreEqual(15, snap.WeakPredecessor(15));\r
- Assert.AreEqual(15, snap.WeakPredecessor(16));\r
- Assert.AreEqual(17, snap.WeakPredecessor(17));\r
- Assert.AreEqual(17, snap.WeakPredecessor(18));\r
- }\r
-\r
-\r
- [Test]\r
- public void WeakSuccessor()\r
- {\r
- Assert.AreEqual(15, snap.WeakSuccessor(15));\r
- Assert.AreEqual(17, snap.WeakSuccessor(16));\r
- Assert.AreEqual(17, snap.WeakSuccessor(17));\r
- Assert.AreEqual(19, snap.WeakSuccessor(18));\r
- }\r
-\r
-\r
- [Test]\r
- [ExpectedException(typeof(NotSupportedException), "Indexing not supported for snapshots")]\r
- public void CountTo()\r
- {\r
- int j = snap.CountTo(15);\r
- }\r
-\r
-\r
- [Test]\r
- [ExpectedException(typeof(NotSupportedException), "Indexing not supported for snapshots")]\r
- public void Indexing()\r
- {\r
- int j = snap[4];\r
- }\r
-\r
-\r
- [Test]\r
- [ExpectedException(typeof(NotSupportedException), "Indexing not supported for snapshots")]\r
- public void Indexing2()\r
- {\r
- int j = snap.IndexOf(5);\r
- }\r
-\r
-\r
- [TearDown]\r
- public void Dispose()\r
- {\r
- tree = null;\r
- ic = null;\r
- }\r
- }\r
-\r
-\r
-\r
- [TestFixture]\r
- public class Single\r
- {\r
- private TreeBag<int> tree;\r
-\r
- private IComparer<int> ic;\r
-\r
-\r
- [SetUp]\r
- public void Init()\r
- {\r
- ic = new IC();\r
- tree = new TreeBag<int>(ic);\r
- for (int i = 0; i < 10; i++)\r
- tree.Add(2 * i + 1);\r
- }\r
-\r
-\r
- [Test]\r
- public void EnumerationWithAdd()\r
- {\r
- int[] orig = new int[] { 1, 3, 5, 7, 9, 11, 13, 15, 17, 19 };\r
- int i = 0;\r
- TreeBag<int> snap = (TreeBag<int>)tree.Snapshot();\r
-\r
- foreach (int j in snap)\r
- {\r
- Assert.AreEqual(1 + 2 * i++, j);\r
- tree.Add(21 - j);\r
- Assert.IsTrue(snap.Check("M"), "Bad snap!");\r
- Assert.IsTrue(IC.eq(snap, orig), "Snap was changed!");\r
- Assert.IsTrue(tree.Check("Tree"), "Bad tree!");\r
- }\r
- }\r
-\r
-\r
- [Test]\r
- public void Remove()\r
- {\r
- int[] orig = new int[] { 1, 3, 5, 7, 9, 11, 13, 15, 17, 19 };\r
- TreeBag<int> snap = (TreeBag<int>)tree.Snapshot();\r
-\r
- Assert.IsTrue(snap.Check("Snap"), "Bad snap!");\r
- Assert.IsTrue(IC.eq(snap, orig), "Snap was changed!");\r
- tree.Remove(19);\r
- Assert.IsTrue(snap.Check("Snap"), "Bad snap!");\r
- Assert.IsTrue(tree.Check("Tree"), "Bad tree!");\r
- Assert.IsTrue(IC.eq(snap, orig), "Snap was changed!");\r
- }\r
-\r
-\r
- [Test]\r
- public void RemoveNormal()\r
- {\r
- tree.Clear();\r
- for (int i = 10; i < 20; i++)\r
- {\r
- tree.Add(i);\r
- tree.Add(i + 10);\r
- }\r
- tree.Add(15);\r
-\r
- int[] orig = new int[] { 10, 11, 12, 13, 14, 15, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29 };\r
- TreeBag<int> snap = (TreeBag<int>)tree.Snapshot();\r
-\r
- Assert.IsFalse(tree.Remove(-20));\r
- Assert.IsTrue(snap.Check("Snap"), "Bad snap!");\r
- Assert.IsTrue(IC.eq(snap, orig), "Snap was changed!");\r
-\r
-\r
- //decrease items case\r
- Assert.IsTrue(tree.Remove(15));\r
- Assert.IsTrue(tree.Check("T1"));\r
- Assert.IsTrue(snap.Check("Snap"), "Bad snap!");\r
- //snap.dump();\r
- Assert.IsTrue(IC.eq(snap, orig), "Snap was changed!");\r
-\r
- //No demote case, with move_item\r
- Assert.IsTrue(tree.Remove(20));\r
- Assert.IsTrue(tree.Check("T1"));\r
- Assert.IsTrue(snap.Check("Snap"), "Bad snap!");\r
- Assert.IsTrue(IC.eq(snap, orig), "Snap was changed!");\r
- Assert.IsFalse(tree.Remove(20));\r
-\r
- //plain case 2\r
- tree.Snapshot();\r
- Assert.IsTrue(tree.Remove(14));\r
- Assert.IsTrue(tree.Check("Normal test 1"), "Bad tree");\r
- Assert.IsTrue(snap.Check("Snap"), "Bad snap!");\r
- Assert.IsTrue(IC.eq(snap, orig), "Snap was changed!");\r
-\r
- //case 1b\r
- Assert.IsTrue(tree.Remove(25));\r
- Assert.IsTrue(tree.Check("Normal test 1"), "Bad tree");\r
- Assert.IsTrue(snap.Check("Snap"), "Bad snap!");\r
- Assert.IsTrue(IC.eq(snap, orig), "Snap was changed!");\r
-\r
- //case 1c\r
- Assert.IsTrue(tree.Remove(29));\r
- Assert.IsTrue(tree.Check("Normal test 1"), "Bad tree");\r
- Assert.IsTrue(snap.Check("Snap"), "Bad snap!");\r
- Assert.IsTrue(IC.eq(snap, orig), "Snap was changed!");\r
-\r
- //1a (terminating)\r
- Assert.IsTrue(tree.Remove(10));\r
- Assert.IsTrue(tree.Check("Normal test 1"), "Bad tree");\r
- Assert.IsTrue(snap.Check("Snap"), "Bad snap!");\r
- Assert.IsTrue(IC.eq(snap, orig), "Snap was changed!");\r
-\r
- //2+1b\r
- Assert.IsTrue(tree.Remove(12));\r
- tree.Snapshot();\r
- Assert.IsTrue(tree.Remove(11));\r
- Assert.IsTrue(tree.Check("Normal test 1"), "Bad tree");\r
- Assert.IsTrue(snap.Check("Snap"), "Bad snap!");\r
- Assert.IsTrue(IC.eq(snap, orig), "Snap was changed!");\r
-\r
- //1a+1b\r
- Assert.IsTrue(tree.Remove(18));\r
- Assert.IsTrue(tree.Remove(13));\r
- Assert.IsTrue(tree.Remove(15));\r
- Assert.IsTrue(tree.Check("Normal test 1"), "Bad tree");\r
- Assert.IsTrue(snap.Check("Snap"), "Bad snap!");\r
- Assert.IsTrue(IC.eq(snap, orig), "Snap was changed!");\r
-\r
- //2+1c\r
- for (int i = 0; i < 10; i++)\r
- tree.Add(50 - 2 * i);\r
-\r
- Assert.IsTrue(tree.Remove(42));\r
- Assert.IsTrue(tree.Remove(38));\r
- Assert.IsTrue(tree.Remove(28));\r
- Assert.IsTrue(tree.Remove(40));\r
- Assert.IsTrue(tree.Check("Normal test 1"), "Bad tree");\r
- Assert.IsTrue(snap.Check("Snap"), "Bad snap!");\r
- Assert.IsTrue(IC.eq(snap, orig), "Snap was changed!");\r
-\r
- //\r
- Assert.IsTrue(tree.Remove(16));\r
- Assert.IsTrue(tree.Remove(23));\r
- Assert.IsTrue(tree.Remove(17));\r
- Assert.IsTrue(tree.Remove(19));\r
- Assert.IsTrue(tree.Remove(50));\r
- Assert.IsTrue(tree.Remove(26));\r
- Assert.IsTrue(tree.Remove(21));\r
- Assert.IsTrue(tree.Remove(22));\r
- Assert.IsTrue(tree.Remove(24));\r
- for (int i = 0; i < 48; i++)\r
- tree.Remove(i);\r
-\r
- //Almost empty tree:\r
- Assert.IsFalse(tree.Remove(26));\r
- Assert.IsTrue(tree.Remove(48));\r
- Assert.IsTrue(tree.Check("Normal test 1"), "Bad tree");\r
- Assert.IsTrue(snap.Check("Snap"), "Bad snap!");\r
- Assert.IsTrue(IC.eq(snap, orig), "Snap was changed!");\r
-\r
- //Empty tree:\r
- Assert.IsFalse(tree.Remove(26));\r
- Assert.IsTrue(tree.Check("Normal test 1"), "Bad tree");\r
- Assert.IsTrue(snap.Check("Snap"), "Bad snap!");\r
- Assert.IsTrue(IC.eq(snap, orig), "Snap was changed!");\r
- }\r
-\r
-\r
- [Test]\r
- public void Add()\r
- {\r
- int[] orig = new int[] { 1, 3, 5, 7, 9, 11, 13, 15, 17, 19 };\r
- TreeBag<int> snap = (TreeBag<int>)tree.Snapshot();\r
-\r
- Assert.IsTrue(snap.Check("M"), "Bad snap!");\r
- Assert.IsTrue(IC.eq(snap, orig), "Snap was changed!");\r
- Assert.IsTrue(tree.Check("Tree"), "Bad tree!");\r
- tree.Add(10);\r
- Assert.IsTrue(snap.Check("M"), "Bad snap!");\r
- Assert.IsTrue(IC.eq(snap, orig), "Snap was changed!");\r
- Assert.IsTrue(tree.Check("Tree"), "Bad tree!");\r
- tree.Add(16);\r
- Assert.IsTrue(snap.Check("M"), "Bad snap!");\r
- Assert.IsTrue(IC.eq(snap, orig), "Snap was changed!");\r
- Assert.IsTrue(tree.Check("Tree"), "Bad tree!");\r
-\r
- tree.Add(9);\r
- Assert.IsTrue(snap.Check("M"), "Bad snap!");\r
- Assert.IsTrue(tree.Check("Tree"), "Bad tree!");\r
- Assert.IsTrue(IC.eq(snap, orig), "Snap was changed!");\r
-\r
- //Promote+zigzig\r
- tree.Add(40);\r
- Assert.IsTrue(snap.Check("M"), "Bad snap!");\r
- Assert.IsTrue(tree.Check("Tree"), "Bad tree!");\r
- Assert.IsTrue(IC.eq(snap, orig), "Snap was changed!");\r
- for (int i = 1; i < 4; i++)\r
- tree.Add(40 - 2 * i);\r
-\r
- Assert.IsTrue(snap.Check("M"), "Bad snap!");\r
- Assert.IsTrue(IC.eq(snap, orig), "Snap was changed!");\r
- Assert.IsTrue(tree.Check("Tree"), "Bad tree!");\r
-\r
- //Zigzag:\r
- tree.Add(32);\r
- Assert.IsTrue(snap.Check("M"), "Bad snap!");\r
- Assert.IsTrue(IC.eq(snap, orig), "Snap was changed!");\r
- Assert.IsTrue(tree.Check("Tree"), "Bad tree!");\r
- }\r
-\r
-\r
- [Test]\r
- public void Clear()\r
- {\r
- int[] orig = new int[] { 1, 3, 5, 7, 9, 11, 13, 15, 17, 19 };\r
- TreeBag<int> snap = (TreeBag<int>)tree.Snapshot();\r
-\r
- tree.Clear();\r
- Assert.IsTrue(snap.Check("Snap"), "Bad snap!");\r
- Assert.IsTrue(tree.Check("Tree"), "Bad tree!");\r
- Assert.IsTrue(IC.eq(snap, orig), "Snap was changed!");\r
- Assert.AreEqual(0, tree.Count);\r
- }\r
-\r
-\r
- [Test]\r
- [ExpectedException(typeof(InvalidOperationException), "Cannot snapshot a snapshot")]\r
- public void SnapSnap()\r
- {\r
- TreeBag<int> snap = (TreeBag<int>)tree.Snapshot();\r
-\r
- snap.Snapshot();\r
- }\r
-\r
-\r
- [TearDown]\r
- public void Dispose()\r
- {\r
- tree = null;\r
- ic = null;\r
- }\r
- }\r
-\r
-\r
-\r
- [TestFixture]\r
- public class Multiple\r
- {\r
- private TreeBag<int> tree;\r
-\r
- private IComparer<int> ic;\r
-\r
-\r
- private bool eq(MSG.IEnumerable<int> me, int[] that)\r
- {\r
- int i = 0, maxind = that.Length - 1;\r
-\r
- foreach (int item in me)\r
- if (i > maxind || ic.Compare(item, that[i++]) != 0)\r
- return false;\r
-\r
- return true;\r
- }\r
-\r
-\r
- [SetUp]\r
- public void Init()\r
- {\r
- ic = new IC();\r
- tree = new TreeBag<int>(ic);\r
- for (int i = 0; i < 10; i++)\r
- tree.Add(2 * i + 1);\r
- }\r
-\r
-\r
- [Test]\r
- public void First()\r
- {\r
- TreeBag<int>[] snaps = new TreeBag<int>[10];\r
-\r
- for (int i = 0; i < 10; i++)\r
- {\r
- snaps[i] = (TreeBag<int>)(tree.Snapshot());\r
- tree.Add(2 * i);\r
- }\r
+ [SetUp]\r
+ public void Init()\r
+ {\r
+ tree = new TreeBag<int>(new IC());\r
+ for (int i = 0; i < 10; i++)\r
+ tree.Add(i);\r
\r
- for (int i = 0; i < 10; i++)\r
- {\r
- Assert.AreEqual(i + 10, snaps[i].Count);\r
- }\r
+ e = tree.RangeFromTo(3, 7).GetEnumerator();\r
+ }\r
\r
- snaps[5] = null;\r
- snaps[9] = null;\r
- GC.Collect();\r
- snaps[8].Dispose();\r
- tree.Remove(14);\r
\r
- int[] res = new int[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 15, 16, 17, 18, 19 };\r
- int[] snap7 = new int[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 15, 17, 19 };\r
- int[] snap3 = new int[] { 0, 1, 2, 3, 4, 5, 7, 9, 11, 13, 15, 17, 19 };\r
+ [Test]\r
+ public void CurrentAfterModification()\r
+ {\r
+ e.MoveNext();\r
+ tree.Add(34);\r
+ Assert.AreEqual(3, e.Current);\r
+ }\r
\r
- Assert.IsTrue(IC.eq(snaps[3], snap3), "Snap 3 was changed!");\r
- Assert.IsTrue(IC.eq(snaps[7], snap7), "Snap 7 was changed!");\r
- Assert.IsTrue(IC.eq(tree, res));\r
- Assert.IsTrue(tree.Check("B"));\r
- Assert.IsTrue(snaps[3].Check("B"));\r
- Assert.IsTrue(snaps[7].Check("B"));\r
- }\r
\r
+ [Test]\r
+ [ExpectedException(typeof(CollectionModifiedException))]\r
+ public void MoveNextAfterAdd()\r
+ {\r
+ tree.Add(34);\r
+ e.MoveNext();\r
+ }\r
+\r
+\r
+ [Test]\r
+ [ExpectedException(typeof(CollectionModifiedException))]\r
+ public void MoveNextAfterRemove()\r
+ {\r
+ tree.Remove(34);\r
+ e.MoveNext();\r
+ }\r
+\r
+\r
+ [Test]\r
+ [ExpectedException(typeof(CollectionModifiedException))]\r
+ public void MoveNextAfterClear()\r
+ {\r
+ tree.Clear();\r
+ e.MoveNext();\r
+ }\r
+\r
+\r
+ [TearDown]\r
+ public void Dispose()\r
+ {\r
+ tree = null;\r
+ e = null;\r
+ }\r
+ }\r
+ }\r
+\r
+\r
+\r
+\r
+ namespace PathcopyPersistence\r
+ {\r
+ [TestFixture]\r
+ public class Navigation\r
+ {\r
+ private TreeBag<int> tree, snap;\r
+\r
+ private SCG.IComparer<int> ic;\r
+\r
+\r
+ [SetUp]\r
+ public void Init()\r
+ {\r
+ ic = new IC();\r
+ tree = new TreeBag<int>(ic);\r
+ for (int i = 0; i <= 20; i++)\r
+ tree.Add(2 * i + 1);\r
+ tree.Add(13);\r
+ snap = (TreeBag<int>)tree.Snapshot();\r
+ for (int i = 0; i <= 10; i++)\r
+ tree.Remove(4 * i + 1);\r
+ }\r
+\r
+\r
+ private bool twomodeleven(int i)\r
+ {\r
+ return i % 11 == 2;\r
+ }\r
+\r
+\r
+ [Test]\r
+ public void InternalEnum()\r
+ {\r
+ Assert.IsTrue(IC.eq(snap.FindAll(new Fun<int, bool>(twomodeleven)), 13, 13, 35));\r
+ }\r
+\r
+\r
+ public void MoreCut()\r
+ {\r
+ //TODO: Assert.Fail("more tests of Cut needed");\r
+ }\r
+\r
+\r
+ [Test]\r
+ public void Cut()\r
+ {\r
+ int lo, hi;\r
+ bool lv, hv;\r
+\r
+ Assert.IsFalse(snap.Cut(new HigherOrder.CubeRoot(64), out lo, out lv, out hi, out hv));\r
+ Assert.IsTrue(lv && hv);\r
+ Assert.AreEqual(5, hi);\r
+ Assert.AreEqual(3, lo);\r
+ Assert.IsTrue(snap.Cut(new HigherOrder.CubeRoot(125), out lo, out lv, out hi, out hv));\r
+ Assert.IsTrue(lv && hv);\r
+ Assert.AreEqual(7, hi);\r
+ Assert.AreEqual(3, lo);\r
+ Assert.IsFalse(snap.Cut(new HigherOrder.CubeRoot(125000), out lo, out lv, out hi, out hv));\r
+ Assert.IsTrue(lv && !hv);\r
+ Assert.AreEqual(41, lo);\r
+ Assert.IsFalse(snap.Cut(new HigherOrder.CubeRoot(-27), out lo, out lv, out hi, out hv));\r
+ Assert.IsTrue(!lv && hv);\r
+ Assert.AreEqual(1, hi);\r
+ }\r
+\r
+\r
+ [Test]\r
+ public void Range()\r
+ {\r
+ Assert.IsTrue(IC.eq(snap.RangeFromTo(5, 16), 5, 7, 9, 11, 13, 13, 15));\r
+ Assert.IsTrue(IC.eq(snap.RangeFromTo(5, 17), 5, 7, 9, 11, 13, 13, 15));\r
+ Assert.IsTrue(IC.eq(snap.RangeFromTo(6, 16), 7, 9, 11, 13, 13, 15));\r
+ }\r
+\r
+\r
+ [Test]\r
+ public void Contains()\r
+ {\r
+ Assert.IsTrue(snap.Contains(5));\r
+ Assert.IsTrue(snap.Contains(13));\r
+ Assert.AreEqual(1, snap.ContainsCount(5));\r
+ Assert.AreEqual(2, snap.ContainsCount(13));\r
+ }\r
+\r
+\r
+ [Test]\r
+ public void FindMin()\r
+ {\r
+ Assert.AreEqual(1, snap.FindMin());\r
+ }\r
+\r
+\r
+ [Test]\r
+ public void FindMax()\r
+ {\r
+ Assert.AreEqual(41, snap.FindMax());\r
+ }\r
+\r
+\r
+ [Test]\r
+ public void Predecessor()\r
+ {\r
+ Assert.AreEqual(13, snap.Predecessor(15));\r
+ Assert.AreEqual(15, snap.Predecessor(16));\r
+ Assert.AreEqual(15, snap.Predecessor(17));\r
+ Assert.AreEqual(17, snap.Predecessor(18));\r
+ }\r
+\r
+\r
+ [Test]\r
+ public void Successor()\r
+ {\r
+ Assert.AreEqual(17, snap.Successor(15));\r
+ Assert.AreEqual(17, snap.Successor(16));\r
+ Assert.AreEqual(19, snap.Successor(17));\r
+ Assert.AreEqual(19, snap.Successor(18));\r
+ }\r
+\r
+\r
+ [Test]\r
+ public void WeakPredecessor()\r
+ {\r
+ Assert.AreEqual(15, snap.WeakPredecessor(15));\r
+ Assert.AreEqual(15, snap.WeakPredecessor(16));\r
+ Assert.AreEqual(17, snap.WeakPredecessor(17));\r
+ Assert.AreEqual(17, snap.WeakPredecessor(18));\r
+ }\r
+\r
+\r
+ [Test]\r
+ public void WeakSuccessor()\r
+ {\r
+ Assert.AreEqual(15, snap.WeakSuccessor(15));\r
+ Assert.AreEqual(17, snap.WeakSuccessor(16));\r
+ Assert.AreEqual(17, snap.WeakSuccessor(17));\r
+ Assert.AreEqual(19, snap.WeakSuccessor(18));\r
+ }\r
+\r
+\r
+ [Test]\r
+ [ExpectedException(typeof(NotSupportedException), "Indexing not supported for snapshots")]\r
+ public void CountTo()\r
+ {\r
+ int j = snap.CountTo(15);\r
+ }\r
+\r
+\r
+ [Test]\r
+ [ExpectedException(typeof(NotSupportedException), "Indexing not supported for snapshots")]\r
+ public void Indexing()\r
+ {\r
+ int j = snap[4];\r
+ }\r
+\r
+\r
+ [Test]\r
+ [ExpectedException(typeof(NotSupportedException), "Indexing not supported for snapshots")]\r
+ public void Indexing2()\r
+ {\r
+ int j = snap.IndexOf(5);\r
+ }\r
+\r
+\r
+ [TearDown]\r
+ public void Dispose()\r
+ {\r
+ tree = null;\r
+ ic = null;\r
+ }\r
+ }\r
+\r
+\r
+\r
+ [TestFixture]\r
+ public class Single\r
+ {\r
+ private TreeBag<int> tree;\r
+\r
+ private SCG.IComparer<int> ic;\r
+\r
+\r
+ [SetUp]\r
+ public void Init()\r
+ {\r
+ ic = new IC();\r
+ tree = new TreeBag<int>(ic);\r
+ for (int i = 0; i < 10; i++)\r
+ tree.Add(2 * i + 1);\r
+ }\r
+\r
+\r
+ [Test]\r
+ public void EnumerationWithAdd()\r
+ {\r
+ int[] orig = new int[] { 1, 3, 5, 7, 9, 11, 13, 15, 17, 19 };\r
+ int i = 0;\r
+ TreeBag<int> snap = (TreeBag<int>)tree.Snapshot();\r
+\r
+ foreach (int j in snap)\r
+ {\r
+ Assert.AreEqual(1 + 2 * i++, j);\r
+ tree.Add(21 - j);\r
+ Assert.IsTrue(snap.Check("M"), "Bad snap!");\r
+ Assert.IsTrue(IC.eq(snap, orig), "Snap was changed!");\r
+ Assert.IsTrue(tree.Check("Tree"), "Bad tree!");\r
+ }\r
+ }\r
+\r
+\r
+ [Test]\r
+ public void Remove()\r
+ {\r
+ int[] orig = new int[] { 1, 3, 5, 7, 9, 11, 13, 15, 17, 19 };\r
+ TreeBag<int> snap = (TreeBag<int>)tree.Snapshot();\r
+\r
+ Assert.IsTrue(snap.Check("Snap"), "Bad snap!");\r
+ Assert.IsTrue(IC.eq(snap, orig), "Snap was changed!");\r
+ tree.Remove(19);\r
+ Assert.IsTrue(snap.Check("Snap"), "Bad snap!");\r
+ Assert.IsTrue(tree.Check("Tree"), "Bad tree!");\r
+ Assert.IsTrue(IC.eq(snap, orig), "Snap was changed!");\r
+ }\r
+\r
+\r
+ [Test]\r
+ public void RemoveNormal()\r
+ {\r
+ tree.Clear();\r
+ for (int i = 10; i < 20; i++)\r
+ {\r
+ tree.Add(i);\r
+ tree.Add(i + 10);\r
+ }\r
+ tree.Add(15);\r
+\r
+ int[] orig = new int[] { 10, 11, 12, 13, 14, 15, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29 };\r
+ TreeBag<int> snap = (TreeBag<int>)tree.Snapshot();\r
+\r
+ Assert.IsFalse(tree.Remove(-20));\r
+ Assert.IsTrue(snap.Check("Snap"), "Bad snap!");\r
+ Assert.IsTrue(IC.eq(snap, orig), "Snap was changed!");\r
+\r
+\r
+ //decrease items case\r
+ Assert.IsTrue(tree.Remove(15));\r
+ Assert.IsTrue(tree.Check("T1"));\r
+ Assert.IsTrue(snap.Check("Snap"), "Bad snap!");\r
+ //snap.dump();\r
+ Assert.IsTrue(IC.eq(snap, orig), "Snap was changed!");\r
+\r
+ //No demote case, with move_item\r
+ Assert.IsTrue(tree.Remove(20));\r
+ Assert.IsTrue(tree.Check("T1"));\r
+ Assert.IsTrue(snap.Check("Snap"), "Bad snap!");\r
+ Assert.IsTrue(IC.eq(snap, orig), "Snap was changed!");\r
+ Assert.IsFalse(tree.Remove(20));\r
+\r
+ //plain case 2\r
+ tree.Snapshot();\r
+ Assert.IsTrue(tree.Remove(14));\r
+ Assert.IsTrue(tree.Check("Normal test 1"), "Bad tree");\r
+ Assert.IsTrue(snap.Check("Snap"), "Bad snap!");\r
+ Assert.IsTrue(IC.eq(snap, orig), "Snap was changed!");\r
+\r
+ //case 1b\r
+ Assert.IsTrue(tree.Remove(25));\r
+ Assert.IsTrue(tree.Check("Normal test 1"), "Bad tree");\r
+ Assert.IsTrue(snap.Check("Snap"), "Bad snap!");\r
+ Assert.IsTrue(IC.eq(snap, orig), "Snap was changed!");\r
+\r
+ //case 1c\r
+ Assert.IsTrue(tree.Remove(29));\r
+ Assert.IsTrue(tree.Check("Normal test 1"), "Bad tree");\r
+ Assert.IsTrue(snap.Check("Snap"), "Bad snap!");\r
+ Assert.IsTrue(IC.eq(snap, orig), "Snap was changed!");\r
+\r
+ //1a (terminating)\r
+ Assert.IsTrue(tree.Remove(10));\r
+ Assert.IsTrue(tree.Check("Normal test 1"), "Bad tree");\r
+ Assert.IsTrue(snap.Check("Snap"), "Bad snap!");\r
+ Assert.IsTrue(IC.eq(snap, orig), "Snap was changed!");\r
+\r
+ //2+1b\r
+ Assert.IsTrue(tree.Remove(12));\r
+ tree.Snapshot();\r
+ Assert.IsTrue(tree.Remove(11));\r
+ Assert.IsTrue(tree.Check("Normal test 1"), "Bad tree");\r
+ Assert.IsTrue(snap.Check("Snap"), "Bad snap!");\r
+ Assert.IsTrue(IC.eq(snap, orig), "Snap was changed!");\r
+\r
+ //1a+1b\r
+ Assert.IsTrue(tree.Remove(18));\r
+ Assert.IsTrue(tree.Remove(13));\r
+ Assert.IsTrue(tree.Remove(15));\r
+ Assert.IsTrue(tree.Check("Normal test 1"), "Bad tree");\r
+ Assert.IsTrue(snap.Check("Snap"), "Bad snap!");\r
+ Assert.IsTrue(IC.eq(snap, orig), "Snap was changed!");\r
+\r
+ //2+1c\r
+ for (int i = 0; i < 10; i++)\r
+ tree.Add(50 - 2 * i);\r
+\r
+ Assert.IsTrue(tree.Remove(42));\r
+ Assert.IsTrue(tree.Remove(38));\r
+ Assert.IsTrue(tree.Remove(28));\r
+ Assert.IsTrue(tree.Remove(40));\r
+ Assert.IsTrue(tree.Check("Normal test 1"), "Bad tree");\r
+ Assert.IsTrue(snap.Check("Snap"), "Bad snap!");\r
+ Assert.IsTrue(IC.eq(snap, orig), "Snap was changed!");\r
+\r
+ //\r
+ Assert.IsTrue(tree.Remove(16));\r
+ Assert.IsTrue(tree.Remove(23));\r
+ Assert.IsTrue(tree.Remove(17));\r
+ Assert.IsTrue(tree.Remove(19));\r
+ Assert.IsTrue(tree.Remove(50));\r
+ Assert.IsTrue(tree.Remove(26));\r
+ Assert.IsTrue(tree.Remove(21));\r
+ Assert.IsTrue(tree.Remove(22));\r
+ Assert.IsTrue(tree.Remove(24));\r
+ for (int i = 0; i < 48; i++)\r
+ tree.Remove(i);\r
+\r
+ //Almost empty tree:\r
+ Assert.IsFalse(tree.Remove(26));\r
+ Assert.IsTrue(tree.Remove(48));\r
+ Assert.IsTrue(tree.Check("Normal test 1"), "Bad tree");\r
+ Assert.IsTrue(snap.Check("Snap"), "Bad snap!");\r
+ Assert.IsTrue(IC.eq(snap, orig), "Snap was changed!");\r
+\r
+ //Empty tree:\r
+ Assert.IsFalse(tree.Remove(26));\r
+ Assert.IsTrue(tree.Check("Normal test 1"), "Bad tree");\r
+ Assert.IsTrue(snap.Check("Snap"), "Bad snap!");\r
+ Assert.IsTrue(IC.eq(snap, orig), "Snap was changed!");\r
+ }\r
+\r
+\r
+ [Test]\r
+ public void Add()\r
+ {\r
+ int[] orig = new int[] { 1, 3, 5, 7, 9, 11, 13, 15, 17, 19 };\r
+ TreeBag<int> snap = (TreeBag<int>)tree.Snapshot();\r
+\r
+ Assert.IsTrue(snap.Check("M"), "Bad snap!");\r
+ Assert.IsTrue(IC.eq(snap, orig), "Snap was changed!");\r
+ Assert.IsTrue(tree.Check("Tree"), "Bad tree!");\r
+ tree.Add(10);\r
+ Assert.IsTrue(snap.Check("M"), "Bad snap!");\r
+ Assert.IsTrue(IC.eq(snap, orig), "Snap was changed!");\r
+ Assert.IsTrue(tree.Check("Tree"), "Bad tree!");\r
+ tree.Add(16);\r
+ Assert.IsTrue(snap.Check("M"), "Bad snap!");\r
+ Assert.IsTrue(IC.eq(snap, orig), "Snap was changed!");\r
+ Assert.IsTrue(tree.Check("Tree"), "Bad tree!");\r
+\r
+ tree.Add(9);\r
+ Assert.IsTrue(snap.Check("M"), "Bad snap!");\r
+ Assert.IsTrue(tree.Check("Tree"), "Bad tree!");\r
+ Assert.IsTrue(IC.eq(snap, orig), "Snap was changed!");\r
+\r
+ //Promote+zigzig\r
+ tree.Add(40);\r
+ Assert.IsTrue(snap.Check("M"), "Bad snap!");\r
+ Assert.IsTrue(tree.Check("Tree"), "Bad tree!");\r
+ Assert.IsTrue(IC.eq(snap, orig), "Snap was changed!");\r
+ for (int i = 1; i < 4; i++)\r
+ tree.Add(40 - 2 * i);\r
+\r
+ Assert.IsTrue(snap.Check("M"), "Bad snap!");\r
+ Assert.IsTrue(IC.eq(snap, orig), "Snap was changed!");\r
+ Assert.IsTrue(tree.Check("Tree"), "Bad tree!");\r
+\r
+ //Zigzag:\r
+ tree.Add(32);\r
+ Assert.IsTrue(snap.Check("M"), "Bad snap!");\r
+ Assert.IsTrue(IC.eq(snap, orig), "Snap was changed!");\r
+ Assert.IsTrue(tree.Check("Tree"), "Bad tree!");\r
+ }\r
+\r
+\r
+ [Test]\r
+ public void Clear()\r
+ {\r
+ int[] orig = new int[] { 1, 3, 5, 7, 9, 11, 13, 15, 17, 19 };\r
+ TreeBag<int> snap = (TreeBag<int>)tree.Snapshot();\r
+\r
+ tree.Clear();\r
+ Assert.IsTrue(snap.Check("Snap"), "Bad snap!");\r
+ Assert.IsTrue(tree.Check("Tree"), "Bad tree!");\r
+ Assert.IsTrue(IC.eq(snap, orig), "Snap was changed!");\r
+ Assert.AreEqual(0, tree.Count);\r
+ }\r
+\r
+\r
+ [Test]\r
+ [ExpectedException(typeof(InvalidOperationException), "Cannot snapshot a snapshot")]\r
+ public void SnapSnap()\r
+ {\r
+ TreeBag<int> snap = (TreeBag<int>)tree.Snapshot();\r
+\r
+ snap.Snapshot();\r
+ }\r
+\r
+\r
+ [TearDown]\r
+ public void Dispose()\r
+ {\r
+ tree = null;\r
+ ic = null;\r
+ }\r
+ }\r
+\r
+\r
+\r
+ [TestFixture]\r
+ public class Multiple\r
+ {\r
+ private TreeBag<int> tree;\r
+\r
+ private SCG.IComparer<int> ic;\r
+\r
+\r
+ private bool eq(SCG.IEnumerable<int> me, int[] that)\r
+ {\r
+ int i = 0, maxind = that.Length - 1;\r
+\r
+ foreach (int item in me)\r
+ if (i > maxind || ic.Compare(item, that[i++]) != 0)\r
+ return false;\r
+\r
+ return true;\r
+ }\r
+\r
+\r
+ [SetUp]\r
+ public void Init()\r
+ {\r
+ ic = new IC();\r
+ tree = new TreeBag<int>(ic);\r
+ for (int i = 0; i < 10; i++)\r
+ tree.Add(2 * i + 1);\r
+ }\r
+\r
+\r
+ [Test]\r
+ public void First()\r
+ {\r
+ TreeBag<int>[] snaps = new TreeBag<int>[10];\r
+\r
+ for (int i = 0; i < 10; i++)\r
+ {\r
+ snaps[i] = (TreeBag<int>)(tree.Snapshot());\r
+ tree.Add(2 * i);\r
+ }\r
\r
- [Test]\r
- public void CollectingTheMaster()\r
- {\r
- TreeBag<int>[] snaps = new TreeBag<int>[10];\r
+ for (int i = 0; i < 10; i++)\r
+ {\r
+ Assert.AreEqual(i + 10, snaps[i].Count);\r
+ }\r
\r
- for (int i = 0; i < 10; i++)\r
- {\r
- snaps[i] = (TreeBag<int>)(tree.Snapshot());\r
- tree.Add(2 * i);\r
- }\r
+ snaps[5] = null;\r
+ snaps[9] = null;\r
+ GC.Collect();\r
+ snaps[8].Dispose();\r
+ tree.Remove(14);\r
+\r
+ int[] res = new int[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 15, 16, 17, 18, 19 };\r
+ int[] snap7 = new int[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 15, 17, 19 };\r
+ int[] snap3 = new int[] { 0, 1, 2, 3, 4, 5, 7, 9, 11, 13, 15, 17, 19 };\r
+\r
+ Assert.IsTrue(IC.eq(snaps[3], snap3), "Snap 3 was changed!");\r
+ Assert.IsTrue(IC.eq(snaps[7], snap7), "Snap 7 was changed!");\r
+ Assert.IsTrue(IC.eq(tree, res));\r
+ Assert.IsTrue(tree.Check("B"));\r
+ Assert.IsTrue(snaps[3].Check("B"));\r
+ Assert.IsTrue(snaps[7].Check("B"));\r
+ }\r
+\r
+\r
+ [Test]\r
+ public void CollectingTheMaster()\r
+ {\r
+ TreeBag<int>[] snaps = new TreeBag<int>[10];\r
+\r
+ for (int i = 0; i < 10; i++)\r
+ {\r
+ snaps[i] = (TreeBag<int>)(tree.Snapshot());\r
+ tree.Add(2 * i);\r
+ }\r
\r
- tree = null;\r
- GC.Collect();\r
- for (int i = 0; i < 10; i++)\r
- {\r
- Assert.AreEqual(i + 10, snaps[i].Count);\r
- }\r
+ tree = null;\r
+ GC.Collect();\r
+ for (int i = 0; i < 10; i++)\r
+ {\r
+ Assert.AreEqual(i + 10, snaps[i].Count);\r
+ }\r
\r
- snaps[5] = null;\r
- snaps[9] = null;\r
- GC.Collect();\r
- snaps[8].Dispose();\r
+ snaps[5] = null;\r
+ snaps[9] = null;\r
+ GC.Collect();\r
+ snaps[8].Dispose();\r
\r
- int[] snap7 = new int[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 15, 17, 19 };\r
- int[] snap3 = new int[] { 0, 1, 2, 3, 4, 5, 7, 9, 11, 13, 15, 17, 19 };\r
+ int[] snap7 = new int[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 15, 17, 19 };\r
+ int[] snap3 = new int[] { 0, 1, 2, 3, 4, 5, 7, 9, 11, 13, 15, 17, 19 };\r
\r
- Assert.IsTrue(IC.eq(snaps[3], snap3), "Snap 3 was changed!");\r
- Assert.IsTrue(IC.eq(snaps[7], snap7), "Snap 7 was changed!");\r
- Assert.IsTrue(snaps[3].Check("B"));\r
- Assert.IsTrue(snaps[7].Check("B"));\r
- }\r
+ Assert.IsTrue(IC.eq(snaps[3], snap3), "Snap 3 was changed!");\r
+ Assert.IsTrue(IC.eq(snaps[7], snap7), "Snap 7 was changed!");\r
+ Assert.IsTrue(snaps[3].Check("B"));\r
+ Assert.IsTrue(snaps[7].Check("B"));\r
+ }\r
\r
\r
- [TearDown]\r
- public void Dispose()\r
- {\r
- tree = null;\r
- ic = null;\r
- }\r
- }\r
- }\r
+ [TearDown]\r
+ public void Dispose()\r
+ {\r
+ tree = null;\r
+ ic = null;\r
+ }\r
+ }\r
+ }\r
\r
\r
\r
\r
- namespace HigherOrder\r
- {\r
- internal class CubeRoot: IComparable<int>\r
- {\r
- private int c;\r
+ namespace HigherOrder\r
+ {\r
+ internal class CubeRoot : IComparable<int>\r
+ {\r
+ private int c;\r
\r
\r
- internal CubeRoot(int c) { this.c = c; }\r
+ internal CubeRoot(int c) { this.c = c; }\r
\r
\r
- public int CompareTo(int that) { return c - that * that * that; }\r
- public bool Equals(int that) { return c == that * that * that; }\r
- }\r
+ public int CompareTo(int that) { return c - that * that * that; }\r
+ public bool Equals(int that) { return c == that * that * that; }\r
+ }\r
\r
\r
\r
- class Interval: IComparable<int>\r
- {\r
- private int b, t;\r
+ class Interval : IComparable<int>\r
+ {\r
+ private int b, t;\r
\r
\r
- internal Interval(int b, int t) { this.b = b; this.t = t; }\r
+ internal Interval(int b, int t) { this.b = b; this.t = t; }\r
\r
\r
- public int CompareTo(int that) { return that < b ? 1 : that > t ? -1 : 0; }\r
- public bool Equals(int that) { return that >= b && that <= t; }\r
- }\r
+ public int CompareTo(int that) { return that < b ? 1 : that > t ? -1 : 0; }\r
+ public bool Equals(int that) { return that >= b && that <= t; }\r
+ }\r
\r
\r
\r
- [TestFixture]\r
- public class Simple\r
- {\r
- private TreeBag<int> tree;\r
+ [TestFixture]\r
+ public class Simple\r
+ {\r
+ private TreeBag<int> tree;\r
\r
- private IComparer<int> ic;\r
+ private SCG.IComparer<int> ic;\r
\r
\r
- [SetUp]\r
- public void Init()\r
- {\r
- ic = new IC();\r
- tree = new TreeBag<int>(ic);\r
- }\r
+ [SetUp]\r
+ public void Init()\r
+ {\r
+ ic = new IC();\r
+ tree = new TreeBag<int>(ic);\r
+ }\r
\r
\r
- private bool never(int i) { return false; }\r
+ private bool never(int i) { return false; }\r
\r
\r
- private bool always(int i) { return true; }\r
+ private bool always(int i) { return true; }\r
\r
\r
- private bool even(int i) { return i % 2 == 0; }\r
+ private bool even(int i) { return i % 2 == 0; }\r
\r
\r
- private string themap(int i) { return String.Format("AA {0,4} BB", i); }\r
+ private string themap(int i) { return String.Format("AA {0,4} BB", i); }\r
\r
\r
- private string badmap(int i) { return String.Format("AA {0} BB", i); }\r
+ private string badmap(int i) { return String.Format("AA {0} BB", i); }\r
\r
\r
- private int appfield1;\r
+ private int appfield1;\r
\r
- private int appfield2;\r
+ private int appfield2;\r
\r
\r
- private void apply(int i) { appfield1++; appfield2 += i * i; }\r
+ private void apply(int i) { appfield1++; appfield2 += i * i; }\r
\r
\r
- [Test]\r
- public void Apply()\r
- {\r
- Simple simple1 = new Simple();\r
+ [Test]\r
+ public void Apply()\r
+ {\r
+ Simple simple1 = new Simple();\r
\r
- tree.Apply(new Applier<int>(simple1.apply));\r
- Assert.AreEqual(0, simple1.appfield1);\r
- Assert.AreEqual(0, simple1.appfield2);\r
+ tree.Apply(new Act<int>(simple1.apply));\r
+ Assert.AreEqual(0, simple1.appfield1);\r
+ Assert.AreEqual(0, simple1.appfield2);\r
\r
- Simple simple2 = new Simple();\r
+ Simple simple2 = new Simple();\r
\r
- for (int i = 0; i < 10; i++) tree.Add(i);\r
- tree.Add(2);\r
+ for (int i = 0; i < 10; i++) tree.Add(i);\r
+ tree.Add(2);\r
\r
- tree.Apply(new Applier<int>(simple2.apply));\r
- Assert.AreEqual(11, simple2.appfield1);\r
- Assert.AreEqual(289, simple2.appfield2);\r
- }\r
+ tree.Apply(new Act<int>(simple2.apply));\r
+ Assert.AreEqual(11, simple2.appfield1);\r
+ Assert.AreEqual(289, simple2.appfield2);\r
+ }\r
\r
\r
- [Test]\r
- public void All()\r
- {\r
- Assert.IsTrue(tree.All(new Filter<int>(never)));\r
- Assert.IsTrue(tree.All(new Filter<int>(even)));\r
- Assert.IsTrue(tree.All(new Filter<int>(always)));\r
- for (int i = 0; i < 10; i++) tree.Add(i);\r
+ [Test]\r
+ public void All()\r
+ {\r
+ Assert.IsTrue(tree.All(new Fun<int, bool>(never)));\r
+ Assert.IsTrue(tree.All(new Fun<int, bool>(even)));\r
+ Assert.IsTrue(tree.All(new Fun<int, bool>(always)));\r
+ for (int i = 0; i < 10; i++) tree.Add(i);\r
\r
- Assert.IsFalse(tree.All(new Filter<int>(never)));\r
- Assert.IsFalse(tree.All(new Filter<int>(even)));\r
- Assert.IsTrue(tree.All(new Filter<int>(always)));\r
- tree.Clear();\r
- for (int i = 0; i < 10; i++) tree.Add(i * 2);\r
+ Assert.IsFalse(tree.All(new Fun<int, bool>(never)));\r
+ Assert.IsFalse(tree.All(new Fun<int, bool>(even)));\r
+ Assert.IsTrue(tree.All(new Fun<int, bool>(always)));\r
+ tree.Clear();\r
+ for (int i = 0; i < 10; i++) tree.Add(i * 2);\r
\r
- Assert.IsFalse(tree.All(new Filter<int>(never)));\r
- Assert.IsTrue(tree.All(new Filter<int>(even)));\r
- Assert.IsTrue(tree.All(new Filter<int>(always)));\r
- tree.Clear();\r
- for (int i = 0; i < 10; i++) tree.Add(i * 2 + 1);\r
+ Assert.IsFalse(tree.All(new Fun<int, bool>(never)));\r
+ Assert.IsTrue(tree.All(new Fun<int, bool>(even)));\r
+ Assert.IsTrue(tree.All(new Fun<int, bool>(always)));\r
+ tree.Clear();\r
+ for (int i = 0; i < 10; i++) tree.Add(i * 2 + 1);\r
\r
- Assert.IsFalse(tree.All(new Filter<int>(never)));\r
- Assert.IsFalse(tree.All(new Filter<int>(even)));\r
- Assert.IsTrue(tree.All(new Filter<int>(always)));\r
- }\r
+ Assert.IsFalse(tree.All(new Fun<int, bool>(never)));\r
+ Assert.IsFalse(tree.All(new Fun<int, bool>(even)));\r
+ Assert.IsTrue(tree.All(new Fun<int, bool>(always)));\r
+ }\r
\r
\r
- [Test]\r
- public void Exists()\r
- {\r
- Assert.IsFalse(tree.Exists(new Filter<int>(never)));\r
- Assert.IsFalse(tree.Exists(new Filter<int>(even)));\r
- Assert.IsFalse(tree.Exists(new Filter<int>(always)));\r
- for (int i = 0; i < 10; i++) tree.Add(i);\r
+ [Test]\r
+ public void Exists()\r
+ {\r
+ Assert.IsFalse(tree.Exists(new Fun<int, bool>(never)));\r
+ Assert.IsFalse(tree.Exists(new Fun<int, bool>(even)));\r
+ Assert.IsFalse(tree.Exists(new Fun<int, bool>(always)));\r
+ for (int i = 0; i < 10; i++) tree.Add(i);\r
\r
- Assert.IsFalse(tree.Exists(new Filter<int>(never)));\r
- Assert.IsTrue(tree.Exists(new Filter<int>(even)));\r
- Assert.IsTrue(tree.Exists(new Filter<int>(always)));\r
- tree.Clear();\r
- for (int i = 0; i < 10; i++) tree.Add(i * 2);\r
+ Assert.IsFalse(tree.Exists(new Fun<int, bool>(never)));\r
+ Assert.IsTrue(tree.Exists(new Fun<int, bool>(even)));\r
+ Assert.IsTrue(tree.Exists(new Fun<int, bool>(always)));\r
+ tree.Clear();\r
+ for (int i = 0; i < 10; i++) tree.Add(i * 2);\r
\r
- Assert.IsFalse(tree.Exists(new Filter<int>(never)));\r
- Assert.IsTrue(tree.Exists(new Filter<int>(even)));\r
- Assert.IsTrue(tree.Exists(new Filter<int>(always)));\r
- tree.Clear();\r
- for (int i = 0; i < 10; i++) tree.Add(i * 2 + 1);\r
+ Assert.IsFalse(tree.Exists(new Fun<int, bool>(never)));\r
+ Assert.IsTrue(tree.Exists(new Fun<int, bool>(even)));\r
+ Assert.IsTrue(tree.Exists(new Fun<int, bool>(always)));\r
+ tree.Clear();\r
+ for (int i = 0; i < 10; i++) tree.Add(i * 2 + 1);\r
\r
- Assert.IsFalse(tree.Exists(new Filter<int>(never)));\r
- Assert.IsFalse(tree.Exists(new Filter<int>(even)));\r
- Assert.IsTrue(tree.Exists(new Filter<int>(always)));\r
- }\r
+ Assert.IsFalse(tree.Exists(new Fun<int, bool>(never)));\r
+ Assert.IsFalse(tree.Exists(new Fun<int, bool>(even)));\r
+ Assert.IsTrue(tree.Exists(new Fun<int, bool>(always)));\r
+ }\r
\r
\r
- [Test]\r
- public void FindAll()\r
- {\r
- Assert.AreEqual(0, tree.FindAll(new Filter<int>(never)).Count);\r
- for (int i = 0; i < 10; i++)\r
- tree.Add(i);\r
- tree.Add(2);\r
+ [Test]\r
+ public void FindAll()\r
+ {\r
+ Assert.AreEqual(0, tree.FindAll(new Fun<int, bool>(never)).Count);\r
+ for (int i = 0; i < 10; i++)\r
+ tree.Add(i);\r
+ tree.Add(2);\r
\r
- Assert.AreEqual(0, tree.FindAll(new Filter<int>(never)).Count);\r
- Assert.AreEqual(11, tree.FindAll(new Filter<int>(always)).Count);\r
- Assert.AreEqual(6, tree.FindAll(new Filter<int>(even)).Count);\r
- Assert.IsTrue(((TreeBag<int>)tree.FindAll(new Filter<int>(even))).Check("R"));\r
- }\r
-\r
-\r
- [Test]\r
- public void Map()\r
- {\r
- Assert.AreEqual(0, tree.Map(new Mapper<int,string>(themap), new SC()).Count);\r
- for (int i = 0; i < 14; i++)\r
- tree.Add(i * i * i);\r
- tree.Add(1);\r
-\r
- IIndexedSorted<string> res = tree.Map(new Mapper<int,string>(themap), new SC());\r
-\r
- Assert.IsTrue(((TreeBag<string>)res).Check("R"));\r
- Assert.AreEqual(15, res.Count);\r
- Assert.AreEqual("AA 0 BB", res[0]);\r
- Assert.AreEqual("AA 1 BB", res[1]);\r
- Assert.AreEqual("AA 1 BB", res[2]);\r
- Assert.AreEqual("AA 8 BB", res[3]);\r
- Assert.AreEqual("AA 27 BB", res[4]);\r
- Assert.AreEqual("AA 125 BB", res[6]);\r
- Assert.AreEqual("AA 1000 BB", res[11]);\r
- }\r
-\r
-\r
- [Test]\r
- [ExpectedException(typeof(ArgumentException), "mapper not monotonic")]\r
- public void BadMap()\r
- {\r
- for (int i = 0; i < 11; i++)\r
- tree.Add(i * i * i);\r
-\r
- ISorted<string> res = tree.Map(new Mapper<int,string>(badmap), new SC());\r
- }\r
-\r
-\r
- [Test]\r
- public void Cut()\r
- {\r
- for (int i = 0; i < 10; i++)\r
- tree.Add(i);\r
- tree.Add(3);\r
-\r
- int low, high;\r
- bool lval, hval;\r
-\r
- Assert.IsTrue(tree.Cut(new CubeRoot(27), out low, out lval, out high, out hval));\r
- Assert.IsTrue(lval && hval);\r
- Assert.AreEqual(4, high);\r
- Assert.AreEqual(2, low);\r
- Assert.IsFalse(tree.Cut(new CubeRoot(30), out low, out lval, out high, out hval));\r
- Assert.IsTrue(lval && hval);\r
- Assert.AreEqual(4, high);\r
- Assert.AreEqual(3, low);\r
- }\r
-\r
-\r
- [Test]\r
- public void CutInt()\r
- {\r
- for (int i = 0; i < 10; i++)\r
- tree.Add(2 * i);\r
-\r
- int low, high;\r
- bool lval, hval;\r
-\r
- Assert.IsFalse(tree.Cut(new IC(3), out low, out lval, out high, out hval));\r
- Assert.IsTrue(lval && hval);\r
- Assert.AreEqual(4, high);\r
- Assert.AreEqual(2, low);\r
- Assert.IsTrue(tree.Cut(new IC(6), out low, out lval, out high, out hval));\r
- Assert.IsTrue(lval && hval);\r
- Assert.AreEqual(8, high);\r
- Assert.AreEqual(4, low);\r
- }\r
-\r
-\r
- [Test]\r
- public void CutInterval()\r
- {\r
- for (int i = 0; i < 10; i++)\r
- tree.Add(2 * i);\r
-\r
- int lo, hi;\r
- bool lv, hv;\r
-\r
- Assert.IsTrue(tree.Cut(new Interval(5, 9), out lo, out lv, out hi, out hv));\r
- Assert.IsTrue(lv && hv);\r
- Assert.AreEqual(10, hi);\r
- Assert.AreEqual(4, lo);\r
- Assert.IsTrue(tree.Cut(new Interval(6, 10), out lo, out lv, out hi, out hv));\r
- Assert.IsTrue(lv && hv);\r
- Assert.AreEqual(12, hi);\r
- Assert.AreEqual(4, lo);\r
- for (int i = 0; i < 100; i++)\r
- tree.Add(2 * i);\r
-\r
- tree.Cut(new Interval(77, 105), out lo, out lv, out hi, out hv);\r
- Assert.IsTrue(lv && hv);\r
- Assert.AreEqual(106, hi);\r
- Assert.AreEqual(76, lo);\r
- tree.Cut(new Interval(5, 7), out lo, out lv, out hi, out hv);\r
- Assert.IsTrue(lv && hv);\r
- Assert.AreEqual(8, hi);\r
- Assert.AreEqual(4, lo);\r
- tree.Cut(new Interval(80, 110), out lo, out lv, out hi, out hv);\r
- Assert.IsTrue(lv && hv);\r
- Assert.AreEqual(112, hi);\r
- Assert.AreEqual(78, lo);\r
- }\r
-\r
-\r
- [Test]\r
- public void UpperCut()\r
- {\r
- for (int i = 0; i < 10; i++)\r
- tree.Add(i);\r
+ Assert.AreEqual(0, tree.FindAll(new Fun<int, bool>(never)).Count);\r
+ Assert.AreEqual(11, tree.FindAll(new Fun<int, bool>(always)).Count);\r
+ Assert.AreEqual(6, tree.FindAll(new Fun<int, bool>(even)).Count);\r
+ Assert.IsTrue(((TreeBag<int>)tree.FindAll(new Fun<int, bool>(even))).Check("R"));\r
+ }\r
+\r
+\r
+ [Test]\r
+ public void Map()\r
+ {\r
+ Assert.AreEqual(0, tree.Map(new Fun<int, string>(themap), new SC()).Count);\r
+ for (int i = 0; i < 14; i++)\r
+ tree.Add(i * i * i);\r
+ tree.Add(1);\r
+\r
+ IIndexedSorted<string> res = tree.Map(new Fun<int, string>(themap), new SC());\r
+\r
+ Assert.IsTrue(((TreeBag<string>)res).Check("R"));\r
+ Assert.AreEqual(15, res.Count);\r
+ Assert.AreEqual("AA 0 BB", res[0]);\r
+ Assert.AreEqual("AA 1 BB", res[1]);\r
+ Assert.AreEqual("AA 1 BB", res[2]);\r
+ Assert.AreEqual("AA 8 BB", res[3]);\r
+ Assert.AreEqual("AA 27 BB", res[4]);\r
+ Assert.AreEqual("AA 125 BB", res[6]);\r
+ Assert.AreEqual("AA 1000 BB", res[11]);\r
+ }\r
+\r
+\r
+ [Test]\r
+ [ExpectedException(typeof(ArgumentException), "mapper not monotonic")]\r
+ public void BadMap()\r
+ {\r
+ for (int i = 0; i < 11; i++)\r
+ tree.Add(i * i * i);\r
+\r
+ ISorted<string> res = tree.Map(new Fun<int, string>(badmap), new SC());\r
+ }\r
+\r
+\r
+ [Test]\r
+ public void Cut()\r
+ {\r
+ for (int i = 0; i < 10; i++)\r
+ tree.Add(i);\r
+ tree.Add(3);\r
+\r
+ int low, high;\r
+ bool lval, hval;\r
+\r
+ Assert.IsTrue(tree.Cut(new CubeRoot(27), out low, out lval, out high, out hval));\r
+ Assert.IsTrue(lval && hval);\r
+ Assert.AreEqual(4, high);\r
+ Assert.AreEqual(2, low);\r
+ Assert.IsFalse(tree.Cut(new CubeRoot(30), out low, out lval, out high, out hval));\r
+ Assert.IsTrue(lval && hval);\r
+ Assert.AreEqual(4, high);\r
+ Assert.AreEqual(3, low);\r
+ }\r
+\r
+\r
+ [Test]\r
+ public void CutInt()\r
+ {\r
+ for (int i = 0; i < 10; i++)\r
+ tree.Add(2 * i);\r
+\r
+ int low, high;\r
+ bool lval, hval;\r
+\r
+ Assert.IsFalse(tree.Cut(new IC(3), out low, out lval, out high, out hval));\r
+ Assert.IsTrue(lval && hval);\r
+ Assert.AreEqual(4, high);\r
+ Assert.AreEqual(2, low);\r
+ Assert.IsTrue(tree.Cut(new IC(6), out low, out lval, out high, out hval));\r
+ Assert.IsTrue(lval && hval);\r
+ Assert.AreEqual(8, high);\r
+ Assert.AreEqual(4, low);\r
+ }\r
+\r
+\r
+ [Test]\r
+ public void CutInterval()\r
+ {\r
+ for (int i = 0; i < 10; i++)\r
+ tree.Add(2 * i);\r
+\r
+ int lo, hi;\r
+ bool lv, hv;\r
+\r
+ Assert.IsTrue(tree.Cut(new Interval(5, 9), out lo, out lv, out hi, out hv));\r
+ Assert.IsTrue(lv && hv);\r
+ Assert.AreEqual(10, hi);\r
+ Assert.AreEqual(4, lo);\r
+ Assert.IsTrue(tree.Cut(new Interval(6, 10), out lo, out lv, out hi, out hv));\r
+ Assert.IsTrue(lv && hv);\r
+ Assert.AreEqual(12, hi);\r
+ Assert.AreEqual(4, lo);\r
+ for (int i = 0; i < 100; i++)\r
+ tree.Add(2 * i);\r
+\r
+ tree.Cut(new Interval(77, 105), out lo, out lv, out hi, out hv);\r
+ Assert.IsTrue(lv && hv);\r
+ Assert.AreEqual(106, hi);\r
+ Assert.AreEqual(76, lo);\r
+ tree.Cut(new Interval(5, 7), out lo, out lv, out hi, out hv);\r
+ Assert.IsTrue(lv && hv);\r
+ Assert.AreEqual(8, hi);\r
+ Assert.AreEqual(4, lo);\r
+ tree.Cut(new Interval(80, 110), out lo, out lv, out hi, out hv);\r
+ Assert.IsTrue(lv && hv);\r
+ Assert.AreEqual(112, hi);\r
+ Assert.AreEqual(78, lo);\r
+ }\r
+\r
+\r
+ [Test]\r
+ public void UpperCut()\r
+ {\r
+ for (int i = 0; i < 10; i++)\r
+ tree.Add(i);\r
\r
- int l, h;\r
- bool lv, hv;\r
+ int l, h;\r
+ bool lv, hv;\r
\r
- Assert.IsFalse(tree.Cut(new CubeRoot(1000), out l, out lv, out h, out hv));\r
- Assert.IsTrue(lv && !hv);\r
- Assert.AreEqual(9, l);\r
- Assert.IsFalse(tree.Cut(new CubeRoot(-50), out l, out lv, out h, out hv));\r
- Assert.IsTrue(!lv && hv);\r
- Assert.AreEqual(0, h);\r
- }\r
+ Assert.IsFalse(tree.Cut(new CubeRoot(1000), out l, out lv, out h, out hv));\r
+ Assert.IsTrue(lv && !hv);\r
+ Assert.AreEqual(9, l);\r
+ Assert.IsFalse(tree.Cut(new CubeRoot(-50), out l, out lv, out h, out hv));\r
+ Assert.IsTrue(!lv && hv);\r
+ Assert.AreEqual(0, h);\r
+ }\r
\r
\r
- [TearDown]\r
- public void Dispose() { ic = null; tree = null; }\r
- }\r
- }\r
+ [TearDown]\r
+ public void Dispose() { ic = null; tree = null; }\r
+ }\r
+ }\r
\r
\r
\r
\r
- namespace MultiOps\r
- {\r
- [TestFixture]\r
- public class AddAll\r
- {\r
- private int sqr(int i) { return i * i; }\r
+ namespace MultiOps\r
+ {\r
+ [TestFixture]\r
+ public class AddAll\r
+ {\r
+ private int sqr(int i) { return i * i; }\r
\r
\r
- TreeBag<int> tree;\r
+ TreeBag<int> tree;\r
\r
\r
- [SetUp]\r
- public void Init() { tree = new TreeBag<int>(new IC()); }\r
+ [SetUp]\r
+ public void Init() { tree = new TreeBag<int>(new IC()); }\r
\r
\r
- [Test]\r
- public void EmptyEmpty()\r
- {\r
- tree.AddAll(new FunEnumerable(0, new Int2Int(sqr)));\r
- Assert.AreEqual(0, tree.Count);\r
- Assert.IsTrue(tree.Check());\r
- }\r
+ [Test]\r
+ public void EmptyEmpty()\r
+ {\r
+ tree.AddAll(new FunEnumerable(0, new Fun<int, int>(sqr)));\r
+ Assert.AreEqual(0, tree.Count);\r
+ Assert.IsTrue(tree.Check());\r
+ }\r
\r
\r
- [Test]\r
- public void SomeEmpty()\r
- {\r
- for (int i = 4; i < 9; i++) tree.Add(i);\r
-\r
- tree.AddAll(new FunEnumerable(0, new Int2Int(sqr)));\r
- Assert.AreEqual(5, tree.Count);\r
- Assert.IsTrue(tree.Check());\r
- }\r
+ [Test]\r
+ public void SomeEmpty()\r
+ {\r
+ for (int i = 4; i < 9; i++) tree.Add(i);\r
+\r
+ tree.AddAll(new FunEnumerable(0, new Fun<int, int>(sqr)));\r
+ Assert.AreEqual(5, tree.Count);\r
+ Assert.IsTrue(tree.Check());\r
+ }\r
\r
\r
- [Test]\r
- public void EmptySome()\r
- {\r
- tree.AddAll(new FunEnumerable(4, new Int2Int(sqr)));\r
- Assert.AreEqual(4, tree.Count);\r
- Assert.IsTrue(tree.Check());\r
- Assert.AreEqual(0, tree[0]);\r
- Assert.AreEqual(1, tree[1]);\r
- Assert.AreEqual(4, tree[2]);\r
- Assert.AreEqual(9, tree[3]);\r
- }\r
+ [Test]\r
+ public void EmptySome()\r
+ {\r
+ tree.AddAll(new FunEnumerable(4, new Fun<int, int>(sqr)));\r
+ Assert.AreEqual(4, tree.Count);\r
+ Assert.IsTrue(tree.Check());\r
+ Assert.AreEqual(0, tree[0]);\r
+ Assert.AreEqual(1, tree[1]);\r
+ Assert.AreEqual(4, tree[2]);\r
+ Assert.AreEqual(9, tree[3]);\r
+ }\r
\r
\r
- [Test]\r
- public void SomeSome()\r
- {\r
- for (int i = 5; i < 9; i++) tree.Add(i);\r
- tree.Add(1);\r
+ [Test]\r
+ public void SomeSome()\r
+ {\r
+ for (int i = 5; i < 9; i++) tree.Add(i);\r
+ tree.Add(1);\r
\r
- tree.AddAll(new FunEnumerable(4, new Int2Int(sqr)));\r
- Assert.AreEqual(9, tree.Count);\r
- Assert.IsTrue(tree.Check());\r
- Assert.IsTrue(IC.eq(tree, 0, 1, 1, 4, 5, 6, 7, 8, 9));\r
- }\r
+ tree.AddAll(new FunEnumerable(4, new Fun<int, int>(sqr)));\r
+ Assert.AreEqual(9, tree.Count);\r
+ Assert.IsTrue(tree.Check());\r
+ Assert.IsTrue(IC.eq(tree, 0, 1, 1, 4, 5, 6, 7, 8, 9));\r
+ }\r
\r
\r
- [TearDown]\r
- public void Dispose() { tree = null; }\r
- }\r
+ [TearDown]\r
+ public void Dispose() { tree = null; }\r
+ }\r
\r
\r
\r
- [TestFixture]\r
- public class AddSorted\r
- {\r
- private int sqr(int i) { return i * i; }\r
+ [TestFixture]\r
+ public class AddSorted\r
+ {\r
+ private int sqr(int i) { return i * i; }\r
\r
- private int step(int i) { return i/3; }\r
+ private int step(int i) { return i / 3; }\r
\r
\r
- private int bad(int i) { return i * (5 - i); }\r
+ private int bad(int i) { return i * (5 - i); }\r
\r
\r
- TreeBag<int> tree;\r
+ TreeBag<int> tree;\r
\r
\r
- [SetUp]\r
- public void Init() { tree = new TreeBag<int>(new IC()); }\r
+ [SetUp]\r
+ public void Init() { tree = new TreeBag<int>(new IC()); }\r
\r
\r
- [Test]\r
- public void EmptyEmpty()\r
- {\r
- tree.AddSorted(new FunEnumerable(0, new Int2Int(sqr)));\r
- Assert.AreEqual(0, tree.Count);\r
- Assert.IsTrue(tree.Check());\r
- }\r
+ [Test]\r
+ public void EmptyEmpty()\r
+ {\r
+ tree.AddSorted(new FunEnumerable(0, new Fun<int, int>(sqr)));\r
+ Assert.AreEqual(0, tree.Count);\r
+ Assert.IsTrue(tree.Check());\r
+ }\r
\r
\r
- [Test]\r
- public void SomeEmpty()\r
- {\r
- for (int i = 4; i < 9; i++) tree.Add(i);\r
+ [Test]\r
+ public void SomeEmpty()\r
+ {\r
+ for (int i = 4; i < 9; i++) tree.Add(i);\r
\r
- tree.AddSorted(new FunEnumerable(0, new Int2Int(sqr)));\r
- Assert.AreEqual(5, tree.Count);\r
- Assert.IsTrue(tree.Check());\r
- }\r
+ tree.AddSorted(new FunEnumerable(0, new Fun<int, int>(sqr)));\r
+ Assert.AreEqual(5, tree.Count);\r
+ Assert.IsTrue(tree.Check());\r
+ }\r
\r
\r
- [Test]\r
- public void EmptySome()\r
- {\r
- tree.AddSorted(new FunEnumerable(4, new Int2Int(sqr)));\r
- Assert.AreEqual(4, tree.Count);\r
- Assert.IsTrue(tree.Check());\r
- Assert.AreEqual(0, tree[0]);\r
- Assert.AreEqual(1, tree[1]);\r
- Assert.AreEqual(4, tree[2]);\r
- Assert.AreEqual(9, tree[3]);\r
- }\r
-\r
- [Test]\r
- public void EmptySome2()\r
- {\r
- tree.AddSorted(new FunEnumerable(4, new Int2Int(step)));\r
- //tree.dump();\r
- Assert.AreEqual(4, tree.Count);\r
- Assert.IsTrue(tree.Check());\r
- Assert.AreEqual(0, tree[0]);\r
- Assert.AreEqual(0, tree[1]);\r
- Assert.AreEqual(0, tree[2]);\r
- Assert.AreEqual(1, tree[3]);\r
- }\r
-\r
-\r
- [Test]\r
- public void SomeSome()\r
- {\r
- for (int i = 5; i < 9; i++) tree.Add(i);\r
- tree.Add(1);\r
-\r
- tree.AddSorted(new FunEnumerable(4, new Int2Int(sqr)));\r
- Assert.AreEqual(9, tree.Count);\r
- Assert.IsTrue(tree.Check());\r
- Assert.IsTrue(IC.eq(tree, 0, 1,1, 4, 5, 6, 7, 8, 9));\r
- }\r
-\r
-\r
- [Test]\r
- [ExpectedException(typeof(ArgumentException), "Argument not sorted")]\r
- public void EmptyBad()\r
- {\r
- tree.AddSorted(new FunEnumerable(9, new Int2Int(bad)));\r
- }\r
-\r
-\r
- [TearDown]\r
- public void Dispose() { tree = null; }\r
- }\r
-\r
-\r
-\r
- [TestFixture]\r
- public class Rest\r
- {\r
- TreeBag<int> tree, tree2;\r
-\r
-\r
- [SetUp]\r
- public void Init()\r
- {\r
- tree = new TreeBag<int>(new IC());\r
- tree2 = new TreeBag<int>(new IC());\r
- for (int i = 0; i < 10; i++)\r
- tree.Add(i);\r
- tree.Add(4);\r
-\r
- for (int i = 0; i < 10; i++)\r
- tree2.Add(2 * i);\r
- }\r
-\r
-\r
- [Test]\r
- public void RemoveAll()\r
- {\r
- tree.RemoveAll(tree2.RangeFromTo(3, 7));\r
- Assert.AreEqual(9, tree.Count);\r
- Assert.IsTrue(tree.Check());\r
- Assert.IsTrue(IC.eq(tree, 0, 1, 2, 3,4, 5, 7, 8, 9));\r
- tree.RemoveAll(tree2.RangeFromTo(3, 7));\r
- Assert.AreEqual(8, tree.Count);\r
- Assert.IsTrue(tree.Check());\r
- Assert.IsTrue(IC.eq(tree, 0, 1, 2, 3, 5, 7, 8, 9));\r
- tree.RemoveAll(tree2.RangeFromTo(13, 17));\r
- Assert.AreEqual(8, tree.Count);\r
- Assert.IsTrue(tree.Check());\r
- Assert.IsTrue(IC.eq(tree, 0, 1, 2, 3, 5, 7, 8, 9));\r
- tree.RemoveAll(tree2.RangeFromTo(3, 17));\r
- Assert.AreEqual(7, tree.Count);\r
- Assert.IsTrue(tree.Check());\r
- Assert.IsTrue(IC.eq(tree, 0, 1, 2, 3, 5, 7, 9));\r
- for (int i = 0; i < 10; i++) tree2.Add(i);\r
-\r
- tree.RemoveAll(tree2.RangeFromTo(-1, 10));\r
- Assert.AreEqual(0, tree.Count);\r
- Assert.IsTrue(tree.Check());\r
- Assert.IsTrue(IC.eq(tree));\r
- }\r
-\r
- private void pint<T>(MSG.IEnumerable<T> e)\r
- {\r
- foreach (T i in e)\r
- Console.Write("{0} ", i);\r
-\r
- Console.WriteLine();\r
- }\r
-\r
- [Test]\r
- public void RetainAll()\r
- {\r
- tree.Add(8);tree2.Add(6);\r
- //pint<int>(tree);\r
- //pint<int>(tree2);\r
- tree.RetainAll(tree2.RangeFromTo(3, 17));\r
- Assert.AreEqual(3, tree.Count);\r
- Assert.IsTrue(tree.Check());\r
- Assert.IsTrue(IC.eq(tree, 4, 6, 8));\r
- tree.RetainAll(tree2.RangeFromTo(1, 17));\r
- Assert.AreEqual(3, tree.Count);\r
- Assert.IsTrue(tree.Check());\r
- Assert.IsTrue(IC.eq(tree, 4, 6 , 8));\r
- tree.RetainAll(tree2.RangeFromTo(3, 5));\r
- Assert.AreEqual(1, tree.Count);\r
- Assert.IsTrue(tree.Check());\r
- Assert.IsTrue(IC.eq(tree, 4));\r
- tree.RetainAll(tree2.RangeFromTo(7, 17));\r
- Assert.AreEqual(0, tree.Count);\r
- Assert.IsTrue(tree.Check());\r
- Assert.IsTrue(IC.eq(tree));\r
- for (int i = 0; i < 10; i++) tree.Add(i);\r
-\r
- tree.RetainAll(tree2.RangeFromTo(5, 5));\r
- Assert.AreEqual(0, tree.Count);\r
- Assert.IsTrue(tree.Check());\r
- Assert.IsTrue(IC.eq(tree));\r
- for (int i = 0; i < 10; i++) tree.Add(i);\r
-\r
- tree.RetainAll(tree2.RangeFromTo(15, 25));\r
- Assert.AreEqual(0, tree.Count);\r
- Assert.IsTrue(tree.Check());\r
- Assert.IsTrue(IC.eq(tree));\r
- }\r
-\r
-\r
- [Test]\r
- public void ContainsAll()\r
- {\r
- Assert.IsFalse(tree.ContainsAll(tree2));\r
- Assert.IsTrue(tree.ContainsAll(tree));\r
- tree2.Clear();\r
- Assert.IsTrue(tree.ContainsAll(tree2));\r
- tree.Clear();\r
- Assert.IsTrue(tree.ContainsAll(tree2));\r
- tree2.Add(8);\r
- Assert.IsFalse(tree.ContainsAll(tree2));\r
- }\r
-\r
-\r
- [Test]\r
- public void RemoveInterval()\r
- {\r
- tree.RemoveInterval(3, 4);\r
- Assert.IsTrue(tree.Check());\r
- Assert.AreEqual(7, tree.Count);\r
- Assert.IsTrue(IC.eq(tree, 0, 1, 2, 6, 7, 8, 9));\r
- tree.RemoveInterval(2, 3);\r
- Assert.IsTrue(tree.Check());\r
- Assert.AreEqual(4, tree.Count);\r
- Assert.IsTrue(IC.eq(tree, 0, 1, 8,9));\r
- tree.RemoveInterval(0, 4);\r
- Assert.IsTrue(tree.Check());\r
- Assert.AreEqual(0, tree.Count);\r
- Assert.IsTrue(IC.eq(tree));\r
- }\r
-\r
-\r
- [Test]\r
- [ExpectedException(typeof(ArgumentOutOfRangeException))]\r
- public void RemoveRangeBad1()\r
- {\r
- tree.RemoveInterval(-3, 8);\r
- }\r
-\r
-\r
- [Test]\r
- [ExpectedException(typeof(ArgumentOutOfRangeException))]\r
- public void RemoveRangeBad2()\r
- {\r
- tree.RemoveInterval(3, -8);\r
- }\r
-\r
-\r
- [Test]\r
- [ExpectedException(typeof(ArgumentException))]\r
- public void RemoveRangeBad3()\r
- {\r
- tree.RemoveInterval(3, 9);\r
- }\r
-\r
-\r
- [Test]\r
- public void GetRange()\r
- {\r
- Assert.IsTrue(IC.eq(tree[3, 3]));\r
- Assert.IsTrue(IC.eq(tree[3, 4], 3));\r
- Assert.IsTrue(IC.eq(tree[3, 5], 3, 4));\r
- Assert.IsTrue(IC.eq(tree[3, 6], 3, 4, 4));\r
- Assert.IsTrue(IC.eq(tree[3, 7], 3, 4, 4, 5));\r
- Assert.IsTrue(IC.eq(tree[4, 4]));\r
- Assert.IsTrue(IC.eq(tree[4, 5], 4));\r
- Assert.IsTrue(IC.eq(tree[4, 6], 4, 4));\r
- Assert.IsTrue(IC.eq(tree[4, 7], 4, 4, 5));\r
- Assert.IsTrue(IC.eq(tree[4, 8], 4, 4, 5, 6));\r
- Assert.IsTrue(IC.eq(tree[5, 5]));\r
- Assert.IsTrue(IC.eq(tree[5, 6], 4));\r
- Assert.IsTrue(IC.eq(tree[5, 7], 4, 5));\r
- Assert.IsTrue(IC.eq(tree[5, 8], 4, 5, 6));\r
- Assert.IsTrue(IC.eq(tree[5, 9], 4, 5, 6, 7));\r
- Assert.IsTrue(IC.eq(tree[5, 11], 4, 5, 6, 7, 8, 9));\r
- }\r
-\r
-\r
- [Test]\r
- public void GetRangeBackwards()\r
- {\r
- Assert.IsTrue(IC.eq(tree[3, 3].Backwards()));\r
- Assert.IsTrue(IC.eq(tree[3, 4].Backwards(), 3));\r
- Assert.IsTrue(IC.eq(tree[3, 5].Backwards(), 4, 3));\r
- Assert.IsTrue(IC.eq(tree[3, 6].Backwards(), 4, 4, 3));\r
- Assert.IsTrue(IC.eq(tree[3, 7].Backwards(), 5, 4, 4, 3));\r
- Assert.IsTrue(IC.eq(tree[4, 4].Backwards()));\r
- Assert.IsTrue(IC.eq(tree[4, 5].Backwards(), 4));\r
- Assert.IsTrue(IC.eq(tree[4, 6].Backwards(), 4, 4));\r
- Assert.IsTrue(IC.eq(tree[4, 7].Backwards(), 5, 4, 4));\r
- Assert.IsTrue(IC.eq(tree[4, 8].Backwards(), 6, 5, 4, 4));\r
- Assert.IsTrue(IC.eq(tree[5, 5].Backwards()));\r
- Assert.IsTrue(IC.eq(tree[5, 6].Backwards(), 4));\r
- Assert.IsTrue(IC.eq(tree[5, 7].Backwards(), 5, 4));\r
- Assert.IsTrue(IC.eq(tree[5, 8].Backwards(), 6, 5, 4));\r
- Assert.IsTrue(IC.eq(tree[5, 9].Backwards(), 7, 6, 5, 4));\r
- }\r
-\r
-\r
- [Test]\r
- [ExpectedException(typeof(ArgumentOutOfRangeException))]\r
- public void GetRangeBad1()\r
- {\r
- object foo = tree[-3, 0];\r
- }\r
-\r
-\r
- [Test]\r
- [ExpectedException(typeof(ArgumentOutOfRangeException))]\r
- public void GetRangeBad2()\r
- {\r
- object foo = tree[3, 2];\r
- }\r
-\r
-\r
- [Test]\r
- [ExpectedException(typeof(ArgumentException))]\r
- public void GetRangeBad3()\r
- {\r
- object foo = tree[3, 12];\r
- }\r
-\r
-\r
- [TearDown]\r
- public void Dispose() { tree = null; tree2 = null; }\r
- }\r
- }\r
-\r
-\r
- namespace Hashing\r
- {\r
- [TestFixture]\r
- public class ISequenced\r
- {\r
- private ISequenced<int> dit, dat, dut;\r
-\r
-\r
- [SetUp]\r
- public void Init()\r
- {\r
- dit = new TreeBag<int>(new IC());\r
- dat = new TreeBag<int>(new IC());\r
- dut = new TreeBag<int>(new RevIC());\r
- }\r
-\r
-\r
- [Test]\r
- public void EmptyEmpty()\r
- {\r
- Assert.IsTrue(dit.Equals(dat));\r
- }\r
-\r
-\r
- [Test]\r
- public void EmptyNonEmpty()\r
- {\r
- dit.Add(3);\r
- Assert.IsFalse(dit.Equals(dat));\r
- Assert.IsFalse(dat.Equals(dit));\r
- }\r
-\r
-\r
- public int hasher(params int[] items)\r
- {\r
- int retval = 0;\r
-\r
- foreach (int i in items)\r
- retval = retval * 31 + i;\r
-\r
- return retval;\r
- }\r
-\r
-\r
- [Test]\r
- public void HashVal()\r
- {\r
- Assert.AreEqual(hasher(), dit.GetHashCode());\r
- dit.Add(3);\r
- Assert.AreEqual(hasher(3), dit.GetHashCode());\r
- dit.Add(7);\r
- Assert.AreEqual(hasher(3, 7), dit.GetHashCode());\r
- Assert.AreEqual(hasher(), dut.GetHashCode());\r
- dut.Add(3);\r
- Assert.AreEqual(hasher(3), dut.GetHashCode());\r
- dut.Add(7);\r
- Assert.AreEqual(hasher(7, 3), dut.GetHashCode());\r
- }\r
-\r
-\r
- [Test]\r
- public void Normal()\r
- {\r
- dit.Add(3);\r
- dit.Add(7);\r
- dat.Add(3);\r
- Assert.IsFalse(dit.Equals(dat));\r
- Assert.IsFalse(dat.Equals(dit));\r
- dat.Add(7);\r
- Assert.IsTrue(dit.Equals(dat));\r
- Assert.IsTrue(dat.Equals(dit));\r
- }\r
-\r
-\r
- [Test]\r
- public void WrongOrder()\r
- {\r
- dit.Add(3);\r
- dut.Add(3);\r
- Assert.IsTrue(dit.Equals(dut));\r
- Assert.IsTrue(dut.Equals(dit));\r
- dit.Add(7);\r
- dut.Add(7);\r
- Assert.IsFalse(dit.Equals(dut));\r
- Assert.IsFalse(dut.Equals(dit));\r
- }\r
-\r
-\r
- [Test]\r
- public void Reflexive()\r
- {\r
- Assert.IsTrue(dit.Equals(dit));\r
- dit.Add(3);\r
- Assert.IsTrue(dit.Equals(dit));\r
- dit.Add(7);\r
- Assert.IsTrue(dit.Equals(dit));\r
- }\r
-\r
-\r
- [TearDown]\r
- public void Dispose()\r
- {\r
- dit = null;\r
- dat = null;\r
- dut = null;\r
- }\r
- }\r
-\r
-\r
-\r
- [TestFixture]\r
- public class IEditableCollection\r
- {\r
- private ICollection<int> dit, dat, dut;\r
-\r
-\r
- [SetUp]\r
- public void Init()\r
- {\r
- dit = new TreeBag<int>(new IC());\r
- dat = new TreeBag<int>(new IC());\r
- dut = new TreeBag<int>(new RevIC());\r
- }\r
-\r
-\r
- [Test]\r
- public void EmptyEmpty()\r
- {\r
- Assert.IsTrue(dit.Equals(dat));\r
- }\r
-\r
-\r
- [Test]\r
- public void EmptyNonEmpty()\r
- {\r
- dit.Add(3);\r
- Assert.IsFalse(dit.Equals(dat));\r
- Assert.IsFalse(dat.Equals(dit));\r
- }\r
-\r
-\r
- public int hasher(int count, params int[] items)\r
- {\r
- int retval = 0;\r
-\r
- foreach (int i in items)\r
- retval ^= i;\r
-\r
- return (count << 16) + retval;\r
- }\r
-\r
-\r
- [Test]\r
- public void HashVal()\r
- {\r
- Assert.AreEqual(hasher(0), dit.GetHashCode());\r
- dit.Add(3);\r
- Assert.AreEqual(hasher(1, 3), dit.GetHashCode());\r
- dit.Add(7);\r
- Assert.AreEqual(hasher(2, 3, 7), dit.GetHashCode());\r
- Assert.AreEqual(hasher(0), dut.GetHashCode());\r
- dut.Add(3);\r
- Assert.AreEqual(hasher(1, 3), dut.GetHashCode());\r
- dut.Add(7);\r
- Assert.AreEqual(hasher(2, 7, 3), dut.GetHashCode());\r
- }\r
-\r
-\r
- [Test]\r
- public void Normal()\r
- {\r
- dit.Add(3);\r
- dit.Add(7);\r
- dat.Add(3);\r
- Assert.IsFalse(dit.Equals(dat));\r
- Assert.IsFalse(dat.Equals(dit));\r
- dat.Add(7);\r
- Assert.IsTrue(dit.Equals(dat));\r
- Assert.IsTrue(dat.Equals(dit));\r
- }\r
-\r
-\r
- [Test]\r
- public void WrongOrder()\r
- {\r
- dit.Add(3);\r
- dut.Add(3);\r
- Assert.IsTrue(dit.Equals(dut));\r
- Assert.IsTrue(dut.Equals(dit));\r
- dit.Add(7);\r
- dut.Add(7);\r
- Assert.IsTrue(dit.Equals(dut));\r
- Assert.IsTrue(dut.Equals(dit));\r
- }\r
-\r
-\r
- [Test]\r
- public void Reflexive()\r
- {\r
- Assert.IsTrue(dit.Equals(dit));\r
- dit.Add(3);\r
- Assert.IsTrue(dit.Equals(dit));\r
- dit.Add(7);\r
- Assert.IsTrue(dit.Equals(dit));\r
- }\r
-\r
-\r
- [TearDown]\r
- public void Dispose()\r
- {\r
- dit = null;\r
- dat = null;\r
- dut = null;\r
- }\r
- }\r
- }\r
+ [Test]\r
+ public void EmptySome()\r
+ {\r
+ tree.AddSorted(new FunEnumerable(4, new Fun<int, int>(sqr)));\r
+ Assert.AreEqual(4, tree.Count);\r
+ Assert.IsTrue(tree.Check());\r
+ Assert.AreEqual(0, tree[0]);\r
+ Assert.AreEqual(1, tree[1]);\r
+ Assert.AreEqual(4, tree[2]);\r
+ Assert.AreEqual(9, tree[3]);\r
+ }\r
+\r
+ [Test]\r
+ public void EmptySome2()\r
+ {\r
+ tree.AddSorted(new FunEnumerable(4, new Fun<int, int>(step)));\r
+ //tree.dump();\r
+ Assert.AreEqual(4, tree.Count);\r
+ Assert.IsTrue(tree.Check());\r
+ Assert.AreEqual(0, tree[0]);\r
+ Assert.AreEqual(0, tree[1]);\r
+ Assert.AreEqual(0, tree[2]);\r
+ Assert.AreEqual(1, tree[3]);\r
+ }\r
+\r
+\r
+ [Test]\r
+ public void SomeSome()\r
+ {\r
+ for (int i = 5; i < 9; i++) tree.Add(i);\r
+ tree.Add(1);\r
+\r
+ tree.AddSorted(new FunEnumerable(4, new Fun<int, int>(sqr)));\r
+ Assert.AreEqual(9, tree.Count);\r
+ Assert.IsTrue(tree.Check());\r
+ Assert.IsTrue(IC.eq(tree, 0, 1, 1, 4, 5, 6, 7, 8, 9));\r
+ }\r
+\r
+\r
+ [Test]\r
+ [ExpectedException(typeof(ArgumentException), "Argument not sorted")]\r
+ public void EmptyBad()\r
+ {\r
+ tree.AddSorted(new FunEnumerable(9, new Fun<int, int>(bad)));\r
+ }\r
+\r
+\r
+ [TearDown]\r
+ public void Dispose() { tree = null; }\r
+ }\r
+\r
+\r
+\r
+ [TestFixture]\r
+ public class Rest\r
+ {\r
+ TreeBag<int> tree, tree2;\r
+\r
+\r
+ [SetUp]\r
+ public void Init()\r
+ {\r
+ tree = new TreeBag<int>(new IC());\r
+ tree2 = new TreeBag<int>(new IC());\r
+ for (int i = 0; i < 10; i++)\r
+ tree.Add(i);\r
+ tree.Add(4);\r
+\r
+ for (int i = 0; i < 10; i++)\r
+ tree2.Add(2 * i);\r
+ }\r
+\r
+\r
+ [Test]\r
+ public void RemoveAll()\r
+ {\r
+ tree.RemoveAll(tree2.RangeFromTo(3, 7));\r
+ Assert.AreEqual(9, tree.Count);\r
+ Assert.IsTrue(tree.Check());\r
+ Assert.IsTrue(IC.eq(tree, 0, 1, 2, 3, 4, 5, 7, 8, 9));\r
+ tree.RemoveAll(tree2.RangeFromTo(3, 7));\r
+ Assert.AreEqual(8, tree.Count);\r
+ Assert.IsTrue(tree.Check());\r
+ Assert.IsTrue(IC.eq(tree, 0, 1, 2, 3, 5, 7, 8, 9));\r
+ tree.RemoveAll(tree2.RangeFromTo(13, 17));\r
+ Assert.AreEqual(8, tree.Count);\r
+ Assert.IsTrue(tree.Check());\r
+ Assert.IsTrue(IC.eq(tree, 0, 1, 2, 3, 5, 7, 8, 9));\r
+ tree.RemoveAll(tree2.RangeFromTo(3, 17));\r
+ Assert.AreEqual(7, tree.Count);\r
+ Assert.IsTrue(tree.Check());\r
+ Assert.IsTrue(IC.eq(tree, 0, 1, 2, 3, 5, 7, 9));\r
+ for (int i = 0; i < 10; i++) tree2.Add(i);\r
+\r
+ tree.RemoveAll(tree2.RangeFromTo(-1, 10));\r
+ Assert.AreEqual(0, tree.Count);\r
+ Assert.IsTrue(tree.Check());\r
+ Assert.IsTrue(IC.eq(tree));\r
+ }\r
+\r
+ private void pint<T>(SCG.IEnumerable<T> e)\r
+ {\r
+ foreach (T i in e)\r
+ Console.Write("{0} ", i);\r
+\r
+ Console.WriteLine();\r
+ }\r
+\r
+ [Test]\r
+ public void RetainAll()\r
+ {\r
+ tree.Add(8); tree2.Add(6);\r
+ //pint<int>(tree);\r
+ //pint<int>(tree2);\r
+ tree.RetainAll(tree2.RangeFromTo(3, 17));\r
+ Assert.AreEqual(3, tree.Count);\r
+ Assert.IsTrue(tree.Check());\r
+ Assert.IsTrue(IC.eq(tree, 4, 6, 8));\r
+ tree.RetainAll(tree2.RangeFromTo(1, 17));\r
+ Assert.AreEqual(3, tree.Count);\r
+ Assert.IsTrue(tree.Check());\r
+ Assert.IsTrue(IC.eq(tree, 4, 6, 8));\r
+ tree.RetainAll(tree2.RangeFromTo(3, 5));\r
+ Assert.AreEqual(1, tree.Count);\r
+ Assert.IsTrue(tree.Check());\r
+ Assert.IsTrue(IC.eq(tree, 4));\r
+ tree.RetainAll(tree2.RangeFromTo(7, 17));\r
+ Assert.AreEqual(0, tree.Count);\r
+ Assert.IsTrue(tree.Check());\r
+ Assert.IsTrue(IC.eq(tree));\r
+ for (int i = 0; i < 10; i++) tree.Add(i);\r
+\r
+ tree.RetainAll(tree2.RangeFromTo(5, 5));\r
+ Assert.AreEqual(0, tree.Count);\r
+ Assert.IsTrue(tree.Check());\r
+ Assert.IsTrue(IC.eq(tree));\r
+ for (int i = 0; i < 10; i++) tree.Add(i);\r
+\r
+ tree.RetainAll(tree2.RangeFromTo(15, 25));\r
+ Assert.AreEqual(0, tree.Count);\r
+ Assert.IsTrue(tree.Check());\r
+ Assert.IsTrue(IC.eq(tree));\r
+ }\r
+\r
+\r
+ [Test]\r
+ public void ContainsAll()\r
+ {\r
+ Assert.IsFalse(tree.ContainsAll(tree2));\r
+ Assert.IsTrue(tree.ContainsAll(tree));\r
+ tree2.Clear();\r
+ Assert.IsTrue(tree.ContainsAll(tree2));\r
+ tree.Clear();\r
+ Assert.IsTrue(tree.ContainsAll(tree2));\r
+ tree2.Add(8);\r
+ Assert.IsFalse(tree.ContainsAll(tree2));\r
+ }\r
+\r
+\r
+ [Test]\r
+ public void RemoveInterval()\r
+ {\r
+ tree.RemoveInterval(3, 4);\r
+ Assert.IsTrue(tree.Check());\r
+ Assert.AreEqual(7, tree.Count);\r
+ Assert.IsTrue(IC.eq(tree, 0, 1, 2, 6, 7, 8, 9));\r
+ tree.RemoveInterval(2, 3);\r
+ Assert.IsTrue(tree.Check());\r
+ Assert.AreEqual(4, tree.Count);\r
+ Assert.IsTrue(IC.eq(tree, 0, 1, 8, 9));\r
+ tree.RemoveInterval(0, 4);\r
+ Assert.IsTrue(tree.Check());\r
+ Assert.AreEqual(0, tree.Count);\r
+ Assert.IsTrue(IC.eq(tree));\r
+ }\r
+\r
+\r
+ [Test]\r
+ [ExpectedException(typeof(ArgumentOutOfRangeException))]\r
+ public void RemoveRangeBad1()\r
+ {\r
+ tree.RemoveInterval(-3, 8);\r
+ }\r
+\r
+\r
+ [Test]\r
+ [ExpectedException(typeof(ArgumentOutOfRangeException))]\r
+ public void RemoveRangeBad2()\r
+ {\r
+ tree.RemoveInterval(3, -8);\r
+ }\r
+\r
+\r
+ [Test]\r
+ [ExpectedException(typeof(ArgumentOutOfRangeException))]\r
+ public void RemoveRangeBad3()\r
+ {\r
+ tree.RemoveInterval(3, 9);\r
+ }\r
+\r
+\r
+ [Test]\r
+ public void GetRange()\r
+ {\r
+ Assert.IsTrue(IC.eq(tree[3, 3]));\r
+ Assert.IsTrue(IC.eq(tree[3, 4], 3));\r
+ Assert.IsTrue(IC.eq(tree[3, 5], 3, 4));\r
+ Assert.IsTrue(IC.eq(tree[3, 6], 3, 4, 4));\r
+ Assert.IsTrue(IC.eq(tree[3, 7], 3, 4, 4, 5));\r
+ Assert.IsTrue(IC.eq(tree[4, 4]));\r
+ Assert.IsTrue(IC.eq(tree[4, 5], 4));\r
+ Assert.IsTrue(IC.eq(tree[4, 6], 4, 4));\r
+ Assert.IsTrue(IC.eq(tree[4, 7], 4, 4, 5));\r
+ Assert.IsTrue(IC.eq(tree[4, 8], 4, 4, 5, 6));\r
+ Assert.IsTrue(IC.eq(tree[5, 5]));\r
+ Assert.IsTrue(IC.eq(tree[5, 6], 4));\r
+ Assert.IsTrue(IC.eq(tree[5, 7], 4, 5));\r
+ Assert.IsTrue(IC.eq(tree[5, 8], 4, 5, 6));\r
+ Assert.IsTrue(IC.eq(tree[5, 9], 4, 5, 6, 7));\r
+ Assert.IsTrue(IC.eq(tree[5, 11], 4, 5, 6, 7, 8, 9));\r
+ }\r
+\r
+\r
+ [Test]\r
+ public void GetRangeBackwards()\r
+ {\r
+ Assert.IsTrue(IC.eq(tree[3, 3].Backwards()));\r
+ Assert.IsTrue(IC.eq(tree[3, 4].Backwards(), 3));\r
+ Assert.IsTrue(IC.eq(tree[3, 5].Backwards(), 4, 3));\r
+ Assert.IsTrue(IC.eq(tree[3, 6].Backwards(), 4, 4, 3));\r
+ Assert.IsTrue(IC.eq(tree[3, 7].Backwards(), 5, 4, 4, 3));\r
+ Assert.IsTrue(IC.eq(tree[4, 4].Backwards()));\r
+ Assert.IsTrue(IC.eq(tree[4, 5].Backwards(), 4));\r
+ Assert.IsTrue(IC.eq(tree[4, 6].Backwards(), 4, 4));\r
+ Assert.IsTrue(IC.eq(tree[4, 7].Backwards(), 5, 4, 4));\r
+ Assert.IsTrue(IC.eq(tree[4, 8].Backwards(), 6, 5, 4, 4));\r
+ Assert.IsTrue(IC.eq(tree[5, 5].Backwards()));\r
+ Assert.IsTrue(IC.eq(tree[5, 6].Backwards(), 4));\r
+ Assert.IsTrue(IC.eq(tree[5, 7].Backwards(), 5, 4));\r
+ Assert.IsTrue(IC.eq(tree[5, 8].Backwards(), 6, 5, 4));\r
+ Assert.IsTrue(IC.eq(tree[5, 9].Backwards(), 7, 6, 5, 4));\r
+ }\r
+\r
+\r
+ [Test]\r
+ [ExpectedException(typeof(ArgumentOutOfRangeException))]\r
+ public void GetRangeBad1()\r
+ {\r
+ object foo = tree[-3, 0];\r
+ }\r
+\r
+\r
+ [Test]\r
+ [ExpectedException(typeof(ArgumentOutOfRangeException))]\r
+ public void GetRangeBad2()\r
+ {\r
+ object foo = tree[3, 2];\r
+ }\r
+\r
+\r
+ [Test]\r
+ [ExpectedException(typeof(ArgumentOutOfRangeException))]\r
+ public void GetRangeBad3()\r
+ {\r
+ object foo = tree[3, 12];\r
+ }\r
+\r
+\r
+ [TearDown]\r
+ public void Dispose() { tree = null; tree2 = null; }\r
+ }\r
+ }\r
+\r
+\r
+ namespace Hashing\r
+ {\r
+ [TestFixture]\r
+ public class ISequenced\r
+ {\r
+ private ISequenced<int> dit, dat, dut;\r
+\r
+\r
+ [SetUp]\r
+ public void Init()\r
+ {\r
+ dit = new TreeBag<int>(Comparer<int>.Default, EqualityComparer<int>.Default);\r
+ dat = new TreeBag<int>(Comparer<int>.Default, EqualityComparer<int>.Default);\r
+ dut = new TreeBag<int>(new RevIC(), EqualityComparer<int>.Default);\r
+ }\r
+\r
+\r
+ [Test]\r
+ public void EmptyEmpty()\r
+ {\r
+ Assert.IsTrue(dit.SequencedEquals(dat));\r
+ }\r
+\r
+\r
+ [Test]\r
+ public void EmptyNonEmpty()\r
+ {\r
+ dit.Add(3);\r
+ Assert.IsFalse(dit.SequencedEquals(dat));\r
+ Assert.IsFalse(dat.SequencedEquals(dit));\r
+ }\r
+\r
+ [Test]\r
+ public void HashVal()\r
+ {\r
+ Assert.AreEqual(CHC.sequencedhashcode(), dit.GetSequencedHashCode());\r
+ dit.Add(3);\r
+ Assert.AreEqual(CHC.sequencedhashcode(3), dit.GetSequencedHashCode());\r
+ dit.Add(7);\r
+ Assert.AreEqual(CHC.sequencedhashcode(3, 7), dit.GetSequencedHashCode());\r
+ Assert.AreEqual(CHC.sequencedhashcode(), dut.GetSequencedHashCode());\r
+ dut.Add(3);\r
+ Assert.AreEqual(CHC.sequencedhashcode(3), dut.GetSequencedHashCode());\r
+ dut.Add(7);\r
+ Assert.AreEqual(CHC.sequencedhashcode(7, 3), dut.GetSequencedHashCode());\r
+ }\r
+\r
+\r
+ [Test]\r
+ public void Normal()\r
+ {\r
+ dit.Add(3);\r
+ dit.Add(7);\r
+ dat.Add(3);\r
+ Assert.IsFalse(dit.SequencedEquals(dat));\r
+ Assert.IsFalse(dat.SequencedEquals(dit));\r
+ dat.Add(7);\r
+ Assert.IsTrue(dit.SequencedEquals(dat));\r
+ Assert.IsTrue(dat.SequencedEquals(dit));\r
+ }\r
+\r
+\r
+ [Test]\r
+ public void WrongOrder()\r
+ {\r
+ dit.Add(3);\r
+ dut.Add(3);\r
+ Assert.IsTrue(dit.SequencedEquals(dut));\r
+ Assert.IsTrue(dut.SequencedEquals(dit));\r
+ dit.Add(7);\r
+ dut.Add(7);\r
+ Assert.IsFalse(dit.SequencedEquals(dut));\r
+ Assert.IsFalse(dut.SequencedEquals(dit));\r
+ }\r
+\r
+\r
+ [Test]\r
+ public void Reflexive()\r
+ {\r
+ Assert.IsTrue(dit.SequencedEquals(dit));\r
+ dit.Add(3);\r
+ Assert.IsTrue(dit.SequencedEquals(dit));\r
+ dit.Add(7);\r
+ Assert.IsTrue(dit.SequencedEquals(dit));\r
+ }\r
+\r
+\r
+ [TearDown]\r
+ public void Dispose()\r
+ {\r
+ dit = null;\r
+ dat = null;\r
+ dut = null;\r
+ }\r
+ }\r
+\r
+\r
+\r
+ [TestFixture]\r
+ public class IEditableCollection\r
+ {\r
+ private ICollection<int> dit, dat, dut;\r
+\r
+\r
+ [SetUp]\r
+ public void Init()\r
+ {\r
+ dit = new TreeBag<int>(Comparer<int>.Default, EqualityComparer<int>.Default);\r
+ dat = new TreeBag<int>(Comparer<int>.Default, EqualityComparer<int>.Default);\r
+ dut = new TreeBag<int>(new RevIC(), EqualityComparer<int>.Default);\r
+ }\r
+\r
+\r
+ [Test]\r
+ public void EmptyEmpty()\r
+ {\r
+ Assert.IsTrue(dit.UnsequencedEquals(dat));\r
+ }\r
+\r
+\r
+ [Test]\r
+ public void EmptyNonEmpty()\r
+ {\r
+ dit.Add(3);\r
+ Assert.IsFalse(dit.UnsequencedEquals(dat));\r
+ Assert.IsFalse(dat.UnsequencedEquals(dit));\r
+ }\r
+\r
+\r
+ [Test]\r
+ public void HashVal()\r
+ {\r
+ Assert.AreEqual(CHC.unsequencedhashcode(), dit.GetUnsequencedHashCode());\r
+ dit.Add(3);\r
+ Assert.AreEqual(CHC.unsequencedhashcode(3), dit.GetUnsequencedHashCode());\r
+ dit.Add(7);\r
+ Assert.AreEqual(CHC.unsequencedhashcode(3, 7), dit.GetUnsequencedHashCode());\r
+ Assert.AreEqual(CHC.unsequencedhashcode(), dut.GetUnsequencedHashCode());\r
+ dut.Add(3);\r
+ Assert.AreEqual(CHC.unsequencedhashcode(3), dut.GetUnsequencedHashCode());\r
+ dut.Add(7);\r
+ Assert.AreEqual(CHC.unsequencedhashcode(7, 3), dut.GetUnsequencedHashCode());\r
+ }\r
+\r
+\r
+ [Test]\r
+ public void Normal()\r
+ {\r
+ dit.Add(3);\r
+ dit.Add(7);\r
+ dat.Add(3);\r
+ Assert.IsFalse(dit.UnsequencedEquals(dat));\r
+ Assert.IsFalse(dat.UnsequencedEquals(dit));\r
+ dat.Add(7);\r
+ Assert.IsTrue(dit.UnsequencedEquals(dat));\r
+ Assert.IsTrue(dat.UnsequencedEquals(dit));\r
+ }\r
+\r
+\r
+ [Test]\r
+ public void WrongOrder()\r
+ {\r
+ dit.Add(3);\r
+ dut.Add(3);\r
+ Assert.IsTrue(dit.UnsequencedEquals(dut));\r
+ Assert.IsTrue(dut.UnsequencedEquals(dit));\r
+ dit.Add(7);\r
+ dut.Add(7);\r
+ Assert.IsTrue(dit.UnsequencedEquals(dut));\r
+ Assert.IsTrue(dut.UnsequencedEquals(dit));\r
+ }\r
+\r
+\r
+ [Test]\r
+ public void Reflexive()\r
+ {\r
+ Assert.IsTrue(dit.UnsequencedEquals(dit));\r
+ dit.Add(3);\r
+ Assert.IsTrue(dit.UnsequencedEquals(dit));\r
+ dit.Add(7);\r
+ Assert.IsTrue(dit.UnsequencedEquals(dit));\r
+ }\r
+\r
+\r
+ [TearDown]\r
+ public void Dispose()\r
+ {\r
+ dit = null;\r
+ dat = null;\r
+ dut = null;\r
+ }\r
+ }\r
+ }\r
\r
}\r
-#endif\r