/*

 * 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.Comparator;

import java.util.Objects;

import java.util.Spliterator;

import java.util.function.Consumer;

import java.util.function.DoubleConsumer;

import java.util.function.IntConsumer;

import java.util.function.LongConsumer;

/**

 * Utility methods for operating on and creating streams.

 *

 * <p>Unless otherwise stated, streams are created as sequential streams.  A

 * sequential stream can be transformed into a parallel stream by calling the

 * {@code parallel()} method on the created stream.

 *

 * @since 1.8

 */

final class Streams {

    private Streams() {

        throw new Error("no instances");

    }

    /**

     * An object instance representing no value, that cannot be an actual

     * data element of a stream.  Used when processing streams that can contain

     * {@code null} elements to distinguish between a {@code null} value and no

     * value.

     */

    static final Object NONE = new Object();

    /**

     * An {@code int} range spliterator.

     */

    static final class RangeIntSpliterator implements Spliterator.OfInt {

        // Can never be greater that upTo, this avoids overflow if upper bound

        // is Integer.MAX_VALUE

        // All elements are traversed if from == upTo & last == 0

        private int from;

        private final int upTo;

        // 1 if the range is closed and the last element has not been traversed

        // Otherwise, 0 if the range is open, or is a closed range and all

        // elements have been traversed

        private int last;

        RangeIntSpliterator(int from, int upTo, boolean closed) {

            this(from, upTo, closed ? 1 : 0);

        }

        private RangeIntSpliterator(int from, int upTo, int last) {

            this.from = from;

            this.upTo = upTo;

            this.last = last;

        }

        @Override

        public boolean tryAdvance(IntConsumer consumer) {

            Objects.requireNonNull(consumer);

            final int i = from;

            if (i < upTo) {

                from++;

                consumer.accept(i);

                return true;

            }

            else if (last > 0) {

                last = 0;

                consumer.accept(i);

                return true;

            }

            return false;

        }

        @Override

        public void forEachRemaining(IntConsumer consumer) {

            Objects.requireNonNull(consumer);

            int i = from;

            final int hUpTo = upTo;

            int hLast = last;

            from = upTo;

            last = 0;

            while (i < hUpTo) {

                consumer.accept(i++);

            }

            if (hLast > 0) {

                // Last element of closed range

                consumer.accept(i);

            }

        }

        @Override

        public long estimateSize() {

            // Ensure ranges of size > Integer.MAX_VALUE report the correct size

            return ((long) upTo) - from + last;

        }

        @Override

        public int characteristics() {

            return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED |

                   Spliterator.IMMUTABLE | Spliterator.NONNULL |

                   Spliterator.DISTINCT | Spliterator.SORTED;

        }

        @Override

        public Comparator<? super Integer> getComparator() {

            return null;

        }

        @Override

        public Spliterator.OfInt trySplit() {

            long size = estimateSize();

            return size <= 1

                   ? null

                   // Left split always has a half-open range

                   : new RangeIntSpliterator(from, from = from + splitPoint(size), 0);

        }

        /**

         * The spliterator size below which the spliterator will be split

         * at the mid-point to produce balanced splits. Above this size the

         * spliterator will be split at a ratio of

         * 1:(RIGHT_BALANCED_SPLIT_RATIO - 1)

         * to produce right-balanced splits.

         *

         * <p>Such splitting ensures that for very large ranges that the left

         * side of the range will more likely be processed at a lower-depth

         * than a balanced tree at the expense of a higher-depth for the right

         * side of the range.

         *

         * <p>This is optimized for cases such as IntStream.ints() that is

         * implemented as range of 0 to Integer.MAX_VALUE but is likely to be

         * augmented with a limit operation that limits the number of elements

         * to a count lower than this threshold.

         */

        private static final int BALANCED_SPLIT_THRESHOLD = 1 << 24;

        /**

         * The split ratio of the left and right split when the spliterator

         * size is above BALANCED_SPLIT_THRESHOLD.

         */

        private static final int RIGHT_BALANCED_SPLIT_RATIO = 1 << 3;

        private int splitPoint(long size) {

            int d = (size < BALANCED_SPLIT_THRESHOLD) ? 2 : RIGHT_BALANCED_SPLIT_RATIO;

            // Cast to int is safe since:

            //   2 <= size < 2^32

            //   2 <= d <= 8

            return (int) (size / d);

        }

    }

