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                                                 String.Format ("(Types: source={0};  target={1})", src_type.FullName, dst_type.FullName));
 470                         }
 471                 }
 472
 473                 public static int IndexOf (Array array, object value)
 474                 {
 475                         if (array == null)
 476                                 throw new ArgumentNullException ();
 477
 478                         return IndexOf (array, value, 0, array.Length);
 479                 }
 480
 481                 public static int IndexOf (Array array, object value, int index)
 482                 {
 483                         if (array == null)
 484                                 throw new ArgumentNullException ();
 485
 486                         return IndexOf (array, value, index, array.Length - index);
 487                 }
 488
 489                 public static int IndexOf (Array array, object value, int index, int length)
 490                 {
 491                         if (array == null)
 492                                 throw new ArgumentNullException ();
 493
 494                         if (array.Rank > 1)
 495                                 throw new RankException ();
 496
 497                         if (length < 0 || index < array.GetLowerBound (0) ||
 498                             index+length-1 > array.GetUpperBound (0))
 499                                 throw new ArgumentOutOfRangeException ();
 500
 501                         for (int i = 0; i < length; i++)
 502                         {
 503                                 if (array.GetValue(index + i).Equals(value))
 504                                         return index + i;
 505                         }
 506
 507                         return array.GetLowerBound (0) - 1;
 508                 }
 509
 510                 public static int LastIndexOf (Array array, object value)
 511                 {
 512                         if (array == null)
 513                                 throw new ArgumentNullException ();
 514
 515                         return LastIndexOf (array, value, array.Length-1);
 516                 }
 517
 518                 public static int LastIndexOf (Array array, object value, int index)
 519                 {
 520                         if (array == null)
 521                                 throw new ArgumentNullException ();
 522
 523                         return LastIndexOf (array, value, index, index-array.GetLowerBound(0)+1);
 524                 }
 525
 526                 public static int LastIndexOf (Array array, object value, int index, int length)
 527                 {
 528                         if (array == null)
 529                                 throw new ArgumentNullException ();
 530
 531                         if (array.Rank > 1)
 532                                 throw new RankException ();
 533
 534                         if (length < 0 || index-length+1 < array.GetLowerBound (0) ||
 535                             index > array.GetUpperBound (0))
 536                                 throw new ArgumentOutOfRangeException ();
 537
 538                         for (int i = index; i >= index-length+1; i--)
 539                         {
 540                                 if (array.GetValue(i).Equals(value))
 541                                         return i;
 542                         }
 543
 544                         return array.GetLowerBound (0) - 1;
 545                 }
 546
 547                 public static void Reverse (Array array)
 548                 {
 549                         if (array == null)
 550                                 throw new ArgumentNullException ();
 551
 552                         Reverse (array, array.GetLowerBound (0), array.GetLength (0));
 553                 }
 554
 555                 public static void Reverse (Array array, int index, int length)
 556                 {
 557                         if (array == null)
 558                                 throw new ArgumentNullException ();
 559
 560                         if (array.Rank > 1)
 561                                 throw new RankException ();
 562
 563                         if (index < array.GetLowerBound (0) || length < 0)
 564                                 throw new ArgumentOutOfRangeException ();
 565
 566                         if (index + length > array.GetUpperBound (0) + 1)
 567                                 throw new ArgumentException ();
 568
 569                         for (int i = 0; i < length/2; i++)
 570                         {
 571                                 object tmp;
 572
 573                                 tmp = array.GetValue (index + i);
 574                                 array.SetValue(array.GetValue (index + length - i - 1), index + i);
 575                                 array.SetValue(tmp, index + length - i - 1);
 576                         }
 577                 }
 578
 579                 public static void Sort (Array array)
 580                 {
 581                         if (array == null)
 582                                 throw new ArgumentNullException ();
 583
 584                         Sort (array, null, array.GetLowerBound (0), array.GetLength (0), null);
 585                 }
 586
 587                 public static void Sort (Array keys, Array items)
 588                 {
 589                         if (keys == null)
 590                                 throw new ArgumentNullException ();
 591
 592                         Sort (keys, items, keys.GetLowerBound (0), keys.GetLength (0), null);
 593                 }
 594
 595                 public static void Sort (Array array, IComparer comparer)
 596                 {
 597                         if (array == null)
 598                                 throw new ArgumentNullException ();
 599
 600                         Sort (array, null, array.GetLowerBound (0), array.GetLength (0), comparer);
 601                 }
 602
 603                 public static void Sort (Array array, int index, int length)
 604                 {
 605                         Sort (array, null, index, length, null);
 606                 }
 607
 608                 public static void Sort (Array keys, Array items, IComparer comparer)
 609                 {
 610                         if (keys == null)
 611                                 throw new ArgumentNullException ();
 612
 613                         Sort (keys, items, keys.GetLowerBound (0), keys.GetLength (0), comparer);
 614                 }
 615
 616                 public static void Sort (Array keys, Array items, int index, int length)
 617                 {
 618                         Sort (keys, items, index, length, null);
 619                 }
 620
 621                 public static void Sort (Array array, int index, int length, IComparer comparer)
 622                 {
 623                         Sort (array, null, index, length, comparer);
 624                 }
 625
 626                 public static void Sort (Array keys, Array items, int index, int length, IComparer comparer)
 627                 {
 628                         int low0 = index;
 629                         int high0 = index + length - 1;
 630
 631                         qsort (keys, items, index, index + length - 1, comparer);
 632                 }
 633
 634                 private static void qsort (Array keys, Array items, int low0, int high0, IComparer comparer)
 635                 {
 636                         int pivot;
 637                         int low = low0;
 638                         int high = high0;
 639
 640                         if (keys == null)
 641                                 throw new ArgumentNullException ();
 642
 643                         if (keys.Rank > 1 || (items != null && items.Rank > 1))
 644                                 throw new RankException ();
 645
 646                         if (low >= high)
 647                                 return;
 648
 649                         pivot = (low + high) / 2;
 650
 651                         if (compare (keys.GetValue (low), keys.GetValue (pivot), comparer) > 0)
 652                                 swap (keys, items, low, pivot);
 653
 654                         if (compare (keys.GetValue (pivot), keys.GetValue (high), comparer) > 0)
 655                                 swap (keys, items, pivot, high);
 656
 657                         while (low < high)
 658                         {
 659                                 // Move the walls in
 660                                 while (low < high && compare (keys.GetValue (low), keys.GetValue (pivot), comparer) < 0)
 661                                         low++;
 662                                 while (low < high && compare (keys.GetValue (pivot), keys.GetValue (high), comparer) < 0)
 663                                         high--;
 664
 665                                 if (low < high)
 666                                 {
 667                                         swap (keys, items, low, high);
 668                                         low++;
 669                                         high--;
 670                                 }
 671                         }
 672
 673                         qsort (keys, items, low0, low - 1, comparer);
 674                         qsort (keys, items, high + 1, high0, comparer);
 675                 }
 676
 677                 private static void swap (Array keys, Array items, int i, int j)
 678                 {
 679                         object tmp;
 680
 681                         tmp = keys.GetValue (i);
 682                         keys.SetValue (keys.GetValue (j), i);
 683                         keys.SetValue (tmp, j);
 684
 685                         if (items != null)
 686                         {
 687                                 tmp = items.GetValue (i);
 688                                 items.SetValue (items.GetValue (j), i);
 689                                 items.SetValue (tmp, j);
 690                         }
 691                 }
 692
 693                 private static int compare (object value1, object value2, IComparer comparer)
 694                 {
 695                         if (comparer == null)
 696                                 return ((IComparable) value1).CompareTo(value2);
 697                         else
 698                                 return comparer.Compare(value1, value2);
 699                 }
 700
 701                 public virtual void CopyTo (Array array, int index)
 702                 {
 703                         if (array == null)
 704                                 throw new ArgumentNullException ();
 705
 706                         // The order of these exception checks may look strange,
 707                         // but that's how the microsoft runtime does it.
 708                         if (this.Rank > 1)
 709                                 throw new RankException ();
 710                         if (index + this.GetLength (0) > array.GetLowerBound (0) + array.GetLength (0))
 711                                 throw new ArgumentException ();
 712                         if (array.Rank > 1)
 713                                 throw new RankException ();
 714                         if (index < 0)
 715                                 throw new ArgumentOutOfRangeException ();
 716
 717                         Copy (this, this.GetLowerBound(0), array, index, this.GetLength (0));
 718                 }
 719
 720                 internal class SimpleEnumerator : IEnumerator {
 721                         Array enumeratee;
 722                         int currentpos;
 723                         int length;
 724
 725                         public SimpleEnumerator (Array arrayToEnumerate) {
 726                                 this.enumeratee = arrayToEnumerate;
 727                                 this.currentpos = -1;
 728                                 this.length = arrayToEnumerate.Length;
 729                         }
 730
 731                         public object Current {
 732                                 get {
 733                                         // Exception messages based on MS implementation
 734                                         if (currentpos < 0 ) {
 735                                                 throw new InvalidOperationException
 736                                                         ("Enumeration has not started");
 737                                         }
 738                                         if  (currentpos >= length) {
 739                                                 throw new InvalidOperationException
 740                                                         ("Enumeration has already ended");
 741                                         }
 742                                         // Current should not increase the position. So no ++ over here.
 743                                         return enumeratee.GetValueImpl(currentpos);
 744                                 }
 745                         }
 746
 747                         public bool MoveNext() {
 748                                 //The docs say Current should throw an exception if last
 749                                 //call to MoveNext returned false. This means currentpos
 750                                 //should be set to length when returning false.
 751                                         if (currentpos < length) {
 752                                                 currentpos++;
 753                                         }
 754                                 if(currentpos < length)
 755                                         return true;
 756                                 else
 757                                         return false;
 758                         }
 759
 760                         public void Reset() {
 761                                 currentpos= -1;
 762                         }
 763                 }
 764         }
 765 }