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