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                 public virtual void 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 bool ContainsKey (TKey key)
 282                 {
 283                         if (key == null)
 284                                 throw new ArgumentNullException ("key");
 285
 286                         return (Find (key) >= 0);
 287                 }
 288
 289                 public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator ()
 290                 {
 291                         for (int i = 0; i < inUse; i ++) {
 292                                 KeyValuePair<TKey, TValue> current = this.table [i];
 293
 294                                 yield return new KeyValuePair<TKey, TValue> (current.Key, current.Value);
 295                         }
 296                 }
 297
 298                 public virtual bool Remove (TKey key)
 299                 {
 300                         if (key == null)
 301                                 throw new ArgumentNullException ("key");
 302
 303                         int i = IndexOfKey (key);
 304                         if (i >= 0) {
 305                                 RemoveAt (i);
 306                                 return true;
 307                         }
 308                         else
 309                                 return false;
 310                 }
 311
 312                 // ICollection<KeyValuePair<TKey, TValue>>
 313
 314                 public virtual void Clear ()
 315                 {
 316                         defaultCapacity = INITIAL_SIZE;
 317                         this.table = new KeyValuePair<TKey, TValue> [defaultCapacity];
 318                         inUse = 0;
 319                         modificationCount++;
 320                 }
 321
 322                 void ICollection<KeyValuePair<TKey, TValue>>.CopyTo (KeyValuePair<TKey, TValue>[] array, int arrayIndex)
 323                 {
 324                         if (null == array)
 325                                 throw new ArgumentNullException();
 326
 327                         if (arrayIndex < 0)
 328                                 throw new ArgumentOutOfRangeException();
 329
 330                         if (arrayIndex >= array.Length)
 331                                 throw new ArgumentNullException("arrayIndex is greater than or equal to array.Length");
 332                         if (Count > (array.Length - arrayIndex))
 333                                 throw new ArgumentNullException("Not enough space in array from arrayIndex to end of array");
 334
 335                         int i = arrayIndex;
 336                         foreach (KeyValuePair<TKey, TValue> pair in this)
 337                                 array [i++] = pair;
 338                 }
 339
 340                 void ICollection<KeyValuePair<TKey, TValue>>.Add (KeyValuePair<TKey, TValue> keyValuePair) {
 341                         Add (keyValuePair.Key, keyValuePair.Value);
 342                 }
 343
 344                 bool ICollection<KeyValuePair<TKey, TValue>>.Contains (KeyValuePair<TKey, TValue> keyValuePair) {
 345                         int i = Find (keyValuePair.Key);
 346
 347                         if (i >= 0)
 348                                 return Comparer<KeyValuePair<TKey, TValue>>.Default.Compare (table [i], keyValuePair) == 0;
 349                         else
 350                                 return false;
 351                 }
 352
 353                 bool ICollection<KeyValuePair<TKey, TValue>>.Remove (KeyValuePair<TKey, TValue> keyValuePair) {
 354                         int i = Find (keyValuePair.Key);
 355
 356                         if (i >= 0 && (Comparer<KeyValuePair<TKey, TValue>>.Default.Compare (table [i], keyValuePair) == 0)) {
 357                                 RemoveAt (i);
 358                                 return true;
 359                         }
 360                         else
 361                                 return false;
 362                 }
 363
 364                 // IEnumerable<KeyValuePair<TKey, TValue>>
 365
 366                 IEnumerator<KeyValuePair<TKey, TValue>> IEnumerable<KeyValuePair<TKey, TValue>>.GetEnumerator ()
 367                 {
 368                         for (int i = 0; i < inUse; i ++) {
 369                                 KeyValuePair<TKey, TValue> current = this.table [i];
 370
 371                                 yield return new KeyValuePair<TKey, TValue> (current.Key, current.Value);
 372                         }
 373                 }
 374
 375                 // IEnumerable
 376
 377                 IEnumerator IEnumerable.GetEnumerator ()
 378                 {
 379                         return GetEnumerator ();
 380                 }
 381
 382                 // IDictionary
 383
 384                 void IDictionary.Add (object key, object value)
 385                 {
 386                         PutImpl (ToKey (key), ToValue (value), false);
 387                 }
 388
 389                 bool IDictionary.Contains (object key)
 390                 {
 391                         if (null == key)
 392                                 throw new ArgumentNullException();
 393                         if (!(key is TKey))
 394                                 return false;
 395
 396                         return (Find ((TKey)key) >= 0);
 397                 }
 398
 399                 IDictionaryEnumerator IDictionary.GetEnumerator ()
 400                 {
 401                         return new Enumerator (this, EnumeratorMode.ENTRY_MODE);
 402                 }
 403
 404                 void IDictionary.Remove (object key)
 405                 {
 406                         if (null == key)
 407                                 throw new ArgumentNullException ("key");
 408                         if (!(key is TKey))
 409                                 return;
 410                         int i = IndexOfKey ((TKey)key);
 411                         if (i >= 0) RemoveAt (i);
 412                 }
 413
 414                 // ICollection
 415
 416                 void ICollection.CopyTo (Array array, int arrayIndex)
 417                 {
 418                         if (null == array)
 419                                 throw new ArgumentNullException();
 420
 421                         if (arrayIndex < 0)
 422                                 throw new ArgumentOutOfRangeException();
 423
 424                         if (array.Rank > 1)
 425                                 throw new ArgumentException("array is multi-dimensional");
 426                         if (arrayIndex >= array.Length)
 427                                 throw new ArgumentNullException("arrayIndex is greater than or equal to array.Length");
 428                         if (Count > (array.Length - arrayIndex))
 429                                 throw new ArgumentNullException("Not enough space in array from arrayIndex to end of array");
 430
 431                         IEnumerator<KeyValuePair<TKey,TValue>> it = GetEnumerator ();
 432                         int i = arrayIndex;
 433
 434                         while (it.MoveNext ()) {
 435                                 array.SetValue (it.Current, i++);
 436                         }
 437                 }
 438
 439                 //
 440                 // SortedList<TKey, TValue>
 441                 //
 442
 443                 public void RemoveAt (int index)
 444                 {
 445                         KeyValuePair<TKey, TValue> [] table = this.table;
 446                         int cnt = Count;
 447                         if (index >= 0 && index < cnt) {
 448                                 if (index != cnt - 1) {
 449                                         Array.Copy (table, index+1, table, index, cnt-1-index);
 450                                 } else {
 451                                         table [index] = default (KeyValuePair <TKey, TValue>);
 452                                 }
 453                                 --inUse;
 454                                 ++modificationCount;
 455                         } else {
 456                                 throw new ArgumentOutOfRangeException("index out of range");
 457                         }
 458                 }
 459
 460                 public int IndexOfKey (TKey key)
 461                 {
 462                         if (key == null)
 463                                 throw new ArgumentNullException ("key");
 464
 465                         int indx = 0;
 466                         try {
 467                                 indx = Find (key);
 468                         } catch (Exception) {
 469                                 throw new InvalidOperationException();
 470                         }
 471
 472                         return (indx | (indx >> 31));
 473                 }
 474
 475                 public int IndexOfValue (TValue value)
 476                 {
 477                         if (inUse == 0)
 478                                 return -1;
 479
 480                         for (int i = 0; i < inUse; i ++) {
 481                                 KeyValuePair<TKey, TValue> current = this.table [i];
 482
 483                                 if (Equals (value, current.Value))
 484                                         return i;
 485                         }
 486
 487                         return -1;
 488                 }
 489
 490                 public bool ContainsValue (TValue value)
 491                 {
 492                         return IndexOfValue (value) >= 0;
 493                 }
 494
 495                 public void TrimExcess ()
 496                 {
 497                         if (inUse < table.Length * 0.9)
 498                                 Capacity = inUse;
 499                 }
 500
 501                 public bool TryGetValue (TKey key, out TValue value)
 502                 {
 503                         if (key == null)
 504                                 throw new ArgumentNullException("key");
 505
 506                         int i = Find (key);
 507
 508                         if (i >= 0) {
 509                                 value = table [i].Value;
 510                                 return true;
 511                         }
 512                         else {
 513                                 value = default (TValue);
 514                                 return false;
 515                         }
 516                 }
 517
 518                 //
 519                 // Private methods
 520                 //
 521
 522                 private void EnsureCapacity (int n, int free)
 523                 {
 524                         KeyValuePair<TKey, TValue> [] table = this.table;
 525                         KeyValuePair<TKey, TValue> [] newTable = null;
 526                         int cap = Capacity;
 527                         bool gap = (free >=0 && free < Count);
 528
 529                         if (n > cap) {
 530                                 newTable = new KeyValuePair<TKey, TValue> [n << 1];
 531                         }
 532
 533                         if (newTable != null) {
 534                                 if (gap) {
 535                                         int copyLen = free;
 536                                         if (copyLen > 0) {
 537                                                 Array.Copy (table, 0, newTable, 0, copyLen);
 538                                         }
 539                                         copyLen = Count - free;
 540                                         if (copyLen > 0) {
 541                                                 Array.Copy (table, free, newTable, free+1, copyLen);
 542                                         }
 543                                 } else {
 544                                         // Just a resizing, copy the entire table.
 545                                         Array.Copy (table, newTable, Count);
 546                                 }
 547                                 this.table = newTable;
 548                         } else if (gap) {
 549                                 Array.Copy (table, free, table, free+1, Count - free);
 550                         }
 551                 }
 552
 553                 private void PutImpl (TKey key, TValue value, bool overwrite)
 554                 {
 555                         if (key == null)
 556                                 throw new ArgumentNullException ("null key");
 557
 558                         KeyValuePair<TKey, TValue> [] table = this.table;
 559
 560                         int freeIndx = -1;
 561
 562                         try {
 563                                 freeIndx = Find (key);
 564                         } catch (Exception) {
 565                                 throw new InvalidOperationException();
 566                         }
 567
 568                         if (freeIndx >= 0) {
 569                                 if (!overwrite)
 570                                         throw new ArgumentException("element already exists");
 571
 572                                 table [freeIndx] = new KeyValuePair <TKey, TValue> (key, value);
 573                                 ++modificationCount;
 574                                 return;
 575                         }
 576
 577                         freeIndx = ~freeIndx;
 578
 579                         if (freeIndx > Capacity + 1)
 580                                 throw new Exception ("SortedList::internal error ("+key+", "+value+") at ["+freeIndx+"]");
 581
 582
 583                         EnsureCapacity (Count+1, freeIndx);
 584
 585                         table = this.table;
 586                         table [freeIndx] = new KeyValuePair <TKey, TValue> (key, value);
 587
 588                         ++inUse;
 589                         ++modificationCount;
 590
 591                 }
 592
 593                 private void Init (IComparer<TKey> comparer, int capacity, bool forceSize)
 594                 {
 595                         if (comparer == null)
 596                                 comparer = Comparer<TKey>.Default;
 597                         this.comparer = comparer;
 598                         if (!forceSize && (capacity < defaultCapacity))
 599                                 capacity = defaultCapacity;
 600                         this.table = new KeyValuePair<TKey, TValue> [capacity];
 601                         this.inUse = 0;
 602                         this.modificationCount = 0;
 603                 }
 604
 605                 private void  CopyToArray (Array arr, int i,
 606                                            EnumeratorMode mode)
 607                 {
 608                         if (arr == null)
 609                                 throw new ArgumentNullException ("arr");
 610
 611                         if (i < 0 || i + this.Count > arr.Length)
 612                                 throw new ArgumentOutOfRangeException ("i");
 613
 614                         IEnumerator it = new Enumerator (this, mode);
 615
 616                         while (it.MoveNext ()) {
 617                                 arr.SetValue (it.Current, i++);
 618                         }
 619                 }
 620
 621                 private int Find (TKey key)
 622                 {
 623                         KeyValuePair<TKey, TValue> [] table = this.table;
 624                         int len = Count;
 625
 626                         if (len == 0) return ~0;
 627
 628                         int left = 0;
 629                         int right = len-1;
 630
 631                         while (left <= right) {
 632                                 int guess = (left + right) >> 1;
 633
 634                                 int cmp = comparer.Compare (key, table[guess].Key);
 635                                 if (cmp == 0) return guess;
 636
 637                                 if (cmp >  0) left = guess+1;
 638                                 else right = guess-1;
 639                         }
 640
 641                         return ~left;
 642                 }
 643
 644                 private TKey ToKey (object key) {
 645                         if (key == null)
 646                                 throw new ArgumentNullException ("key");
 647                         if (!(key is TKey))
 648                                 throw new ArgumentException ("The value \"" + key + "\" isn't of type \"" + typeof (TKey) + "\" and can't be used in this generic collection.", "key");
 649                         return (TKey)key;
 650                 }
 651
 652                 private TValue ToValue (object value) {
 653                         if (!(value is TValue))
 654                                 throw new ArgumentException ("The value \"" + value + "\" isn't of type \"" + typeof (TValue) + "\" and can't be used in this generic collection.", "value");
 655                         return (TValue)value;
 656                 }
 657
 658                 internal TKey KeyAt (int index) {
 659                         if (index >= 0 && index < Count)
 660                                 return table [index].Key;
 661                         else
 662                                 throw new ArgumentOutOfRangeException("Index out of range");
 663                 }
 664
 665                 internal TValue ValueAt (int index) {
 666                         if (index >= 0 && index < Count)
 667                                 return table [index].Value;
 668                         else
 669                                 throw new ArgumentOutOfRangeException("Index out of range");
 670                 }
 671
 672                 //
 673                 // Inner classes
 674                 //
 675
 676
 677                 private sealed class Enumerator : ICloneable, IDictionaryEnumerator, IEnumerator {
 678
 679                         private SortedList<TKey, TValue>host;
 680                         private int stamp;
 681                         private int pos;
 682                         private int size;
 683                         private EnumeratorMode mode;
 684
 685                         private object currentKey;
 686                         private object currentValue;
 687
 688                         bool invalid = false;
 689
 690                         private readonly static string xstr = "SortedList.Enumerator: snapshot out of sync.";
 691
 692                         public Enumerator (SortedList<TKey, TValue>host, EnumeratorMode mode)
 693                         {
 694                                 this.host = host;
 695                                 stamp = host.modificationCount;
 696                                 size = host.Count;
 697                                 this.mode = mode;
 698                                 Reset ();
 699                         }
 700
 701                         public Enumerator (SortedList<TKey, TValue>host)
 702                         : this (host, EnumeratorMode.ENTRY_MODE)
 703                         {
 704                         }
 705
 706                         public void Reset ()
 707                         {
 708                                 if (host.modificationCount != stamp || invalid)
 709                                         throw new InvalidOperationException (xstr);
 710
 711                                 pos = -1;
 712                                 currentKey = null;
 713                                 currentValue = null;
 714                         }
 715
 716                         public bool MoveNext ()
 717                         {
 718                                 if (host.modificationCount != stamp || invalid)
 719                                         throw new InvalidOperationException (xstr);
 720
 721                                 KeyValuePair<TKey, TValue> [] table = host.table;
 722
 723                                 if (++pos < size) {
 724                                         KeyValuePair<TKey, TValue> entry = table [pos];
 725
 726                                         currentKey = entry.Key;
 727                                         currentValue = entry.Value;
 728                                         return true;
 729                                 }
 730
 731                                 currentKey = null;
 732                                 currentValue = null;
 733                                 return false;
 734                         }
 735
 736                         public DictionaryEntry Entry
 737                         {
 738                                 get {
 739                                         if (invalid || pos >= size || pos == -1)
 740                                                 throw new InvalidOperationException (xstr);
 741
 742                                         return new DictionaryEntry (currentKey,
 743                                                                     currentValue);
 744                                 }
 745                         }
 746
 747                         public Object Key {
 748                                 get {
 749                                         if (invalid || pos >= size || pos == -1)
 750                                                 throw new InvalidOperationException (xstr);
 751                                         return currentKey;
 752                                 }
 753                         }
 754
 755                         public Object Value {
 756                                 get {
 757                                         if (invalid || pos >= size || pos == -1)
 758                                                 throw new InvalidOperationException (xstr);
 759                                         return currentValue;
 760                                 }
 761                         }
 762
 763                         public Object Current {
 764                                 get {
 765                                         if (invalid || pos >= size || pos == -1)
 766                                                 throw new InvalidOperationException (xstr);
 767
 768                                         switch (mode) {
 769                                         case EnumeratorMode.KEY_MODE:
 770                                                 return currentKey;
 771                                         case EnumeratorMode.VALUE_MODE:
 772                                                 return currentValue;
 773                                         case EnumeratorMode.ENTRY_MODE:
 774                                                 return this.Entry;
 775
 776                                         default:
 777                                                 throw new NotSupportedException (mode + " is not a supported mode.");
 778                                         }
 779                                 }
 780                         }
 781
 782                         // ICloneable
 783
 784                         public object Clone ()
 785                         {
 786                                 Enumerator e = new Enumerator (host, mode);
 787                                 e.stamp = stamp;
 788                                 e.pos = pos;
 789                                 e.size = size;
 790                                 e.currentKey = currentKey;
 791                                 e.currentValue = currentValue;
 792                                 e.invalid = invalid;
 793                                 return e;
 794                         }
 795                 }
 796
 797
 798                 private class ListKeys : IList<TKey>, ICollection, IEnumerable {
 799
 800                         private SortedList<TKey, TValue> host;
 801
 802                         public ListKeys (SortedList<TKey, TValue> host)
 803                         {
 804                                 if (host == null)
 805                                         throw new ArgumentNullException ();
 806
 807                                 this.host = host;
 808                         }
 809
 810                         // ICollection<TKey>
 811
 812                         public virtual void Add (TKey item) {
 813                                 throw new NotSupportedException();
 814                         }
 815
 816                         public virtual bool Remove (TKey key) {
 817                                 throw new NotSupportedException ();
 818                         }
 819
 820                         public virtual void Clear () {
 821                                 throw new NotSupportedException();
 822                         }
 823
 824                         public virtual void CopyTo (TKey[] array, int arrayIndex) {
 825                                 if (array == null)
 826                                         throw new ArgumentNullException ("array");
 827                                 if (arrayIndex < 0)
 828                                         throw new ArgumentOutOfRangeException();
 829                                 if (arrayIndex >= array.Length)
 830                                         throw new ArgumentOutOfRangeException ("arrayIndex is greater than or equal to array.Length");
 831                                 if (Count > (array.Length - arrayIndex))
 832                                         throw new ArgumentOutOfRangeException("Not enough space in array from arrayIndex to end of array");
 833
 834                                 int j = arrayIndex;
 835                                 for (int i = 0; i < Count; ++i)
 836                                         array [j ++] = host.KeyAt (i);
 837                         }
 838
 839                         public virtual bool Contains (TKey item) {
 840                                 return host.IndexOfKey (item) > -1;
 841                         }
 842
 843                         //
 844                         // IList<TKey>
 845                         //
 846                         public virtual int IndexOf (TKey item) {
 847                                 return host.IndexOfKey (item);
 848                         }
 849
 850                         public virtual void Insert (int index, TKey item) {
 851                                 throw new NotSupportedException ();
 852                         }
 853
 854                         public virtual void RemoveAt (int index) {
 855                                 throw new NotSupportedException ();
 856                         }
 857
 858                         public virtual TKey this [int index] {
 859                                 get {
 860                                         return host.KeyAt (index);
 861                                 }
 862                                 set {
 863                                         throw new NotSupportedException("attempt to modify a key");
 864                                 }
 865                         }
 866
 867                         //
 868                         // IEnumerable<TKey>
 869                         //
 870
 871                         public virtual IEnumerator<TKey> GetEnumerator ()
 872                         {
 873                                 for (int i = 0; i < host.Count; ++i)
 874                                         yield return host.KeyAt (i);
 875                         }
 876
 877                         //
 878                         // ICollection
 879                         //
 880
 881                         public virtual int Count {
 882                                 get {
 883                                         return host.Count;
 884                                 }
 885                         }
 886
 887                         public virtual bool IsSynchronized {
 888                                 get {
 889                                         return ((ICollection)host).IsSynchronized;
 890                                 }
 891                         }
 892
 893                         public virtual bool IsReadOnly {
 894                                 get {
 895                                         return true;
 896                                 }
 897                         }
 898
 899                         public virtual Object SyncRoot {
 900                                 get {
 901                                         return ((ICollection)host).SyncRoot;
 902                                 }
 903                         }
 904
 905                         public virtual void CopyTo (Array array, int arrayIndex)
 906                         {
 907                                 host.CopyToArray (array, arrayIndex, EnumeratorMode.KEY_MODE);
 908                         }
 909
 910                         //
 911                         // IEnumerable
 912                         //
 913
 914                         IEnumerator IEnumerable.GetEnumerator ()
 915                         {
 916                                 for (int i = 0; i < host.Count; ++i)
 917                                         yield return host.KeyAt (i);
 918                         }
 919                 }
 920
 921                 private class ListValues : IList<TValue>, ICollection, IEnumerable {
 922
 923                         private SortedList<TKey, TValue>host;
 924
 925                         public ListValues (SortedList<TKey, TValue>host)
 926                         {
 927                                 if (host == null)
 928                                         throw new ArgumentNullException ();
 929
 930                                 this.host = host;
 931                         }
 932
 933                         // ICollection<TValue>
 934
 935                         public virtual void Add (TValue item) {
 936                                 throw new NotSupportedException();
 937                         }
 938
 939                         public virtual bool Remove (TValue value) {
 940                                 throw new NotSupportedException ();
 941                         }
 942
 943                         public virtual void Clear () {
 944                                 throw new NotSupportedException();
 945                         }
 946
 947                         public virtual void CopyTo (TValue[] array, int arrayIndex) {
 948                                 if (array == null)
 949                                         throw new ArgumentNullException ("array");
 950                                 if (arrayIndex < 0)
 951                                         throw new ArgumentOutOfRangeException();
 952                                 if (arrayIndex >= array.Length)
 953                                         throw new ArgumentOutOfRangeException ("arrayIndex is greater than or equal to array.Length");
 954                                 if (Count > (array.Length - arrayIndex))
 955                                         throw new ArgumentOutOfRangeException("Not enough space in array from arrayIndex to end of array");
 956
 957                                 int j = arrayIndex;
 958                                 for (int i = 0; i < Count; ++i)
 959                                         array [j ++] = host.ValueAt (i);
 960                         }
 961
 962                         public virtual bool Contains (TValue item) {
 963                                 return host.IndexOfValue (item) > -1;
 964                         }
 965
 966                         //
 967                         // IList<TValue>
 968                         //
 969                         public virtual int IndexOf (TValue item) {
 970                                 return host.IndexOfValue (item);
 971                         }
 972
 973                         public virtual void Insert (int index, TValue item) {
 974                                 throw new NotSupportedException ();
 975                         }
 976
 977                         public virtual void RemoveAt (int index) {
 978                                 throw new NotSupportedException ();
 979                         }
 980
 981                         public virtual TValue this [int index] {
 982                                 get {
 983                                         return host.ValueAt (index);
 984                                 }
 985                                 set {
 986                                         throw new NotSupportedException("attempt to modify a key");
 987                                 }
 988                         }
 989
 990                         //
 991                         // IEnumerable<TValue>
 992                         //
 993
 994                         public virtual IEnumerator<TValue> GetEnumerator ()
 995                         {
 996                                 for (int i = 0; i < host.Count; ++i)
 997                                         yield return host.ValueAt (i);
 998                         }
 999
1000                         //
1001                         // ICollection
1002                         //
1003
1004                         public virtual int Count {
1005                                 get {
1006                                         return host.Count;
1007                                 }
1008                         }
1009
1010                         public virtual bool IsSynchronized {
1011                                 get {
1012                                         return ((ICollection)host).IsSynchronized;
1013                                 }
1014                         }
1015
1016                         public virtual bool IsReadOnly {
1017                                 get {
1018                                         return true;
1019                                 }
1020                         }
1021
1022                         public virtual Object SyncRoot {
1023                                 get {
1024                                         return ((ICollection)host).SyncRoot;
1025                                 }
1026                         }
1027
1028                         public virtual void CopyTo (Array array, int arrayIndex)
1029                         {
1030                                 host.CopyToArray (array, arrayIndex, EnumeratorMode.VALUE_MODE);
1031                         }
1032
1033                         //
1034                         // IEnumerable
1035                         //
1036
1037                         IEnumerator IEnumerable.GetEnumerator ()
1038                         {
1039                                 for (int i = 0; i < host.Count; ++i)
1040                                         yield return host.ValueAt (i);
1041                         }
1042                 }
1043
1044         } // SortedList
1045
1046 } // System.Collections.Generic
1047
1048 #endif