package ee.ttu.algoritmid.trampoline;

import java.util.*;

public class HW02 {
    private Queue<Node> path;
    private int[][] map;
    private Node finish;

    public List<String> findMinJumps(int[][] mapOrigin) {
        this.map = deepCopy(mapOrigin); // V
        this.path = new LinkedList<>();
        this.finish = getFinish(); // 1
        path.add(finish); // 1

        Node current;
        Node best = null;

        while (!path.isEmpty()) { // sqrt V * V * log V
            current = path.poll(); // log V
            if (current.getX() == 0 && current.getY() == 0) { // 1
                best = current;
                break;
            }
            addPossiblePath(current); // sqrt(V) * log V
        }
        return composeAnswer(best);
    }

    private void eliminateRowsWithOnes(int x, int y) {
        int standardJump = map[x][y];
        if (standardJump == 1) {
            int xLocal = x;
            boolean canReplace = false;
            outer:
            while (xLocal != -1) {
                for (int j = y - 1; j >= 0; j--) {
                    if (map[xLocal][j] != standardJump) {
                        break outer;
                    }
                    if (canReplace) {
                        map[xLocal + 1][j] = -1;
                    }
                }
                canReplace = true;
                xLocal--;
            }
        }
    }

    private static int[][] deepCopy(int[][] original) {
        final int[][] result = new int[original.length][];
        for (int i = 0; i < original.length; i++) {
            result[i] = Arrays.copyOf(original[i], original[i].length);
        }
        return result;
    }

    private Node getFinish() {
        return new Node(map.length - 1, map[0].length - 1, 0, null);
    }

    private void addPossiblePath(Node target) { // sqrt(V) * log V
        for (int i = 0; i < target.getX(); i++) { // sqrt(V) * log V
            int y = target.getY(); // 1
            addToQueue(map[i][y], i, y, target); // log V
        }

        for (int i = 0; i < target.getY(); i++) { // sqrt(V) * log V
            int x = target.getX();
            addToQueue(map[x][i], x, i, target); // log V
        }
    }

    private void addToQueue(int jump, int x, int y, Node target) { // log V
        if (jump != -1) { //1
            Node possible = new Node(x, y, jump, target); // 1
            int shift = canReachPlusMinus(possible, target); // 1
            if (Math.abs(shift) <= 1) { // 1
                possible.setJump(jump + shift); // 1
                possible.postConstruct(); // 1
                path.add(possible); // log V
                if (!(x == 0 && y == 0)) { // 1
                    map[x][y] = -1; // 1
                }
            }
        }
    }

    private int canReachPlusMinus(Node jumpFrom, Node target) { // 1
        if (jumpFrom.getX() == target.getX()) { //1
            return target.getY() - (jumpFrom.getY() + jumpFrom.getJump());
        } else {
            return target.getX() - (jumpFrom.getX() + jumpFrom.getJump());
        }
    }

    private List<String> composeAnswer(Node curNode) {
        List<String> result = new ArrayList<>();
        if (curNode != null) {
            while (curNode != finish) {
                result.add(curNode.toString());
                curNode = curNode.getPrevious();
            }
        }
        return result;
    }

}