/*
 * 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.step.map;

import org.apache.tinkerpop.gremlin.process.traversal.Path;
import org.apache.tinkerpop.gremlin.process.traversal.Pop;
import org.apache.tinkerpop.gremlin.process.traversal.Step;
import org.apache.tinkerpop.gremlin.process.traversal.Traversal;
import org.apache.tinkerpop.gremlin.process.traversal.Traverser;
import org.apache.tinkerpop.gremlin.process.traversal.step.Barrier;
import org.apache.tinkerpop.gremlin.process.traversal.step.PathProcessor;
import org.apache.tinkerpop.gremlin.process.traversal.step.Scoping;
import org.apache.tinkerpop.gremlin.process.traversal.step.TraversalParent;
import org.apache.tinkerpop.gremlin.process.traversal.step.filter.AndStep;
import org.apache.tinkerpop.gremlin.process.traversal.step.filter.ConnectiveStep;
import org.apache.tinkerpop.gremlin.process.traversal.step.filter.NotStep;
import org.apache.tinkerpop.gremlin.process.traversal.step.filter.WherePredicateStep;
import org.apache.tinkerpop.gremlin.process.traversal.step.filter.WhereTraversalStep;
import org.apache.tinkerpop.gremlin.process.traversal.step.sideEffect.StartStep;
import org.apache.tinkerpop.gremlin.process.traversal.step.util.AbstractStep;
import org.apache.tinkerpop.gremlin.process.traversal.step.util.ComputerAwareStep;
import org.apache.tinkerpop.gremlin.process.traversal.step.util.ProfileStep;
import org.apache.tinkerpop.gremlin.process.traversal.strategy.decoration.ConnectiveStrategy;
import org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization.PathRetractionStrategy;
import org.apache.tinkerpop.gremlin.process.traversal.traverser.TraverserRequirement;
import org.apache.tinkerpop.gremlin.process.traversal.traverser.util.TraverserSet;
import org.apache.tinkerpop.gremlin.process.traversal.util.DefaultTraversal;
import org.apache.tinkerpop.gremlin.process.traversal.util.PathUtil;
import org.apache.tinkerpop.gremlin.process.traversal.util.TraversalHelper;
import org.apache.tinkerpop.gremlin.structure.util.StringFactory;
import org.apache.tinkerpop.gremlin.util.iterator.IteratorUtils;

import java.io.Serializable;
import java.lang.reflect.InvocationTargetException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.Optional;
import java.util.Set;
import java.util.function.Function;
import java.util.stream.Collectors;
import java.util.stream.Stream;

/**
 * @author Marko A. Rodriguez (http://markorodriguez.com)
 */
public final class MatchStep<S, E> extends ComputerAwareStep<S, Map<String, E>> implements TraversalParent, Scoping, PathProcessor {

    public enum TraversalType {WHERE_PREDICATE, WHERE_TRAVERSAL, MATCH_TRAVERSAL}

    private List<Traversal.Admin<Object, Object>> matchTraversals = new ArrayList<>();
    private boolean first = true;
    private Set<String> matchStartLabels = new HashSet<>();
    private Set<String> matchEndLabels = new HashSet<>();
    private Set<String> scopeKeys = null;
    private final ConnectiveStep.Connective connective;
    private final String computedStartLabel;
    private MatchAlgorithm matchAlgorithm;
    private Class<? extends MatchAlgorithm> matchAlgorithmClass = CountMatchAlgorithm.class; // default is CountMatchAlgorithm (use MatchAlgorithmStrategy to change)
    private Map<String, Set<String>> referencedLabelsMap; // memoization of referenced labels for MatchEndSteps (Map<startStepId, referencedLabels>)

    private Set<List<Object>> dedups = null;
    private Set<String> dedupLabels = null;
    private Set<String> keepLabels = null;

    public MatchStep(final Traversal.Admin traversal, final ConnectiveStep.Connective connective, final Traversal... matchTraversals) {
        super(traversal);
        this.connective = connective;
        this.matchTraversals = (List) Stream.of(matchTraversals).map(Traversal::asAdmin).collect(Collectors.toList());
        this.matchTraversals.forEach(this::configureStartAndEndSteps); // recursively convert to MatchStep, MatchStartStep, or MatchEndStep
        this.matchTraversals.forEach(this::integrateChild);
        this.computedStartLabel = Helper.computeStartLabel(this.matchTraversals);
    }

