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)
10 // Copyright (C) 2004-2005 Novell, Inc (http://www.novell.com)
11 // Copyright (C) 2005 David Waite
13 // Permission is hereby granted, free of charge, to any person obtaining
14 // a copy of this software and associated documentation files (the
15 // "Software"), to deal in the Software without restriction, including
16 // without limitation the rights to use, copy, modify, merge, publish,
17 // distribute, sublicense, and/or sell copies of the Software, and to
18 // permit persons to whom the Software is furnished to do so, subject to
19 // the following conditions:
21 // The above copyright notice and this permission notice shall be
22 // included in all copies or substantial portions of the Software.
24 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27 // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28 // LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29 // OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30 // WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35 using System.Collections.ObjectModel;
36 using System.Runtime.InteropServices;
38 namespace System.Collections.Generic {
40 public class List <T> : IList <T>, IList, ICollection {
45 static readonly T [] EmptyArray = new T [0];
46 const int DefaultCapacity = 4;
53 public List (IEnumerable <T> collection)
55 CheckCollection (collection);
57 // initialize to needed size (if determinable)
58 ICollection <T> c = collection as ICollection <T>;
62 AddEnumerable (collection);
66 _items = new T [c.Count];
71 public List (int capacity)
74 throw new ArgumentOutOfRangeException ("capacity");
75 _items = new T [capacity];
78 internal List (T [] data, int size)
83 public void Add (T item)
85 // If we check to see if we need to grow before trying to grow
86 // we can speed things up by 25%
87 if (_size == _items.Length)
89 _items [_size ++] = item;
93 void GrowIfNeeded (int newCount)
95 int minimumSize = _size + newCount;
96 if (minimumSize > _items.Length)
97 Capacity = Math.Max (Math.Max (Capacity * 2, DefaultCapacity), minimumSize);
100 void CheckRange (int idx, int count)
103 throw new ArgumentOutOfRangeException ("index");
106 throw new ArgumentOutOfRangeException ("count");
108 if ((uint) idx + (uint) count > (uint) _size)
109 throw new ArgumentException ("index and count exceed length of list");
112 void AddCollection (ICollection <T> collection)
114 int collectionCount = collection.Count;
115 if (collectionCount == 0)
118 GrowIfNeeded (collectionCount);
119 collection.CopyTo (_items, _size);
120 _size += collectionCount;
123 void AddEnumerable (IEnumerable <T> enumerable)
125 foreach (T t in enumerable)
131 public void AddRange (IEnumerable <T> collection)
133 CheckCollection (collection);
135 ICollection <T> c = collection as ICollection <T>;
139 AddEnumerable (collection);
143 public ReadOnlyCollection <T> AsReadOnly ()
145 return new ReadOnlyCollection <T> (this);
148 public int BinarySearch (T item)
150 return Array.BinarySearch <T> (_items, 0, _size, item);
153 public int BinarySearch (T item, IComparer <T> comparer)
155 return Array.BinarySearch <T> (_items, 0, _size, item, comparer);
158 public int BinarySearch (int index, int count, T item, IComparer <T> comparer)
160 CheckRange (index, count);
161 return Array.BinarySearch <T> (_items, index, count, item, comparer);
166 Array.Clear (_items, 0, _items.Length);
171 public bool Contains (T item)
173 return Array.IndexOf<T>(_items, item, 0, _size) != -1;
176 public List <TOutput> ConvertAll <TOutput> (Converter <T, TOutput> converter)
178 if (converter == null)
179 throw new ArgumentNullException ("converter");
180 List <TOutput> u = new List <TOutput> (_size);
181 for (int i = 0; i < _size; i++)
182 u._items[i] = converter(_items[i]);
188 public void CopyTo (T [] array)
190 Array.Copy (_items, 0, array, 0, _size);
193 public void CopyTo (T [] array, int arrayIndex)
195 Array.Copy (_items, 0, array, arrayIndex, _size);
198 public void CopyTo (int index, T [] array, int arrayIndex, int count)
200 CheckRange (index, count);
201 Array.Copy (_items, index, array, arrayIndex, count);
204 public bool Exists (Predicate <T> match)
207 return GetIndex(0, _size, match) != -1;
210 public T Find (Predicate <T> match)
213 int i = GetIndex(0, _size, match);
214 return (i != -1) ? _items [i] : default (T);
217 static void CheckMatch (Predicate <T> match)
220 throw new ArgumentNullException ("match");
223 public List <T> FindAll (Predicate <T> match)
226 if (this._size <= 0x10000) // <= 8 * 1024 * 8 (8k in stack)
227 return this.FindAllStackBits (match);
229 return this.FindAllList (match);
232 private List <T> FindAllStackBits (Predicate <T> match)
236 uint *bits = stackalloc uint [(this._size / 32) + 1];
239 uint bitmask = 0x80000000;
241 for (int i = 0; i < this._size; i++)
243 if (match (this._items [i]))
245 (*ptr) = (*ptr) | bitmask;
249 bitmask = bitmask >> 1;
253 bitmask = 0x80000000;
257 T [] results = new T [found];
258 bitmask = 0x80000000;
261 for (int i = 0; i < this._size && j < found; i++)
263 if (((*ptr) & bitmask) == bitmask)
264 results [j++] = this._items [i];
266 bitmask = bitmask >> 1;
270 bitmask = 0x80000000;
274 return new List <T> (results, found);
278 private List <T> FindAllList (Predicate <T> match)
280 List <T> results = new List <T> ();
281 for (int i = 0; i < this._size; i++)
282 if (match (this._items [i]))
283 results.Add (this._items [i]);
288 public int FindIndex (Predicate <T> match)
291 return GetIndex (0, _size, match);
294 public int FindIndex (int startIndex, Predicate <T> match)
297 CheckIndex (startIndex);
298 return GetIndex (startIndex, _size - startIndex, match);
300 public int FindIndex (int startIndex, int count, Predicate <T> match)
303 CheckRange (startIndex, count);
304 return GetIndex (startIndex, count, match);
306 int GetIndex (int startIndex, int count, Predicate <T> match)
308 int end = startIndex + count;
309 for (int i = startIndex; i < end; i ++)
310 if (match (_items [i]))
316 public T FindLast (Predicate <T> match)
319 int i = GetLastIndex (0, _size, match);
320 return i == -1 ? default (T) : this [i];
323 public int FindLastIndex (Predicate <T> match)
326 return GetLastIndex (0, _size, match);
329 public int FindLastIndex (int startIndex, Predicate <T> match)
332 CheckIndex (startIndex);
333 return GetLastIndex (0, startIndex + 1, match);
336 public int FindLastIndex (int startIndex, int count, Predicate <T> match)
339 int start = startIndex - count + 1;
340 CheckRange (start, count);
341 return GetLastIndex (start, count, match);
344 int GetLastIndex (int startIndex, int count, Predicate <T> match)
346 // unlike FindLastIndex, takes regular params for search range
347 for (int i = startIndex + count; i != startIndex;)
348 if (match (_items [--i]))
353 public void ForEach (Action <T> action)
356 throw new ArgumentNullException ("action");
357 for(int i=0; i < _size; i++)
361 public Enumerator GetEnumerator ()
363 return new Enumerator (this);
366 public List <T> GetRange (int index, int count)
368 CheckRange (index, count);
369 T [] tmpArray = new T [count];
370 Array.Copy (_items, index, tmpArray, 0, count);
371 return new List <T> (tmpArray, count);
374 public int IndexOf (T item)
376 return Array.IndexOf<T> (_items, item, 0, _size);
379 public int IndexOf (T item, int index)
382 return Array.IndexOf<T> (_items, item, index, _size - index);
385 public int IndexOf (T item, int index, int count)
388 throw new ArgumentOutOfRangeException ("index");
391 throw new ArgumentOutOfRangeException ("count");
393 if ((uint) index + (uint) count > (uint) _size)
394 throw new ArgumentOutOfRangeException ("index and count exceed length of list");
396 return Array.IndexOf<T> (_items, item, index, count);
399 void Shift (int start, int delta)
405 Array.Copy (_items, start, _items, start + delta, _size - start);
410 void CheckIndex (int index)
412 if (index < 0 || (uint) index > (uint) _size)
413 throw new ArgumentOutOfRangeException ("index");
416 public void Insert (int index, T item)
419 if (_size == _items.Length)
422 _items[index] = item;
426 void CheckCollection (IEnumerable <T> collection)
428 if (collection == null)
429 throw new ArgumentNullException ("collection");
432 public void InsertRange (int index, IEnumerable <T> collection)
434 CheckCollection (collection);
436 if (collection == this) {
437 T[] buffer = new T[_size];
439 GrowIfNeeded (_size);
440 Shift (index, buffer.Length);
441 Array.Copy (buffer, 0, _items, index, buffer.Length);
443 ICollection <T> c = collection as ICollection <T>;
445 InsertCollection (index, c);
447 InsertEnumeration (index, collection);
452 void InsertCollection (int index, ICollection <T> collection)
454 int collectionCount = collection.Count;
455 GrowIfNeeded (collectionCount);
457 Shift (index, collectionCount);
458 collection.CopyTo (_items, index);
460 void InsertEnumeration (int index, IEnumerable <T> enumerable)
462 foreach (T t in enumerable)
466 public int LastIndexOf (T item)
468 return Array.LastIndexOf<T> (_items, item, _size - 1, _size);
471 public int LastIndexOf (T item, int index)
474 return Array.LastIndexOf<T> (_items, item, index, index + 1);
477 public int LastIndexOf (T item, int index, int count)
480 throw new ArgumentOutOfRangeException ("index", index, "index is negative");
483 throw new ArgumentOutOfRangeException ("count", count, "count is negative");
485 if (index - count + 1 < 0)
486 throw new ArgumentOutOfRangeException ("cound", count, "count is too large");
488 return Array.LastIndexOf<T> (_items, item, index, count);
491 public bool Remove (T item)
493 int loc = IndexOf (item);
500 public int RemoveAll (Predicate <T> match)
506 // Find the first item to remove
507 for (i = 0; i < _size; i++)
508 if (match(_items[i]))
516 // Remove any additional items
517 for (j = i + 1; j < _size; j++)
519 if (!match(_items[j]))
520 _items[i++] = _items[j];
527 public void RemoveAt (int index)
529 if (index < 0 || (uint)index >= (uint)_size)
530 throw new ArgumentOutOfRangeException("index");
532 Array.Clear (_items, _size, 1);
536 public void RemoveRange (int index, int count)
538 CheckRange (index, count);
540 Shift (index, -count);
541 Array.Clear (_items, _size, count);
546 public void Reverse ()
548 Array.Reverse (_items, 0, _size);
551 public void Reverse (int index, int count)
553 CheckRange (index, count);
554 Array.Reverse (_items, index, count);
560 Array.Sort<T> (_items, 0, _size, Comparer <T>.Default);
563 public void Sort (IComparer <T> comparer)
565 Array.Sort<T> (_items, 0, _size, comparer);
569 public void Sort (Comparison <T> comparison)
571 Array.Sort<T> (_items, _size, comparison);
575 public void Sort (int index, int count, IComparer <T> comparer)
577 CheckRange (index, count);
578 Array.Sort<T> (_items, index, count, comparer);
582 public T [] ToArray ()
584 T [] t = new T [_size];
585 Array.Copy (_items, t, _size);
590 public void TrimExcess ()
595 public bool TrueForAll (Predicate <T> match)
599 for (int i = 0; i < _size; i++)
600 if (!match(_items[i]))
606 public int Capacity {
608 return _items.Length;
611 if ((uint) value < (uint) _size)
612 throw new ArgumentOutOfRangeException ();
614 Array.Resize (ref _items, value);
619 get { return _size; }
622 public T this [int index] {
624 if ((uint) index >= (uint) _size)
625 throw new ArgumentOutOfRangeException ("index");
626 return _items [index];
630 if ((uint) index == (uint) _size)
631 throw new ArgumentOutOfRangeException ("index");
632 _items [index] = value;
636 #region Interface implementations.
637 IEnumerator <T> IEnumerable <T>.GetEnumerator ()
639 return GetEnumerator ();
642 void ICollection.CopyTo (Array array, int arrayIndex)
644 Array.Copy (_items, 0, array, arrayIndex, _size);
647 IEnumerator IEnumerable.GetEnumerator ()
649 return GetEnumerator ();
652 int IList.Add (object item)
656 } catch (InvalidCastException) {
657 throw new ArgumentException("item");
662 bool IList.Contains (object item)
665 return Contains ((T) item);
666 } catch (InvalidCastException) {
671 int IList.IndexOf (object item)
674 return IndexOf((T) item);
675 } catch (InvalidCastException) {
680 void IList.Insert (int index, object item)
682 // We need to check this first because, even if the
683 // item is null or not the correct type, we need to
684 // return an ArgumentOutOfRange exception if the
685 // index is out of range
688 Insert (index, (T) item);
689 } catch (InvalidCastException) {
690 throw new ArgumentException("item");
694 void IList.Remove (object item)
698 } catch (InvalidCastException) {
699 // Swallow the exception--if we
700 // can't cast to the correct type
701 // then we've already "succeeded"
702 // in removing the item from the
707 bool ICollection <T>.IsReadOnly {
708 get { return false; }
710 bool ICollection.IsSynchronized {
711 get { return false; }
714 object ICollection.SyncRoot {
717 bool IList.IsFixedSize {
718 get { return false; }
721 bool IList.IsReadOnly {
722 get { return false; }
725 object IList.this [int index] {
726 get { return this [index]; }
727 set { this [index] = (T) value; }
732 public struct Enumerator : IEnumerator <T>, IDisposable {
733 const int NOT_STARTED = -2;
735 // this MUST be -1, because we depend on it in move next.
736 // we just decr the size, so, 0 - 1 == FINISHED
737 const int FINISHED = -1;
743 internal Enumerator (List <T> l)
750 // for some fucked up reason, MSFT added a useless dispose to this class
751 // It means that in foreach, we must still do a try/finally. Broken, very
753 public void Dispose ()
758 public bool MoveNext ()
760 if (ver != l._version)
761 throw new InvalidOperationException ("Collection was modified;"
762 + "enumeration operation may not execute.");
764 if (idx == NOT_STARTED)
767 return idx != FINISHED && -- idx != FINISHED;
773 throw new InvalidOperationException ();
775 return l._items [l._size - 1 - idx];
779 void IEnumerator.Reset ()
781 if (ver != l._version)
782 throw new InvalidOperationException ("Collection was modified;"
783 + "enumeration operation may not execute.");
788 object IEnumerator.Current {
789 get { return Current; }