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