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 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;
39 namespace System.Collections.Generic {
41 [DebuggerDisplay ("Count={Count}")]
42 [DebuggerTypeProxy (typeof (CollectionDebuggerView<>))]
43 public class List<T> : IList<T>, IList
52 static readonly T [] EmptyArray = new T [0];
53 const int DefaultCapacity = 4;
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>;
69 AddEnumerable (collection);
72 _items = new T [Math.Max (_size, DefaultCapacity)];
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 AddCollection (ICollection <T> collection)
121 int collectionCount = collection.Count;
122 if (collectionCount == 0)
125 GrowIfNeeded (collectionCount);
126 collection.CopyTo (_items, _size);
127 _size += collectionCount;
130 void AddEnumerable (IEnumerable <T> enumerable)
132 foreach (T t in enumerable)
138 public void AddRange (IEnumerable <T> collection)
140 if (collection == null)
141 throw new ArgumentNullException ("collection");
143 ICollection <T> c = collection as ICollection <T>;
147 AddEnumerable (collection);
151 public ReadOnlyCollection <T> AsReadOnly ()
153 return new ReadOnlyCollection <T> (this);
156 public int BinarySearch (T item)
158 return Array.BinarySearch <T> (_items, 0, _size, item);
161 public int BinarySearch (T item, IComparer <T> comparer)
163 return Array.BinarySearch <T> (_items, 0, _size, item, comparer);
166 public int BinarySearch (int index, int count, T item, IComparer <T> comparer)
168 CheckRange (index, count);
169 return Array.BinarySearch <T> (_items, index, count, item, comparer);
174 Array.Clear (_items, 0, _items.Length);
179 public bool Contains (T item)
181 return Array.IndexOf<T>(_items, item, 0, _size) != -1;
184 public List <TOutput> ConvertAll <TOutput> (Converter <T, TOutput> converter)
186 if (converter == null)
187 throw new ArgumentNullException ("converter");
188 List <TOutput> u = new List <TOutput> (_size);
189 for (int i = 0; i < _size; i++)
190 u._items[i] = converter(_items[i]);
196 public void CopyTo (T [] array)
198 Array.Copy (_items, 0, array, 0, _size);
201 public void CopyTo (T [] array, int arrayIndex)
203 Array.Copy (_items, 0, array, arrayIndex, _size);
206 public void CopyTo (int index, T [] array, int arrayIndex, int count)
208 CheckRange (index, count);
209 Array.Copy (_items, index, array, arrayIndex, count);
212 public bool Exists (Predicate <T> match)
215 return GetIndex(0, _size, match) != -1;
218 public T Find (Predicate <T> match)
221 int i = GetIndex(0, _size, match);
222 return (i != -1) ? _items [i] : default (T);
225 static void CheckMatch (Predicate <T> match)
228 throw new ArgumentNullException ("match");
231 public List <T> FindAll (Predicate <T> match)
234 if (this._size <= 0x10000) // <= 8 * 1024 * 8 (8k in stack)
235 return this.FindAllStackBits (match);
237 return this.FindAllList (match);
240 private List <T> FindAllStackBits (Predicate <T> match)
244 uint *bits = stackalloc uint [(this._size / 32) + 1];
247 uint bitmask = 0x80000000;
249 for (int i = 0; i < this._size; i++)
251 if (match (this._items [i]))
253 (*ptr) = (*ptr) | bitmask;
257 bitmask = bitmask >> 1;
261 bitmask = 0x80000000;
265 T [] results = new T [found];
266 bitmask = 0x80000000;
269 for (int i = 0; i < this._size && j < found; i++)
271 if (((*ptr) & bitmask) == bitmask)
272 results [j++] = this._items [i];
274 bitmask = bitmask >> 1;
278 bitmask = 0x80000000;
282 return new List <T> (results, found);
286 private List <T> FindAllList (Predicate <T> match)
288 List <T> results = new List <T> ();
289 for (int i = 0; i < this._size; i++)
290 if (match (this._items [i]))
291 results.Add (this._items [i]);
296 public int FindIndex (Predicate <T> match)
299 return GetIndex (0, _size, match);
302 public int FindIndex (int startIndex, Predicate <T> match)
305 CheckIndex (startIndex);
306 return GetIndex (startIndex, _size - startIndex, match);
308 public int FindIndex (int startIndex, int count, Predicate <T> match)
311 CheckRange (startIndex, count);
312 return GetIndex (startIndex, count, match);
314 int GetIndex (int startIndex, int count, Predicate <T> match)
316 int end = startIndex + count;
317 for (int i = startIndex; i < end; i ++)
318 if (match (_items [i]))
324 public T FindLast (Predicate <T> match)
327 int i = GetLastIndex (0, _size, match);
328 return i == -1 ? default (T) : this [i];
331 public int FindLastIndex (Predicate <T> match)
334 return GetLastIndex (0, _size, match);
337 public int FindLastIndex (int startIndex, Predicate <T> match)
340 CheckIndex (startIndex);
341 return GetLastIndex (0, startIndex + 1, match);
344 public int FindLastIndex (int startIndex, int count, Predicate <T> match)
347 int start = startIndex - count + 1;
348 CheckRange (start, count);
349 return GetLastIndex (start, count, match);
352 int GetLastIndex (int startIndex, int count, Predicate <T> match)
354 // unlike FindLastIndex, takes regular params for search range
355 for (int i = startIndex + count; i != startIndex;)
356 if (match (_items [--i]))
361 public void ForEach (Action <T> action)
364 throw new ArgumentNullException ("action");
365 for(int i=0; i < _size; i++)
369 public Enumerator GetEnumerator ()
371 return new Enumerator (this);
374 public List <T> GetRange (int index, int count)
376 CheckRange (index, count);
377 T [] tmpArray = new T [count];
378 Array.Copy (_items, index, tmpArray, 0, count);
379 return new List <T> (tmpArray, count);
382 public int IndexOf (T item)
384 return Array.IndexOf<T> (_items, item, 0, _size);
387 public int IndexOf (T item, int index)
390 return Array.IndexOf<T> (_items, item, index, _size - index);
393 public int IndexOf (T item, int index, int count)
396 throw new ArgumentOutOfRangeException ("index");
399 throw new ArgumentOutOfRangeException ("count");
401 if ((uint) index + (uint) count > (uint) _size)
402 throw new ArgumentOutOfRangeException ("index and count exceed length of list");
404 return Array.IndexOf<T> (_items, item, index, count);
407 void Shift (int start, int delta)
413 Array.Copy (_items, start, _items, start + delta, _size - start);
418 Array.Clear (_items, _size, -delta);
421 void CheckIndex (int index)
423 if (index < 0 || (uint) index > (uint) _size)
424 throw new ArgumentOutOfRangeException ("index");
427 public void Insert (int index, T item)
430 if (_size == _items.Length)
433 _items[index] = item;
437 public void InsertRange (int index, IEnumerable <T> collection)
439 if (collection == null)
440 throw new ArgumentNullException ("collection");
443 if (collection == this) {
444 T[] buffer = new T[_size];
446 GrowIfNeeded (_size);
447 Shift (index, buffer.Length);
448 Array.Copy (buffer, 0, _items, index, buffer.Length);
450 ICollection <T> c = collection as ICollection <T>;
452 InsertCollection (index, c);
454 InsertEnumeration (index, collection);
459 void InsertCollection (int index, ICollection <T> collection)
461 int collectionCount = collection.Count;
462 GrowIfNeeded (collectionCount);
464 Shift (index, collectionCount);
465 collection.CopyTo (_items, index);
468 void InsertEnumeration (int index, IEnumerable <T> enumerable)
470 foreach (T t in enumerable)
474 public int LastIndexOf (T item)
478 return Array.LastIndexOf<T> (_items, item, _size - 1, _size);
481 public int LastIndexOf (T item, int index)
484 return Array.LastIndexOf<T> (_items, item, index, index + 1);
487 public int LastIndexOf (T item, int index, int count)
490 throw new ArgumentOutOfRangeException ("index", index, "index is negative");
493 throw new ArgumentOutOfRangeException ("count", count, "count is negative");
495 if (index - count + 1 < 0)
496 throw new ArgumentOutOfRangeException ("cound", count, "count is too large");
498 return Array.LastIndexOf<T> (_items, item, index, count);
501 public bool Remove (T item)
503 int loc = IndexOf (item);
510 public int RemoveAll (Predicate <T> match)
516 // Find the first item to remove
517 for (i = 0; i < _size; i++)
518 if (match(_items[i]))
526 // Remove any additional items
527 for (j = i + 1; j < _size; j++)
529 if (!match(_items[j]))
530 _items[i++] = _items[j];
533 Array.Clear (_items, i, j - i);
539 public void RemoveAt (int index)
541 if (index < 0 || (uint)index >= (uint)_size)
542 throw new ArgumentOutOfRangeException("index");
544 Array.Clear (_items, _size, 1);
548 public void RemoveRange (int index, int count)
550 CheckRange (index, count);
552 Shift (index, -count);
553 Array.Clear (_items, _size, count);
558 public void Reverse ()
560 Array.Reverse (_items, 0, _size);
563 public void Reverse (int index, int count)
565 CheckRange (index, count);
566 Array.Reverse (_items, index, count);
572 Array.Sort<T> (_items, 0, _size);
575 public void Sort (IComparer <T> comparer)
577 Array.Sort<T> (_items, 0, _size, comparer);
581 public void Sort (Comparison <T> comparison)
583 if (comparison == null)
584 throw new ArgumentNullException ("comparison");
586 Array.SortImpl<T> (_items, _size, comparison);
590 public void Sort (int index, int count, IComparer <T> comparer)
592 CheckRange (index, count);
593 Array.Sort<T> (_items, index, count, comparer);
597 public T [] ToArray ()
599 T [] t = new T [_size];
600 Array.Copy (_items, t, _size);
605 public void TrimExcess ()
610 public bool TrueForAll (Predicate <T> match)
614 for (int i = 0; i < _size; i++)
615 if (!match(_items[i]))
621 public int Capacity {
623 return _items.Length;
626 if ((uint) value < (uint) _size)
627 throw new ArgumentOutOfRangeException ();
629 Array.Resize (ref _items, value);
634 get { return _size; }
637 public T this [int index] {
639 if ((uint) index >= (uint) _size)
640 throw new ArgumentOutOfRangeException ("index");
641 return _items [index];
645 if ((uint) index == (uint) _size)
646 throw new ArgumentOutOfRangeException ("index");
647 _items [index] = value;
652 #region Interface implementations.
653 IEnumerator <T> IEnumerable <T>.GetEnumerator ()
655 return GetEnumerator ();
658 void ICollection.CopyTo (Array array, int arrayIndex)
661 throw new ArgumentNullException ("array");
662 if (array.Rank > 1 || array.GetLowerBound (0) != 0)
663 throw new ArgumentException ("Array must be zero based and single dimentional", "array");
664 Array.Copy (_items, 0, array, arrayIndex, _size);
667 IEnumerator IEnumerable.GetEnumerator ()
669 return GetEnumerator ();
672 int IList.Add (object item)
677 } catch (NullReferenceException) {
678 } catch (InvalidCastException) {
680 throw new ArgumentException ("item");
683 bool IList.Contains (object item)
686 return Contains ((T) item);
687 } catch (NullReferenceException) {
688 } catch (InvalidCastException) {
693 int IList.IndexOf (object item)
696 return IndexOf ((T) item);
697 } catch (NullReferenceException) {
698 } catch (InvalidCastException) {
703 void IList.Insert (int index, object item)
705 // We need to check this first because, even if the
706 // item is null or not the correct type, we need to
707 // return an ArgumentOutOfRange exception if the
708 // index is out of range
711 Insert (index, (T) item);
713 } catch (NullReferenceException) {
714 } catch (InvalidCastException) {
716 throw new ArgumentException ("item");
719 void IList.Remove (object item)
724 } catch (NullReferenceException) {
725 } catch (InvalidCastException) {
727 // Swallow the exception--if we can't cast to the
728 // correct type then we've already "succeeded" in
729 // removing the item from the List.
732 bool ICollection <T>.IsReadOnly {
733 get { return false; }
735 bool ICollection.IsSynchronized {
736 get { return false; }
739 object ICollection.SyncRoot {
742 bool IList.IsFixedSize {
743 get { return false; }
746 bool IList.IsReadOnly {
747 get { return false; }
750 object IList.this [int index] {
751 get { return this [index]; }
754 this [index] = (T) value;
756 } catch (NullReferenceException) {
757 // can happen when 'value' is null and T is a valuetype
758 } catch (InvalidCastException) {
760 throw new ArgumentException ("value");
766 public struct Enumerator : IEnumerator <T>, IDisposable {
773 internal Enumerator (List <T> l)
780 public void Dispose ()
786 if (ver != l._version)
787 throw new InvalidOperationException (
788 "Collection was modified; enumeration operation may not execute.");
791 public bool MoveNext ()
798 if (next < l._size) {
799 current = l._items [next++];
808 get { return current; }
811 void IEnumerator.Reset ()
817 object IEnumerator.Current {
821 throw new InvalidOperationException ();