    /**

     * A {@code long} range spliterator.

     *

     * This implementation cannot be used for ranges whose size is greater

     * than Long.MAX_VALUE

     */

    static final class RangeLongSpliterator implements Spliterator.OfLong {

        // Can never be greater that upTo, this avoids overflow if upper bound

        // is Long.MAX_VALUE

        // All elements are traversed if from == upTo & last == 0

        private long from;

        private final long upTo;

        // 1 if the range is closed and the last element has not been traversed

        // Otherwise, 0 if the range is open, or is a closed range and all

        // elements have been traversed

        private int last;

        RangeLongSpliterator(long from, long upTo, boolean closed) {

            this(from, upTo, closed ? 1 : 0);

        }

        private RangeLongSpliterator(long from, long upTo, int last) {

            assert upTo - from + last > 0;

            this.from = from;

            this.upTo = upTo;

            this.last = last;

        }

        @Override

        public boolean tryAdvance(LongConsumer consumer) {

            Objects.requireNonNull(consumer);

            final long i = from;

            if (i < upTo) {

                from++;

                consumer.accept(i);

                return true;

            }

            else if (last > 0) {

                last = 0;

                consumer.accept(i);

                return true;

            }

            return false;

        }

        @Override

        public void forEachRemaining(LongConsumer consumer) {

            Objects.requireNonNull(consumer);

            long i = from;

            final long hUpTo = upTo;

            int hLast = last;

            from = upTo;

            last = 0;

            while (i < hUpTo) {

                consumer.accept(i++);

            }

            if (hLast > 0) {

                // Last element of closed range

                consumer.accept(i);

            }

        }

        @Override

        public long estimateSize() {

            return upTo - from + last;

        }

        @Override

        public int characteristics() {

            return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED |

                   Spliterator.IMMUTABLE | Spliterator.NONNULL |

                   Spliterator.DISTINCT | Spliterator.SORTED;

        }

        @Override

        public Comparator<? super Long> getComparator() {

            return null;

        }

        @Override

        public Spliterator.OfLong trySplit() {

            long size = estimateSize();

            return size <= 1

                   ? null

                   // Left split always has a half-open range

                   : new RangeLongSpliterator(from, from = from + splitPoint(size), 0);

        }

        /**

         * The spliterator size below which the spliterator will be split

         * at the mid-point to produce balanced splits. Above this size the

         * spliterator will be split at a ratio of

         * 1:(RIGHT_BALANCED_SPLIT_RATIO - 1)

         * to produce right-balanced splits.

         *

         * <p>Such splitting ensures that for very large ranges that the left

         * side of the range will more likely be processed at a lower-depth

         * than a balanced tree at the expense of a higher-depth for the right

         * side of the range.

         *

         * <p>This is optimized for cases such as LongStream.longs() that is

         * implemented as range of 0 to Long.MAX_VALUE but is likely to be

         * augmented with a limit operation that limits the number of elements

         * to a count lower than this threshold.

         */

        private static final long BALANCED_SPLIT_THRESHOLD = 1 << 24;

        /**

         * The split ratio of the left and right split when the spliterator

         * size is above BALANCED_SPLIT_THRESHOLD.

         */

        private static final long RIGHT_BALANCED_SPLIT_RATIO = 1 << 3;

        private long splitPoint(long size) {

            long d = (size < BALANCED_SPLIT_THRESHOLD) ? 2 : RIGHT_BALANCED_SPLIT_RATIO;

            // 2 <= size <= Long.MAX_VALUE

            return size / d;

        }

    }

    private static abstract class AbstractStreamBuilderImpl<T, S extends Spliterator<T>> implements Spliterator<T> {

        // >= 0 when building, < 0 when built

        // -1 == no elements

        // -2 == one element, held by first

        // -3 == two or more elements, held by buffer

        int count;

        // Spliterator implementation for 0 or 1 element

        // count == -1 for no elements

        // count == -2 for one element held by first

        @Override

        public S trySplit() {

            return null;

        }

        @Override

        public long estimateSize() {

            return -count - 1;

        }

        @Override

