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