mcs/class/corlib/System.Collections.Generic/List.cs

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