    //////////////////
    private String pullOutVariableStartStepToParent(final WhereTraversalStep<?> whereStep) {
        return this.pullOutVariableStartStepToParent(new HashSet<>(), whereStep.getLocalChildren().get(0), true).size() != 1 ? null : pullOutVariableStartStepToParent(new HashSet<>(), whereStep.getLocalChildren().get(0), false).iterator().next();
    }

    private Set<String> pullOutVariableStartStepToParent(final Set<String> selectKeys, final Traversal.Admin<?, ?> traversal, boolean testRun) {
        final Step<?, ?> startStep = traversal.getStartStep();
        if (startStep instanceof WhereTraversalStep.WhereStartStep && !((WhereTraversalStep.WhereStartStep) startStep).getScopeKeys().isEmpty()) {
            selectKeys.addAll(((WhereTraversalStep.WhereStartStep<?>) startStep).getScopeKeys());
            if (!testRun) ((WhereTraversalStep.WhereStartStep) startStep).removeScopeKey();
        } else if (startStep instanceof ConnectiveStep || startStep instanceof NotStep) {
            ((TraversalParent) startStep).getLocalChildren().forEach(child -> this.pullOutVariableStartStepToParent(selectKeys, child, testRun));
        }
        return selectKeys;
    }
    //////////////////

    private void configureStartAndEndSteps(final Traversal.Admin<?, ?> matchTraversal) {
        ConnectiveStrategy.instance().apply(matchTraversal);
        // START STEP to MatchStep OR MatchStartStep
        final Step<?, ?> startStep = matchTraversal.getStartStep();
        if (startStep instanceof ConnectiveStep) {
            final MatchStep matchStep = new MatchStep(matchTraversal,
                    startStep instanceof AndStep ? ConnectiveStep.Connective.AND : ConnectiveStep.Connective.OR,
                    ((ConnectiveStep<?>) startStep).getLocalChildren().toArray(new Traversal[((ConnectiveStep<?>) startStep).getLocalChildren().size()]));
            TraversalHelper.replaceStep(startStep, matchStep, matchTraversal);
            this.matchStartLabels.addAll(matchStep.matchStartLabels);
            this.matchEndLabels.addAll(matchStep.matchEndLabels);
        } else if (startStep instanceof NotStep) {
            final DefaultTraversal notTraversal = new DefaultTraversal<>();
            TraversalHelper.removeToTraversal(startStep, startStep.getNextStep(), notTraversal);
            matchTraversal.addStep(0, new WhereTraversalStep<>(matchTraversal, notTraversal));
            this.configureStartAndEndSteps(matchTraversal);
        } else if (StartStep.isVariableStartStep(startStep)) {
            final String label = startStep.getLabels().iterator().next();
            this.matchStartLabels.add(label);
            TraversalHelper.replaceStep((Step) matchTraversal.getStartStep(), new MatchStartStep(matchTraversal, label), matchTraversal);
        } else if (startStep instanceof WhereTraversalStep) {  // necessary for GraphComputer so the projection is not select'd from a path
            final WhereTraversalStep<?> whereStep = (WhereTraversalStep<?>) startStep;
            TraversalHelper.insertBeforeStep(new MatchStartStep(matchTraversal, this.pullOutVariableStartStepToParent(whereStep)), (Step) whereStep, matchTraversal);             // where(as('a').out()) -> as('a').where(out())
        } else if (startStep instanceof WherePredicateStep) {  // necessary for GraphComputer so the projection is not select'd from a path
            final WherePredicateStep<?> whereStep = (WherePredicateStep<?>) startStep;
            TraversalHelper.insertBeforeStep(new MatchStartStep(matchTraversal, whereStep.getStartKey().orElse(null)), (Step) whereStep, matchTraversal);   // where('a',eq('b')) --> as('a').where(eq('b'))
            whereStep.removeStartKey();
        } else {
            throw new IllegalArgumentException("All match()-traversals must have a single start label (i.e. variable): " + matchTraversal);
        }
        // END STEP to MatchEndStep
        final Step<?, ?> endStep = matchTraversal.getEndStep();
        if (endStep.getLabels().size() > 1)
            throw new IllegalArgumentException("The end step of a match()-traversal can have at most one label: " + endStep);
        final String label = endStep.getLabels().size() == 0 ? null : endStep.getLabels().iterator().next();
        if (null != label) endStep.removeLabel(label);
        final Step<?, ?> matchEndStep = new MatchEndStep(matchTraversal, label);
        if (null != label) this.matchEndLabels.add(label);
        matchTraversal.asAdmin().addStep(matchEndStep);

        // this turns barrier computations into locally computable traversals
        if (TraversalHelper.getStepsOfAssignableClass(Barrier.class, matchTraversal).stream().
                filter(s -> !(s instanceof NoOpBarrierStep)).findAny().isPresent()) { // exclude NoOpBarrierSteps from the determination as they are optimization barriers
            final Traversal.Admin newTraversal = new DefaultTraversal<>();
            TraversalHelper.removeToTraversal(matchTraversal.getStartStep().getNextStep(), matchTraversal.getEndStep(), newTraversal);
            TraversalHelper.insertAfterStep(new TraversalFlatMapStep<>(matchTraversal, newTraversal), matchTraversal.getStartStep(), matchTraversal);
        }
    }


