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         public abstract class Array : ICloneable, ICollection
  17         {
  18                 // Constructor
  19                 protected Array ()
  20                 {
  21                         /* empty */
  22                 }
  23
  24                 // Properties
  25                 public int Length
  26                 {
  27                         get
  28                         {
  29                                 int length = this.GetLength (0);
  30
  31                                 for (int i = 1; i < this.Rank; i++) {
  32                                         length *= this.GetLength (i);
  33                                 }
  34
  35                                 return length;
  36                         }
  37                 }
  38
  39                 public int Rank
  40                 {
  41                         get
  42                         {
  43                                 return this.GetRank ();
  44                         }
  45                 }
  46
  47                 // InternalCall Methods
  48
  49                 [MethodImplAttribute(MethodImplOptions.InternalCall)]
  50                 public extern int GetRank ();
  51
  52                 [MethodImplAttribute(MethodImplOptions.InternalCall)]
  53                 public extern int GetLength (int dimension);
  54
  55                 [MethodImplAttribute(MethodImplOptions.InternalCall)]
  56                 public extern int GetLowerBound (int dimension);
  57
  58                 [MethodImplAttribute(MethodImplOptions.InternalCall)]
  59                 public extern object GetValue (int[] idxs);
  60
  61                 [MethodImplAttribute(MethodImplOptions.InternalCall)]
  62                 public extern void SetValue (object value, int[] idxs);
  63
  64                 [MethodImplAttribute(MethodImplOptions.InternalCall)]
  65                 public extern static Array CreateInstance(Type elementType, int[] lengths, int [] bounds);
  66
  67                 // Methods Implementations
  68
  69                 public int Count {
  70                         get {
  71                                 return Length;
  72                         }
  73                 }
  74
  75                 [TODO]
  76                 public bool IsSynchronized {
  77                         get {
  78                                 // FIXME?
  79                                 return false;
  80                         }
  81                 }
  82
  83                 [TODO]
  84                 public object SyncRoot {
  85                         get {
  86                                 // FIXME
  87                                 return null;
  88                         }
  89                 }
  90
  91                 [TODO]
  92                 public virtual IEnumerator GetEnumerator ()
  93                 {
  94                         // FIXME
  95                         return null;
  96                 }
  97
  98                 public int GetUpperBound (int dimension)
  99                 {
 100                         return GetLowerBound (dimension) +
 101                                 GetLength (dimension);
 102                 }
 103
 104                 public object GetValue (int idx)
 105                 {
 106                         int[] ind = new int [1];
 107
 108                         ind [0] = idx;
 109
 110                         return GetValue (ind);
 111                 }
 112
 113                 public object GetValue (int idx1, int idx2)
 114                 {
 115                         int[] ind = new int [2];
 116
 117                         ind [0] = idx1;
 118                         ind [1] = idx2;
 119
 120                         return GetValue (ind);
 121                 }
 122
 123                 public object GetValue (int idx1, int idx2, int idx3)
 124                 {
 125                         int[] ind = new int [3];
 126
 127                         ind [0] = idx1;
 128                         ind [1] = idx2;
 129                         ind [2] = idx3;
 130
 131                         return GetValue (ind);
 132                 }
 133
 134                 public void SetValue (object value, int idx)
 135                 {
 136                         int[] ind = new int [1];
 137
 138                         ind [0] = idx;
 139
 140                         SetValue (value, ind);
 141                 }
 142
 143                 public void SetValue (object value, int idx1, int idx2)
 144                 {
 145                         int[] ind = new int [2];
 146
 147                         ind [0] = idx1;
 148                         ind [1] = idx2;
 149
 150                         SetValue (value, ind);
 151                 }
 152
 153                 public void SetValue (object value, int idx1, int idx2, int idx3)
 154                 {
 155                         int[] ind = new int [3];
 156
 157                         ind [0] = idx1;
 158                         ind [1] = idx2;
 159                         ind [2] = idx3;
 160
 161                         SetValue (value, ind);
 162                 }
 163
 164                 public static Array CreateInstance(Type elementType, int length)
 165                 {
 166                         int[] lengths = new int [1];
 167                         int[] bounds = null;
 168
 169                         lengths [0] = length;
 170
 171                         return CreateInstance (elementType, lengths, bounds);
 172                 }
 173
 174                 public static Array CreateInstance(Type elementType, int l1, int l2)
 175                 {
 176                         int[] lengths = new int [2];
 177                         int[] bounds = null;
 178
 179                         lengths [0] = l1;
 180                         lengths [1] = l2;
 181
 182                         return CreateInstance (elementType, lengths, bounds);
 183                 }
 184
 185                 public static Array CreateInstance(Type elementType, int l1, int l2, int l3)
 186                 {
 187                         int[] lengths = new int [3];
 188                         int[] bounds = null;
 189
 190                         lengths [0] = l1;
 191                         lengths [1] = l2;
 192                         lengths [2] = l3;
 193
 194                         return CreateInstance (elementType, lengths, bounds);
 195                 }
 196
 197                 public static Array CreateInstance(Type elementType, int[] lengths)
 198                 {
 199                         int[] bounds = null;
 200
 201                         return CreateInstance (elementType, lengths, bounds);
 202                 }
 203
 204
 205                 public static int BinarySearch (Array array, object value)
 206                 {
 207                         return BinarySearch (array, array.GetLowerBound (0), array.GetLength (0),
 208                                              value, null);
 209                 }
 210
 211                 public static int BinarySearch (Array array, object value, IComparer comparer)
 212                 {
 213                         return BinarySearch (array, array.GetLowerBound (0), array.GetLength (0),
 214                                              value, comparer);
 215                 }
 216
 217                 public static int BinarySearch (Array array, int index, int length, object value)
 218                 {
 219                         return BinarySearch (array, index, length, value, null);
 220                 }
 221
 222                 public static int BinarySearch (Array array, int index,
 223                                                 int length, object value,
 224                                                 IComparer comparer)
 225                 {
 226                         if (array == null)
 227                                 throw new ArgumentNullException ();
 228
 229                         if (array.Rank > 1)
 230                                 throw new RankException ();
 231
 232                         if (index < array.GetLowerBound (0) || length < 0)
 233                                 throw new ArgumentOutOfRangeException ();
 234
 235                         if (index + length > array.GetUpperBound (0))
 236                                 throw new ArgumentException ();
 237
 238                         if (comparer == null && !(value is IComparable))
 239                                 throw new ArgumentException ();
 240
 241                         // FIXME: Throw an ArgumentException if comparer
 242                         // is null and value is not of the same type as the
 243                         // elements of array.
 244
 245                         for (int i = 0; i < length; i++)
 246                         {
 247                                 int result;
 248
 249                                 if (comparer == null && !(array.GetValue(index + i) is IComparable))
 250                                         throw new ArgumentException ();
 251
 252                                 if (comparer == null)
 253                                         result = (value as IComparable).CompareTo(array.GetValue(index + i));
 254                                 else
 255                                         result = comparer.Compare(value, array.GetValue(index + i));
 256
 257                                 if (result == 0)
 258                                         return index + i;
 259                                 else if (result < 0)
 260                                         return ~(index + i);
 261                         }
 262
 263                         return ~(index + length);
 264                 }
 265
 266                 public static void Clear (Array array, int index, int length)
 267                 {
 268                         if (array == null)
 269                                 throw new ArgumentNullException ();
 270
 271                         if (array.Rank > 1)
 272                                 throw new RankException ();
 273
 274                         if (index < array.GetLowerBound (0) || length < 0 ||
 275                                 index + length > array.GetUpperBound (0))
 276                                 throw new ArgumentOutOfRangeException ();
 277
 278                         for (int i = 0; i < length; i++)
 279                         {
 280                                 if (array.GetValue(index + i) is bool)
 281                                         array.SetValue(false, index + i);
 282                                 else if (array.GetValue(index + i) is ValueType)
 283                                         array.SetValue(0, index + i);
 284                                 else
 285                                         array.SetValue(null, index + i);
 286                         }
 287                 }
 288
 289                 public virtual object Clone ()
 290                 {
 291                         // Array is abstract -- Array a = new Array();
 292                         Array a = (Array)this.Clone();
 293
 294                         // I don't know how to handle this ?
 295                         if (this.Rank > 1)
 296                                 throw new RankException ();
 297
 298                         for (int i = 0; i < this.GetLength (0); i++)
 299                         {
 300                                 int index = this.GetLowerBound (0) + i;
 301
 302                                 a.SetValue(this.GetValue(index), index);
 303                         }
 304
 305                         return a;
 306                 }
 307
 308                 public static void Copy (Array source, Array dest, int length)
 309                 {
 310                         // I don't know how to handle this ?
 311                         if (source.Rank > 1 || dest.Rank > 1)
 312                                 throw new RankException ();
 313
 314                         Copy (source, source.GetLowerBound (0), dest, dest.GetLowerBound (0), length);
 315                 }
 316
 317                 public static void Copy (Array source, int source_idx, Array dest, int dest_idx, int length)
 318                 {
 319                         // I don't know how to handle this ?
 320                         if (source.Rank > 1 || dest.Rank > 1)
 321                                 throw new RankException ();
 322
 323                         if (length < 0)
 324                                 throw new ArgumentOutOfRangeException ();
 325
 326                         if (source == null || dest == null)
 327                                 throw new ArgumentNullException ();
 328
 329                         if (source_idx < source.GetLowerBound (0) ||
 330                             source_idx + length > source.GetUpperBound (0) ||
 331                             dest_idx < dest.GetLowerBound (0) || dest_idx + length > dest.GetUpperBound (0))
 332                                 throw new ArgumentException ();
 333
 334                         if (source.Rank != dest.Rank)
 335                                 throw new RankException ();
 336
 337                         for (int i = 0; i < length; i++)
 338                         {
 339                                 int index = source.GetLowerBound (0) + i + source_idx;
 340
 341                                 dest.SetValue(source.GetValue(index), dest_idx + i + dest.GetLowerBound (0));
 342                         }
 343
 344                 }
 345
 346                 public static int IndexOf (Array array, object value)
 347                 {
 348                         return IndexOf (array, value, 0, array.Length);
 349                 }
 350
 351                 public static int IndexOf (Array array, object value, int index)
 352                 {
 353                         return IndexOf (array, value, index, array.Length - index);
 354                 }
 355
 356                 public static int IndexOf (Array array, object value, int index, int length)
 357                 {
 358                         if (array == null)
 359                                 throw new ArgumentNullException ();
 360
 361                         if (length < 0 || index < array.GetLowerBound (0) ||
 362                             index > array.GetUpperBound (0))
 363                                 throw new ArgumentOutOfRangeException ();
 364
 365                         for (int i = 0; i < length; i++)
 366                         {
 367                                 if (array.GetValue(index + i) == value)
 368                                         return index + i;
 369                         }
 370
 371                         return array.GetLowerBound (0) - 1;
 372                 }
 373
 374                 public static int LastIndexOf (Array array, object value)
 375                 {
 376                         return LastIndexOf (array, value, 0, array.Length);
 377                 }
 378
 379                 public static int LastIndexOf (Array array, object value, int index)
 380                 {
 381                         return LastIndexOf (array, value, index, array.Length - index);
 382                 }
 383
 384                 public static int LastIndexOf (Array array, object value, int index, int length)
 385                 {
 386                         if (array == null)
 387                                 throw new ArgumentNullException ();
 388
 389                         if (length < 0 || index < array.GetLowerBound (0) ||
 390                             index > array.GetUpperBound (0))
 391                                 throw new ArgumentOutOfRangeException ();
 392
 393                         for (int i = length - 1; i >= 0; i--)
 394                         {
 395                                 if (array.GetValue(index + i) == value)
 396                                         return index + i;
 397                         }
 398
 399                         return array.GetLowerBound (0) - 1;
 400                 }
 401
 402                 public static void Reverse (Array array)
 403                 {
 404                         Reverse (array, array.GetLowerBound (0), array.GetLength (0));
 405                 }
 406
 407                 public static void Reverse (Array array, int index, int length)
 408                 {
 409                         if (array == null)
 410                                 throw new ArgumentNullException ();
 411
 412                         if (array.Rank > 1)
 413                                 throw new RankException ();
 414
 415                         if (index < array.GetLowerBound (0) || length < 0)
 416                                 throw new ArgumentOutOfRangeException ();
 417
 418                         if (index + length > array.GetUpperBound (0))
 419                                 throw new ArgumentException ();
 420
 421                         for (int i = 0; i < length/2; i++)
 422                         {
 423                                 object tmp;
 424
 425                                 tmp = array.GetValue (index + i);
 426                                 array.SetValue(array.GetValue (index + length - i - 1), index + i);
 427                                 array.SetValue(tmp, index + length - i - 1);
 428                         }
 429                 }
 430
 431                 public static void Sort (Array array)
 432                 {
 433                         Sort (array, null, array.GetLowerBound (0), array.GetLength (0), null);
 434                 }
 435
 436                 public static void Sort (Array keys, Array items)
 437                 {
 438                         Sort (keys, items, keys.GetLowerBound (0), keys.GetLength (0), null);
 439                 }
 440
 441                 public static void Sort (Array array, IComparer comparer)
 442                 {
 443                         Sort (array, null, array.GetLowerBound (0), array.GetLength (0), comparer);
 444                 }
 445
 446                 public static void Sort (Array array, int index, int length)
 447                 {
 448                         Sort (array, null, index, length, null);
 449                 }
 450
 451                 public static void Sort (Array keys, Array items, IComparer comparer)
 452                 {
 453                         Sort (keys, items, keys.GetLowerBound (0), keys.GetLength (0), comparer);
 454                 }
 455
 456                 public static void Sort (Array keys, Array items, int index, int length)
 457                 {
 458                         Sort (keys, items, index, length, null);
 459                 }
 460
 461                 public static void Sort (Array array, int index, int length, IComparer comparer)
 462                 {
 463                         Sort (array, null, index, length, comparer);
 464                 }
 465
 466                 public static void Sort (Array keys, Array items, int index, int length, IComparer comparer)
 467                 {
 468                         int low0 = index;
 469                         int high0 = index + length - 1;
 470
 471                         qsort (keys, items, index, index + length - 1, comparer);
 472                 }
 473
 474                 private static void qsort (Array keys, Array items, int low0, int high0, IComparer comparer)
 475                 {
 476                         int pivot;
 477                         int low = low0;
 478                         int high = high0;
 479
 480                         if (keys.Rank > 1 || (items != null && items.Rank > 1))
 481                                 throw new RankException ();
 482
 483                         if (low >= high)
 484                                 return;
 485
 486                         pivot = (low + high) / 2;
 487
 488                         if (compare (keys.GetValue (low), keys.GetValue (pivot), comparer) > 0)
 489                                 swap (keys, items, low, pivot);
 490
 491                         if (compare (keys.GetValue (pivot), keys.GetValue (high), comparer) > 0)
 492                                 swap (keys, items, pivot, high);
 493
 494                         while (low < high)
 495                         {
 496                                 // Move the walls in
 497                                 while (low < high && compare (keys.GetValue (low), keys.GetValue (pivot), comparer) < 0)
 498                                         low++;
 499                                 while (low < high && compare (keys.GetValue (pivot), keys.GetValue (high), comparer) < 0)
 500                                         high--;
 501
 502                                 if (low < high)
 503                                 {
 504                                         swap (keys, items, low, high);
 505                                         low++;
 506                                         high--;
 507                                 }
 508                         }
 509
 510                         qsort (keys, items, low0, low - 1, comparer);
 511                         qsort (keys, items, high + 1, high0, comparer);
 512                 }
 513
 514                 private static void swap (Array keys, Array items, int i, int j)
 515                 {
 516                         object tmp;
 517
 518                         tmp = keys.GetValue (i);
 519                         keys.SetValue (keys.GetValue (j), i);
 520                         keys.SetValue (tmp, j);
 521
 522                         if (items != null)
 523                         {
 524                                 tmp = items.GetValue (i);
 525                                 items.SetValue (items.GetValue (j), i);
 526                                 items.SetValue (tmp, j);
 527                         }
 528                 }
 529
 530                 private static int compare (object value1, object value2, IComparer comparer)
 531                 {
 532                         if (comparer == null)
 533                                 return ((IComparable) value1).CompareTo(value2);
 534                         else
 535                                 return comparer.Compare(value1, value2);
 536                 }
 537
 538                 public virtual void CopyTo (Array array, int index)
 539                 {
 540                         Copy (this, this.GetLowerBound(0), array, index, this.GetUpperBound (0));
 541                 }
 542         }
 543 }