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