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

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