/*

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

import java.util.Spliterator;

import java.util.function.IntFunction;

import java.util.function.Supplier;

/**

 * Abstract base class for "pipeline" classes, which are the core

 * implementations of the Stream interface and its primitive specializations.

 * Manages construction and evaluation of stream pipelines.

 *

 * <p>An {@code AbstractPipeline} represents an initial portion of a stream

 * pipeline, encapsulating a stream source and zero or more intermediate

 * operations.  The individual {@code AbstractPipeline} objects are often

 * referred to as <em>stages</em>, where each stage describes either the stream

 * source or an intermediate operation.

 *

 * <p>A concrete intermediate stage is generally built from an

 * {@code AbstractPipeline}, a shape-specific pipeline class which extends it

 * (e.g., {@code IntPipeline}) which is also abstract, and an operation-specific

 * concrete class which extends that.  {@code AbstractPipeline} contains most of

 * the mechanics of evaluating the pipeline, and implements methods that will be

 * used by the operation; the shape-specific classes add helper methods for

 * dealing with collection of results into the appropriate shape-specific

 * containers.

 *

 * <p>After chaining a new intermediate operation, or executing a terminal

 * operation, the stream is considered to be consumed, and no more intermediate

 * or terminal operations are permitted on this stream instance.

 *

 * <p>{@code AbstractPipeline} implements a number of methods that are

 * specified in {@link BaseStream}, though it does not implement

 * {@code BaseStream} directly.  Subclasses of {@code AbstractPipeline}

 * will generally implement {@code BaseStream}.

 *

 * @implNote

 * <p>For sequential streams, and parallel streams without

 * <a href="package-summary.html#StreamOps">stateful intermediate

 * operations</a>, parallel streams, pipeline evaluation is done in a single

 * pass that "jams" all the operations together.  For parallel streams with

 * stateful operations, execution is divided into segments, where each

 * stateful operations marks the end of a segment, and each segment is

 * evaluated separately and the result used as the input to the next

 * segment.  In all cases, the source data is not consumed until a terminal

 * operation begins.

 *

 * @param <E_IN>  type of input elements

 * @param <E_OUT> type of output elements

 * @param <S> type of the subclass implementing {@code BaseStream}

 * @since 1.8

 */

