package autostep;

import java.math.BigDecimal;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;
import java.util.Map;
import java.util.Map.Entry;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import autostep.chart.BaseStepChart;
import autostep.chart.ParsedStepChart;
import autostep.feet.Foot;
import autostep.feet.FootWeight;
import autostep.feet.Limb;
import autostep.feet.LimbPlacement;
import autostep.feet.LimbPlacement.LimbPlacementBuilder;
import autostep.pad.PadArrow;
import autostep.pad.SinglesPad;
import autostep.step.ArrowType;
import autostep.step.Mine;
import autostep.step.ParsedStep;
import autostep.step.Step;
import autostep.step.trailing.Trailing;
import autostep.step.trailing.TrailingEnd;

import com.google.common.base.Function;
import com.google.common.base.Preconditions;
import com.google.common.base.Predicate;
import com.google.common.collect.FluentIterable;
import com.google.common.collect.ImmutableList;
import com.google.common.collect.ImmutableList.Builder;
import com.google.common.collect.ImmutableSet;
import com.google.common.collect.Lists;
import com.google.common.collect.Multimap;

/**
 * Parser to convert a {@link BaseStepChart} to {@link ParsedStepChart}.
 *
 * @author rchiu
 *
 */
public final class StepChartStepParser {

    private static final Logger logger = LoggerFactory.getLogger(StepChartStepParser.class);

    private StepChartStepParser() {
    }

    static final Predicate<LimbPlacement> validAnglePredicate = new Predicate<LimbPlacement>() {
        @Override
        public boolean apply(LimbPlacement input) {
            double angle = input.getAngle();
            return angle <= 180 && angle >= -180;
        }
    };

    private static final Predicate<ParsedStep> validStepPredicate = new Predicate<ParsedStep>() {
        @Override
        public boolean apply(ParsedStep input) {
            return validAnglePredicate.apply(input.getLimbPlacement());
        }
    };

    public static List<ParsedStep> parse(BaseStepChart baseStepChart) {
        ListIterator<Step> stepIter = baseStepChart.getSteps().listIterator();
        List<ParsedStep> nextNodes = Lists.newArrayList();
        List<ParsedStep> rootNodes = evaluate(new ParsedStep(Step.PLACEHOLDER_STEP, SinglesPad.NEUTRAL, baseStepChart
                .getHeader().getOffset()), stepIter.next());
        logger.debug("First step evaluated to {} steps", rootNodes.size());
        Preconditions.checkArgument(rootNodes.size() != 0);

        List<ParsedStep> prevNodes = rootNodes;
        while (stepIter.hasNext()) {
            int stepIndex = stepIter.nextIndex();
            Step step = stepIter.next();
            for (int branchIndex = 0; branchIndex < prevNodes.size(); branchIndex++) {
                ParsedStep prevStep = prevNodes.get(branchIndex);
                List<ParsedStep> possibleSteps = evaluate(prevStep, step);
                if (possibleSteps.size() == 0) {
                    logger.debug("Branch did not evaluate any valid steps, deleting");
                    prevStep.invalidateBranch();
                } else {
                    logger.debug("step #{} = {} on branch {} evaluated to {} steps: {}", stepIndex, step, branchIndex,
                            possibleSteps.size(), possibleSteps);
                    prevStep.addChildren(possibleSteps);
                    nextNodes.addAll(possibleSteps);
                }
            }
            // combine multiple branches that end up with the same parsed step
            for (int branchIndex = nextNodes.size() - 1; branchIndex >= 0; branchIndex--) {
                LimbPlacement feet = nextNodes.get(branchIndex).getLimbPlacement();
                for (int otherBranchIndex = branchIndex - 1; otherBranchIndex >= 0; otherBranchIndex--) {
                    ParsedStep other = nextNodes.get(otherBranchIndex);
                    if (other.getLimbPlacement().equals(feet)) {
                        logger.debug("Branches {} and {} match on {}, removing {}", branchIndex, otherBranchIndex,
                                feet, branchIndex);
                        other.addParents(nextNodes.get(branchIndex).getParentNodes());
                        nextNodes.remove(branchIndex);
                        break;
                    }
                }
            }

            if (nextNodes.isEmpty()) {
                logger.error("No valid branches left after parsing " + step.prettyPrint() + " #" + stepIndex);
                return prevNodes;
            }
            prevNodes = nextNodes;
            nextNodes = Lists.newArrayList();
        }

        ParsedStep dummyStep = new ParsedStep(Step.PLACEHOLDER_STEP, SinglesPad.NEUTRAL);
        dummyStep.addParents(prevNodes);
        return Collections.singletonList(dummyStep);
    }

