mcs/class/Mono.C5/Test/trees/Bag.cs

   1 #if NET_2_0\r
   2 /*\r
   3  Copyright (c) 2003-2004 Niels Kokholm <kokholm@itu.dk> and Peter Sestoft <sestoft@dina.kvl.dk>\r
   4  Permission is hereby granted, free of charge, to any person obtaining a copy\r
   5  of this software and associated documentation files (the "Software"), to deal\r
   6  in the Software without restriction, including without limitation the rights\r
   7  to use, copy, modify, merge, publish, distribute, sublicense, and/or sell\r
   8  copies of the Software, and to permit persons to whom the Software is\r
   9  furnished to do so, subject to the following conditions:\r
  10  \r
  11  The above copyright notice and this permission notice shall be included in\r
  12  all copies or substantial portions of the Software.\r
  13  \r
  14  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR\r
  15  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,\r
  16  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE\r
  17  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER\r
  18  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,\r
  19  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE\r
  20  SOFTWARE.\r
  21 */\r
  22 \r
  23 using System;\r
  24 using C5;\r
  25 using NUnit.Framework;\r
  26 using MSG=System.Collections.Generic;\r
  27 \r
  28 \r
  29 namespace nunit.trees.TreeBag\r
  30 {\r
  31         [TestFixture]\r
  32         public class Combined\r
  33         {\r
  34                 private IIndexedSorted<KeyValuePair<int,int>> lst;\r
  35 \r
  36 \r
  37                 [SetUp]\r
  38                 public void Init()\r
  39                 {\r
  40                         lst = new TreeBag<KeyValuePair<int,int>>(new KeyValuePairComparer<int,int>(new IC()));\r
  41                         for (int i = 0; i < 10; i++)\r
  42                                 lst.Add(new KeyValuePair<int,int>(i, i + 30));\r
  43                 }\r
  44 \r
  45 \r
  46                 [TearDown]\r
  47                 public void Dispose() { lst = null; }\r
  48 \r
  49 \r
  50                 [Test]\r
  51                 public void Find()\r
  52                 {\r
  53                         KeyValuePair<int,int> p = new KeyValuePair<int,int>(3, 78);\r
  54 \r
  55                         Assert.IsTrue(lst.Find(ref p));\r
  56                         Assert.AreEqual(3, p.key);\r
  57                         Assert.AreEqual(33, p.value);\r
  58                         p = new KeyValuePair<int,int>(13, 78);\r
  59                         Assert.IsFalse(lst.Find(ref p));\r
  60                 }\r
  61 \r
  62 \r
  63                 [Test] \r
  64                 public void FindOrAdd()\r
  65                 {\r
  66                         KeyValuePair<int,int> p = new KeyValuePair<int,int>(3, 78);\r
  67 \r
  68                         Assert.IsTrue(lst.FindOrAdd(ref p));\r
  69                         Assert.AreEqual(3, p.key);\r
  70                         Assert.AreEqual(33, p.value);\r
  71                         p = new KeyValuePair<int,int>(13, 79);\r
  72                         Assert.IsFalse(lst.FindOrAdd(ref p));\r
  73                         Assert.AreEqual(13, lst[11].key);\r
  74                         Assert.AreEqual(79, lst[11].value);\r
  75                 }\r
  76 \r
  77 \r
  78                 [Test]\r
  79                 public void Update()\r
  80                 {\r
  81                         KeyValuePair<int,int> p = new KeyValuePair<int,int>(3, 78);\r
  82 \r
  83                         Assert.IsTrue(lst.Update(p));\r
  84                         Assert.AreEqual(3, lst[3].key);\r
  85                         Assert.AreEqual(78, lst[3].value);\r
  86                         p = new KeyValuePair<int,int>(13, 78);\r
  87                         Assert.IsFalse(lst.Update(p));\r
  88                 }\r
  89 \r
  90 \r
  91                 [Test]\r
  92                 public void UpdateOrAdd()\r
  93                 {\r
  94                         KeyValuePair<int,int> p = new KeyValuePair<int,int>(3, 78);\r
  95 \r
  96                         Assert.IsTrue(lst.UpdateOrAdd(p));\r
  97                         Assert.AreEqual(3, lst[3].key);\r
  98                         Assert.AreEqual(78, lst[3].value);\r
  99                         p = new KeyValuePair<int,int>(13, 79);\r
 100                         Assert.IsFalse(lst.UpdateOrAdd(p));\r
 101                         Assert.AreEqual(13, lst[11].key);\r
 102                         Assert.AreEqual(79, lst[11].value);\r
 103                 }\r
 104 \r
 105 \r
 106                 [Test]\r
 107                 public void RemoveWithReturn()\r
 108                 {\r
 109                         KeyValuePair<int,int> p = new KeyValuePair<int,int>(3, 78);\r
 110 \r
 111                         Assert.IsTrue(lst.RemoveWithReturn(ref p));\r
 112                         Assert.AreEqual(3, p.key);\r
 113                         Assert.AreEqual(33, p.value);\r
 114                         Assert.AreEqual(4, lst[3].key);\r
 115                         Assert.AreEqual(34, lst[3].value);\r
 116                         p = new KeyValuePair<int,int>(13, 78);\r
 117                         Assert.IsFalse(lst.RemoveWithReturn(ref p));\r
 118                 }\r
 119         }\r
 120 \r
 121 \r
 122         [TestFixture]\r
 123         public class Simple\r
 124         {\r
 125                 private TreeBag<string> bag;\r
 126 \r
 127 \r
 128                 [SetUp]\r
 129                 public void Init()\r
 130                 {\r
 131                         bag = new TreeBag<string>(new SC());\r
 132                 }\r
 133 \r
 134 \r
 135                 [TearDown]\r
 136                 public void Dispose()\r
 137                 {\r
 138                         bag = null;\r
 139                 }\r
 140 \r
 141                         [Test]\r
 142                 public void Initial()\r
 143                 {\r
 144                         bool res;\r
 145 \r
 146                         Assert.IsFalse(bag.IsReadOnly);\r
 147                         Assert.AreEqual(0, bag.Count, "new bag should be empty");\r
 148                         Assert.AreEqual(0, bag.ContainsCount("A"));\r
 149                         Assert.AreEqual(0, bag.ContainsCount("B"));\r
 150                         Assert.AreEqual(0, bag.ContainsCount("C"));\r
 151                         Assert.IsFalse(bag.Contains("A"));\r
 152                         Assert.IsFalse(bag.Contains("B"));\r
 153                         Assert.IsFalse(bag.Contains("C"));\r
 154                         bag.Add("A");\r
 155                         Assert.AreEqual(1, bag.Count);\r
 156                         Assert.AreEqual(1, bag.ContainsCount("A"));\r
 157                         Assert.AreEqual(0, bag.ContainsCount("B"));\r
 158                         Assert.AreEqual(0, bag.ContainsCount("C"));\r
 159                         Assert.IsTrue(bag.Contains("A"));\r
 160                         Assert.IsFalse(bag.Contains("B"));\r
 161                         Assert.IsFalse(bag.Contains("C"));\r
 162                         bag.Add("C");\r
 163                         Assert.AreEqual(2, bag.Count);\r
 164                         Assert.AreEqual(1, bag.ContainsCount("A"));\r
 165                         Assert.AreEqual(0, bag.ContainsCount("B"));\r
 166                         Assert.AreEqual(1, bag.ContainsCount("C"));\r
 167                         Assert.IsTrue(bag.Contains("A"));\r
 168                         Assert.IsFalse(bag.Contains("B"));\r
 169                         Assert.IsTrue(bag.Contains("C"));\r
 170                         bag.Add("C");\r
 171                         Assert.AreEqual(3, bag.Count);\r
 172                         Assert.AreEqual(1, bag.ContainsCount("A"));\r
 173                         Assert.AreEqual(0, bag.ContainsCount("B"));\r
 174                         Assert.AreEqual(2, bag.ContainsCount("C"));\r
 175                         Assert.IsTrue(bag.Contains("A"));\r
 176                         Assert.IsFalse(bag.Contains("B"));\r
 177                         Assert.IsTrue(bag.Contains("C"));\r
 178                         bag.Add("B");\r
 179                         bag.Add("C");\r
 180                         Assert.AreEqual(5, bag.Count);\r
 181                         Assert.AreEqual(1, bag.ContainsCount("A"));\r
 182                         Assert.AreEqual(1, bag.ContainsCount("B"));\r
 183                         Assert.AreEqual(3, bag.ContainsCount("C"));\r
 184                         Assert.IsTrue(bag.Contains("A"));\r
 185                         Assert.IsTrue(bag.Contains("B"));\r
 186                         Assert.IsTrue(bag.Contains("C"));\r
 187                         res = bag.Remove("C");\r
 188                         Assert.AreEqual(4, bag.Count);\r
 189                         Assert.AreEqual(1, bag.ContainsCount("A"));\r
 190                         Assert.AreEqual(1, bag.ContainsCount("B"));\r
 191                         Assert.AreEqual(2, bag.ContainsCount("C"));\r
 192                         Assert.IsTrue(bag.Contains("A"));\r
 193                         Assert.IsTrue(bag.Contains("B"));\r
 194                         Assert.IsTrue(bag.Contains("C"));\r
 195                         res = bag.Remove("A");\r
 196                         Assert.AreEqual(3, bag.Count);\r
 197                         Assert.AreEqual(0, bag.ContainsCount("A"));\r
 198                         Assert.AreEqual(1, bag.ContainsCount("B"));\r
 199                         Assert.AreEqual(2, bag.ContainsCount("C"));\r
 200                         Assert.IsFalse(bag.Contains("A"));\r
 201                         Assert.IsTrue(bag.Contains("B"));\r
 202                         Assert.IsTrue(bag.Contains("C"));\r
 203                         bag.RemoveAllCopies("C");\r
 204                         Assert.AreEqual(1, bag.Count);\r
 205                         Assert.AreEqual(0, bag.ContainsCount("A"));\r
 206                         Assert.AreEqual(1, bag.ContainsCount("B"));\r
 207                         Assert.AreEqual(0, bag.ContainsCount("C"));\r
 208                         Assert.IsFalse(bag.Contains("A"));\r
 209                         Assert.IsTrue(bag.Contains("B"));\r
 210                         Assert.IsFalse(bag.Contains("C"));\r
 211                         Assert.IsFalse(bag.Contains("Z"));\r
 212                         Assert.IsFalse(bag.Remove("Z"));\r
 213                         bag.RemoveAllCopies("Z");\r
 214                         Assert.AreEqual(1, bag.Count);\r
 215                         Assert.AreEqual(0, bag.ContainsCount("A"));\r
 216                         Assert.AreEqual(1, bag.ContainsCount("B"));\r
 217                         Assert.AreEqual(0, bag.ContainsCount("C"));\r
 218                         Assert.IsFalse(bag.Contains("A"));\r
 219                         Assert.IsTrue(bag.Contains("B"));\r
 220                         Assert.IsFalse(bag.Contains("C"));\r
 221                         Assert.IsFalse(bag.Contains("Z"));\r
 222                 }\r
 223         }\r
 224 \r
 225         [TestFixture]\r
 226         public class FindOrAdd\r
 227         {\r
 228                 private TreeBag<KeyValuePair<int,string>> bag;\r
 229 \r
 230 \r
 231                 [SetUp]\r
 232                 public void Init()\r
 233                 {\r
 234                         bag = new TreeBag<KeyValuePair<int,string>>(new KeyValuePairComparer<int,string>(new IC()));\r
 235                 }\r
 236 \r
 237 \r
 238                 [TearDown]\r
 239                 public void Dispose()\r
 240                 {\r
 241                         bag = null;\r
 242                 }\r
 243 \r
 244 \r
 245                 [Test]\r
 246                 public void Test()\r
 247                 {\r
 248                         KeyValuePair<int,string> p = new KeyValuePair<int,string>(3,"tre");\r
 249                         Assert.IsFalse(bag.FindOrAdd(ref p));\r
 250                         p.value = "drei";\r
 251                         Assert.IsTrue(bag.FindOrAdd(ref p));\r
 252                         Assert.AreEqual("tre", p.value);\r
 253                         p.value = "three";\r
 254                         Assert.AreEqual(2, bag.ContainsCount(p));\r
 255                         Assert.AreEqual("tre", bag[0].value);\r
 256                 }\r
 257         }\r
 258 \r
 259 \r
 260         [TestFixture]\r
 261         public class Enumerators\r
 262         {\r
 263                 private TreeBag<string> bag;\r
 264 \r
 265                 private MSG.IEnumerator<string> bagenum;\r
 266 \r
 267 \r
 268                 [SetUp]\r
 269                 public void Init()\r
 270                 {\r
 271                         bag = new TreeBag<string>(new SC());\r
 272                         foreach (string s in new string[] { "A", "B", "A", "A", "B", "C", "D", "B" })\r
 273                                 bag.Add(s);\r
 274 \r
 275                         bagenum = bag.GetEnumerator();\r
 276                 }\r
 277 \r
 278 \r
 279                 [TearDown]\r
 280                 public void Dispose()\r
 281                 {\r
 282                         bagenum = null;\r
 283                         bag = null;\r
 284                 }\r
 285 \r
 286 \r
 287                 [Test]\r
 288                 [ExpectedException(typeof(InvalidOperationException))]\r
 289                 public void MoveNextOnModified()\r
 290                 {\r
 291                         //TODO: also problem before first MoveNext!!!!!!!!!!\r
 292                         bagenum.MoveNext();\r
 293                         bag.Add("T");\r
 294                         bagenum.MoveNext();\r
 295                 }\r
 296 \r
 297 \r
 298                 [Test]\r
 299                 public void NormalUse()\r
 300                 {\r
 301                         Assert.IsTrue(bagenum.MoveNext());\r
 302                         Assert.AreEqual(bagenum.Current, "A");\r
 303                         Assert.IsTrue(bagenum.MoveNext());\r
 304                         Assert.AreEqual(bagenum.Current, "A");\r
 305                         Assert.IsTrue(bagenum.MoveNext());\r
 306                         Assert.AreEqual(bagenum.Current, "A");\r
 307                         Assert.IsTrue(bagenum.MoveNext());\r
 308                         Assert.AreEqual(bagenum.Current, "B");\r
 309                         Assert.IsTrue(bagenum.MoveNext());\r
 310                         Assert.AreEqual(bagenum.Current, "B");\r
 311                         Assert.IsTrue(bagenum.MoveNext());\r
 312                         Assert.AreEqual(bagenum.Current, "B");\r
 313                         Assert.IsTrue(bagenum.MoveNext());\r
 314                         Assert.AreEqual(bagenum.Current, "C");\r
 315                         Assert.IsTrue(bagenum.MoveNext());\r
 316                         Assert.AreEqual(bagenum.Current, "D");\r
 317                         Assert.IsFalse(bagenum.MoveNext());\r
 318                 }\r
 319         }\r
 320 \r
 321         [TestFixture]\r
 322         public class Ranges\r
 323         {\r
 324                 private TreeBag<int> tree;\r
 325 \r
 326                 private IComparer<int> c;\r
 327 \r
 328 \r
 329                 [SetUp]\r
 330                 public void Init()\r
 331                 {\r
 332                         c = new IC();\r
 333                         tree = new TreeBag<int>(c);\r
 334                         for (int i = 1; i <= 10; i++)\r
 335                         {\r
 336                                 tree.Add(i * 2);tree.Add(i);\r
 337                         }\r
 338                 }\r
 339 \r
 340 \r
 341                 [Test]\r
 342                 public void Enumerator()\r
 343                 {\r
 344                         MSG.IEnumerator<int> e = tree.RangeFromTo(5, 17).GetEnumerator();\r
 345                         int i = 0;\r
 346                         int[] all = new int[] { 5, 6, 6, 7, 8, 8, 9, 10, 10, 12, 14, 16 };\r
 347                         while (e.MoveNext())\r
 348                         {\r
 349                                 Assert.AreEqual(all[i++], e.Current);\r
 350                         }\r
 351 \r
 352                         Assert.AreEqual(12, i);\r
 353                 }\r
 354 \r
 355 \r
 356                 [Test]\r
 357                 [ExpectedException(typeof(InvalidOperationException))]\r
 358                 public void Enumerator2()\r
 359                 {\r
 360                         MSG.IEnumerator<int> e = tree.RangeFromTo(5, 17).GetEnumerator();\r
 361                         int i = e.Current;\r
 362                 }\r
 363 \r
 364 \r
 365                 [Test]\r
 366                 [ExpectedException(typeof(InvalidOperationException))]\r
 367                 public void Enumerator3()\r
 368                 {\r
 369                         MSG.IEnumerator<int> e = tree.RangeFromTo(5, 17).GetEnumerator();\r
 370 \r
 371                         while (e.MoveNext());\r
 372 \r
 373                         int i = e.Current;\r
 374                 }\r
 375 \r
 376 \r
 377                 [Test]\r
 378                 public void Remove()\r
 379                 {\r
 380                         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
 381 \r
 382                         tree.RemoveRangeFrom(18);\r
 383                         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
 384                         tree.RemoveRangeFrom(28);\r
 385                         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
 386                         tree.RemoveRangeFrom(1);\r
 387                         Assert.IsTrue(IC.eq(tree));\r
 388                         foreach (int i in all) tree.Add(i);\r
 389 \r
 390                         tree.RemoveRangeTo(10);\r
 391                         Assert.IsTrue(IC.eq(tree, new int[] { 10, 10, 12, 14, 16, 18, 20 }));\r
 392                         tree.RemoveRangeTo(2);\r
 393                         Assert.IsTrue(IC.eq(tree, new int[] { 10, 10, 12, 14, 16, 18, 20 }));\r
 394                         tree.RemoveRangeTo(21);\r
 395                         Assert.IsTrue(IC.eq(tree));\r
 396                         foreach (int i in all) tree.Add(i);\r
 397 \r
 398                         tree.RemoveRangeFromTo(4, 8);\r
 399                         Assert.IsTrue(IC.eq(tree, 1, 2, 2, 3, 8, 8, 9, 10, 10, 12, 14, 16, 18, 20));\r
 400                         tree.RemoveRangeFromTo(14, 28);\r
 401                         Assert.IsTrue(IC.eq(tree, 1, 2, 2, 3, 8, 8, 9, 10, 10, 12));\r
 402                         tree.RemoveRangeFromTo(0, 9);\r
 403                         Assert.IsTrue(IC.eq(tree, 9, 10, 10, 12));\r
 404                         tree.RemoveRangeFromTo(0, 81);\r
 405                         Assert.IsTrue(IC.eq(tree));\r
 406                 }\r
 407 \r
 408 \r
 409                 [Test]\r
 410                 public void Normal()\r
 411                 {\r
 412                         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
 413 \r
 414                         Assert.IsTrue(IC.eq(tree, all));\r
 415                         Assert.IsTrue(IC.eq(tree.RangeAll(), all));\r
 416                         Assert.AreEqual(20, tree.RangeAll().Count);\r
 417                         Assert.IsTrue(IC.eq(tree.RangeFrom(11), new int[] { 12, 14, 16, 18, 20 }));\r
 418                         Assert.AreEqual(5, tree.RangeFrom(11).Count);\r
 419                         Assert.IsTrue(IC.eq(tree.RangeFrom(12), new int[] { 12, 14, 16, 18, 20 }));\r
 420                         Assert.IsTrue(IC.eq(tree.RangeFrom(1), all));\r
 421                         Assert.IsTrue(IC.eq(tree.RangeFrom(0), all));\r
 422                         Assert.IsTrue(IC.eq(tree.RangeFrom(21), new int[] { }));\r
 423                         Assert.IsTrue(IC.eq(tree.RangeFrom(20), new int[] { 20 }));\r
 424                         Assert.IsTrue(IC.eq(tree.RangeTo(8), new int[] { 1, 2, 2, 3, 4, 4, 5, 6, 6, 7 }));\r
 425                         Assert.IsTrue(IC.eq(tree.RangeTo(7), new int[] { 1, 2, 2, 3, 4, 4, 5, 6, 6 }));\r
 426                         Assert.AreEqual(9, tree.RangeTo(7).Count);\r
 427                         Assert.IsTrue(IC.eq(tree.RangeTo(1), new int[] { }));\r
 428                         Assert.IsTrue(IC.eq(tree.RangeTo(0), new int[] {  }));\r
 429                         Assert.IsTrue(IC.eq(tree.RangeTo(3), new int[] { 1, 2,2 }));\r
 430                         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
 431                         Assert.IsTrue(IC.eq(tree.RangeTo(21), all));\r
 432                         Assert.IsTrue(IC.eq(tree.RangeFromTo(7, 12), new int[] { 7, 8, 8, 9, 10, 10 }));\r
 433                         Assert.IsTrue(IC.eq(tree.RangeFromTo(6, 11), new int[] { 6, 6, 7, 8, 8, 9, 10, 10 }));\r
 434                         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
 435                         Assert.AreEqual(15, tree.RangeFromTo(1, 12).Count);\r
 436                         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
 437                         Assert.IsTrue(IC.eq(tree.RangeFromTo(6, 21), new int[] { 6, 6, 7, 8, 8, 9, 10, 10, 12, 14, 16, 18, 20 }));\r
 438                         Assert.IsTrue(IC.eq(tree.RangeFromTo(6, 20), new int[] { 6, 6, 7, 8, 8, 9, 10, 10, 12, 14, 16, 18 }));\r
 439                 }\r
 440 \r
 441 \r
 442                 [Test]\r
 443                 public void Backwards()\r
 444                 {\r
 445                         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
 446                         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
 447 \r
 448                         Assert.IsTrue(IC.eq(tree, all));\r
 449                         Assert.IsTrue(IC.eq(tree.RangeAll().Backwards(), lla));\r
 450                         Assert.IsTrue(IC.eq(tree.RangeFrom(11).Backwards(), new int[] { 20, 18, 16, 14, 12 }));\r
 451                         Assert.IsTrue(IC.eq(tree.RangeFrom(12).Backwards(), new int[] { 20, 18, 16, 14, 12 }));\r
 452                         Assert.IsTrue(IC.eq(tree.RangeFrom(1).Backwards(), lla));\r
 453                         Assert.IsTrue(IC.eq(tree.RangeFrom(0).Backwards(), lla));\r
 454                         Assert.IsTrue(IC.eq(tree.RangeFrom(21).Backwards(), new int[] { }));\r
 455                         Assert.IsTrue(IC.eq(tree.RangeFrom(20).Backwards(), new int[] { 20 }));\r
 456                         Assert.IsTrue(IC.eq(tree.RangeTo(8).Backwards(), new int[] { 7, 6, 6, 5, 4, 4, 3, 2, 2, 1 }));\r
 457                         Assert.IsTrue(IC.eq(tree.RangeTo(7).Backwards(), new int[] { 6, 6, 5, 4, 4, 3, 2, 2, 1 }));\r
 458                         Assert.IsTrue(IC.eq(tree.RangeTo(1).Backwards(), new int[] { }));\r
 459                         Assert.IsTrue(IC.eq(tree.RangeTo(0).Backwards(), new int[] {  }));\r
 460                         Assert.IsTrue(IC.eq(tree.RangeTo(3).Backwards(), new int[] { 2, 2, 1 }));\r
 461                         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
 462                         Assert.IsTrue(IC.eq(tree.RangeTo(21).Backwards(), lla));\r
 463                         Assert.IsTrue(IC.eq(tree.RangeFromTo(7, 12).Backwards(), new int[] { 10, 10, 9, 8, 8, 7 }));\r
 464                         Assert.IsTrue(IC.eq(tree.RangeFromTo(6, 11).Backwards(), new int[] { 10, 10, 9, 8, 8, 7, 6, 6 }));\r
 465                         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
 466                         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
 467                         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
 468                         Assert.IsTrue(IC.eq(tree.RangeFromTo(6, 20).Backwards(), new int[] { 18, 16, 14, 12, 10, 10, 9, 8, 8, 7, 6, 6 }));\r
 469                 }\r
 470 \r
 471 \r
 472                 [Test]\r
 473                 public void Direction()\r
 474                 {\r
 475                         Assert.AreEqual(EnumerationDirection.Forwards, tree.Direction);\r
 476                         Assert.AreEqual(EnumerationDirection.Forwards, tree.RangeFrom(20).Direction);\r
 477                         Assert.AreEqual(EnumerationDirection.Forwards, tree.RangeTo(7).Direction);\r
 478                         Assert.AreEqual(EnumerationDirection.Forwards, tree.RangeFromTo(1, 12).Direction);\r
 479                         Assert.AreEqual(EnumerationDirection.Forwards, tree.RangeAll().Direction);\r
 480                         Assert.AreEqual(EnumerationDirection.Backwards, tree.Backwards().Direction);\r
 481                         Assert.AreEqual(EnumerationDirection.Backwards, tree.RangeFrom(20).Backwards().Direction);\r
 482                         Assert.AreEqual(EnumerationDirection.Backwards, tree.RangeTo(7).Backwards().Direction);\r
 483                         Assert.AreEqual(EnumerationDirection.Backwards, tree.RangeFromTo(1, 12).Backwards().Direction);\r
 484                         Assert.AreEqual(EnumerationDirection.Backwards, tree.RangeAll().Backwards().Direction);\r
 485                 }\r
 486 \r
 487 \r
 488                 [TearDown]\r
 489                 public void Dispose()\r
 490                 {\r
 491                         tree = null;\r
 492                         c = null;\r
 493                 }\r
 494         }\r
 495 \r
 496 \r
 497 \r
 498         [TestFixture]\r
 499         public class BagItf\r
 500         {\r
 501                 private TreeBag<int> tree;\r
 502 \r
 503 \r
 504                 [SetUp]\r
 505                 public void Init()\r
 506                 {\r
 507                         tree = new TreeBag<int>(new IC());\r
 508                         for (int i = 10; i < 20; i++)\r
 509                         {\r
 510                                 tree.Add(i);\r
 511                                 tree.Add(i + 5);\r
 512                         }\r
 513                 }\r
 514 \r
 515 \r
 516                 [Test]\r
 517                 public void Both()\r
 518                 {\r
 519                         Assert.AreEqual(0, tree.ContainsCount(7));\r
 520                         Assert.AreEqual(1, tree.ContainsCount(10));\r
 521                         Assert.AreEqual(2, tree.ContainsCount(17));\r
 522                         tree.RemoveAllCopies(17);\r
 523                         Assert.AreEqual(0, tree.ContainsCount(17));\r
 524                         tree.RemoveAllCopies(7);\r
 525                 }\r
 526 \r
 527 \r
 528                 [TearDown]\r
 529                 public void Dispose()\r
 530                 {\r
 531                         tree = null;\r
 532                 }\r
 533         }\r
 534 \r
 535 \r
 536 \r
 537         [TestFixture]\r
 538         public class Div\r
 539         {\r
 540                 private TreeBag<int> tree;\r
 541 \r
 542 \r
 543                 [SetUp]\r
 544                 public void Init()\r
 545                 {\r
 546                         tree = new TreeBag<int>(new IC());\r
 547                 }\r
 548 \r
 549 \r
 550                 private void loadup()\r
 551                 {\r
 552                         for (int i = 10; i < 20; i++)\r
 553                         {\r
 554                                 tree.Add(i);\r
 555                                 tree.Add(i + 5);\r
 556                         }\r
 557                 }\r
 558 \r
 559 \r
 560                 [Test]\r
 561                 public void NoDuplicates()\r
 562                 {\r
 563             Assert.IsTrue(tree.AllowsDuplicates);\r
 564             loadup();\r
 565             Assert.IsTrue(tree.AllowsDuplicates);\r
 566         }\r
 567 \r
 568 \r
 569                 [Test]\r
 570                 public void Add()\r
 571                 {\r
 572                         Assert.IsTrue(tree.Add(17));\r
 573                         Assert.IsTrue(tree.Add(17));\r
 574                         Assert.IsTrue(tree.Add(18));\r
 575                         Assert.IsTrue(tree.Add(18));\r
 576                         Assert.AreEqual(4, tree.Count);\r
 577                         Assert.IsTrue(IC.eq(tree, 17, 17, 18, 18));\r
 578                 }\r
 579 \r
 580 \r
 581                 [TearDown]\r
 582                 public void Dispose()\r
 583                 {\r
 584                         tree = null;\r
 585                 }\r
 586         }\r
 587 \r
 588 \r
 589 \r
 590         [TestFixture]\r
 591         public class ArrayTest\r
 592         {\r
 593                 private TreeBag<int> tree;\r
 594 \r
 595                 int[] a;\r
 596 \r
 597 \r
 598                 [SetUp]\r
 599                 public void Init()\r
 600                 {\r
 601                         tree = new TreeBag<int>(new IC());\r
 602                         a = new int[10];\r
 603                         for (int i = 0; i < 10; i++)\r
 604                                 a[i] = 1000 + i;\r
 605                 }\r
 606 \r
 607 \r
 608                 [TearDown]\r
 609                 public void Dispose() { tree = null; }\r
 610 \r
 611 \r
 612                 private string aeq(int[] a, params int[] b)\r
 613                 {\r
 614                         if (a.Length != b.Length)\r
 615                                 return "Lengths differ: " + a.Length + " != " + b.Length;\r
 616 \r
 617                         for (int i = 0; i < a.Length; i++)\r
 618                                 if (a[i] != b[i])\r
 619                                         return String.Format("{0}'th elements differ: {1} != {2}", i, a[i], b[i]);\r
 620 \r
 621                         return "Alles klar";\r
 622                 }\r
 623 \r
 624 \r
 625                 [Test]\r
 626                 public void ToArray()\r
 627                 {\r
 628                         Assert.AreEqual("Alles klar", aeq(tree.ToArray()));\r
 629                         tree.Add(4);\r
 630                         tree.Add(7);\r
 631                         tree.Add(4);\r
 632                         Assert.AreEqual("Alles klar", aeq(tree.ToArray(), 4, 4, 7));\r
 633                 }\r
 634 \r
 635 \r
 636                 [Test]\r
 637                 public void CopyTo()\r
 638                 {\r
 639                         tree.CopyTo(a, 1);\r
 640                         Assert.AreEqual("Alles klar", aeq(a, 1000, 1001, 1002, 1003, 1004, 1005, 1006, 1007, 1008, 1009));\r
 641                         tree.Add(6);\r
 642                         tree.Add(6);\r
 643                         tree.CopyTo(a, 2);\r
 644                         Assert.AreEqual("Alles klar", aeq(a, 1000, 1001, 6, 6, 1004, 1005, 1006, 1007, 1008, 1009));\r
 645                         tree.Add(4);\r
 646                         tree.Add(9);\r
 647                         tree.CopyTo(a, 4);\r
 648                         Assert.AreEqual("Alles klar", aeq(a, 1000, 1001, 6, 6, 4, 6, 6, 9, 1008, 1009));\r
 649                         tree.Clear();\r
 650                         tree.Add(7);\r
 651                         tree.CopyTo(a, 9);\r
 652                         Assert.AreEqual("Alles klar", aeq(a, 1000, 1001, 6, 6, 4, 6, 6, 9, 1008, 7));\r
 653                 }\r
 654 \r
 655 \r
 656                 [Test]\r
 657                 [ExpectedException(typeof(ArgumentException))]\r
 658                 public void CopyToBad()\r
 659                 {\r
 660                         tree.Add(3);\r
 661                         tree.CopyTo(a, 10);\r
 662                 }\r
 663 \r
 664 \r
 665                 [Test]\r
 666                 [ExpectedException(typeof(ArgumentOutOfRangeException))]\r
 667                 public void CopyToBad2()\r
 668                 {\r
 669                         tree.CopyTo(a, -1);\r
 670                 }\r
 671 \r
 672 \r
 673                 [Test]\r
 674                 [ExpectedException(typeof(ArgumentException))]\r
 675                 public void CopyToTooFar()\r
 676                 {\r
 677                         tree.Add(3);\r
 678                         tree.Add(4);\r
 679                         tree.CopyTo(a, 9);\r
 680                 }\r
 681         }\r
 682 \r
 683 \r
 684 \r
 685         [TestFixture]\r
 686         public class Remove\r
 687         {\r
 688                 private TreeBag<int> tree;\r
 689 \r
 690 \r
 691                 [SetUp]\r
 692                 public void Init()\r
 693                 {\r
 694                         tree = new TreeBag<int>(new IC());\r
 695                         for (int i = 10; i < 20; i++)\r
 696                         {\r
 697                                 tree.Add(i);\r
 698                                 tree.Add(i + 5);\r
 699                         }\r
 700                         //10,11,12,13,14,15,15,16,16,17,17,18,18,19,19,20,21,22,23,24\r
 701                 }\r
 702 \r
 703 \r
 704                 [Test]\r
 705                 public void SmallTrees()\r
 706                 {\r
 707                         tree.Clear();\r
 708                         tree.Add(9);\r
 709                         tree.Add(7);\r
 710                         tree.Add(9);\r
 711                         Assert.IsTrue(tree.Remove(7));\r
 712                         Assert.IsTrue(tree.Check(""));\r
 713                 }\r
 714 \r
 715 \r
 716                 [Test]\r
 717                 public void ByIndex()\r
 718                 {\r
 719                         //Remove root!\r
 720                         int n = tree.Count;\r
 721                         int i = tree[10];\r
 722 \r
 723                         Assert.AreEqual(17,tree.RemoveAt(10));\r
 724                         Assert.IsTrue(tree.Check(""));\r
 725                         Assert.IsTrue(tree.Contains(i));\r
 726                         Assert.AreEqual(n - 1, tree.Count);\r
 727                         Assert.AreEqual(17, tree.RemoveAt(9));\r
 728                         Assert.IsTrue(tree.Check(""));\r
 729                         Assert.IsFalse(tree.Contains(i));\r
 730                         Assert.AreEqual(n - 2, tree.Count);\r
 731 \r
 732                         //Low end\r
 733                         i = tree.FindMin();\r
 734                         tree.RemoveAt(0);\r
 735                         Assert.IsTrue(tree.Check(""));\r
 736                         Assert.IsFalse(tree.Contains(i));\r
 737                         Assert.AreEqual(n - 3, tree.Count);\r
 738 \r
 739                         //high end\r
 740                         i = tree.FindMax();\r
 741                         tree.RemoveAt(tree.Count - 1);\r
 742                         Assert.IsTrue(tree.Check(""));\r
 743                         Assert.IsFalse(tree.Contains(i));\r
 744                         Assert.AreEqual(n - 4, tree.Count);\r
 745 \r
 746                         //Some leaf\r
 747                         //tree.dump();\r
 748                         i = 18;\r
 749                         Assert.AreEqual(i, tree.RemoveAt(9));\r
 750                         Assert.IsTrue(tree.Check(""));\r
 751                         Assert.AreEqual(i, tree.RemoveAt(8));\r
 752                         Assert.IsTrue(tree.Check(""));\r
 753                         Assert.IsFalse(tree.Contains(i));\r
 754                         Assert.AreEqual(n - 6, tree.Count);\r
 755                 }\r
 756 \r
 757 \r
 758                 [Test]\r
 759                 public void AlmostEmpty()\r
 760                 {\r
 761                         //Almost empty\r
 762                         tree.Clear();\r
 763                         tree.Add(3);\r
 764                         tree.RemoveAt(0);\r
 765                         Assert.IsTrue(tree.Check(""));\r
 766                         Assert.IsFalse(tree.Contains(3));\r
 767                         Assert.AreEqual(0, tree.Count);\r
 768                 }\r
 769 \r
 770 \r
 771                 [Test]\r
 772                 [ExpectedException(typeof(IndexOutOfRangeException), "Index out of range for sequenced collection")]\r
 773                 public void Empty()\r
 774                 {\r
 775                         tree.Clear();\r
 776                         tree.RemoveAt(0);\r
 777                 }\r
 778 \r
 779 \r
 780                 [Test]\r
 781                 [ExpectedException(typeof(IndexOutOfRangeException), "Index out of range for sequenced collection")]\r
 782                 public void HighIndex()\r
 783                 {\r
 784                         tree.RemoveAt(tree.Count);\r
 785                 }\r
 786 \r
 787 \r
 788                 [Test]\r
 789                 [ExpectedException(typeof(IndexOutOfRangeException), "Index out of range for sequenced collection")]\r
 790                 public void LowIndex()\r
 791                 {\r
 792                         tree.RemoveAt(-1);\r
 793                 }\r
 794 \r
 795 \r
 796                 [Test]\r
 797                 public void Normal()\r
 798                 {\r
 799                         //Note: ids does not match for bag\r
 800                         Assert.IsFalse(tree.Remove(-20));\r
 801 \r
 802                         //1b\r
 803                         Assert.IsTrue(tree.Remove(20));\r
 804                         Assert.IsTrue(tree.Check("T1"));\r
 805                         Assert.IsFalse(tree.Remove(20));\r
 806 \r
 807                         //1b\r
 808                         Assert.IsTrue(tree.Remove(10));\r
 809                         Assert.IsTrue(tree.Check("Normal test 1"), "Bad tree");\r
 810 \r
 811                         //case 1c\r
 812                         Assert.IsTrue(tree.Remove(24));\r
 813                         Assert.IsTrue(tree.Check("Normal test 1"), "Bad tree");\r
 814 \r
 815                         //1a (terminating)\r
 816                         Assert.IsTrue(tree.Remove(16));\r
 817                         Assert.IsTrue(tree.Remove(16));\r
 818                         Assert.IsTrue(tree.Check("Normal test 1"), "Bad tree");\r
 819 \r
 820                         //2\r
 821                         Assert.IsTrue(tree.Remove(18));\r
 822                         Assert.IsTrue(tree.Remove(17));\r
 823                         Assert.IsTrue(tree.Remove(18));\r
 824                         Assert.IsTrue(tree.Remove(17));\r
 825                         Assert.IsTrue(tree.Check("Normal test 1"), "Bad tree");\r
 826 \r
 827                         //2+1b\r
 828                         Assert.IsTrue(tree.Remove(15));\r
 829                         Assert.IsTrue(tree.Remove(15));\r
 830                         for (int i = 0; i < 5; i++) tree.Add(17 + i);\r
 831                         Assert.IsTrue(tree.Remove(23));\r
 832                         Assert.IsTrue(tree.Check("Normal test 1"), "Bad tree");\r
 833 \r
 834                         //1a+1b\r
 835                         Assert.IsTrue(tree.Remove(11));\r
 836                         Assert.IsTrue(tree.Check("Normal test 1"), "Bad tree");\r
 837 \r
 838                         //2+1c\r
 839                         for (int i = 0; i < 10; i++)\r
 840                                 tree.Add(50 - 2 * i);\r
 841 \r
 842                         Assert.IsTrue(tree.Remove(42));\r
 843                         Assert.IsTrue(tree.Remove(38));\r
 844                         Assert.IsTrue(tree.Remove(22));\r
 845                         Assert.IsTrue(tree.Remove(40));\r
 846 \r
 847                         //\r
 848                         for (int i = 0; i < 48; i++)\r
 849                                 tree.Remove(i);\r
 850 \r
 851                         //Almost empty tree:*\r
 852                         Assert.IsFalse(tree.Remove(26));\r
 853                         Assert.IsTrue(tree.Remove(48));\r
 854                         Assert.IsTrue(tree.Check("Normal test 1"), "Bad tree");\r
 855 \r
 856                         //Empty tree:*\r
 857                         Assert.IsFalse(tree.Remove(26));\r
 858                         Assert.IsTrue(tree.Check("Normal test 1"), "Bad tree");\r
 859                 }\r
 860 \r
 861 \r
 862                 [TearDown]\r
 863                 public void Dispose()\r
 864                 {\r
 865                         tree = null;\r
 866                 }\r
 867         }\r
 868 \r
 869 \r
 870 \r
 871         [TestFixture]\r
 872         public class PredecessorStructure\r
 873         {\r
 874                 private TreeBag<int> tree;\r
 875 \r
 876 \r
 877                 [SetUp]\r
 878                 public void Init()\r
 879                 {\r
 880                         tree = new TreeBag<int>(new IC());\r
 881                 }\r
 882 \r
 883 \r
 884                 private void loadup()\r
 885                 {\r
 886                         for (int i = 0; i < 20; i++) \r
 887                                 tree.Add(2 * i);\r
 888                         for (int i = 0; i < 10; i++)\r
 889                                 tree.Add(4 * i);\r
 890                 }\r
 891 \r
 892 \r
 893                 [Test]\r
 894                 public void Predecessor()\r
 895                 {\r
 896                         loadup();\r
 897                         Assert.AreEqual(6, tree.Predecessor(7));\r
 898                         Assert.AreEqual(6, tree.Predecessor(8));\r
 899 \r
 900                         //The bottom\r
 901                         Assert.AreEqual(0, tree.Predecessor(1));\r
 902 \r
 903                         //The top\r
 904                         Assert.AreEqual(38, tree.Predecessor(39));\r
 905                 }\r
 906 \r
 907 \r
 908                 [Test]\r
 909                 [ExpectedException(typeof(ArgumentOutOfRangeException))]\r
 910                 public void PredecessorTooLow1()\r
 911                 {\r
 912                         tree.Predecessor(-2);\r
 913                 }\r
 914 \r
 915 \r
 916                 [Test]\r
 917                 [ExpectedException(typeof(ArgumentOutOfRangeException))]\r
 918                 public void PredecessorTooLow2()\r
 919                 {\r
 920                         tree.Predecessor(0);\r
 921                 }\r
 922 \r
 923 \r
 924                 [Test]\r
 925                 public void WeakPredecessor()\r
 926                 {\r
 927                         loadup();\r
 928                         Assert.AreEqual(6, tree.WeakPredecessor(7));\r
 929                         Assert.AreEqual(8, tree.WeakPredecessor(8));\r
 930 \r
 931                         //The bottom\r
 932                         Assert.AreEqual(0, tree.WeakPredecessor(1));\r
 933                         Assert.AreEqual(0, tree.WeakPredecessor(0));\r
 934 \r
 935                         //The top\r
 936                         Assert.AreEqual(38, tree.WeakPredecessor(39));\r
 937                         Assert.AreEqual(38, tree.WeakPredecessor(38));\r
 938                 }\r
 939 \r
 940 \r
 941                 [Test]\r
 942                 [ExpectedException(typeof(ArgumentOutOfRangeException))]\r
 943                 public void WeakPredecessorTooLow1()\r
 944                 {\r
 945                         tree.WeakPredecessor(-2);\r
 946                 }\r
 947 \r
 948 \r
 949                 [Test]\r
 950                 public void Successor()\r
 951                 {\r
 952                         loadup();\r
 953                         Assert.AreEqual(8, tree.Successor(7));\r
 954                         Assert.AreEqual(10, tree.Successor(8));\r
 955 \r
 956                         //The bottom\r
 957                         Assert.AreEqual(2, tree.Successor(0));\r
 958                         Assert.AreEqual(0, tree.Successor(-1));\r
 959 \r
 960                         //The top\r
 961                         Assert.AreEqual(38, tree.Successor(37));\r
 962                 }\r
 963 \r
 964 \r
 965                 [Test]\r
 966                 [ExpectedException(typeof(ArgumentOutOfRangeException))]\r
 967                 public void SuccessorTooHigh1()\r
 968                 {\r
 969                         tree.Successor(38);\r
 970                 }\r
 971 \r
 972 \r
 973                 [Test]\r
 974                 [ExpectedException(typeof(ArgumentOutOfRangeException))]\r
 975                 public void SuccessorTooHigh2()\r
 976                 {\r
 977                         tree.Successor(39);\r
 978                 }\r
 979 \r
 980 \r
 981                 [Test]\r
 982                 public void WeakSuccessor()\r
 983                 {\r
 984                         loadup();\r
 985                         Assert.AreEqual(6, tree.WeakSuccessor(6));\r
 986                         Assert.AreEqual(8, tree.WeakSuccessor(7));\r
 987 \r
 988                         //The bottom\r
 989                         Assert.AreEqual(0, tree.WeakSuccessor(-1));\r
 990                         Assert.AreEqual(0, tree.WeakSuccessor(0));\r
 991 \r
 992                         //The top\r
 993                         Assert.AreEqual(38, tree.WeakSuccessor(37));\r
 994                         Assert.AreEqual(38, tree.WeakSuccessor(38));\r
 995                 }\r
 996 \r
 997 \r
 998                 [Test]\r
 999                 [ExpectedException(typeof(ArgumentOutOfRangeException))]\r
1000                 public void WeakSuccessorTooHigh1()\r
1001                 {\r
1002                         tree.WeakSuccessor(39);\r
1003                 }\r
1004 \r
1005 \r
1006                 [TearDown]\r
1007                 public void Dispose()\r
1008                 {\r
1009                         tree = null;\r
1010                 }\r
1011         }\r
1012 \r
1013 \r
1014 \r
1015         [TestFixture]\r
1016         public class PriorityQueue\r
1017         {\r
1018                 private TreeBag<int> tree;\r
1019 \r
1020 \r
1021                 [SetUp]\r
1022                 public void Init()\r
1023                 {\r
1024                         tree = new TreeBag<int>(new IC());\r
1025                 }\r
1026 \r
1027 \r
1028                 private void loadup()\r
1029                 {\r
1030                         foreach (int i in new int[] { 1, 2, 3, 4 })\r
1031                                 tree.Add(i);\r
1032                         tree.Add(1);\r
1033                         tree.Add(3);\r
1034                 }\r
1035 \r
1036 \r
1037                 [Test]\r
1038                 public void Normal()\r
1039                 {\r
1040                         loadup();\r
1041                         Assert.AreEqual(1, tree.FindMin());\r
1042                         Assert.AreEqual(4, tree.FindMax());\r
1043                         Assert.AreEqual(1, tree.DeleteMin());\r
1044                         Assert.AreEqual(4, tree.DeleteMax());\r
1045                         Assert.IsTrue(tree.Check("Normal test 1"), "Bad tree");\r
1046                         Assert.AreEqual(1, tree.FindMin());\r
1047                         Assert.AreEqual(3, tree.FindMax());\r
1048                         Assert.AreEqual(1, tree.DeleteMin());\r
1049                         Assert.AreEqual(3, tree.DeleteMax());\r
1050                         Assert.IsTrue(tree.Check("Normal test 2"), "Bad tree");\r
1051                 }\r
1052 \r
1053 \r
1054                 [Test]\r
1055                 [ExpectedException(typeof(InvalidOperationException), "Priority queue is empty")]\r
1056                 public void Empty1()\r
1057                 {\r
1058                         tree.FindMin();\r
1059                 }\r
1060 \r
1061 \r
1062                 [Test]\r
1063                 [ExpectedException(typeof(InvalidOperationException), "Priority queue is empty")]\r
1064                 public void Empty2()\r
1065                 {\r
1066                         tree.FindMax();\r
1067                 }\r
1068 \r
1069 \r
1070                 [Test]\r
1071                 [ExpectedException(typeof(InvalidOperationException), "Priority queue is empty")]\r
1072                 public void Empty3()\r
1073                 {\r
1074                         tree.DeleteMin();\r
1075                 }\r
1076 \r
1077 \r
1078                 [Test]\r
1079                 [ExpectedException(typeof(InvalidOperationException), "Priority queue is empty")]\r
1080                 public void Empty4()\r
1081                 {\r
1082                         tree.DeleteMax();\r
1083                 }\r
1084 \r
1085 \r
1086                 [TearDown]\r
1087                 public void Dispose()\r
1088                 {\r
1089                         tree = null;\r
1090                 }\r
1091         }\r
1092 \r
1093 \r
1094 \r
1095         [TestFixture]\r
1096         public class IndexingAndCounting\r
1097         {\r
1098                 private TreeBag<int> tree;\r
1099 \r
1100 \r
1101                 [SetUp]\r
1102                 public void Init()\r
1103                 {\r
1104                         tree = new TreeBag<int>(new IC());\r
1105                 }\r
1106 \r
1107 \r
1108                 private void populate()\r
1109                 {\r
1110                         tree.Add(30);\r
1111                         tree.Add(30);\r
1112                         tree.Add(50);\r
1113                         tree.Add(10);\r
1114                         tree.Add(70);\r
1115                         tree.Add(70);\r
1116                 }\r
1117 \r
1118 \r
1119                 [Test]\r
1120                 public void ToArray()\r
1121                 {\r
1122                         populate();\r
1123 \r
1124                         int[] a = tree.ToArray();\r
1125 \r
1126                         Assert.AreEqual(6, a.Length);\r
1127                         Assert.AreEqual(10, a[0]);\r
1128                         Assert.AreEqual(30, a[1]);\r
1129                         Assert.AreEqual(30, a[2]);\r
1130                         Assert.AreEqual(50, a[3]);\r
1131                         Assert.AreEqual(70, a[4]);\r
1132                         Assert.AreEqual(70, a[5]);\r
1133                 }\r
1134 \r
1135 \r
1136                 [Test]\r
1137                 public void GoodIndex()\r
1138                 {\r
1139                         Assert.AreEqual(-1, tree.IndexOf(20));\r
1140                         Assert.AreEqual(-1, tree.LastIndexOf(20));\r
1141                         populate();\r
1142                         Assert.AreEqual(10, tree[0]);\r
1143                         Assert.AreEqual(30, tree[1]);\r
1144                         Assert.AreEqual(30, tree[2]);\r
1145                         Assert.AreEqual(50, tree[3]);\r
1146                         Assert.AreEqual(70, tree[4]);\r
1147                         Assert.AreEqual(70, tree[5]);\r
1148                         Assert.AreEqual(0, tree.IndexOf(10));\r
1149                         Assert.AreEqual(1, tree.IndexOf(30));\r
1150                         Assert.AreEqual(3, tree.IndexOf(50));\r
1151                         Assert.AreEqual(4, tree.IndexOf(70));\r
1152                         Assert.AreEqual(-1, tree.IndexOf(20));\r
1153                         Assert.AreEqual(-1, tree.IndexOf(0));\r
1154                         Assert.AreEqual(-1, tree.IndexOf(90));\r
1155                         Assert.AreEqual(0, tree.LastIndexOf(10));\r
1156                         Assert.AreEqual(2, tree.LastIndexOf(30));\r
1157                         Assert.AreEqual(3, tree.LastIndexOf(50));\r
1158                         Assert.AreEqual(5, tree.LastIndexOf(70));\r
1159                         Assert.AreEqual(-1, tree.LastIndexOf(20));\r
1160                         Assert.AreEqual(-1, tree.LastIndexOf(0));\r
1161                         Assert.AreEqual(-1, tree.LastIndexOf(90));\r
1162                 }\r
1163 \r
1164 \r
1165                 [Test]\r
1166                 [ExpectedException(typeof(IndexOutOfRangeException))]\r
1167                 public void IndexTooLarge()\r
1168                 {\r
1169                         populate();\r
1170                         Console.WriteLine(tree[6]);\r
1171                 }\r
1172 \r
1173 \r
1174                 [Test]\r
1175                 [ExpectedException(typeof(IndexOutOfRangeException))]\r
1176                 public void IndexTooSmall()\r
1177                 {\r
1178                         populate();\r
1179                         Console.WriteLine(tree[-1]);\r
1180                 }\r
1181 \r
1182 \r
1183                 [Test]\r
1184                 public void FilledTreeOutsideInput()\r
1185                 {\r
1186                         populate();\r
1187                         Assert.AreEqual(0, tree.CountFrom(90));\r
1188                         Assert.AreEqual(0, tree.CountFromTo(-20, 0));\r
1189                         Assert.AreEqual(0, tree.CountFromTo(80, 100));\r
1190                         Assert.AreEqual(0, tree.CountTo(0));\r
1191                         Assert.AreEqual(6, tree.CountTo(90));\r
1192                         Assert.AreEqual(6, tree.CountFromTo(-20, 90));\r
1193                         Assert.AreEqual(6, tree.CountFrom(0));\r
1194                 }\r
1195 \r
1196 \r
1197                 [Test]\r
1198                 public void FilledTreeIntermediateInput()\r
1199                 {\r
1200                         populate();\r
1201                         Assert.AreEqual(5, tree.CountFrom(20));\r
1202                         Assert.AreEqual(2, tree.CountFromTo(20, 40));\r
1203                         Assert.AreEqual(3, tree.CountTo(40));\r
1204                 }\r
1205 \r
1206 \r
1207                 [Test]\r
1208                 public void FilledTreeMatchingInput()\r
1209                 {\r
1210                         populate();\r
1211                         Assert.AreEqual(5, tree.CountFrom(30));\r
1212                         Assert.AreEqual(3, tree.CountFromTo(30, 70));\r
1213                         Assert.AreEqual(0, tree.CountFromTo(50, 30));\r
1214                         Assert.AreEqual(0, tree.CountFromTo(50, 50));\r
1215                         Assert.AreEqual(0, tree.CountTo(10));\r
1216                         Assert.AreEqual(3, tree.CountTo(50));\r
1217                 }\r
1218 \r
1219 \r
1220                 [Test]\r
1221                 public void CountEmptyTree()\r
1222                 {\r
1223                         Assert.AreEqual(0, tree.CountFrom(20));\r
1224                         Assert.AreEqual(0, tree.CountFromTo(20, 40));\r
1225                         Assert.AreEqual(0, tree.CountTo(40));\r
1226                 }\r
1227 \r
1228 \r
1229                 [TearDown]\r
1230                 public void Dispose()\r
1231                 {\r
1232                         tree = null;\r
1233                 }\r
1234         }\r
1235 \r
1236 \r
1237 \r
1238 \r
1239         namespace ModificationCheck\r
1240         {\r
1241                 [TestFixture]\r
1242                 public class Enumerator\r
1243                 {\r
1244                         private TreeBag<int> tree;\r
1245 \r
1246                         private MSG.IEnumerator<int> e;\r
1247 \r
1248 \r
1249                         [SetUp]\r
1250                         public void Init()\r
1251                         {\r
1252                                 tree = new TreeBag<int>(new IC());\r
1253                                 for (int i = 0; i < 10; i++)\r
1254                                         tree.Add(i);\r
1255                                 tree.Add(3); \r
1256                                 tree.Add(7);\r
1257                                 e = tree.GetEnumerator();\r
1258                         }\r
1259 \r
1260 \r
1261                         [Test]\r
1262                         public void CurrentAfterModification()\r
1263                         {\r
1264                                 e.MoveNext();\r
1265                                 tree.Add(34);\r
1266                                 Assert.AreEqual(0, e.Current);\r
1267                         }\r
1268 \r
1269 \r
1270                         [Test]\r
1271                         [ExpectedException(typeof(InvalidOperationException), "Collection was modified")]\r
1272                         public void MoveNextAfterAdd()\r
1273                         {\r
1274                                 tree.Add(34);\r
1275                                 e.MoveNext();\r
1276                         }\r
1277 \r
1278 \r
1279                         [Test]\r
1280                         [ExpectedException(typeof(InvalidOperationException), "Collection was modified")]\r
1281                         public void MoveNextAfterRemove()\r
1282                         {\r
1283                                 tree.Remove(34);\r
1284                                 e.MoveNext();\r
1285                         }\r
1286 \r
1287 \r
1288                         [Test]\r
1289                         [ExpectedException(typeof(InvalidOperationException), "Collection was modified")]\r
1290                         public void MoveNextAfterClear()\r
1291                         {\r
1292                                 tree.Clear();\r
1293                                 e.MoveNext();\r
1294                         }\r
1295 \r
1296 \r
1297                         [TearDown]\r
1298                         public void Dispose()\r
1299                         {\r
1300                                 tree = null;\r
1301                                 e = null;\r
1302                         }\r
1303                 }\r
1304 \r
1305 \r
1306 \r
1307                 [TestFixture]\r
1308                 public class RangeEnumerator\r
1309                 {\r
1310                         private TreeBag<int> tree;\r
1311 \r
1312                         private MSG.IEnumerator<int> e;\r
1313 \r
1314 \r
1315                         [SetUp]\r
1316                         public void Init()\r
1317                         {\r
1318                                 tree = new TreeBag<int>(new IC());\r
1319                                 for (int i = 0; i < 10; i++)\r
1320                                         tree.Add(i);\r
1321 \r
1322                                 e = tree.RangeFromTo(3, 7).GetEnumerator();\r
1323                         }\r
1324 \r
1325 \r
1326                         [Test]\r
1327                         public void CurrentAfterModification()\r
1328                         {\r
1329                                 e.MoveNext();\r
1330                                 tree.Add(34);\r
1331                                 Assert.AreEqual(3, e.Current);\r
1332                         }\r
1333 \r
1334 \r
1335                         [Test]\r
1336                         [ExpectedException(typeof(InvalidOperationException), "Collection was modified")]\r
1337                         public void MoveNextAfterAdd()\r
1338                         {\r
1339                                 tree.Add(34);\r
1340                                 e.MoveNext();\r
1341                         }\r
1342 \r
1343 \r
1344                         [Test]\r
1345                         [ExpectedException(typeof(InvalidOperationException), "Collection was modified")]\r
1346                         public void MoveNextAfterRemove()\r
1347                         {\r
1348                                 tree.Remove(34);\r
1349                                 e.MoveNext();\r
1350                         }\r
1351 \r
1352 \r
1353                         [Test]\r
1354                         [ExpectedException(typeof(InvalidOperationException), "Collection was modified")]\r
1355                         public void MoveNextAfterClear()\r
1356                         {\r
1357                                 tree.Clear();\r
1358                                 e.MoveNext();\r
1359                         }\r
1360 \r
1361 \r
1362                         [TearDown]\r
1363                         public void Dispose()\r
1364                         {\r
1365                                 tree = null;\r
1366                                 e = null;\r
1367                         }\r
1368                 }\r
1369         }\r
1370 \r
1371 \r
1372 \r
1373 \r
1374         namespace PathcopyPersistence\r
1375         {\r
1376                 [TestFixture]\r
1377                 public class Navigation\r
1378                 {\r
1379                         private TreeBag<int> tree, snap;\r
1380 \r
1381                         private IComparer<int> ic;\r
1382 \r
1383 \r
1384                         [SetUp]\r
1385                         public void Init()\r
1386                         {\r
1387                                 ic = new IC();\r
1388                                 tree = new TreeBag<int>(ic);\r
1389                                 for (int i = 0; i <= 20; i++)\r
1390                                         tree.Add(2 * i + 1);\r
1391                                 tree.Add(13);\r
1392                                 snap = (TreeBag<int>)tree.Snapshot();\r
1393                                 for (int i = 0; i <= 10; i++)\r
1394                                         tree.Remove(4 * i + 1);\r
1395                         }\r
1396 \r
1397 \r
1398                         private bool twomodeleven(int i)\r
1399                         {\r
1400                                 return i % 11 == 2;\r
1401                         }\r
1402 \r
1403 \r
1404                         [Test]\r
1405                         public void InternalEnum()\r
1406                         {\r
1407                                 Assert.IsTrue(IC.eq(snap.FindAll(new Filter<int>(twomodeleven)), 13, 13, 35));\r
1408                         }\r
1409 \r
1410 \r
1411                         public void MoreCut()\r
1412                         {\r
1413                                 //TODO: Assert.Fail("more tests of Cut needed");\r
1414                         }\r
1415 \r
1416 \r
1417                         [Test]\r
1418                         public void Cut()\r
1419                         {\r
1420                                 int lo, hi;\r
1421                                 bool lv, hv;\r
1422 \r
1423                                 Assert.IsFalse(snap.Cut(new HigherOrder.CubeRoot(64), out lo, out lv, out hi, out hv));\r
1424                                 Assert.IsTrue(lv && hv);\r
1425                                 Assert.AreEqual(5, hi);\r
1426                                 Assert.AreEqual(3, lo);\r
1427                                 Assert.IsTrue(snap.Cut(new HigherOrder.CubeRoot(125), out lo, out lv, out hi, out hv));\r
1428                                 Assert.IsTrue(lv && hv);\r
1429                                 Assert.AreEqual(7, hi);\r
1430                                 Assert.AreEqual(3, lo);\r
1431                                 Assert.IsFalse(snap.Cut(new HigherOrder.CubeRoot(125000), out lo, out lv, out hi, out hv));\r
1432                                 Assert.IsTrue(lv && !hv);\r
1433                                 Assert.AreEqual(41, lo);\r
1434                                 Assert.IsFalse(snap.Cut(new HigherOrder.CubeRoot(-27), out lo, out lv, out hi, out hv));\r
1435                                 Assert.IsTrue(!lv && hv);\r
1436                                 Assert.AreEqual(1, hi);\r
1437                         }\r
1438 \r
1439 \r
1440                         [Test]\r
1441                         public void Range()\r
1442                         {\r
1443                                 Assert.IsTrue(IC.eq(snap.RangeFromTo(5, 16), 5, 7, 9, 11,13,  13, 15));\r
1444                                 Assert.IsTrue(IC.eq(snap.RangeFromTo(5, 17), 5, 7, 9, 11,13,  13, 15));\r
1445                                 Assert.IsTrue(IC.eq(snap.RangeFromTo(6, 16), 7, 9, 11,13,  13, 15));\r
1446                         }\r
1447 \r
1448 \r
1449                         [Test]\r
1450                         public void Contains()\r
1451                         {\r
1452                                 Assert.IsTrue(snap.Contains(5));\r
1453                                 Assert.IsTrue(snap.Contains(13));\r
1454                                 Assert.AreEqual(1, snap.ContainsCount(5));\r
1455                                 Assert.AreEqual(2, snap.ContainsCount(13));\r
1456                         }\r
1457 \r
1458 \r
1459                         [Test]\r
1460                         public void FindMin()\r
1461                         {\r
1462                                 Assert.AreEqual(1, snap.FindMin());\r
1463                         }\r
1464 \r
1465 \r
1466                         [Test]\r
1467                         public void FindMax()\r
1468                         {\r
1469                                 Assert.AreEqual(41, snap.FindMax());\r
1470                         }\r
1471 \r
1472 \r
1473                         [Test]\r
1474                         public void Predecessor()\r
1475                         {\r
1476                                 Assert.AreEqual(13, snap.Predecessor(15));\r
1477                                 Assert.AreEqual(15, snap.Predecessor(16));\r
1478                                 Assert.AreEqual(15, snap.Predecessor(17));\r
1479                                 Assert.AreEqual(17, snap.Predecessor(18));\r
1480                         }\r
1481 \r
1482 \r
1483                         [Test]\r
1484                         public void Successor()\r
1485                         {\r
1486                                 Assert.AreEqual(17, snap.Successor(15));\r
1487                                 Assert.AreEqual(17, snap.Successor(16));\r
1488                                 Assert.AreEqual(19, snap.Successor(17));\r
1489                                 Assert.AreEqual(19, snap.Successor(18));\r
1490                         }\r
1491 \r
1492 \r
1493                         [Test]\r
1494                         public void WeakPredecessor()\r
1495                         {\r
1496                                 Assert.AreEqual(15, snap.WeakPredecessor(15));\r
1497                                 Assert.AreEqual(15, snap.WeakPredecessor(16));\r
1498                                 Assert.AreEqual(17, snap.WeakPredecessor(17));\r
1499                                 Assert.AreEqual(17, snap.WeakPredecessor(18));\r
1500                         }\r
1501 \r
1502 \r
1503                         [Test]\r
1504                         public void WeakSuccessor()\r
1505                         {\r
1506                                 Assert.AreEqual(15, snap.WeakSuccessor(15));\r
1507                                 Assert.AreEqual(17, snap.WeakSuccessor(16));\r
1508                                 Assert.AreEqual(17, snap.WeakSuccessor(17));\r
1509                                 Assert.AreEqual(19, snap.WeakSuccessor(18));\r
1510                         }\r
1511 \r
1512 \r
1513                         [Test]\r
1514                         [ExpectedException(typeof(NotSupportedException), "Indexing not supported for snapshots")]\r
1515                         public void CountTo()\r
1516                         {\r
1517                                 int j = snap.CountTo(15);\r
1518                         }\r
1519 \r
1520 \r
1521                         [Test]\r
1522                         [ExpectedException(typeof(NotSupportedException), "Indexing not supported for snapshots")]\r
1523                         public void Indexing()\r
1524                         {\r
1525                                 int j = snap[4];\r
1526                         }\r
1527 \r
1528 \r
1529                         [Test]\r
1530                         [ExpectedException(typeof(NotSupportedException), "Indexing not supported for snapshots")]\r
1531                         public void Indexing2()\r
1532                         {\r
1533                                 int j = snap.IndexOf(5);\r
1534                         }\r
1535 \r
1536 \r
1537                         [TearDown]\r
1538                         public void Dispose()\r
1539                         {\r
1540                                 tree = null;\r
1541                                 ic = null;\r
1542                         }\r
1543                 }\r
1544 \r
1545 \r
1546 \r
1547                 [TestFixture]\r
1548                 public class Single\r
1549                 {\r
1550                         private TreeBag<int> tree;\r
1551 \r
1552                         private IComparer<int> ic;\r
1553 \r
1554 \r
1555                         [SetUp]\r
1556                         public void Init()\r
1557                         {\r
1558                                 ic = new IC();\r
1559                                 tree = new TreeBag<int>(ic);\r
1560                                 for (int i = 0; i < 10; i++)\r
1561                                         tree.Add(2 * i + 1);\r
1562                         }\r
1563 \r
1564 \r
1565                         [Test]\r
1566                         public void EnumerationWithAdd()\r
1567                         {\r
1568                                 int[] orig = new int[] { 1, 3, 5, 7, 9, 11, 13, 15, 17, 19 };\r
1569                                 int i = 0;\r
1570                                 TreeBag<int> snap = (TreeBag<int>)tree.Snapshot();\r
1571 \r
1572                                 foreach (int j in snap)\r
1573                                 {\r
1574                                         Assert.AreEqual(1 + 2 * i++, j);\r
1575                                         tree.Add(21 - j);\r
1576                                         Assert.IsTrue(snap.Check("M"), "Bad snap!");\r
1577                                         Assert.IsTrue(IC.eq(snap, orig), "Snap was changed!");\r
1578                                         Assert.IsTrue(tree.Check("Tree"), "Bad tree!");\r
1579                                 }\r
1580                         }\r
1581 \r
1582 \r
1583                         [Test]\r
1584                         public void Remove()\r
1585                         {\r
1586                                 int[] orig = new int[] { 1, 3, 5, 7, 9, 11, 13, 15, 17, 19 };\r
1587                                 TreeBag<int> snap = (TreeBag<int>)tree.Snapshot();\r
1588 \r
1589                                 Assert.IsTrue(snap.Check("Snap"), "Bad snap!");\r
1590                                 Assert.IsTrue(IC.eq(snap, orig), "Snap was changed!");\r
1591                                 tree.Remove(19);\r
1592                                 Assert.IsTrue(snap.Check("Snap"), "Bad snap!");\r
1593                                 Assert.IsTrue(tree.Check("Tree"), "Bad tree!");\r
1594                                 Assert.IsTrue(IC.eq(snap, orig), "Snap was changed!");\r
1595                         }\r
1596 \r
1597 \r
1598                         [Test]\r
1599                         public void RemoveNormal()\r
1600                         {\r
1601                                 tree.Clear();\r
1602                                 for (int i = 10; i < 20; i++)\r
1603                                 {\r
1604                                         tree.Add(i);\r
1605                                         tree.Add(i + 10);\r
1606                                 }\r
1607                                 tree.Add(15);\r
1608 \r
1609                                 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
1610                                 TreeBag<int> snap = (TreeBag<int>)tree.Snapshot();\r
1611 \r
1612                                 Assert.IsFalse(tree.Remove(-20));\r
1613                                 Assert.IsTrue(snap.Check("Snap"), "Bad snap!");\r
1614                                 Assert.IsTrue(IC.eq(snap, orig), "Snap was changed!");\r
1615 \r
1616 \r
1617                                 //decrease items case\r
1618                                 Assert.IsTrue(tree.Remove(15));\r
1619                                 Assert.IsTrue(tree.Check("T1"));\r
1620                                 Assert.IsTrue(snap.Check("Snap"), "Bad snap!");\r
1621                                 //snap.dump();\r
1622                                 Assert.IsTrue(IC.eq(snap, orig), "Snap was changed!");\r
1623 \r
1624                                 //No demote case, with move_item\r
1625                                 Assert.IsTrue(tree.Remove(20));\r
1626                                 Assert.IsTrue(tree.Check("T1"));\r
1627                                 Assert.IsTrue(snap.Check("Snap"), "Bad snap!");\r
1628                                 Assert.IsTrue(IC.eq(snap, orig), "Snap was changed!");\r
1629                                 Assert.IsFalse(tree.Remove(20));\r
1630 \r
1631                                 //plain case 2\r
1632                                 tree.Snapshot();\r
1633                                 Assert.IsTrue(tree.Remove(14));\r
1634                                 Assert.IsTrue(tree.Check("Normal test 1"), "Bad tree");\r
1635                                 Assert.IsTrue(snap.Check("Snap"), "Bad snap!");\r
1636                                 Assert.IsTrue(IC.eq(snap, orig), "Snap was changed!");\r
1637 \r
1638                                 //case 1b\r
1639                                 Assert.IsTrue(tree.Remove(25));\r
1640                                 Assert.IsTrue(tree.Check("Normal test 1"), "Bad tree");\r
1641                                 Assert.IsTrue(snap.Check("Snap"), "Bad snap!");\r
1642                                 Assert.IsTrue(IC.eq(snap, orig), "Snap was changed!");\r
1643 \r
1644                                 //case 1c\r
1645                                 Assert.IsTrue(tree.Remove(29));\r
1646                                 Assert.IsTrue(tree.Check("Normal test 1"), "Bad tree");\r
1647                                 Assert.IsTrue(snap.Check("Snap"), "Bad snap!");\r
1648                                 Assert.IsTrue(IC.eq(snap, orig), "Snap was changed!");\r
1649 \r
1650                                 //1a (terminating)\r
1651                                 Assert.IsTrue(tree.Remove(10));\r
1652                                 Assert.IsTrue(tree.Check("Normal test 1"), "Bad tree");\r
1653                                 Assert.IsTrue(snap.Check("Snap"), "Bad snap!");\r
1654                                 Assert.IsTrue(IC.eq(snap, orig), "Snap was changed!");\r
1655 \r
1656                                 //2+1b\r
1657                                 Assert.IsTrue(tree.Remove(12));\r
1658                                 tree.Snapshot();\r
1659                                 Assert.IsTrue(tree.Remove(11));\r
1660                                 Assert.IsTrue(tree.Check("Normal test 1"), "Bad tree");\r
1661                                 Assert.IsTrue(snap.Check("Snap"), "Bad snap!");\r
1662                                 Assert.IsTrue(IC.eq(snap, orig), "Snap was changed!");\r
1663 \r
1664                                 //1a+1b\r
1665                                 Assert.IsTrue(tree.Remove(18));\r
1666                                 Assert.IsTrue(tree.Remove(13));\r
1667                                 Assert.IsTrue(tree.Remove(15));\r
1668                                 Assert.IsTrue(tree.Check("Normal test 1"), "Bad tree");\r
1669                                 Assert.IsTrue(snap.Check("Snap"), "Bad snap!");\r
1670                                 Assert.IsTrue(IC.eq(snap, orig), "Snap was changed!");\r
1671 \r
1672                                 //2+1c\r
1673                                 for (int i = 0; i < 10; i++)\r
1674                                         tree.Add(50 - 2 * i);\r
1675 \r
1676                                 Assert.IsTrue(tree.Remove(42));\r
1677                                 Assert.IsTrue(tree.Remove(38));\r
1678                                 Assert.IsTrue(tree.Remove(28));\r
1679                                 Assert.IsTrue(tree.Remove(40));\r
1680                                 Assert.IsTrue(tree.Check("Normal test 1"), "Bad tree");\r
1681                                 Assert.IsTrue(snap.Check("Snap"), "Bad snap!");\r
1682                                 Assert.IsTrue(IC.eq(snap, orig), "Snap was changed!");\r
1683 \r
1684                                 //\r
1685                                 Assert.IsTrue(tree.Remove(16));\r
1686                                 Assert.IsTrue(tree.Remove(23));\r
1687                                 Assert.IsTrue(tree.Remove(17));\r
1688                                 Assert.IsTrue(tree.Remove(19));\r
1689                                 Assert.IsTrue(tree.Remove(50));\r
1690                                 Assert.IsTrue(tree.Remove(26));\r
1691                                 Assert.IsTrue(tree.Remove(21));\r
1692                                 Assert.IsTrue(tree.Remove(22));\r
1693                                 Assert.IsTrue(tree.Remove(24));\r
1694                                 for (int i = 0; i < 48; i++)\r
1695                                         tree.Remove(i);\r
1696 \r
1697                                 //Almost empty tree:\r
1698                                 Assert.IsFalse(tree.Remove(26));\r
1699                                 Assert.IsTrue(tree.Remove(48));\r
1700                                 Assert.IsTrue(tree.Check("Normal test 1"), "Bad tree");\r
1701                                 Assert.IsTrue(snap.Check("Snap"), "Bad snap!");\r
1702                                 Assert.IsTrue(IC.eq(snap, orig), "Snap was changed!");\r
1703 \r
1704                                 //Empty tree:\r
1705                                 Assert.IsFalse(tree.Remove(26));\r
1706                                 Assert.IsTrue(tree.Check("Normal test 1"), "Bad tree");\r
1707                                 Assert.IsTrue(snap.Check("Snap"), "Bad snap!");\r
1708                                 Assert.IsTrue(IC.eq(snap, orig), "Snap was changed!");\r
1709                         }\r
1710 \r
1711 \r
1712                         [Test]\r
1713                         public void Add()\r
1714                         {\r
1715                                 int[] orig = new int[] { 1, 3, 5, 7, 9, 11, 13, 15, 17, 19 };\r
1716                                 TreeBag<int> snap = (TreeBag<int>)tree.Snapshot();\r
1717 \r
1718                                 Assert.IsTrue(snap.Check("M"), "Bad snap!");\r
1719                                 Assert.IsTrue(IC.eq(snap, orig), "Snap was changed!");\r
1720                                 Assert.IsTrue(tree.Check("Tree"), "Bad tree!");\r
1721                                 tree.Add(10);\r
1722                                 Assert.IsTrue(snap.Check("M"), "Bad snap!");\r
1723                                 Assert.IsTrue(IC.eq(snap, orig), "Snap was changed!");\r
1724                                 Assert.IsTrue(tree.Check("Tree"), "Bad tree!");\r
1725                                 tree.Add(16);\r
1726                                 Assert.IsTrue(snap.Check("M"), "Bad snap!");\r
1727                                 Assert.IsTrue(IC.eq(snap, orig), "Snap was changed!");\r
1728                                 Assert.IsTrue(tree.Check("Tree"), "Bad tree!");\r
1729 \r
1730                                 tree.Add(9);\r
1731                                 Assert.IsTrue(snap.Check("M"), "Bad snap!");\r
1732                                 Assert.IsTrue(tree.Check("Tree"), "Bad tree!");\r
1733                                 Assert.IsTrue(IC.eq(snap, orig), "Snap was changed!");\r
1734 \r
1735                                 //Promote+zigzig\r
1736                                 tree.Add(40);\r
1737                                 Assert.IsTrue(snap.Check("M"), "Bad snap!");\r
1738                                 Assert.IsTrue(tree.Check("Tree"), "Bad tree!");\r
1739                                 Assert.IsTrue(IC.eq(snap, orig), "Snap was changed!");\r
1740                                 for (int i = 1; i < 4; i++)\r
1741                                         tree.Add(40 - 2 * i);\r
1742 \r
1743                                 Assert.IsTrue(snap.Check("M"), "Bad snap!");\r
1744                                 Assert.IsTrue(IC.eq(snap, orig), "Snap was changed!");\r
1745                                 Assert.IsTrue(tree.Check("Tree"), "Bad tree!");\r
1746 \r
1747                                 //Zigzag:\r
1748                                 tree.Add(32);\r
1749                                 Assert.IsTrue(snap.Check("M"), "Bad snap!");\r
1750                                 Assert.IsTrue(IC.eq(snap, orig), "Snap was changed!");\r
1751                                 Assert.IsTrue(tree.Check("Tree"), "Bad tree!");\r
1752                         }\r
1753 \r
1754 \r
1755                         [Test]\r
1756                         public void Clear()\r
1757                         {\r
1758                                 int[] orig = new int[] { 1, 3, 5, 7, 9, 11, 13, 15, 17, 19 };\r
1759                                 TreeBag<int> snap = (TreeBag<int>)tree.Snapshot();\r
1760 \r
1761                                 tree.Clear();\r
1762                                 Assert.IsTrue(snap.Check("Snap"), "Bad snap!");\r
1763                                 Assert.IsTrue(tree.Check("Tree"), "Bad tree!");\r
1764                                 Assert.IsTrue(IC.eq(snap, orig), "Snap was changed!");\r
1765                                 Assert.AreEqual(0, tree.Count);\r
1766                         }\r
1767 \r
1768 \r
1769                         [Test]\r
1770                         [ExpectedException(typeof(InvalidOperationException), "Cannot snapshot a snapshot")]\r
1771                         public void SnapSnap()\r
1772                         {\r
1773                                 TreeBag<int> snap = (TreeBag<int>)tree.Snapshot();\r
1774 \r
1775                                 snap.Snapshot();\r
1776                         }\r
1777 \r
1778 \r
1779                         [TearDown]\r
1780                         public void Dispose()\r
1781                         {\r
1782                                 tree = null;\r
1783                                 ic = null;\r
1784                         }\r
1785                 }\r
1786 \r
1787 \r
1788 \r
1789                 [TestFixture]\r
1790                 public class Multiple\r
1791                 {\r
1792                         private TreeBag<int> tree;\r
1793 \r
1794                         private IComparer<int> ic;\r
1795 \r
1796 \r
1797                         private bool eq(MSG.IEnumerable<int> me, int[] that)\r
1798                         {\r
1799                                 int i = 0, maxind = that.Length - 1;\r
1800 \r
1801                                 foreach (int item in me)\r
1802                                         if (i > maxind || ic.Compare(item, that[i++]) != 0)\r
1803                                                 return false;\r
1804 \r
1805                                 return true;\r
1806                         }\r
1807 \r
1808 \r
1809                         [SetUp]\r
1810                         public void Init()\r
1811                         {\r
1812                                 ic = new IC();\r
1813                                 tree = new TreeBag<int>(ic);\r
1814                                 for (int i = 0; i < 10; i++)\r
1815                                         tree.Add(2 * i + 1);\r
1816                         }\r
1817 \r
1818 \r
1819                         [Test]\r
1820                         public void First()\r
1821                         {\r
1822                                 TreeBag<int>[] snaps = new TreeBag<int>[10];\r
1823 \r
1824                                 for (int i = 0; i < 10; i++)\r
1825                                 {\r
1826                                         snaps[i] = (TreeBag<int>)(tree.Snapshot());\r
1827                                         tree.Add(2 * i);\r
1828                                 }\r
1829 \r
1830                                 for (int i = 0; i < 10; i++)\r
1831                                 {\r
1832                                         Assert.AreEqual(i + 10, snaps[i].Count);\r
1833                                 }\r
1834 \r
1835                                 snaps[5] = null;\r
1836                                 snaps[9] = null;\r
1837                                 GC.Collect();\r
1838                                 snaps[8].Dispose();\r
1839                                 tree.Remove(14);\r
1840 \r
1841                                 int[] res = new int[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 15, 16, 17, 18, 19 };\r
1842                                 int[] snap7 = new int[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 15, 17, 19 };\r
1843                                 int[] snap3 = new int[] { 0, 1, 2, 3, 4, 5, 7, 9, 11, 13, 15, 17, 19 };\r
1844 \r
1845                                 Assert.IsTrue(IC.eq(snaps[3], snap3), "Snap 3 was changed!");\r
1846                                 Assert.IsTrue(IC.eq(snaps[7], snap7), "Snap 7 was changed!");\r
1847                                 Assert.IsTrue(IC.eq(tree, res));\r
1848                                 Assert.IsTrue(tree.Check("B"));\r
1849                                 Assert.IsTrue(snaps[3].Check("B"));\r
1850                                 Assert.IsTrue(snaps[7].Check("B"));\r
1851                         }\r
1852 \r
1853 \r
1854                         [Test]\r
1855                         public void CollectingTheMaster()\r
1856                         {\r
1857                                 TreeBag<int>[] snaps = new TreeBag<int>[10];\r
1858 \r
1859                                 for (int i = 0; i < 10; i++)\r
1860                                 {\r
1861                                         snaps[i] = (TreeBag<int>)(tree.Snapshot());\r
1862                                         tree.Add(2 * i);\r
1863                                 }\r
1864 \r
1865                                 tree = null;\r
1866                                 GC.Collect();\r
1867                                 for (int i = 0; i < 10; i++)\r
1868                                 {\r
1869                                         Assert.AreEqual(i + 10, snaps[i].Count);\r
1870                                 }\r
1871 \r
1872                                 snaps[5] = null;\r
1873                                 snaps[9] = null;\r
1874                                 GC.Collect();\r
1875                                 snaps[8].Dispose();\r
1876 \r
1877                                 int[] snap7 = new int[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 15, 17, 19 };\r
1878                                 int[] snap3 = new int[] { 0, 1, 2, 3, 4, 5, 7, 9, 11, 13, 15, 17, 19 };\r
1879 \r
1880                                 Assert.IsTrue(IC.eq(snaps[3], snap3), "Snap 3 was changed!");\r
1881                                 Assert.IsTrue(IC.eq(snaps[7], snap7), "Snap 7 was changed!");\r
1882                                 Assert.IsTrue(snaps[3].Check("B"));\r
1883                                 Assert.IsTrue(snaps[7].Check("B"));\r
1884                         }\r
1885 \r
1886 \r
1887                         [TearDown]\r
1888                         public void Dispose()\r
1889                         {\r
1890                                 tree = null;\r
1891                                 ic = null;\r
1892                         }\r
1893                 }\r
1894         }\r
1895 \r
1896 \r
1897 \r
1898 \r
1899         namespace HigherOrder\r
1900         {\r
1901                 internal class CubeRoot: IComparable<int>\r
1902                 {\r
1903                         private int c;\r
1904 \r
1905 \r
1906                         internal CubeRoot(int c) { this.c = c; }\r
1907 \r
1908 \r
1909             public int CompareTo(int that) { return c - that * that * that; }\r
1910             public bool Equals(int that) { return c == that * that * that; }\r
1911         }\r
1912 \r
1913 \r
1914 \r
1915         class Interval: IComparable<int>\r
1916                 {\r
1917                         private int b, t;\r
1918 \r
1919 \r
1920                         internal Interval(int b, int t) { this.b = b; this.t = t; }\r
1921 \r
1922 \r
1923             public int CompareTo(int that) { return that < b ? 1 : that > t ? -1 : 0; }\r
1924             public bool Equals(int that) { return that >= b && that <= t; }\r
1925         }\r
1926 \r
1927 \r
1928 \r
1929         [TestFixture]\r
1930                 public class Simple\r
1931                 {\r
1932                         private TreeBag<int> tree;\r
1933 \r
1934                         private IComparer<int> ic;\r
1935 \r
1936 \r
1937                         [SetUp]\r
1938                         public void Init()\r
1939                         {\r
1940                                 ic = new IC();\r
1941                                 tree = new TreeBag<int>(ic);\r
1942                         }\r
1943 \r
1944 \r
1945                         private bool never(int i) { return false; }\r
1946 \r
1947 \r
1948                         private bool always(int i) { return true; }\r
1949 \r
1950 \r
1951                         private bool even(int i) { return i % 2 == 0; }\r
1952 \r
1953 \r
1954                         private string themap(int i) { return String.Format("AA {0,4} BB", i); }\r
1955 \r
1956 \r
1957                         private string badmap(int i) { return String.Format("AA {0} BB", i); }\r
1958 \r
1959 \r
1960                         private int appfield1;\r
1961 \r
1962                         private int appfield2;\r
1963 \r
1964 \r
1965                         private void apply(int i) { appfield1++; appfield2 += i * i; }\r
1966 \r
1967 \r
1968                         [Test]\r
1969                         public void Apply()\r
1970                         {\r
1971                                 Simple simple1 = new Simple();\r
1972 \r
1973                                 tree.Apply(new Applier<int>(simple1.apply));\r
1974                                 Assert.AreEqual(0, simple1.appfield1);\r
1975                                 Assert.AreEqual(0, simple1.appfield2);\r
1976 \r
1977                                 Simple simple2 = new Simple();\r
1978 \r
1979                                 for (int i = 0; i < 10; i++) tree.Add(i);\r
1980                                 tree.Add(2);\r
1981 \r
1982                                 tree.Apply(new Applier<int>(simple2.apply));\r
1983                                 Assert.AreEqual(11, simple2.appfield1);\r
1984                                 Assert.AreEqual(289, simple2.appfield2);\r
1985                         }\r
1986 \r
1987 \r
1988                         [Test]\r
1989                         public void All()\r
1990                         {\r
1991                                 Assert.IsTrue(tree.All(new Filter<int>(never)));\r
1992                                 Assert.IsTrue(tree.All(new Filter<int>(even)));\r
1993                                 Assert.IsTrue(tree.All(new Filter<int>(always)));\r
1994                                 for (int i = 0; i < 10; i++)                                    tree.Add(i);\r
1995 \r
1996                                 Assert.IsFalse(tree.All(new Filter<int>(never)));\r
1997                                 Assert.IsFalse(tree.All(new Filter<int>(even)));\r
1998                                 Assert.IsTrue(tree.All(new Filter<int>(always)));\r
1999                                 tree.Clear();\r
2000                                 for (int i = 0; i < 10; i++)                                    tree.Add(i * 2);\r
2001 \r
2002                                 Assert.IsFalse(tree.All(new Filter<int>(never)));\r
2003                                 Assert.IsTrue(tree.All(new Filter<int>(even)));\r
2004                                 Assert.IsTrue(tree.All(new Filter<int>(always)));\r
2005                                 tree.Clear();\r
2006                                 for (int i = 0; i < 10; i++)                                    tree.Add(i * 2 + 1);\r
2007 \r
2008                                 Assert.IsFalse(tree.All(new Filter<int>(never)));\r
2009                                 Assert.IsFalse(tree.All(new Filter<int>(even)));\r
2010                                 Assert.IsTrue(tree.All(new Filter<int>(always)));\r
2011                         }\r
2012 \r
2013 \r
2014                         [Test]\r
2015                         public void Exists()\r
2016                         {\r
2017                                 Assert.IsFalse(tree.Exists(new Filter<int>(never)));\r
2018                                 Assert.IsFalse(tree.Exists(new Filter<int>(even)));\r
2019                                 Assert.IsFalse(tree.Exists(new Filter<int>(always)));\r
2020                                 for (int i = 0; i < 10; i++)                                    tree.Add(i);\r
2021 \r
2022                                 Assert.IsFalse(tree.Exists(new Filter<int>(never)));\r
2023                                 Assert.IsTrue(tree.Exists(new Filter<int>(even)));\r
2024                                 Assert.IsTrue(tree.Exists(new Filter<int>(always)));\r
2025                                 tree.Clear();\r
2026                                 for (int i = 0; i < 10; i++)                                    tree.Add(i * 2);\r
2027 \r
2028                                 Assert.IsFalse(tree.Exists(new Filter<int>(never)));\r
2029                                 Assert.IsTrue(tree.Exists(new Filter<int>(even)));\r
2030                                 Assert.IsTrue(tree.Exists(new Filter<int>(always)));\r
2031                                 tree.Clear();\r
2032                                 for (int i = 0; i < 10; i++)                                    tree.Add(i * 2 + 1);\r
2033 \r
2034                                 Assert.IsFalse(tree.Exists(new Filter<int>(never)));\r
2035                                 Assert.IsFalse(tree.Exists(new Filter<int>(even)));\r
2036                                 Assert.IsTrue(tree.Exists(new Filter<int>(always)));\r
2037                         }\r
2038 \r
2039 \r
2040                         [Test]\r
2041                         public void FindAll()\r
2042                         {\r
2043                                 Assert.AreEqual(0, tree.FindAll(new Filter<int>(never)).Count);\r
2044                                 for (int i = 0; i < 10; i++)\r
2045                                         tree.Add(i);\r
2046                                 tree.Add(2);\r
2047 \r
2048                                 Assert.AreEqual(0, tree.FindAll(new Filter<int>(never)).Count);\r
2049                                 Assert.AreEqual(11, tree.FindAll(new Filter<int>(always)).Count);\r
2050                                 Assert.AreEqual(6, tree.FindAll(new Filter<int>(even)).Count);\r
2051                                 Assert.IsTrue(((TreeBag<int>)tree.FindAll(new Filter<int>(even))).Check("R"));\r
2052                         }\r
2053 \r
2054 \r
2055                         [Test]\r
2056                         public void Map()\r
2057                         {\r
2058                                 Assert.AreEqual(0, tree.Map(new Mapper<int,string>(themap), new SC()).Count);\r
2059                                 for (int i = 0; i < 14; i++)\r
2060                                         tree.Add(i * i * i);\r
2061                                 tree.Add(1);\r
2062 \r
2063                                 IIndexedSorted<string> res = tree.Map(new Mapper<int,string>(themap), new SC());\r
2064 \r
2065                                 Assert.IsTrue(((TreeBag<string>)res).Check("R"));\r
2066                                 Assert.AreEqual(15, res.Count);\r
2067                                 Assert.AreEqual("AA    0 BB", res[0]);\r
2068                                 Assert.AreEqual("AA    1 BB", res[1]);\r
2069                                 Assert.AreEqual("AA    1 BB", res[2]);\r
2070                                 Assert.AreEqual("AA    8 BB", res[3]);\r
2071                                 Assert.AreEqual("AA   27 BB", res[4]);\r
2072                                 Assert.AreEqual("AA  125 BB", res[6]);\r
2073                                 Assert.AreEqual("AA 1000 BB", res[11]);\r
2074                         }\r
2075 \r
2076 \r
2077                         [Test]\r
2078                         [ExpectedException(typeof(ArgumentException), "mapper not monotonic")]\r
2079                         public void BadMap()\r
2080                         {\r
2081                                 for (int i = 0; i < 11; i++)\r
2082                                         tree.Add(i * i * i);\r
2083 \r
2084                                 ISorted<string> res = tree.Map(new Mapper<int,string>(badmap), new SC());\r
2085                         }\r
2086 \r
2087 \r
2088                         [Test]\r
2089                         public void Cut()\r
2090                         {\r
2091                                 for (int i = 0; i < 10; i++)\r
2092                                         tree.Add(i);\r
2093                                 tree.Add(3);\r
2094 \r
2095                                 int low, high;\r
2096                                 bool lval, hval;\r
2097 \r
2098                                 Assert.IsTrue(tree.Cut(new CubeRoot(27), out low, out lval, out high, out hval));\r
2099                                 Assert.IsTrue(lval && hval);\r
2100                                 Assert.AreEqual(4, high);\r
2101                                 Assert.AreEqual(2, low);\r
2102                                 Assert.IsFalse(tree.Cut(new CubeRoot(30), out low, out lval, out high, out hval));\r
2103                                 Assert.IsTrue(lval && hval);\r
2104                                 Assert.AreEqual(4, high);\r
2105                                 Assert.AreEqual(3, low);\r
2106                         }\r
2107 \r
2108 \r
2109                         [Test]\r
2110                         public void CutInt()\r
2111                         {\r
2112                                 for (int i = 0; i < 10; i++)\r
2113                                         tree.Add(2 * i);\r
2114 \r
2115                                 int low, high;\r
2116                                 bool lval, hval;\r
2117 \r
2118                                 Assert.IsFalse(tree.Cut(new IC(3), out low, out lval, out high, out hval));\r
2119                                 Assert.IsTrue(lval && hval);\r
2120                                 Assert.AreEqual(4, high);\r
2121                                 Assert.AreEqual(2, low);\r
2122                                 Assert.IsTrue(tree.Cut(new IC(6), out low, out lval, out high, out hval));\r
2123                                 Assert.IsTrue(lval && hval);\r
2124                                 Assert.AreEqual(8, high);\r
2125                                 Assert.AreEqual(4, low);\r
2126                         }\r
2127 \r
2128 \r
2129                         [Test]\r
2130                         public void CutInterval()\r
2131                         {\r
2132                                 for (int i = 0; i < 10; i++)\r
2133                                         tree.Add(2 * i);\r
2134 \r
2135                                 int lo, hi;\r
2136                                 bool lv, hv;\r
2137 \r
2138                                 Assert.IsTrue(tree.Cut(new Interval(5, 9), out lo, out lv, out hi, out hv));\r
2139                                 Assert.IsTrue(lv && hv);\r
2140                                 Assert.AreEqual(10, hi);\r
2141                                 Assert.AreEqual(4, lo);\r
2142                                 Assert.IsTrue(tree.Cut(new Interval(6, 10), out lo, out lv, out hi, out hv));\r
2143                                 Assert.IsTrue(lv && hv);\r
2144                                 Assert.AreEqual(12, hi);\r
2145                                 Assert.AreEqual(4, lo);\r
2146                                 for (int i = 0; i < 100; i++)\r
2147                                         tree.Add(2 * i);\r
2148 \r
2149                                 tree.Cut(new Interval(77, 105), out lo, out lv, out hi, out hv);\r
2150                                 Assert.IsTrue(lv && hv);\r
2151                                 Assert.AreEqual(106, hi);\r
2152                                 Assert.AreEqual(76, lo);\r
2153                                 tree.Cut(new Interval(5, 7), out lo, out lv, out hi, out hv);\r
2154                                 Assert.IsTrue(lv && hv);\r
2155                                 Assert.AreEqual(8, hi);\r
2156                                 Assert.AreEqual(4, lo);\r
2157                                 tree.Cut(new Interval(80, 110), out lo, out lv, out hi, out hv);\r
2158                                 Assert.IsTrue(lv && hv);\r
2159                                 Assert.AreEqual(112, hi);\r
2160                                 Assert.AreEqual(78, lo);\r
2161                         }\r
2162 \r
2163 \r
2164                         [Test]\r
2165                         public void UpperCut()\r
2166                         {\r
2167                                 for (int i = 0; i < 10; i++)\r
2168                                         tree.Add(i);\r
2169 \r
2170                                 int l, h;\r
2171                                 bool lv, hv;\r
2172 \r
2173                                 Assert.IsFalse(tree.Cut(new CubeRoot(1000), out l, out lv, out h, out hv));\r
2174                                 Assert.IsTrue(lv && !hv);\r
2175                                 Assert.AreEqual(9, l);\r
2176                                 Assert.IsFalse(tree.Cut(new CubeRoot(-50), out l, out lv, out h, out hv));\r
2177                                 Assert.IsTrue(!lv && hv);\r
2178                                 Assert.AreEqual(0, h);\r
2179                         }\r
2180 \r
2181 \r
2182                         [TearDown]\r
2183                         public void Dispose() { ic = null; tree = null; }\r
2184                 }\r
2185         }\r
2186 \r
2187 \r
2188 \r
2189 \r
2190         namespace MultiOps\r
2191         {\r
2192                 [TestFixture]\r
2193                 public class AddAll\r
2194                 {\r
2195                         private int sqr(int i) { return i * i; }\r
2196 \r
2197 \r
2198                         TreeBag<int> tree;\r
2199 \r
2200 \r
2201                         [SetUp]\r
2202                         public void Init() { tree = new TreeBag<int>(new IC()); }\r
2203 \r
2204 \r
2205                         [Test]\r
2206                         public void EmptyEmpty()\r
2207                         {\r
2208                                 tree.AddAll(new FunEnumerable(0, new Int2Int(sqr)));\r
2209                                 Assert.AreEqual(0, tree.Count);\r
2210                                 Assert.IsTrue(tree.Check());\r
2211                         }\r
2212 \r
2213 \r
2214                         [Test]\r
2215                         public void SomeEmpty()\r
2216                         {\r
2217                                 for (int i = 4; i < 9; i++) tree.Add(i);\r
2218 \r
2219                                 tree.AddAll(new FunEnumerable(0, new Int2Int(sqr)));\r
2220                                 Assert.AreEqual(5, tree.Count);\r
2221                                 Assert.IsTrue(tree.Check());\r
2222                         }\r
2223 \r
2224 \r
2225                         [Test]\r
2226                         public void EmptySome()\r
2227                         {\r
2228                                 tree.AddAll(new FunEnumerable(4, new Int2Int(sqr)));\r
2229                                 Assert.AreEqual(4, tree.Count);\r
2230                                 Assert.IsTrue(tree.Check());\r
2231                                 Assert.AreEqual(0, tree[0]);\r
2232                                 Assert.AreEqual(1, tree[1]);\r
2233                                 Assert.AreEqual(4, tree[2]);\r
2234                                 Assert.AreEqual(9, tree[3]);\r
2235                         }\r
2236 \r
2237 \r
2238                         [Test]\r
2239                         public void SomeSome()\r
2240                         {\r
2241                                 for (int i = 5; i < 9; i++) tree.Add(i);\r
2242                                 tree.Add(1);\r
2243 \r
2244                                 tree.AddAll(new FunEnumerable(4, new Int2Int(sqr)));\r
2245                                 Assert.AreEqual(9, tree.Count);\r
2246                                 Assert.IsTrue(tree.Check());\r
2247                                 Assert.IsTrue(IC.eq(tree, 0, 1, 1, 4, 5, 6, 7, 8, 9));\r
2248                         }\r
2249 \r
2250 \r
2251                         [TearDown]\r
2252                         public void Dispose() { tree = null; }\r
2253                 }\r
2254 \r
2255 \r
2256 \r
2257                 [TestFixture]\r
2258                 public class AddSorted\r
2259                 {\r
2260                         private int sqr(int i) { return i * i; }\r
2261 \r
2262                         private int step(int i) { return i/3; }\r
2263 \r
2264 \r
2265                         private int bad(int i) { return i * (5 - i); }\r
2266 \r
2267 \r
2268                         TreeBag<int> tree;\r
2269 \r
2270 \r
2271                         [SetUp]\r
2272                         public void Init() { tree = new TreeBag<int>(new IC()); }\r
2273 \r
2274 \r
2275                         [Test]\r
2276                         public void EmptyEmpty()\r
2277                         {\r
2278                                 tree.AddSorted(new FunEnumerable(0, new Int2Int(sqr)));\r
2279                                 Assert.AreEqual(0, tree.Count);\r
2280                                 Assert.IsTrue(tree.Check());\r
2281                         }\r
2282 \r
2283 \r
2284                         [Test]\r
2285                         public void SomeEmpty()\r
2286                         {\r
2287                                 for (int i = 4; i < 9; i++) tree.Add(i);\r
2288 \r
2289                                 tree.AddSorted(new FunEnumerable(0, new Int2Int(sqr)));\r
2290                                 Assert.AreEqual(5, tree.Count);\r
2291                                 Assert.IsTrue(tree.Check());\r
2292                         }\r
2293 \r
2294 \r
2295                         [Test]\r
2296                         public void EmptySome()\r
2297                         {\r
2298                                 tree.AddSorted(new FunEnumerable(4, new Int2Int(sqr)));\r
2299                                 Assert.AreEqual(4, tree.Count);\r
2300                                 Assert.IsTrue(tree.Check());\r
2301                                 Assert.AreEqual(0, tree[0]);\r
2302                                 Assert.AreEqual(1, tree[1]);\r
2303                                 Assert.AreEqual(4, tree[2]);\r
2304                                 Assert.AreEqual(9, tree[3]);\r
2305                         }\r
2306 \r
2307                         [Test]\r
2308                         public void EmptySome2()\r
2309                         {\r
2310                                 tree.AddSorted(new FunEnumerable(4, new Int2Int(step)));\r
2311                                 //tree.dump();\r
2312                                 Assert.AreEqual(4, tree.Count);\r
2313                                 Assert.IsTrue(tree.Check());\r
2314                                 Assert.AreEqual(0, tree[0]);\r
2315                                 Assert.AreEqual(0, tree[1]);\r
2316                                 Assert.AreEqual(0, tree[2]);\r
2317                                 Assert.AreEqual(1, tree[3]);\r
2318                         }\r
2319 \r
2320 \r
2321                         [Test]\r
2322                         public void SomeSome()\r
2323                         {\r
2324                                 for (int i = 5; i < 9; i++) tree.Add(i);\r
2325                                 tree.Add(1);\r
2326 \r
2327                                 tree.AddSorted(new FunEnumerable(4, new Int2Int(sqr)));\r
2328                                 Assert.AreEqual(9, tree.Count);\r
2329                                 Assert.IsTrue(tree.Check());\r
2330                                 Assert.IsTrue(IC.eq(tree, 0, 1,1, 4, 5, 6, 7, 8, 9));\r
2331                         }\r
2332 \r
2333 \r
2334                         [Test]\r
2335                         [ExpectedException(typeof(ArgumentException), "Argument not sorted")]\r
2336                         public void EmptyBad()\r
2337                         {\r
2338                                 tree.AddSorted(new FunEnumerable(9, new Int2Int(bad)));\r
2339                         }\r
2340 \r
2341 \r
2342                         [TearDown]\r
2343                         public void Dispose() { tree = null; }\r
2344                 }\r
2345 \r
2346 \r
2347 \r
2348                 [TestFixture]\r
2349                 public class Rest\r
2350                 {\r
2351                         TreeBag<int> tree, tree2;\r
2352 \r
2353 \r
2354                         [SetUp]\r
2355                         public void Init()\r
2356                         {\r
2357                                 tree = new TreeBag<int>(new IC());\r
2358                                 tree2 = new TreeBag<int>(new IC());\r
2359                                 for (int i = 0; i < 10; i++)\r
2360                                         tree.Add(i);\r
2361                                 tree.Add(4);\r
2362 \r
2363                                 for (int i = 0; i < 10; i++)\r
2364                                         tree2.Add(2 * i);\r
2365                         }\r
2366 \r
2367 \r
2368                         [Test]\r
2369                         public void RemoveAll()\r
2370                         {\r
2371                                 tree.RemoveAll(tree2.RangeFromTo(3, 7));\r
2372                                 Assert.AreEqual(9, tree.Count);\r
2373                                 Assert.IsTrue(tree.Check());\r
2374                                 Assert.IsTrue(IC.eq(tree, 0, 1, 2, 3,4, 5, 7, 8, 9));\r
2375                                 tree.RemoveAll(tree2.RangeFromTo(3, 7));\r
2376                                 Assert.AreEqual(8, tree.Count);\r
2377                                 Assert.IsTrue(tree.Check());\r
2378                                 Assert.IsTrue(IC.eq(tree, 0, 1, 2, 3, 5, 7, 8, 9));\r
2379                                 tree.RemoveAll(tree2.RangeFromTo(13, 17));\r
2380                                 Assert.AreEqual(8, tree.Count);\r
2381                                 Assert.IsTrue(tree.Check());\r
2382                                 Assert.IsTrue(IC.eq(tree, 0, 1, 2, 3, 5, 7, 8, 9));\r
2383                                 tree.RemoveAll(tree2.RangeFromTo(3, 17));\r
2384                                 Assert.AreEqual(7, tree.Count);\r
2385                                 Assert.IsTrue(tree.Check());\r
2386                                 Assert.IsTrue(IC.eq(tree, 0, 1, 2, 3, 5, 7, 9));\r
2387                                 for (int i = 0; i < 10; i++) tree2.Add(i);\r
2388 \r
2389                                 tree.RemoveAll(tree2.RangeFromTo(-1, 10));\r
2390                                 Assert.AreEqual(0, tree.Count);\r
2391                                 Assert.IsTrue(tree.Check());\r
2392                                 Assert.IsTrue(IC.eq(tree));\r
2393                         }\r
2394 \r
2395                         private void pint<T>(MSG.IEnumerable<T> e)\r
2396                         {\r
2397                                 foreach (T i in e)\r
2398                                         Console.Write("{0} ", i);\r
2399 \r
2400                                 Console.WriteLine();\r
2401                         }\r
2402 \r
2403                         [Test]\r
2404                         public void RetainAll()\r
2405                         {\r
2406                                 tree.Add(8);tree2.Add(6);\r
2407                                 //pint<int>(tree);\r
2408                                 //pint<int>(tree2);\r
2409                                 tree.RetainAll(tree2.RangeFromTo(3, 17));\r
2410                                 Assert.AreEqual(3, tree.Count);\r
2411                                 Assert.IsTrue(tree.Check());\r
2412                                 Assert.IsTrue(IC.eq(tree, 4, 6, 8));\r
2413                                 tree.RetainAll(tree2.RangeFromTo(1, 17));\r
2414                                 Assert.AreEqual(3, tree.Count);\r
2415                                 Assert.IsTrue(tree.Check());\r
2416                                 Assert.IsTrue(IC.eq(tree, 4, 6 , 8));\r
2417                                 tree.RetainAll(tree2.RangeFromTo(3, 5));\r
2418                                 Assert.AreEqual(1, tree.Count);\r
2419                                 Assert.IsTrue(tree.Check());\r
2420                                 Assert.IsTrue(IC.eq(tree, 4));\r
2421                                 tree.RetainAll(tree2.RangeFromTo(7, 17));\r
2422                                 Assert.AreEqual(0, tree.Count);\r
2423                                 Assert.IsTrue(tree.Check());\r
2424                                 Assert.IsTrue(IC.eq(tree));\r
2425                                 for (int i = 0; i < 10; i++) tree.Add(i);\r
2426 \r
2427                                 tree.RetainAll(tree2.RangeFromTo(5, 5));\r
2428                                 Assert.AreEqual(0, tree.Count);\r
2429                                 Assert.IsTrue(tree.Check());\r
2430                                 Assert.IsTrue(IC.eq(tree));\r
2431                                 for (int i = 0; i < 10; i++) tree.Add(i);\r
2432 \r
2433                                 tree.RetainAll(tree2.RangeFromTo(15, 25));\r
2434                                 Assert.AreEqual(0, tree.Count);\r
2435                                 Assert.IsTrue(tree.Check());\r
2436                                 Assert.IsTrue(IC.eq(tree));\r
2437                         }\r
2438 \r
2439 \r
2440                         [Test]\r
2441                         public void ContainsAll()\r
2442                         {\r
2443                                 Assert.IsFalse(tree.ContainsAll(tree2));\r
2444                                 Assert.IsTrue(tree.ContainsAll(tree));\r
2445                                 tree2.Clear();\r
2446                                 Assert.IsTrue(tree.ContainsAll(tree2));\r
2447                                 tree.Clear();\r
2448                                 Assert.IsTrue(tree.ContainsAll(tree2));\r
2449                                 tree2.Add(8);\r
2450                                 Assert.IsFalse(tree.ContainsAll(tree2));\r
2451                         }\r
2452 \r
2453 \r
2454                         [Test]\r
2455                         public void RemoveInterval()\r
2456                         {\r
2457                                 tree.RemoveInterval(3, 4);\r
2458                                 Assert.IsTrue(tree.Check());\r
2459                                 Assert.AreEqual(7, tree.Count);\r
2460                                 Assert.IsTrue(IC.eq(tree, 0, 1, 2, 6, 7, 8, 9));\r
2461                                 tree.RemoveInterval(2, 3);\r
2462                                 Assert.IsTrue(tree.Check());\r
2463                                 Assert.AreEqual(4, tree.Count);\r
2464                                 Assert.IsTrue(IC.eq(tree, 0, 1, 8,9));\r
2465                                 tree.RemoveInterval(0, 4);\r
2466                                 Assert.IsTrue(tree.Check());\r
2467                                 Assert.AreEqual(0, tree.Count);\r
2468                                 Assert.IsTrue(IC.eq(tree));\r
2469                         }\r
2470 \r
2471 \r
2472                         [Test]\r
2473                         [ExpectedException(typeof(ArgumentOutOfRangeException))]\r
2474                         public void RemoveRangeBad1()\r
2475                         {\r
2476                                 tree.RemoveInterval(-3, 8);\r
2477                         }\r
2478 \r
2479 \r
2480                         [Test]\r
2481                         [ExpectedException(typeof(ArgumentOutOfRangeException))]\r
2482                         public void RemoveRangeBad2()\r
2483                         {\r
2484                                 tree.RemoveInterval(3, -8);\r
2485                         }\r
2486 \r
2487 \r
2488                         [Test]\r
2489                         [ExpectedException(typeof(ArgumentException))]\r
2490                         public void RemoveRangeBad3()\r
2491                         {\r
2492                                 tree.RemoveInterval(3, 9);\r
2493                         }\r
2494 \r
2495 \r
2496                         [Test]\r
2497                         public void GetRange()\r
2498                         {\r
2499                                 Assert.IsTrue(IC.eq(tree[3, 3]));\r
2500                                 Assert.IsTrue(IC.eq(tree[3, 4], 3));\r
2501                                 Assert.IsTrue(IC.eq(tree[3, 5], 3, 4));\r
2502                                 Assert.IsTrue(IC.eq(tree[3, 6], 3, 4, 4));\r
2503                                 Assert.IsTrue(IC.eq(tree[3, 7], 3, 4, 4, 5));\r
2504                                 Assert.IsTrue(IC.eq(tree[4, 4]));\r
2505                                 Assert.IsTrue(IC.eq(tree[4, 5], 4));\r
2506                                 Assert.IsTrue(IC.eq(tree[4, 6], 4, 4));\r
2507                                 Assert.IsTrue(IC.eq(tree[4, 7], 4, 4, 5));\r
2508                                 Assert.IsTrue(IC.eq(tree[4, 8], 4, 4, 5, 6));\r
2509                                 Assert.IsTrue(IC.eq(tree[5, 5]));\r
2510                                 Assert.IsTrue(IC.eq(tree[5, 6], 4));\r
2511                                 Assert.IsTrue(IC.eq(tree[5, 7], 4, 5));\r
2512                                 Assert.IsTrue(IC.eq(tree[5, 8], 4, 5, 6));\r
2513                                 Assert.IsTrue(IC.eq(tree[5, 9], 4, 5, 6, 7));\r
2514                                 Assert.IsTrue(IC.eq(tree[5, 11], 4, 5, 6, 7, 8, 9));\r
2515                         }\r
2516 \r
2517 \r
2518                         [Test]\r
2519                         public void GetRangeBackwards()\r
2520                         {\r
2521                                 Assert.IsTrue(IC.eq(tree[3, 3].Backwards()));\r
2522                                 Assert.IsTrue(IC.eq(tree[3, 4].Backwards(), 3));\r
2523                                 Assert.IsTrue(IC.eq(tree[3, 5].Backwards(), 4, 3));\r
2524                                 Assert.IsTrue(IC.eq(tree[3, 6].Backwards(), 4, 4, 3));\r
2525                                 Assert.IsTrue(IC.eq(tree[3, 7].Backwards(), 5, 4, 4, 3));\r
2526                                 Assert.IsTrue(IC.eq(tree[4, 4].Backwards()));\r
2527                                 Assert.IsTrue(IC.eq(tree[4, 5].Backwards(), 4));\r
2528                                 Assert.IsTrue(IC.eq(tree[4, 6].Backwards(), 4, 4));\r
2529                                 Assert.IsTrue(IC.eq(tree[4, 7].Backwards(), 5, 4, 4));\r
2530                                 Assert.IsTrue(IC.eq(tree[4, 8].Backwards(), 6, 5, 4, 4));\r
2531                                 Assert.IsTrue(IC.eq(tree[5, 5].Backwards()));\r
2532                                 Assert.IsTrue(IC.eq(tree[5, 6].Backwards(), 4));\r
2533                                 Assert.IsTrue(IC.eq(tree[5, 7].Backwards(), 5, 4));\r
2534                                 Assert.IsTrue(IC.eq(tree[5, 8].Backwards(), 6, 5, 4));\r
2535                                 Assert.IsTrue(IC.eq(tree[5, 9].Backwards(), 7, 6, 5, 4));\r
2536                         }\r
2537 \r
2538 \r
2539                         [Test]\r
2540                         [ExpectedException(typeof(ArgumentOutOfRangeException))]\r
2541                         public void GetRangeBad1()\r
2542                         {\r
2543                                 object foo = tree[-3, 0];\r
2544                         }\r
2545 \r
2546 \r
2547                         [Test]\r
2548                         [ExpectedException(typeof(ArgumentOutOfRangeException))]\r
2549                         public void GetRangeBad2()\r
2550                         {\r
2551                                 object foo = tree[3, 2];\r
2552                         }\r
2553 \r
2554 \r
2555                         [Test]\r
2556                         [ExpectedException(typeof(ArgumentException))]\r
2557                         public void GetRangeBad3()\r
2558                         {\r
2559                                 object foo = tree[3, 12];\r
2560                         }\r
2561 \r
2562 \r
2563                         [TearDown]\r
2564                         public void Dispose() { tree = null; tree2 = null; }\r
2565                 }\r
2566         }\r
2567 \r
2568 \r
2569         namespace Hashing\r
2570         {\r
2571                 [TestFixture]\r
2572                 public class ISequenced\r
2573                 {\r
2574                         private ISequenced<int> dit, dat, dut;\r
2575 \r
2576 \r
2577                         [SetUp]\r
2578                         public void Init()\r
2579                         {\r
2580                                 dit = new TreeBag<int>(new IC());\r
2581                                 dat = new TreeBag<int>(new IC());\r
2582                                 dut = new TreeBag<int>(new RevIC());\r
2583                         }\r
2584 \r
2585 \r
2586                         [Test]\r
2587                         public void EmptyEmpty()\r
2588                         {\r
2589                                 Assert.IsTrue(dit.Equals(dat));\r
2590                         }\r
2591 \r
2592 \r
2593                         [Test]\r
2594                         public void EmptyNonEmpty()\r
2595                         {\r
2596                                 dit.Add(3);\r
2597                                 Assert.IsFalse(dit.Equals(dat));\r
2598                                 Assert.IsFalse(dat.Equals(dit));\r
2599                         }\r
2600 \r
2601 \r
2602                         public int hasher(params int[] items)\r
2603                         {\r
2604                                 int retval = 0;\r
2605 \r
2606                                 foreach (int i in items)\r
2607                                         retval = retval * 31 + i;\r
2608 \r
2609                                 return retval;\r
2610                         }\r
2611 \r
2612 \r
2613                         [Test]\r
2614                         public void HashVal()\r
2615                         {\r
2616                                 Assert.AreEqual(hasher(), dit.GetHashCode());\r
2617                                 dit.Add(3);\r
2618                                 Assert.AreEqual(hasher(3), dit.GetHashCode());\r
2619                                 dit.Add(7);\r
2620                                 Assert.AreEqual(hasher(3, 7), dit.GetHashCode());\r
2621                                 Assert.AreEqual(hasher(), dut.GetHashCode());\r
2622                                 dut.Add(3);\r
2623                                 Assert.AreEqual(hasher(3), dut.GetHashCode());\r
2624                                 dut.Add(7);\r
2625                                 Assert.AreEqual(hasher(7, 3), dut.GetHashCode());\r
2626                         }\r
2627 \r
2628 \r
2629                         [Test]\r
2630                         public void Normal()\r
2631                         {\r
2632                                 dit.Add(3);\r
2633                                 dit.Add(7);\r
2634                                 dat.Add(3);\r
2635                                 Assert.IsFalse(dit.Equals(dat));\r
2636                                 Assert.IsFalse(dat.Equals(dit));\r
2637                                 dat.Add(7);\r
2638                                 Assert.IsTrue(dit.Equals(dat));\r
2639                                 Assert.IsTrue(dat.Equals(dit));\r
2640                         }\r
2641 \r
2642 \r
2643                         [Test]\r
2644                         public void WrongOrder()\r
2645                         {\r
2646                                 dit.Add(3);\r
2647                                 dut.Add(3);\r
2648                                 Assert.IsTrue(dit.Equals(dut));\r
2649                                 Assert.IsTrue(dut.Equals(dit));\r
2650                                 dit.Add(7);\r
2651                                 dut.Add(7);\r
2652                                 Assert.IsFalse(dit.Equals(dut));\r
2653                                 Assert.IsFalse(dut.Equals(dit));\r
2654                         }\r
2655 \r
2656 \r
2657                         [Test]\r
2658                         public void Reflexive()\r
2659                         {\r
2660                                 Assert.IsTrue(dit.Equals(dit));\r
2661                                 dit.Add(3);\r
2662                                 Assert.IsTrue(dit.Equals(dit));\r
2663                                 dit.Add(7);\r
2664                                 Assert.IsTrue(dit.Equals(dit));\r
2665                         }\r
2666 \r
2667 \r
2668                         [TearDown]\r
2669                         public void Dispose()\r
2670                         {\r
2671                                 dit = null;\r
2672                                 dat = null;\r
2673                                 dut = null;\r
2674                         }\r
2675                 }\r
2676 \r
2677 \r
2678 \r
2679                 [TestFixture]\r
2680                 public class IEditableCollection\r
2681                 {\r
2682                         private ICollection<int> dit, dat, dut;\r
2683 \r
2684 \r
2685                         [SetUp]\r
2686                         public void Init()\r
2687                         {\r
2688                                 dit = new TreeBag<int>(new IC());\r
2689                                 dat = new TreeBag<int>(new IC());\r
2690                                 dut = new TreeBag<int>(new RevIC());\r
2691                         }\r
2692 \r
2693 \r
2694                         [Test]\r
2695                         public void EmptyEmpty()\r
2696                         {\r
2697                                 Assert.IsTrue(dit.Equals(dat));\r
2698                         }\r
2699 \r
2700 \r
2701                         [Test]\r
2702                         public void EmptyNonEmpty()\r
2703                         {\r
2704                                 dit.Add(3);\r
2705                                 Assert.IsFalse(dit.Equals(dat));\r
2706                                 Assert.IsFalse(dat.Equals(dit));\r
2707                         }\r
2708 \r
2709 \r
2710                         public int hasher(int count, params int[] items)\r
2711                         {\r
2712                                 int retval = 0;\r
2713 \r
2714                                 foreach (int i in items)\r
2715                                         retval ^= i;\r
2716 \r
2717                                 return (count << 16) + retval;\r
2718                         }\r
2719 \r
2720 \r
2721                         [Test]\r
2722                         public void HashVal()\r
2723                         {\r
2724                                 Assert.AreEqual(hasher(0), dit.GetHashCode());\r
2725                                 dit.Add(3);\r
2726                                 Assert.AreEqual(hasher(1, 3), dit.GetHashCode());\r
2727                                 dit.Add(7);\r
2728                                 Assert.AreEqual(hasher(2, 3, 7), dit.GetHashCode());\r
2729                                 Assert.AreEqual(hasher(0), dut.GetHashCode());\r
2730                                 dut.Add(3);\r
2731                                 Assert.AreEqual(hasher(1, 3), dut.GetHashCode());\r
2732                                 dut.Add(7);\r
2733                                 Assert.AreEqual(hasher(2, 7, 3), dut.GetHashCode());\r
2734                         }\r
2735 \r
2736 \r
2737                         [Test]\r
2738                         public void Normal()\r
2739                         {\r
2740                                 dit.Add(3);\r
2741                                 dit.Add(7);\r
2742                                 dat.Add(3);\r
2743                                 Assert.IsFalse(dit.Equals(dat));\r
2744                                 Assert.IsFalse(dat.Equals(dit));\r
2745                                 dat.Add(7);\r
2746                                 Assert.IsTrue(dit.Equals(dat));\r
2747                                 Assert.IsTrue(dat.Equals(dit));\r
2748                         }\r
2749 \r
2750 \r
2751                         [Test]\r
2752                         public void WrongOrder()\r
2753                         {\r
2754                                 dit.Add(3);\r
2755                                 dut.Add(3);\r
2756                                 Assert.IsTrue(dit.Equals(dut));\r
2757                                 Assert.IsTrue(dut.Equals(dit));\r
2758                                 dit.Add(7);\r
2759                                 dut.Add(7);\r
2760                                 Assert.IsTrue(dit.Equals(dut));\r
2761                                 Assert.IsTrue(dut.Equals(dit));\r
2762                         }\r
2763 \r
2764 \r
2765                         [Test]\r
2766                         public void Reflexive()\r
2767                         {\r
2768                                 Assert.IsTrue(dit.Equals(dit));\r
2769                                 dit.Add(3);\r
2770                                 Assert.IsTrue(dit.Equals(dit));\r
2771                                 dit.Add(7);\r
2772                                 Assert.IsTrue(dit.Equals(dit));\r
2773                         }\r
2774 \r
2775 \r
2776                         [TearDown]\r
2777                         public void Dispose()\r
2778                         {\r
2779                                 dit = null;\r
2780                                 dat = null;\r
2781                                 dut = null;\r
2782                         }\r
2783                 }\r
2784         }\r
2785 \r
2786 }\r
2787 #endif\r