View Javadoc
1   /*
2    * Copyright (C) 2015 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.testing;
18  
19  import static com.google.common.base.Preconditions.checkNotNull;
20  import static com.google.common.collect.testing.Helpers.assertEqualIgnoringOrder;
21  import static com.google.common.collect.testing.Helpers.assertEqualInOrder;
22  import static com.google.common.collect.testing.Platform.format;
23  import static junit.framework.Assert.assertEquals;
24  import static junit.framework.Assert.assertFalse;
25  import static junit.framework.Assert.assertTrue;
26  import static junit.framework.Assert.fail;
27  
28  import com.google.common.annotations.GwtCompatible;
29  import com.google.common.collect.Ordering;
30  import com.google.common.primitives.Ints;
31  import java.util.ArrayList;
32  import java.util.Arrays;
33  import java.util.Comparator;
34  import java.util.EnumSet;
35  import java.util.List;
36  import java.util.Spliterator;
37  import java.util.function.Consumer;
38  import java.util.function.Supplier;
39  import javax.annotation.Nullable;
40  
41  /**
42   * Tester for {@code Spliterator} implementations.
43   */
44  @GwtCompatible
45  public final class SpliteratorTester<E> {
46    /**
47     * Return type from "contains the following elements" assertions.
48     */
49    public interface Ordered {
50      /**
51       * Attests that the expected values must not just be present but must be present in the order
52       * they were given.
53       */
54      void inOrder();
55    }
56  
57    /**
58     * Different ways of decomposing a Spliterator, all of which must produce the same
59     * elements (up to ordering, if Spliterator.ORDERED is not present).
60     */
61    enum SpliteratorDecompositionStrategy {
62      NO_SPLIT_FOR_EACH_REMAINING {
63        @Override
64        <E> void forEach(Spliterator<E> spliterator, Consumer<? super E> consumer) {
65          spliterator.forEachRemaining(consumer);
66        }
67      },
68      NO_SPLIT_TRY_ADVANCE {
69        @Override
70        <E> void forEach(Spliterator<E> spliterator, Consumer<? super E> consumer) {
71          while (spliterator.tryAdvance(consumer)) {
72            // do nothing
73          }
74        }
75      },
76      MAXIMUM_SPLIT {
77        @Override
78        <E> void forEach(Spliterator<E> spliterator, Consumer<? super E> consumer) {
79          for (Spliterator<E> prefix = trySplitTestingSize(spliterator);
80              prefix != null;
81              prefix = trySplitTestingSize(spliterator)) {
82            forEach(prefix, consumer);
83          }
84          long size = spliterator.getExactSizeIfKnown();
85          long[] counter = {0};
86          spliterator.forEachRemaining(e -> {
87            consumer.accept(e);
88            counter[0]++;
89          });
90          if (size >= 0) {
91            assertEquals(size, counter[0]);
92          }
93        }
94      },
95      ALTERNATE_ADVANCE_AND_SPLIT {
96        @Override
97        <E> void forEach(Spliterator<E> spliterator, Consumer<? super E> consumer) {
98          while (spliterator.tryAdvance(consumer)) {
99            Spliterator<E> prefix = trySplitTestingSize(spliterator);
100           if (prefix != null) {
101             forEach(prefix, consumer);
102           }
103         }
104       }
105     };
106 
107     abstract <E> void forEach(Spliterator<E> spliterator, Consumer<? super E> consumer);
108   }
109 
110   @Nullable
111   private static <E> Spliterator<E> trySplitTestingSize(Spliterator<E> spliterator) {
112     boolean subsized = spliterator.hasCharacteristics(Spliterator.SUBSIZED);
113     long originalSize = spliterator.estimateSize();
114     Spliterator<E> trySplit = spliterator.trySplit();
115     if (spliterator.estimateSize() > originalSize) {
116       fail(
117           format(
118               "estimated size of spliterator after trySplit (%s) is larger than original size (%s)",
119               spliterator.estimateSize(),
120               originalSize));
121     }
122     if (trySplit != null) {
123       if (trySplit.estimateSize() > originalSize) {
124         fail(
125             format(
126                 "estimated size of trySplit result (%s) is larger than original size (%s)",
127                 trySplit.estimateSize(),
128                 originalSize));
129       }
130     }
131     if (subsized) {
132       if (trySplit != null) {
133         assertEquals(
134             "sum of estimated sizes of trySplit and original spliterator after trySplit",
135             originalSize,
136             trySplit.estimateSize() + spliterator.estimateSize());
137       } else {
138         assertEquals(
139             "estimated size of spliterator after failed trySplit",
140             originalSize,
141             spliterator.estimateSize());
142       }
143     }
144     return trySplit;
145   }
146 
147   public static <E> SpliteratorTester<E> of(Supplier<Spliterator<E>> spliteratorSupplier) {
148     return new SpliteratorTester<E>(spliteratorSupplier);
149   }
150 
151   private final Supplier<Spliterator<E>> spliteratorSupplier;
152 
153   private SpliteratorTester(Supplier<Spliterator<E>> spliteratorSupplier) {
154     this.spliteratorSupplier = checkNotNull(spliteratorSupplier);
155   }
156 
157   @SafeVarargs
158   public final Ordered expect(Object... elements) {
159     return expect(Arrays.asList(elements));
160   }
161 
162   public final Ordered expect(Iterable<?> elements) {
163     List<List<E>> resultsForAllStrategies = new ArrayList<>();
164     Spliterator<E> spliterator = spliteratorSupplier.get();
165     int characteristics = spliterator.characteristics();
166     long estimatedSize = spliterator.estimateSize();
167     for (SpliteratorDecompositionStrategy strategy :
168         EnumSet.allOf(SpliteratorDecompositionStrategy.class)) {
169       List<E> resultsForStrategy = new ArrayList<>();
170       strategy.forEach(spliteratorSupplier.get(), resultsForStrategy::add);
171 
172       // TODO(cpovirk): better failure messages
173       if ((characteristics & Spliterator.NONNULL) != 0) {
174         assertFalse(resultsForStrategy.contains(null));
175       }
176       if ((characteristics & Spliterator.SORTED) != 0) {
177         Comparator<? super E> comparator = spliterator.getComparator();
178         if (comparator == null) {
179           comparator = (Comparator) Comparator.naturalOrder();
180         }
181         assertTrue(Ordering.from(comparator).isOrdered(resultsForStrategy));
182       }
183       if ((characteristics & Spliterator.SIZED) != 0) {
184         assertEquals(Ints.checkedCast(estimatedSize), resultsForStrategy.size());
185       }
186 
187       assertEqualIgnoringOrder(elements, resultsForStrategy);
188       resultsForAllStrategies.add(resultsForStrategy);
189     }
190     return new Ordered() {
191       @Override
192       public void inOrder() {
193         resultsForAllStrategies.forEach(
194             resultsForStrategy -> assertEqualInOrder(elements, resultsForStrategy));
195       }
196     };
197   }
198 }