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 //
  10 //
  11 // Copyright (C) 2004 Novell, Inc (http://www.novell.com)
  12 // Copyright (C) 2005 David Waite
  13 //
  14 // Permission is hereby granted, free of charge, to any person obtaining
  15 // a copy of this software and associated documentation files (the
  16 // "Software"), to deal in the Software without restriction, including
  17 // without limitation the rights to use, copy, modify, merge, publish,
  18 // distribute, sublicense, and/or sell copies of the Software, and to
  19 // permit persons to whom the Software is furnished to do so, subject to
  20 // the following conditions:
  21 //
  22 // The above copyright notice and this permission notice shall be
  23 // included in all copies or substantial portions of the Software.
  24 //
  25 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  26 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  27 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  28 // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  29 // LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  30 // OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  31 // WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  32 //
  33
  34 #if NET_2_0
  35
  36 using System;
  37 using System.Collections;
  38 using System.Collections.Generic;
  39 using System.Runtime.Serialization;
  40 using System.Security.Permissions;
  41 using System.Runtime.InteropServices;
  42
  43 namespace System.Collections.Generic {
  44
  45         [ComVisible(true)]
  46         [Serializable]
  47         public class Dictionary<TKey, TValue> : IDictionary<TKey, TValue>,
  48                 IDictionary,
  49                 ICollection,
  50                 ICollection<KeyValuePair<TKey, TValue>>,
  51                 IEnumerable<KeyValuePair<TKey, TValue>>,
  52                 ISerializable,
  53                 IDeserializationCallback
  54         {
  55                 const int INITIAL_SIZE = 10;
  56                 const float DEFAULT_LOAD_FACTOR = (90f / 100);
  57
  58                 private class Slot {
  59                         // Can't use KeyValuePair here since the JIT won't inline the Key/Value accessors
  60                         public TKey Key;
  61                         public TValue Value;
  62                         public Slot Next;
  63
  64                         public Slot (TKey Key, TValue Value, Slot Next)
  65                         {
  66                                 this.Key = Key;
  67                                 this.Value = Value;
  68                                 this.Next = Next;
  69                         }
  70                 }
  71
  72                 Slot [] table;
  73                 int used_slots;
  74                 private int threshold;
  75
  76                 IEqualityComparer<TKey> hcp;
  77                 SerializationInfo serialization_info;
  78
  79                 private uint generation;
  80
  81                 public int Count {
  82                         get { return used_slots; }
  83                         /* FIXME: this should be 'private' not 'internal'.  */
  84                         internal set {
  85                                 used_slots = value;
  86                                 ++generation;
  87                         }
  88                 }
  89
  90                 // This is perf critical so inline calls etc.
  91                 public TValue this [TKey key] {
  92                         get {
  93                                 if (key == null)
  94                                         throw new ArgumentNullException ("key");
  95                                 uint size = (uint)table.Length;
  96                                 uint i = ((uint)hcp.GetHashCode (key) & Int32.MaxValue) % size;
  97                                 Slot slot = table [i];
  98                                 while (slot != null) {
  99                                         // The ordering is important for compatibility with MS and strange
 100                                         // Object.Equals () implementations
 101                                         if (hcp.Equals (slot.Key, key))
 102                                                 return slot.Value;
 103                                         slot = slot.Next;
 104                                 }
 105                                 throw new KeyNotFoundException ();
 106                         }
 107
 108                         set {
 109                                 int index;
 110                                 Slot prev = GetPrev (key, out index);
 111                                 Slot slot = prev == null ? table [index] : prev.Next;
 112                                 if (slot == null) {
 113                                         if (Count++ >= threshold) {
 114                                                 Resize ();
 115                                                 index = DoHash (key);
 116                                         }
 117                                         table [index] = new Slot (key, value, table [index]);
 118                                 } else {
 119                                         ++generation;
 120                                         if (prev != null) {
 121                                                 // move-to-front on update
 122                                                 prev.Next = slot.Next;
 123                                                 slot.Next = table [index];
 124                                                 table [index] = slot;
 125                                         }
 126                                         slot.Key = key;
 127                                         slot.Value = value;
 128                                 }
 129                         }
 130                 }
 131
 132                 public Dictionary ()
 133                 {
 134                         Init (INITIAL_SIZE, null);
 135                 }
 136
 137                 public Dictionary (IEqualityComparer<TKey> comparer)
 138                 {
 139                         Init (INITIAL_SIZE, comparer);
 140                 }
 141
 142                 public Dictionary (IDictionary<TKey, TValue> dictionary)
 143                         : this (dictionary, null)
 144                 {
 145                 }
 146
 147                 public Dictionary (int capacity)
 148                 {
 149                         Init (capacity, null);
 150                 }
 151
 152                 public Dictionary (IDictionary<TKey, TValue> dictionary, IEqualityComparer<TKey> comparer)
 153                 {
 154                         if (dictionary == null)
 155                                 throw new ArgumentNullException ("dictionary");
 156                         int capacity = dictionary.Count;
 157                         Init (capacity, comparer);
 158                         foreach (KeyValuePair<TKey, TValue> entry in dictionary)
 159                                 this.Add (entry.Key, entry.Value);
 160                 }
 161
 162                 public Dictionary (int capacity, IEqualityComparer<TKey> comparer)
 163                 {
 164                         Init (capacity, comparer);
 165                 }
 166
 167                 protected Dictionary (SerializationInfo info, StreamingContext context)
 168                 {
 169                         serialization_info = info;
 170                 }
 171
 172                 void SetThreshold ()
 173                 {
 174                         threshold = (int)(table.Length * DEFAULT_LOAD_FACTOR);
 175                         if (threshold == 0 && table.Length > 0)
 176                                 threshold = 1;
 177                 }
 178
 179                 private void Init (int capacity, IEqualityComparer<TKey> hcp)
 180                 {
 181                         if (capacity < 0)
 182                                 throw new ArgumentOutOfRangeException ("capacity");
 183                         this.hcp = (hcp != null) ? hcp : EqualityComparer<TKey>.Default;
 184                         if (capacity == 0)
 185                                 capacity = INITIAL_SIZE;
 186
 187                         /* Modify capacity so 'capacity' elements can be added without resizing */
 188                         capacity = (int)(capacity / DEFAULT_LOAD_FACTOR) + 1;
 189
 190                         table = new Slot [capacity];
 191                         SetThreshold ();
 192                         generation = 0;
 193                 }
 194
 195                 void CopyTo (KeyValuePair<TKey, TValue> [] array, int index)
 196                 {
 197                         if (array == null)
 198                                 throw new ArgumentNullException ("array");
 199                         if (index < 0)
 200                                 throw new ArgumentOutOfRangeException ("index");
 201                         // we want no exception for index==array.Length && Count == 0
 202                         if (index > array.Length)
 203                                 throw new ArgumentException ("index larger than largest valid index of array");
 204                         if (array.Length - index < Count)
 205                                 throw new ArgumentException ("Destination array cannot hold the requested elements!");
 206
 207                         for (int i = 0; i < table.Length; ++i) {
 208                                 for (Slot slot = table [i]; slot != null; slot = slot.Next)
 209                                         array [index++] = new KeyValuePair<TKey, TValue> (slot.Key, slot.Value);
 210                         }
 211                 }
 212
 213                 private void Resize ()
 214                 {
 215                         // From the SDK docs:
 216                         //       Hashtable is automatically increased
 217                         //       to the smallest prime number that is larger
 218                         //       than twice the current number of Hashtable buckets
 219                         uint newSize = (uint) Hashtable.ToPrime ((table.Length << 1) | 1);
 220
 221                         Slot nextslot = null;
 222                         Slot [] oldTable = table;
 223
 224                         table = new Slot [newSize];
 225                         SetThreshold ();
 226
 227                         int index;
 228                         for (int i = 0; i < oldTable.Length; i++) {
 229                                 for (Slot slot = oldTable [i]; slot != null; slot = nextslot) {
 230                                         nextslot = slot.Next;
 231
 232                                         index = DoHash (slot.Key);
 233                                         slot.Next = table [index];
 234                                         table [index] = slot;
 235                                 }
 236                         }
 237                 }
 238
 239                 public void Add (TKey key, TValue value)
 240                 {
 241                         int index;
 242                         Slot slot = GetSlot (key, out index);
 243                         if (slot != null)
 244                                 throw new ArgumentException ("An element with the same key already exists in the dictionary.");
 245                         DoAdd (index, key, value);
 246                 }
 247
 248                 void DoAdd (int index, TKey key, TValue value)
 249                 {
 250                         if (Count++ >= threshold) {
 251                                 Resize ();
 252                                 index = DoHash (key);
 253                         }
 254                         table [index] = new Slot (key, value, table [index]);
 255                 }
 256
 257                 private int DoHash (TKey key)
 258                 {
 259                         uint size = (uint)this.table.Length;
 260                         uint h = (uint)hcp.GetHashCode (key) & Int32.MaxValue;
 261                         int spot = (int) (h % size);
 262                         return spot;
 263                 }
 264
 265                 public IEqualityComparer<TKey> Comparer {
 266                         get { return hcp; }
 267                 }
 268
 269                 public void Clear ()
 270                 {
 271                         Count = 0;
 272                         for (int i = 0; i < table.Length; i++)
 273                                 table [i] = null;
 274                 }
 275
 276                 public bool ContainsKey (TKey key)
 277                 {
 278                         int index;
 279                         return GetSlot (key, out index) != null;
 280                 }
 281
 282                 public bool ContainsValue (TValue value)
 283                 {
 284                         IEqualityComparer<TValue> cmp = EqualityComparer<TValue>.Default;
 285
 286                         for (int i = 0; i < table.Length; ++i) {
 287                                 for (Slot slot = table [i]; slot != null; slot = slot.Next) {
 288                                         if (cmp.Equals (slot.Value, value))
 289                                                 return true;
 290                                 }
 291                         }
 292                         return false;
 293                 }
 294
 295                 [SecurityPermission (SecurityAction.LinkDemand, Flags=SecurityPermissionFlag.SerializationFormatter)]
 296                 public virtual void GetObjectData (SerializationInfo info, StreamingContext context)
 297                 {
 298                         if (info == null)
 299                                 throw new ArgumentNullException ("info");
 300
 301                         info.AddValue ("hcp", hcp);
 302                         KeyValuePair<TKey, TValue> [] data = null;
 303                         if (Count > 0) {
 304                                 data = new KeyValuePair<TKey,TValue> [Count];
 305                                 CopyTo (data, 0);
 306                         }
 307                         info.AddValue ("data", data);
 308                         info.AddValue ("buckets_hint", table.Length);
 309                 }
 310
 311                 public virtual void OnDeserialization (object sender)
 312                 {
 313                         if (serialization_info == null)
 314                                 return;
 315
 316                         hcp = (IEqualityComparer<TKey>) serialization_info.GetValue ("hcp", typeof (IEqualityComparer<TKey>));
 317                         KeyValuePair<TKey, TValue> [] data =
 318                                 (KeyValuePair<TKey, TValue> [])
 319                                 serialization_info.GetValue ("data", typeof (KeyValuePair<TKey, TValue> []));
 320
 321                         int buckets = serialization_info.GetInt32 ("buckets_hint");
 322                         if (buckets < INITIAL_SIZE)
 323                                 buckets = INITIAL_SIZE;
 324
 325                         table = new Slot [buckets];
 326                         SetThreshold ();
 327                         Count = 0;
 328
 329                         if (data != null) {
 330                                 for (int i = 0; i < data.Length; ++i)
 331                                         Add (data [i].Key, data [i].Value);
 332                         }
 333                         serialization_info = null;
 334                 }
 335
 336                 public bool Remove (TKey key)
 337                 {
 338                         int index;
 339                         Slot prev = GetPrev (key, out index);
 340                         Slot slot = prev == null ? table [index] : prev.Next;
 341                         if (slot == null)
 342                                 return false;
 343                         --Count;
 344                         if (prev == null)
 345                                 table [index] = slot.Next;
 346                         else
 347                                 prev.Next = slot.Next;
 348                         return true;
 349                 }
 350
 351                 //
 352                 // Return the predecessor of the slot containing 'key', and set 'index' to the
 353                 // chain the key was found in.
 354                 // If the key is not found, return null and set 'index' to the chain that would've
 355                 // contained the key.
 356                 //
 357                 private Slot GetPrev (TKey key, out int index)
 358                 {
 359                         // This method is perf critical so inline DoHash () etc.
 360                         if (key == null)
 361                                 throw new ArgumentNullException ("key");
 362                         uint size = (uint)table.Length;
 363                         // Use uint to help ABCREM
 364                         uint i = ((uint)hcp.GetHashCode (key) & Int32.MaxValue) % size;
 365                         Slot slot = table [i];
 366                         if (slot != null) {
 367                                 Slot prev = null;
 368                                 do {
 369                                         // The ordering is important for compatibility with MS and strange
 370                                         // Object.Equals () implementations
 371                                         if (hcp.Equals (slot.Key, key))
 372                                                 break;
 373                                         prev = slot;
 374                                         slot = slot.Next;
 375                                 } while (slot != null);
 376                                 index = (int)i;
 377                                 return prev;
 378                         }
 379                         else {
 380                                 index = (int)i;
 381                                 return null;
 382                         }
 383                 }
 384
 385                 private Slot GetSlot (TKey key, out int index)
 386                 {
 387                         Slot prev = GetPrev (key, out index);
 388                         return prev == null ? table [index] : prev.Next;
 389                 }
 390
 391                 public bool TryGetValue (TKey key, out TValue value)
 392                 {
 393                         int index;
 394                         Slot slot = GetSlot (key, out index);
 395                         bool found = slot != null;
 396                         value = found ? slot.Value : default (TValue);
 397                         return found;
 398                 }
 399
 400                 ICollection<TKey> IDictionary<TKey, TValue>.Keys {
 401                         get { return Keys; }
 402                 }
 403
 404                 ICollection<TValue> IDictionary<TKey, TValue>.Values {
 405                         get { return Values; }
 406                 }
 407
 408                 public KeyCollection Keys {
 409                         get { return new KeyCollection (this); }
 410                 }
 411
 412                 public ValueCollection Values {
 413                         get { return new ValueCollection (this); }
 414                 }
 415
 416                 ICollection IDictionary.Keys {
 417                         get { return Keys; }
 418                 }
 419
 420                 ICollection IDictionary.Values {
 421                         get { return Values; }
 422                 }
 423
 424                 bool IDictionary.IsFixedSize {
 425                         get { return false; }
 426                 }
 427
 428                 bool IDictionary.IsReadOnly {
 429                         get { return false; }
 430                 }
 431
 432                 TKey ToTKey (object key)
 433                 {
 434                         if (key == null)
 435                                 throw new ArgumentNullException ("key");
 436                         if (!(key is TKey))
 437                                 throw new ArgumentException ("not of type: " + typeof (TKey).ToString (), "key");
 438                         return (TKey) key;
 439                 }
 440
 441                 TValue ToTValue (object value)
 442                 {
 443                         if (!(value is TValue))
 444                                 throw new ArgumentException ("not of type: " + typeof (TValue).ToString (), "value");
 445                         return (TValue) value;
 446                 }
 447
 448                 object IDictionary.this [object key] {
 449                         get { return this [ToTKey (key)]; }
 450                         set { this [ToTKey (key)] = ToTValue (value); }
 451                 }
 452
 453                 void IDictionary.Add (object key, object value)
 454                 {
 455                         this.Add (ToTKey (key), ToTValue (value));
 456                 }
 457
 458                 bool IDictionary.Contains (object key)
 459                 {
 460                         if (key == null)
 461                                 throw new ArgumentNullException ("key");
 462                         if (key is TKey)
 463                                 return ContainsKey ((TKey) key);
 464                         return false;
 465                 }
 466
 467                 void IDictionary.Remove (object key)
 468                 {
 469                         if (key == null)
 470                                 throw new ArgumentNullException ("key");
 471                         if (key is TKey)
 472                                 Remove ((TKey) key);
 473                 }
 474
 475                 bool ICollection.IsSynchronized {
 476                         get { return false; }
 477                 }
 478
 479                 object ICollection.SyncRoot {
 480                         get { return this; }
 481                 }
 482
 483                 bool ICollection<KeyValuePair<TKey, TValue>>.IsReadOnly {
 484                         get { return false; }
 485                 }
 486
 487                 void ICollection<KeyValuePair<TKey, TValue>>.Add (KeyValuePair<TKey, TValue> keyValuePair)
 488                 {
 489                         Add (keyValuePair.Key, keyValuePair.Value);
 490                 }
 491
 492                 bool ICollection<KeyValuePair<TKey, TValue>>.Contains (KeyValuePair<TKey, TValue> keyValuePair)
 493                 {
 494                         return this.ContainsKey (keyValuePair.Key);
 495                 }
 496
 497                 void ICollection<KeyValuePair<TKey, TValue>>.CopyTo (KeyValuePair<TKey, TValue> [] array, int index)
 498                 {
 499                         this.CopyTo (array, index);
 500                 }
 501
 502                 bool ICollection<KeyValuePair<TKey, TValue>>.Remove (KeyValuePair<TKey, TValue> keyValuePair)
 503                 {
 504                         return Remove (keyValuePair.Key);
 505                 }
 506
 507                 void ICollection.CopyTo (Array array, int index)
 508                 {
 509                         if (array == null)
 510                                 throw new ArgumentNullException ("array");
 511                         if (index < 0)
 512                                 throw new ArgumentOutOfRangeException ("index");
 513                         // we want no exception for index==array.Length && Count == 0
 514                         if (index > array.Length)
 515                                 throw new ArgumentException ("index larger than largest valid index of array");
 516                         if (array.Length - index < Count)
 517                                 throw new ArgumentException ("Destination array cannot hold the requested elements!");
 518
 519                         for (int i = 0; i < table.Length; ++i) {
 520                                 for (Slot slot = table [i]; slot != null; slot = slot.Next)
 521                                         array.SetValue (new DictionaryEntry (slot.Key, slot.Value), index++);
 522                         }
 523                 }
 524
 525                 IEnumerator IEnumerable.GetEnumerator ()
 526                 {
 527                         return new Enumerator (this);
 528                 }
 529
 530                 IEnumerator<KeyValuePair<TKey, TValue>> IEnumerable<KeyValuePair<TKey, TValue>>.GetEnumerator ()
 531                 {
 532                         return new Enumerator (this);
 533                 }
 534
 535                 IDictionaryEnumerator IDictionary.GetEnumerator ()
 536                 {
 537                         return new ShimEnumerator (this);
 538                 }
 539
 540                 public Enumerator GetEnumerator ()
 541                 {
 542                         return new Enumerator (this);
 543                 }
 544
 545                 [Serializable]
 546                 private class ShimEnumerator : IDictionaryEnumerator, IEnumerator
 547                 {
 548                         Enumerator host_enumerator;
 549                         public ShimEnumerator (Dictionary<TKey, TValue> host)
 550                         {
 551                                 host_enumerator = host.GetEnumerator ();
 552                         }
 553
 554                         public void Dispose ()
 555                         {
 556                                 host_enumerator.Dispose ();
 557                         }
 558
 559                         public bool MoveNext ()
 560                         {
 561                                 return host_enumerator.MoveNext ();
 562                         }
 563
 564                         public DictionaryEntry Entry {
 565                                 get { return ((IDictionaryEnumerator) host_enumerator).Entry; }
 566                         }
 567
 568                         public object Key {
 569                                 get { return host_enumerator.Current.Key; }
 570                         }
 571
 572                         public object Value {
 573                                 get { return host_enumerator.Current.Value; }
 574                         }
 575
 576                         // This is the raison d' etre of this $%!@$%@^@ class.
 577                         // We want: IDictionary.GetEnumerator ().Current is DictionaryEntry
 578                         public object Current {
 579                                 get { return Entry; }
 580                         }
 581
 582                         public void Reset ()
 583                         {
 584                                 ((IEnumerator)host_enumerator).Reset ();
 585                         }
 586                 }
 587
 588                 [Serializable]
 589                 public struct Enumerator : IEnumerator<KeyValuePair<TKey,TValue>>,
 590                         IDisposable, IDictionaryEnumerator, IEnumerator
 591                 {
 592                         Dictionary<TKey, TValue> dictionary;
 593                         uint stamp;
 594
 595                         Slot current;
 596                         int next_index;
 597
 598                         internal Enumerator (Dictionary<TKey, TValue> dictionary)
 599                         {
 600                                 this.dictionary = dictionary;
 601                                 stamp = dictionary.generation;
 602
 603                                 // The following stanza is identical to IEnumerator.Reset (),
 604                                 // but because of the definite assignment rule, we cannot call it here.
 605                                 next_index = 0;
 606                                 current = null;
 607                         }
 608
 609                         public bool MoveNext ()
 610                         {
 611                                 VerifyState ();
 612
 613                                 // Pre-condition: current == null => this is the first call to MoveNext ()
 614                                 if (current != null)
 615                                         current = current.Next;
 616
 617                                 while (current == null && next_index < dictionary.table.Length)
 618                                         current = dictionary.table [next_index++];
 619
 620                                 // Post-condition: current == null => this is the last call to MoveNext()
 621                                 return current != null;
 622                         }
 623
 624                         public KeyValuePair<TKey, TValue> Current {
 625                                 get {
 626                                         Slot s = CurrentSlot ();
 627                                         return new KeyValuePair <TKey, TValue> (s.Key, s.Value);
 628                                 }
 629                         }
 630
 631                         object IEnumerator.Current {
 632                                 get { return Current; }
 633                         }
 634
 635                         void IEnumerator.Reset ()
 636                         {
 637                                 next_index = 0;
 638                                 current = null;
 639                         }
 640
 641                         DictionaryEntry IDictionaryEnumerator.Entry {
 642                                 get {
 643                                         Slot s = CurrentSlot ();
 644                                         return new DictionaryEntry (s.Key, s.Value);
 645                                 }
 646                         }
 647
 648                         object IDictionaryEnumerator.Key {
 649                                 get { return Current.Key; }
 650                         }
 651
 652                         object IDictionaryEnumerator.Value {
 653                                 get { return Current.Value; }
 654                         }
 655
 656                         void VerifyState ()
 657                         {
 658                                 if (dictionary == null)
 659                                         throw new ObjectDisposedException (null);
 660                                 if (dictionary.generation != stamp)
 661                                         throw new InvalidOperationException ("out of sync");
 662                         }
 663
 664                         Slot CurrentSlot ()
 665                         {
 666                                 VerifyState ();
 667                                 if (current == null)
 668                                         throw new InvalidOperationException ("Current is not valid");
 669                                 return current;
 670                         }
 671
 672                         public void Dispose ()
 673                         {
 674                                 current = null;
 675                                 dictionary = null;
 676                         }
 677                 }
 678
 679                 // This collection is a read only collection
 680                 [Serializable]
 681                 public sealed class KeyCollection : ICollection<TKey>, IEnumerable<TKey>, ICollection, IEnumerable {
 682                         Dictionary<TKey, TValue> dictionary;
 683
 684                         public KeyCollection (Dictionary<TKey, TValue> dictionary)
 685                         {
 686                                 if (dictionary == null)
 687                                         throw new ArgumentNullException ("dictionary");
 688                                 this.dictionary = dictionary;
 689                         }
 690
 691                         public void CopyTo (TKey [] array, int index)
 692                         {
 693                                 if (array == null)
 694                                         throw new ArgumentNullException ("array");
 695                                 if (index < 0)
 696                                         throw new ArgumentOutOfRangeException ("index");
 697                                 // we want no exception for index==array.Length && dictionary.Count == 0
 698                                 if (index > array.Length)
 699                                         throw new ArgumentException ("index larger than largest valid index of array");
 700                                 if (array.Length - index < dictionary.Count)
 701                                         throw new ArgumentException ("Destination array cannot hold the requested elements!");
 702
 703                                 foreach (TKey k in this)
 704                                         array [index++] = k;
 705                         }
 706
 707                         public Enumerator GetEnumerator ()
 708                         {
 709                                 return new Enumerator (dictionary);
 710                         }
 711
 712                         void ICollection<TKey>.Add (TKey item)
 713                         {
 714                                 throw new NotSupportedException ("this is a read-only collection");
 715                         }
 716
 717                         void ICollection<TKey>.Clear ()
 718                         {
 719                                 throw new NotSupportedException ("this is a read-only collection");
 720                         }
 721
 722                         bool ICollection<TKey>.Contains (TKey item)
 723                         {
 724                                 return dictionary.ContainsKey (item);
 725                         }
 726
 727                         bool ICollection<TKey>.Remove (TKey item)
 728                         {
 729                                 throw new NotSupportedException ("this is a read-only collection");
 730                         }
 731
 732                         IEnumerator<TKey> IEnumerable<TKey>.GetEnumerator ()
 733                         {
 734                                 return this.GetEnumerator ();
 735                         }
 736
 737                         void ICollection.CopyTo (Array array, int index)
 738                         {
 739                                 CopyTo ((TKey []) array, index);
 740                         }
 741
 742                         IEnumerator IEnumerable.GetEnumerator ()
 743                         {
 744                                 return this.GetEnumerator ();
 745                         }
 746
 747                         public int Count {
 748                                 get { return dictionary.Count; }
 749                         }
 750
 751                         bool ICollection<TKey>.IsReadOnly {
 752                                 get { return true; }
 753                         }
 754
 755                         bool ICollection.IsSynchronized {
 756                                 get { return false; }
 757                         }
 758
 759                         object ICollection.SyncRoot {
 760                                 get { return ((ICollection) dictionary).SyncRoot; }
 761                         }
 762
 763                         [Serializable]
 764                         public struct Enumerator : IEnumerator<TKey>, IDisposable, IEnumerator {
 765                                 Dictionary<TKey, TValue>.Enumerator host_enumerator;
 766
 767                                 internal Enumerator (Dictionary<TKey, TValue> host)
 768                                 {
 769                                         host_enumerator = host.GetEnumerator ();
 770                                 }
 771
 772                                 public void Dispose ()
 773                                 {
 774                                         host_enumerator.Dispose ();
 775                                 }
 776
 777                                 public bool MoveNext ()
 778                                 {
 779                                         return host_enumerator.MoveNext ();
 780                                 }
 781
 782                                 public TKey Current {
 783                                         get { return host_enumerator.Current.Key; }
 784                                 }
 785
 786                                 object IEnumerator.Current {
 787                                         get { return host_enumerator.Current.Key; }
 788                                 }
 789
 790                                 void IEnumerator.Reset ()
 791                                 {
 792                                         ((IEnumerator)host_enumerator).Reset ();
 793                                 }
 794                         }
 795                 }
 796
 797                 // This collection is a read only collection
 798                 [Serializable]
 799                 public sealed class ValueCollection : ICollection<TValue>, IEnumerable<TValue>, ICollection, IEnumerable {
 800                         Dictionary<TKey, TValue> dictionary;
 801
 802                         public ValueCollection (Dictionary<TKey, TValue> dictionary)
 803                         {
 804                                 if (dictionary == null)
 805                                         throw new ArgumentNullException ("dictionary");
 806                                 this.dictionary = dictionary;
 807                         }
 808
 809                         public void CopyTo (TValue [] array, int index)
 810                         {
 811                                 if (array == null)
 812                                         throw new ArgumentNullException ("array");
 813                                 if (index < 0)
 814                                         throw new ArgumentOutOfRangeException ("index");
 815                                 // we want no exception for index==array.Length && dictionary.Count == 0
 816                                 if (index > array.Length)
 817                                         throw new ArgumentException ("index larger than largest valid index of array");
 818                                 if (array.Length - index < dictionary.Count)
 819                                         throw new ArgumentException ("Destination array cannot hold the requested elements!");
 820
 821                                 foreach (TValue k in this)
 822                                         array [index++] = k;
 823                         }
 824
 825                         public Enumerator GetEnumerator ()
 826                         {
 827                                 return new Enumerator (dictionary);
 828                         }
 829
 830                         void ICollection<TValue>.Add (TValue item)
 831                         {
 832                                 throw new NotSupportedException ("this is a read-only collection");
 833                         }
 834
 835                         void ICollection<TValue>.Clear ()
 836                         {
 837                                 throw new NotSupportedException ("this is a read-only collection");
 838                         }
 839
 840                         bool ICollection<TValue>.Contains (TValue item)
 841                         {
 842                                 return dictionary.ContainsValue (item);
 843                         }
 844
 845                         bool ICollection<TValue>.Remove (TValue item)
 846                         {
 847                                 throw new NotSupportedException ("this is a read-only collection");
 848                         }
 849
 850                         IEnumerator<TValue> IEnumerable<TValue>.GetEnumerator ()
 851                         {
 852                                 return this.GetEnumerator ();
 853                         }
 854
 855                         void ICollection.CopyTo (Array array, int index)
 856                         {
 857                                 CopyTo ((TValue []) array, index);
 858                         }
 859
 860                         IEnumerator IEnumerable.GetEnumerator ()
 861                         {
 862                                 return this.GetEnumerator ();
 863                         }
 864
 865                         public int Count {
 866                                 get { return dictionary.Count; }
 867                         }
 868
 869                         bool ICollection<TValue>.IsReadOnly {
 870                                 get { return true; }
 871                         }
 872
 873                         bool ICollection.IsSynchronized {
 874                                 get { return false; }
 875                         }
 876
 877                         object ICollection.SyncRoot {
 878                                 get { return ((ICollection) dictionary).SyncRoot; }
 879                         }
 880
 881                         [Serializable]
 882                         public struct Enumerator : IEnumerator<TValue>, IDisposable, IEnumerator {
 883                                 Dictionary<TKey, TValue>.Enumerator host_enumerator;
 884
 885                                 internal Enumerator (Dictionary<TKey,TValue> host)
 886                                 {
 887                                         host_enumerator = host.GetEnumerator ();
 888                                 }
 889
 890                                 public void Dispose ()
 891                                 {
 892                                         host_enumerator.Dispose();
 893                                 }
 894
 895                                 public bool MoveNext ()
 896                                 {
 897                                         return host_enumerator.MoveNext ();
 898                                 }
 899
 900                                 public TValue Current {
 901                                         get { return host_enumerator.Current.Value; }
 902                                 }
 903
 904                                 object IEnumerator.Current {
 905                                         get { return host_enumerator.Current.Value; }
 906                                 }
 907
 908                                 void IEnumerator.Reset ()
 909                                 {
 910                                         ((IEnumerator)host_enumerator).Reset ();
 911                                 }
 912                         }
 913                 }
 914         }
 915 }
 916 #endif