abstract class AbstractPipeline<E_IN, E_OUT, S extends BaseStream<E_OUT, S>>

        extends PipelineHelper<E_OUT> {

    /**

     * Backlink to the head of the pipeline chain (self if this is the source

     * stage).

     */

    private final AbstractPipeline sourceStage;

    /**

     * The "upstream" pipeline, or null if this is the source stage.

     */

    private final AbstractPipeline previousStage;

    /**

     * The operation flags for the intermediate operation represented by this

     * pipeline object.

     */

    protected final int sourceOrOpFlags;

    /**

     * The next stage in the pipeline, or null if this is the last stage.

     * Effectively final at the point of linking to the next pipeline.

     */

    private AbstractPipeline nextStage;

    /**

     * The number of intermediate operations between this pipeline object

     * and the stream source if sequential, or the previous stateful if parallel.

     * Valid at the point of pipeline preparation for evaluation.

     */

    private int depth;

    /**

     * The combined source and operation flags for the source and all operations

     * up to and including the operation represented by this pipeline object.

     * Valid at the point of pipeline preparation for evaluation.

     */

    private int combinedFlags;

    /**

     * The source spliterator. Only valid for the head pipeline.

     * Before the pipeline is consumed if non-null then {@code sourceSupplier}

     * must be null. After the pipeline is consumed if non-null then is set to

     * null.

     */

    private Spliterator<?> sourceSpliterator;

    /**

     * The source supplier. Only valid for the head pipeline. Before the

     * pipeline is consumed if non-null then {@code sourceSpliterator} must be

     * null. After the pipeline is consumed if non-null then is set to null.

     */

    private Supplier<? extends Spliterator<?>> sourceSupplier;

    /**

     * True if this pipeline has been linked or consumed

     */

    private boolean linkedOrConsumed;

    /**

     * True if there are any stateful ops in the pipeline; only valid for the

     * source stage.

     */

    private boolean sourceAnyStateful;

    /**

     * True if pipeline is parallel, otherwise the pipeline is sequential; only

     * valid for the source stage.

     */

    private boolean parallel;

    /**

     * Constructor for the head of a stream pipeline.

     *

     * @param source {@code Supplier<Spliterator>} describing the stream source

     * @param sourceFlags The source flags for the stream source, described in

     * {@link StreamOpFlag}

     * @param parallel True if the pipeline is parallel

     */

    AbstractPipeline(Supplier<? extends Spliterator<?>> source,

                     int sourceFlags, boolean parallel) {

        this.previousStage = null;

        this.sourceSupplier = source;

        this.sourceStage = this;

        this.sourceOrOpFlags = sourceFlags & StreamOpFlag.STREAM_MASK;

        // The following is an optimization of:

        // StreamOpFlag.combineOpFlags(sourceOrOpFlags, StreamOpFlag.INITIAL_OPS_VALUE);

        this.combinedFlags = (~(sourceOrOpFlags << 1)) & StreamOpFlag.INITIAL_OPS_VALUE;

        this.depth = 0;

        this.parallel = parallel;

    }

    /**

     * Constructor for the head of a stream pipeline.

     *

     * @param source {@code Spliterator} describing the stream source

     * @param sourceFlags the source flags for the stream source, described in

     * {@link StreamOpFlag}

     * @param parallel {@code true} if the pipeline is parallel

     */

    AbstractPipeline(Spliterator<?> source,

                     int sourceFlags, boolean parallel) {

        this.previousStage = null;

        this.sourceSpliterator = source;

        this.sourceStage = this;

        this.sourceOrOpFlags = sourceFlags & StreamOpFlag.STREAM_MASK;

        // The following is an optimization of:

        // StreamOpFlag.combineOpFlags(sourceOrOpFlags, StreamOpFlag.INITIAL_OPS_VALUE);

        this.combinedFlags = (~(sourceOrOpFlags << 1)) & StreamOpFlag.INITIAL_OPS_VALUE;

        this.depth = 0;

        this.parallel = parallel;

    }

    /**

     * Constructor for appending an intermediate operation stage onto an

     * existing pipeline.

     *

     * @param previousStage the upstream pipeline stage

     * @param opFlags the operation flags for the new stage, described in

     * {@link StreamOpFlag}

     */

    AbstractPipeline(AbstractPipeline<?, E_IN, ?> previousStage, int opFlags) {

        if (previousStage.linkedOrConsumed)

            throw new IllegalStateException("stream has already been operated upon");

        previousStage.linkedOrConsumed = true;

        previousStage.nextStage = this;

        this.previousStage = previousStage;

        this.sourceOrOpFlags = opFlags & StreamOpFlag.OP_MASK;

        this.combinedFlags = StreamOpFlag.combineOpFlags(opFlags, previousStage.combinedFlags);

        this.sourceStage = previousStage.sourceStage;

        if (opIsStateful())

            sourceStage.sourceAnyStateful = true;

        this.depth = previousStage.depth + 1;

    }

    // Terminal evaluation methods

    /**

     * Evaluate the pipeline with a terminal operation to produce a result.

     *

     * @param <R> the type of result

     * @param terminalOp the terminal operation to be applied to the pipeline.

     * @return the result

     */

    final <R> R evaluate(TerminalOp<E_OUT, R> terminalOp) {

        assert getOutputShape() == terminalOp.inputShape();

        if (linkedOrConsumed)

            throw new IllegalStateException("stream has already been operated upon");

        linkedOrConsumed = true;

        return isParallel()

               ? (R) terminalOp.evaluateParallel(this, sourceSpliterator(terminalOp.getOpFlags()))

               : (R) terminalOp.evaluateSequential(this, sourceSpliterator(terminalOp.getOpFlags()));

    }

    /**

     * Collect the elements output from the pipeline stage.

     *

     * @param generator the array generator to be used to create array instances

     * @return a flat array-backed Node that holds the collected output elements

     */

    final Node<E_OUT> evaluateToArrayNode(IntFunction<E_OUT[]> generator) {

        if (linkedOrConsumed)

            throw new IllegalStateException("stream has already been operated upon");

        linkedOrConsumed = true;

        // If the last intermediate operation is stateful then

        // evaluate directly to avoid an extra collection step

        if (isParallel() && previousStage != null && opIsStateful()) {

            return opEvaluateParallel(previousStage, previousStage.sourceSpliterator(0), generator);

        }

        else {

            return evaluate(sourceSpliterator(0), true, generator);

        }

    }

    /**

     * Gets the source stage spliterator if this pipeline stage is the source

     * stage.  The pipeline is consumed after this method is called and

     * returns successfully.

     *

     * @return the source stage spliterator

     * @throws IllegalStateException if this pipeline stage is not the source

     *         stage.

     */

    final Spliterator<E_OUT> sourceStageSpliterator() {

        if (this != sourceStage)

            throw new IllegalStateException();

        if (linkedOrConsumed)

            throw new IllegalStateException("stream has already been operated upon");

        linkedOrConsumed = true;

        if (sourceStage.sourceSpliterator != null) {

            Spliterator<E_OUT> s = sourceStage.sourceSpliterator;

            sourceStage.sourceSpliterator = null;

            return s;

        }

        else if (sourceStage.sourceSupplier != null) {

            Spliterator<E_OUT> s = (Spliterator<E_OUT>) sourceStage.sourceSupplier.get();

            sourceStage.sourceSupplier = null;

            return s;

        }

        else {

            throw new IllegalStateException("source already consumed");

        }

    }

    // BaseStream

    /**

     * Implements {@link BaseStream#sequential()}

     */

    public final S sequential() {

        sourceStage.parallel = false;

        return (S) this;

    }

    /**

     * Implements {@link BaseStream#parallel()}

     */

    public final S parallel() {

        sourceStage.parallel = true;

        return (S) this;

    }

    // Primitive specialization use co-variant overrides, hence is not final

    /**

     * Implements {@link BaseStream#spliterator()}

     */

    public Spliterator<E_OUT> spliterator() {

        if (linkedOrConsumed)

            throw new IllegalStateException("stream has already been operated upon");

        linkedOrConsumed = true;

        if (this == sourceStage) {

            if (sourceStage.sourceSpliterator != null) {

                Spliterator<E_OUT> s = sourceStage.sourceSpliterator;

                sourceStage.sourceSpliterator = null;

                return s;

            }

            else if (sourceStage.sourceSupplier != null) {

                Supplier<Spliterator<E_OUT>> s = sourceStage.sourceSupplier;

                sourceStage.sourceSupplier = null;

                return lazySpliterator(s);

            }

            else {

                throw new IllegalStateException("source already consumed");

            }

        }

        else {

            return wrap(this, () -> sourceSpliterator(0), isParallel());

        }

    }

    /**

     * Implements {@link BaseStream#isParallel()}

     */

    public final boolean isParallel() {

        return sourceStage.parallel;

    }

    /**

     * Returns the composition of stream flags of the stream source and all

     * intermediate operations.

     *

     * @return the composition of stream flags of the stream source and all

     *         intermediate operations

     * @see StreamOpFlag

     */

    final int getStreamFlags() {

        return StreamOpFlag.toStreamFlags(combinedFlags);

    }

    /**

     * Prepare the pipeline for a parallel execution.  As the pipeline is built,

     * the flags and depth indicators are set up for a sequential execution.

     * If the execution is parallel, and there are any stateful operations, then

     * some of these need to be adjusted, as well as adjusting for flags from

     * the terminal operation (such as back-propagating UNORDERED).

     * Need not be called for a sequential execution.

     *

     * @param terminalFlags Operation flags for the terminal operation

     */

    private void parallelPrepare(int terminalFlags) {

        AbstractPipeline backPropagationHead = sourceStage;

        if (sourceStage.sourceAnyStateful) {

            int depth = 1;

            for (AbstractPipeline u = sourceStage, p = sourceStage.nextStage;

                 p != null;

                 u = p, p = p.nextStage) {

                int thisOpFlags = p.sourceOrOpFlags;

                if (p.opIsStateful()) {

                    // If the stateful operation is a short-circuit operation

                    // then move the back propagation head forwards

                    // NOTE: there are no size-injecting ops

                    if (StreamOpFlag.SHORT_CIRCUIT.isKnown(thisOpFlags)) {

                        backPropagationHead = p;

                    }

                    depth = 0;

                    // The following injects size, it is equivalent to:

                    // StreamOpFlag.combineOpFlags(StreamOpFlag.IS_SIZED, p.combinedFlags);

                    thisOpFlags = (thisOpFlags & ~StreamOpFlag.NOT_SIZED) | StreamOpFlag.IS_SIZED;

                }

                p.depth = depth++;

                p.combinedFlags = StreamOpFlag.combineOpFlags(thisOpFlags, u.combinedFlags);

            }

        }

        // Apply the upstream terminal flags

        if (terminalFlags != 0) {

            int upstreamTerminalFlags = terminalFlags & StreamOpFlag.UPSTREAM_TERMINAL_OP_MASK;

            for (AbstractPipeline p = backPropagationHead; p.nextStage != null; p = p.nextStage) {

                p.combinedFlags = StreamOpFlag.combineOpFlags(upstreamTerminalFlags, p.combinedFlags);

            }

            combinedFlags = StreamOpFlag.combineOpFlags(terminalFlags, combinedFlags);

        }

    }

    /**

     * Get the source spliterator for this pipeline stage.  For a sequential or

     * stateless parallel pipeline, this is the source spliterator.  For a

     * stateful parallel pipeline, this is a spliterator describing the results

     * of all computations up to and including the most recent stateful

     * operation.

     */

    private Spliterator<?> sourceSpliterator(int terminalFlags) {

        // Get the source spliterator of the pipeline

        Spliterator<?> spliterator = null;

        if (sourceStage.sourceSpliterator != null) {

            spliterator = sourceStage.sourceSpliterator;

            sourceStage.sourceSpliterator = null;

        }

        else if (sourceStage.sourceSupplier != null) {

            spliterator = (Spliterator<?>) sourceStage.sourceSupplier.get();

            sourceStage.sourceSupplier = null;

        }

        else {

            throw new IllegalStateException("source already consumed");

        }

        if (isParallel()) {

            // @@@ Merge parallelPrepare with the loop below and use the

            //     spliterator characteristics to determine if SIZED

            //     should be injected

            parallelPrepare(terminalFlags);

            // Adapt the source spliterator, evaluating each stateful op

            // in the pipeline up to and including this pipeline stage

            for (AbstractPipeline u = sourceStage, p = sourceStage.nextStage, e = this;

                 u != e;

                 u = p, p = p.nextStage) {

                if (p.opIsStateful()) {

                    spliterator = p.opEvaluateParallelLazy(u, spliterator);

                }

            }

        }

        else if (terminalFlags != 0)  {

            combinedFlags = StreamOpFlag.combineOpFlags(terminalFlags, combinedFlags);

        }

        return spliterator;

    }

    // PipelineHelper

    @Override

    final <P_IN> long exactOutputSizeIfKnown(Spliterator<P_IN> spliterator) {

        return StreamOpFlag.SIZED.isKnown(getStreamAndOpFlags()) ? spliterator.getExactSizeIfKnown() : -1;

    }

    @Override

    final <P_IN, S extends Sink<E_OUT>> S wrapAndCopyInto(S sink, Spliterator<P_IN> spliterator) {

        copyInto(wrapSink(Objects.requireNonNull(sink)), spliterator);

        return sink;

    }

    @Override

    final <P_IN> void copyInto(Sink<P_IN> wrappedSink, Spliterator<P_IN> spliterator) {

        Objects.requireNonNull(wrappedSink);

        if (!StreamOpFlag.SHORT_CIRCUIT.isKnown(getStreamAndOpFlags())) {

            wrappedSink.begin(spliterator.getExactSizeIfKnown());

            spliterator.forEachRemaining(wrappedSink);

            wrappedSink.end();

        }

        else {

            copyIntoWithCancel(wrappedSink, spliterator);

        }

    }

    @Override

    final <P_IN> void copyIntoWithCancel(Sink<P_IN> wrappedSink, Spliterator<P_IN> spliterator) {

        AbstractPipeline p = AbstractPipeline.this;

        while (p.depth > 0) {

            p = p.previousStage;

        }

        wrappedSink.begin(spliterator.getExactSizeIfKnown());

        p.forEachWithCancel(spliterator, wrappedSink);

        wrappedSink.end();

    }

    @Override

    final int getStreamAndOpFlags() {

        return combinedFlags;

    }

    final boolean isOrdered() {

        return StreamOpFlag.ORDERED.isKnown(combinedFlags);

    }

    @Override

    final <P_IN> Sink<P_IN> wrapSink(Sink<E_OUT> sink) {

        Objects.requireNonNull(sink);

        for (AbstractPipeline p=AbstractPipeline.this; p.depth > 0; p=p.previousStage) {

            sink = p.opWrapSink(p.previousStage.combinedFlags, sink);

        }

        return (Sink<P_IN>) sink;

    }

    @Override

    @SuppressWarnings("unchecked")

    final <P_IN> Node<E_OUT> evaluate(Spliterator<P_IN> spliterator,

                                      boolean flatten,

                                      IntFunction<E_OUT[]> generator) {

        if (isParallel()) {

            // @@@ Optimize if op of this pipeline stage is a stateful op

            return evaluateToNode(this, spliterator, flatten, generator);

        }

        else {

            Node.Builder<E_OUT> nb = makeNodeBuilder(

                    exactOutputSizeIfKnown(spliterator), generator);

            return wrapAndCopyInto(nb, spliterator).build();

        }

    }

    // Shape-specific abstract methods, implemented by XxxPipeline classes

    /**

     * Get the output shape of the pipeline.  If the pipeline is the head,

     * then it's output shape corresponds to the shape of the source.

     * Otherwise, it's output shape corresponds to the output shape of the

     * associated operation.

     *