mcs/class/referencesource/mscorlib/system/collections/generic/list.cs

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