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