    public ConnectiveStep.Connective getConnective() {
        return this.connective;
    }

    public void addGlobalChild(final Traversal.Admin<?, ?> globalChildTraversal) {
        this.configureStartAndEndSteps(globalChildTraversal);
        this.matchTraversals.add(this.integrateChild(globalChildTraversal));
    }

    @Override
    public void removeGlobalChild(final Traversal.Admin<?, ?> globalChildTraversal) {
        this.matchTraversals.remove(globalChildTraversal);
    }

    @Override
    public List<Traversal.Admin<Object, Object>> getGlobalChildren() {
        return Collections.unmodifiableList(this.matchTraversals);
    }

    @Override
    public void setKeepLabels(final Set<String> keepLabels) {
        this.keepLabels = new HashSet<>(keepLabels);
        if (null != this.dedupLabels)
            this.keepLabels.addAll(this.dedupLabels);
    }

    @Override
    public Set<String> getKeepLabels() {
        return keepLabels;
    }

    public Set<String> getMatchEndLabels() {
        return this.matchEndLabels;
    }

    public Set<String> getMatchStartLabels() {
        return this.matchStartLabels;
    }

    @Override
    public Set<String> getScopeKeys() {
        if (null == this.scopeKeys) {
            this.scopeKeys = new HashSet<>();
            this.matchTraversals.forEach(traversal -> {
                if (traversal.getStartStep() instanceof Scoping)
                    this.scopeKeys.addAll(((Scoping) traversal.getStartStep()).getScopeKeys());
                if (traversal.getEndStep() instanceof Scoping)
                    this.scopeKeys.addAll(((Scoping) traversal.getEndStep()).getScopeKeys());
            });
            this.scopeKeys.removeAll(this.matchEndLabels);
            this.scopeKeys.remove(this.computedStartLabel);
            this.scopeKeys = Collections.unmodifiableSet(this.scopeKeys);
        }
        return this.scopeKeys;
    }

    @Override
    public String toString() {
        return StringFactory.stepString(this, this.dedupLabels, this.connective, this.matchTraversals);
    }

    @Override
    public void reset() {
        super.reset();
        this.first = true;
    }

    public void setMatchAlgorithm(final Class<? extends MatchAlgorithm> matchAlgorithmClass) {
        this.matchAlgorithmClass = matchAlgorithmClass;
    }

    public MatchAlgorithm getMatchAlgorithm() {
        if (null == this.matchAlgorithm)
            this.initializeMatchAlgorithm(this.traverserStepIdAndLabelsSetByChild);
        return this.matchAlgorithm;
    }

    @Override
    public MatchStep<S, E> clone() {
        final MatchStep<S, E> clone = (MatchStep<S, E>) super.clone();
        clone.matchTraversals = new ArrayList<>();
        for (final Traversal.Admin<Object, Object> traversal : this.matchTraversals) {
            clone.matchTraversals.add(traversal.clone());
        }
        if (this.dedups != null) clone.dedups = new HashSet<>();
        clone.standardAlgorithmBarrier = new TraverserSet();
        return clone;
    }

    @Override
    public void setTraversal(final Traversal.Admin<?, ?> parentTraversal) {
        super.setTraversal(parentTraversal);
        for (final Traversal.Admin<Object, Object> traversal : this.matchTraversals) {
            this.integrateChild(traversal);
        }
    }

    public void setDedupLabels(final Set<String> labels) {
        if (!labels.isEmpty()) {
            this.dedups = new HashSet<>();
            this.dedupLabels = new HashSet<>(labels);
            if (null != this.keepLabels)
                this.keepLabels.addAll(this.dedupLabels);
        }
    }

    /*public boolean isDeduping() {
        return this.dedupLabels != null;
    }*/

