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]
  44         [DebuggerDisplay ("Count={Count}")]
  45         [DebuggerTypeProxy (typeof (CollectionDebuggerView<,>))]
  46         public class HashSet<T> : ICollection<T>, ISerializable, IDeserializationCallback
  47 #if NET_4_0
  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 = HashPrimeNumbers.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, Comparer);
 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                 public static IEqualityComparer<HashSet<T>> CreateSetComparer ()
 538                 {
 539                         return HashSetEqualityComparer<T>.Instance;
 540                 }
 541
 542                 [SecurityPermission (SecurityAction.LinkDemand, Flags = SecurityPermissionFlag.SerializationFormatter)]
 543                 public virtual void GetObjectData (SerializationInfo info, StreamingContext context)
 544                 {
 545                         if (info == null) {
 546                                 throw new ArgumentNullException("info");
 547                         }
 548                         info.AddValue("Version", generation);
 549                         info.AddValue("Comparer", comparer, typeof(IEqualityComparer<T>));
 550                         info.AddValue("Capacity", (table == null) ? 0 : table.Length);
 551                         if (table != null) {
 552                                 T[] tableArray = new T[count];
 553                                 CopyTo(tableArray);
 554                                 info.AddValue("Elements", tableArray, typeof(T[]));
 555                         }
 556                 }
 557
 558                 public virtual void OnDeserialization (object sender)
 559                 {
 560                         if (si != null)
 561                         {
 562                                 generation = (int) si.GetValue("Version", typeof(int));
 563                                 comparer = (IEqualityComparer<T>) si.GetValue("Comparer",
 564                                                                               typeof(IEqualityComparer<T>));
 565                                 int capacity = (int) si.GetValue("Capacity", typeof(int));
 566
 567                                 empty_slot = NO_SLOT;
 568                                 if (capacity > 0) {
 569                                         InitArrays(capacity);
 570
 571                                         T[] tableArray = (T[]) si.GetValue("Elements", typeof(T[]));
 572                                         if (tableArray == null)
 573                                                 throw new SerializationException("Missing Elements");
 574
 575                                         for (int iElement = 0; iElement < tableArray.Length; iElement++) {
 576                                                 Add(tableArray[iElement]);
 577                                         }
 578                                 } else
 579                                         table = null;
 580
 581                                 si = null;
 582                         }
 583                 }
 584
 585
 586                 IEnumerator<T> IEnumerable<T>.GetEnumerator ()
 587                 {
 588                         return new Enumerator (this);
 589                 }
 590
 591                 bool ICollection<T>.IsReadOnly {
 592                         get { return false; }
 593                 }
 594
 595                 void ICollection<T>.Add (T item)
 596                 {
 597                         Add (item);
 598                 }
 599
 600                 IEnumerator IEnumerable.GetEnumerator ()
 601                 {
 602                         return new Enumerator (this);
 603                 }
 604
 605                 public Enumerator GetEnumerator ()
 606                 {
 607                         return new Enumerator (this);
 608                 }
 609
 610                 [Serializable]
 611                 public struct Enumerator : IEnumerator<T>, IDisposable {
 612
 613                         HashSet<T> hashset;
 614                         int next;
 615                         int stamp;
 616
 617                         T current;
 618
 619                         internal Enumerator (HashSet<T> hashset)
 620                                 : this ()
 621                         {
 622                                 this.hashset = hashset;
 623                                 this.stamp = hashset.generation;
 624                         }
 625
 626                         public bool MoveNext ()
 627                         {
 628                                 CheckState ();
 629
 630                                 if (next < 0)
 631                                         return false;
 632
 633                                 while (next < hashset.touched) {
 634                                         int cur = next++;
 635                                         if (hashset.GetLinkHashCode (cur) != 0) {
 636                                                 current = hashset.slots [cur];
 637                                                 return true;
 638                                         }
 639                                 }
 640
 641                                 next = NO_SLOT;
 642                                 return false;
 643                         }
 644
 645                         public T Current {
 646                                 get { return current; }
 647                         }
 648
 649                         object IEnumerator.Current {
 650                                 get {
 651                                         CheckState ();
 652                                         if (next <= 0)
 653                                                 throw new InvalidOperationException ("Current is not valid");
 654                                         return current;
 655                                 }
 656                         }
 657
 658                         void IEnumerator.Reset ()
 659                         {
 660                                 CheckState ();
 661                                 next = 0;
 662                         }
 663
 664                         public void Dispose ()
 665                         {
 666                                 hashset = null;
 667                         }
 668
 669                         void CheckState ()
 670                         {
 671                                 if (hashset == null)
 672                                         throw new ObjectDisposedException (null);
 673                                 if (hashset.generation != stamp)
 674                                         throw new InvalidOperationException ("HashSet have been modified while it was iterated over");
 675                         }
 676                 }
 677         }
 678
 679         sealed class HashSetEqualityComparer<T> : IEqualityComparer<HashSet<T>>
 680         {
 681                 public static readonly HashSetEqualityComparer<T> Instance = new HashSetEqualityComparer<T> ();
 682
 683                 public bool Equals (HashSet<T> lhs, HashSet<T> rhs)
 684                 {
 685                         if (lhs == rhs)
 686                                 return true;
 687
 688                         if (lhs == null || rhs == null || lhs.Count != rhs.Count)
 689                                 return false;
 690
 691                         foreach (var item in lhs)
 692                                 if (!rhs.Contains (item))
 693                                         return false;
 694
 695                         return true;
 696                 }
 697
 698                 public int GetHashCode (HashSet<T> hashset)
 699                 {
 700                         if (hashset == null)
 701                                 return 0;
 702
 703                         IEqualityComparer<T> comparer = EqualityComparer<T>.Default;
 704                         int hash = 0;
 705                         foreach (var item in hashset)
 706                                 hash ^= comparer.GetHashCode (item);
 707
 708                         return hash;
 709                 }
 710         }
 711 }