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