mcs/class/corlib/System/Array.cs

   1 //
   2 // System.Array.cs
   3 //
   4 // Authors:
   5 //   Joe Shaw (joe@ximian.com)
   6 //   Martin Baulig (martin@gnome.org)
   7 //   Dietmar Maurer (dietmar@ximian.com)
   8 //
   9 // (C) 2001 Ximian, Inc.  http://www.ximian.com
  10 //
  11
  12 using System.Collections;
  13 using System.Runtime.CompilerServices;
  14
  15 namespace System
  16 {
  17
  18         public abstract class Array : ICloneable, ICollection, IList, IEnumerable
  19         {
  20                 // Constructor
  21                 protected Array ()
  22                 {
  23                         /* empty */
  24                 }
  25
  26                 // Properties
  27                 public int Length
  28                 {
  29                         get
  30                         {
  31                                 int length = this.GetLength (0);
  32
  33                                 for (int i = 1; i < this.Rank; i++) {
  34                                         length *= this.GetLength (i);
  35                                 }
  36
  37                                 return length;
  38                         }
  39                 }
  40
  41                 public int Rank
  42                 {
  43                         get
  44                         {
  45                                 return this.GetRank ();
  46                         }
  47                 }
  48
  49                 // IList interface
  50                 public object this [int index] {
  51                         get {
  52                                 return GetValueImpl (index);
  53                         }
  54                         set {
  55                                 SetValueImpl (value, index);
  56                         }
  57                 }
  58
  59                 int IList.Add (object value) {
  60                         throw new NotSupportedException ();
  61                 }
  62
  63                 void IList.Clear () {
  64                         Array.Clear (this, this.GetLowerBound(0), this.Length);
  65                 }
  66
  67                 bool IList.Contains (object value) {
  68                         int length = this.Length;
  69                         for (int i = 0; i < length; i++) {
  70                                 if (value.Equals (this.GetValueImpl (i)))
  71                                         return true;
  72                         }
  73                         return false;
  74                 }
  75
  76                 int IList.IndexOf (object value) {
  77                         if (this.Rank > 1)
  78                                 throw new RankException ();
  79
  80                         int length = this.Length;
  81                         for (int i = 0; i < length; i++) {
  82                                 if (value.Equals (this.GetValueImpl (i)))
  83                                         // array index may not be zero-based.
  84                                         // use lower bound
  85                                         return i + this.GetLowerBound (0);
  86                         }
  87
  88                         int retVal;
  89                         unchecked {
  90                                 // lower bound may be MinValue
  91                                 retVal = this.GetLowerBound (0) - 1;
  92                         }
  93
  94                         return retVal;
  95                 }
  96
  97                 void IList.Insert (int index, object value) {
  98                         throw new NotSupportedException ();
  99                 }
 100
 101                 void IList.Remove (object value) {
 102                         throw new NotSupportedException ();
 103                 }
 104
 105                 void IList.RemoveAt (int index) {
 106                         throw new NotSupportedException ();
 107                 }
 108
 109                 // InternalCall Methods
 110
 111                 [MethodImplAttribute(MethodImplOptions.InternalCall)]
 112                 public extern int GetRank ();
 113
 114                 [MethodImplAttribute(MethodImplOptions.InternalCall)]
 115                 public extern int GetLength (int dimension);
 116
 117                 [MethodImplAttribute(MethodImplOptions.InternalCall)]
 118                 public extern int GetLowerBound (int dimension);
 119
 120                 [MethodImplAttribute(MethodImplOptions.InternalCall)]
 121                 public extern object GetValue (int[] idxs);
 122
 123                 [MethodImplAttribute(MethodImplOptions.InternalCall)]
 124                 public extern void SetValue (object value, int[] idxs);
 125
 126                 [MethodImplAttribute(MethodImplOptions.InternalCall)]
 127                 internal extern object GetValueImpl (int pos);
 128
 129                 [MethodImplAttribute(MethodImplOptions.InternalCall)]
 130                 internal extern void SetValueImpl (object value, int pos);
 131
 132                 [MethodImplAttribute(MethodImplOptions.InternalCall)]
 133                 internal extern static void FastCopy (Array source, int source_idx, Array dest, int dest_idx, int length);\r
 134 \r
 135                 [MethodImplAttribute(MethodImplOptions.InternalCall)]\r
 136                 internal extern static Array CreateInstanceImpl(Type elementType, int[] lengths, int [] bounds);
 137
 138                 // Properties
 139                 public virtual int Count {
 140                         get {
 141                                 return Length;
 142                         }
 143                 }
 144
 145                 [MonoTODO]
 146                 public virtual bool IsSynchronized {
 147                         get {
 148                                 // FIXME?
 149                                 return false;
 150                         }
 151                 }
 152
 153                 [MonoTODO]
 154                 public virtual object SyncRoot {
 155                         get {
 156                                 // FIXME
 157                                 return null;
 158                         }
 159                 }
 160
 161                 public virtual bool IsFixedSize
 162                 {
 163                         get {
 164                                 return true;
 165                         }
 166                 }
 167
 168                 public virtual bool IsReadOnly
 169                 {
 170                         get{
 171                                 return false;
 172                         }
 173                 }
 174
 175                 public virtual IEnumerator GetEnumerator ()
 176                 {
 177                         return new SimpleEnumerator(this);
 178                 }
 179
 180                 public int GetUpperBound (int dimension)
 181                 {
 182                         return GetLowerBound (dimension) +
 183                                 GetLength (dimension) - 1;
 184                 }
 185
 186                 public object GetValue (int idx)
 187                 {
 188                         int[] ind = new int [1];
 189
 190                         ind [0] = idx;
 191
 192                         return GetValue (ind);
 193                 }
 194
 195                 public object GetValue (int idx1, int idx2)
 196                 {
 197                         int[] ind = new int [2];
 198
 199                         ind [0] = idx1;
 200                         ind [1] = idx2;
 201
 202                         return GetValue (ind);
 203                 }
 204
 205                 public object GetValue (int idx1, int idx2, int idx3)
 206                 {
 207                         int[] ind = new int [3];
 208
 209                         ind [0] = idx1;
 210                         ind [1] = idx2;
 211                         ind [2] = idx3;
 212
 213                         return GetValue (ind);
 214                 }
 215
 216                 // This function is currently unused, but just in case we need it later on ... */
 217                 internal int IndexToPos (int[] idxs)
 218                 {
 219                         if (idxs == null)
 220                                 throw new ArgumentNullException ();
 221
 222                         if ((idxs.Rank != 1) || (idxs.Length != Rank))
 223                                 throw new ArgumentException ();
 224
 225                         if ((idxs [0] < GetLowerBound (0)) || (idxs [0] > GetUpperBound (0)))
 226                                 throw new IndexOutOfRangeException();
 227
 228                         int pos = idxs [0] - GetLowerBound (0);
 229                         for (int i = 1; i < Rank; i++) {
 230                                 if ((idxs [i] < GetLowerBound (i)) || (idxs [i] > GetUpperBound (i)))
 231                                         throw new IndexOutOfRangeException();
 232
 233                                 pos *= GetLength (i);
 234                                 pos += idxs [i] - GetLowerBound (i);
 235                         }
 236
 237                         return pos;
 238                 }
 239
 240                 public void SetValue (object value, int idx)
 241                 {
 242                         int[] ind = new int [1];
 243
 244                         ind [0] = idx;
 245
 246                         SetValue (value, ind);
 247                 }
 248
 249                 public void SetValue (object value, int idx1, int idx2)
 250                 {
 251                         int[] ind = new int [2];
 252
 253                         ind [0] = idx1;
 254                         ind [1] = idx2;
 255
 256                         SetValue (value, ind);
 257                 }
 258
 259                 public void SetValue (object value, int idx1, int idx2, int idx3)
 260                 {
 261                         int[] ind = new int [3];
 262
 263                         ind [0] = idx1;
 264                         ind [1] = idx2;
 265                         ind [2] = idx3;
 266
 267                         SetValue (value, ind);
 268                 }
 269
 270                 public static Array CreateInstance(Type elementType, int length)
 271                 {
 272                         int[] lengths = new int [1];
 273                         int[] bounds = null;
 274
 275                         lengths [0] = length;
 276
 277                         return CreateInstanceImpl (elementType, lengths, bounds);
 278                 }
 279
 280                 public static Array CreateInstance(Type elementType, int l1, int l2)
 281                 {
 282                         int[] lengths = new int [2];
 283                         int[] bounds = null;
 284
 285                         lengths [0] = l1;
 286                         lengths [1] = l2;
 287
 288                         return CreateInstanceImpl (elementType, lengths, bounds);
 289                 }
 290
 291                 public static Array CreateInstance(Type elementType, int l1, int l2, int l3)
 292                 {
 293                         int[] lengths = new int [3];
 294                         int[] bounds = null;
 295
 296                         lengths [0] = l1;
 297                         lengths [1] = l2;
 298                         lengths [2] = l3;
 299
 300                         return CreateInstanceImpl (elementType, lengths, bounds);
 301                 }
 302
 303                 public static Array CreateInstance(Type elementType, int[] lengths)
 304                 {
 305                         int[] bounds = null;
 306
 307                         return CreateInstanceImpl (elementType, lengths, bounds);
 308                 }
 309
 310                 public static Array CreateInstance(Type elementType, int[] lengths, int [] bounds)
 311                 {
 312                         if (bounds == null)
 313                                 throw new ArgumentNullException("bounds");
 314
 315                         return CreateInstanceImpl (elementType, lengths, bounds);
 316                 }
 317
 318
 319                 public static int BinarySearch (Array array, object value)
 320                 {
 321                         if (array == null)
 322                                 throw new ArgumentNullException ();
 323
 324                         return BinarySearch (array, array.GetLowerBound (0), array.GetLength (0),
 325                                              value, null);
 326                 }
 327
 328                 public static int BinarySearch (Array array, object value, IComparer comparer)
 329                 {
 330                         if (array == null)
 331                                 throw new ArgumentNullException ();
 332
 333                         return BinarySearch (array, array.GetLowerBound (0), array.GetLength (0),
 334                                              value, comparer);
 335                 }
 336
 337                 public static int BinarySearch (Array array, int index, int length, object value)
 338                 {
 339                         if (array == null)
 340                                 throw new ArgumentNullException ();
 341
 342                         return BinarySearch (array, index, length, value, null);
 343                 }
 344
 345                 public static int BinarySearch (Array array, int index,
 346                                                 int length, object value,
 347                                                 IComparer comparer)
 348                 {
 349                         if (array == null)
 350                                 throw new ArgumentNullException ();
 351
 352                         if (array.Rank > 1)
 353                                 throw new RankException ();
 354
 355                         if (index < array.GetLowerBound (0) || length < 0)
 356                                 throw new ArgumentOutOfRangeException ();
 357
 358                         if (index + length > array.GetUpperBound (0) + 1)
 359                                 throw new ArgumentException ();
 360
 361                         if (comparer == null && !(value is IComparable))
 362                                 throw new ArgumentException ();
 363
 364                         // FIXME: Throw an ArgumentException if comparer
 365                         // is null and value is not of the same type as the
 366                         // elements of array.
 367
 368                         // FIXME: This is implementing linear search. While it should do a binary one
 369                         // FIXME: Should not throw exception when values are null
 370
 371                         for (int i = 0; i < length; i++)
 372                         {
 373                                 int result;
 374
 375                                 if (comparer == null && !(array.GetValue(index + i) is IComparable))
 376                                         throw new ArgumentException ();
 377
 378                                 if (comparer == null)
 379                                         result = (value as IComparable).CompareTo(array.GetValue(index + i));
 380                                 else
 381                                         result = comparer.Compare(value, array.GetValue(index + i));
 382
 383                                 if (result == 0)
 384                                         return index + i;
 385                                 else if (result < 0)
 386                                         return ~(index + i);
 387                         }
 388
 389                         return ~(index + length);
 390                 }
 391
 392                 public static void Clear (Array array, int index, int length)
 393                 {
 394                         if (array == null)
 395                                 throw new ArgumentNullException ();
 396
 397                         if (array.Rank > 1)
 398                                 throw new RankException ();
 399
 400                         if (index < array.GetLowerBound (0) || length < 0 ||
 401                                 index + length > array.GetUpperBound (0) + 1)
 402                                 throw new ArgumentOutOfRangeException ();
 403
 404                         for (int i = 0; i < length; i++)
 405                         {
 406                                 array.SetValue(null, index + i);
 407                         }
 408                 }
 409
 410                 [MethodImplAttribute(MethodImplOptions.InternalCall)]
 411                 public virtual extern object Clone ();
 412
 413                 public static void Copy (Array source, Array dest, int length)
 414                 {
 415                         if (source == null || dest == null)
 416                                 throw new ArgumentNullException ();
 417
 418                         Copy (source, source.GetLowerBound (0), dest, dest.GetLowerBound (0), length);
 419                 }
 420
 421                 public static void Copy (Array source, int source_idx, Array dest, int dest_idx, int length)
 422                 {
 423                         if (source == null || dest == null)
 424                                 throw new ArgumentNullException ();
 425
 426                         if (length < 0)
 427                                 throw new ArgumentOutOfRangeException ();
 428
 429                         int source_pos = source_idx - source.GetLowerBound (0);
 430                         int dest_pos = dest_idx - dest.GetLowerBound (0);
 431
 432                         if (source_idx < 0 || dest_idx < 0)
 433                                 throw new ArgumentException ();
 434
 435                         if (source_pos + length > source.Length || dest_pos + length > dest.Length)
 436                                 throw new ArgumentException ();
 437
 438                         if (source.Rank != dest.Rank)
 439                                 throw new RankException ();
 440
 441                         Type src_type = source.GetType ().GetElementType ();
 442                         Type dst_type = dest.GetType ().GetElementType ();
 443
 444                         if (src_type.IsValueType && (src_type == dst_type)) {
 445                                 FastCopy (source, source_pos, dest, dest_pos, length);
 446                                 return;
 447                         }
 448
 449                         for (int i = 0; i < length; i++)
 450                         {
 451                                 Object srcval = source.GetValueImpl (source_pos + i);
 452
 453                                 bool errorThrown = false;
 454
 455                                 try {
 456                                         dest.SetValueImpl (srcval, dest_pos + i);
 457                                 } catch {
 458                                         errorThrown = true;
 459                                 }
 460
 461                                 if (!errorThrown)
 462                                         continue;
 463
 464                                 if ((dst_type.IsValueType || dst_type.Equals (typeof (String))) &&
 465                                     (src_type.Equals (typeof (Object))))
 466                                         throw new InvalidCastException ();
 467                                 else
 468                                         throw new ArrayTypeMismatchException ();
 469                         }
 470                 }
 471
 472                 public static int IndexOf (Array array, object value)
 473                 {
 474                         if (array == null)
 475                                 throw new ArgumentNullException ();
 476
 477                         return IndexOf (array, value, 0, array.Length);
 478                 }
 479
 480                 public static int IndexOf (Array array, object value, int index)
 481                 {
 482                         if (array == null)
 483                                 throw new ArgumentNullException ();
 484
 485                         return IndexOf (array, value, index, array.Length - index);
 486                 }
 487
 488                 public static int IndexOf (Array array, object value, int index, int length)
 489                 {
 490                         if (array == null)
 491                                 throw new ArgumentNullException ();
 492
 493                         if (array.Rank > 1)
 494                                 throw new RankException ();
 495
 496                         if (length < 0 || index < array.GetLowerBound (0) ||
 497                             index+length-1 > array.GetUpperBound (0))
 498                                 throw new ArgumentOutOfRangeException ();
 499
 500                         for (int i = 0; i < length; i++)
 501                         {
 502                                 if (array.GetValue(index + i).Equals(value))
 503                                         return index + i;
 504                         }
 505
 506                         return array.GetLowerBound (0) - 1;
 507                 }
 508
 509                 public static int LastIndexOf (Array array, object value)
 510                 {
 511                         if (array == null)
 512                                 throw new ArgumentNullException ();
 513
 514                         return LastIndexOf (array, value, array.Length-1);
 515                 }
 516
 517                 public static int LastIndexOf (Array array, object value, int index)
 518                 {
 519                         if (array == null)
 520                                 throw new ArgumentNullException ();
 521
 522                         return LastIndexOf (array, value, index, index-array.GetLowerBound(0)+1);
 523                 }
 524
 525                 public static int LastIndexOf (Array array, object value, int index, int length)
 526                 {
 527                         if (array == null)
 528                                 throw new ArgumentNullException ();
 529
 530                         if (array.Rank > 1)
 531                                 throw new RankException ();
 532
 533                         if (length < 0 || index-length+1 < array.GetLowerBound (0) ||
 534                             index > array.GetUpperBound (0))
 535                                 throw new ArgumentOutOfRangeException ();
 536
 537                         for (int i = index; i >= index-length+1; i--)
 538                         {
 539                                 if (array.GetValue(i).Equals(value))
 540                                         return i;
 541                         }
 542
 543                         return array.GetLowerBound (0) - 1;
 544                 }
 545
 546                 public static void Reverse (Array array)
 547                 {
 548                         if (array == null)
 549                                 throw new ArgumentNullException ();
 550
 551                         Reverse (array, array.GetLowerBound (0), array.GetLength (0));
 552                 }
 553
 554                 public static void Reverse (Array array, int index, int length)
 555                 {
 556                         if (array == null)
 557                                 throw new ArgumentNullException ();
 558
 559                         if (array.Rank > 1)
 560                                 throw new RankException ();
 561
 562                         if (index < array.GetLowerBound (0) || length < 0)
 563                                 throw new ArgumentOutOfRangeException ();
 564
 565                         if (index + length > array.GetUpperBound (0) + 1)
 566                                 throw new ArgumentException ();
 567
 568                         for (int i = 0; i < length/2; i++)
 569                         {
 570                                 object tmp;
 571
 572                                 tmp = array.GetValue (index + i);
 573                                 array.SetValue(array.GetValue (index + length - i - 1), index + i);
 574                                 array.SetValue(tmp, index + length - i - 1);
 575                         }
 576                 }
 577
 578                 public static void Sort (Array array)
 579                 {
 580                         if (array == null)
 581                                 throw new ArgumentNullException ();
 582
 583                         Sort (array, null, array.GetLowerBound (0), array.GetLength (0), null);
 584                 }
 585
 586                 public static void Sort (Array keys, Array items)
 587                 {
 588                         if (keys == null)
 589                                 throw new ArgumentNullException ();
 590
 591                         Sort (keys, items, keys.GetLowerBound (0), keys.GetLength (0), null);
 592                 }
 593
 594                 public static void Sort (Array array, IComparer comparer)
 595                 {
 596                         if (array == null)
 597                                 throw new ArgumentNullException ();
 598
 599                         Sort (array, null, array.GetLowerBound (0), array.GetLength (0), comparer);
 600                 }
 601
 602                 public static void Sort (Array array, int index, int length)
 603                 {
 604                         Sort (array, null, index, length, null);
 605                 }
 606
 607                 public static void Sort (Array keys, Array items, IComparer comparer)
 608                 {
 609                         if (keys == null)
 610                                 throw new ArgumentNullException ();
 611
 612                         Sort (keys, items, keys.GetLowerBound (0), keys.GetLength (0), comparer);
 613                 }
 614
 615                 public static void Sort (Array keys, Array items, int index, int length)
 616                 {
 617                         Sort (keys, items, index, length, null);
 618                 }
 619
 620                 public static void Sort (Array array, int index, int length, IComparer comparer)
 621                 {
 622                         Sort (array, null, index, length, comparer);
 623                 }
 624
 625                 public static void Sort (Array keys, Array items, int index, int length, IComparer comparer)
 626                 {
 627                         int low0 = index;
 628                         int high0 = index + length - 1;
 629
 630                         qsort (keys, items, index, index + length - 1, comparer);
 631                 }
 632
 633                 private static void qsort (Array keys, Array items, int low0, int high0, IComparer comparer)
 634                 {
 635                         int pivot;
 636                         int low = low0;
 637                         int high = high0;
 638
 639                         if (keys == null)
 640                                 throw new ArgumentNullException ();
 641
 642                         if (keys.Rank > 1 || (items != null && items.Rank > 1))
 643                                 throw new RankException ();
 644
 645                         if (low >= high)
 646                                 return;
 647
 648                         pivot = (low + high) / 2;
 649
 650                         if (compare (keys.GetValue (low), keys.GetValue (pivot), comparer) > 0)
 651                                 swap (keys, items, low, pivot);
 652
 653                         if (compare (keys.GetValue (pivot), keys.GetValue (high), comparer) > 0)
 654                                 swap (keys, items, pivot, high);
 655
 656                         while (low < high)
 657                         {
 658                                 // Move the walls in
 659                                 while (low < high && compare (keys.GetValue (low), keys.GetValue (pivot), comparer) < 0)
 660                                         low++;
 661                                 while (low < high && compare (keys.GetValue (pivot), keys.GetValue (high), comparer) < 0)
 662                                         high--;
 663
 664                                 if (low < high)
 665                                 {
 666                                         swap (keys, items, low, high);
 667                                         low++;
 668                                         high--;
 669                                 }
 670                         }
 671
 672                         qsort (keys, items, low0, low - 1, comparer);
 673                         qsort (keys, items, high + 1, high0, comparer);
 674                 }
 675
 676                 private static void swap (Array keys, Array items, int i, int j)
 677                 {
 678                         object tmp;
 679
 680                         tmp = keys.GetValue (i);
 681                         keys.SetValue (keys.GetValue (j), i);
 682                         keys.SetValue (tmp, j);
 683
 684                         if (items != null)
 685                         {
 686                                 tmp = items.GetValue (i);
 687                                 items.SetValue (items.GetValue (j), i);
 688                                 items.SetValue (tmp, j);
 689                         }
 690                 }
 691
 692                 private static int compare (object value1, object value2, IComparer comparer)
 693                 {
 694                         if (comparer == null)
 695                                 return ((IComparable) value1).CompareTo(value2);
 696                         else
 697                                 return comparer.Compare(value1, value2);
 698                 }
 699
 700                 public virtual void CopyTo (Array array, int index)
 701                 {
 702                         if (array == null)
 703                                 throw new ArgumentNullException ();
 704
 705                         // The order of these exception checks may look strange,
 706                         // but that's how the microsoft runtime does it.
 707                         if (this.Rank > 1)
 708                                 throw new RankException ();
 709                         if (index + this.GetLength (0) > array.GetLowerBound (0) + array.GetLength (0))
 710                                 throw new ArgumentException ();
 711                         if (array.Rank > 1)
 712                                 throw new RankException ();
 713                         if (index < 0)
 714                                 throw new ArgumentOutOfRangeException ();
 715
 716                         Copy (this, this.GetLowerBound(0), array, index, this.GetLength (0));
 717                 }
 718
 719                 internal class SimpleEnumerator : IEnumerator {
 720                         Array enumeratee;
 721                         int currentpos;
 722                         int length;
 723
 724                         public SimpleEnumerator (Array arrayToEnumerate) {
 725                                 this.enumeratee = arrayToEnumerate;
 726                                 this.currentpos = -1;
 727                                 this.length = arrayToEnumerate.Length;
 728                         }
 729
 730                         public object Current {
 731                                 get {
 732                                         // Exception messages based on MS implementation
 733                                         if (currentpos < 0 ) {
 734                                                 throw new InvalidOperationException
 735                                                         ("Enumeration has not started");
 736                                         }
 737                                         if  (currentpos >= length) {
 738                                                 throw new InvalidOperationException
 739                                                         ("Enumeration has already ended");
 740                                         }
 741                                         // Current should not increase the position. So no ++ over here.
 742                                         return enumeratee.GetValueImpl(currentpos);
 743                                 }
 744                         }
 745
 746                         public bool MoveNext() {
 747                                 //The docs say Current should throw an exception if last
 748                                 //call to MoveNext returned false. This means currentpos
 749                                 //should be set to length when returning false.
 750                                         if (currentpos < length) {
 751                                                 currentpos++;
 752                                         }
 753                                 if(currentpos < length)
 754                                         return true;
 755                                 else
 756                                         return false;
 757                         }
 758
 759                         public void Reset() {
 760                                 currentpos= -1;
 761                         }
 762                 }
 763         }
 764 }