mcs/class/System/Test/System.Collections.Generic/SortedSetTest.cs

   1 //
   2 // SortedSetTest.cs
   3 //
   4 // Author:
   5 //      Jb Evain <jbevain@novell.com>
   6 //
   7 // Copyright (C) 2010 Novell, Inc (http://www.novell.com)
   8 //
   9 // Permission is hereby granted, free of charge, to any person obtaining
  10 // a copy of this software and associated documentation files (the
  11 // "Software"), to deal in the Software without restriction, including
  12 // without limitation the rights to use, copy, modify, merge, publish,
  13 // distribute, sublicense, and/or sell copies of the Software, and to
  14 // permit persons to whom the Software is furnished to do so, subject to
  15 // the following conditions:
  16 //
  17 // The above copyright notice and this permission notice shall be
  18 // included in all copies or substantial portions of the Software.
  19 //
  20 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  21 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  22 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  23 // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  24 // LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  25 // OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  26 // WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  27 //
  28
  29
  30 using System;
  31 using System.Collections;
  32 using System.Collections.Generic;
  33 using System.Linq;
  34 using System.Runtime.Serialization;
  35
  36 using NUnit.Framework;
  37
  38 namespace MonoTests.System.Collections.Generic
  39 {
  40         [TestFixture]
  41         public class SortedSetTest
  42         {
  43                 [Test]
  44                 public void CtorNullComparer ()
  45                 {
  46                         var set = new SortedSet<int> ((IComparer<int>) null);
  47                         Assert.AreEqual (Comparer<int>.Default, set.Comparer);
  48                 }
  49
  50                 [Test]
  51                 [ExpectedException (typeof (ArgumentNullException))]
  52                 public void CtorNullCollection ()
  53                 {
  54                         new SortedSet<int> (null as IEnumerable<int>);
  55                 }
  56
  57                 [Test]
  58                 public void CtorDefault ()
  59                 {
  60                         var set = new SortedSet<int> ();
  61                         Assert.IsNotNull (set.Comparer);
  62                 }
  63
  64                 [Test]
  65                 public void Add ()
  66                 {
  67                         var set = new SortedSet<int> ();
  68                         Assert.AreEqual (0, set.Count);
  69                         Assert.IsTrue (set.Add (2));
  70                         Assert.IsTrue (set.Add (4));
  71                         Assert.IsTrue (set.Add (3));
  72                         Assert.AreEqual (3, set.Count);
  73                         Assert.IsFalse (set.Add (2));
  74                 }
  75
  76                 [Test]
  77                 public void Remove ()
  78                 {
  79                         var set = new SortedSet<int> ();
  80                         Assert.IsTrue (set.Add (2));
  81                         Assert.IsTrue (set.Add (4));
  82                         Assert.AreEqual (2, set.Count);
  83                         Assert.IsTrue (set.Remove (4));
  84                         Assert.IsTrue (set.Remove (2));
  85                         Assert.AreEqual (0, set.Count);
  86                         Assert.IsFalse (set.Remove (4));
  87                         Assert.IsFalse (set.Remove (2));
  88                 }
  89
  90                 [Test]
  91                 public void Clear ()
  92                 {
  93                         var set = new SortedSet<int> { 2, 3, 4, 5 };
  94                         Assert.AreEqual (4, set.Count);
  95                         set.Clear ();
  96                         Assert.AreEqual (0, set.Count);
  97                 }
  98
  99                 [Test]
 100                 public void Contains ()
 101                 {
 102                         var set = new SortedSet<int> { 2, 3, 4, 5 };
 103                         Assert.IsTrue (set.Contains (4));
 104                         Assert.IsFalse (set.Contains (7));
 105                 }
 106
 107                 [Test]
 108                 public void GetEnumerator ()
 109                 {
 110                         var set = new SortedSet<int> { 5, 3, 1, 2, 6, 4  };
 111                         Assert.IsTrue (set.SequenceEqual (new [] { 1, 2, 3, 4, 5, 6 }));
 112                 }
 113
 114                 [Test]
 115                 public void Reverse ()
 116                 {
 117                         var set = new SortedSet<int> { 5, 3, 1, 2, 6, 4  };
 118                         var reversed = set.Reverse ();
 119                         Assert.IsTrue (reversed.SequenceEqual (new [] { 6, 5, 4, 3, 2, 1 }));
 120                 }
 121
 122                 [Test]
 123                 public void ReverseView ()
 124                 {
 125                         var set = new SortedSet<int> { 1, 2, 3, 4, 5, 6 };
 126                         var subset = set.GetViewBetween (3, 5);
 127                         Assert.AreEqual (3, subset.Count, "#1");
 128                         Assert.AreEqual (3, subset.Reverse ().Count (), "#2");
 129                 }
 130
 131                 [Test]
 132                 public void RemoveWhere ()
 133                 {
 134                         var set = new SortedSet<int> { 1, 2, 3, 4, 5, 6 };
 135                         Assert.AreEqual (3, set.RemoveWhere (i => i % 2 == 0));
 136                         Assert.AreEqual (3, set.Count);
 137                         Assert.IsTrue (set.SequenceEqual (new [] { 1, 3, 5 }));
 138
 139                 }
 140
 141                 [Test]
 142                 public void Max ()
 143                 {
 144                         var set = new SortedSet<int> { 1, 3, 12, 9 };
 145                         Assert.AreEqual (12, set.Max);
 146                 }
 147
 148                 [Test]
 149                 public void Min ()
 150                 {
 151                         var set = new SortedSet<int> { 2, 3, 1, 9 };
 152                         Assert.AreEqual (1, set.Min);
 153                 }
 154
 155                 [Test]
 156                 [ExpectedException (typeof (ArgumentException))]
 157                 public void GetViewBetweenLowerBiggerThanUpper ()
 158                 {
 159                         var set = new SortedSet<int> { 1, 2, 3, 4, 5, 6 };
 160                         set.GetViewBetween (4, 2);
 161                 }
 162
 163                 [Test]
 164                 public void GetView ()
 165                 {
 166                         var set = new SortedSet<int> { 1, 3, 5, 7, 9 };
 167                         var view = set.GetViewBetween (3, 7);
 168
 169                         Assert.IsTrue (view.SequenceEqual (new [] { 3, 5, 7 }));
 170                 }
 171
 172                 [Test]
 173                 public void ViewAdd ()
 174                 {
 175                         var set = new SortedSet<int> { 1, 3, 5, 7 };
 176                         var view = set.GetViewBetween (3, 5);
 177
 178                         Assert.IsTrue (view.Add (4));
 179                         Assert.IsTrue (view.Contains (4));
 180                         Assert.IsTrue (set.Contains (4));
 181
 182                         Assert.IsFalse (view.Add (5));
 183                 }
 184
 185                 [Test]
 186                 [ExpectedException (typeof (ArgumentOutOfRangeException))]
 187                 public void ViewAddOutOfRange ()
 188                 {
 189                         var set = new SortedSet<int> { 1, 3, 5, 7 };
 190                         var view = set.GetViewBetween (3, 5);
 191
 192                         view.Add (7);
 193                 }
 194
 195                 [Test]
 196                 public void ViewContains ()
 197                 {
 198                         var set = new SortedSet<int> { 1, 3, 5, 7, 9 };
 199                         var view = set.GetViewBetween (3, 7);
 200
 201                         Assert.IsFalse (view.Contains (4));
 202                         Assert.IsTrue (view.Contains (3));
 203                         Assert.IsTrue (view.Contains (5));
 204                 }
 205
 206                 [Test]
 207                 public void ViewRemove ()
 208                 {
 209                         var set = new SortedSet<int> { 1, 3, 5, 7, 9 };
 210                         var view = set.GetViewBetween (3, 7);
 211
 212                         Assert.IsTrue (view.Remove (3));
 213                         Assert.IsFalse (view.Contains (3));
 214                         Assert.IsFalse (set.Contains (3));
 215                         Assert.IsFalse (view.Remove (9));
 216                         Assert.IsTrue (set.Contains (9));
 217                 }
 218
 219                 [Test]
 220                 public void ViewClear ()
 221                 {
 222                         var set = new SortedSet<int> { 1, 3, 5, 7, 9 };
 223                         var view = set.GetViewBetween (3, 7);
 224
 225                         view.Clear ();
 226
 227                         Assert.AreEqual (0, view.Count);
 228                         Assert.IsTrue (set.SequenceEqual (new [] { 1, 9 }));
 229                 }
 230
 231                 [Test]
 232                 [ExpectedException (typeof (ArgumentOutOfRangeException))]
 233                 public void ViewGetViewLowerOutOfRange ()
 234                 {
 235                         var set = new SortedSet<int> { 1, 3, 5, 7, 9 };
 236                         var view = set.GetViewBetween (3, 7);
 237                         view.GetViewBetween (2, 5);
 238                 }
 239
 240                 [Test]
 241                 [ExpectedException (typeof (ArgumentOutOfRangeException))]
 242                 public void ViewGetViewUpperOutOfRange ()
 243                 {
 244                         var set = new SortedSet<int> { 1, 3, 5, 7, 9 };
 245                         var view = set.GetViewBetween (3, 7);
 246                         view.GetViewBetween (5, 9);
 247                 }
 248
 249                 [Test]
 250                 public void ViewGetView ()
 251                 {
 252                         var set = new SortedSet<int> { 1, 3, 5, 7, 9 };
 253                         var view = set.GetViewBetween (3, 7);
 254                         view = view.GetViewBetween (4, 6);
 255
 256                         Assert.IsTrue (view.SequenceEqual (new [] { 5 }));
 257                 }
 258
 259                 void EmptySubView (SortedSet<int> set)
 260                 {
 261                         var view = set.GetViewBetween (-20, -15);
 262                         Assert.AreEqual (0, view.Count);
 263                         Assert.AreEqual (0, view.Min);
 264                         Assert.AreEqual (0, view.Max);
 265
 266                         view = set.GetViewBetween (15, 20);
 267                         Assert.AreEqual (0, view.Count);
 268                         Assert.AreEqual (0, view.Min);
 269                         Assert.AreEqual (0, view.Max);
 270                 }
 271
 272                 [Test]
 273                 public void EmptySubView ()
 274                 {
 275                         EmptySubView (new SortedSet<int> ());
 276                         EmptySubView (new SortedSet<int> { 1, 3, 5, 7, 9 });
 277                         EmptySubView (new SortedSet<int> { -40, 40 });
 278                         EmptySubView (new SortedSet<int> { -40, -10, 10, 40 });
 279                 }
 280
 281                 [Test]
 282                 public void ViewMin ()
 283                 {
 284                         var set = new SortedSet<int> { 1, 3, 5, 7, 9 };
 285
 286                         var view = set.GetViewBetween (4, 8);
 287                         Assert.AreEqual (5, view.Min);
 288
 289                         view = set.GetViewBetween (-2, 4);
 290                         Assert.AreEqual (1, view.Min);
 291
 292                         view = set.GetViewBetween (1, 9);
 293                         Assert.AreEqual (1, view.Min);
 294                 }
 295
 296                 [Test]
 297                 public void ViewMax ()
 298                 {
 299                         var set = new SortedSet<int> { 1, 3, 5, 7, 9 };
 300
 301                         var view = set.GetViewBetween (4, 8);
 302                         Assert.AreEqual (7, view.Max);
 303
 304                         view = set.GetViewBetween (4, 55);
 305                         Assert.AreEqual (9, view.Max);
 306
 307                         view = set.GetViewBetween (1, 9);
 308                         Assert.AreEqual (9, view.Max);
 309                 }
 310
 311                 [Test]
 312                 public void ViewCount ()
 313                 {
 314                         var set = new SortedSet<int> { 1, 3, 4, 5, 6, 7, 8, 9 };
 315                         var view = set.GetViewBetween (4, 8);
 316
 317                         Assert.AreEqual (5, view.Count);
 318                         set.Remove (5);
 319                         Assert.AreEqual (4, view.Count);
 320                         set.Add (10);
 321                         Assert.AreEqual (4, view.Count);
 322                         set.Add (6);
 323                         Assert.AreEqual (4, view.Count);
 324                         set.Add (5);
 325                         Assert.AreEqual (5, view.Count);
 326                 }
 327
 328                 [Test, ExpectedException (typeof (ArgumentNullException))]
 329                 public void IntersectWith_Null ()
 330                 {
 331                         var set = new SortedSet<int> ();
 332                         set.IntersectWith (null);
 333                 }
 334
 335                 [Test]
 336                 public void IntersectWith ()
 337                 {
 338                         var set = new SortedSet<int> { 1, 3, 5, 7, 9 };
 339                         set.IntersectWith (new [] { 5, 7, 3, 7, 11, 7, 5, 2 });
 340                         Assert.IsTrue (set.SequenceEqual (new [] { 3, 5, 7 }));
 341                 }
 342
 343                 [Test]
 344                 public void ViewIntersectWith ()
 345                 {
 346                         var set = new SortedSet<int> { 1, 3, 5, 7, 9 };
 347                         var view = set.GetViewBetween (4, 8);
 348                         view.IntersectWith (new [] { 1, 5, 9 });
 349                         Assert.IsTrue (view.SequenceEqual (new [] { 5 }));
 350                         Assert.IsTrue (set.SequenceEqual (new [] { 1, 3, 5, 9 }));
 351                         view.IntersectWith (new [] { 1, 2 });
 352                         Assert.IsTrue (view.SequenceEqual (new int [] {}));
 353                         Assert.IsTrue (set.SequenceEqual (new [] { 1, 3, 9 }));
 354                 }
 355
 356                 [Test, ExpectedException (typeof (ArgumentNullException))]
 357                 public void UnionWith_Null ()
 358                 {
 359                         var set = new SortedSet<int> ();
 360                         set.UnionWith (null);
 361                 }
 362
 363                 [Test]
 364                 public void UnionWith ()
 365                 {
 366                         var set = new SortedSet<int> { 1, 3, 5, 7, 9 };
 367                         set.UnionWith (new [] { 5, 7, 3, 7, 11, 7, 5, 2 });
 368                         Assert.IsTrue (set.SequenceEqual (new [] { 1, 2, 3, 5, 7, 9, 11 }));
 369                 }
 370
 371                 [Test]
 372                 public void ViewUnionWith ()
 373                 {
 374                         var set = new SortedSet<int> { 1, 3, 5, 7, 9 };
 375                         var view = set.GetViewBetween (4, 8);
 376                         view.UnionWith (new [] { 4, 5, 6, 6, 4 });
 377                         Assert.IsTrue (view.SequenceEqual (new [] { 4, 5, 6, 7 }));
 378                         Assert.IsTrue (set.SequenceEqual (new [] { 1, 3, 4, 5, 6, 7, 9 }));
 379                 }
 380
 381                 [Test, ExpectedException (typeof (ArgumentOutOfRangeException))]
 382                 public void ViewUnionWith_oor ()
 383                 {
 384                         var set = new SortedSet<int> { 1, 3, 5, 7, 9 };
 385                         var view = set.GetViewBetween (4, 8);
 386                         view.UnionWith (new [] {1});
 387                 }
 388
 389                 [Test, ExpectedException (typeof (ArgumentNullException))]
 390                 public void ExceptWith_Null ()
 391                 {
 392                         var set = new SortedSet<int> ();
 393                         set.ExceptWith (null);
 394                 }
 395
 396                 [Test]
 397                 public void ExceptWith ()
 398                 {
 399                         var set = new SortedSet<int> { 1, 3, 5, 7, 9 };
 400                         set.ExceptWith (new [] { 5, 7, 3, 7, 11, 7, 5, 2 });
 401                         Assert.IsTrue (set.SequenceEqual (new [] { 1, 9 }));
 402                 }
 403
 404                 [Test]
 405                 public void ExceptWithItself ()
 406                 {
 407                         var set = new SortedSet<int> (new [] { 1, 5 });
 408                         set.ExceptWith (set);
 409                         Assert.AreEqual (0, set.Count);
 410                 }
 411
 412                 [Test]
 413                 public void ViewExceptWith ()
 414                 {
 415                         var set = new SortedSet<int> { 1, 3, 5, 7, 9 };
 416                         var view = set.GetViewBetween (4, 8);
 417                         view.ExceptWith (new [] { 4, 5, 6, 6, 4 });
 418                         Assert.IsTrue (view.SequenceEqual (new [] { 7 }));
 419                         Assert.IsTrue (set.SequenceEqual (new [] { 1, 3, 7, 9 }));
 420                         view.ExceptWith (new [] { 1, 2 });
 421                         Assert.IsTrue (view.SequenceEqual (new [] { 7 }));
 422                         Assert.IsTrue (set.SequenceEqual (new [] { 1, 3, 7, 9 }));
 423                 }
 424
 425                 [Test, ExpectedException (typeof (ArgumentNullException))]
 426                 public void SymmetricExceptWith_Null ()
 427                 {
 428                         var set = new SortedSet<int> ();
 429                         set.SymmetricExceptWith (null);
 430                 }
 431
 432                 [Test]
 433                 public void SymmetricExceptWith ()
 434                 {
 435                         var set = new SortedSet<int> { 1, 3, 5, 7, 9 };
 436                         set.SymmetricExceptWith (new [] { 5, 7, 3, 7, 11, 7, 5, 2 });
 437                         Assert.IsTrue (set.SequenceEqual (new [] { 1, 2, 9, 11 }));
 438                 }
 439
 440                 [Test]
 441                 public void SymetricExceptWithItself ()
 442                 {
 443                         var set = new SortedSet<int> (new [] { 1, 5 });
 444                         set.SymmetricExceptWith (set);
 445                         Assert.AreEqual (0, set.Count);
 446                 }
 447
 448                 [Test]
 449                 public void ViewSymmetricExceptWith ()
 450                 {
 451                         var set = new SortedSet<int> { 1, 3, 5, 7, 9 };
 452                         var view = set.GetViewBetween (4, 8);
 453                         view.SymmetricExceptWith (new [] { 4, 5, 6, 6, 4 });
 454                         Assert.IsTrue (view.SequenceEqual (new [] { 4, 6, 7 }));
 455                         Assert.IsTrue (set.SequenceEqual (new [] { 1, 3, 4, 6, 7, 9 }));
 456                 }
 457
 458                 [Test, ExpectedException (typeof (ArgumentOutOfRangeException))]
 459                 public void ViewSymmetricExceptWith_oor ()
 460                 {
 461                         var set = new SortedSet<int> { 1, 3, 5, 7, 9 };
 462                         var view = set.GetViewBetween (4, 8);
 463                         view.SymmetricExceptWith (new [] {2});
 464                 }
 465
 466                 void do_test_e (SortedSet<int> s1, IEnumerable<int> s2, bool o, bool se = false, bool psb = false, bool psu = false)
 467                 {
 468                         bool sb = false, su = false;
 469                         if (se)
 470                                 sb = su = true;
 471                         if (psb)
 472                                 sb = true;
 473                         if (psu)
 474                                 su = true;
 475
 476                         Assert.IsTrue (!su || !psb);
 477                         Assert.IsTrue (!sb || !psu);
 478
 479                         // actual tests
 480                         Assert.AreEqual (o, s1.Overlaps (s2));
 481                         Assert.AreEqual (se, s1.SetEquals (s2));
 482                         Assert.AreEqual (sb, s1.IsSubsetOf (s2));
 483                         Assert.AreEqual (su, s1.IsSupersetOf (s2));
 484                         Assert.AreEqual (psb, s1.IsProperSubsetOf (s2));
 485                         Assert.AreEqual (psu, s1.IsProperSupersetOf (s2));
 486                 }
 487
 488                 void do_test (SortedSet<int> s1, SortedSet<int> s2, bool o = false, bool se = false, bool psb = false, bool psu = false)
 489                 {
 490                         if (s1.Count != 0 && s2.Count != 0 && (se || psb || psu))
 491                                 o = true;
 492                         do_test_e (s1, s2, o, se, psb, psu);
 493                         do_test_e (s2, s1, o, se, psu, psb);
 494                 }
 495
 496                 [Test]
 497                 public void TestSetCompares ()
 498                 {
 499                         var empty = new SortedSet<int> ();
 500                         var zero = new SortedSet<int> { 0 };
 501                         var one = new SortedSet<int> { 1 };
 502                         var two = new SortedSet<int> { 2 };
 503                         var bit = new SortedSet<int> { 0, 1 };
 504                         var trit = new SortedSet<int> { 0, 1, 2 };
 505                         var odds = new SortedSet<int> { 1, 3, 5, 7, 9 };
 506                         var evens = new SortedSet<int> { 2, 4, 6, 8 };
 507                         var digits = new SortedSet<int> { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
 508                         var squares = new SortedSet<int> { 0, 1, 4, 9 };
 509
 510                         var non_prime_odd_digit = odds.GetViewBetween (8, 42);
 511                         var non_trit = digits.GetViewBetween (3, 42);
 512
 513                         do_test (empty, empty, se: true);
 514                         do_test (empty, zero, psb: true);
 515                         do_test (empty, digits, psb: true);
 516                         do_test (zero, zero, se: true);
 517                         do_test (zero, one);
 518                         do_test (zero, bit, psb: true);
 519                         do_test (zero, trit, psb: true);
 520                         do_test (one, bit, psb: true);
 521                         do_test (one, trit, psb: true);
 522                         do_test (two, bit);
 523                         do_test (two, trit, psb: true);
 524                         do_test (odds, squares, o: true);
 525                         do_test (evens, squares, o: true);
 526                         do_test (odds, digits, psb: true);
 527                         do_test (evens, digits, psb: true);
 528                         do_test (squares, digits, psb: true);
 529                         do_test (digits, digits, se: true);
 530                         do_test_e (digits, squares.Concat (evens.Concat (odds)), o: true, se: true);
 531                         do_test (non_prime_odd_digit, digits, psb: true);
 532                         do_test_e (non_prime_odd_digit, new [] { 9 }, o: true, se: true);
 533                         do_test (non_trit, digits, psb: true);
 534 //                      do_test (trit, non_trit);
 535                         do_test_e (digits, trit.Concat (non_trit), o: true, se: true);
 536                         do_test_e (non_trit, new [] { 3, 4, 5, 6, 7, 8, 9 }, o: true, se: true);
 537                         do_test (digits.GetViewBetween (0, 2), trit, se: true);
 538                 }
 539         }
 540 }
 541