src/mscorlib/shared/System/Collections/Generic/List.cs

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