?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
2010-04-07 Jb Evain <jbevain@novell.com>
[mcs.git] / class / corlib / System.Collections.Generic / List.cs
blob6b766dcd2d50bb15cbb1ee3f8621eb0cc12bd747
1 //
2 // System.Collections.Generic.List
3 //
4 // Authors:
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 //
10 // Copyright (C) 2004-2005 Novell, Inc (http://www.novell.com)
11 // Copyright (C) 2005 David Waite
12 //
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:
20 //
21 // The above copyright notice and this permission notice shall be
22 // included in all copies or substantial portions of the Software.
23 //
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.
31 //
32
33 using System.Collections.ObjectModel;
34 using System.Runtime.InteropServices;
35 using System.Diagnostics;
36
37 namespace System.Collections.Generic {
38 [Serializable]
39 [DebuggerDisplay ("Count={Count}")]
40 [DebuggerTypeProxy (typeof (CollectionDebuggerView<>))]
41 public class List <T> : IList <T>, IList, ICollection {
42 T [] _items;
43 int _size;
44 int _version;
45
46 static readonly T [] EmptyArray = new T [0];
47 const int DefaultCapacity = 4;
48
49 public List ()
50 {
51 _items = EmptyArray;
52 }
53
54 public List (IEnumerable <T> collection)
55 {
56 CheckCollection (collection);
57
58 // initialize to needed size (if determinable)
59 ICollection <T> c = collection as ICollection <T>;
60 if (c == null)
61 {
62 _items = EmptyArray;
63 AddEnumerable (collection);
64 }
65 else
66 {
67 _items = new T [c.Count];
68 AddCollection (c);
69 }
70 }
71
72 public List (int capacity)
73 {
74 if (capacity < 0)
75 throw new ArgumentOutOfRangeException ("capacity");
76 _items = new T [capacity];
77 }
78
79 internal List (T [] data, int size)
80 {
81 _items = data;
82 _size = size;
83 }
84 public void Add (T item)
85 {
86 // If we check to see if we need to grow before trying to grow
87 // we can speed things up by 25%
88 if (_size == _items.Length)
89 GrowIfNeeded (1);
90 _items [_size ++] = item;
91 _version++;
92 }
93
94 void GrowIfNeeded (int newCount)
95 {
96 int minimumSize = _size + newCount;
97 if (minimumSize > _items.Length)
98 Capacity = Math.Max (Math.Max (Capacity * 2, DefaultCapacity), minimumSize);
99 }
100
101 void CheckRange (int idx, int count)
102 {
103 if (idx < 0)
104 throw new ArgumentOutOfRangeException ("index");
105
106 if (count < 0)
107 throw new ArgumentOutOfRangeException ("count");
108
109 if ((uint) idx + (uint) count > (uint) _size)
110 throw new ArgumentException ("index and count exceed length of list");
111 }
112
113 void AddCollection (ICollection <T> collection)
114 {
115 int collectionCount = collection.Count;
116 if (collectionCount == 0)
117 return;
118
119 GrowIfNeeded (collectionCount);
120 collection.CopyTo (_items, _size);
121 _size += collectionCount;
122 }
123
124 void AddEnumerable (IEnumerable <T> enumerable)
125 {
126 foreach (T t in enumerable)
127 {
128 Add (t);
129 }
130 }
131
132 public void AddRange (IEnumerable <T> collection)
133 {
134 CheckCollection (collection);
135
136 ICollection <T> c = collection as ICollection <T>;
137 if (c != null)
138 AddCollection (c);
139 else
140 AddEnumerable (collection);
141 _version++;
142 }
143
144 public ReadOnlyCollection <T> AsReadOnly ()
145 {
146 return new ReadOnlyCollection <T> (this);
147 }
148
149 public int BinarySearch (T item)
150 {
151 return Array.BinarySearch <T> (_items, 0, _size, item);
152 }
153
154 public int BinarySearch (T item, IComparer <T> comparer)
155 {
156 return Array.BinarySearch <T> (_items, 0, _size, item, comparer);
157 }
158
159 public int BinarySearch (int index, int count, T item, IComparer <T> comparer)
160 {
161 CheckRange (index, count);
162 return Array.BinarySearch <T> (_items, index, count, item, comparer);
163 }
164
165 public void Clear ()
166 {
167 Array.Clear (_items, 0, _items.Length);
168 _size = 0;
169 _version++;
170 }
171
172 public bool Contains (T item)
173 {
174 return Array.IndexOf<T>(_items, item, 0, _size) != -1;
175 }
176
177 public List <TOutput> ConvertAll <TOutput> (Converter <T, TOutput> converter)
178 {
179 if (converter == null)
180 throw new ArgumentNullException ("converter");
181 List <TOutput> u = new List <TOutput> (_size);
182 for (int i = 0; i < _size; i++)
183 u._items[i] = converter(_items[i]);
184
185 u._size = _size;
186 return u;
187 }
188
189 public void CopyTo (T [] array)
190 {
191 Array.Copy (_items, 0, array, 0, _size);
192 }
193
194 public void CopyTo (T [] array, int arrayIndex)
195 {
196 Array.Copy (_items, 0, array, arrayIndex, _size);
197 }
198
199 public void CopyTo (int index, T [] array, int arrayIndex, int count)
200 {
201 CheckRange (index, count);
202 Array.Copy (_items, index, array, arrayIndex, count);
203 }
204
205 public bool Exists (Predicate <T> match)
206 {
207 CheckMatch(match);
208 return GetIndex(0, _size, match) != -1;
209 }
210
211 public T Find (Predicate <T> match)
212 {
213 CheckMatch(match);
214 int i = GetIndex(0, _size, match);
215 return (i != -1) ? _items [i] : default (T);
216 }
217
218 static void CheckMatch (Predicate <T> match)
219 {
220 if (match == null)
221 throw new ArgumentNullException ("match");
222 }
223
224 public List <T> FindAll (Predicate <T> match)
225 {
226 CheckMatch (match);
227 if (this._size <= 0x10000) // <= 8 * 1024 * 8 (8k in stack)
228 return this.FindAllStackBits (match);
229 else
230 return this.FindAllList (match);
231 }
232
233 private List <T> FindAllStackBits (Predicate <T> match)
234 {
235 unsafe
236 {
237 uint *bits = stackalloc uint [(this._size / 32) + 1];
238 uint *ptr = bits;
239 int found = 0;
240 uint bitmask = 0x80000000;
241
242 for (int i = 0; i < this._size; i++)
243 {
244 if (match (this._items [i]))
245 {
246 (*ptr) = (*ptr) | bitmask;
247 found++;
248 }
249
250 bitmask = bitmask >> 1;
251 if (bitmask == 0)
252 {
253 ptr++;
254 bitmask = 0x80000000;
255 }
256 }
257
258 T [] results = new T [found];
259 bitmask = 0x80000000;
260 ptr = bits;
261 int j = 0;
262 for (int i = 0; i < this._size && j < found; i++)
263 {
264 if (((*ptr) & bitmask) == bitmask)
265 results [j++] = this._items [i];
266
267 bitmask = bitmask >> 1;
268 if (bitmask == 0)
269 {
270 ptr++;
271 bitmask = 0x80000000;
272 }
273 }
274
275 return new List <T> (results, found);
276 }
277 }
278
279 private List <T> FindAllList (Predicate <T> match)
280 {
281 List <T> results = new List <T> ();
282 for (int i = 0; i < this._size; i++)
283 if (match (this._items [i]))
284 results.Add (this._items [i]);
285
286 return results;
287 }
288
289 public int FindIndex (Predicate <T> match)
290 {
291 CheckMatch (match);
292 return GetIndex (0, _size, match);
293 }
294
295 public int FindIndex (int startIndex, Predicate <T> match)
296 {
297 CheckMatch (match);
298 CheckIndex (startIndex);
299 return GetIndex (startIndex, _size - startIndex, match);
300 }
301 public int FindIndex (int startIndex, int count, Predicate <T> match)
302 {
303 CheckMatch (match);
304 CheckRange (startIndex, count);
305 return GetIndex (startIndex, count, match);
306 }
307 int GetIndex (int startIndex, int count, Predicate <T> match)
308 {
309 int end = startIndex + count;
310 for (int i = startIndex; i < end; i ++)
311 if (match (_items [i]))
312 return i;
313
314 return -1;
315 }
316
317 public T FindLast (Predicate <T> match)
318 {
319 CheckMatch (match);
320 int i = GetLastIndex (0, _size, match);
321 return i == -1 ? default (T) : this [i];
322 }
323
324 public int FindLastIndex (Predicate <T> match)
325 {
326 CheckMatch (match);
327 return GetLastIndex (0, _size, match);
328 }
329
330 public int FindLastIndex (int startIndex, Predicate <T> match)
331 {
332 CheckMatch (match);
333 CheckIndex (startIndex);
334 return GetLastIndex (0, startIndex + 1, match);
335 }
336
337 public int FindLastIndex (int startIndex, int count, Predicate <T> match)
338 {
339 CheckMatch (match);
340 int start = startIndex - count + 1;
341 CheckRange (start, count);
342 return GetLastIndex (start, count, match);
343 }
344
345 int GetLastIndex (int startIndex, int count, Predicate <T> match)
346 {
347 // unlike FindLastIndex, takes regular params for search range
348 for (int i = startIndex + count; i != startIndex;)
349 if (match (_items [--i]))
350 return i;
351 return -1;
352 }
353
354 public void ForEach (Action <T> action)
355 {
356 if (action == null)
357 throw new ArgumentNullException ("action");
358 for(int i=0; i < _size; i++)
359 action(_items[i]);
360 }
361
362 public Enumerator GetEnumerator ()
363 {
364 return new Enumerator (this);
365 }
366
367 public List <T> GetRange (int index, int count)
368 {
369 CheckRange (index, count);
370 T [] tmpArray = new T [count];
371 Array.Copy (_items, index, tmpArray, 0, count);
372 return new List <T> (tmpArray, count);
373 }
374
375 public int IndexOf (T item)
376 {
377 return Array.IndexOf<T> (_items, item, 0, _size);
378 }
379
380 public int IndexOf (T item, int index)
381 {
382 CheckIndex (index);
383 return Array.IndexOf<T> (_items, item, index, _size - index);
384 }
385
386 public int IndexOf (T item, int index, int count)
387 {
388 if (index < 0)
389 throw new ArgumentOutOfRangeException ("index");
390
391 if (count < 0)
392 throw new ArgumentOutOfRangeException ("count");
393
394 if ((uint) index + (uint) count > (uint) _size)
395 throw new ArgumentOutOfRangeException ("index and count exceed length of list");
396
397 return Array.IndexOf<T> (_items, item, index, count);
398 }
399
400 void Shift (int start, int delta)
401 {
402 if (delta < 0)
403 start -= delta;
404
405 if (start < _size)
406 Array.Copy (_items, start, _items, start + delta, _size - start);
407
408 _size += delta;
409
410 if (delta < 0)
411 Array.Clear (_items, _size, -delta);
412 }
413
414 void CheckIndex (int index)
415 {
416 if (index < 0 || (uint) index > (uint) _size)
417 throw new ArgumentOutOfRangeException ("index");
418 }
419
420 public void Insert (int index, T item)
421 {
422 CheckIndex (index);
423 if (_size == _items.Length)
424 GrowIfNeeded (1);
425 Shift (index, 1);
426 _items[index] = item;
427 _version++;
428 }
429
430 void CheckCollection (IEnumerable <T> collection)
431 {
432 if (collection == null)
433 throw new ArgumentNullException ("collection");
434 }
435
436 public void InsertRange (int index, IEnumerable <T> collection)
437 {
438 CheckCollection (collection);
439 CheckIndex (index);
440 if (collection == this) {
441 T[] buffer = new T[_size];
442 CopyTo (buffer, 0);
443 GrowIfNeeded (_size);
444 Shift (index, buffer.Length);
445 Array.Copy (buffer, 0, _items, index, buffer.Length);
446 } else {
447 ICollection <T> c = collection as ICollection <T>;
448 if (c != null)
449 InsertCollection (index, c);
450 else
451 InsertEnumeration (index, collection);
452 }
453 _version++;
454 }
455
456 void InsertCollection (int index, ICollection <T> collection)
457 {
458 int collectionCount = collection.Count;
459 GrowIfNeeded (collectionCount);
460
461 Shift (index, collectionCount);
462 collection.CopyTo (_items, index);
463 }
464 void InsertEnumeration (int index, IEnumerable <T> enumerable)
465 {
466 foreach (T t in enumerable)
467 Insert (index++, t);
468 }
469
470 public int LastIndexOf (T item)
471 {
472 return Array.LastIndexOf<T> (_items, item, _size - 1, _size);
473 }
474
475 public int LastIndexOf (T item, int index)
476 {
477 CheckIndex (index);
478 return Array.LastIndexOf<T> (_items, item, index, index + 1);
479 }
480
481 public int LastIndexOf (T item, int index, int count)
482 {
483 if (index < 0)
484 throw new ArgumentOutOfRangeException ("index", index, "index is negative");
485
486 if (count < 0)
487 throw new ArgumentOutOfRangeException ("count", count, "count is negative");
488
489 if (index - count + 1 < 0)
490 throw new ArgumentOutOfRangeException ("cound", count, "count is too large");
491
492 return Array.LastIndexOf<T> (_items, item, index, count);
493 }
494
495 public bool Remove (T item)
496 {
497 int loc = IndexOf (item);
498 if (loc != -1)
499 RemoveAt (loc);
500
501 return loc != -1;
502 }
503
504 public int RemoveAll (Predicate <T> match)
505 {
506 CheckMatch(match);
507 int i = 0;
508 int j = 0;
509
510 // Find the first item to remove
511 for (i = 0; i < _size; i++)
512 if (match(_items[i]))
513 break;
514
515 if (i == _size)
516 return 0;
517
518 _version++;
519
520 // Remove any additional items
521 for (j = i + 1; j < _size; j++)
522 {
523 if (!match(_items[j]))
524 _items[i++] = _items[j];
525 }
526 if (j - i > 0)
527 Array.Clear (_items, i, j - i);
528
529 _size = i;
530 return (j - i);
531 }
532
533 public void RemoveAt (int index)
534 {
535 if (index < 0 || (uint)index >= (uint)_size)
536 throw new ArgumentOutOfRangeException("index");
537 Shift (index, -1);
538 Array.Clear (_items, _size, 1);
539 _version++;
540 }
541
542 public void RemoveRange (int index, int count)
543 {
544 CheckRange (index, count);
545 if (count > 0) {
546 Shift (index, -count);
547 Array.Clear (_items, _size, count);
548 _version++;
549 }
550 }
551
552 public void Reverse ()
553 {
554 Array.Reverse (_items, 0, _size);
555 _version++;
556 }
557 public void Reverse (int index, int count)
558 {
559 CheckRange (index, count);
560 Array.Reverse (_items, index, count);
561 _version++;
562 }
563
564 public void Sort ()
565 {
566 Array.Sort<T> (_items, 0, _size);
567 _version++;
568 }
569 public void Sort (IComparer <T> comparer)
570 {
571 Array.Sort<T> (_items, 0, _size, comparer);
572 _version++;
573 }
574
575 public void Sort (Comparison <T> comparison)
576 {
577 if (comparison == null)
578 throw new ArgumentNullException ("comparison");
579
580 Array.SortImpl<T> (_items, _size, comparison);
581 _version++;
582 }
583
584 public void Sort (int index, int count, IComparer <T> comparer)
585 {
586 CheckRange (index, count);
587 Array.Sort<T> (_items, index, count, comparer);
588 _version++;
589 }
590
591 public T [] ToArray ()
592 {
593 T [] t = new T [_size];
594 Array.Copy (_items, t, _size);
595
596 return t;
597 }
598
599 public void TrimExcess ()
600 {
601 Capacity = _size;
602 }
603
604 public bool TrueForAll (Predicate <T> match)
605 {
606 CheckMatch (match);
607
608 for (int i = 0; i < _size; i++)
609 if (!match(_items[i]))
610 return false;
611
612 return true;
613 }
614
615 public int Capacity {
616 get {
617 return _items.Length;
618 }
619 set {
620 if ((uint) value < (uint) _size)
621 throw new ArgumentOutOfRangeException ();
622
623 Array.Resize (ref _items, value);
624 }
625 }
626
627 public int Count {
628 get { return _size; }
629 }
630
631 public T this [int index] {
632 get {
633 if ((uint) index >= (uint) _size)
634 throw new ArgumentOutOfRangeException ("index");
635 return _items [index];
636 }
637 set {
638 CheckIndex (index);
639 if ((uint) index == (uint) _size)
640 throw new ArgumentOutOfRangeException ("index");
641 _items [index] = value;
642 }
643 }
644
645 #region Interface implementations.
646 IEnumerator <T> IEnumerable <T>.GetEnumerator ()
647 {
648 return GetEnumerator ();
649 }
650
651 void ICollection.CopyTo (Array array, int arrayIndex)
652 {
653 Array.Copy (_items, 0, array, arrayIndex, _size);
654 }
655
656 IEnumerator IEnumerable.GetEnumerator ()
657 {
658 return GetEnumerator ();
659 }
660
661 int IList.Add (object item)
662 {
663 try {
664 Add ((T) item);
665 return _size - 1;
666 } catch (NullReferenceException) {
667 } catch (InvalidCastException) {
668 }
669 throw new ArgumentException ("item");
670 }
671
672 bool IList.Contains (object item)
673 {
674 try {
675 return Contains ((T) item);
676 } catch (NullReferenceException) {
677 } catch (InvalidCastException) {
678 }
679 return false;
680 }
681
682 int IList.IndexOf (object item)
683 {
684 try {
685 return IndexOf ((T) item);
686 } catch (NullReferenceException) {
687 } catch (InvalidCastException) {
688 }
689 return -1;
690 }
691
692 void IList.Insert (int index, object item)
693 {
694 // We need to check this first because, even if the
695 // item is null or not the correct type, we need to
696 // return an ArgumentOutOfRange exception if the
697 // index is out of range
698 CheckIndex (index);
699 try {
700 Insert (index, (T) item);
701 return;
702 } catch (NullReferenceException) {
703 } catch (InvalidCastException) {
704 }
705 throw new ArgumentException ("item");
706 }
707
708 void IList.Remove (object item)
709 {
710 try {
711 Remove ((T) item);
712 return;
713 } catch (NullReferenceException) {
714 } catch (InvalidCastException) {
715 }
716 // Swallow the exception--if we can't cast to the
717 // correct type then we've already "succeeded" in
718 // removing the item from the List.
719 }
720
721 bool ICollection <T>.IsReadOnly {
722 get { return false; }
723 }
724 bool ICollection.IsSynchronized {
725 get { return false; }
726 }
727
728 object ICollection.SyncRoot {
729 get { return this; }
730 }
731 bool IList.IsFixedSize {
732 get { return false; }
733 }
734
735 bool IList.IsReadOnly {
736 get { return false; }
737 }
738
739 object IList.this [int index] {
740 get { return this [index]; }
741 set {
742 try {
743 this [index] = (T) value;
744 return;
745 } catch (NullReferenceException) {
746 // can happen when 'value' is null and T is a valuetype
747 } catch (InvalidCastException) {
748 }
749 throw new ArgumentException ("value");
750 }
751 }
752 #endregion
753
754 [Serializable]
755 public struct Enumerator : IEnumerator <T>, IDisposable {
756 List <T> l;
757 int next;
758 int ver;
759
760 T current;
761
762 internal Enumerator (List <T> l)
763 : this ()
764 {
765 this.l = l;
766 ver = l._version;
767 }
768
769 public void Dispose ()
770 {
771 l = null;
772 }
773
774 void VerifyState ()
775 {
776 if (l == null)
777 throw new ObjectDisposedException (GetType ().FullName);
778 if (ver != l._version)
779 throw new InvalidOperationException (
780 "Collection was modified; enumeration operation may not execute.");
781 }
782
783 public bool MoveNext ()
784 {
785 VerifyState ();
786
787 if (next < 0)
788 return false;
789
790 if (next < l._size) {
791 current = l._items [next++];
792 return true;
793 }
794
795 next = -1;
796 return false;
797 }
798
799 public T Current {
800 get { return current; }
801 }
802
803 void IEnumerator.Reset ()
804 {
805 VerifyState ();
806 next = 0;
807 }
808
809 object IEnumerator.Current {
810 get {
811 VerifyState ();
812 if (next <= 0)
813 throw new InvalidOperationException ();
814 return current;
815 }
816 }
817 }
818 }
819 }
git-svn mirror of mcs