mcs/class/System.Core/Test/System.Collections.Generic/HashSetTest.cs

   1 //
   2 // HashSetTest.cs
   3 //
   4 // Authors:
   5 //  Jb Evain  <jbevain@novell.com>
   6 //
   7 // Copyright (C) 2007 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 using System;
  30 using System.Collections;
  31 using System.Collections.Generic;
  32 using System.Linq;
  33
  34 using NUnit.Framework;
  35
  36 namespace MonoTests.System.Collections.Generic {
  37
  38         [TestFixture]
  39         public class HashSetTest {
  40
  41                 [Test]
  42                 public void TestAdd ()
  43                 {
  44                         var set = new HashSet<int> ();
  45
  46                         Assert.IsTrue (set.Add (1));
  47                         Assert.IsTrue (set.Add (2));
  48                         Assert.IsTrue (set.Add (3));
  49                         Assert.IsTrue (set.Add (4));
  50                         Assert.IsFalse (set.Add (4));
  51                         Assert.IsFalse (set.Add (3));
  52                         Assert.IsFalse (set.Add (2));
  53                         Assert.IsFalse (set.Add (1));
  54                         Assert.IsTrue (set.Add (0));
  55                         Assert.IsFalse (set.Add (0));
  56                 }
  57
  58                 [Test]
  59                 public void TestRemove ()
  60                 {
  61                         var set = new HashSet<int> ();
  62
  63                         Assert.IsTrue (set.Add (1));
  64                         Assert.IsTrue (set.Add (2));
  65                         Assert.IsTrue (set.Add (3));
  66                         Assert.IsTrue (set.Add (4));
  67
  68                         Assert.IsTrue (set.Remove (2));
  69                         Assert.IsTrue (set.Remove (3));
  70
  71                         AssertContainsOnly (new int [] {1, 4}, set);
  72                 }
  73
  74                 [Test]
  75                 public void TestMassiveAdd ()
  76                 {
  77                         var set = new HashSet<int> ();
  78
  79                         var massive = Enumerable.Range (0, 10000).ToArray ();
  80                         foreach (var item in massive)
  81                                 Assert.IsTrue (set.Add (item));
  82
  83                         AssertContainsOnly (massive, set);
  84                 }
  85
  86                 [Test]
  87                 public void TestMassiveRemove ()
  88                 {
  89                         var massive = Enumerable.Range (0, 10000).ToArray ();
  90                         var set = new HashSet<int> (massive);
  91
  92                         foreach (var item in massive)
  93                                 Assert.IsTrue (set.Remove (item));
  94
  95                         AssertIsEmpty (set);
  96                 }
  97
  98                 [Test]
  99                 public void TestCopyTo ()
 100                 {
 101                         var data = new [] {1, 2, 3, 4, 5};
 102                         var set = new HashSet<int> (data);
 103
 104                         var array = new int [set.Count];
 105                         set.CopyTo (array, 0);
 106
 107                         AssertContainsOnly (data, array);
 108                 }
 109
 110                 [Test]
 111                 public void TestClear ()
 112                 {
 113                         var data = new [] {1, 2, 3, 4, 5, 6};
 114                         var set = new HashSet<int> (data);
 115
 116                         Assert.AreEqual (data.Length, set.Count);
 117                         set.Clear ();
 118                         AssertIsEmpty (set);
 119                 }
 120
 121                 [Test]
 122                 public void TestContains ()
 123                 {
 124                         var data = new [] {1, 2, 3, 4, 5, 6};
 125                         var set = new HashSet<int> (data);
 126
 127                         foreach (var item in data)
 128                                 Assert.IsTrue (set.Contains (item));
 129                 }
 130
 131                 [Test, ExpectedException (typeof (InvalidOperationException))]
 132                 public void TestModifySetWhileForeach ()
 133                 {
 134                         var set = new HashSet<int> (new [] {1, 2, 3, 4});
 135                         foreach (var item in set)
 136                                 set.Add (item + 2);
 137                 }
 138
 139                 [Test]
 140                 public void TestRemoveWhere ()
 141                 {
 142                         var data = new [] {1, 2, 3, 4, 5, 6, 7, 8, 9};
 143                         var result = new [] {2, 4, 6, 8};
 144
 145                         var set = new HashSet<int> (data);
 146                         int removed = set.RemoveWhere (i => (i % 2) != 0);
 147
 148                         Assert.AreEqual (data.Length - result.Length, removed);
 149                         AssertContainsOnly (result, set);
 150                 }
 151
 152                 [Test]
 153                 public void TestOverlaps ()
 154                 {
 155                         var set = new HashSet<int> (new [] {1, 2, 3, 4, 5});
 156
 157                         Assert.IsTrue (set.Overlaps (new [] {0, 2}));
 158                 }
 159
 160                 [Test]
 161                 public void TestIntersectWith ()
 162                 {
 163                         var data = new [] {1, 2, 3, 4};
 164                         var other = new [] {2, 4, 5, 6};
 165                         var result = new [] {2, 4};
 166
 167                         var set = new HashSet<int> (data);
 168
 169                         set.IntersectWith (other);
 170
 171                         AssertContainsOnly (result, set);
 172                 }
 173
 174                 [Test]
 175                 public void TestIntersectWithComparer ()
 176                 {
 177                         var data = new[] {"a", "b", "C", "d", "E"};
 178                         var other = new[] {"a", "B", "e"};
 179                         var result = new[] {"a", "b", "E"};
 180
 181                         var set = new HashSet<string> (data, StringComparer.OrdinalIgnoreCase);
 182
 183                         set.IntersectWith (other);
 184
 185                         AssertContainsOnly (result, set);
 186                 }
 187
 188                 [Test]
 189                 public void TestExceptWith ()
 190                 {
 191                         var data = new [] {1, 2, 3, 4, 5, 6};
 192                         var other = new [] {2, 4, 6};
 193                         var result = new [] {1, 3, 5};
 194                         var set = new HashSet<int> (data);
 195
 196                         set.ExceptWith (other);
 197
 198                         AssertContainsOnly (result, set);
 199                 }
 200
 201                 [Test]
 202                 public void TestUnionWith ()
 203                 {
 204                         var data = new [] {1, 2, 3, 4, 5, 6};
 205                         var other = new [] {4, 5, 6, 7, 8, 9};
 206                         var result = new [] {1, 2, 3, 4, 5, 6, 7, 8, 9};
 207
 208                         var set = new HashSet<int> (data);
 209                         set.UnionWith (other);
 210
 211                         AssertContainsOnly (result, set);
 212                 }
 213
 214                 [Test]
 215                 public void TestSymmetricExceptWith ()
 216                 {
 217                         var data = new [] {1, 2, 3, 4, 5};
 218                         var other = new [] {4, 5, 6, 7, 8, 9, 9};
 219                         var result = new [] {1, 2, 3, 6, 7, 8, 9};
 220
 221                         var set = new HashSet<int> (data);
 222                         set.SymmetricExceptWith (other);
 223
 224                         AssertContainsOnly (result, set);
 225                 }
 226
 227                 [Test]
 228                 public void TestEmptyHashSubsetOf ()
 229                 {
 230                         var set = new HashSet<int> ();
 231
 232                         Assert.IsTrue (set.IsSubsetOf (new int [0]));
 233                         Assert.IsTrue (set.IsSubsetOf (new [] {1, 2}));
 234                 }
 235
 236                 [Test]
 237                 public void TestSubsetOf ()
 238                 {
 239                         var data = new [] {1, 2, 3};
 240                         var other = new [] {1, 2, 3, 4, 5};
 241                         var other2 = new [] {1, 2, 3};
 242                         var other3 = new [] {0, 1, 2};
 243
 244                         var set = new HashSet<int> (data);
 245
 246                         Assert.IsTrue (set.IsSubsetOf (other));
 247                         Assert.IsTrue (set.IsSubsetOf (other2));
 248                         Assert.IsFalse (set.IsSubsetOf (other3));
 249                 }
 250
 251                 [Test]
 252                 public void TestSubsetOfComparer ()
 253                 {
 254                         var data = new[] { "abc", "DF", "gHIl" };
 255
 256                         var other1 = new[] { "pqR", "ABC", "ghil", "dF", "lmn" };
 257
 258                         var set = new HashSet<string> (data, StringComparer.OrdinalIgnoreCase);
 259
 260                         Assert.IsTrue (set.IsSubsetOf (other1));
 261                 }
 262
 263                 [Test]
 264                 public void TestProperSubsetOf ()
 265                 {
 266                         var data = new [] {1, 2, 3};
 267                         var other = new [] {1, 2, 3, 4, 5};
 268                         var other2 = new [] {1, 2, 3};
 269                         var other3 = new [] {0, 1, 2};
 270
 271                         var set = new HashSet<int> (data);
 272
 273                         Assert.IsTrue (set.IsProperSubsetOf (other));
 274                         Assert.IsFalse (set.IsProperSubsetOf (other2));
 275                         Assert.IsFalse (set.IsProperSubsetOf (other3));
 276                 }
 277
 278                 [Test]
 279                 public void TestProperSubsetOfComparer ()
 280                 {
 281                         var data = new[] { "abc", "DF", "gHIl" };
 282
 283                         var other1 = new[] { "pqR", "ABC", "ghil", "dF", "lmn" };
 284
 285                         var set = new HashSet<string> (data, StringComparer.OrdinalIgnoreCase);
 286
 287                         Assert.IsTrue (set.IsProperSubsetOf (other1));
 288                 }
 289
 290                 [Test]
 291                 public void TestSupersetOf ()
 292                 {
 293                         var data = new [] {1, 2, 3, 4, 5};
 294                         var other = new [] {2, 3, 4};
 295                         var other2 = new [] {1, 2, 3, 4, 5};
 296                         var other3 = new [] {4, 5, 6};
 297
 298                         var set = new HashSet<int> (data);
 299
 300                         Assert.IsTrue (set.IsSupersetOf (other));
 301                         Assert.IsTrue (set.IsSupersetOf (other2));
 302                         Assert.IsFalse (set.IsSupersetOf (other3));
 303                 }
 304
 305                 [Test]
 306                 public void TestSupersetOfComparer ()
 307                 {
 308                         var data = new[] {"a", "B", "c", "D"};
 309
 310                         var other1 = new[] {"A", "a", "C", "c"};
 311                         var other2 = new[] {"A", "a", "B", "D", "C", "c"};
 312
 313                         var set = new HashSet<string> (data, StringComparer.OrdinalIgnoreCase);
 314
 315                         Assert.IsTrue (set.IsSupersetOf (other1));
 316                         Assert.IsTrue (set.IsSupersetOf (other2));
 317                 }
 318
 319                 [Test]
 320                 public void TestProperSupersetOf ()
 321                 {
 322                         var data = new [] {1, 2, 3, 4, 5};
 323                         var other = new [] {2, 3, 4};
 324                         var other2 = new [] {1, 2, 3, 4, 5};
 325                         var other3 = new [] {4, 5, 6};
 326
 327                         var set = new HashSet<int> (data);
 328
 329                         Assert.IsTrue (set.IsProperSupersetOf (other));
 330                         Assert.IsFalse (set.IsProperSupersetOf (other2));
 331                         Assert.IsFalse (set.IsProperSupersetOf (other3));
 332                 }
 333
 334                 [Test]
 335                 public void TestProperSupersetOfComparer ()
 336                 {
 337                         var data = new[] { "a", "B", "c", "D" };
 338
 339                         var other1 = new[] { "A", "a", "d", "D" };
 340                         var other2 = new[] { "A", "a", "B", "D", "C", "c" };
 341
 342                         var set = new HashSet<string> (data, StringComparer.OrdinalIgnoreCase);
 343
 344                         Assert.IsTrue (set.IsProperSupersetOf (other1));
 345                         Assert.IsFalse (set.IsProperSupersetOf (other2));
 346                 }
 347
 348                 [Test]
 349                 public void TestSetEquals ()
 350                 {
 351                         var data = new [] {1, 2, 3, 4};
 352
 353                         var other = new [] {1, 2, 3, 4};
 354                         var other2 = new [] {1, 2, 2, 4};
 355                         var other3 = new [] {1, 2};
 356                         var other4 = new [] {1, 2, 3, 4, 5};
 357                         var other5 = new [] {1, 1, 1, 1};
 358
 359                         var set = new HashSet<int> (data);
 360
 361                         Assert.IsTrue (set.SetEquals (other));
 362                         Assert.IsFalse (set.SetEquals (other2));
 363                         Assert.IsFalse (set.SetEquals (other3));
 364                         Assert.IsFalse (set.SetEquals (other4));
 365                         Assert.IsFalse (set.SetEquals (other5));
 366                 }
 367
 368                 [Test]
 369                 public void TestSetEqualsComparer ()
 370                 {
 371                         var data = new[] { "abc", "DF", "gHIl" };
 372
 373                         var other1 = new[] { "ABC", "DF", "GHIL" };
 374                         var other2 = new[] { "ABC", "aBc", "DF", "GHIL", "ghil" };
 375
 376                         var set = new HashSet<string>(data, StringComparer.OrdinalIgnoreCase);
 377
 378                         Assert.IsTrue (set.SetEquals (other1));
 379                         Assert.IsTrue (set.SetEquals (other2));
 380                 }
 381
 382                 [Test]
 383                 public void TestCopyToFull ()
 384                 {
 385                         var data = new [] {1, 2, 3, 4};
 386
 387                         var set = new HashSet<int> (data);
 388
 389                         var res = new int [set.Count];
 390                         set.CopyTo (res, 0);
 391
 392                         AssertContainsOnly (res, data);
 393                 }
 394
 395                 [Test]
 396                 public void TestCopyToEmpty ()
 397                 {
 398                         var set = new HashSet<int> ();
 399
 400                         var res = new int [0];
 401                         set.CopyTo (res, 0);
 402                 }
 403
 404                 [Test]
 405                 public void TestCopyToPrecise ()
 406                 {
 407                         var set = new HashSet<int> ();
 408                         set.Add (42);
 409
 410                         var dest = new int [12];
 411
 412                         set.CopyTo (dest, 6, 1);
 413
 414                         Assert.AreEqual (42, dest [6]);
 415                 }
 416
 417                 [Test]
 418                 public void TestICollection ()
 419                 {
 420                         var set = new HashSet<int> () as ICollection<int>;
 421                         set.Add (42);
 422                         set.Add (42);
 423
 424                         Assert.AreEqual (1, set.Count);
 425                 }
 426
 427                 [Test]
 428                 public void TestHashSetEqualityComparer ()
 429                 {
 430                         var data = new string[] { "foo", "bar", "foobar" };
 431                         var set1 = new HashSet<string> (data, StringComparer.Ordinal);
 432                         var set2 = new HashSet<string> (data, StringComparer.OrdinalIgnoreCase);
 433
 434                         var comparer = HashSet<string>.CreateSetComparer ();
 435                         Assert.IsTrue (comparer.Equals (set1, set1));
 436                         Assert.IsTrue (comparer.Equals (set1, set2));
 437                         Assert.AreEqual (comparer.GetHashCode (set1), comparer.GetHashCode (set2));
 438
 439                         var set3 = new HashSet<string> (new [] { "foobar", "foo", "bar" });
 440                         Assert.IsTrue (comparer.Equals (set1, set3));
 441                         Assert.AreEqual (comparer.GetHashCode (set1), comparer.GetHashCode (set3));
 442
 443                         var set4 = new HashSet<string> (new [] { "oh", "hai", "folks" });
 444                         Assert.IsFalse (comparer.Equals (set2, set4));
 445                         Assert.AreNotEqual (comparer.GetHashCode (set2), comparer.GetHashCode (set4));
 446
 447                         Assert.IsTrue (comparer.Equals (null, null));
 448                         Assert.AreEqual (0, comparer.GetHashCode (null));
 449                         Assert.IsFalse (comparer.Equals (set1, null));
 450                 }
 451
 452                 static void AssertContainsOnly<T> (IEnumerable<T> result, IEnumerable<T> data)
 453                 {
 454                         Assert.AreEqual (result.Count (), data.Count ());
 455
 456                         var store = new List<T> (result);
 457                         foreach (var element in data) {
 458                                 Assert.IsTrue (store.Contains (element));
 459                                 store.Remove (element);
 460                         }
 461
 462                         AssertIsEmpty (store);
 463                 }
 464
 465                 static void AssertIsEmpty<T> (IEnumerable<T> source)
 466                 {
 467                         Assert.AreEqual (0, source.Count ());
 468                 }
 469
 470
 471                 delegate void D ();
 472                 bool Throws (D d)
 473                 {
 474                         try {
 475                                 d ();
 476                                 return false;
 477                         } catch {
 478                                 return true;
 479                         }
 480                 }
 481
 482                 [Test]
 483                 // based on #491858, #517415
 484                 public void Enumerator_Current ()
 485                 {
 486 #pragma warning disable 0168
 487                         var e1 = new HashSet<int>.Enumerator ();
 488                         Assert.IsFalse (Throws (delegate { var x = e1.Current; }));
 489
 490                         var d = new HashSet<int> ();
 491                         var e2 = d.GetEnumerator ();
 492                         Assert.IsFalse (Throws (delegate { var x = e2.Current; }));
 493                         e2.MoveNext ();
 494                         Assert.IsFalse (Throws (delegate { var x = e2.Current; }));
 495                         e2.Dispose ();
 496                         Assert.IsFalse (Throws (delegate { var x = e2.Current; }));
 497
 498                         var e3 = ((IEnumerable<int>) d).GetEnumerator ();
 499                         Assert.IsFalse (Throws (delegate { var x = e3.Current; }));
 500                         e3.MoveNext ();
 501                         Assert.IsFalse (Throws (delegate { var x = e3.Current; }));
 502                         e3.Dispose ();
 503                         Assert.IsFalse (Throws (delegate { var x = e3.Current; }));
 504
 505                         var e4 = ((IEnumerable) d).GetEnumerator ();
 506                         Assert.IsTrue (Throws (delegate { var x = e4.Current; }));
 507                         e4.MoveNext ();
 508                         Assert.IsTrue (Throws (delegate { var x = e4.Current; }));
 509                         ((IDisposable) e4).Dispose ();
 510                         Assert.IsTrue (Throws (delegate { var x = e4.Current; }));
 511 #pragma warning restore 0168
 512                 }
 513
 514                 [Test]
 515                 public void TestNullsWithComparerThrowingException ()
 516                 {
 517                         // NOTE: We should get the same errors when using StringComparer.Ordinal on Mono 2.6.1, but the look-alike gives us more control over this test case
 518                         var set = new HashSet<string> (new StringComparerOrdinalLookAlike ());
 519                         Assert.IsTrue (set.Add (string.Empty), "#1a");
 520                         Assert.IsFalse (set.Contains (null), "#2a");
 521                         Assert.IsTrue (set.Add (null), "#2b");
 522                         Assert.IsTrue (set.Contains (null), "#2c");
 523                         Assert.AreEqual (2, set.Count, "#3");
 524                         Assert.IsTrue (set.Add ("a"), "#4");
 525                         AssertContainsOnly (new string [] { string.Empty, null, "a" }, set);
 526                         Assert.IsFalse (set.Add (null), "#5");
 527                         Assert.IsTrue (set.Add ("b"), "#6");
 528                         Assert.IsFalse (set.Add ("b"), "#7");
 529                         Assert.IsFalse (set.Add (string.Empty), "#8");
 530                         Assert.IsFalse (set.Add ("a"), "#9");
 531                         Assert.IsFalse (set.Add (null), "#10");
 532                         Assert.IsTrue (set.Add ("c"), "#11");
 533                         Assert.IsFalse (set.Add ("c"), "#12");
 534                         Assert.AreEqual (5, set.Count, "#13");
 535                         Assert.IsTrue (set.Remove (null), "#14");
 536                         Assert.IsTrue (set.Remove ("b"), "#15");
 537                         Assert.IsFalse (set.Remove (null), "#16");
 538                         Assert.AreEqual (3, set.Count, "#17");
 539                         AssertContainsOnly (new string [] { string.Empty, "a", "c" }, set);
 540                 }
 541
 542                 private class StringComparerOrdinalLookAlike : IEqualityComparer<string>
 543                 {
 544                         public bool Equals(string x, string y)
 545                         {
 546                                 return string.CompareOrdinal(x, y) == 0;
 547                         }
 548
 549                         public int GetHashCode(string str)
 550                         {
 551                                 if (str != null)
 552                                         return str.GetHashCode();
 553                                 throw new ArgumentNullException ();  // Important aspect for test (same as what StringComparer.Ordinal does, and different from GenericEqualityComparer<string>)
 554                         }
 555                 }
 556
 557                 [Test]
 558                 public void TrimWithoutChange ()
 559                 {
 560                         var lookup = new HashSet<string> ();
 561
 562                         for (int i = 0; i < 10000; i++) {
 563                                 lookup.Add (i.ToString ());
 564                         }
 565
 566                         lookup.Remove (3.ToString ());
 567
 568                         for (int i = 0; i < 1000; i++) {
 569                                 lookup.TrimExcess ();
 570                         }
 571                 }
 572         }
 573 }