The Labs \ Source Viewer \ SSCLI \ System.Collections.Generic \ ValueList

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

Developer Fusion