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

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