    private boolean isDuplicate(final Traverser<S> traverser) {
        if (null == this.dedups)
            return false;
        final Path path = traverser.path();
        for (final String label : this.dedupLabels) {
            if (!path.hasLabel(label))
                return false;
        }
        final List<Object> objects = new ArrayList<>(this.dedupLabels.size());
        for (final String label : this.dedupLabels) {
            objects.add(path.get(Pop.last, label));
        }
        return this.dedups.contains(objects);
    }

    private boolean hasMatched(final ConnectiveStep.Connective connective, final Traverser.Admin<S> traverser) {
        int counter = 0;
        boolean matched = false;
        for (final Traversal.Admin<Object, Object> matchTraversal : this.matchTraversals) {
            if (traverser.getTags().contains(matchTraversal.getStartStep().getId())) {
                if (connective == ConnectiveStep.Connective.OR) {
                    matched = true;
                    break;
                }
                counter++;
            }
        }
        if (!matched)
            matched = this.matchTraversals.size() == counter;
        if (matched && this.dedupLabels != null) {
            final Path path = traverser.path();
            final List<Object> objects = new ArrayList<>(this.dedupLabels.size());
            for (final String label : this.dedupLabels) {
                objects.add(path.get(Pop.last, label));
            }
            this.dedups.add(objects);
        }
        return matched;
    }

    private Map<String, E> getBindings(final Traverser<S> traverser) {
        final Map<String, E> bindings = new HashMap<>();
        traverser.path().forEach((object, labels) -> {
            for (final String label : labels) {
                if (this.matchStartLabels.contains(label) || this.matchEndLabels.contains(label))
                    bindings.put(label, (E) object);
            }
        });
        return bindings;
    }

    private void initializeMatchAlgorithm(final boolean onComputer) {
        try {
            this.matchAlgorithm = this.matchAlgorithmClass.getConstructor().newInstance();
        } catch (final NoSuchMethodException | IllegalAccessException | InvocationTargetException | InstantiationException e) {
            throw new IllegalStateException(e.getMessage(), e);
        }
        this.matchAlgorithm.initialize(onComputer, this.matchTraversals);
    }

    private boolean hasPathLabel(final Path path, final Set<String> labels) {
        for (final String label : labels) {
            if (path.hasLabel(label))
                return true;
        }
        return false;
    }

    private Map<String, Set<String>> getReferencedLabelsMap() {
        if (null == this.referencedLabelsMap) {
            this.referencedLabelsMap = new HashMap<>();
            for (final Traversal.Admin<?, ?> traversal : this.matchTraversals) {
                final Set<String> referencedLabels = new HashSet<>();
                for (final Step<?, ?> step : traversal.getSteps()) {
                    referencedLabels.addAll(PathUtil.getReferencedLabels(step));
                }
                this.referencedLabelsMap.put(traversal.getStartStep().getId(), referencedLabels);
            }
        }
        return this.referencedLabelsMap;
    }

    private TraverserSet standardAlgorithmBarrier = new TraverserSet();

    @Override
    protected Iterator<Traverser.Admin<Map<String, E>>> standardAlgorithm() throws NoSuchElementException {
        while (true) {
            if (this.first) {
                this.first = false;
                this.initializeMatchAlgorithm(false);
                if (null != this.keepLabels &&
                        this.keepLabels.containsAll(this.matchEndLabels) &&
                        this.keepLabels.containsAll(this.matchStartLabels))
                    this.keepLabels = null;
            } else { // TODO: if(standardAlgorithmBarrier.isEmpty()) -- leads to consistent counts without retracting paths, but orders of magnitude slower (or make Traverser.tags an equality concept)
                boolean stop = false;
                for (final Traversal.Admin<?, ?> matchTraversal : this.matchTraversals) {
                    while (matchTraversal.hasNext()) { // TODO: perhaps make MatchStep a LocalBarrierStep ??
                        this.standardAlgorithmBarrier.add(matchTraversal.nextTraverser());
                        if (null == this.keepLabels || this.standardAlgorithmBarrier.size() >= PathRetractionStrategy.MAX_BARRIER_SIZE) {
                            stop = true;
                            break;
                        }
                    }
                    if (stop) break;
                }
            }
            final Traverser.Admin traverser;
            if (this.standardAlgorithmBarrier.isEmpty()) {
                traverser = this.starts.next();
                if (!traverser.getTags().contains(this.getId())) {
                    traverser.getTags().add(this.getId()); // so the traverser never returns to this branch ever again
                    if (!this.hasPathLabel(traverser.path(), this.matchStartLabels))
                        traverser.addLabels(Collections.singleton(this.computedStartLabel)); // if the traverser doesn't have a legal start, then provide it the pre-computed one
                }
            } else
                traverser = this.standardAlgorithmBarrier.remove();

            ///
            if (!this.isDuplicate(traverser)) {
                if (hasMatched(this.connective, traverser))
                    return IteratorUtils.of(traverser.split(this.getBindings(traverser), this));

                if (this.connective == ConnectiveStep.Connective.AND) {
                    final Traversal.Admin<Object, Object> matchTraversal = this.getMatchAlgorithm().apply(traverser);
                    traverser.getTags().add(matchTraversal.getStartStep().getId());
                    matchTraversal.addStart(traverser); // determine which sub-pattern the traverser should try next
                } else {  // OR
                    for (final Traversal.Admin<?, ?> matchTraversal : this.matchTraversals) {
                        final Traverser.Admin split = traverser.split();
                        split.getTags().add(matchTraversal.getStartStep().getId());
                        matchTraversal.addStart(split);
                    }
                }
            }
        }
    }

