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