Merge branch 'oc-bridge'
[idea/community.git] / platform / util / src / com / intellij / util / containers / ContainerUtil.java
1 /*
2  * Copyright 2000-2015 JetBrains s.r.o.
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  * http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 package com.intellij.util.containers;
17
18 import com.intellij.openapi.Disposable;
19 import com.intellij.openapi.util.*;
20 import com.intellij.openapi.util.text.StringUtil;
21 import com.intellij.util.*;
22 import gnu.trove.*;
23 import org.jetbrains.annotations.Contract;
24 import org.jetbrains.annotations.NotNull;
25 import org.jetbrains.annotations.Nullable;
26
27 import java.lang.reflect.Array;
28 import java.util.*;
29 import java.util.HashMap;
30 import java.util.HashSet;
31 import java.util.LinkedHashMap;
32 import java.util.LinkedHashSet;
33 import java.util.concurrent.ConcurrentMap;
34 import java.util.concurrent.CopyOnWriteArrayList;
35
36 @SuppressWarnings({"UtilityClassWithoutPrivateConstructor", "MethodOverridesStaticMethodOfSuperclass"})
37 public class ContainerUtil extends ContainerUtilRt {
38   private static final int INSERTION_SORT_THRESHOLD = 10;
39   private static final int DEFAULT_CONCURRENCY_LEVEL = Math.min(16, Runtime.getRuntime().availableProcessors());
40
41   @NotNull
42   @Contract(pure=true)
43   public static <T> T[] ar(@NotNull T... elements) {
44     return elements;
45   }
46
47   @NotNull
48   @Contract(pure=true)
49   public static <K, V> HashMap<K, V> newHashMap() {
50     return ContainerUtilRt.newHashMap();
51   }
52
53   @NotNull
54   @Contract(pure=true)
55   public static <K, V> HashMap<K, V> newHashMap(@NotNull Map<? extends K, ? extends V> map) {
56     return ContainerUtilRt.newHashMap(map);
57   }
58
59   @NotNull
60   @Contract(pure=true)
61   public static <K, V> Map<K, V> newHashMap(@NotNull Pair<K, ? extends V> first, @NotNull Pair<K, ? extends V>... entries) {
62     return ContainerUtilRt.newHashMap(first, entries);
63   }
64
65   @NotNull
66   @Contract(pure=true)
67   public static <K, V> Map<K, V> newHashMap(@NotNull List<K> keys, @NotNull List<V> values) {
68     return ContainerUtilRt.newHashMap(keys, values);
69   }
70
71   @NotNull
72   @Contract(pure=true)
73   public static <K extends Comparable, V> TreeMap<K, V> newTreeMap() {
74     return ContainerUtilRt.newTreeMap();
75   }
76
77   @NotNull
78   @Contract(pure=true)
79   public static <K extends Comparable, V> TreeMap<K, V> newTreeMap(@NotNull Map<K, V> map) {
80     return ContainerUtilRt.newTreeMap(map);
81   }
82
83   @NotNull
84   @Contract(pure=true)
85   public static <K, V> LinkedHashMap<K, V> newLinkedHashMap() {
86     return ContainerUtilRt.newLinkedHashMap();
87   }
88
89   @NotNull
90   @Contract(pure=true)
91   public static <K, V> LinkedHashMap<K, V> newLinkedHashMap(int capacity) {
92     return ContainerUtilRt.newLinkedHashMap(capacity);
93   }
94
95   @NotNull
96   @Contract(pure=true)
97   public static <K, V> LinkedHashMap<K, V> newLinkedHashMap(@NotNull Map<K, V> map) {
98     return ContainerUtilRt.newLinkedHashMap(map);
99   }
100
101   @NotNull
102   @Contract(pure=true)
103   public static <K, V> LinkedHashMap<K, V> newLinkedHashMap(@NotNull Pair<K, V> first, @NotNull Pair<K, V>... entries) {
104     return ContainerUtilRt.newLinkedHashMap(first, entries);
105   }
106
107   @NotNull
108   @Contract(pure=true)
109   public static <K, V> THashMap<K, V> newTroveMap() {
110     return new THashMap<K, V>();
111   }
112
113   @NotNull
114   @Contract(pure=true)
115   public static <K, V> THashMap<K, V> newTroveMap(@NotNull TObjectHashingStrategy<K> strategy) {
116     return new THashMap<K, V>(strategy);
117   }
118
119   @NotNull
120   @Contract(pure=true)
121   public static <K extends Enum<K>, V> EnumMap<K, V> newEnumMap(@NotNull Class<K> keyType) {
122     return new EnumMap<K, V>(keyType);
123   }
124
125   @SuppressWarnings("unchecked")
126   @NotNull
127   @Contract(pure=true)
128   public static <T> TObjectHashingStrategy<T> canonicalStrategy() {
129     return TObjectHashingStrategy.CANONICAL;
130   }
131
132   @SuppressWarnings("unchecked")
133   @NotNull
134   @Contract(pure=true)
135   public static <T> TObjectHashingStrategy<T> identityStrategy() {
136     return TObjectHashingStrategy.IDENTITY;
137   }
138
139   @NotNull
140   @Contract(pure=true)
141   public static <K, V> IdentityHashMap<K, V> newIdentityHashMap() {
142     return new IdentityHashMap<K, V>();
143   }
144
145   @NotNull
146   @Contract(pure=true)
147   public static <T> LinkedList<T> newLinkedList() {
148     return ContainerUtilRt.newLinkedList();
149   }
150
151   @NotNull
152   @Contract(pure=true)
153   public static <T> LinkedList<T> newLinkedList(@NotNull T... elements) {
154     return ContainerUtilRt.newLinkedList(elements);
155   }
156
157   @NotNull
158   @Contract(pure=true)
159   public static <T> LinkedList<T> newLinkedList(@NotNull Iterable<? extends T> elements) {
160     return ContainerUtilRt.newLinkedList(elements);
161   }
162
163   @NotNull
164   @Contract(pure=true)
165   public static <T> ArrayList<T> newArrayList() {
166     return ContainerUtilRt.newArrayList();
167   }
168
169   @NotNull
170   @Contract(pure=true)
171   public static <E> ArrayList<E> newArrayList(@NotNull E... array) {
172     return ContainerUtilRt.newArrayList(array);
173   }
174
175   @NotNull
176   @Contract(pure=true)
177   public static <E> ArrayList<E> newArrayList(@NotNull Iterable<? extends E> iterable) {
178     return ContainerUtilRt.newArrayList(iterable);
179   }
180
181   /** @deprecated Use {@link #newArrayListWithCapacity(int)} (to remove in IDEA 15) */
182   @SuppressWarnings("deprecation")
183   @Contract(pure=true)
184   public static <T> ArrayList<T> newArrayListWithExpectedSize(int size) {
185     return ContainerUtilRt.newArrayListWithCapacity(size);
186   }
187
188   @NotNull
189   @Contract(pure=true)
190   public static <T> ArrayList<T> newArrayListWithCapacity(int size) {
191     return ContainerUtilRt.newArrayListWithCapacity(size);
192   }
193
194   @NotNull
195   @Contract(pure=true)
196   public static <T> List<T> newArrayList(@NotNull final T[] elements, final int start, final int end) {
197     if (start < 0 || start > end || end > elements.length) {
198       throw new IllegalArgumentException("start:" + start + " end:" + end + " length:" + elements.length);
199     }
200
201     return new AbstractList<T>() {
202       private final int size = end - start;
203
204       @Override
205       public T get(final int index) {
206         if (index < 0 || index >= size) throw new IndexOutOfBoundsException("index:" + index + " size:" + size);
207         return elements[start + index];
208       }
209
210       @Override
211       public int size() {
212         return size;
213       }
214     };
215   }
216
217   @NotNull
218   @Contract(pure = true)
219   public static <T> List<T> newUnmodifiableList(List<? extends T> originalList) {
220     int size = originalList.size();
221     if (size == 0) {
222       return emptyList();
223     }
224     else if (size == 1) {
225       return Collections.singletonList(originalList.get(0));
226     }
227     else {
228       return Collections.unmodifiableList(newArrayList(originalList));
229     }
230   }
231
232
233   @NotNull
234   @Contract(pure=true)
235   public static <T> List<T> newSmartList() {
236     return new SmartList<T>();
237   }
238
239   @NotNull
240   @Contract(pure=true)
241   public static <T> List<T> newSmartList(T element) {
242     return new SmartList<T>(element);
243   }
244
245   @NotNull
246   @Contract(pure=true)
247   public static <T> List<T> newSmartList(@NotNull T... elements) {
248     return new SmartList<T>(elements);
249   }
250
251   @NotNull
252   @Contract(pure=true)
253   public static <T> HashSet<T> newHashSet() {
254     return ContainerUtilRt.newHashSet();
255   }
256
257   @NotNull
258   @Contract(pure=true)
259   public static <T> HashSet<T> newHashSet(int initialCapacity) {
260     return ContainerUtilRt.newHashSet(initialCapacity);
261   }
262
263   @NotNull
264   @Contract(pure=true)
265   public static <T> HashSet<T> newHashSet(@NotNull T... elements) {
266     return ContainerUtilRt.newHashSet(elements);
267   }
268
269   @NotNull
270   @Contract(pure=true)
271   public static <T> HashSet<T> newHashSet(@NotNull Iterable<? extends T> iterable) {
272     return ContainerUtilRt.newHashSet(iterable);
273   }
274
275   @NotNull
276   public static <T> HashSet<T> newHashSet(@NotNull Iterator<? extends T> iterator) {
277     return ContainerUtilRt.newHashSet(iterator);
278   }
279
280   @NotNull
281   @Contract(pure=true)
282   public static <T> Set<T> newHashOrEmptySet(@Nullable Iterable<? extends T> iterable) {
283     boolean empty = iterable == null || iterable instanceof Collection && ((Collection)iterable).isEmpty();
284     return empty ? Collections.<T>emptySet() : ContainerUtilRt.newHashSet(iterable);
285   }
286
287   @NotNull
288   @Contract(pure=true)
289   public static <T> LinkedHashSet<T> newLinkedHashSet() {
290     return ContainerUtilRt.newLinkedHashSet();
291   }
292
293   @NotNull
294   @Contract(pure=true)
295   public static <T> LinkedHashSet<T> newLinkedHashSet(@NotNull Iterable<? extends T> elements) {
296     return ContainerUtilRt.newLinkedHashSet(elements);
297   }
298
299   @NotNull
300   @Contract(pure=true)
301   public static <T> LinkedHashSet<T> newLinkedHashSet(@NotNull T... elements) {
302     return ContainerUtilRt.newLinkedHashSet(elements);
303   }
304
305   @NotNull
306   @Contract(pure=true)
307   public static <T> THashSet<T> newTroveSet() {
308     return new THashSet<T>();
309   }
310
311   @NotNull
312   @Contract(pure=true)
313   public static <T> THashSet<T> newTroveSet(@NotNull TObjectHashingStrategy<T> strategy) {
314     return new THashSet<T>(strategy);
315   }
316
317   @NotNull
318   @Contract(pure=true)
319   public static <T> THashSet<T> newTroveSet(@NotNull T... elements) {
320     return newTroveSet(Arrays.asList(elements));
321   }
322
323   @NotNull
324   @Contract(pure=true)
325   public static <T> THashSet<T> newTroveSet(@NotNull TObjectHashingStrategy<T> strategy, @NotNull T... elements) {
326     return new THashSet<T>(Arrays.asList(elements), strategy);
327   }
328
329   @NotNull
330   @Contract(pure=true)
331   public static <T> THashSet<T> newTroveSet(@NotNull TObjectHashingStrategy<T> strategy, @NotNull Collection<T> elements) {
332     return new THashSet<T>(elements, strategy);
333   }
334
335   @NotNull
336   @Contract(pure=true)
337   public static <T> THashSet<T> newTroveSet(@NotNull Collection<T> elements) {
338     return new THashSet<T>(elements);
339   }
340
341   @NotNull
342   @Contract(pure=true)
343   public static <K> THashSet<K> newIdentityTroveSet() {
344     return new THashSet<K>(ContainerUtil.<K>identityStrategy());
345   }
346
347   @NotNull
348   @Contract(pure=true)
349   public static <K> THashSet<K> newIdentityTroveSet(int initialCapacity) {
350     return new THashSet<K>(initialCapacity, ContainerUtil.<K>identityStrategy());
351   }
352   @NotNull
353   @Contract(pure=true)
354   public static <K> THashSet<K> newIdentityTroveSet(@NotNull Collection<K> collection) {
355     return new THashSet<K>(collection, ContainerUtil.<K>identityStrategy());
356   }
357
358   @NotNull
359   @Contract(pure=true)
360   public static <K,V> THashMap<K,V> newIdentityTroveMap() {
361     return new THashMap<K,V>(ContainerUtil.<K>identityStrategy());
362   }
363
364   @NotNull
365   @Contract(pure=true)
366   public static <T> TreeSet<T> newTreeSet() {
367     return ContainerUtilRt.newTreeSet();
368   }
369
370   @NotNull
371   @Contract(pure=true)
372   public static <T> TreeSet<T> newTreeSet(@NotNull Iterable<? extends T> elements) {
373     return ContainerUtilRt.newTreeSet(elements);
374   }
375
376   @NotNull
377   @Contract(pure=true)
378   public static <T> TreeSet<T> newTreeSet(@NotNull T... elements) {
379     return ContainerUtilRt.newTreeSet(elements);
380   }
381
382   @NotNull
383   @Contract(pure=true)
384   public static <T> TreeSet<T> newTreeSet(@Nullable Comparator<? super T> comparator) {
385     return ContainerUtilRt.newTreeSet(comparator);
386   }
387
388   @NotNull
389   @Contract(pure=true)
390   public static <T> Set<T> newConcurrentSet() {
391     return new ConcurrentHashSet<T>();
392   }
393
394   @NotNull
395   @Contract(pure=true)
396   public static <T> Set<T> newConcurrentSet(@NotNull TObjectHashingStrategy<T> hashStrategy) {
397     return new ConcurrentHashSet<T>(hashStrategy);
398   }
399
400   @NotNull
401   @Contract(pure=true)
402   public static <K, V> ConcurrentMap<K, V> newConcurrentMap() {
403     return CHM_FACTORY.createMap();
404   }
405
406   @Contract(pure=true)
407   public static <K, V> ConcurrentMap<K,V> newConcurrentMap(@NotNull TObjectHashingStrategy<K> hashStrategy) {
408     return CHM_FACTORY.createMap(hashStrategy);
409   }
410
411   @Contract(pure=true)
412   public static <K, V> ConcurrentMap<K,V> newConcurrentMap(int initialCapacity) {
413     return CHM_FACTORY.createMap(initialCapacity);
414   }
415
416   @Contract(pure=true)
417   public static <K, V> ConcurrentMap<K,V> newConcurrentMap(int initialCapacity, float loadFactor, int concurrencyLevel, @NotNull TObjectHashingStrategy<K> hashStrategy) {
418     return CHM_FACTORY.createMap(initialCapacity, loadFactor, concurrencyLevel, hashStrategy);
419   }
420
421   @Contract(pure=true)
422   public static <K, V> ConcurrentMap<K,V> newConcurrentMap(int initialCapacity, float loadFactor, int concurrencyLevel) {
423     return CHM_FACTORY.createMap(initialCapacity, loadFactor, concurrencyLevel);
424   }
425
426   @NotNull
427   @Contract(pure=true)
428   public static <E> List<E> reverse(@NotNull final List<E> elements) {
429     if (elements.isEmpty()) {
430       return ContainerUtilRt.emptyList();
431     }
432
433     return new AbstractList<E>() {
434       @Override
435       public E get(int index) {
436         return elements.get(elements.size() - 1 - index);
437       }
438
439       @Override
440       public int size() {
441         return elements.size();
442       }
443     };
444   }
445
446   @NotNull
447   @Contract(pure=true)
448   public static <K, V> Map<K, V> union(@NotNull Map<? extends K, ? extends V> map, @NotNull Map<? extends K, ? extends V> map2) {
449     Map<K, V> result = new THashMap<K, V>(map.size() + map2.size());
450     result.putAll(map);
451     result.putAll(map2);
452     return result;
453   }
454
455   @NotNull
456   @Contract(pure=true)
457   public static <T> Set<T> union(@NotNull Set<T> set, @NotNull Set<T> set2) {
458     Set<T> result = new THashSet<T>(set.size() + set2.size());
459     result.addAll(set);
460     result.addAll(set2);
461     return result;
462   }
463
464   @NotNull
465   @Contract(pure=true)
466   public static <E> Set<E> immutableSet(@NotNull E ... elements) {
467     return Collections.unmodifiableSet(new THashSet<E>(Arrays.asList(elements)));
468   }
469
470   @NotNull
471   @Contract(pure=true)
472   public static <E> ImmutableList<E> immutableList(@NotNull E ... array) {
473     return new ImmutableListBackedByArray<E>(array);
474   }
475
476   @NotNull
477   @Contract(pure=true)
478   public static <E> ImmutableList<E> immutableList(@NotNull List<E> list) {
479     return new ImmutableListBackedByList<E>(list);
480   }
481
482   @NotNull
483   @Contract(pure=true)
484   public static <K, V> ImmutableMapBuilder<K, V> immutableMapBuilder() {
485     return new ImmutableMapBuilder<K, V>();
486   }
487
488   public static class ImmutableMapBuilder<K, V> {
489     private final Map<K, V> myMap = new THashMap<K, V>();
490
491     public ImmutableMapBuilder<K, V> put(K key, V value) {
492       myMap.put(key, value);
493       return this;
494     }
495
496     @Contract(pure=true)
497     public Map<K, V> build() {
498       return Collections.unmodifiableMap(myMap);
499     }
500   }
501
502   private static class ImmutableListBackedByList<E> extends ImmutableList<E> {
503     private final List<E> myStore;
504
505     private ImmutableListBackedByList(@NotNull List<E> list) {
506       myStore = list;
507     }
508
509     @Override
510     public E get(int index) {
511       return myStore.get(index);
512     }
513
514     @Override
515     public int size() {
516       return myStore.size();
517     }
518   }
519
520   private static class ImmutableListBackedByArray<E> extends ImmutableList<E> {
521     private final E[] myStore;
522
523     private ImmutableListBackedByArray(@NotNull E[] array) {
524       myStore = array;
525     }
526
527     @Override
528     public E get(int index) {
529       return myStore[index];
530     }
531
532     @Override
533     public int size() {
534       return myStore.length;
535     }
536   }
537
538   @NotNull
539   @Contract(pure=true)
540   public static <K, V> Map<K, V> intersection(@NotNull Map<K, V> map1, @NotNull Map<K, V> map2) {
541     final Map<K, V> res = newHashMap();
542     final Set<K> keys = newHashSet();
543     keys.addAll(map1.keySet());
544     keys.addAll(map2.keySet());
545     for (K k : keys) {
546       V v1 = map1.get(k);
547       V v2 = map2.get(k);
548       if (v1 == v2 || v1 != null && v1.equals(v2)) {
549         res.put(k, v1);
550       }
551     }
552     return res;
553   }
554
555   @NotNull
556   @Contract(pure=true)
557   public static <K, V> Map<K,Couple<V>> diff(@NotNull Map<K, V> map1, @NotNull Map<K, V> map2) {
558     final Map<K, Couple<V>> res = newHashMap();
559     final Set<K> keys = newHashSet();
560     keys.addAll(map1.keySet());
561     keys.addAll(map2.keySet());
562     for (K k : keys) {
563       V v1 = map1.get(k);
564       V v2 = map2.get(k);
565       if (!(v1 == v2 || v1 != null && v1.equals(v2))) {
566         res.put(k, Couple.of(v1, v2));
567       }
568     }
569     return res;
570   }
571
572   public static <T> boolean processSortedListsInOrder(@NotNull List<T> list1,
573                                                       @NotNull List<T> list2,
574                                                       @NotNull Comparator<? super T> comparator,
575                                                       boolean mergeEqualItems,
576                                                       @NotNull Processor<T> processor) {
577     int index1 = 0;
578     int index2 = 0;
579     while (index1 < list1.size() || index2 < list2.size()) {
580       T e;
581       if (index1 >= list1.size()) {
582         e = list2.get(index2++);
583       }
584       else if (index2 >= list2.size()) {
585         e = list1.get(index1++);
586       }
587       else {
588         T element1 = list1.get(index1);
589         T element2 = list2.get(index2);
590         int c = comparator.compare(element1, element2);
591         if (c <= 0) {
592           e = element1;
593           index1++;
594         }
595         else {
596           e = element2;
597           index2++;
598         }
599         if (c == 0 && !mergeEqualItems) {
600           if (!processor.process(e)) return false;
601           index2++;
602           e = element2;
603         }
604       }
605       if (!processor.process(e)) return false;
606     }
607
608     return true;
609   }
610
611   @NotNull
612   @Contract(pure=true)
613   public static <T> List<T> mergeSortedLists(@NotNull List<T> list1,
614                                              @NotNull List<T> list2,
615                                              @NotNull Comparator<? super T> comparator,
616                                              boolean mergeEqualItems) {
617     final List<T> result = new ArrayList<T>(list1.size() + list2.size());
618     processSortedListsInOrder(list1, list2, comparator, mergeEqualItems, new Processor<T>() {
619       @Override
620       public boolean process(T t) {
621         result.add(t);
622         return true;
623       }
624     });
625     return result;
626   }
627
628   @NotNull
629   @Contract(pure=true)
630   public static <T> List<T> mergeSortedArrays(@NotNull T[] list1, @NotNull T[] list2, @NotNull Comparator<? super T> comparator, boolean mergeEqualItems, @Nullable Processor<? super T> filter) {
631     int index1 = 0;
632     int index2 = 0;
633     List<T> result = new ArrayList<T>(list1.length + list2.length);
634
635     while (index1 < list1.length || index2 < list2.length) {
636       if (index1 >= list1.length) {
637         T t = list2[index2++];
638         if (filter != null && !filter.process(t)) continue;
639         result.add(t);
640       }
641       else if (index2 >= list2.length) {
642         T t = list1[index1++];
643         if (filter != null && !filter.process(t)) continue;
644         result.add(t);
645       }
646       else {
647         T element1 = list1[index1];
648         if (filter != null && !filter.process(element1)) {
649           index1++;
650           continue;
651         }
652         T element2 = list2[index2];
653         if (filter != null && !filter.process(element2)) {
654           index2++;
655           continue;
656         }
657         int c = comparator.compare(element1, element2);
658         if (c < 0) {
659           result.add(element1);
660           index1++;
661         }
662         else if (c > 0) {
663           result.add(element2);
664           index2++;
665         }
666         else {
667           result.add(element1);
668           if (!mergeEqualItems) {
669             result.add(element2);
670           }
671           index1++;
672           index2++;
673         }
674       }
675     }
676
677     return result;
678   }
679
680   @NotNull
681   @Contract(pure=true)
682   public static <T> List<T> subList(@NotNull List<T> list, int from) {
683     return list.subList(from, list.size());
684   }
685
686   public static <T> void addAll(@NotNull Collection<T> collection, @NotNull Iterable<? extends T> appendix) {
687     addAll(collection, appendix.iterator());
688   }
689
690   public static <T> void addAll(@NotNull Collection<T> collection, @NotNull Iterator<? extends T> iterator) {
691     while (iterator.hasNext()) {
692       T o = iterator.next();
693       collection.add(o);
694     }
695   }
696
697   /**
698    * Adds all not-null elements from the {@code elements}, ignoring nulls
699    */
700   public static <T> void addAllNotNull(@NotNull Collection<T> collection, @NotNull Iterable<? extends T> elements) {
701     addAllNotNull(collection, elements.iterator());
702   }
703
704   /**
705    * Adds all not-null elements from the {@code elements}, ignoring nulls
706    */
707   public static <T> void addAllNotNull(@NotNull Collection<T> collection, @NotNull Iterator<? extends T> elements) {
708     while (elements.hasNext()) {
709       T o = elements.next();
710       if (o != null) {
711         collection.add(o);
712       }
713     }
714   }
715
716   @NotNull
717   public static <T> List<T> collect(@NotNull Iterator<T> iterator) {
718     if (!iterator.hasNext()) return emptyList();
719     List<T> list = new ArrayList<T>();
720     addAll(list, iterator);
721     return list;
722   }
723
724   @NotNull
725   public static <T> Set<T> collectSet(@NotNull Iterator<T> iterator) {
726     if (!iterator.hasNext()) return Collections.emptySet();
727     Set<T> hashSet = newHashSet();
728     addAll(hashSet, iterator);
729     return hashSet;
730   }
731
732   @NotNull
733   public static <K, V> Map<K, V> newMapFromKeys(@NotNull Iterator<K> keys, @NotNull Convertor<K, V> valueConvertor) {
734     Map<K, V> map = newHashMap();
735     while (keys.hasNext()) {
736       K key = keys.next();
737       map.put(key, valueConvertor.convert(key));
738     }
739     return map;
740   }
741
742   @NotNull
743   public static <K, V> Map<K, V> newMapFromValues(@NotNull Iterator<V> values, @NotNull Convertor<V, K> keyConvertor) {
744     Map<K, V> map = newHashMap();
745     while (values.hasNext()) {
746       V value = values.next();
747       map.put(keyConvertor.convert(value), value);
748     }
749     return map;
750   }
751
752   @NotNull
753   public static <K, V> Map<K, Set<V>> classify(@NotNull Iterator<V> iterator, @NotNull Convertor<V, K> keyConvertor) {
754     Map<K, Set<V>> hashMap = new LinkedHashMap<K, Set<V>>();
755     while (iterator.hasNext()) {
756       V value = iterator.next();
757       final K key = keyConvertor.convert(value);
758       Set<V> set = hashMap.get(key);
759       if (set == null) {
760         hashMap.put(key, set = new LinkedHashSet<V>()); // ordered set!!
761       }
762       set.add(value);
763     }
764     return hashMap;
765   }
766
767   @NotNull
768   @Contract(pure=true)
769   public static <T> Iterator<T> emptyIterator() {
770     return EmptyIterator.getInstance();
771   }
772
773   @NotNull
774   @Contract(pure=true)
775   public static <T> Iterable<T> emptyIterable() {
776     return EmptyIterable.getInstance();
777   }
778
779   @Nullable
780   @Contract(pure=true)
781   public static <T> T find(@NotNull T[] array, @NotNull Condition<T> condition) {
782     for (T element : array) {
783       if (condition.value(element)) return element;
784     }
785     return null;
786   }
787
788   public static <T> boolean process(@NotNull Iterable<? extends T> iterable, @NotNull Processor<T> processor) {
789     for (final T t : iterable) {
790       if (!processor.process(t)) {
791         return false;
792       }
793     }
794     return true;
795   }
796
797   public static <T> boolean process(@NotNull List<? extends T> list, @NotNull Processor<T> processor) {
798     //noinspection ForLoopReplaceableByForEach
799     for (int i = 0, size = list.size(); i < size; i++) {
800       T t = list.get(i);
801       if (!processor.process(t)) {
802         return false;
803       }
804     }
805     return true;
806   }
807
808   public static <T> boolean process(@NotNull T[] iterable, @NotNull Processor<? super T> processor) {
809     for (final T t : iterable) {
810       if (!processor.process(t)) {
811         return false;
812       }
813     }
814     return true;
815   }
816
817   public static <T> boolean process(@NotNull Iterator<T> iterator, @NotNull Processor<? super T> processor) {
818     while (iterator.hasNext()) {
819       if (!processor.process(iterator.next())) {
820         return false;
821       }
822     }
823     return true;
824   }
825
826   @Nullable
827   @Contract(pure=true)
828   public static <T, V extends T> V find(@NotNull Iterable<V> iterable, @NotNull Condition<T> condition) {
829     return find(iterable.iterator(), condition);
830   }
831
832   @Nullable
833   @Contract(pure=true)
834   public static <T> T find(@NotNull Iterable<? extends T> iterable, @NotNull final T equalTo) {
835     return find(iterable, new Condition<T>() {
836       @Override
837       public boolean value(final T object) {
838         return equalTo == object || equalTo.equals(object);
839       }
840     });
841   }
842
843   @Nullable
844   public static <T, V extends T> V find(@NotNull Iterator<V> iterator, @NotNull Condition<T> condition) {
845     while (iterator.hasNext()) {
846       V value = iterator.next();
847       if (condition.value(value)) return value;
848     }
849     return null;
850   }
851
852   @NotNull
853   @Contract(pure=true)
854   public static <T, KEY, VALUE> Map<KEY, VALUE> map2Map(@NotNull T[] collection, @NotNull Function<T, Pair<KEY, VALUE>> mapper) {
855     return map2Map(Arrays.asList(collection), mapper);
856   }
857
858   @NotNull
859   @Contract(pure=true)
860   public static <T, KEY, VALUE> Map<KEY, VALUE> map2Map(@NotNull Collection<? extends T> collection,
861                                                         @NotNull Function<T, Pair<KEY, VALUE>> mapper) {
862     final Map<KEY, VALUE> set = new THashMap<KEY, VALUE>(collection.size());
863     for (T t : collection) {
864       Pair<KEY, VALUE> pair = mapper.fun(t);
865       set.put(pair.first, pair.second);
866     }
867     return set;
868   }
869
870   @NotNull
871   @Contract(pure = true)
872   public static <T, KEY, VALUE> Map<KEY, VALUE> map2MapNotNull(@NotNull T[] collection,
873                                                                @NotNull Function<T, Pair<KEY, VALUE>> mapper) {
874     return map2MapNotNull(Arrays.asList(collection), mapper);
875   }
876
877   @NotNull
878   @Contract(pure = true)
879   public static <T, KEY, VALUE> Map<KEY, VALUE> map2MapNotNull(@NotNull Collection<? extends T> collection,
880                                                                @NotNull Function<T, Pair<KEY, VALUE>> mapper) {
881     final Map<KEY, VALUE> set = new THashMap<KEY, VALUE>(collection.size());
882     for (T t : collection) {
883       Pair<KEY, VALUE> pair = mapper.fun(t);
884       if (pair != null) {
885         set.put(pair.first, pair.second);
886       }
887     }
888     return set;
889   }
890
891   @NotNull
892   @Contract(pure=true)
893   public static <KEY, VALUE> Map<KEY, VALUE> map2Map(@NotNull Collection<Pair<KEY, VALUE>> collection) {
894     final Map<KEY, VALUE> result = new THashMap<KEY, VALUE>(collection.size());
895     for (Pair<KEY, VALUE> pair : collection) {
896       result.put(pair.first, pair.second);
897     }
898     return result;
899   }
900
901   @NotNull
902   @Contract(pure=true)
903   public static <T> Object[] map2Array(@NotNull T[] array, @NotNull Function<T, Object> mapper) {
904     return map2Array(array, Object.class, mapper);
905   }
906
907   @NotNull
908   @Contract(pure=true)
909   public static <T> Object[] map2Array(@NotNull Collection<T> array, @NotNull Function<T, Object> mapper) {
910     return map2Array(array, Object.class, mapper);
911   }
912
913   @NotNull
914   @Contract(pure=true)
915   public static <T, V> V[] map2Array(@NotNull T[] array, @NotNull Class<? super V> aClass, @NotNull Function<T, V> mapper) {
916     return map2Array(Arrays.asList(array), aClass, mapper);
917   }
918
919   @NotNull
920   @Contract(pure=true)
921   public static <T, V> V[] map2Array(@NotNull Collection<? extends T> collection, @NotNull Class<? super V> aClass, @NotNull Function<T, V> mapper) {
922     final List<V> list = map2List(collection, mapper);
923     @SuppressWarnings("unchecked") V[] array = (V[])Array.newInstance(aClass, list.size());
924     return list.toArray(array);
925   }
926
927   @NotNull
928   @Contract(pure=true)
929   public static <T, V> V[] map2Array(@NotNull Collection<? extends T> collection, @NotNull V[] to, @NotNull Function<T, V> mapper) {
930     return map2List(collection, mapper).toArray(to);
931   }
932
933   @NotNull
934   @Contract(pure=true)
935   public static <T> List<T> filter(@NotNull T[] collection, @NotNull Condition<? super T> condition) {
936     return findAll(collection, condition);
937   }
938
939   @NotNull
940   @Contract(pure=true)
941   public static int[] filter(@NotNull int[] collection, @NotNull TIntProcedure condition) {
942     TIntArrayList result = new TIntArrayList();
943     for (int t : collection) {
944       if (condition.execute(t)) {
945         result.add(t);
946       }
947     }
948     return result.isEmpty() ? ArrayUtil.EMPTY_INT_ARRAY : result.toNativeArray();
949   }
950
951   @NotNull
952   @Contract(pure=true)
953   public static <T> List<T> filter(@NotNull Condition<? super T> condition, @NotNull T... collection) {
954     return findAll(collection, condition);
955   }
956
957   @NotNull
958   @Contract(pure=true)
959   public static <T> List<T> findAll(@NotNull T[] collection, @NotNull Condition<? super T> condition) {
960     final List<T> result = new SmartList<T>();
961     for (T t : collection) {
962       if (condition.value(t)) {
963         result.add(t);
964       }
965     }
966     return result;
967   }
968
969   @NotNull
970   @Contract(pure=true)
971   public static <T> List<T> filter(@NotNull Collection<? extends T> collection, @NotNull Condition<? super T> condition) {
972     return findAll(collection, condition);
973   }
974
975   @NotNull
976   @Contract(pure = true)
977   public static <K, V> Map<K, V> filter(@NotNull Map<K, ? extends V> map, @NotNull Condition<? super K> keyFilter) {
978     Map<K, V> result = newHashMap();
979     for (Map.Entry<K, ? extends V> entry : map.entrySet()) {
980       if (keyFilter.value(entry.getKey())) {
981         result.put(entry.getKey(), entry.getValue());
982       }
983     }
984     return result;
985   }
986
987   @NotNull
988   @Contract(pure=true)
989   public static <T> List<T> findAll(@NotNull Collection<? extends T> collection, @NotNull Condition<? super T> condition) {
990     if (collection.isEmpty()) return emptyList();
991     final List<T> result = new SmartList<T>();
992     for (final T t : collection) {
993       if (condition.value(t)) {
994         result.add(t);
995       }
996     }
997     return result;
998   }
999
1000   @NotNull
1001   @Contract(pure=true)
1002   public static <T> List<T> skipNulls(@NotNull Collection<? extends T> collection) {
1003     return findAll(collection, Condition.NOT_NULL);
1004   }
1005
1006   @NotNull
1007   @Contract(pure=true)
1008   public static <T, V> List<V> findAll(@NotNull T[] collection, @NotNull Class<V> instanceOf) {
1009     return findAll(Arrays.asList(collection), instanceOf);
1010   }
1011
1012   @NotNull
1013   @Contract(pure=true)
1014   public static <T, V> V[] findAllAsArray(@NotNull T[] collection, @NotNull Class<V> instanceOf) {
1015     List<V> list = findAll(Arrays.asList(collection), instanceOf);
1016     @SuppressWarnings("unchecked") V[] array = (V[])Array.newInstance(instanceOf, list.size());
1017     return list.toArray(array);
1018   }
1019
1020   @NotNull
1021   @Contract(pure=true)
1022   public static <T, V> V[] findAllAsArray(@NotNull Collection<? extends T> collection, @NotNull Class<V> instanceOf) {
1023     List<V> list = findAll(collection, instanceOf);
1024     @SuppressWarnings("unchecked") V[] array = (V[])Array.newInstance(instanceOf, list.size());
1025     return list.toArray(array);
1026   }
1027
1028   @NotNull
1029   @Contract(pure=true)
1030   public static <T> T[] findAllAsArray(@NotNull T[] collection, @NotNull Condition<? super T> instanceOf) {
1031     List<T> list = findAll(collection, instanceOf);
1032     @SuppressWarnings("unchecked") T[] array = (T[])Array.newInstance(collection.getClass().getComponentType(), list.size());
1033     return list.toArray(array);
1034   }
1035
1036   @NotNull
1037   @Contract(pure=true)
1038   public static <T, V> List<V> findAll(@NotNull Collection<? extends T> collection, @NotNull Class<V> instanceOf) {
1039     final List<V> result = new SmartList<V>();
1040     for (final T t : collection) {
1041       if (instanceOf.isInstance(t)) {
1042         @SuppressWarnings("unchecked") V v = (V)t;
1043         result.add(v);
1044       }
1045     }
1046     return result;
1047   }
1048
1049   public static <T> void removeDuplicates(@NotNull Collection<T> collection) {
1050     Set<T> collected = newHashSet();
1051     for (Iterator<T> iterator = collection.iterator(); iterator.hasNext();) {
1052       T t = iterator.next();
1053       if (!collected.contains(t)) {
1054         collected.add(t);
1055       }
1056       else {
1057         iterator.remove();
1058       }
1059     }
1060   }
1061
1062   @NotNull
1063   @Contract(pure=true)
1064   public static Map<String, String> stringMap(@NotNull final String... keyValues) {
1065     final Map<String, String> result = newHashMap();
1066     for (int i = 0; i < keyValues.length - 1; i+=2) {
1067       result.put(keyValues[i], keyValues[i+1]);
1068     }
1069
1070     return result;
1071   }
1072
1073   @NotNull
1074   @Contract(pure=true)
1075   public static <T> Iterator<T> iterate(@NotNull T[] arrays) {
1076     return Arrays.asList(arrays).iterator();
1077   }
1078
1079   @NotNull
1080   @Contract(pure=true)
1081   public static <T> Iterator<T> iterate(@NotNull final Enumeration<T> enumeration) {
1082     return new Iterator<T>() {
1083       @Override
1084       public boolean hasNext() {
1085         return enumeration.hasMoreElements();
1086       }
1087
1088       @Override
1089       public T next() {
1090         return enumeration.nextElement();
1091       }
1092
1093       @Override
1094       public void remove() {
1095         throw new UnsupportedOperationException();
1096       }
1097     };
1098   }
1099
1100   @NotNull
1101   @Contract(pure=true)
1102   public static <T> Iterable<T> iterate(@NotNull T[] arrays, @NotNull Condition<? super T> condition) {
1103     return iterate(Arrays.asList(arrays), condition);
1104   }
1105
1106   @NotNull
1107   @Contract(pure=true)
1108   public static <T> Iterable<T> iterate(@NotNull final Collection<? extends T> collection, @NotNull final Condition<? super T> condition) {
1109     if (collection.isEmpty()) return emptyIterable();
1110     return new Iterable<T>() {
1111       @Override
1112       public Iterator<T> iterator() {
1113         return new Iterator<T>() {
1114           Iterator<? extends T> impl = collection.iterator();
1115           T next = findNext();
1116
1117           @Override
1118           public boolean hasNext() {
1119             return next != null;
1120           }
1121
1122           @Override
1123           public T next() {
1124             T result = next;
1125             next = findNext();
1126             return result;
1127           }
1128
1129           @Nullable
1130           private T findNext() {
1131             while (impl.hasNext()) {
1132               T each = impl.next();
1133               if (condition.value(each)) {
1134                 return each;
1135               }
1136             }
1137             return null;
1138           }
1139
1140           @Override
1141           public void remove() {
1142             throw new UnsupportedOperationException();
1143           }
1144         };
1145       }
1146     };
1147   }
1148
1149   @NotNull
1150   @Contract(pure=true)
1151   public static <T> Iterable<T> iterateBackward(@NotNull final List<? extends T> list) {
1152     return new Iterable<T>() {
1153       @Override
1154       public Iterator<T> iterator() {
1155         return new Iterator<T>() {
1156           ListIterator<? extends T> it = list.listIterator(list.size());
1157
1158           @Override
1159           public boolean hasNext() {
1160             return it.hasPrevious();
1161           }
1162
1163           @Override
1164           public T next() {
1165             return it.previous();
1166           }
1167
1168           @Override
1169           public void remove() {
1170             it.remove();
1171           }
1172         };
1173       }
1174     };
1175   }
1176
1177   public static <E> void swapElements(@NotNull List<E> list, int index1, int index2) {
1178     E e1 = list.get(index1);
1179     E e2 = list.get(index2);
1180     list.set(index1, e2);
1181     list.set(index2, e1);
1182   }
1183
1184   @NotNull
1185   public static <T> List<T> collect(@NotNull Iterator<?> iterator, @NotNull FilteringIterator.InstanceOf<T> instanceOf) {
1186     @SuppressWarnings("unchecked") List<T> list = collect(FilteringIterator.create((Iterator<T>)iterator, instanceOf));
1187     return list;
1188   }
1189
1190   public static <T> void addAll(@NotNull Collection<T> collection, @NotNull Enumeration<? extends T> enumeration) {
1191     while (enumeration.hasMoreElements()) {
1192       T element = enumeration.nextElement();
1193       collection.add(element);
1194     }
1195   }
1196
1197   @NotNull
1198   public static <T, A extends T, C extends Collection<T>> C addAll(@NotNull C collection, @NotNull A... elements) {
1199     //noinspection ManualArrayToCollectionCopy
1200     for (T element : elements) {
1201       collection.add(element);
1202     }
1203     return collection;
1204   }
1205
1206   /**
1207    * Adds all not-null elements from the {@code elements}, ignoring nulls
1208    */
1209   @NotNull
1210   public static <T, A extends T, C extends Collection<T>> C addAllNotNull(@NotNull C collection, @NotNull A... elements) {
1211     for (T element : elements) {
1212       if (element != null) {
1213         collection.add(element);
1214       }
1215     }
1216     return collection;
1217   }
1218
1219   public static <T> boolean removeAll(@NotNull Collection<T> collection, @NotNull T... elements) {
1220     boolean modified = false;
1221     for (T element : elements) {
1222       modified |= collection.remove(element);
1223     }
1224     return modified;
1225   }
1226
1227   // returns true if the collection was modified
1228   public static <T> boolean retainAll(@NotNull Collection<T> collection, @NotNull Condition<? super T> condition) {
1229     boolean modified = false;
1230
1231     for (Iterator<T> iterator = collection.iterator(); iterator.hasNext(); ) {
1232       T next = iterator.next();
1233       if (!condition.value(next)) {
1234         iterator.remove();
1235         modified = true;
1236       }
1237     }
1238
1239     return modified;
1240   }
1241
1242   @Contract(pure=true)
1243   public static <T, U extends T> U findInstance(@NotNull Iterable<T> iterable, @NotNull Class<U> aClass) {
1244     return findInstance(iterable.iterator(), aClass);
1245   }
1246
1247   public static <T, U extends T> U findInstance(@NotNull Iterator<T> iterator, @NotNull Class<U> aClass) {
1248     //noinspection unchecked
1249     U u = (U)find(iterator, FilteringIterator.instanceOf(aClass));
1250     return u;
1251   }
1252
1253   @Nullable
1254   @Contract(pure=true)
1255   public static <T, U extends T> U findInstance(@NotNull T[] array, @NotNull Class<U> aClass) {
1256     return findInstance(Arrays.asList(array), aClass);
1257   }
1258
1259   @NotNull
1260   @Contract(pure=true)
1261   public static <T, V> List<T> concat(@NotNull V[] array, @NotNull Function<V, Collection<? extends T>> fun) {
1262     return concat(Arrays.asList(array), fun);
1263   }
1264
1265   /**
1266    * @return read-only list consisting of the elements from the collections stored in list added together
1267    */
1268   @NotNull
1269   @Contract(pure=true)
1270   public static <T> List<T> concat(@NotNull Iterable<? extends Collection<T>> list) {
1271     List<T> result = new ArrayList<T>();
1272     for (final Collection<T> ts : list) {
1273       result.addAll(ts);
1274     }
1275     return result.isEmpty() ? Collections.<T>emptyList() : result;
1276   }
1277
1278   /**
1279    * @deprecated Use {@link #append(java.util.List, java.lang.Object[])} or {@link #prepend(java.util.List, java.lang.Object[])} instead
1280    * @param appendTail specify whether additional values should be appended in front or after the list
1281    * @return read-only list consisting of the elements from specified list with some additional values
1282    */
1283   @Deprecated
1284   @NotNull
1285   @Contract(pure=true)
1286   public static <T> List<T> concat(boolean appendTail, @NotNull List<? extends T> list, @NotNull T... values) {
1287     return appendTail ? concat(list, list(values)) : concat(list(values), list);
1288   }
1289
1290   @NotNull
1291   @Contract(pure=true)
1292   public static <T> List<T> append(@NotNull List<? extends T> list, @NotNull T... values) {
1293     return concat(list, list(values));
1294   }
1295
1296   /**
1297    * prepend values in front of the list
1298    * @return read-only list consisting of values and the elements from specified list
1299    */
1300   @NotNull
1301   @Contract(pure=true)
1302   public static <T> List<T> prepend(@NotNull List<? extends T> list, @NotNull T... values) {
1303     return concat(list(values), list);
1304   }
1305
1306   /**
1307    * @return read-only list consisting of the two lists added together
1308    */
1309   @NotNull
1310   @Contract(pure=true)
1311   public static <T> List<T> concat(@NotNull final List<? extends T> list1, @NotNull final List<? extends T> list2) {
1312     if (list1.isEmpty() && list2.isEmpty()) {
1313       return Collections.emptyList();
1314     }
1315     else if (list1.isEmpty()) {
1316       //noinspection unchecked
1317       return (List<T>)list2;
1318     }
1319     else if (list2.isEmpty()) {
1320       //noinspection unchecked
1321       return (List<T>)list1;
1322     }
1323
1324     final int size1 = list1.size();
1325     final int size = size1 + list2.size();
1326
1327     return new AbstractList<T>() {
1328       @Override
1329       public T get(int index) {
1330         if (index < size1) {
1331           return list1.get(index);
1332         }
1333
1334         return list2.get(index - size1);
1335       }
1336
1337       @Override
1338       public int size() {
1339         return size;
1340       }
1341     };
1342   }
1343
1344   @NotNull
1345   @Contract(pure=true)
1346   public static <T> Iterable<T> concat(@NotNull final Iterable<? extends T>... iterables) {
1347     return new Iterable<T>() {
1348       @Override
1349       public Iterator<T> iterator() {
1350         Iterator[] iterators = new Iterator[iterables.length];
1351         for (int i = 0; i < iterables.length; i++) {
1352           Iterable<? extends T> iterable = iterables[i];
1353           iterators[i] = iterable.iterator();
1354         }
1355         @SuppressWarnings("unchecked") Iterator<T> i = concatIterators(iterators);
1356         return i;
1357       }
1358     };
1359   }
1360
1361   @NotNull
1362   @Contract(pure=true)
1363   public static <T> Iterator<T> concatIterators(@NotNull Iterator<T>... iterators) {
1364     return new SequenceIterator<T>(iterators);
1365   }
1366
1367   @NotNull
1368   @Contract(pure=true)
1369   public static <T> Iterator<T> concatIterators(@NotNull Collection<Iterator<T>> iterators) {
1370     return new SequenceIterator<T>(iterators);
1371   }
1372
1373   @NotNull
1374   @Contract(pure=true)
1375   public static <T> Iterable<T> concat(@NotNull final T[]... iterables) {
1376     return new Iterable<T>() {
1377       @Override
1378       public Iterator<T> iterator() {
1379         Iterator[] iterators = new Iterator[iterables.length];
1380         for (int i = 0, iterablesLength = iterables.length; i < iterablesLength; i++) {
1381           T[] iterable = iterables[i];
1382           iterators[i] = Arrays.asList(iterable).iterator();
1383         }
1384         @SuppressWarnings("unchecked") Iterator<T> i = concatIterators(iterators);
1385         return i;
1386       }
1387     };
1388   }
1389
1390   /**
1391    * @return read-only list consisting of the lists added together
1392    */
1393   @NotNull
1394   @Contract(pure=true)
1395   public static <T> List<T> concat(@NotNull final List<? extends T>... lists) {
1396     int size = 0;
1397     for (List<? extends T> each : lists) {
1398       size += each.size();
1399     }
1400     if (size == 0) return emptyList();
1401     final int finalSize = size;
1402     return new AbstractList<T>() {
1403       @Override
1404       public T get(final int index) {
1405         if (index >= 0 && index < finalSize) {
1406           int from = 0;
1407           for (List<? extends T> each : lists) {
1408             if (from <= index && index < from + each.size()) return each.get(index - from);
1409             from += each.size();
1410           }
1411         }
1412         throw new IndexOutOfBoundsException("index: " + index + "size: " + size());
1413       }
1414
1415       @Override
1416       public int size() {
1417         return finalSize;
1418       }
1419     };
1420   }
1421
1422   /**
1423    * @return read-only list consisting of the lists added together
1424    */
1425   @NotNull
1426   @Contract(pure=true)
1427   public static <T> List<T> concat(@NotNull final List<List<? extends T>> lists) {
1428     @SuppressWarnings("unchecked") List<? extends T>[] array = lists.toArray(new List[lists.size()]);
1429     return concat(array);
1430   }
1431
1432   /**
1433    * @return read-only list consisting of the lists (made by listGenerator) added together
1434    */
1435   @NotNull
1436   @Contract(pure=true)
1437   public static <T, V> List<T> concat(@NotNull Iterable<? extends V> list, @NotNull Function<V, Collection<? extends T>> listGenerator) {
1438     List<T> result = new ArrayList<T>();
1439     for (final V v : list) {
1440       result.addAll(listGenerator.fun(v));
1441     }
1442     return result.isEmpty() ? ContainerUtil.<T>emptyList() : result;
1443   }
1444
1445   @Contract(pure=true)
1446   public static <T> boolean intersects(@NotNull Collection<? extends T> collection1, @NotNull Collection<? extends T> collection2) {
1447     if (collection1.size() <= collection2.size()) {
1448       for (T t : collection1) {
1449         if (collection2.contains(t)) {
1450           return true;
1451         }
1452       }
1453     }
1454     else {
1455       for (T t : collection2) {
1456         if (collection1.contains(t)) {
1457           return true;
1458         }
1459       }
1460     }
1461     return false;
1462   }
1463
1464   /**
1465    * @return read-only collection consisting of elements from both collections
1466    */
1467   @NotNull
1468   @Contract(pure=true)
1469   public static <T> Collection<T> intersection(@NotNull Collection<? extends T> collection1, @NotNull Collection<? extends T> collection2) {
1470     List<T> result = new ArrayList<T>();
1471     for (T t : collection1) {
1472       if (collection2.contains(t)) {
1473         result.add(t);
1474       }
1475     }
1476     return result.isEmpty() ? ContainerUtil.<T>emptyList() : result;
1477   }
1478
1479   @Nullable
1480   @Contract(pure=true)
1481   public static <T> T getFirstItem(@Nullable Collection<T> items) {
1482     return getFirstItem(items, null);
1483   }
1484
1485   @Nullable
1486   @Contract(pure=true)
1487   public static <T> T getFirstItem(@Nullable List<T> items) {
1488     return items == null || items.isEmpty() ? null : items.get(0);
1489   }
1490
1491   @Contract(pure=true)
1492   public static <T> T getFirstItem(@Nullable final Collection<T> items, @Nullable final T defaultResult) {
1493     return items == null || items.isEmpty() ? defaultResult : items.iterator().next();
1494   }
1495
1496   /**
1497    * The main difference from <code>subList</code> is that <code>getFirstItems</code> does not
1498    * throw any exceptions, even if maxItems is greater than size of the list
1499    *
1500    * @param items list
1501    * @param maxItems size of the result will be equal or less than <code>maxItems</code>
1502    * @param <T> type of list
1503    * @return new list with no more than <code>maxItems</code> first elements
1504    */
1505   @NotNull
1506   @Contract(pure=true)
1507   public static <T> List<T> getFirstItems(@NotNull final List<T> items, int maxItems) {
1508     return items.subList(0, Math.min(maxItems, items.size()));
1509   }
1510
1511   @Nullable
1512   @Contract(pure=true)
1513   public static <T> T iterateAndGetLastItem(@NotNull Iterable<T> items) {
1514     Iterator<T> itr = items.iterator();
1515     T res = null;
1516     while (itr.hasNext()) {
1517       res = itr.next();
1518     }
1519
1520     return res;
1521   }
1522
1523   @Nullable
1524   @Contract(pure=true)
1525   public static <T, L extends List<T>> T getLastItem(@Nullable L list, @Nullable T def) {
1526     return isEmpty(list) ? def : list.get(list.size() - 1);
1527   }
1528
1529   @Nullable
1530   @Contract(pure=true)
1531   public static <T, L extends List<T>> T getLastItem(@Nullable L list) {
1532     return getLastItem(list, null);
1533   }
1534
1535   /**
1536    * @return read-only collection consisting of elements from the 'from' collection which are absent from the 'what' collection
1537    */
1538   @NotNull
1539   @Contract(pure=true)
1540   public static <T> Collection<T> subtract(@NotNull Collection<T> from, @NotNull Collection<T> what) {
1541     final Set<T> set = newHashSet(from);
1542     set.removeAll(what);
1543     return set.isEmpty() ? ContainerUtil.<T>emptyList() : set;
1544   }
1545
1546   @NotNull
1547   @Contract(pure=true)
1548   public static <T> T[] toArray(@Nullable Collection<T> c, @NotNull ArrayFactory<T> factory) {
1549     return c != null ? c.toArray(factory.create(c.size())) : factory.create(0);
1550   }
1551
1552   @NotNull
1553   @Contract(pure=true)
1554   public static <T> T[] toArray(@NotNull Collection<? extends T> c1, @NotNull Collection<? extends T> c2, @NotNull ArrayFactory<T> factory) {
1555     return ArrayUtil.mergeCollections(c1, c2, factory);
1556   }
1557
1558   @NotNull
1559   @Contract(pure=true)
1560   public static <T> T[] mergeCollectionsToArray(@NotNull Collection<? extends T> c1, @NotNull Collection<? extends T> c2, @NotNull ArrayFactory<T> factory) {
1561     return ArrayUtil.mergeCollections(c1, c2, factory);
1562   }
1563
1564   public static <T extends Comparable<T>> void sort(@NotNull List<T> list) {
1565     int size = list.size();
1566
1567     if (size < 2) return;
1568     if (size == 2) {
1569       T t0 = list.get(0);
1570       T t1 = list.get(1);
1571
1572       if (t0.compareTo(t1) > 0) {
1573         list.set(0, t1);
1574         list.set(1, t0);
1575       }
1576     }
1577     else if (size < INSERTION_SORT_THRESHOLD) {
1578       for (int i = 0; i < size; i++) {
1579         for (int j = 0; j < i; j++) {
1580           T ti = list.get(i);
1581           T tj = list.get(j);
1582
1583           if (ti.compareTo(tj) < 0) {
1584             list.set(i, tj);
1585             list.set(j, ti);
1586           }
1587         }
1588       }
1589     }
1590     else {
1591       Collections.sort(list);
1592     }
1593   }
1594
1595   public static <T> void sort(@NotNull List<T> list, @NotNull Comparator<? super T> comparator) {
1596     int size = list.size();
1597
1598     if (size < 2) return;
1599     if (size == 2) {
1600       T t0 = list.get(0);
1601       T t1 = list.get(1);
1602
1603       if (comparator.compare(t0, t1) > 0) {
1604         list.set(0, t1);
1605         list.set(1, t0);
1606       }
1607     }
1608     else if (size < INSERTION_SORT_THRESHOLD) {
1609       for (int i = 0; i < size; i++) {
1610         for (int j = 0; j < i; j++) {
1611           T ti = list.get(i);
1612           T tj = list.get(j);
1613
1614           if (comparator.compare(ti, tj) < 0) {
1615             list.set(i, tj);
1616             list.set(j, ti);
1617           }
1618         }
1619       }
1620     }
1621     else {
1622       Collections.sort(list, comparator);
1623     }
1624   }
1625
1626   public static <T extends Comparable<T>> void sort(@NotNull T[] a) {
1627     int size = a.length;
1628
1629     if (size < 2) return;
1630     if (size == 2) {
1631       T t0 = a[0];
1632       T t1 = a[1];
1633
1634       if (t0.compareTo(t1) > 0) {
1635         a[0] = t1;
1636         a[1] = t0;
1637       }
1638     }
1639     else if (size < INSERTION_SORT_THRESHOLD) {
1640       for (int i = 0; i < size; i++) {
1641         for (int j = 0; j < i; j++) {
1642           T ti = a[i];
1643           T tj = a[j];
1644
1645           if (ti.compareTo(tj) < 0) {
1646             a[i] = tj;
1647             a[j] = ti;
1648           }
1649         }
1650       }
1651     }
1652     else {
1653       Arrays.sort(a);
1654     }
1655   }
1656
1657   @NotNull
1658   @Contract(pure=true)
1659   public static <T> List<T> sorted(@NotNull Collection<T> list, @NotNull Comparator<T> comparator) {
1660     return sorted((Iterable<T>)list, comparator);
1661   }
1662
1663   @NotNull
1664   @Contract(pure=true)
1665   public static <T> List<T> sorted(@NotNull Iterable<T> list, @NotNull Comparator<T> comparator) {
1666     List<T> sorted = newArrayList(list);
1667     sort(sorted, comparator);
1668     return sorted;
1669   }
1670
1671   @NotNull
1672   @Contract(pure=true)
1673   public static <T extends Comparable<T>> List<T> sorted(@NotNull Collection<T> list) {
1674     return sorted(list, new Comparator<T>() {
1675       @Override
1676       public int compare(T o1, T o2) {
1677         return o1.compareTo(o2);
1678       }
1679     });
1680   }
1681
1682   public static <T> void sort(@NotNull T[] a, @NotNull Comparator<T> comparator) {
1683     int size = a.length;
1684
1685     if (size < 2) return;
1686     if (size == 2) {
1687       T t0 = a[0];
1688       T t1 = a[1];
1689
1690       if (comparator.compare(t0, t1) > 0) {
1691         a[0] = t1;
1692         a[1] = t0;
1693       }
1694     }
1695     else if (size < INSERTION_SORT_THRESHOLD) {
1696       for (int i = 0; i < size; i++) {
1697         for (int j = 0; j < i; j++) {
1698           T ti = a[i];
1699           T tj = a[j];
1700
1701           if (comparator.compare(ti, tj) < 0) {
1702             a[i] = tj;
1703             a[j] = ti;
1704           }
1705         }
1706       }
1707     }
1708     else {
1709       Arrays.sort(a, comparator);
1710     }
1711   }
1712
1713   /**
1714    * @return read-only list consisting of the elements from the iterable converted by mapping
1715    */
1716   @NotNull
1717   @Contract(pure=true)
1718   public static <T,V> List<V> map(@NotNull Iterable<? extends T> iterable, @NotNull Function<T, V> mapping) {
1719     List<V> result = new ArrayList<V>();
1720     for (T t : iterable) {
1721       result.add(mapping.fun(t));
1722     }
1723     return result.isEmpty() ? ContainerUtil.<V>emptyList() : result;
1724   }
1725
1726   /**
1727    * @return read-only list consisting of the elements from the iterable converted by mapping
1728    */
1729   @NotNull
1730   @Contract(pure=true)
1731   public static <T,V> List<V> map(@NotNull Collection<? extends T> iterable, @NotNull Function<T, V> mapping) {
1732     if (iterable.isEmpty()) return emptyList();
1733     List<V> result = new ArrayList<V>(iterable.size());
1734     for (T t : iterable) {
1735       result.add(mapping.fun(t));
1736     }
1737     return result;
1738   }
1739
1740   /**
1741    * @return read-only list consisting of the elements from the array converted by mapping with nulls filtered out
1742    */
1743   @NotNull
1744   @Contract(pure=true)
1745   public static <T, V> List<V> mapNotNull(@NotNull T[] array, @NotNull Function<T, V> mapping) {
1746     return mapNotNull(Arrays.asList(array), mapping);
1747   }
1748
1749   /**
1750    * @return read-only list consisting of the elements from the array converted by mapping with nulls filtered out
1751    */
1752   @NotNull
1753   @Contract(pure=true)
1754   public static <T, V> V[] mapNotNull(@NotNull T[] array, @NotNull Function<T, V> mapping, @NotNull V[] emptyArray) {
1755     List<V> result = new ArrayList<V>(array.length);
1756     for (T t : array) {
1757       V v = mapping.fun(t);
1758       if (v != null) {
1759         result.add(v);
1760       }
1761     }
1762     if (result.isEmpty()) {
1763       assert emptyArray.length == 0 : "You must pass an empty array";
1764       return emptyArray;
1765     }
1766     return result.toArray(emptyArray);
1767   }
1768
1769   /**
1770    * @return read-only list consisting of the elements from the iterable converted by mapping with nulls filtered out
1771    */
1772   @NotNull
1773   @Contract(pure=true)
1774   public static <T, V> List<V> mapNotNull(@NotNull Iterable<? extends T> iterable, @NotNull Function<T, V> mapping) {
1775     List<V> result = new ArrayList<V>();
1776     for (T t : iterable) {
1777       final V o = mapping.fun(t);
1778       if (o != null) {
1779         result.add(o);
1780       }
1781     }
1782     return result.isEmpty() ? ContainerUtil.<V>emptyList() : result;
1783   }
1784
1785   /**
1786    * @return read-only list consisting of the elements from the array converted by mapping with nulls filtered out
1787    */
1788   @NotNull
1789   @Contract(pure=true)
1790   public static <T, V> List<V> mapNotNull(@NotNull Collection<? extends T> iterable, @NotNull Function<T, V> mapping) {
1791     if (iterable.isEmpty()) {
1792       return emptyList();
1793     }
1794
1795     List<V> result = new ArrayList<V>(iterable.size());
1796     for (T t : iterable) {
1797       final V o = mapping.fun(t);
1798       if (o != null) {
1799         result.add(o);
1800       }
1801     }
1802     return result.isEmpty() ? ContainerUtil.<V>emptyList() : result;
1803   }
1804
1805   /**
1806    * @return read-only list consisting of the elements with nulls filtered out
1807    */
1808   @NotNull
1809   @Contract(pure=true)
1810   public static <T> List<T> packNullables(@NotNull T... elements) {
1811     List<T> list = new ArrayList<T>();
1812     for (T element : elements) {
1813       addIfNotNull(element, list);
1814     }
1815     return list.isEmpty() ? ContainerUtil.<T>emptyList() : list;
1816   }
1817
1818   /**
1819    * @return read-only list consisting of the elements from the array converted by mapping
1820    */
1821   @NotNull
1822   @Contract(pure=true)
1823   public static <T, V> List<V> map(@NotNull T[] array, @NotNull Function<T, V> mapping) {
1824     List<V> result = new ArrayList<V>(array.length);
1825     for (T t : array) {
1826       result.add(mapping.fun(t));
1827     }
1828     return result.isEmpty() ? ContainerUtil.<V>emptyList() : result;
1829   }
1830
1831   @NotNull
1832   @Contract(pure=true)
1833   public static <T, V> V[] map(@NotNull T[] arr, @NotNull Function<T, V> mapping, @NotNull V[] emptyArray) {
1834     if (arr.length==0) {
1835       assert emptyArray.length == 0 : "You must pass an empty array";
1836       return emptyArray;
1837     }
1838
1839     List<V> result = new ArrayList<V>(arr.length);
1840     for (T t : arr) {
1841       result.add(mapping.fun(t));
1842     }
1843     return result.toArray(emptyArray);
1844   }
1845
1846   @NotNull
1847   @Contract(pure=true)
1848   public static <T> Set<T> set(@NotNull T ... items) {
1849     return newHashSet(items);
1850   }
1851
1852   public static <K, V> void putIfNotNull(final K key, @Nullable V value, @NotNull final Map<K, V> result) {
1853     if (value != null) {
1854       result.put(key, value);
1855     }
1856   }
1857
1858   public static <T> void add(final T element, @NotNull final Collection<T> result, @NotNull final Disposable parentDisposable) {
1859     if (result.add(element)) {
1860       Disposer.register(parentDisposable, new Disposable() {
1861         @Override
1862         public void dispose() {
1863           result.remove(element);
1864         }
1865       });
1866     }
1867   }
1868
1869   @NotNull
1870   @Contract(pure=true)
1871   public static <T> List<T> createMaybeSingletonList(@Nullable T element) {
1872     return element == null ? ContainerUtil.<T>emptyList() : Collections.singletonList(element);
1873   }
1874
1875   @NotNull
1876   @Contract(pure=true)
1877   public static <T> Set<T> createMaybeSingletonSet(@Nullable T element) {
1878     return element == null ? Collections.<T>emptySet() : Collections.singleton(element);
1879   }
1880
1881   @NotNull
1882   public static <T, V> V getOrCreate(@NotNull Map<T, V> result, final T key, @NotNull V defaultValue) {
1883     V value = result.get(key);
1884     if (value == null) {
1885       result.put(key, value = defaultValue);
1886     }
1887     return value;
1888   }
1889
1890   public static <T, V> V getOrCreate(@NotNull Map<T, V> result, final T key, @NotNull Factory<V> factory) {
1891     V value = result.get(key);
1892     if (value == null) {
1893       result.put(key, value = factory.create());
1894     }
1895     return value;
1896   }
1897
1898   @NotNull
1899   @Contract(pure=true)
1900   public static <T, V> V getOrElse(@NotNull Map<T, V> result, final T key, @NotNull V defValue) {
1901     V value = result.get(key);
1902     return value == null ? defValue : value;
1903   }
1904
1905   @Contract(pure=true)
1906   public static <T> boolean and(@NotNull T[] iterable, @NotNull Condition<T> condition) {
1907     return and(Arrays.asList(iterable), condition);
1908   }
1909
1910   @Contract(pure=true)
1911   public static <T> boolean and(@NotNull Iterable<T> iterable, @NotNull Condition<T> condition) {
1912     for (final T t : iterable) {
1913       if (!condition.value(t)) return false;
1914     }
1915     return true;
1916   }
1917
1918   @Contract(pure=true)
1919   public static <T> boolean exists(@NotNull T[] iterable, @NotNull Condition<T> condition) {
1920     return or(Arrays.asList(iterable), condition);
1921   }
1922
1923   @Contract(pure=true)
1924   public static <T> boolean exists(@NotNull Iterable<T> iterable, @NotNull Condition<T> condition) {
1925     return or(iterable, condition);
1926   }
1927
1928   @Contract(pure=true)
1929   public static <T> boolean or(@NotNull T[] iterable, @NotNull Condition<T> condition) {
1930     return or(Arrays.asList(iterable), condition);
1931   }
1932
1933   @Contract(pure=true)
1934   public static <T> boolean or(@NotNull Iterable<T> iterable, @NotNull Condition<T> condition) {
1935     for (final T t : iterable) {
1936       if (condition.value(t)) return true;
1937     }
1938     return false;
1939   }
1940
1941   @NotNull
1942   @Contract(pure=true)
1943   public static <T> List<T> unfold(@Nullable T t, @NotNull NullableFunction<T, T> next) {
1944     if (t == null) return emptyList();
1945
1946     List<T> list = new ArrayList<T>();
1947     while (t != null) {
1948       list.add(t);
1949       t = next.fun(t);
1950     }
1951     return list;
1952   }
1953
1954   @NotNull
1955   @Contract(pure=true)
1956   public static <T> List<T> dropTail(@NotNull List<T> items) {
1957     return items.subList(0, items.size() - 1);
1958   }
1959
1960   @NotNull
1961   @Contract(pure=true)
1962   public static <T> List<T> list(@NotNull T... items) {
1963     return Arrays.asList(items);
1964   }
1965
1966   // Generalized Quick Sort. Does neither array.clone() nor list.toArray()
1967
1968   public static <T> void quickSort(@NotNull List<T> list, @NotNull Comparator<? super T> comparator) {
1969     quickSort(list, comparator, 0, list.size());
1970   }
1971
1972   private static <T> void quickSort(@NotNull List<T> x, @NotNull Comparator<? super T> comparator, int off, int len) {
1973     // Insertion sort on smallest arrays
1974     if (len < 7) {
1975       for (int i = off; i < len + off; i++) {
1976         for (int j = i; j > off && comparator.compare(x.get(j), x.get(j - 1)) < 0; j--) {
1977           swapElements(x, j, j - 1);
1978         }
1979       }
1980       return;
1981     }
1982
1983     // Choose a partition element, v
1984     int m = off + (len >> 1);       // Small arrays, middle element
1985     if (len > 7) {
1986       int l = off;
1987       int n = off + len - 1;
1988       if (len > 40) {        // Big arrays, pseudomedian of 9
1989         int s = len / 8;
1990         l = med3(x, comparator, l, l + s, l + 2 * s);
1991         m = med3(x, comparator, m - s, m, m + s);
1992         n = med3(x, comparator, n - 2 * s, n - s, n);
1993       }
1994       m = med3(x, comparator, l, m, n); // Mid-size, med of 3
1995     }
1996     T v = x.get(m);
1997
1998     // Establish Invariant: v* (<v)* (>v)* v*
1999     int a = off;
2000     int b = a;
2001     int c = off + len - 1;
2002     int d = c;
2003     while (true) {
2004       while (b <= c && comparator.compare(x.get(b), v) <= 0) {
2005         if (comparator.compare(x.get(b), v) == 0) {
2006           swapElements(x, a++, b);
2007         }
2008         b++;
2009       }
2010       while (c >= b && comparator.compare(v, x.get(c)) <= 0) {
2011         if (comparator.compare(x.get(c), v) == 0) {
2012           swapElements(x, c, d--);
2013         }
2014         c--;
2015       }
2016       if (b > c) break;
2017       swapElements(x, b++, c--);
2018     }
2019
2020     // Swap partition elements back to middle
2021     int n = off + len;
2022     int s = Math.min(a - off, b - a);
2023     vecswap(x, off, b - s, s);
2024     s = Math.min(d - c, n - d - 1);
2025     vecswap(x, b, n - s, s);
2026
2027     // Recursively sort non-partition-elements
2028     if ((s = b - a) > 1) quickSort(x, comparator, off, s);
2029     if ((s = d - c) > 1) quickSort(x, comparator, n - s, s);
2030   }
2031
2032   /*
2033    * Returns the index of the median of the three indexed longs.
2034    */
2035   private static <T> int med3(@NotNull List<T> x, Comparator<? super T> comparator, int a, int b, int c) {
2036     return comparator.compare(x.get(a), x.get(b)) < 0 ? comparator.compare(x.get(b), x.get(c)) < 0
2037                                                         ? b
2038                                                         : comparator.compare(x.get(a), x.get(c)) < 0 ? c : a
2039                                                       : comparator.compare(x.get(c), x.get(b)) < 0
2040                                                         ? b
2041                                                         : comparator.compare(x.get(c), x.get(a)) < 0 ? c : a;
2042   }
2043
2044   /*
2045    * Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)].
2046    */
2047   private static <T> void vecswap(List<T> x, int a, int b, int n) {
2048     for (int i = 0; i < n; i++, a++, b++) {
2049       swapElements(x, a, b);
2050     }
2051   }
2052
2053   /**
2054    * Merge sorted points, which are sorted by x and with equal x by y.
2055    * Result is put to x1 y1.
2056    */
2057   public static void mergeSortedArrays(@NotNull TIntArrayList x1,
2058                                        @NotNull TIntArrayList y1,
2059                                        @NotNull TIntArrayList x2,
2060                                        @NotNull TIntArrayList y2) {
2061     TIntArrayList newX = new TIntArrayList();
2062     TIntArrayList newY = new TIntArrayList();
2063
2064     int i = 0;
2065     int j = 0;
2066
2067     while (i < x1.size() && j < x2.size()) {
2068       if (x1.get(i) < x2.get(j) || x1.get(i) == x2.get(j) && y1.get(i) < y2.get(j)) {
2069         newX.add(x1.get(i));
2070         newY.add(y1.get(i));
2071         i++;
2072       }
2073       else if (x1.get(i) > x2.get(j) || x1.get(i) == x2.get(j) && y1.get(i) > y2.get(j)) {
2074         newX.add(x2.get(j));
2075         newY.add(y2.get(j));
2076         j++;
2077       }
2078       else { //equals
2079         newX.add(x1.get(i));
2080         newY.add(y1.get(i));
2081         i++;
2082         j++;
2083       }
2084     }
2085
2086     while (i < x1.size()) {
2087       newX.add(x1.get(i));
2088       newY.add(y1.get(i));
2089       i++;
2090     }
2091
2092     while (j < x2.size()) {
2093       newX.add(x2.get(j));
2094       newY.add(y2.get(j));
2095       j++;
2096     }
2097
2098     x1.clear();
2099     y1.clear();
2100     x1.add(newX.toNativeArray());
2101     y1.add(newY.toNativeArray());
2102   }
2103
2104
2105   /**
2106    * @return read-only set consisting of the only element o
2107    */
2108   @NotNull
2109   @Contract(pure=true)
2110   public static <T> Set<T> singleton(final T o, @NotNull final TObjectHashingStrategy<T> strategy) {
2111     return new SingletonSet<T>(o, strategy);
2112   }
2113
2114   /**
2115    * @return read-only list consisting of the elements from all of the collections
2116    */
2117   @NotNull
2118   @Contract(pure=true)
2119   public static <E> List<E> flatten(@NotNull Collection<E>[] collections) {
2120     return flatten(Arrays.asList(collections));
2121   }
2122
2123   /**
2124    * @return read-only list consisting of the elements from all of the collections
2125    */
2126   @NotNull
2127   @Contract(pure=true)
2128   public static <E> List<E> flatten(@NotNull Iterable<? extends Collection<E>> collections) {
2129     List<E> result = new ArrayList<E>();
2130     for (Collection<E> list : collections) {
2131       result.addAll(list);
2132     }
2133
2134     return result.isEmpty() ? ContainerUtil.<E>emptyList() : result;
2135   }
2136
2137   /**
2138    * @return read-only list consisting of the elements from all of the collections
2139    */
2140   @NotNull
2141   @Contract(pure=true)
2142   public static <E> List<E> flattenIterables(@NotNull Iterable<? extends Iterable<E>> collections) {
2143     List<E> result = new ArrayList<E>();
2144     for (Iterable<E> list : collections) {
2145       for (E e : list) {
2146         result.add(e);
2147       }
2148     }
2149     return result.isEmpty() ? ContainerUtil.<E>emptyList() : result;
2150   }
2151
2152   @NotNull
2153   @Contract(pure=true)
2154   public static <K,V> V[] convert(@NotNull K[] from, @NotNull V[] to, @NotNull Function<K,V> fun) {
2155     if (to.length < from.length) {
2156       @SuppressWarnings("unchecked") V[] array = (V[])Array.newInstance(to.getClass().getComponentType(), from.length);
2157       to = array;
2158     }
2159     for (int i = 0; i < from.length; i++) {
2160       to[i] = fun.fun(from[i]);
2161     }
2162     return to;
2163   }
2164
2165   @Contract(pure=true)
2166   public static <T> boolean containsIdentity(@NotNull Iterable<T> list, T element) {
2167     for (T t : list) {
2168       if (t == element) {
2169         return true;
2170       }
2171     }
2172     return false;
2173   }
2174
2175   @Contract(pure=true)
2176   public static <T> int indexOfIdentity(@NotNull List<T> list, T element) {
2177     for (int i = 0, listSize = list.size(); i < listSize; i++) {
2178       if (list.get(i) == element) {
2179         return i;
2180       }
2181     }
2182     return -1;
2183   }
2184
2185   @Contract(pure=true)
2186   public static <T> boolean equalsIdentity(@NotNull List<T> list1, @NotNull List<T> list2) {
2187     int listSize = list1.size();
2188     if (list2.size() != listSize) {
2189       return false;
2190     }
2191
2192     for (int i = 0; i < listSize; i++) {
2193       if (list1.get(i) != list2.get(i)) {
2194         return false;
2195       }
2196     }
2197     return true;
2198   }
2199
2200   @Contract(pure=true)
2201   public static <T> int indexOf(@NotNull List<T> list, @NotNull Condition<T> condition) {
2202     for (int i = 0, listSize = list.size(); i < listSize; i++) {
2203       T t = list.get(i);
2204       if (condition.value(t)) {
2205         return i;
2206       }
2207     }
2208     return -1;
2209   }
2210
2211   @Contract(pure=true)
2212   public static <T> int lastIndexOf(@NotNull List<T> list, @NotNull Condition<T> condition) {
2213     for (int i = list.size() - 1; i >= 0; i--) {
2214       T t = list.get(i);
2215       if (condition.value(t)) {
2216         return i;
2217       }
2218     }
2219     return -1;
2220   }
2221
2222   @Nullable
2223   @Contract(pure = true)
2224   public static <T, U extends T> U findLastInstance(@NotNull List<T> list, @NotNull final Class<U> clazz) {
2225     int i = lastIndexOf(list, new Condition<T>() {
2226       @Override
2227       public boolean value(T t) {
2228         return clazz.isInstance(t);
2229       }
2230     });
2231     //noinspection unchecked
2232     return i < 0 ? null : (U)list.get(i);
2233   }
2234
2235   @Contract(pure=true)
2236   public static <T> int indexOf(@NotNull List<T> list, @NotNull final T object) {
2237     return indexOf(list, new Condition<T>() {
2238       @Override
2239       public boolean value(T t) {
2240         return t.equals(object);
2241       }
2242     });
2243   }
2244
2245   @NotNull
2246   @Contract(pure=true)
2247   public static <A,B> Map<B,A> reverseMap(@NotNull Map<A,B> map) {
2248     final Map<B,A> result = newHashMap();
2249     for (Map.Entry<A, B> entry : map.entrySet()) {
2250       result.put(entry.getValue(), entry.getKey());
2251     }
2252     return result;
2253   }
2254
2255   @Contract(pure=true)
2256   public static <T> boolean processRecursively(final T root, @NotNull PairProcessor<T, List<T>> processor) {
2257     final LinkedList<T> list = new LinkedList<T>();
2258     list.add(root);
2259     while (!list.isEmpty()) {
2260       final T o = list.removeFirst();
2261       if (!processor.process(o, list)) return false;
2262     }
2263     return true;
2264   }
2265
2266   @Nullable
2267   public static <T> List<T> trimToSize(@Nullable List<T> list) {
2268     if (list == null) return null;
2269     if (list.isEmpty()) return emptyList();
2270
2271     if (list instanceof ArrayList) {
2272       ((ArrayList)list).trimToSize();
2273     }
2274
2275     return list;
2276   }
2277
2278   @NotNull
2279   @Contract(pure=true)
2280   public static <T> Stack<T> newStack() {
2281     return ContainerUtilRt.newStack();
2282   }
2283
2284   @NotNull
2285   @Contract(pure=true)
2286   public static <T> Stack<T> newStack(@NotNull Collection<T> initial) {
2287     return ContainerUtilRt.newStack(initial);
2288   }
2289
2290   @NotNull
2291   @Contract(pure=true)
2292   public static <T> Stack<T> newStack(@NotNull T... initial) {
2293     return ContainerUtilRt.newStack(initial);
2294   }
2295
2296   @NotNull
2297   @Contract(pure=true)
2298   public static <T> List<T> emptyList() {
2299     return ContainerUtilRt.emptyList();
2300   }
2301
2302   @NotNull
2303   @Contract(pure=true)
2304   public static <T> CopyOnWriteArrayList<T> createEmptyCOWList() {
2305     return ContainerUtilRt.createEmptyCOWList();
2306   }
2307
2308   /**
2309    * Creates List which is thread-safe to modify and iterate.
2310    * It differs from the java.util.concurrent.CopyOnWriteArrayList in the following:
2311    * - faster modification in the uncontended case
2312    * - less memory
2313    * - slower modification in highly contented case (which is the kind of situation you shouldn't use COWAL anyway)
2314    *
2315    * N.B. Avoid using <code>list.toArray(new T[list.size()])</code> on this list because it is inherently racey and
2316    * therefore can return array with null elements at the end.
2317    */
2318   @NotNull
2319   @Contract(pure=true)
2320   public static <T> List<T> createLockFreeCopyOnWriteList() {
2321     return createConcurrentList();
2322   }
2323
2324   @NotNull
2325   @Contract(pure=true)
2326   public static <T> List<T> createLockFreeCopyOnWriteList(@NotNull Collection<? extends T> c) {
2327     return new LockFreeCopyOnWriteArrayList<T>(c);
2328   }
2329
2330   @NotNull
2331   @Contract(pure=true)
2332   public static <V> ConcurrentIntObjectMap<V> createConcurrentIntObjectMap() {
2333     //noinspection deprecation
2334     return new ConcurrentIntObjectHashMap<V>();
2335   }
2336
2337   @NotNull
2338   @Contract(pure=true)
2339   public static <V> ConcurrentIntObjectMap<V> createConcurrentIntObjectSoftValueMap() {
2340     //noinspection deprecation
2341     return new ConcurrentSoftValueIntObjectHashMap<V>();
2342   }
2343
2344   @NotNull
2345   @Contract(pure=true)
2346   public static <V> ConcurrentLongObjectMap<V> createConcurrentLongObjectMap() {
2347     //noinspection deprecation
2348     return new ConcurrentLongObjectHashMap<V>();
2349   }
2350
2351   @NotNull
2352   @Contract(pure=true)
2353   public static <K,V> ConcurrentMap<K,V> createConcurrentWeakValueMap() {
2354     //noinspection deprecation
2355     return new ConcurrentWeakValueHashMap<K, V>();
2356   }
2357
2358   @NotNull
2359   @Contract(pure=true)
2360   public static <V> ConcurrentIntObjectMap<V> createConcurrentIntObjectWeakValueMap() {
2361     //noinspection deprecation
2362     return new ConcurrentWeakValueIntObjectHashMap<V>();
2363   }
2364
2365   @NotNull
2366   @Contract(pure=true)
2367   public static <K,V> ConcurrentMap<K,V> createConcurrentWeakKeySoftValueMap(int initialCapacity,
2368                                                                              float loadFactor,
2369                                                                              int concurrencyLevel,
2370                                                                              @NotNull final TObjectHashingStrategy<K> hashingStrategy) {
2371     //noinspection deprecation
2372     return new ConcurrentWeakKeySoftValueHashMap<K, V>(initialCapacity, loadFactor, concurrencyLevel, hashingStrategy);
2373   }
2374
2375   @NotNull
2376   @Contract(pure=true)
2377   public static <K,V> ConcurrentMap<K,V> createConcurrentWeakKeySoftValueMap() {
2378     return createConcurrentWeakKeySoftValueMap(100, 0.75f, Runtime.getRuntime().availableProcessors(), ContainerUtil.<K>canonicalStrategy());
2379   }
2380
2381   @NotNull
2382   @Contract(pure=true)
2383   public static <K,V> ConcurrentMap<K,V> createConcurrentWeakKeyWeakValueMap() {
2384     //noinspection deprecation
2385     return new ConcurrentWeakKeyWeakValueHashMap<K, V>(100, 0.75f, Runtime.getRuntime().availableProcessors(), ContainerUtil.<K>canonicalStrategy());
2386   }
2387
2388   @NotNull
2389   @Contract(pure = true)
2390   public static <K, V> ConcurrentMap<K,V> createConcurrentSoftValueMap() {
2391     //noinspection deprecation
2392     return new ConcurrentSoftValueHashMap<K, V>();
2393   }
2394
2395   @NotNull
2396   @Contract(pure=true)
2397   public static <K,V> ConcurrentMap<K,V> createConcurrentSoftMap() {
2398     //noinspection deprecation
2399     return new ConcurrentSoftHashMap<K, V>();
2400   }
2401
2402   @NotNull
2403   @Contract(pure=true)
2404   public static <K,V> ConcurrentMap<K,V> createConcurrentWeakMap() {
2405     //noinspection deprecation
2406     return new ConcurrentWeakHashMap<K, V>();
2407   }
2408   @NotNull
2409   @Contract(pure=true)
2410   public static <K,V> ConcurrentMap<K,V> createConcurrentWeakMap(int initialCapacity,
2411                                  float loadFactor,
2412                                  int concurrencyLevel,
2413                                  @NotNull TObjectHashingStrategy<K> hashingStrategy) {
2414     //noinspection deprecation
2415     return new ConcurrentWeakHashMap<K, V>(initialCapacity, loadFactor, concurrencyLevel, hashingStrategy);
2416   }
2417
2418   /**
2419    * @see {@link #createLockFreeCopyOnWriteList()}
2420    */
2421   @NotNull
2422   @Contract(pure=true)
2423   public static <T> ConcurrentList<T> createConcurrentList() {
2424     return new LockFreeCopyOnWriteArrayList<T>();
2425   }
2426
2427   public static <T> void addIfNotNull(@Nullable T element, @NotNull Collection<T> result) {
2428     ContainerUtilRt.addIfNotNull(element, result);
2429   }
2430
2431   public static <T> void addIfNotNull(@NotNull Collection<T> result, @Nullable T element) {
2432     ContainerUtilRt.addIfNotNull(result, element);
2433   }
2434
2435   @NotNull
2436   @Contract(pure=true)
2437   public static <T, V> List<V> map2List(@NotNull T[] array, @NotNull Function<T, V> mapper) {
2438     return ContainerUtilRt.map2List(array, mapper);
2439   }
2440
2441   @NotNull
2442   @Contract(pure=true)
2443   public static <T, V> List<V> map2List(@NotNull Collection<? extends T> collection, @NotNull Function<T, V> mapper) {
2444     return ContainerUtilRt.map2List(collection, mapper);
2445   }
2446
2447   @NotNull
2448   @Contract(pure=true)
2449   public static <T, V> Set<V> map2Set(@NotNull T[] collection, @NotNull Function<T, V> mapper) {
2450     return ContainerUtilRt.map2Set(collection, mapper);
2451   }
2452
2453   @NotNull
2454   @Contract(pure=true)
2455   public static <T, V> Set<V> map2Set(@NotNull Collection<? extends T> collection, @NotNull Function<T, V> mapper) {
2456     return ContainerUtilRt.map2Set(collection, mapper);
2457   }
2458
2459   @NotNull
2460   @Contract(pure=true)
2461   public static <T, V> Set<V> map2LinkedSet(@NotNull Collection<? extends T> collection, @NotNull Function<T, V> mapper) {
2462     if (collection.isEmpty()) return Collections.emptySet();
2463     Set <V> set = new LinkedHashSet<V>(collection.size());
2464     for (final T t : collection) {
2465       set.add(mapper.fun(t));
2466     }
2467     return set;
2468   }
2469
2470   @NotNull
2471   @Contract(pure=true)
2472   public static <T, V> Set<V> map2SetNotNull(@NotNull Collection<? extends T> collection, @NotNull Function<T, V> mapper) {
2473     if (collection.isEmpty()) return Collections.emptySet();
2474     Set <V> set = new HashSet<V>(collection.size());
2475     for (T t : collection) {
2476       V value = mapper.fun(t);
2477       if (value != null) {
2478         set.add(value);
2479       }
2480     }
2481     return set.isEmpty() ? Collections.<V>emptySet() : set;
2482   }
2483
2484   @NotNull
2485   @Contract(pure=true)
2486   public static <T> T[] toArray(@NotNull List<T> collection, @NotNull T[] array) {
2487     return ContainerUtilRt.toArray(collection, array);
2488   }
2489
2490   @NotNull
2491   @Contract(pure=true)
2492   public static <T> T[] toArray(@NotNull Collection<T> c, @NotNull T[] sample) {
2493     return ContainerUtilRt.toArray(c, sample);
2494   }
2495
2496   @NotNull
2497   public static <T> T[] copyAndClear(@NotNull Collection<T> collection, @NotNull ArrayFactory<T> factory, boolean clear) {
2498     int size = collection.size();
2499     T[] a = factory.create(size);
2500     if (size > 0) {
2501       a = collection.toArray(a);
2502       if (clear) collection.clear();
2503     }
2504     return a;
2505   }
2506
2507   @NotNull
2508   @Contract(pure=true)
2509   public static <T> Collection<T> toCollection(@NotNull Iterable<T> iterable) {
2510     return iterable instanceof Collection ? (Collection<T>)iterable : newArrayList(iterable);
2511   }
2512
2513   @NotNull
2514   public static <T> List<T> toList(@NotNull Enumeration<T> enumeration) {
2515     if (!enumeration.hasMoreElements()) {
2516       return Collections.emptyList();
2517     }
2518
2519     List<T> result = new SmartList<T>();
2520     while (enumeration.hasMoreElements()) {
2521       result.add(enumeration.nextElement());
2522     }
2523     return result;
2524   }
2525
2526   @Contract(value = "null -> true", pure = true)
2527   public static <T> boolean isEmpty(Collection<T> collection) {
2528     return collection == null || collection.isEmpty();
2529   }
2530
2531   @NotNull
2532   @Contract(pure=true)
2533   public static <T> List<T> notNullize(@Nullable List<T> list) {
2534     return list == null ? ContainerUtilRt.<T>emptyList() : list;
2535   }
2536
2537   @NotNull
2538   @Contract(pure=true)
2539   public static <T> Set<T> notNullize(@Nullable Set<T> set) {
2540     //noinspection unchecked
2541     return set == null ? Collections.<T>emptySet() : set;
2542   }
2543
2544   @Nullable
2545   @Contract(pure=true)
2546   public static <T, C extends Collection<T>> C nullize(@Nullable C collection) {
2547     return isEmpty(collection) ? null : collection;
2548   }
2549
2550   private interface ConcurrentMapFactory {
2551     @NotNull <T, V> ConcurrentMap<T, V> createMap();
2552     @NotNull <T, V> ConcurrentMap<T, V> createMap(int initialCapacity);
2553     @NotNull <T, V> ConcurrentMap<T, V> createMap(@NotNull TObjectHashingStrategy<T> hashStrategy);
2554     @NotNull <T, V> ConcurrentMap<T, V> createMap(int initialCapacity, float loadFactor, int concurrencyLevel);
2555     @NotNull <T, V> ConcurrentMap<T, V> createMap(int initialCapacity, float loadFactor, int concurrencyLevel, @NotNull TObjectHashingStrategy<T> hashStrategy);
2556   }
2557
2558   private static final ConcurrentMapFactory V8_MAP_FACTORY = new ConcurrentMapFactory() {
2559     @Override
2560     @NotNull
2561     public <T, V> ConcurrentMap<T, V> createMap() {
2562       return new ConcurrentHashMap<T,V>();
2563     }
2564
2565     @Override
2566     @NotNull
2567     public <T, V> ConcurrentMap<T, V> createMap(int initialCapacity) {
2568       return new ConcurrentHashMap<T,V>(initialCapacity);
2569     }
2570
2571     @Override
2572     @NotNull
2573     public <T, V> ConcurrentMap<T, V> createMap(@NotNull TObjectHashingStrategy<T> hashStrategy) {
2574       return new ConcurrentHashMap<T,V>(hashStrategy);
2575     }
2576
2577     @Override
2578     @NotNull
2579     public <T, V> ConcurrentMap<T, V> createMap(int initialCapacity, float loadFactor, int concurrencyLevel) {
2580       return new ConcurrentHashMap<T,V>(initialCapacity, loadFactor, concurrencyLevel);
2581     }
2582
2583     @Override
2584     @NotNull
2585     public <T, V> ConcurrentMap<T, V> createMap(int initialCapacity, float loadFactor, int concurrencyLevel, @NotNull TObjectHashingStrategy<T> hashingStrategy) {
2586       return new ConcurrentHashMap<T,V>(initialCapacity, loadFactor, concurrencyLevel, hashingStrategy);
2587     }
2588   };
2589
2590   private static final ConcurrentMapFactory PLATFORM_MAP_FACTORY = new ConcurrentMapFactory() {
2591     @Override
2592     @NotNull
2593     public <T, V> ConcurrentMap<T, V> createMap() {
2594       return createMap(16, 0.75f, DEFAULT_CONCURRENCY_LEVEL);
2595     }
2596
2597     @Override
2598     @NotNull
2599     public <T, V> ConcurrentMap<T, V> createMap(int initialCapacity) {
2600       return new java.util.concurrent.ConcurrentHashMap<T,V>(initialCapacity);
2601     }
2602
2603     @Override
2604     @NotNull
2605     public <T, V> ConcurrentMap<T, V> createMap(@NotNull TObjectHashingStrategy<T> hashingStrategy) {
2606       if (hashingStrategy != canonicalStrategy()) {
2607         throw new UnsupportedOperationException("Custom hashStrategy is not supported in java.util.concurrent.ConcurrentHashMap");
2608       }
2609       // ignoring strategy parameter, because it is not supported by this implementation
2610       return createMap();
2611     }
2612
2613     @Override
2614     @NotNull
2615     public <T, V> ConcurrentMap<T, V> createMap(int initialCapacity, float loadFactor, int concurrencyLevel) {
2616       return new java.util.concurrent.ConcurrentHashMap<T,V>(initialCapacity, loadFactor, concurrencyLevel);
2617     }
2618
2619     @Override
2620     @NotNull
2621     public <T, V> ConcurrentMap<T, V> createMap(int initialCapacity, float loadFactor, int concurrencyLevel, @NotNull TObjectHashingStrategy<T> hashingStrategy) {
2622       if (hashingStrategy != canonicalStrategy()) {
2623         throw new UnsupportedOperationException("Custom hashStrategy is not supported in java.util.concurrent.ConcurrentHashMap");
2624       }
2625       // ignoring strategy parameter, because it is not supported by this implementation
2626       return createMap(initialCapacity, loadFactor, concurrencyLevel);
2627     }
2628   };
2629
2630   private static final ConcurrentMapFactory CHM_FACTORY = SystemInfo.isOracleJvm || SystemInfo.isSunJvm || SystemInfo.isAppleJvm || isAtLeastJava7() ? V8_MAP_FACTORY : PLATFORM_MAP_FACTORY;
2631
2632   private static boolean isAtLeastJava7() {
2633     // IBM JDK provides correct version in java.version property, but not in java.runtime.version property
2634     return StringUtil.compareVersionNumbers(SystemInfo.JAVA_VERSION, "1.7") >= 0;
2635   }
2636
2637   @Contract(pure=true)
2638   public static <T extends Comparable<T>> int compareLexicographically(@NotNull List<T> o1, @NotNull List<T> o2) {
2639     for (int i = 0; i < Math.min(o1.size(), o2.size()); i++) {
2640       int result = Comparing.compare(o1.get(i), o2.get(i));
2641       if (result != 0) {
2642         return result;
2643       }
2644     }
2645     return o1.size() < o2.size() ? -1 : o1.size() == o2.size() ? 0 : 1;
2646   }
2647
2648   @Contract(pure=true)
2649   public static <T> int compareLexicographically(@NotNull List<T> o1, @NotNull List<T> o2, @NotNull Comparator<T> comparator) {
2650     for (int i = 0; i < Math.min(o1.size(), o2.size()); i++) {
2651       int result = comparator.compare(o1.get(i), o2.get(i));
2652       if (result != 0) {
2653         return result;
2654       }
2655     }
2656     return o1.size() < o2.size() ? -1 : o1.size() == o2.size() ? 0 : 1;
2657   }
2658
2659   /**
2660    * Returns a String representation of the given map, by listing all key-value pairs contained in the map.
2661    */
2662   @NotNull
2663   @Contract(pure = true)
2664   public static String toString(@NotNull Map<?, ?> map) {
2665     StringBuilder sb = new StringBuilder("{");
2666     for (Iterator<? extends Map.Entry<?, ?>> iterator = map.entrySet().iterator(); iterator.hasNext(); ) {
2667       Map.Entry<?, ?> entry = iterator.next();
2668       sb.append(entry.getKey()).append('=').append(entry.getValue());
2669       if (iterator.hasNext()) {
2670         sb.append(", ");
2671       }
2672     }
2673     sb.append('}');
2674     return sb.toString();
2675   }
2676 }
2677