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

  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:  List
  18. **
  19. ** Purpose: Implements a generic, dynamically sized list as an
  20. **          array.
  21. **
  22. **
  23. ===========================================================*/
  24. namespace System.Collections.Generic
  25. {
  26.    
  27.     using System;
  28.     using System.Diagnostics;
  29.     using System.Collections.ObjectModel;
  30.     using System.Security.Permissions;
  31.    
  32.     // Implements a variable-size List that uses an array of objects to store the
  33.     // elements. A List has a capacity, which is the allocated length
  34.     // of the internal array. As elements are added to a List, the capacity
  35.     // of the List is automatically increased as required by reallocating the
  36.     // internal array.
  37.     //
  38.     [DebuggerTypeProxy(typeof(Mscorlib_CollectionDebugView<>))]
  39.     [DebuggerDisplay("Count = {Count}")]
  40.     [Serializable()]
  41.    
  42.     public class List<T> : IList<T>, System.Collections.IList
  43.     {
  44.         private const int _defaultCapacity = 4;
  45.        
  46.         private T[] _items;
  47.         private int _size;
  48.         private int _version;
  49.         [NonSerialized()]
  50.         private object _syncRoot;
  51.        
  52.         static T[] _emptyArray = new T[0];
  53.        
  54.         // Constructs a List. The list is initially empty and has a capacity
  55.         // of zero. Upon adding the first element to the list the capacity is
  56.         // increased to 16, and then increased in multiples of two as required.
  57.         public List()
  58.         {
  59.             _items = _emptyArray;
  60.         }
  61.        
  62.         // Constructs a List with a given initial capacity. The list is
  63.         // initially empty, but will have room for the given number of elements
  64.         // before any reallocations are required.
  65.         //
  66.         public List(int capacity)
  67.         {
  68.             if (capacity < 0)
  69.                 ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.capacity, ExceptionResource.ArgumentOutOfRange_SmallCapacity);
  70.             _items = new T[capacity];
  71.         }
  72.        
  73.         // Constructs a List, copying the contents of the given collection. The
  74.         // size and capacity of the new list will both be equal to the size of the
  75.         // given collection.
  76.         //
  77.         public List(IEnumerable<T> collection)
  78.         {
  79.             if (collection == null)
  80.                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.collection);
  81.            
  82.             ICollection<T> c = collection as ICollection<T>;
  83.             if (c != null) {
  84.                 int count = c.Count;
  85.                 _items = new T[count];
  86.                 c.CopyTo(_items, 0);
  87.                 _size = count;
  88.             }
  89.             else {
  90.                 _size = 0;
  91.                 _items = new T[_defaultCapacity];
  92.                
  93.                 using (IEnumerator<T> en = collection.GetEnumerator()) {
  94.                     while (en.MoveNext()) {
  95.                         Add(en.Current);
  96.                     }
  97.                 }
  98.             }
  99.         }
  100.        
  101.         // Gets and sets the capacity of this list. The capacity is the size of
  102.         // the internal array used to hold items. When set, the internal
  103.         // array of the list is reallocated to the given capacity.
  104.         //
  105.         public int Capacity {
  106.             get { return _items.Length; }
  107.             set {
  108.                 if (value != _items.Length) {
  109.                     if (value < _size) {
  110.                         ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.value, ExceptionResource.ArgumentOutOfRange_SmallCapacity);
  111.                     }
  112.                    
  113.                     if (value > 0) {
  114.                         T[] newItems = new T[value];
  115.                         if (_size > 0) {
  116.                             Array.Copy(_items, 0, newItems, 0, _size);
  117.                         }
  118.                         _items = newItems;
  119.                     }
  120.                     else {
  121.                         _items = _emptyArray;
  122.                     }
  123.                 }
  124.             }
  125.         }
  126.        
  127.         // Read-only property describing how many elements are in the List.
  128.         public int Count {
  129.             get { return _size; }
  130.         }
  131.        
  132.         bool System.Collections.IList.IsFixedSize {
  133.             get { return false; }
  134.         }
  135.        
  136.        
  137.         // Is this List read-only?
  138.         bool ICollection<T>.IsReadOnly {
  139.             get { return false; }
  140.         }
  141.        
  142.         bool System.Collections.IList.IsReadOnly {
  143.             get { return false; }
  144.         }
  145.        
  146.         // Is this List synchronized (thread-safe)?
  147.         bool System.Collections.ICollection.IsSynchronized {
  148.             get { return false; }
  149.         }
  150.        
  151.         // Synchronization root for this object.
  152.         object System.Collections.ICollection.SyncRoot {
  153.             get {
  154.                 if (_syncRoot == null) {
  155.                     System.Threading.Interlocked.CompareExchange(ref _syncRoot, new object(), null);
  156.                 }
  157.                 return _syncRoot;
  158.             }
  159.         }
  160.         // Sets or Gets the element at the given index.
  161.         //
  162.         public T this[int index]
  163.         {
  164.             get {
  165.                 // Fllowing trick can reduce the range check by one
  166.                 if ((uint)index >= (uint)_size) {
  167.                     ThrowHelper.ThrowArgumentOutOfRangeException();
  168.                 }
  169.                 return _items[index];
  170.             }
  171.             set {
  172.                 if ((uint)index >= (uint)_size) {
  173.                     ThrowHelper.ThrowArgumentOutOfRangeException();
  174.                 }
  175.                 _items[index] = value;
  176.                 _version++;
  177.             }
  178.         }
  179.        
  180.         private static bool IsCompatibleObject(object value)
  181.         {
  182.             if ((value is T) || (value == null && !typeof(T).IsValueType)) {
  183.                 return true;
  184.             }
  185.             return false;
  186.         }
  187.        
  188.         private static void VerifyValueType(object value)
  189.         {
  190.             if (!IsCompatibleObject(value)) {
  191.                 ThrowHelper.ThrowWrongValueTypeArgumentException(value, typeof(T));
  192.             }
  193.         }
  194.        
  195.         object System.Collections.IList.this[int index]
  196.         {
  197.             get { return this[index]; }
  198.             set {
  199.                 VerifyValueType(value);
  200.                 this[index] = (T)value;
  201.             }
  202.         }
  203.        
  204.         // Adds the given object to the end of this list. The size of the list is
  205.         // increased by one. If required, the capacity of the list is doubled
  206.         // before adding the new element.
  207.         //
  208.         public void Add(T item)
  209.         {
  210.             if (_size == _items.Length)
  211.                 EnsureCapacity(_size + 1);
  212.             _items[_size++] = item;
  213.             _version++;
  214.         }
  215.        
  216.         int System.Collections.IList.Add(object item)
  217.         {
  218.             VerifyValueType(item);
  219.             Add((T)item);
  220.             return Count - 1;
  221.         }
  222.        
  223.        
  224.         // Adds the elements of the given collection to the end of this list. If
  225.         // required, the capacity of the list is increased to twice the previous
  226.         // capacity or the new size, whichever is larger.
  227.         //
  228.         public void AddRange(IEnumerable<T> collection)
  229.         {
  230.             InsertRange(_size, collection);
  231.         }
  232.        
  233.         public ReadOnlyCollection<T> AsReadOnly()
  234.         {
  235.             return new ReadOnlyCollection<T>(this);
  236.         }
  237.        
  238.         // Searches a section of the list for a given element using a binary search
  239.         // algorithm. Elements of the list are compared to the search value using
  240.         // the given IComparer interface. If comparer is null, elements of
  241.         // the list are compared to the search value using the IComparable
  242.         // interface, which in that case must be implemented by all elements of the
  243.         // list and the given search value. This method assumes that the given
  244.         // section of the list is already sorted; if this is not the case, the
  245.         // result will be incorrect.
  246.         //
  247.         // The method returns the index of the given value in the list. If the
  248.         // list does not contain the given value, the method returns a negative
  249.         // integer. The bitwise complement operator (~) can be applied to a
  250.         // negative result to produce the index of the first element (if any) that
  251.         // is larger than the given search value. This is also the index at which
  252.         // the search value should be inserted into the list in order for the list
  253.         // to remain sorted.
  254.         //
  255.         // The method uses the Array.BinarySearch method to perform the
  256.         // search.
  257.         //
  258.         public int BinarySearch(int index, int count, T item, IComparer<T> comparer)
  259.         {
  260.             if (index < 0 || count < 0)
  261.                 ThrowHelper.ThrowArgumentOutOfRangeException((index < 0 ? ExceptionArgument.index : ExceptionArgument.count), ExceptionResource.ArgumentOutOfRange_NeedNonNegNum);
  262.             if (_size - index < count)
  263.                 ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidOffLen);
  264.            
  265.             return Array.BinarySearch<T>(_items, index, count, item, comparer);
  266.         }
  267.        
  268.         public int BinarySearch(T item)
  269.         {
  270.             return BinarySearch(0, Count, item, null);
  271.         }
  272.        
  273.         public int BinarySearch(T item, IComparer<T> comparer)
  274.         {
  275.             return BinarySearch(0, Count, item, comparer);
  276.         }
  277.        
  278.        
  279.         // Clears the contents of List.
  280.         public void Clear()
  281.         {
  282.             Array.Clear(_items, 0, _size);
  283.             // Don't need to doc this but we clear the elements so that the gc can reclaim the references.
  284.             _size = 0;
  285.             _version++;
  286.         }
  287.        
  288.         // Contains returns true if the specified element is in the List.
  289.         // It does a linear, O(n) search. Equality is determined by calling
  290.         // item.Equals().
  291.         //
  292.         public bool Contains(T item)
  293.         {
  294.             if ((object)item == null) {
  295.                 for (int i = 0; i < _size; i++)
  296.                     if ((object)_items[i] == null)
  297.                         return true;
  298.                 return false;
  299.             }
  300.             else {
  301.                 EqualityComparer<T> c = EqualityComparer<T>.Default;
  302.                 for (int i = 0; i < _size; i++) {
  303.                     if (c.Equals(_items[i], item))
  304.                         return true;
  305.                 }
  306.                 return false;
  307.             }
  308.         }
  309.        
  310.         bool System.Collections.IList.Contains(object item)
  311.         {
  312.             if (IsCompatibleObject(item)) {
  313.                 return Contains((T)item);
  314.             }
  315.             return false;
  316.         }
  317.        
  318.         public List<TOutput> ConvertAll<TOutput>(Converter<T, TOutput> converter)
  319.         {
  320.             if (converter == null) {
  321.                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.converter);
  322.             }
  323.            
  324.             List<TOutput> list = new List<TOutput>(_size);
  325.             for (int i = 0; i < _size; i++) {
  326.                 list._items[i] = converter(_items[i]);
  327.             }
  328.             list._size = _size;
  329.             return list;
  330.         }
  331.        
  332.         // Copies this List into array, which must be of a
  333.         // compatible array type.
  334.         //
  335.         public void CopyTo(T[] array)
  336.         {
  337.             CopyTo(array, 0);
  338.         }
  339.        
  340.         // Copies this List into array, which must be of a
  341.         // compatible array type.
  342.         //
  343.         void System.Collections.ICollection.CopyTo(Array array, int arrayIndex)
  344.         {
  345.             if ((array != null) && (array.Rank != 1)) {
  346.                 ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_RankMultiDimNotSupported);
  347.             }
  348.            
  349.             try {
  350.                 // Array.Copy will check for NULL.
  351.                 Array.Copy(_items, 0, array, arrayIndex, _size);
  352.             }
  353.             catch (ArrayTypeMismatchException) {
  354.                 ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidArrayType);
  355.             }
  356.         }
  357.        
  358.         // Copies a section of this list to the given array at the given index.
  359.         //
  360.         // The method uses the Array.Copy method to copy the elements.
  361.         //
  362.         public void CopyTo(int index, T[] array, int arrayIndex, int count)
  363.         {
  364.             if (_size - index < count) {
  365.                 ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidOffLen);
  366.             }
  367.            
  368.             // Delegate rest of error checking to Array.Copy.
  369.             Array.Copy(_items, index, array, arrayIndex, count);
  370.         }
  371.        
  372.         public void CopyTo(T[] array, int arrayIndex)
  373.         {
  374.             // Delegate rest of error checking to Array.Copy.
  375.             Array.Copy(_items, 0, array, arrayIndex, _size);
  376.         }
  377.        
  378.         // Ensures that the capacity of this list is at least the given minimum
  379.         // value. If the currect capacity of the list is less than min, the
  380.         // capacity is increased to twice the current capacity or to min,
  381.         // whichever is larger.
  382.         private void EnsureCapacity(int min)
  383.         {
  384.             if (_items.Length < min) {
  385.                 int newCapacity = _items.Length == 0 ? _defaultCapacity : _items.Length * 2;
  386.                 if (newCapacity < min)
  387.                     newCapacity = min;
  388.                 Capacity = newCapacity;
  389.             }
  390.         }
  391.        
  392.         public bool Exists(Predicate<T> match)
  393.         {
  394.             return FindIndex(match) != -1;
  395.         }
  396.        
  397.         public T Find(Predicate<T> match)
  398.         {
  399.             if (match == null) {
  400.                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.match);
  401.             }
  402.            
  403.             for (int i = 0; i < _size; i++) {
  404.                 if (match(_items[i])) {
  405.                     return _items[i];
  406.                 }
  407.             }
  408.             return default(T);
  409.         }
  410.        
  411.         public List<T> FindAll(Predicate<T> match)
  412.         {
  413.             if (match == null) {
  414.                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.match);
  415.             }
  416.            
  417.             List<T> list = new List<T>();
  418.             for (int i = 0; i < _size; i++) {
  419.                 if (match(_items[i])) {
  420.                     list.Add(_items[i]);
  421.                 }
  422.             }
  423.             return list;
  424.         }
  425.        
  426.         public int FindIndex(Predicate<T> match)
  427.         {
  428.             return FindIndex(0, _size, match);
  429.         }
  430.        
  431.         public int FindIndex(int startIndex, Predicate<T> match)
  432.         {
  433.             return FindIndex(startIndex, _size - startIndex, match);
  434.         }
  435.        
  436.         public int FindIndex(int startIndex, int count, Predicate<T> match)
  437.         {
  438.             if ((uint)startIndex > (uint)_size) {
  439.                 ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.startIndex, ExceptionResource.ArgumentOutOfRange_Index);
  440.             }
  441.            
  442.             if (count < 0 || startIndex > _size - count) {
  443.                 ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.count, ExceptionResource.ArgumentOutOfRange_Count);
  444.             }
  445.            
  446.             if (match == null) {
  447.                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.match);
  448.             }
  449.            
  450.             int endIndex = startIndex + count;
  451.             for (int i = startIndex; i < endIndex; i++) {
  452.                 if (match(_items[i]))
  453.                     return i;
  454.             }
  455.             return -1;
  456.         }
  457.        
  458.         public T FindLast(Predicate<T> match)
  459.         {
  460.             if (match == null) {
  461.                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.match);
  462.             }
  463.            
  464.             for (int i = _size - 1; i >= 0; i--) {
  465.                 if (match(_items[i])) {
  466.                     return _items[i];
  467.                 }
  468.             }
  469.             return default(T);
  470.         }
  471.        
  472.         public int FindLastIndex(Predicate<T> match)
  473.         {
  474.             return FindLastIndex(_size - 1, _size, match);
  475.         }
  476.        
  477.         public int FindLastIndex(int startIndex, Predicate<T> match)
  478.         {
  479.             return FindLastIndex(startIndex, startIndex + 1, match);
  480.         }
  481.        
  482.         public int FindLastIndex(int startIndex, int count, Predicate<T> match)
  483.         {
  484.             if (match == null) {
  485.                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.match);
  486.             }
  487.            
  488.             if (_size == 0) {
  489.                 // Special case for 0 length List
  490.                 if (startIndex != -1) {
  491.                     ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.startIndex, ExceptionResource.ArgumentOutOfRange_Index);
  492.                 }
  493.             }
  494.             else {
  495.                 // Make sure we're not out of range
  496.                 if ((uint)startIndex >= (uint)_size) {
  497.                     ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.startIndex, ExceptionResource.ArgumentOutOfRange_Index);
  498.                 }
  499.             }
  500.            
  501.             // 2nd have of this also catches when startIndex == MAXINT, so MAXINT - 0 + 1 == -1, which is < 0.
  502.             if (count < 0 || startIndex - count + 1 < 0) {
  503.                 ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.count, ExceptionResource.ArgumentOutOfRange_Count);
  504.             }
  505.            
  506.             int endIndex = startIndex - count;
  507.             for (int i = startIndex; i > endIndex; i--) {
  508.                 if (match(_items[i])) {
  509.                     return i;
  510.                 }
  511.             }
  512.             return -1;
  513.         }
  514.        
  515.        
  516.         public void ForEach(Action<T> action)
  517.         {
  518.             if (action == null) {
  519.                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.match);
  520.             }
  521.            
  522.             for (int i = 0; i < _size; i++) {
  523.                 action(_items[i]);
  524.             }
  525.         }
  526.        
  527.         // Returns an enumerator for this list with the given
  528.         // permission for removal of elements. If modifications made to the list
  529.         // while an enumeration is in progress, the MoveNext and
  530.         // GetObject methods of the enumerator will throw an exception.
  531.         //
  532.         public Enumerator GetEnumerator()
  533.         {
  534.             return new Enumerator(this);
  535.         }
  536.        
  537.         /// <internalonly/>
  538.         IEnumerator<T> IEnumerable<T>.GetEnumerator()
  539.         {
  540.             return new Enumerator(this);
  541.         }
  542.        
  543.         System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
  544.         {
  545.             return new Enumerator(this);
  546.         }
  547.        
  548.         public List<T> GetRange(int index, int count)
  549.         {
  550.             if (index < 0 || count < 0) {
  551.                 ThrowHelper.ThrowArgumentOutOfRangeException((index < 0 ? ExceptionArgument.index : ExceptionArgument.count), ExceptionResource.ArgumentOutOfRange_NeedNonNegNum);
  552.             }
  553.            
  554.             if (_size - index < count) {
  555.                 ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidOffLen);
  556.             }
  557.            
  558.             List<T> list = new List<T>(count);
  559.             Array.Copy(_items, index, list._items, 0, count);
  560.             list._size = count;
  561.             return list;
  562.         }
  563.        
  564.        
  565.         // Returns the index of the first occurrence of a given value in a range of
  566.         // this list. The list is searched forwards from beginning to end.
  567.         // The elements of the list are compared to the given value using the
  568.         // Object.Equals method.
  569.         //
  570.         // This method uses the Array.IndexOf method to perform the
  571.         // search.
  572.         //
  573.         public int IndexOf(T item)
  574.         {
  575.             return Array.IndexOf(_items, item, 0, _size);
  576.         }
  577.        
  578.         int System.Collections.IList.IndexOf(object item)
  579.         {
  580.             if (IsCompatibleObject(item)) {
  581.                 return IndexOf((T)item);
  582.             }
  583.             return -1;
  584.         }
  585.        
  586.         // Returns the index of the first occurrence of a given value in a range of
  587.         // this list. The list is searched forwards, starting at index
  588.         // index and ending at count number of elements. The
  589.         // elements of the list are compared to the given value using the
  590.         // Object.Equals method.
  591.         //
  592.         // This method uses the Array.IndexOf method to perform the
  593.         // search.
  594.         //
  595.         public int IndexOf(T item, int index)
  596.         {
  597.             if (index > _size)
  598.                 ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_Index);
  599.             return Array.IndexOf(_items, item, index, _size - index);
  600.         }
  601.        
  602.         // Returns the index of the first occurrence of a given value in a range of
  603.         // this list. The list is searched forwards, starting at index
  604.         // index and upto count number of elements. The
  605.         // elements of the list are compared to the given value using the
  606.         // Object.Equals method.
  607.         //
  608.         // This method uses the Array.IndexOf method to perform the
  609.         // search.
  610.         //
  611.         public int IndexOf(T item, int index, int count)
  612.         {
  613.             if (index > _size)
  614.                 ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_Index);
  615.            
  616.             if (count < 0 || index > _size - count)
  617.                 ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.count, ExceptionResource.ArgumentOutOfRange_Count);
  618.            
  619.             return Array.IndexOf(_items, item, index, count);
  620.         }
  621.        
  622.         // Inserts an element into this list at a given index. The size of the list
  623.         // is increased by one. If required, the capacity of the list is doubled
  624.         // before inserting the new element.
  625.         //
  626.         public void Insert(int index, T item)
  627.         {
  628.             // Note that insertions at the end are legal.
  629.             if ((uint)index > (uint)_size) {
  630.                 ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_ListInsert);
  631.             }
  632.             if (_size == _items.Length)
  633.                 EnsureCapacity(_size + 1);
  634.             if (index < _size) {
  635.                 Array.Copy(_items, index, _items, index + 1, _size - index);
  636.             }
  637.             _items[index] = item;
  638.             _size++;
  639.             _version++;
  640.         }
  641.        
  642.         void System.Collections.IList.Insert(int index, object item)
  643.         {
  644.             VerifyValueType(item);
  645.             Insert(index, (T)item);
  646.         }
  647.        
  648.         // Inserts the elements of the given collection at a given index. If
  649.         // required, the capacity of the list is increased to twice the previous
  650.         // capacity or the new size, whichever is larger. Ranges may be added
  651.         // to the end of the list by setting index to the List's size.
  652.         //
  653.         public void InsertRange(int index, IEnumerable<T> collection)
  654.         {
  655.             if (collection == null) {
  656.                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.collection);
  657.             }
  658.            
  659.             if ((uint)index > (uint)_size) {
  660.                 ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_Index);
  661.             }
  662.            
  663.             ICollection<T> c = collection as ICollection<T>;
  664.             if (c != null) {
  665.                 // if collection is ICollection<T>
  666.                 int count = c.Count;
  667.                 if (count > 0) {
  668.                     EnsureCapacity(_size + count);
  669.                     if (index < _size) {
  670.                         Array.Copy(_items, index, _items, index + count, _size - index);
  671.                     }
  672.                    
  673.                     // If we're inserting a List into itself, we want to be able to deal with that.
  674.                     if (this == c) {
  675.                         // Copy first part of _items to insert location
  676.                         Array.Copy(_items, 0, _items, index, index);
  677.                         // Copy last part of _items back to inserted location
  678.                         Array.Copy(_items, index + count, _items, index * 2, _size - index);
  679.                     }
  680.                     else {
  681.                         T[] itemsToInsert = new T[count];
  682.                         c.CopyTo(itemsToInsert, 0);
  683.                         itemsToInsert.CopyTo(_items, index);
  684.                     }
  685.                     _size += count;
  686.                 }
  687.             }
  688.             else {
  689.                 using (IEnumerator<T> en = collection.GetEnumerator()) {
  690.                     while (en.MoveNext()) {
  691.                         Insert(index++, en.Current);
  692.                     }
  693.                 }
  694.             }
  695.             _version++;
  696.         }
  697.        
  698.         // Returns the index of the last occurrence of a given value in a range of
  699.         // this list. The list is searched backwards, starting at the end
  700.         // and ending at the first element in the list. The elements of the list
  701.         // are compared to the given value using the Object.Equals method.
  702.         //
  703.         // This method uses the Array.LastIndexOf method to perform the
  704.         // search.
  705.         //
  706.         public int LastIndexOf(T item)
  707.         {
  708.             return LastIndexOf(item, _size - 1, _size);
  709.         }
  710.        
  711.         // Returns the index of the last occurrence of a given value in a range of
  712.         // this list. The list is searched backwards, starting at index
  713.         // index and ending at the first element in the list. The
  714.         // elements of the list are compared to the given value using the
  715.         // Object.Equals method.
  716.         //
  717.         // This method uses the Array.LastIndexOf method to perform the
  718.         // search.
  719.         //
  720.         public int LastIndexOf(T item, int index)
  721.         {
  722.             if (index >= _size)
  723.                 ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_Index);
  724.             return LastIndexOf(item, index, index + 1);
  725.         }
  726.        
  727.         // Returns the index of the last occurrence of a given value in a range of
  728.         // this list. The list is searched backwards, starting at index
  729.         // index and upto count elements. The elements of
  730.         // the list are compared to the given value using the Object.Equals
  731.         // method.
  732.         //
  733.         // This method uses the Array.LastIndexOf method to perform the
  734.         // search.
  735.         //
  736.         public int LastIndexOf(T item, int index, int count)
  737.         {
  738.             if (_size == 0) {
  739.                 return -1;
  740.             }
  741.            
  742.             if (index < 0 || count < 0) {
  743.                 ThrowHelper.ThrowArgumentOutOfRangeException((index < 0 ? ExceptionArgument.index : ExceptionArgument.count), ExceptionResource.ArgumentOutOfRange_NeedNonNegNum);
  744.             }
  745.            
  746.             if (index >= _size || count > index + 1) {
  747.                 ThrowHelper.ThrowArgumentOutOfRangeException((index >= _size ? ExceptionArgument.index : ExceptionArgument.count), ExceptionResource.ArgumentOutOfRange_BiggerThanCollection);
  748.             }
  749.            
  750.             return Array.LastIndexOf(_items, item, index, count);
  751.         }
  752.        
  753.         // Removes the element at the given index. The size of the list is
  754.         // decreased by one.
  755.         //
  756.         public bool Remove(T item)
  757.         {
  758.             int index = IndexOf(item);
  759.             if (index >= 0) {
  760.                 RemoveAt(index);
  761.                 return true;
  762.             }
  763.            
  764.             return false;
  765.         }
  766.        
  767.         void System.Collections.IList.Remove(object item)
  768.         {
  769.             if (IsCompatibleObject(item)) {
  770.                 Remove((T)item);
  771.             }
  772.         }
  773.        
  774.         // This method removes all items which matches the predicate.
  775.         // The complexity is O(n).
  776.         public int RemoveAll(Predicate<T> match)
  777.         {
  778.             if (match == null) {
  779.                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.match);
  780.             }
  781.            
  782.             int freeIndex = 0;
  783.             // the first free slot in items array
  784.             // Find the first item which needs to be removed.
  785.             while (freeIndex < _size && !match(_items[freeIndex]))
  786.                 freeIndex++;
  787.             if (freeIndex >= _size)
  788.                 return 0;
  789.            
  790.             int current = freeIndex + 1;
  791.             while (current < _size) {
  792.                 // Find the first item which needs to be kept.
  793.                 while (current < _size && match(_items[current]))
  794.                     current++;
  795.                
  796.                 if (current < _size) {
  797.                     // copy item to the free slot.
  798.                     _items[freeIndex++] = _items[current++];
  799.                 }
  800.             }
  801.            
  802.             Array.Clear(_items, freeIndex, _size - freeIndex);
  803.             int result = _size - freeIndex;
  804.             _size = freeIndex;
  805.             _version++;
  806.             return result;
  807.         }
  808.        
  809.         // Removes the element at the given index. The size of the list is
  810.         // decreased by one.
  811.         //
  812.         public void RemoveAt(int index)
  813.         {
  814.             if ((uint)index >= (uint)_size) {
  815.                 ThrowHelper.ThrowArgumentOutOfRangeException();
  816.             }
  817.             _size--;
  818.             if (index < _size) {
  819.                 Array.Copy(_items, index + 1, _items, index, _size - index);
  820.             }
  821.             _items[_size] = default(T);
  822.             _version++;
  823.         }
  824.        
  825.         // Removes a range of elements from this list.
  826.         //
  827.         public void RemoveRange(int index, int count)
  828.         {
  829.             if (index < 0 || count < 0) {
  830.                 ThrowHelper.ThrowArgumentOutOfRangeException((index < 0 ? ExceptionArgument.index : ExceptionArgument.count), ExceptionResource.ArgumentOutOfRange_NeedNonNegNum);
  831.             }
  832.            
  833.             if (_size - index < count)
  834.                 ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidOffLen);
  835.            
  836.             if (count > 0) {
  837.                 int i = _size;
  838.                 _size -= count;
  839.                 if (index < _size) {
  840.                     Array.Copy(_items, index + count, _items, index, _size - index);
  841.                 }
  842.                 Array.Clear(_items, _size, count);
  843.                 _version++;
  844.             }
  845.         }
  846.        
  847.         // Reverses the elements in this list.
  848.         public void Reverse()
  849.         {
  850.             Reverse(0, Count);
  851.         }
  852.        
  853.         // Reverses the elements in a range of this list. Following a call to this
  854.         // method, an element in the range given by index and count
  855.         // which was previously located at index i will now be located at
  856.         // index index + (index + count - i - 1).
  857.         //
  858.         // This method uses the Array.Reverse method to reverse the
  859.         // elements.
  860.         //
  861.         public void Reverse(int index, int count)
  862.         {
  863.             if (index < 0 || count < 0) {
  864.                 ThrowHelper.ThrowArgumentOutOfRangeException((index < 0 ? ExceptionArgument.index : ExceptionArgument.count), ExceptionResource.ArgumentOutOfRange_NeedNonNegNum);
  865.             }
  866.            
  867.             if (_size - index < count)
  868.                 ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidOffLen);
  869.             Array.Reverse(_items, index, count);
  870.             _version++;
  871.         }
  872.        
  873.         // Sorts the elements in this list. Uses the default comparer and
  874.         // Array.Sort.
  875.         public void Sort()
  876.         {
  877.             Sort(0, Count, null);
  878.         }
  879.        
  880.         // Sorts the elements in this list. Uses Array.Sort with the
  881.         // provided comparer.
  882.         public void Sort(IComparer<T> comparer)
  883.         {
  884.             Sort(0, Count, comparer);
  885.         }
  886.        
  887.         // Sorts the elements in a section of this list. The sort compares the
  888.         // elements to each other using the given IComparer interface. If
  889.         // comparer is null, the elements are compared to each other using
  890.         // the IComparable interface, which in that case must be implemented by all
  891.         // elements of the list.
  892.         //
  893.         // This method uses the Array.Sort method to sort the elements.
  894.         //
  895.         public void Sort(int index, int count, IComparer<T> comparer)
  896.         {
  897.             if (index < 0 || count < 0) {
  898.                 ThrowHelper.ThrowArgumentOutOfRangeException((index < 0 ? ExceptionArgument.index : ExceptionArgument.count), ExceptionResource.ArgumentOutOfRange_NeedNonNegNum);
  899.             }
  900.            
  901.             if (_size - index < count)
  902.                 ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidOffLen);
  903.            
  904.             Array.Sort<T>(_items, index, count, comparer);
  905.             _version++;
  906.         }
  907.        
  908.         public void Sort(Comparison<T> comparison)
  909.         {
  910.             if (comparison == null) {
  911.                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.match);
  912.             }
  913.            
  914.             if (_size > 0) {
  915.                 IComparer<T> comparer = new Array.FunctorComparer<T>(comparison);
  916.                 Array.Sort(_items, 0, _size, comparer);
  917.             }
  918.         }
  919.        
  920.         // ToArray returns a new Object array containing the contents of the List.
  921.         // This requires copying the List, which is an O(n) operation.
  922.         public T[] ToArray()
  923.         {
  924.             T[] array = new T[_size];
  925.             Array.Copy(_items, 0, array, 0, _size);
  926.             return array;
  927.         }
  928.        
  929.         // Sets the capacity of this list to the size of the list. This method can
  930.         // be used to minimize a list's memory overhead once it is known that no
  931.         // new elements will be added to the list. To completely clear a list and
  932.         // release all memory referenced by the list, execute the following
  933.         // statements:
  934.         //
  935.         // list.Clear();
  936.         // list.TrimExcess();
  937.         //
  938.         public void TrimExcess()
  939.         {
  940.             int threshold = (int)(((double)_items.Length) * 0.9);
  941.             if (_size < threshold) {
  942.                 Capacity = _size;
  943.             }
  944.         }
  945.        
  946.         public bool TrueForAll(Predicate<T> match)
  947.         {
  948.             if (match == null) {
  949.                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.match);
  950.             }
  951.            
  952.             for (int i = 0; i < _size; i++) {
  953.                 if (!match(_items[i])) {
  954.                     return false;
  955.                 }
  956.             }
  957.             return true;
  958.         }
  959.        
  960.         [Serializable()]
  961.         public struct Enumerator : IEnumerator<T>, System.Collections.IEnumerator
  962.         {
  963.             private List<T> list;
  964.             private int index;
  965.             private int version;
  966.             private T current;
  967.            
  968.             internal Enumerator(List<T> list)
  969.             {
  970.                 this.list = list;
  971.                 index = 0;
  972.                 version = list._version;
  973.                 current = default(T);
  974.             }
  975.            
  976.             public void Dispose()
  977.             {
  978.             }
  979.            
  980.             public bool MoveNext()
  981.             {
  982.                 if (version != list._version) {
  983.                     ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumFailedVersion);
  984.                 }
  985.                
  986.                 if ((uint)index < (uint)list._size) {
  987.                     current = list._items[index];
  988.                     index++;
  989.                     return true;
  990.                 }
  991.                 index = list._size + 1;
  992.                 current = default(T);
  993.                 return false;
  994.             }
  995.            
  996.             public T Current {
  997.                 get { return current; }
  998.             }
  999.            
  1000.             object System.Collections.IEnumerator.Current {
  1001.                 get {
  1002.                     if (index == 0 || index == list._size + 1) {
  1003.                         ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumOpCantHappen);
  1004.                     }
  1005.                     return Current;
  1006.                 }
  1007.             }
  1008.            
  1009.             void System.Collections.IEnumerator.Reset()
  1010.             {
  1011.                 if (version != list._version) {
  1012.                     ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumFailedVersion);
  1013.                 }
  1014.                
  1015.                 index = 0;
  1016.                 current = default(T);
  1017.             }
  1018.         }
  1019.     }
  1020. }

Developer Fusion