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 GrowIfNeeded (collectionCount);
116 collection.CopyTo (_items, _size);
117 _size += collectionCount;
119 void AddEnumerable (IEnumerable <T> enumerable)
121 foreach (T t in enumerable)
127 public void AddRange (IEnumerable <T> collection)
129 CheckCollection (collection);
131 ICollection <T> c = collection as ICollection <T>;
135 AddEnumerable (collection);
139 public ReadOnlyCollection <T> AsReadOnly ()
141 return new ReadOnlyCollection <T> (this);
144 public int BinarySearch (T item)
146 return Array.BinarySearch <T> (_items, 0, _size, item);
149 public int BinarySearch (T item, IComparer <T> comparer)
151 return Array.BinarySearch <T> (_items, 0, _size, item, comparer);
154 public int BinarySearch (int index, int count, T item, IComparer <T> comparer)
156 CheckRange (index, count);
157 return Array.BinarySearch <T> (_items, index, count, item, comparer);
162 Array.Clear (_items, 0, _items.Length);
167 public bool Contains (T item)
169 return Array.IndexOf<T>(_items, item, 0, _size) != -1;
172 public List <TOutput> ConvertAll <TOutput> (Converter <T, TOutput> converter)
174 if (converter == null)
175 throw new ArgumentNullException ("converter");
176 List <TOutput> u = new List <TOutput> (_size);
177 for (int i = 0; i < _size; i++)
178 u._items[i] = converter(_items[i]);
184 public void CopyTo (T [] array)
186 Array.Copy (_items, 0, array, 0, _size);
189 public void CopyTo (T [] array, int arrayIndex)
191 Array.Copy (_items, 0, array, arrayIndex, _size);
194 public void CopyTo (int index, T [] array, int arrayIndex, int count)
196 CheckRange (index, count);
197 Array.Copy (_items, index, array, arrayIndex, count);
200 public bool Exists (Predicate <T> match)
203 return GetIndex(0, _size, match) != -1;
206 public T Find (Predicate <T> match)
209 int i = GetIndex(0, _size, match);
210 return (i != -1) ? _items [i] : default (T);
212 void CheckMatch (Predicate <T> match)
215 throw new ArgumentNullException ("match");
218 public List <T> FindAll (Predicate <T> match)
220 this.CheckMatch (match);
221 if (this._size <= 0x10000) // <= 8 * 1024 * 8 (8k in stack)
222 return this.FindAllStackBits (match);
224 return this.FindAllList (match);
227 private List <T> FindAllStackBits (Predicate <T> match)
231 uint *bits = stackalloc uint [(this._size / 32) + 1];
234 uint bitmask = 0x80000000;
236 for (int i = 0; i < this._size; i++)
238 if (match (this._items [i]))
240 (*ptr) = (*ptr) | bitmask;
244 bitmask = bitmask >> 1;
248 bitmask = 0x80000000;
252 T [] results = new T [found];
253 bitmask = 0x80000000;
256 for (int i = 0; i < this._size && j < found; i++)
258 if (((*ptr) & bitmask) == bitmask)
259 results [j++] = this._items [i];
261 bitmask = bitmask >> 1;
265 bitmask = 0x80000000;
269 return new List <T> (results, found);
273 private List <T> FindAllList (Predicate <T> match)
275 List <T> results = new List <T> ();
276 for (int i = 0; i < this._size; i++)
277 if (match (this._items [i]))
278 results.Add (this._items [i]);
283 public int FindIndex (Predicate <T> match)
286 return GetIndex (0, _size, match);
289 public int FindIndex (int startIndex, Predicate <T> match)
292 CheckIndex (startIndex);
293 return GetIndex (startIndex, _size - startIndex, match);
295 public int FindIndex (int startIndex, int count, Predicate <T> match)
298 CheckRange (startIndex, count);
299 return GetIndex (startIndex, count, match);
301 int GetIndex (int startIndex, int count, Predicate <T> match)
303 int end = startIndex + count;
304 for (int i = startIndex; i < end; i ++)
305 if (match (_items [i]))
311 public T FindLast (Predicate <T> match)
314 int i = GetLastIndex (0, _size, match);
315 return i == -1 ? default (T) : this [i];
318 public int FindLastIndex (Predicate <T> match)
321 return GetLastIndex (0, _size, match);
324 public int FindLastIndex (int startIndex, Predicate <T> match)
327 CheckIndex (startIndex);
328 return GetLastIndex (0, startIndex + 1, match);
331 public int FindLastIndex (int startIndex, int count, Predicate <T> match)
334 int start = startIndex - count + 1;
335 CheckRange (start, count);
336 return GetLastIndex (start, count, match);
339 int GetLastIndex (int startIndex, int count, Predicate <T> match)
341 // unlike FindLastIndex, takes regular params for search range
342 for (int i = startIndex + count; i != startIndex;)
343 if (match (_items [--i]))
348 public void ForEach (Action <T> action)
351 throw new ArgumentNullException ("action");
352 for(int i=0; i < _size; i++)
356 public Enumerator GetEnumerator ()
358 return new Enumerator (this);
361 public List <T> GetRange (int index, int count)
363 CheckRange (index, count);
364 T [] tmpArray = new T [count];
365 Array.Copy (_items, index, tmpArray, 0, count);
366 return new List <T> (tmpArray, count);
369 public int IndexOf (T item)
371 return Array.IndexOf<T> (_items, item, 0, _size);
374 public int IndexOf (T item, int index)
377 return Array.IndexOf<T> (_items, item, index, _size - index);
380 public int IndexOf (T item, int index, int count)
383 throw new ArgumentOutOfRangeException ("index");
386 throw new ArgumentOutOfRangeException ("count");
388 if ((uint) index + (uint) count > (uint) _size)
389 throw new ArgumentOutOfRangeException ("index and count exceed length of list");
391 return Array.IndexOf<T> (_items, item, index, count);
394 void Shift (int start, int delta)
400 Array.Copy (_items, start, _items, start + delta, _size - start);
405 void CheckIndex (int index)
407 if (index < 0 || (uint) index > (uint) _size)
408 throw new ArgumentOutOfRangeException ("index");
411 public void Insert (int index, T item)
414 if (_size == _items.Length)
417 _items[index] = item;
421 void CheckCollection (IEnumerable <T> collection)
423 if (collection == null)
424 throw new ArgumentNullException ("collection");
427 public void InsertRange (int index, IEnumerable <T> collection)
429 CheckCollection (collection);
431 if (collection == this) {
432 T[] buffer = new T[_size];
434 GrowIfNeeded (_size);
435 Shift (index, buffer.Length);
436 Array.Copy (buffer, 0, _items, index, buffer.Length);
438 ICollection <T> c = collection as ICollection <T>;
440 InsertCollection (index, c);
442 InsertEnumeration (index, collection);
447 void InsertCollection (int index, ICollection <T> collection)
449 int collectionCount = collection.Count;
450 GrowIfNeeded (collectionCount);
452 Shift (index, collectionCount);
453 collection.CopyTo (_items, index);
455 void InsertEnumeration (int index, IEnumerable <T> enumerable)
457 foreach (T t in enumerable)
461 public int LastIndexOf (T item)
463 return Array.LastIndexOf<T> (_items, item, _size - 1, _size);
466 public int LastIndexOf (T item, int index)
469 return Array.LastIndexOf<T> (_items, item, index, index + 1);
472 public int LastIndexOf (T item, int index, int count)
475 throw new ArgumentOutOfRangeException ("index", index, "index is negative");
478 throw new ArgumentOutOfRangeException ("count", count, "count is negative");
480 if (index - count + 1 < 0)
481 throw new ArgumentOutOfRangeException ("cound", count, "count is too large");
483 return Array.LastIndexOf<T> (_items, item, index, count);
486 public bool Remove (T item)
488 int loc = IndexOf (item);
495 public int RemoveAll (Predicate <T> match)
501 // Find the first item to remove
502 for (i = 0; i < _size; i++)
503 if (match(_items[i]))
511 // Remove any additional items
512 for (j = i + 1; j < _size; j++)
514 if (!match(_items[j]))
515 _items[i++] = _items[j];
522 public void RemoveAt (int index)
524 if (index < 0 || (uint)index >= (uint)_size)
525 throw new ArgumentOutOfRangeException("index");
527 Array.Clear (_items, _size, 1);
531 public void RemoveRange (int index, int count)
533 CheckRange (index, count);
535 Shift (index, -count);
536 Array.Clear (_items, _size, count);
541 public void Reverse ()
543 Array.Reverse (_items, 0, _size);
546 public void Reverse (int index, int count)
548 CheckRange (index, count);
549 Array.Reverse (_items, index, count);
555 Array.Sort<T> (_items, 0, _size, Comparer <T>.Default);
558 public void Sort (IComparer <T> comparer)
560 Array.Sort<T> (_items, 0, _size, comparer);
564 public void Sort (Comparison <T> comparison)
566 Array.Sort<T> (_items, _size, comparison);
570 public void Sort (int index, int count, IComparer <T> comparer)
572 CheckRange (index, count);
573 Array.Sort<T> (_items, index, count, comparer);
577 public T [] ToArray ()
579 T [] t = new T [_size];
580 Array.Copy (_items, t, _size);
585 public void TrimExcess ()
590 public bool TrueForAll (Predicate <T> match)
594 for (int i = 0; i < _size; i++)
595 if (!match(_items[i]))
601 public int Capacity {
603 return _items.Length;
606 if ((uint) value < (uint) _size)
607 throw new ArgumentOutOfRangeException ();
609 Array.Resize (ref _items, value);
614 get { return _size; }
617 public T this [int index] {
619 if ((uint) index >= (uint) _size)
620 throw new ArgumentOutOfRangeException ("index");
621 return _items [index];
625 if ((uint) index == (uint) _size)
626 throw new ArgumentOutOfRangeException ("index");
627 _items [index] = value;
631 #region Interface implementations.
632 IEnumerator <T> IEnumerable <T>.GetEnumerator ()
634 return GetEnumerator ();
637 void ICollection.CopyTo (Array array, int arrayIndex)
639 Array.Copy (_items, 0, array, arrayIndex, _size);
642 IEnumerator IEnumerable.GetEnumerator ()
644 return GetEnumerator ();
647 int IList.Add (object item)
651 } catch (InvalidCastException) {
652 throw new ArgumentException("item");
657 bool IList.Contains (object item)
660 return Contains ((T) item);
661 } catch (InvalidCastException) {
666 int IList.IndexOf (object item)
669 return IndexOf((T) item);
670 } catch (InvalidCastException) {
675 void IList.Insert (int index, object item)
677 // We need to check this first because, even if the
678 // item is null or not the correct type, we need to
679 // return an ArgumentOutOfRange exception if the
680 // index is out of range
683 Insert (index, (T) item);
684 } catch (InvalidCastException) {
685 throw new ArgumentException("item");
689 void IList.Remove (object item)
693 } catch (InvalidCastException) {
694 // Swallow the exception--if we
695 // can't cast to the correct type
696 // then we've already "succeeded"
697 // in removing the item from the
702 bool ICollection <T>.IsReadOnly {
703 get { return false; }
705 bool ICollection.IsSynchronized {
706 get { return false; }
709 object ICollection.SyncRoot {
712 bool IList.IsFixedSize {
713 get { return false; }
716 bool IList.IsReadOnly {
717 get { return false; }
720 object IList.this [int index] {
721 get { return this [index]; }
722 set { this [index] = (T) value; }
727 public struct Enumerator : IEnumerator <T>, IDisposable {
728 const int NOT_STARTED = -2;
730 // this MUST be -1, because we depend on it in move next.
731 // we just decr the size, so, 0 - 1 == FINISHED
732 const int FINISHED = -1;
738 internal Enumerator (List <T> l)
745 // for some fucked up reason, MSFT added a useless dispose to this class
746 // It means that in foreach, we must still do a try/finally. Broken, very
748 public void Dispose ()
753 public bool MoveNext ()
755 if (ver != l._version)
756 throw new InvalidOperationException ("Collection was modified;"
757 + "enumeration operation may not execute.");
759 if (idx == NOT_STARTED)
762 return idx != FINISHED && -- idx != FINISHED;
768 throw new InvalidOperationException ();
770 return l._items [l._size - 1 - idx];
774 void IEnumerator.Reset ()
776 if (ver != l._version)
777 throw new InvalidOperationException ("Collection was modified;"
778 + "enumeration operation may not execute.");
783 object IEnumerator.Current {
784 get { return Current; }