mcs/class/Mono.C5/current/Test/arrays/SortedArrayTests.cs

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