001 /*
002 * Copyright (C) 2008 The Guava Authors
003 *
004 * Licensed under the Apache License, Version 2.0 (the "License");
005 * you may not use this file except in compliance with the License.
006 * You may obtain a copy of the License at
007 *
008 * http://www.apache.org/licenses/LICENSE-2.0
009 *
010 * Unless required by applicable law or agreed to in writing, software
011 * distributed under the License is distributed on an "AS IS" BASIS,
012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013 * See the License for the specific language governing permissions and
014 * limitations under the License.
015 */
016
017 package com.google.common.collect;
018
019 import static com.google.common.base.Preconditions.checkArgument;
020 import static com.google.common.base.Preconditions.checkNotNull;
021 import static com.google.common.math.LongMath.binomial;
022
023 import com.google.common.annotations.Beta;
024 import com.google.common.annotations.GwtCompatible;
025 import com.google.common.base.Function;
026 import com.google.common.base.Joiner;
027 import com.google.common.base.Predicate;
028 import com.google.common.base.Predicates;
029 import com.google.common.math.IntMath;
030 import com.google.common.primitives.Ints;
031
032 import java.util.AbstractCollection;
033 import java.util.ArrayList;
034 import java.util.Collection;
035 import java.util.Collections;
036 import java.util.Comparator;
037 import java.util.Iterator;
038 import java.util.List;
039
040 import javax.annotation.Nullable;
041
042 /**
043 * Provides static methods for working with {@code Collection} instances.
044 *
045 * @author Chris Povirk
046 * @author Mike Bostock
047 * @author Jared Levy
048 * @since 2.0 (imported from Google Collections Library)
049 */
050 @GwtCompatible
051 public final class Collections2 {
052 private Collections2() {}
053
054 /**
055 * Returns the elements of {@code unfiltered} that satisfy a predicate. The
056 * returned collection is a live view of {@code unfiltered}; changes to one
057 * affect the other.
058 *
059 * <p>The resulting collection's iterator does not support {@code remove()},
060 * but all other collection methods are supported. When given an element that
061 * doesn't satisfy the predicate, the collection's {@code add()} and {@code
062 * addAll()} methods throw an {@link IllegalArgumentException}. When methods
063 * such as {@code removeAll()} and {@code clear()} are called on the filtered
064 * collection, only elements that satisfy the filter will be removed from the
065 * underlying collection.
066 *
067 * <p>The returned collection isn't threadsafe or serializable, even if
068 * {@code unfiltered} is.
069 *
070 * <p>Many of the filtered collection's methods, such as {@code size()},
071 * iterate across every element in the underlying collection and determine
072 * which elements satisfy the filter. When a live view is <i>not</i> needed,
073 * it may be faster to copy {@code Iterables.filter(unfiltered, predicate)}
074 * and use the copy.
075 *
076 * <p><b>Warning:</b> {@code predicate} must be <i>consistent with equals</i>,
077 * as documented at {@link Predicate#apply}. Do not provide a predicate such
078 * as {@code Predicates.instanceOf(ArrayList.class)}, which is inconsistent
079 * with equals. (See {@link Iterables#filter(Iterable, Class)} for related
080 * functionality.)
081 */
082 // TODO(kevinb): how can we omit that Iterables link when building gwt
083 // javadoc?
084 public static <E> Collection<E> filter(
085 Collection<E> unfiltered, Predicate<? super E> predicate) {
086 if (unfiltered instanceof FilteredCollection) {
087 // Support clear(), removeAll(), and retainAll() when filtering a filtered
088 // collection.
089 return ((FilteredCollection<E>) unfiltered).createCombined(predicate);
090 }
091
092 return new FilteredCollection<E>(
093 checkNotNull(unfiltered), checkNotNull(predicate));
094 }
095
096 /**
097 * Delegates to {@link Collection#contains}. Returns {@code false} if the
098 * {@code contains} method throws a {@code ClassCastException}.
099 */
100 static boolean safeContains(Collection<?> collection, Object object) {
101 try {
102 return collection.contains(object);
103 } catch (ClassCastException e) {
104 return false;
105 }
106 }
107
108 static class FilteredCollection<E> implements Collection<E> {
109 final Collection<E> unfiltered;
110 final Predicate<? super E> predicate;
111
112 FilteredCollection(Collection<E> unfiltered,
113 Predicate<? super E> predicate) {
114 this.unfiltered = unfiltered;
115 this.predicate = predicate;
116 }
117
118 FilteredCollection<E> createCombined(Predicate<? super E> newPredicate) {
119 return new FilteredCollection<E>(unfiltered,
120 Predicates.<E>and(predicate, newPredicate));
121 // .<E> above needed to compile in JDK 5
122 }
123
124 @Override
125 public boolean add(E element) {
126 checkArgument(predicate.apply(element));
127 return unfiltered.add(element);
128 }
129
130 @Override
131 public boolean addAll(Collection<? extends E> collection) {
132 for (E element : collection) {
133 checkArgument(predicate.apply(element));
134 }
135 return unfiltered.addAll(collection);
136 }
137
138 @Override
139 public void clear() {
140 Iterables.removeIf(unfiltered, predicate);
141 }
142
143 @Override
144 public boolean contains(Object element) {
145 try {
146 // unsafe cast can result in a CCE from predicate.apply(), which we
147 // will catch
148 @SuppressWarnings("unchecked")
149 E e = (E) element;
150
151 /*
152 * We check whether e satisfies the predicate, when we really mean to
153 * check whether the element contained in the set does. This is ok as
154 * long as the predicate is consistent with equals, as required.
155 */
156 return predicate.apply(e) && unfiltered.contains(element);
157 } catch (NullPointerException e) {
158 return false;
159 } catch (ClassCastException e) {
160 return false;
161 }
162 }
163
164 @Override
165 public boolean containsAll(Collection<?> collection) {
166 for (Object element : collection) {
167 if (!contains(element)) {
168 return false;
169 }
170 }
171 return true;
172 }
173
174 @Override
175 public boolean isEmpty() {
176 return !Iterators.any(unfiltered.iterator(), predicate);
177 }
178
179 @Override
180 public Iterator<E> iterator() {
181 return Iterators.filter(unfiltered.iterator(), predicate);
182 }
183
184 @Override
185 public boolean remove(Object element) {
186 try {
187 // unsafe cast can result in a CCE from predicate.apply(), which we
188 // will catch
189 @SuppressWarnings("unchecked")
190 E e = (E) element;
191
192 // See comment in contains() concerning predicate.apply(e)
193 return predicate.apply(e) && unfiltered.remove(element);
194 } catch (NullPointerException e) {
195 return false;
196 } catch (ClassCastException e) {
197 return false;
198 }
199 }
200
201 @Override
202 public boolean removeAll(final Collection<?> collection) {
203 checkNotNull(collection);
204 Predicate<E> combinedPredicate = new Predicate<E>() {
205 @Override
206 public boolean apply(E input) {
207 return predicate.apply(input) && collection.contains(input);
208 }
209 };
210 return Iterables.removeIf(unfiltered, combinedPredicate);
211 }
212
213 @Override
214 public boolean retainAll(final Collection<?> collection) {
215 checkNotNull(collection);
216 Predicate<E> combinedPredicate = new Predicate<E>() {
217 @Override
218 public boolean apply(E input) {
219 // See comment in contains() concerning predicate.apply(e)
220 return predicate.apply(input) && !collection.contains(input);
221 }
222 };
223 return Iterables.removeIf(unfiltered, combinedPredicate);
224 }
225
226 @Override
227 public int size() {
228 return Iterators.size(iterator());
229 }
230
231 @Override
232 public Object[] toArray() {
233 // creating an ArrayList so filtering happens once
234 return Lists.newArrayList(iterator()).toArray();
235 }
236
237 @Override
238 public <T> T[] toArray(T[] array) {
239 return Lists.newArrayList(iterator()).toArray(array);
240 }
241
242 @Override public String toString() {
243 return Iterators.toString(iterator());
244 }
245 }
246
247 /**
248 * Returns a collection that applies {@code function} to each element of
249 * {@code fromCollection}. The returned collection is a live view of {@code
250 * fromCollection}; changes to one affect the other.
251 *
252 * <p>The returned collection's {@code add()} and {@code addAll()} methods
253 * throw an {@link UnsupportedOperationException}. All other collection
254 * methods are supported, as long as {@code fromCollection} supports them.
255 *
256 * <p>The returned collection isn't threadsafe or serializable, even if
257 * {@code fromCollection} is.
258 *
259 * <p>When a live view is <i>not</i> needed, it may be faster to copy the
260 * transformed collection and use the copy.
261 *
262 * <p>If the input {@code Collection} is known to be a {@code List}, consider
263 * {@link Lists#transform}. If only an {@code Iterable} is available, use
264 * {@link Iterables#transform}.
265 */
266 public static <F, T> Collection<T> transform(Collection<F> fromCollection,
267 Function<? super F, T> function) {
268 return new TransformedCollection<F, T>(fromCollection, function);
269 }
270
271 static class TransformedCollection<F, T> extends AbstractCollection<T> {
272 final Collection<F> fromCollection;
273 final Function<? super F, ? extends T> function;
274
275 TransformedCollection(Collection<F> fromCollection,
276 Function<? super F, ? extends T> function) {
277 this.fromCollection = checkNotNull(fromCollection);
278 this.function = checkNotNull(function);
279 }
280
281 @Override public void clear() {
282 fromCollection.clear();
283 }
284
285 @Override public boolean isEmpty() {
286 return fromCollection.isEmpty();
287 }
288
289 @Override public Iterator<T> iterator() {
290 return Iterators.transform(fromCollection.iterator(), function);
291 }
292
293 @Override public int size() {
294 return fromCollection.size();
295 }
296 }
297
298 /**
299 * Returns {@code true} if the collection {@code self} contains all of the
300 * elements in the collection {@code c}.
301 *
302 * <p>This method iterates over the specified collection {@code c}, checking
303 * each element returned by the iterator in turn to see if it is contained in
304 * the specified collection {@code self}. If all elements are so contained,
305 * {@code true} is returned, otherwise {@code false}.
306 *
307 * @param self a collection which might contain all elements in {@code c}
308 * @param c a collection whose elements might be contained by {@code self}
309 */
310 static boolean containsAllImpl(Collection<?> self, Collection<?> c) {
311 checkNotNull(self);
312 for (Object o : c) {
313 if (!self.contains(o)) {
314 return false;
315 }
316 }
317 return true;
318 }
319
320 /**
321 * An implementation of {@link Collection#toString()}.
322 */
323 static String toStringImpl(final Collection<?> collection) {
324 StringBuilder sb
325 = newStringBuilderForCollection(collection.size()).append('[');
326 STANDARD_JOINER.appendTo(
327 sb, Iterables.transform(collection, new Function<Object, Object>() {
328 @Override public Object apply(Object input) {
329 return input == collection ? "(this Collection)" : input;
330 }
331 }));
332 return sb.append(']').toString();
333 }
334
335 /**
336 * Returns best-effort-sized StringBuilder based on the given collection size.
337 */
338 static StringBuilder newStringBuilderForCollection(int size) {
339 checkArgument(size >= 0, "size must be non-negative");
340 return new StringBuilder((int) Math.min(size * 8L, Ints.MAX_POWER_OF_TWO));
341 }
342
343 /**
344 * Used to avoid http://bugs.sun.com/view_bug.do?bug_id=6558557
345 */
346 static <T> Collection<T> cast(Iterable<T> iterable) {
347 return (Collection<T>) iterable;
348 }
349
350 static final Joiner STANDARD_JOINER = Joiner.on(", ").useForNull("null");
351
352 /**
353 * Returns a {@link Collection} of all the permutations of the specified
354 * {@link Iterable}.
355 *
356 * <p><i>Notes:</i> This is an implementation of the algorithm for
357 * Lexicographical Permutations Generation, described in Knuth's "The Art of
358 * Computer Programming", Volume 4, Chapter 7, Section 7.2.1.2. The
359 * iteration order follows the lexicographical order. This means that
360 * the first permutation will be in ascending order, and the last will be in
361 * descending order.
362 *
363 * <p>Duplicate elements are considered equal. For example, the list [1, 1]
364 * will have only one permutation, instead of two. This is why the elements
365 * have to implement {@link Comparable}.
366 *
367 * <p>An empty iterable has only one permutation, which is an empty list.
368 *
369 * <p>This method is equivalent to
370 * {@code Collections2.orderedPermutations(list, Ordering.natural())}.
371 *
372 * @param elements the original iterable whose elements have to be permuted.
373 * @return an immutable {@link Collection} containing all the different
374 * permutations of the original iterable.
375 * @throws NullPointerException if the specified iterable is null or has any
376 * null elements.
377 * @since 12.0
378 */
379 @Beta public static <E extends Comparable<? super E>>
380 Collection<List<E>> orderedPermutations(Iterable<E> elements) {
381 return orderedPermutations(elements, Ordering.natural());
382 }
383
384 /**
385 * Returns a {@link Collection} of all the permutations of the specified
386 * {@link Iterable} using the specified {@link Comparator} for establishing
387 * the lexicographical ordering.
388 *
389 * <p>Examples: <pre> {@code
390 *
391 * for (List<String> perm : orderedPermutations(asList("b", "c", "a"))) {
392 * println(perm);
393 * }
394 * // -> ["a", "b", "c"]
395 * // -> ["a", "c", "b"]
396 * // -> ["b", "a", "c"]
397 * // -> ["b", "c", "a"]
398 * // -> ["c", "a", "b"]
399 * // -> ["c", "b", "a"]
400 *
401 * for (List<Integer> perm : orderedPermutations(asList(1, 2, 2, 1))) {
402 * println(perm);
403 * }
404 * // -> [1, 1, 2, 2]
405 * // -> [1, 2, 1, 2]
406 * // -> [1, 2, 2, 1]
407 * // -> [2, 1, 1, 2]
408 * // -> [2, 1, 2, 1]
409 * // -> [2, 2, 1, 1]}</pre>
410 *
411 * <p><i>Notes:</i> This is an implementation of the algorithm for
412 * Lexicographical Permutations Generation, described in Knuth's "The Art of
413 * Computer Programming", Volume 4, Chapter 7, Section 7.2.1.2. The
414 * iteration order follows the lexicographical order. This means that
415 * the first permutation will be in ascending order, and the last will be in
416 * descending order.
417 *
418 * <p>Elements that compare equal are considered equal and no new permutations
419 * are created by swapping them.
420 *
421 * <p>An empty iterable has only one permutation, which is an empty list.
422 *
423 * @param elements the original iterable whose elements have to be permuted.
424 * @param comparator a comparator for the iterable's elements.
425 * @return an immutable {@link Collection} containing all the different
426 * permutations of the original iterable.
427 * @throws NullPointerException If the specified iterable is null, has any
428 * null elements, or if the specified comparator is null.
429 * @since 12.0
430 */
431 @Beta public static <E> Collection<List<E>> orderedPermutations(
432 Iterable<E> elements, Comparator<? super E> comparator) {
433 return new OrderedPermutationCollection<E>(elements, comparator);
434 }
435
436 private static final class OrderedPermutationCollection<E>
437 extends AbstractCollection<List<E>> {
438 final ImmutableList<E> inputList;
439 final Comparator<? super E> comparator;
440 final int size;
441
442 OrderedPermutationCollection(Iterable<E> input,
443 Comparator<? super E> comparator) {
444 this.inputList = Ordering.from(comparator).immutableSortedCopy(input);
445 this.comparator = comparator;
446 this.size = calculateSize(inputList, comparator);
447 }
448
449 /**
450 * The number of permutations with repeated elements is calculated as
451 * follows:
452 * <ul>
453 * <li>For an empty list, it is 1 (base case).</li>
454 * <li>When r numbers are added to a list of n-r elements, the number of
455 * permutations is increased by a factor of (n choose r).</li>
456 * </ul>
457 */
458 private static <E> int calculateSize(
459 List<E> sortedInputList, Comparator<? super E> comparator) {
460 long permutations = 1;
461 int n = 1;
462 int r = 1;
463 while (n < sortedInputList.size()) {
464 int comparison = comparator.compare(
465 sortedInputList.get(n - 1), sortedInputList.get(n));
466 if (comparison < 0) {
467 // We move to the next non-repeated element.
468 permutations *= binomial(n, r);
469 r = 0;
470 if (!isPositiveInt(permutations)) {
471 return Integer.MAX_VALUE;
472 }
473 }
474 n++;
475 r++;
476 }
477 permutations *= binomial(n, r);
478 if (!isPositiveInt(permutations)) {
479 return Integer.MAX_VALUE;
480 }
481 return (int) permutations;
482 }
483
484 @Override public int size() {
485 return size;
486 }
487
488 @Override public boolean isEmpty() {
489 return false;
490 }
491
492 @Override public Iterator<List<E>> iterator() {
493 return new OrderedPermutationIterator<E>(inputList, comparator);
494 }
495
496 @Override public boolean contains(@Nullable Object obj) {
497 if (obj instanceof List) {
498 List<?> list = (List<?>) obj;
499 return isPermutation(inputList, list);
500 }
501 return false;
502 }
503
504 @Override public String toString() {
505 return "orderedPermutationCollection(" + inputList + ")";
506 }
507 }
508
509 private static final class OrderedPermutationIterator<E>
510 extends AbstractIterator<List<E>> {
511
512 List<E> nextPermutation;
513 final Comparator<? super E> comparator;
514
515 OrderedPermutationIterator(List<E> list,
516 Comparator<? super E> comparator) {
517 this.nextPermutation = Lists.newArrayList(list);
518 this.comparator = comparator;
519 }
520
521 @Override protected List<E> computeNext() {
522 if (nextPermutation == null) {
523 return endOfData();
524 }
525 ImmutableList<E> next = ImmutableList.copyOf(nextPermutation);
526 calculateNextPermutation();
527 return next;
528 }
529
530 void calculateNextPermutation() {
531 int j = findNextJ();
532 if (j == -1) {
533 nextPermutation = null;
534 return;
535 }
536
537 int l = findNextL(j);
538 Collections.swap(nextPermutation, j, l);
539 int n = nextPermutation.size();
540 Collections.reverse(nextPermutation.subList(j + 1, n));
541 }
542
543 int findNextJ() {
544 for (int k = nextPermutation.size() - 2; k >= 0; k--) {
545 if (comparator.compare(nextPermutation.get(k),
546 nextPermutation.get(k + 1)) < 0) {
547 return k;
548 }
549 }
550 return -1;
551 }
552
553 int findNextL(int j) {
554 E ak = nextPermutation.get(j);
555 for (int l = nextPermutation.size() - 1; l > j; l--) {
556 if (comparator.compare(ak, nextPermutation.get(l)) < 0) {
557 return l;
558 }
559 }
560 throw new AssertionError("this statement should be unreachable");
561 }
562 }
563
564 /**
565 * Returns a {@link Collection} of all the permutations of the specified
566 * {@link Collection}.
567 *
568 * <p><i>Notes:</i> This is an implementation of the Plain Changes algorithm
569 * for permutations generation, described in Knuth's "The Art of Computer
570 * Programming", Volume 4, Chapter 7, Section 7.2.1.2.
571 *
572 * <p>If the input list contains equal elements, some of the generated
573 * permutations will be equal.
574 *
575 * <p>An empty collection has only one permutation, which is an empty list.
576 *
577 * @param elements the original collection whose elements have to be permuted.
578 * @return an immutable {@link Collection} containing all the different
579 * permutations of the original collection.
580 * @throws NullPointerException if the specified collection is null or has any
581 * null elements.
582 * @since 12.0
583 */
584 @Beta public static <E> Collection<List<E>> permutations(
585 Collection<E> elements) {
586 return new PermutationCollection<E>(ImmutableList.copyOf(elements));
587 }
588
589 private static final class PermutationCollection<E>
590 extends AbstractCollection<List<E>> {
591 final ImmutableList<E> inputList;
592
593 PermutationCollection(ImmutableList<E> input) {
594 this.inputList = input;
595 }
596
597 @Override public int size() {
598 return IntMath.factorial(inputList.size());
599 }
600
601 @Override public boolean isEmpty() {
602 return false;
603 }
604
605 @Override public Iterator<List<E>> iterator() {
606 return new PermutationIterator<E>(inputList);
607 }
608
609 @Override public boolean contains(@Nullable Object obj) {
610 if (obj instanceof List) {
611 List<?> list = (List<?>) obj;
612 return isPermutation(inputList, list);
613 }
614 return false;
615 }
616
617 @Override public String toString() {
618 return "permutations(" + inputList + ")";
619 }
620 }
621
622 private static class PermutationIterator<E>
623 extends AbstractIterator<List<E>> {
624 final List<E> list;
625 final int[] c;
626 final int[] o;
627 int j;
628
629 PermutationIterator(List<E> list) {
630 this.list = new ArrayList<E>(list);
631 int n = list.size();
632 c = new int[n];
633 o = new int[n];
634 for (int i = 0; i < n; i++) {
635 c[i] = 0;
636 o[i] = 1;
637 }
638 j = Integer.MAX_VALUE;
639 }
640
641 @Override protected List<E> computeNext() {
642 if (j <= 0) {
643 return endOfData();
644 }
645 ImmutableList<E> next = ImmutableList.copyOf(list);
646 calculateNextPermutation();
647 return next;
648 }
649
650 void calculateNextPermutation() {
651 j = list.size() - 1;
652 int s = 0;
653
654 // Handle the special case of an empty list. Skip the calculation of the
655 // next permutation.
656 if (j == -1) {
657 return;
658 }
659
660 while (true) {
661 int q = c[j] + o[j];
662 if (q < 0) {
663 switchDirection();
664 continue;
665 }
666 if (q == j + 1) {
667 if (j == 0) {
668 break;
669 }
670 s++;
671 switchDirection();
672 continue;
673 }
674
675 Collections.swap(list, j - c[j] + s, j - q + s);
676 c[j] = q;
677 break;
678 }
679 }
680
681 void switchDirection() {
682 o[j] = -o[j];
683 j--;
684 }
685 }
686
687 /**
688 * Returns {@code true} if the second list is a permutation of the first.
689 */
690 private static boolean isPermutation(List<?> first,
691 List<?> second) {
692 if (first.size() != second.size()) {
693 return false;
694 }
695 Multiset<?> firstSet = HashMultiset.create(first);
696 Multiset<?> secondSet = HashMultiset.create(second);
697 return firstSet.equals(secondSet);
698 }
699
700 private static boolean isPositiveInt(long n) {
701 return n >= 0 && n <= Integer.MAX_VALUE;
702 }
703 }