2 // System.Collections.Generic.List
5 // Ben Maurer (bmaurer@ximian.com)
6 // Martin Baulig (martin@ximian.com)
7 // Carlos Alberto Cortez (calberto.cortez@gmail.com)
8 // David Waite (mass@akuma.org)
9 // Marek Safar (marek.safar@gmail.com)
11 // Copyright (C) 2004-2005 Novell, Inc (http://www.novell.com)
12 // Copyright (C) 2005 David Waite
13 // Copyright (C) 2011,2012 Xamarin, Inc (http://www.xamarin.com)
15 // Permission is hereby granted, free of charge, to any person obtaining
16 // a copy of this software and associated documentation files (the
17 // "Software"), to deal in the Software without restriction, including
18 // without limitation the rights to use, copy, modify, merge, publish,
19 // distribute, sublicense, and/or sell copies of the Software, and to
20 // permit persons to whom the Software is furnished to do so, subject to
21 // the following conditions:
23 // The above copyright notice and this permission notice shall be
24 // included in all copies or substantial portions of the Software.
26 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
27 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
28 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
29 // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
30 // LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
31 // OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
32 // WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35 using System.Collections.ObjectModel;
36 using System.Runtime.InteropServices;
37 using System.Diagnostics;
38 using System.Runtime.CompilerServices;
40 namespace System.Collections.Generic {
42 [DebuggerDisplay ("Count={Count}")]
43 [DebuggerTypeProxy (typeof (CollectionDebuggerView<>))]
44 public class List<T> : IList<T>, IList
53 const int DefaultCapacity = 4;
57 _items = EmptyArray<T>.Value;
60 public List (IEnumerable <T> collection)
62 if (collection == null)
63 throw new ArgumentNullException ("collection");
65 // initialize to needed size (if determinable)
66 ICollection <T> c = collection as ICollection <T>;
68 _items = EmptyArray<T>.Value;;
69 AddEnumerable (collection);
72 _items = new T [_size];
77 public List (int capacity)
80 throw new ArgumentOutOfRangeException ("capacity");
81 _items = new T [capacity];
84 internal List (T [] data, int size)
90 public void Add (T item)
92 // If we check to see if we need to grow before trying to grow
93 // we can speed things up by 25%
94 if (_size == _items.Length)
96 _items [_size++] = item;
100 void GrowIfNeeded (int newCount)
102 int minimumSize = _size + newCount;
103 if (minimumSize > _items.Length)
104 Capacity = Math.Max (Math.Max (Capacity * 2, DefaultCapacity), minimumSize);
107 void CheckRange (int idx, int count)
110 throw new ArgumentOutOfRangeException ("index");
113 throw new ArgumentOutOfRangeException ("count");
115 if ((uint) idx + (uint) count > (uint) _size)
116 throw new ArgumentException ("index and count exceed length of list");
119 void CheckRangeOutOfRange (int idx, int count)
122 throw new ArgumentOutOfRangeException ("index");
125 throw new ArgumentOutOfRangeException ("count");
127 if ((uint) idx + (uint) count > (uint) _size)
128 throw new ArgumentOutOfRangeException ("index and count exceed length of list");
131 void AddCollection (ICollection <T> collection)
133 int collectionCount = collection.Count;
134 if (collectionCount == 0)
137 GrowIfNeeded (collectionCount);
138 collection.CopyTo (_items, _size);
139 _size += collectionCount;
142 void AddEnumerable (IEnumerable <T> enumerable)
144 foreach (T t in enumerable)
150 public void AddRange (IEnumerable <T> collection)
152 if (collection == null)
153 throw new ArgumentNullException ("collection");
155 ICollection <T> c = collection as ICollection <T>;
159 AddEnumerable (collection);
163 public ReadOnlyCollection <T> AsReadOnly ()
165 return new ReadOnlyCollection <T> (this);
168 public int BinarySearch (T item)
170 return Array.BinarySearch <T> (_items, 0, _size, item);
173 public int BinarySearch (T item, IComparer <T> comparer)
175 return Array.BinarySearch <T> (_items, 0, _size, item, comparer);
178 public int BinarySearch (int index, int count, T item, IComparer <T> comparer)
180 CheckRange (index, count);
181 return Array.BinarySearch <T> (_items, index, count, item, comparer);
186 Array.Clear (_items, 0, _items.Length);
191 public bool Contains (T item)
193 return Array.IndexOf<T>(_items, item, 0, _size) != -1;
196 public List <TOutput> ConvertAll <TOutput> (Converter <T, TOutput> converter)
198 if (converter == null)
199 throw new ArgumentNullException ("converter");
200 List <TOutput> u = new List <TOutput> (_size);
201 for (int i = 0; i < _size; i++)
202 u._items[i] = converter(_items[i]);
208 public void CopyTo (T [] array)
210 Array.Copy (_items, 0, array, 0, _size);
213 public void CopyTo (T [] array, int arrayIndex)
215 Array.Copy (_items, 0, array, arrayIndex, _size);
218 public void CopyTo (int index, T [] array, int arrayIndex, int count)
220 CheckRange (index, count);
221 Array.Copy (_items, index, array, arrayIndex, count);
224 public bool Exists (Predicate <T> match)
228 for (int i = 0; i < _size; i++) {
229 var item = _items [i];
237 public T Find (Predicate <T> match)
241 for (int i = 0; i < _size; i++) {
242 var item = _items [i];
250 static void CheckMatch (Predicate <T> match)
253 throw new ArgumentNullException ("match");
256 public List <T> FindAll (Predicate <T> match)
259 if (this._size <= 0x10000) // <= 8 * 1024 * 8 (8k in stack)
260 return this.FindAllStackBits (match);
262 return this.FindAllList (match);
265 private List <T> FindAllStackBits (Predicate <T> match)
269 uint *bits = stackalloc uint [(this._size / 32) + 1];
272 uint bitmask = 0x80000000;
274 for (int i = 0; i < this._size; i++)
276 if (match (this._items [i]))
278 (*ptr) = (*ptr) | bitmask;
282 bitmask = bitmask >> 1;
286 bitmask = 0x80000000;
290 T [] results = new T [found];
291 bitmask = 0x80000000;
294 for (int i = 0; i < this._size && j < found; i++)
296 if (((*ptr) & bitmask) == bitmask)
297 results [j++] = this._items [i];
299 bitmask = bitmask >> 1;
303 bitmask = 0x80000000;
307 return new List <T> (results, found);
311 private List <T> FindAllList (Predicate <T> match)
313 List <T> results = new List <T> ();
314 for (int i = 0; i < this._size; i++)
315 if (match (this._items [i]))
316 results.Add (this._items [i]);
321 public int FindIndex (Predicate <T> match)
324 return Array.GetIndex (_items, 0, _size, match);
327 public int FindIndex (int startIndex, Predicate <T> match)
330 CheckStartIndex (startIndex);
331 return Array.GetIndex (_items, startIndex, _size - startIndex, match);
333 public int FindIndex (int startIndex, int count, Predicate <T> match)
336 CheckRangeOutOfRange (startIndex, count);
337 return Array.GetIndex (_items, startIndex, count, match);
340 public T FindLast (Predicate <T> match)
343 int i = Array.GetLastIndex (_items, 0, _size, match);
344 return i == -1 ? default (T) : this [i];
347 public int FindLastIndex (Predicate <T> match)
350 return Array.GetLastIndex (_items, 0, _size, match);
353 public int FindLastIndex (int startIndex, Predicate <T> match)
356 CheckStartIndex (startIndex);
357 return Array.GetLastIndex (_items, 0, startIndex + 1, match);
360 public int FindLastIndex (int startIndex, int count, Predicate <T> match)
363 CheckStartIndex (startIndex);
366 throw new ArgumentOutOfRangeException ("count");
368 if (startIndex - count + 1 < 0)
369 throw new ArgumentOutOfRangeException ("count must refer to a location within the collection");
371 return Array.GetLastIndex (_items, startIndex - count + 1, count, match);
374 public void ForEach (Action <T> action)
377 throw new ArgumentNullException ("action");
378 for(int i=0; i < _size; i++)
382 public Enumerator GetEnumerator ()
384 return new Enumerator (this);
387 public List <T> GetRange (int index, int count)
389 CheckRange (index, count);
390 T [] tmpArray = new T [count];
391 Array.Copy (_items, index, tmpArray, 0, count);
392 return new List <T> (tmpArray, count);
395 public int IndexOf (T item)
397 return Array.IndexOf<T> (_items, item, 0, _size);
400 public int IndexOf (T item, int index)
403 return Array.IndexOf<T> (_items, item, index, _size - index);
406 public int IndexOf (T item, int index, int count)
409 throw new ArgumentOutOfRangeException ("index");
412 throw new ArgumentOutOfRangeException ("count");
414 if ((uint) index + (uint) count > (uint) _size)
415 throw new ArgumentOutOfRangeException ("index and count exceed length of list");
417 return Array.IndexOf<T> (_items, item, index, count);
420 void Shift (int start, int delta)
426 Array.Copy (_items, start, _items, start + delta, _size - start);
431 Array.Clear (_items, _size, -delta);
434 void CheckIndex (int index)
436 if (index < 0 || (uint) index > (uint) _size)
437 throw new ArgumentOutOfRangeException ("index");
440 void CheckStartIndex (int index)
442 if (index < 0 || (uint) index > (uint) _size)
443 throw new ArgumentOutOfRangeException ("startIndex");
446 public void Insert (int index, T item)
449 if (_size == _items.Length)
452 _items[index] = item;
456 public void InsertRange (int index, IEnumerable <T> collection)
458 if (collection == null)
459 throw new ArgumentNullException ("collection");
462 if (collection == this) {
463 T[] buffer = new T[_size];
465 GrowIfNeeded (_size);
466 Shift (index, buffer.Length);
467 Array.Copy (buffer, 0, _items, index, buffer.Length);
469 ICollection <T> c = collection as ICollection <T>;
471 InsertCollection (index, c);
473 InsertEnumeration (index, collection);
478 void InsertCollection (int index, ICollection <T> collection)
480 int collectionCount = collection.Count;
481 GrowIfNeeded (collectionCount);
483 Shift (index, collectionCount);
484 collection.CopyTo (_items, index);
487 void InsertEnumeration (int index, IEnumerable <T> enumerable)
489 foreach (T t in enumerable)
493 public int LastIndexOf (T item)
497 return Array.LastIndexOf<T> (_items, item, _size - 1, _size);
500 public int LastIndexOf (T item, int index)
503 return Array.LastIndexOf<T> (_items, item, index, index + 1);
506 public int LastIndexOf (T item, int index, int count)
509 throw new ArgumentOutOfRangeException ("index", index, "index is negative");
512 throw new ArgumentOutOfRangeException ("count", count, "count is negative");
514 if (index - count + 1 < 0)
515 throw new ArgumentOutOfRangeException ("cound", count, "count is too large");
517 return Array.LastIndexOf<T> (_items, item, index, count);
520 public bool Remove (T item)
522 int loc = IndexOf (item);
529 public int RemoveAll (Predicate <T> match)
535 // Find the first item to remove
536 for (i = 0; i < _size; i++)
537 if (match(_items[i]))
545 // Remove any additional items
546 for (j = i + 1; j < _size; j++)
548 if (!match(_items[j]))
549 _items[i++] = _items[j];
552 Array.Clear (_items, i, j - i);
558 public void RemoveAt (int index)
560 if (index < 0 || (uint)index >= (uint)_size)
561 throw new ArgumentOutOfRangeException("index");
563 Array.Clear (_items, _size, 1);
567 public void RemoveRange (int index, int count)
569 CheckRange (index, count);
571 Shift (index, -count);
572 Array.Clear (_items, _size, count);
577 public void Reverse ()
579 Array.Reverse (_items, 0, _size);
582 public void Reverse (int index, int count)
584 CheckRange (index, count);
585 Array.Reverse (_items, index, count);
591 Array.Sort<T> (_items, 0, _size);
594 public void Sort (IComparer <T> comparer)
596 Array.Sort<T> (_items, 0, _size, comparer);
600 public void Sort (Comparison <T> comparison)
602 if (comparison == null)
603 throw new ArgumentNullException ("comparison");
605 Array.SortImpl<T> (_items, _size, comparison);
609 public void Sort (int index, int count, IComparer <T> comparer)
611 CheckRange (index, count);
612 Array.Sort<T> (_items, index, count, comparer);
616 public T [] ToArray ()
618 T [] t = new T [_size];
619 Array.Copy (_items, t, _size);
624 public void TrimExcess ()
629 public bool TrueForAll (Predicate <T> match)
633 for (int i = 0; i < _size; i++)
634 if (!match(_items[i]))
640 public int Capacity {
642 return _items.Length;
645 if ((uint) value < (uint) _size)
646 throw new ArgumentOutOfRangeException ();
648 Array.Resize (ref _items, value);
653 get { return _size; }
656 public T this [int index] {
657 [MethodImpl ((MethodImplOptions)256)]
659 if ((uint) index >= (uint) _size)
660 throw new ArgumentOutOfRangeException ("index");
661 return Array.UnsafeLoad (_items, index);
664 [MethodImpl ((MethodImplOptions)256)]
666 if ((uint) index >= (uint) _size)
667 throw new ArgumentOutOfRangeException ("index");
668 _items [index] = value;
673 #region Interface implementations.
674 IEnumerator <T> IEnumerable <T>.GetEnumerator ()
676 return GetEnumerator ();
679 void ICollection.CopyTo (Array array, int arrayIndex)
682 throw new ArgumentNullException ("array");
683 if (array.Rank > 1 || array.GetLowerBound (0) != 0)
684 throw new ArgumentException ("Array must be zero based and single dimentional", "array");
685 Array.Copy (_items, 0, array, arrayIndex, _size);
688 IEnumerator IEnumerable.GetEnumerator ()
690 return GetEnumerator ();
693 int IList.Add (object item)
698 } catch (NullReferenceException) {
699 } catch (InvalidCastException) {
701 throw new ArgumentException ("item");
704 bool IList.Contains (object item)
707 return Contains ((T) item);
708 } catch (NullReferenceException) {
709 } catch (InvalidCastException) {
714 int IList.IndexOf (object item)
717 return IndexOf ((T) item);
718 } catch (NullReferenceException) {
719 } catch (InvalidCastException) {
724 void IList.Insert (int index, object item)
726 // We need to check this first because, even if the
727 // item is null or not the correct type, we need to
728 // return an ArgumentOutOfRange exception if the
729 // index is out of range
732 Insert (index, (T) item);
734 } catch (NullReferenceException) {
735 } catch (InvalidCastException) {
737 throw new ArgumentException ("item");
740 void IList.Remove (object item)
745 } catch (NullReferenceException) {
746 } catch (InvalidCastException) {
748 // Swallow the exception--if we can't cast to the
749 // correct type then we've already "succeeded" in
750 // removing the item from the List.
753 bool ICollection <T>.IsReadOnly {
754 get { return false; }
756 bool ICollection.IsSynchronized {
757 get { return false; }
760 object ICollection.SyncRoot {
763 bool IList.IsFixedSize {
764 get { return false; }
767 bool IList.IsReadOnly {
768 get { return false; }
771 object IList.this [int index] {
772 get { return this [index]; }
775 this [index] = (T) value;
777 } catch (NullReferenceException) {
778 // can happen when 'value' is null and T is a valuetype
779 } catch (InvalidCastException) {
781 throw new ArgumentException ("value");
787 public struct Enumerator : IEnumerator <T>, IDisposable {
794 internal Enumerator (List <T> l)
801 public void Dispose ()
805 public bool MoveNext ()
809 if ((uint)next < (uint)list._size && ver == list._version) {
810 current = list._items [next++];
814 if (ver != l._version)
815 throw new InvalidOperationException ("Collection was modified; enumeration operation may not execute.");
822 get { return current; }
825 void IEnumerator.Reset ()
827 if (ver != l._version)
828 throw new InvalidOperationException ("Collection was modified; enumeration operation may not execute.");
831 current = default (T);
834 object IEnumerator.Current {
836 if (ver != l._version)
837 throw new InvalidOperationException ("Collection was modified; enumeration operation may not execute.");
840 throw new InvalidOperationException ();