mcs/class/System/System.Collections.Generic/SortedDictionary.cs

   1 //
   2 // System.Collections.Generic.SortedDictionary
   3 //
   4 // Authors:
   5 //    Kazuki Oikawa (kazuki@panicode.com)
   6 //    Atsushi Enomoto (atsushi@ximian.com)
   7 //
   8
   9 //
  10 // Permission is hereby granted, free of charge, to any person obtaining
  11 // a copy of this software and associated documentation files (the
  12 // "Software"), to deal in the Software without restriction, including
  13 // without limitation the rights to use, copy, modify, merge, publish,
  14 // distribute, sublicense, and/or sell copies of the Software, and to
  15 // permit persons to whom the Software is furnished to do so, subject to
  16 // the following conditions:
  17 //
  18 // The above copyright notice and this permission notice shall be
  19 // included in all copies or substantial portions of the Software.
  20 //
  21 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  22 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  23 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  24 // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  25 // LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  26 // OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  27 // WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  28 //
  29
  30 #if NET_2_0
  31 using System;
  32 using System.Collections;
  33
  34 namespace System.Collections.Generic
  35 {
  36         [Serializable]
  37         public class SortedDictionary<TKey,TValue> : IDictionary<TKey,TValue>, ICollection<KeyValuePair<TKey,TValue>>, IEnumerable<KeyValuePair<TKey,TValue>>, IDictionary, ICollection, IEnumerable
  38         {
  39                 TKey [] _keys;
  40                 TValue [] _values;
  41                 IComparer<TKey> _comparer;
  42                 int _size;
  43                 int _version = 0;
  44                 const int DefaultCapacitySize = 4;
  45
  46                 KeyCollection _keyList;
  47                 ValueCollection _valueList;
  48
  49                 #region Constructor
  50                 public SortedDictionary () : this (0, null)
  51                 {
  52                 }
  53
  54                 public SortedDictionary (IComparer<TKey> comparer) : this (0, comparer)
  55                 {
  56                 }
  57
  58                 public SortedDictionary (IDictionary<TKey,TValue> dic) : this (dic, null)
  59                 {
  60                 }
  61
  62                 // it disappeared in 2.0 RTM
  63                 SortedDictionary (int capacity) : this (capacity, null)
  64                 {
  65
  66                 }
  67
  68                 public SortedDictionary (IDictionary<TKey,TValue> dic, IComparer<TKey> comparer) : this (dic == null ? 0 : dic.Count, comparer)
  69                 {
  70                         if (dic == null)
  71                                 throw new ArgumentNullException ();
  72
  73                         dic.Keys.CopyTo (_keys, 0);
  74                         dic.Values.CopyTo (_values, 0);
  75                         Array.Sort<TKey,TValue> (_keys, _values);
  76                         _size = dic.Count;
  77                 }
  78
  79                 // it disappeared in 2.0 RTM
  80                 SortedDictionary (int capacity, IComparer<TKey> comparer)
  81                 {
  82                         if (capacity < 0)
  83                                 throw new ArgumentOutOfRangeException ();
  84
  85                         _keys = new TKey [capacity];
  86                         _values = new TValue [capacity];
  87                         _size = 0;
  88
  89                         if (comparer == null)
  90                                 _comparer = Comparer<TKey>.Default;
  91                         else
  92                                 _comparer = comparer;
  93                 }
  94                 #endregion
  95
  96                 #region PublicProperty
  97
  98                 public IComparer<TKey> Comparer {
  99                         get { return _comparer; }
 100                 }
 101
 102                 // It disappeared in 2.0 RTM.
 103                 int Capacity {
 104                         get { return _keys.Length; }
 105                         set {
 106                                 if (value < _size)
 107                                         throw new ArgumentOutOfRangeException ();
 108
 109                                 Array.Resize<TKey> (ref _keys, value);
 110                                 Array.Resize<TValue> (ref _values, value);
 111                         }
 112                 }
 113
 114                 public int Count {
 115                         get { return _size; }
 116                 }
 117
 118                 public TValue this [TKey key] {
 119                         get {
 120                                 int index = IndexOfKey (key);
 121                                 if (index >= 0)
 122                                         return _values [index];
 123
 124                                 throw new KeyNotFoundException ();
 125                         }
 126                         set {
 127                                 if (key == null)
 128                                         throw new ArgumentNullException ();
 129
 130                                 int index = IndexOfKey (key);
 131                                 if (index < 0)
 132                                         Add (key, value);
 133                                 else
 134                                         _values [index] = value;
 135                         }
 136                 }
 137
 138                 public KeyCollection Keys {
 139                         get { return GetKeyCollection (); }
 140                 }
 141
 142                 public ValueCollection Values {
 143                         get { return GetValueCollection (); }
 144                 }
 145                 #endregion
 146
 147                 #region PublicMethod
 148
 149                 public void Add (TKey key, TValue value)
 150                 {
 151                         if (key == null)
 152                                 throw new ArgumentNullException ();
 153
 154                         int index = Array.BinarySearch<TKey> (_keys, 0, _size, key, _comparer);
 155                         if (index >= 0)
 156                                 throw new ArgumentException ();
 157
 158                         index = ~index;
 159
 160                         if (_size == _keys.Length)
 161                                 Capacity += Capacity > 0 ? Capacity : DefaultCapacitySize;
 162
 163                         if (index < _size) {
 164                                 Array.Copy (_keys, index, _keys, index + 1, _size - index);
 165                                 Array.Copy (_values, index, _values, index + 1, _size - index);
 166                         }
 167
 168                         _keys [index] = key;
 169                         _values [index] = value;
 170                         _size++;
 171                         _version++;
 172                 }
 173
 174                 public void Clear ()
 175                 {
 176                         Array.Clear (_keys, 0, _size);
 177                         Array.Clear (_values, 0, _size);
 178                         _size = 0;
 179                         _version++;
 180                 }
 181
 182                 public bool ContainsKey (TKey key)
 183                 {
 184                         return IndexOfKey (key) >= 0;
 185                 }
 186
 187                 public bool ContainsValue (TValue value)
 188                 {
 189                         return IndexOfValue (value) >= 0;
 190                 }
 191
 192                 public void CopyTo (KeyValuePair<TKey,TValue>[] array, int arrayIndex)
 193                 {
 194                         if (array == null)
 195                                 throw new ArgumentNullException ();
 196                         if (arrayIndex < 0 || array.Length <= arrayIndex)
 197                                 throw new ArgumentOutOfRangeException ();
 198                         if (array.Length - arrayIndex < _size)
 199                                 throw new ArgumentException ();
 200
 201                         for (int i = 0; i < _size; i ++) {
 202                                 array [arrayIndex + i] = new KeyValuePair<TKey,TValue> (_keys [i], _values [i]);
 203                         }
 204                 }
 205
 206                 public Enumerator GetEnumerator ()
 207                 {
 208                         return new Enumerator (this);
 209                 }
 210
 211                 int IndexOfKey (TKey key)
 212                 {
 213                         if (key == null)
 214                                 throw new ArgumentNullException ();
 215
 216                         return Array.BinarySearch<TKey> (_keys, 0, _size, key, _comparer);
 217                 }
 218
 219                 int IndexOfValue (TValue value)
 220                 {
 221                         return Array.IndexOf<TValue> (_values, value, 0, _size);
 222                 }
 223
 224                 public bool Remove (TKey key)
 225                 {
 226                         int index = IndexOfKey (key);
 227                         if (index >= 0) {
 228                                 RemoveAt (index);
 229                                 return true;
 230                         }
 231                         return false;
 232                 }
 233
 234                 void RemoveAt (int index)
 235                 {
 236                         if (index < 0 || _size <= index)
 237                                 throw new ArgumentOutOfRangeException ();
 238
 239                         _size--;
 240                         if (index < _size) {
 241                                 Array.Copy (_keys, index + 1, _keys, index, _size - index);
 242                                 Array.Copy (_values, index + 1, _values, index, _size - index);
 243                         }
 244
 245                         _keys[_size] = default (TKey) ;
 246                         _values[_size] = default (TValue) ;
 247                         _version++;
 248                 }
 249
 250                 public bool TryGetValue (TKey key, out TValue value)
 251                 {
 252                         int index = IndexOfKey (key);
 253                         if (index >= 0) {
 254                                 value = _values [index];
 255                                 return true;
 256                         }
 257
 258                         value = default (TValue) ;
 259                         return false;
 260                 }
 261
 262                 #endregion
 263
 264                 #region PrivateMethod
 265                 private KeyCollection GetKeyCollection ()
 266                 {
 267                         if (_keyList == null)
 268                                 _keyList = new KeyCollection (this);
 269                         return _keyList;
 270                 }
 271                 private ValueCollection GetValueCollection ()
 272                 {
 273                         if (_valueList == null)
 274                                 _valueList = new ValueCollection (this);
 275                         return _valueList;
 276                 }
 277
 278                 TKey ToKey (object key)
 279                 {
 280                         if (key == null)
 281                                 throw new ArgumentNullException ("key");
 282                         if (!(key is TKey))
 283                                 throw new ArgumentException (String.Format ("Key \"{0}\" cannot be converted to the key type {1}.", key, typeof (TKey)));
 284                         return (TKey) key;
 285                 }
 286
 287                 TValue ToValue (object value)
 288                 {
 289                         if (!(value is TValue) && (value != null || typeof (TValue).IsValueType))
 290                                 throw new ArgumentException (String.Format ("Value \"{0}\" cannot be converted to the value type {1}.", value, typeof (TValue)));
 291                         return (TValue) value;
 292                 }
 293                 #endregion
 294
 295                 #region IDictionary<TKey,TValue> Member
 296
 297                 ICollection<TKey> IDictionary<TKey,TValue>.Keys {
 298                         get { return GetKeyCollection (); }
 299                 }
 300
 301                 ICollection<TValue> IDictionary<TKey,TValue>.Values {
 302                         get { return GetValueCollection (); }
 303                 }
 304
 305                 #endregion
 306
 307                 #region ICollection<KeyValuePair<TKey,TValue>> Member
 308
 309                 void ICollection<KeyValuePair<TKey,TValue>>.Add (KeyValuePair<TKey,TValue> item)
 310                 {
 311                         Add (item.Key, item.Value);
 312                 }
 313
 314                 bool ICollection<KeyValuePair<TKey,TValue>>.Contains (KeyValuePair<TKey,TValue> item)
 315                 {
 316                         int index = IndexOfKey (item.Key);
 317                         return index >= 0 && Comparer<TValue>.Default.Compare (_values [index], item.Value) == 0;
 318                 }
 319
 320                 bool ICollection<KeyValuePair<TKey,TValue>>.IsReadOnly {
 321                         get { return false; }
 322                 }
 323
 324                 bool ICollection<KeyValuePair<TKey,TValue>>.Remove (KeyValuePair<TKey,TValue> item)
 325                 {
 326                         int index = IndexOfKey (item.Key);
 327                         if (index >= 0 && Comparer<TValue>.Default.Compare (_values [index], item.Value) == 0) {
 328                                 RemoveAt (index);
 329                                 return true;
 330                         }
 331                         return false;
 332                 }
 333
 334                 #endregion
 335
 336                 #region IDictionary Member
 337
 338                 void IDictionary.Add (object key, object value)
 339                 {
 340                         Add (ToKey (key), ToValue (value));
 341                 }
 342
 343                 bool IDictionary.Contains (object key)
 344                 {
 345                         return ContainsKey (ToKey (key));
 346                 }
 347
 348                 IDictionaryEnumerator IDictionary.GetEnumerator ()
 349                 {
 350                         return new Enumerator (this);
 351                 }
 352
 353                 bool IDictionary.IsFixedSize {
 354                         get { return false; }
 355                 }
 356
 357                 bool IDictionary.IsReadOnly {
 358                         get { return false; }
 359                 }
 360
 361                 ICollection IDictionary.Keys  {
 362                         get { return GetKeyCollection (); }
 363                 }
 364
 365                 void IDictionary.Remove (object key)
 366                 {
 367                         Remove (ToKey (key));
 368                 }
 369                 ICollection IDictionary.Values {
 370                         get { return GetValueCollection (); }
 371                 }
 372
 373                 object IDictionary.this [object key] {
 374                         get {
 375                                 return this [ToKey (key)];
 376                         }
 377                         set {
 378                                 if (!(value is TValue))
 379                                         throw new ArgumentException ();
 380
 381                                 this [ToKey (key)] = ToValue (value);
 382                         }
 383                 }
 384
 385                 #endregion
 386
 387                 #region ICollection Member
 388
 389                 void ICollection.CopyTo (Array array, int index)
 390                 {
 391                         if (array == null)
 392                                 throw new ArgumentNullException ();
 393                         if (index < 0 || array.Length <= index)
 394                                 throw new ArgumentOutOfRangeException ();
 395                         if (array.Length - index < _size)
 396                                 throw new ArgumentException ();
 397
 398                         for (int i = 0; i < _size; i ++) {
 399                                 array.SetValue (new KeyValuePair<TKey,TValue> (_keys [i], _values [i]), i);
 400                         }
 401                 }
 402
 403                 bool ICollection.IsSynchronized {
 404                         get { return false; }
 405                 }
 406
 407                 // TODO:Is this correct? If this is wrong,please fix.
 408                 object ICollection.SyncRoot {
 409                         get { return this; }
 410                 }
 411
 412                 #endregion
 413
 414                 #region IEnumerable Member
 415
 416                 IEnumerator IEnumerable.GetEnumerator ()
 417                 {
 418                         return new Enumerator (this);
 419                 }
 420
 421                 #endregion
 422
 423                 #region IEnumerable<TKey> Member
 424
 425                 IEnumerator<KeyValuePair<TKey,TValue>> IEnumerable<KeyValuePair<TKey,TValue>>.GetEnumerator ()
 426                 {
 427                         return new Enumerator (this);
 428                 }
 429
 430                 #endregion
 431
 432                 [Serializable]
 433                 public sealed class ValueCollection : ICollection<TValue>,
 434                         IEnumerable<TValue>, ICollection, IEnumerable
 435                 {
 436                         SortedDictionary<TKey,TValue> _dic;
 437
 438                         public ValueCollection (SortedDictionary<TKey,TValue> dic)
 439                         {
 440                                 _dic = dic;
 441                         }
 442
 443                         void ICollection<TValue>.Add (TValue item)
 444                         {
 445                                 throw new NotSupportedException ();
 446                         }
 447
 448                         void ICollection<TValue>.Clear ()
 449                         {
 450                                 throw new NotSupportedException ();
 451                         }
 452
 453                         bool ICollection<TValue>.Contains (TValue item)
 454                         {
 455                                 return _dic.ContainsValue (item);
 456                         }
 457
 458                         public void CopyTo (TValue [] array, int arrayIndex)
 459                         {
 460                                 if (array == null)
 461                                         throw new ArgumentNullException ();
 462                                 if (arrayIndex < 0 || array.Length <= arrayIndex)
 463                                         throw new ArgumentOutOfRangeException ();
 464                                 if (array.Length - arrayIndex < _dic._size)
 465                                         throw new ArgumentException ();
 466                                 Array.Copy (_dic._values, 0, array, arrayIndex, _dic._size);
 467                         }
 468
 469                         public int Count {
 470                                 get { return _dic._size; }
 471                         }
 472
 473                         bool ICollection<TValue>.IsReadOnly {
 474                                 get { return true; }
 475                         }
 476
 477                         bool ICollection<TValue>.Remove (TValue item)
 478                         {
 479                                 throw new NotSupportedException ();
 480                         }
 481
 482                         IEnumerator<TValue> IEnumerable<TValue>.GetEnumerator ()
 483                         {
 484                                 return GetEnumerator ();
 485                         }
 486
 487                         public Enumerator GetEnumerator ()
 488                         {
 489                                 return new Enumerator (_dic);
 490                         }
 491
 492                         void ICollection.CopyTo(Array array, int index)
 493                         {
 494                                 if (array == null)
 495                                         throw new ArgumentNullException ();
 496                                 if (index < 0 || array.Length <= index)
 497                                         throw new ArgumentOutOfRangeException ();
 498                                 if (array.Length - index < _dic._size)
 499                                         throw new ArgumentException ();
 500                                 Array.Copy (_dic._values, 0, array, index, _dic._size);
 501                         }
 502
 503                         bool ICollection.IsSynchronized {
 504                                 get { return false; }
 505                         }
 506
 507                         object ICollection.SyncRoot {
 508                                 get { return _dic; }
 509                         }
 510
 511                         IEnumerator IEnumerable.GetEnumerator ()
 512                         {
 513                                 return new Enumerator (_dic);
 514                         }
 515
 516                         public struct Enumerator : IEnumerator<TValue>,IEnumerator, IDisposable
 517                         {
 518                                 SortedDictionary<TKey,TValue> _dic;
 519                                 int _version;
 520                                 int _index;
 521                                 int _count;
 522
 523                                 internal Enumerator (SortedDictionary<TKey,TValue> dic)
 524                                 {
 525                                         _dic = dic;
 526                                         _version = dic._version;
 527                                         _index = -1;
 528                                         _count = dic._size;
 529                                 }
 530
 531                                 public TValue Current {
 532                                         get {
 533                                                 if (_count <= _index)
 534                                                         throw new InvalidOperationException ();
 535                                                 return _dic._values [_index];
 536                                         }
 537                                 }
 538
 539                                 public bool MoveNext ()
 540                                 {
 541                                         if (_version != _dic._version)
 542                                                 throw new InvalidOperationException ();
 543
 544                                         if (_index + 1 < _count) {
 545                                                 _index ++;
 546                                                 return true;
 547                                         }
 548
 549                                         return false;
 550                                 }
 551
 552                                 public void Dispose ()
 553                                 {
 554                                         _dic = null;
 555                                 }
 556
 557                                 object IEnumerator.Current {
 558                                         get { return Current; }
 559                                 }
 560
 561                                 void IEnumerator.Reset ()
 562                                 {
 563                                         if (_version != _dic._version)
 564                                                 throw new InvalidOperationException ();
 565                                         _index = -1;
 566                                 }
 567                         }
 568                 }
 569
 570                 [Serializable]
 571                 public sealed class KeyCollection : ICollection<TKey>,
 572                         IEnumerable<TKey>, ICollection, IEnumerable
 573                 {
 574                         SortedDictionary<TKey,TValue> _dic;
 575
 576                         public KeyCollection (SortedDictionary<TKey,TValue> dic)
 577                         {
 578                                 _dic = dic;
 579                         }
 580
 581                         void ICollection<TKey>.Add (TKey item)
 582                         {
 583                                 throw new NotSupportedException ();
 584                         }
 585
 586                         void ICollection<TKey>.Clear ()
 587                         {
 588                                 throw new NotSupportedException ();
 589                         }
 590
 591                         bool ICollection<TKey>.Contains (TKey item)
 592                         {
 593                                 return _dic.ContainsKey (item);
 594                         }
 595
 596                         IEnumerator<TKey> IEnumerable<TKey>.GetEnumerator ()
 597                         {
 598                                 return GetEnumerator ();
 599                         }
 600
 601                         public void CopyTo (TKey [] array, int arrayIndex)
 602                         {
 603                                 Array.Copy (_dic._keys, 0, array, arrayIndex, _dic._size);
 604                         }
 605
 606                         public int Count {
 607                                 get { return _dic._size; }
 608                         }
 609
 610                         bool ICollection<TKey>.IsReadOnly {
 611                                 get { return true; }
 612                         }
 613
 614                         bool ICollection<TKey>.Remove (TKey item)
 615                         {
 616                                 throw new NotSupportedException ();
 617                         }
 618
 619                         public Enumerator GetEnumerator ()
 620                         {
 621                                 return new Enumerator (_dic);
 622                         }
 623
 624                         void ICollection.CopyTo (Array array, int index)
 625                         {
 626                                 if (array == null)
 627                                         throw new ArgumentNullException ();
 628                                 if (index < 0 || array.Length <= index)
 629                                         throw new ArgumentOutOfRangeException ();
 630                                 if (array.Length - index < _dic._size)
 631                                         throw new ArgumentException ();
 632                                 Array.Copy (_dic._keys, 0, array, index, _dic._size);
 633                         }
 634
 635                         bool ICollection.IsSynchronized {
 636                                 get { return false; }
 637                         }
 638
 639                         object ICollection.SyncRoot {
 640                                 get { return _dic; }
 641                         }
 642
 643                         IEnumerator IEnumerable.GetEnumerator ()
 644                         {
 645                                 return new Enumerator (_dic);
 646                         }
 647
 648                         public struct Enumerator : IEnumerator<TKey>, IEnumerator, IDisposable
 649                         {
 650                                 SortedDictionary<TKey,TValue> _dic;
 651                                 int _version;
 652                                 int _index;
 653                                 int _count;
 654
 655                                 internal Enumerator (SortedDictionary<TKey,TValue> dic)
 656                                 {
 657                                         _dic = dic;
 658                                         _version = dic._version;
 659                                         _index = -1;
 660                                         _count = dic._size;
 661                                 }
 662
 663                                 public TKey Current {
 664                                         get {
 665                                                 if (_count <= _index)
 666                                                         throw new InvalidOperationException ();
 667                                                 return _dic._keys [_index];
 668                                         }
 669                                 }
 670
 671                                 public bool MoveNext ()
 672                                 {
 673                                         if (_version != _dic._version)
 674                                                 throw new InvalidOperationException ();
 675
 676                                         if (_index + 1 < _count) {
 677                                                 _index ++;
 678                                                 return true;
 679                                         }
 680
 681                                         return false;
 682                                 }
 683
 684                                 public void Dispose ()
 685                                 {
 686                                         _dic = null;
 687                                 }
 688
 689                                 object IEnumerator.Current {
 690                                         get { return Current; }
 691                                 }
 692
 693                                 void IEnumerator.Reset ()
 694                                 {
 695                                         if (_version != _dic._version)
 696                                                 throw new InvalidOperationException ();
 697                                         _index = -1;
 698                                 }
 699                         }
 700
 701                 }
 702
 703                 public struct Enumerator : IEnumerator<KeyValuePair<TKey,TValue>>, IDisposable , IDictionaryEnumerator, IEnumerator
 704                 {
 705                         SortedDictionary<TKey,TValue> _dic;
 706                         int _version;
 707                         int _index;
 708                         int _count;
 709
 710                         internal Enumerator (SortedDictionary<TKey,TValue> dic)
 711                         {
 712                                 _dic = dic;
 713                                 _version = dic._version;
 714                                 _index = -1;
 715                                 _count = dic._size;
 716                         }
 717
 718                         public KeyValuePair<TKey,TValue> Current {
 719                                 get {
 720                                         if (_count <= _index)
 721                                                 throw new InvalidOperationException ();
 722                                         return new KeyValuePair<TKey,TValue> (_dic._keys [_index], _dic._values [_index]);
 723                                 }
 724                         }
 725
 726                         public bool MoveNext ()
 727                         {
 728                                 if (_version != _dic._version)
 729                                         throw new InvalidOperationException ();
 730
 731                                 if (_index + 1 < _count) {
 732                                         _index ++;
 733                                         return true;
 734                                 }
 735
 736                                 return false;
 737                         }
 738
 739                         public void Dispose ()
 740                         {
 741                                 _dic = null;
 742                         }
 743
 744                         DictionaryEntry IDictionaryEnumerator.Entry {
 745                                 get {
 746                                         if (_count <= _index)
 747                                                 throw new InvalidOperationException ();
 748                                         return new DictionaryEntry (_dic._keys [_index], _dic._values [_index]);
 749                                 }
 750                         }
 751
 752                         object IDictionaryEnumerator.Key {
 753                                 get {
 754                                         if (_count <= _index)
 755                                                 throw new InvalidOperationException ();
 756                                         return _dic._keys [_index];
 757                                 }
 758                         }
 759
 760                         object IDictionaryEnumerator.Value {
 761                                 get {
 762                                         if (_count <= _index)
 763                                                 throw new InvalidOperationException ();
 764                                         return _dic._values [_index];
 765                                 }
 766                         }
 767
 768                         object IEnumerator.Current {
 769                                 get {
 770                                         if (_count <= _index)
 771                                                 throw new InvalidOperationException ();
 772                                         return new DictionaryEntry (_dic._keys [_index], _dic._values [_index]);
 773                                 }
 774                         }
 775
 776                         void IEnumerator.Reset ()
 777                         {
 778                                 if (_version != _dic._version)
 779                                         throw new InvalidOperationException ();
 780
 781                                 _index = -1;
 782                         }
 783                 }
 784         }
 785 }
 786 #endif