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
  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 index)
 181                 {
 182                         CopyTo (array, index, count);
 183                 }
 184
 185                 public void CopyTo (T [] array, int index, int count)
 186                 {
 187                         if (array == null)
 188                                 throw new ArgumentNullException ("array");
 189                         if (index < 0)
 190                                 throw new ArgumentOutOfRangeException ("index");
 191                         if (index > array.Length)
 192                                 throw new ArgumentException ("index larger than largest valid index of array");
 193                         if (array.Length - index < 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 [index++] = 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> predicate)
 356                 {
 357                         if (predicate == null)
 358                                 throw new ArgumentNullException ("predicate");
 359
 360                         int counter = 0;
 361
 362                         var candidates = new List<T> ();
 363
 364                         foreach (var item in this)
 365                                 if (predicate (item))
 366                                         candidates.Add (item);
 367
 368                         foreach (var item in candidates)
 369                                 Remove (item);
 370
 371                         return candidates.Count;
 372                 }
 373
 374                 public void TrimExcess ()
 375                 {
 376                         Resize ();
 377                 }
 378
 379                 // set operations
 380
 381                 public void IntersectWith (IEnumerable<T> other)
 382                 {
 383                         if (other == null)
 384                                 throw new ArgumentNullException ("other");
 385
 386                         var other_set = ToSet (other);
 387
 388                         RemoveWhere (item => !other_set.Contains (item));
 389                 }
 390
 391                 public void ExceptWith (IEnumerable<T> other)
 392                 {
 393                         if (other == null)
 394                                 throw new ArgumentNullException ("other");
 395
 396                         foreach (var item in other)
 397                                 Remove (item);
 398                 }
 399
 400                 public bool Overlaps (IEnumerable<T> other)
 401                 {
 402                         if (other == null)
 403                                 throw new ArgumentNullException ("other");
 404
 405                         foreach (var item in other)
 406                                 if (Contains (item))
 407                                         return true;
 408
 409                         return false;
 410                 }
 411
 412                 public bool SetEquals (IEnumerable<T> other)
 413                 {
 414                         if (other == null)
 415                                 throw new ArgumentNullException ("other");
 416
 417                         var other_set = ToSet (other);
 418
 419                         if (count != other_set.Count)
 420                                 return false;
 421
 422                         foreach (var item in this)
 423                                 if (!other_set.Contains (item))
 424                                         return false;
 425
 426                         return true;
 427                 }
 428
 429                 public void SymmetricExceptWith (IEnumerable<T> other)
 430                 {
 431                         if (other == null)
 432                                 throw new ArgumentNullException ("other");
 433
 434                         foreach (var item in ToSet (other))
 435                                 if (!Add (item))
 436                                         Remove (item);
 437                 }
 438
 439                 HashSet<T> ToSet (IEnumerable<T> enumerable)
 440                 {
 441                         var set = enumerable as HashSet<T>;
 442                         if (set == null || !Comparer.Equals (set.Comparer))
 443                                 set = new HashSet<T> (enumerable);
 444
 445                         return set;
 446                 }
 447
 448                 public void UnionWith (IEnumerable<T> other)
 449                 {
 450                         if (other == null)
 451                                 throw new ArgumentNullException ("other");
 452
 453                         foreach (var item in other)
 454                                 Add (item);
 455                 }
 456
 457                 bool CheckIsSubsetOf (HashSet<T> other)
 458                 {
 459                         if (other == null)
 460                                 throw new ArgumentNullException ("other");
 461
 462                         foreach (var item in this)
 463                                 if (!other.Contains (item))
 464                                         return false;
 465
 466                         return true;
 467                 }
 468
 469                 public bool IsSubsetOf (IEnumerable<T> other)
 470                 {
 471                         if (other == null)
 472                                 throw new ArgumentNullException ("other");
 473
 474                         if (count == 0)
 475                                 return true;
 476
 477                         var other_set = ToSet (other);
 478
 479                         if (count > other_set.Count)
 480                                 return false;
 481
 482                         return CheckIsSubsetOf (other_set);
 483                 }
 484
 485                 public bool IsProperSubsetOf (IEnumerable<T> other)
 486                 {
 487                         if (other == null)
 488                                 throw new ArgumentNullException ("other");
 489
 490                         if (count == 0)
 491                                 return true;
 492
 493                         var other_set = ToSet (other);
 494
 495                         if (count >= other_set.Count)
 496                                 return false;
 497
 498                         return CheckIsSubsetOf (other_set);
 499                 }
 500
 501                 bool CheckIsSupersetOf (HashSet<T> other)
 502                 {
 503                         if (other == null)
 504                                 throw new ArgumentNullException ("other");
 505
 506                         foreach (var item in other)
 507                                 if (!Contains (item))
 508                                         return false;
 509
 510                         return true;
 511                 }
 512
 513                 public bool IsSupersetOf (IEnumerable<T> other)
 514                 {
 515                         if (other == null)
 516                                 throw new ArgumentNullException ("other");
 517
 518                         var other_set = ToSet (other);
 519
 520                         if (count < other_set.Count)
 521                                 return false;
 522
 523                         return CheckIsSupersetOf (other_set);
 524                 }
 525
 526                 public bool IsProperSupersetOf (IEnumerable<T> other)
 527                 {
 528                         if (other == null)
 529                                 throw new ArgumentNullException ("other");
 530
 531                         var other_set = ToSet (other);
 532
 533                         if (count <= other_set.Count)
 534                                 return false;
 535
 536                         return CheckIsSupersetOf (other_set);
 537                 }
 538
 539                 [MonoTODO]
 540                 public static IEqualityComparer<HashSet<T>> CreateSetComparer ()
 541                 {
 542                         throw new NotImplementedException ();
 543                 }
 544
 545                 [MonoTODO]
 546                 [SecurityPermission (SecurityAction.LinkDemand, Flags = SecurityPermissionFlag.SerializationFormatter)]
 547                 public virtual void GetObjectData (SerializationInfo info, StreamingContext context)
 548                 {
 549                         throw new NotImplementedException ();
 550                 }
 551
 552                 [MonoTODO]
 553                 public virtual void OnDeserialization (object sender)
 554                 {
 555                         if (si == null)
 556                                 return;
 557
 558                         throw new NotImplementedException ();
 559                 }
 560
 561                 IEnumerator<T> IEnumerable<T>.GetEnumerator ()
 562                 {
 563                         return new Enumerator (this);
 564                 }
 565
 566                 bool ICollection<T>.IsReadOnly {
 567                         get { return false; }
 568                 }
 569
 570                 void ICollection<T>.CopyTo (T [] array, int index)
 571                 {
 572                         CopyTo (array, index);
 573                 }
 574
 575                 void ICollection<T>.Add (T item)
 576                 {
 577                         Add (item);
 578                 }
 579
 580                 IEnumerator IEnumerable.GetEnumerator ()
 581                 {
 582                         return new Enumerator (this);
 583                 }
 584
 585                 public Enumerator GetEnumerator ()
 586                 {
 587                         return new Enumerator (this);
 588                 }
 589
 590                 [Serializable]
 591                 public struct Enumerator : IEnumerator<T>, IDisposable {
 592
 593                         HashSet<T> hashset;
 594                         int next;
 595                         int stamp;
 596
 597                         T current;
 598
 599                         internal Enumerator (HashSet<T> hashset)
 600                                 : this ()
 601                         {
 602                                 this.hashset = hashset;
 603                                 this.stamp = hashset.generation;
 604                         }
 605
 606                         public bool MoveNext ()
 607                         {
 608                                 CheckState ();
 609
 610                                 if (next < 0)
 611                                         return false;
 612
 613                                 while (next < hashset.touched) {
 614                                         int cur = next++;
 615                                         if (hashset.GetLinkHashCode (cur) != 0) {
 616                                                 current = hashset.slots [cur];
 617                                                 return true;
 618                                         }
 619                                 }
 620
 621                                 next = NO_SLOT;
 622                                 return false;
 623                         }
 624
 625                         public T Current {
 626                                 get { return current; }
 627                         }
 628
 629                         object IEnumerator.Current {
 630                                 get {
 631                                         CheckState ();
 632                                         if (next <= 0)
 633                                                 throw new InvalidOperationException ("Current is not valid");
 634                                         return current;
 635                                 }
 636                         }
 637
 638                         void IEnumerator.Reset ()
 639                         {
 640                                 CheckState ();
 641                                 next = 0;
 642                         }
 643
 644                         public void Dispose ()
 645                         {
 646                                 hashset = null;
 647                         }
 648
 649                         void CheckState ()
 650                         {
 651                                 if (hashset == null)
 652                                         throw new ObjectDisposedException (null);
 653                                 if (hashset.generation != stamp)
 654                                         throw new InvalidOperationException ("HashSet have been modified while it was iterated over");
 655                         }
 656                 }
 657
 658                 // borrowed from System.Collections.HashTable
 659                 static class PrimeHelper {
 660
 661                         static readonly int [] primes_table = {
 662                                 11,
 663                                 19,
 664                                 37,
 665                                 73,
 666                                 109,
 667                                 163,
 668                                 251,
 669                                 367,
 670                                 557,
 671                                 823,
 672                                 1237,
 673                                 1861,
 674                                 2777,
 675                                 4177,
 676                                 6247,
 677                                 9371,
 678                                 14057,
 679                                 21089,
 680                                 31627,
 681                                 47431,
 682                                 71143,
 683                                 106721,
 684                                 160073,
 685                                 240101,
 686                                 360163,
 687                                 540217,
 688                                 810343,
 689                                 1215497,
 690                                 1823231,
 691                                 2734867,
 692                                 4102283,
 693                                 6153409,
 694                                 9230113,
 695                                 13845163
 696                         };
 697
 698                         static bool TestPrime (int x)
 699                         {
 700                                 if ((x & 1) != 0) {
 701                                         int top = (int) Math.Sqrt (x);
 702
 703                                         for (int n = 3; n < top; n += 2) {
 704                                                 if ((x % n) == 0)
 705                                                         return false;
 706                                         }
 707
 708                                         return true;
 709                                 }
 710
 711                                 // There is only one even prime - 2.
 712                                 return x == 2;
 713                         }
 714
 715                         static int CalcPrime (int x)
 716                         {
 717                                 for (int i = (x & (~1)) - 1; i < Int32.MaxValue; i += 2)
 718                                         if (TestPrime (i))
 719                                                 return i;
 720
 721                                 return x;
 722                         }
 723
 724                         public static int ToPrime (int x)
 725                         {
 726                                 for (int i = 0; i < primes_table.Length; i++)
 727                                         if (x <= primes_table [i])
 728                                                 return primes_table [i];
 729
 730                                 return CalcPrime (x);
 731                         }
 732                 }
 733         }
 734 }