mcs/class/corlib/System/Array.cs

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