platform/util/src/com/intellij/util/ArrayUtil.java

   1 /*
   2  * Copyright 2000-2015 JetBrains s.r.o.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  * http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16 package com.intellij.util;
  17
  18 import com.intellij.openapi.util.Comparing;
  19 import com.intellij.util.text.CharArrayCharSequence;
  20 import gnu.trove.Equality;
  21 import org.jetbrains.annotations.Contract;
  22 import org.jetbrains.annotations.NotNull;
  23 import org.jetbrains.annotations.Nullable;
  24
  25 import java.io.File;
  26 import java.lang.reflect.Array;
  27 import java.util.Arrays;
  28 import java.util.Collection;
  29 import java.util.Comparator;
  30 import java.util.List;
  31
  32 /**
  33  * Author: msk
  34  */
  35 @SuppressWarnings("MethodOverridesStaticMethodOfSuperclass")
  36 public class ArrayUtil extends ArrayUtilRt {
  37   public static final short[] EMPTY_SHORT_ARRAY = ArrayUtilRt.EMPTY_SHORT_ARRAY;
  38   public static final char[] EMPTY_CHAR_ARRAY = ArrayUtilRt.EMPTY_CHAR_ARRAY;
  39   public static final byte[] EMPTY_BYTE_ARRAY = ArrayUtilRt.EMPTY_BYTE_ARRAY;
  40   public static final int[] EMPTY_INT_ARRAY = ArrayUtilRt.EMPTY_INT_ARRAY;
  41   public static final boolean[] EMPTY_BOOLEAN_ARRAY = ArrayUtilRt.EMPTY_BOOLEAN_ARRAY;
  42   public static final Object[] EMPTY_OBJECT_ARRAY = ArrayUtilRt.EMPTY_OBJECT_ARRAY;
  43   public static final String[] EMPTY_STRING_ARRAY = ArrayUtilRt.EMPTY_STRING_ARRAY;
  44   public static final Class[] EMPTY_CLASS_ARRAY = ArrayUtilRt.EMPTY_CLASS_ARRAY;
  45   public static final long[] EMPTY_LONG_ARRAY = ArrayUtilRt.EMPTY_LONG_ARRAY;
  46   public static final Collection[] EMPTY_COLLECTION_ARRAY = ArrayUtilRt.EMPTY_COLLECTION_ARRAY;
  47   public static final File[] EMPTY_FILE_ARRAY = ArrayUtilRt.EMPTY_FILE_ARRAY;
  48   public static final Runnable[] EMPTY_RUNNABLE_ARRAY = ArrayUtilRt.EMPTY_RUNNABLE_ARRAY;
  49   public static final CharSequence EMPTY_CHAR_SEQUENCE = new CharArrayCharSequence(EMPTY_CHAR_ARRAY);
  50
  51   public static final ArrayFactory<String> STRING_ARRAY_FACTORY = new ArrayFactory<String>() {
  52     @NotNull
  53     @Override
  54     public String[] create(int count) {
  55       return newStringArray(count);
  56     }
  57   };
  58   public static final ArrayFactory<Object> OBJECT_ARRAY_FACTORY = new ArrayFactory<Object>() {
  59     @NotNull
  60     @Override
  61     public Object[] create(int count) {
  62       return newObjectArray(count);
  63     }
  64   };
  65
  66   private ArrayUtil() { }
  67
  68   @NotNull
  69   @Contract(pure=true)
  70   public static byte[] realloc(@NotNull byte[] array, final int newSize) {
  71     if (newSize == 0) {
  72       return EMPTY_BYTE_ARRAY;
  73     }
  74
  75     final int oldSize = array.length;
  76     if (oldSize == newSize) {
  77       return array;
  78     }
  79
  80     final byte[] result = new byte[newSize];
  81     System.arraycopy(array, 0, result, 0, Math.min(oldSize, newSize));
  82     return result;
  83   }
  84   @NotNull
  85   @Contract(pure=true)
  86   public static boolean[] realloc(@NotNull boolean[] array, final int newSize) {
  87     if (newSize == 0) {
  88       return EMPTY_BOOLEAN_ARRAY;
  89     }
  90
  91     final int oldSize = array.length;
  92     if (oldSize == newSize) {
  93       return array;
  94     }
  95
  96     boolean[] result = new boolean[newSize];
  97     System.arraycopy(array, 0, result, 0, Math.min(oldSize, newSize));
  98     return result;
  99   }
 100
 101   @NotNull
 102   @Contract(pure=true)
 103   public static long[] realloc(@NotNull long[] array, int newSize) {
 104     if (newSize == 0) {
 105       return EMPTY_LONG_ARRAY;
 106     }
 107
 108     final int oldSize = array.length;
 109     if (oldSize == newSize) {
 110       return array;
 111     }
 112
 113     long[] result = new long[newSize];
 114     System.arraycopy(array, 0, result, 0, Math.min(oldSize, newSize));
 115     return result;
 116   }
 117   @NotNull
 118   @Contract(pure=true)
 119   public static int[] realloc(@NotNull int[] array, final int newSize) {
 120     if (newSize == 0) {
 121       return EMPTY_INT_ARRAY;
 122     }
 123
 124     final int oldSize = array.length;
 125     if (oldSize == newSize) {
 126       return array;
 127     }
 128
 129     final int[] result = new int[newSize];
 130     System.arraycopy(array, 0, result, 0, Math.min(oldSize, newSize));
 131     return result;
 132   }
 133   @NotNull
 134   @Contract(pure=true)
 135   public static <T> T[] realloc(@NotNull T[] array, final int newSize, @NotNull ArrayFactory<T> factory) {
 136     final int oldSize = array.length;
 137     if (oldSize == newSize) {
 138       return array;
 139     }
 140
 141     T[] result = factory.create(newSize);
 142     if (newSize == 0) {
 143       return result;
 144     }
 145
 146     System.arraycopy(array, 0, result, 0, Math.min(oldSize, newSize));
 147     return result;
 148   }
 149
 150   @NotNull
 151   @Contract(pure=true)
 152   public static long[] append(@NotNull long[] array, long value) {
 153     array = realloc(array, array.length + 1);
 154     array[array.length - 1] = value;
 155     return array;
 156   }
 157   @NotNull
 158   @Contract(pure=true)
 159   public static int[] append(@NotNull int[] array, int value) {
 160     array = realloc(array, array.length + 1);
 161     array[array.length - 1] = value;
 162     return array;
 163   }
 164
 165   @NotNull
 166   @Contract(pure=true)
 167   public static <T> T[] insert(@NotNull T[] array, int index, T value) {
 168     @SuppressWarnings("unchecked")
 169     T[] result = (T[])Array.newInstance(array.getClass().getComponentType(), array.length + 1);
 170     System.arraycopy(array, 0, result, 0, index);
 171     result[index] = value;
 172     System.arraycopy(array, index, result, index + 1, array.length - index);
 173     return result;
 174   }
 175
 176   @NotNull
 177   @Contract(pure=true)
 178   public static int[] insert(@NotNull int[] array, int index, int value) {
 179     int[] result = new int[array.length + 1];
 180     System.arraycopy(array, 0, result, 0, index);
 181     result[index] = value;
 182     System.arraycopy(array, index, result, index+1, array.length - index);
 183     return result;
 184   }
 185
 186   @NotNull
 187   @Contract(pure=true)
 188   public static byte[] append(@NotNull byte[] array, byte value) {
 189     array = realloc(array, array.length + 1);
 190     array[array.length - 1] = value;
 191     return array;
 192   }
 193   @NotNull
 194   @Contract(pure=true)
 195   public static boolean[] append(@NotNull boolean[] array, boolean value) {
 196     array = realloc(array, array.length + 1);
 197     array[array.length - 1] = value;
 198     return array;
 199   }
 200
 201   @NotNull
 202   @Contract(pure=true)
 203   public static char[] realloc(@NotNull char[] array, final int newSize) {
 204     if (newSize == 0) {
 205       return EMPTY_CHAR_ARRAY;
 206     }
 207
 208     final int oldSize = array.length;
 209     if (oldSize == newSize) {
 210       return array;
 211     }
 212
 213     final char[] result = new char[newSize];
 214     System.arraycopy(array, 0, result, 0, Math.min(oldSize, newSize));
 215     return result;
 216   }
 217
 218   @NotNull
 219   @Contract(pure=true)
 220   public static <T> T[] toObjectArray(@NotNull Collection<T> collection, @NotNull Class<T> aClass) {
 221     @SuppressWarnings("unchecked") T[] array = (T[])Array.newInstance(aClass, collection.size());
 222     return collection.toArray(array);
 223   }
 224
 225   @NotNull
 226   @Contract(pure=true)
 227   public static <T> T[] toObjectArray(@NotNull Class<T> aClass, @NotNull Object... source) {
 228     @SuppressWarnings("unchecked") T[] array = (T[])Array.newInstance(aClass, source.length);
 229     System.arraycopy(source, 0, array, 0, array.length);
 230     return array;
 231   }
 232
 233   @NotNull
 234   @Contract(pure=true)
 235   public static Object[] toObjectArray(@NotNull Collection<?> collection) {
 236     if (collection.isEmpty()) return EMPTY_OBJECT_ARRAY;
 237     //noinspection SSBasedInspection
 238     return collection.toArray(new Object[collection.size()]);
 239   }
 240
 241   @NotNull
 242   @Contract(pure=true)
 243   public static int[] toIntArray(@NotNull Collection<Integer> list) {
 244     int[] ret = newIntArray(list.size());
 245     int i = 0;
 246     for (Integer e : list) {
 247       ret[i++] = e.intValue();
 248     }
 249     return ret;
 250   }
 251
 252   @NotNull
 253   @Contract(pure=true)
 254   public static <T> T[] mergeArrays(@NotNull T[] a1, @NotNull T[] a2) {
 255     if (a1.length == 0) {
 256       return a2;
 257     }
 258     if (a2.length == 0) {
 259       return a1;
 260     }
 261
 262     final Class<?> class1 = a1.getClass().getComponentType();
 263     final Class<?> class2 = a2.getClass().getComponentType();
 264     final Class<?> aClass = class1.isAssignableFrom(class2) ? class1 : class2;
 265
 266     @SuppressWarnings("unchecked") T[] result = (T[])Array.newInstance(aClass, a1.length + a2.length);
 267     System.arraycopy(a1, 0, result, 0, a1.length);
 268     System.arraycopy(a2, 0, result, a1.length, a2.length);
 269     return result;
 270   }
 271
 272   @NotNull
 273   @Contract(pure=true)
 274   public static <T> T[] mergeCollections(@NotNull Collection<? extends T> c1, @NotNull Collection<? extends T> c2, @NotNull ArrayFactory<T> factory) {
 275     T[] res = factory.create(c1.size() + c2.size());
 276
 277     int i = 0;
 278
 279     for (T t : c1) {
 280       res[i++] = t;
 281     }
 282
 283     for (T t : c2) {
 284       res[i++] = t;
 285     }
 286
 287     return res;
 288   }
 289
 290   @NotNull
 291   @Contract(pure=true)
 292   public static <T> T[] mergeArrays(@NotNull T[] a1, @NotNull T[] a2, @NotNull ArrayFactory<T> factory) {
 293     if (a1.length == 0) {
 294       return a2;
 295     }
 296     if (a2.length == 0) {
 297       return a1;
 298     }
 299     T[] result = factory.create(a1.length + a2.length);
 300     System.arraycopy(a1, 0, result, 0, a1.length);
 301     System.arraycopy(a2, 0, result, a1.length, a2.length);
 302     return result;
 303   }
 304
 305   @NotNull
 306   @Contract(pure=true)
 307   public static String[] mergeArrays(@NotNull String[] a1, @NotNull String... a2) {
 308     return mergeArrays(a1, a2, STRING_ARRAY_FACTORY);
 309   }
 310
 311   @NotNull
 312   @Contract(pure=true)
 313   public static int[] mergeArrays(@NotNull int[] a1, @NotNull int[] a2) {
 314     if (a1.length == 0) {
 315       return a2;
 316     }
 317     if (a2.length == 0) {
 318       return a1;
 319     }
 320     int[] result = new int[a1.length + a2.length];
 321     System.arraycopy(a1, 0, result, 0, a1.length);
 322     System.arraycopy(a2, 0, result, a1.length, a2.length);
 323     return result;
 324   }
 325
 326   @NotNull
 327   @Contract(pure=true)
 328   public static byte[] mergeArrays(@NotNull byte[] a1, @NotNull byte[] a2) {
 329     if (a1.length == 0) {
 330       return a2;
 331     }
 332     if (a2.length == 0) {
 333       return a1;
 334     }
 335     byte[] result = new byte[a1.length + a2.length];
 336     System.arraycopy(a1, 0, result, 0, a1.length);
 337     System.arraycopy(a2, 0, result, a1.length, a2.length);
 338     return result;
 339   }
 340
 341   /**
 342    * Allocates new array of size <code>array.length + collection.size()</code> and copies elements of <code>array</code> and
 343    * <code>collection</code> to it.
 344    *
 345    * @param array      source array
 346    * @param collection source collection
 347    * @param factory    array factory used to create destination array of type <code>T</code>
 348    * @return destination array
 349    */
 350   @NotNull
 351   @Contract(pure=true)
 352   public static <T> T[] mergeArrayAndCollection(@NotNull T[] array,
 353                                                 @NotNull Collection<T> collection,
 354                                                 @NotNull final ArrayFactory<T> factory) {
 355     if (collection.isEmpty()) {
 356       return array;
 357     }
 358
 359     final T[] array2;
 360     try {
 361       array2 = collection.toArray(factory.create(collection.size()));
 362     }
 363     catch (ArrayStoreException e) {
 364       throw new RuntimeException("Bad elements in collection: " + collection, e);
 365     }
 366
 367     if (array.length == 0) {
 368       return array2;
 369     }
 370
 371     final T[] result = factory.create(array.length + collection.size());
 372     System.arraycopy(array, 0, result, 0, array.length);
 373     System.arraycopy(array2, 0, result, array.length, array2.length);
 374     return result;
 375   }
 376
 377   /**
 378    * Appends <code>element</code> to the <code>src</code> array. As you can
 379    * imagine the appended element will be the last one in the returned result.
 380    *
 381    * @param src     array to which the <code>element</code> should be appended.
 382    * @param element object to be appended to the end of <code>src</code> array.
 383    * @return new array
 384    */
 385   @NotNull
 386   @Contract(pure=true)
 387   public static <T> T[] append(@NotNull final T[] src, @Nullable final T element) {
 388     return append(src, element, (Class<T>)src.getClass().getComponentType());
 389   }
 390
 391   @NotNull
 392   @Contract(pure=true)
 393   public static <T> T[] prepend(final T element, @NotNull final T[] array) {
 394     return prepend(element, array, (Class<T>)array.getClass().getComponentType());
 395   }
 396
 397   @NotNull
 398   @Contract(pure=true)
 399   public static <T> T[] prepend(T element, @NotNull T[] array, @NotNull Class<T> type) {
 400     int length = array.length;
 401     T[] result = (T[])Array.newInstance(type, length + 1);
 402     System.arraycopy(array, 0, result, 1, length);
 403     result[0] = element;
 404     return result;
 405   }
 406
 407   @NotNull
 408   @Contract(pure=true)
 409   public static <T> T[] prepend(final T element, @NotNull final T[] src, @NotNull ArrayFactory<T> factory) {
 410     int length = src.length;
 411     T[] result = factory.create(length + 1);
 412     System.arraycopy(src, 0, result, 1, length);
 413     result[0] = element;
 414     return result;
 415   }
 416
 417   @NotNull
 418   @Contract(pure=true)
 419   public static byte[] prepend(byte element, @NotNull byte[] array) {
 420     int length = array.length;
 421     final byte[] result = new byte[length + 1];
 422     result[0] = element;
 423     System.arraycopy(array, 0, result, 1, length);
 424     return result;
 425   }
 426
 427   @NotNull
 428   @Contract(pure=true)
 429   public static <T> T[] append(@NotNull final T[] src, final T element, @NotNull ArrayFactory<T> factory) {
 430     int length = src.length;
 431     T[] result = factory.create(length + 1);
 432     System.arraycopy(src, 0, result, 0, length);
 433     result[length] = element;
 434     return result;
 435   }
 436
 437   @NotNull
 438   @Contract(pure=true)
 439   public static <T> T[] append(@NotNull T[] src, @Nullable final T element, @NotNull Class<T> componentType) {
 440     int length = src.length;
 441     T[] result = (T[])Array.newInstance(componentType, length + 1);
 442     System.arraycopy(src, 0, result, 0, length);
 443     result[length] = element;
 444     return result;
 445   }
 446
 447   /**
 448    * Removes element with index <code>idx</code> from array <code>src</code>.
 449    *
 450    * @param src array.
 451    * @param idx index of element to be removed.
 452    * @return modified array.
 453    */
 454   @NotNull
 455   @Contract(pure=true)
 456   public static <T> T[] remove(@NotNull final T[] src, int idx) {
 457     int length = src.length;
 458     if (idx < 0 || idx >= length) {
 459       throw new IllegalArgumentException("invalid index: " + idx);
 460     }
 461     T[] result = (T[])Array.newInstance(src.getClass().getComponentType(), length - 1);
 462     System.arraycopy(src, 0, result, 0, idx);
 463     System.arraycopy(src, idx + 1, result, idx, length - idx - 1);
 464     return result;
 465   }
 466
 467   @NotNull
 468   @Contract(pure=true)
 469   public static <T> T[] remove(@NotNull final T[] src, int idx, @NotNull ArrayFactory<T> factory) {
 470     int length = src.length;
 471     if (idx < 0 || idx >= length) {
 472       throw new IllegalArgumentException("invalid index: " + idx);
 473     }
 474     T[] result = factory.create(length - 1);
 475     System.arraycopy(src, 0, result, 0, idx);
 476     System.arraycopy(src, idx + 1, result, idx, length - idx - 1);
 477     return result;
 478   }
 479
 480   @NotNull
 481   @Contract(pure=true)
 482   public static <T> T[] remove(@NotNull final T[] src, T element) {
 483     final int idx = find(src, element);
 484     if (idx == -1) return src;
 485
 486     return remove(src, idx);
 487   }
 488
 489   @NotNull
 490   @Contract(pure=true)
 491   public static <T> T[] remove(@NotNull final T[] src, T element, @NotNull ArrayFactory<T> factory) {
 492     final int idx = find(src, element);
 493     if (idx == -1) return src;
 494
 495     return remove(src, idx, factory);
 496   }
 497
 498   @NotNull
 499   @Contract(pure=true)
 500   public static int[] remove(@NotNull final int[] src, int idx) {
 501     int length = src.length;
 502     if (idx < 0 || idx >= length) {
 503       throw new IllegalArgumentException("invalid index: " + idx);
 504     }
 505     int[] result = newIntArray(src.length - 1);
 506     System.arraycopy(src, 0, result, 0, idx);
 507     System.arraycopy(src, idx + 1, result, idx, length - idx - 1);
 508     return result;
 509   }
 510   @NotNull
 511   @Contract(pure=true)
 512   public static short[] remove(@NotNull final short[] src, int idx) {
 513     int length = src.length;
 514     if (idx < 0 || idx >= length) {
 515       throw new IllegalArgumentException("invalid index: " + idx);
 516     }
 517     short[] result = src.length == 1 ? EMPTY_SHORT_ARRAY : new short[src.length - 1];
 518     System.arraycopy(src, 0, result, 0, idx);
 519     System.arraycopy(src, idx + 1, result, idx, length - idx - 1);
 520     return result;
 521   }
 522
 523   @Contract(pure=true)
 524   public static int find(@NotNull int[] src, int obj) {
 525     return indexOf(src, obj);
 526   }
 527
 528   @Contract(pure=true)
 529   public static <T> int find(@NotNull final T[] src, final T obj) {
 530     return ArrayUtilRt.find(src, obj);
 531   }
 532
 533   @Contract(pure=true)
 534   public static boolean startsWith(@NotNull byte[] array, @NotNull byte[] prefix) {
 535     if (array == prefix) {
 536       return true;
 537     }
 538     int length = prefix.length;
 539     if (array.length < length) {
 540       return false;
 541     }
 542
 543     for (int i = 0; i < length; i++) {
 544       if (array[i] != prefix[i]) {
 545         return false;
 546       }
 547     }
 548
 549     return true;
 550   }
 551
 552   @Contract(pure=true)
 553   public static <E> boolean startsWith(@NotNull E[] array, @NotNull E[] subArray) {
 554     if (array == subArray) {
 555       return true;
 556     }
 557     int length = subArray.length;
 558     if (array.length < length) {
 559       return false;
 560     }
 561
 562     for (int i = 0; i < length; i++) {
 563       if (!Comparing.equal(array[i], subArray[i])) {
 564         return false;
 565       }
 566     }
 567
 568     return true;
 569   }
 570
 571   @Contract(pure=true)
 572   public static boolean startsWith(@NotNull byte[] array, int start, @NotNull byte[] subArray) {
 573     int length = subArray.length;
 574     if (array.length - start < length) {
 575       return false;
 576     }
 577
 578     for (int i = 0; i < length; i++) {
 579       if (array[start + i] != subArray[i]) {
 580         return false;
 581       }
 582     }
 583
 584     return true;
 585   }
 586
 587   @Contract(pure=true)
 588   public static <T> boolean equals(@NotNull T[] a1, @NotNull T[] a2, @NotNull Equality<? super T> comparator) {
 589     if (a1 == a2) {
 590       return true;
 591     }
 592
 593     int length = a2.length;
 594     if (a1.length != length) {
 595       return false;
 596     }
 597
 598     for (int i = 0; i < length; i++) {
 599       if (!comparator.equals(a1[i], a2[i])) {
 600         return false;
 601       }
 602     }
 603     return true;
 604   }
 605
 606   @Contract(pure=true)
 607   public static <T> boolean equals(@NotNull T[] a1, @NotNull T[] a2, @NotNull Comparator<? super T> comparator) {
 608     if (a1 == a2) {
 609       return true;
 610     }
 611     int length = a2.length;
 612     if (a1.length != length) {
 613       return false;
 614     }
 615
 616     for (int i = 0; i < length; i++) {
 617       if (comparator.compare(a1[i], a2[i]) != 0) {
 618         return false;
 619       }
 620     }
 621     return true;
 622   }
 623
 624   @NotNull
 625   @Contract(pure=true)
 626   public static <T> T[] reverseArray(@NotNull T[] array) {
 627     T[] newArray = array.clone();
 628     for (int i = 0; i < array.length; i++) {
 629       newArray[array.length - i - 1] = array[i];
 630     }
 631     return newArray;
 632   }
 633
 634   @NotNull
 635   @Contract(pure=true)
 636   public static int[] reverseArray(@NotNull int[] array) {
 637     int[] newArray = array.clone();
 638     for (int i = 0; i < array.length; i++) {
 639       newArray[array.length - i - 1] = array[i];
 640     }
 641     return newArray;
 642   }
 643
 644   public static void reverse(@NotNull char[] array) {
 645     for (int i = 0; i < array.length; i++) {
 646       swap(array, array.length - i - 1, i);
 647     }
 648   }
 649
 650   @Contract(pure=true)
 651   public static int lexicographicCompare(@NotNull String[] obj1, @NotNull String[] obj2) {
 652     for (int i = 0; i < Math.max(obj1.length, obj2.length); i++) {
 653       String o1 = i < obj1.length ? obj1[i] : null;
 654       String o2 = i < obj2.length ? obj2[i] : null;
 655       if (o1 == null) return -1;
 656       if (o2 == null) return 1;
 657       int res = o1.compareToIgnoreCase(o2);
 658       if (res != 0) return res;
 659     }
 660     return 0;
 661   }
 662
 663   //must be Comparables
 664   @Contract(pure=true)
 665   public static <T> int lexicographicCompare(@NotNull T[] obj1, @NotNull T[] obj2) {
 666     for (int i = 0; i < Math.max(obj1.length, obj2.length); i++) {
 667       T o1 = i < obj1.length ? obj1[i] : null;
 668       T o2 = i < obj2.length ? obj2[i] : null;
 669       if (o1 == null) return -1;
 670       if (o2 == null) return 1;
 671       int res = ((Comparable)o1).compareTo(o2);
 672       if (res != 0) return res;
 673     }
 674     return 0;
 675   }
 676
 677   public static <T> void swap(@NotNull T[] array, int i1, int i2) {
 678     final T t = array[i1];
 679     array[i1] = array[i2];
 680     array[i2] = t;
 681   }
 682
 683   public static void swap(@NotNull int[] array, int i1, int i2) {
 684     final int t = array[i1];
 685     array[i1] = array[i2];
 686     array[i2] = t;
 687   }
 688
 689   public static void swap(@NotNull boolean[] array, int i1, int i2) {
 690     final boolean t = array[i1];
 691     array[i1] = array[i2];
 692     array[i2] = t;
 693   }
 694
 695   public static void swap(@NotNull char[] array, int i1, int i2) {
 696     final char t = array[i1];
 697     array[i1] = array[i2];
 698     array[i2] = t;
 699   }
 700
 701   public static <T> void rotateLeft(@NotNull T[] array, int i1, int i2) {
 702     final T t = array[i1];
 703     System.arraycopy(array, i1 + 1, array, i1, i2 - i1);
 704     array[i2] = t;
 705   }
 706
 707   public static <T> void rotateRight(@NotNull T[] array, int i1, int i2) {
 708     final T t = array[i2];
 709     System.arraycopy(array, i1, array, i1 + 1, i2 - i1);
 710     array[i1] = t;
 711   }
 712
 713   @Contract(pure=true)
 714   public static int indexOf(@NotNull Object[] objects, @Nullable Object object) {
 715     return indexOf(objects, object, 0, objects.length);
 716   }
 717
 718   @Contract(pure=true)
 719   public static int indexOf(@NotNull Object[] objects, Object object, int start, int end) {
 720     if (object == null) {
 721       for (int i = start; i < end; i++) {
 722         if (objects[i] == null) return i;
 723       }
 724     }
 725     else {
 726       for (int i = start; i < end; i++) {
 727         if (object.equals(objects[i])) return i;
 728       }
 729     }
 730     return -1;
 731   }
 732
 733   @Contract(pure=true)
 734   public static <T> int indexOf(@NotNull List<T> objects, T object, @NotNull Equality<T> comparator) {
 735     for (int i = 0; i < objects.size(); i++) {
 736       if (comparator.equals(objects.get(i), object)) return i;
 737     }
 738     return -1;
 739   }
 740
 741   @Contract(pure=true)
 742   public static <T> int indexOf(@NotNull List<T> objects, T object, @NotNull Comparator<T> comparator) {
 743     for (int i = 0; i < objects.size(); i++) {
 744       if (comparator.compare(objects.get(i), object) == 0) return i;
 745     }
 746     return -1;
 747   }
 748
 749   @Contract(pure=true)
 750   public static <T> int indexOf(@NotNull T[] objects, T object, @NotNull Equality<T> comparator) {
 751     for (int i = 0; i < objects.length; i++) {
 752       if (comparator.equals(objects[i], object)) return i;
 753     }
 754     return -1;
 755   }
 756
 757   @Contract(pure=true)
 758   public static int indexOf(@NotNull long[] ints, long value) {
 759     for (int i = 0; i < ints.length; i++) {
 760       if (ints[i] == value) return i;
 761     }
 762
 763     return -1;
 764   }
 765   @Contract(pure=true)
 766   public static int indexOf(@NotNull int[] ints, int value) {
 767     for (int i = 0; i < ints.length; i++) {
 768       if (ints[i] == value) return i;
 769     }
 770
 771     return -1;
 772   }
 773   @Contract(pure=true)
 774   public static int indexOf(@NotNull short[] ints, short value) {
 775     for (int i = 0; i < ints.length; i++) {
 776       if (ints[i] == value) return i;
 777     }
 778
 779     return -1;
 780   }
 781
 782   @Contract(pure=true)
 783   public static <T> int lastIndexOf(@NotNull final T[] src, final T obj) {
 784     for (int i = src.length - 1; i >= 0; i--) {
 785       final T o = src[i];
 786       if (o == null) {
 787         if (obj == null) {
 788           return i;
 789         }
 790       }
 791       else {
 792         if (o.equals(obj)) {
 793           return i;
 794         }
 795       }
 796     }
 797     return -1;
 798   }
 799
 800   @Contract(pure=true)
 801   public static <T> int lastIndexOf(@NotNull final int[] src, final int obj) {
 802     for (int i = src.length - 1; i >= 0; i--) {
 803       final int o = src[i];
 804       if (o == obj) {
 805           return i;
 806       }
 807     }
 808     return -1;
 809   }
 810
 811   @Contract(pure=true)
 812   public static <T> int lastIndexOf(@NotNull final T[] src, final T obj, @NotNull Equality<? super T> comparator) {
 813     for (int i = src.length - 1; i >= 0; i--) {
 814       final T o = src[i];
 815       if (comparator.equals(obj, o)) {
 816         return i;
 817       }
 818     }
 819     return -1;
 820   }
 821
 822   @Contract(pure=true)
 823   public static <T> int lastIndexOf(@NotNull List<T> src, final T obj, @NotNull Equality<? super T> comparator) {
 824     for (int i = src.size() - 1; i >= 0; i--) {
 825       final T o = src.get(i);
 826       if (comparator.equals(obj, o)) {
 827         return i;
 828       }
 829     }
 830     return -1;
 831   }
 832
 833   @Contract(pure=true)
 834   public static boolean contains(@Nullable final Object o, @NotNull Object... objects) {
 835     return indexOf(objects, o) >= 0;
 836   }
 837
 838   @Contract(pure=true)
 839   public static boolean contains(@Nullable final String s, @NotNull String... strings) {
 840     if (s == null) {
 841       for (String str : strings) {
 842         if (str == null) return true;
 843       }
 844     }
 845     else {
 846       for (String str : strings) {
 847         if (s.equals(str)) return true;
 848       }
 849     }
 850
 851     return false;
 852   }
 853
 854   @NotNull
 855   @Contract(pure=true)
 856   public static int[] newIntArray(int count) {
 857     return count == 0 ? EMPTY_INT_ARRAY : new int[count];
 858   }
 859
 860   @NotNull
 861   @Contract(pure=true)
 862   public static long[] newLongArray(int count) {
 863     return count == 0 ? EMPTY_LONG_ARRAY : new long[count];
 864   }
 865
 866   @NotNull
 867   @Contract(pure=true)
 868   public static String[] newStringArray(int count) {
 869     return count == 0 ? EMPTY_STRING_ARRAY : new String[count];
 870   }
 871
 872   @NotNull
 873   @Contract(pure=true)
 874   public static Object[] newObjectArray(int count) {
 875     return count == 0 ? EMPTY_OBJECT_ARRAY : new Object[count];
 876   }
 877
 878   @NotNull
 879   @Contract(pure=true)
 880   public static <E> E[] ensureExactSize(int count, @NotNull E[] sample) {
 881     if (count == sample.length) return sample;
 882     @SuppressWarnings({"unchecked"}) final E[] array = (E[])Array.newInstance(sample.getClass().getComponentType(), count);
 883     return array;
 884   }
 885
 886   @Nullable
 887   @Contract(pure=true)
 888   public static <T> T getFirstElement(@Nullable T[] array) {
 889     return array != null && array.length > 0 ? array[0] : null;
 890   }
 891
 892   @Nullable
 893   @Contract(pure=true)
 894   public static <T> T getLastElement(@Nullable T[] array) {
 895     return array != null && array.length > 0 ? array[array.length - 1] : null;
 896   }
 897
 898   @NotNull
 899   @Contract(pure=true)
 900   public static String[] toStringArray(@Nullable Collection<String> collection) {
 901     return ArrayUtilRt.toStringArray(collection);
 902   }
 903
 904   public static <T> void copy(@NotNull final Collection<? extends T> src, @NotNull final T[] dst, final int dstOffset) {
 905     int i = dstOffset;
 906     for (T t : src) {
 907       dst[i++] = t;
 908     }
 909   }
 910
 911   @NotNull
 912   public static <T> T[] stripTrailingNulls(@NotNull T[] array) {
 913     return array.length != 0 && array[array.length-1] == null ? Arrays.copyOf(array, trailingNullsIndex(array)) : array;
 914   }
 915
 916   private static <T> int trailingNullsIndex(@NotNull T[] array) {
 917     for (int i = array.length - 1; i >= 0; i--) {
 918       if (array[i] != null) {
 919         return i + 1;
 920       }
 921     }
 922     return 0;
 923   }
 924
 925   // calculates average of the median values in the selected part of the array. E.g. for part=3 returns average in the middle third.
 926   public static long averageAmongMedians(@NotNull long[] time, int part) {
 927     assert part >= 1;
 928     int n = time.length;
 929     Arrays.sort(time);
 930     long total = 0;
 931     for (int i= n /2- n / part /2; i< n /2+ n / part /2; i++) {
 932       total += time[i];
 933     }
 934     int middlePartLength = n / part;
 935     return middlePartLength == 0 ? 0 : total / middlePartLength;
 936   }
 937   public static long averageAmongMedians(@NotNull int[] time, int part) {
 938     assert part >= 1;
 939     int n = time.length;
 940     Arrays.sort(time);
 941     long total = 0;
 942     for (int i= n /2- n / part /2; i< n /2+ n / part /2; i++) {
 943       total += time[i];
 944     }
 945     int middlePartLength = n / part;
 946     return middlePartLength == 0 ? 0 : total / middlePartLength;
 947   }
 948 }