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 }