0fe8eaa0f31431079e16788e5787ee941987e84a
[idea/community.git] / platform / util / src / com / intellij / util / containers / ContainerUtil.java
1 /*
2  * Copyright 2000-2011 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.containers;
17
18 import com.intellij.openapi.Disposable;
19 import com.intellij.openapi.util.Condition;
20 import com.intellij.openapi.util.Disposer;
21 import com.intellij.openapi.util.Factory;
22 import com.intellij.openapi.util.Pair;
23 import com.intellij.util.*;
24 import gnu.trove.THashMap;
25 import gnu.trove.TIntArrayList;
26 import gnu.trove.TObjectHashingStrategy;
27 import org.jetbrains.annotations.NotNull;
28 import org.jetbrains.annotations.Nullable;
29
30 import java.lang.reflect.Array;
31 import java.util.*;
32 import java.util.concurrent.CopyOnWriteArrayList;
33
34 @SuppressWarnings({"UtilityClassWithoutPrivateConstructor", "unchecked"})
35 public class ContainerUtil {
36   private static final int INSERTION_SORT_THRESHOLD = 10;
37
38   @NotNull
39   public static <T> List<T> mergeSortedLists(@NotNull List<T> list1, @NotNull List<T> list2, @NotNull Comparator<? super T> comparator, boolean mergeEqualItems){
40     List<T> result = new ArrayList<T>(list1.size() + list2.size());
41
42     int index1 = 0;
43     int index2 = 0;
44     while (index1 < list1.size() || index2 < list2.size()) {
45       if (index1 >= list1.size()) {
46         result.add(list2.get(index2++));
47       }
48       else if (index2 >= list2.size()) {
49         result.add(list1.get(index1++));
50       }
51       else {
52         T element1 = list1.get(index1);
53         T element2 = list2.get(index2);
54         int c = comparator.compare(element1, element2);
55         if (c < 0) {
56           result.add(element1);
57           index1++;
58         }
59         else if (c > 0) {
60           result.add(element2);
61           index2++;
62         }
63         else {
64           result.add(element1);
65           if (!mergeEqualItems) {
66             result.add(element2);
67           }
68           index1++;
69           index2++;
70         }
71       }
72     }
73
74     return result;
75   }
76   @NotNull
77   public static <T> List<T> mergeSortedArrays(@NotNull T[] list1, @NotNull T[] list2, @NotNull Comparator<? super T> comparator, boolean mergeEqualItems, @Nullable Processor<? super T> filter){
78     int index1 = 0;
79     int index2 = 0;
80     List<T> result = new ArrayList<T>(list1.length + list2.length);
81
82     while (index1 < list1.length || index2 < list2.length) {
83       if (index1 >= list1.length) {
84         T t = list2[index2++];
85         if (filter != null && !filter.process(t)) continue;
86         result.add(t);
87       }
88       else if (index2 >= list2.length) {
89         T t = list1[index1++];
90         if (filter != null && !filter.process(t)) continue;
91         result.add(t);
92       }
93       else {
94         T element1 = list1[index1];
95         if (filter != null && !filter.process(element1)) {
96           index1++;
97           continue;
98         }
99         T element2 = list2[index2];
100         if (filter != null && !filter.process(element2)) {
101           index2++;
102           continue;
103         }
104         int c = comparator.compare(element1, element2);
105         if (c < 0) {
106           result.add(element1);
107           index1++;
108         }
109         else if (c > 0) {
110           result.add(element2);
111           index2++;
112         }
113         else {
114           result.add(element1);
115           if (!mergeEqualItems) {
116             result.add(element2);
117           }
118           index1++;
119           index2++;
120         }
121       }
122     }
123
124     return result;
125   }
126
127   public static <T> List<T> subList(List<T> list, int from) {
128     return list.subList(from, list.size());
129   }
130
131   public static <T> void addAll(@NotNull Collection<T> collection, @NotNull Iterable<T> appendix) {
132     addAll(collection, appendix.iterator());
133   }
134
135   public static <T> void addAll(@NotNull Collection<T> collection, @NotNull Iterator<T> iterator) {
136     while (iterator.hasNext()) {
137       T o = iterator.next();
138       collection.add(o);
139     }
140   }
141
142   @NotNull
143   public static <T> List<T> collect(@NotNull Iterator<T> iterator) {
144     if (!iterator.hasNext()) return Collections.emptyList();
145     List<T> list = new ArrayList<T>();
146     addAll(list, iterator);
147     return list;
148   }
149
150   @NotNull
151   public static <T> Set<T> collectSet(@NotNull Iterator<T> iterator) {
152     if (!iterator.hasNext()) return Collections.emptySet();
153     Set<T> hashSet = new HashSet<T>();
154     addAll(hashSet, iterator);
155     return hashSet;
156   }
157
158   @NotNull
159   public static <K, V> HashMap<K, V> assignKeys(@NotNull Iterator<V> iterator, @NotNull Convertor<V, K> keyConvertor) {
160     HashMap<K, V> hashMap = new HashMap<K, V>();
161     while (iterator.hasNext()) {
162       V value = iterator.next();
163       hashMap.put(keyConvertor.convert(value), value);
164     }
165     return hashMap;
166   }
167
168   @NotNull
169   public static <K, V> Map<K, Set<V>> classify(@NotNull Iterator<V> iterator, @NotNull Convertor<V, K> keyConvertor) {
170     Map<K, Set<V>> hashMap = new LinkedHashMap<K, Set<V>>();
171     while (iterator.hasNext()) {
172       V value = iterator.next();
173       final K key = keyConvertor.convert(value);
174       Set<V> set = hashMap.get(key);
175       if (set == null) {
176         hashMap.put(key, set = new LinkedHashSet<V>()); // ordered set!!
177       }
178       set.add(value);
179     }
180     return hashMap;
181   }
182
183   @NotNull
184   public static <K, V> HashMap<K, V> assignValues(@NotNull Iterator<K> iterator, @NotNull Convertor<K, V> valueConvertor) {
185     HashMap<K, V> hashMap = new HashMap<K, V>();
186     while (iterator.hasNext()) {
187       K key = iterator.next();
188       hashMap.put(key, valueConvertor.convert(key));
189     }
190     return hashMap;
191   }
192
193   @NotNull
194   public static <T> Iterator<T> emptyIterator() {
195     return EmptyIterator.getInstance();
196   }
197
198   @NotNull
199   public static <T> Iterable<T> emptyIterable() {
200     return EmptyIterable.getInstance();
201   }
202
203   @Nullable
204   public static <T> T find(@NotNull T[] array, @NotNull Condition<T> condition) {
205     for (T element : array) {
206       if (condition.value(element)) return element;
207     }
208     return null;
209   }
210
211   public static <T> boolean process(@NotNull Iterable<? extends T> iterable, @NotNull Processor<T> processor) {
212     for (final T t : iterable) {
213       if (!processor.process(t)) {
214         return false;
215       }
216     }
217     return true;
218   }
219
220   public static <T> boolean process(@NotNull List<? extends T> list, @NotNull Processor<T> processor) {
221     //noinspection ForLoopReplaceableByForEach
222     for (int i = 0, size = list.size(); i < size; i++) {
223       T t = list.get(i);
224       if (!processor.process(t)) {
225         return false;
226       }
227     }
228     return true;
229   }
230
231   public static <T> boolean process(@NotNull T[] iterable, @NotNull Processor<? super T> processor) {
232     for (final T t : iterable) {
233       if (!processor.process(t)) {
234         return false;
235       }
236     }
237     return true;
238   }
239
240   @Nullable
241   public static <T, V extends T> V find(@NotNull Iterable<V> iterable, @NotNull Condition<T> condition) {
242     return find(iterable.iterator(), condition);
243   }
244
245   @Nullable
246   public static <T> T find(@NotNull Iterable<? extends T> iterable, final T equalTo) {
247     return find(iterable, new Condition<T>() {
248       public boolean value(final T object) {
249         return equalTo == object || equalTo.equals(object);
250       }
251     });
252   }
253
254   @Nullable
255   public static <T, V extends T> V find(@NotNull Iterator<V> iterator, @NotNull Condition<T> condition) {
256     while (iterator.hasNext()) {
257       V value = iterator.next();
258       if (condition.value(value)) return value;
259     }
260     return null;
261   }
262
263   @NotNull
264   public static <T, V> List<V> map2List(@NotNull T[] array, @NotNull Function<T, V> mapper) {
265     return map2List(Arrays.asList(array), mapper);
266   }
267
268   @NotNull
269   public static <T, V> List<V> map2List(@NotNull Collection<? extends T> collection, @NotNull Function<T, V> mapper) {
270     final ArrayList<V> list = new ArrayList<V>(collection.size());
271     for (final T t : collection) {
272       list.add(mapper.fun(t));
273     }
274     return list;
275   }
276
277   @NotNull
278   public static <T, V> Set<V> map2Set(@NotNull T[] collection, @NotNull Function<T, V> mapper) {
279     return map2Set(Arrays.asList(collection), mapper);
280   }
281
282   @NotNull
283   public static <T, V> Set<V> map2Set(@NotNull Collection<? extends T> collection, @NotNull Function<T, V> mapper) {
284     final HashSet<V> set = new HashSet<V>(collection.size());
285     for (final T t : collection) {
286       set.add(mapper.fun(t));
287     }
288     return set;
289   }
290
291   @NotNull
292   public static <T, KEY, VALUE> Map<KEY, VALUE> map2Map(@NotNull T[] collection, @NotNull Function<T, Pair<KEY, VALUE>> mapper) {
293     return map2Map(Arrays.asList(collection), mapper);
294   }
295
296   @NotNull
297   public static <T, KEY, VALUE> Map<KEY, VALUE> map2Map(@NotNull Collection<? extends T> collection,
298                                                         @NotNull Function<T, Pair<KEY, VALUE>> mapper) {
299     final Map<KEY, VALUE> set = new THashMap<KEY, VALUE>(collection.size());
300     for (T t : collection) {
301       Pair<KEY, VALUE> pair = mapper.fun(t);
302       set.put(pair.first, pair.second);
303     }
304     return set;
305   }
306
307   @NotNull
308   public static <T> Object[] map2Array(@NotNull T[] array, @NotNull Function<T, Object> mapper) {
309     return map2Array(array, Object.class, mapper);
310   }
311
312   @NotNull
313   public static <T> Object[] map2Array(@NotNull Collection<T> array, @NotNull Function<T, Object> mapper) {
314     return map2Array(array, Object.class, mapper);
315   }
316
317   @NotNull
318   public static <T, V> V[] map2Array(@NotNull T[] array, @NotNull Class<? extends V> aClass, @NotNull Function<T, V> mapper) {
319     return map2Array(Arrays.asList(array), aClass, mapper);
320   }
321
322   @NotNull
323   public static <T, V> V[] map2Array(@NotNull Collection<? extends T> collection, @NotNull Class<? extends V> aClass, @NotNull Function<T, V> mapper) {
324     final List<V> list = map2List(collection, mapper);
325     return list.toArray((V[])Array.newInstance(aClass, list.size()));
326   }
327
328   @NotNull
329   public static <T, V> V[] map2Array(@NotNull Collection<? extends T> collection, @NotNull V[] to, @NotNull Function<T, V> mapper) {
330     return map2List(collection, mapper).toArray(to);
331   }
332
333   @NotNull
334   public static <T> List<T> filter(@NotNull T[] collection, @NotNull Condition<? super T> condition) {
335     return findAll(collection, condition);
336   }
337
338   @NotNull
339   public static <T> List<T> findAll(@NotNull T[] collection, @NotNull Condition<? super T> condition) {
340     return findAll(Arrays.asList(collection), condition);
341   }
342
343   @NotNull
344   public static <T> List<T> filter(@NotNull Collection<? extends T> collection, @NotNull Condition<? super T> condition) {
345     return findAll(collection, condition);
346   }
347
348   @NotNull
349   public static <T> List<T> findAll(@NotNull Collection<? extends T> collection, @NotNull Condition<? super T> condition) {
350     final ArrayList<T> result = new ArrayList<T>();
351     for (final T t : collection) {
352       if (condition.value(t)) {
353         result.add(t);
354       }
355     }
356     return result;
357   }
358
359   @NotNull
360   public static <T> List<T> skipNulls(@NotNull Collection<? extends T> collection) {
361     return findAll(collection, Condition.NOT_NULL);
362   }
363
364   @NotNull
365   public static <T, V> List<V> findAll(@NotNull T[] collection, @NotNull Class<V> instanceOf) {
366     return findAll(Arrays.asList(collection), instanceOf);
367   }
368
369   @NotNull
370   public static <T, V> V[] findAllAsArray(@NotNull T[] collection, @NotNull Class<V> instanceOf) {
371     List<V> list = findAll(Arrays.asList(collection), instanceOf);
372     return list.toArray((V[])Array.newInstance(instanceOf, list.size()));
373   }
374
375   @NotNull
376   public static <T, V> V[] findAllAsArray(@NotNull Collection<? extends T> collection, @NotNull Class<V> instanceOf) {
377     List<V> list = findAll(collection, instanceOf);
378     return list.toArray((V[])Array.newInstance(instanceOf, list.size()));
379   }
380
381   @NotNull
382   public static <T> T[] findAllAsArray(@NotNull T[] collection, @NotNull Condition<? super T> instanceOf) {
383     List<T> list = findAll(collection, instanceOf);
384     return list.toArray((T[])Array.newInstance(collection.getClass().getComponentType(), list.size()));
385   }
386
387   @NotNull
388   public static <T, V> List<V> findAll(@NotNull Collection<? extends T> collection, @NotNull Class<V> instanceOf) {
389     final ArrayList<V> result = new ArrayList<V>();
390     for (final T t : collection) {
391       if (instanceOf.isInstance(t)) {
392         result.add((V)t);
393       }
394     }
395     return result;
396   }
397
398   public static <T> void removeDuplicates(@NotNull Collection<T> collection) {
399     Set<T> collected = new HashSet<T>();
400     for (Iterator<T> iterator = collection.iterator(); iterator.hasNext();) {
401       T t = iterator.next();
402       if (!collected.contains(t)) {
403         collected.add(t);
404       }
405       else {
406         iterator.remove();
407       }
408     }
409   }
410
411   public static Map<String, String> stringMap(@NotNull final String... keyValues) {
412     final Map<String, String> result = new HashMap<String, String>();
413     for (int i = 0; i < keyValues.length - 1; i+=2) {
414       result.put(keyValues[i], keyValues[i+1]);
415     }
416
417     return result;
418   }
419
420   @NotNull
421   public static <T> Iterator<T> iterate(@NotNull T[] arrays) {
422     return Arrays.asList(arrays).iterator();
423   }
424
425   @NotNull
426   public static <T> Iterator<T> iterate(@NotNull final Enumeration<T> enumeration) {
427     return new Iterator<T>() {
428       public boolean hasNext() {
429         return enumeration.hasMoreElements();
430       }
431
432       public T next() {
433         return enumeration.nextElement();
434       }
435
436       public void remove() {
437         throw new UnsupportedOperationException();
438       }
439     };
440   }
441
442   @NotNull
443   public static <T> Iterable<T> iterate(@NotNull T[] arrays, @NotNull Condition<? super T> condition) {
444     return iterate(Arrays.asList(arrays), condition);
445   }
446
447   @NotNull
448   public static <T> Iterable<T> iterate(@NotNull final Collection<? extends T> collection, @NotNull final Condition<? super T> condition) {
449     if (collection.isEmpty()) return emptyIterable();
450     return new Iterable<T>() {
451       public Iterator<T> iterator() {
452         return new Iterator<T>() {
453           Iterator<? extends T> impl = collection.iterator();
454           T next = findNext();
455
456           public boolean hasNext() {
457             return next != null;
458           }
459
460           public T next() {
461             T result = next;
462             next = findNext();
463             return result;
464           }
465
466           private T findNext() {
467             while (impl.hasNext()) {
468               T each = impl.next();
469               if (condition.value(each)) {
470                 return each;
471               }
472             }
473             return null;
474           }
475
476           public void remove() {
477             throw new UnsupportedOperationException();
478           }
479         };
480       }
481     };
482   }
483
484   @NotNull
485   public static <T> Iterable<T> iterateBackward(@NotNull final List<? extends T> list) {
486     return new Iterable<T>() {
487       public Iterator<T> iterator() {
488         return new Iterator<T>() {
489           ListIterator<? extends T> it = list.listIterator(list.size());
490
491           public boolean hasNext() {
492             return it.hasPrevious();
493           }
494
495           public T next() {
496             return it.previous();
497           }
498
499           public void remove() {
500             it.remove();
501           }
502         };
503       }
504     };
505   }
506
507   public static <E> void swapElements(@NotNull List<E> list, int index1, int index2) {
508     E e1 = list.get(index1);
509     E e2 = list.get(index2);
510     list.set(index1, e2);
511     list.set(index2, e1);
512   }
513
514   @NotNull
515   public static <T> List<T> collect(@NotNull Iterator<?> iterator, @NotNull FilteringIterator.InstanceOf<T> instanceOf) {
516     return collect(FilteringIterator.create((Iterator<T>)iterator, instanceOf));
517   }
518
519   public static <T> void addAll(@NotNull Collection<T> collection, @NotNull Enumeration<T> enumeration) {
520     while (enumeration.hasMoreElements()) {
521       T element = enumeration.nextElement();
522       collection.add(element);
523     }
524   }
525
526   public static <T, A extends T, C extends Collection<T>> C addAll(@NotNull C collection, @NotNull A... elements) {
527     //noinspection ManualArrayToCollectionCopy
528     for (T element : elements) {
529       collection.add(element);
530     }
531     return collection;
532   }
533
534   public static <T, U extends T> U findInstance(@NotNull Iterable<T> iterable, @NotNull Class<U> aClass) {
535     return findInstance(iterable.iterator(), aClass);
536   }
537
538   public static <T, U extends T> U findInstance(@NotNull Iterator<T> iterator, @NotNull Class<U> aClass) {
539     // uncomment for 1.5
540     //return (U)find(iterator, new FilteringIterator.InstanceOf<U>(aClass));
541     return (U)find(iterator, new FilteringIterator.InstanceOf<T>((Class<T>)aClass));
542   }
543
544   @Nullable
545   public static <T, U extends T> U findInstance(@NotNull T[] array, @NotNull Class<U> aClass) {
546     return findInstance(Arrays.asList(array), aClass);
547   }
548
549   @NotNull
550   public static <T, V> List<T> concat(@NotNull V[] array, @NotNull Function<V, Collection<? extends T>> fun) {
551     return concat(Arrays.asList(array), fun);
552   }
553
554   @NotNull
555   public static <T> List<T> concat(@NotNull Iterable<? extends Collection<T>> list) {
556     List<T> result = new ArrayList<T>();
557     for (final Collection<T> ts : list) {
558       result.addAll(ts);
559     }
560     return result;
561   }
562
563   @NotNull
564   public static <T> List<T> concat(@NotNull final List<? extends T> list1, @NotNull final List<? extends T> list2) {
565     final int size1 = list1.size();
566     final int size = size1 + list2.size();
567
568     return new AbstractList<T>() {
569       public T get(int index) {
570         if (index < size1) {
571           return list1.get(index);
572         }
573
574         return list2.get(index - size1);
575       }
576
577       public int size() {
578         return size;
579       }
580     };
581   }
582
583   @NotNull
584   public static <T> Iterable<T> concat(@NotNull final Iterable<? extends T>... iterables) {
585     return new Iterable<T>() {
586       public Iterator<T> iterator() {
587         Iterator[] iterators = new Iterator[iterables.length];
588         for (int i = 0, iterablesLength = iterables.length; i < iterablesLength; i++) {
589           Iterable<? extends T> iterable = iterables[i];
590           iterators[i] = iterable.iterator();
591         }
592         return new SequenceIterator<T>(iterators);
593       }
594     };
595   }
596   @NotNull
597   public static <T> Iterable<T> concat(@NotNull final T[]... iterables) {
598     return new Iterable<T>() {
599       public Iterator<T> iterator() {
600         Iterator[] iterators = new Iterator[iterables.length];
601         for (int i = 0, iterablesLength = iterables.length; i < iterablesLength; i++) {
602           T[] iterable = iterables[i];
603           iterators[i] = Arrays.asList(iterable).iterator();
604         }
605         return new SequenceIterator<T>(iterators);
606       }
607     };
608   }
609
610   @NotNull
611   public static <T> List<T> concat(@NotNull final List<? extends T>... lists) {
612     int size = 0;
613     for (List<? extends T> each : lists) {
614       size += each.size();
615     }
616     final int finalSize = size;
617     return new AbstractList<T>() {
618       public T get(final int index) {
619         if (index >= 0 && index < finalSize) {
620           int from = 0;
621           for (List<? extends T> each : lists) {
622             if (from <= index && index < from + each.size()) return each.get(index - from);
623             from += each.size();
624           }
625         }
626         throw new IndexOutOfBoundsException("index: " + index + "size: " + size());
627       }
628
629       public int size() {
630         return finalSize;
631       }
632     };
633   }
634
635   @NotNull
636   public static <T> List<T> concat(@NotNull final List<List<? extends T>> lists) {
637     List<? extends T>[] array = lists.toArray(new List[lists.size()]);
638     return concat(array);
639   }
640
641   @NotNull
642   public static <T, V> List<T> concat(@NotNull Iterable<? extends V> list, @NotNull Function<V, Collection<? extends T>> fun) {
643     final ArrayList<T> result = new ArrayList<T>();
644     for (final V v : list) {
645       result.addAll(fun.fun(v));
646     }
647     return result;
648   }
649
650   public static <T> boolean intersects(@NotNull Collection<? extends T> collection1, @NotNull Collection<? extends T> collection2) {
651     for (T t : collection1) {
652       //noinspection SuspiciousMethodCalls
653       if (collection2.contains(t)) {
654         return true;
655       }
656     }
657     return false;
658   }
659
660   @NotNull
661   public static <T> Collection<T> intersection(@NotNull Collection<? extends T> collection1, @NotNull Collection<? extends T> collection2) {
662     ArrayList<T> result = new ArrayList<T>();
663     for (T t : collection1) {
664       if (collection2.contains(t)) {
665         result.add(t);
666       }
667     }
668     return result;
669   }
670
671   @Nullable
672   public static <T> T getFirstItem(final Collection<T> items) {
673     return getFirstItem(items, null);
674   }
675
676   public static <T> T getFirstItem(final Collection<T> items, @Nullable final T def) {
677     return items == null || items.isEmpty() ? def : items.iterator().next();
678   }
679
680   @NotNull
681   public static <T> Collection<T> subtract(@NotNull Collection<T> from, @NotNull Collection<T> what) {
682     final HashSet<T> set = new HashSet<T>(from);
683     set.removeAll(what);
684     return set;
685   }
686
687   public static <T> T[] toArray(@Nullable Collection<T> c, @NotNull ArrayFactory<T> factory) {
688     return c != null ? c.toArray(factory.create(c.size())) : factory.create(0);
689   }
690
691   public static <T> T[] toArray(@NotNull Collection<? extends T> c1, @NotNull Collection<? extends T> c2, @NotNull ArrayFactory<T> factory) {
692     return ArrayUtil.mergeCollections(c1, c2, factory);
693   }
694
695   public static <T> T[] mergeCollectionsToArray(@NotNull Collection<? extends T> c1, @NotNull Collection<? extends T> c2, @NotNull ArrayFactory<T> factory) {
696     return ArrayUtil.mergeCollections(c1, c2, factory);
697   }
698   
699   @NotNull
700   public static <T> T[] toArray(@NotNull List<T> collection, @NotNull T[] array) {
701     final int length = array.length;
702     if (length < 20) {
703       for (int i = 0; i < collection.size(); i++) {
704         array[i] = collection.get(i);
705       }
706       return array;
707     }
708     else {
709       return collection.toArray(array);
710     }
711   }
712
713   /**
714    * This is a replacement for {@link Collection#toArray(Object[])}. For small collections it is faster to stay at java level and refrain
715    * from calling JNI {@link System#arraycopy(Object, int, Object, int, int)}
716    */
717   @NotNull
718   public static <T> T[] toArray(@NotNull Collection<T> c, @NotNull T[] sample) {
719     final int size = c.size();
720     if (size == sample.length && size < 20) {
721       int i = 0;
722       for (T t : c) {
723         sample[i++] = t;
724       }
725       return sample;
726     }
727
728     return c.toArray(sample);
729   }
730
731   public static <T extends Comparable<T>> void sort(@NotNull List<T> list) {
732     int size = list.size();
733
734     if (size < 2) return;
735     if (size == 2) {
736       T t0 = list.get(0);
737       T t1 = list.get(1);
738
739       if (t0.compareTo(t1) > 0) {
740         list.set(0, t1);
741         list.set(1, t0);
742       }
743     }
744     else if (size < INSERTION_SORT_THRESHOLD) {
745       for (int i = 0; i < size; i++) {
746         for (int j = 0; j < i; j++) {
747           T ti = list.get(i);
748           T tj = list.get(j);
749
750           if (ti.compareTo(tj) < 0) {
751             list.set(i, tj);
752             list.set(j, ti);
753           }
754         }
755       }
756     }
757     else {
758       Collections.sort(list);
759     }
760   }
761
762   public static <T> void sort(@NotNull List<T> list, @NotNull Comparator<T> comparator) {
763     int size = list.size();
764
765     if (size < 2) return;
766     if (size == 2) {
767       T t0 = list.get(0);
768       T t1 = list.get(1);
769
770       if (comparator.compare(t0, t1) > 0) {
771         list.set(0, t1);
772         list.set(1, t0);
773       }
774     }
775     else if (size < INSERTION_SORT_THRESHOLD) {
776       for (int i = 0; i < size; i++) {
777         for (int j = 0; j < i; j++) {
778           T ti = list.get(i);
779           T tj = list.get(j);
780
781           if (comparator.compare(ti, tj) < 0) {
782             list.set(i, tj);
783             list.set(j, ti);
784           }
785         }
786       }
787     }
788     else {
789       Collections.sort(list, comparator);
790     }
791   }
792
793   public static <T extends Comparable<T>> void sort(@NotNull T[] a) {
794     int size = a.length;
795
796     if (size < 2) return;
797     if (size == 2) {
798       T t0 = a[0];
799       T t1 = a[1];
800
801       if (t0.compareTo(t1) > 0) {
802         a[0] = t1;
803         a[1] = t0;
804       }
805     }
806     else if (size < INSERTION_SORT_THRESHOLD) {
807       for (int i = 0; i < size; i++) {
808         for (int j = 0; j < i; j++) {
809           T ti = a[i];
810           T tj = a[j];
811
812           if (ti.compareTo(tj) < 0) {
813             a[i] = tj;
814             a[j] = ti;
815           }
816         }
817       }
818     }
819     else {
820       Arrays.sort(a);
821     }
822   }
823
824   public static <T> void sort(@NotNull T[] a, @NotNull Comparator<T> comparator) {
825     int size = a.length;
826
827     if (size < 2) return;
828     if (size == 2) {
829       T t0 = a[0];
830       T t1 = a[1];
831
832       if (comparator.compare(t0, t1) > 0) {
833         a[0] = t1;
834         a[1] = t0;
835       }
836     }
837     else if (size < INSERTION_SORT_THRESHOLD) {
838       for (int i = 0; i < size; i++) {
839         for (int j = 0; j < i; j++) {
840           T ti = a[i];
841           T tj = a[j];
842
843           if (comparator.compare(ti, tj) < 0) {
844             a[i] = tj;
845             a[j] = ti;
846           }
847         }
848       }
849     }
850     else {
851       Arrays.sort(a, comparator);
852     }
853   }
854
855   @NotNull
856   public static <T,V> List<V> map(@NotNull Iterable<? extends T> iterable, @NotNull Function<T, V> mapping) {
857     List<V> result = new ArrayList<V>();
858     for (T t : iterable) {
859       result.add(mapping.fun(t));
860     }
861     return result;
862   }
863   @NotNull
864   public static <T,V> List<V> map(@NotNull Collection<? extends T> iterable, @NotNull Function<T, V> mapping) {
865     List<V> result = new ArrayList<V>(iterable.size());
866     for (T t : iterable) {
867       result.add(mapping.fun(t));
868     }
869     return result;
870   }
871
872   @NotNull
873   public static <T, V> List<V> mapNotNull(@NotNull T[] array, Function<T, V> mapping) {
874     return mapNotNull(Arrays.asList(array), mapping);
875   }
876   public static <T, V> V[] mapNotNull(@NotNull T[] arr, @NotNull Function<T, V> mapping, @NotNull V[] emptyArray) {
877     List<V> result = new ArrayList<V>(arr.length);
878     for (T t : arr) {
879       V v = mapping.fun(t);
880       if (v != null) {
881         result.add(v);
882       }
883     }
884     return result.toArray(emptyArray);
885   }
886
887   @NotNull
888   public static <T, V> List<V> mapNotNull(Iterable<? extends T> iterable, Function<T, V> mapping) {
889     List<V> result = new ArrayList<V>();
890     for (T t : iterable) {
891       final V o = mapping.fun(t);
892       if (o != null) {
893         result.add(o);
894       }
895     }
896     return result;
897   }
898   @NotNull
899   public static <T, V> List<V> mapNotNull(Collection<? extends T> iterable, Function<T, V> mapping) {
900     List<V> result = new ArrayList<V>(iterable.size());
901     for (T t : iterable) {
902       final V o = mapping.fun(t);
903       if (o != null) {
904         result.add(o);
905       }
906     }
907     return result;
908   }
909
910   @NotNull
911   public static <T> List<T> packNullables(@NotNull T... elements) {
912     ArrayList<T> list = new ArrayList<T>();
913     for (T element : elements) {
914       addIfNotNull(element, list);
915     }
916     return list;
917   }
918
919   @NotNull
920   public static <T, V> List<V> map(@NotNull T[] arr, @NotNull Function<T, V> mapping) {
921     List<V> result = new ArrayList<V>(arr.length);
922     for (T t : arr) {
923       result.add(mapping.fun(t));
924     }
925     return result;
926   }
927
928   @NotNull
929   public static <T, V> V[] map(@NotNull T[] arr, @NotNull Function<T, V> mapping, @NotNull V[] emptyArray) {
930     List<V> result = new ArrayList<V>(arr.length);
931     for (T t : arr) {
932       result.add(mapping.fun(t));
933     }
934     return result.toArray(emptyArray);
935   }
936
937   @NotNull
938   public static <T> Set<T> set(T ... items) {
939     return addAll(new HashSet<T>(), items);
940   }
941   
942   public static <T> void addIfNotNull(final T element, @NotNull Collection<T> result) {
943     if (element != null) {
944       result.add(element);
945     }
946   }
947   public static <T> void addIfNotNull(@NotNull Collection<T> result, @Nullable final T element) {
948     if (element != null) {
949       result.add(element);
950     }
951   }
952
953   public static <K, V> void putIfNotNull(final K key, @Nullable V value, @NotNull final Map<K, V> result) {
954     if (value != null) {
955       result.put(key, value);
956     }
957   }
958
959   public static <T> void add(final T element, @NotNull final Collection<T> result, @NotNull final Disposable parentDisposable) {
960     if (result.add(element)) {
961       Disposer.register(parentDisposable, new Disposable() {
962         public void dispose() {
963           result.remove(element);
964         }
965       });
966     }
967   }
968
969   @NotNull
970   public static <T> List<T> createMaybeSingletonList(@Nullable T element) {
971     return element == null ? Collections.<T>emptyList() : Collections.singletonList(element);
972   }
973
974   public static <T, V> V getOrCreate(@NotNull Map<T, V> result, final T key, final V defaultValue) {
975     V value = result.get(key);
976     if (value == null) {
977       result.put(key, value = defaultValue);
978     }
979     return value;
980   }
981
982   public static <T, V> V getOrCreate(@NotNull Map<T, V> result, final T key, @NotNull  Factory<V> factory) {
983     V value = result.get(key);
984     if (value == null) {
985       result.put(key, value = factory.create());
986     }
987     return value;
988   }
989
990   public static <T> boolean and(@NotNull T[] iterable, @NotNull Condition<T> condition) {
991     return and(Arrays.asList(iterable), condition);
992   }
993
994   public static <T> boolean and(@NotNull Iterable<T> iterable, @NotNull Condition<T> condition) {
995     for (final T t : iterable) {
996       if (!condition.value(t)) return false;
997     }
998     return true;
999   }
1000
1001   public static <T> boolean exists(@NotNull T[] iterable, @NotNull Condition<T> condition) {
1002     return or(Arrays.asList(iterable), condition);
1003   }
1004
1005   public static <T> boolean exists(@NotNull Iterable<T> iterable, @NotNull Condition<T> condition) {
1006     return or(iterable, condition);
1007   }
1008
1009   public static <T> boolean or(@NotNull T[] iterable, @NotNull Condition<T> condition) {
1010     return or(Arrays.asList(iterable), condition);
1011   }
1012
1013   public static <T> boolean or(@NotNull Iterable<T> iterable, @NotNull Condition<T> condition) {
1014     for (final T t : iterable) {
1015       if (condition.value(t)) return true;
1016     }
1017     return false;
1018   }
1019
1020   public static <T> List<T> unfold(@Nullable T t, @NotNull NullableFunction<T, T> next) {
1021     if (t == null) return Collections.emptyList();
1022
1023     final ArrayList<T> list = new ArrayList<T>();
1024     while (t != null) {
1025       list.add(t);
1026       t = next.fun(t);
1027     }
1028     return list;
1029   }
1030
1031   @NotNull
1032   public static <T> List<T> dropTail(@NotNull List<T> items) {
1033     return items.subList(0, items.size() - 1);
1034   }
1035
1036   @NotNull
1037   public static <T> List<T> list(@NotNull T... items) {
1038     return Arrays.asList(items);
1039   }
1040
1041   // Generalized Quick Sort. Does neither array.clone() nor list.toArray()
1042
1043   public static <T> void quickSort(@NotNull List<T> list, @NotNull Comparator<? super T> comparator) {
1044     quickSort(list, comparator, 0, list.size());
1045   }
1046
1047   private static <T> void quickSort(@NotNull List<T> x, @NotNull Comparator<? super T> comparator, int off, int len) {
1048     // Insertion sort on smallest arrays
1049     if (len < 7) {
1050       for (int i = off; i < len + off; i++) {
1051         for (int j = i; j > off && comparator.compare(x.get(j), x.get(j - 1)) < 0; j--) {
1052           swapElements(x, j, j - 1);
1053         }
1054       }
1055       return;
1056     }
1057
1058     // Choose a partition element, v
1059     int m = off + (len >> 1);       // Small arrays, middle element
1060     if (len > 7) {
1061       int l = off;
1062       int n = off + len - 1;
1063       if (len > 40) {        // Big arrays, pseudomedian of 9
1064         int s = len / 8;
1065         l = med3(x, comparator, l, l + s, l + 2 * s);
1066         m = med3(x, comparator, m - s, m, m + s);
1067         n = med3(x, comparator, n - 2 * s, n - s, n);
1068       }
1069       m = med3(x, comparator, l, m, n); // Mid-size, med of 3
1070     }
1071     T v = x.get(m);
1072
1073     // Establish Invariant: v* (<v)* (>v)* v*
1074     int a = off;
1075     int b = a;
1076     int c = off + len - 1;
1077     int d = c;
1078     while (true) {
1079       while (b <= c && comparator.compare(x.get(b), v) <= 0) {
1080         if (comparator.compare(x.get(b), v) == 0) {
1081           swapElements(x, a++, b);
1082         }
1083         b++;
1084       }
1085       while (c >= b && comparator.compare(v, x.get(c)) <= 0) {
1086         if (comparator.compare(x.get(c), v) == 0) {
1087           swapElements(x, c, d--);
1088         }
1089         c--;
1090       }
1091       if (b > c) break;
1092       swapElements(x, b++, c--);
1093     }
1094
1095     // Swap partition elements back to middle
1096     int n = off + len;
1097     int s = Math.min(a - off, b - a);
1098     vecswap(x, off, b - s, s);
1099     s = Math.min(d - c, n - d - 1);
1100     vecswap(x, b, n - s, s);
1101
1102     // Recursively sort non-partition-elements
1103     if ((s = b - a) > 1) quickSort(x, comparator, off, s);
1104     if ((s = d - c) > 1) quickSort(x, comparator, n - s, s);
1105   }
1106
1107   /*
1108    * Returns the index of the median of the three indexed longs.
1109    */
1110   private static <T> int med3(@NotNull List<T> x, Comparator<? super T> comparator, int a, int b, int c) {
1111     return comparator.compare(x.get(a), x.get(b)) < 0 ? comparator.compare(x.get(b), x.get(c)) < 0
1112                                                         ? b
1113                                                         : comparator.compare(x.get(a), x.get(c)) < 0 ? c : a
1114                                                       : comparator.compare(x.get(c), x.get(b)) < 0
1115                                                         ? b
1116                                                         : comparator.compare(x.get(c), x.get(a)) < 0 ? c : a;
1117   }
1118
1119   /*
1120    * Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)].
1121    */
1122   private static <T> void vecswap(List<T> x, int a, int b, int n) {
1123     for (int i = 0; i < n; i++, a++, b++) {
1124       swapElements(x, a, b);
1125     }
1126   }
1127
1128   @NotNull
1129   public static <T> CopyOnWriteArrayList<T> createEmptyCOWList() {
1130     // does not create garbage new Object[0]
1131     return new CopyOnWriteArrayList<T>(ContainerUtil.<T>emptyList());
1132   }
1133
1134   @NotNull
1135   public static <T> List<T> emptyList() {
1136     return (List<T>)EmptyList.INSTANCE;
1137   }
1138
1139   /**
1140    * Merge sorted points, which are sorted by x and with equal x by y.
1141    * Result is put to x1 y1.
1142    */
1143   public static void mergeSortedArrays(TIntArrayList x1,
1144                                        TIntArrayList y1,
1145                                        TIntArrayList x2,
1146                                        TIntArrayList y2) {
1147     TIntArrayList newX = new TIntArrayList();
1148     TIntArrayList newY = new TIntArrayList();
1149
1150     int i = 0;
1151     int j = 0;
1152
1153     while (i < x1.size() && j < x2.size()) {
1154       if (x1.get(i) < x2.get(j) || (x1.get(i) == x2.get(j) && y1.get(i) < y2.get(j))) {
1155         newX.add(x1.get(i));
1156         newY.add(y1.get(i));
1157         i++;
1158       }
1159       else if (x1.get(i) > x2.get(j) || (x1.get(i) == x2.get(j) && y1.get(i) > y2.get(j))) {
1160         newX.add(x2.get(j));
1161         newY.add(y2.get(j));
1162         j++;
1163       }
1164       else { //equals
1165         newX.add(x1.get(i));
1166         newY.add(y1.get(i));
1167         i++;
1168         j++;
1169       }
1170     }
1171
1172     while (i < x1.size()) {
1173       newX.add(x1.get(i));
1174       newY.add(y1.get(i));
1175       i++;
1176     }
1177
1178     while (j < x2.size()) {
1179       newX.add(x2.get(j));
1180       newY.add(y2.get(j));
1181       j++;
1182     }
1183
1184     x1.clear();
1185     y1.clear();
1186     x1.add(newX.toNativeArray());
1187     y1.add(newY.toNativeArray());
1188   }
1189
1190   /**
1191    * has optimized toArray() as opposed to the {@link java.util.Collections#emptyList()}
1192    */
1193   private static class EmptyList extends AbstractList<Object> implements RandomAccess {
1194     private static final EmptyList INSTANCE = new EmptyList();
1195
1196     public int size() {
1197       return 0;
1198     }
1199
1200     public boolean contains(Object obj) {
1201       return false;
1202     }
1203
1204     public Object get(int index) {
1205       throw new IndexOutOfBoundsException("Index: " + index);
1206     }
1207
1208     @Override
1209     public Object[] toArray() {
1210       return ArrayUtil.EMPTY_OBJECT_ARRAY;
1211     }
1212
1213     @Override
1214     public <T> T[] toArray(T[] a) {
1215       return a;
1216     }
1217   }
1218
1219   @NotNull
1220   public static <T> Set<T> singleton(final T o, @NotNull final TObjectHashingStrategy<T> strategy) {
1221     return new Set<T>() {
1222       public int size() {
1223         return 1;
1224       }
1225
1226       public boolean isEmpty() {
1227         return false;
1228       }
1229
1230       public boolean contains(Object elem) {
1231         return strategy.equals(o, (T)elem);
1232       }
1233
1234       public Iterator<T> iterator() {
1235         return new Iterator<T>() {
1236           boolean atEnd;
1237
1238           public boolean hasNext() {
1239             return !atEnd;
1240           }
1241
1242           public T next() {
1243             if (atEnd) throw new NoSuchElementException();
1244             atEnd = true;
1245             return o;
1246           }
1247
1248           public void remove() {
1249             throw new IncorrectOperationException();
1250           }
1251         };
1252       }
1253
1254       public Object[] toArray() {
1255         return new Object[]{o};
1256       }
1257
1258       public <T> T[] toArray(T[] a) {
1259         assert a.length == 1;
1260         a[0] = (T)o;
1261         return a;
1262       }
1263
1264       public boolean add(T t) {
1265         throw new IncorrectOperationException();
1266       }
1267
1268       public boolean remove(Object o) {
1269         throw new IncorrectOperationException();
1270       }
1271
1272       public boolean containsAll(Collection<?> c) {
1273         return false;
1274       }
1275
1276       public boolean addAll(Collection<? extends T> c) {
1277         throw new IncorrectOperationException();
1278       }
1279
1280       public boolean retainAll(Collection<?> c) {
1281         throw new IncorrectOperationException();
1282       }
1283
1284       public boolean removeAll(Collection<?> c) {
1285         throw new IncorrectOperationException();
1286       }
1287
1288       public void clear() {
1289         throw new IncorrectOperationException();
1290       }
1291     };
1292   }
1293
1294   @NotNull
1295   public static <E> List<E> flatten(@NotNull Collection<E>[] collections) {
1296     return flatten(Arrays.asList(collections));
1297   }
1298   @NotNull
1299   public static <E> List<E> flatten(@NotNull Iterable<? extends Collection<E>> collections) {
1300     List<E> result = new ArrayList<E>();
1301     for (Collection<E> list : collections) {
1302       result.addAll(list);
1303     }
1304
1305     return result;
1306   }
1307
1308   public static <K,V> V[] convert(K[] from, V[] to, Function<K,V> fun) {
1309     if (to.length < from.length) {
1310       to = (V[])Array.newInstance(to.getClass().getComponentType(), from.length);
1311     }
1312     for (int i = 0; i < from.length; i++) {
1313       to[i] = fun.fun(from[i]);
1314     }
1315     return to;
1316   }
1317
1318   public static <T> int indexOf(List<T> list, Condition<T> condition) {
1319     for (int i = 0, listSize = list.size(); i < listSize; i++) {
1320       T t = list.get(i);
1321       if (condition.value(t)) {
1322         return i;
1323       }
1324     }
1325     return -1;
1326   }
1327
1328   public static <A,B> Map<B,A> reverseMap(Map<A,B> map) {
1329     final Map<B,A> result = new HashMap<B, A>();
1330     for (A a : map.keySet()) {
1331       result.put(map.get(a), a);
1332     }
1333     return result;
1334   }
1335
1336   public static <T> boolean processRecursively(final T root, final PairProcessor<T, List<T>> processor) {
1337     final LinkedList<T> list = new LinkedList<T>();
1338     list.add(root);
1339     while (!list.isEmpty()) {
1340       final T o = list.removeFirst();
1341       if (!processor.process(o, list)) return false;
1342     }
1343     return true;
1344   }
1345
1346   public static <T> List<T> trimToSize(List<T> list) {
1347     if (list == null) return null;
1348     if (list.isEmpty()) return Collections.emptyList();
1349
1350     if (list instanceof ArrayList) {
1351       list = new ArrayList(list);
1352     }
1353
1354     return list;
1355   }
1356 }