KezvhLib/src-lib/net/kezvh/collections/CollectionsUtilities.java

   1 package net.kezvh.collections;
   2
   3 import java.lang.reflect.Array;
   4 import java.lang.reflect.InvocationTargetException;
   5 import java.lang.reflect.Method;
   6 import java.util.AbstractSet;
   7 import java.util.ArrayList;
   8 import java.util.Arrays;
   9 import java.util.Collection;
  10 import java.util.Collections;
  11 import java.util.Comparator;
  12 import java.util.Iterator;
  13 import java.util.List;
  14 import java.util.Map;
  15 import java.util.NoSuchElementException;
  16 import java.util.Set;
  17 import java.util.SortedSet;
  18 import java.util.TreeSet;
  19
  20 import net.kezvh.functional.lambda.EquivalenceRelation;
  21 import net.kezvh.functional.lambda.L1;
  22 import net.kezvh.functional.lambda.Predicate1;
  23 import net.kezvh.math.KezvhMath;
  24 import net.kezvh.patterns.AbstractFactory;
  25 import net.kezvh.patterns.AbstractFactory.CreationFailedException;
  26
  27 /**
  28  * @author afflux
  29  */
  30 public final class CollectionsUtilities {
  31         private static final String COULD_NOT_CONSTRUCT_DEFAULT_VALUE = "Could not construct default value";
  32
  33         private static final class ConditionalIterator<T> implements Iterator<T> {
  34                 private final Iterator<T> iterator;
  35                 private final Predicate1<T> condition;
  36                 private boolean notEmpty = false;
  37                 private T current;
  38
  39                 public ConditionalIterator(final Iterator<T> iterator, final Predicate1<T> condition) {
  40                         this.iterator = iterator;
  41                         this.condition = condition;
  42                         this.advance();
  43                 }
  44
  45                 private void advance() {
  46                         this.notEmpty = false;
  47                         while (this.iterator.hasNext() && !this.notEmpty) {
  48                                 this.current = this.iterator.next();
  49                                 this.notEmpty = this.condition.op(this.current);
  50                         }
  51                 }
  52
  53                 public boolean hasNext() {
  54                         return this.notEmpty;
  55                 }
  56
  57                 public T next() {
  58                         if (!this.hasNext())
  59                                 throw new NoSuchElementException();
  60
  61                         try {
  62                                 return this.current;
  63                         } finally {
  64                                 this.advance();
  65                         }
  66                 }
  67
  68                 public void remove() {
  69                         throw new UnsupportedOperationException();
  70                 }
  71         }
  72
  73         private static final class ConditionalSet<T> extends AbstractSet<T> {
  74                 private final Set<T> set;
  75                 private final Predicate1<T> condition;
  76
  77                 public ConditionalSet(final Set<T> set, final Predicate1<T> condition) {
  78                         this.set = set;
  79                         this.condition = condition;
  80                 }
  81
  82                 @Override
  83                 public int size() {
  84                         return CollectionsUtilities.count(this.iterator());
  85                 }
  86
  87                 @Override
  88                 public Iterator<T> iterator() {
  89                         return new ConditionalIterator<T>(this.set.iterator(), this.condition);
  90                 }
  91         }
  92
  93         private static class ConcatenatedIterator<T> implements Iterator<T> {
  94                 private final Iterator<T>[] iterators;
  95                 private int index = 0;
  96
  97                 public ConcatenatedIterator(final Iterator<T>[] iterators) {
  98                         this.iterators = Arrays.copyOf(iterators, iterators.length);
  99                 }
 100
 101                 public boolean hasNext() {
 102                         return this.index != this.iterators.length && this.iterators[this.index].hasNext();
 103                 }
 104
 105                 public T next() {
 106                         while (!this.iterators[this.index].hasNext()) {
 107                                 this.index++;
 108
 109                                 if (this.index == this.iterators.length)
 110                                         throw new NoSuchElementException();
 111                         }
 112
 113                         return this.iterators[this.index].next();
 114                 }
 115
 116                 public void remove() {
 117                         this.iterators[this.index].remove();
 118                 }
 119         }
 120
 121         /**
 122          * @param <T> COMMENT
 123          * @param iterator COMMENT
 124          * @return COMMENT
 125          */
 126         public static <T> int count(final Iterator<T> iterator) {
 127                 int count = 0;
 128                 while (iterator.hasNext()) {
 129                         iterator.next();
 130                         count++;
 131                 }
 132                 return count;
 133         }
 134
 135         /**
 136          * @param <T> COMMENT
 137          * @param start COMMENT
 138          * @param end COMMENT
 139          * @param incrementer COMMENT
 140          * @return COMMENT
 141          */
 142         public static <T extends Comparable<T>> List<T> range(final T start, final T end, final L1<T, T> incrementer) {
 143                 final List<T> range = new ArrayList<T>();
 144                 T current = start;
 145                 while (current.compareTo(end) < 0) {
 146                         range.add(current);
 147                         current = incrementer.op(current);
 148                 }
 149                 return Collections.unmodifiableList(range);
 150         }
 151
 152         /**
 153          * @param <T> COMMENT
 154          * @param iterators COMMENT
 155          * @return COMMENT
 156          */
 157         public static <T> Iterator<T> concatenate(final Iterator<T>[] iterators) {
 158                 return new ConcatenatedIterator<T>(iterators);
 159         }
 160
 161         /**
 162          * @param <T> COMMENT
 163          * @param iterators COMMENT
 164          * @return COMMENT
 165          */
 166         public static <T> Iterator<T> concatenate(final Collection<Iterator<T>> iterators) {
 167                 final Iterator<T>[] array = (Iterator<T>[]) Array.newInstance(iterators.iterator().next().getClass(), iterators.size());
 168                 return CollectionsUtilities.concatenate(array);
 169         }
 170
 171         /**
 172          * @param <T> COMMENT
 173          * @param c COMMENT
 174          * @param toAdd COMMENT
 175          * @return COMMENT
 176          */
 177         public static <T> boolean addAll(final Collection<T> c, final T[] toAdd) {
 178                 return c.addAll(Arrays.asList(toAdd));
 179         }
 180
 181         /**
 182          * @param <T> COMMENT
 183          * @param collection COMMENT
 184          * @param condition COMMENT
 185          * @return COMMENT
 186          */
 187         // //////////////////////////////////////
 188         public static <T> List<T> match(final List<T> collection, final Predicate1<T> condition) {
 189                 List<T> matches;
 190                 try {
 191                         matches = collection.getClass().newInstance();
 192                 } catch (final Exception e) {
 193                         matches = new ArrayList<T>();
 194                 }
 195                 for (final T o : collection)
 196                         if (condition.op(o))
 197                                 matches.add(o);
 198
 199                 return matches;
 200         }
 201
 202         /**
 203          * @param <T> COMMENT
 204          * @param iterator COMMENT
 205          * @param condition COMMENT
 206          * @return COMMENT
 207          */
 208         public static <T> Iterator<T> matchView(final Iterator<T> iterator, final Predicate1<T> condition) {
 209                 return new ConditionalIterator<T>(iterator, condition);
 210         }
 211
 212         /**
 213          * @param <T> COMMENT
 214          * @param set COMMENT
 215          * @param condition COMMENT
 216          * @return COMMENT
 217          */
 218         public static <T> Set<T> matchView(final Set<T> set, final Predicate1<T> condition) {
 219                 return new ConditionalSet<T>(set, condition);
 220         }
 221
 222         // //////////
 223         /**
 224          * @param <K> COMMENT
 225          * @param <V> COMMENT
 226          * @param map COMMENT
 227          * @param key COMMENT
 228          * @param defaultValueClass COMMENT
 229          * @return COMMENT
 230          * @throws InstantiationException COMMENT
 231          * @throws IllegalAccessException COMMENT
 232          */
 233         public static <K, V> V ensureContainsKey(final Map<K, V> map, final K key, final Class<V> defaultValueClass) throws InstantiationException, IllegalAccessException {
 234                 if (map.containsKey(key))
 235                         return map.get(key);
 236                 V defaultValue;
 237
 238                 defaultValue = defaultValueClass.newInstance();
 239
 240                 map.put(key, defaultValue);
 241                 return defaultValue;
 242         }
 243
 244         /**
 245          * @param <K> COMMENT
 246          * @param <V> COMMENT
 247          * @param map COMMENT
 248          * @param key COMMENT
 249          * @param clonableDefaultValue COMMENT
 250          * @return COMMENT
 251          * @throws NoSuchMethodException COMMENT
 252          * @throws InvocationTargetException COMMENT
 253          * @throws IllegalAccessException COMMENT
 254          */
 255         public static <K, V> V ensureContainsKey(final Map<K, V> map, final K key, final Cloneable clonableDefaultValue) throws NoSuchMethodException, InvocationTargetException, IllegalAccessException {
 256                 if (map.containsKey(key))
 257                         return map.get(key);
 258                 V defaultValue;
 259
 260                 final Method cloneMethod = clonableDefaultValue.getClass().getMethod("clone", null);
 261                 defaultValue = (V) cloneMethod.invoke(clonableDefaultValue, null);
 262
 263                 map.put(key, defaultValue);
 264                 return defaultValue;
 265         }
 266
 267         /**
 268          * @param <K> COMMENT
 269          * @param <V> COMMENT
 270          * @param map COMMENT
 271          * @param key COMMENT
 272          * @param defaultValueConstructor COMMENT
 273          * @return COMMENT
 274          * @throws CreationFailedException  COMMENT
 275          */
 276         public static <K, V> V ensureContainsKey(final Map<K, V> map, final K key, final AbstractFactory<V> defaultValueConstructor) throws CreationFailedException {
 277                 if (map.containsKey(key))
 278                         return map.get(key);
 279                 final V defaultValue = defaultValueConstructor.create();
 280
 281                 map.put(key, defaultValue);
 282                 return defaultValue;
 283         }
 284
 285         // ///////////////////////////////////////
 286
 287         /**
 288          * @param <V> COMMENT
 289          * @param c COMMENT
 290          * @param o COMMENT
 291          * @param e COMMENT
 292          * @return COMMENT
 293          */
 294         public static <V> boolean removeFirst(final Collection<V> c, final V o, final EquivalenceRelation<V> e) {
 295                 for (final Iterator<V> i = c.iterator(); i.hasNext();)
 296                         if (e.op(o, i.next())) {
 297                                 i.remove();
 298                                 return true;
 299                         }
 300                 return false;
 301         }
 302
 303         /**
 304          * @param <V> COMMENT
 305          * @param c COMMENT
 306          * @param o COMMENT
 307          * @param e COMMENT
 308          * @return COMMENT
 309          */
 310         public static <V> boolean removeAll(final Collection<V> c, final V o, final EquivalenceRelation<V> e) {
 311                 boolean removed = false;
 312
 313                 for (final Iterator<V> i = c.iterator(); i.hasNext();)
 314                         if (e.op(o, i.next())) {
 315                                 i.remove();
 316                                 removed = true;
 317                         }
 318
 319                 return removed;
 320         }
 321
 322         /**
 323          * @param <V> COMMENT
 324          * @param l COMMENT
 325          * @param o COMMENT
 326          * @param e COMMENT
 327          * @return COMMENT
 328          */
 329         public static <V> boolean replaceFirst(final List<V> l, final V o, final EquivalenceRelation<V> e) {
 330                 for (int i = 0; i < l.size(); i++)
 331                         if (e.op(o, l.get(i))) {
 332                                 l.set(i, o);
 333                                 return true;
 334                         }
 335
 336                 return false;
 337         }
 338
 339         // ///////////////////////////////////////
 340
 341         /**
 342          * @param <K> COMMENT
 343          * @param <V> COMMENT
 344          * @param map COMMENT
 345          * @param keys COMMENT
 346          * @return COMMENT
 347          */
 348         public static <K, V> V[] slice(final Map<K, V> map, final K... keys) {
 349                 final V[] values = (V[]) Array.newInstance(map.get(keys[0]).getClass(), keys.length);
 350                 for (int i = 0; i < keys.length; i++)
 351                         values[i] = map.get(keys[i]);
 352                 return values;
 353         }
 354
 355         /**
 356          * @param <K> COMMENT
 357          * @param <V> COMMENT
 358          * @param map COMMENT
 359          * @param keys COMMENT
 360          * @return COMMENT
 361          */
 362         public static <K, V> List<V> slice(final Map<K, V> map, final List<K> keys) {
 363                 List<V> values;
 364                 try {
 365                         values = keys.getClass().newInstance();
 366                 } catch (final InstantiationException e) {
 367                         values = new ArrayList<V>();
 368                 } catch (final IllegalAccessException e) {
 369                         values = new ArrayList<V>();
 370                 }
 371
 372                 for (int i = 0; i < keys.size(); i++)
 373                         values.add(map.get(keys.get(i)));
 374                 return values;
 375         }
 376
 377         // //////////////////////////////////////////////
 378
 379         /**
 380          * @param <V> COMMENT
 381          * @param comparator COMMENT
 382          * @return COMMENT
 383          */
 384         public static <V> Comparator<V> reverse(final Comparator<V> comparator) {
 385                 return new Comparator<V>() {
 386                         public int compare(final V arg0, final V arg1) {
 387                                 return comparator.compare(arg1, arg0);
 388                         }
 389                 };
 390         }
 391
 392         // ////////////////////////////////////////////////
 393
 394         /**
 395          * @param <V> COMMENT
 396          * @param a COMMENT
 397          * @param b COMMENT
 398          * @return COMMENT
 399          */
 400         public static <V> boolean sameContents(final Collection<V> a, final Collection<V> b) {
 401                 final Multiset<V> x = new MappedMultiset<V>(a);
 402                 final Multiset<V> y = new MappedMultiset<V>(b);
 403                 return x.equals(y);
 404         }
 405
 406         // ////////////////////////////////////////////////
 407
 408         private static final class ComparableComarator<V extends Comparable<V>> implements Comparator<V> {
 409                 public int compare(final V o1, final V o2) {
 410                         return o1.compareTo(o2);
 411                 }
 412         }
 413
 414         /**
 415          * @param <K> COMMENT
 416          * @param <V> COMMENT
 417          * @param map COMMENT
 418          * @return COMMENT
 419          */
 420         public static <K, V extends Comparable<V>> SortedSet<K> keySetByValues(final Map<K, V> map) {
 421                 return CollectionsUtilities.keySetByValues(map, new ComparableComarator<V>());
 422         }
 423
 424         @SuppressWarnings("unchecked")
 425         private static <T> int finagleComparison(final T arg0, final T arg1) {
 426                 if (arg0 instanceof Comparable && arg1 instanceof Comparable)
 427                         try {
 428                                 return ((Comparable<T>) arg0).compareTo(arg1);
 429                         } catch (final ClassCastException e) {
 430                                 try {
 431                                         return -((Comparable<T>) arg1).compareTo(arg0);
 432                                 } catch (final ClassCastException f) {
 433                                         // fall through
 434                                 }
 435                         }
 436
 437                 final int hashCompare = KezvhMath.compare(arg0.hashCode(), arg1.hashCode()); // usually different if objects are not
 438                 // equal
 439                 if (hashCompare != 0)
 440                         return hashCompare;
 441
 442                 return KezvhMath.compare(System.identityHashCode(arg0), System.identityHashCode(arg1)); // kind of a last ditch effort,
 443                 // which should *usually* return
 444                 // different values for objects
 445                 // which are not equal. otw, yur screwed
 446         }
 447
 448         /**
 449          * @param <K> COMMENT
 450          * @param <V> COMMENT
 451          * @param map COMMENT
 452          * @param c COMMENT
 453          * @return COMMENT
 454          */
 455         public static <K, V> SortedSet<K> keySetByValues(final Map<K, V> map, final Comparator<V> c) {
 456                 final Comparator<K> orderByValue = new Comparator<K>() {
 457                         public int compare(final K arg0, final K arg1) {
 458                                 final boolean has0 = map.containsKey(arg0);
 459                                 final boolean has1 = map.containsKey(arg1);
 460                                 if (!has0 || !has1)
 461                                         return KezvhMath.compare(has0, has1);
 462
 463                                 int cmp = c.compare(map.get(arg0), map.get(arg1));
 464                                 if (cmp == 0 && !arg0.equals(arg1)) { // distinct keys map to equal objects
 465                                         cmp = CollectionsUtilities.finagleComparison(arg0, arg1); // we do this to try to keep two separate keys from
 466                                         // mapping to the same index of the sorted set
 467                                         if (cmp == 0) // this is bad - no way to order things...
 468                                                 throw new IllegalArgumentException("cannot figure out how to order two equal objects: " + arg0 + ", " + arg1);
 469                                 }
 470                                 return cmp;
 471                         }
 472                 };
 473                 final SortedSet<K> keySet = new TreeSet<K>(orderByValue);
 474                 keySet.addAll(map.keySet());
 475                 return keySet;
 476         }
 477
 478         // ///////////////////////////////////////////////
 479
 480         /**
 481          * @param <T>  COMMENT
 482          * @param c COMMENT
 483          * @return COMMENT
 484          */
 485         public static <T> int hash(final Iterable<T> c) {
 486                 if (c == null)
 487                         return 0;
 488
 489                 int result = 1;
 490
 491                 for (final T element : c)
 492                         result = 31 * result + (element == null ? 0 : element.hashCode());
 493
 494                 return result;
 495         }
 496 }