1090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson/* 21d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Copyright (C) 2008 The Guava Authors 3090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 4090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Licensed under the Apache License, Version 2.0 (the "License"); 5090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * you may not use this file except in compliance with the License. 6090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * You may obtain a copy of the License at 7090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 8090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * http://www.apache.org/licenses/LICENSE-2.0 9090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 10090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Unless required by applicable law or agreed to in writing, software 11090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * distributed under the License is distributed on an "AS IS" BASIS, 12090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * See the License for the specific language governing permissions and 14090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * limitations under the License. 15090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 16090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 17090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonpackage com.google.common.collect; 18090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport static com.google.common.base.Preconditions.checkArgument; 201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport static com.google.common.base.Preconditions.checkNotNull; 210888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport static com.google.common.base.Predicates.and; 220888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport static com.google.common.base.Predicates.in; 230888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport static com.google.common.base.Predicates.not; 240888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport static com.google.common.collect.CollectPreconditions.checkNonnegative; 257dd252788645e940eada959bdde927426e2531c9Paul Duffinimport static com.google.common.math.LongMath.binomial; 261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 277dd252788645e940eada959bdde927426e2531c9Paul Duffinimport com.google.common.annotations.Beta; 28090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport com.google.common.annotations.GwtCompatible; 29090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport com.google.common.base.Function; 30090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport com.google.common.base.Joiner; 31090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport com.google.common.base.Predicate; 32090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport com.google.common.base.Predicates; 337dd252788645e940eada959bdde927426e2531c9Paul Duffinimport com.google.common.math.IntMath; 341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.primitives.Ints; 35090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 36090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.AbstractCollection; 371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.ArrayList; 380888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport java.util.Arrays; 39090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.Collection; 401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.Collections; 417dd252788645e940eada959bdde927426e2531c9Paul Duffinimport java.util.Comparator; 42090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.Iterator; 431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.List; 44bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor 457dd252788645e940eada959bdde927426e2531c9Paul Duffinimport javax.annotation.Nullable; 467dd252788645e940eada959bdde927426e2531c9Paul Duffin 47090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson/** 48090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Provides static methods for working with {@code Collection} instances. 49090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 50090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @author Chris Povirk 51090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @author Mike Bostock 52090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @author Jared Levy 531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @since 2.0 (imported from Google Collections Library) 54090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 55090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson@GwtCompatible 56090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonpublic final class Collections2 { 57090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private Collections2() {} 58090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 59090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 60090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns the elements of {@code unfiltered} that satisfy a predicate. The 61090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * returned collection is a live view of {@code unfiltered}; changes to one 62090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * affect the other. 63090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 64090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>The resulting collection's iterator does not support {@code remove()}, 651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * but all other collection methods are supported. When given an element that 661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * doesn't satisfy the predicate, the collection's {@code add()} and {@code 671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * addAll()} methods throw an {@link IllegalArgumentException}. When methods 681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * such as {@code removeAll()} and {@code clear()} are called on the filtered 691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * collection, only elements that satisfy the filter will be removed from the 701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * underlying collection. 71090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 72090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>The returned collection isn't threadsafe or serializable, even if 73090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@code unfiltered} is. 74090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 75090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>Many of the filtered collection's methods, such as {@code size()}, 76090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * iterate across every element in the underlying collection and determine 77090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * which elements satisfy the filter. When a live view is <i>not</i> needed, 78090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * it may be faster to copy {@code Iterables.filter(unfiltered, predicate)} 79090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * and use the copy. 801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p><b>Warning:</b> {@code predicate} must be <i>consistent with equals</i>, 821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * as documented at {@link Predicate#apply}. Do not provide a predicate such 831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * as {@code Predicates.instanceOf(ArrayList.class)}, which is inconsistent 841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * with equals. (See {@link Iterables#filter(Iterable, Class)} for related 851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * functionality.) 86090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // TODO(kevinb): how can we omit that Iterables link when building gwt 881d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // javadoc? 890888a09821a98ac0680fad765217302858e70fa4Paul Duffin public static <E> Collection<E> filter( 900888a09821a98ac0680fad765217302858e70fa4Paul Duffin Collection<E> unfiltered, Predicate<? super E> predicate) { 91090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (unfiltered instanceof FilteredCollection) { 92090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // Support clear(), removeAll(), and retainAll() when filtering a filtered 93090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // collection. 94090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return ((FilteredCollection<E>) unfiltered).createCombined(predicate); 95090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 96090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 970888a09821a98ac0680fad765217302858e70fa4Paul Duffin return new FilteredCollection<E>( 980888a09821a98ac0680fad765217302858e70fa4Paul Duffin checkNotNull(unfiltered), checkNotNull(predicate)); 99090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 100090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 101bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor /** 1021d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Delegates to {@link Collection#contains}. Returns {@code false} if the 1037dd252788645e940eada959bdde927426e2531c9Paul Duffin * {@code contains} method throws a {@code ClassCastException} or 1047dd252788645e940eada959bdde927426e2531c9Paul Duffin * {@code NullPointerException}. 105bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor */ 1060888a09821a98ac0680fad765217302858e70fa4Paul Duffin static boolean safeContains( 1070888a09821a98ac0680fad765217302858e70fa4Paul Duffin Collection<?> collection, @Nullable Object object) { 1087dd252788645e940eada959bdde927426e2531c9Paul Duffin checkNotNull(collection); 109bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor try { 110bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor return collection.contains(object); 111bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor } catch (ClassCastException e) { 112bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor return false; 1137dd252788645e940eada959bdde927426e2531c9Paul Duffin } catch (NullPointerException e) { 1147dd252788645e940eada959bdde927426e2531c9Paul Duffin return false; 1157dd252788645e940eada959bdde927426e2531c9Paul Duffin } 1167dd252788645e940eada959bdde927426e2531c9Paul Duffin } 1177dd252788645e940eada959bdde927426e2531c9Paul Duffin 1187dd252788645e940eada959bdde927426e2531c9Paul Duffin /** 1197dd252788645e940eada959bdde927426e2531c9Paul Duffin * Delegates to {@link Collection#remove}. Returns {@code false} if the 1207dd252788645e940eada959bdde927426e2531c9Paul Duffin * {@code remove} method throws a {@code ClassCastException} or 1217dd252788645e940eada959bdde927426e2531c9Paul Duffin * {@code NullPointerException}. 1227dd252788645e940eada959bdde927426e2531c9Paul Duffin */ 1230888a09821a98ac0680fad765217302858e70fa4Paul Duffin static boolean safeRemove(Collection<?> collection, @Nullable Object object) { 1247dd252788645e940eada959bdde927426e2531c9Paul Duffin checkNotNull(collection); 1257dd252788645e940eada959bdde927426e2531c9Paul Duffin try { 1267dd252788645e940eada959bdde927426e2531c9Paul Duffin return collection.remove(object); 1277dd252788645e940eada959bdde927426e2531c9Paul Duffin } catch (ClassCastException e) { 1287dd252788645e940eada959bdde927426e2531c9Paul Duffin return false; 1297dd252788645e940eada959bdde927426e2531c9Paul Duffin } catch (NullPointerException e) { 1307dd252788645e940eada959bdde927426e2531c9Paul Duffin return false; 131bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor } 132bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor } 133bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor 1340888a09821a98ac0680fad765217302858e70fa4Paul Duffin static class FilteredCollection<E> extends AbstractCollection<E> { 135090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson final Collection<E> unfiltered; 136090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson final Predicate<? super E> predicate; 137090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 1380888a09821a98ac0680fad765217302858e70fa4Paul Duffin FilteredCollection(Collection<E> unfiltered, 1390888a09821a98ac0680fad765217302858e70fa4Paul Duffin Predicate<? super E> predicate) { 140090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson this.unfiltered = unfiltered; 141090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson this.predicate = predicate; 142090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 143090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 144090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson FilteredCollection<E> createCombined(Predicate<? super E> newPredicate) { 1450888a09821a98ac0680fad765217302858e70fa4Paul Duffin return new FilteredCollection<E>(unfiltered, 1460888a09821a98ac0680fad765217302858e70fa4Paul Duffin Predicates.<E>and(predicate, newPredicate)); 147090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // .<E> above needed to compile in JDK 5 148090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 149090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 1500888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 151090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public boolean add(E element) { 152090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson checkArgument(predicate.apply(element)); 153090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return unfiltered.add(element); 154090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 155090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 1560888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 157090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public boolean addAll(Collection<? extends E> collection) { 158090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson for (E element : collection) { 159090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson checkArgument(predicate.apply(element)); 160090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 161090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return unfiltered.addAll(collection); 162090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 163090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 1640888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 165090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public void clear() { 166090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Iterables.removeIf(unfiltered, predicate); 167090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 168090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 1690888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 1700888a09821a98ac0680fad765217302858e70fa4Paul Duffin public boolean contains(@Nullable Object element) { 1710888a09821a98ac0680fad765217302858e70fa4Paul Duffin if (safeContains(unfiltered, element)) { 1720888a09821a98ac0680fad765217302858e70fa4Paul Duffin @SuppressWarnings("unchecked") // element is in unfiltered, so it must be an E 173090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson E e = (E) element; 1740888a09821a98ac0680fad765217302858e70fa4Paul Duffin return predicate.apply(e); 175090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 1760888a09821a98ac0680fad765217302858e70fa4Paul Duffin return false; 177090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 178090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 1790888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 180090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public boolean containsAll(Collection<?> collection) { 1810888a09821a98ac0680fad765217302858e70fa4Paul Duffin return containsAllImpl(this, collection); 182090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 183090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 1840888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 185090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public boolean isEmpty() { 1860888a09821a98ac0680fad765217302858e70fa4Paul Duffin return !Iterables.any(unfiltered, predicate); 187090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 188090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 1890888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 190090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public Iterator<E> iterator() { 191090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return Iterators.filter(unfiltered.iterator(), predicate); 192090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 193090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 1940888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 195090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public boolean remove(Object element) { 1960888a09821a98ac0680fad765217302858e70fa4Paul Duffin return contains(element) && unfiltered.remove(element); 197090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 198090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 1990888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 200090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public boolean removeAll(final Collection<?> collection) { 2015f3ab914effbe60066541b8e1ff9afe508d541cdIan Rogers return Iterables.removeIf(unfiltered, and(predicate, Predicates.<Object>in(collection))); 202090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 203090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 2040888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 205090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public boolean retainAll(final Collection<?> collection) { 2065f3ab914effbe60066541b8e1ff9afe508d541cdIan Rogers return Iterables.removeIf(unfiltered, and(predicate, not(Predicates.<Object>in(collection)))); 207090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 208090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 2090888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 210090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public int size() { 211090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return Iterators.size(iterator()); 212090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 213090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 2140888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 215090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public Object[] toArray() { 216090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // creating an ArrayList so filtering happens once 217090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return Lists.newArrayList(iterator()).toArray(); 218090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 219090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 2200888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 221090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public <T> T[] toArray(T[] array) { 222090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return Lists.newArrayList(iterator()).toArray(array); 223090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 224090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 225090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 226090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 227090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns a collection that applies {@code function} to each element of 228090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@code fromCollection}. The returned collection is a live view of {@code 229090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * fromCollection}; changes to one affect the other. 230090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 231090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>The returned collection's {@code add()} and {@code addAll()} methods 232090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * throw an {@link UnsupportedOperationException}. All other collection 233090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * methods are supported, as long as {@code fromCollection} supports them. 234090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 235090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>The returned collection isn't threadsafe or serializable, even if 236090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@code fromCollection} is. 237090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 238090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>When a live view is <i>not</i> needed, it may be faster to copy the 239090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * transformed collection and use the copy. 2401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 2411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>If the input {@code Collection} is known to be a {@code List}, consider 2421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@link Lists#transform}. If only an {@code Iterable} is available, use 2431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@link Iterables#transform}. 244090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 245090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public static <F, T> Collection<T> transform(Collection<F> fromCollection, 246090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Function<? super F, T> function) { 247090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new TransformedCollection<F, T>(fromCollection, function); 248090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 249090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 250090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson static class TransformedCollection<F, T> extends AbstractCollection<T> { 251090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson final Collection<F> fromCollection; 252090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson final Function<? super F, ? extends T> function; 253090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 2540888a09821a98ac0680fad765217302858e70fa4Paul Duffin TransformedCollection(Collection<F> fromCollection, 2550888a09821a98ac0680fad765217302858e70fa4Paul Duffin Function<? super F, ? extends T> function) { 256090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson this.fromCollection = checkNotNull(fromCollection); 257090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson this.function = checkNotNull(function); 258090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 259090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 2600888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public void clear() { 261090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson fromCollection.clear(); 262090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 263090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 2640888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public boolean isEmpty() { 265090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return fromCollection.isEmpty(); 266090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 267090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 2680888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public Iterator<T> iterator() { 269090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return Iterators.transform(fromCollection.iterator(), function); 270090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 271090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 2720888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public int size() { 273090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return fromCollection.size(); 274090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 275090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 276090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 2771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 2781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns {@code true} if the collection {@code self} contains all of the 2791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * elements in the collection {@code c}. 2801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 2811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>This method iterates over the specified collection {@code c}, checking 2821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * each element returned by the iterator in turn to see if it is contained in 2831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * the specified collection {@code self}. If all elements are so contained, 2841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@code true} is returned, otherwise {@code false}. 2851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 2861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @param self a collection which might contain all elements in {@code c} 2871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @param c a collection whose elements might be contained by {@code self} 2881d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 2891d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert static boolean containsAllImpl(Collection<?> self, Collection<?> c) { 2900888a09821a98ac0680fad765217302858e70fa4Paul Duffin return Iterables.all(c, Predicates.in(self)); 291090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 292090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 2931d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 2941d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * An implementation of {@link Collection#toString()}. 2951d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 2961d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert static String toStringImpl(final Collection<?> collection) { 2970888a09821a98ac0680fad765217302858e70fa4Paul Duffin StringBuilder sb 2980888a09821a98ac0680fad765217302858e70fa4Paul Duffin = newStringBuilderForCollection(collection.size()).append('['); 2990888a09821a98ac0680fad765217302858e70fa4Paul Duffin STANDARD_JOINER.appendTo( 3000888a09821a98ac0680fad765217302858e70fa4Paul Duffin sb, Iterables.transform(collection, new Function<Object, Object>() { 3010888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public Object apply(Object input) { 3020888a09821a98ac0680fad765217302858e70fa4Paul Duffin return input == collection ? "(this Collection)" : input; 3030888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 3040888a09821a98ac0680fad765217302858e70fa4Paul Duffin })); 3051d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return sb.append(']').toString(); 3061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3071d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3081d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 3091d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns best-effort-sized StringBuilder based on the given collection size. 3101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 3111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert static StringBuilder newStringBuilderForCollection(int size) { 3120888a09821a98ac0680fad765217302858e70fa4Paul Duffin checkNonnegative(size, "size"); 3131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return new StringBuilder((int) Math.min(size * 8L, Ints.MAX_POWER_OF_TWO)); 3141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 3171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Used to avoid http://bugs.sun.com/view_bug.do?bug_id=6558557 3181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 3191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert static <T> Collection<T> cast(Iterable<T> iterable) { 3201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return (Collection<T>) iterable; 3211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3237dd252788645e940eada959bdde927426e2531c9Paul Duffin static final Joiner STANDARD_JOINER = Joiner.on(", ").useForNull("null"); 3247dd252788645e940eada959bdde927426e2531c9Paul Duffin 3257dd252788645e940eada959bdde927426e2531c9Paul Duffin /** 3267dd252788645e940eada959bdde927426e2531c9Paul Duffin * Returns a {@link Collection} of all the permutations of the specified 3277dd252788645e940eada959bdde927426e2531c9Paul Duffin * {@link Iterable}. 3287dd252788645e940eada959bdde927426e2531c9Paul Duffin * 3297dd252788645e940eada959bdde927426e2531c9Paul Duffin * <p><i>Notes:</i> This is an implementation of the algorithm for 3307dd252788645e940eada959bdde927426e2531c9Paul Duffin * Lexicographical Permutations Generation, described in Knuth's "The Art of 3317dd252788645e940eada959bdde927426e2531c9Paul Duffin * Computer Programming", Volume 4, Chapter 7, Section 7.2.1.2. The 3327dd252788645e940eada959bdde927426e2531c9Paul Duffin * iteration order follows the lexicographical order. This means that 3337dd252788645e940eada959bdde927426e2531c9Paul Duffin * the first permutation will be in ascending order, and the last will be in 3347dd252788645e940eada959bdde927426e2531c9Paul Duffin * descending order. 3357dd252788645e940eada959bdde927426e2531c9Paul Duffin * 3367dd252788645e940eada959bdde927426e2531c9Paul Duffin * <p>Duplicate elements are considered equal. For example, the list [1, 1] 3377dd252788645e940eada959bdde927426e2531c9Paul Duffin * will have only one permutation, instead of two. This is why the elements 3387dd252788645e940eada959bdde927426e2531c9Paul Duffin * have to implement {@link Comparable}. 3397dd252788645e940eada959bdde927426e2531c9Paul Duffin * 3407dd252788645e940eada959bdde927426e2531c9Paul Duffin * <p>An empty iterable has only one permutation, which is an empty list. 3417dd252788645e940eada959bdde927426e2531c9Paul Duffin * 3427dd252788645e940eada959bdde927426e2531c9Paul Duffin * <p>This method is equivalent to 3437dd252788645e940eada959bdde927426e2531c9Paul Duffin * {@code Collections2.orderedPermutations(list, Ordering.natural())}. 3447dd252788645e940eada959bdde927426e2531c9Paul Duffin * 3457dd252788645e940eada959bdde927426e2531c9Paul Duffin * @param elements the original iterable whose elements have to be permuted. 3467dd252788645e940eada959bdde927426e2531c9Paul Duffin * @return an immutable {@link Collection} containing all the different 3477dd252788645e940eada959bdde927426e2531c9Paul Duffin * permutations of the original iterable. 3487dd252788645e940eada959bdde927426e2531c9Paul Duffin * @throws NullPointerException if the specified iterable is null or has any 3497dd252788645e940eada959bdde927426e2531c9Paul Duffin * null elements. 3507dd252788645e940eada959bdde927426e2531c9Paul Duffin * @since 12.0 3517dd252788645e940eada959bdde927426e2531c9Paul Duffin */ 3520888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Beta public static <E extends Comparable<? super E>> 3530888a09821a98ac0680fad765217302858e70fa4Paul Duffin Collection<List<E>> orderedPermutations(Iterable<E> elements) { 3547dd252788645e940eada959bdde927426e2531c9Paul Duffin return orderedPermutations(elements, Ordering.natural()); 3557dd252788645e940eada959bdde927426e2531c9Paul Duffin } 3567dd252788645e940eada959bdde927426e2531c9Paul Duffin 3577dd252788645e940eada959bdde927426e2531c9Paul Duffin /** 3587dd252788645e940eada959bdde927426e2531c9Paul Duffin * Returns a {@link Collection} of all the permutations of the specified 3597dd252788645e940eada959bdde927426e2531c9Paul Duffin * {@link Iterable} using the specified {@link Comparator} for establishing 3607dd252788645e940eada959bdde927426e2531c9Paul Duffin * the lexicographical ordering. 3617dd252788645e940eada959bdde927426e2531c9Paul Duffin * 3627dd252788645e940eada959bdde927426e2531c9Paul Duffin * <p>Examples: <pre> {@code 3637dd252788645e940eada959bdde927426e2531c9Paul Duffin * 3647dd252788645e940eada959bdde927426e2531c9Paul Duffin * for (List<String> perm : orderedPermutations(asList("b", "c", "a"))) { 3657dd252788645e940eada959bdde927426e2531c9Paul Duffin * println(perm); 3667dd252788645e940eada959bdde927426e2531c9Paul Duffin * } 3677dd252788645e940eada959bdde927426e2531c9Paul Duffin * // -> ["a", "b", "c"] 3687dd252788645e940eada959bdde927426e2531c9Paul Duffin * // -> ["a", "c", "b"] 3697dd252788645e940eada959bdde927426e2531c9Paul Duffin * // -> ["b", "a", "c"] 3707dd252788645e940eada959bdde927426e2531c9Paul Duffin * // -> ["b", "c", "a"] 3717dd252788645e940eada959bdde927426e2531c9Paul Duffin * // -> ["c", "a", "b"] 3727dd252788645e940eada959bdde927426e2531c9Paul Duffin * // -> ["c", "b", "a"] 3737dd252788645e940eada959bdde927426e2531c9Paul Duffin * 3747dd252788645e940eada959bdde927426e2531c9Paul Duffin * for (List<Integer> perm : orderedPermutations(asList(1, 2, 2, 1))) { 3757dd252788645e940eada959bdde927426e2531c9Paul Duffin * println(perm); 3767dd252788645e940eada959bdde927426e2531c9Paul Duffin * } 3777dd252788645e940eada959bdde927426e2531c9Paul Duffin * // -> [1, 1, 2, 2] 3787dd252788645e940eada959bdde927426e2531c9Paul Duffin * // -> [1, 2, 1, 2] 3797dd252788645e940eada959bdde927426e2531c9Paul Duffin * // -> [1, 2, 2, 1] 3807dd252788645e940eada959bdde927426e2531c9Paul Duffin * // -> [2, 1, 1, 2] 3817dd252788645e940eada959bdde927426e2531c9Paul Duffin * // -> [2, 1, 2, 1] 3827dd252788645e940eada959bdde927426e2531c9Paul Duffin * // -> [2, 2, 1, 1]}</pre> 3837dd252788645e940eada959bdde927426e2531c9Paul Duffin * 3847dd252788645e940eada959bdde927426e2531c9Paul Duffin * <p><i>Notes:</i> This is an implementation of the algorithm for 3857dd252788645e940eada959bdde927426e2531c9Paul Duffin * Lexicographical Permutations Generation, described in Knuth's "The Art of 3867dd252788645e940eada959bdde927426e2531c9Paul Duffin * Computer Programming", Volume 4, Chapter 7, Section 7.2.1.2. The 3877dd252788645e940eada959bdde927426e2531c9Paul Duffin * iteration order follows the lexicographical order. This means that 3887dd252788645e940eada959bdde927426e2531c9Paul Duffin * the first permutation will be in ascending order, and the last will be in 3897dd252788645e940eada959bdde927426e2531c9Paul Duffin * descending order. 3907dd252788645e940eada959bdde927426e2531c9Paul Duffin * 3917dd252788645e940eada959bdde927426e2531c9Paul Duffin * <p>Elements that compare equal are considered equal and no new permutations 3927dd252788645e940eada959bdde927426e2531c9Paul Duffin * are created by swapping them. 3937dd252788645e940eada959bdde927426e2531c9Paul Duffin * 3947dd252788645e940eada959bdde927426e2531c9Paul Duffin * <p>An empty iterable has only one permutation, which is an empty list. 3957dd252788645e940eada959bdde927426e2531c9Paul Duffin * 3967dd252788645e940eada959bdde927426e2531c9Paul Duffin * @param elements the original iterable whose elements have to be permuted. 3977dd252788645e940eada959bdde927426e2531c9Paul Duffin * @param comparator a comparator for the iterable's elements. 3987dd252788645e940eada959bdde927426e2531c9Paul Duffin * @return an immutable {@link Collection} containing all the different 3997dd252788645e940eada959bdde927426e2531c9Paul Duffin * permutations of the original iterable. 4007dd252788645e940eada959bdde927426e2531c9Paul Duffin * @throws NullPointerException If the specified iterable is null, has any 4017dd252788645e940eada959bdde927426e2531c9Paul Duffin * null elements, or if the specified comparator is null. 4027dd252788645e940eada959bdde927426e2531c9Paul Duffin * @since 12.0 4037dd252788645e940eada959bdde927426e2531c9Paul Duffin */ 4040888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Beta public static <E> Collection<List<E>> orderedPermutations( 4050888a09821a98ac0680fad765217302858e70fa4Paul Duffin Iterable<E> elements, Comparator<? super E> comparator) { 4067dd252788645e940eada959bdde927426e2531c9Paul Duffin return new OrderedPermutationCollection<E>(elements, comparator); 4077dd252788645e940eada959bdde927426e2531c9Paul Duffin } 4087dd252788645e940eada959bdde927426e2531c9Paul Duffin 4090888a09821a98ac0680fad765217302858e70fa4Paul Duffin private static final class OrderedPermutationCollection<E> 4100888a09821a98ac0680fad765217302858e70fa4Paul Duffin extends AbstractCollection<List<E>> { 4117dd252788645e940eada959bdde927426e2531c9Paul Duffin final ImmutableList<E> inputList; 4127dd252788645e940eada959bdde927426e2531c9Paul Duffin final Comparator<? super E> comparator; 4137dd252788645e940eada959bdde927426e2531c9Paul Duffin final int size; 4147dd252788645e940eada959bdde927426e2531c9Paul Duffin 4150888a09821a98ac0680fad765217302858e70fa4Paul Duffin OrderedPermutationCollection(Iterable<E> input, 4160888a09821a98ac0680fad765217302858e70fa4Paul Duffin Comparator<? super E> comparator) { 4177dd252788645e940eada959bdde927426e2531c9Paul Duffin this.inputList = Ordering.from(comparator).immutableSortedCopy(input); 4187dd252788645e940eada959bdde927426e2531c9Paul Duffin this.comparator = comparator; 4197dd252788645e940eada959bdde927426e2531c9Paul Duffin this.size = calculateSize(inputList, comparator); 4207dd252788645e940eada959bdde927426e2531c9Paul Duffin } 4217dd252788645e940eada959bdde927426e2531c9Paul Duffin 4227dd252788645e940eada959bdde927426e2531c9Paul Duffin /** 4237dd252788645e940eada959bdde927426e2531c9Paul Duffin * The number of permutations with repeated elements is calculated as 4247dd252788645e940eada959bdde927426e2531c9Paul Duffin * follows: 4257dd252788645e940eada959bdde927426e2531c9Paul Duffin * <ul> 4267dd252788645e940eada959bdde927426e2531c9Paul Duffin * <li>For an empty list, it is 1 (base case).</li> 4277dd252788645e940eada959bdde927426e2531c9Paul Duffin * <li>When r numbers are added to a list of n-r elements, the number of 4287dd252788645e940eada959bdde927426e2531c9Paul Duffin * permutations is increased by a factor of (n choose r).</li> 4297dd252788645e940eada959bdde927426e2531c9Paul Duffin * </ul> 4307dd252788645e940eada959bdde927426e2531c9Paul Duffin */ 4310888a09821a98ac0680fad765217302858e70fa4Paul Duffin private static <E> int calculateSize( 4320888a09821a98ac0680fad765217302858e70fa4Paul Duffin List<E> sortedInputList, Comparator<? super E> comparator) { 4337dd252788645e940eada959bdde927426e2531c9Paul Duffin long permutations = 1; 4347dd252788645e940eada959bdde927426e2531c9Paul Duffin int n = 1; 4357dd252788645e940eada959bdde927426e2531c9Paul Duffin int r = 1; 4367dd252788645e940eada959bdde927426e2531c9Paul Duffin while (n < sortedInputList.size()) { 4370888a09821a98ac0680fad765217302858e70fa4Paul Duffin int comparison = comparator.compare( 4380888a09821a98ac0680fad765217302858e70fa4Paul Duffin sortedInputList.get(n - 1), sortedInputList.get(n)); 4397dd252788645e940eada959bdde927426e2531c9Paul Duffin if (comparison < 0) { 4407dd252788645e940eada959bdde927426e2531c9Paul Duffin // We move to the next non-repeated element. 4417dd252788645e940eada959bdde927426e2531c9Paul Duffin permutations *= binomial(n, r); 4427dd252788645e940eada959bdde927426e2531c9Paul Duffin r = 0; 4437dd252788645e940eada959bdde927426e2531c9Paul Duffin if (!isPositiveInt(permutations)) { 4447dd252788645e940eada959bdde927426e2531c9Paul Duffin return Integer.MAX_VALUE; 4457dd252788645e940eada959bdde927426e2531c9Paul Duffin } 4467dd252788645e940eada959bdde927426e2531c9Paul Duffin } 4477dd252788645e940eada959bdde927426e2531c9Paul Duffin n++; 4487dd252788645e940eada959bdde927426e2531c9Paul Duffin r++; 4497dd252788645e940eada959bdde927426e2531c9Paul Duffin } 4507dd252788645e940eada959bdde927426e2531c9Paul Duffin permutations *= binomial(n, r); 4517dd252788645e940eada959bdde927426e2531c9Paul Duffin if (!isPositiveInt(permutations)) { 4527dd252788645e940eada959bdde927426e2531c9Paul Duffin return Integer.MAX_VALUE; 4537dd252788645e940eada959bdde927426e2531c9Paul Duffin } 4547dd252788645e940eada959bdde927426e2531c9Paul Duffin return (int) permutations; 4557dd252788645e940eada959bdde927426e2531c9Paul Duffin } 4567dd252788645e940eada959bdde927426e2531c9Paul Duffin 4570888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public int size() { 4587dd252788645e940eada959bdde927426e2531c9Paul Duffin return size; 4597dd252788645e940eada959bdde927426e2531c9Paul Duffin } 4607dd252788645e940eada959bdde927426e2531c9Paul Duffin 4610888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public boolean isEmpty() { 4627dd252788645e940eada959bdde927426e2531c9Paul Duffin return false; 4637dd252788645e940eada959bdde927426e2531c9Paul Duffin } 4647dd252788645e940eada959bdde927426e2531c9Paul Duffin 4650888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public Iterator<List<E>> iterator() { 4667dd252788645e940eada959bdde927426e2531c9Paul Duffin return new OrderedPermutationIterator<E>(inputList, comparator); 4677dd252788645e940eada959bdde927426e2531c9Paul Duffin } 4687dd252788645e940eada959bdde927426e2531c9Paul Duffin 4690888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public boolean contains(@Nullable Object obj) { 4707dd252788645e940eada959bdde927426e2531c9Paul Duffin if (obj instanceof List) { 4717dd252788645e940eada959bdde927426e2531c9Paul Duffin List<?> list = (List<?>) obj; 4727dd252788645e940eada959bdde927426e2531c9Paul Duffin return isPermutation(inputList, list); 4737dd252788645e940eada959bdde927426e2531c9Paul Duffin } 4747dd252788645e940eada959bdde927426e2531c9Paul Duffin return false; 4757dd252788645e940eada959bdde927426e2531c9Paul Duffin } 4767dd252788645e940eada959bdde927426e2531c9Paul Duffin 4770888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public String toString() { 4787dd252788645e940eada959bdde927426e2531c9Paul Duffin return "orderedPermutationCollection(" + inputList + ")"; 4797dd252788645e940eada959bdde927426e2531c9Paul Duffin } 4807dd252788645e940eada959bdde927426e2531c9Paul Duffin } 4817dd252788645e940eada959bdde927426e2531c9Paul Duffin 4820888a09821a98ac0680fad765217302858e70fa4Paul Duffin private static final class OrderedPermutationIterator<E> 4830888a09821a98ac0680fad765217302858e70fa4Paul Duffin extends AbstractIterator<List<E>> { 4847dd252788645e940eada959bdde927426e2531c9Paul Duffin 4857dd252788645e940eada959bdde927426e2531c9Paul Duffin List<E> nextPermutation; 4867dd252788645e940eada959bdde927426e2531c9Paul Duffin final Comparator<? super E> comparator; 4877dd252788645e940eada959bdde927426e2531c9Paul Duffin 4880888a09821a98ac0680fad765217302858e70fa4Paul Duffin OrderedPermutationIterator(List<E> list, 4890888a09821a98ac0680fad765217302858e70fa4Paul Duffin Comparator<? super E> comparator) { 4907dd252788645e940eada959bdde927426e2531c9Paul Duffin this.nextPermutation = Lists.newArrayList(list); 4917dd252788645e940eada959bdde927426e2531c9Paul Duffin this.comparator = comparator; 4927dd252788645e940eada959bdde927426e2531c9Paul Duffin } 4937dd252788645e940eada959bdde927426e2531c9Paul Duffin 4940888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override protected List<E> computeNext() { 4957dd252788645e940eada959bdde927426e2531c9Paul Duffin if (nextPermutation == null) { 4967dd252788645e940eada959bdde927426e2531c9Paul Duffin return endOfData(); 4977dd252788645e940eada959bdde927426e2531c9Paul Duffin } 4987dd252788645e940eada959bdde927426e2531c9Paul Duffin ImmutableList<E> next = ImmutableList.copyOf(nextPermutation); 4997dd252788645e940eada959bdde927426e2531c9Paul Duffin calculateNextPermutation(); 5007dd252788645e940eada959bdde927426e2531c9Paul Duffin return next; 5017dd252788645e940eada959bdde927426e2531c9Paul Duffin } 5027dd252788645e940eada959bdde927426e2531c9Paul Duffin 5037dd252788645e940eada959bdde927426e2531c9Paul Duffin void calculateNextPermutation() { 5047dd252788645e940eada959bdde927426e2531c9Paul Duffin int j = findNextJ(); 5057dd252788645e940eada959bdde927426e2531c9Paul Duffin if (j == -1) { 5067dd252788645e940eada959bdde927426e2531c9Paul Duffin nextPermutation = null; 5077dd252788645e940eada959bdde927426e2531c9Paul Duffin return; 5087dd252788645e940eada959bdde927426e2531c9Paul Duffin } 5097dd252788645e940eada959bdde927426e2531c9Paul Duffin 5107dd252788645e940eada959bdde927426e2531c9Paul Duffin int l = findNextL(j); 5117dd252788645e940eada959bdde927426e2531c9Paul Duffin Collections.swap(nextPermutation, j, l); 5127dd252788645e940eada959bdde927426e2531c9Paul Duffin int n = nextPermutation.size(); 5137dd252788645e940eada959bdde927426e2531c9Paul Duffin Collections.reverse(nextPermutation.subList(j + 1, n)); 5147dd252788645e940eada959bdde927426e2531c9Paul Duffin } 5157dd252788645e940eada959bdde927426e2531c9Paul Duffin 5167dd252788645e940eada959bdde927426e2531c9Paul Duffin int findNextJ() { 5177dd252788645e940eada959bdde927426e2531c9Paul Duffin for (int k = nextPermutation.size() - 2; k >= 0; k--) { 5180888a09821a98ac0680fad765217302858e70fa4Paul Duffin if (comparator.compare(nextPermutation.get(k), 5190888a09821a98ac0680fad765217302858e70fa4Paul Duffin nextPermutation.get(k + 1)) < 0) { 5207dd252788645e940eada959bdde927426e2531c9Paul Duffin return k; 5217dd252788645e940eada959bdde927426e2531c9Paul Duffin } 5227dd252788645e940eada959bdde927426e2531c9Paul Duffin } 5237dd252788645e940eada959bdde927426e2531c9Paul Duffin return -1; 5247dd252788645e940eada959bdde927426e2531c9Paul Duffin } 5257dd252788645e940eada959bdde927426e2531c9Paul Duffin 5267dd252788645e940eada959bdde927426e2531c9Paul Duffin int findNextL(int j) { 5277dd252788645e940eada959bdde927426e2531c9Paul Duffin E ak = nextPermutation.get(j); 5287dd252788645e940eada959bdde927426e2531c9Paul Duffin for (int l = nextPermutation.size() - 1; l > j; l--) { 5297dd252788645e940eada959bdde927426e2531c9Paul Duffin if (comparator.compare(ak, nextPermutation.get(l)) < 0) { 5307dd252788645e940eada959bdde927426e2531c9Paul Duffin return l; 5317dd252788645e940eada959bdde927426e2531c9Paul Duffin } 5327dd252788645e940eada959bdde927426e2531c9Paul Duffin } 5337dd252788645e940eada959bdde927426e2531c9Paul Duffin throw new AssertionError("this statement should be unreachable"); 5347dd252788645e940eada959bdde927426e2531c9Paul Duffin } 5357dd252788645e940eada959bdde927426e2531c9Paul Duffin } 5367dd252788645e940eada959bdde927426e2531c9Paul Duffin 5377dd252788645e940eada959bdde927426e2531c9Paul Duffin /** 5387dd252788645e940eada959bdde927426e2531c9Paul Duffin * Returns a {@link Collection} of all the permutations of the specified 5397dd252788645e940eada959bdde927426e2531c9Paul Duffin * {@link Collection}. 5407dd252788645e940eada959bdde927426e2531c9Paul Duffin * 5417dd252788645e940eada959bdde927426e2531c9Paul Duffin * <p><i>Notes:</i> This is an implementation of the Plain Changes algorithm 5427dd252788645e940eada959bdde927426e2531c9Paul Duffin * for permutations generation, described in Knuth's "The Art of Computer 5437dd252788645e940eada959bdde927426e2531c9Paul Duffin * Programming", Volume 4, Chapter 7, Section 7.2.1.2. 5447dd252788645e940eada959bdde927426e2531c9Paul Duffin * 5457dd252788645e940eada959bdde927426e2531c9Paul Duffin * <p>If the input list contains equal elements, some of the generated 5467dd252788645e940eada959bdde927426e2531c9Paul Duffin * permutations will be equal. 5477dd252788645e940eada959bdde927426e2531c9Paul Duffin * 5487dd252788645e940eada959bdde927426e2531c9Paul Duffin * <p>An empty collection has only one permutation, which is an empty list. 5497dd252788645e940eada959bdde927426e2531c9Paul Duffin * 5507dd252788645e940eada959bdde927426e2531c9Paul Duffin * @param elements the original collection whose elements have to be permuted. 5517dd252788645e940eada959bdde927426e2531c9Paul Duffin * @return an immutable {@link Collection} containing all the different 5527dd252788645e940eada959bdde927426e2531c9Paul Duffin * permutations of the original collection. 5537dd252788645e940eada959bdde927426e2531c9Paul Duffin * @throws NullPointerException if the specified collection is null or has any 5547dd252788645e940eada959bdde927426e2531c9Paul Duffin * null elements. 5557dd252788645e940eada959bdde927426e2531c9Paul Duffin * @since 12.0 5567dd252788645e940eada959bdde927426e2531c9Paul Duffin */ 5570888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Beta public static <E> Collection<List<E>> permutations( 5580888a09821a98ac0680fad765217302858e70fa4Paul Duffin Collection<E> elements) { 5597dd252788645e940eada959bdde927426e2531c9Paul Duffin return new PermutationCollection<E>(ImmutableList.copyOf(elements)); 5607dd252788645e940eada959bdde927426e2531c9Paul Duffin } 5617dd252788645e940eada959bdde927426e2531c9Paul Duffin 5620888a09821a98ac0680fad765217302858e70fa4Paul Duffin private static final class PermutationCollection<E> 5630888a09821a98ac0680fad765217302858e70fa4Paul Duffin extends AbstractCollection<List<E>> { 5647dd252788645e940eada959bdde927426e2531c9Paul Duffin final ImmutableList<E> inputList; 5657dd252788645e940eada959bdde927426e2531c9Paul Duffin 5667dd252788645e940eada959bdde927426e2531c9Paul Duffin PermutationCollection(ImmutableList<E> input) { 5677dd252788645e940eada959bdde927426e2531c9Paul Duffin this.inputList = input; 5687dd252788645e940eada959bdde927426e2531c9Paul Duffin } 5697dd252788645e940eada959bdde927426e2531c9Paul Duffin 5700888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public int size() { 5717dd252788645e940eada959bdde927426e2531c9Paul Duffin return IntMath.factorial(inputList.size()); 5727dd252788645e940eada959bdde927426e2531c9Paul Duffin } 5737dd252788645e940eada959bdde927426e2531c9Paul Duffin 5740888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public boolean isEmpty() { 5757dd252788645e940eada959bdde927426e2531c9Paul Duffin return false; 5767dd252788645e940eada959bdde927426e2531c9Paul Duffin } 5777dd252788645e940eada959bdde927426e2531c9Paul Duffin 5780888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public Iterator<List<E>> iterator() { 5797dd252788645e940eada959bdde927426e2531c9Paul Duffin return new PermutationIterator<E>(inputList); 5807dd252788645e940eada959bdde927426e2531c9Paul Duffin } 5817dd252788645e940eada959bdde927426e2531c9Paul Duffin 5820888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public boolean contains(@Nullable Object obj) { 5837dd252788645e940eada959bdde927426e2531c9Paul Duffin if (obj instanceof List) { 5847dd252788645e940eada959bdde927426e2531c9Paul Duffin List<?> list = (List<?>) obj; 5857dd252788645e940eada959bdde927426e2531c9Paul Duffin return isPermutation(inputList, list); 5867dd252788645e940eada959bdde927426e2531c9Paul Duffin } 5877dd252788645e940eada959bdde927426e2531c9Paul Duffin return false; 5887dd252788645e940eada959bdde927426e2531c9Paul Duffin } 5897dd252788645e940eada959bdde927426e2531c9Paul Duffin 5900888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public String toString() { 5917dd252788645e940eada959bdde927426e2531c9Paul Duffin return "permutations(" + inputList + ")"; 5927dd252788645e940eada959bdde927426e2531c9Paul Duffin } 5937dd252788645e940eada959bdde927426e2531c9Paul Duffin } 5947dd252788645e940eada959bdde927426e2531c9Paul Duffin 5950888a09821a98ac0680fad765217302858e70fa4Paul Duffin private static class PermutationIterator<E> 5960888a09821a98ac0680fad765217302858e70fa4Paul Duffin extends AbstractIterator<List<E>> { 5977dd252788645e940eada959bdde927426e2531c9Paul Duffin final List<E> list; 5987dd252788645e940eada959bdde927426e2531c9Paul Duffin final int[] c; 5997dd252788645e940eada959bdde927426e2531c9Paul Duffin final int[] o; 6007dd252788645e940eada959bdde927426e2531c9Paul Duffin int j; 6017dd252788645e940eada959bdde927426e2531c9Paul Duffin 6027dd252788645e940eada959bdde927426e2531c9Paul Duffin PermutationIterator(List<E> list) { 6037dd252788645e940eada959bdde927426e2531c9Paul Duffin this.list = new ArrayList<E>(list); 6047dd252788645e940eada959bdde927426e2531c9Paul Duffin int n = list.size(); 6057dd252788645e940eada959bdde927426e2531c9Paul Duffin c = new int[n]; 6067dd252788645e940eada959bdde927426e2531c9Paul Duffin o = new int[n]; 6070888a09821a98ac0680fad765217302858e70fa4Paul Duffin Arrays.fill(c, 0); 6080888a09821a98ac0680fad765217302858e70fa4Paul Duffin Arrays.fill(o, 1); 6097dd252788645e940eada959bdde927426e2531c9Paul Duffin j = Integer.MAX_VALUE; 6107dd252788645e940eada959bdde927426e2531c9Paul Duffin } 6117dd252788645e940eada959bdde927426e2531c9Paul Duffin 6120888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override protected List<E> computeNext() { 6137dd252788645e940eada959bdde927426e2531c9Paul Duffin if (j <= 0) { 6147dd252788645e940eada959bdde927426e2531c9Paul Duffin return endOfData(); 6157dd252788645e940eada959bdde927426e2531c9Paul Duffin } 6167dd252788645e940eada959bdde927426e2531c9Paul Duffin ImmutableList<E> next = ImmutableList.copyOf(list); 6177dd252788645e940eada959bdde927426e2531c9Paul Duffin calculateNextPermutation(); 6187dd252788645e940eada959bdde927426e2531c9Paul Duffin return next; 6197dd252788645e940eada959bdde927426e2531c9Paul Duffin } 6207dd252788645e940eada959bdde927426e2531c9Paul Duffin 6217dd252788645e940eada959bdde927426e2531c9Paul Duffin void calculateNextPermutation() { 6227dd252788645e940eada959bdde927426e2531c9Paul Duffin j = list.size() - 1; 6237dd252788645e940eada959bdde927426e2531c9Paul Duffin int s = 0; 6247dd252788645e940eada959bdde927426e2531c9Paul Duffin 6257dd252788645e940eada959bdde927426e2531c9Paul Duffin // Handle the special case of an empty list. Skip the calculation of the 6267dd252788645e940eada959bdde927426e2531c9Paul Duffin // next permutation. 6277dd252788645e940eada959bdde927426e2531c9Paul Duffin if (j == -1) { 6287dd252788645e940eada959bdde927426e2531c9Paul Duffin return; 6297dd252788645e940eada959bdde927426e2531c9Paul Duffin } 6307dd252788645e940eada959bdde927426e2531c9Paul Duffin 6317dd252788645e940eada959bdde927426e2531c9Paul Duffin while (true) { 6327dd252788645e940eada959bdde927426e2531c9Paul Duffin int q = c[j] + o[j]; 6337dd252788645e940eada959bdde927426e2531c9Paul Duffin if (q < 0) { 6347dd252788645e940eada959bdde927426e2531c9Paul Duffin switchDirection(); 6357dd252788645e940eada959bdde927426e2531c9Paul Duffin continue; 6367dd252788645e940eada959bdde927426e2531c9Paul Duffin } 6377dd252788645e940eada959bdde927426e2531c9Paul Duffin if (q == j + 1) { 6387dd252788645e940eada959bdde927426e2531c9Paul Duffin if (j == 0) { 6397dd252788645e940eada959bdde927426e2531c9Paul Duffin break; 6407dd252788645e940eada959bdde927426e2531c9Paul Duffin } 6417dd252788645e940eada959bdde927426e2531c9Paul Duffin s++; 6427dd252788645e940eada959bdde927426e2531c9Paul Duffin switchDirection(); 6437dd252788645e940eada959bdde927426e2531c9Paul Duffin continue; 6447dd252788645e940eada959bdde927426e2531c9Paul Duffin } 6457dd252788645e940eada959bdde927426e2531c9Paul Duffin 6467dd252788645e940eada959bdde927426e2531c9Paul Duffin Collections.swap(list, j - c[j] + s, j - q + s); 6477dd252788645e940eada959bdde927426e2531c9Paul Duffin c[j] = q; 6487dd252788645e940eada959bdde927426e2531c9Paul Duffin break; 6497dd252788645e940eada959bdde927426e2531c9Paul Duffin } 6507dd252788645e940eada959bdde927426e2531c9Paul Duffin } 6517dd252788645e940eada959bdde927426e2531c9Paul Duffin 6527dd252788645e940eada959bdde927426e2531c9Paul Duffin void switchDirection() { 6537dd252788645e940eada959bdde927426e2531c9Paul Duffin o[j] = -o[j]; 6547dd252788645e940eada959bdde927426e2531c9Paul Duffin j--; 6557dd252788645e940eada959bdde927426e2531c9Paul Duffin } 6567dd252788645e940eada959bdde927426e2531c9Paul Duffin } 6577dd252788645e940eada959bdde927426e2531c9Paul Duffin 6587dd252788645e940eada959bdde927426e2531c9Paul Duffin /** 6597dd252788645e940eada959bdde927426e2531c9Paul Duffin * Returns {@code true} if the second list is a permutation of the first. 6607dd252788645e940eada959bdde927426e2531c9Paul Duffin */ 6610888a09821a98ac0680fad765217302858e70fa4Paul Duffin private static boolean isPermutation(List<?> first, 6620888a09821a98ac0680fad765217302858e70fa4Paul Duffin List<?> second) { 6637dd252788645e940eada959bdde927426e2531c9Paul Duffin if (first.size() != second.size()) { 6647dd252788645e940eada959bdde927426e2531c9Paul Duffin return false; 6657dd252788645e940eada959bdde927426e2531c9Paul Duffin } 6660888a09821a98ac0680fad765217302858e70fa4Paul Duffin Multiset<?> firstMultiset = HashMultiset.create(first); 6670888a09821a98ac0680fad765217302858e70fa4Paul Duffin Multiset<?> secondMultiset = HashMultiset.create(second); 6680888a09821a98ac0680fad765217302858e70fa4Paul Duffin return firstMultiset.equals(secondMultiset); 6697dd252788645e940eada959bdde927426e2531c9Paul Duffin } 6701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 6717dd252788645e940eada959bdde927426e2531c9Paul Duffin private static boolean isPositiveInt(long n) { 6727dd252788645e940eada959bdde927426e2531c9Paul Duffin return n >= 0 && n <= Integer.MAX_VALUE; 6737dd252788645e940eada959bdde927426e2531c9Paul Duffin } 674090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson} 675