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