/*
 * Licensed to the Apache Software Foundation (ASF) under one
 * or more contributor license agreements.  See the NOTICE file
 * distributed with this work for additional information
 * regarding copyright ownership.  The ASF licenses this file
 * to you under the Apache License, Version 2.0 (the
 * "License"); you may not use this file except in compliance
 * with the License.  You may obtain a copy of the License at
 *
 *   http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing,
 * software distributed under the License is distributed on an
 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
 * KIND, either express or implied.  See the License for the
 * specific language governing permissions and limitations
 * under the License.
 */
package org.apache.tinkerpop.gremlin.process.traversal;

import org.apache.tinkerpop.gremlin.process.traversal.step.util.MutablePath;
import org.apache.tinkerpop.gremlin.structure.Graph;
import org.javatuples.Pair;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import java.util.Objects;
import java.util.Optional;
import java.util.Set;
import java.util.function.BiConsumer;
import java.util.stream.IntStream;
import java.util.stream.Stream;

/**
 * A Path denotes a particular walk through a {@link Graph} as defined by a {@link Traversal}.
 * In abstraction, any Path implementation maintains two lists: a list of sets of labels and a list of objects.
 * The list of labels are the labels of the steps traversed. The list of objects are the objects traversed.
 *
 * @author Marko A. Rodriguez (http://markorodriguez.com)
 */
public interface Path extends Cloneable, Iterable<Object> {

    /**
     * Get the number of step in the path.
     *
     * @return the size of the path
     */
    public default int size() {
        return this.objects().size();
    }

    /**
     * Determine if the path is empty or not.
     *
     * @return whether the path is empty or not.
     */
    public default boolean isEmpty() {
        return this.size() == 0;
    }

    /**
     * Get the head of the path.
     *
     * @param <A> the type of the head of the path
     * @return the head of the path
     */
    public default <A> A head() {
        return (A) this.objects().get(this.size() - 1);
    }

    /**
     * Add a new step to the path with an object and any number of associated labels.
     *
     * @param object the new head of the path
     * @param labels the labels at the head of the path
     * @return the extended path
     */
    public Path extend(final Object object, final Set<String> labels);

    /**
     * Add labels to the head of the path.
     *
     * @param labels the labels at the head of the path
     * @return the path with added labels
     */
    public Path extend(final Set<String> labels);

    /**
     * Remove labels from path.
     *
     * @param labels the labels to remove
     * @return the path with removed labels
     */
    public Path retract(final Set<String> labels);

    /**
     * Get the object associated with the particular label of the path.
     * If the path as multiple labels of the type, then return a {@link List} of those objects.
     *
     * @param label the label of the path
     * @param <A>   the type of the object associated with the label
     * @return the object associated with the label of the path
     * @throws IllegalArgumentException if the path does not contain the label
     */
    public default <A> A get(final String label) throws IllegalArgumentException {
        final List<Object> objects = this.objects();
        final List<Set<String>> labels = this.labels();
        Optional<Object> object = null;
        for (int i = 0; i < labels.size(); i++) {
            if (labels.get(i).contains(label)) {
                if (null == object) {
                    object = Optional.ofNullable(objects.get(i));
                } else if (object.get() instanceof List) {
                    ((List) object.get()).add(objects.get(i));
                } else {
                    final List<Object> list = new ArrayList<>(2);
                    list.add(object.get());
                    list.add(objects.get(i));
                    object = Optional.of(list);
                }
            }
        }

        if (null == object) throw Path.Exceptions.stepWithProvidedLabelDoesNotExist(label);

        return (A) object.orElse(null);
    }

    /**
     * Pop the object(s) associated with the label of the path.
     *
     * @param pop   first for least recent, last for most recent, and all for all in a list
     * @param label the label of the path
     * @param <A>   the type of the object associated with the label
     * @return the object associated with the label of the path
     * @throws IllegalArgumentException if the path does not contain the label
     */
    public default <A> A get(final Pop pop, final String label) throws IllegalArgumentException {
        if (Pop.mixed == pop) {
            return this.get(label);
        } else if (Pop.all == pop) {
            if (this.hasLabel(label)) {
                final Object object = this.get(label);
                if (object instanceof List)
                    return (A) object;
                else
                    return (A) Collections.singletonList(object);
            } else {
                return (A) Collections.emptyList();
            }
        } else {
            final Object object = this.get(label);
            if (object instanceof List) {
                return Pop.last == pop ? ((List<A>) object).get(((List) object).size() - 1) : ((List<A>) object).get(0);
            } else
                return (A) object;
        }
    }

    /**
     * Get the object associated with the specified index into the path.
     *
     * @param index the index of the path
     * @param <A>   the type of the object associated with the index
     * @return the object associated with the index of the path
     */
    public default <A> A get(final int index) {
        return (A) this.objects().get(index);
    }

