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