platform/util/src/com/intellij/util/containers/ContainerUtil.java

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