1 /*
2 * Copyright (c) 2012, 2013, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation. Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25 package java.util.stream;
26
27 import java.util.Collections;
28 import java.util.EnumSet;
29 import java.util.Objects;
30 import java.util.Set;
31 import java.util.function.BiConsumer;
32 import java.util.function.BinaryOperator;
33 import java.util.function.Function;
34 import java.util.function.Supplier;
35
36 /**
37 * A <a href="package-summary.html#Reduction">mutable reduction operation</a> that
38 * accumulates input elements into a mutable result container, optionally transforming
39 * the accumulated result into a final representation after all input elements
40 * have been processed. Reduction operations can be performed either sequentially
41 * or in parallel.
42 *
43 * <p>Examples of mutable reduction operations include:
44 * accumulating elements into a {@code Collection}; concatenating
45 * strings using a {@code StringBuilder}; computing summary information about
46 * elements such as sum, min, max, or average; computing "pivot table" summaries
47 * such as "maximum valued transaction by seller", etc. The class {@link Collectors}
48 * provides implementations of many common mutable reductions.
49 *
50 * <p>A {@code Collector} is specified by four functions that work together to
51 * accumulate entries into a mutable result container, and optionally perform
52 * a final transform on the result. They are: <ul>
53 * <li>creation of a new result container ({@link #supplier()})</li>
54 * <li>incorporating a new data element into a result container ({@link #accumulator()})</li>
55 * <li>combining two result containers into one ({@link #combiner()})</li>
56 * <li>performing an optional final transform on the container ({@link #finisher()})</li>
57 * </ul>
58 *
59 * <p>Collectors also have a set of characteristics, such as
60 * {@link Characteristics#CONCURRENT}, that provide hints that can be used by a
61 * reduction implementation to provide better performance.
62 *
63 * <p>A sequential implementation of a reduction using a collector would
64 * create a single result container using the supplier function, and invoke the
65 * accumulator function once for each input element. A parallel implementation
66 * would partition the input, create a result container for each partition,
67 * accumulate the contents of each partition into a subresult for that partition,
68 * and then use the combiner function to merge the subresults into a combined
69 * result.
70 *
71 * <p>To ensure that sequential and parallel executions produce equivalent
72 * results, the collector functions must satisfy an <em>identity</em> and an
73 * <a href="package-summary.html#Associativity">associativity</a> constraints.
74 *
75 * <p>The identity constraint says that for any partially accumulated result,
76 * combining it with an empty result container must produce an equivalent
77 * result. That is, for a partially accumulated result {@code a} that is the
78 * result of any series of accumulator and combiner invocations, {@code a} must
79 * be equivalent to {@code combiner.apply(a, supplier.get())}.
80 *
81 * <p>The associativity constraint says that splitting the computation must
82 * produce an equivalent result. That is, for any input elements {@code t1}
83 * and {@code t2}, the results {@code r1} and {@code r2} in the computation
84 * below must be equivalent:
85 * <pre>{@code
86 * A a1 = supplier.get();
87 * accumulator.accept(a1, t1);
88 * accumulator.accept(a1, t2);
89 * R r1 = finisher.apply(a1); // result without splitting
90 *
91 * A a2 = supplier.get();
92 * accumulator.accept(a2, t1);
93 * A a3 = supplier.get();
94 * accumulator.accept(a3, t2);
95 * R r2 = finisher.apply(combiner.apply(a2, a3)); // result with splitting
96 * } </pre>
97 *
98 * <p>For collectors that do not have the {@code UNORDERED} characteristic,
99 * two accumulated results {@code a1} and {@code a2} are equivalent if
100 * {@code finisher.apply(a1).equals(finisher.apply(a2))}. For unordered
101 * collectors, equivalence is relaxed to allow for non-equality related to
102 * differences in order. (For example, an unordered collector that accumulated
103 * elements to a {@code List} would consider two lists equivalent if they
104 * contained the same elements, ignoring order.)
105 *
106 * <p>Libraries that implement reduction based on {@code Collector}, such as
107 * {@link Stream#collect(Collector)}, must adhere to the following constraints:
108 * <ul>
109 * <li>The first argument passed to the accumulator function, both
110 * arguments passed to the combiner function, and the argument passed to the
111 * finisher function must be the result of a previous invocation of the
112 * result supplier, accumulator, or combiner functions.</li>
113 * <li>The implementation should not do anything with the result of any of
114 * the result supplier, accumulator, or combiner functions other than to
115 * pass them again to the accumulator, combiner, or finisher functions,
116 * or return them to the caller of the reduction operation.</li>
117 * <li>If a result is passed to the combiner or finisher
118 * function, and the same object is not returned from that function, it is
119 * never used again.</li>
120 * <li>Once a result is passed to the combiner or finisher function, it
121 * is never passed to the accumulator function again.</li>
122 * <li>For non-concurrent collectors, any result returned from the result
123 * supplier, accumulator, or combiner functions must be serially
124 * thread-confined. This enables collection to occur in parallel without
125 * the {@code Collector} needing to implement any additional synchronization.
126 * The reduction implementation must manage that the input is properly
127 * partitioned, that partitions are processed in isolation, and combining
128 * happens only after accumulation is complete.</li>
129 * <li>For concurrent collectors, an implementation is free to (but not
130 * required to) implement reduction concurrently. A concurrent reduction
131 * is one where the accumulator function is called concurrently from
132 * multiple threads, using the same concurrently-modifiable result container,
133 * rather than keeping the result isolated during accumulation.
134 * A concurrent reduction should only be applied if the collector has the
135 * {@link Characteristics#UNORDERED} characteristics or if the
136 * originating data is unordered.</li>
137 * </ul>
138 *
139 * <p>In addition to the predefined implementations in {@link Collectors}, the
140 * static factory methods {@link #of(Supplier, BiConsumer, BinaryOperator, Characteristics...)}
141 * can be used to construct collectors. For example, you could create a collector
142 * that accumulates widgets into a {@code TreeSet} with:
143 *
144 * <pre>{@code
145 * Collector<Widget, ?, TreeSet<Widget>> intoSet =
146 * Collector.of(TreeSet::new, TreeSet::add,
147 * (left, right) -> { left.addAll(right); return left; });
148 * }</pre>
149 *
150 * (This behavior is also implemented by the predefined collector
151 * {@link Collectors#toCollection(Supplier)}).
152 *
153 * @apiNote
154 * Performing a reduction operation with a {@code Collector} should produce a
155 * result equivalent to:
156 * <pre>{@code
157 * R container = collector.supplier().get();
158 * for (T t : data)
159 * collector.accumulator().accept(container, t);
160 * return collector.finisher().apply(container);
161 * }</pre>
162 *
163 * <p>However, the library is free to partition the input, perform the reduction
164 * on the partitions, and then use the combiner function to combine the partial
165 * results to achieve a parallel reduction. (Depending on the specific reduction
166 * operation, this may perform better or worse, depending on the relative cost
167 * of the accumulator and combiner functions.)
168 *
169 * <p>Collectors are designed to be <em>composed</em>; many of the methods
170 * in {@link Collectors} are functions that take a collector and produce
171 * a new collector. For example, given the following collector that computes
172 * the sum of the salaries of a stream of employees:
173 *
174 * <pre>{@code
175 * Collector<Employee, ?, Integer> summingSalaries
176 * = Collectors.summingInt(Employee::getSalary))
177 * }</pre>
178 *
179 * If we wanted to create a collector to tabulate the sum of salaries by
180 * department, we could reuse the "sum of salaries" logic using
181 * {@link Collectors#groupingBy(Function, Collector)}:
182 *
183 * <pre>{@code
184 * Collector<Employee, ?, Map<Department, Integer>> summingSalariesByDept
185 * = Collectors.groupingBy(Employee::getDepartment, summingSalaries);
186 * }</pre>
187 *
188 * @see Stream#collect(Collector)
189 * @see Collectors
190 *
191 * @param <T> the type of input elements to the reduction operation
192 * @param <A> the mutable accumulation type of the reduction operation (often
193 * hidden as an implementation detail)
194 * @param <R> the result type of the reduction operation
195 * @since 1.8
196 */
197 public interface Collector<T, A, R> {
198 /**
199 * A function that creates and returns a new mutable result container.
200 *
201 * @return a function which returns a new, mutable result container
202 */
203 Supplier<A> supplier();
204
205 /**
206 * A function that folds a value into a mutable result container.
207 *
208 * @return a function which folds a value into a mutable result container
209 */
210 BiConsumer<A, T> accumulator();
211
212 /**
213 * A function that accepts two partial results and merges them. The
214 * combiner function may fold state from one argument into the other and
215 * return that, or may return a new result container.
216 *
217 * @return a function which combines two partial results into a combined
218 * result
219 */
220 BinaryOperator<A> combiner();
221
222 /**
223 * Perform the final transformation from the intermediate accumulation type
224 * {@code A} to the final result type {@code R}.
225 *
226 * <p>If the characteristic {@code IDENTITY_FINISH} is
227 * set, this function may be presumed to be an identity transform with an
228 * unchecked cast from {@code A} to {@code R}.
229 *
230 * @return a function which transforms the intermediate result to the final
231 * result
232 */
233 Function<A, R> finisher();
234
235 /**
236 * Returns a {@code Set} of {@code Collector.Characteristics} indicating
237 * the characteristics of this Collector. This set should be immutable.
238 *
239 * @return an immutable set of collector characteristics
240 */
241 Set<Characteristics> characteristics();
242
243 /**
244 * Returns a new {@code Collector} described by the given {@code supplier},
245 * {@code accumulator}, and {@code combiner} functions. The resulting
246 * {@code Collector} has the {@code Collector.Characteristics.IDENTITY_FINISH}
247 * characteristic.
248 *
249 * @param supplier The supplier function for the new collector
250 * @param accumulator The accumulator function for the new collector
251 * @param combiner The combiner function for the new collector
252 * @param characteristics The collector characteristics for the new
253 * collector
254 * @param <T> The type of input elements for the new collector
255 * @param <R> The type of intermediate accumulation result, and final result,
256 * for the new collector
257 * @throws NullPointerException if any argument is null
258 * @return the new {@code Collector}
259 */
260 public static<T, R> Collector<T, R, R> of(Supplier<R> supplier,
261 BiConsumer<R, T> accumulator,
262 BinaryOperator<R> combiner,
263 Characteristics... characteristics) {
264 Objects.requireNonNull(supplier);
265 Objects.requireNonNull(accumulator);
266 Objects.requireNonNull(combiner);
267 Objects.requireNonNull(characteristics);
268 Set<Characteristics> cs = (characteristics.length == 0)
269 ? Collectors.CH_ID
270 : Collections.unmodifiableSet(EnumSet.of(Collector.Characteristics.IDENTITY_FINISH,
271 characteristics));
272 return new Collectors.CollectorImpl<>(supplier, accumulator, combiner, cs);
273 }
274
275 /**
276 * Returns a new {@code Collector} described by the given {@code supplier},
277 * {@code accumulator}, {@code combiner}, and {@code finisher} functions.
278 *
279 * @param supplier The supplier function for the new collector
280 * @param accumulator The accumulator function for the new collector
281 * @param combiner The combiner function for the new collector
282 * @param finisher The finisher function for the new collector
283 * @param characteristics The collector characteristics for the new
284 * collector
285 * @param <T> The type of input elements for the new collector
286 * @param <A> The intermediate accumulation type of the new collector
287 * @param <R> The final result type of the new collector
288 * @throws NullPointerException if any argument is null
289 * @return the new {@code Collector}
290 */
291 public static<T, A, R> Collector<T, A, R> of(Supplier<A> supplier,
292 BiConsumer<A, T> accumulator,
293 BinaryOperator<A> combiner,
294 Function<A, R> finisher,
295 Characteristics... characteristics) {
296 Objects.requireNonNull(supplier);
297 Objects.requireNonNull(accumulator);
298 Objects.requireNonNull(combiner);
299 Objects.requireNonNull(finisher);
300 Objects.requireNonNull(characteristics);
301 Set<Characteristics> cs = Collectors.CH_NOID;
302 if (characteristics.length > 0) {
303 cs = EnumSet.noneOf(Characteristics.class);
304 Collections.addAll(cs, characteristics);
305 cs = Collections.unmodifiableSet(cs);
306 }
307 return new Collectors.CollectorImpl<>(supplier, accumulator, combiner, finisher, cs);
308 }
309
310 /**
311 * Characteristics indicating properties of a {@code Collector}, which can
312 * be used to optimize reduction implementations.
313 */
314 enum Characteristics {
315 /**
316 * Indicates that this collector is <em>concurrent</em>, meaning that
317 * the result container can support the accumulator function being
318 * called concurrently with the same result container from multiple
319 * threads.
320 *
321 * <p>If a {@code CONCURRENT} collector is not also {@code UNORDERED},
322 * then it should only be evaluated concurrently if applied to an
323 * unordered data source.
324 */
325 CONCURRENT,
326
327 /**
328 * Indicates that the collection operation does not commit to preserving
329 * the encounter order of input elements. (This might be true if the
330 * result container has no intrinsic order, such as a {@link Set}.)
331 */
332 UNORDERED,
333
334 /**
335 * Indicates that the finisher function is the identity function and
336 * can be elided. If set, it must be the case that an unchecked cast
337 * from A to R will succeed.
338 */
339 IDENTITY_FINISH
340 }
341 }
342