    public static ParsedStepChart buildChartFromLeaf(BaseStepChart base, ParsedStep leaf) {
        Preconditions.checkArgument(leaf.getChildrenNodes().isEmpty());
        Builder<ParsedStep> builder = ImmutableList.builder();
        ParsedStep currNode = leaf;
        builder.add(currNode);
        while (!currNode.getParentNodes().isEmpty()) {
            currNode = currNode.getParentNodes().get(0);
            builder.add(currNode);
        }
        return new ParsedStepChart(base, builder.build().reverse());
    }

    static List<ParsedStep> evaluate(final ParsedStep prevStep, final Step step) {
        logger.debug("Evaluating {}", step);
        // copy of arrows in the next step to be placed
        final Map<PadArrow, ArrowType> unplacedArrows = step.getArrows();
        // determined locations of limbs for current step
        final LimbPlacementBuilder currentLimbs = new LimbPlacementBuilder();
        // copy of previous limb placement to overlay after setting limbs on
        // current step's arrows
        final LimbPlacementBuilder prevLimbs = new LimbPlacementBuilder(prevStep.getLimbPlacement());

        if (unplacedArrows.size() == 0) {
            logger.debug("No arrows in step, returning step with previous foot placement");
            return Collections.singletonList(new ParsedStep(step, prevLimbs, prevStep));
        }

        // preprocess mines and trailing notes
        int numNotes = unplacedArrows.size();
        for (PadArrow arrow : ImmutableSet.copyOf(unplacedArrows.keySet())) {
            ArrowType stepType = unplacedArrows.get(arrow);
            Limb limb = prevLimbs.limbOn(arrow);
            if (stepType instanceof Mine) {
                // if it is a mine, shift previous limb on that arrow to its
                // default
                if (limb != null) {
                    logger.debug("Found mine on {}, moving {} to default", arrow, limb);
                    prevLimbs.shiftLimbToDefault(limb);
                    if (limb instanceof Foot && prevLimbs.getWeight().getFoot() == limb) {
                        prevLimbs.setWeight(FootWeight.BALANCED);
                    }
                }
                unplacedArrows.remove(arrow);
                numNotes--;
            } else if (stepType instanceof Trailing || stepType instanceof TrailingEnd) {
                // if it is a trailing note, hold trail
                logger.debug("Found trailing arrow on {}, planting {}", arrow, limb);
                currentLimbs.put(limb, arrow);
                unplacedArrows.remove(arrow);
            }
        }

        // if no parsable arrows left, then keep the same
        if (unplacedArrows.size() == 0) {
            logger.debug("All arrows were trailing or mines");
            // if both feet on TrailingEnd, set weight to balanced
            if (step.getArrows().get(currentLimbs.get(Foot.LEFT)) instanceof TrailingEnd
                    && step.getArrows().get(currentLimbs.get(Foot.RIGHT)) instanceof TrailingEnd) {
                prevLimbs.setWeight(FootWeight.BALANCED);
            }
            return Collections.singletonList(new ParsedStep(step, prevLimbs, prevStep));
        }

        // find possible configurations
        FluentIterable<LimbPlacementBuilder> allConfigs = FluentIterable.from(SinglesPad.LIMB_CONFIGURATIONS
                .get(numNotes));
        logger.debug("Using starting set for numArrows = {} with size = {}", numNotes, allConfigs.size());
        logger.debug("Matching unplaced arrows {} and current limbs {}", unplacedArrows.keySet(),
                currentLimbs.mapping());

        // filter by configurations matching unplacedArrows and currentLimbs
        FluentIterable<LimbPlacementBuilder> matchingConfigs = allConfigs.filter(new Predicate<LimbPlacementBuilder>() {
            @Override
            public boolean apply(LimbPlacementBuilder input) {
                Map<Limb, PadArrow> mapping = input.mapping();
                // arrows hit by step must be in input
                for (PadArrow arrow : unplacedArrows.keySet()) {
                    if (!mapping.containsValue(arrow)) {
                        return false;
                    }
                }
                // limbs currently on an arrow must be on that arrow
                for (Entry<Limb, PadArrow> entry : currentLimbs.mapping().entrySet()) {
                    if (SinglesPad.ORDERED_ARROWS.contains(entry.getValue())
                            && input.get(entry.getKey()) != entry.getValue()) {
                        return false;
                    }
                }
                return true;
            }
        });

        logger.debug("After filtering matching configs, size = {}", matchingConfigs.size());
        if (matchingConfigs.size() == 0) {
            // exit when facing an impossible configuration, ex. current limbs =
            // {lf : ->, rf : <-}, unplaced arrows = [\/]
            return ImmutableList.of();
        }

        // if heading into a jump, balance weight to avoid the situation
        // prev = {lf : <-, RF : /\}, step = <-\/____ => configs = {lf : \/, rf
        // : <-}, {lf : <-, rf: \/}
        // where FeetDistance = W,T = 2, 4, W,T = 4, 4 => best distance = {lf :
        // \/, rf : <-}
        if (unplacedArrows.size() >= 2) {
            prevLimbs.setWeight(FootWeight.BALANCED);
        }

        // map each configuration by distance to filter configurations with
        // minimum distance, biased by foot weight
        Multimap<FeetDistance, LimbPlacementBuilder> configsByDistance = matchingConfigs
                .index(new Function<LimbPlacementBuilder, FeetDistance>() {
                    @Override
                    public FeetDistance apply(LimbPlacementBuilder input) {
                        BigDecimal left = SinglesPad.dist2(input.get(Foot.LEFT), prevLimbs.get(Foot.LEFT));
                        BigDecimal right = SinglesPad.dist2(input.get(Foot.RIGHT), prevLimbs.get(Foot.RIGHT));
                        return new FeetDistance(left, right, prevLimbs.getWeight());
                    }
                });
        logger.debug("Distances: " + configsByDistance);

        List<FeetDistance> distances = Lists.newArrayList(configsByDistance.keySet());
        Collections.sort(distances);
        Iterator<FeetDistance> iter = distances.iterator();
        FeetDistance minDist = iter.next();
        List<LimbPlacementBuilder> leastDistConfigs = Lists.newArrayList(configsByDistance.get(minDist));
        // if balanced, account for nearby matching distances
        if (prevLimbs.getWeight() == FootWeight.BALANCED) {
            while (iter.hasNext()) {
                FeetDistance nextDist = iter.next();
                if (minDist.tolerablyClose(nextDist)) {
                    leastDistConfigs.addAll(configsByDistance.get(nextDist));
                } else {
                    break;
                }
            }
        }
        FluentIterable<LimbPlacementBuilder> minimizedConfigs = FluentIterable.from(leastDistConfigs);
        logger.debug("Minimum distance is {} with {} matching configs: {}", minDist, minimizedConfigs.size(),
                minimizedConfigs);

        Preconditions.checkArgument(minimizedConfigs.size() > 0);

        // filter impossible configurations
        List<ParsedStep> possibleSteps = minimizedConfigs.transform(new Function<LimbPlacementBuilder, ParsedStep>() {
            @Override
            public ParsedStep apply(LimbPlacementBuilder input) {
                input.determineWeight(unplacedArrows.keySet());
                return new ParsedStep(step, input, prevStep);
            }
        }).filter(validStepPredicate).toList();

        return possibleSteps;
    }

