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 namespace System\r
  11 {
  12
  13         public abstract class Array : ICloneable \r
  14         {
  15                 public int lower_bound = 0;
  16                 private int length;
  17                 private int rank;
  18
  19                 // Properties
  20                 public int Length \r
  21                 {
  22                         get \r
  23                         {
  24                                 return length;
  25                         }
  26                 }
  27
  28                 public int Rank \r
  29                 {
  30                         get \r
  31                         {
  32                                 return rank;
  33                         }
  34                 }
  35
  36                 // Methods
  37                 public static int BinarySearch (Array array, object value)
  38                 {
  39                         return BinarySearch (array, this.lower_bound, this.length, value, null);
  40                 }
  41
  42                 public static int BinarySearch (Array array, object value, IComparer comparer)
  43                 {
  44                         return BinarySearch (array, this.lower_bound, this.length, value, comparer);
  45                 }
  46
  47                 public static int BinarySearch (Array array, int index, int length, object value)
  48                 {
  49                         return BinarySearch (array, index, length, value, null);
  50                 }
  51
  52                 public static int BinarySearch (Array array, int index, int length, object value, IComparer comparer)
  53                 {
  54                         if (array == null)
  55                                 throw new ArgumentNullException ();
  56
  57                         if (array.Rank > 1)
  58                                 throw new RankException ();
  59
  60                         if (index < array.lower_bound || length < 0)
  61                                 throw new ArgumentOutOfRangeException ();
  62
  63                         if (index + length > array.lower_bound + array.Length)
  64                                 throw new ArgumentException ();
  65
  66                         if (comparer == null && !(value is IComparable))
  67                                 throw new ArgumentException ();
  68
  69                         // FIXME: Throw an ArgumentException if comparer
  70                         // is null and value is not of the same type as the
  71                         // elements of array.
  72
  73                         for (int i = 0; i < length; i++) \r
  74                         {
  75                                 int result;
  76
  77                                 if (comparer == null && !(array.GetValue(index + i) is IComparable))
  78                                         throw new ArgumentException ();
  79
  80                                 if (comparer == null)
  81                                         result = value.CompareTo(array.GetValue(index + i));
  82                                 else
  83                                         result = comparer.Compare(value, array.GetValue(index + i));
  84
  85                                 if (result == 0)
  86                                         return index + i;
  87                                 else if (result < 0)
  88                                         return ~(index + i);
  89                         }
  90
  91                         return ~(index + length);
  92                 }
  93
  94                 public static void Clear (Array array, int index, int length)
  95                 {
  96                         if (array == null)
  97                                 throw new ArgumentNullException ();
  98
  99                         if (index < this.lower_bound || length < 0 ||
 100                                 index + length > this.lower_bound + this.length)
 101                                 throw new ArgumentOutOfRangeException ();
 102
 103                         for (int i = 0; i < length; i++) \r
 104                         {
 105                                 if (array.GetValue(index + i) is bool)
 106                                         array.SetValue(false, index + i);
 107                                 else if (array.GetValue(index + i) is ValueType)
 108                                         array.SetValue(0, index + i);
 109                                 else
 110                                         array.SetValue(null, index + i);
 111                         }
 112                 }
 113
 114                 public virtual object Clone ()
 115                 {
 116                         Array a = new Array();
 117
 118                         for (int i = 0; i < this.length; i++) \r
 119                         {
 120                                 int index = this.lower_bound + i;
 121
 122                                 a.SetValue(this.GetValue(index), index);
 123                         }
 124
 125                         return a;
 126                 }
 127
 128                 public static void Copy (Array source, Array dest, int length)
 129                 {
 130                         Copy (source, source.lower_bound, dest, dest.lower_bound, length);
 131                 }
 132
 133                 public static void Copy (Array source, int source_idx, Array dest, int dest_idx, int length)
 134                 {
 135                         if (length < 0)
 136                                 throw new ArgumentOutOfRangeException ();
 137
 138                         if (source == null || dest == null)
 139                                 throw new ArgumentNullException ();
 140
 141                         if (source_idx < source.lower_bound || source_idx + length > source.lower_bound + source.Length || dest_idx < dest.lower_bound || dest_idx + length > dest.lower_bound + dest.Length)
 142                                 throw new ArgumentException ();
 143
 144                         if (source.Rank != dest.Rank)
 145                                 throw new RankException ();
 146
 147                         for (int i = 0; i < length; i++) \r
 148                         {
 149                                 int index = source.lower_bound + i;
 150
 151                                 dest.SetValue(source.GetValue(index), index);
 152                         }
 153                 }
 154
 155                 [MethodImplAttribute(InternalCall)]
 156                 private object InternalGetValue (int index);
 157
 158                 public object GetValue (int index)
 159                 {
 160                         if (this.rank > 1)
 161                                 throw new ArgumentException ();
 162
 163                         if (index < this.lower_bound ||
 164                                 index > this.lower_bound + this.length)
 165                                 throw new ArgumentOutOfRangeException ();
 166
 167                         return InternalGetValue (index);
 168                 }
 169
 170                 [MethodImplAttribute(InternalCall)]
 171                 private void InternalSetValue (object value, int index);
 172
 173                 public void SetValue (object value, int index)
 174                 {
 175                         if (this.rank > 1)
 176                                 throw new ArgumentException ();
 177
 178                         if (index < this.lower_bound ||
 179                                 index > this.lower_bound + this.length)
 180                                 throw new ArgumentOutOfRangeException ();
 181
 182                         InternalSetValue (value);
 183                 }
 184
 185                 public static int IndexOf (Array array, object value)
 186                 {
 187                         return IndexOf (array, value, 0, array.Length);
 188                 }
 189
 190                 public static int IndexOf (Array array, object value, int index)
 191                 {
 192                         return IndexOf (array, value, index, array.Length - index);
 193                 }
 194
 195                 public static int IndexOf (Array array, object value, int index, int length)
 196                 {
 197                         if (array == null)
 198                                 throw new ArgumentNullException ();
 199
 200                         if (length < 0 || index < array.lower_bound || index > array.lower_bound + length)
 201                                 throw new ArgumentOutOfRangeException ();
 202
 203                         for (int i = 0; i < length; i++) \r
 204                         {
 205                                 if (array.GetValue(index + i) == value)
 206                                         return index + i;
 207                         }
 208
 209                         return array.lower_bound - 1;
 210                 }
 211
 212                 public static int LastIndexOf (Array array, object value)
 213                 {
 214                         return LastIndexOf (array, value, 0, array.Length);
 215                 }
 216
 217                 public static int LastIndexOf (Array array, object value, int index)
 218                 {
 219                         return LastIndexOf (array, value, index, array.Length - index);
 220                 }
 221
 222                 public static int LastIndexOf (Array array, object value, int index, int length)
 223                 {
 224                         if (array == null)
 225                                 throw new ArgumentNullException ();
 226
 227                         if (length < 0 || index < array.lower_bound || index > array.lower_bound + length)
 228                                 throw new ArgumentOutOfRangeException ();
 229
 230                         for (int i = length - 1; i >= 0; i--) \r
 231                         {
 232                                 if (array.GetValue(index + i) == value)
 233                                         return index + i;
 234                         }
 235
 236                         return array.lower_bound - 1;
 237                 }
 238
 239                 public static void Reverse (Array array)
 240                 {
 241                         Reverse (array, array.lower_bound, array.Length);
 242                 }
 243
 244                 public static void Reverse (Array array, int index, int length)
 245                 {
 246                         if (array == null)
 247                                 throw new ArgumentNullException ();
 248
 249                         if (array.Rank > 1)
 250                                 throw new RankException ();
 251
 252                         if (index < array.lower_bound || length < 0)
 253                                 throw new ArgumentOutOfRangeException ();
 254
 255                         if (index + length > array.lower_bound + array.Length)
 256                                 throw new ArgumentException ();
 257
 258                         for (int i = 0; i < length/2; i++) \r
 259                         {
 260                                 object tmp;
 261
 262                                 tmp = array.GetValue(index + i);
 263                                 array.SetValue(array.GetValue(index + length - i - 1), index + i);
 264                                 array.SetValue(tmp, index + length - i - 1);
 265                         }
 266                 }
 267
 268                 public static void Sort (Array array)
 269                 {
 270                         Sort (array, null, array.lower_bound, array.Length, null);
 271                 }
 272
 273                 public static void Sort (Array keys, Array items)
 274                 {
 275                         Sort (keys, items, keys.lower_bound, keys.Length, null);
 276                 }
 277
 278                 public static void Sort (Array array, IComparer comparer)
 279                 {
 280                         Sort (array, null, array.lower_bound, array.Length, comparer);
 281                 }
 282
 283                 public static void Sort (Array array, int index, int length)
 284                 {
 285                         Sort (array, null, index, length, null);
 286                 }
 287
 288                 public static void Sort (Array keys, Array items, IComparer comparer)
 289                 {
 290                         Sort (keys, items, keys.lower_bound, keys.Length, comparer);
 291                 }
 292
 293                 public static void Sort (Array keys, Array items, int index, int length)
 294                 {
 295                         Sort (keys, items, index, length, null);
 296                 }
 297
 298                 public static void Sort (Array array, int index, int length, IComparer comparer)
 299                 {
 300                         Sort (array, null, index, length, comparer);
 301                 }
 302
 303                 public static void Sort (Array keys, Array items, int index, int length, IComparer comparer)
 304                 {
 305                         int low0 = index;
 306                         int high0 = index + length - 1;
 307
 308                         qsort (keys, items, index, index + length - 1, comparer);
 309                 }
 310
 311                 private static void qsort (Array keys, Array items, int low0, int high0, IComparer comparer)
 312                 {
 313                         int pivot;
 314                         int low = low0;
 315                         int high = high0;
 316
 317                         if (low >= high)
 318                                 return;
 319
 320                         pivot = (low + high) / 2;
 321
 322                         if (compare(keys.GetValue(low), keys.GetValue(pivot), comparer) > 0)
 323                                 swap(keys, items, low, pivot);
 324
 325                         if (compare(keys.GetValue(pivot), keys.GetValue(high), comparer) > 0)
 326                                 swap(keys, items, pivot, high);
 327
 328                         while (low < high) \r
 329                         {
 330                                 // Move the walls in
 331                                 while (low < high && compare(keys.GetValue(low), keys.GetValue(pivot), comparer) < 0)
 332                                         low++;
 333                                 while (low < high && compare(keys.GetValue(pivot), keys.GetValue(high), comparer) < 0)
 334                                         high--;
 335
 336                                 if (low < high) \r
 337                                 {
 338                                         swap(keys, items, low, high);
 339                                         low++;
 340                                         high--;
 341                                 }
 342                         }
 343
 344                         qsort (keys, items, low0, low - 1);
 345                         qsort (keys, items, high + 1, high0);
 346                 }
 347
 348                 private static void swap (Array keys, Array items, int i, int j)
 349                 {
 350                         object tmp;
 351
 352                         tmp = keys.GetValue(i);
 353                         keys.SetValue(keys.GetValue(j), i);
 354                         keys.SetValue(tmp, j);
 355
 356                         if (items != null) \r
 357                         {
 358                                 tmp = items.GetValue(i);
 359                                 items.SetValue(items.GetValue(j), i);
 360                                 items.SetValue(tmp, j);
 361                         }
 362                 }
 363
 364                 private static int compare (object value1, object value2, IComparer comparer)
 365                 {
 366                         if (comparer == null)
 367                                 return ((IComparable) value1).CompareTo(value2);
 368                         else
 369                                 return comparer.Compare(value1, value2);
 370                 }
 371         }
 372 }