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