    @Override
    protected Iterator<Traverser.Admin<Map<String, E>>> computerAlgorithm() throws NoSuchElementException {
        while (true) {
            if (this.first) {
                this.first = false;
                this.initializeMatchAlgorithm(true);
                if (null != this.keepLabels &&
                        this.keepLabels.containsAll(this.matchEndLabels) &&
                        this.keepLabels.containsAll(this.matchStartLabels))
                    this.keepLabels = null;
            }
            final Traverser.Admin traverser = this.starts.next();
            if (!traverser.getTags().contains(this.getId())) {
                traverser.getTags().add(this.getId()); // so the traverser never returns to this branch ever again
                if (!this.hasPathLabel(traverser.path(), this.matchStartLabels))
                    traverser.addLabels(Collections.singleton(this.computedStartLabel)); // if the traverser doesn't have a legal start, then provide it the pre-computed one
            }
            ///
            if (!this.isDuplicate(traverser)) {
                if (hasMatched(this.connective, traverser)) {
                    traverser.setStepId(this.getNextStep().getId());
                    traverser.addLabels(this.labels);
                    return IteratorUtils.of(traverser.split(this.getBindings(traverser), this));
                }
                if (this.connective == ConnectiveStep.Connective.AND) {
                    final Traversal.Admin<Object, Object> matchTraversal = this.getMatchAlgorithm().apply(traverser); // determine which sub-pattern the traverser should try next
                    traverser.getTags().add(matchTraversal.getStartStep().getId());
                    traverser.setStepId(matchTraversal.getStartStep().getId()); // go down the traversal match sub-pattern
                    return IteratorUtils.of(traverser);
                } else { // OR
                    final List<Traverser.Admin<Map<String, E>>> traversers = new ArrayList<>(this.matchTraversals.size());
                    for (final Traversal.Admin<?, ?> matchTraversal : this.matchTraversals) {
                        final Traverser.Admin split = traverser.split();
                        split.getTags().add(matchTraversal.getStartStep().getId());
                        split.setStepId(matchTraversal.getStartStep().getId());
                        traversers.add(split);
                    }
                    return traversers.iterator();
                }
            }
        }
    }

    @Override
    public int hashCode() {
        int result = super.hashCode() ^ this.connective.hashCode();
        for (final Traversal t : this.matchTraversals) {
            result ^= t.hashCode();
        }
        return result;
    }

    @Override
    public Set<TraverserRequirement> getRequirements() {
        return this.getSelfAndChildRequirements(TraverserRequirement.LABELED_PATH, TraverserRequirement.SIDE_EFFECTS);
    }

    //////////////////////////////

    public static final class MatchStartStep extends AbstractStep<Object, Object> implements Scoping {

        private final String selectKey;
        private Set<String> scopeKeys;
        private MatchStep<?, ?> parent;

        public MatchStartStep(final Traversal.Admin traversal, final String selectKey) {
            super(traversal);
            this.selectKey = selectKey;
        }

        @Override
        protected Traverser.Admin<Object> processNextStart() throws NoSuchElementException {
            if (null == this.parent)
                this.parent = (MatchStep<?, ?>) this.getTraversal().getParent();

            final Traverser.Admin<Object> traverser = this.starts.next();
            this.parent.getMatchAlgorithm().recordStart(traverser, this.getTraversal());
            // TODO: sideEffect check?
            return null == this.selectKey ? traverser : traverser.split(traverser.path().get(Pop.last, this.selectKey), this);
        }

