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 [] data;
  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                         data = 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                                 data = EmptyArray;
  62                                 AddEnumerable (collection);
  63                         }
  64                         else
  65                         {
  66                                 data = 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                         data = new T [capacity];
  76                 }
  77
  78                 internal List (T [] data, int size)
  79                 {
  80                         this.data = data;
  81                         this.size = size;
  82                 }
  83                 public void Add (T item)
  84                 {
  85                         GrowIfNeeded (1);
  86                         data [size ++] = item;
  87                 }
  88
  89                 void GrowIfNeeded (int newCount)
  90                 {
  91                         int minimumSize = size + newCount;
  92                         if (minimumSize > data.Length)
  93                                 Capacity = Math.Max (Math.Max (Capacity * 2, DefaultCapacity), minimumSize);
  94                 }
  95
  96                 void CheckRange (int idx, int count)
  97                 {
  98                         if (idx < 0)
  99                                 throw new ArgumentOutOfRangeException ("index");
 100
 101                         if (count < 0)
 102                                 throw new ArgumentOutOfRangeException ("count");
 103
 104                         if ((uint) idx + (uint) count > (uint) size)
 105                                 throw new ArgumentException ("index and count exceed length of list");
 106                 }
 107
 108                 void AddCollection (ICollection <T> collection)
 109                 {
 110                         int collectionCount = collection.Count;
 111                         GrowIfNeeded (collectionCount);
 112                         collection.CopyTo (data, size);
 113                         size += collectionCount;
 114                 }
 115                 void AddEnumerable (IEnumerable <T> enumerable)
 116                 {
 117                         foreach (T t in enumerable)
 118                         {
 119                                 Add (t);
 120                         }
 121                 }
 122
 123                 public void AddRange (IEnumerable <T> collection)
 124                 {
 125                         CheckCollection (collection);
 126
 127                         ICollection <T> c = collection as ICollection <T>;
 128                         if (c != null)
 129                                 AddCollection (c);
 130                         else
 131                                 AddEnumerable (collection);
 132                 }
 133
 134                 public ReadOnlyCollection <T> AsReadOnly ()
 135                 {
 136                         return new ReadOnlyCollection <T> (this);
 137                 }
 138
 139                 public int BinarySearch (T item)
 140                 {
 141                         return Array.BinarySearch <T> (data, 0, size, item);
 142                 }
 143
 144                 public int BinarySearch (T item, IComparer <T> comparer)
 145                 {
 146                         return Array.BinarySearch <T> (data, 0, size, item, comparer);
 147                 }
 148
 149                 public int BinarySearch (int index, int count, T item, IComparer <T> comparer)
 150                 {
 151                         CheckRange (index, count);
 152                         return Array.BinarySearch <T> (data, index, count, item, comparer);
 153                 }
 154
 155                 public void Clear ()
 156                 {
 157                         Array.Clear (data, 0, data.Length);
 158                         size = 0;
 159                 }
 160
 161                 public bool Contains (T item)
 162                 {
 163                         EqualityComparer<T> equalityComparer = EqualityComparer<T>.Default;
 164                         for (int i = 0; i < size; i++)
 165                                 if (equalityComparer.Equals (data[i], item))
 166                                         return true;
 167                         return false;
 168                 }
 169
 170                 public List <TOutput> ConvertAll <TOutput> (Converter <T, TOutput> converter)
 171                 {
 172                         if (converter == null)
 173                                 throw new ArgumentNullException ("converter");
 174                         List <TOutput> u = new List <TOutput> (size);
 175                         foreach (T t in this)
 176                                 u.Add (converter (t));
 177                         return u;
 178                 }
 179
 180                 public void CopyTo (T [] array)
 181                 {
 182                         Array.Copy (data, 0, array, 0, size);
 183                 }
 184
 185                 public void CopyTo (T [] array, int arrayIndex)
 186                 {
 187                         Array.Copy (data, 0, array, arrayIndex, size);
 188                 }
 189
 190                 public void CopyTo (int index, T [] array, int arrayIndex, int count)
 191                 {
 192                         CheckRange (index, count);
 193                         Array.Copy (data, index, array, arrayIndex, count);
 194                 }
 195
 196                 public bool Exists (Predicate <T> match)
 197                 {
 198                         return FindIndex (match) != -1;
 199                 }
 200
 201                 public T Find (Predicate <T> match)
 202                 {
 203                         int i = FindIndex (match);
 204                         return (i != -1) ? data [i] : default (T);
 205                 }
 206                 void CheckMatch (Predicate <T> match)
 207                 {
 208                         if (match == null)
 209                                 throw new ArgumentNullException ("match");
 210                 }
 211
 212                 // Maybe we could make this faster. For example, you could
 213                 // make a bit set with stackalloc for which elements to copy
 214                 // then you could size the array correctly.
 215                 public List <T> FindAll (Predicate <T> match)
 216                 {
 217                         CheckMatch (match);
 218                         List <T> f = new List <T> ();
 219
 220                         foreach (T t in this)
 221                                 if (match (t))
 222                                         f.Add (t);
 223
 224                         return f;
 225                 }
 226
 227                 public int FindIndex (Predicate <T> match)
 228                 {
 229                         CheckMatch (match);
 230                         return GetIndex (0, size, match);
 231                 }
 232
 233                 public int FindIndex (int startIndex, Predicate <T> match)
 234                 {
 235                         CheckMatch (match);
 236                         CheckIndex (startIndex);
 237                         return GetIndex (startIndex, size - startIndex, match);
 238                 }
 239                 public int FindIndex (int startIndex, int count, Predicate <T> match)
 240                 {
 241                         CheckMatch (match);
 242                         CheckRange (startIndex, count);
 243                         return GetIndex (startIndex, count, match);
 244                 }
 245                 int GetIndex (int startIndex, int count, Predicate <T> match)
 246                 {
 247                         for (int i = startIndex; i < startIndex + count; i ++)
 248                                 if (match (data [i]))
 249                                         return i;
 250
 251                         return -1;
 252                 }
 253
 254                 public T FindLast (Predicate <T> match)
 255                 {
 256                         CheckMatch (match);
 257                         int i = GetLastIndex (0, size, match);
 258                         return i == -1 ? default (T) : this [i];
 259                 }
 260
 261                 public int FindLastIndex (Predicate <T> match)
 262                 {
 263                         CheckMatch (match);
 264                         return GetLastIndex (0, size, match);
 265                 }
 266
 267                 public int FindLastIndex (int startIndex, Predicate <T> match)
 268                 {
 269                         CheckMatch (match);
 270                         CheckIndex (startIndex);
 271                         return GetLastIndex (0, startIndex + 1, match);
 272                 }
 273
 274                 public int FindLastIndex (int startIndex, int count, Predicate <T> match)
 275                 {
 276                         CheckMatch (match);
 277                         int start = startIndex - count + 1;
 278                         CheckRange (start, count);
 279                         return GetLastIndex (start, count, match);
 280                 }
 281
 282                 int GetLastIndex (int startIndex, int count, Predicate <T> match)
 283                 {
 284                         // unlike FindLastIndex, takes regular params for search range
 285                         for (int i = startIndex + count; i != startIndex;)
 286                                 if (match (data [--i]))
 287                                         return i;
 288                         return -1;
 289                 }
 290
 291                 public void ForEach (Action <T> action)
 292                 {
 293                         if (action == null)
 294                                 throw new ArgumentNullException ("action");
 295                         foreach (T t in this)
 296                                 action (t);
 297                 }
 298
 299                 public Enumerator GetEnumerator ()
 300                 {
 301                         return new Enumerator (this);
 302                 }
 303
 304                 public List <T> GetRange (int index, int count)
 305                 {
 306                         CheckRange (index, count);
 307                         T [] tmpArray = new T [count];
 308                         Array.Copy (data, index, tmpArray, 0, count);
 309                         return new List <T> (tmpArray, count);
 310                 }
 311
 312                 public int IndexOf (T item)
 313                 {
 314                         return Array.IndexOf<T> (data, item, 0, size);
 315                 }
 316
 317                 public int IndexOf (T item, int index)
 318                 {
 319                         CheckIndex (index);
 320                         return Array.IndexOf<T> (data, item, index, size - index);
 321                 }
 322
 323                 public int IndexOf (T item, int index, int count)
 324                 {
 325                         if (index < 0)
 326                                 throw new ArgumentOutOfRangeException ("index");
 327
 328                         if (count < 0)
 329                                 throw new ArgumentOutOfRangeException ("count");
 330
 331                         if ((uint) index + (uint) count > (uint) size)
 332                                 throw new ArgumentOutOfRangeException ("index and count exceed length of list");
 333
 334                         return Array.IndexOf<T> (data, item, index, count);
 335                 }
 336
 337                 void Shift (int start, int delta)
 338                 {
 339                         if (delta < 0)
 340                                 start -= delta;
 341
 342                         Array.Copy (data, start, data, start + delta, size - start);
 343
 344                         size += delta;
 345                 }
 346
 347                 void CheckIndex (int index)
 348                 {
 349                         if (index < 0 || (uint) index > (uint) size)
 350                                 throw new ArgumentOutOfRangeException ("index");
 351                 }
 352
 353                 public void Insert (int index, T item)
 354                 {
 355                         CheckIndex (index);
 356                         GrowIfNeeded (1);
 357                         Shift (index, 1);
 358                         this [index] = item;
 359
 360                 }
 361
 362                 void CheckCollection (IEnumerable <T> collection)
 363                 {
 364                         if (collection == null)
 365                                 throw new ArgumentNullException ("collection");
 366                 }
 367
 368                 public void InsertRange (int index, IEnumerable <T> collection)
 369                 {
 370                         CheckCollection (collection);
 371                         CheckIndex (index);
 372                         ICollection <T> c = collection as ICollection <T>;
 373                         if (c != null)
 374                                 InsertCollection (index, c);
 375                         else
 376                                 InsertEnumeration (index, collection);
 377                 }
 378
 379                 void InsertCollection (int index, ICollection <T> collection)
 380                 {
 381                         int collectionCount = collection.Count;
 382                         GrowIfNeeded (collectionCount);
 383
 384                         Shift (index, collectionCount);
 385                         collection.CopyTo (data, index);
 386                 }
 387                 void InsertEnumeration (int index, IEnumerable <T> enumerable)
 388                 {
 389                         foreach (T t in enumerable)
 390                                 Insert (index++, t);
 391                 }
 392
 393                 public int LastIndexOf (T item)
 394                 {
 395                         return Array.LastIndexOf<T> (data, item, size - 1, size);
 396                 }
 397
 398                 public int LastIndexOf (T item, int index)
 399                 {
 400                         CheckIndex (index);
 401                         return Array.LastIndexOf<T> (data, item, index, index + 1);
 402                 }
 403
 404                 public int LastIndexOf (T item, int index, int count)
 405                 {
 406                         if (index < 0)
 407                                 throw new ArgumentOutOfRangeException ("index", index, "index is negative");
 408
 409                         if (count < 0)
 410                                 throw new ArgumentOutOfRangeException ("count", count, "count is negative");
 411
 412                         if (index - count + 1 < 0)
 413                                 throw new ArgumentOutOfRangeException ("cound", count, "count is too large");
 414
 415                         return Array.LastIndexOf<T> (data, item, index, count);
 416                 }
 417
 418                 public bool Remove (T item)
 419                 {
 420                         int loc = IndexOf (item);
 421                         if (loc != -1)
 422                                 RemoveAt (loc);
 423
 424                         return loc != -1;
 425                 }
 426
 427                 [MonoTODO ("I can make it faster than this...")]
 428                 public int RemoveAll (Predicate <T> match)
 429                 {
 430                         CheckMatch (match);
 431
 432                         int index = 0;
 433                         int c = 0;
 434                         while ((index = GetIndex (index, size - index, match)) != -1) {
 435                                 RemoveAt (index);
 436                                 c ++;
 437                         }
 438
 439                         Array.Clear (data, size, c);
 440                         return c;
 441                 }
 442
 443                 public void RemoveAt (int index)
 444                 {
 445                         CheckIndex (index);
 446                         Shift (index, -1);
 447                         Array.Clear (data, size, 0);
 448                 }
 449
 450                 public void RemoveRange (int index, int count)
 451                 {
 452                         CheckRange (index, count);
 453                         Shift (index, -count);
 454                         Array.Clear (data, size, count);
 455                 }
 456
 457                 public void Reverse ()
 458                 {
 459                         Array.Reverse (data, 0, size);
 460                 }
 461                 public void Reverse (int index, int count)
 462                 {
 463                         CheckRange (index, count);
 464                         Array.Reverse (data, index, count);
 465                 }
 466
 467                 public void Sort ()
 468                 {
 469                         Array.Sort<T> (data, 0, size, Comparer <T>.Default);
 470                 }
 471                 public void Sort (IComparer <T> comparer)
 472                 {
 473                         Array.Sort<T> (data, 0, size, comparer);
 474                 }
 475
 476                 public void Sort (Comparison <T> comparison)
 477                 {
 478                         Array.Sort<T> (data, size, comparison);
 479                 }
 480
 481                 public void Sort (int index, int count, IComparer <T> comparer)
 482                 {
 483                         CheckRange (index, count);
 484                         Array.Sort<T> (data, index, count, comparer);
 485                 }
 486
 487                 public T [] ToArray ()
 488                 {
 489                         T [] t = new T [size];
 490                         Array.Copy (data, t, size);
 491
 492                         return t;
 493                 }
 494
 495                 public void TrimExcess ()
 496                 {
 497                         Capacity = size;
 498                 }
 499
 500                 public bool TrueForAll (Predicate <T> match)
 501                 {
 502                         CheckMatch (match);
 503
 504                         foreach (T t in this)
 505                                 if (!match (t))
 506                                         return false;
 507
 508                         return true;
 509                 }
 510
 511                 public int Capacity {
 512                         get {
 513                                 return data.Length;
 514                         }
 515                         set {
 516                                 if ((uint) value < (uint) size)
 517                                         throw new ArgumentOutOfRangeException ();
 518
 519                                 Array.Resize (ref data, value);
 520                         }
 521                 }
 522
 523                 public int Count {
 524                         get { return size; }
 525                 }
 526
 527                 public T this [int index] {
 528                         get {
 529                                 if ((uint) index >= (uint) size)
 530                                         throw new ArgumentOutOfRangeException ("index");
 531                                 return data [index];
 532                         }
 533                         set {
 534                                 CheckIndex (index);
 535                                 data [index] = value;
 536                         }
 537                 }
 538
 539 #region Interface implementations.
 540                 IEnumerator <T> IEnumerable <T>.GetEnumerator ()
 541                 {
 542                         return GetEnumerator ();
 543                 }
 544
 545                 void ICollection.CopyTo (Array array, int arrayIndex)
 546                 {
 547                         Array.Copy (data, 0, array, arrayIndex, size);
 548                 }
 549
 550                 IEnumerator IEnumerable.GetEnumerator ()
 551                 {
 552                         return GetEnumerator ();
 553                 }
 554
 555                 int IList.Add (object item)
 556                 {
 557                         Add ((T) item);
 558                         return size - 1;
 559                 }
 560
 561                 bool IList.Contains (object item)
 562                 {
 563                         return Contains ((T) item);
 564                 }
 565
 566                 int IList.IndexOf (object item)
 567                 {
 568                         return IndexOf ((T) item);
 569                 }
 570
 571                 void IList.Insert (int index, object item)
 572                 {
 573                         Insert (index, (T) item);
 574                 }
 575
 576                 void IList.Remove (object item)
 577                 {
 578                         Remove ((T) item);
 579                 }
 580
 581                 bool ICollection <T>.IsReadOnly {
 582                         get { return false; }
 583                 }
 584                 bool ICollection.IsSynchronized {
 585                         get { return false; }
 586                 }
 587
 588                 object ICollection.SyncRoot {
 589                         get { return this; }
 590                 }
 591                 bool IList.IsFixedSize {
 592                         get { return false; }
 593                 }
 594
 595                 bool IList.IsReadOnly {
 596                         get { return false; }
 597                 }
 598
 599                 object IList.this [int index] {
 600                         get { return this [index]; }
 601                         set { this [index] = (T) value; }
 602                 }
 603 #endregion
 604
 605                 [Serializable]
 606                 public struct Enumerator : IEnumerator <T>, IDisposable {
 607                         const int NOT_STARTED = -2;
 608
 609                         // this MUST be -1, because we depend on it in move next.
 610                         // we just decr the size, so, 0 - 1 == FINISHED
 611                         const int FINISHED = -1;
 612
 613                         List <T> l;
 614                         int idx;
 615                         int ver;
 616
 617                         internal Enumerator (List <T> l)
 618                         {
 619                                 this.l = l;
 620                                 idx = NOT_STARTED;
 621                                 ver = l.version;
 622                         }
 623
 624                         // for some fucked up reason, MSFT added a useless dispose to this class
 625                         // It means that in foreach, we must still do a try/finally. Broken, very
 626                         // broken.
 627                         public void Dispose ()
 628                         {
 629                                 idx = NOT_STARTED;
 630                         }
 631
 632                         public bool MoveNext ()
 633                         {
 634                                 if (ver != l.version)
 635                                         throw new InvalidOperationException ();
 636
 637                                 if (idx == NOT_STARTED)
 638                                         idx = l.size;
 639
 640                                 return idx != FINISHED && -- idx != FINISHED;
 641                         }
 642
 643                         public T Current {
 644                                 get {
 645                                         if (idx < 0)
 646                                                 throw new InvalidOperationException ();
 647
 648                                         return l.data [l.size - 1 - idx];
 649                                 }
 650                         }
 651
 652                         void IEnumerator.Reset ()
 653                         {
 654                                 if (ver != l.version)
 655                                         throw new InvalidOperationException ();
 656
 657                                 idx = NOT_STARTED;
 658                         }
 659
 660                         object IEnumerator.Current {
 661                                 get { return Current; }
 662                         }
 663                 }
 664         }
 665 }
 666 #endif