package net.ciklum.icfpc11.plan

import net.ciklum.icfpc11.parser.Command

import net.ciklum.icfpc11.domain.Card
import static net.ciklum.icfpc11.parser.Application.*
import net.ciklum.icfpc11.domain.GameError

/**
 * Plans the moves required to get the given Function (always incomplete, otherwise function gets evaluated)
 * TODO: check slot contents and maybe erase it by errrorneous move (1,slot,zero)
 * TODO: optimize, whether it is more efficient to create a constant in a buffer, and then get it over
 * @author mym
 */
@Typed
class MovePlanner {
    private int slot

    /**
     * Create the planner
     * @param slot Slot number we should get the final formula in (should be I beforehand)
     */
    MovePlanner(int slot) {
        this.slot = slot
    }

    /**
     * Plans the tree. Use {@link FunctionTreeBuilder} to construct the tree
     */
    List<Command> plan(BinaryTree tree) {
        def clone = tree.clone()
        clone = normalizeTheTree(clone)
        planTheTree(clone)
    }

    /**
     * note: modifies the tree itself
     * @author leo.fedorenko
     */
    BinaryTree normalizeTheTree(BinaryTree tree) {
        def root = tree

        // find leftmost deepest node
        def node = tree
        while (node.subtree) {
            node = node.subtree[0]
        }

        // now go up and unwrap overly complex right operands
        while (node != null) {
            if (node.subtree.size() >= 2 && node.subtree[1].hasChildren()) {
                // moving up anything on the right that has an operand
                def right = node.subtree[1]
                def parent = node.parent
                node.subtree.remove(1)
                int operands = right.operands()
                def s
                if (operands == 1) {
                    // long one-operand list is unrolled
                    def k = new BinaryTree(Card.K, [node])
                    s = new BinaryTree(Card.S, [k, right])
                    while (right.depth() > 1) {
                        def rightTop = new BinaryTree(right.card, [])
                        right = right.subtree[0]
                        s.subtree[1] = rightTop
                        k = new BinaryTree(Card.K, [s])
                        s = new BinaryTree(Card.S, [k, right])
                    }
                } else {
                    // if (operands == 2)
                    // two-op subtree is easily unrolled either
                    def k1 = new BinaryTree(Card.K, [node])
                    def s1 = new BinaryTree(Card.S, [k1])
                    def k = new BinaryTree(Card.K, [s1])
                    def rightUnrolled = new BinaryTree(right.card, [new BinaryTree(right.subtree[0].card, [new BinaryTree(right.subtree[1].card, [])])])
                    s = new BinaryTree(Card.S, [k, rightUnrolled])
                }
                s.parent = parent
                if (parent) {
                    parent.subtree[0] = s
                } else {
                    root = s
                }
                // and jump above not to repeat the unroll
                node = s
            }
            node = node.parent
            // System.err.println root
        }

        // at the root!
        return root
    }

    private List<Command> planTheTree(BinaryTree tree) {
        // find leftmost deepest node
        def node = tree
        while (node.subtree) {
            node = node.subtree[0]
        }

        def commands = []
        commands << new Command(RIGHT, slot, node.card)
        while (node != null) {
            // go right to the bottom
            if (node.subtree.size() >= 2) {
                def subnode = node.subtree[1]
                while (subnode != null) {
                    commands << new Command(RIGHT, slot, subnode.card)
                    subnode = subnode.subtree[0]
                }
            }
            // go left to parent
            if (node.parent) {
                commands << new Command(LEFT, slot, node.parent.card)
            }
            // and next
            node = node.parent
        }

        return commands
    }

    /*
    //TODO: commented out for later use?
    BinaryTree convertToTree(Function function) {
        if (function instanceof ConstantFunction) {
            return constantToTree(function.value)
        } else if (function instanceof CurriedFunction) {
            CurriedFunction cfunction = function
            return new BinaryTree(Card.fromFunction(function), (List<BinaryTree>) cfunction.args.collect {convertToTree(it)})
        } else {
            return new BinaryTree(Card.fromFunction(function), [])
        }
    }
    */


    static class BinaryTree {
        BinaryTree parent
        final Card card
        final List<BinaryTree> subtree

        BinaryTree(Card card, List<BinaryTree> subtree) {
            this.card = card
            this.subtree = subtree
            this.subtree.each {it.parent = this}
        }

        String toString() {
            "${card.name()}${subtree ? '(' + subtree.collect {it.toString()}.join(',') + ')' : ''}"
        }

        /** anything that has a child of itself is too complex to stay on right hand  */
        boolean hasChildren() {
            !subtree.isEmpty()
        }

        /**
         * currently we can only reduce right subtrees that are either:
         * - long one-operand lists
         * - two-operand command on two leafs
         */
        int operands() {
            if (subtree.isEmpty()) {
                return 0
            }
            if (subtree.size() == 1) {
                if (subtree[0].operands() <= 1) {
                    return 1
                } else {
                    throw new GameError("Sorry, but I cannot plan too complex one-op subtree ${toString()}")
                }
            } else if (subtree.size() == 2) {
                if (subtree[0].operands() == 0 && subtree[1].operands() == 0) {
                    return 2
                } else {
                    throw new GameError("Sorry, but I cannot plan too complex two-op subtree ${toString()}")
                }
            } else {
                throw new GameError("Sorry, but I cannot plan three-op subtree ${toString()}")
            }
        }

        /** applies to one-operand list-like trees (note: depth does not include this node) */
        int depth() {
            int d = 0
            BinaryTree node = this
            while (node.subtree) {
                d++
                node = node.subtree[0]
            }
            return d
        }

        int hashCode() {
            toString().hashCode()
        }

        boolean equals(BinaryTree that) {
            this.toString() == that.toString()
        }

        /** deep-clones the tree     */
        BinaryTree clone() {
            new BinaryTree(card, (List<BinaryTree>) subtree.collect {it.clone()})
        }
    }
}