/*

 * Copyright (c) 2012, 2013, Oracle and/or its affiliates. All rights reserved.

 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

 *

 * This code is free software; you can redistribute it and/or modify it

 * under the terms of the GNU General Public License version 2 only, as

 * published by the Free Software Foundation.  Oracle designates this

 * particular file as subject to the "Classpath" exception as provided

 * by Oracle in the LICENSE file that accompanied this code.

 *

 * This code is distributed in the hope that it will be useful, but WITHOUT

 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

 * version 2 for more details (a copy is included in the LICENSE file that

 * accompanied this code).

 *

 * You should have received a copy of the GNU General Public License version

 * 2 along with this work; if not, write to the Free Software Foundation,

 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

 *

 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

 * or visit www.oracle.com if you need additional information or have any

 * questions.

 */

package java.util.stream;

import java.util.AbstractMap;

import java.util.AbstractSet;

import java.util.ArrayList;

import java.util.Collection;

import java.util.Collections;

import java.util.Comparator;

import java.util.Comparators;

import java.util.DoubleSummaryStatistics;

import java.util.EnumSet;

import java.util.HashMap;

import java.util.HashSet;

import java.util.IntSummaryStatistics;

import java.util.Iterator;

import java.util.List;

import java.util.LongSummaryStatistics;

import java.util.Map;

import java.util.NoSuchElementException;

import java.util.Objects;

import java.util.Set;

import java.util.StringJoiner;

import java.util.concurrent.ConcurrentHashMap;

import java.util.concurrent.ConcurrentMap;

import java.util.function.BiFunction;

import java.util.function.BinaryOperator;

import java.util.function.Function;

import java.util.function.Predicate;

import java.util.function.Supplier;

import java.util.function.ToDoubleFunction;

import java.util.function.ToIntFunction;

import java.util.function.ToLongFunction;

/**

 * Implementations of {@link Collector} that implement various useful reduction

 * operations, such as accumulating elements into collections, summarizing

 * elements according to various criteria, etc.

 *

 * <p>The following are examples of using the predefined {@code Collector}

 * implementations in {@link Collectors} with the {@code Stream} API to perform

 * mutable reduction tasks:

 *

 * <pre>{@code

 *     // Accumulate elements into a List

 *     List<Person> list = people.collect(Collectors.toList());

 *

 *     // Accumulate elements into a TreeSet

 *     List<Person> list = people.collect(Collectors.toCollection(TreeSet::new));

 *

 *     // Convert elements to strings and concatenate them, separated by commas

 *     String joined = stream.map(Object::toString)

 *                           .collect(Collectors.toStringJoiner(", "))

 *                           .toString();

 *

 *     // Find highest-paid employee

 *     Employee highestPaid = employees.stream()

 *                                     .collect(Collectors.maxBy(Comparators.comparing(Employee::getSalary)));

 *

 *     // Group employees by department

 *     Map<Department, List<Employee>> byDept

 *         = employees.stream()

 *                    .collect(Collectors.groupingBy(Employee::getDepartment));

 *

 *     // Find highest-paid employee by department

 *     Map<Department, Employee> highestPaidByDept

 *         = employees.stream()

 *                    .collect(Collectors.groupingBy(Employee::getDepartment,

 *                                                   Collectors.maxBy(Comparators.comparing(Employee::getSalary))));

 *

 *     // Partition students into passing and failing

 *     Map<Boolean, List<Student>> passingFailing =

 *         students.stream()

 *                 .collect(Collectors.partitioningBy(s -> s.getGrade() >= PASS_THRESHOLD);

 *

 * }</pre>

 *

 * TODO explanation of parallel collection

 *

 * @since 1.8

 */

public final class Collectors {

    private static final Set<Collector.Characteristics> CH_CONCURRENT

            = Collections.unmodifiableSet(EnumSet.of(Collector.Characteristics.CONCURRENT,

                                                     Collector.Characteristics.STRICTLY_MUTATIVE,

                                                     Collector.Characteristics.UNORDERED));

    private static final Set<Collector.Characteristics> CH_STRICT

            = Collections.unmodifiableSet(EnumSet.of(Collector.Characteristics.STRICTLY_MUTATIVE));

    private static final Set<Collector.Characteristics> CH_STRICT_UNORDERED

            = Collections.unmodifiableSet(EnumSet.of(Collector.Characteristics.STRICTLY_MUTATIVE,

                                                     Collector.Characteristics.UNORDERED));

    private Collectors() { }

    /**

     * Returns a merge function, suitable for use in

     * {@link Map#merge(Object, Object, BiFunction) Map.merge()} or

     * {@link #toMap(Function, Function, BinaryOperator) toMap()}, which always

     * throws {@code IllegalStateException}.  This can be used to enforce the

     * assumption that the elements being collected are distinct.

     *

     * @param <T> the type of input arguments to the merge function

     * @return a merge function which always throw {@code IllegalStateException}

     *

     * @see #firstWinsMerger()

     * @see #lastWinsMerger()

     */

