mcs/class/corlib/System.Collections.Generic/Dictionary.cs

   1 //
   2 // System.Collections.Generic.Dictionary
   3 //
   4 // Authors:
   5 //      Sureshkumar T (tsureshkumar@novell.com)
   6 //      Marek Safar (marek.safar@seznam.cz) (stubs)
   7 //      Ankit Jain (radical@corewars.org)
   8 //      David Waite (mass@akuma.org)
   9 //      Juraj Skripsky (js@hotfeet.ch)
  10 //
  11 //
  12 // Copyright (C) 2004 Novell, Inc (http://www.novell.com)
  13 // Copyright (C) 2005 David Waite
  14 // Copyright (C) 2007 HotFeet GmbH (http://www.hotfeet.ch)
  15 //
  16 // Permission is hereby granted, free of charge, to any person obtaining
  17 // a copy of this software and associated documentation files (the
  18 // "Software"), to deal in the Software without restriction, including
  19 // without limitation the rights to use, copy, modify, merge, publish,
  20 // distribute, sublicense, and/or sell copies of the Software, and to
  21 // permit persons to whom the Software is furnished to do so, subject to
  22 // the following conditions:
  23 //
  24 // The above copyright notice and this permission notice shall be
  25 // included in all copies or substantial portions of the Software.
  26 //
  27 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  28 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  29 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  30 // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  31 // LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  32 // OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  33 // WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  34 //
  35
  36 #if NET_2_0
  37
  38 using System;
  39 using System.Collections;
  40 using System.Collections.Generic;
  41 using System.Runtime.Serialization;
  42 using System.Security.Permissions;
  43 using System.Runtime.InteropServices;
  44
  45 namespace System.Collections.Generic {
  46
  47         /*
  48          * Declare this outside the main class so it doesn't have to be inflated for each
  49          * instantiation of Dictionary.
  50          */
  51         internal struct Link {
  52                 public int HashCode;
  53                 public int Next;
  54         }
  55
  56         [ComVisible(false)]
  57         [Serializable]
  58         public class Dictionary<TKey, TValue> : IDictionary<TKey, TValue>,
  59                 IDictionary,
  60                 ICollection,
  61                 ICollection<KeyValuePair<TKey, TValue>>,
  62                 IEnumerable<KeyValuePair<TKey, TValue>>,
  63                 ISerializable,
  64                 IDeserializationCallback
  65         {
  66                 // The implementation of this class uses a hash table and linked lists
  67                 // (see: http://msdn2.microsoft.com/en-us/library/ms379571(VS.80).aspx).
  68                 //
  69                 // We use a kind of "mini-heap" instead of reference-based linked lists:
  70                 // "keySlots" and "valueSlots" is the heap itself, it stores the data
  71                 // "linkSlots" contains information about how the slots in the heap
  72                 //             are connected into linked lists
  73                 //             In addition, the HashCode field can be used to check if the
  74                 //             corresponding key and value are present (HashCode has the
  75                 //             HASH_FLAG bit set in this case), so, to iterate over all the
  76                 //             items in the dictionary, simply iterate the linkSlots array
  77                 //             and check for the HASH_FLAG bit in the HashCode field.
  78                 //             For this reason, each time a hashcode is calculated, it needs
  79                 //             to be ORed with HASH_FLAG before comparing it with the save hashcode.
  80                 // "touchedSlots" and "emptySlot" manage the free space in the heap
  81
  82                 const int INITIAL_SIZE = 10;
  83                 const float DEFAULT_LOAD_FACTOR = (90f / 100);
  84                 const int NO_SLOT = -1;
  85                 const int HASH_FLAG = -2147483648;
  86
  87                 // The hash table contains indices into the linkSlots array
  88                 int [] table;
  89
  90                 // All (key,value) pairs are chained into linked lists. The connection
  91                 // information is stored in "linkSlots" along with the key's hash code
  92                 // (for performance reasons).
  93                 // TODO: get rid of the hash code in Link (this depends on a few
  94                 // JIT-compiler optimizations)
  95                 // Every link in "linkSlots" corresponds to the (key,value) pair
  96                 // in "keySlots"/"valueSlots" with the same index.
  97                 Link [] linkSlots;
  98                 TKey [] keySlots;
  99                 TValue [] valueSlots;
 100
 101                 // The number of slots in "linkSlots" and "keySlots"/"valueSlots" that
 102                 // are in use (i.e. filled with data) or have been used and marked as
 103                 // "empty" later on.
 104                 int touchedSlots;
 105
 106                 // The index of the first slot in the "empty slots chain".
 107                 // "Remove()" prepends the cleared slots to the empty chain.
 108                 // "Add()" fills the first slot in the empty slots chain with the
 109                 // added item (or increases "touchedSlots" if the chain itself is empty).
 110                 int emptySlot;
 111
 112                 // The number of (key,value) pairs in this dictionary.
 113                 int count;
 114
 115                 // The number of (key,value) pairs the dictionary can hold without
 116                 // resizing the hash table and the slots arrays.
 117                 int threshold;
 118
 119                 IEqualityComparer<TKey> hcp;
 120                 SerializationInfo serialization_info;
 121
 122                 // The number of changes made to this dictionary. Used by enumerators
 123                 // to detect changes and invalidate themselves.
 124                 int generation;
 125
 126                 public int Count {
 127                         get { return count; }
 128                 }
 129
 130                 public TValue this [TKey key] {
 131                         get {
 132                                 if (key == null)
 133                                         throw new ArgumentNullException ("key");
 134
 135                                 // get first item of linked list corresponding to given key
 136                                 int hashCode = hcp.GetHashCode (key) | HASH_FLAG;
 137                                 int cur = table [(hashCode & int.MaxValue) % table.Length] - 1;
 138
 139                                 // walk linked list until right slot is found or end is reached
 140                                 while (cur != NO_SLOT) {
 141                                         // The ordering is important for compatibility with MS and strange
 142                                         // Object.Equals () implementations
 143                                         if (linkSlots [cur].HashCode == hashCode && hcp.Equals (keySlots [cur], key))
 144                                                 return valueSlots [cur];
 145                                         cur = linkSlots [cur].Next;
 146                                 }
 147                                 throw new KeyNotFoundException ();
 148                         }
 149
 150                         set {
 151                                 if (key == null)
 152                                         throw new ArgumentNullException ("key");
 153
 154                                 // get first item of linked list corresponding to given key
 155                                 int hashCode = hcp.GetHashCode (key) | HASH_FLAG;
 156                                 int index = (hashCode & int.MaxValue) % table.Length;
 157                                 int cur = table [index] - 1;
 158
 159                                 // walk linked list until right slot (and its predecessor) is
 160                                 // found or end is reached
 161                                 int prev = NO_SLOT;
 162                                 if (cur != NO_SLOT) {
 163                                         do {
 164                                                 // The ordering is important for compatibility with MS and strange
 165                                                 // Object.Equals () implementations
 166                                                 if (linkSlots [cur].HashCode == hashCode && hcp.Equals (keySlots [cur], key))
 167                                                         break;
 168                                                 prev = cur;
 169                                                 cur = linkSlots [cur].Next;
 170                                         } while (cur != NO_SLOT);
 171                                 }
 172
 173                                 // is there no slot for the given key yet?
 174                                 if (cur == NO_SLOT) {
 175                                         // there is no existing slot for the given key,
 176                                         // allocate one and prepend it to its corresponding linked
 177                                         // list
 178
 179                                         if (++count > threshold) {
 180                                                 Resize ();
 181                                                 index = (hashCode & int.MaxValue) % table.Length;
 182                                         }
 183
 184                                         // find an empty slot
 185                                         cur = emptySlot;
 186                                         if (cur == NO_SLOT)
 187                                                 cur = touchedSlots++;
 188                                         else
 189                                                 emptySlot = linkSlots [cur].Next;
 190
 191                                         // prepend the added item to its linked list,
 192                                         // update the hash table
 193                                         linkSlots [cur].Next = table [index] - 1;
 194                                         table [index] = cur + 1;
 195
 196                                         // store the new item and its hash code
 197                                         linkSlots [cur].HashCode = hashCode;
 198                                         keySlots [cur] = key;
 199                                 } else {
 200                                         // we already have a slot for the given key,
 201                                         // update the existing slot
 202
 203                                         // if the slot is not at the front of its linked list,
 204                                         // we move it there
 205                                         if (prev != NO_SLOT) {
 206                                                 linkSlots [prev].Next = linkSlots [cur].Next;
 207                                                 linkSlots [cur].Next = table [index] - 1;
 208                                                 table [index] = cur + 1;
 209                                         }
 210                                 }
 211
 212                                 // store the item's data itself
 213                                 valueSlots [cur] = value;
 214
 215                                 generation++;
 216                         }
 217                 }
 218
 219                 public Dictionary ()
 220                 {
 221                         Init (INITIAL_SIZE, null);
 222                 }
 223
 224                 public Dictionary (IEqualityComparer<TKey> comparer)
 225                 {
 226                         Init (INITIAL_SIZE, comparer);
 227                 }
 228
 229                 public Dictionary (IDictionary<TKey, TValue> dictionary)
 230                         : this (dictionary, null)
 231                 {
 232                 }
 233
 234                 public Dictionary (int capacity)
 235                 {
 236                         Init (capacity, null);
 237                 }
 238
 239                 public Dictionary (IDictionary<TKey, TValue> dictionary, IEqualityComparer<TKey> comparer)
 240                 {
 241                         if (dictionary == null)
 242                                 throw new ArgumentNullException ("dictionary");
 243                         int capacity = dictionary.Count;
 244                         Init (capacity, comparer);
 245                         foreach (KeyValuePair<TKey, TValue> entry in dictionary)
 246                                 this.Add (entry.Key, entry.Value);
 247                 }
 248
 249                 public Dictionary (int capacity, IEqualityComparer<TKey> comparer)
 250                 {
 251                         Init (capacity, comparer);
 252                 }
 253
 254                 protected Dictionary (SerializationInfo info, StreamingContext context)
 255                 {
 256                         serialization_info = info;
 257                 }
 258
 259                 private void Init (int capacity, IEqualityComparer<TKey> hcp)
 260                 {
 261                         if (capacity < 0)
 262                                 throw new ArgumentOutOfRangeException ("capacity");
 263                         this.hcp = (hcp != null) ? hcp : EqualityComparer<TKey>.Default;
 264                         if (capacity == 0)
 265                                 capacity = INITIAL_SIZE;
 266
 267                         /* Modify capacity so 'capacity' elements can be added without resizing */
 268                         capacity = (int)(capacity / DEFAULT_LOAD_FACTOR) + 1;
 269
 270                         InitArrays (capacity);
 271                         generation = 0;
 272                 }
 273
 274                 private void InitArrays (int size) {
 275                         table = new int [size];
 276
 277                         linkSlots = new Link [size];
 278                         emptySlot = NO_SLOT;
 279
 280                         keySlots = new TKey [size];
 281                         valueSlots = new TValue [size];
 282                         touchedSlots = 0;
 283
 284                         threshold = (int)(table.Length * DEFAULT_LOAD_FACTOR);
 285                         if (threshold == 0 && table.Length > 0)
 286                                 threshold = 1;
 287                 }
 288
 289                 void CopyToCheck (Array array, int index)
 290                 {
 291                         if (array == null)
 292                                 throw new ArgumentNullException ("array");
 293                         if (index < 0)
 294                                 throw new ArgumentOutOfRangeException ("index");
 295                         // we want no exception for index==array.Length && Count == 0
 296                         if (index > array.Length)
 297                                 throw new ArgumentException ("index larger than largest valid index of array");
 298                         if (array.Length - index < Count)
 299                                 throw new ArgumentException ("Destination array cannot hold the requested elements!");
 300                 }
 301
 302                 delegate TRet Transform<TRet> (TKey key, TValue value);
 303
 304                 void Do_CopyTo<TRet, TElem> (TElem [] array, int index, Transform<TRet> transform)
 305                         where TRet : TElem
 306                 {
 307                         for (int i = 0; i < touchedSlots; i++) {
 308                                 if ((linkSlots [i].HashCode & HASH_FLAG) != 0)
 309                                         array [index++] = transform (keySlots [i], valueSlots [i]);
 310                         }
 311                 }
 312
 313                 static KeyValuePair<TKey, TValue> make_pair (TKey key, TValue value)
 314                 {
 315                         return new KeyValuePair<TKey, TValue> (key, value);
 316                 }
 317
 318                 static TKey pick_key (TKey key, TValue value)
 319                 {
 320                         return key;
 321                 }
 322
 323                 static TValue pick_value (TKey key, TValue value)
 324                 {
 325                         return value;
 326                 }
 327
 328                 void CopyTo (KeyValuePair<TKey, TValue> [] array, int index)
 329                 {
 330                         CopyToCheck (array, index);
 331                         Do_CopyTo<KeyValuePair<TKey, TValue>, KeyValuePair<TKey, TValue>> (array, index, make_pair);
 332                 }
 333
 334                 void Do_ICollectionCopyTo<TRet> (Array array, int index, Transform<TRet> transform)
 335                 {
 336                         Type src = typeof (TRet);
 337                         Type tgt = array.GetType ().GetElementType ();
 338
 339                         try {
 340                                 if ((src.IsPrimitive || tgt.IsPrimitive) && !tgt.IsAssignableFrom (src))
 341                                         throw new Exception (); // we don't care.  it'll get transformed to an ArgumentException below
 342
 343                                 Do_CopyTo <TRet, TRet> ((TRet []) array, index, transform);
 344                         } catch (Exception e) {
 345                                 throw new ArgumentException ("Cannot copy source collection elements to destination array", "array", e);
 346                         }
 347                 }
 348
 349                 private void Resize ()
 350                 {
 351                         // From the SDK docs:
 352                         //       Hashtable is automatically increased
 353                         //       to the smallest prime number that is larger
 354                         //       than twice the current number of Hashtable buckets
 355                         int newSize = Hashtable.ToPrime ((table.Length << 1) | 1);
 356
 357                         // allocate new hash table and link slots array
 358                         int [] newTable = new int [newSize];
 359                         Link [] newLinkSlots = new Link [newSize];
 360
 361                         for (int i = 0; i < table.Length; i++) {
 362                                 int cur = table [i] - 1;
 363                                 while (cur != NO_SLOT) {
 364                                         int hashCode = newLinkSlots [cur].HashCode = hcp.GetHashCode(keySlots [cur]) | HASH_FLAG;
 365                                         int index = (hashCode & int.MaxValue) % newSize;
 366                                         newLinkSlots [cur].Next = newTable [index] - 1;
 367                                         newTable [index] = cur + 1;
 368                                         cur = linkSlots [cur].Next;
 369                                 }
 370                         }
 371                         table = newTable;
 372                         linkSlots = newLinkSlots;
 373
 374                         // allocate new data slots, copy data
 375                         TKey [] newKeySlots = new TKey [newSize];
 376                         TValue [] newValueSlots = new TValue [newSize];
 377                         Array.Copy (keySlots, 0, newKeySlots, 0, touchedSlots);
 378                         Array.Copy (valueSlots, 0, newValueSlots, 0, touchedSlots);
 379                         keySlots = newKeySlots;
 380                         valueSlots = newValueSlots;
 381
 382                         threshold = (int)(newSize * DEFAULT_LOAD_FACTOR);
 383                 }
 384
 385                 public void Add (TKey key, TValue value)
 386                 {
 387                         if (key == null)
 388                                 throw new ArgumentNullException ("key");
 389
 390                         // get first item of linked list corresponding to given key
 391                         int hashCode = hcp.GetHashCode (key) | HASH_FLAG;
 392                         int index = (hashCode & int.MaxValue) % table.Length;
 393                         int cur = table [index] - 1;
 394
 395                         // walk linked list until end is reached (throw an exception if a
 396                         // existing slot is found having an equivalent key)
 397                         while (cur != NO_SLOT) {
 398                                 // The ordering is important for compatibility with MS and strange
 399                                 // Object.Equals () implementations
 400                                 if (linkSlots [cur].HashCode == hashCode && hcp.Equals (keySlots [cur], key))
 401                                         throw new ArgumentException ("An element with the same key already exists in the dictionary.");
 402                                 cur = linkSlots [cur].Next;
 403                         }
 404
 405                         if (++count > threshold) {
 406                                 Resize ();
 407                                 index = (hashCode & int.MaxValue) % table.Length;
 408                         }
 409
 410                         // find an empty slot
 411                         cur = emptySlot;
 412                         if (cur == NO_SLOT)
 413                                 cur = touchedSlots++;
 414                         else
 415                                 emptySlot = linkSlots [cur].Next;
 416
 417                         // store the hash code of the added item,
 418                         // prepend the added item to its linked list,
 419                         // update the hash table
 420                         linkSlots [cur].HashCode = hashCode;
 421                         linkSlots [cur].Next = table [index] - 1;
 422                         table [index] = cur + 1;
 423
 424                         // store item's data
 425                         keySlots [cur] = key;
 426                         valueSlots [cur] = value;
 427
 428                         generation++;
 429                 }
 430
 431                 public IEqualityComparer<TKey> Comparer {
 432                         get { return hcp; }
 433                 }
 434
 435                 public void Clear ()
 436                 {
 437                         count = 0;
 438                         // clear the hash table
 439                         Array.Clear (table, 0, table.Length);
 440                         // clear arrays
 441                         Array.Clear (keySlots, 0, keySlots.Length);
 442                         Array.Clear (valueSlots, 0, valueSlots.Length);
 443                         Array.Clear (linkSlots, 0, linkSlots.Length);
 444
 445                         // empty the "empty slots chain"
 446                         emptySlot = NO_SLOT;
 447
 448                         touchedSlots = 0;
 449                         generation++;
 450                 }
 451
 452                 public bool ContainsKey (TKey key)
 453                 {
 454                         if (key == null)
 455                                 throw new ArgumentNullException ("key");
 456
 457                         // get first item of linked list corresponding to given key
 458                         int hashCode = hcp.GetHashCode (key) | HASH_FLAG;
 459                         int cur = table [(hashCode & int.MaxValue) % table.Length] - 1;
 460
 461                         // walk linked list until right slot is found or end is reached
 462                         while (cur != NO_SLOT) {
 463                                 // The ordering is important for compatibility with MS and strange
 464                                 // Object.Equals () implementations
 465                                 if (linkSlots [cur].HashCode == hashCode && hcp.Equals (keySlots [cur], key))
 466                                         return true;
 467                                 cur = linkSlots [cur].Next;
 468                         }
 469
 470                         return false;
 471                 }
 472
 473                 public bool ContainsValue (TValue value)
 474                 {
 475                         IEqualityComparer<TValue> cmp = EqualityComparer<TValue>.Default;
 476
 477                         for (int i = 0; i < table.Length; i++) {
 478                                 int cur = table [i] - 1;
 479                                 while (cur != NO_SLOT) {
 480                                         if (cmp.Equals (valueSlots [cur], value))
 481                                                 return true;
 482                                         cur = linkSlots [cur].Next;
 483                                 }
 484                         }
 485                         return false;
 486                 }
 487
 488                 [SecurityPermission (SecurityAction.LinkDemand, Flags=SecurityPermissionFlag.SerializationFormatter)]
 489                 public virtual void GetObjectData (SerializationInfo info, StreamingContext context)
 490                 {
 491                         if (info == null)
 492                                 throw new ArgumentNullException ("info");
 493
 494                         info.AddValue ("Version", generation);
 495                         info.AddValue ("Comparer", hcp);
 496                         KeyValuePair<TKey, TValue> [] data = null;
 497                         if (count > 0) {
 498                                 data = new KeyValuePair<TKey,TValue> [count];
 499                                 CopyTo (data, 0);
 500                         }
 501                         info.AddValue ("HashSize", table.Length);
 502                         info.AddValue ("KeyValuePairs", data);
 503                 }
 504
 505                 public virtual void OnDeserialization (object sender)
 506                 {
 507                         if (serialization_info == null)
 508                                 return;
 509
 510                         generation = serialization_info.GetInt32 ("Version");
 511                         hcp = (IEqualityComparer<TKey>) serialization_info.GetValue ("Comparer", typeof (IEqualityComparer<TKey>));
 512
 513                         int hashSize = serialization_info.GetInt32 ("HashSize");
 514                         KeyValuePair<TKey, TValue> [] data =
 515                                 (KeyValuePair<TKey, TValue> [])
 516                                 serialization_info.GetValue ("KeyValuePairs", typeof (KeyValuePair<TKey, TValue> []));
 517
 518                         if (hashSize < INITIAL_SIZE)
 519                                 hashSize = INITIAL_SIZE;
 520                         InitArrays (hashSize);
 521                         count = 0;
 522
 523                         if (data != null) {
 524                                 for (int i = 0; i < data.Length; ++i)
 525                                         Add (data [i].Key, data [i].Value);
 526                         }
 527                         generation++;
 528                         serialization_info = null;
 529                 }
 530
 531                 public bool Remove (TKey key)
 532                 {
 533                         if (key == null)
 534                                 throw new ArgumentNullException ("key");
 535
 536                         // get first item of linked list corresponding to given key
 537                         int hashCode = hcp.GetHashCode (key) | HASH_FLAG;
 538                         int index = (hashCode & int.MaxValue) % table.Length;
 539                         int cur = table [index] - 1;
 540
 541                         // if there is no linked list, return false
 542                         if (cur == NO_SLOT)
 543                                 return false;
 544
 545                         // walk linked list until right slot (and its predecessor) is
 546                         // found or end is reached
 547                         int prev = NO_SLOT;
 548                         do {
 549                                 // The ordering is important for compatibility with MS and strange
 550                                 // Object.Equals () implementations
 551                                 if (linkSlots [cur].HashCode == hashCode && hcp.Equals (keySlots [cur], key))
 552                                         break;
 553                                 prev = cur;
 554                                 cur = linkSlots [cur].Next;
 555                         } while (cur != NO_SLOT);
 556
 557                         // if we reached the end of the chain, return false
 558                         if (cur == NO_SLOT)
 559                                 return false;
 560
 561                         count--;
 562                         // remove slot from linked list
 563                         // is slot at beginning of linked list?
 564                         if (prev == NO_SLOT)
 565                                 table [index] = linkSlots [cur].Next + 1;
 566                         else
 567                                 linkSlots [prev].Next = linkSlots [cur].Next;
 568
 569                         // mark slot as empty and prepend it to "empty slots chain"
 570                         linkSlots [cur].Next = emptySlot;
 571                         emptySlot = cur;
 572
 573                         linkSlots [cur].HashCode = 0;
 574                         // clear empty key and value slots
 575                         keySlots [cur] = default (TKey);
 576                         valueSlots [cur] = default (TValue);
 577
 578                         generation++;
 579                         return true;
 580                 }
 581
 582                 public bool TryGetValue (TKey key, out TValue value)
 583                 {
 584                         if (key == null)
 585                                 throw new ArgumentNullException ("key");
 586
 587                         // get first item of linked list corresponding to given key
 588                         int hashCode = hcp.GetHashCode (key) | HASH_FLAG;
 589                         int cur = table [(hashCode & int.MaxValue) % table.Length] - 1;
 590
 591                         // walk linked list until right slot is found or end is reached
 592                         while (cur != NO_SLOT) {
 593                                 // The ordering is important for compatibility with MS and strange
 594                                 // Object.Equals () implementations
 595                                 if (linkSlots [cur].HashCode == hashCode && hcp.Equals (keySlots [cur], key)) {
 596                                         value = valueSlots [cur];
 597                                         return true;
 598                                 }
 599                                 cur = linkSlots [cur].Next;
 600                         }
 601
 602                         // we did not find the slot
 603                         value = default (TValue);
 604                         return false;
 605                 }
 606
 607                 ICollection<TKey> IDictionary<TKey, TValue>.Keys {
 608                         get { return Keys; }
 609                 }
 610
 611                 ICollection<TValue> IDictionary<TKey, TValue>.Values {
 612                         get { return Values; }
 613                 }
 614
 615                 public KeyCollection Keys {
 616                         get { return new KeyCollection (this); }
 617                 }
 618
 619                 public ValueCollection Values {
 620                         get { return new ValueCollection (this); }
 621                 }
 622
 623                 ICollection IDictionary.Keys {
 624                         get { return Keys; }
 625                 }
 626
 627                 ICollection IDictionary.Values {
 628                         get { return Values; }
 629                 }
 630
 631                 bool IDictionary.IsFixedSize {
 632                         get { return false; }
 633                 }
 634
 635                 bool IDictionary.IsReadOnly {
 636                         get { return false; }
 637                 }
 638
 639                 TKey ToTKey (object key)
 640                 {
 641                         if (key == null)
 642                                 throw new ArgumentNullException ("key");
 643                         if (!(key is TKey))
 644                                 throw new ArgumentException ("not of type: " + typeof (TKey).ToString (), "key");
 645                         return (TKey) key;
 646                 }
 647
 648                 TValue ToTValue (object value)
 649                 {
 650                         if (value == null && !typeof (TValue).IsValueType)
 651                                 return default (TValue);
 652                         if (!(value is TValue))
 653                                 throw new ArgumentException ("not of type: " + typeof (TValue).ToString (), "value");
 654                         return (TValue) value;
 655                 }
 656
 657                 object IDictionary.this [object key] {
 658                         get {
 659                                 if (key is TKey && ContainsKey((TKey) key))
 660                                         return this [ToTKey (key)];
 661                                 return null;
 662                         }
 663                         set { this [ToTKey (key)] = ToTValue (value); }
 664                 }
 665
 666                 void IDictionary.Add (object key, object value)
 667                 {
 668                         this.Add (ToTKey (key), ToTValue (value));
 669                 }
 670
 671                 bool IDictionary.Contains (object key)
 672                 {
 673                         if (key == null)
 674                                 throw new ArgumentNullException ("key");
 675                         if (key is TKey)
 676                                 return ContainsKey ((TKey) key);
 677                         return false;
 678                 }
 679
 680                 void IDictionary.Remove (object key)
 681                 {
 682                         if (key == null)
 683                                 throw new ArgumentNullException ("key");
 684                         if (key is TKey)
 685                                 Remove ((TKey) key);
 686                 }
 687
 688                 bool ICollection.IsSynchronized {
 689                         get { return false; }
 690                 }
 691
 692                 object ICollection.SyncRoot {
 693                         get { return this; }
 694                 }
 695
 696                 bool ICollection<KeyValuePair<TKey, TValue>>.IsReadOnly {
 697                         get { return false; }
 698                 }
 699
 700                 void ICollection<KeyValuePair<TKey, TValue>>.Add (KeyValuePair<TKey, TValue> keyValuePair)
 701                 {
 702                         Add (keyValuePair.Key, keyValuePair.Value);
 703                 }
 704
 705                 bool ICollection<KeyValuePair<TKey, TValue>>.Contains (KeyValuePair<TKey, TValue> keyValuePair)
 706                 {
 707                         return ContainsKeyValuePair (keyValuePair);
 708                 }
 709
 710                 void ICollection<KeyValuePair<TKey, TValue>>.CopyTo (KeyValuePair<TKey, TValue> [] array, int index)
 711                 {
 712                         this.CopyTo (array, index);
 713                 }
 714
 715                 bool ICollection<KeyValuePair<TKey, TValue>>.Remove (KeyValuePair<TKey, TValue> keyValuePair)
 716                 {
 717                         if (!ContainsKeyValuePair (keyValuePair))
 718                                 return false;
 719
 720                         return Remove (keyValuePair.Key);
 721                 }
 722
 723                 bool ContainsKeyValuePair (KeyValuePair<TKey, TValue> pair)
 724                 {
 725                         TValue value;
 726                         if (!TryGetValue (pair.Key, out value))
 727                                 return false;
 728
 729                         return EqualityComparer<TValue>.Default.Equals (pair.Value, value);
 730                 }
 731
 732                 void ICollection.CopyTo (Array array, int index)
 733                 {
 734                         KeyValuePair<TKey, TValue> [] pairs = array as KeyValuePair<TKey, TValue> [];
 735                         if (pairs != null) {
 736                                 this.CopyTo (pairs, index);
 737                                 return;
 738                         }
 739
 740                         CopyToCheck (array, index);
 741                         DictionaryEntry [] entries = array as DictionaryEntry [];
 742                         if (entries != null) {
 743                                 Do_CopyTo (entries, index, delegate (TKey key, TValue value) { return new DictionaryEntry (key, value); });
 744                                 return;
 745                         }
 746
 747                         Do_ICollectionCopyTo<KeyValuePair<TKey, TValue>> (array, index, make_pair);
 748                 }
 749
 750                 IEnumerator IEnumerable.GetEnumerator ()
 751                 {
 752                         return new Enumerator (this);
 753                 }
 754
 755                 IEnumerator<KeyValuePair<TKey, TValue>> IEnumerable<KeyValuePair<TKey, TValue>>.GetEnumerator ()
 756                 {
 757                         return new Enumerator (this);
 758                 }
 759
 760                 IDictionaryEnumerator IDictionary.GetEnumerator ()
 761                 {
 762                         return new ShimEnumerator (this);
 763                 }
 764
 765                 public Enumerator GetEnumerator ()
 766                 {
 767                         return new Enumerator (this);
 768                 }
 769
 770                 [Serializable]
 771                 private class ShimEnumerator : IDictionaryEnumerator, IEnumerator
 772                 {
 773                         Enumerator host_enumerator;
 774                         public ShimEnumerator (Dictionary<TKey, TValue> host)
 775                         {
 776                                 host_enumerator = host.GetEnumerator ();
 777                         }
 778
 779                         public void Dispose ()
 780                         {
 781                                 host_enumerator.Dispose ();
 782                         }
 783
 784                         public bool MoveNext ()
 785                         {
 786                                 return host_enumerator.MoveNext ();
 787                         }
 788
 789                         public DictionaryEntry Entry {
 790                                 get { return ((IDictionaryEnumerator) host_enumerator).Entry; }
 791                         }
 792
 793                         public object Key {
 794                                 get { return host_enumerator.Current.Key; }
 795                         }
 796
 797                         public object Value {
 798                                 get { return host_enumerator.Current.Value; }
 799                         }
 800
 801                         // This is the raison d' etre of this $%!@$%@^@ class.
 802                         // We want: IDictionary.GetEnumerator ().Current is DictionaryEntry
 803                         public object Current {
 804                                 get { return Entry; }
 805                         }
 806
 807                         public void Reset ()
 808                         {
 809                                 host_enumerator.Reset ();
 810                         }
 811                 }
 812
 813                 [Serializable]
 814                 public struct Enumerator : IEnumerator<KeyValuePair<TKey,TValue>>,
 815                         IDisposable, IDictionaryEnumerator, IEnumerator
 816                 {
 817                         Dictionary<TKey, TValue> dictionary;
 818                         int next;
 819                         int stamp;
 820
 821                         internal KeyValuePair<TKey, TValue> current;
 822
 823                         internal Enumerator (Dictionary<TKey, TValue> dictionary)
 824                                 : this ()
 825                         {
 826                                 this.dictionary = dictionary;
 827                                 stamp = dictionary.generation;
 828                         }
 829
 830                         public bool MoveNext ()
 831                         {
 832                                 VerifyState ();
 833
 834                                 if (next < 0)
 835                                         return false;
 836
 837                                 while (next < dictionary.touchedSlots) {
 838                                         int cur = next++;
 839                                         if ((dictionary.linkSlots [cur].HashCode & HASH_FLAG) != 0) {
 840                                                 current = new KeyValuePair <TKey, TValue> (
 841                                                         dictionary.keySlots [cur],
 842                                                         dictionary.valueSlots [cur]
 843                                                         );
 844                                                 return true;
 845                                         }
 846                                 }
 847
 848                                 next = -1;
 849                                 return false;
 850                         }
 851
 852                         // No error checking happens.  Usually, Current is immediately preceded by a MoveNext(), so it's wasteful to check again
 853                         public KeyValuePair<TKey, TValue> Current {
 854                                 get { return current; }
 855                         }
 856
 857                         internal TKey CurrentKey {
 858                                 get {
 859                                         VerifyCurrent ();
 860                                         return current.Key;
 861                                 }
 862                         }
 863
 864                         internal TValue CurrentValue {
 865                                 get {
 866                                         VerifyCurrent ();
 867                                         return current.Value;
 868                                 }
 869                         }
 870
 871                         object IEnumerator.Current {
 872                                 get {
 873                                         VerifyCurrent ();
 874                                         return current;
 875                                 }
 876                         }
 877
 878                         void IEnumerator.Reset ()
 879                         {
 880                                 Reset ();
 881                         }
 882
 883                         internal void Reset ()
 884                         {
 885                                 VerifyState ();
 886                                 next = 0;
 887                         }
 888
 889                         DictionaryEntry IDictionaryEnumerator.Entry {
 890                                 get {
 891                                         VerifyCurrent ();
 892                                         return new DictionaryEntry (current.Key, current.Value);
 893                                 }
 894                         }
 895
 896                         object IDictionaryEnumerator.Key {
 897                                 get { return CurrentKey; }
 898                         }
 899
 900                         object IDictionaryEnumerator.Value {
 901                                 get { return CurrentValue; }
 902                         }
 903
 904                         void VerifyState ()
 905                         {
 906                                 if (dictionary == null)
 907                                         throw new ObjectDisposedException (null);
 908                                 if (dictionary.generation != stamp)
 909                                         throw new InvalidOperationException ("out of sync");
 910                         }
 911
 912                         void VerifyCurrent ()
 913                         {
 914                                 VerifyState ();
 915                                 if (next <= 0)
 916                                         throw new InvalidOperationException ("Current is not valid");
 917                         }
 918
 919                         public void Dispose ()
 920                         {
 921                                 dictionary = null;
 922                         }
 923                 }
 924
 925                 // This collection is a read only collection
 926                 [Serializable]
 927                 public sealed class KeyCollection : ICollection<TKey>, IEnumerable<TKey>, ICollection, IEnumerable {
 928                         Dictionary<TKey, TValue> dictionary;
 929
 930                         public KeyCollection (Dictionary<TKey, TValue> dictionary)
 931                         {
 932                                 if (dictionary == null)
 933                                         throw new ArgumentNullException ("dictionary");
 934                                 this.dictionary = dictionary;
 935                         }
 936
 937
 938                         public void CopyTo (TKey [] array, int index)
 939                         {
 940                                 dictionary.CopyToCheck (array, index);
 941                                 dictionary.Do_CopyTo<TKey, TKey> (array, index, pick_key);
 942                         }
 943
 944                         public Enumerator GetEnumerator ()
 945                         {
 946                                 return new Enumerator (dictionary);
 947                         }
 948
 949                         void ICollection<TKey>.Add (TKey item)
 950                         {
 951                                 throw new NotSupportedException ("this is a read-only collection");
 952                         }
 953
 954                         void ICollection<TKey>.Clear ()
 955                         {
 956                                 throw new NotSupportedException ("this is a read-only collection");
 957                         }
 958
 959                         bool ICollection<TKey>.Contains (TKey item)
 960                         {
 961                                 return dictionary.ContainsKey (item);
 962                         }
 963
 964                         bool ICollection<TKey>.Remove (TKey item)
 965                         {
 966                                 throw new NotSupportedException ("this is a read-only collection");
 967                         }
 968
 969                         IEnumerator<TKey> IEnumerable<TKey>.GetEnumerator ()
 970                         {
 971                                 return this.GetEnumerator ();
 972                         }
 973
 974                         void ICollection.CopyTo (Array array, int index)
 975                         {
 976                                 var target = array as TKey [];
 977                                 if (target != null) {
 978                                         CopyTo (target, index);
 979                                         return;
 980                                 }
 981
 982                                 dictionary.CopyToCheck (array, index);
 983                                 dictionary.Do_ICollectionCopyTo<TKey> (array, index, pick_key);
 984                         }
 985
 986                         IEnumerator IEnumerable.GetEnumerator ()
 987                         {
 988                                 return this.GetEnumerator ();
 989                         }
 990
 991                         public int Count {
 992                                 get { return dictionary.Count; }
 993                         }
 994
 995                         bool ICollection<TKey>.IsReadOnly {
 996                                 get { return true; }
 997                         }
 998
 999                         bool ICollection.IsSynchronized {
1000                                 get { return false; }
1001                         }
1002
1003                         object ICollection.SyncRoot {
1004                                 get { return ((ICollection) dictionary).SyncRoot; }
1005                         }
1006
1007                         [Serializable]
1008                         public struct Enumerator : IEnumerator<TKey>, IDisposable, IEnumerator {
1009                                 Dictionary<TKey, TValue>.Enumerator host_enumerator;
1010
1011                                 internal Enumerator (Dictionary<TKey, TValue> host)
1012                                 {
1013                                         host_enumerator = host.GetEnumerator ();
1014                                 }
1015
1016                                 public void Dispose ()
1017                                 {
1018                                         host_enumerator.Dispose ();
1019                                 }
1020
1021                                 public bool MoveNext ()
1022                                 {
1023                                         return host_enumerator.MoveNext ();
1024                                 }
1025
1026                                 public TKey Current {
1027                                         get { return host_enumerator.current.Key; }
1028                                 }
1029
1030                                 object IEnumerator.Current {
1031                                         get { return host_enumerator.CurrentKey; }
1032                                 }
1033
1034                                 void IEnumerator.Reset ()
1035                                 {
1036                                         host_enumerator.Reset ();
1037                                 }
1038                         }
1039                 }
1040
1041                 // This collection is a read only collection
1042                 [Serializable]
1043                 public sealed class ValueCollection : ICollection<TValue>, IEnumerable<TValue>, ICollection, IEnumerable {
1044                         Dictionary<TKey, TValue> dictionary;
1045
1046                         public ValueCollection (Dictionary<TKey, TValue> dictionary)
1047                         {
1048                                 if (dictionary == null)
1049                                         throw new ArgumentNullException ("dictionary");
1050                                 this.dictionary = dictionary;
1051                         }
1052
1053                         public void CopyTo (TValue [] array, int index)
1054                         {
1055                                 dictionary.CopyToCheck (array, index);
1056                                 dictionary.Do_CopyTo<TValue, TValue> (array, index, pick_value);
1057                         }
1058
1059                         public Enumerator GetEnumerator ()
1060                         {
1061                                 return new Enumerator (dictionary);
1062                         }
1063
1064                         void ICollection<TValue>.Add (TValue item)
1065                         {
1066                                 throw new NotSupportedException ("this is a read-only collection");
1067                         }
1068
1069                         void ICollection<TValue>.Clear ()
1070                         {
1071                                 throw new NotSupportedException ("this is a read-only collection");
1072                         }
1073
1074                         bool ICollection<TValue>.Contains (TValue item)
1075                         {
1076                                 return dictionary.ContainsValue (item);
1077                         }
1078
1079                         bool ICollection<TValue>.Remove (TValue item)
1080                         {
1081                                 throw new NotSupportedException ("this is a read-only collection");
1082                         }
1083
1084                         IEnumerator<TValue> IEnumerable<TValue>.GetEnumerator ()
1085                         {
1086                                 return this.GetEnumerator ();
1087                         }
1088
1089                         void ICollection.CopyTo (Array array, int index)
1090                         {
1091                                 var target = array as TValue [];
1092                                 if (target != null) {
1093                                         CopyTo (target, index);
1094                                         return;
1095                                 }
1096
1097                                 dictionary.CopyToCheck (array, index);
1098                                 dictionary.Do_ICollectionCopyTo<TValue> (array, index, pick_value);
1099                         }
1100
1101                         IEnumerator IEnumerable.GetEnumerator ()
1102                         {
1103                                 return this.GetEnumerator ();
1104                         }
1105
1106                         public int Count {
1107                                 get { return dictionary.Count; }
1108                         }
1109
1110                         bool ICollection<TValue>.IsReadOnly {
1111                                 get { return true; }
1112                         }
1113
1114                         bool ICollection.IsSynchronized {
1115                                 get { return false; }
1116                         }
1117
1118                         object ICollection.SyncRoot {
1119                                 get { return ((ICollection) dictionary).SyncRoot; }
1120                         }
1121
1122                         [Serializable]
1123                         public struct Enumerator : IEnumerator<TValue>, IDisposable, IEnumerator {
1124                                 Dictionary<TKey, TValue>.Enumerator host_enumerator;
1125
1126                                 internal Enumerator (Dictionary<TKey,TValue> host)
1127                                 {
1128                                         host_enumerator = host.GetEnumerator ();
1129                                 }
1130
1131                                 public void Dispose ()
1132                                 {
1133                                         host_enumerator.Dispose ();
1134                                 }
1135
1136                                 public bool MoveNext ()
1137                                 {
1138                                         return host_enumerator.MoveNext ();
1139                                 }
1140
1141                                 public TValue Current {
1142                                         get { return host_enumerator.current.Value; }
1143                                 }
1144
1145                                 object IEnumerator.Current {
1146                                         get { return host_enumerator.CurrentValue; }
1147                                 }
1148
1149                                 void IEnumerator.Reset ()
1150                                 {
1151                                         host_enumerator.Reset ();
1152                                 }
1153                         }
1154                 }
1155         }
1156 }
1157 #endif