The Labs \ Source Viewer \ SSCLI \ System.Collections \ KeyList

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

Developer Fusion