mcs/class/corlib/System.Collections/ArrayList.cs

   1 // ArrayList.cs
   2 //
   3 // Implementation of the ECMA ArrayList.
   4 //
   5 // Copyright (c) 2003 Thong (Tum) Nguyen [tum@veridicus.com]
   6 // Copyright (C) 2004-2005 Novell, Inc (http://www.novell.com)
   7 //
   8 // Permission is hereby granted, free of charge, to any person obtaining
   9 // a copy of this software and associated documentation files (the
  10 // "Software"), to deal in the Software without restriction, including
  11 // without limitation the rights to use, copy, modify, merge, publish,
  12 // distribute, sublicense, and/or sell copies of the Software, and to
  13 // permit persons to whom the Software is furnished to do so, subject to
  14 // the following conditions:
  15 //
  16 // The above copyright notice and this permission notice shall be
  17 // included in all copies or substantial portions of the Software.
  18 //
  19 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  20 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  21 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  22 // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  23 // LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  24 // OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  25 // WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  26 //
  27
  28 using System.Runtime.InteropServices;
  29 using System.Diagnostics;
  30
  31 namespace System.Collections
  32 {
  33         [ComVisible(true)]
  34         [DebuggerDisplay ("Count={Count}")]
  35         [DebuggerTypeProxy (typeof (CollectionDebuggerView))]
  36         [Serializable]
  37 #if INSIDE_CORLIB
  38         public
  39 #else
  40         internal
  41 #endif
  42         class ArrayList
  43                 : IList, ICloneable, ICollection, IEnumerable
  44         {
  45                 #region Enumerator
  46
  47                 private sealed class ArrayListEnumerator
  48                         : IEnumerator, ICloneable
  49                 {
  50                         private int m_Pos;
  51                         private int m_Index;
  52                         private int m_Count;
  53                         private object m_Current;
  54                         private ArrayList m_List;
  55                         private int m_ExpectedStateChanges;
  56
  57                         public ArrayListEnumerator(ArrayList list)
  58                                 : this(list, 0, list.Count)
  59                         {
  60                         }
  61
  62                         public object Clone()
  63                         {
  64                                 return this.MemberwiseClone();
  65                         }
  66
  67                         public ArrayListEnumerator(ArrayList list, int index, int count)
  68                         {
  69                                 m_List = list;
  70                                 m_Index = index;
  71                                 m_Count = count;
  72                                 m_Pos = m_Index - 1;
  73                                 m_Current = null;
  74                                 m_ExpectedStateChanges = list._version;
  75                         }
  76
  77                         public object Current
  78                         {
  79                                 get
  80                                 {
  81                                         if (m_Pos == m_Index - 1) {
  82                                                 throw new InvalidOperationException("Enumerator unusable (Reset pending, or past end of array.");
  83                                         }
  84
  85                                         return m_Current;
  86                                 }
  87                         }
  88
  89                         public bool MoveNext()
  90                         {
  91                                 if (m_List._version != m_ExpectedStateChanges)
  92                                 {
  93                                         throw new InvalidOperationException("List has changed.");
  94                                 }
  95
  96                                 m_Pos++;
  97
  98                                 if (m_Pos - m_Index < m_Count)
  99                                 {
 100                                         m_Current = m_List[m_Pos];
 101
 102                                         return true;
 103                                 }
 104
 105                                 return false;
 106                         }
 107
 108                         public void Reset()
 109                         {
 110                                 m_Current = null;
 111                                 m_Pos = m_Index - 1;
 112                         }
 113                 }
 114
 115                 sealed class SimpleEnumerator : IEnumerator, ICloneable
 116                 {
 117                         ArrayList list;
 118                         int index;
 119                         int version;
 120                         object currentElement;
 121                         static object endFlag = new object ();
 122
 123                         public SimpleEnumerator (ArrayList list)
 124                         {
 125                                 this.list = list;
 126                                 index = -1;
 127                                 version = list._version;
 128                                 currentElement = endFlag;
 129                         }
 130
 131                         public object Clone ()
 132                         {
 133                                 return MemberwiseClone ();
 134                         }
 135
 136                         public bool MoveNext ()
 137                         {
 138                                 if (version != list._version)
 139                                         throw new InvalidOperationException("List has changed.");
 140
 141                                 if (++index < list.Count) {
 142                                         currentElement = list [index];
 143                                         return true;
 144                                 } else {
 145                                         currentElement = endFlag;
 146                                         return false;
 147                                 }
 148                         }
 149
 150                         public object Current {
 151                                 get {
 152                                         if (currentElement == endFlag) {
 153                                                 if (index == -1)
 154                                                         throw new InvalidOperationException ("Enumerator not started");
 155                                                 else
 156                                                         throw new InvalidOperationException ("Enumerator ended");
 157                                         }
 158
 159                                         return currentElement;
 160                                 }
 161                         }
 162
 163                         public void Reset ()
 164                         {
 165                                 if (version != list._version)
 166                                         throw new InvalidOperationException ("List has changed.");
 167
 168                                 currentElement = endFlag;
 169                                 index = -1;
 170                         }
 171                 }
 172
 173                 #endregion
 174
 175                 #region ArrayListAdapter
 176
 177                 /// <summary>
 178                 /// Adapts various ILists into an ArrayList.
 179                 /// </summary>
 180                 [Serializable]
 181                 private sealed class ArrayListAdapter
 182                         : ArrayList
 183                 {
 184                         private sealed class EnumeratorWithRange
 185                                 : IEnumerator, ICloneable
 186                         {
 187                                 private int m_StartIndex;
 188                                 private int m_Count;
 189                                 private int m_MaxCount;
 190                                 private IEnumerator m_Enumerator;
 191
 192                                 public EnumeratorWithRange(IEnumerator enumerator, int index, int count)
 193                                 {
 194                                         m_Count = 0;
 195                                         m_StartIndex = index;
 196                                         m_MaxCount = count;
 197                                         m_Enumerator = enumerator;
 198
 199                                         Reset();
 200                                 }
 201
 202                                 public object Clone()
 203                                 {
 204                                         return this.MemberwiseClone();
 205                                 }
 206
 207                                 public object Current
 208                                 {
 209                                         get
 210                                         {
 211                                                 return m_Enumerator.Current;
 212                                         }
 213                                 }
 214
 215                                 public bool MoveNext()
 216                                 {
 217                                         if (m_Count >= m_MaxCount)
 218                                         {
 219                                                 return false;
 220                                         }
 221
 222                                         m_Count++;
 223
 224                                         return m_Enumerator.MoveNext();
 225                                 }
 226
 227                                 public void Reset()
 228                                 {
 229                                         m_Count = 0;
 230                                         m_Enumerator.Reset();
 231
 232                                         for (int i = 0; i < m_StartIndex; i++)
 233                                         {
 234                                                 m_Enumerator.MoveNext();
 235                                         }
 236                                 }
 237                         }
 238
 239                         private IList m_Adaptee;
 240
 241                         public ArrayListAdapter(IList adaptee)
 242                                 : base(0, true)
 243                         {
 244                                 m_Adaptee = adaptee;
 245                         }
 246
 247                         public override object this[int index]
 248                         {
 249                                 get
 250                                 {
 251                                         return m_Adaptee[index];
 252                                 }
 253
 254                                 set
 255                                 {
 256                                         m_Adaptee[index] = value;
 257                                 }
 258                         }
 259
 260                         public override int Count
 261                         {
 262                                 get
 263                                 {
 264                                         return m_Adaptee.Count;
 265                                 }
 266                         }
 267
 268                         public override int Capacity
 269                         {
 270                                 get
 271                                 {
 272                                         return m_Adaptee.Count;
 273                                 }
 274
 275                                 set
 276                                 {
 277                                         if (value < m_Adaptee.Count)
 278                                         {
 279                                                 throw new ArgumentException("capacity");
 280                                         }
 281                                 }
 282                         }
 283
 284                         public override bool IsFixedSize
 285                         {
 286                                 get
 287                                 {
 288                                         return m_Adaptee.IsFixedSize;
 289                                 }
 290                         }
 291
 292                         public override bool IsReadOnly
 293                         {
 294                                 get
 295                                 {
 296                                         return m_Adaptee.IsReadOnly;
 297                                 }
 298                         }
 299
 300                         public override object SyncRoot
 301                         {
 302                                 get
 303                                 {
 304                                         return m_Adaptee.SyncRoot;
 305                                 }
 306                         }
 307
 308                         public override int Add(object value)
 309                         {
 310                                 return m_Adaptee.Add(value);
 311                         }
 312
 313                         public override void Clear()
 314                         {
 315                                 m_Adaptee.Clear();
 316                         }
 317
 318                         public override bool Contains(object value)
 319                         {
 320                                 return m_Adaptee.Contains(value);
 321                         }
 322
 323                         public override int IndexOf(object value)
 324                         {
 325                                 return m_Adaptee.IndexOf(value);
 326                         }
 327
 328                         public override int IndexOf(object value, int startIndex)
 329                         {
 330                                 return IndexOf(value, startIndex, m_Adaptee.Count - startIndex);
 331                         }
 332
 333                         public override int IndexOf(object value, int startIndex, int count)
 334                         {
 335                                 if (startIndex < 0 || startIndex > m_Adaptee.Count)
 336                                 {
 337                                         ThrowNewArgumentOutOfRangeException ("startIndex", startIndex,
 338                                                 "Does not specify valid index.");
 339                                 }
 340
 341                                 if (count < 0)
 342                                 {
 343                                         ThrowNewArgumentOutOfRangeException ("count", count,
 344                                                 "Can't be less than 0.");
 345                                 }
 346
 347                                 // re-ordered to avoid possible integer overflow
 348                                 if (startIndex > m_Adaptee.Count - count) {
 349                                         // LAMESPEC: Every other method throws ArgumentException
 350                                         throw new ArgumentOutOfRangeException("count",
 351                                                 "Start index and count do not specify a valid range.");
 352                                 }
 353
 354                                 if (value == null)
 355                                 {
 356                                         for (int i = startIndex; i < startIndex + count; i++)
 357                                         {
 358                                                 if (m_Adaptee[i] == null)
 359                                                 {
 360                                                         return i;
 361                                                 }
 362                                         }
 363                                 }
 364                                 else
 365                                 {
 366                                         for (int i = startIndex; i < startIndex + count; i++)
 367                                         {
 368                                                 if (value.Equals(m_Adaptee[i]))
 369                                                 {
 370                                                         return i;
 371                                                 }
 372                                         }
 373                                 }
 374
 375                                 return -1;
 376                         }
 377
 378                         public override int LastIndexOf(object value)
 379                         {
 380                                 return LastIndexOf(value, m_Adaptee.Count - 1);
 381                         }
 382
 383                         public override int LastIndexOf(object value, int startIndex)
 384                         {
 385                                 return LastIndexOf(value, startIndex, startIndex + 1);
 386                         }
 387
 388                         public override int LastIndexOf(object value, int startIndex, int count)
 389                         {
 390                                 if (startIndex < 0)
 391                                 {
 392                                         ThrowNewArgumentOutOfRangeException ("startIndex", startIndex, "< 0");
 393                                 }
 394
 395                                 if (count < 0)
 396                                 {
 397                                         ThrowNewArgumentOutOfRangeException ("count", count, "count is negative.");
 398                                 }
 399
 400                                 if (startIndex - count  + 1 < 0)
 401                                 {
 402                                         ThrowNewArgumentOutOfRangeException ("count", count, "count is too large.");
 403                                 }
 404
 405                                 if (value == null)
 406                                 {
 407                                         for (int i = startIndex; i > startIndex - count; i--)
 408                                         {
 409                                                 if (m_Adaptee[i] == null)
 410                                                 {
 411                                                         return i;
 412                                                 }
 413                                         }
 414                                 }
 415                                 else
 416                                 {
 417                                         for (int i = startIndex; i > startIndex - count; i--)
 418                                         {
 419                                                 if (value.Equals(m_Adaptee[i]))
 420                                                 {
 421                                                         return i;
 422                                                 }
 423                                         }
 424                                 }
 425
 426                                 return -1;
 427                         }
 428
 429                         public override void Insert(int index, object value)
 430                         {
 431                                 m_Adaptee.Insert(index, value);
 432                         }
 433
 434                         public override void InsertRange(int index, ICollection c)
 435                         {
 436                                 if (c == null)
 437                                 {
 438                                         throw new ArgumentNullException("c");
 439                                 }
 440
 441                                 if (index > m_Adaptee.Count)
 442                                 {
 443                                         ThrowNewArgumentOutOfRangeException ("index", index,
 444                                                 "Index must be >= 0 and <= Count.");
 445                                 }
 446
 447                                 foreach (object value in c)
 448                                 {
 449                                         m_Adaptee.Insert(index++, value);
 450                                 }
 451                         }
 452
 453                         public override void Remove(object value)
 454                         {
 455                                 m_Adaptee.Remove(value);
 456                         }
 457
 458                         public override void RemoveAt(int index)
 459                         {
 460                                 m_Adaptee.RemoveAt(index);
 461                         }
 462
 463                         public override void RemoveRange(int index, int count)
 464                         {
 465                                 CheckRange(index, count, m_Adaptee.Count);
 466
 467                                 for (int i = 0; i < count; i++)
 468                                 {
 469                                         m_Adaptee.RemoveAt(index);
 470                                 }
 471                         }
 472
 473                         public override void Reverse()
 474                         {
 475                                 Reverse(0, m_Adaptee.Count);
 476                         }
 477
 478                         public override void Reverse(int index, int count)
 479                         {
 480                                 object tmp;
 481
 482                                 CheckRange(index, count, m_Adaptee.Count);
 483
 484                                 for (int i = 0; i < count / 2; i++)
 485                                 {
 486                                         tmp = m_Adaptee[i + index];
 487                                         m_Adaptee[i + index] = m_Adaptee[(index + count) - i + index - 1];
 488                                         m_Adaptee[(index + count) - i + index - 1] = tmp;
 489                                 }
 490                         }
 491
 492                         public override void SetRange(int index, ICollection c)
 493                         {
 494                                 if (c == null)
 495                                 {
 496                                         throw new ArgumentNullException("c");
 497                                 }
 498
 499                                 if (index < 0 || index + c.Count > m_Adaptee.Count)
 500                                 {
 501                                         throw new ArgumentOutOfRangeException("index");
 502                                 }
 503
 504                                 int x = index;
 505
 506                                 foreach (object value in c)
 507                                 {
 508                                         m_Adaptee[x++] = value;
 509                                 }
 510                         }
 511
 512                         public override void CopyTo(System.Array array)
 513                         {
 514                                 m_Adaptee.CopyTo(array, 0);
 515                         }
 516
 517                         public override void CopyTo(System.Array array, int index)
 518                         {
 519                                 m_Adaptee.CopyTo(array, index);
 520                         }
 521
 522                         public override void CopyTo(int index, System.Array array, int arrayIndex, int count)
 523                         {
 524                                 if (index < 0)
 525                                 {
 526                                         ThrowNewArgumentOutOfRangeException ("index", index,
 527                                                 "Can't be less than zero.");
 528                                 }
 529
 530                                 if (arrayIndex < 0)
 531                                 {
 532                                         ThrowNewArgumentOutOfRangeException ("arrayIndex", arrayIndex,
 533                                                 "Can't be less than zero.");
 534                                 }
 535
 536                                 if (count < 0)
 537                                 {
 538                                         ThrowNewArgumentOutOfRangeException ("index", index,
 539                                                 "Can't be less than zero.");
 540                                 }
 541
 542                                 if (index >= m_Adaptee.Count)
 543                                 {
 544                                         throw new ArgumentException("Can't be more or equal to list count.",
 545                                                 "index");
 546                                 }
 547
 548                                 if (array.Rank > 1)
 549                                 {
 550                                         throw new ArgumentException("Can't copy into multi-dimensional array.");
 551                                 }
 552
 553                                 if (arrayIndex >= array.Length)
 554                                 {
 555                                         throw new ArgumentException("arrayIndex can't be greater than array.Length - 1.");
 556                                 }
 557
 558                                 if (array.Length - arrayIndex + 1 < count)
 559                                 {
 560                                         throw new ArgumentException("Destination array is too small.");
 561                                 }
 562
 563                                 // re-ordered to avoid possible integer overflow
 564                                 if (index > m_Adaptee.Count - count) {
 565                                         throw new ArgumentException("Index and count do not denote a valid range of elements.", "index");
 566                                 }
 567
 568                                 for (int i = 0; i < count; i++)
 569                                 {
 570                                         array.SetValue(m_Adaptee[index + i], arrayIndex + i);
 571                                 }
 572                         }
 573
 574                         public override bool IsSynchronized
 575                         {
 576                                 get
 577                                 {
 578                                         return m_Adaptee.IsSynchronized;
 579                                 }
 580                         }
 581
 582                         public override IEnumerator GetEnumerator()
 583                         {
 584                                 return m_Adaptee.GetEnumerator();
 585                         }
 586
 587                         public override IEnumerator GetEnumerator(int index, int count)
 588                         {
 589                                 CheckRange(index, count, m_Adaptee.Count);
 590
 591                                 return new EnumeratorWithRange(m_Adaptee.GetEnumerator(), index, count);
 592                         }
 593
 594                         public override void AddRange(ICollection c)
 595                         {
 596                                 foreach (object value in c)
 597                                 {
 598                                         m_Adaptee.Add(value);
 599                                 }
 600                         }
 601
 602                         public override int BinarySearch(object value)
 603                         {
 604                                 return BinarySearch(value, null);
 605                         }
 606
 607                         public override int BinarySearch(object value, IComparer comparer)
 608                         {
 609                                 return BinarySearch(0, m_Adaptee.Count, value, comparer);
 610                         }
 611
 612                         public override int BinarySearch(int index, int count, object value, IComparer comparer)
 613                         {
 614                                 int r, x, y, z;
 615
 616                                 // Doing a direct BinarySearch on the adaptee will perform poorly if the adaptee is a linked-list.
 617                                 // Alternatives include copying the adaptee to a temporary array first.
 618
 619                                 CheckRange(index, count, m_Adaptee.Count);
 620
 621                                 if (comparer == null)
 622                                 {
 623                                         comparer = Comparer.Default;
 624                                 }
 625
 626                                 x = index;
 627                                 y = index + count - 1;
 628
 629                                 while (x <= y)
 630                                 {
 631                                         // Be careful with overflows
 632                                         z = x + ((y - x) / 2);
 633
 634                                         r = comparer.Compare(value, m_Adaptee[z]);
 635
 636                                         if (r < 0)
 637                                         {
 638                                                 y = z - 1;
 639                                         }
 640                                         else if (r > 0)
 641                                         {
 642                                                 x = z + 1;
 643                                         }
 644                                         else
 645                                         {
 646                                                 return z;
 647                                         }
 648                                 }
 649
 650                                 return ~x;
 651                         }
 652
 653                         public override object Clone()
 654                         {
 655                                 return new ArrayList.ArrayListAdapter(m_Adaptee);
 656                         }
 657
 658                         public override ArrayList GetRange(int index, int count)
 659                         {
 660                                 CheckRange(index, count, m_Adaptee.Count);
 661
 662                                 return new RangedArrayList(this, index, count);
 663                         }
 664
 665                         public override void TrimToSize()
 666                         {
 667                                 // N/A
 668                         }
 669
 670                         public override void Sort()
 671                         {
 672                                 Sort(Comparer.Default);
 673                         }
 674
 675                         public override void Sort(IComparer comparer)
 676                         {
 677                                 Sort(0, m_Adaptee.Count, comparer);
 678                         }
 679
 680                         public override void Sort(int index, int count, IComparer comparer)
 681                         {
 682                                 CheckRange(index, count, m_Adaptee.Count);
 683
 684                                 if (comparer == null)
 685                                 {
 686                                         comparer = Comparer.Default;
 687                                 }
 688
 689                                 // Doing a direct sort on the adaptee will perform poorly if the adaptee is a linked-list.
 690                                 // Alternatives include copying the adaptee into a temporary array first.
 691
 692                                 QuickSort(m_Adaptee, index, index + count - 1, comparer);
 693                         }
 694
 695
 696                         /// <summary>
 697                         /// Swaps two items in a list at the specified indexes.
 698                         /// </summary>
 699                         private static void Swap(IList list, int x, int y)
 700                         {
 701                                 object tmp;
 702
 703                                 tmp = list[x];
 704                                 list[x] = list[y];
 705                                 list[y] = tmp;
 706                         }
 707
 708                         /// <summary>
 709                         /// Quicksort for lists.
 710                         /// </summary>
 711                         /// <remarks>
 712                         /// This function acts as both qsort() and partition().
 713                         /// </remarks>
 714                         internal static void QuickSort(IList list, int left, int right, IComparer comparer)
 715                         {
 716                                 int i, j, middle;
 717                                 object pivot;
 718
 719                                 if (left >= right)
 720                                 {
 721                                         return;
 722                                 }
 723
 724                                 // Pick the pivot using the median-of-three strategy.
 725
 726                                 // Be careful with overflows
 727                                 middle = left + ((right - left) / 2);
 728
 729                                 if (comparer.Compare(list[middle], list[left]) < 0)
 730                                 {
 731                                         Swap(list, middle, left);
 732                                 }
 733
 734                                 if (comparer.Compare(list[right], list[left]) < 0)
 735                                 {
 736                                         Swap(list, right, left);
 737                                 }
 738
 739                                 if (comparer.Compare(list[right], list[middle]) < 0)
 740                                 {
 741                                         Swap(list, right, middle);
 742                                 }
 743
 744                                 if (right - left + 1 <= 3)
 745                                 {
 746                                         return;
 747                                 }
 748
 749                                 // Put the pivot in right - 1.
 750                                 Swap(list, right - 1, middle);
 751
 752                                 // List should look like:
 753                                 //
 754                                 // [Small] ..Numbers.. [Middle] ..Numbers.. [Pivot][Large]
 755
 756                                 pivot = list[right - 1];
 757
 758                                 // Sort from (left + 1) to (right - 2).
 759
 760                                 i = left;
 761                                 j = right - 1;
 762
 763                                 for (;;)
 764                                 {
 765                                         while (comparer.Compare(list[++i], pivot) < 0);
 766                                         while (comparer.Compare(list[--j], pivot) > 0);
 767
 768                                         if (i < j)
 769                                         {
 770                                                 Swap(list, i, j);
 771                                         }
 772                                         else
 773                                         {
 774                                                 break;
 775                                         }
 776                                 }
 777
 778                                 // Put pivot into the right position (real middle).
 779
 780                                 Swap(list, right - 1, i);
 781
 782                                 // Recursively sort the left and right sub lists.
 783
 784                                 QuickSort(list, left, i - 1, comparer);
 785                                 QuickSort(list, i + 1, right, comparer);
 786                         }
 787
 788                         public override object[] ToArray()
 789                         {
 790                                 object[] retval;
 791
 792                                 retval = new object[m_Adaptee.Count];
 793
 794                                 m_Adaptee.CopyTo(retval, 0);
 795
 796                                 return retval;
 797                         }
 798
 799                         public override Array ToArray(Type elementType)
 800                         {
 801                                 Array retval;
 802
 803                                 retval = Array.CreateInstance(elementType, m_Adaptee.Count);
 804
 805                                 m_Adaptee.CopyTo(retval, 0);
 806
 807                                 return retval;
 808                         }
 809                 }
 810
 811                 #endregion // ArrayListAdapter
 812
 813                 //
 814                 // ArrayList wrappers
 815                 //
 816
 817                 #region ArrayListWrapper
 818
 819                 /// <summary>
 820                 /// Base wrapper/decorator for ArrayLists.  Simply delegates all methods to
 821                 /// the underlying wrappee.
 822                 /// </summary>
 823                 [Serializable]
 824                 private class ArrayListWrapper
 825                         : ArrayList
 826                 {
 827                         protected ArrayList m_InnerArrayList;
 828
 829                         #region Constructors
 830
 831                         public ArrayListWrapper(ArrayList innerArrayList)
 832                         {
 833                                 m_InnerArrayList = innerArrayList;
 834                         }
 835
 836                         #endregion
 837
 838                         #region Indexers
 839
 840                         public override object this[int index]
 841                         {
 842                                 get
 843                                 {
 844                                         return m_InnerArrayList[index];
 845                                 }
 846
 847                                 set
 848                                 {
 849                                         m_InnerArrayList[index] = value;
 850                                 }
 851                         }
 852
 853                         #endregion
 854
 855                         #region Properties
 856
 857                         public override int Count
 858                         {
 859                                 get
 860                                 {
 861                                         return m_InnerArrayList.Count;
 862                                 }
 863                         }
 864
 865                         public override int Capacity
 866                         {
 867                                 get
 868                                 {
 869                                         return m_InnerArrayList.Capacity;
 870                                 }
 871
 872                                 set
 873                                 {
 874                                         m_InnerArrayList.Capacity = value;
 875                                 }
 876                         }
 877
 878                         public override bool IsFixedSize
 879                         {
 880                                 get
 881                                 {
 882                                         return m_InnerArrayList.IsFixedSize;
 883                                 }
 884                         }
 885
 886                         public override bool IsReadOnly
 887                         {
 888                                 get
 889                                 {
 890                                         return m_InnerArrayList.IsReadOnly;
 891                                 }
 892                         }
 893
 894                         public override bool IsSynchronized
 895                         {
 896                                 get
 897                                 {
 898                                         return m_InnerArrayList.IsSynchronized;
 899                                 }
 900                         }
 901
 902                         public override object SyncRoot
 903                         {
 904                                 get
 905                                 {
 906                                         return m_InnerArrayList.SyncRoot;
 907                                 }
 908                         }
 909
 910                         #endregion
 911
 912                         #region Methods
 913
 914                         public override int Add(object value)
 915                         {
 916                                 return m_InnerArrayList.Add(value);
 917                         }
 918
 919                         public override void Clear()
 920                         {
 921                                 m_InnerArrayList.Clear();
 922                         }
 923
 924                         public override bool Contains(object value)
 925                         {
 926                                 return m_InnerArrayList.Contains(value);
 927                         }
 928
 929                         public override int IndexOf(object value)
 930                         {
 931                                 return m_InnerArrayList.IndexOf(value);
 932                         }
 933
 934                         public override int IndexOf(object value, int startIndex)
 935                         {
 936                                 return m_InnerArrayList.IndexOf(value, startIndex);
 937                         }
 938
 939                         public override int IndexOf(object value, int startIndex, int count)
 940                         {
 941                                 return m_InnerArrayList.IndexOf(value, startIndex, count);
 942                         }
 943
 944                         public override int LastIndexOf(object value)
 945                         {
 946                                 return m_InnerArrayList.LastIndexOf(value);
 947                         }
 948
 949                         public override int LastIndexOf(object value, int startIndex)
 950                         {
 951                                 return m_InnerArrayList.LastIndexOf(value, startIndex);
 952                         }
 953
 954                         public override int LastIndexOf(object value, int startIndex, int count)
 955                         {
 956                                 return m_InnerArrayList.LastIndexOf(value, startIndex, count);
 957                         }
 958
 959                         public override void Insert(int index, object value)
 960                         {
 961                                 m_InnerArrayList.Insert(index, value);
 962                         }
 963
 964                         public override void InsertRange(int index, ICollection c)
 965                         {
 966                                 m_InnerArrayList.InsertRange(index, c);
 967                         }
 968
 969                         public override void Remove(object value)
 970                         {
 971                                 m_InnerArrayList.Remove(value);
 972                         }
 973
 974                         public override void RemoveAt(int index)
 975                         {
 976                                 m_InnerArrayList.RemoveAt(index);
 977                         }
 978
 979                         public override void RemoveRange(int index, int count)
 980                         {
 981                                 m_InnerArrayList.RemoveRange(index, count);
 982                         }
 983
 984                         public override void Reverse()
 985                         {
 986                                 m_InnerArrayList.Reverse();
 987                         }
 988
 989                         public override void Reverse(int index, int count)
 990                         {
 991                                 m_InnerArrayList.Reverse(index, count);
 992                         }
 993
 994                         public override void SetRange(int index, ICollection c)
 995                         {
 996                                 m_InnerArrayList.SetRange(index, c);
 997                         }
 998
 999                         public override void CopyTo(System.Array array)
1000                         {
1001                                 m_InnerArrayList.CopyTo(array);
1002                         }
1003
1004                         public override void CopyTo(System.Array array, int index)
1005                         {
1006                                 m_InnerArrayList.CopyTo(array, index);
1007                         }
1008
1009                         public override void CopyTo(int index, System.Array array, int arrayIndex, int count)
1010                         {
1011                                 m_InnerArrayList.CopyTo(index, array, arrayIndex, count);
1012                         }
1013
1014                         public override IEnumerator GetEnumerator()
1015                         {
1016                                 return m_InnerArrayList.GetEnumerator();
1017                         }
1018
1019                         public override IEnumerator GetEnumerator(int index, int count)
1020                         {
1021                                 return m_InnerArrayList.GetEnumerator(index, count);
1022                         }
1023
1024                         public override void AddRange(ICollection c)
1025                         {
1026                                 m_InnerArrayList.AddRange(c);
1027                         }
1028
1029                         public override int BinarySearch(object value)
1030                         {
1031                                 return m_InnerArrayList.BinarySearch(value);
1032                         }
1033
1034                         public override int BinarySearch(object value, IComparer comparer)
1035                         {
1036                                 return m_InnerArrayList.BinarySearch(value, comparer);
1037                         }
1038
1039                         public override int BinarySearch(int index, int count, object value, IComparer comparer)
1040                         {
1041                                 return m_InnerArrayList.BinarySearch(index, count, value, comparer);
1042                         }
1043
1044                         public override object Clone()
1045                         {
1046                                 return m_InnerArrayList.Clone();
1047                         }
1048
1049                         public override ArrayList GetRange(int index, int count)
1050                         {
1051                                 return m_InnerArrayList.GetRange(index, count);
1052                         }
1053
1054                         public override void TrimToSize()
1055                         {
1056                                 m_InnerArrayList.TrimToSize();
1057                         }
1058
1059                         public override void Sort()
1060                         {
1061                                 m_InnerArrayList.Sort();
1062                         }
1063
1064                         public override void Sort(IComparer comparer)
1065                         {
1066                                 m_InnerArrayList.Sort(comparer);
1067                         }
1068
1069                         public override void Sort(int index, int count, IComparer comparer)
1070                         {
1071                                 m_InnerArrayList.Sort(index, count, comparer);
1072                         }
1073
1074                         public override object[] ToArray()
1075                         {
1076                                 return m_InnerArrayList.ToArray();
1077                         }
1078
1079                         public override Array ToArray(Type elementType)
1080                         {
1081                                 return m_InnerArrayList.ToArray(elementType);
1082                         }
1083
1084                         #endregion
1085                 }
1086
1087                 #endregion
1088
1089                 #region SynchronizedArrayListWrapper
1090
1091                 /// <summary>
1092                 /// ArrayListWrapper that synchronizes calls to all methods/properties.
1093                 /// </summary>
1094                 /// <remarks>
1095                 /// Works by just synchronizing all method calls.  In the future careful optimisation
1096                 /// could give better performance...
1097                 /// </remarks>
1098                 [Serializable]
1099                 private sealed class SynchronizedArrayListWrapper
1100                         : ArrayListWrapper
1101                 {
1102                         private object m_SyncRoot;
1103
1104                         #region Constructors
1105
1106                         /// <summary>
1107                         /// Creates a new synchronized wrapper for the given <see cref="ArrayList"/>.
1108                         /// </summary>
1109                         /// <param name="innerArrayList"></param>
1110                         internal SynchronizedArrayListWrapper(ArrayList innerArrayList)
1111                                 : base(innerArrayList)
1112                         {
1113                                 m_SyncRoot = innerArrayList.SyncRoot;
1114                         }
1115
1116                         #endregion
1117
1118                         #region Indexers
1119
1120                         public override object this[int index]
1121                         {
1122                                 get
1123                                 {
1124                                         lock (m_SyncRoot)
1125                                         {
1126                                                 return m_InnerArrayList[index];
1127                                         }
1128                                 }
1129
1130                                 set
1131                                 {
1132                                         lock (m_SyncRoot)
1133                                         {
1134                                                 m_InnerArrayList[index] = value;
1135                                         }
1136                                 }
1137                         }
1138
1139                         #endregion
1140
1141                         #region Properties
1142
1143                         // Some of these properties may be calculated so it's best to synchronize
1144                         // them even though it might cause a performance hit.
1145                         // Better safe than sorry ;D.
1146
1147                         public override int Count
1148                         {
1149                                 get
1150                                 {
1151                                         lock (m_SyncRoot)
1152                                         {
1153                                                 return m_InnerArrayList.Count;
1154                                         }
1155                                 }
1156                         }
1157
1158                         public override int Capacity
1159                         {
1160                                 get
1161                                 {
1162                                         lock (m_SyncRoot)
1163                                         {
1164                                                 return m_InnerArrayList.Capacity;
1165                                         }
1166                                 }
1167
1168                                 set
1169                                 {
1170                                         lock (m_SyncRoot)
1171                                         {
1172                                                 m_InnerArrayList.Capacity = value;
1173                                         }
1174                                 }
1175                         }
1176
1177                         public override bool IsFixedSize
1178                         {
1179                                 get
1180                                 {
1181                                         lock (m_SyncRoot)
1182                                         {
1183                                                 return m_InnerArrayList.IsFixedSize;
1184                                         }
1185                                 }
1186                         }
1187
1188                         public override bool IsReadOnly
1189                         {
1190                                 get
1191                                 {
1192                                         lock (m_SyncRoot)
1193                                         {
1194                                                 return m_InnerArrayList.IsReadOnly;
1195                                         }
1196                                 }
1197                         }
1198
1199                         public override bool IsSynchronized
1200                         {
1201                                 get
1202                                 {
1203                                         return true;
1204                                 }
1205                         }
1206
1207                         public override object SyncRoot
1208                         {
1209                                 get
1210                                 {
1211                                         return m_SyncRoot;
1212                                 }
1213                         }
1214
1215                         #endregion
1216
1217                         #region Methods
1218
1219                         public override int Add(object value)
1220                         {
1221                                 lock (m_SyncRoot)
1222                                 {
1223                                         return m_InnerArrayList.Add(value);
1224                                 }
1225                         }
1226
1227                         public override void Clear()
1228                         {
1229                                 lock (m_SyncRoot)
1230                                 {
1231                                         m_InnerArrayList.Clear();
1232                                 }
1233                         }
1234
1235                         public override bool Contains(object value)
1236                         {
1237                                 lock (m_SyncRoot)
1238                                 {
1239                                         return m_InnerArrayList.Contains(value);
1240                                 }
1241                         }
1242
1243                         public override int IndexOf(object value)
1244                         {
1245                                 lock (m_SyncRoot)
1246                                 {
1247                                         return m_InnerArrayList.IndexOf(value);
1248                                 }
1249                         }
1250
1251                         public override int IndexOf(object value, int startIndex)
1252                         {
1253                                 lock (m_SyncRoot)
1254                                 {
1255                                         return m_InnerArrayList.IndexOf(value, startIndex);
1256                                 }
1257                         }
1258
1259                         public override int IndexOf(object value, int startIndex, int count)
1260                         {
1261                                 lock (m_SyncRoot)
1262                                 {
1263                                         return m_InnerArrayList.IndexOf(value, startIndex, count);
1264                                 }
1265                         }
1266
1267                         public override int LastIndexOf(object value)
1268                         {
1269                                 lock (m_SyncRoot)
1270                                 {
1271                                         return m_InnerArrayList.LastIndexOf(value);
1272                                 }
1273                         }
1274
1275                         public override int LastIndexOf(object value, int startIndex)
1276                         {
1277                                 lock (m_SyncRoot)
1278                                 {
1279                                         return m_InnerArrayList.LastIndexOf(value, startIndex);
1280                                 }
1281                         }
1282
1283                         public override int LastIndexOf(object value, int startIndex, int count)
1284                         {
1285                                 lock (m_SyncRoot)
1286                                 {
1287                                         return m_InnerArrayList.LastIndexOf(value, startIndex, count);
1288                                 }
1289                         }
1290
1291                         public override void Insert(int index, object value)
1292                         {
1293                                 lock (m_SyncRoot)
1294                                 {
1295                                         m_InnerArrayList.Insert(index, value);
1296                                 }
1297                         }
1298
1299                         public override void InsertRange(int index, ICollection c)
1300                         {
1301                                 lock (m_SyncRoot)
1302                                 {
1303                                         m_InnerArrayList.InsertRange(index, c);
1304                                 }
1305                         }
1306
1307                         public override void Remove(object value)
1308                         {
1309                                 lock (m_SyncRoot)
1310                                 {
1311                                         m_InnerArrayList.Remove(value);
1312                                 }
1313                         }
1314
1315                         public override void RemoveAt(int index)
1316                         {
1317                                 lock (m_SyncRoot)
1318                                 {
1319                                         m_InnerArrayList.RemoveAt(index);
1320                                 }
1321                         }
1322
1323                         public override void RemoveRange(int index, int count)
1324                         {
1325                                 lock (m_SyncRoot)
1326                                 {
1327                                         m_InnerArrayList.RemoveRange(index, count);
1328                                 }
1329                         }
1330
1331                         public override void Reverse()
1332                         {
1333                                 lock (m_SyncRoot)
1334                                 {
1335                                         m_InnerArrayList.Reverse();
1336                                 }
1337                         }
1338
1339                         public override void Reverse(int index, int count)
1340                         {
1341                                 lock (m_SyncRoot)
1342                                 {
1343                                         m_InnerArrayList.Reverse(index, count);
1344                                 }
1345                         }
1346
1347                         public override void CopyTo(System.Array array)
1348                         {
1349                                 lock (m_SyncRoot)
1350                                 {
1351                                         m_InnerArrayList.CopyTo(array);
1352                                 }
1353                         }
1354
1355                         public override void CopyTo(System.Array array, int index)
1356                         {
1357                                 lock (m_SyncRoot)
1358                                 {
1359                                         m_InnerArrayList.CopyTo(array, index);
1360                                 }
1361                         }
1362
1363                         public override void CopyTo(int index, System.Array array, int arrayIndex, int count)
1364                         {
1365                                 lock (m_SyncRoot)
1366                                 {
1367                                         m_InnerArrayList.CopyTo(index, array, arrayIndex, count);
1368                                 }
1369                         }
1370
1371                         public override IEnumerator GetEnumerator()
1372                         {
1373                                 lock (m_SyncRoot)
1374                                 {
1375                                         return m_InnerArrayList.GetEnumerator();
1376                                 }
1377                         }
1378
1379                         public override IEnumerator GetEnumerator(int index, int count)
1380                         {
1381                                 lock (m_SyncRoot)
1382                                 {
1383                                         return m_InnerArrayList.GetEnumerator(index, count);
1384                                 }
1385                         }
1386
1387                         public override void AddRange(ICollection c)
1388                         {
1389                                 lock (m_SyncRoot)
1390                                 {
1391                                         m_InnerArrayList.AddRange(c);
1392                                 }
1393                         }
1394
1395                         public override int BinarySearch(object value)
1396                         {
1397                                 lock (m_SyncRoot)
1398                                 {
1399                                         return m_InnerArrayList.BinarySearch(value);
1400                                 }
1401                         }
1402
1403                         public override int BinarySearch(object value, IComparer comparer)
1404                         {
1405                                 lock (m_SyncRoot)
1406                                 {
1407                                         return m_InnerArrayList.BinarySearch(value, comparer);
1408                                 }
1409                         }
1410
1411                         public override int BinarySearch(int index, int count, object value, IComparer comparer)
1412                         {
1413                                 lock (m_SyncRoot)
1414                                 {
1415                                         return m_InnerArrayList.BinarySearch(index, count, value, comparer);
1416                                 }
1417                         }
1418
1419                         public override object Clone()
1420                         {
1421                                 lock (m_SyncRoot)
1422                                 {
1423                                         return m_InnerArrayList.Clone();
1424                                 }
1425                         }
1426
1427                         public override ArrayList GetRange(int index, int count)
1428                         {
1429                                 lock (m_SyncRoot)
1430                                 {
1431                                         return m_InnerArrayList.GetRange(index, count);
1432                                 }
1433                         }
1434
1435                         public override void TrimToSize()
1436                         {
1437                                 lock (m_SyncRoot)
1438                                 {
1439                                         m_InnerArrayList.TrimToSize();
1440                                 }
1441                         }
1442
1443                         public override void Sort()
1444                         {
1445                                 lock (m_SyncRoot)
1446                                 {
1447                                         m_InnerArrayList.Sort();
1448                                 }
1449                         }
1450
1451                         public override void Sort(IComparer comparer)
1452                         {
1453                                 lock (m_SyncRoot)
1454                                 {
1455                                         m_InnerArrayList.Sort(comparer);
1456                                 }
1457                         }
1458
1459                         public override void Sort(int index, int count, IComparer comparer)
1460                         {
1461                                 lock (m_SyncRoot)
1462                                 {
1463                                         m_InnerArrayList.Sort(index, count, comparer);
1464                                 }
1465                         }
1466
1467                         public override object[] ToArray()
1468                         {
1469                                 lock (m_SyncRoot)
1470                                 {
1471                                         return m_InnerArrayList.ToArray();
1472                                 }
1473                         }
1474
1475                         public override Array ToArray(Type elementType)
1476                         {
1477                                 lock (m_SyncRoot)
1478                                 {
1479                                         return m_InnerArrayList.ToArray(elementType);
1480                                 }
1481                         }
1482
1483                         #endregion
1484                 }
1485
1486                 #endregion
1487
1488                 #region FixedSizeArrayListWrapper
1489
1490                 [Serializable]
1491                 private class FixedSizeArrayListWrapper
1492                         : ArrayListWrapper
1493                 {
1494                         #region Constructors
1495
1496                         public FixedSizeArrayListWrapper(ArrayList innerList)
1497                                 : base(innerList)
1498                         {
1499                         }
1500
1501                         #endregion
1502
1503                         #region Properties
1504
1505                         /// <summary>
1506                         /// Gets the error message to display when an readonly/fixedsize related exception is
1507                         /// thrown.
1508                         /// </summary>
1509                         protected virtual string ErrorMessage
1510                         {
1511                                 get
1512                                 {
1513                                         return "Can't add or remove from a fixed-size list.";
1514                                 }
1515                         }
1516
1517                         public override int Capacity
1518                         {
1519                                 get
1520                                 {
1521                                         return base.Capacity;
1522                                 }
1523
1524                                 set
1525                                 {
1526                                         throw new NotSupportedException(this.ErrorMessage);
1527                                 }
1528                         }
1529
1530                         public override bool IsFixedSize
1531                         {
1532                                 get
1533                                 {
1534                                         return true;
1535                                 }
1536                         }
1537
1538                         #endregion
1539
1540                         #region Methods
1541
1542                         public override int Add(object value)
1543                         {
1544                                 throw new NotSupportedException(this.ErrorMessage);
1545                         }
1546
1547                         public override void AddRange(ICollection c)
1548                         {
1549                                 throw new NotSupportedException(this.ErrorMessage);
1550                         }
1551
1552                         public override void Clear()
1553                         {
1554                                 throw new NotSupportedException(this.ErrorMessage);
1555                         }
1556
1557                         public override void Insert(int index, object value)
1558                         {
1559                                 throw new NotSupportedException(this.ErrorMessage);
1560                         }
1561
1562                         public override void InsertRange(int index, ICollection c)
1563                         {
1564                                 throw new NotSupportedException(this.ErrorMessage);
1565                         }
1566
1567                         public override void Remove(object value)
1568                         {
1569                                 throw new NotSupportedException(this.ErrorMessage);
1570                         }
1571
1572                         public override void RemoveAt(int index)
1573                         {
1574                                 throw new NotSupportedException(this.ErrorMessage);
1575                         }
1576
1577                         public override void RemoveRange(int index, int count)
1578                         {
1579                                 throw new NotSupportedException(this.ErrorMessage);
1580                         }
1581
1582                         public override void TrimToSize()
1583                         {
1584                                 throw new NotSupportedException(this.ErrorMessage);
1585                         }
1586
1587                         #endregion
1588                 }
1589
1590                 #endregion
1591
1592                 #region ReadOnlyArrayListWrapper
1593
1594                 [Serializable]
1595                 private sealed class ReadOnlyArrayListWrapper
1596                         : FixedSizeArrayListWrapper
1597                 {
1598                         protected override string ErrorMessage
1599                         {
1600                                 get
1601                                 {
1602                                         return "Can't modify a readonly list.";
1603                                 }
1604                         }
1605
1606                         public override bool IsReadOnly
1607                         {
1608                                 get
1609                                 {
1610                                         return true;
1611                                 }
1612                         }
1613
1614                         public ReadOnlyArrayListWrapper(ArrayList innerArrayList)
1615                                 : base(innerArrayList)
1616                         {
1617                         }
1618
1619                         public override object this[int index]
1620                         {
1621                                 get
1622                                 {
1623                                         return m_InnerArrayList[index];
1624                                 }
1625
1626                                 set
1627                                 {
1628                                         throw new NotSupportedException(this.ErrorMessage);
1629                                 }
1630                         }
1631
1632                         public override void Reverse()
1633                         {
1634                                 throw new NotSupportedException(this.ErrorMessage);
1635                         }
1636
1637                         public override void Reverse(int index, int count)
1638                         {
1639                                 throw new NotSupportedException(this.ErrorMessage);
1640                         }
1641
1642                         public override void SetRange(int index, ICollection c)
1643                         {
1644                                 throw new NotSupportedException(this.ErrorMessage);
1645                         }
1646
1647                         public override void Sort()
1648                         {
1649                                 throw new NotSupportedException(this.ErrorMessage);
1650                         }
1651
1652                         public override void Sort(IComparer comparer)
1653                         {
1654                                 throw new NotSupportedException(this.ErrorMessage);
1655                         }
1656
1657                         public override void Sort(int index, int count, IComparer comparer)
1658                         {
1659                                 throw new NotSupportedException(this.ErrorMessage);
1660                         }
1661                 }
1662
1663                 #endregion
1664
1665                 #region RangedArrayList
1666
1667                 [Serializable]
1668                 private sealed class RangedArrayList
1669                         : ArrayListWrapper
1670                 {
1671                         private int m_InnerIndex;
1672                         private int m_InnerCount;
1673                         private int m_InnerStateChanges;
1674
1675                         public RangedArrayList(ArrayList innerList, int index, int count)
1676                                 : base(innerList)
1677                         {
1678                                 m_InnerIndex = index;
1679                                 m_InnerCount = count;
1680                                 m_InnerStateChanges = innerList._version;
1681                         }
1682
1683                         #region Indexers
1684
1685                         public override bool IsSynchronized
1686                         {
1687                                 get
1688                                 {
1689                                         return false;
1690                                 }
1691                         }
1692
1693                         public override object this[int index]
1694                         {
1695                                 get
1696                                 {
1697                                         if (index < 0 || index > m_InnerCount)
1698                                         {
1699                                                 throw new ArgumentOutOfRangeException("index");
1700                                         }
1701
1702                                         return m_InnerArrayList[m_InnerIndex + index];
1703                                 }
1704
1705                                 set
1706                                 {
1707                                         if (index < 0 || index > m_InnerCount)
1708                                         {
1709                                                 throw new ArgumentOutOfRangeException("index");
1710                                         }
1711
1712                                         m_InnerArrayList[m_InnerIndex + index] = value;
1713                                 }
1714                         }
1715
1716                         #endregion
1717
1718                         #region Properties
1719
1720                         public override int Count
1721                         {
1722                                 get
1723                                 {
1724                                         VerifyStateChanges();
1725
1726                                         return m_InnerCount;
1727                                 }
1728                         }
1729
1730                         public override int Capacity
1731                         {
1732                                 get
1733                                 {
1734                                         return m_InnerArrayList.Capacity;
1735                                 }
1736
1737                                 set
1738                                 {
1739                                         if (value < m_InnerCount)
1740                                         {
1741                                                 throw new ArgumentOutOfRangeException();
1742                                         }
1743                                 }
1744                         }
1745
1746                         #endregion
1747
1748                         #region Methods
1749
1750                         private void VerifyStateChanges()
1751                         {
1752                                 if (m_InnerStateChanges != m_InnerArrayList._version)
1753                                 {
1754                                         throw new InvalidOperationException
1755                                                 ("ArrayList view is invalid because the underlying ArrayList was modified.");
1756                                 }
1757                         }
1758
1759                         public override int Add(object value)
1760                         {
1761                                 VerifyStateChanges();
1762
1763                                 m_InnerArrayList.Insert(m_InnerIndex + m_InnerCount, value);
1764
1765                                 m_InnerStateChanges = m_InnerArrayList._version;
1766
1767                                 return ++m_InnerCount;
1768                         }
1769
1770                         public override void Clear()
1771                         {
1772                                 VerifyStateChanges();
1773
1774                                 m_InnerArrayList.RemoveRange(m_InnerIndex, m_InnerCount);
1775                                 m_InnerCount = 0;
1776
1777                                 m_InnerStateChanges = m_InnerArrayList._version;
1778                         }
1779
1780                         public override bool Contains(object value)
1781                         {
1782                                 return m_InnerArrayList.Contains(value, m_InnerIndex, m_InnerCount);
1783                         }
1784
1785                         public override int IndexOf(object value)
1786                         {
1787                                 return IndexOf(value, 0);
1788                         }
1789
1790                         public override int IndexOf(object value, int startIndex)
1791                         {
1792                                 return IndexOf(value, startIndex, m_InnerCount - startIndex);
1793                         }
1794
1795                         public override int IndexOf(object value, int startIndex, int count)
1796                         {
1797                                 if (startIndex < 0 || startIndex > m_InnerCount)
1798                                 {
1799                                         ThrowNewArgumentOutOfRangeException ("startIndex", startIndex,
1800                                                 "Does not specify valid index.");
1801                                 }
1802
1803                                 if (count < 0)
1804                                 {
1805                                         ThrowNewArgumentOutOfRangeException ("count", count,
1806                                                 "Can't be less than 0.");
1807                                 }
1808
1809                                 // re-ordered to avoid possible integer overflow
1810                                 if (startIndex > m_InnerCount - count)
1811                                 {
1812                                         // LAMESPEC: Every other method throws ArgumentException
1813
1814                                         throw new ArgumentOutOfRangeException("count",
1815                                                 "Start index and count do not specify a valid range.");
1816                                 }
1817
1818                                 int retval = m_InnerArrayList.IndexOf(value, m_InnerIndex + startIndex, count);
1819
1820                                 if (retval == -1)
1821                                 {
1822                                         return -1;
1823                                 }
1824                                 else
1825                                 {
1826                                         return retval - m_InnerIndex;
1827                                 }
1828                         }
1829
1830                         public override int LastIndexOf(object value)
1831                         {
1832                                 return LastIndexOf(value, m_InnerCount - 1);
1833                         }
1834
1835                         public override int LastIndexOf(object value, int startIndex)
1836                         {
1837                                 return LastIndexOf(value, startIndex, startIndex + 1);
1838                         }
1839
1840                         public override int LastIndexOf(object value, int startIndex, int count)
1841                         {
1842                                 if (startIndex < 0)
1843                                 {
1844                                         ThrowNewArgumentOutOfRangeException ("startIndex", startIndex,  "< 0");
1845                                 }
1846
1847                                 if (count < 0)
1848                                 {
1849                                         ThrowNewArgumentOutOfRangeException ("count", count, "count is negative.");
1850                                 }
1851
1852                                 int retval = m_InnerArrayList.LastIndexOf(value, m_InnerIndex + startIndex, count);
1853
1854                                 if (retval == -1)
1855                                 {
1856                                         return -1;
1857                                 }
1858                                 else
1859                                 {
1860                                         return retval - m_InnerIndex;
1861                                 }
1862                         }
1863
1864                         public override void Insert(int index, object value)
1865                         {
1866                                 VerifyStateChanges();
1867
1868                                 if (index < 0 || index > m_InnerCount)
1869                                 {
1870                                         ThrowNewArgumentOutOfRangeException ("index", index,
1871                                                 "Index must be >= 0 and <= Count.");
1872                                 }
1873
1874                                 m_InnerArrayList.Insert(m_InnerIndex + index, value);
1875
1876                                 m_InnerCount++;
1877
1878                                 m_InnerStateChanges = m_InnerArrayList._version;
1879                         }
1880
1881                         public override void InsertRange(int index, ICollection c)
1882                         {
1883                                 VerifyStateChanges();
1884
1885                                 if (index < 0 || index > m_InnerCount)
1886                                 {
1887                                         ThrowNewArgumentOutOfRangeException ("index", index,
1888                                                 "Index must be >= 0 and <= Count.");
1889                                 }
1890
1891                                 m_InnerArrayList.InsertRange(m_InnerIndex + index, c);
1892
1893                                 m_InnerCount += c.Count;
1894
1895                                 m_InnerStateChanges = m_InnerArrayList._version;
1896                         }
1897
1898                         public override void Remove(object value)
1899                         {
1900                                 VerifyStateChanges();
1901
1902                                 int x = IndexOf(value);
1903
1904                                 if (x > -1)
1905                                 {
1906                                         RemoveAt(x);
1907                                 }
1908
1909                                 m_InnerStateChanges = m_InnerArrayList._version;
1910                         }
1911
1912                         public override void RemoveAt(int index)
1913                         {
1914                                 VerifyStateChanges();
1915
1916                                 if (index < 0 || index > m_InnerCount)
1917                                 {
1918                                         ThrowNewArgumentOutOfRangeException ("index", index,
1919                                                 "Index must be >= 0 and <= Count.");
1920                                 }
1921
1922                                 m_InnerArrayList.RemoveAt(m_InnerIndex + index);
1923
1924                                 m_InnerCount--;
1925                                 m_InnerStateChanges = m_InnerArrayList._version;
1926                         }
1927
1928                         public override void RemoveRange(int index, int count)
1929                         {
1930                                 VerifyStateChanges();
1931
1932                                 CheckRange(index, count, m_InnerCount);
1933
1934                                 m_InnerArrayList.RemoveRange(m_InnerIndex + index, count);
1935
1936                                 m_InnerCount -= count;
1937
1938                                 m_InnerStateChanges = m_InnerArrayList._version;
1939                         }
1940
1941                         public override void Reverse()
1942                         {
1943                                 Reverse(0, m_InnerCount);
1944                         }
1945
1946                         public override void Reverse(int index, int count)
1947                         {
1948                                 VerifyStateChanges();
1949
1950                                 CheckRange(index, count, m_InnerCount);
1951
1952                                 m_InnerArrayList.Reverse(m_InnerIndex + index, count);
1953
1954                                 m_InnerStateChanges = m_InnerArrayList._version;
1955                         }
1956
1957                         public override void SetRange(int index, ICollection c)
1958                         {
1959                                 VerifyStateChanges();
1960
1961                                 if (index < 0 || index > m_InnerCount)
1962                                 {
1963                                         ThrowNewArgumentOutOfRangeException ("index", index,
1964                                                 "Index must be >= 0 and <= Count.");
1965                                 }
1966
1967                                 m_InnerArrayList.SetRange(m_InnerIndex + index, c);
1968
1969                                 m_InnerStateChanges = m_InnerArrayList._version;
1970                         }
1971
1972                         public override void CopyTo(System.Array array)
1973                         {
1974                                 CopyTo(array, 0);
1975                         }
1976
1977                         public override void CopyTo(System.Array array, int index)
1978                         {
1979                                 CopyTo(0, array, index, m_InnerCount);
1980                         }
1981
1982                         public override void CopyTo(int index, System.Array array, int arrayIndex, int count)
1983                         {
1984                                 CheckRange(index, count, m_InnerCount);
1985
1986                                 m_InnerArrayList.CopyTo(m_InnerIndex + index, array, arrayIndex, count);
1987                         }
1988
1989                         public override IEnumerator GetEnumerator()
1990                         {
1991                                 return GetEnumerator(0, m_InnerCount);
1992                         }
1993
1994                         public override IEnumerator GetEnumerator(int index, int count)
1995                         {
1996                                 CheckRange(index, count, m_InnerCount);
1997
1998                                 return m_InnerArrayList.GetEnumerator(m_InnerIndex + index, count);
1999                         }
2000
2001                         public override void AddRange(ICollection c)
2002                         {
2003                                 VerifyStateChanges();
2004
2005                                 m_InnerArrayList.InsertRange(m_InnerCount, c);
2006
2007                                 m_InnerCount += c.Count;
2008
2009                                 m_InnerStateChanges = m_InnerArrayList._version;
2010                         }
2011
2012                         public override int BinarySearch(object value)
2013                         {
2014                                 return BinarySearch(0, m_InnerCount, value, Comparer.Default);
2015                         }
2016
2017                         public override int BinarySearch(object value, IComparer comparer)
2018                         {
2019                                 return BinarySearch(0, m_InnerCount, value, comparer);
2020                         }
2021
2022                         public override int BinarySearch(int index, int count, object value, IComparer comparer)
2023                         {
2024                                 CheckRange(index, count, m_InnerCount);
2025
2026                                 return m_InnerArrayList.BinarySearch(m_InnerIndex + index, count, value, comparer);
2027                         }
2028
2029                         public override object Clone()
2030                         {
2031                                 return new RangedArrayList((ArrayList)m_InnerArrayList.Clone(), m_InnerIndex, m_InnerCount);
2032                         }
2033
2034                         public override ArrayList GetRange(int index, int count)
2035                         {
2036                                 CheckRange(index, count, m_InnerCount);
2037
2038                                 return new RangedArrayList(this, index, count);
2039                         }
2040
2041                         public override void TrimToSize()
2042                         {
2043                                 throw new NotSupportedException();
2044                         }
2045
2046                         public override void Sort()
2047                         {
2048                                 Sort(Comparer.Default);
2049                         }
2050
2051                         public override void Sort(IComparer comparer)
2052                         {
2053                                 Sort(0, m_InnerCount, comparer);
2054                         }
2055
2056                         public override void Sort(int index, int count, IComparer comparer)
2057                         {
2058                                 VerifyStateChanges();
2059
2060                                 CheckRange(index, count, m_InnerCount);
2061
2062                                 m_InnerArrayList.Sort(m_InnerIndex + index, count, comparer);
2063
2064                                 m_InnerStateChanges = m_InnerArrayList._version;
2065                         }
2066
2067                         public override object[] ToArray()
2068                         {
2069                                 object[] array;
2070
2071                                 array = new object[m_InnerCount];
2072
2073                                 m_InnerArrayList.CopyTo (m_InnerIndex, array, 0, m_InnerCount);
2074
2075                                 return array;
2076                         }
2077
2078                         public override Array ToArray(Type elementType)
2079                         {
2080                                 Array array;
2081
2082                                 array = Array.CreateInstance(elementType, m_InnerCount);
2083
2084                                 m_InnerArrayList.CopyTo(m_InnerIndex, array, 0, m_InnerCount);
2085
2086                                 return array;
2087                         }
2088
2089                         #endregion
2090                 }
2091
2092                 #endregion
2093
2094                 //
2095                 // List wrappers
2096                 //
2097
2098                 #region SynchronizedListWrapper
2099
2100                 [Serializable]
2101                 private sealed class SynchronizedListWrapper
2102                         : ListWrapper
2103                 {
2104                         private object m_SyncRoot;
2105
2106                         public SynchronizedListWrapper(IList innerList)
2107                                 : base(innerList)
2108                         {
2109                                 m_SyncRoot = innerList.SyncRoot;
2110                         }
2111
2112                         public override int Count
2113                         {
2114                                 get
2115                                 {
2116                                         lock (m_SyncRoot)
2117                                         {
2118                                                 return m_InnerList.Count;
2119                                         }
2120                                 }
2121                         }
2122
2123                         public override bool IsSynchronized
2124                         {
2125                                 get
2126                                 {
2127                                         return true;
2128                                 }
2129                         }
2130
2131                         public override object SyncRoot
2132                         {
2133                                 get
2134                                 {
2135                                         lock (m_SyncRoot)
2136                                         {
2137                                                 return m_InnerList.SyncRoot;
2138                                         }
2139                                 }
2140                         }
2141
2142                         public override bool IsFixedSize
2143                         {
2144                                 get
2145                                 {
2146                                         lock (m_SyncRoot)
2147                                         {
2148                                                 return m_InnerList.IsFixedSize;
2149                                         }
2150                                 }
2151                         }
2152
2153                         public override bool IsReadOnly
2154                         {
2155                                 get
2156                                 {
2157                                         lock (m_SyncRoot)
2158                                         {
2159                                                 return m_InnerList.IsReadOnly;
2160                                         }
2161                                 }
2162                         }
2163
2164                         public override object this[int index]
2165                         {
2166                                 get
2167                                 {
2168                                         lock (m_SyncRoot)
2169                                         {
2170                                                 return m_InnerList[index];
2171                                         }
2172                                 }
2173
2174                                 set
2175                                 {
2176                                         lock (m_SyncRoot)
2177                                         {
2178                                                 m_InnerList[index] = value;
2179                                         }
2180                                 }
2181                         }
2182
2183                         public override int Add(object value)
2184                         {
2185                                 lock (m_SyncRoot)
2186                                 {
2187                                         return m_InnerList.Add(value);
2188                                 }
2189                         }
2190
2191                         public override void Clear()
2192                         {
2193                                 lock (m_SyncRoot)
2194                                 {
2195                                         m_InnerList.Clear();
2196                                 }
2197                         }
2198
2199                         public override bool Contains(object value)
2200                         {
2201                                 lock (m_SyncRoot)
2202                                 {
2203                                         return m_InnerList.Contains(value);
2204                                 }
2205                         }
2206
2207                         public override int IndexOf(object value)
2208                         {
2209                                 lock (m_SyncRoot)
2210                                 {
2211                                         return m_InnerList.IndexOf(value);
2212                                 }
2213                         }
2214
2215                         public override void Insert(int index, object value)
2216                         {
2217                                 lock (m_SyncRoot)
2218                                 {
2219                                         m_InnerList.Insert(index, value);
2220                                 }
2221                         }
2222
2223                         public override void Remove(object value)
2224                         {
2225                                 lock (m_SyncRoot)
2226                                 {
2227                                         m_InnerList.Remove(value);
2228                                 }
2229                         }
2230
2231                         public override void RemoveAt(int index)
2232                         {
2233                                 lock (m_SyncRoot)
2234                                 {
2235                                         m_InnerList.RemoveAt(index);
2236                                 }
2237                         }
2238
2239                         public override void CopyTo(Array array, int index)
2240                         {
2241                                 lock (m_SyncRoot)
2242                                 {
2243                                         m_InnerList.CopyTo(array, index);
2244                                 }
2245                         }
2246
2247                         public override IEnumerator GetEnumerator()
2248                         {
2249                                 lock (m_SyncRoot)
2250                                 {
2251                                         return m_InnerList.GetEnumerator();
2252                                 }
2253                         }
2254                 }
2255
2256                 #endregion
2257
2258                 #region FixedSizeListWrapper
2259
2260                 [Serializable]
2261                         private class FixedSizeListWrapper
2262                         : ListWrapper
2263                 {
2264                         protected virtual string ErrorMessage
2265                         {
2266                                 get
2267                                 {
2268                                         return "List is fixed-size.";
2269                                 }
2270                         }
2271
2272                         public override bool IsFixedSize
2273                         {
2274                                 get
2275                                 {
2276                                         return true;
2277                                 }
2278                         }
2279
2280                         public FixedSizeListWrapper(IList innerList)
2281                                 : base(innerList)
2282                         {
2283                         }
2284
2285                         public override int Add(object value)
2286                         {
2287                                 throw new NotSupportedException(this.ErrorMessage);
2288                         }
2289
2290                         public override void Clear()
2291                         {
2292                                 throw new NotSupportedException(this.ErrorMessage);
2293                         }
2294
2295                         public override void Insert(int index, object value)
2296                         {
2297                                 throw new NotSupportedException(this.ErrorMessage);
2298                         }
2299
2300                         public override void Remove(object value)
2301                         {
2302                                 throw new NotSupportedException(this.ErrorMessage);
2303                         }
2304
2305                         public override void RemoveAt(int index)
2306                         {
2307                                 throw new NotSupportedException(this.ErrorMessage);
2308                         }
2309                 }
2310
2311                 #endregion
2312
2313                 #region ReadOnlyListWrapper
2314
2315                 [Serializable]
2316                 private sealed class ReadOnlyListWrapper
2317                         : FixedSizeListWrapper
2318                 {
2319                         protected override string ErrorMessage
2320                         {
2321                                 get
2322                                 {
2323                                         return "List is read-only.";
2324                                 }
2325                         }
2326
2327                         public override bool IsReadOnly
2328                         {
2329                                 get
2330                                 {
2331                                         return true;
2332                                 }
2333                         }
2334
2335                         public ReadOnlyListWrapper(IList innerList)
2336                                 : base(innerList)
2337                         {
2338                         }
2339
2340                         public override object this[int index]
2341                         {
2342                                 get
2343                                 {
2344                                         return m_InnerList[index];
2345                                 }
2346
2347                                 set
2348                                 {
2349                                         throw new NotSupportedException(this.ErrorMessage);
2350                                 }
2351                         }
2352                 }
2353
2354                 #endregion
2355
2356                 #region ListWrapper
2357
2358                 /// <summary>
2359                 /// Decorates/Wraps any <c>IList</c> implementing object.
2360                 /// </summary>
2361                 [Serializable]
2362                 private class ListWrapper
2363                         : IList
2364                 {
2365                         #region Fields
2366
2367                         protected IList m_InnerList;
2368
2369                         #endregion
2370
2371                         #region Constructors
2372
2373                         public ListWrapper(IList innerList)
2374                         {
2375                                 m_InnerList = innerList;
2376                         }
2377
2378                         #endregion
2379
2380                         #region Indexers
2381
2382                         public virtual object this[int index]
2383                         {
2384                                 get
2385                                 {
2386                                         return m_InnerList[index];
2387                                 }
2388
2389                                 set
2390                                 {
2391                                         m_InnerList[index] = value;
2392                                 }
2393                         }
2394
2395                         #endregion
2396
2397                         #region Properties
2398
2399                         public virtual int Count
2400                         {
2401                                 get
2402                                 {
2403                                         return m_InnerList.Count;
2404                                 }
2405                         }
2406
2407                         public virtual bool IsSynchronized
2408                         {
2409                                 get
2410                                 {
2411                                         return m_InnerList.IsSynchronized;
2412                                 }
2413                         }
2414
2415                         public virtual object SyncRoot
2416                         {
2417                                 get
2418                                 {
2419                                         return m_InnerList.SyncRoot;
2420                                 }
2421                         }
2422
2423                         public virtual bool IsFixedSize
2424                         {
2425                                 get
2426                                 {
2427                                         return m_InnerList.IsFixedSize;
2428                                 }
2429                         }
2430
2431                         public virtual bool IsReadOnly
2432                         {
2433                                 get
2434                                 {
2435                                         return m_InnerList.IsReadOnly;
2436                                 }
2437                         }
2438
2439                         #endregion
2440
2441                         #region Methods
2442
2443                         public virtual int Add(object value)
2444                         {
2445                                 return m_InnerList.Add(value);
2446                         }
2447
2448                         public virtual void Clear()
2449                         {
2450                                 m_InnerList.Clear();
2451                         }
2452
2453                         public virtual bool Contains(object value)
2454                         {
2455                                 return m_InnerList.Contains(value);
2456                         }
2457
2458                         public virtual int IndexOf(object value)
2459                         {
2460                                 return m_InnerList.IndexOf(value);
2461                         }
2462
2463                         public virtual void Insert(int index, object value)
2464                         {
2465                                 m_InnerList.Insert(index, value);
2466                         }
2467
2468                         public virtual void Remove(object value)
2469                         {
2470                                 m_InnerList.Remove(value);
2471                         }
2472
2473                         public virtual void RemoveAt(int index)
2474                         {
2475                                 m_InnerList.RemoveAt(index);
2476                         }
2477
2478                         public virtual void CopyTo(Array array, int index)
2479                         {
2480                                 m_InnerList.CopyTo(array, index);
2481                         }
2482
2483                         public virtual IEnumerator GetEnumerator()
2484                         {
2485                                 return m_InnerList.GetEnumerator();
2486                         }
2487
2488                         #endregion
2489                 }
2490
2491                 #endregion
2492
2493                 //
2494                 // Start of ArrayList
2495                 //
2496
2497                 #region Fields
2498
2499                 private const int DefaultInitialCapacity = 4;
2500
2501                 /// <summary>
2502                 /// Number of items in the list.
2503                 /// </summary>
2504                 private int _size;
2505
2506                 /// <summary>
2507                 /// Array to store the items.
2508                 /// </summary>
2509                 private object[] _items;
2510
2511                 /// <summary>
2512                 /// Total number of state changes.
2513                 /// </summary>
2514                 private int _version;
2515
2516                 private static readonly object [] EmptyArray = new object [0];
2517
2518                 #endregion
2519
2520                 #region Constructors
2521
2522                 /// <summary>
2523                 /// Initializes a new instance of the <see cref="ArrayList"/> class that is empty and
2524                 /// has the default initial capacity (16).
2525                 /// </summary>
2526                 public ArrayList()
2527                 {
2528                         _items = EmptyArray;
2529                 }
2530
2531                 /// <summary>
2532                 /// Initializes a new instance of the <see cref="ArrayList"/> class that contains
2533                 /// elements copied from the specified collection and that has the same initial capacity
2534                 /// as the number of elements copied.
2535                 /// </summary>
2536                 /// <param name="c">
2537                 /// The <see cref="ICollection"/> whose elements are copied into the new list.
2538                 /// </param>
2539                 /// <exception cref="ArgumentNullException">
2540                 /// The argument <c>c</c> is a null reference.
2541                 /// </exception>
2542                 public ArrayList(ICollection c)
2543                 {
2544                         Array array;
2545
2546                         if (c == null)
2547                         {
2548                                 throw new ArgumentNullException("c");
2549                         }
2550
2551                         array = c as Array;
2552
2553                         if (array != null && array.Rank != 1)
2554                         {
2555                                 throw new RankException();
2556                         }
2557
2558                         _items = new object[c.Count];
2559
2560                         AddRange(c);
2561                 }
2562
2563                 /// <summary>
2564                 /// Initializes a new instance of the <see cref="ArrayList"/> class that is empty and
2565                 /// has the specified initial capacity.
2566                 /// </summary>
2567                 /// <param name="capacity">
2568                 /// The number of elements that hte new list is initially capable of storing.
2569                 /// </param>
2570                 /// <exception cref="ArgumentOutOfRangeException">
2571                 /// The <c>capacity</c> is less than zero.
2572                 /// </exception>
2573                 public ArrayList(int capacity)
2574                 {
2575                         if (capacity < 0)
2576                         {
2577                                 ThrowNewArgumentOutOfRangeException ("capacity",
2578                                         capacity, "The initial capacity can't be smaller than zero.");
2579                         }
2580
2581                         if (capacity == 0)
2582                         {
2583                                 capacity = DefaultInitialCapacity;
2584                         }
2585                         _items = new object [capacity];
2586                 }
2587
2588                 /// <summary>
2589                 /// Used by ArrayListAdapter to allow creation of an ArrayList with no storage buffer.
2590                 /// </summary>
2591                 private ArrayList(int initialCapacity, bool forceZeroSize)
2592                 {
2593                         if (forceZeroSize)
2594                         {
2595                                 _items = null;
2596                         }
2597                         else
2598                         {
2599                                 throw new InvalidOperationException("Use ArrayList(int)");
2600                         }
2601                 }
2602
2603                 /// <summary>
2604                 /// Initializes a new array list that contains a copy of the given array and with the
2605                 /// given count.
2606                 /// </summary>
2607                 /// <param name="array"></param>
2608                 private ArrayList(object[] array, int index, int count)
2609                 {
2610                         if (count == 0)
2611                         {
2612                                 _items = new object[DefaultInitialCapacity];
2613                         }
2614                         else
2615                         {
2616                                 _items = new object[count];
2617                         }
2618
2619                         Array.Copy(array, index, _items, 0, count);
2620
2621                         _size = count;
2622                 }
2623
2624                 #endregion
2625
2626                 #region Indexers
2627
2628                 /// <summary>
2629                 /// Gets/Sets an element in the list by index.
2630                 /// </summary>
2631                 /// <exception cref="ArgumentOutOfRangeException">
2632                 /// The index is less than 0 or more then or equal to the list count.
2633                 /// </exception>
2634                 public virtual object this[int index]
2635                 {
2636                         get
2637                         {
2638                                 if (index < 0 || index >= _size)
2639                                 {
2640                                         ThrowNewArgumentOutOfRangeException ("index", index,
2641                                                 "Index is less than 0 or more than or equal to the list count.");
2642                                 }
2643
2644                                 return _items[index];
2645                         }
2646
2647                         set
2648                         {
2649                                 if (index < 0 || index >= _size)
2650                                 {
2651                                         ThrowNewArgumentOutOfRangeException ("index", index,
2652                                                 "Index is less than 0 or more than or equal to the list count.");
2653                                 }
2654
2655                                 _items[index] = value;
2656                                 _version++;
2657                         }
2658                 }
2659
2660                 #endregion
2661
2662                 #region Properties
2663
2664                 /// <summary>
2665                 /// Gets the number of elements in the list.
2666                 /// </summary>
2667                 public virtual int Count
2668                 {
2669                         get
2670                         {
2671                                 return _size;
2672                         }
2673                 }
2674
2675                 /// <summary>
2676                 /// Gets the number of elements the list can carry without needing to expand.
2677                 /// </summary>
2678                 /// <remarks>
2679                 /// ArrayLists automatically double their capacity when the capacity limit is broken.
2680                 /// </remarks>
2681                 /// <exception cref="ArgumentOutOfRangeException">
2682                 /// The capacity is less than the count.
2683                 /// </exception>
2684                 public virtual int Capacity
2685                 {
2686                         get
2687                         {
2688                                 return _items.Length;
2689                         }
2690
2691                         set
2692                         {
2693                                 if (value < _size)
2694                                 {
2695                                         ThrowNewArgumentOutOfRangeException ("Capacity", value,
2696                                                 "Must be more than count.");
2697                                 }
2698
2699                                 object[] newArray;
2700
2701                                 newArray = new object[value];
2702
2703                                 Array.Copy(_items, 0, newArray, 0, _size);
2704
2705                                 _items = newArray;
2706                         }
2707                 }
2708
2709                 /// <summary>
2710                 /// <see cref="IList.IsFixedSize"/>
2711                 /// </summary>
2712                 /// <remarks/>
2713                 public virtual bool IsFixedSize
2714                 {
2715                         get
2716                         {
2717                                 return false;
2718                         }
2719                 }
2720
2721                 /// <summary>
2722                 /// <see cref="IList.IsReadOnly"/>
2723                 /// </summary>
2724                 public virtual bool IsReadOnly
2725                 {
2726                         get
2727                         {
2728                                 return false;
2729                         }
2730                 }
2731
2732                 /// <summary>
2733                 /// <see cref="ICollection.IsSynchronized"/>
2734                 /// </summary>
2735                 public virtual bool IsSynchronized
2736                 {
2737                         get
2738                         {
2739                                 return false;
2740                         }
2741                 }
2742
2743                 /// <summary>
2744                 /// <see cref="ICollection.SyncRoot"/>
2745                 /// </summary>
2746                 public virtual object SyncRoot
2747                 {
2748                         get
2749                         {
2750                                 return this;
2751                         }
2752                 }
2753
2754                 #endregion
2755
2756                 #region Methods
2757
2758                 /// <remarks>
2759                 /// Ensures that the list has the capacity to contain the given <c>count</c> by
2760                 /// automatically expanding the capacity when required.
2761                 /// </remarks>
2762                 private void EnsureCapacity(int count)
2763                 {
2764                         if (count <= _items.Length)
2765                         {
2766                                 return;
2767                         }
2768
2769                         int newLength;
2770                         object[] newData;
2771
2772                         newLength = _items.Length << 1;
2773                         if (newLength == 0)
2774                                 newLength = DefaultInitialCapacity;
2775
2776                         while (newLength < count)
2777                         {
2778                                 newLength <<= 1;
2779                         }
2780
2781                         newData = new object[newLength];
2782
2783                         Array.Copy(_items, 0, newData, 0, _items.Length);
2784
2785                         _items = newData;
2786                 }
2787
2788                 /// <summary>
2789                 /// Shifts a section of the list.
2790                 /// </summary>
2791                 /// <param name="index">
2792                 /// The start of the section to shift (the element at index is included in the shift).
2793                 /// </param>
2794                 /// <param name="count">
2795                 /// The number of positions to shift by (can be negative).
2796                 /// </param>
2797                 private void Shift(int index, int count)
2798                 {
2799                         if (count > 0)
2800                         {
2801                                 if (_size + count > _items.Length)
2802                                 {
2803                                         int newLength;
2804                                         object[] newData;
2805
2806                                         newLength = (_items.Length > 0) ? _items.Length << 1 : 1;
2807
2808                                         while (newLength < _size + count)
2809                                         {
2810                                                 newLength <<= 1;
2811                                         }
2812
2813                                         newData = new object[newLength];
2814
2815                                         Array.Copy(_items, 0, newData, 0, index);
2816                                         Array.Copy(_items, index, newData, index + count, _size - index);
2817
2818                                         _items = newData;
2819                                 }
2820                                 else
2821                                 {
2822                                         Array.Copy(_items, index, _items, index + count, _size - index);
2823                                 }
2824                         }
2825                         else if (count < 0)
2826                         {
2827                                 // Remember count is negative so this is actually index + (-count)
2828
2829                                 int x = index - count ;
2830
2831                                 Array.Copy(_items, x, _items, index, _size - x);
2832                                 Array.Clear(_items, _size + count, - count);
2833                         }
2834                 }
2835
2836                 public virtual int Add(object value)
2837                 {
2838                         // Do a check here in case EnsureCapacity isn't inlined.
2839
2840                         if (_items.Length <= _size /* same as _items.Length < _size + 1) */)
2841                         {
2842                                 EnsureCapacity(_size + 1);
2843                         }
2844
2845                         _items[_size] = value;
2846
2847                         _version++;
2848
2849                         return _size++;
2850                 }
2851
2852                 public virtual void Clear()
2853                 {
2854                         // Keep the array but null all members so they can be garbage collected.
2855
2856                         Array.Clear(_items, 0, _size);
2857
2858                         _size = 0;
2859                         _version++;
2860                 }
2861
2862                 public virtual bool Contains(object item)
2863                 {
2864                         return IndexOf(item, 0, _size) > -1;
2865                 }
2866
2867                 internal virtual bool Contains(object value, int startIndex, int count)
2868                 {
2869                         return IndexOf(value, startIndex, count) > -1;
2870                 }
2871
2872                 public virtual int IndexOf(object value)
2873                 {
2874                         return IndexOf(value, 0);
2875                 }
2876
2877                 public virtual int IndexOf(object value, int startIndex)
2878                 {
2879                         return IndexOf(value, startIndex, _size - startIndex);
2880                 }
2881
2882                 public virtual int IndexOf(object value, int startIndex, int count)
2883                 {
2884                         if (startIndex < 0 || startIndex > _size)
2885                         {
2886                                 ThrowNewArgumentOutOfRangeException ("startIndex", startIndex,
2887                                         "Does not specify valid index.");
2888                         }
2889
2890                         if (count < 0)
2891                         {
2892                                 ThrowNewArgumentOutOfRangeException ("count", count,
2893                                         "Can't be less than 0.");
2894                         }
2895
2896                         // re-ordered to avoid integer overflow
2897                         if (startIndex > _size - count)
2898                         {
2899                                 // LAMESPEC: Every other method throws ArgumentException
2900
2901                                 throw new ArgumentOutOfRangeException("count",
2902                                         "Start index and count do not specify a valid range.");
2903                         }
2904
2905                         return Array.IndexOf(_items, value, startIndex, count);
2906                 }
2907
2908                 public virtual int LastIndexOf(object value)
2909                 {
2910                         return LastIndexOf(value, _size - 1);
2911                 }
2912
2913                 public virtual int LastIndexOf(object value, int startIndex)
2914                 {
2915                         return LastIndexOf(value, startIndex, startIndex + 1);
2916                 }
2917
2918                 public virtual int LastIndexOf (object value, int startIndex, int count)
2919                 {
2920                         // Array will catch the exceptions
2921                         return Array.LastIndexOf (_items, value, startIndex, count);
2922                 }
2923
2924                 public virtual void Insert(int index, object value)
2925                 {
2926                         if (index < 0 || index > _size)
2927                         {
2928                                 ThrowNewArgumentOutOfRangeException ("index", index,
2929                                         "Index must be >= 0 and <= Count.");
2930                         }
2931
2932                         Shift(index, 1);
2933
2934                         _items[index] = value;
2935                         _size++;
2936                         _version++;
2937                 }
2938
2939                 public virtual void InsertRange(int index, ICollection c)
2940                 {
2941                         int i;
2942
2943                         if (c == null)
2944                         {
2945                                 throw new ArgumentNullException("c");
2946                         }
2947
2948                         if (index < 0 || index > _size)
2949                         {
2950                                 ThrowNewArgumentOutOfRangeException ("index", index,
2951                                         "Index must be >= 0 and <= Count.");
2952                         }
2953
2954                         i = c.Count;
2955
2956                         // Do a check here in case EnsureCapacity isn't inlined.
2957
2958                         if (_items.Length < _size + i)
2959                         {
2960                                 EnsureCapacity(_size + i);
2961                         }
2962
2963                         if (index < _size)
2964                         {
2965                                 Array.Copy(_items, index, _items, index + i, _size - index);
2966                         }
2967
2968                         // Handle inserting a range from a list to itself specially.
2969
2970                         if (this == c.SyncRoot)
2971                         {
2972                                 // Copy range before the insert point.
2973
2974                                 Array.Copy(_items, 0, _items, index, index);
2975
2976                                 // Copy range after the insert point.
2977
2978                                 Array.Copy(_items, index + i, _items, index << 1, _size - index);
2979                         }
2980                         else
2981                         {
2982                                 c.CopyTo(_items, index);
2983                         }
2984
2985                         _size += c.Count;
2986                         _version++;
2987                 }
2988
2989                 public virtual void Remove(object obj)
2990                 {
2991                         int x;
2992
2993                         x = IndexOf(obj);
2994
2995                         if (x > -1)
2996                         {
2997                                 RemoveAt(x);
2998                         }
2999
3000                         _version++;
3001                 }
3002
3003                 public virtual void RemoveAt(int index)
3004                 {
3005                         if (index < 0 || index >= _size)
3006                         {
3007                                 ThrowNewArgumentOutOfRangeException ("index", index,
3008                                         "Less than 0 or more than list count.");
3009                         }
3010
3011                         Shift(index, -1);
3012                         _size--;
3013                         _version++;
3014                 }
3015
3016                 public virtual void RemoveRange(int index, int count)
3017                 {
3018                         ArrayList.CheckRange(index, count, _size);
3019
3020                         Shift(index, -count);
3021                         _size -= count;
3022                         _version++;
3023                 }
3024
3025                 public virtual void Reverse()
3026                 {
3027                         Array.Reverse(_items, 0, _size);
3028                         _version++;
3029                 }
3030
3031                 public virtual void Reverse(int index, int count)
3032                 {
3033                         ArrayList.CheckRange(index, count, _size);
3034
3035                         Array.Reverse(_items, index, count);
3036                         _version++;
3037                 }
3038
3039                 public virtual void CopyTo(System.Array array)
3040                 {
3041                         Array.Copy(_items, array, _size);
3042                 }
3043
3044                 public virtual void CopyTo(System.Array array, int arrayIndex)
3045                 {
3046                         CopyTo(0, array, arrayIndex, _size);
3047                 }
3048
3049                 public virtual void CopyTo(int index, System.Array array, int arrayIndex, int count)
3050                 {
3051                         if (array == null)
3052                         {
3053                                 throw new ArgumentNullException("array");
3054                         }
3055
3056                         if (array.Rank != 1)
3057                         {
3058                                 // LAMESPEC:
3059                                 // This should be a RankException because Array.Copy throws RankException.
3060
3061                                 throw new ArgumentException("Must have only 1 dimensions.", "array");
3062                         }
3063
3064                         Array.Copy(_items, index, array, arrayIndex, count);
3065                 }
3066
3067                 public virtual IEnumerator GetEnumerator()
3068                 {
3069                         return new SimpleEnumerator(this);
3070                 }
3071
3072                 public virtual IEnumerator GetEnumerator(int index, int count)
3073                 {
3074                         ArrayList.CheckRange(index, count, _size);
3075
3076                         return new ArrayListEnumerator(this, index, count);
3077                 }
3078
3079                 public virtual void AddRange(ICollection c)
3080                 {
3081                         InsertRange(_size, c);
3082                 }
3083
3084                 public virtual int BinarySearch(object value)
3085                 {
3086                         try
3087                         {
3088                                 return Array.BinarySearch(_items, 0, _size, value);
3089                         }
3090                         catch (InvalidOperationException e)
3091                         {
3092                                 throw new ArgumentException(e.Message);
3093                         }
3094                 }
3095
3096                 public virtual int BinarySearch(object value, IComparer comparer)
3097                 {
3098                         try
3099                         {
3100                                 return Array.BinarySearch(_items, 0, _size, value, comparer);
3101                         }
3102                         catch (InvalidOperationException e)
3103                         {
3104                                 throw new ArgumentException(e.Message);
3105                         }
3106                 }
3107
3108                 public virtual int BinarySearch(int index, int count, object value, IComparer comparer)
3109                 {
3110                         try
3111                         {
3112                                 return Array.BinarySearch(_items, index, count, value, comparer);
3113                         }
3114                         catch (InvalidOperationException e)
3115                         {
3116                                 throw new ArgumentException(e.Message);
3117                         }
3118                 }
3119                 public virtual ArrayList GetRange(int index, int count)
3120                 {
3121                         ArrayList.CheckRange(index, count, _size);
3122
3123                         if (this.IsSynchronized)
3124                         {
3125                                 return ArrayList.Synchronized(new RangedArrayList(this, index, count));
3126                         }
3127                         else
3128                         {
3129                                 return new RangedArrayList(this, index, count);
3130                         }
3131                 }
3132
3133                 public virtual void SetRange(int index, ICollection c)
3134                 {
3135                         if (c == null)
3136                         {
3137                                 throw new ArgumentNullException("c");
3138                         }
3139
3140                         if (index < 0 || index + c.Count > _size)
3141                         {
3142                                 throw new ArgumentOutOfRangeException("index");
3143                         }
3144
3145                         c.CopyTo(_items, index);
3146
3147                         _version++;
3148                 }
3149
3150                 public virtual void TrimToSize()
3151                 {
3152                         if (_items.Length > _size)
3153                         {
3154                                 object[] newArray;
3155
3156                                 if (_size == 0)
3157                                 {
3158                                         newArray = new object[DefaultInitialCapacity];
3159                                 }
3160                                 else
3161                                 {
3162                                         newArray = new object[_size];
3163                                 }
3164
3165                                 Array.Copy(_items, 0, newArray, 0, _size);
3166
3167                                 _items = newArray;
3168                         }
3169                 }
3170
3171                 public virtual void Sort()
3172                 {
3173                         Array.Sort(_items, 0, _size);
3174
3175                         _version++;
3176                 }
3177
3178                 public virtual void Sort(IComparer comparer)
3179                 {
3180                         Array.Sort(_items, 0, _size, comparer);
3181                 }
3182
3183                 public virtual void Sort(int index, int count, IComparer comparer)
3184                 {
3185                         ArrayList.CheckRange(index, count, _size);
3186
3187                         Array.Sort(_items, index, count, comparer);
3188                 }
3189
3190                 public virtual object[] ToArray()
3191                 {
3192                         object[] retval;
3193
3194                         retval = new object[_size];
3195
3196                         CopyTo(retval);
3197
3198                         return retval;
3199                 }
3200
3201                 public virtual Array ToArray(Type type)
3202                 {
3203                         Array retval;
3204
3205                         retval = Array.CreateInstance(type, _size);
3206
3207                         CopyTo(retval);
3208
3209                         return retval;
3210                 }
3211
3212                 public virtual object Clone()
3213                 {
3214                         return new ArrayList(this._items, 0, this._size);
3215                 }
3216
3217                 #endregion
3218
3219                 #region Static Methods
3220
3221                 /// <summary>
3222                 /// Does a check of the arguments many of the methods in ArrayList use.
3223                 /// </summary>
3224                 /// <remarks>
3225                 /// The choice of exceptions thrown sometimes seem to be arbitrarily chosen so
3226                 /// not all methods actually make use of CheckRange.
3227                 /// </remarks>
3228                 internal static void CheckRange(int index, int count, int listCount)
3229                 {
3230                         if (index < 0)
3231                         {
3232                                 ThrowNewArgumentOutOfRangeException ("index", index, "Can't be less than 0.");
3233                         }
3234
3235                         if (count < 0)
3236                         {
3237                                 ThrowNewArgumentOutOfRangeException ("count", count, "Can't be less than 0.");
3238                         }
3239
3240                         // re-ordered to avoid possible integer overflow
3241                         if (index > listCount - count)
3242                         {
3243                                 throw new ArgumentException("Index and count do not denote a valid range of elements.", "index");
3244                         }
3245                 }
3246
3247                 internal static void ThrowNewArgumentOutOfRangeException (string name, object actual, string message)
3248                 {
3249                         throw new ArgumentOutOfRangeException (
3250 #if !INSIDE_CORLIB && NET_2_1
3251                                 name, message
3252 #else
3253                                 name, actual, message
3254 #endif
3255                         );
3256                 }
3257
3258                 public static ArrayList Adapter(IList list)
3259                 {
3260                         // LAMESPEC: EWWW.  Other lists aren't *Array*Lists.
3261
3262                         if (list == null)
3263                         {
3264                                 throw new ArgumentNullException("list");
3265                         }
3266
3267                         ArrayList arrayList = list as ArrayList;
3268                         if (arrayList != null)
3269                                 return arrayList;
3270                         else
3271                                 arrayList = new ArrayListAdapter(list);
3272
3273                         if (list.IsSynchronized)
3274                                 return ArrayList.Synchronized(arrayList);
3275                         else
3276                                 return arrayList;
3277                 }
3278
3279                 public static ArrayList Synchronized(ArrayList list)
3280                 {
3281                         if (list == null)
3282                         {
3283                                 throw new ArgumentNullException("list");
3284                         }
3285
3286                         if (list.IsSynchronized)
3287                         {
3288                                 return list;
3289                         }
3290
3291                         return new SynchronizedArrayListWrapper(list);
3292                 }
3293
3294                 public static IList Synchronized(IList list)
3295                 {
3296                         if (list == null)
3297                         {
3298                                 throw new ArgumentNullException("list");
3299                         }
3300
3301                         if (list.IsSynchronized)
3302                         {
3303                                 return list;
3304                         }
3305
3306                         return new SynchronizedListWrapper(list);
3307                 }
3308
3309                 public static ArrayList ReadOnly(ArrayList list)
3310                 {
3311                         if (list == null)
3312                         {
3313                                 throw new ArgumentNullException("list");
3314                         }
3315
3316                         if (list.IsReadOnly)
3317                         {
3318                                 return list;
3319                         }
3320
3321                         return new ReadOnlyArrayListWrapper(list);
3322                 }
3323
3324                 public static IList ReadOnly(IList list)
3325                 {
3326                         if (list == null)
3327                         {
3328                                 throw new ArgumentNullException("list");
3329                         }
3330
3331                         if (list.IsReadOnly)
3332                         {
3333                                 return list;
3334                         }
3335
3336                         return new ReadOnlyListWrapper(list);
3337                 }
3338
3339                 public static ArrayList FixedSize(ArrayList list)
3340                 {
3341                         if (list == null)
3342                         {
3343                                 throw new ArgumentNullException("list");
3344                         }
3345
3346                         if (list.IsFixedSize)
3347                         {
3348                                 return list;
3349                         }
3350
3351                         return new FixedSizeArrayListWrapper(list);
3352                 }
3353
3354                 public static IList FixedSize(IList list)
3355                 {
3356                         if (list == null)
3357                         {
3358                                 throw new ArgumentNullException("list");
3359                         }
3360
3361                         if (list.IsFixedSize)
3362                         {
3363                                 return list;
3364                         }
3365
3366                         return new FixedSizeListWrapper(list);
3367                 }
3368
3369                 public static ArrayList Repeat(object value, int count)
3370                 {
3371                         ArrayList arrayList = new ArrayList(count);
3372
3373                         for (int i = 0; i < count; i++)
3374                         {
3375                                 arrayList.Add(value);
3376                         }
3377
3378                         return arrayList;
3379                 }
3380
3381                 #endregion
3382         }
3383 }