        public int characteristics() {

            return Spliterator.SIZED | Spliterator.SUBSIZED |

                   Spliterator.ORDERED | Spliterator.IMMUTABLE;

        }

    }

    static final class StreamBuilderImpl<T>

            extends AbstractStreamBuilderImpl<T, Spliterator<T>>

            implements Stream.Builder<T> {

        // The first element in the stream

        // valid if count == 1

        T first;

        // The first and subsequent elements in the stream

        // non-null if count == 2

        SpinedBuffer<T> buffer;

        /**

         * Constructor for building a stream of 0 or more elements.

         */

        StreamBuilderImpl() { }

        /**

         * Constructor for a singleton stream.

         *

         * @param t the single element

         */

        StreamBuilderImpl(T t) {

            first = t;

            count = -2;

        }

        // StreamBuilder implementation

        @Override

        public void accept(T t) {

            if (count == 0) {

                first = t;

                count++;

            }

            else if (count > 0) {

                if (buffer == null) {

                    buffer = new SpinedBuffer<>();

                    buffer.accept(first);

                    count++;

                }

                buffer.accept(t);

            }

            else {

                throw new IllegalStateException();

            }

        }

        public Stream.Builder<T> add(T t) {

            accept(t);

            return this;

        }

        @Override

        public Stream<T> build() {

            int c = count;

            if (c >= 0) {

                // Switch count to negative value signalling the builder is built

                count = -count - 1;

                // Use this spliterator if 0 or 1 elements, otherwise use

                // the spliterator of the spined buffer

                return (c < 2) ? StreamSupport.stream(this, false) : StreamSupport.stream(buffer.spliterator(), false);

            }

            throw new IllegalStateException();

        }

        // Spliterator implementation for 0 or 1 element

        // count == -1 for no elements

        // count == -2 for one element held by first

        @Override

        public boolean tryAdvance(Consumer<? super T> action) {

            Objects.requireNonNull(action);

            if (count == -2) {

                action.accept(first);

                count = -1;

                return true;

            }

            else {

                return false;

            }

        }

        @Override

        public void forEachRemaining(Consumer<? super T> action) {

            Objects.requireNonNull(action);

            if (count == -2) {

                action.accept(first);

                count = -1;

            }

        }

    }

    static final class IntStreamBuilderImpl

            extends AbstractStreamBuilderImpl<Integer, Spliterator.OfInt>

            implements IntStream.Builder, Spliterator.OfInt {

        // The first element in the stream

        // valid if count == 1

        int first;

        // The first and subsequent elements in the stream

        // non-null if count == 2

        SpinedBuffer.OfInt buffer;

        /**

         * Constructor for building a stream of 0 or more elements.

         */

        IntStreamBuilderImpl() { }

        /**

         * Constructor for a singleton stream.

         *

         * @param t the single element

         */

        IntStreamBuilderImpl(int t) {

            first = t;

            count = -2;

        }

        // StreamBuilder implementation

        @Override

        public void accept(int t) {

            if (count == 0) {

                first = t;

                count++;

            }

            else if (count > 0) {

                if (buffer == null) {

                    buffer = new SpinedBuffer.OfInt();

                    buffer.accept(first);

                    count++;

                }

                buffer.accept(t);

            }

            else {

                throw new IllegalStateException();

            }

        }

        @Override

        public IntStream build() {

            int c = count;

            if (c >= 0) {

                // Switch count to negative value signalling the builder is built

                count = -count - 1;

                // Use this spliterator if 0 or 1 elements, otherwise use

                // the spliterator of the spined buffer

                return (c < 2) ? StreamSupport.intStream(this, false) : StreamSupport.intStream(buffer.spliterator(), false);

            }

            throw new IllegalStateException();

        }

        // Spliterator implementation for 0 or 1 element

        // count == -1 for no elements

        // count == -2 for one element held by first

        @Override

        public boolean tryAdvance(IntConsumer action) {

            Objects.requireNonNull(action);

            if (count == -2) {

                action.accept(first);

                count = -1;

                return true;

            }

            else {

                return false;

            }

        }

        @Override

        public void forEachRemaining(IntConsumer action) {

            Objects.requireNonNull(action);

            if (count == -2) {

                action.accept(first);

                count = -1;

            }