mcs/class/System.Core/System.Collections.Generic/HashSet.cs

   1 //
   2 // HashSet.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 using System.Runtime.Serialization;
  34 using System.Runtime.InteropServices;
  35 using System.Security;
  36 using System.Security.Permissions;
  37 using System.Diagnostics;
  38
  39 // HashSet is basically implemented as a reduction of Dictionary<K, V>
  40
  41 namespace System.Collections.Generic {
  42
  43         [Serializable, HostProtection (SecurityAction.LinkDemand, MayLeakOnAbort = true)]
  44         [DebuggerDisplay ("Count={Count}")]
  45         [DebuggerTypeProxy (typeof (CollectionDebuggerView<,>))]
  46         public class HashSet<T> : ICollection<T>, ISerializable, IDeserializationCallback
  47 #if NET_4_0 || MOONLIGHT || MOBILE
  48                                                         , ISet<T>
  49 #endif
  50         {
  51                 const int INITIAL_SIZE = 10;
  52                 const float DEFAULT_LOAD_FACTOR = (90f / 100);
  53                 const int NO_SLOT = -1;
  54                 const int HASH_FLAG = -2147483648;
  55
  56                 struct Link {
  57                         public int HashCode;
  58                         public int Next;
  59                 }
  60
  61                 // The hash table contains indices into the "links" array
  62                 int [] table;
  63
  64                 Link [] links;
  65                 T [] slots;
  66
  67                 // The number of slots in "links" and "slots" that
  68                 // are in use (i.e. filled with data) or have been used and marked as
  69                 // "empty" later on.
  70                 int touched;
  71
  72                 // The index of the first slot in the "empty slots chain".
  73                 // "Remove ()" prepends the cleared slots to the empty chain.
  74                 // "Add ()" fills the first slot in the empty slots chain with the
  75                 // added item (or increases "touched" if the chain itself is empty).
  76                 int empty_slot;
  77
  78                 // The number of items in this set.
  79                 int count;
  80
  81                 // The number of items the set can hold without
  82                 // resizing the hash table and the slots arrays.
  83                 int threshold;
  84
  85                 IEqualityComparer<T> comparer;
  86                 SerializationInfo si;
  87
  88                 // The number of changes made to this set. Used by enumerators
  89                 // to detect changes and invalidate themselves.
  90                 int generation;
  91
  92                 public int Count {
  93                         get { return count; }
  94                 }
  95
  96                 public HashSet ()
  97                 {
  98                         Init (INITIAL_SIZE, null);
  99                 }
 100
 101                 public HashSet (IEqualityComparer<T> comparer)
 102                 {
 103                         Init (INITIAL_SIZE, comparer);
 104                 }
 105
 106                 public HashSet (IEnumerable<T> collection) : this (collection, null)
 107                 {
 108                 }
 109
 110                 public HashSet (IEnumerable<T> collection, IEqualityComparer<T> comparer)
 111                 {
 112                         if (collection == null)
 113                                 throw new ArgumentNullException ("collection");
 114
 115                         int capacity = 0;
 116                         var col = collection as ICollection<T>;
 117                         if (col != null)
 118                                 capacity = col.Count;
 119
 120                         Init (capacity, comparer);
 121                         foreach (var item in collection)
 122                                 Add (item);
 123                 }
 124
 125                 protected HashSet (SerializationInfo info, StreamingContext context)
 126                 {
 127                         si = info;
 128                 }
 129
 130                 void Init (int capacity, IEqualityComparer<T> comparer)
 131                 {
 132                         if (capacity < 0)
 133                                 throw new ArgumentOutOfRangeException ("capacity");
 134
 135                         this.comparer = comparer ?? EqualityComparer<T>.Default;
 136                         if (capacity == 0)
 137                                 capacity = INITIAL_SIZE;
 138
 139                         /* Modify capacity so 'capacity' elements can be added without resizing */
 140                         capacity = (int) (capacity / DEFAULT_LOAD_FACTOR) + 1;
 141
 142                         InitArrays (capacity);
 143                         generation = 0;
 144                 }
 145
 146                 void InitArrays (int size)
 147                 {
 148                         table = new int [size];
 149
 150                         links = new Link [size];
 151                         empty_slot = NO_SLOT;
 152
 153                         slots = new T [size];
 154                         touched = 0;
 155
 156                         threshold = (int) (table.Length * DEFAULT_LOAD_FACTOR);
 157                         if (threshold == 0 && table.Length > 0)
 158                                 threshold = 1;
 159                 }
 160
 161                 bool SlotsContainsAt (int index, int hash, T item)
 162                 {
 163                         int current = table [index] - 1;
 164                         while (current != NO_SLOT) {
 165                                 Link link = links [current];
 166                                 if (link.HashCode == hash && ((hash == HASH_FLAG && (item == null || null == slots [current])) ? (item == null && null == slots [current]) : comparer.Equals (item, slots [current])))
 167                                         return true;
 168
 169                                 current = link.Next;
 170                         }
 171
 172                         return false;
 173                 }
 174
 175                 public void CopyTo (T [] array)
 176                 {
 177                         CopyTo (array, 0, count);
 178                 }
 179
 180                 public void CopyTo (T [] array, int arrayIndex)
 181                 {
 182                         CopyTo (array, arrayIndex, count);
 183                 }
 184
 185                 public void CopyTo (T [] array, int arrayIndex, int count)
 186                 {
 187                         if (array == null)
 188                                 throw new ArgumentNullException ("array");
 189                         if (arrayIndex < 0)
 190                                 throw new ArgumentOutOfRangeException ("arrayIndex");
 191                         if (arrayIndex > array.Length)
 192                                 throw new ArgumentException ("index larger than largest valid index of array");
 193                         if (array.Length - arrayIndex < count)
 194                                 throw new ArgumentException ("Destination array cannot hold the requested elements!");
 195
 196                         for (int i = 0, items = 0; i < touched && items < count; i++) {
 197                                 if (GetLinkHashCode (i) != 0)
 198                                         array [arrayIndex++] = slots [i];
 199                         }
 200                 }
 201
 202                 void Resize ()
 203                 {
 204                         int newSize = PrimeHelper.ToPrime ((table.Length << 1) | 1);
 205
 206                         // allocate new hash table and link slots array
 207                         var newTable = new int [newSize];
 208                         var newLinks = new Link [newSize];
 209
 210                         for (int i = 0; i < table.Length; i++) {
 211                                 int current = table [i] - 1;
 212                                 while (current != NO_SLOT) {
 213                                         int hashCode = newLinks [current].HashCode = GetItemHashCode (slots [current]);
 214                                         int index = (hashCode & int.MaxValue) % newSize;
 215                                         newLinks [current].Next = newTable [index] - 1;
 216                                         newTable [index] = current + 1;
 217                                         current = links [current].Next;
 218                                 }
 219                         }
 220
 221                         table = newTable;
 222                         links = newLinks;
 223
 224                         // allocate new data slots, copy data
 225                         var newSlots = new T [newSize];
 226                         Array.Copy (slots, 0, newSlots, 0, touched);
 227                         slots = newSlots;
 228
 229                         threshold = (int) (newSize * DEFAULT_LOAD_FACTOR);
 230                 }
 231
 232                 int GetLinkHashCode (int index)
 233                 {
 234                         return links [index].HashCode & HASH_FLAG;
 235                 }
 236
 237                 int GetItemHashCode (T item)
 238                 {
 239                         if (item == null)
 240                                 return HASH_FLAG;
 241                         return comparer.GetHashCode (item) | HASH_FLAG;
 242                 }
 243
 244                 public bool Add (T item)
 245                 {
 246                         int hashCode = GetItemHashCode (item);
 247                         int index = (hashCode & int.MaxValue) % table.Length;
 248
 249                         if (SlotsContainsAt (index, hashCode, item))
 250                                 return false;
 251
 252                         if (++count > threshold) {
 253                                 Resize ();
 254                                 index = (hashCode & int.MaxValue) % table.Length;
 255                         }
 256
 257                         // find an empty slot
 258                         int current = empty_slot;
 259                         if (current == NO_SLOT)
 260                                 current = touched++;
 261                         else
 262                                 empty_slot = links [current].Next;
 263
 264                         // store the hash code of the added item,
 265                         // prepend the added item to its linked list,
 266                         // update the hash table
 267                         links [current].HashCode = hashCode;
 268                         links [current].Next = table [index] - 1;
 269                         table [index] = current + 1;
 270
 271                         // store item
 272                         slots [current] = item;
 273
 274                         generation++;
 275
 276                         return true;
 277                 }
 278
 279                 public IEqualityComparer<T> Comparer {
 280                         get { return comparer; }
 281                 }
 282
 283                 public void Clear ()
 284                 {
 285                         count = 0;
 286
 287                         Array.Clear (table, 0, table.Length);
 288                         Array.Clear (slots, 0, slots.Length);
 289                         Array.Clear (links, 0, links.Length);
 290
 291                         // empty the "empty slots chain"
 292                         empty_slot = NO_SLOT;
 293
 294                         touched = 0;
 295                         generation++;
 296                 }
 297
 298                 public bool Contains (T item)
 299                 {
 300                         int hashCode = GetItemHashCode (item);
 301                         int index = (hashCode & int.MaxValue) % table.Length;
 302
 303                         return SlotsContainsAt (index, hashCode, item);
 304                 }
 305
 306                 public bool Remove (T item)
 307                 {
 308                         // get first item of linked list corresponding to given key
 309                         int hashCode = GetItemHashCode (item);
 310                         int index = (hashCode & int.MaxValue) % table.Length;
 311                         int current = table [index] - 1;
 312
 313                         // if there is no linked list, return false
 314                         if (current == NO_SLOT)
 315                                 return false;
 316
 317                         // walk linked list until right slot (and its predecessor) is
 318                         // found or end is reached
 319                         int prev = NO_SLOT;
 320                         do {
 321                                 Link link = links [current];
 322                                 if (link.HashCode == hashCode && ((hashCode == HASH_FLAG && (item == null || null == slots [current])) ? (item == null && null == slots [current]) : comparer.Equals (slots [current], item)))
 323                                         break;
 324
 325                                 prev = current;
 326                                 current = link.Next;
 327                         } while (current != NO_SLOT);
 328
 329                         // if we reached the end of the chain, return false
 330                         if (current == NO_SLOT)
 331                                 return false;
 332
 333                         count--;
 334
 335                         // remove slot from linked list
 336                         // is slot at beginning of linked list?
 337                         if (prev == NO_SLOT)
 338                                 table [index] = links [current].Next + 1;
 339                         else
 340                                 links [prev].Next = links [current].Next;
 341
 342                         // mark slot as empty and prepend it to "empty slots chain"
 343                         links [current].Next = empty_slot;
 344                         empty_slot = current;
 345
 346                         // clear slot
 347                         links [current].HashCode = 0;
 348                         slots [current] = default (T);
 349
 350                         generation++;
 351
 352                         return true;
 353                 }
 354
 355                 public int RemoveWhere (Predicate<T> match)
 356                 {
 357                         if (match == null)
 358                                 throw new ArgumentNullException ("match");
 359
 360                         var candidates = new List<T> ();
 361
 362                         foreach (var item in this)
 363                                 if (match (item))
 364                                         candidates.Add (item);
 365
 366                         foreach (var item in candidates)
 367                                 Remove (item);
 368
 369                         return candidates.Count;
 370                 }
 371
 372                 public void TrimExcess ()
 373                 {
 374                         Resize ();
 375                 }
 376
 377                 // set operations
 378
 379                 public void IntersectWith (IEnumerable<T> other)
 380                 {
 381                         if (other == null)
 382                                 throw new ArgumentNullException ("other");
 383
 384                         var other_set = ToSet (other);
 385
 386                         RemoveWhere (item => !other_set.Contains (item));
 387                 }
 388
 389                 public void ExceptWith (IEnumerable<T> other)
 390                 {
 391                         if (other == null)
 392                                 throw new ArgumentNullException ("other");
 393
 394                         foreach (var item in other)
 395                                 Remove (item);
 396                 }
 397
 398                 public bool Overlaps (IEnumerable<T> other)
 399                 {
 400                         if (other == null)
 401                                 throw new ArgumentNullException ("other");
 402
 403                         foreach (var item in other)
 404                                 if (Contains (item))
 405                                         return true;
 406
 407                         return false;
 408                 }
 409
 410                 public bool SetEquals (IEnumerable<T> other)
 411                 {
 412                         if (other == null)
 413                                 throw new ArgumentNullException ("other");
 414
 415                         var other_set = ToSet (other);
 416
 417                         if (count != other_set.Count)
 418                                 return false;
 419
 420                         foreach (var item in this)
 421                                 if (!other_set.Contains (item))
 422                                         return false;
 423
 424                         return true;
 425                 }
 426
 427                 public void SymmetricExceptWith (IEnumerable<T> other)
 428                 {
 429                         if (other == null)
 430                                 throw new ArgumentNullException ("other");
 431
 432                         foreach (var item in ToSet (other))
 433                                 if (!Add (item))
 434                                         Remove (item);
 435                 }
 436
 437                 HashSet<T> ToSet (IEnumerable<T> enumerable)
 438                 {
 439                         var set = enumerable as HashSet<T>;
 440                         if (set == null || !Comparer.Equals (set.Comparer))
 441                                 set = new HashSet<T> (enumerable);
 442
 443                         return set;
 444                 }
 445
 446                 public void UnionWith (IEnumerable<T> other)
 447                 {
 448                         if (other == null)
 449                                 throw new ArgumentNullException ("other");
 450
 451                         foreach (var item in other)
 452                                 Add (item);
 453                 }
 454
 455                 bool CheckIsSubsetOf (HashSet<T> other)
 456                 {
 457                         if (other == null)
 458                                 throw new ArgumentNullException ("other");
 459
 460                         foreach (var item in this)
 461                                 if (!other.Contains (item))
 462                                         return false;
 463
 464                         return true;
 465                 }
 466
 467                 public bool IsSubsetOf (IEnumerable<T> other)
 468                 {
 469                         if (other == null)
 470                                 throw new ArgumentNullException ("other");
 471
 472                         if (count == 0)
 473                                 return true;
 474
 475                         var other_set = ToSet (other);
 476
 477                         if (count > other_set.Count)
 478                                 return false;
 479
 480                         return CheckIsSubsetOf (other_set);
 481                 }
 482
 483                 public bool IsProperSubsetOf (IEnumerable<T> other)
 484                 {
 485                         if (other == null)
 486                                 throw new ArgumentNullException ("other");
 487
 488                         if (count == 0)
 489                                 return true;
 490
 491                         var other_set = ToSet (other);
 492
 493                         if (count >= other_set.Count)
 494                                 return false;
 495
 496                         return CheckIsSubsetOf (other_set);
 497                 }
 498
 499                 bool CheckIsSupersetOf (HashSet<T> other)
 500                 {
 501                         if (other == null)
 502                                 throw new ArgumentNullException ("other");
 503
 504                         foreach (var item in other)
 505                                 if (!Contains (item))
 506                                         return false;
 507
 508                         return true;
 509                 }
 510
 511                 public bool IsSupersetOf (IEnumerable<T> other)
 512                 {
 513                         if (other == null)
 514                                 throw new ArgumentNullException ("other");
 515
 516                         var other_set = ToSet (other);
 517
 518                         if (count < other_set.Count)
 519                                 return false;
 520
 521                         return CheckIsSupersetOf (other_set);
 522                 }
 523
 524                 public bool IsProperSupersetOf (IEnumerable<T> other)
 525                 {
 526                         if (other == null)
 527                                 throw new ArgumentNullException ("other");
 528
 529                         var other_set = ToSet (other);
 530
 531                         if (count <= other_set.Count)
 532                                 return false;
 533
 534                         return CheckIsSupersetOf (other_set);
 535                 }
 536
 537                 class HashSetEqualityComparer : IEqualityComparer<HashSet<T>>
 538                 {
 539                         public bool Equals (HashSet<T> lhs, HashSet<T> rhs)
 540                         {
 541                                 if (lhs == rhs)
 542                                         return true;
 543
 544                                 if (lhs == null || rhs == null || lhs.Count != rhs.Count)
 545                                         return false;
 546
 547                                 foreach (var item in lhs)
 548                                         if (!rhs.Contains (item))
 549                                                 return false;
 550
 551                                 return true;
 552                         }
 553
 554                         public int GetHashCode (HashSet<T> hashset)
 555                         {
 556                                 if (hashset == null)
 557                                         return 0;
 558
 559                                 IEqualityComparer<T> comparer = EqualityComparer<T>.Default;
 560                                 int hash = 0;
 561                                 foreach (var item in hashset)
 562                                         hash ^= comparer.GetHashCode (item);
 563
 564                                 return hash;
 565                         }
 566                 }
 567
 568                 static readonly HashSetEqualityComparer setComparer = new HashSetEqualityComparer ();
 569
 570                 public static IEqualityComparer<HashSet<T>> CreateSetComparer ()
 571                 {
 572                         return setComparer;
 573                 }
 574
 575                 [SecurityPermission (SecurityAction.LinkDemand, Flags = SecurityPermissionFlag.SerializationFormatter)]
 576                 public virtual void GetObjectData (SerializationInfo info, StreamingContext context)
 577                 {
 578                         if (info == null) {
 579                                 throw new ArgumentNullException("info");
 580                         }
 581                         info.AddValue("Version", generation);
 582                         info.AddValue("Comparer", comparer, typeof(IEqualityComparer<T>));
 583                         info.AddValue("Capacity", (table == null) ? 0 : table.Length);
 584                         if (table != null) {
 585                                 T[] tableArray = new T[table.Length];
 586                                 CopyTo(tableArray);
 587                                 info.AddValue("Elements", tableArray, typeof(T[]));
 588                         }
 589                 }
 590
 591                 public virtual void OnDeserialization (object sender)
 592                 {
 593                         if (si != null)
 594                         {
 595                                 generation = (int) si.GetValue("Version", typeof(int));
 596                                 comparer = (IEqualityComparer<T>) si.GetValue("Comparer",
 597                                                                               typeof(IEqualityComparer<T>));
 598                                 int capacity = (int) si.GetValue("Capacity", typeof(int));
 599
 600                                 empty_slot = NO_SLOT;
 601                                 if (capacity > 0) {
 602                                         table = new int[capacity];
 603                                         slots = new T[capacity];
 604
 605                                         T[] tableArray = (T[]) si.GetValue("Elements", typeof(T[]));
 606                                         if (tableArray == null)
 607                                                 throw new SerializationException("Missing Elements");
 608
 609                                         for (int iElement = 0; iElement < tableArray.Length; iElement++) {
 610                                                 Add(tableArray[iElement]);
 611                                         }
 612                                 } else
 613                                         table = null;
 614
 615                                 si = null;
 616                         }
 617                 }
 618
 619
 620                 IEnumerator<T> IEnumerable<T>.GetEnumerator ()
 621                 {
 622                         return new Enumerator (this);
 623                 }
 624
 625                 bool ICollection<T>.IsReadOnly {
 626                         get { return false; }
 627                 }
 628
 629                 void ICollection<T>.Add (T item)
 630                 {
 631                         Add (item);
 632                 }
 633
 634                 IEnumerator IEnumerable.GetEnumerator ()
 635                 {
 636                         return new Enumerator (this);
 637                 }
 638
 639                 public Enumerator GetEnumerator ()
 640                 {
 641                         return new Enumerator (this);
 642                 }
 643
 644                 [Serializable]
 645                 public struct Enumerator : IEnumerator<T>, IDisposable {
 646
 647                         HashSet<T> hashset;
 648                         int next;
 649                         int stamp;
 650
 651                         T current;
 652
 653                         internal Enumerator (HashSet<T> hashset)
 654                                 : this ()
 655                         {
 656                                 this.hashset = hashset;
 657                                 this.stamp = hashset.generation;
 658                         }
 659
 660                         public bool MoveNext ()
 661                         {
 662                                 CheckState ();
 663
 664                                 if (next < 0)
 665                                         return false;
 666
 667                                 while (next < hashset.touched) {
 668                                         int cur = next++;
 669                                         if (hashset.GetLinkHashCode (cur) != 0) {
 670                                                 current = hashset.slots [cur];
 671                                                 return true;
 672                                         }
 673                                 }
 674
 675                                 next = NO_SLOT;
 676                                 return false;
 677                         }
 678
 679                         public T Current {
 680                                 get { return current; }
 681                         }
 682
 683                         object IEnumerator.Current {
 684                                 get {
 685                                         CheckState ();
 686                                         if (next <= 0)
 687                                                 throw new InvalidOperationException ("Current is not valid");
 688                                         return current;
 689                                 }
 690                         }
 691
 692                         void IEnumerator.Reset ()
 693                         {
 694                                 CheckState ();
 695                                 next = 0;
 696                         }
 697
 698                         public void Dispose ()
 699                         {
 700                                 hashset = null;
 701                         }
 702
 703                         void CheckState ()
 704                         {
 705                                 if (hashset == null)
 706                                         throw new ObjectDisposedException (null);
 707                                 if (hashset.generation != stamp)
 708                                         throw new InvalidOperationException ("HashSet have been modified while it was iterated over");
 709                         }
 710                 }
 711
 712                 // borrowed from System.Collections.HashTable
 713                 static class PrimeHelper {
 714
 715                         static readonly int [] primes_table = {
 716                                 11,
 717                                 19,
 718                                 37,
 719                                 73,
 720                                 109,
 721                                 163,
 722                                 251,
 723                                 367,
 724                                 557,
 725                                 823,
 726                                 1237,
 727                                 1861,
 728                                 2777,
 729                                 4177,
 730                                 6247,
 731                                 9371,
 732                                 14057,
 733                                 21089,
 734                                 31627,
 735                                 47431,
 736                                 71143,
 737                                 106721,
 738                                 160073,
 739                                 240101,
 740                                 360163,
 741                                 540217,
 742                                 810343,
 743                                 1215497,
 744                                 1823231,
 745                                 2734867,
 746                                 4102283,
 747                                 6153409,
 748                                 9230113,
 749                                 13845163
 750                         };
 751
 752                         static bool TestPrime (int x)
 753                         {
 754                                 if ((x & 1) != 0) {
 755                                         int top = (int) Math.Sqrt (x);
 756
 757                                         for (int n = 3; n < top; n += 2) {
 758                                                 if ((x % n) == 0)
 759                                                         return false;
 760                                         }
 761
 762                                         return true;
 763                                 }
 764
 765                                 // There is only one even prime - 2.
 766                                 return x == 2;
 767                         }
 768
 769                         static int CalcPrime (int x)
 770                         {
 771                                 for (int i = (x & (~1)) - 1; i < Int32.MaxValue; i += 2)
 772                                         if (TestPrime (i))
 773                                                 return i;
 774
 775                                 return x;
 776                         }
 777
 778                         public static int ToPrime (int x)
 779                         {
 780                                 for (int i = 0; i < primes_table.Length; i++)
 781                                         if (x <= primes_table [i])
 782                                                 return primes_table [i];
 783
 784                                 return CalcPrime (x);
 785                         }
 786                 }
 787         }
 788 }