    public static <T> BinaryOperator<T> throwingMerger() {

        return (u,v) -> { throw new IllegalStateException(String.format("Duplicate key %s", u)); };

    }

    /**

     * Returns a merge function, suitable for use in

     * {@link Map#merge(Object, Object, BiFunction) Map.merge()} or

     * {@link #toMap(Function, Function, BinaryOperator) toMap()},

     * which implements a "first wins" policy.

     *

     * @param <T> the type of input arguments to the merge function

     * @return a merge function which always returns its first argument

     * @see #lastWinsMerger()

     * @see #throwingMerger()

     */

    public static <T> BinaryOperator<T> firstWinsMerger() {

        return (u,v) -> u;

    }

    /**

     * Returns a merge function, suitable for use in

     * {@link Map#merge(Object, Object, BiFunction) Map.merge()} or

     * {@link #toMap(Function, Function, BinaryOperator) toMap()},

     * which implements a "last wins" policy.

     *

     * @param <T> the type of input arguments to the merge function

     * @return a merge function which always returns its second argument

     * @see #firstWinsMerger()

     * @see #throwingMerger()

     */

    public static <T> BinaryOperator<T> lastWinsMerger() {

        return (u,v) -> v;

    }

    /**

     * Simple implementation class for {@code Collector}.

     *

     * @param <T> the type of elements to be collected

     * @param <R> the type of the result

     */

    private static final class CollectorImpl<T, R> implements Collector<T,R> {

        private final Supplier<R> resultSupplier;

        private final BiFunction<R, T, R> accumulator;

        private final BinaryOperator<R> combiner;

        private final Set<Characteristics> characteristics;

        CollectorImpl(Supplier<R> resultSupplier,

                      BiFunction<R, T, R> accumulator,

                      BinaryOperator<R> combiner,

                      Set<Characteristics> characteristics) {

            this.resultSupplier = resultSupplier;

            this.accumulator = accumulator;

            this.combiner = combiner;

            this.characteristics = characteristics;

        }

        CollectorImpl(Supplier<R> resultSupplier,

                      BiFunction<R, T, R> accumulator,

                      BinaryOperator<R> combiner) {

            this(resultSupplier, accumulator, combiner, Collections.emptySet());

        }

        @Override

        public BiFunction<R, T, R> accumulator() {

            return accumulator;

        }

        @Override

        public Supplier<R> resultSupplier() {

            return resultSupplier;

        }

        @Override

        public BinaryOperator<R> combiner() {

            return combiner;

        }

        @Override

        public Set<Characteristics> characteristics() {

            return characteristics;

        }

    }

    /**

     * Returns a {@code Collector} that accumulates the input elements into a

     * new {@code Collection}, in encounter order.  The {@code Collection} is

     * created by the provided factory.

     *

     * @param <T> the type of the input elements

     * @param <C> the type of the resulting {@code Collection}

     * @param collectionFactory a {@code Supplier} which returns a new, empty

     * {@code Collection} of the appropriate type

     * @return a {@code Collector} which collects all the input elements into a

     * {@code Collection}, in encounter order

     */

    public static <T, C extends Collection<T>>

    Collector<T, C> toCollection(Supplier<C> collectionFactory) {

        return new CollectorImpl<>(collectionFactory,

                                   (r, t) -> { r.add(t); return r; },

                                   (r1, r2) -> { r1.addAll(r2); return r1; },

                                   CH_STRICT);

    }

    /**

     * Returns a {@code Collector} that accumulates the input elements into a

     * new {@code List}. There are no guarantees on the type, mutability,

     * serializability, or thread-safety of the {@code List} returned.

     *

     * @param <T> the type of the input elements

     * @return a {@code Collector} which collects all the input elements into a

     * {@code List}, in encounter order

     */

    public static <T>

    Collector<T, List<T>> toList() {

        BiFunction<List<T>, T, List<T>> accumulator = (list, t) -> {

            switch (list.size()) {

                case 0:

                    return Collections.singletonList(t);

                case 1:

                    List<T> newList = new ArrayList<>();

                    newList.add(list.get(0));

                    newList.add(t);

                    return newList;

                default:

                    list.add(t);

                    return list;

            }

        };

        BinaryOperator<List<T>> combiner = (left, right) -> {

            switch (left.size()) {

                case 0:

                    return right;

                case 1:

                    List<T> newList = new ArrayList<>(left.size() + right.size());

                    newList.addAll(left);

                    newList.addAll(right);

                    return newList;

                default:

                    left.addAll(right);

                    return left;

            }

        };

        return new CollectorImpl<>(Collections::emptyList, accumulator, combiner);

    }

