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                 [MonoTODO]
 576                 [SecurityPermission (SecurityAction.LinkDemand, Flags = SecurityPermissionFlag.SerializationFormatter)]
 577                 public virtual void GetObjectData (SerializationInfo info, StreamingContext context)
 578                 {
 579                         throw new NotImplementedException ();
 580                 }
 581
 582                 [MonoTODO]
 583                 public virtual void OnDeserialization (object sender)
 584                 {
 585                         if (si == null)
 586                                 return;
 587
 588                         throw new NotImplementedException ();
 589                 }
 590
 591                 IEnumerator<T> IEnumerable<T>.GetEnumerator ()
 592                 {
 593                         return new Enumerator (this);
 594                 }
 595
 596                 bool ICollection<T>.IsReadOnly {
 597                         get { return false; }
 598                 }
 599
 600                 void ICollection<T>.Add (T item)
 601                 {
 602                         Add (item);
 603                 }
 604
 605                 IEnumerator IEnumerable.GetEnumerator ()
 606                 {
 607                         return new Enumerator (this);
 608                 }
 609
 610                 public Enumerator GetEnumerator ()
 611                 {
 612                         return new Enumerator (this);
 613                 }
 614
 615                 [Serializable]
 616                 public struct Enumerator : IEnumerator<T>, IDisposable {
 617
 618                         HashSet<T> hashset;
 619                         int next;
 620                         int stamp;
 621
 622                         T current;
 623
 624                         internal Enumerator (HashSet<T> hashset)
 625                                 : this ()
 626                         {
 627                                 this.hashset = hashset;
 628                                 this.stamp = hashset.generation;
 629                         }
 630
 631                         public bool MoveNext ()
 632                         {
 633                                 CheckState ();
 634
 635                                 if (next < 0)
 636                                         return false;
 637
 638                                 while (next < hashset.touched) {
 639                                         int cur = next++;
 640                                         if (hashset.GetLinkHashCode (cur) != 0) {
 641                                                 current = hashset.slots [cur];
 642                                                 return true;
 643                                         }
 644                                 }
 645
 646                                 next = NO_SLOT;
 647                                 return false;
 648                         }
 649
 650                         public T Current {
 651                                 get { return current; }
 652                         }
 653
 654                         object IEnumerator.Current {
 655                                 get {
 656                                         CheckState ();
 657                                         if (next <= 0)
 658                                                 throw new InvalidOperationException ("Current is not valid");
 659                                         return current;
 660                                 }
 661                         }
 662
 663                         void IEnumerator.Reset ()
 664                         {
 665                                 CheckState ();
 666                                 next = 0;
 667                         }
 668
 669                         public void Dispose ()
 670                         {
 671                                 hashset = null;
 672                         }
 673
 674                         void CheckState ()
 675                         {
 676                                 if (hashset == null)
 677                                         throw new ObjectDisposedException (null);
 678                                 if (hashset.generation != stamp)
 679                                         throw new InvalidOperationException ("HashSet have been modified while it was iterated over");
 680                         }
 681                 }
 682
 683                 // borrowed from System.Collections.HashTable
 684                 static class PrimeHelper {
 685
 686                         static readonly int [] primes_table = {
 687                                 11,
 688                                 19,
 689                                 37,
 690                                 73,
 691                                 109,
 692                                 163,
 693                                 251,
 694                                 367,
 695                                 557,
 696                                 823,
 697                                 1237,
 698                                 1861,
 699                                 2777,
 700                                 4177,
 701                                 6247,
 702                                 9371,
 703                                 14057,
 704                                 21089,
 705                                 31627,
 706                                 47431,
 707                                 71143,
 708                                 106721,
 709                                 160073,
 710                                 240101,
 711                                 360163,
 712                                 540217,
 713                                 810343,
 714                                 1215497,
 715                                 1823231,
 716                                 2734867,
 717                                 4102283,
 718                                 6153409,
 719                                 9230113,
 720                                 13845163
 721                         };
 722
 723                         static bool TestPrime (int x)
 724                         {
 725                                 if ((x & 1) != 0) {
 726                                         int top = (int) Math.Sqrt (x);
 727
 728                                         for (int n = 3; n < top; n += 2) {
 729                                                 if ((x % n) == 0)
 730                                                         return false;
 731                                         }
 732
 733                                         return true;
 734                                 }
 735
 736                                 // There is only one even prime - 2.
 737                                 return x == 2;
 738                         }
 739
 740                         static int CalcPrime (int x)
 741                         {
 742                                 for (int i = (x & (~1)) - 1; i < Int32.MaxValue; i += 2)
 743                                         if (TestPrime (i))
 744                                                 return i;
 745
 746                                 return x;
 747                         }
 748
 749                         public static int ToPrime (int x)
 750                         {
 751                                 for (int i = 0; i < primes_table.Length; i++)
 752                                         if (x <= primes_table [i])
 753                                                 return primes_table [i];
 754
 755                                 return CalcPrime (x);
 756                         }
 757                 }
 758         }
 759 }