        @Override
        public String toString() {
            return StringFactory.stepString(this, this.selectKey);
        }

        @Override
        public int hashCode() {
            int result = super.hashCode();
            if (null != this.selectKey)
                result ^= this.selectKey.hashCode();
            return result;
        }

        public Optional<String> getSelectKey() {
            return Optional.ofNullable(this.selectKey);
        }

        @Override
        public Set<String> getScopeKeys() {
            if (null == this.scopeKeys) { // computer the first time and then save resultant keys
                this.scopeKeys = new HashSet<>();
                if (null != this.selectKey)
                    this.scopeKeys.add(this.selectKey);
                final Set<String> endLabels = ((MatchStep<?, ?>) this.getTraversal().getParent()).getMatchEndLabels();
                TraversalHelper.anyStepRecursively(step -> {
                    if (step instanceof WherePredicateStep || step instanceof WhereTraversalStep) {
                        for (final String key : ((Scoping) step).getScopeKeys()) {
                            if (endLabels.contains(key)) this.scopeKeys.add(key);
                        }
                    }
                    return false;
                }, this.getTraversal());
                // this is the old way but it only checked for where() as the next step, not arbitrarily throughout traversal
                // just going to keep this in case something pops up in the future and this is needed as an original reference.
                /* if (this.getNextStep() instanceof WhereTraversalStep || this.getNextStep() instanceof WherePredicateStep)
                   this.scopeKeys.addAll(((Scoping) this.getNextStep()).getScopeKeys());*/
                this.scopeKeys = Collections.unmodifiableSet(this.scopeKeys);
            }
            return this.scopeKeys;
        }
    }

    public static final class MatchEndStep extends EndStep<Object> implements Scoping {

        private final String matchKey;
        private final Set<String> matchKeyCollection;
        private MatchStep<?, ?> parent;

        public MatchEndStep(final Traversal.Admin traversal, final String matchKey) {
            super(traversal);
            this.matchKey = matchKey;
            this.matchKeyCollection = null == matchKey ? Collections.emptySet() : Collections.singleton(this.matchKey);
        }


        private <S> Traverser.Admin<S> retractUnnecessaryLabels(final Traverser.Admin<S> traverser) {
            if (null == this.parent.getKeepLabels())
                return traverser;

            final Set<String> keepers = new HashSet<>(this.parent.getKeepLabels());
            final Set<String> tags = traverser.getTags();
            for (final Traversal.Admin<?, ?> matchTraversal : this.parent.matchTraversals) { // get remaining traversal patterns for the traverser
                final String startStepId = matchTraversal.getStartStep().getId();
                if (!tags.contains(startStepId)) {
                    keepers.addAll(this.parent.getReferencedLabelsMap().get(startStepId)); // get the reference labels required for those remaining traversals
                }
            }
            return PathProcessor.processTraverserPathLabels(traverser, keepers); // remove all reference labels that are no longer required
        }

        @Override
        protected Traverser.Admin<Object> processNextStart() throws NoSuchElementException {
            if (null == this.parent)
                this.parent = ((MatchStep) this.getTraversal().getParent().asStep());

            while (true) {
                final Traverser.Admin traverser = this.starts.next();
                // no end label
                if (null == this.matchKey) {
                    // if (this.traverserStepIdAndLabelsSetByChild) -- traverser equality is based on stepId, lets ensure they are all at the parent
                    traverser.setStepId(this.parent.getId());
                    this.parent.getMatchAlgorithm().recordEnd(traverser, this.getTraversal());
                    return this.retractUnnecessaryLabels(traverser);
                }
                // TODO: sideEffect check?
                // path check
                final Path path = traverser.path();
                if (!path.hasLabel(this.matchKey) || traverser.get().equals(path.get(Pop.last, this.matchKey))) {
                    // if (this.traverserStepIdAndLabelsSetByChild) -- traverser equality is based on stepId and thus, lets ensure they are all at the parent
                    traverser.setStepId(this.parent.getId());
                    traverser.addLabels(this.matchKeyCollection);
                    this.parent.getMatchAlgorithm().recordEnd(traverser, this.getTraversal());
                    return this.retractUnnecessaryLabels(traverser);
                }
            }
        }

        public Optional<String> getMatchKey() {
            return Optional.ofNullable(this.matchKey);
        }

        @Override
        public String toString() {
            return StringFactory.stepString(this, this.matchKey);
        }