    /**
     * Return true if the path has the specified label, else return false.
     *
     * @param label the label to search for
     * @return true if the label exists in the path
     */
    public default boolean hasLabel(final String label) {
        return this.labels().stream().filter(labels -> labels.contains(label)).findAny().isPresent();
    }

    /**
     * An ordered list of the objects in the path.
     *
     * @return the objects of the path
     */
    public List<Object> objects();

    /**
     * An ordered list of the labels associated with the path
     * The set of labels for a particular step are ordered by the order in which {@link Path#extend(Object, Set)} was called.
     *
     * @return the labels of the path
     */
    public List<Set<String>> labels();

    @SuppressWarnings("CloneDoesntDeclareCloneNotSupportedException")
    public Path clone();

    /**
     * Determines whether the path is a simple or not. A simple path has no cycles and thus, no repeated objects.
     *
     * @return Whether the path is simple or not
     */
    public default boolean isSimple() {
        final List<Object> objects = this.objects();
        for (int i = 0; i < objects.size() - 1; i++) {
            for (int j = i + 1; j < objects.size(); j++) {
                if (Objects.equals(objects.get(i), objects.get(j)))
                    return false;
            }
        }
        return true;
    }

    public default Iterator<Object> iterator() {
        return this.objects().iterator();
    }

    public default void forEach(final BiConsumer<Object, Set<String>> consumer) {
        final List<Object> objects = this.objects();
        final List<Set<String>> labels = this.labels();
        for (int i = 0; i < objects.size(); i++) {
            consumer.accept(objects.get(i), labels.get(i));
        }
    }

    public default Stream<Pair<Object, Set<String>>> stream() {
        final List<Set<String>> labels = this.labels();
        final List<Object> objects = this.objects();
        return IntStream.range(0, this.size()).mapToObj(i -> Pair.with(objects.get(i), labels.get(i)));
    }

    public default boolean popEquals(final Pop pop, final Object other) {
        if (!(other instanceof Path))
            return false;
        final Path otherPath = (Path) other;
        return this.labels().stream().
                flatMap(Set::stream).
                noneMatch(label -> {
                    if (!otherPath.hasLabel(label)) return true;
                    final Object o1 = otherPath.get(pop, label);
                    final Object o2 = this.get(pop, label);
                    return !((null == o1 && null == o2) || (o1 != null && o1.equals(o2)));
                });
    }

    /**
     * Isolate a sub-path from the path object. The isolation is based solely on the path labels.
     * The to-label is inclusive. Thus, from "b" to "c" would isolate the example path as follows {@code a,[b,c],d}.
     * Note that if there are multiple path segments with the same label, then its the last occurrence that is isolated.
     * For instance, from "b" to "c" would be {@code a,b,[b,c,d,c]}.
     *
     * @param fromLabel The label to start recording the sub-path from.
     * @param toLabel   The label to end recording the sub-path to.
     * @return the isolated sub-path.
     */
    public default Path subPath(final String fromLabel, final String toLabel) {
        if (null == fromLabel && null == toLabel)
            return this;
        else {
            Path subPath = MutablePath.make();
            final int size = this.size();
            int fromIndex = -1;
            int toIndex = -1;
            for (int i = size - 1; i >= 0; i--) {
                final Set<String> labels = this.labels().get(i);
                if (-1 == fromIndex && labels.contains(fromLabel))
                    fromIndex = i;
                if (-1 == toIndex && labels.contains(toLabel))
                    toIndex = i;
            }
            if (null != fromLabel && -1 == fromIndex)
                throw Path.Exceptions.couldNotLocatePathFromLabel(fromLabel);
            if (null != toLabel && -1 == toIndex)
                throw Path.Exceptions.couldNotLocatePathToLabel(toLabel);

            if (fromIndex == -1)
                fromIndex = 0;
            if (toIndex == -1)
                toIndex = size-1;
            if (fromIndex > toIndex)
                throw Path.Exceptions.couldNotIsolatedSubPath(fromLabel, toLabel);
            for (int i = fromIndex; i <= toIndex; i++) {
                final Set<String> labels = this.labels().get(i);
                subPath.extend(this.get(i), labels);
            }
            return subPath;
        }
    }

    public static class Exceptions {

        public static IllegalArgumentException stepWithProvidedLabelDoesNotExist(final String label) {
            return new IllegalArgumentException("The step with label " + label + " does not exist");
        }

        public static IllegalArgumentException couldNotLocatePathFromLabel(final String fromLabel) {
            return new IllegalArgumentException("Could not locate path from-label: " + fromLabel);
        }

        public static IllegalArgumentException couldNotLocatePathToLabel(final String toLabel) {
            return new IllegalArgumentException("Could not locate path to-label: " + toLabel);
        }

        public static IllegalArgumentException couldNotIsolatedSubPath(final String fromLabel, final String toLabel) {
            return new IllegalArgumentException("Could not isolate path because from comes after to: " + fromLabel + "->" + toLabel);
        }
    }
}
