Home | History | Annotate | Download | only in collect 
      1 /*
      2  * Copyright (C) 2008 The Guava Authors
      3  *
      4  * Licensed under the Apache License, Version 2.0 (the "License");
      5  * you may not use this file except in compliance with the License.
      6  * You may obtain a copy of the License at
      7  *
      8  * http://www.apache.org/licenses/LICENSE-2.0
      9  *
     10  * Unless required by applicable law or agreed to in writing, software
     11  * distributed under the License is distributed on an "AS IS" BASIS,
     12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
     13  * See the License for the specific language governing permissions and
     14  * limitations under the License.
     15  */
     16 
     17 package com.google.common.collect;
     18 
     19 import static com.google.common.collect.Iterables.concat;
     20 import static com.google.common.collect.Lists.newArrayList;
     21 import static com.google.common.truth.Truth.assertThat;
     22 import static java.util.Arrays.asList;
     23 import static java.util.Collections.nCopies;
     24 
     25 import com.google.common.annotations.GwtCompatible;
     26 import com.google.common.base.Function;
     27 import com.google.common.base.Predicate;
     28 
     29 import junit.framework.TestCase;
     30 
     31 import java.util.Collection;
     32 import java.util.Collections;
     33 import java.util.Iterator;
     34 import java.util.List;
     35 import java.util.NoSuchElementException;
     36 
     37 /**
     38  * Tests for {@link Collections2}.
     39  *
     40  * @author Chris Povirk
     41  * @author Jared Levy
     42  */
     43 @GwtCompatible(emulated = true)
     44 public class Collections2Test extends TestCase {
     45 
     46   static final Predicate<String> NOT_YYY_ZZZ = new Predicate<String>() {
     47       @Override
     48       public boolean apply(String input) {
     49         return !"yyy".equals(input) && !"zzz".equals(input);
     50       }
     51   };
     52 
     53   static final Predicate<String> LENGTH_1 = new Predicate<String>() {
     54     @Override
     55     public boolean apply(String input) {
     56       return input.length() == 1;
     57     }
     58   };
     59 
     60   static final Predicate<String> STARTS_WITH_VOWEL = new Predicate<String>() {
     61     @Override
     62     public boolean apply(String input) {
     63       return asList('a', 'e', 'i', 'o', 'u').contains(input.charAt(0));
     64     }
     65   };
     66 
     67   private static final Function<String, String> REMOVE_FIRST_CHAR
     68       = new Function<String, String>() {
     69         @Override
     70         public String apply(String from) {
     71           return ((from == null) || "".equals(from))
     72               ? null : from.substring(1);
     73         }
     74       };
     75 
     76   public void testOrderedPermutationSetEmpty() {
     77     List<Integer> list = newArrayList();
     78     Collection<List<Integer>> permutationSet =
     79         Collections2.orderedPermutations(list);
     80 
     81     assertEquals(1, permutationSet.size());
     82     assertThat(permutationSet).has().item(list);
     83 
     84     Iterator<List<Integer>> permutations = permutationSet.iterator();
     85 
     86     assertNextPermutation(Lists.<Integer>newArrayList(), permutations);
     87     assertNoMorePermutations(permutations);
     88   }
     89 
     90   public void testOrderedPermutationSetOneElement() {
     91     List<Integer> list = newArrayList(1);
     92     Iterator<List<Integer>> permutations =
     93         Collections2.orderedPermutations(list).iterator();
     94 
     95     assertNextPermutation(newArrayList(1), permutations);
     96     assertNoMorePermutations(permutations);
     97   }
     98 
     99   public void testOrderedPermutationSetThreeElements() {
    100     List<String> list = newArrayList("b", "a", "c");
    101     Iterator<List<String>> permutations =
    102         Collections2.orderedPermutations(list).iterator();
    103 
    104     assertNextPermutation(newArrayList("a", "b", "c"), permutations);
    105     assertNextPermutation(newArrayList("a", "c", "b"), permutations);
    106     assertNextPermutation(newArrayList("b", "a", "c"), permutations);
    107     assertNextPermutation(newArrayList("b", "c", "a"), permutations);
    108     assertNextPermutation(newArrayList("c", "a", "b"), permutations);
    109     assertNextPermutation(newArrayList("c", "b", "a"), permutations);
    110     assertNoMorePermutations(permutations);
    111   }
    112 
    113   public void testOrderedPermutationSetRepeatedElements() {
    114     List<Integer> list = newArrayList(1, 1, 2, 2);
    115     Iterator<List<Integer>> permutations =
    116         Collections2.orderedPermutations(list, Ordering.natural()).iterator();
    117 
    118     assertNextPermutation(newArrayList(1, 1, 2, 2), permutations);
    119     assertNextPermutation(newArrayList(1, 2, 1, 2), permutations);
    120     assertNextPermutation(newArrayList(1, 2, 2, 1), permutations);
    121     assertNextPermutation(newArrayList(2, 1, 1, 2), permutations);
    122     assertNextPermutation(newArrayList(2, 1, 2, 1), permutations);
    123     assertNextPermutation(newArrayList(2, 2, 1, 1), permutations);
    124     assertNoMorePermutations(permutations);
    125   }
    126 
    127   public void testOrderedPermutationSetRepeatedElementsSize() {
    128     List<Integer> list = newArrayList(1, 1, 1, 1, 2, 2, 3);
    129     Collection<List<Integer>> permutations =
    130         Collections2.orderedPermutations(list, Ordering.natural());
    131 
    132     assertPermutationsCount(105, permutations);
    133   }
    134 
    135   public void testOrderedPermutationSetSizeOverflow() {
    136     // 12 elements won't overflow
    137     assertEquals(479001600 /*12!*/, Collections2.orderedPermutations(
    138         newArrayList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)).size());
    139     // 13 elements overflow an int
    140     assertEquals(Integer.MAX_VALUE, Collections2.orderedPermutations(
    141         newArrayList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13)).size());
    142     // 21 elements overflow a long
    143     assertEquals(Integer.MAX_VALUE, Collections2.orderedPermutations(
    144         newArrayList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
    145             16, 17, 18, 19, 20, 21)).size());
    146 
    147     // Almost force an overflow in the binomial coefficient calculation
    148     assertEquals(1391975640 /*C(34,14)*/, Collections2.orderedPermutations(
    149         concat(nCopies(20, 1), nCopies(14, 2))).size());
    150     // Do force an overflow in the binomial coefficient calculation
    151     assertEquals(Integer.MAX_VALUE, Collections2.orderedPermutations(
    152         concat(nCopies(21, 1), nCopies(14, 2))).size());
    153   }
    154 
    155   public void testOrderedPermutationSetContains() {
    156     List<Integer> list = newArrayList(3, 2, 1);
    157     Collection<List<Integer>> permutationSet =
    158         Collections2.orderedPermutations(list);
    159 
    160     assertTrue(permutationSet.contains(newArrayList(1, 2, 3)));
    161     assertTrue(permutationSet.contains(newArrayList(2, 3, 1)));
    162     assertFalse(permutationSet.contains(newArrayList(1, 2)));
    163     assertFalse(permutationSet.contains(newArrayList(1, 1, 2, 3)));
    164     assertFalse(permutationSet.contains(newArrayList(1, 2, 3, 4)));
    165     assertFalse(permutationSet.contains(null));
    166   }
    167 
    168   public void testPermutationSetEmpty() {
    169     Collection<List<Integer>> permutationSet =
    170         Collections2.permutations(Collections.<Integer>emptyList());
    171 
    172     assertEquals(1, permutationSet.size());
    173     assertTrue(permutationSet.contains(Collections.<Integer> emptyList()));
    174 
    175     Iterator<List<Integer>> permutations = permutationSet.iterator();
    176     assertNextPermutation(Collections.<Integer> emptyList(), permutations);
    177     assertNoMorePermutations(permutations);
    178   }
    179 
    180   public void testPermutationSetOneElement() {
    181     Iterator<List<Integer>> permutations =
    182         Collections2.permutations(Collections.<Integer> singletonList(1))
    183         .iterator();
    184     assertNextPermutation(newArrayList(1), permutations);
    185     assertNoMorePermutations(permutations);
    186   }
    187 
    188   public void testPermutationSetTwoElements() {
    189     Iterator<List<Integer>> permutations = Collections2.permutations(
    190         newArrayList(1, 2)).iterator();
    191     assertNextPermutation(newArrayList(1, 2), permutations);
    192     assertNextPermutation(newArrayList(2, 1), permutations);
    193     assertNoMorePermutations(permutations);
    194   }
    195 
    196   public void testPermutationSetThreeElements() {
    197     Iterator<List<Integer>> permutations = Collections2.permutations(
    198         newArrayList(1, 2, 3)).iterator();
    199     assertNextPermutation(newArrayList(1, 2, 3), permutations);
    200     assertNextPermutation(newArrayList(1, 3, 2), permutations);
    201     assertNextPermutation(newArrayList(3, 1, 2), permutations);
    202 
    203     assertNextPermutation(newArrayList(3, 2, 1), permutations);
    204     assertNextPermutation(newArrayList(2, 3, 1), permutations);
    205     assertNextPermutation(newArrayList(2, 1, 3), permutations);
    206     assertNoMorePermutations(permutations);
    207   }
    208 
    209   public void testPermutationSetThreeElementsOutOfOrder() {
    210     Iterator<List<Integer>> permutations = Collections2.permutations(
    211         newArrayList(3, 2, 1)).iterator();
    212     assertNextPermutation(newArrayList(3, 2, 1), permutations);
    213     assertNextPermutation(newArrayList(3, 1, 2), permutations);
    214     assertNextPermutation(newArrayList(1, 3, 2), permutations);
    215 
    216     assertNextPermutation(newArrayList(1, 2, 3), permutations);
    217     assertNextPermutation(newArrayList(2, 1, 3), permutations);
    218     assertNextPermutation(newArrayList(2, 3, 1), permutations);
    219     assertNoMorePermutations(permutations);
    220   }
    221 
    222   public void testPermutationSetThreeRepeatedElements() {
    223     Iterator<List<Integer>> permutations = Collections2.permutations(
    224         newArrayList(1, 1, 2)).iterator();
    225     assertNextPermutation(newArrayList(1, 1, 2), permutations);
    226     assertNextPermutation(newArrayList(1, 2, 1), permutations);
    227     assertNextPermutation(newArrayList(2, 1, 1), permutations);
    228     assertNextPermutation(newArrayList(2, 1, 1), permutations);
    229     assertNextPermutation(newArrayList(1, 2, 1), permutations);
    230     assertNextPermutation(newArrayList(1, 1, 2), permutations);
    231     assertNoMorePermutations(permutations);
    232   }
    233 
    234   public void testPermutationSetFourElements() {
    235     Iterator<List<Integer>> permutations = Collections2.permutations(
    236         newArrayList(1, 2, 3, 4)).iterator();
    237     assertNextPermutation(newArrayList(1, 2, 3, 4), permutations);
    238     assertNextPermutation(newArrayList(1, 2, 4, 3), permutations);
    239     assertNextPermutation(newArrayList(1, 4, 2, 3), permutations);
    240     assertNextPermutation(newArrayList(4, 1, 2, 3), permutations);
    241 
    242     assertNextPermutation(newArrayList(4, 1, 3, 2), permutations);
    243     assertNextPermutation(newArrayList(1, 4, 3, 2), permutations);
    244     assertNextPermutation(newArrayList(1, 3, 4, 2), permutations);
    245     assertNextPermutation(newArrayList(1, 3, 2, 4), permutations);
    246 
    247     assertNextPermutation(newArrayList(3, 1, 2, 4), permutations);
    248     assertNextPermutation(newArrayList(3, 1, 4, 2), permutations);
    249     assertNextPermutation(newArrayList(3, 4, 1, 2), permutations);
    250     assertNextPermutation(newArrayList(4, 3, 1, 2), permutations);
    251 
    252     assertNextPermutation(newArrayList(4, 3, 2, 1), permutations);
    253     assertNextPermutation(newArrayList(3, 4, 2, 1), permutations);
    254     assertNextPermutation(newArrayList(3, 2, 4, 1), permutations);
    255     assertNextPermutation(newArrayList(3, 2, 1, 4), permutations);
    256 
    257     assertNextPermutation(newArrayList(2, 3, 1, 4), permutations);
    258     assertNextPermutation(newArrayList(2, 3, 4, 1), permutations);
    259     assertNextPermutation(newArrayList(2, 4, 3, 1), permutations);
    260     assertNextPermutation(newArrayList(4, 2, 3, 1), permutations);
    261 
    262     assertNextPermutation(newArrayList(4, 2, 1, 3), permutations);
    263     assertNextPermutation(newArrayList(2, 4, 1, 3), permutations);
    264     assertNextPermutation(newArrayList(2, 1, 4, 3), permutations);
    265     assertNextPermutation(newArrayList(2, 1, 3, 4), permutations);
    266     assertNoMorePermutations(permutations);
    267   }
    268 
    269   public void testPermutationSetSize() {
    270     assertPermutationsCount(1,
    271         Collections2.permutations(Collections.<Integer>emptyList()));
    272     assertPermutationsCount(1, Collections2.permutations(newArrayList(1)));
    273     assertPermutationsCount(2, Collections2.permutations(newArrayList(1, 2)));
    274     assertPermutationsCount(6,
    275         Collections2.permutations(newArrayList(1, 2, 3)));
    276     assertPermutationsCount(5040,
    277         Collections2.permutations(newArrayList(1, 2, 3, 4, 5, 6, 7)));
    278     assertPermutationsCount(40320,
    279         Collections2.permutations(newArrayList(1, 2, 3, 4, 5, 6, 7, 8)));
    280   }
    281 
    282   public void testPermutationSetSizeOverflow() {
    283     // 13 elements overflow an int
    284     assertEquals(Integer.MAX_VALUE, Collections2.permutations(newArrayList(
    285         1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13)).size());
    286     // 21 elements overflow a long
    287     assertEquals(Integer.MAX_VALUE, Collections2.orderedPermutations(
    288         newArrayList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
    289             16, 17, 18, 19, 20)).size());
    290     assertEquals(Integer.MAX_VALUE, Collections2.orderedPermutations(
    291         newArrayList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
    292             16, 17, 18, 19, 20, 21)).size());
    293   }
    294 
    295   public void testPermutationSetContains() {
    296     List<Integer> list = newArrayList(3, 2, 1);
    297     Collection<List<Integer>> permutationSet =
    298         Collections2.permutations(list);
    299 
    300     assertTrue(permutationSet.contains(newArrayList(1, 2, 3)));
    301     assertTrue(permutationSet.contains(newArrayList(2, 3, 1)));
    302     assertFalse(permutationSet.contains(newArrayList(1, 2)));
    303     assertFalse(permutationSet.contains(newArrayList(1, 1, 2, 3)));
    304     assertFalse(permutationSet.contains(newArrayList(1, 2, 3, 4)));
    305     assertFalse(permutationSet.contains(null));
    306   }
    307 
    308   private <T> void assertNextPermutation(List<T> expectedPermutation,
    309       Iterator<List<T>> permutations) {
    310     assertTrue("Expected another permutation, but there was none.",
    311         permutations.hasNext());
    312     assertEquals(expectedPermutation, permutations.next());
    313   }
    314 
    315   private <T> void assertNoMorePermutations(
    316       Iterator<List<T>> permutations) {
    317     assertFalse("Expected no more permutations, but there was one.",
    318         permutations.hasNext());
    319     try {
    320       permutations.next();
    321       fail("Expected NoSuchElementException.");
    322     } catch (NoSuchElementException expected) {}
    323   }
    324 
    325   private <T> void assertPermutationsCount(int expected,
    326       Collection<List<T>> permutationSet) {
    327     assertEquals(expected, permutationSet.size());
    328     Iterator<List<T>> permutations = permutationSet.iterator();
    329     for (int i = 0; i < expected; i++) {
    330       assertTrue(permutations.hasNext());
    331       permutations.next();
    332     }
    333     assertNoMorePermutations(permutations);
    334   }
    335 
    336   public void testToStringImplWithNullEntries() throws Exception {
    337     List<String> list = Lists.newArrayList();
    338     list.add("foo");
    339     list.add(null);
    340 
    341     assertEquals(list.toString(), Collections2.toStringImpl(list));
    342   }
    343 
    344 }
    345 
    346