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