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 #if NET_4_0
  30
  31 using System;
  32 using System.Collections;
  33 using System.Collections.Generic;
  34 using System.Linq;
  35 using System.Runtime.Serialization;
  36
  37 using NUnit.Framework;
  38
  39 namespace MonoTests.System.Collections.Generic
  40 {
  41         [TestFixture]
  42         public class SortedSetTest
  43         {
  44                 [Test]
  45                 public void CtorNullComparer ()
  46                 {
  47                         var set = new SortedSet<int> ((IComparer<int>) null);
  48                         Assert.AreEqual (Comparer<int>.Default, set.Comparer);
  49                 }
  50
  51                 [Test]
  52                 [ExpectedException (typeof (ArgumentNullException))]
  53                 public void CtorNullCollection ()
  54                 {
  55                         new SortedSet<int> (null as IEnumerable<int>);
  56                 }
  57
  58                 [Test]
  59                 public void CtorDefault ()
  60                 {
  61                         var set = new SortedSet<int> ();
  62                         Assert.IsNotNull (set.Comparer);
  63                 }
  64
  65                 [Test]
  66                 public void Add ()
  67                 {
  68                         var set = new SortedSet<int> ();
  69                         Assert.AreEqual (0, set.Count);
  70                         Assert.IsTrue (set.Add (2));
  71                         Assert.IsTrue (set.Add (4));
  72                         Assert.IsTrue (set.Add (3));
  73                         Assert.AreEqual (3, set.Count);
  74                         Assert.IsFalse (set.Add (2));
  75                 }
  76
  77                 [Test]
  78                 public void Remove ()
  79                 {
  80                         var set = new SortedSet<int> ();
  81                         Assert.IsTrue (set.Add (2));
  82                         Assert.IsTrue (set.Add (4));
  83                         Assert.AreEqual (2, set.Count);
  84                         Assert.IsTrue (set.Remove (4));
  85                         Assert.IsTrue (set.Remove (2));
  86                         Assert.AreEqual (0, set.Count);
  87                         Assert.IsFalse (set.Remove (4));
  88                         Assert.IsFalse (set.Remove (2));
  89                 }
  90
  91                 [Test]
  92                 public void Clear ()
  93                 {
  94                         var set = new SortedSet<int> { 2, 3, 4, 5 };
  95                         Assert.AreEqual (4, set.Count);
  96                         set.Clear ();
  97                         Assert.AreEqual (0, set.Count);
  98                 }
  99
 100                 [Test]
 101                 public void Contains ()
 102                 {
 103                         var set = new SortedSet<int> { 2, 3, 4, 5 };
 104                         Assert.IsTrue (set.Contains (4));
 105                         Assert.IsFalse (set.Contains (7));
 106                 }
 107
 108                 [Test]
 109                 public void GetEnumerator ()
 110                 {
 111                         var set = new SortedSet<int> { 5, 3, 1, 2, 6, 4  };
 112                         Assert.IsTrue (set.SequenceEqual (new [] { 1, 2, 3, 4, 5, 6 }));
 113                 }
 114
 115                 [Test]
 116                 public void Reverse ()
 117                 {
 118                         var set = new SortedSet<int> { 5, 3, 1, 2, 6, 4  };
 119                         var reversed = set.Reverse ();
 120                         Assert.IsTrue (reversed.SequenceEqual (new [] { 6, 5, 4, 3, 2, 1 }));
 121                 }
 122
 123                 [Test]
 124                 public void RemoveWhere ()
 125                 {
 126                         var set = new SortedSet<int> { 1, 2, 3, 4, 5, 6 };
 127                         Assert.AreEqual (3, set.RemoveWhere (i => i % 2 == 0));
 128                         Assert.AreEqual (3, set.Count);
 129                         Assert.IsTrue (set.SequenceEqual (new [] { 1, 3, 5 }));
 130
 131                 }
 132
 133                 [Test]
 134                 public void Max ()
 135                 {
 136                         var set = new SortedSet<int> { 1, 3, 12, 9 };
 137                         Assert.AreEqual (12, set.Max);
 138                 }
 139
 140                 [Test]
 141                 public void Min ()
 142                 {
 143                         var set = new SortedSet<int> { 2, 3, 1, 9 };
 144                         Assert.AreEqual (1, set.Min);
 145                 }
 146
 147                 [Test]
 148                 [ExpectedException (typeof (ArgumentException))]
 149                 public void GetViewBetweenLowerBiggerThanUpper ()
 150                 {
 151                         var set = new SortedSet<int> { 1, 2, 3, 4, 5, 6 };
 152                         set.GetViewBetween (4, 2);
 153                 }
 154
 155                 [Test]
 156                 public void GetView ()
 157                 {
 158                         var set = new SortedSet<int> { 1, 3, 5, 7, 9 };
 159                         var view = set.GetViewBetween (3, 7);
 160
 161                         Assert.IsTrue (view.SequenceEqual (new [] { 3, 5, 7 }));
 162                 }
 163
 164                 [Test]
 165                 public void ViewAdd ()
 166                 {
 167                         var set = new SortedSet<int> { 1, 3, 5, 7 };
 168                         var view = set.GetViewBetween (3, 5);
 169
 170                         Assert.IsTrue (view.Add (4));
 171                         Assert.IsTrue (view.Contains (4));
 172                         Assert.IsTrue (set.Contains (4));
 173
 174                         Assert.IsFalse (view.Add (5));
 175                 }
 176
 177                 [Test]
 178                 [ExpectedException (typeof (ArgumentOutOfRangeException))]
 179                 public void ViewAddOutOfRange ()
 180                 {
 181                         var set = new SortedSet<int> { 1, 3, 5, 7 };
 182                         var view = set.GetViewBetween (3, 5);
 183
 184                         view.Add (7);
 185                 }
 186
 187                 [Test]
 188                 public void ViewContains ()
 189                 {
 190                         var set = new SortedSet<int> { 1, 3, 5, 7, 9 };
 191                         var view = set.GetViewBetween (3, 7);
 192
 193                         Assert.IsFalse (view.Contains (4));
 194                         Assert.IsTrue (view.Contains (3));
 195                         Assert.IsTrue (view.Contains (5));
 196                 }
 197
 198                 [Test]
 199                 public void ViewRemove ()
 200                 {
 201                         var set = new SortedSet<int> { 1, 3, 5, 7, 9 };
 202                         var view = set.GetViewBetween (3, 7);
 203
 204                         Assert.IsTrue (view.Remove (3));
 205                         Assert.IsFalse (view.Contains (3));
 206                         Assert.IsFalse (set.Contains (3));
 207                         Assert.IsFalse (view.Remove (9));
 208                         Assert.IsTrue (set.Contains (9));
 209                 }
 210
 211                 [Test]
 212                 public void ViewClear ()
 213                 {
 214                         var set = new SortedSet<int> { 1, 3, 5, 7, 9 };
 215                         var view = set.GetViewBetween (3, 7);
 216
 217                         view.Clear ();
 218
 219                         Assert.AreEqual (0, view.Count);
 220                         Assert.IsTrue (set.SequenceEqual (new [] { 1, 9 }));
 221                 }
 222
 223                 [Test]
 224                 [ExpectedException (typeof (ArgumentOutOfRangeException))]
 225                 public void ViewGetViewLowerOutOfRange ()
 226                 {
 227                         var set = new SortedSet<int> { 1, 3, 5, 7, 9 };
 228                         var view = set.GetViewBetween (3, 7);
 229                         view.GetViewBetween (2, 5);
 230                 }
 231
 232                 [Test]
 233                 [ExpectedException (typeof (ArgumentOutOfRangeException))]
 234                 public void ViewGetViewUpperOutOfRange ()
 235                 {
 236                         var set = new SortedSet<int> { 1, 3, 5, 7, 9 };
 237                         var view = set.GetViewBetween (3, 7);
 238                         view.GetViewBetween (5, 9);
 239                 }
 240
 241                 [Test]
 242                 public void ViewGetView ()
 243                 {
 244                         var set = new SortedSet<int> { 1, 3, 5, 7, 9 };
 245                         var view = set.GetViewBetween (3, 7);
 246                         view = view.GetViewBetween (4, 6);
 247
 248                         Assert.IsTrue (view.SequenceEqual (new [] { 5 }));
 249                 }
 250
 251                 void EmptySubView (SortedSet<int> set)
 252                 {
 253                         var view = set.GetViewBetween (-20, -15);
 254                         Assert.AreEqual (0, view.Count);
 255                         Assert.AreEqual (0, view.Min);
 256                         Assert.AreEqual (0, view.Max);
 257
 258                         view = set.GetViewBetween (15, 20);
 259                         Assert.AreEqual (0, view.Count);
 260                         Assert.AreEqual (0, view.Min);
 261                         Assert.AreEqual (0, view.Max);
 262                 }
 263
 264                 [Test]
 265                 public void EmptySubView ()
 266                 {
 267                         EmptySubView (new SortedSet<int> ());
 268                         EmptySubView (new SortedSet<int> { 1, 3, 5, 7, 9 });
 269                         EmptySubView (new SortedSet<int> { -40, 40 });
 270                         EmptySubView (new SortedSet<int> { -40, -10, 10, 40 });
 271                 }
 272
 273                 [Test]
 274                 public void ViewMin ()
 275                 {
 276                         var set = new SortedSet<int> { 1, 3, 5, 7, 9 };
 277
 278                         var view = set.GetViewBetween (4, 8);
 279                         Assert.AreEqual (5, view.Min);
 280
 281                         view = set.GetViewBetween (-2, 4);
 282                         Assert.AreEqual (1, view.Min);
 283
 284                         view = set.GetViewBetween (1, 9);
 285                         Assert.AreEqual (1, view.Min);
 286                 }
 287
 288                 [Test]
 289                 public void ViewMax ()
 290                 {
 291                         var set = new SortedSet<int> { 1, 3, 5, 7, 9 };
 292
 293                         var view = set.GetViewBetween (4, 8);
 294                         Assert.AreEqual (7, view.Max);
 295
 296                         view = set.GetViewBetween (4, 55);
 297                         Assert.AreEqual (9, view.Max);
 298
 299                         view = set.GetViewBetween (1, 9);
 300                         Assert.AreEqual (9, view.Max);
 301                 }
 302
 303                 [Test]
 304                 public void ViewCount ()
 305                 {
 306                         var set = new SortedSet<int> { 1, 3, 4, 5, 6, 7, 8, 9 };
 307                         var view = set.GetViewBetween (4, 8);
 308
 309                         Assert.AreEqual (5, view.Count);
 310                         set.Remove (5);
 311                         Assert.AreEqual (4, view.Count);
 312                         set.Add (10);
 313                         Assert.AreEqual (4, view.Count);
 314                         set.Add (6);
 315                         Assert.AreEqual (4, view.Count);
 316                         set.Add (5);
 317                         Assert.AreEqual (5, view.Count);
 318                 }
 319
 320                 [Test, ExpectedException (typeof (ArgumentNullException))]
 321                 public void IntersectWith_Null ()
 322                 {
 323                         var set = new SortedSet<int> ();
 324                         set.IntersectWith (null);
 325                 }
 326
 327                 [Test]
 328                 public void IntersectWith ()
 329                 {
 330                         var set = new SortedSet<int> { 1, 3, 5, 7, 9 };
 331                         set.IntersectWith (new [] { 5, 7, 3, 7, 11, 7, 5, 2 });
 332                         Assert.IsTrue (set.SequenceEqual (new [] { 3, 5, 7 }));
 333                 }
 334
 335                 [Test]
 336                 public void ViewIntersectWith ()
 337                 {
 338                         var set = new SortedSet<int> { 1, 3, 5, 7, 9 };
 339                         var view = set.GetViewBetween (4, 8);
 340                         view.IntersectWith (new [] { 1, 5, 9 });
 341                         Assert.IsTrue (view.SequenceEqual (new [] { 5 }));
 342                         Assert.IsTrue (set.SequenceEqual (new [] { 1, 3, 5, 9 }));
 343                         view.IntersectWith (new [] { 1, 2 });
 344                         Assert.IsTrue (view.SequenceEqual (new int [] {}));
 345                         Assert.IsTrue (set.SequenceEqual (new [] { 1, 3, 9 }));
 346                 }
 347
 348                 [Test, ExpectedException (typeof (ArgumentNullException))]
 349                 public void UnionWith_Null ()
 350                 {
 351                         var set = new SortedSet<int> ();
 352                         set.UnionWith (null);
 353                 }
 354
 355                 [Test]
 356                 public void UnionWith ()
 357                 {
 358                         var set = new SortedSet<int> { 1, 3, 5, 7, 9 };
 359                         set.UnionWith (new [] { 5, 7, 3, 7, 11, 7, 5, 2 });
 360                         Assert.IsTrue (set.SequenceEqual (new [] { 1, 2, 3, 5, 7, 9, 11 }));
 361                 }
 362
 363                 [Test]
 364                 public void ViewUnionWith ()
 365                 {
 366                         var set = new SortedSet<int> { 1, 3, 5, 7, 9 };
 367                         var view = set.GetViewBetween (4, 8);
 368                         view.UnionWith (new [] { 4, 5, 6, 6, 4 });
 369                         Assert.IsTrue (view.SequenceEqual (new [] { 4, 5, 6, 7 }));
 370                         Assert.IsTrue (set.SequenceEqual (new [] { 1, 3, 4, 5, 6, 7, 9 }));
 371                 }
 372
 373                 [Test, ExpectedException (typeof (ArgumentOutOfRangeException))]
 374                 public void ViewUnionWith_oor ()
 375                 {
 376                         var set = new SortedSet<int> { 1, 3, 5, 7, 9 };
 377                         var view = set.GetViewBetween (4, 8);
 378                         view.UnionWith (new [] {1});
 379                 }
 380
 381                 [Test, ExpectedException (typeof (ArgumentNullException))]
 382                 public void ExceptWith_Null ()
 383                 {
 384                         var set = new SortedSet<int> ();
 385                         set.ExceptWith (null);
 386                 }
 387
 388                 [Test]
 389                 public void ExceptWith ()
 390                 {
 391                         var set = new SortedSet<int> { 1, 3, 5, 7, 9 };
 392                         set.ExceptWith (new [] { 5, 7, 3, 7, 11, 7, 5, 2 });
 393                         Assert.IsTrue (set.SequenceEqual (new [] { 1, 9 }));
 394                 }
 395
 396                 [Test]
 397                 public void ViewExceptWith ()
 398                 {
 399                         var set = new SortedSet<int> { 1, 3, 5, 7, 9 };
 400                         var view = set.GetViewBetween (4, 8);
 401                         view.ExceptWith (new [] { 4, 5, 6, 6, 4 });
 402                         Assert.IsTrue (view.SequenceEqual (new [] { 7 }));
 403                         Assert.IsTrue (set.SequenceEqual (new [] { 1, 3, 7, 9 }));
 404                         view.ExceptWith (new [] { 1, 2 });
 405                         Assert.IsTrue (view.SequenceEqual (new [] { 7 }));
 406                         Assert.IsTrue (set.SequenceEqual (new [] { 1, 3, 7, 9 }));
 407                 }
 408
 409                 [Test, ExpectedException (typeof (ArgumentNullException))]
 410                 public void SymmetricExceptWith_Null ()
 411                 {
 412                         var set = new SortedSet<int> ();
 413                         set.SymmetricExceptWith (null);
 414                 }
 415
 416                 [Test]
 417                 public void SymmetricExceptWith ()
 418                 {
 419                         var set = new SortedSet<int> { 1, 3, 5, 7, 9 };
 420                         set.SymmetricExceptWith (new [] { 5, 7, 3, 7, 11, 7, 5, 2 });
 421                         Assert.IsTrue (set.SequenceEqual (new [] { 1, 2, 9, 11 }));
 422                 }
 423
 424                 [Test]
 425                 public void ViewSymmetricExceptWith ()
 426                 {
 427                         var set = new SortedSet<int> { 1, 3, 5, 7, 9 };
 428                         var view = set.GetViewBetween (4, 8);
 429                         view.SymmetricExceptWith (new [] { 4, 5, 6, 6, 4 });
 430                         Assert.IsTrue (view.SequenceEqual (new [] { 4, 6, 7 }));
 431                         Assert.IsTrue (set.SequenceEqual (new [] { 1, 3, 4, 6, 7, 9 }));
 432                 }
 433
 434                 [Test, ExpectedException (typeof (ArgumentOutOfRangeException))]
 435                 public void ViewSymmetricExceptWith_oor ()
 436                 {
 437                         var set = new SortedSet<int> { 1, 3, 5, 7, 9 };
 438                         var view = set.GetViewBetween (4, 8);
 439                         view.SymmetricExceptWith (new [] {2});
 440                 }
 441
 442                 void do_test_e (SortedSet<int> s1, IEnumerable<int> s2, bool o, bool se = false, bool psb = false, bool psu = false)
 443                 {
 444                         bool sb = false, su = false;
 445                         if (se)
 446                                 sb = su = true;
 447                         if (psb)
 448                                 sb = true;
 449                         if (psu)
 450                                 su = true;
 451
 452                         Assert.IsTrue (!su || !psb);
 453                         Assert.IsTrue (!sb || !psu);
 454
 455                         // actual tests
 456                         Assert.AreEqual (o, s1.Overlaps (s2));
 457                         Assert.AreEqual (se, s1.SetEquals (s2));
 458                         Assert.AreEqual (sb, s1.IsSubsetOf (s2));
 459                         Assert.AreEqual (su, s1.IsSupersetOf (s2));
 460                         Assert.AreEqual (psb, s1.IsProperSubsetOf (s2));
 461                         Assert.AreEqual (psu, s1.IsProperSupersetOf (s2));
 462                 }
 463
 464                 void do_test (SortedSet<int> s1, SortedSet<int> s2, bool o = false, bool se = false, bool psb = false, bool psu = false)
 465                 {
 466                         if (s1.Count != 0 && s2.Count != 0 && (se || psb || psu))
 467                                 o = true;
 468                         do_test_e (s1, s2, o, se, psb, psu);
 469                         do_test_e (s2, s1, o, se, psu, psb);
 470                 }
 471
 472                 [Test]
 473                 public void TestSetCompares ()
 474                 {
 475                         var empty = new SortedSet<int> ();
 476                         var zero = new SortedSet<int> { 0 };
 477                         var one = new SortedSet<int> { 1 };
 478                         var two = new SortedSet<int> { 2 };
 479                         var bit = new SortedSet<int> { 0, 1 };
 480                         var trit = new SortedSet<int> { 0, 1, 2 };
 481                         var odds = new SortedSet<int> { 1, 3, 5, 7, 9 };
 482                         var evens = new SortedSet<int> { 2, 4, 6, 8 };
 483                         var digits = new SortedSet<int> { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
 484                         var squares = new SortedSet<int> { 0, 1, 4, 9 };
 485
 486                         var non_prime_odd_digit = odds.GetViewBetween (8, 42);
 487                         var non_trit = digits.GetViewBetween (3, 42);
 488
 489                         do_test (empty, empty, se: true);
 490                         do_test (empty, zero, psb: true);
 491                         do_test (empty, digits, psb: true);
 492                         do_test (zero, zero, se: true);
 493                         do_test (zero, one);
 494                         do_test (zero, bit, psb: true);
 495                         do_test (zero, trit, psb: true);
 496                         do_test (one, bit, psb: true);
 497                         do_test (one, trit, psb: true);
 498                         do_test (two, bit);
 499                         do_test (two, trit, psb: true);
 500                         do_test (odds, squares, o: true);
 501                         do_test (evens, squares, o: true);
 502                         do_test (odds, digits, psb: true);
 503                         do_test (evens, digits, psb: true);
 504                         do_test (squares, digits, psb: true);
 505                         do_test (digits, digits, se: true);
 506                         do_test_e (digits, squares.Concat (evens.Concat (odds)), o: true, se: true);
 507                         do_test (non_prime_odd_digit, digits, psb: true);
 508                         do_test_e (non_prime_odd_digit, new [] { 9 }, o: true, se: true);
 509                         do_test (non_trit, digits, psb: true);
 510                         do_test (trit, non_trit);
 511                         do_test_e (digits, trit.Concat (non_trit), o: true, se: true);
 512                         do_test_e (non_trit, new [] { 3, 4, 5, 6, 7, 8, 9 }, o: true, se: true);
 513                         do_test (digits.GetViewBetween (0, 2), trit, se: true);
 514                 }
 515         }
 516 }
 517
 518 #endif