    /**

     * Returns a {@code Collector} that accumulates the input elements into a

     * new {@code Set}. There are no guarantees on the type, mutability,

     * serializability, or thread-safety of the {@code Set} returned.

     *

     * <p>This is an {@link Collector.Characteristics#UNORDERED unordered}

     * Collector.

     *

     * @param <T> the type of the input elements

     * @return a {@code Collector} which collects all the input elements into a

     * {@code Set}

     */

    public static <T>

    Collector<T, Set<T>> toSet() {

        return new CollectorImpl<>((Supplier<Set<T>>) HashSet::new,

                                   (r, t) -> { r.add(t); return r; },

                                   (r1, r2) -> { r1.addAll(r2); return r1; },

                                   CH_STRICT_UNORDERED);

    }

    /**

     * Returns a {@code Collector} that concatenates the input elements into a

     * new {@link StringBuilder}.

     *

     * @return a {@code Collector} which collects String elements into a

     * {@code StringBuilder}, in encounter order

     */

    public static Collector<String, StringBuilder> toStringBuilder() {

        return new CollectorImpl<>(StringBuilder::new,

                                   (r, t) -> { r.append(t); return r; },

                                   (r1, r2) -> { r1.append(r2); return r1; },

                                   CH_STRICT);

    }

    /**

     * Returns a {@code Collector} that concatenates the input elements into a

     * new {@link StringJoiner}, using the specified delimiter.

     *

     * @param delimiter the delimiter to be used between each element

     * @return A {@code Collector} which collects String elements into a

     * {@code StringJoiner}, in encounter order

     */

    public static Collector<CharSequence, StringJoiner> toStringJoiner(CharSequence delimiter) {

        BinaryOperator<StringJoiner> merger = (sj, other) -> {

            if (other.length() > 0)

                sj.add(other.toString());

            return sj;

        };

        return new CollectorImpl<>(() -> new StringJoiner(delimiter),

                                   (r, t) -> { r.add(t); return r; },

                                   merger, CH_STRICT);

    }

    /**

     * {@code BinaryOperator<Map>} that merges the contents of its right

     * argument into its left argument, using the provided merge function to

     * handle duplicate keys.

     *

     * @param <K> type of the map keys

     * @param <V> type of the map values

     * @param <M> type of the map

     * @param mergeFunction A merge function suitable for

     * {@link Map#merge(Object, Object, BiFunction) Map.merge()}

     * @return a merge function for two maps

     */

    private static <K, V, M extends Map<K,V>>

    BinaryOperator<M> mapMerger(BinaryOperator<V> mergeFunction) {

        return (m1, m2) -> {

            for (Map.Entry<K,V> e : m2.entrySet())

                m1.merge(e.getKey(), e.getValue(), mergeFunction);

            return m1;

        };

    }

    /**

     * Adapts a {@code Collector<U,R>} to a {@code Collector<T,R>} by applying

     * a mapping function to each input element before accumulation.

     *

     * @apiNote

     * The {@code mapping()} collectors are most useful when used in a

     * multi-level reduction, downstream of {@code groupingBy} or

     * {@code partitioningBy}.  For example, given a stream of

     * {@code Person}, to accumulate the set of last names in each city:

     * <pre>{@code

     *     Map<City, Set<String>> lastNamesByCity

     *         = people.stream().collect(groupingBy(Person::getCity,

     *                                              mapping(Person::getLastName, toSet())));

     * }</pre>

     *

     * @param <T> the type of the input elements

     * @param <U> type of elements accepted by downstream collector

     * @param <R> result type of collector

     * @param mapper a function to be applied to the input elements

     * @param downstream a collector which will accept mapped values

     * @return a collector which applies the mapping function to the input

     * elements and provides the mapped results to the downstream collector

     */

    public static <T, U, R> Collector<T, R>

    mapping(Function<? super T, ? extends U> mapper, Collector<? super U, R> downstream) {

        BiFunction<R, ? super U, R> downstreamAccumulator = downstream.accumulator();

        return new CollectorImpl<>(downstream.resultSupplier(),

                                   (r, t) -> downstreamAccumulator.apply(r, mapper.apply(t)),

                                   downstream.combiner(), downstream.characteristics());

    }

    /**

     * Returns a {@code Collector<T, Long>} that counts the number of input

     * elements.

     *

     * @implSpec

     * This produces a result equivalent to:

     * <pre>{@code

     *     reducing(0L, e -> 1L, Long::sum)

     * }</pre>

     *

     * @param <T> the type of the input elements

     * @return a {@code Collector} that counts the input elements

     */

    public static <T> Collector<T, Long>

    counting() {

        return reducing(0L, e -> 1L, Long::sum);

    }

