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