2 * Copyright 2000-2015 JetBrains s.r.o.
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
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
16 package com.intellij.util;
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;
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;
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);
51 public static final ArrayFactory<String> STRING_ARRAY_FACTORY = new ArrayFactory<String>() {
54 public String[] create(int count) {
55 return newStringArray(count);
58 public static final ArrayFactory<Object> OBJECT_ARRAY_FACTORY = new ArrayFactory<Object>() {
61 public Object[] create(int count) {
62 return newObjectArray(count);
66 private ArrayUtil() { }
70 public static byte[] realloc(@NotNull byte[] array, final int newSize) {
72 return EMPTY_BYTE_ARRAY;
75 final int oldSize = array.length;
76 if (oldSize == newSize) {
80 final byte[] result = new byte[newSize];
81 System.arraycopy(array, 0, result, 0, Math.min(oldSize, newSize));
86 public static boolean[] realloc(@NotNull boolean[] array, final int newSize) {
88 return EMPTY_BOOLEAN_ARRAY;
91 final int oldSize = array.length;
92 if (oldSize == newSize) {
96 boolean[] result = new boolean[newSize];
97 System.arraycopy(array, 0, result, 0, Math.min(oldSize, newSize));
103 public static long[] realloc(@NotNull long[] array, int newSize) {
105 return EMPTY_LONG_ARRAY;
108 final int oldSize = array.length;
109 if (oldSize == newSize) {
113 long[] result = new long[newSize];
114 System.arraycopy(array, 0, result, 0, Math.min(oldSize, newSize));
119 public static int[] realloc(@NotNull int[] array, final int newSize) {
121 return EMPTY_INT_ARRAY;
124 final int oldSize = array.length;
125 if (oldSize == newSize) {
129 final int[] result = new int[newSize];
130 System.arraycopy(array, 0, result, 0, Math.min(oldSize, newSize));
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) {
141 T[] result = factory.create(newSize);
146 System.arraycopy(array, 0, result, 0, Math.min(oldSize, newSize));
152 public static long[] append(@NotNull long[] array, long value) {
153 array = realloc(array, array.length + 1);
154 array[array.length - 1] = value;
159 public static int[] append(@NotNull int[] array, int value) {
160 array = realloc(array, array.length + 1);
161 array[array.length - 1] = value;
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);
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);
188 public static byte[] append(@NotNull byte[] array, byte value) {
189 array = realloc(array, array.length + 1);
190 array[array.length - 1] = value;
195 public static boolean[] append(@NotNull boolean[] array, boolean value) {
196 array = realloc(array, array.length + 1);
197 array[array.length - 1] = value;
203 public static char[] realloc(@NotNull char[] array, final int newSize) {
205 return EMPTY_CHAR_ARRAY;
208 final int oldSize = array.length;
209 if (oldSize == newSize) {
213 final char[] result = new char[newSize];
214 System.arraycopy(array, 0, result, 0, Math.min(oldSize, newSize));
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);
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);
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()]);
243 public static int[] toIntArray(@NotNull Collection<Integer> list) {
244 int[] ret = newIntArray(list.size());
246 for (Integer e : list) {
247 ret[i++] = e.intValue();
254 public static <T> T[] mergeArrays(@NotNull T[] a1, @NotNull T[] a2) {
255 if (a1.length == 0) {
258 if (a2.length == 0) {
262 final Class<?> class1 = a1.getClass().getComponentType();
263 final Class<?> class2 = a2.getClass().getComponentType();
264 final Class<?> aClass = class1.isAssignableFrom(class2) ? class1 : class2;
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);
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());
292 public static <T> T[] mergeArrays(@NotNull T[] a1, @NotNull T[] a2, @NotNull ArrayFactory<T> factory) {
293 if (a1.length == 0) {
296 if (a2.length == 0) {
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);
307 public static String[] mergeArrays(@NotNull String[] a1, @NotNull String... a2) {
308 return mergeArrays(a1, a2, STRING_ARRAY_FACTORY);
313 public static int[] mergeArrays(@NotNull int[] a1, @NotNull int[] a2) {
314 if (a1.length == 0) {
317 if (a2.length == 0) {
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);
328 public static byte[] mergeArrays(@NotNull byte[] a1, @NotNull byte[] a2) {
329 if (a1.length == 0) {
332 if (a2.length == 0) {
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);
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.
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
352 public static <T> T[] mergeArrayAndCollection(@NotNull T[] array,
353 @NotNull Collection<T> collection,
354 @NotNull final ArrayFactory<T> factory) {
355 if (collection.isEmpty()) {
361 array2 = collection.toArray(factory.create(collection.size()));
363 catch (ArrayStoreException e) {
364 throw new RuntimeException("Bad elements in collection: " + collection, e);
367 if (array.length == 0) {
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);
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.
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.
387 public static <T> T[] append(@NotNull final T[] src, @Nullable final T element) {
388 return append(src, element, (Class<T>)src.getClass().getComponentType());
393 public static <T> T[] prepend(final T element, @NotNull final T[] array) {
394 return prepend(element, array, (Class<T>)array.getClass().getComponentType());
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);
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);
419 public static byte[] prepend(byte element, @NotNull byte[] array) {
420 int length = array.length;
421 final byte[] result = new byte[length + 1];
423 System.arraycopy(array, 0, result, 1, length);
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;
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;
448 * Removes element with index <code>idx</code> from array <code>src</code>.
451 * @param idx index of element to be removed.
452 * @return modified array.
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);
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);
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);
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);
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;
486 return remove(src, idx);
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;
495 return remove(src, idx, factory);
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);
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);
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);
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);
524 public static int find(@NotNull int[] src, int obj) {
525 return indexOf(src, obj);
529 public static <T> int find(@NotNull final T[] src, final T obj) {
530 return ArrayUtilRt.find(src, obj);
534 public static boolean startsWith(@NotNull byte[] array, @NotNull byte[] prefix) {
535 if (array == prefix) {
538 int length = prefix.length;
539 if (array.length < length) {
543 for (int i = 0; i < length; i++) {
544 if (array[i] != prefix[i]) {
553 public static <E> boolean startsWith(@NotNull E[] array, @NotNull E[] subArray) {
554 if (array == subArray) {
557 int length = subArray.length;
558 if (array.length < length) {
562 for (int i = 0; i < length; i++) {
563 if (!Comparing.equal(array[i], subArray[i])) {
572 public static boolean startsWith(@NotNull byte[] array, int start, @NotNull byte[] subArray) {
573 int length = subArray.length;
574 if (array.length - start < length) {
578 for (int i = 0; i < length; i++) {
579 if (array[start + i] != subArray[i]) {
588 public static <T> boolean equals(@NotNull T[] a1, @NotNull T[] a2, @NotNull Equality<? super T> comparator) {
593 int length = a2.length;
594 if (a1.length != length) {
598 for (int i = 0; i < length; i++) {
599 if (!comparator.equals(a1[i], a2[i])) {
607 public static <T> boolean equals(@NotNull T[] a1, @NotNull T[] a2, @NotNull Comparator<? super T> comparator) {
611 int length = a2.length;
612 if (a1.length != length) {
616 for (int i = 0; i < length; i++) {
617 if (comparator.compare(a1[i], a2[i]) != 0) {
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];
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];
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);
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;
663 //must be Comparables
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;
677 public static <T> void swap(@NotNull T[] array, int i1, int i2) {
678 final T t = array[i1];
679 array[i1] = array[i2];
683 public static void swap(@NotNull int[] array, int i1, int i2) {
684 final int t = array[i1];
685 array[i1] = array[i2];
689 public static void swap(@NotNull boolean[] array, int i1, int i2) {
690 final boolean t = array[i1];
691 array[i1] = array[i2];
695 public static void swap(@NotNull char[] array, int i1, int i2) {
696 final char t = array[i1];
697 array[i1] = array[i2];
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);
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);
714 public static int indexOf(@NotNull Object[] objects, @Nullable Object object) {
715 return indexOf(objects, object, 0, objects.length);
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;
726 for (int i = start; i < end; i++) {
727 if (object.equals(objects[i])) return i;
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;
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;
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;
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;
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;
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;
783 public static <T> int lastIndexOf(@NotNull final T[] src, final T obj) {
784 for (int i = src.length - 1; i >= 0; i--) {
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];
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--) {
815 if (comparator.equals(obj, o)) {
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)) {
834 public static boolean contains(@Nullable final Object o, @NotNull Object... objects) {
835 return indexOf(objects, o) >= 0;
839 public static boolean contains(@Nullable final String s, @NotNull String... strings) {
841 for (String str : strings) {
842 if (str == null) return true;
846 for (String str : strings) {
847 if (s.equals(str)) return true;
856 public static int[] newIntArray(int count) {
857 return count == 0 ? EMPTY_INT_ARRAY : new int[count];
862 public static long[] newLongArray(int count) {
863 return count == 0 ? EMPTY_LONG_ARRAY : new long[count];
868 public static String[] newStringArray(int count) {
869 return count == 0 ? EMPTY_STRING_ARRAY : new String[count];
874 public static Object[] newObjectArray(int count) {
875 return count == 0 ? EMPTY_OBJECT_ARRAY : new Object[count];
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);
888 public static <T> T getFirstElement(@Nullable T[] array) {
889 return array != null && array.length > 0 ? array[0] : null;
894 public static <T> T getLastElement(@Nullable T[] array) {
895 return array != null && array.length > 0 ? array[array.length - 1] : null;
900 public static String[] toStringArray(@Nullable Collection<String> collection) {
901 return ArrayUtilRt.toStringArray(collection);
904 public static <T> void copy(@NotNull final Collection<? extends T> src, @NotNull final T[] dst, final int dstOffset) {
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;
916 private static <T> int trailingNullsIndex(@NotNull T[] array) {
917 for (int i = array.length - 1; i >= 0; i--) {
918 if (array[i] != null) {
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) {
931 for (int i= n /2- n / part /2; i< n /2+ n / part /2; i++) {
934 int middlePartLength = n / part;
935 return middlePartLength == 0 ? 0 : total / middlePartLength;
937 public static long averageAmongMedians(@NotNull int[] time, int part) {
942 for (int i= n /2- n / part /2; i< n /2+ n / part /2; i++) {
945 int middlePartLength = n / part;
946 return middlePartLength == 0 ? 0 : total / middlePartLength;