    private static class FeetDistance implements Comparable<FeetDistance> {
        private static final BigDecimal TOLERANCE = new BigDecimal(2);

        private final BigDecimal totalDist;
        private final BigDecimal weightedDist;

        public FeetDistance(BigDecimal left, BigDecimal right, FootWeight weight) {
            this.totalDist = left.add(right);
            switch (weight) {
                case BALANCED:
                    this.weightedDist = BigDecimal.ZERO;
                    break;
                case LEFT:
                    this.weightedDist = left;
                    break;
                case RIGHT:
                    this.weightedDist = right;
                    break;
                default:
                    throw new IllegalArgumentException("Unrecognized foot weight " + weight);
            }
        }

        public boolean tolerablyClose(FeetDistance other) {
            if (weightedDist.compareTo(other.weightedDist) != 0) {
                return false;
            }
            if (totalDist.subtract(other.totalDist).abs().compareTo(TOLERANCE) > 0) {
                return false;
            }
            return true;
        }

        @Override
        public int compareTo(FeetDistance o) {
            // first compare distance moved by weighted foot
            int dist = weightedDist.compareTo(o.weightedDist);
            // then by total distance
            return dist == 0 ? totalDist.compareTo(o.totalDist) : dist;

        }

        @Override
        public String toString() {
            return String.format("W,T: %s,%s", weightedDist, totalDist);
        }

        @Override
        public boolean equals(Object o) {
            if (!(o instanceof FeetDistance)) {
                return false;
            }
            FeetDistance fd = (FeetDistance) o;
            if (this.compareTo(fd) != 0) {
                return false;
            }
            return true;
        }

        @Override
        public int hashCode() {
            return totalDist.hashCode() ^ weightedDist.hashCode();
        }

    }
}
