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