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 //
   9 // (C) 2004 Novell, Inc.
  10 //
  11
  12 //
  13 // Copyright (C) 2004 Novell, Inc (http://www.novell.com)
  14 //
  15 // Permission is hereby granted, free of charge, to any person obtaining
  16 // a copy of this software and associated documentation files (the
  17 // "Software"), to deal in the Software without restriction, including
  18 // without limitation the rights to use, copy, modify, merge, publish,
  19 // distribute, sublicense, and/or sell copies of the Software, and to
  20 // permit persons to whom the Software is furnished to do so, subject to
  21 // the following conditions:
  22 //
  23 // The above copyright notice and this permission notice shall be
  24 // included in all copies or substantial portions of the Software.
  25 //
  26 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  27 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  28 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  29 // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  30 // LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  31 // OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  32 // WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  33 //
  34
  35 #if NET_2_0
  36 using System;
  37 using System.Collections;
  38 using System.Runtime.InteropServices;
  39
  40 namespace System.Collections.Generic
  41 {
  42         [ComVisible(false)]
  43         public class List<T> : IList<T>, ICollection<T>, IEnumerable<T>, IList, ICollection, IEnumerable
  44         {
  45                 T [] data;
  46                 int size;
  47                 int version;
  48
  49                 const int DefaultCapacity = 4;
  50
  51                 public List ()
  52                 {
  53                         data = new T [DefaultCapacity];
  54                 }
  55
  56                 public List (IEnumerable <T> collection)
  57                 {
  58                         AddRange (collection);
  59                 }
  60
  61                 public List (int capacity)
  62                 {
  63                         data = new T [capacity];
  64                 }
  65
  66                 public void Add (T item)
  67                 {
  68                         if (size == data.Length)
  69                                 Capacity = Math.Max (Capacity * 2, DefaultCapacity);
  70
  71                         data [size ++] = item;
  72                 }
  73
  74                 public void CheckRange (int idx, int count)
  75                 {
  76                         if (idx < 0)
  77                                 throw new ArgumentOutOfRangeException ("index must be equal or larger than zero");
  78
  79                         if (count < 0 || idx > size - count)
  80                                 throw new ArgumentOutOfRangeException ("Count must refer to an element in the list");
  81                 }
  82
  83                 [MonoTODO ("PERFORMANCE: fix if it is an IList <T>")]
  84                 public void AddRange(IEnumerable<T> collection)
  85                 {
  86                         foreach (T t in collection)
  87                                 Add (t);
  88                 }
  89
  90                 public IList<T> AsReadOnly ()
  91                 {
  92                         return new ReadOnlyList<T>(this);
  93                 }
  94
  95                 public int BinarySearch(T item)
  96                 {
  97                         return BinarySearch (item, Comparer <T>.Default);
  98                 }
  99
 100                 public int BinarySearch(T item, IComparer<T> comparer)
 101                 {
 102                         return BinarySearch (0, size, item, comparer);
 103                 }
 104
 105                 public int BinarySearch(int index, int count, T item, IComparer<T> comparer)
 106                 {
 107                         CheckRange (index, count);
 108                         return Array.BinarySearch (data, index, size, item, comparer);
 109                 }
 110
 111                 public void Clear ()
 112                 {
 113                         Array.Clear (data, 0, data.Length);
 114                 }
 115
 116                 public bool Contains (T item)
 117                 {
 118                         return IndexOf (item) != -1;
 119                 }
 120
 121                 public List <U> ConvertAll <U> (Converter<T, U> converter)
 122                 {
 123                         List <U> u = new List <U> (size);
 124                         int i = 0;
 125                         foreach (T t in this)
 126                                 u [i ++] = converter (t);
 127
 128                         return u;
 129                 }
 130
 131                 public void CopyTo (T [] array)
 132                 {
 133                         CopyTo (array, 0);
 134                 }
 135
 136                 public void CopyTo (T [] array, int arrayIndex)
 137                 {
 138                         CopyTo (0, array, arrayIndex, size);
 139                 }
 140
 141                 public void CopyTo (int index, T[] array, int arrayIndex, int count)
 142                 {
 143                         CheckRange (index, count);
 144                         Array.Copy (data, index, array, arrayIndex, count);
 145                 }
 146
 147                 public bool Exists (Predicate<T> match)
 148                 {
 149                         foreach (T t in this)
 150                                 if (match (t))
 151                                         return true;
 152
 153                         return false;
 154                 }
 155
 156                 public T Find (Predicate<T> match)
 157                 {
 158                         foreach (T t in this)
 159                                 if (match (t))
 160                                         return t;
 161
 162                         return default (T);
 163                 }
 164
 165                 // Maybe we could make this faster. For example, you could
 166                 // make a bit set with stackalloc for which elements to copy
 167                 // then you could size the array correctly.
 168                 public List<T> FindAll (Predicate<T> match)
 169                 {
 170                         List <T> f = new List <T> ();
 171
 172                         foreach (T t in this)
 173                                 if (match (t))
 174                                         f.Add (t);
 175
 176                         return f;
 177                 }
 178
 179                 public int FindIndex (Predicate <T> match)
 180                 {
 181                         return FindIndex (0, match);
 182                 }
 183
 184                 public int FindIndex (int startIndex, Predicate <T> match)
 185                 {
 186                         return FindIndex (startIndex, size - startIndex, match);
 187                 }
 188
 189                 public int FindIndex (int startIndex, int count, Predicate <T> match)
 190                 {
 191                         CheckRange (startIndex, count);
 192
 193                         for (int i = startIndex; i < startIndex + count; i ++)
 194                                 if (match (data [i]))
 195                                         return i;
 196
 197                         return -1;
 198                 }
 199
 200                 public T FindLast (Predicate <T> match)
 201                 {
 202                         int i = FindLastIndex (match);
 203                         return i == -1 ? default (T) : this [i];
 204                 }
 205
 206                 public int FindLastIndex (Predicate <T> match)
 207                 {
 208                         return FindLastIndex (0, match);
 209                 }
 210
 211                 public int FindLastIndex (int startIndex, Predicate <T> match)
 212                 {
 213                         return FindLastIndex (startIndex, size - startIndex, match);
 214                 }
 215
 216                 public int FindLastIndex (int startIndex, int count, Predicate <T> match)
 217                 {
 218                         CheckRange (startIndex, count);
 219                         for (int i = startIndex + count; i != startIndex;)
 220                                 if (match (data [--i]))
 221                                         return i;
 222
 223                         return -1;
 224                 }
 225
 226                 public void ForEach (Action <T> action)
 227                 {
 228                         foreach (T t in this)
 229                                 action (t);
 230                 }
 231
 232                 public Enumerator GetEnumerator ()
 233                 {
 234                         return new Enumerator (this);
 235                 }
 236
 237                 public List <T> GetRange (int index, int count)
 238                 {
 239                         CheckRange (index, count);
 240                         List<T> result = new List<T> (count);
 241
 242                         result.size = count;
 243                         for (int i = 0; i < count; i++)
 244                                 result.data [i] = data [i+index];
 245
 246                         return result;
 247                 }
 248
 249                 public int IndexOf (T item)
 250                 {
 251                         return IndexOf (item, 0);
 252                 }
 253
 254                 public int IndexOf (T item, int index)
 255                 {
 256                         return IndexOf (item, index, size - index);
 257                 }
 258
 259                 public int IndexOf (T item, int index, int count)
 260                 {
 261                         CheckRange (index, count);
 262                         return Array.IndexOf (data, item, index, count);
 263                 }
 264
 265                 void Shift (int start, int delta)
 266                 {
 267                         if (delta < 0)
 268                                 start -= delta;
 269
 270                         Array.Copy (data, start, data, start + delta, size - start);
 271
 272                         size += delta;
 273                 }
 274
 275                 public void Insert (int index, T item)
 276                 {
 277                         if ((uint) index > (uint) size)
 278                                 throw new ArgumentOutOfRangeException ("index");
 279
 280                         if (size == data.Length)
 281                                  Capacity = Math.Max (Capacity * 2, DefaultCapacity);
 282                         Shift (index, 1);
 283                         this [index] = item;
 284
 285                 }
 286                 [MonoTODO ("Performance for collection")]
 287                 public void InsertRange (int index, IEnumerable<T> collection)
 288                 {
 289                         foreach (T t in collection)
 290                                 Insert (index ++, t);
 291                 }
 292
 293                 public int LastIndexOf (T item)
 294                 {
 295                         return LastIndexOf  (item, 0);
 296                 }
 297
 298                 public int LastIndexOf  (T item, int index)
 299                 {
 300                         return LastIndexOf  (item, index, size - index);
 301                 }
 302
 303                 public int LastIndexOf (T item, int index, int count)
 304                 {
 305                         CheckRange (index, count);
 306                         return Array.LastIndexOf (data, item, index, count);
 307                 }
 308
 309                 public bool Remove (T item)
 310                 {
 311                         int loc = IndexOf (item);
 312                         if (loc != -1)
 313                                 RemoveAt (loc);
 314
 315                         return loc != -1;
 316                 }
 317
 318                 [MonoTODO ("I can make it faster than this...")]
 319                 public int RemoveAll (Predicate<T> match)
 320                 {
 321                         int index = 0;
 322                         int c = 0;
 323                         while ((index = FindIndex (index, match)) != -1) {
 324                                 RemoveAt (index);
 325                                 c ++;
 326                         }
 327
 328                         return c;
 329                 }
 330
 331                 public void RemoveAt (int index)
 332                 {
 333                         RemoveRange (index, 1);
 334                 }
 335
 336                 public void RemoveRange (int index, int count)
 337                 {
 338                         CheckRange (index, count);
 339                         Shift (index, -count);
 340                 }
 341
 342                 public void Reverse ()
 343                 {
 344                         Reverse (0, size);
 345                 }
 346                 public void Reverse (int index, int count)
 347                 {
 348                         CheckRange (index, count);
 349                         Array.Reverse (data, index, count);
 350                 }
 351
 352                 public void Sort ()
 353                 {
 354                         Sort (Comparer <T>.Default);
 355                 }
 356                 public void Sort (IComparer<T> comparer)
 357                 {
 358                         Sort (0, size, comparer);
 359                 }
 360
 361                 // Waiting on Array
 362                 [MonoTODO]
 363                 public void Sort (Comparison<T> comparison)
 364                 {
 365                         throw new NotImplementedException ();
 366                 }
 367
 368                 [MonoTODO]
 369                 public void Sort (int index, int count, IComparer<T> comparer)
 370                 {
 371                         CheckRange (index, count);
 372                         throw new NotImplementedException ();
 373                 }
 374
 375                 public T [] ToArray ()
 376                 {
 377                         T [] t = new T [size];
 378                         if (data != null)
 379                                 Array.Copy (data, t, size);
 380
 381                         return t;
 382                 }
 383
 384                 public void TrimToSize ()
 385                 {
 386                         Capacity = size;
 387                 }
 388
 389                 public bool TrueForAll (Predicate <T> match)
 390                 {
 391                         foreach (T t in this)
 392                                 if (!match (t))
 393                                         return false;
 394
 395                         return true;
 396                 }
 397
 398                 public int Capacity {
 399                         get {
 400                                 return data.Length;
 401                         }
 402                         set {
 403                                 if ((uint) value < (uint) size)
 404                                         throw new ArgumentOutOfRangeException ();
 405
 406                                 Array.Resize (ref data, value);
 407                         }
 408                 }
 409
 410                 public int Count {
 411                         get { return size; }
 412                 }
 413
 414                 public T this [int index] {
 415                         get {
 416                                 if ((uint) index >= (uint) size)
 417                                         throw new IndexOutOfRangeException ();
 418                                 return data [index];
 419                         }
 420                         set {
 421                                 if ((uint) index >= (uint) size)
 422                                         throw new IndexOutOfRangeException ();
 423                                 data [index] = value;
 424                         }
 425                 }
 426
 427 #region Interface implementations.
 428                 IEnumerator <T> IEnumerable <T>.GetEnumerator()
 429                 {
 430                         return GetEnumerator ();
 431                 }
 432
 433                 void ICollection.CopyTo (Array array, int arrayIndex)
 434                 {
 435                         Array.Copy (data, 0, data, arrayIndex, size);
 436                 }
 437
 438                 IEnumerator IEnumerable.GetEnumerator()
 439                 {
 440                         return GetEnumerator ();
 441                 }
 442
 443                 int IList.Add (object item)
 444                 {
 445                         Add ((T) item);
 446                         return size - 1;
 447                 }
 448
 449                 bool IList.Contains (object item)
 450                 {
 451                         return Contains ((T) item);
 452                 }
 453
 454                 int IList.IndexOf (object item)
 455                 {
 456                         return IndexOf ((T) item);
 457                 }
 458
 459                 void IList.Insert (int index, object item)
 460                 {
 461                         Insert (index, (T) item);
 462                 }
 463
 464                 void IList.Remove (object item)
 465                 {
 466                         Remove ((T) item);
 467                 }
 468
 469                 bool ICollection <T>.IsReadOnly {
 470                         get { return false; }
 471                 }
 472                 bool ICollection.IsSynchronized {
 473                         get { return false; }
 474                 }
 475
 476                 object ICollection.SyncRoot {
 477                         get { return this; }
 478                 }
 479                 bool IList.IsFixedSize {
 480                         get { return false; }
 481                 }
 482
 483                 bool IList.IsReadOnly {
 484                         get { return false; }
 485                 }
 486
 487                 object IList.this [int index] {
 488                         get { return this [index]; }
 489                         set { this [index] = (T) value; }
 490                 }
 491 #endregion
 492
 493                 [ComVisible (false)]
 494                 internal class ReadOnlyList<I> : IList<I>, ICollection<I>, IEnumerable<I>
 495                 {
 496                         IList<I> list;
 497
 498                         internal ReadOnlyList (IList<I> list)
 499                         {
 500                                 this.list = list;
 501                         }
 502
 503                         public void Add (I item)
 504                         {
 505                                 throw new NotSupportedException ();
 506                         }
 507
 508                         public void Clear ()
 509                         {
 510                                 throw new NotSupportedException ();
 511                         }
 512
 513                         public bool Contains (I item)
 514                         {
 515                                 return list.Contains (item);
 516                         }
 517
 518                         public void CopyTo (I [] array, int index)
 519                         {
 520                                 list.CopyTo (array, index);
 521                         }
 522
 523                         public IEnumerator<I> GetEnumerator ()
 524                         {
 525                                 return list.GetEnumerator ();
 526                         }
 527
 528                         IEnumerator IEnumerable.GetEnumerator ()
 529                         {
 530                                 return ((IEnumerable) list).GetEnumerator ();
 531                         }
 532
 533                         public int IndexOf (I item)
 534                         {
 535                                 return list.IndexOf (item);
 536                         }
 537
 538                         public void Insert (int index, I item)
 539                         {
 540                                 throw new NotSupportedException ();
 541                         }
 542
 543                         public bool Remove (I item)
 544                         {
 545                                 throw new NotSupportedException ();
 546                         }
 547
 548                         public void RemoveAt (int index)
 549                         {
 550                                 throw new NotSupportedException ();
 551                         }
 552
 553                         public int Count {
 554                                 get {
 555                                         return list.Count;
 556                                 }
 557                         }
 558
 559                         public bool IsReadOnly {
 560                                 get {
 561                                         return true;
 562                                 }
 563                         }
 564
 565                         public I this [int index] {
 566                                 get {
 567                                         return list [index];
 568                                 }
 569                                 set {
 570                                         throw new NotSupportedException ();
 571                                 }
 572                         }
 573                 }
 574
 575                 public struct Enumerator : IEnumerator <T>, IDisposable {
 576                         const int NOT_STARTED = -2;
 577
 578                         // this MUST be -1, because we depend on it in move next.
 579                         // we just decr the size, so, 0 - 1 == FINISHED
 580                         const int FINISHED = -1;
 581
 582                         List <T> l;
 583                         int idx;
 584                         int ver;
 585
 586                         internal Enumerator (List <T> l)
 587                         {
 588                                 this.l = l;
 589                                 idx = NOT_STARTED;
 590                                 ver = l.version;
 591                         }
 592
 593                         // for some fucked up reason, MSFT added a useless dispose to this class
 594                         // It means that in foreach, we must still do a try/finally. Broken, very
 595                         // broken.
 596                         public void Dispose ()
 597                         {
 598                                 idx = NOT_STARTED;
 599                         }
 600
 601                         public bool MoveNext ()
 602                         {
 603                                 if (ver != l.version)
 604                                         throw new InvalidOperationException ();
 605
 606                                 if (idx == NOT_STARTED)
 607                                         idx = l.size;
 608
 609                                 return idx != FINISHED && -- idx != FINISHED;
 610                         }
 611
 612                         public T Current {
 613                                 get {
 614                                         if (idx < 0)
 615                                                 throw new InvalidOperationException ();
 616
 617                                         return l.data [l.size - 1 - idx];
 618                                 }
 619                         }
 620
 621                         void IEnumerator.Reset ()
 622                         {
 623                                 if (ver != l.version)
 624                                         throw new InvalidOperationException ();
 625
 626                                 idx = NOT_STARTED;
 627                         }
 628
 629                         object IEnumerator.Current {
 630                                 get { return Current; }
 631                         }
 632
 633                 }
 634         }
 635 }
 636 #endif