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