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         [CLSCompliant(false)]
  43         [ComVisible(false)]
  44         public class List<T> : IList<T>, ICollection<T>, IEnumerable<T>, IList, ICollection, IEnumerable
  45         {
  46                 T [] data;
  47                 int size;
  48                 int version;
  49
  50                 const int DefaultCapacity = 4;
  51
  52                 public List ()
  53                 {
  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 (data == null)
  69                                 Capacity = DefaultCapacity;
  70                         else if (size == data.Length)
  71                                 Capacity = Math.Max (Capacity * 2, DefaultCapacity);
  72
  73                         data [size ++] = item;
  74                 }
  75
  76                 public void CheckRange (int idx, int count)
  77                 {
  78                         if (idx < 0 || count < 0 || idx > size - count)
  79                                 throw new ArgumentOutOfRangeException ();
  80                 }
  81
  82                 [MonoTODO ("PERFORMANCE: fix if it is an IList <T>")]
  83                 public void AddRange(IEnumerable<T> collection)
  84                 {
  85                         foreach (T t in collection)
  86                                 Add (t);
  87                 }
  88
  89                 public IList<T> AsReadOnly ()
  90                 {
  91                         return new ReadOnlyList<T>(this);
  92                 }
  93
  94                 public int BinarySearch(T item)
  95                 {
  96                         return BinarySearch (item, Comparer <T>.Default);
  97                 }
  98
  99                 public int BinarySearch(T item, IComparer<T> comparer)
 100                 {
 101                         return BinarySearch (0, size, item, comparer);
 102                 }
 103
 104                 public int BinarySearch(int index, int count, T item, IComparer<T> comparer)
 105                 {
 106                         CheckRange (index, count);
 107                         return Array.BinarySearch (data, index, size, item, comparer);
 108                 }
 109
 110                 public void Clear ()
 111                 {
 112                         if (data == null)
 113                                 return;
 114
 115                         Array.Clear (data, 0, data.Length);
 116                 }
 117
 118                 public bool Contains (T item)
 119                 {
 120                         return IndexOf (item) != -1;
 121                 }
 122
 123                 public List <U> ConvertAll <U> (Converter<T, U> converter)
 124                 {
 125                         List <U> u = new List <U> (size);
 126                         int i = 0;
 127                         foreach (T t in this)
 128                                 u [i ++] = converter (t);
 129
 130                         return u;
 131                 }
 132
 133                 public void CopyTo (T [] array)
 134                 {
 135                         CopyTo (array, 0);
 136                 }
 137
 138                 public void CopyTo (T [] array, int arrayIndex)
 139                 {
 140                         CopyTo (0, array, arrayIndex, size);
 141                 }
 142
 143                 public void CopyTo (int index, T[] array, int arrayIndex, int count)
 144                 {
 145                         CheckRange (index, count);
 146                         Array.Copy (data, index, array, arrayIndex, count);
 147                 }
 148
 149                 public bool Exists (Predicate<T> match)
 150                 {
 151                         foreach (T t in this)
 152                                 if (match (t))
 153                                         return true;
 154
 155                         return false;
 156                 }
 157
 158                 public T Find (Predicate<T> match)
 159                 {
 160                         foreach (T t in this)
 161                                 if (match (t))
 162                                         return t;
 163
 164                         return default (T);
 165                 }
 166
 167                 // Maybe we could make this faster. For example, you could
 168                 // make a bit set with stackalloc for which elements to copy
 169                 // then you could size the array correctly.
 170                 public List<T> FindAll (Predicate<T> match)
 171                 {
 172                         List <T> f = new List <T> ();
 173
 174                         foreach (T t in this)
 175                                 if (match (t))
 176                                         f.Add (t);
 177
 178                         return f;
 179                 }
 180
 181                 public int FindIndex (Predicate <T> match)
 182                 {
 183                         return FindIndex (0, match);
 184                 }
 185
 186                 public int FindIndex (int startIndex, Predicate <T> match)
 187                 {
 188                         return FindIndex (startIndex, size - startIndex, match);
 189                 }
 190
 191                 public int FindIndex (int startIndex, int count, Predicate <T> match)
 192                 {
 193                         CheckRange (startIndex, count);
 194
 195                         for (int i = startIndex; i < startIndex + count; i ++)
 196                                 if (match (data [i]))
 197                                         return i;
 198
 199                         return -1;
 200                 }
 201
 202                 public T FindLast (Predicate <T> match)
 203                 {
 204                         int i = FindLastIndex (match);
 205                         return i == -1 ? default (T) : this [i];
 206                 }
 207
 208                 public int FindLastIndex (Predicate <T> match)
 209                 {
 210                         return FindLastIndex (0, match);
 211                 }
 212
 213                 public int FindLastIndex (int startIndex, Predicate <T> match)
 214                 {
 215                         return FindLastIndex (startIndex, size - startIndex, match);
 216                 }
 217
 218                 public int FindLastIndex (int startIndex, int count, Predicate <T> match)
 219                 {
 220                         CheckRange (startIndex, count);
 221                         for (int i = startIndex + count; i != startIndex;)
 222                                 if (match (data [--i]))
 223                                         return i;
 224
 225                         return -1;
 226                 }
 227
 228                 public void ForEach (Action <T> action)
 229                 {
 230                         foreach (T t in this)
 231                                 action (t);
 232                 }
 233
 234                 public Enumerator <T> GetEnumerator ()
 235                 {
 236                         return new Enumerator <T> (this);
 237                 }
 238
 239                 [MonoTODO]
 240                 public List <T> GetRange (int index, int count)
 241                 {
 242                         throw new NotImplementedException ();
 243                 }
 244
 245                 public int IndexOf (T item)
 246                 {
 247                         return IndexOf (item, 0);
 248                 }
 249
 250                 public int IndexOf (T item, int index)
 251                 {
 252                         return IndexOf (item, index, size - index);
 253                 }
 254
 255                 public int IndexOf (T item, int index, int count)
 256                 {
 257                         CheckRange (index, count);
 258                         if (data == null)
 259                                 return -1;
 260
 261                         return Array.IndexOf (data, item, index, count);
 262                 }
 263
 264                 void Shift (int start, int delta)
 265                 {
 266                         if (delta < 0)
 267                                 start -= delta;
 268
 269                         Array.Copy (data, start, data, start + delta, size - start);
 270
 271                         size += delta;
 272                 }
 273
 274                 public void Insert (int index, T item)
 275                 {
 276                         if ((uint) index < (uint) size)
 277                                 throw new ArgumentOutOfRangeException ();
 278
 279                         Shift (index, 1);
 280                         this [index] = item;
 281
 282                 }
 283                 [MonoTODO ("Performance for collection")]
 284                 public void InsertRange (int index, IEnumerable<T> collection)
 285                 {
 286                         foreach (T t in collection)
 287                                 Insert (index ++, t);
 288                 }
 289
 290                 public int LastIndexOf (T item)
 291                 {
 292                         return LastIndexOf  (item, 0);
 293                 }
 294
 295                 public int LastIndexOf  (T item, int index)
 296                 {
 297                         return LastIndexOf  (item, index, size - index);
 298                 }
 299
 300                 public int LastIndexOf (T item, int index, int count)
 301                 {
 302                         CheckRange (index, count);
 303                         if (data == null)
 304                                 return -1;
 305
 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                                 data.CopyTo (t, 0);
 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                                 if (data == null)
 401                                         return DefaultCapacity;
 402                                 return data.Length;
 403                         }
 404                         set {
 405                                 if ((uint) value < (uint) size)
 406                                         throw new ArgumentOutOfRangeException ();
 407
 408                                 Array.Resize (ref data, value);
 409                         }
 410                 }
 411
 412                 public int Count {
 413                         get { return size; }
 414                 }
 415
 416                 public T this [int index] {
 417                         get {
 418                                 if ((uint) index >= (uint) size)
 419                                         throw new IndexOutOfRangeException ();
 420                                 return data [index];
 421                         }
 422                         set {
 423                                 if ((uint) index >= (uint) size)
 424                                         throw new IndexOutOfRangeException ();
 425                                 data [index] = value;
 426                         }
 427                 }
 428
 429 #region Interface Crap
 430                 IEnumerator <T> IEnumerable <T>.GetEnumerator()
 431                 {
 432                         return GetEnumerator ();
 433                 }
 434
 435                 void ICollection.CopyTo (Array array, int arrayIndex)
 436                 {
 437                         Array.Copy (data, 0, data, arrayIndex, size);
 438                 }
 439
 440                 IEnumerator IEnumerable.GetEnumerator()
 441                 {
 442                         return GetEnumerator ();
 443                 }
 444
 445                 int IList.Add (object item)
 446                 {
 447                         Add ((T) item);
 448                         return size - 1;
 449                 }
 450
 451                 bool IList.Contains (object item)
 452                 {
 453                         return Contains ((T) item);
 454                 }
 455
 456                 int IList.IndexOf (object item)
 457                 {
 458                         return IndexOf ((T) item);
 459                 }
 460
 461                 void IList.Insert (int index, object item)
 462                 {
 463                         Insert (index, (T) item);
 464                 }
 465
 466                 void IList.Remove (object item)
 467                 {
 468                         Remove ((T) item);
 469                 }
 470
 471                 bool ICollection <T>.IsReadOnly {
 472                         get { return false; }
 473                 }
 474                 bool ICollection.IsSynchronized {
 475                         get { return false; }
 476                 }
 477
 478                 object ICollection.SyncRoot {
 479                         get { return this; }
 480                 }
 481                 bool IList.IsFixedSize {
 482                         get { return false; }
 483                 }
 484
 485                 bool IList.IsReadOnly {
 486                         get { return false; }
 487                 }
 488
 489                 object IList.this [int index] {
 490                         get { return this [index]; }
 491                         set { this [index] = (T) value; }
 492                 }
 493 #endregion
 494
 495                 [ComVisible (false)]
 496                 internal class ReadOnlyList<I> : IList<I>, ICollection<I>, IEnumerable<I>
 497                 {
 498                         IList<I> list;
 499
 500                         internal ReadOnlyList (IList<I> list)
 501                         {
 502                                 this.list = list;
 503                         }
 504
 505                         public void Add (I item)
 506                         {
 507                                 throw new NotSupportedException ();
 508                         }
 509
 510                         public void Clear ()
 511                         {
 512                                 throw new NotSupportedException ();
 513                         }
 514
 515                         public bool Contains (I item)
 516                         {
 517                                 return list.Contains (item);
 518                         }
 519
 520                         public void CopyTo (I [] array, int index)
 521                         {
 522                                 list.CopyTo (array, index);
 523                         }
 524
 525                         public IEnumerator<I> GetEnumerator ()
 526                         {
 527                                 return list.GetEnumerator ();
 528                         }
 529
 530                         public int IndexOf (I item)
 531                         {
 532                                 return list.IndexOf (item);
 533                         }
 534
 535                         public void Insert (int index, I item)
 536                         {
 537                                 throw new NotSupportedException ();
 538                         }
 539
 540                         public bool Remove (I item)
 541                         {
 542                                 throw new NotSupportedException ();
 543                         }
 544
 545                         public void RemoveAt (int index)
 546                         {
 547                                 throw new NotSupportedException ();
 548                         }
 549
 550                         public int Count {
 551                                 get {
 552                                         return list.Count;
 553                                 }
 554                         }
 555
 556                         public bool IsReadOnly {
 557                                 get {
 558                                         return true;
 559                                 }
 560                         }
 561
 562                         public I this [int index] {
 563                                 get {
 564                                         return list [index];
 565                                 }
 566                                 set {
 567                                         throw new NotSupportedException ();
 568                                 }
 569                         }
 570                 }
 571
 572                 public struct Enumerator <T> : IEnumerator <T>, IEnumerator, IDisposable {
 573                         const int NOT_STARTED = -2;
 574
 575                         // this MUST be -1, because we depend on it in move next.
 576                         // we just decr the size, so, 0 - 1 == FINISHED
 577                         const int FINISHED = -1;
 578
 579                         List <T> l;
 580                         int idx;
 581                         int ver;
 582
 583                         internal Enumerator (List <T> l)
 584                         {
 585                                 this.l = l;
 586                                 idx = NOT_STARTED;
 587                                 ver = l.version;
 588                         }
 589
 590                         // for some fucked up reason, MSFT added a useless dispose to this class
 591                         // It means that in foreach, we must still do a try/finally. Broken, very
 592                         // broken.
 593                         public void Dispose ()
 594                         {
 595                                 idx = NOT_STARTED;
 596                         }
 597
 598                         public bool MoveNext ()
 599                         {
 600                                 if (ver != l.version)
 601                                         throw new InvalidOperationException ();
 602
 603                                 if (idx == NOT_STARTED)
 604                                         idx = l.size;
 605
 606                                 return idx != FINISHED && -- idx != FINISHED;
 607                         }
 608
 609                         public T Current {
 610                                 get {
 611                                         if (idx < 0)
 612                                                 throw new InvalidOperationException ();
 613
 614                                         return l.data [l.size - 1 - idx];
 615                                 }
 616                         }
 617
 618                         void IEnumerator.Reset ()
 619                         {
 620                                 if (ver != l.version)
 621                                         throw new InvalidOperationException ();
 622
 623                                 idx = NOT_STARTED;
 624                         }
 625
 626                         object IEnumerator.Current {
 627                                 get { return Current; }
 628                         }
 629
 630                 }
 631         }
 632 }
 633 #endif