    /**

     * Returns a {@code Collector<T, T>} that produces the minimal element

     * according to a given {@code Comparator}.

     *

     * @implSpec

     * This produces a result equivalent to:

     * <pre>{@code

     *     reducing(Comparators.lesserOf(comparator))

     * }</pre>

     *

     * @param <T> the type of the input elements

     * @param comparator a {@code Comparator} for comparing elements

     * @return a {@code Collector} that produces the minimal value

     */

    public static <T> Collector<T, T>

    minBy(Comparator<? super T> comparator) {

        return reducing(Comparators.lesserOf(comparator));

    }

    /**

     * Returns a {@code Collector<T, T>} that produces the maximal element

     * according to a given {@code Comparator}.

     *

     * @implSpec

     * This produces a result equivalent to:

     * <pre>{@code

     *     reducing(Comparators.greaterOf(comparator))

     * }</pre>

     *

     * @param <T> the type of the input elements

     * @param comparator a {@code Comparator} for comparing elements

     * @return a {@code Collector} that produces the maximal value

     */

    public static <T> Collector<T, T>

    maxBy(Comparator<? super T> comparator) {

        return reducing(Comparators.greaterOf(comparator));

    }

    /**

     * Returns a {@code Collector<T, Long>} that produces the sum of a

     * long-valued function applied to the input element.

     *

     * @implSpec

     * This produces a result equivalent to:

     * <pre>{@code

     *     reducing(0L, mapper, Long::sum)

     * }</pre>

     *

     * @param <T> the type of the input elements

     * @param mapper a function extracting the property to be summed

     * @return a {@code Collector} that produces the sum of a derived property

     */

    public static <T> Collector<T, Long>

    sumBy(Function<? super T, Long> mapper) {

        return reducing(0L, mapper, Long::sum);

    }

    /**

     * Returns a {@code Collector<T,T>} which performs a reduction of its

     * input elements under a specified {@code BinaryOperator}.

     *

     * @apiNote

     * The {@code reducing()} collectors are most useful when used in a

     * multi-level reduction, downstream of {@code groupingBy} or

     * {@code partitioningBy}.  To perform a simple reduction on a stream,

     * use {@link Stream#reduce(BinaryOperator)} instead.

     *

     * @param <T> element type for the input and output of the reduction

     * @param identity the identity value for the reduction (also, the value

     *                 that is returned when there are no input elements)

     * @param op a {@code BinaryOperator<T>} used to reduce the input elements

     * @return a {@code Collector} which implements the reduction operation

     *

     * @see #reducing(BinaryOperator)

     * @see #reducing(Object, Function, BinaryOperator)

     */

    public static <T> Collector<T, T>

    reducing(T identity, BinaryOperator<T> op) {

        return new CollectorImpl<>(() -> identity, (r, t) -> (r == null ? t : op.apply(r, t)), op);

    }

    /**

     * Returns a {@code Collector<T,T>} which performs a reduction of its

     * input elements under a specified {@code BinaryOperator}.

     *

     * @apiNote

     * The {@code reducing()} collectors are most useful when used in a

     * multi-level reduction, downstream of {@code groupingBy} or

     * {@code partitioningBy}.  To perform a simple reduction on a stream,

     * use {@link Stream#reduce(BinaryOperator)} instead.

     *

     * <p>For example, given a stream of {@code Person}, to calculate tallest

     * person in each city:

     * <pre>{@code

     *     Comparator<Person> byHeight = Comparators.comparing(Person::getHeight);

     *     BinaryOperator<Person> tallerOf = Comparators.greaterOf(byHeight);

     *     Map<City, Person> tallestByCity

     *         = people.stream().collect(groupingBy(Person::getCity, reducing(tallerOf)));

     * }</pre>

     *

     * @implSpec

     * The default implementation is equivalent to:

     * <pre>{@code

     *     reducing(null, op);

     * }</pre>

     *

     * @param <T> element type for the input and output of the reduction

     * @param op a {@code BinaryOperator<T>} used to reduce the input elements

     * @return a {@code Collector} which implements the reduction operation

     *

     * @see #reducing(Object, BinaryOperator)

     * @see #reducing(Object, Function, BinaryOperator)

     */

    public static <T> Collector<T, T>

    reducing(BinaryOperator<T> op) {

        return reducing(null, op);

    }

    /**

     * Returns a {@code Collector<T,U>} which performs a reduction of its

     * input elements under a specified mapping function and

     * {@code BinaryOperator}. This is a generalization of

     * {@link #reducing(Object, BinaryOperator)} which allows a transformation

     * of the elements before reduction.

     *

     * @apiNote

     * The {@code reducing()} collectors are most useful when used in a

     * multi-level reduction, downstream of {@code groupingBy} or

     * {@code partitioningBy}.  To perform a simple reduction on a stream,