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