IDEA-79726 (Grails: 'Create action' intention should create action in bottom of contr...
[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   @Nullable
681   public static <T> T getLastItem(final Collection<T> items) {
682     Iterator<T> itr = items.iterator();
683     T res = null;
684     while (itr.hasNext()) {
685       res = itr.next();
686     }
687
688     return res;
689   }
690
691   @NotNull
692   public static <T> Collection<T> subtract(@NotNull Collection<T> from, @NotNull Collection<T> what) {
693     final HashSet<T> set = new HashSet<T>(from);
694     set.removeAll(what);
695     return set;
696   }
697
698   public static <T> T[] toArray(@Nullable Collection<T> c, @NotNull ArrayFactory<T> factory) {
699     return c != null ? c.toArray(factory.create(c.size())) : factory.create(0);
700   }
701
702   public static <T> T[] toArray(@NotNull Collection<? extends T> c1, @NotNull Collection<? extends T> c2, @NotNull ArrayFactory<T> factory) {
703     return ArrayUtil.mergeCollections(c1, c2, factory);
704   }
705
706   public static <T> T[] mergeCollectionsToArray(@NotNull Collection<? extends T> c1, @NotNull Collection<? extends T> c2, @NotNull ArrayFactory<T> factory) {
707     return ArrayUtil.mergeCollections(c1, c2, factory);
708   }
709   
710   @NotNull
711   public static <T> T[] toArray(@NotNull List<T> collection, @NotNull T[] array) {
712     final int length = array.length;
713     if (length < 20) {
714       for (int i = 0; i < collection.size(); i++) {
715         array[i] = collection.get(i);
716       }
717       return array;
718     }
719     else {
720       return collection.toArray(array);
721     }
722   }
723
724   /**
725    * This is a replacement for {@link Collection#toArray(Object[])}. For small collections it is faster to stay at java level and refrain
726    * from calling JNI {@link System#arraycopy(Object, int, Object, int, int)}
727    */
728   @NotNull
729   public static <T> T[] toArray(@NotNull Collection<T> c, @NotNull T[] sample) {
730     final int size = c.size();
731     if (size == sample.length && size < 20) {
732       int i = 0;
733       for (T t : c) {
734         sample[i++] = t;
735       }
736       return sample;
737     }
738
739     return c.toArray(sample);
740   }
741
742   public static <T extends Comparable<T>> void sort(@NotNull List<T> list) {
743     int size = list.size();
744
745     if (size < 2) return;
746     if (size == 2) {
747       T t0 = list.get(0);
748       T t1 = list.get(1);
749
750       if (t0.compareTo(t1) > 0) {
751         list.set(0, t1);
752         list.set(1, t0);
753       }
754     }
755     else if (size < INSERTION_SORT_THRESHOLD) {
756       for (int i = 0; i < size; i++) {
757         for (int j = 0; j < i; j++) {
758           T ti = list.get(i);
759           T tj = list.get(j);
760
761           if (ti.compareTo(tj) < 0) {
762             list.set(i, tj);
763             list.set(j, ti);
764           }
765         }
766       }
767     }
768     else {
769       Collections.sort(list);
770     }
771   }
772
773   public static <T> void sort(@NotNull List<T> list, @NotNull Comparator<T> comparator) {
774     int size = list.size();
775
776     if (size < 2) return;
777     if (size == 2) {
778       T t0 = list.get(0);
779       T t1 = list.get(1);
780
781       if (comparator.compare(t0, t1) > 0) {
782         list.set(0, t1);
783         list.set(1, t0);
784       }
785     }
786     else if (size < INSERTION_SORT_THRESHOLD) {
787       for (int i = 0; i < size; i++) {
788         for (int j = 0; j < i; j++) {
789           T ti = list.get(i);
790           T tj = list.get(j);
791
792           if (comparator.compare(ti, tj) < 0) {
793             list.set(i, tj);
794             list.set(j, ti);
795           }
796         }
797       }
798     }
799     else {
800       Collections.sort(list, comparator);
801     }
802   }
803
804   public static <T extends Comparable<T>> void sort(@NotNull T[] a) {
805     int size = a.length;
806
807     if (size < 2) return;
808     if (size == 2) {
809       T t0 = a[0];
810       T t1 = a[1];
811
812       if (t0.compareTo(t1) > 0) {
813         a[0] = t1;
814         a[1] = t0;
815       }
816     }
817     else if (size < INSERTION_SORT_THRESHOLD) {
818       for (int i = 0; i < size; i++) {
819         for (int j = 0; j < i; j++) {
820           T ti = a[i];
821           T tj = a[j];
822
823           if (ti.compareTo(tj) < 0) {
824             a[i] = tj;
825             a[j] = ti;
826           }
827         }
828       }
829     }
830     else {
831       Arrays.sort(a);
832     }
833   }
834
835   public static <T> void sort(@NotNull T[] a, @NotNull Comparator<T> comparator) {
836     int size = a.length;
837
838     if (size < 2) return;
839     if (size == 2) {
840       T t0 = a[0];
841       T t1 = a[1];
842
843       if (comparator.compare(t0, t1) > 0) {
844         a[0] = t1;
845         a[1] = t0;
846       }
847     }
848     else if (size < INSERTION_SORT_THRESHOLD) {
849       for (int i = 0; i < size; i++) {
850         for (int j = 0; j < i; j++) {
851           T ti = a[i];
852           T tj = a[j];
853
854           if (comparator.compare(ti, tj) < 0) {
855             a[i] = tj;
856             a[j] = ti;
857           }
858         }
859       }
860     }
861     else {
862       Arrays.sort(a, comparator);
863     }
864   }
865
866   @NotNull
867   public static <T,V> List<V> map(@NotNull Iterable<? extends T> iterable, @NotNull Function<T, V> mapping) {
868     List<V> result = new ArrayList<V>();
869     for (T t : iterable) {
870       result.add(mapping.fun(t));
871     }
872     return result;
873   }
874   @NotNull
875   public static <T,V> List<V> map(@NotNull Collection<? extends T> iterable, @NotNull Function<T, V> mapping) {
876     List<V> result = new ArrayList<V>(iterable.size());
877     for (T t : iterable) {
878       result.add(mapping.fun(t));
879     }
880     return result;
881   }
882
883   @NotNull
884   public static <T, V> List<V> mapNotNull(@NotNull T[] array, Function<T, V> mapping) {
885     return mapNotNull(Arrays.asList(array), mapping);
886   }
887   public static <T, V> V[] mapNotNull(@NotNull T[] arr, @NotNull Function<T, V> mapping, @NotNull V[] emptyArray) {
888     List<V> result = new ArrayList<V>(arr.length);
889     for (T t : arr) {
890       V v = mapping.fun(t);
891       if (v != null) {
892         result.add(v);
893       }
894     }
895     return result.toArray(emptyArray);
896   }
897
898   @NotNull
899   public static <T, V> List<V> mapNotNull(Iterable<? extends T> iterable, Function<T, V> mapping) {
900     List<V> result = new ArrayList<V>();
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   @NotNull
910   public static <T, V> List<V> mapNotNull(Collection<? extends T> iterable, Function<T, V> mapping) {
911     List<V> result = new ArrayList<V>(iterable.size());
912     for (T t : iterable) {
913       final V o = mapping.fun(t);
914       if (o != null) {
915         result.add(o);
916       }
917     }
918     return result;
919   }
920
921   @NotNull
922   public static <T> List<T> packNullables(@NotNull T... elements) {
923     ArrayList<T> list = new ArrayList<T>();
924     for (T element : elements) {
925       addIfNotNull(element, list);
926     }
927     return list;
928   }
929
930   @NotNull
931   public static <T, V> List<V> map(@NotNull T[] arr, @NotNull Function<T, V> mapping) {
932     List<V> result = new ArrayList<V>(arr.length);
933     for (T t : arr) {
934       result.add(mapping.fun(t));
935     }
936     return result;
937   }
938
939   @NotNull
940   public static <T, V> V[] map(@NotNull T[] arr, @NotNull Function<T, V> mapping, @NotNull V[] emptyArray) {
941     List<V> result = new ArrayList<V>(arr.length);
942     for (T t : arr) {
943       result.add(mapping.fun(t));
944     }
945     return result.toArray(emptyArray);
946   }
947
948   @NotNull
949   public static <T> Set<T> set(T ... items) {
950     return addAll(new HashSet<T>(), items);
951   }
952   
953   public static <T> void addIfNotNull(final T element, @NotNull Collection<T> result) {
954     if (element != null) {
955       result.add(element);
956     }
957   }
958   public static <T> void addIfNotNull(@NotNull Collection<T> result, @Nullable final T element) {
959     if (element != null) {
960       result.add(element);
961     }
962   }
963
964   public static <K, V> void putIfNotNull(final K key, @Nullable V value, @NotNull final Map<K, V> result) {
965     if (value != null) {
966       result.put(key, value);
967     }
968   }
969
970   public static <T> void add(final T element, @NotNull final Collection<T> result, @NotNull final Disposable parentDisposable) {
971     if (result.add(element)) {
972       Disposer.register(parentDisposable, new Disposable() {
973         public void dispose() {
974           result.remove(element);
975         }
976       });
977     }
978   }
979
980   @NotNull
981   public static <T> List<T> createMaybeSingletonList(@Nullable T element) {
982     return element == null ? Collections.<T>emptyList() : Collections.singletonList(element);
983   }
984
985   public static <T, V> V getOrCreate(@NotNull Map<T, V> result, final T key, final V defaultValue) {
986     V value = result.get(key);
987     if (value == null) {
988       result.put(key, value = defaultValue);
989     }
990     return value;
991   }
992
993   public static <T, V> V getOrCreate(@NotNull Map<T, V> result, final T key, @NotNull  Factory<V> factory) {
994     V value = result.get(key);
995     if (value == null) {
996       result.put(key, value = factory.create());
997     }
998     return value;
999   }
1000
1001   public static <T> boolean and(@NotNull T[] iterable, @NotNull Condition<T> condition) {
1002     return and(Arrays.asList(iterable), condition);
1003   }
1004
1005   public static <T> boolean and(@NotNull Iterable<T> iterable, @NotNull Condition<T> condition) {
1006     for (final T t : iterable) {
1007       if (!condition.value(t)) return false;
1008     }
1009     return true;
1010   }
1011
1012   public static <T> boolean exists(@NotNull T[] iterable, @NotNull Condition<T> condition) {
1013     return or(Arrays.asList(iterable), condition);
1014   }
1015
1016   public static <T> boolean exists(@NotNull Iterable<T> iterable, @NotNull Condition<T> condition) {
1017     return or(iterable, condition);
1018   }
1019
1020   public static <T> boolean or(@NotNull T[] iterable, @NotNull Condition<T> condition) {
1021     return or(Arrays.asList(iterable), condition);
1022   }
1023
1024   public static <T> boolean or(@NotNull Iterable<T> iterable, @NotNull Condition<T> condition) {
1025     for (final T t : iterable) {
1026       if (condition.value(t)) return true;
1027     }
1028     return false;
1029   }
1030
1031   public static <T> List<T> unfold(@Nullable T t, @NotNull NullableFunction<T, T> next) {
1032     if (t == null) return Collections.emptyList();
1033
1034     final ArrayList<T> list = new ArrayList<T>();
1035     while (t != null) {
1036       list.add(t);
1037       t = next.fun(t);
1038     }
1039     return list;
1040   }
1041
1042   @NotNull
1043   public static <T> List<T> dropTail(@NotNull List<T> items) {
1044     return items.subList(0, items.size() - 1);
1045   }
1046
1047   @NotNull
1048   public static <T> List<T> list(@NotNull T... items) {
1049     return Arrays.asList(items);
1050   }
1051
1052   // Generalized Quick Sort. Does neither array.clone() nor list.toArray()
1053
1054   public static <T> void quickSort(@NotNull List<T> list, @NotNull Comparator<? super T> comparator) {
1055     quickSort(list, comparator, 0, list.size());
1056   }
1057
1058   private static <T> void quickSort(@NotNull List<T> x, @NotNull Comparator<? super T> comparator, int off, int len) {
1059     // Insertion sort on smallest arrays
1060     if (len < 7) {
1061       for (int i = off; i < len + off; i++) {
1062         for (int j = i; j > off && comparator.compare(x.get(j), x.get(j - 1)) < 0; j--) {
1063           swapElements(x, j, j - 1);
1064         }
1065       }
1066       return;
1067     }
1068
1069     // Choose a partition element, v
1070     int m = off + (len >> 1);       // Small arrays, middle element
1071     if (len > 7) {
1072       int l = off;
1073       int n = off + len - 1;
1074       if (len > 40) {        // Big arrays, pseudomedian of 9
1075         int s = len / 8;
1076         l = med3(x, comparator, l, l + s, l + 2 * s);
1077         m = med3(x, comparator, m - s, m, m + s);
1078         n = med3(x, comparator, n - 2 * s, n - s, n);
1079       }
1080       m = med3(x, comparator, l, m, n); // Mid-size, med of 3
1081     }
1082     T v = x.get(m);
1083
1084     // Establish Invariant: v* (<v)* (>v)* v*
1085     int a = off;
1086     int b = a;
1087     int c = off + len - 1;
1088     int d = c;
1089     while (true) {
1090       while (b <= c && comparator.compare(x.get(b), v) <= 0) {
1091         if (comparator.compare(x.get(b), v) == 0) {
1092           swapElements(x, a++, b);
1093         }
1094         b++;
1095       }
1096       while (c >= b && comparator.compare(v, x.get(c)) <= 0) {
1097         if (comparator.compare(x.get(c), v) == 0) {
1098           swapElements(x, c, d--);
1099         }
1100         c--;
1101       }
1102       if (b > c) break;
1103       swapElements(x, b++, c--);
1104     }
1105
1106     // Swap partition elements back to middle
1107     int n = off + len;
1108     int s = Math.min(a - off, b - a);
1109     vecswap(x, off, b - s, s);
1110     s = Math.min(d - c, n - d - 1);
1111     vecswap(x, b, n - s, s);
1112
1113     // Recursively sort non-partition-elements
1114     if ((s = b - a) > 1) quickSort(x, comparator, off, s);
1115     if ((s = d - c) > 1) quickSort(x, comparator, n - s, s);
1116   }
1117
1118   /*
1119    * Returns the index of the median of the three indexed longs.
1120    */
1121   private static <T> int med3(@NotNull List<T> x, Comparator<? super T> comparator, int a, int b, int c) {
1122     return comparator.compare(x.get(a), x.get(b)) < 0 ? comparator.compare(x.get(b), x.get(c)) < 0
1123                                                         ? b
1124                                                         : comparator.compare(x.get(a), x.get(c)) < 0 ? c : a
1125                                                       : comparator.compare(x.get(c), x.get(b)) < 0
1126                                                         ? b
1127                                                         : comparator.compare(x.get(c), x.get(a)) < 0 ? c : a;
1128   }
1129
1130   /*
1131    * Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)].
1132    */
1133   private static <T> void vecswap(List<T> x, int a, int b, int n) {
1134     for (int i = 0; i < n; i++, a++, b++) {
1135       swapElements(x, a, b);
1136     }
1137   }
1138
1139   @NotNull
1140   public static <T> CopyOnWriteArrayList<T> createEmptyCOWList() {
1141     // does not create garbage new Object[0]
1142     return new CopyOnWriteArrayList<T>(ContainerUtil.<T>emptyList());
1143   }
1144
1145   @NotNull
1146   public static <T> List<T> emptyList() {
1147     return (List<T>)EmptyList.INSTANCE;
1148   }
1149
1150   /**
1151    * Merge sorted points, which are sorted by x and with equal x by y.
1152    * Result is put to x1 y1.
1153    */
1154   public static void mergeSortedArrays(TIntArrayList x1,
1155                                        TIntArrayList y1,
1156                                        TIntArrayList x2,
1157                                        TIntArrayList y2) {
1158     TIntArrayList newX = new TIntArrayList();
1159     TIntArrayList newY = new TIntArrayList();
1160
1161     int i = 0;
1162     int j = 0;
1163
1164     while (i < x1.size() && j < x2.size()) {
1165       if (x1.get(i) < x2.get(j) || (x1.get(i) == x2.get(j) && y1.get(i) < y2.get(j))) {
1166         newX.add(x1.get(i));
1167         newY.add(y1.get(i));
1168         i++;
1169       }
1170       else if (x1.get(i) > x2.get(j) || (x1.get(i) == x2.get(j) && y1.get(i) > y2.get(j))) {
1171         newX.add(x2.get(j));
1172         newY.add(y2.get(j));
1173         j++;
1174       }
1175       else { //equals
1176         newX.add(x1.get(i));
1177         newY.add(y1.get(i));
1178         i++;
1179         j++;
1180       }
1181     }
1182
1183     while (i < x1.size()) {
1184       newX.add(x1.get(i));
1185       newY.add(y1.get(i));
1186       i++;
1187     }
1188
1189     while (j < x2.size()) {
1190       newX.add(x2.get(j));
1191       newY.add(y2.get(j));
1192       j++;
1193     }
1194
1195     x1.clear();
1196     y1.clear();
1197     x1.add(newX.toNativeArray());
1198     y1.add(newY.toNativeArray());
1199   }
1200
1201   /**
1202    * has optimized toArray() as opposed to the {@link java.util.Collections#emptyList()}
1203    */
1204   private static class EmptyList extends AbstractList<Object> implements RandomAccess {
1205     private static final EmptyList INSTANCE = new EmptyList();
1206
1207     public int size() {
1208       return 0;
1209     }
1210
1211     public boolean contains(Object obj) {
1212       return false;
1213     }
1214
1215     public Object get(int index) {
1216       throw new IndexOutOfBoundsException("Index: " + index);
1217     }
1218
1219     @Override
1220     public Object[] toArray() {
1221       return ArrayUtil.EMPTY_OBJECT_ARRAY;
1222     }
1223
1224     @Override
1225     public <T> T[] toArray(T[] a) {
1226       return a;
1227     }
1228   }
1229
1230   @NotNull
1231   public static <T> Set<T> singleton(final T o, @NotNull final TObjectHashingStrategy<T> strategy) {
1232     return new Set<T>() {
1233       public int size() {
1234         return 1;
1235       }
1236
1237       public boolean isEmpty() {
1238         return false;
1239       }
1240
1241       public boolean contains(Object elem) {
1242         return strategy.equals(o, (T)elem);
1243       }
1244
1245       public Iterator<T> iterator() {
1246         return new Iterator<T>() {
1247           boolean atEnd;
1248
1249           public boolean hasNext() {
1250             return !atEnd;
1251           }
1252
1253           public T next() {
1254             if (atEnd) throw new NoSuchElementException();
1255             atEnd = true;
1256             return o;
1257           }
1258
1259           public void remove() {
1260             throw new IncorrectOperationException();
1261           }
1262         };
1263       }
1264
1265       public Object[] toArray() {
1266         return new Object[]{o};
1267       }
1268
1269       public <T> T[] toArray(T[] a) {
1270         assert a.length == 1;
1271         a[0] = (T)o;
1272         return a;
1273       }
1274
1275       public boolean add(T t) {
1276         throw new IncorrectOperationException();
1277       }
1278
1279       public boolean remove(Object o) {
1280         throw new IncorrectOperationException();
1281       }
1282
1283       public boolean containsAll(Collection<?> c) {
1284         return false;
1285       }
1286
1287       public boolean addAll(Collection<? extends T> c) {
1288         throw new IncorrectOperationException();
1289       }
1290
1291       public boolean retainAll(Collection<?> c) {
1292         throw new IncorrectOperationException();
1293       }
1294
1295       public boolean removeAll(Collection<?> c) {
1296         throw new IncorrectOperationException();
1297       }
1298
1299       public void clear() {
1300         throw new IncorrectOperationException();
1301       }
1302     };
1303   }
1304
1305   @NotNull
1306   public static <E> List<E> flatten(@NotNull Collection<E>[] collections) {
1307     return flatten(Arrays.asList(collections));
1308   }
1309   @NotNull
1310   public static <E> List<E> flatten(@NotNull Iterable<? extends Collection<E>> collections) {
1311     List<E> result = new ArrayList<E>();
1312     for (Collection<E> list : collections) {
1313       result.addAll(list);
1314     }
1315
1316     return result;
1317   }
1318
1319   public static <K,V> V[] convert(K[] from, V[] to, Function<K,V> fun) {
1320     if (to.length < from.length) {
1321       to = (V[])Array.newInstance(to.getClass().getComponentType(), from.length);
1322     }
1323     for (int i = 0; i < from.length; i++) {
1324       to[i] = fun.fun(from[i]);
1325     }
1326     return to;
1327   }
1328
1329   public static <T> int indexOf(List<T> list, Condition<T> condition) {
1330     for (int i = 0, listSize = list.size(); i < listSize; i++) {
1331       T t = list.get(i);
1332       if (condition.value(t)) {
1333         return i;
1334       }
1335     }
1336     return -1;
1337   }
1338
1339   public static <A,B> Map<B,A> reverseMap(Map<A,B> map) {
1340     final Map<B,A> result = new HashMap<B, A>();
1341     for (A a : map.keySet()) {
1342       result.put(map.get(a), a);
1343     }
1344     return result;
1345   }
1346
1347   public static <T> boolean processRecursively(final T root, final PairProcessor<T, List<T>> processor) {
1348     final LinkedList<T> list = new LinkedList<T>();
1349     list.add(root);
1350     while (!list.isEmpty()) {
1351       final T o = list.removeFirst();
1352       if (!processor.process(o, list)) return false;
1353     }
1354     return true;
1355   }
1356
1357   public static <T> List<T> trimToSize(List<T> list) {
1358     if (list == null) return null;
1359     if (list.isEmpty()) return Collections.emptyList();
1360
1361     if (list instanceof ArrayList) {
1362       list = new ArrayList(list);
1363     }
1364
1365     return list;
1366   }
1367 }