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