mcs/class/referencesource/System/compmod/system/collections/generic/sortedlist.cs

   1 // ==++==
   2 //
   3 //   Copyright (c) Microsoft Corporation.  All rights reserved.
   4 //
   5 // ==--==
   6 /*============================================================
   7 **
   8 ** Class:  SortedList
   9 **
  10 ** Purpose: A generic sorted list.
  11 **
  12 ** Date:  January 28, 2003
  13 **
  14 ===========================================================*/
  15 namespace System.Collections.Generic {
  16     using System;
  17     using System.Security.Permissions;
  18     using System.Diagnostics;
  19
  20     // The SortedDictionary class implements a generic sorted list of keys
  21     // and values. Entries in a sorted list are sorted by their keys and
  22     // are accessible both by key and by index. The keys of a sorted dictionary
  23     // can be ordered either according to a specific IComparer
  24     // implementation given when the sorted dictionary is instantiated, or
  25     // according to the IComparable implementation provided by the keys
  26     // themselves. In either case, a sorted dictionary does not allow entries
  27     // with duplicate or null keys.
  28     //
  29     // A sorted list internally maintains two arrays that store the keys and
  30     // values of the entries. The capacity of a sorted list is the allocated
  31     // length of these internal arrays. As elements are added to a sorted list, the
  32     // capacity of the sorted list is automatically increased as required by
  33     // reallocating the internal arrays.  The capacity is never automatically
  34     // decreased, but users can call either TrimExcess or
  35     // Capacity explicitly.
  36     //
  37     // The GetKeyList and GetValueList methods of a sorted list
  38     // provides access to the keys and values of the sorted list in the form of
  39     // List implementations. The List objects returned by these
  40     // methods are aliases for the underlying sorted list, so modifications
  41     // made to those lists are directly reflected in the sorted list, and vice
  42     // versa.
  43     //
  44     // The SortedList class provides a convenient way to create a sorted
  45     // copy of another dictionary, such as a Hashtable. For example:
  46     //
  47     // Hashtable h = new Hashtable();
  48     // h.Add(...);
  49     // h.Add(...);
  50     // ...
  51     // SortedList s = new SortedList(h);
  52     //
  53     // The last line above creates a sorted list that contains a copy of the keys
  54     // and values stored in the hashtable. In this particular example, the keys
  55     // will be ordered according to the IComparable interface, which they
  56     // all must implement. To impose a different ordering, SortedList also
  57     // has a constructor that allows a specific IComparer implementation to
  58     // be specified.
  59     //
  60     [DebuggerTypeProxy(typeof(System_DictionaryDebugView<,>))]
  61     [DebuggerDisplay("Count = {Count}")]
  62     [Serializable()]
  63     [System.Runtime.InteropServices.ComVisible(false)]
  64     public class SortedList<TKey, TValue> :
  65         IDictionary<TKey, TValue>, System.Collections.IDictionary
  66     {
  67         private TKey[] keys;
  68         private TValue[] values;
  69         private int _size;
  70         private int version;
  71         private IComparer<TKey> comparer;
  72         private KeyList keyList;
  73         private ValueList valueList;
  74         [NonSerialized]
  75         private Object _syncRoot;
  76
  77         static TKey[] emptyKeys = new TKey[0];
  78         static TValue[] emptyValues = new TValue[0];
  79
  80         private const int _defaultCapacity = 4;
  81
  82         // Constructs a new sorted list. The sorted list is initially empty and has
  83         // a capacity of zero. Upon adding the first element to the sorted list the
  84         // capacity is increased to _defaultCapacity, and then increased in multiples of two as
  85         // required. The elements of the sorted list are ordered according to the
  86         // IComparable interface, which must be implemented by the keys of
  87         // all entries added to the sorted list.
  88         public SortedList() {
  89             keys = emptyKeys;
  90             values = emptyValues;
  91             _size = 0;
  92             comparer = Comparer<TKey>.Default;
  93         }
  94
  95         // Constructs a new sorted list. The sorted list is initially empty and has
  96         // a capacity of zero. Upon adding the first element to the sorted list the
  97         // capacity is increased to 16, and then increased in multiples of two as
  98         // required. The elements of the sorted list are ordered according to the
  99         // IComparable interface, which must be implemented by the keys of
 100         // all entries added to the sorted list.
 101         //
 102         public SortedList(int capacity) {
 103             if (capacity < 0)
 104                 ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.capacity, ExceptionResource.ArgumentOutOfRange_NeedNonNegNumRequired);
 105             keys = new TKey[capacity];
 106             values = new TValue[capacity];
 107             comparer = Comparer<TKey>.Default;
 108         }
 109
 110         // Constructs a new sorted list with a given IComparer
 111         // implementation. The sorted list is initially empty and has a capacity of
 112         // zero. Upon adding the first element to the sorted list the capacity is
 113         // increased to 16, and then increased in multiples of two as required. The
 114         // elements of the sorted list are ordered according to the given
 115         // IComparer implementation. If comparer is null, the
 116         // elements are compared to each other using the IComparable
 117         // interface, which in that case must be implemented by the keys of all
 118         // entries added to the sorted list.
 119         //
 120         public SortedList(IComparer<TKey> comparer)
 121             : this() {
 122             if (comparer != null) {
 123                 this.comparer = comparer;
 124             }
 125         }
 126
 127         // Constructs a new sorted dictionary with a given IComparer
 128         // implementation and a given initial capacity. The sorted list is
 129         // initially empty, but will have room for the given number of elements
 130         // before any reallocations are required. The elements of the sorted list
 131         // are ordered according to the given IComparer implementation. If
 132         // comparer is null, the elements are compared to each other using
 133         // the IComparable interface, which in that case must be implemented
 134         // by the keys of all entries added to the sorted list.
 135         //
 136         public SortedList(int capacity, IComparer<TKey> comparer)
 137             : this(comparer) {
 138             Capacity = capacity;
 139         }
 140
 141         // Constructs a new sorted list containing a copy of the entries in the
 142         // given dictionary. The elements of the sorted list are ordered according
 143         // to the IComparable interface, which must be implemented by the
 144         // keys of all entries in the the given dictionary as well as keys
 145         // subsequently added to the sorted list.
 146         //
 147         public SortedList(IDictionary<TKey, TValue> dictionary)
 148             : this(dictionary, null) {
 149         }
 150
 151         // Constructs a new sorted list containing a copy of the entries in the
 152         // given dictionary. The elements of the sorted list are ordered according
 153         // to the given IComparer implementation. If comparer is
 154         // null, the elements are compared to each other using the
 155         // IComparable interface, which in that case must be implemented
 156         // by the keys of all entries in the the given dictionary as well as keys
 157         // subsequently added to the sorted list.
 158         //
 159         public SortedList(IDictionary<TKey, TValue> dictionary, IComparer<TKey> comparer)
 160             : this((dictionary != null ? dictionary.Count : 0), comparer) {
 161             if (dictionary==null)
 162                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.dictionary);
 163
 164             dictionary.Keys.CopyTo(keys, 0);
 165             dictionary.Values.CopyTo(values, 0);
 166             Array.Sort<TKey, TValue>(keys, values, comparer);
 167             _size = dictionary.Count;
 168         }
 169
 170         // Adds an entry with the given key and value to this sorted list. An
 171         // ArgumentException is thrown if the key is already present in the sorted list.
 172         //
 173         public void Add(TKey key, TValue value) {
 174             if (key == null) ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
 175             int i = Array.BinarySearch<TKey>(keys, 0, _size, key, comparer);
 176             if (i >= 0)
 177                 ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_AddingDuplicate);
 178             Insert(~i, key, value);
 179         }
 180
 181         void ICollection<KeyValuePair<TKey, TValue>>.Add(KeyValuePair<TKey, TValue> keyValuePair) {
 182             Add(keyValuePair.Key, keyValuePair.Value);
 183         }
 184
 185         bool ICollection<KeyValuePair<TKey, TValue>>.Contains(KeyValuePair<TKey, TValue> keyValuePair) {
 186             int index = IndexOfKey(keyValuePair.Key);
 187             if( index >= 0 && EqualityComparer<TValue>.Default.Equals(values[index], keyValuePair.Value)) {
 188                 return true;
 189             }
 190             return false;
 191         }
 192
 193         bool ICollection<KeyValuePair<TKey, TValue>>.Remove(KeyValuePair<TKey, TValue> keyValuePair) {
 194             int index = IndexOfKey(keyValuePair.Key);
 195             if( index >= 0 && EqualityComparer<TValue>.Default.Equals(values[index], keyValuePair.Value)) {
 196                 RemoveAt(index);
 197                 return true;
 198             }
 199             return false;
 200         }
 201
 202         // Returns the capacity of this sorted list. The capacity of a sorted list
 203         // represents the allocated length of the internal arrays used to store the
 204         // keys and values of the list, and thus also indicates the maximum number
 205         // of entries the list can contain before a reallocation of the internal
 206         // arrays is required.
 207         //
 208          public int Capacity {
 209             get {
 210                 return keys.Length;
 211             }
 212             set {
 213                 if (value != keys.Length) {
 214                     if (value < _size) {
 215                         ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.value, ExceptionResource.ArgumentOutOfRange_SmallCapacity);
 216                     }
 217
 218                     if (value > 0) {
 219                         TKey[] newKeys = new TKey[value];
 220                         TValue[] newValues = new TValue[value];
 221                         if (_size > 0) {
 222                             Array.Copy(keys, 0, newKeys, 0, _size);
 223                             Array.Copy(values, 0, newValues, 0, _size);
 224                         }
 225                         keys = newKeys;
 226                         values = newValues;
 227                     }
 228                     else {
 229                         keys = emptyKeys;
 230                         values = emptyValues;
 231                     }
 232                }
 233             }
 234          }
 235
 236         public IComparer<TKey> Comparer {
 237             get {
 238                 return comparer;
 239              }
 240         }
 241
 242         void System.Collections.IDictionary.Add(Object key, Object value) {
 243             if (key == null)
 244             {
 245                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
 246             }
 247
 248             ThrowHelper.IfNullAndNullsAreIllegalThenThrow<TValue>(value, ExceptionArgument.value);
 249
 250             try {
 251                 TKey tempKey = (TKey)key;
 252
 253                 try {
 254                     Add(tempKey, (TValue)value);
 255                 }
 256                 catch (InvalidCastException) {
 257                     ThrowHelper.ThrowWrongValueTypeArgumentException(value, typeof(TValue));
 258                 }
 259             }
 260             catch (InvalidCastException) {
 261                 ThrowHelper.ThrowWrongKeyTypeArgumentException(key, typeof(TKey));
 262             }
 263         }
 264
 265         // Returns the number of entries in this sorted list.
 266         //
 267         public int Count {
 268             get {
 269                 return _size;
 270             }
 271         }
 272
 273         // Returns a collection representing the keys of this sorted list. This
 274         // method returns the same object as GetKeyList, but typed as an
 275         // ICollection instead of an IList.
 276         //
 277         public IList<TKey> Keys {
 278             get {
 279                 return GetKeyListHelper();
 280             }
 281         }
 282
 283         ICollection<TKey> IDictionary<TKey,TValue>.Keys {
 284             get {
 285                 return GetKeyListHelper();
 286             }
 287         }
 288
 289         System.Collections.ICollection System.Collections.IDictionary.Keys {
 290             get {
 291                 return GetKeyListHelper();
 292             }
 293         }
 294
 295         // Returns a collection representing the values of this sorted list. This
 296         // method returns the same object as GetValueList, but typed as an
 297         // ICollection instead of an IList.
 298         //
 299         public IList<TValue> Values {
 300             get {
 301                 return GetValueListHelper();
 302             }
 303         }
 304
 305         ICollection<TValue> IDictionary<TKey,TValue>.Values {
 306             get {
 307                 return GetValueListHelper();
 308             }
 309         }
 310
 311         System.Collections.ICollection System.Collections.IDictionary.Values {
 312             get {
 313                 return GetValueListHelper();
 314             }
 315         }
 316
 317         private KeyList GetKeyListHelper() {
 318             if (keyList == null)
 319                 keyList = new KeyList(this);
 320             return keyList;
 321         }
 322
 323         private ValueList GetValueListHelper() {
 324             if (valueList == null)
 325                 valueList = new ValueList(this);
 326             return valueList;
 327         }
 328
 329         bool ICollection<KeyValuePair<TKey, TValue>>.IsReadOnly {
 330             get { return false; }
 331         }
 332
 333         bool System.Collections.IDictionary.IsReadOnly {
 334             get { return false; }
 335         }
 336
 337         bool System.Collections.IDictionary.IsFixedSize {
 338             get { return false; }
 339         }
 340
 341         bool System.Collections.ICollection.IsSynchronized {
 342             get { return false; }
 343         }
 344
 345         // Synchronization root for this object.
 346         Object System.Collections.ICollection.SyncRoot {
 347             get {
 348                 if( _syncRoot == null) {
 349                     System.Threading.Interlocked.CompareExchange(ref _syncRoot, new Object(), null);
 350                 }
 351                 return _syncRoot;
 352             }
 353         }
 354
 355         // Removes all entries from this sorted list.
 356         public void Clear() {
 357             // clear does not change the capacity
 358             version++;
 359             // Don't need to doc this but we clear the elements so that the gc can reclaim the references.
 360             Array.Clear(keys, 0, _size);
 361             Array.Clear(values, 0, _size);
 362             _size = 0;
 363         }
 364
 365
 366         bool System.Collections.IDictionary.Contains(Object key) {
 367             if( IsCompatibleKey(key)) {
 368                 return ContainsKey((TKey) key);
 369             }
 370             return false;
 371         }
 372
 373         // Checks if this sorted list contains an entry with the given key.
 374         //
 375         public bool ContainsKey(TKey key) {
 376             return IndexOfKey(key) >= 0;
 377         }
 378
 379         // Checks if this sorted list contains an entry with the given value. The
 380         // values of the entries of the sorted list are compared to the given value
 381         // using the Object.Equals method. This method performs a linear
 382         // search and is substantially slower than the Contains
 383         // method.
 384         //
 385         public bool ContainsValue(TValue value) {
 386             return IndexOfValue(value) >= 0;
 387         }
 388
 389         // Copies the values in this SortedList to an array.
 390         void ICollection<KeyValuePair<TKey, TValue>>.CopyTo(KeyValuePair<TKey, TValue>[] array, int arrayIndex) {
 391             if (array == null) {
 392                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
 393             }
 394
 395             if (arrayIndex < 0 || arrayIndex > array.Length)  {
 396                 ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.arrayIndex, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum);
 397             }
 398
 399             if (array.Length - arrayIndex < Count) {
 400                 ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_ArrayPlusOffTooSmall);
 401             }
 402
 403             for (int i = 0; i < Count; i++) {
 404                 KeyValuePair<TKey, TValue> entry = new KeyValuePair<TKey, TValue>(keys[i],values[i]);
 405                 array[arrayIndex + i] = entry;
 406             }
 407         }
 408
 409         void System.Collections.ICollection.CopyTo(Array array, int arrayIndex) {
 410             if (array == null) {
 411                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
 412             }
 413
 414             if (array.Rank != 1) {
 415                 ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_RankMultiDimNotSupported);
 416             }
 417
 418             if( array.GetLowerBound(0) != 0 ) {
 419                 ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_NonZeroLowerBound);
 420             }
 421
 422             if (arrayIndex < 0 || arrayIndex > array.Length) {
 423                 ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.arrayIndex, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum);
 424             }
 425
 426             if (array.Length - arrayIndex < Count) {
 427                 ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_ArrayPlusOffTooSmall);
 428             }
 429
 430             KeyValuePair<TKey, TValue>[] keyValuePairArray = array as KeyValuePair<TKey, TValue>[];
 431             if (keyValuePairArray != null) {
 432                 for (int i = 0; i < Count; i++) {
 433                     keyValuePairArray[i + arrayIndex] = new KeyValuePair<TKey, TValue>(keys[i],values[i]);
 434                 }
 435             }
 436             else {
 437                 object[] objects = array as object[];
 438                 if( objects == null) {
 439                     ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidArrayType);
 440                 }
 441
 442                 try {
 443                     for (int i = 0; i < Count; i++) {
 444                         objects[i + arrayIndex] = new KeyValuePair<TKey, TValue>(keys[i],values[i]);
 445                     }
 446                 }
 447                 catch(ArrayTypeMismatchException) {
 448                     ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidArrayType);
 449                 }
 450
 451             }
 452         }
 453
 454         private const int MaxArrayLength = 0X7FEFFFFF;
 455
 456         // Ensures that the capacity of this sorted list is at least the given
 457         // minimum value. If the currect capacity of the list is less than
 458         // min, the capacity is increased to twice the current capacity or
 459         // to min, whichever is larger.
 460         private void EnsureCapacity(int min) {
 461             int newCapacity = keys.Length == 0? _defaultCapacity: keys.Length * 2;
 462             // Allow the list to grow to maximum possible capacity (~2G elements) before encountering overflow.
 463             // Note that this check works even when _items.Length overflowed thanks to the (uint) cast
 464             if ((uint)newCapacity > MaxArrayLength) newCapacity = MaxArrayLength;
 465             if (newCapacity < min) newCapacity = min;
 466             Capacity = newCapacity;
 467         }
 468
 469         // Returns the value of the entry at the given index.
 470         //
 471         private TValue GetByIndex(int index) {
 472             if (index < 0 || index >= _size)
 473                 ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_Index);
 474             return values[index];
 475         }
 476
 477
 478         public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator() {
 479             return new Enumerator(this, Enumerator.KeyValuePair);
 480         }
 481
 482         IEnumerator<KeyValuePair<TKey, TValue>> IEnumerable<KeyValuePair<TKey, TValue>>.GetEnumerator()
 483         {
 484             return new Enumerator(this, Enumerator.KeyValuePair);
 485         }
 486
 487         System.Collections.IDictionaryEnumerator System.Collections.IDictionary.GetEnumerator() {
 488             return new Enumerator(this, Enumerator.DictEntry);
 489         }
 490
 491         System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() {
 492             return new Enumerator(this, Enumerator.KeyValuePair);
 493         }
 494
 495
 496         // Returns the key of the entry at the given index.
 497         //
 498         private TKey GetKey(int index) {
 499             if (index < 0 || index >= _size) ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_Index);
 500             return keys[index];
 501         }
 502
 503
 504         // Returns the value associated with the given key. If an entry with the
 505         // given key is not found, the returned value is null.
 506         //
 507         public TValue this[TKey key] {
 508             get {
 509                 int i = IndexOfKey(key);
 510                 if (i >= 0)
 511                     return values[i];
 512
 513                 ThrowHelper.ThrowKeyNotFoundException();
 514                 return default(TValue);
 515             }
 516             set {
 517                 if (((Object) key) == null) ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
 518                 int i = Array.BinarySearch<TKey>(keys, 0, _size, key, comparer);
 519                 if (i >= 0) {
 520                     values[i] = value;
 521                     version++;
 522                     return;
 523                 }
 524                 Insert(~i, key, value);
 525             }
 526         }
 527
 528         Object System.Collections.IDictionary.this[Object key] {
 529             get {
 530                 if( IsCompatibleKey(key)) {
 531                     int i = IndexOfKey((TKey)key);
 532                     if (i >= 0) {
 533                         return values[i];
 534                     }
 535                 }
 536
 537                 return null;
 538             }
 539             set {
 540                 if(!IsCompatibleKey(key)) {
 541                     ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
 542                 }
 543
 544                 ThrowHelper.IfNullAndNullsAreIllegalThenThrow<TValue>(value, ExceptionArgument.value);
 545
 546                 try {
 547                     TKey tempKey = (TKey)key;
 548                     try {
 549                         this[tempKey] = (TValue)value;
 550                     }
 551                     catch (InvalidCastException) {
 552                         ThrowHelper.ThrowWrongValueTypeArgumentException(value, typeof(TValue));
 553                     }
 554                 }
 555                 catch (InvalidCastException) {
 556                     ThrowHelper.ThrowWrongKeyTypeArgumentException(key, typeof(TKey));
 557                 }
 558             }
 559         }
 560
 561         // Returns the index of the entry with a given key in this sorted list. The
 562         // key is located through a binary search, and thus the average execution
 563         // time of this method is proportional to Log2(size), where
 564         // size is the size of this sorted list. The returned value is -1 if
 565         // the given key does not occur in this sorted list. Null is an invalid
 566         // key value.
 567         //
 568         public int IndexOfKey(TKey key) {
 569             if (key == null)
 570                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
 571             int ret = Array.BinarySearch<TKey>(keys, 0, _size, key, comparer);
 572             return ret >=0 ? ret : -1;
 573         }
 574
 575         // Returns the index of the first occurrence of an entry with a given value
 576         // in this sorted list. The entry is located through a linear search, and
 577         // thus the average execution time of this method is proportional to the
 578         // size of this sorted list. The elements of the list are compared to the
 579         // given value using the Object.Equals method.
 580         //
 581         public int IndexOfValue(TValue value) {
 582             return Array.IndexOf(values, value, 0, _size);
 583         }
 584
 585         // Inserts an entry with a given key and value at a given index.
 586         private void Insert(int index, TKey key, TValue value) {
 587             if (_size == keys.Length) EnsureCapacity(_size + 1);
 588             if (index < _size) {
 589                 Array.Copy(keys, index, keys, index + 1, _size - index);
 590                 Array.Copy(values, index, values, index + 1, _size - index);
 591             }
 592             keys[index] = key;
 593             values[index] = value;
 594             _size++;
 595             version++;
 596         }
 597
 598         public bool TryGetValue(TKey key, out TValue value) {
 599             int i = IndexOfKey(key);
 600             if (i >= 0) {
 601                 value =values[i];
 602                 return true;
 603             }
 604
 605             value = default(TValue);
 606             return false;
 607         }
 608
 609         // Removes the entry at the given index. The size of the sorted list is
 610         // decreased by one.
 611         //
 612         public void RemoveAt(int index) {
 613             if (index < 0 || index >= _size) ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_Index);
 614             _size--;
 615             if (index < _size) {
 616                 Array.Copy(keys, index + 1, keys, index, _size - index);
 617                 Array.Copy(values, index + 1, values, index, _size - index);
 618             }
 619             keys[_size] = default(TKey);
 620             values[_size] = default(TValue);
 621             version++;
 622         }
 623
 624         // Removes an entry from this sorted list. If an entry with the specified
 625         // key exists in the sorted list, it is removed. An ArgumentException is
 626         // thrown if the key is null.
 627         //
 628         public bool Remove(TKey key) {
 629             int i = IndexOfKey(key);
 630             if (i >= 0)
 631                 RemoveAt(i);
 632             return i >= 0;
 633         }
 634
 635         void System.Collections.IDictionary.Remove(Object key) {
 636             if( IsCompatibleKey(key)) {
 637                 Remove((TKey) key);
 638             }
 639         }
 640
 641         // Sets the capacity of this sorted list to the size of the sorted list.
 642         // This method can be used to minimize a sorted list's memory overhead once
 643         // it is known that no new elements will be added to the sorted list. To
 644         // completely clear a sorted list and release all memory referenced by the
 645         // sorted list, execute the following statements:
 646         //
 647         // SortedList.Clear();
 648         // SortedList.TrimExcess();
 649         //
 650         public void TrimExcess() {
 651             int threshold = (int)(((double)keys.Length) * 0.9);
 652             if( _size < threshold ) {
 653                 Capacity = _size;
 654             }
 655         }
 656
 657         private static bool IsCompatibleKey(object key) {
 658             if( key == null) {
 659                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
 660             }
 661
 662             return (key is TKey);
 663         }
 664
 665
 666         /// <include file='doc\SortedList.uex' path='docs/doc[@for="SortedListEnumerator"]/*' />
 667         [Serializable()]
 668         private struct Enumerator : IEnumerator<KeyValuePair<TKey, TValue>>, System.Collections.IDictionaryEnumerator
 669         {
 670             private SortedList<TKey, TValue> _sortedList;
 671             private TKey key;
 672             private TValue value;
 673             private int index;
 674             private int version;
 675             private int getEnumeratorRetType;  // What should Enumerator.Current return?
 676
 677             internal const int KeyValuePair = 1;
 678             internal const int DictEntry = 2;
 679
 680             internal Enumerator(SortedList<TKey, TValue> sortedList, int getEnumeratorRetType) {
 681                 this._sortedList = sortedList;
 682                 this.index = 0;
 683                 version = _sortedList.version;
 684                 this.getEnumeratorRetType = getEnumeratorRetType;
 685                 key = default(TKey);
 686                 value = default(TValue);
 687             }
 688
 689             public void Dispose()
 690             {
 691                 index = 0;
 692                 key = default(TKey);
 693                 value = default(TValue);
 694             }
 695
 696
 697             Object System.Collections.IDictionaryEnumerator.Key {
 698                 get {
 699                     if( index == 0 || (index == _sortedList.Count + 1) ) {
 700                          ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumOpCantHappen);
 701                     }
 702
 703                     return key;
 704                 }
 705             }
 706
 707             public bool MoveNext() {
 708                 if (version != _sortedList.version) ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumFailedVersion);
 709
 710                 if ( (uint)index < (uint)_sortedList.Count ) {
 711                     key = _sortedList.keys[index];
 712                     value = _sortedList.values[index];
 713                     index++;
 714                     return true;
 715                 }
 716
 717                 index = _sortedList.Count + 1;
 718                 key = default(TKey);
 719                 value = default(TValue);
 720                 return false;
 721             }
 722
 723             DictionaryEntry System.Collections.IDictionaryEnumerator.Entry {
 724                 get {
 725                     if( index == 0 || (index == _sortedList.Count + 1) ) {
 726                          ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumOpCantHappen);
 727                     }
 728
 729                     return new DictionaryEntry(key, value);
 730                 }
 731             }
 732
 733             public KeyValuePair<TKey, TValue> Current {
 734                 get {
 735                     return new KeyValuePair<TKey, TValue>(key, value);
 736                 }
 737             }
 738
 739             Object System.Collections.IEnumerator.Current {
 740                 get {
 741                     if( index == 0 || (index == _sortedList.Count + 1) ) {
 742                         ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumOpCantHappen);
 743                     }
 744
 745                     if (getEnumeratorRetType == DictEntry) {
 746                         return new System.Collections.DictionaryEntry(key, value);
 747                     } else {
 748                         return new KeyValuePair<TKey, TValue>(key, value);
 749                     }
 750                 }
 751             }
 752
 753             Object System.Collections.IDictionaryEnumerator.Value {
 754                 get {
 755                     if( index == 0 || (index == _sortedList.Count + 1) ) {
 756                          ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumOpCantHappen);
 757                     }
 758
 759                     return value;
 760                 }
 761             }
 762
 763             void System.Collections.IEnumerator.Reset() {
 764                 if (version != _sortedList.version) {
 765                     ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumFailedVersion);
 766                 }
 767
 768                 index = 0;
 769                 key = default(TKey);
 770                 value = default(TValue);
 771             }
 772         }
 773
 774
 775         [Serializable()]
 776         private sealed class SortedListKeyEnumerator : IEnumerator<TKey>, System.Collections.IEnumerator
 777         {
 778             private SortedList<TKey, TValue> _sortedList;
 779             private int index;
 780             private int version;
 781             private TKey currentKey;
 782
 783             internal SortedListKeyEnumerator(SortedList<TKey, TValue> sortedList) {
 784                 _sortedList = sortedList;
 785                 version = sortedList.version;
 786             }
 787
 788             public void Dispose() {
 789                 index = 0;
 790                 currentKey = default(TKey);
 791             }
 792
 793             public bool MoveNext() {
 794                 if (version != _sortedList.version) {
 795                     ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumFailedVersion);
 796                 }
 797
 798                 if ( (uint)index < (uint)_sortedList.Count) {
 799                     currentKey = _sortedList.keys[index];
 800                     index++;
 801                     return true;
 802                 }
 803
 804                 index = _sortedList.Count + 1;
 805                 currentKey = default(TKey);
 806                 return false;
 807             }
 808
 809             public TKey Current {
 810                 get {
 811                     return currentKey;
 812                 }
 813             }
 814
 815             Object System.Collections.IEnumerator.Current {
 816                 get {
 817                     if( index == 0 || (index == _sortedList.Count + 1) ) {
 818                          ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumOpCantHappen);
 819                     }
 820
 821                     return currentKey;
 822                 }
 823             }
 824
 825             void System.Collections.IEnumerator.Reset() {
 826                 if (version != _sortedList.version) {
 827                     ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumFailedVersion);
 828                 }
 829                 index = 0;
 830                 currentKey = default(TKey);
 831             }
 832         }
 833
 834
 835         [Serializable()]
 836         private sealed class SortedListValueEnumerator : IEnumerator<TValue>, System.Collections.IEnumerator
 837         {
 838             private SortedList<TKey, TValue> _sortedList;
 839             private int index;
 840             private int version;
 841             private TValue currentValue;
 842
 843             internal SortedListValueEnumerator(SortedList<TKey, TValue> sortedList) {
 844                 _sortedList = sortedList;
 845                 version = sortedList.version;
 846             }
 847
 848             public void Dispose() {
 849                 index = 0;
 850                 currentValue = default(TValue);
 851             }
 852
 853             public bool MoveNext() {
 854                 if (version != _sortedList.version) {
 855                     ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumFailedVersion);
 856                 }
 857
 858                 if ( (uint)index < (uint)_sortedList.Count) {
 859                     currentValue = _sortedList.values[index];
 860                     index++;
 861                     return true;
 862                 }
 863
 864                 index = _sortedList.Count + 1;
 865                 currentValue = default(TValue);
 866                 return false;
 867             }
 868
 869             public TValue Current {
 870                 get {
 871                     return currentValue;
 872                 }
 873             }
 874
 875             Object System.Collections.IEnumerator.Current {
 876                 get {
 877                     if( index == 0 || (index == _sortedList.Count + 1) ) {
 878                          ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumOpCantHappen);
 879                     }
 880
 881                     return currentValue;
 882                 }
 883             }
 884
 885             void System.Collections.IEnumerator.Reset() {
 886                 if (version != _sortedList.version) {
 887                     ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumFailedVersion);
 888                 }
 889                 index = 0;
 890                 currentValue = default(TValue);
 891             }
 892         }
 893
 894
 895         [DebuggerTypeProxy(typeof(System_DictionaryKeyCollectionDebugView<,>))]
 896         [DebuggerDisplay("Count = {Count}")]
 897         [Serializable()]
 898         private sealed class KeyList : IList<TKey>, System.Collections.ICollection
 899         {
 900             private SortedList<TKey, TValue> _dict;
 901
 902             internal KeyList(SortedList<TKey, TValue> dictionary) {
 903                 this._dict = dictionary;
 904             }
 905
 906             public int Count {
 907                 get { return _dict._size; }
 908             }
 909
 910             public bool IsReadOnly {
 911                 get { return true; }
 912             }
 913
 914             bool System.Collections.ICollection.IsSynchronized {
 915                 get { return false; }
 916             }
 917
 918             Object System.Collections.ICollection.SyncRoot {
 919                 get { return ((ICollection)_dict).SyncRoot; }
 920             }
 921
 922             public void Add(TKey key) {
 923                 ThrowHelper.ThrowNotSupportedException(ExceptionResource.NotSupported_SortedListNestedWrite);
 924             }
 925
 926             public void Clear() {
 927                 ThrowHelper.ThrowNotSupportedException(ExceptionResource.NotSupported_SortedListNestedWrite);
 928             }
 929
 930             public bool Contains(TKey key) {
 931                 return _dict.ContainsKey(key);
 932             }
 933
 934             public void CopyTo(TKey[] array, int arrayIndex) {
 935                 // defer error checking to Array.Copy
 936                 Array.Copy(_dict.keys, 0, array, arrayIndex, _dict.Count);
 937             }
 938
 939             void System.Collections.ICollection.CopyTo(Array array, int arrayIndex) {
 940                 if (array != null && array.Rank != 1)
 941                     ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_RankMultiDimNotSupported);
 942
 943                 try {
 944                     // defer error checking to Array.Copy
 945                     Array.Copy(_dict.keys, 0, array, arrayIndex, _dict.Count);
 946                 }
 947                 catch(ArrayTypeMismatchException){
 948                     ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidArrayType);
 949                 }
 950             }
 951
 952             public void Insert(int index, TKey value) {
 953                 ThrowHelper.ThrowNotSupportedException(ExceptionResource.NotSupported_SortedListNestedWrite);
 954             }
 955
 956             public TKey this[int index] {
 957                 get {
 958                     return _dict.GetKey(index);
 959                 }
 960                 set {
 961                     ThrowHelper.ThrowNotSupportedException(ExceptionResource.NotSupported_KeyCollectionSet);
 962                 }
 963             }
 964
 965             public IEnumerator<TKey> GetEnumerator() {
 966                 return new SortedListKeyEnumerator(_dict);
 967             }
 968
 969             System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() {
 970                 return new SortedListKeyEnumerator(_dict);
 971             }
 972
 973             public int IndexOf(TKey key) {
 974                 if (((Object) key) == null)
 975                     ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
 976
 977                 int i = Array.BinarySearch<TKey>(_dict.keys, 0,
 978                                           _dict.Count, key, _dict.comparer);
 979                 if (i >= 0) return i;
 980                 return -1;
 981             }
 982
 983             public bool Remove(TKey key) {
 984                 ThrowHelper.ThrowNotSupportedException(ExceptionResource.NotSupported_SortedListNestedWrite);
 985                 return false;
 986             }
 987
 988             public void RemoveAt(int index) {
 989                 ThrowHelper.ThrowNotSupportedException(ExceptionResource.NotSupported_SortedListNestedWrite);
 990             }
 991         }
 992
 993         [DebuggerTypeProxy(typeof(System_DictionaryValueCollectionDebugView<,>))]
 994         [DebuggerDisplay("Count = {Count}")]
 995         [Serializable()]
 996         private sealed class ValueList : IList<TValue>, System.Collections.ICollection
 997         {
 998             private SortedList<TKey, TValue> _dict;
 999
1000             internal ValueList(SortedList<TKey, TValue> dictionary) {
1001                 this._dict = dictionary;
1002             }
1003
1004             public int Count {
1005                 get { return _dict._size; }
1006             }
1007
1008             public bool IsReadOnly {
1009                 get { return true; }
1010             }
1011
1012             bool System.Collections.ICollection.IsSynchronized {
1013                 get { return false; }
1014             }
1015
1016             Object System.Collections.ICollection.SyncRoot {
1017                 get { return ((ICollection)_dict).SyncRoot; }
1018             }
1019
1020             public void Add(TValue key) {
1021                 ThrowHelper.ThrowNotSupportedException(ExceptionResource.NotSupported_SortedListNestedWrite);
1022             }
1023
1024             public void Clear() {
1025                 ThrowHelper.ThrowNotSupportedException(ExceptionResource.NotSupported_SortedListNestedWrite);
1026             }
1027
1028             public bool Contains(TValue value) {
1029                 return _dict.ContainsValue(value);
1030             }
1031
1032             public void CopyTo(TValue[] array, int arrayIndex) {
1033                 // defer error checking to Array.Copy
1034                 Array.Copy(_dict.values, 0, array, arrayIndex, _dict.Count);
1035             }
1036
1037             void System.Collections.ICollection.CopyTo(Array array, int arrayIndex) {
1038                 if (array != null && array.Rank != 1)
1039                     ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_RankMultiDimNotSupported);
1040
1041                 try {
1042                     // defer error checking to Array.Copy
1043                     Array.Copy(_dict.values, 0, array, arrayIndex, _dict.Count);
1044                 }
1045                 catch(ArrayTypeMismatchException){
1046                     ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidArrayType);
1047                 }
1048             }
1049
1050             public void Insert(int index, TValue value) {
1051                 ThrowHelper.ThrowNotSupportedException(ExceptionResource.NotSupported_SortedListNestedWrite);
1052             }
1053
1054             public TValue this[int index] {
1055                 get {
1056                     return _dict.GetByIndex(index);
1057                 }
1058                 set {
1059                     ThrowHelper.ThrowNotSupportedException(ExceptionResource.NotSupported_SortedListNestedWrite);
1060                 }
1061             }
1062
1063             public IEnumerator<TValue> GetEnumerator() {
1064                 return new SortedListValueEnumerator(_dict);
1065             }
1066
1067             System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() {
1068                 return new SortedListValueEnumerator(_dict);
1069             }
1070
1071             public int IndexOf(TValue value) {
1072                 return Array.IndexOf(_dict.values, value, 0, _dict.Count);
1073             }
1074
1075             public bool Remove(TValue value) {
1076                 ThrowHelper.ThrowNotSupportedException(ExceptionResource.NotSupported_SortedListNestedWrite);
1077                 return false;
1078             }
1079
1080             public void RemoveAt(int index) {
1081                 ThrowHelper.ThrowNotSupportedException(ExceptionResource.NotSupported_SortedListNestedWrite);
1082             }
1083
1084         }
1085     }
1086 }