/* * Copyright 2000-2014 JetBrains s.r.o. * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. * You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * See the License for the specific language governing permissions and * limitations under the License. */ package com.intellij.util.containers; import com.intellij.openapi.Disposable; import com.intellij.openapi.util.*; import com.intellij.openapi.util.text.StringUtil; import com.intellij.util.*; import gnu.trove.*; import org.jetbrains.annotations.Contract; import org.jetbrains.annotations.NotNull; import org.jetbrains.annotations.Nullable; import java.lang.reflect.Array; import java.util.*; import java.util.HashMap; import java.util.HashSet; import java.util.LinkedHashMap; import java.util.LinkedHashSet; import java.util.concurrent.ConcurrentMap; import java.util.concurrent.CopyOnWriteArrayList; @SuppressWarnings({"UtilityClassWithoutPrivateConstructor", "MethodOverridesStaticMethodOfSuperclass", "UnusedDeclaration"}) public class ContainerUtil extends ContainerUtilRt { private static final int INSERTION_SORT_THRESHOLD = 10; private static final int DEFAULT_CONCURRENCY_LEVEL = Math.min(16, Runtime.getRuntime().availableProcessors()); @NotNull public static T[] ar(@NotNull T... elements) { return elements; } @NotNull public static HashMap newHashMap() { return ContainerUtilRt.newHashMap(); } @NotNull public static HashMap newHashMap(@NotNull Map map) { return ContainerUtilRt.newHashMap(map); } @NotNull public static Map newHashMap(@NotNull Pair first, Pair... entries) { return ContainerUtilRt.newHashMap(first, entries); } @NotNull public static Map newHashMap(@NotNull List keys, @NotNull List values) { return ContainerUtilRt.newHashMap(keys, values); } @NotNull public static TreeMap newTreeMap() { return ContainerUtilRt.newTreeMap(); } @NotNull public static TreeMap newTreeMap(@NotNull Map map) { return ContainerUtilRt.newTreeMap(map); } @NotNull public static LinkedHashMap newLinkedHashMap() { return ContainerUtilRt.newLinkedHashMap(); } @NotNull public static LinkedHashMap newLinkedHashMap(@NotNull Map map) { return ContainerUtilRt.newLinkedHashMap(map); } @NotNull public static LinkedHashMap newLinkedHashMap(@NotNull Pair first, Pair... entries) { return ContainerUtilRt.newLinkedHashMap(first, entries); } @NotNull public static THashMap newTroveMap() { return new THashMap(); } @NotNull public static THashMap newTroveMap(@NotNull TObjectHashingStrategy strategy) { return new THashMap(strategy); } @NotNull public static , V> EnumMap newEnumMap(@NotNull Class keyType) { return new EnumMap(keyType); } @SuppressWarnings("unchecked") @NotNull public static TObjectHashingStrategy canonicalStrategy() { return TObjectHashingStrategy.CANONICAL; } @SuppressWarnings("unchecked") @NotNull public static TObjectHashingStrategy identityStrategy() { return TObjectHashingStrategy.IDENTITY; } @NotNull public static IdentityHashMap newIdentityHashMap() { return new IdentityHashMap(); } @NotNull public static LinkedList newLinkedList() { return ContainerUtilRt.newLinkedList(); } @NotNull public static LinkedList newLinkedList(@NotNull T... elements) { return ContainerUtilRt.newLinkedList(elements); } @NotNull public static LinkedList newLinkedList(@NotNull Iterable elements) { return ContainerUtilRt.newLinkedList(elements); } @NotNull public static ArrayList newArrayList() { return ContainerUtilRt.newArrayList(); } @NotNull public static ArrayList newArrayList(@NotNull E... array) { return ContainerUtilRt.newArrayList(array); } @NotNull public static ArrayList newArrayList(@NotNull Iterable iterable) { return ContainerUtilRt.newArrayList(iterable); } /** @deprecated Use {@link #newArrayListWithCapacity(int)} (to remove in IDEA 15) */ @SuppressWarnings("deprecation") public static ArrayList newArrayListWithExpectedSize(int size) { return ContainerUtilRt.newArrayListWithCapacity(size); } @NotNull public static ArrayList newArrayListWithCapacity(int size) { return ContainerUtilRt.newArrayListWithCapacity(size); } @NotNull public static List newArrayList(@NotNull final T[] elements, final int start, final int end) { if (start < 0 || start > end || end > elements.length) { throw new IllegalArgumentException("start:" + start + " end:" + end + " length:" + elements.length); } return new AbstractList() { private final int size = end - start; @Override public T get(final int index) { if (index < 0 || index >= size) throw new IndexOutOfBoundsException("index:" + index + " size:" + size); return elements[start + index]; } @Override public int size() { return size; } }; } @NotNull public static List newSmartList(T element) { return new SmartList(element); } @NotNull public static List newSmartList(@NotNull T... elements) { return new SmartList(elements); } @NotNull public static HashSet newHashSet() { return ContainerUtilRt.newHashSet(); } @NotNull public static HashSet newHashSet(int initialCapacity) { return ContainerUtilRt.newHashSet(initialCapacity); } @NotNull public static HashSet newHashSet(@NotNull T... elements) { return ContainerUtilRt.newHashSet(elements); } @NotNull public static HashSet newHashSet(@NotNull Iterable iterable) { return ContainerUtilRt.newHashSet(iterable); } @NotNull public static HashSet newHashSet(@NotNull Iterator iterator) { return ContainerUtilRt.newHashSet(iterator); } @NotNull public static Set newHashOrEmptySet(@Nullable Iterable iterable) { boolean empty = iterable == null || iterable instanceof Collection && ((Collection)iterable).isEmpty(); return empty ? Collections.emptySet() : ContainerUtilRt.newHashSet(iterable); } @NotNull public static LinkedHashSet newLinkedHashSet() { return ContainerUtilRt.newLinkedHashSet(); } @NotNull public static LinkedHashSet newLinkedHashSet(@NotNull Iterable elements) { return ContainerUtilRt.newLinkedHashSet(elements); } @NotNull public static LinkedHashSet newLinkedHashSet(@NotNull T... elements) { return ContainerUtilRt.newLinkedHashSet(elements); } @NotNull public static THashSet newTroveSet() { return new THashSet(); } @NotNull public static THashSet newTroveSet(@NotNull TObjectHashingStrategy strategy) { return new THashSet(strategy); } @NotNull public static THashSet newTroveSet(@NotNull T... elements) { return newTroveSet(Arrays.asList(elements)); } @NotNull public static THashSet newTroveSet(@NotNull TObjectHashingStrategy strategy, @NotNull T... elements) { return new THashSet(Arrays.asList(elements), strategy); } @NotNull public static THashSet newTroveSet(@NotNull TObjectHashingStrategy strategy, @NotNull Collection elements) { return new THashSet(elements, strategy); } @NotNull public static THashSet newTroveSet(@NotNull Collection elements) { return new THashSet(elements); } @NotNull public static THashSet newIdentityTroveSet() { return new THashSet(ContainerUtil.identityStrategy()); } @NotNull public static THashSet newIdentityTroveSet(int initialCapacity) { return new THashSet(initialCapacity, ContainerUtil.identityStrategy()); } @NotNull public static THashSet newIdentityTroveSet(@NotNull Collection collection) { return new THashSet(collection, ContainerUtil.identityStrategy()); } @NotNull public static THashMap newIdentityTroveMap() { return new THashMap(ContainerUtil.identityStrategy()); } @NotNull public static TreeSet newTreeSet() { return ContainerUtilRt.newTreeSet(); } @NotNull public static TreeSet newTreeSet(@NotNull Iterable elements) { return ContainerUtilRt.newTreeSet(elements); } @NotNull public static TreeSet newTreeSet(@NotNull T... elements) { return ContainerUtilRt.newTreeSet(elements); } @NotNull public static TreeSet newTreeSet(@Nullable Comparator comparator) { return ContainerUtilRt.newTreeSet(comparator); } @NotNull public static ConcurrentMap newConcurrentMap() { return CHM_FACTORY.createMap(); } public static ConcurrentMap newConcurrentMap(@NotNull TObjectHashingStrategy hashStrategy) { return CHM_FACTORY.createMap(hashStrategy); } public static ConcurrentMap newConcurrentMap(int initialCapacity) { return CHM_FACTORY.createMap(initialCapacity); } public static ConcurrentMap newConcurrentMap(int initialCapacity, float loadFactor, int concurrencyLevel, @NotNull TObjectHashingStrategy hashStrategy) { return CHM_FACTORY.createMap(initialCapacity, loadFactor, concurrencyLevel, hashStrategy); } public static ConcurrentMap newConcurrentMap(int initialCapacity, float loadFactor, int concurrencyLevel) { return CHM_FACTORY.createMap(initialCapacity, loadFactor, concurrencyLevel); } @NotNull public static List reverse(@NotNull final List elements) { if (elements.isEmpty()) { return ContainerUtilRt.emptyList(); } return new AbstractList() { @Override public E get(int index) { return elements.get(elements.size() - 1 - index); } @Override public int size() { return elements.size(); } }; } @NotNull public static Map union(@NotNull Map map, @NotNull Map map2) { THashMap result = new THashMap(map.size() + map2.size()); result.putAll(map); result.putAll(map2); return result; } @NotNull public static Set union(@NotNull Set set, @NotNull Set set2) { THashSet result = new THashSet(set.size() + set2.size()); result.addAll(set); result.addAll(set2); return result; } @NotNull public static Set immutableSet(@NotNull E ... elements) { return Collections.unmodifiableSet(new THashSet(Arrays.asList(elements))); } @NotNull public static ImmutableList immutableList(@NotNull E ... array) { return new ImmutableListBackedByArray(array); } @NotNull public static ImmutableList immutableList(@NotNull List list) { return new ImmutableListBackedByList(list); } @NotNull public static ImmutableMapBuilder immutableMapBuilder() { return new ImmutableMapBuilder(); } public static class ImmutableMapBuilder { private final Map myMap = new THashMap(); public ImmutableMapBuilder put(K key, V value) { myMap.put(key, value); return this; } public Map build() { return Collections.unmodifiableMap(myMap); } } private static class ImmutableListBackedByList extends ImmutableList { private final List myStore; private ImmutableListBackedByList(@NotNull List list) { myStore = list; } @Override public E get(int index) { return myStore.get(index); } @Override public int size() { return myStore.size(); } } private static class ImmutableListBackedByArray extends ImmutableList { private final E[] myStore; private ImmutableListBackedByArray(@NotNull E[] array) { myStore = array; } @Override public E get(int index) { return myStore[index]; } @Override public int size() { return myStore.length; } } @NotNull public static Map intersection(@NotNull Map map1, @NotNull Map map2) { final Map res = newHashMap(); final Set keys = newHashSet(); keys.addAll(map1.keySet()); keys.addAll(map2.keySet()); for (K k : keys) { V v1 = map1.get(k); V v2 = map2.get(k); if (v1 == v2 || v1 != null && v1.equals(v2)) { res.put(k, v1); } } return res; } @NotNull public static Map> diff(@NotNull Map map1, @NotNull Map map2) { final Map> res = newHashMap(); final Set keys = newHashSet(); keys.addAll(map1.keySet()); keys.addAll(map2.keySet()); for (K k : keys) { V v1 = map1.get(k); V v2 = map2.get(k); if (!(v1 == v2 || v1 != null && v1.equals(v2))) { res.put(k, Couple.of(v1, v2)); } } return res; } public static boolean processSortedListsInOrder(@NotNull List list1, @NotNull List list2, @NotNull Comparator comparator, boolean mergeEqualItems, @NotNull Processor processor) { int index1 = 0; int index2 = 0; while (index1 < list1.size() || index2 < list2.size()) { T e; if (index1 >= list1.size()) { e = list2.get(index2++); } else if (index2 >= list2.size()) { e = list1.get(index1++); } else { T element1 = list1.get(index1); T element2 = list2.get(index2); int c = comparator.compare(element1, element2); if (c <= 0) { e = element1; index1++; } else { e = element2; index2++; } if (c == 0 && !mergeEqualItems) { if (!processor.process(e)) return false; index2++; e = element2; } } if (!processor.process(e)) return false; } return true; } @NotNull public static List mergeSortedLists(@NotNull List list1, @NotNull List list2, @NotNull Comparator comparator, boolean mergeEqualItems) { final List result = new ArrayList(list1.size() + list2.size()); processSortedListsInOrder(list1, list2, comparator, mergeEqualItems, new Processor() { @Override public boolean process(T t) { result.add(t); return true; } }); return result; } @NotNull public static List mergeSortedArrays(@NotNull T[] list1, @NotNull T[] list2, @NotNull Comparator comparator, boolean mergeEqualItems, @Nullable Processor filter) { int index1 = 0; int index2 = 0; List result = new ArrayList(list1.length + list2.length); while (index1 < list1.length || index2 < list2.length) { if (index1 >= list1.length) { T t = list2[index2++]; if (filter != null && !filter.process(t)) continue; result.add(t); } else if (index2 >= list2.length) { T t = list1[index1++]; if (filter != null && !filter.process(t)) continue; result.add(t); } else { T element1 = list1[index1]; if (filter != null && !filter.process(element1)) { index1++; continue; } T element2 = list2[index2]; if (filter != null && !filter.process(element2)) { index2++; continue; } int c = comparator.compare(element1, element2); if (c < 0) { result.add(element1); index1++; } else if (c > 0) { result.add(element2); index2++; } else { result.add(element1); if (!mergeEqualItems) { result.add(element2); } index1++; index2++; } } } return result; } @NotNull public static List subList(@NotNull List list, int from) { return list.subList(from, list.size()); } public static void addAll(@NotNull Collection collection, @NotNull Iterable appendix) { addAll(collection, appendix.iterator()); } public static void addAll(@NotNull Collection collection, @NotNull Iterator iterator) { while (iterator.hasNext()) { T o = iterator.next(); collection.add(o); } } /** * Adds all not-null elements from the {@code elements}, ignoring nulls */ public static void addAllNotNull(@NotNull Collection collection, @NotNull Iterable elements) { addAllNotNull(collection, elements.iterator()); } /** * Adds all not-null elements from the {@code elements}, ignoring nulls */ public static void addAllNotNull(@NotNull Collection collection, @NotNull Iterator elements) { while (elements.hasNext()) { T o = elements.next(); if (o != null) { collection.add(o); } } } @NotNull public static List collect(@NotNull Iterator iterator) { if (!iterator.hasNext()) return emptyList(); List list = new ArrayList(); addAll(list, iterator); return list; } @NotNull public static Set collectSet(@NotNull Iterator iterator) { if (!iterator.hasNext()) return Collections.emptySet(); Set hashSet = newHashSet(); addAll(hashSet, iterator); return hashSet; } @NotNull public static Map newMapFromKeys(@NotNull Iterator keys, @NotNull Convertor valueConvertor) { Map map = newHashMap(); while (keys.hasNext()) { K key = keys.next(); map.put(key, valueConvertor.convert(key)); } return map; } @NotNull public static Map newMapFromValues(@NotNull Iterator values, @NotNull Convertor keyConvertor) { Map map = newHashMap(); while (values.hasNext()) { V value = values.next(); map.put(keyConvertor.convert(value), value); } return map; } @NotNull public static Map> classify(@NotNull Iterator iterator, @NotNull Convertor keyConvertor) { Map> hashMap = new LinkedHashMap>(); while (iterator.hasNext()) { V value = iterator.next(); final K key = keyConvertor.convert(value); Set set = hashMap.get(key); if (set == null) { hashMap.put(key, set = new LinkedHashSet()); // ordered set!! } set.add(value); } return hashMap; } @NotNull public static Iterator emptyIterator() { return EmptyIterator.getInstance(); } @NotNull public static Iterable emptyIterable() { return EmptyIterable.getInstance(); } @Nullable public static T find(@NotNull T[] array, @NotNull Condition condition) { for (T element : array) { if (condition.value(element)) return element; } return null; } public static boolean process(@NotNull Iterable iterable, @NotNull Processor processor) { for (final T t : iterable) { if (!processor.process(t)) { return false; } } return true; } public static boolean process(@NotNull List list, @NotNull Processor processor) { //noinspection ForLoopReplaceableByForEach for (int i = 0, size = list.size(); i < size; i++) { T t = list.get(i); if (!processor.process(t)) { return false; } } return true; } public static boolean process(@NotNull T[] iterable, @NotNull Processor processor) { for (final T t : iterable) { if (!processor.process(t)) { return false; } } return true; } public static boolean process(@NotNull Iterator iterator, @NotNull Processor processor) { while (iterator.hasNext()) { if (!processor.process(iterator.next())) { return false; } } return true; } @Nullable public static V find(@NotNull Iterable iterable, @NotNull Condition condition) { return find(iterable.iterator(), condition); } @Nullable public static T find(@NotNull Iterable iterable, final T equalTo) { return find(iterable, new Condition() { @Override public boolean value(final T object) { return equalTo == object || equalTo.equals(object); } }); } @Nullable public static V find(@NotNull Iterator iterator, @NotNull Condition condition) { while (iterator.hasNext()) { V value = iterator.next(); if (condition.value(value)) return value; } return null; } @NotNull public static Map map2Map(@NotNull T[] collection, @NotNull Function> mapper) { return map2Map(Arrays.asList(collection), mapper); } @NotNull public static Map map2Map(@NotNull Collection collection, @NotNull Function> mapper) { final Map set = new THashMap(collection.size()); for (T t : collection) { Pair pair = mapper.fun(t); set.put(pair.first, pair.second); } return set; } @NotNull public static Map map2Map(@NotNull Collection> collection) { final Map result = new THashMap(collection.size()); for (Pair pair : collection) { result.put(pair.first, pair.second); } return result; } @NotNull public static Object[] map2Array(@NotNull T[] array, @NotNull Function mapper) { return map2Array(array, Object.class, mapper); } @NotNull public static Object[] map2Array(@NotNull Collection array, @NotNull Function mapper) { return map2Array(array, Object.class, mapper); } @NotNull public static V[] map2Array(@NotNull T[] array, @NotNull Class aClass, @NotNull Function mapper) { return map2Array(Arrays.asList(array), aClass, mapper); } @NotNull public static V[] map2Array(@NotNull Collection collection, @NotNull Class aClass, @NotNull Function mapper) { final List list = map2List(collection, mapper); @SuppressWarnings("unchecked") V[] array = (V[])Array.newInstance(aClass, list.size()); return list.toArray(array); } @NotNull public static V[] map2Array(@NotNull Collection collection, @NotNull V[] to, @NotNull Function mapper) { return map2List(collection, mapper).toArray(to); } @NotNull public static List filter(@NotNull T[] collection, @NotNull Condition condition) { return findAll(collection, condition); } @NotNull public static int[] filter(@NotNull int[] collection, @NotNull TIntProcedure condition) { TIntArrayList result = new TIntArrayList(); for (int t : collection) { if (condition.execute(t)) { result.add(t); } } return result.isEmpty() ? ArrayUtil.EMPTY_INT_ARRAY : result.toNativeArray(); } @NotNull public static List filter(@NotNull Condition condition, @NotNull T... collection) { return findAll(collection, condition); } @NotNull public static List findAll(@NotNull T[] collection, @NotNull Condition condition) { final List result = new SmartList(); for (T t : collection) { if (condition.value(t)) { result.add(t); } } return result; } @NotNull public static List filter(@NotNull Collection collection, @NotNull Condition condition) { return findAll(collection, condition); } @NotNull public static List findAll(@NotNull Collection collection, @NotNull Condition condition) { if (collection.isEmpty()) return emptyList(); final List result = new SmartList(); for (final T t : collection) { if (condition.value(t)) { result.add(t); } } return result; } @NotNull public static List skipNulls(@NotNull Collection collection) { return findAll(collection, Condition.NOT_NULL); } @NotNull public static List findAll(@NotNull T[] collection, @NotNull Class instanceOf) { return findAll(Arrays.asList(collection), instanceOf); } @NotNull public static V[] findAllAsArray(@NotNull T[] collection, @NotNull Class instanceOf) { List list = findAll(Arrays.asList(collection), instanceOf); @SuppressWarnings("unchecked") V[] array = (V[])Array.newInstance(instanceOf, list.size()); return list.toArray(array); } @NotNull public static V[] findAllAsArray(@NotNull Collection collection, @NotNull Class instanceOf) { List list = findAll(collection, instanceOf); @SuppressWarnings("unchecked") V[] array = (V[])Array.newInstance(instanceOf, list.size()); return list.toArray(array); } @NotNull public static T[] findAllAsArray(@NotNull T[] collection, @NotNull Condition instanceOf) { List list = findAll(collection, instanceOf); @SuppressWarnings("unchecked") T[] array = (T[])Array.newInstance(collection.getClass().getComponentType(), list.size()); return list.toArray(array); } @NotNull public static List findAll(@NotNull Collection collection, @NotNull Class instanceOf) { final List result = new SmartList(); for (final T t : collection) { if (instanceOf.isInstance(t)) { @SuppressWarnings("unchecked") V v = (V)t; result.add(v); } } return result; } public static void removeDuplicates(@NotNull Collection collection) { Set collected = newHashSet(); for (Iterator iterator = collection.iterator(); iterator.hasNext();) { T t = iterator.next(); if (!collected.contains(t)) { collected.add(t); } else { iterator.remove(); } } } @NotNull public static Map stringMap(@NotNull final String... keyValues) { final Map result = newHashMap(); for (int i = 0; i < keyValues.length - 1; i+=2) { result.put(keyValues[i], keyValues[i+1]); } return result; } @NotNull public static Iterator iterate(@NotNull T[] arrays) { return Arrays.asList(arrays).iterator(); } @NotNull public static Iterator iterate(@NotNull final Enumeration enumeration) { return new Iterator() { @Override public boolean hasNext() { return enumeration.hasMoreElements(); } @Override public T next() { return enumeration.nextElement(); } @Override public void remove() { throw new UnsupportedOperationException(); } }; } @NotNull public static Iterable iterate(@NotNull T[] arrays, @NotNull Condition condition) { return iterate(Arrays.asList(arrays), condition); } @NotNull public static Iterable iterate(@NotNull final Collection collection, @NotNull final Condition condition) { if (collection.isEmpty()) return emptyIterable(); return new Iterable() { @Override public Iterator iterator() { return new Iterator() { Iterator impl = collection.iterator(); T next = findNext(); @Override public boolean hasNext() { return next != null; } @Override public T next() { T result = next; next = findNext(); return result; } @Nullable private T findNext() { while (impl.hasNext()) { T each = impl.next(); if (condition.value(each)) { return each; } } return null; } @Override public void remove() { throw new UnsupportedOperationException(); } }; } }; } @NotNull public static Iterable iterateBackward(@NotNull final List list) { return new Iterable() { @Override public Iterator iterator() { return new Iterator() { ListIterator it = list.listIterator(list.size()); @Override public boolean hasNext() { return it.hasPrevious(); } @Override public T next() { return it.previous(); } @Override public void remove() { it.remove(); } }; } }; } public static void swapElements(@NotNull List list, int index1, int index2) { E e1 = list.get(index1); E e2 = list.get(index2); list.set(index1, e2); list.set(index2, e1); } @NotNull public static List collect(@NotNull Iterator iterator, @NotNull FilteringIterator.InstanceOf instanceOf) { @SuppressWarnings("unchecked") List list = collect(FilteringIterator.create((Iterator)iterator, instanceOf)); return list; } public static void addAll(@NotNull Collection collection, @NotNull Enumeration enumeration) { while (enumeration.hasMoreElements()) { T element = enumeration.nextElement(); collection.add(element); } } @NotNull public static > C addAll(@NotNull C collection, @NotNull A... elements) { //noinspection ManualArrayToCollectionCopy for (T element : elements) { collection.add(element); } return collection; } /** * Adds all not-null elements from the {@code elements}, ignoring nulls */ @NotNull public static > C addAllNotNull(@NotNull C collection, @NotNull A... elements) { for (T element : elements) { if (element != null) { collection.add(element); } } return collection; } public static boolean removeAll(@NotNull Collection collection, @NotNull T... elements) { boolean modified = false; for (T element : elements) { modified |= collection.remove(element); } return modified; } // returns true if the collection was modified public static boolean retainAll(@NotNull Collection collection, @NotNull Condition condition) { boolean modified = false; for (Iterator iterator = collection.iterator(); iterator.hasNext(); ) { T next = iterator.next(); if (!condition.value(next)) { iterator.remove(); modified = true; } } return modified; } public static U findInstance(@NotNull Iterable iterable, @NotNull Class aClass) { return findInstance(iterable.iterator(), aClass); } public static U findInstance(@NotNull Iterator iterator, @NotNull Class aClass) { @SuppressWarnings("unchecked") U u = (U)find(iterator, new FilteringIterator.InstanceOf(aClass)); return u; } @Nullable public static U findInstance(@NotNull T[] array, @NotNull Class aClass) { return findInstance(Arrays.asList(array), aClass); } @NotNull public static List concat(@NotNull V[] array, @NotNull Function> fun) { return concat(Arrays.asList(array), fun); } /** * @return read-only list consisting of the elements from the collections stored in list added together */ @NotNull public static List concat(@NotNull Iterable> list) { List result = new ArrayList(); for (final Collection ts : list) { result.addAll(ts); } return result.isEmpty() ? Collections.emptyList() : result; } /** * @param appendTail specify whether additional values should be appended in front or after the list * @return read-only list consisting of the elements from specified list with some additional values */ @NotNull public static List concat(boolean appendTail, @NotNull List list, T... values) { return appendTail ? concat(list, list(values)) : concat(list(values), list); } /** * @return read-only list consisting of the two lists added together */ @NotNull public static List concat(@NotNull final List list1, @NotNull final List list2) { if (list1.isEmpty() && list2.isEmpty()) { return Collections.emptyList(); } final int size1 = list1.size(); final int size = size1 + list2.size(); return new AbstractList() { @Override public T get(int index) { if (index < size1) { return list1.get(index); } return list2.get(index - size1); } @Override public int size() { return size; } }; } @NotNull public static Iterable concat(@NotNull final Iterable... iterables) { return new Iterable() { @Override public Iterator iterator() { Iterator[] iterators = new Iterator[iterables.length]; for (int i = 0; i < iterables.length; i++) { Iterable iterable = iterables[i]; iterators[i] = iterable.iterator(); } @SuppressWarnings("unchecked") Iterator i = concatIterators(iterators); return i; } }; } @NotNull public static Iterator concatIterators(@NotNull Iterator... iterators) { return new SequenceIterator(iterators); } @NotNull public static Iterator concatIterators(@NotNull Collection> iterators) { return new SequenceIterator(iterators); } @NotNull public static Iterable concat(@NotNull final T[]... iterables) { return new Iterable() { @Override public Iterator iterator() { Iterator[] iterators = new Iterator[iterables.length]; for (int i = 0, iterablesLength = iterables.length; i < iterablesLength; i++) { T[] iterable = iterables[i]; iterators[i] = Arrays.asList(iterable).iterator(); } @SuppressWarnings("unchecked") Iterator i = concatIterators(iterators); return i; } }; } /** * @return read-only list consisting of the lists added together */ @NotNull public static List concat(@NotNull final List... lists) { int size = 0; for (List each : lists) { size += each.size(); } if (size == 0) return emptyList(); final int finalSize = size; return new AbstractList() { @Override public T get(final int index) { if (index >= 0 && index < finalSize) { int from = 0; for (List each : lists) { if (from <= index && index < from + each.size()) return each.get(index - from); from += each.size(); } } throw new IndexOutOfBoundsException("index: " + index + "size: " + size()); } @Override public int size() { return finalSize; } }; } /** * @return read-only list consisting of the lists added together */ @NotNull public static List concat(@NotNull final List> lists) { @SuppressWarnings("unchecked") List[] array = lists.toArray(new List[lists.size()]); return concat(array); } /** * @return read-only list consisting of the lists (made by listGenerator) added together */ @NotNull public static List concat(@NotNull Iterable list, @NotNull Function> listGenerator) { List result = new ArrayList(); for (final V v : list) { result.addAll(listGenerator.fun(v)); } return result.isEmpty() ? ContainerUtil.emptyList() : result; } public static boolean intersects(@NotNull Collection collection1, @NotNull Collection collection2) { for (T t : collection1) { //noinspection SuspiciousMethodCalls if (collection2.contains(t)) { return true; } } return false; } /** * @return read-only collection consisting of elements from both collections */ @NotNull public static Collection intersection(@NotNull Collection collection1, @NotNull Collection collection2) { List result = new ArrayList(); for (T t : collection1) { if (collection2.contains(t)) { result.add(t); } } return result.isEmpty() ? ContainerUtil.emptyList() : result; } @Nullable public static T getFirstItem(@Nullable Collection items) { return getFirstItem(items, null); } @Nullable public static T getFirstItem(@Nullable List items) { return items == null || items.isEmpty() ? null : items.get(0); } public static T getFirstItem(@Nullable final Collection items, @Nullable final T def) { return items == null || items.isEmpty() ? def : items.iterator().next(); } /** * The main difference from subList is that getFirstItems does not * throw any exceptions, even if maxItems is greater than size of the list * * @param items list * @param maxItems size of the result will be equal or less than maxItems * @param type of list * @return new list with no more than maxItems first elements */ @NotNull public static List getFirstItems(@NotNull final List items, int maxItems) { return items.subList(0, Math.min(maxItems, items.size())); } @Nullable public static T iterateAndGetLastItem(@NotNull Iterable items) { Iterator itr = items.iterator(); T res = null; while (itr.hasNext()) { res = itr.next(); } return res; } @Nullable public static > T getLastItem(@NotNull L list, @Nullable T def) { return list.isEmpty() ? def : list.get(list.size() - 1); } @Nullable public static > T getLastItem(@NotNull L list) { return getLastItem(list, null); } /** * @return read-only collection consisting of elements from the 'from' collection which are absent from the 'what' collection */ @NotNull public static Collection subtract(@NotNull Collection from, @NotNull Collection what) { final Set set = newHashSet(from); set.removeAll(what); return set.isEmpty() ? ContainerUtil.emptyList() : set; } @NotNull public static T[] toArray(@Nullable Collection c, @NotNull ArrayFactory factory) { return c != null ? c.toArray(factory.create(c.size())) : factory.create(0); } @NotNull public static T[] toArray(@NotNull Collection c1, @NotNull Collection c2, @NotNull ArrayFactory factory) { return ArrayUtil.mergeCollections(c1, c2, factory); } @NotNull public static T[] mergeCollectionsToArray(@NotNull Collection c1, @NotNull Collection c2, @NotNull ArrayFactory factory) { return ArrayUtil.mergeCollections(c1, c2, factory); } public static > void sort(@NotNull List list) { int size = list.size(); if (size < 2) return; if (size == 2) { T t0 = list.get(0); T t1 = list.get(1); if (t0.compareTo(t1) > 0) { list.set(0, t1); list.set(1, t0); } } else if (size < INSERTION_SORT_THRESHOLD) { for (int i = 0; i < size; i++) { for (int j = 0; j < i; j++) { T ti = list.get(i); T tj = list.get(j); if (ti.compareTo(tj) < 0) { list.set(i, tj); list.set(j, ti); } } } } else { Collections.sort(list); } } public static void sort(@NotNull List list, @NotNull Comparator comparator) { int size = list.size(); if (size < 2) return; if (size == 2) { T t0 = list.get(0); T t1 = list.get(1); if (comparator.compare(t0, t1) > 0) { list.set(0, t1); list.set(1, t0); } } else if (size < INSERTION_SORT_THRESHOLD) { for (int i = 0; i < size; i++) { for (int j = 0; j < i; j++) { T ti = list.get(i); T tj = list.get(j); if (comparator.compare(ti, tj) < 0) { list.set(i, tj); list.set(j, ti); } } } } else { Collections.sort(list, comparator); } } public static > void sort(@NotNull T[] a) { int size = a.length; if (size < 2) return; if (size == 2) { T t0 = a[0]; T t1 = a[1]; if (t0.compareTo(t1) > 0) { a[0] = t1; a[1] = t0; } } else if (size < INSERTION_SORT_THRESHOLD) { for (int i = 0; i < size; i++) { for (int j = 0; j < i; j++) { T ti = a[i]; T tj = a[j]; if (ti.compareTo(tj) < 0) { a[i] = tj; a[j] = ti; } } } } else { Arrays.sort(a); } } @NotNull public static List sorted(@NotNull Collection list, @NotNull Comparator comparator) { List sorted = newArrayList(list); sort(sorted, comparator); return sorted; } public static void sort(@NotNull T[] a, @NotNull Comparator comparator) { int size = a.length; if (size < 2) return; if (size == 2) { T t0 = a[0]; T t1 = a[1]; if (comparator.compare(t0, t1) > 0) { a[0] = t1; a[1] = t0; } } else if (size < INSERTION_SORT_THRESHOLD) { for (int i = 0; i < size; i++) { for (int j = 0; j < i; j++) { T ti = a[i]; T tj = a[j]; if (comparator.compare(ti, tj) < 0) { a[i] = tj; a[j] = ti; } } } } else { Arrays.sort(a, comparator); } } /** * @return read-only list consisting of the elements from the iterable converted by mapping */ @NotNull public static List map(@NotNull Iterable iterable, @NotNull Function mapping) { List result = new ArrayList(); for (T t : iterable) { result.add(mapping.fun(t)); } return result.isEmpty() ? ContainerUtil.emptyList() : result; } /** * @return read-only list consisting of the elements from the iterable converted by mapping */ @NotNull public static List map(@NotNull Collection iterable, @NotNull Function mapping) { if (iterable.isEmpty()) return emptyList(); List result = new ArrayList(iterable.size()); for (T t : iterable) { result.add(mapping.fun(t)); } return result; } /** * @return read-only list consisting of the elements from the array converted by mapping with nulls filtered out */ @NotNull public static List mapNotNull(@NotNull T[] array, @NotNull Function mapping) { return mapNotNull(Arrays.asList(array), mapping); } /** * @return read-only list consisting of the elements from the array converted by mapping with nulls filtered out */ @NotNull public static V[] mapNotNull(@NotNull T[] array, @NotNull Function mapping, @NotNull V[] emptyArray) { List result = new ArrayList(array.length); for (T t : array) { V v = mapping.fun(t); if (v != null) { result.add(v); } } if (result.isEmpty()) { assert emptyArray.length == 0 : "You must pass an empty array"; return emptyArray; } return result.toArray(emptyArray); } /** * @return read-only list consisting of the elements from the iterable converted by mapping with nulls filtered out */ @NotNull public static List mapNotNull(@NotNull Iterable iterable, @NotNull Function mapping) { List result = new ArrayList(); for (T t : iterable) { final V o = mapping.fun(t); if (o != null) { result.add(o); } } return result.isEmpty() ? ContainerUtil.emptyList() : result; } /** * @return read-only list consisting of the elements from the array converted by mapping with nulls filtered out */ @NotNull public static List mapNotNull(@NotNull Collection iterable, @NotNull Function mapping) { if (iterable.isEmpty()) { return emptyList(); } List result = new ArrayList(iterable.size()); for (T t : iterable) { final V o = mapping.fun(t); if (o != null) { result.add(o); } } return result.isEmpty() ? ContainerUtil.emptyList() : result; } /** * @return read-only list consisting of the elements with nulls filtered out */ @NotNull public static List packNullables(@NotNull T... elements) { List list = new ArrayList(); for (T element : elements) { addIfNotNull(element, list); } return list.isEmpty() ? ContainerUtil.emptyList() : list; } /** * @return read-only list consisting of the elements from the array converted by mapping */ @NotNull public static List map(@NotNull T[] array, @NotNull Function mapping) { List result = new ArrayList(array.length); for (T t : array) { result.add(mapping.fun(t)); } return result.isEmpty() ? ContainerUtil.emptyList() : result; } @NotNull public static V[] map(@NotNull T[] arr, @NotNull Function mapping, @NotNull V[] emptyArray) { if (arr.length==0) { assert emptyArray.length == 0 : "You must pass an empty array"; return emptyArray; } List result = new ArrayList(arr.length); for (T t : arr) { result.add(mapping.fun(t)); } return result.toArray(emptyArray); } @NotNull public static Set set(@NotNull T ... items) { return newHashSet(items); } public static void putIfNotNull(final K key, @Nullable V value, @NotNull final Map result) { if (value != null) { result.put(key, value); } } public static void add(final T element, @NotNull final Collection result, @NotNull final Disposable parentDisposable) { if (result.add(element)) { Disposer.register(parentDisposable, new Disposable() { @Override public void dispose() { result.remove(element); } }); } } @NotNull public static List createMaybeSingletonList(@Nullable T element) { return element == null ? ContainerUtil.emptyList() : Collections.singletonList(element); } @NotNull public static Set createMaybeSingletonSet(@Nullable T element) { return element == null ? Collections.emptySet() : Collections.singleton(element); } @NotNull public static V getOrCreate(@NotNull Map result, final T key, @NotNull V defaultValue) { V value = result.get(key); if (value == null) { result.put(key, value = defaultValue); } return value; } public static V getOrCreate(@NotNull Map result, final T key, @NotNull Factory factory) { V value = result.get(key); if (value == null) { result.put(key, value = factory.create()); } return value; } @NotNull public static V getOrElse(@NotNull Map result, final T key, @NotNull V defValue) { V value = result.get(key); return value == null ? defValue : value; } public static boolean and(@NotNull T[] iterable, @NotNull Condition condition) { return and(Arrays.asList(iterable), condition); } public static boolean and(@NotNull Iterable iterable, @NotNull Condition condition) { for (final T t : iterable) { if (!condition.value(t)) return false; } return true; } public static boolean exists(@NotNull T[] iterable, @NotNull Condition condition) { return or(Arrays.asList(iterable), condition); } public static boolean exists(@NotNull Iterable iterable, @NotNull Condition condition) { return or(iterable, condition); } public static boolean or(@NotNull T[] iterable, @NotNull Condition condition) { return or(Arrays.asList(iterable), condition); } public static boolean or(@NotNull Iterable iterable, @NotNull Condition condition) { for (final T t : iterable) { if (condition.value(t)) return true; } return false; } @NotNull public static List unfold(@Nullable T t, @NotNull NullableFunction next) { if (t == null) return emptyList(); final ArrayList list = new ArrayList(); while (t != null) { list.add(t); t = next.fun(t); } return list; } @NotNull public static List dropTail(@NotNull List items) { return items.subList(0, items.size() - 1); } @NotNull public static List list(@NotNull T... items) { return Arrays.asList(items); } // Generalized Quick Sort. Does neither array.clone() nor list.toArray() public static void quickSort(@NotNull List list, @NotNull Comparator comparator) { quickSort(list, comparator, 0, list.size()); } private static void quickSort(@NotNull List x, @NotNull Comparator comparator, int off, int len) { // Insertion sort on smallest arrays if (len < 7) { for (int i = off; i < len + off; i++) { for (int j = i; j > off && comparator.compare(x.get(j), x.get(j - 1)) < 0; j--) { swapElements(x, j, j - 1); } } return; } // Choose a partition element, v int m = off + (len >> 1); // Small arrays, middle element if (len > 7) { int l = off; int n = off + len - 1; if (len > 40) { // Big arrays, pseudomedian of 9 int s = len / 8; l = med3(x, comparator, l, l + s, l + 2 * s); m = med3(x, comparator, m - s, m, m + s); n = med3(x, comparator, n - 2 * s, n - s, n); } m = med3(x, comparator, l, m, n); // Mid-size, med of 3 } T v = x.get(m); // Establish Invariant: v* (v)* v* int a = off; int b = a; int c = off + len - 1; int d = c; while (true) { while (b <= c && comparator.compare(x.get(b), v) <= 0) { if (comparator.compare(x.get(b), v) == 0) { swapElements(x, a++, b); } b++; } while (c >= b && comparator.compare(v, x.get(c)) <= 0) { if (comparator.compare(x.get(c), v) == 0) { swapElements(x, c, d--); } c--; } if (b > c) break; swapElements(x, b++, c--); } // Swap partition elements back to middle int n = off + len; int s = Math.min(a - off, b - a); vecswap(x, off, b - s, s); s = Math.min(d - c, n - d - 1); vecswap(x, b, n - s, s); // Recursively sort non-partition-elements if ((s = b - a) > 1) quickSort(x, comparator, off, s); if ((s = d - c) > 1) quickSort(x, comparator, n - s, s); } /* * Returns the index of the median of the three indexed longs. */ private static int med3(@NotNull List x, Comparator comparator, int a, int b, int c) { return comparator.compare(x.get(a), x.get(b)) < 0 ? comparator.compare(x.get(b), x.get(c)) < 0 ? b : comparator.compare(x.get(a), x.get(c)) < 0 ? c : a : comparator.compare(x.get(c), x.get(b)) < 0 ? b : comparator.compare(x.get(c), x.get(a)) < 0 ? c : a; } /* * Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)]. */ private static void vecswap(List x, int a, int b, int n) { for (int i = 0; i < n; i++, a++, b++) { swapElements(x, a, b); } } /** * Merge sorted points, which are sorted by x and with equal x by y. * Result is put to x1 y1. */ public static void mergeSortedArrays(@NotNull TIntArrayList x1, @NotNull TIntArrayList y1, @NotNull TIntArrayList x2, @NotNull TIntArrayList y2) { TIntArrayList newX = new TIntArrayList(); TIntArrayList newY = new TIntArrayList(); int i = 0; int j = 0; while (i < x1.size() && j < x2.size()) { if (x1.get(i) < x2.get(j) || x1.get(i) == x2.get(j) && y1.get(i) < y2.get(j)) { newX.add(x1.get(i)); newY.add(y1.get(i)); i++; } else if (x1.get(i) > x2.get(j) || x1.get(i) == x2.get(j) && y1.get(i) > y2.get(j)) { newX.add(x2.get(j)); newY.add(y2.get(j)); j++; } else { //equals newX.add(x1.get(i)); newY.add(y1.get(i)); i++; j++; } } while (i < x1.size()) { newX.add(x1.get(i)); newY.add(y1.get(i)); i++; } while (j < x2.size()) { newX.add(x2.get(j)); newY.add(y2.get(j)); j++; } x1.clear(); y1.clear(); x1.add(newX.toNativeArray()); y1.add(newY.toNativeArray()); } /** * @return read-only set consisting of the only element o */ @NotNull public static Set singleton(final T o, @NotNull final TObjectHashingStrategy strategy) { return new SingletonSet(o, strategy); } /** * @return read-only list consisting of the elements from all of the collections */ @NotNull public static List flatten(@NotNull Collection[] collections) { return flatten(Arrays.asList(collections)); } /** * @return read-only list consisting of the elements from all of the collections */ @NotNull public static List flatten(@NotNull Iterable> collections) { List result = new ArrayList(); for (Collection list : collections) { result.addAll(list); } return result.isEmpty() ? ContainerUtil.emptyList() : result; } /** * @return read-only list consisting of the elements from all of the collections */ @NotNull public static List flattenIterables(@NotNull Iterable> collections) { List result = new ArrayList(); for (Iterable list : collections) { for (E e : list) { result.add(e); } } return result.isEmpty() ? ContainerUtil.emptyList() : result; } @NotNull public static V[] convert(@NotNull K[] from, @NotNull V[] to, @NotNull Function fun) { if (to.length < from.length) { @SuppressWarnings("unchecked") V[] array = (V[])Array.newInstance(to.getClass().getComponentType(), from.length); to = array; } for (int i = 0; i < from.length; i++) { to[i] = fun.fun(from[i]); } return to; } public static boolean containsIdentity(@NotNull Iterable list, T element) { for (T t : list) { if (t == element) { return true; } } return false; } public static int indexOfIdentity(@NotNull List list, T element) { for (int i = 0, listSize = list.size(); i < listSize; i++) { if (list.get(i) == element) { return i; } } return -1; } public static boolean equalsIdentity(@NotNull List list1, @NotNull List list2) { int listSize = list1.size(); if (list2.size() != listSize) { return false; } for (int i = 0; i < listSize; i++) { if (list1.get(i) != list2.get(i)) { return false; } } return true; } public static int indexOf(@NotNull List list, @NotNull Condition condition) { for (int i = 0, listSize = list.size(); i < listSize; i++) { T t = list.get(i); if (condition.value(t)) { return i; } } return -1; } @NotNull public static Map reverseMap(@NotNull Map map) { final Map result = newHashMap(); for (Map.Entry entry : map.entrySet()) { result.put(entry.getValue(), entry.getKey()); } return result; } public static boolean processRecursively(final T root, @NotNull PairProcessor> processor) { final LinkedList list = new LinkedList(); list.add(root); while (!list.isEmpty()) { final T o = list.removeFirst(); if (!processor.process(o, list)) return false; } return true; } @Nullable public static List trimToSize(@Nullable List list) { if (list == null) return null; if (list.isEmpty()) return emptyList(); if (list instanceof ArrayList) { ((ArrayList)list).trimToSize(); } return list; } @NotNull public static Stack newStack() { return ContainerUtilRt.newStack(); } @NotNull public static Stack newStack(@NotNull Collection initial) { return ContainerUtilRt.newStack(initial); } @NotNull public static Stack newStack(@NotNull T... initial) { return ContainerUtilRt.newStack(initial); } @NotNull public static List emptyList() { return ContainerUtilRt.emptyList(); } @NotNull public static CopyOnWriteArrayList createEmptyCOWList() { return ContainerUtilRt.createEmptyCOWList(); } /** * Creates List which is thread-safe to modify and iterate. * It differs from the java.util.concurrent.CopyOnWriteArrayList in the following: * - faster modification in the uncontended case * - less memory * - slower modification in highly contented case (which is the kind of situation you shouldn't use COWAL anyway) */ @NotNull public static List createLockFreeCopyOnWriteList() { return createConcurrentList(); } @NotNull public static List createLockFreeCopyOnWriteList(@NotNull Collection c) { return new LockFreeCopyOnWriteArrayList(c); } @NotNull public static ConcurrentList createConcurrentList() { return new LockFreeCopyOnWriteArrayList(); } public static void addIfNotNull(@Nullable T element, @NotNull Collection result) { ContainerUtilRt.addIfNotNull(element, result); } public static void addIfNotNull(@NotNull Collection result, @Nullable T element) { ContainerUtilRt.addIfNotNull(result, element); } @NotNull public static List map2List(@NotNull T[] array, @NotNull Function mapper) { return ContainerUtilRt.map2List(array, mapper); } @NotNull public static List map2List(@NotNull Collection collection, @NotNull Function mapper) { return ContainerUtilRt.map2List(collection, mapper); } @NotNull public static Set map2Set(@NotNull T[] collection, @NotNull Function mapper) { return ContainerUtilRt.map2Set(collection, mapper); } @NotNull public static Set map2Set(@NotNull Collection collection, @NotNull Function mapper) { return ContainerUtilRt.map2Set(collection, mapper); } @NotNull public static T[] toArray(@NotNull List collection, @NotNull T[] array) { return ContainerUtilRt.toArray(collection, array); } @NotNull public static T[] toArray(@NotNull Collection c, @NotNull T[] sample) { return ContainerUtilRt.toArray(c, sample); } @NotNull public static T[] copyAndClear(@NotNull Collection collection, @NotNull ArrayFactory factory, boolean clear) { int size = collection.size(); T[] a = factory.create(size); if (size > 0) { a = collection.toArray(a); if (clear) collection.clear(); } return a; } @NotNull public static Collection toCollection(@NotNull Iterable iterable) { return iterable instanceof Collection ? (Collection)iterable : newArrayList(iterable); } @NotNull public static List toList(@NotNull Enumeration enumeration) { if (!enumeration.hasMoreElements()) { return Collections.emptyList(); } List result = new SmartList(); while (enumeration.hasMoreElements()) { result.add(enumeration.nextElement()); } return result; } @Contract("null -> true") public static boolean isEmpty(Collection collection) { return collection == null || collection.isEmpty(); } @NotNull public static > C notNullize(@Nullable C collection) { //noinspection unchecked return collection == null ? (C)ContainerUtilRt.emptyList() : collection; } @Nullable public static > C nullize(@Nullable C collection) { return isEmpty(collection) ? null : collection; } private interface ConcurrentMapFactory { @NotNull ConcurrentMap createMap(); @NotNull ConcurrentMap createMap(int initialCapacity); @NotNull ConcurrentMap createMap(@NotNull TObjectHashingStrategy hashStrategy); @NotNull ConcurrentMap createMap(int initialCapacity, float loadFactor, int concurrencyLevel); @NotNull ConcurrentMap createMap(int initialCapacity, float loadFactor, int concurrencyLevel, @NotNull TObjectHashingStrategy hashStrategy); } private static final ConcurrentMapFactory V8_MAP_FACTORY = new ConcurrentMapFactory() { @NotNull public ConcurrentMap createMap() { return new ConcurrentHashMap(); } @NotNull public ConcurrentMap createMap(int initialCapacity) { return new ConcurrentHashMap(initialCapacity); } @NotNull public ConcurrentMap createMap(@NotNull TObjectHashingStrategy hashStrategy) { return new ConcurrentHashMap(hashStrategy); } @NotNull public ConcurrentMap createMap(int initialCapacity, float loadFactor, int concurrencyLevel) { return new ConcurrentHashMap(initialCapacity, loadFactor, concurrencyLevel); } @NotNull public ConcurrentMap createMap(int initialCapacity, float loadFactor, int concurrencyLevel, @NotNull TObjectHashingStrategy hashingStrategy) { return new ConcurrentHashMap(initialCapacity, loadFactor, concurrencyLevel, hashingStrategy); } }; private static final ConcurrentMapFactory PLATFORM_MAP_FACTORY = new ConcurrentMapFactory() { @NotNull public ConcurrentMap createMap() { return createMap(16, 0.75f, DEFAULT_CONCURRENCY_LEVEL); } @NotNull public ConcurrentMap createMap(int initialCapacity) { return new java.util.concurrent.ConcurrentHashMap(initialCapacity); } @NotNull public ConcurrentMap createMap(@NotNull TObjectHashingStrategy hashingStrategy) { if (hashingStrategy != canonicalStrategy()) { throw new UnsupportedOperationException("Custom hashStrategy is not supported in java.util.concurrent.ConcurrentHashMap"); } // ignoring strategy parameter, because it is not supported by this implementation return createMap(); } @NotNull public ConcurrentMap createMap(int initialCapacity, float loadFactor, int concurrencyLevel) { return new java.util.concurrent.ConcurrentHashMap(initialCapacity, loadFactor, concurrencyLevel); } @NotNull public ConcurrentMap createMap(int initialCapacity, float loadFactor, int concurrencyLevel, @NotNull TObjectHashingStrategy hashingStrategy) { if (hashingStrategy != canonicalStrategy()) { throw new UnsupportedOperationException("Custom hashStrategy is not supported in java.util.concurrent.ConcurrentHashMap"); } // ignoring strategy parameter, because it is not supported by this implementation return createMap(initialCapacity, loadFactor, concurrencyLevel); } }; private static final ConcurrentMapFactory CHM_FACTORY = SystemInfo.isOracleJvm || SystemInfo.isSunJvm || SystemInfo.isAppleJvm || isAtLeastJava7() ? V8_MAP_FACTORY : PLATFORM_MAP_FACTORY; private static boolean isAtLeastJava7() { // IBM JDK provides correct version in java.version property, but not in java.runtime.version property return StringUtil.compareVersionNumbers(SystemInfo.JAVA_VERSION, "1.7") >= 0; } public static > int compareLexicographically(List o1, List o2) { for (int i = 0; i < Math.min(o1.size(), o2.size()); i++) { int result = o1.get(i).compareTo(o2.get(i)); if (result != 0) { return result; } } return o1.size() < o2.size() ? -1 : o1.size() == o2.size() ? 0 : 1; } }