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