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

   1 /*
   2  * Copyright 2000-2009 JetBrains s.r.o.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  * http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16 package com.intellij.util.containers;
  17
  18 import com.intellij.openapi.Disposable;
  19 import com.intellij.openapi.util.Condition;
  20 import com.intellij.openapi.util.Disposer;
  21 import com.intellij.openapi.util.Factory;
  22 import com.intellij.util.*;
  23 import gnu.trove.TObjectHashingStrategy;
  24 import org.jetbrains.annotations.NotNull;
  25 import org.jetbrains.annotations.Nullable;
  26
  27 import java.io.Serializable;
  28 import java.lang.reflect.Array;
  29 import java.util.*;
  30 import java.util.concurrent.CopyOnWriteArrayList;
  31
  32 public class ContainerUtil {
  33   public static List<Object> mergeSortedLists(List<Object> list1, List<Object> list2, Comparator<Object> comparator, boolean mergeEqualItems){
  34     ArrayList<Object> result = new ArrayList<Object>();
  35
  36     int index1 = 0;
  37     int index2 = 0;
  38     while(index1 < list1.size() || index2 < list2.size()){
  39       if (index1 >= list1.size()){
  40         result.add(list2.get(index2++));
  41       }
  42       else if (index2 >= list2.size()){
  43         result.add(list1.get(index1++));
  44       }
  45       else{
  46         Object element1 = list1.get(index1);
  47         Object element2 = list2.get(index2);
  48         int c = comparator.compare(element1,  element2);
  49         if (c < 0){
  50           result.add(element1);
  51           index1++;
  52         }
  53         else if (c > 0){
  54           result.add(element2);
  55           index2++;
  56         }
  57         else{
  58           result.add(element1);
  59           if (!mergeEqualItems){
  60             result.add(element2);
  61           }
  62           index1++;
  63           index2++;
  64         }
  65       }
  66     }
  67
  68     return result;
  69   }
  70
  71   public static <T> void addAll(Collection<T> collection, Iterator<T> iterator) {
  72     while (iterator.hasNext()) {
  73       T o = iterator.next();
  74       collection.add(o);
  75     }
  76   }
  77
  78   public static <T> ArrayList<T> collect(Iterator<T> iterator) {
  79     ArrayList<T> list = new ArrayList<T>();
  80     addAll(list, iterator);
  81     return list;
  82   }
  83
  84   public static <T> HashSet<T> collectSet(Iterator<T> iterator) {
  85     HashSet<T> hashSet = new HashSet<T>();
  86     addAll(hashSet, iterator);
  87     return hashSet;
  88   }
  89
  90   public static <K,V> HashMap<K, V> assignKeys(Iterator<V> iterator, Convertor<V, K> keyConvertor) {
  91     HashMap<K, V> hashMap = new HashMap<K, V>();
  92     while (iterator.hasNext()) {
  93       V value = iterator.next();
  94       hashMap.put(keyConvertor.convert(value), value);
  95     }
  96     return hashMap;
  97   }
  98
  99   public static <K,V> HashMap<K, Set<V>> classify(Iterator<V> iterator, Convertor<V, K> keyConvertor) {
 100     HashMap<K, Set<V>> hashMap = new HashMap<K, Set<V>>();
 101     while (iterator.hasNext()) {
 102       V value = iterator.next();
 103       final K key = keyConvertor.convert(value);
 104       Set<V> set = hashMap.get(key);
 105       if (set == null) {
 106         hashMap.put(key, set = new LinkedHashSet<V>()); // ordered set!!
 107       }
 108       set.add(value);
 109     }
 110     return hashMap;
 111   }
 112
 113   public static <K, V> HashMap<K, V> assignValues(Iterator<K> iterator, Convertor<K, V> valueConvertor) {
 114     HashMap<K, V> hashMap = new HashMap<K, V>();
 115     while (iterator.hasNext()) {
 116       K key = iterator.next();
 117       hashMap.put(key, valueConvertor.convert(key));
 118     }
 119     return hashMap;
 120   }
 121
 122   public static <T> Iterator<T> emptyIterator() {
 123     return EmptyIterator.getInstance();
 124   }
 125
 126   public static <T> Iterable<T> emptyIterable() {
 127     return EmptyIterable.getInstance();
 128   }
 129
 130   @Nullable
 131   public static <T> T find(T[] array, Condition<T> condition) {
 132     for (T element : array) {
 133       if (condition.value(element)) return element;
 134     }
 135     return null;
 136   }
 137
 138   public static <T> boolean process(Iterable<? extends T> iterable, Processor<T> processor) {
 139     for (final T t : iterable) {
 140       if (!processor.process(t)) {
 141         return false;
 142       }
 143     }
 144     return true;
 145   }
 146
 147   public static <T> boolean process(T[] iterable, Processor<? super T> processor) {
 148     for (final T t : iterable) {
 149       if (!processor.process(t)) {
 150         return false;
 151       }
 152     }
 153     return true;
 154   }
 155
 156   @Nullable
 157   public static <T,V extends T> V find(Iterable<V> iterable, Condition<T> condition) {
 158     return find(iterable.iterator(), condition);
 159   }
 160
 161   @Nullable
 162   public static <T> T find(Iterable<? extends T> iterable, final T equalTo) {
 163     return find(iterable, new Condition<T>() {
 164       public boolean value(final T object) {
 165         return equalTo == object || equalTo.equals(object);
 166       }
 167     });
 168   }
 169
 170   @Nullable
 171   public static <T,V extends T> V find(Iterator<V> iterator, Condition<T> condition) {
 172     while (iterator.hasNext()) {
 173       V value = iterator.next();
 174       if (condition.value(value)) return value;
 175     }
 176     return null;
 177   }
 178
 179   public static <T,V> List<V> map2List(T[] array, Function<T,V> mapper) {
 180     return map2List(Arrays.asList(array), mapper);
 181   }
 182
 183   public static <T,V> List<V> map2List(Collection<? extends T> collection, Function<T,V> mapper) {
 184     final ArrayList<V> list = new ArrayList<V>(collection.size());
 185     for (final T t : collection) {
 186       list.add(mapper.fun(t));
 187     }
 188     return list;
 189   }
 190
 191   public static <T,V> Set<V> map2Set(T[] collection, Function<T,V> mapper) {
 192     return map2Set(Arrays.asList(collection), mapper);
 193   }
 194
 195   public static <T,V> Set<V> map2Set(Collection<? extends T> collection, Function<T,V> mapper) {
 196     final HashSet<V> set = new HashSet<V>(collection.size());
 197     for (final T t : collection) {
 198       set.add(mapper.fun(t));
 199     }
 200     return set;
 201   }
 202
 203   public static <T> Object[] map2Array(T[] array, Function<T,Object> mapper) {
 204     return map2Array(array, Object.class, mapper);
 205   }
 206
 207   public static <T> Object[] map2Array(Collection<T> array, Function<T,Object> mapper) {
 208     return map2Array(array, Object.class, mapper);
 209   }
 210
 211   public static <T,V> V[] map2Array(T[] array, Class<? extends V> aClass, Function<T,V> mapper) {
 212     return map2Array(Arrays.asList(array), aClass, mapper);
 213   }
 214
 215   public static <T,V> V[] map2Array(Collection<? extends T> collection, Class<? extends V> aClass, Function<T,V> mapper) {
 216     final List<V> list = map2List(collection, mapper);
 217     return list.toArray((V[])Array.newInstance(aClass, list.size()));
 218   }
 219
 220   public static <T,V> V[] map2Array(Collection<? extends T> collection, V[] to, Function<T,V> mapper) {
 221     return map2List(collection, mapper).toArray(to);
 222   }
 223
 224   public static <T> List<T> findAll(T[] collection, Condition<? super T> condition) {
 225     return findAll(Arrays.asList(collection), condition);
 226   }
 227
 228   public static <T> List<T> findAll(Collection<? extends T> collection, Condition<? super T> condition) {
 229     final ArrayList<T> result = new ArrayList<T>();
 230     for (final T t : collection) {
 231       if (condition.value(t)) {
 232         result.add(t);
 233       }
 234     }
 235     return result;
 236   }
 237
 238   public static <T> List<T> skipNulls (Collection<? extends T> collection) {
 239     return findAll(collection, Condition.NOT_NULL);
 240   }
 241
 242   public static <T,V> List<V> findAll(T[] collection, Class<V> instanceOf) {
 243     return findAll(Arrays.asList(collection), instanceOf);
 244   }
 245
 246   public static <T,V> V[] findAllAsArray(T[] collection, Class<V> instanceOf) {
 247     List<V> list = findAll(Arrays.asList(collection), instanceOf);
 248     return list.toArray((V[])Array.newInstance(instanceOf, list.size()));
 249   }
 250
 251   public static <T,V> V[] findAllAsArray(Collection<? extends T> collection, Class<V> instanceOf) {
 252     List<V> list = findAll(collection, instanceOf);
 253     return list.toArray((V[])Array.newInstance(instanceOf, list.size()));
 254   }
 255
 256   public static <T> T[] findAllAsArray(T[] collection, Condition<? super T> instanceOf) {
 257     List<T> list = findAll(collection, instanceOf);
 258     return list.toArray((T[])Array.newInstance(collection.getClass().getComponentType(), list.size()));
 259   }
 260
 261   public static <T,V> List<V> findAll(Collection<? extends T> collection, Class<V> instanceOf) {
 262     final ArrayList<V> result = new ArrayList<V>();
 263     for (final T t : collection) {
 264       if (instanceOf.isInstance(t)) {
 265         result.add((V)t);
 266       }
 267     }
 268     return result;
 269   }
 270
 271   public static <T> void removeDuplicates(Collection<T> collection) {
 272     Set<T> collected = new HashSet<T>();
 273     for (Iterator<T> iterator = collection.iterator(); iterator.hasNext();) {
 274       T t = iterator.next();
 275       if (!collected.contains(t)) {
 276         collected.add(t);
 277       }
 278       else {
 279         iterator.remove();
 280       }
 281     }
 282   }
 283
 284   public static <T> Iterator<T> iterate(T[] arrays) {
 285     return Arrays.asList(arrays).iterator();
 286   }
 287
 288   public static <T> Iterator<T> iterate(final Enumeration<T> enumeration) {
 289     return new Iterator<T>() {
 290       public boolean hasNext() {
 291         return enumeration.hasMoreElements();
 292       }
 293
 294       public T next() {
 295         return enumeration.nextElement();
 296       }
 297
 298       public void remove() {
 299         throw new UnsupportedOperationException();
 300       }
 301     };
 302   }
 303
 304   public static <T> Iterable<T> iterate(T[] arrays, final Condition<? super T> condition) {
 305     return iterate(Arrays.asList(arrays), condition);
 306   }
 307
 308   public static <T> Iterable<T> iterate(final Collection<? extends T> collection, final Condition<? super T> condition) {
 309     if (collection.isEmpty()) return emptyIterable();
 310     return new Iterable<T>() {
 311       public Iterator<T> iterator() {
 312         return new Iterator<T>() {
 313           Iterator<? extends T> impl = collection.iterator();
 314           T next = findNext();
 315
 316           public boolean hasNext() {
 317             return next != null;
 318           }
 319
 320           public T next() {
 321             T result = next;
 322             next = findNext();
 323             return result;
 324           }
 325
 326           private T findNext() {
 327             while (impl.hasNext()) {
 328               T each = impl.next();
 329               if (condition.value(each)) {
 330                 return each;
 331               }
 332             }
 333             return null;
 334           }
 335
 336           public void remove() {
 337             throw new UnsupportedOperationException();
 338           }
 339         };
 340       }
 341     };
 342   }
 343
 344   public static <E> void swapElements(final List<E> list, final int index1, final int index2) {
 345     E e1 = list.get(index1);
 346     E e2 = list.get(index2);
 347     list.set(index1, e2);
 348     list.set(index2, e1);
 349   }
 350
 351   public static <T> ArrayList<T> collect(Iterator<?> iterator, FilteringIterator.InstanceOf<T> instanceOf) {
 352     return collect(FilteringIterator.create(iterator, instanceOf));
 353   }
 354
 355   public static <T> void addAll(Collection<T> collection, Enumeration<T> enumeration) {
 356     while (enumeration.hasMoreElements()) {
 357       T element = enumeration.nextElement();
 358       collection.add(element);
 359     }
 360   }
 361
 362   public static <T, U extends T> U findInstance(Iterable<T> iterable, Class<U> aClass) {
 363     return findInstance(iterable.iterator(), aClass);
 364   }
 365
 366   public static <T, U extends T> U findInstance(Iterator<T> iterator, Class<U> aClass) {
 367     // uncomment for 1.5
 368     //return (U)find(iterator, new FilteringIterator.InstanceOf<U>(aClass));
 369     return (U)find(iterator, new FilteringIterator.InstanceOf<T>((Class<T>)aClass));
 370   }
 371
 372   @Nullable
 373   public static <T, U extends T> U findInstance(T[] array, Class<U> aClass) {
 374     return findInstance(Arrays.asList(array), aClass);
 375   }
 376
 377   public static <T,V> List<T> concat(V[] array, Function<V,Collection<? extends T>> fun) {
 378     return concat(Arrays.asList(array), fun);
 379   }
 380
 381   public static <T> List<T> concat(Iterable<? extends Collection<T>> list) {
 382     final ArrayList<T> result = new ArrayList<T>();
 383     for (final Collection<T> ts : list) {
 384       result.addAll(ts);
 385     }
 386     return result;
 387   }
 388
 389   public static <T> List<T> concat(@NotNull final List<? extends T> list1, @NotNull final List<? extends T> list2) {
 390     return concat(new List[]{list1, list2});
 391   }
 392
 393   public static <T> List<T> concat(@NotNull final List<? extends T>... lists) {
 394     int size = 0;
 395     for (List<? extends T> each : lists) {
 396       size += each.size();
 397     }
 398     final int finalSize = size;
 399     return new AbstractList<T>() {
 400       public T get(final int index) {
 401         if (index >= 0 && index < finalSize) {
 402           int from = 0;
 403           for (List<? extends T> each : lists) {
 404             if (from <= index && index < from + each.size()) return each.get(index - from);
 405             from += each.size();
 406           }
 407         }
 408         throw new IndexOutOfBoundsException("index: " + index + "size: " + size());
 409       }
 410
 411       public int size() {
 412         return finalSize;
 413       }
 414     };
 415   }
 416
 417   public static <T,V> List<T> concat(Iterable<? extends V> list, Function<V,Collection<? extends T>> fun) {
 418     final ArrayList<T> result = new ArrayList<T>();
 419     for (final V v : list) {
 420       result.addAll(fun.fun(v));
 421     }
 422     return result;
 423   }
 424
 425   public static <T> boolean intersects(Collection<? extends T> collection1, Collection<? extends T> collection2) {
 426     for (T t : collection1) {
 427       //noinspection SuspiciousMethodCalls
 428       if (collection2.contains(t)) {
 429         return true;
 430       }
 431     }
 432     return false;
 433   }
 434
 435   public static <T> T getFirstItem(final Collection<T> items, final T def) {
 436     return items == null || items.isEmpty()? def : items.iterator().next();
 437   }
 438
 439   public static <T> Collection<T> subtract(Collection<T> from, Collection<T> what) {
 440     final HashSet<T> set = new HashSet<T>(from);
 441     set.removeAll(what);
 442     return set;
 443   }
 444
 445   public static <T> T[] toArray(List<T> collection, T[] array){
 446     final int length = array.length;
 447     if (length < 20) {
 448       for (int i = 0; i < collection.size(); i++) {
 449         array[i] = collection.get(i);
 450       }
 451       return array;
 452     }
 453     else {
 454       return collection.toArray(array);
 455     }
 456   }
 457
 458   public static <T,V> List<V> map(Iterable<? extends T> iterable, Function<T, V> mapping) {
 459     List<V> result = new ArrayList<V>();
 460     for (T t : iterable) {
 461       result.add(mapping.fun(t));
 462     }
 463     return result;
 464   }
 465
 466   public static <T,V> List<V> mapNotNull(T[] array, Function<T, V> mapping) {
 467     return mapNotNull(Arrays.asList(array), mapping);
 468   }
 469
 470   public static <T,V> List<V> mapNotNull(Iterable<? extends T> iterable, Function<T, V> mapping) {
 471     List<V> result = new ArrayList<V>();
 472     for (T t : iterable) {
 473       final V o = mapping.fun(t);
 474       if (o != null) {
 475         result.add(o);
 476       }
 477     }
 478     return result;
 479   }
 480
 481   public static <T> List<T> packNullables(T... elements) {
 482     ArrayList<T> list = new ArrayList<T>();
 483     for (T element : elements) {
 484       addIfNotNull(element, list);
 485     }
 486     return list;
 487   }
 488
 489   public static <T,V> List<V> map(T[] arr, Function<T, V> mapping) {
 490     List<V> result = new ArrayList<V>();
 491     for (T t : arr) {
 492       result.add(mapping.fun(t));
 493     }
 494     return result;
 495   }
 496
 497   public static <T,V> V[] map(T[] arr, Function<T, V> mapping, V[] emptyArray) {
 498     List<V> result = new ArrayList<V>();
 499     for (T t : arr) {
 500       result.add(mapping.fun(t));
 501     }
 502     return result.toArray(emptyArray);
 503   }
 504
 505   public static <T> void addIfNotNull(final T element, final Collection<T> result) {
 506     if (element != null) {
 507       result.add(element);
 508     }
 509   }
 510
 511   public static <K, V> void putIfNotNull(final K key, final V value, final Map<K, V> result) {
 512     if (value != null) {
 513       result.put(key, value);
 514     }
 515   }
 516
 517   public static <T> void add(final T element, final Collection<T> result, final Disposable parentDisposable) {
 518     if (result.add(element)) {
 519       Disposer.register(parentDisposable, new Disposable() {
 520         public void dispose() {
 521           result.remove(element);
 522         }
 523       });
 524     }
 525   }
 526
 527   public static <T> List<T> createMaybeSingletonList(@Nullable T element) {
 528     return element == null ? Collections.<T>emptyList() : Arrays.asList(element);
 529   }
 530
 531   public static <T,V> V getOrCreate(final Map<T, V> result, final T key, final V defaultValue) {
 532     V value = result.get(key);
 533     if (value == null) {
 534       result.put(key, value = defaultValue);
 535     }
 536     return value;
 537   }
 538
 539   public static <T,V> V getOrCreate(final Map<T, V> result, final T key, final Factory<V> factory) {
 540     V value = result.get(key);
 541     if (value == null) {
 542       result.put(key, value = factory.create());
 543     }
 544     return value;
 545   }
 546
 547   public static <T> boolean and(T[] iterable, Condition<T> condition) {
 548     return and(Arrays.asList(iterable), condition);
 549   }
 550
 551   public static <T> boolean and(Iterable<T> iterable, Condition<T> condition) {
 552     for (final T t : iterable) {
 553       if (!condition.value(t)) return false;
 554     }
 555     return true;
 556   }
 557
 558   public static <T> boolean or(T[] iterable, Condition<T> condition) {
 559     return or(Arrays.asList(iterable), condition);
 560   }
 561
 562   public static <T> boolean or(Iterable<T> iterable, Condition<T> condition) {
 563     for (final T t : iterable) {
 564       if (condition.value(t)) return true;
 565     }
 566     return false;
 567   }
 568
 569   public static <T> List<T> unfold(@Nullable T t, @NotNull NullableFunction<T,T> next) {
 570     if (t == null) return Collections.emptyList();
 571
 572     final ArrayList<T> list = new ArrayList<T>();
 573     while (t != null) {
 574       list.add(t);
 575       t = next.fun(t);
 576     }
 577     return list;
 578   }
 579
 580   public static <T> List<T> dropTail(List<T> items) {
 581     return items.subList(0, items.size()-1);
 582   }
 583
 584   public static <T> List<T> list(T... items) {
 585     return Arrays.asList(items);
 586   }
 587
 588   // Generalized Quick Sort. Does neither array.clone() nor list.toArray()
 589   public static <T> void quickSort(List<T> list, Comparator<? super T> comparator) {
 590     quickSort(list, comparator, 0, list.size());
 591   }
 592
 593   private static <T> void quickSort(List<T> x, Comparator<? super T> comparator, int off, int len) {
 594     // Insertion sort on smallest arrays
 595     if (len < 7) {
 596       for (int i = off; i < len + off; i++) {
 597         for (int j = i; j > off && comparator.compare(x.get(j), x.get(j - 1)) < 0; j--) {
 598           swapElements(x, j, j - 1);
 599         }
 600       }
 601       return;
 602     }
 603
 604     // Choose a partition element, v
 605     int m = off + (len >> 1);       // Small arrays, middle element
 606     if (len > 7) {
 607       int l = off;
 608       int n = off + len - 1;
 609       if (len > 40) {        // Big arrays, pseudomedian of 9
 610         int s = len / 8;
 611         l = med3(x, comparator, l, l + s, l + 2 * s);
 612         m = med3(x, comparator, m - s, m, m + s);
 613         n = med3(x, comparator, n - 2 * s, n - s, n);
 614       }
 615       m = med3(x, comparator, l, m, n); // Mid-size, med of 3
 616     }
 617     T v = x.get(m);
 618
 619     // Establish Invariant: v* (<v)* (>v)* v*
 620     int a = off;
 621     int b = a;
 622     int c = off + len - 1;
 623     int d = c;
 624     while (true) {
 625       while (b <= c && comparator.compare(x.get(b), v) <= 0) {
 626         if (comparator.compare(x.get(b), v) == 0) {
 627           swapElements(x, a++, b);
 628         }
 629         b++;
 630       }
 631       while (c >= b && comparator.compare(v, x.get(c)) <= 0) {
 632         if (comparator.compare(x.get(c), v) == 0) {
 633           swapElements(x, c, d--);
 634         }
 635         c--;
 636       }
 637       if (b > c) break;
 638       swapElements(x, b++, c--);
 639     }
 640
 641     // Swap partition elements back to middle
 642     int n = off + len;
 643     int s = Math.min(a - off, b - a);
 644     vecswap(x, off, b - s, s);
 645     s = Math.min(d - c, n - d - 1);
 646     vecswap(x, b, n - s, s);
 647
 648     // Recursively sort non-partition-elements
 649     if ((s = b - a) > 1) quickSort(x, comparator, off, s);
 650     if ((s = d - c) > 1) quickSort(x, comparator, n - s, s);
 651   }
 652
 653   /**
 654    * Returns the index of the median of the three indexed longs.
 655    */
 656   private static <T> int med3(List<T> x, Comparator<? super T> comparator, int a, int b, int c) {
 657     return comparator.compare(x.get(a), x.get(b)) < 0 ? comparator.compare(x.get(b), x.get(c)) < 0
 658                                                         ? b
 659                                                         : comparator.compare(x.get(a), x.get(c)) < 0 ? c : a
 660                                                       : comparator.compare(x.get(c), x.get(b)) < 0
 661                                                         ? b
 662                                                         : comparator.compare(x.get(c), x.get(a)) < 0 ? c : a;
 663   }
 664
 665   /**
 666    * Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)].
 667    */
 668   private static <T> void vecswap(List<T> x, int a, int b, int n) {
 669     for (int i = 0; i < n; i++, a++, b++) {
 670       swapElements(x, a, b);
 671     }
 672   }
 673
 674   public static <T> CopyOnWriteArrayList<T> createEmptyCOWList() {
 675     // does not create garbage new Object[0]
 676     return new CopyOnWriteArrayList<T>(ContainerUtil.<T>emptyList());
 677   }
 678
 679   public static <T> List<T> emptyList() {
 680     return (List<T>)EmptyList.INSTANCE;
 681   }
 682
 683   private static class EmptyList extends AbstractList<Object> implements RandomAccess, Serializable {
 684     private static final EmptyList INSTANCE = new EmptyList();
 685     public int size() {
 686       return 0;
 687     }
 688
 689     public boolean contains(Object obj) {
 690       return false;
 691     }
 692
 693     public Object get(int index) {
 694       throw new IndexOutOfBoundsException("Index: " + index);
 695     }
 696
 697     @Override
 698     public Object[] toArray() {
 699       return ArrayUtil.EMPTY_OBJECT_ARRAY;
 700     }
 701
 702     @Override
 703     public <T> T[] toArray(T[] a) {
 704       return a;
 705     }
 706   }
 707
 708   @NotNull
 709   public static <T> Set<T> singleton(final T o, @NotNull final TObjectHashingStrategy<T> strategy) {
 710     return new Set<T>() {
 711       public int size() {
 712         return 1;
 713       }
 714
 715       public boolean isEmpty() {
 716         return false;
 717       }
 718
 719       public boolean contains(Object elem) {
 720         return strategy.equals(o, (T)elem);
 721       }
 722
 723       public Iterator<T> iterator() {
 724         return new Iterator<T>() {
 725           boolean atEnd;
 726           public boolean hasNext() {
 727             return !atEnd;
 728           }
 729
 730           public T next() {
 731             if (atEnd) throw new NoSuchElementException();
 732             atEnd = true;
 733             return o;
 734           }
 735
 736           public void remove() {
 737             throw new IncorrectOperationException();
 738           }
 739         };
 740       }
 741
 742       public Object[] toArray() {
 743         return new Object[]{o};
 744       }
 745
 746       public <T> T[] toArray(T[] a) {
 747         assert a.length == 1;
 748         a[0] = (T)o;
 749         return a;
 750       }
 751
 752       public boolean add(T t) {
 753         throw new IncorrectOperationException();
 754       }
 755
 756       public boolean remove(Object o) {
 757         throw new IncorrectOperationException();
 758       }
 759
 760       public boolean containsAll(Collection<?> c) {
 761         return false;
 762       }
 763
 764       public boolean addAll(Collection<? extends T> c) {
 765         throw new IncorrectOperationException();
 766       }
 767
 768       public boolean retainAll(Collection<?> c) {
 769         throw new IncorrectOperationException();
 770       }
 771
 772       public boolean removeAll(Collection<?> c) {
 773         throw new IncorrectOperationException();
 774       }
 775
 776       public void clear() {
 777         throw new IncorrectOperationException();
 778       }
 779     };
 780   }
 781 }