        @Override
        public int hashCode() {
            int result = super.hashCode();
            if (null != this.matchKey)
                result ^= this.matchKey.hashCode();
            return result;
        }

        @Override
        public Set<String> getScopeKeys() {
            return this.matchKeyCollection;
        }
    }


    //////////////////////////////

    public static final class Helper {
        private Helper() {
        }

        public static Optional<String> getEndLabel(final Traversal.Admin<Object, Object> traversal) {
            final Step<?, ?> endStep = traversal.getEndStep();
            return endStep instanceof ProfileStep ?           // TOTAL HACK
                    ((MatchEndStep) endStep.getPreviousStep()).getMatchKey() :
                    ((MatchEndStep) endStep).getMatchKey();
        }

        public static Set<String> getStartLabels(final Traversal.Admin<Object, Object> traversal) {
            return ((Scoping) traversal.getStartStep()).getScopeKeys();
        }

        public static boolean hasStartLabels(final Traverser.Admin<Object> traverser, final Traversal.Admin<Object, Object> traversal) {
            for (final String label : Helper.getStartLabels(traversal)) {
                if (!traverser.path().hasLabel(label))
                    return false;
            }
            return true;
        }

        public static boolean hasEndLabel(final Traverser.Admin<Object> traverser, final Traversal.Admin<Object, Object> traversal) {
            final Optional<String> endLabel = Helper.getEndLabel(traversal);
            return endLabel.isPresent() && traverser.path().hasLabel(endLabel.get()); // TODO: !isPresent?
        }

        public static boolean hasExecutedTraversal(final Traverser.Admin<Object> traverser, final Traversal.Admin<Object, Object> traversal) {
            return traverser.getTags().contains(traversal.getStartStep().getId());
        }

        public static TraversalType getTraversalType(final Traversal.Admin<Object, Object> traversal) {
            final Step<?, ?> nextStep = traversal.getStartStep().getNextStep();
            if (nextStep instanceof WherePredicateStep)
                return TraversalType.WHERE_PREDICATE;
            else if (nextStep instanceof WhereTraversalStep)
                return TraversalType.WHERE_TRAVERSAL;
            else
                return TraversalType.MATCH_TRAVERSAL;
        }

        public static String computeStartLabel(final List<Traversal.Admin<Object, Object>> traversals) {
            {
                // a traversal start label, that's not used as an end label, must be the step's start label
                final Set<String> startLabels = new HashSet<>();
                final Set<String> endLabels = new HashSet<>();
                for (final Traversal.Admin<Object, Object> traversal : traversals) {
                    Helper.getEndLabel(traversal).ifPresent(endLabels::add);
                    startLabels.addAll(Helper.getStartLabels(traversal));
                }
                startLabels.removeAll(endLabels);
                if (!startLabels.isEmpty())
                    return startLabels.iterator().next();
            }
            final List<String> sort = new ArrayList<>();
            for (final Traversal.Admin<Object, Object> traversal : traversals) {
                Helper.getStartLabels(traversal).stream().filter(startLabel -> !sort.contains(startLabel)).forEach(sort::add);
                Helper.getEndLabel(traversal).ifPresent(endLabel -> {
                    if (!sort.contains(endLabel))
                        sort.add(endLabel);
                });
            }
            Collections.sort(sort, (a, b) -> {
                for (final Traversal.Admin<Object, Object> traversal : traversals) {
                    final Optional<String> endLabel = Helper.getEndLabel(traversal);
                    if (endLabel.isPresent()) {
                        final Set<String> startLabels = Helper.getStartLabels(traversal);
                        if (a.equals(endLabel.get()) && startLabels.contains(b))
                            return 1;
                        else if (b.equals(endLabel.get()) && startLabels.contains(a))
                            return -1;
                    }
                }
                return 0;
            });
            return sort.get(0);
        }
    }


    //////////////////////////////

    public interface MatchAlgorithm extends Function<Traverser.Admin<Object>, Traversal.Admin<Object, Object>>, Serializable {


        public static Function<List<Traversal.Admin<Object, Object>>, IllegalStateException> UNMATCHABLE_PATTERN = traversals -> new IllegalStateException("The provided match pattern is unsolvable: " + traversals);


        public void initialize(final boolean onComputer, final List<Traversal.Admin<Object, Object>> traversals);

        public default void recordStart(final Traverser.Admin<Object> traverser, final Traversal.Admin<Object, Object> traversal) {

        }

        public default void recordEnd(final Traverser.Admin<Object> traverser, final Traversal.Admin<Object, Object> traversal) {

        }
    }

