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

   1 //
   2 // System.Collections.Generic.SortedList.cs
   3 //
   4 // Author:
   5 //   Sergey Chaban (serge@wildwestsoftware.com)
   6 //   Duncan Mak (duncan@ximian.com)
   7 //   Herve Poussineau (hpoussineau@fr.st
   8 //   Zoltan Varga (vargaz@gmail.com)
   9 //
  10
  11 //
  12 // Copyright (C) 2004 Novell, Inc (http://www.novell.com)
  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.Globalization;
  39 using System.Runtime.InteropServices;
  40
  41 namespace System.Collections.Generic {
  42
  43         /// <summary>
  44         ///  Represents a collection of associated keys and values
  45         ///  that are sorted by the keys and are accessible by key
  46         ///  and by index.
  47         /// </summary>
  48         [Serializable]
  49         [ComVisible(false)]
  50         public class SortedList<TKey, TValue> : IDictionary<TKey, TValue>,
  51                 IDictionary,
  52                 ICollection,
  53                 ICollection<KeyValuePair<TKey, TValue>>,
  54                 IEnumerable<KeyValuePair<TKey, TValue>>,
  55                 IEnumerable {
  56
  57                 private readonly static int INITIAL_SIZE = 16;
  58
  59                 private enum EnumeratorMode : int { KEY_MODE = 0, VALUE_MODE, ENTRY_MODE }
  60
  61                 private int inUse;
  62                 private int modificationCount;
  63                 private KeyValuePair<TKey, TValue>[] table;
  64                 private IComparer<TKey> comparer;
  65                 private int defaultCapacity;
  66
  67                 //
  68                 // Constructors
  69                 //
  70                 public SortedList ()
  71                         : this (INITIAL_SIZE, null)
  72                 {
  73                 }
  74
  75                 public SortedList (int capacity)
  76                         : this (capacity, null)
  77                 {
  78                 }
  79
  80                 public SortedList (int capacity, IComparer<TKey> comparer)
  81                 {
  82                         if (capacity < 0)
  83                                 throw new ArgumentOutOfRangeException ("initialCapacity");
  84
  85                         if (capacity == 0)
  86                                 defaultCapacity = 0;
  87                         else
  88                                 defaultCapacity = INITIAL_SIZE;
  89                         Init (comparer, capacity, true);
  90                 }
  91
  92                 public SortedList (IComparer<TKey> comparer) : this (INITIAL_SIZE, comparer)
  93                 {
  94                 }
  95
  96                 public SortedList (IDictionary<TKey, TValue> dictionary) : this (dictionary, null)
  97                 {
  98                 }
  99
 100                 public SortedList (IDictionary<TKey, TValue> dictionary, IComparer<TKey> comparer)
 101                 {
 102                         if (dictionary == null)
 103                                 throw new ArgumentNullException ("dictionary");
 104
 105                         Init (comparer, dictionary.Count, true);
 106
 107                         foreach (KeyValuePair<TKey, TValue> kvp in dictionary)
 108                                 Add (kvp.Key, kvp.Value);
 109                 }
 110
 111                 //
 112                 // Properties
 113                 //
 114
 115                 // ICollection
 116
 117                 public virtual int Count {
 118                         get {
 119                                 return inUse;
 120                         }
 121                 }
 122
 123                 bool ICollection.IsSynchronized {
 124                         get {
 125                                 return false;
 126                         }
 127                 }
 128
 129                 Object ICollection.SyncRoot {
 130                         get {
 131                                 return this;
 132                         }
 133                 }
 134
 135                 // IDictionary
 136
 137                 bool IDictionary.IsFixedSize {
 138                         get {
 139                                 return false;
 140                         }
 141                 }
 142
 143                 bool IDictionary.IsReadOnly {
 144                         get {
 145                                 return false;
 146                         }
 147                 }
 148
 149                 public virtual TValue this [TKey key] {
 150                         get {
 151                                 if (key == null)
 152                                         throw new ArgumentNullException("key");
 153
 154                                 int i = Find (key);
 155
 156                                 if (i >= 0)
 157                                         return table [i].Value;
 158                                 else
 159                                         throw new KeyNotFoundException ();
 160                         }
 161                         set {
 162                                 if (key == null)
 163                                         throw new ArgumentNullException("key");
 164
 165                                 PutImpl (key, value, true);
 166                         }
 167                 }
 168
 169                 object IDictionary.this [object key] {
 170                         get {
 171                                 if (!(key is TKey))
 172                                         return null;
 173                                 else
 174                                         return this [(TKey)key];
 175                         }
 176
 177                         set {
 178                                 this [ToKey (key)] = ToValue (value);
 179                         }
 180                 }
 181
 182                 public int Capacity {
 183                         get {
 184                                 return table.Length;
 185                         }
 186
 187                         set {
 188                                 int current = this.table.Length;
 189
 190                                 if (inUse > value) {
 191                                         throw new ArgumentOutOfRangeException("capacity too small");
 192                                 }
 193                                 else if (value == 0) {
 194                                         // return to default size
 195                                         KeyValuePair<TKey, TValue> [] newTable = new KeyValuePair<TKey, TValue> [defaultCapacity];
 196                                         Array.Copy (table, newTable, inUse);
 197                                         this.table = newTable;
 198                                 }
 199 #if NET_1_0
 200                                 else if (current > defaultCapacity && value < current) {
 201                                         KeyValuePair<TKey, TValue> [] newTable = new KeyValuePair<TKey, TValue> [defaultCapacity];
 202                                         Array.Copy (table, newTable, inUse);
 203                                         this.table = newTable;
 204                                 }
 205 #endif
 206                                 else if (value > inUse) {
 207                                         KeyValuePair<TKey, TValue> [] newTable = new KeyValuePair<TKey, TValue> [value];
 208                                         Array.Copy (table, newTable, inUse);
 209                                         this.table = newTable;
 210                                 }
 211                                 else if (value > current) {
 212                                         KeyValuePair<TKey, TValue> [] newTable = new KeyValuePair<TKey, TValue> [value];
 213                                         Array.Copy (table, newTable, current);
 214                                         this.table = newTable;
 215                                 }
 216                         }
 217                 }
 218
 219                 public IList<TKey> Keys {
 220                         get {
 221                                 return new ListKeys (this);
 222                         }
 223                 }
 224
 225                 public IList<TValue> Values {
 226                         get {
 227                                 return new ListValues (this);
 228                         }
 229                 }
 230
 231                 ICollection IDictionary.Keys {
 232                         get {
 233                                 return new ListKeys (this);
 234                         }
 235                 }
 236
 237                 ICollection IDictionary.Values {
 238                         get {
 239                                 return new ListValues (this);
 240                         }
 241                 }
 242
 243                 ICollection<TKey> IDictionary<TKey, TValue>.Keys {
 244                         get {
 245                                 return Keys;
 246                         }
 247                 }
 248
 249                 ICollection<TValue> IDictionary<TKey, TValue>.Values {
 250                         get {
 251                                 return Values;
 252                         }
 253                 }
 254
 255                 public IComparer<TKey> Comparer {
 256                         get {
 257                                 return comparer;
 258                         }
 259                 }
 260
 261                 bool ICollection<KeyValuePair<TKey, TValue>>.IsReadOnly {
 262                         get {
 263                                 return false;
 264                         }
 265                 }
 266
 267                 //
 268                 // Public instance methods.
 269                 //
 270
 271                 // IDictionary<TKey, TValue>
 272
 273                 void IDictionary<TKey,TValue>.Add (TKey key, TValue value)
 274                 {
 275                         if (key == null)
 276                                 throw new ArgumentNullException ("key");
 277
 278                         PutImpl (key, value, false);
 279                 }
 280
 281                 public virtual void Add (TKey key, TValue value)
 282                 {
 283                         if (key == null)
 284                                 throw new ArgumentNullException ("key");
 285
 286                         PutImpl (key, value, false);
 287                 }
 288
 289                 public bool ContainsKey (TKey key)
 290                 {
 291                         if (key == null)
 292                                 throw new ArgumentNullException ("key");
 293
 294                         return (Find (key) >= 0);
 295                 }
 296
 297                 public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator ()
 298                 {
 299                         for (int i = 0; i < inUse; i ++) {
 300                                 KeyValuePair<TKey, TValue> current = this.table [i];
 301
 302                                 yield return new KeyValuePair<TKey, TValue> (current.Key, current.Value);
 303                         }
 304                 }
 305
 306                 bool IDictionary<TKey,TValue>.Remove (TKey key)
 307                 {
 308                         if (key == null)
 309                                 throw new ArgumentNullException ("key");
 310
 311                         int i = IndexOfKey (key);
 312                         if (i >= 0) {
 313                                 RemoveAt (i);
 314                                 return true;
 315                         }
 316                         else
 317                                 return false;
 318                 }
 319
 320                 public virtual bool Remove (TKey key)
 321                 {
 322                         if (key == null)
 323                                 throw new ArgumentNullException ("key");
 324
 325                         int i = IndexOfKey (key);
 326                         if (i >= 0) {
 327                                 RemoveAt (i);
 328                                 return true;
 329                         }
 330                         else
 331                                 return false;
 332                 }
 333
 334                 // ICollection<KeyValuePair<TKey, TValue>>
 335
 336                 void ICollection<KeyValuePair<TKey, TValue>>.Clear ()
 337                 {
 338                         defaultCapacity = INITIAL_SIZE;
 339                         this.table = new KeyValuePair<TKey, TValue> [defaultCapacity];
 340                         inUse = 0;
 341                         modificationCount++;
 342                 }
 343
 344                 public virtual void Clear ()
 345                 {
 346                         defaultCapacity = INITIAL_SIZE;
 347                         this.table = new KeyValuePair<TKey, TValue> [defaultCapacity];
 348                         inUse = 0;
 349                         modificationCount++;
 350                 }
 351
 352                 void ICollection<KeyValuePair<TKey, TValue>>.CopyTo (KeyValuePair<TKey, TValue>[] array, int arrayIndex)
 353                 {
 354                         if (null == array)
 355                                 throw new ArgumentNullException();
 356
 357                         if (arrayIndex < 0)
 358                                 throw new ArgumentOutOfRangeException();
 359
 360                         if (arrayIndex >= array.Length)
 361                                 throw new ArgumentNullException("arrayIndex is greater than or equal to array.Length");
 362                         if (Count > (array.Length - arrayIndex))
 363                                 throw new ArgumentNullException("Not enough space in array from arrayIndex to end of array");
 364
 365                         int i = arrayIndex;
 366                         foreach (KeyValuePair<TKey, TValue> pair in this)
 367                                 array [i++] = pair;
 368                 }
 369
 370                 void ICollection<KeyValuePair<TKey, TValue>>.Add (KeyValuePair<TKey, TValue> keyValuePair) {
 371                         Add (keyValuePair.Key, keyValuePair.Value);
 372                 }
 373
 374                 bool ICollection<KeyValuePair<TKey, TValue>>.Contains (KeyValuePair<TKey, TValue> keyValuePair) {
 375                         int i = Find (keyValuePair.Key);
 376
 377                         if (i >= 0)
 378                                 return Comparer<KeyValuePair<TKey, TValue>>.Default.Compare (table [i], keyValuePair) == 0;
 379                         else
 380                                 return false;
 381                 }
 382
 383                 bool ICollection<KeyValuePair<TKey, TValue>>.Remove (KeyValuePair<TKey, TValue> keyValuePair) {
 384                         int i = Find (keyValuePair.Key);
 385
 386                         if (i >= 0 && (Comparer<KeyValuePair<TKey, TValue>>.Default.Compare (table [i], keyValuePair) == 0)) {
 387                                 RemoveAt (i);
 388                                 return true;
 389                         }
 390                         else
 391                                 return false;
 392                 }
 393
 394                 // IEnumerable<KeyValuePair<TKey, TValue>>
 395
 396                 IEnumerator<KeyValuePair<TKey, TValue>> IEnumerable<KeyValuePair<TKey, TValue>>.GetEnumerator ()
 397                 {
 398                         for (int i = 0; i < inUse; i ++) {
 399                                 KeyValuePair<TKey, TValue> current = this.table [i];
 400
 401                                 yield return new KeyValuePair<TKey, TValue> (current.Key, current.Value);
 402                         }
 403                 }
 404
 405                 // IEnumerable
 406
 407                 IEnumerator IEnumerable.GetEnumerator ()
 408                 {
 409                         return GetEnumerator ();
 410                 }
 411
 412                 // IDictionary
 413
 414                 void IDictionary.Add (object key, object value)
 415                 {
 416                         PutImpl (ToKey (key), ToValue (value), false);
 417                 }
 418
 419                 bool IDictionary.Contains (object key)
 420                 {
 421                         if (null == key)
 422                                 throw new ArgumentNullException();
 423                         if (!(key is TKey))
 424                                 return false;
 425
 426                         return (Find ((TKey)key) >= 0);
 427                 }
 428
 429                 IDictionaryEnumerator IDictionary.GetEnumerator ()
 430                 {
 431                         return new Enumerator (this, EnumeratorMode.ENTRY_MODE);
 432                 }
 433
 434                 void IDictionary.Remove (object key)
 435                 {
 436                         if (null == key)
 437                                 throw new ArgumentNullException ("key");
 438                         if (!(key is TKey))
 439                                 return;
 440                         int i = IndexOfKey ((TKey)key);
 441                         if (i >= 0) RemoveAt (i);
 442                 }
 443
 444                 // ICollection
 445
 446                 void ICollection.CopyTo (Array array, int arrayIndex)
 447                 {
 448                         if (null == array)
 449                                 throw new ArgumentNullException();
 450
 451                         if (arrayIndex < 0)
 452                                 throw new ArgumentOutOfRangeException();
 453
 454                         if (array.Rank > 1)
 455                                 throw new ArgumentException("array is multi-dimensional");
 456                         if (arrayIndex >= array.Length)
 457                                 throw new ArgumentNullException("arrayIndex is greater than or equal to array.Length");
 458                         if (Count > (array.Length - arrayIndex))
 459                                 throw new ArgumentNullException("Not enough space in array from arrayIndex to end of array");
 460
 461                         IEnumerator<KeyValuePair<TKey,TValue>> it = GetEnumerator ();
 462                         int i = arrayIndex;
 463
 464                         while (it.MoveNext ()) {
 465                                 array.SetValue (it.Current, i++);
 466                         }
 467                 }
 468
 469                 //
 470                 // SortedList<TKey, TValue>
 471                 //
 472
 473                 public void RemoveAt (int index)
 474                 {
 475                         KeyValuePair<TKey, TValue> [] table = this.table;
 476                         int cnt = Count;
 477                         if (index >= 0 && index < cnt) {
 478                                 if (index != cnt - 1) {
 479                                         Array.Copy (table, index+1, table, index, cnt-1-index);
 480                                 } else {
 481                                         table [index] = default (KeyValuePair <TKey, TValue>);
 482                                 }
 483                                 --inUse;
 484                                 ++modificationCount;
 485                         } else {
 486                                 throw new ArgumentOutOfRangeException("index out of range");
 487                         }
 488                 }
 489
 490                 public int IndexOfKey (TKey key)
 491                 {
 492                         if (key == null)
 493                                 throw new ArgumentNullException ("key");
 494
 495                         int indx = 0;
 496                         try {
 497                                 indx = Find (key);
 498                         } catch (Exception) {
 499                                 throw new InvalidOperationException();
 500                         }
 501
 502                         return (indx | (indx >> 31));
 503                 }
 504
 505                 public int IndexOfValue (TValue value)
 506                 {
 507                         if (inUse == 0)
 508                                 return -1;
 509
 510                         for (int i = 0; i < inUse; i ++) {
 511                                 KeyValuePair<TKey, TValue> current = this.table [i];
 512
 513                                 if (Equals (value, current.Value))
 514                                         return i;
 515                         }
 516
 517                         return -1;
 518                 }
 519
 520                 public bool ContainsValue (TValue value)
 521                 {
 522                         return IndexOfValue (value) >= 0;
 523                 }
 524
 525                 public void TrimExcess ()
 526                 {
 527                         if (inUse < table.Length * 0.9)
 528                                 Capacity = inUse;
 529                 }
 530
 531                 public bool TryGetValue (TKey key, out TValue value)
 532                 {
 533                         if (key == null)
 534                                 throw new ArgumentNullException("key");
 535
 536                         int i = Find (key);
 537
 538                         if (i >= 0) {
 539                                 value = table [i].Value;
 540                                 return true;
 541                         }
 542                         else {
 543                                 value = default (TValue);
 544                                 return false;
 545                         }
 546                 }
 547
 548                 //
 549                 // Private methods
 550                 //
 551
 552                 private void EnsureCapacity (int n, int free)
 553                 {
 554                         KeyValuePair<TKey, TValue> [] table = this.table;
 555                         KeyValuePair<TKey, TValue> [] newTable = null;
 556                         int cap = Capacity;
 557                         bool gap = (free >=0 && free < Count);
 558
 559                         if (n > cap) {
 560                                 newTable = new KeyValuePair<TKey, TValue> [n << 1];
 561                         }
 562
 563                         if (newTable != null) {
 564                                 if (gap) {
 565                                         int copyLen = free;
 566                                         if (copyLen > 0) {
 567                                                 Array.Copy (table, 0, newTable, 0, copyLen);
 568                                         }
 569                                         copyLen = Count - free;
 570                                         if (copyLen > 0) {
 571                                                 Array.Copy (table, free, newTable, free+1, copyLen);
 572                                         }
 573                                 } else {
 574                                         // Just a resizing, copy the entire table.
 575                                         Array.Copy (table, newTable, Count);
 576                                 }
 577                                 this.table = newTable;
 578                         } else if (gap) {
 579                                 Array.Copy (table, free, table, free+1, Count - free);
 580                         }
 581                 }
 582
 583                 private void PutImpl (TKey key, TValue value, bool overwrite)
 584                 {
 585                         if (key == null)
 586                                 throw new ArgumentNullException ("null key");
 587
 588                         KeyValuePair<TKey, TValue> [] table = this.table;
 589
 590                         int freeIndx = -1;
 591
 592                         try {
 593                                 freeIndx = Find (key);
 594                         } catch (Exception) {
 595                                 throw new InvalidOperationException();
 596                         }
 597
 598                         if (freeIndx >= 0) {
 599                                 if (!overwrite)
 600                                         throw new ArgumentException("element already exists");
 601
 602                                 table [freeIndx] = new KeyValuePair <TKey, TValue> (key, value);
 603                                 ++modificationCount;
 604                                 return;
 605                         }
 606
 607                         freeIndx = ~freeIndx;
 608
 609                         if (freeIndx > Capacity + 1)
 610                                 throw new Exception ("SortedList::internal error ("+key+", "+value+") at ["+freeIndx+"]");
 611
 612
 613                         EnsureCapacity (Count+1, freeIndx);
 614
 615                         table = this.table;
 616                         table [freeIndx] = new KeyValuePair <TKey, TValue> (key, value);
 617
 618                         ++inUse;
 619                         ++modificationCount;
 620
 621                 }
 622
 623                 private void Init (IComparer<TKey> comparer, int capacity, bool forceSize)
 624                 {
 625                         if (comparer == null)
 626                                 comparer = Comparer<TKey>.Default;
 627                         this.comparer = comparer;
 628                         if (!forceSize && (capacity < defaultCapacity))
 629                                 capacity = defaultCapacity;
 630                         this.table = new KeyValuePair<TKey, TValue> [capacity];
 631                         this.inUse = 0;
 632                         this.modificationCount = 0;
 633                 }
 634
 635                 private void  CopyToArray (Array arr, int i,
 636                                            EnumeratorMode mode)
 637                 {
 638                         if (arr == null)
 639                                 throw new ArgumentNullException ("arr");
 640
 641                         if (i < 0 || i + this.Count > arr.Length)
 642                                 throw new ArgumentOutOfRangeException ("i");
 643
 644                         IEnumerator it = new Enumerator (this, mode);
 645
 646                         while (it.MoveNext ()) {
 647                                 arr.SetValue (it.Current, i++);
 648                         }
 649                 }
 650
 651                 private int Find (TKey key)
 652                 {
 653                         KeyValuePair<TKey, TValue> [] table = this.table;
 654                         int len = Count;
 655
 656                         if (len == 0) return ~0;
 657
 658                         int left = 0;
 659                         int right = len-1;
 660
 661                         while (left <= right) {
 662                                 int guess = (left + right) >> 1;
 663
 664                                 int cmp = comparer.Compare (key, table[guess].Key);
 665                                 if (cmp == 0) return guess;
 666
 667                                 if (cmp >  0) left = guess+1;
 668                                 else right = guess-1;
 669                         }
 670
 671                         return ~left;
 672                 }
 673
 674                 private TKey ToKey (object key) {
 675                         if (key == null)
 676                                 throw new ArgumentNullException ("key");
 677                         if (!(key is TKey))
 678                                 throw new ArgumentException ("The value \"" + key + "\" isn't of type \"" + typeof (TKey) + "\" and can't be used in this generic collection.", "key");
 679                         return (TKey)key;
 680                 }
 681
 682                 private TValue ToValue (object value) {
 683                         if (!(value is TValue))
 684                                 throw new ArgumentException ("The value \"" + value + "\" isn't of type \"" + typeof (TValue) + "\" and can't be used in this generic collection.", "value");
 685                         return (TValue)value;
 686                 }
 687
 688                 internal TKey KeyAt (int index) {
 689                         if (index >= 0 && index < Count)
 690                                 return table [index].Key;
 691                         else
 692                                 throw new ArgumentOutOfRangeException("Index out of range");
 693                 }
 694
 695                 internal TValue ValueAt (int index) {
 696                         if (index >= 0 && index < Count)
 697                                 return table [index].Value;
 698                         else
 699                                 throw new ArgumentOutOfRangeException("Index out of range");
 700                 }
 701
 702                 //
 703                 // Inner classes
 704                 //
 705
 706
 707                 private sealed class Enumerator : ICloneable, IDictionaryEnumerator, IEnumerator {
 708
 709                         private SortedList<TKey, TValue>host;
 710                         private int stamp;
 711                         private int pos;
 712                         private int size;
 713                         private EnumeratorMode mode;
 714
 715                         private object currentKey;
 716                         private object currentValue;
 717
 718                         bool invalid = false;
 719
 720                         private readonly static string xstr = "SortedList.Enumerator: snapshot out of sync.";
 721
 722                         public Enumerator (SortedList<TKey, TValue>host, EnumeratorMode mode)
 723                         {
 724                                 this.host = host;
 725                                 stamp = host.modificationCount;
 726                                 size = host.Count;
 727                                 this.mode = mode;
 728                                 Reset ();
 729                         }
 730
 731                         public Enumerator (SortedList<TKey, TValue>host)
 732                         : this (host, EnumeratorMode.ENTRY_MODE)
 733                         {
 734                         }
 735
 736                         public void Reset ()
 737                         {
 738                                 if (host.modificationCount != stamp || invalid)
 739                                         throw new InvalidOperationException (xstr);
 740
 741                                 pos = -1;
 742                                 currentKey = null;
 743                                 currentValue = null;
 744                         }
 745
 746                         public bool MoveNext ()
 747                         {
 748                                 if (host.modificationCount != stamp || invalid)
 749                                         throw new InvalidOperationException (xstr);
 750
 751                                 KeyValuePair<TKey, TValue> [] table = host.table;
 752
 753                                 if (++pos < size) {
 754                                         KeyValuePair<TKey, TValue> entry = table [pos];
 755
 756                                         currentKey = entry.Key;
 757                                         currentValue = entry.Value;
 758                                         return true;
 759                                 }
 760
 761                                 currentKey = null;
 762                                 currentValue = null;
 763                                 return false;
 764                         }
 765
 766                         public DictionaryEntry Entry
 767                         {
 768                                 get {
 769                                         if (invalid || pos >= size || pos == -1)
 770                                                 throw new InvalidOperationException (xstr);
 771
 772                                         return new DictionaryEntry (currentKey,
 773                                                                     currentValue);
 774                                 }
 775                         }
 776
 777                         public Object Key {
 778                                 get {
 779                                         if (invalid || pos >= size || pos == -1)
 780                                                 throw new InvalidOperationException (xstr);
 781                                         return currentKey;
 782                                 }
 783                         }
 784
 785                         public Object Value {
 786                                 get {
 787                                         if (invalid || pos >= size || pos == -1)
 788                                                 throw new InvalidOperationException (xstr);
 789                                         return currentValue;
 790                                 }
 791                         }
 792
 793                         public Object Current {
 794                                 get {
 795                                         if (invalid || pos >= size || pos == -1)
 796                                                 throw new InvalidOperationException (xstr);
 797
 798                                         switch (mode) {
 799                                         case EnumeratorMode.KEY_MODE:
 800                                                 return currentKey;
 801                                         case EnumeratorMode.VALUE_MODE:
 802                                                 return currentValue;
 803                                         case EnumeratorMode.ENTRY_MODE:
 804                                                 return this.Entry;
 805
 806                                         default:
 807                                                 throw new NotSupportedException (mode + " is not a supported mode.");
 808                                         }
 809                                 }
 810                         }
 811
 812                         // ICloneable
 813
 814                         public object Clone ()
 815                         {
 816                                 Enumerator e = new Enumerator (host, mode);
 817                                 e.stamp = stamp;
 818                                 e.pos = pos;
 819                                 e.size = size;
 820                                 e.currentKey = currentKey;
 821                                 e.currentValue = currentValue;
 822                                 e.invalid = invalid;
 823                                 return e;
 824                         }
 825                 }
 826
 827
 828                 private class ListKeys : IList<TKey>, ICollection, IEnumerable {
 829
 830                         private SortedList<TKey, TValue> host;
 831
 832                         public ListKeys (SortedList<TKey, TValue> host)
 833                         {
 834                                 if (host == null)
 835                                         throw new ArgumentNullException ();
 836
 837                                 this.host = host;
 838                         }
 839
 840                         // ICollection<TKey>
 841
 842                         public virtual void Add (TKey item) {
 843                                 throw new NotSupportedException();
 844                         }
 845
 846                         public virtual bool Remove (TKey key) {
 847                                 throw new NotSupportedException ();
 848                         }
 849
 850                         public virtual void Clear () {
 851                                 throw new NotSupportedException();
 852                         }
 853
 854                         public virtual void CopyTo (TKey[] array, int arrayIndex) {
 855                                 if (array == null)
 856                                         throw new ArgumentNullException ("array");
 857                                 if (arrayIndex < 0)
 858                                         throw new ArgumentOutOfRangeException();
 859                                 if (arrayIndex >= array.Length)
 860                                         throw new ArgumentOutOfRangeException ("arrayIndex is greater than or equal to array.Length");
 861                                 if (Count > (array.Length - arrayIndex))
 862                                         throw new ArgumentOutOfRangeException("Not enough space in array from arrayIndex to end of array");
 863
 864                                 int j = arrayIndex;
 865                                 for (int i = 0; i < Count; ++i)
 866                                         array [j ++] = host.KeyAt (i);
 867                         }
 868
 869                         public virtual bool Contains (TKey item) {
 870                                 return host.IndexOfKey (item) > -1;
 871                         }
 872
 873                         //
 874                         // IList<TKey>
 875                         //
 876                         public virtual int IndexOf (TKey item) {
 877                                 return host.IndexOfKey (item);
 878                         }
 879
 880                         public virtual void Insert (int index, TKey item) {
 881                                 throw new NotSupportedException ();
 882                         }
 883
 884                         public virtual void RemoveAt (int index) {
 885                                 throw new NotSupportedException ();
 886                         }
 887
 888                         public virtual TKey this [int index] {
 889                                 get {
 890                                         return host.KeyAt (index);
 891                                 }
 892                                 set {
 893                                         throw new NotSupportedException("attempt to modify a key");
 894                                 }
 895                         }
 896
 897                         //
 898                         // IEnumerable<TKey>
 899                         //
 900
 901                         public virtual IEnumerator<TKey> GetEnumerator ()
 902                         {
 903                                 for (int i = 0; i < host.Count; ++i)
 904                                         yield return host.KeyAt (i);
 905                         }
 906
 907                         //
 908                         // ICollection
 909                         //
 910
 911                         public virtual int Count {
 912                                 get {
 913                                         return host.Count;
 914                                 }
 915                         }
 916
 917                         public virtual bool IsSynchronized {
 918                                 get {
 919                                         return ((ICollection)host).IsSynchronized;
 920                                 }
 921                         }
 922
 923                         public virtual bool IsReadOnly {
 924                                 get {
 925                                         return true;
 926                                 }
 927                         }
 928
 929                         public virtual Object SyncRoot {
 930                                 get {
 931                                         return ((ICollection)host).SyncRoot;
 932                                 }
 933                         }
 934
 935                         public virtual void CopyTo (Array array, int arrayIndex)
 936                         {
 937                                 host.CopyToArray (array, arrayIndex, EnumeratorMode.KEY_MODE);
 938                         }
 939
 940                         //
 941                         // IEnumerable
 942                         //
 943
 944                         IEnumerator IEnumerable.GetEnumerator ()
 945                         {
 946                                 for (int i = 0; i < host.Count; ++i)
 947                                         yield return host.KeyAt (i);
 948                         }
 949                 }
 950
 951                 private class ListValues : IList<TValue>, ICollection, IEnumerable {
 952
 953                         private SortedList<TKey, TValue>host;
 954
 955                         public ListValues (SortedList<TKey, TValue>host)
 956                         {
 957                                 if (host == null)
 958                                         throw new ArgumentNullException ();
 959
 960                                 this.host = host;
 961                         }
 962
 963                         // ICollection<TValue>
 964
 965                         public virtual void Add (TValue item) {
 966                                 throw new NotSupportedException();
 967                         }
 968
 969                         public virtual bool Remove (TValue value) {
 970                                 throw new NotSupportedException ();
 971                         }
 972
 973                         public virtual void Clear () {
 974                                 throw new NotSupportedException();
 975                         }
 976
 977                         public virtual void CopyTo (TValue[] array, int arrayIndex) {
 978                                 if (array == null)
 979                                         throw new ArgumentNullException ("array");
 980                                 if (arrayIndex < 0)
 981                                         throw new ArgumentOutOfRangeException();
 982                                 if (arrayIndex >= array.Length)
 983                                         throw new ArgumentOutOfRangeException ("arrayIndex is greater than or equal to array.Length");
 984                                 if (Count > (array.Length - arrayIndex))
 985                                         throw new ArgumentOutOfRangeException("Not enough space in array from arrayIndex to end of array");
 986
 987                                 int j = arrayIndex;
 988                                 for (int i = 0; i < Count; ++i)
 989                                         array [j ++] = host.ValueAt (i);
 990                         }
 991
 992                         public virtual bool Contains (TValue item) {
 993                                 return host.IndexOfValue (item) > -1;
 994                         }
 995
 996                         //
 997                         // IList<TValue>
 998                         //
 999                         public virtual int IndexOf (TValue item) {
1000                                 return host.IndexOfValue (item);
1001                         }
1002
1003                         public virtual void Insert (int index, TValue item) {
1004                                 throw new NotSupportedException ();
1005                         }
1006
1007                         public virtual void RemoveAt (int index) {
1008                                 throw new NotSupportedException ();
1009                         }
1010
1011                         public virtual TValue this [int index] {
1012                                 get {
1013                                         return host.ValueAt (index);
1014                                 }
1015                                 set {
1016                                         throw new NotSupportedException("attempt to modify a key");
1017                                 }
1018                         }
1019
1020                         //
1021                         // IEnumerable<TValue>
1022                         //
1023
1024                         public virtual IEnumerator<TValue> GetEnumerator ()
1025                         {
1026                                 for (int i = 0; i < host.Count; ++i)
1027                                         yield return host.ValueAt (i);
1028                         }
1029
1030                         //
1031                         // ICollection
1032                         //
1033
1034                         public virtual int Count {
1035                                 get {
1036                                         return host.Count;
1037                                 }
1038                         }
1039
1040                         public virtual bool IsSynchronized {
1041                                 get {
1042                                         return ((ICollection)host).IsSynchronized;
1043                                 }
1044                         }
1045
1046                         public virtual bool IsReadOnly {
1047                                 get {
1048                                         return true;
1049                                 }
1050                         }
1051
1052                         public virtual Object SyncRoot {
1053                                 get {
1054                                         return ((ICollection)host).SyncRoot;
1055                                 }
1056                         }
1057
1058                         public virtual void CopyTo (Array array, int arrayIndex)
1059                         {
1060                                 host.CopyToArray (array, arrayIndex, EnumeratorMode.VALUE_MODE);
1061                         }
1062
1063                         //
1064                         // IEnumerable
1065                         //
1066
1067                         IEnumerator IEnumerable.GetEnumerator ()
1068                         {
1069                                 for (int i = 0; i < host.Count; ++i)
1070                                         yield return host.ValueAt (i);
1071                         }
1072                 }
1073
1074         } // SortedList
1075
1076 } // System.Collections.Generic
1077
1078 #endif