f0abaedc7a9443fa3c49e0cbb4b6b4abdb12d2a4
[idea/community.git] / 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 / 2; 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 }