    public static class GreedyMatchAlgorithm implements MatchAlgorithm {

        private List<Traversal.Admin<Object, Object>> traversals;

        @Override
        public void initialize(final boolean onComputer, final List<Traversal.Admin<Object, Object>> traversals) {
            this.traversals = traversals;
        }

        @Override
        public Traversal.Admin<Object, Object> apply(final Traverser.Admin<Object> traverser) {
            for (final Traversal.Admin<Object, Object> traversal : this.traversals) {
                if (!Helper.hasExecutedTraversal(traverser, traversal) && Helper.hasStartLabels(traverser, traversal))
                    return traversal;
            }
            throw UNMATCHABLE_PATTERN.apply(this.traversals);
        }
    }

    public static class CountMatchAlgorithm implements MatchAlgorithm {

        protected List<Bundle> bundles;
        protected int counter = 0;
        protected boolean onComputer;

        public void initialize(final boolean onComputer, final List<Traversal.Admin<Object, Object>> traversals) {
            this.onComputer = onComputer;
            this.bundles = traversals.stream().map(Bundle::new).collect(Collectors.toList());
        }

        @Override
        public Traversal.Admin<Object, Object> apply(final Traverser.Admin<Object> traverser) {
            // optimization to favor processing StarGraph local objects first to limit message passing (GraphComputer only)
            // TODO: generalize this for future MatchAlgorithms (given that 3.2.0 will focus on RealTimeStrategy, it will probably go there)
            if (this.onComputer) {
                final List<Set<String>> labels = traverser.path().labels();
                final Set<String> lastLabels = labels.get(labels.size() - 1);
                Collections.sort(this.bundles,
                        Comparator.<Bundle>comparingLong(b -> Helper.getStartLabels(b.traversal).stream().filter(startLabel -> !lastLabels.contains(startLabel)).count()).
                                thenComparingInt(b -> b.traversalType.ordinal()).
                                thenComparingDouble(b -> b.multiplicity));
            }

            Bundle startLabelsBundle = null;
            for (final Bundle bundle : this.bundles) {
                if (!Helper.hasExecutedTraversal(traverser, bundle.traversal) && Helper.hasStartLabels(traverser, bundle.traversal)) {
                    if (bundle.traversalType != TraversalType.MATCH_TRAVERSAL || Helper.hasEndLabel(traverser, bundle.traversal))
                        return bundle.traversal;
                    else if (null == startLabelsBundle)
                        startLabelsBundle = bundle;
                }
            }
            if (null != startLabelsBundle) return startLabelsBundle.traversal;
            throw UNMATCHABLE_PATTERN.apply(this.bundles.stream().map(record -> record.traversal).collect(Collectors.toList()));
        }

        @Override
        public void recordStart(final Traverser.Admin<Object> traverser, final Traversal.Admin<Object, Object> traversal) {
            this.getBundle(traversal).startsCount++;
        }

        @Override
        public void recordEnd(final Traverser.Admin<Object> traverser, final Traversal.Admin<Object, Object> traversal) {
            this.getBundle(traversal).incrementEndCount();
            if (!this.onComputer) {  // if on computer, sort on a per traverser-basis with bias towards local star graph
                if (this.counter < 200 || this.counter % 250 == 0) // aggressively sort for the first 200 results -- after that, sort every 250
                    Collections.sort(this.bundles, Comparator.<Bundle>comparingInt(b -> b.traversalType.ordinal()).thenComparingDouble(b -> b.multiplicity));
                this.counter++;
            }
        }

        protected Bundle getBundle(final Traversal.Admin<Object, Object> traversal) {
            for (final Bundle bundle : this.bundles) {
                if (bundle.traversal == traversal)
                    return bundle;
            }
            throw new IllegalStateException("No equivalent traversal could be found in " + CountMatchAlgorithm.class.getSimpleName() + ": " + traversal);
        }

        ///////////

        public class Bundle {
            public Traversal.Admin<Object, Object> traversal;
            public TraversalType traversalType;
            public long startsCount;
            public long endsCount;
            public double multiplicity;

            public Bundle(final Traversal.Admin<Object, Object> traversal) {
                this.traversal = traversal;
                this.traversalType = Helper.getTraversalType(traversal);
                this.startsCount = 0l;
                this.endsCount = 0l;
                this.multiplicity = 0.0d;
            }

            public final void incrementEndCount() {
                this.multiplicity = (double) ++this.endsCount / (double) this.startsCount;
            }
        }
    }
}