/**
 * @author Pacien TRAN-GIRARD
 * @author Timothée FLOURE
 */
public final class Seam {

    /**
     * Find the best predecessors between {@code from} and {@code to} using Dijkstra's algorithm
     *
     * @param successors adjacency list for all vertices
     * @param costs      weight for all vertices
     * @param from       first vertex
     * @return best predecessor of each vertex
     */
    private static int[] findBestPredecessors(int[][] successors, float[] costs, int from) {
        int nbVertices = successors.length;
        float distances[] = new float[nbVertices];
        int bestPredecessors[] = new int[nbVertices];

        for (int v = 0; v < nbVertices; ++v) {
            distances[v] = Float.POSITIVE_INFINITY;
            bestPredecessors[v] = -1;
        }

        distances[from] = costs[from];
        boolean modified = true;

        while (modified) {
            modified = false;
            for (int v = 0; v < nbVertices; ++v)
                for (int n : successors[v])
                    if (distances[n] > distances[v] + costs[n]) {
                        distances[n] = distances[v] + costs[n];
                        bestPredecessors[n] = v;
                        modified = true;
                    }
        }

        return bestPredecessors;
    }

    /**
     * Build the vertical predecessors graph of a matrix, plus an entry and an exit vertex
     *
     * @param width  width of the matrix
     * @param height height of the matrix
     * @return an oriented predecessors graph of the size (width * height + 2)
     */
    private static int[][] buildPredecessorsGraph(int width, int height) {
        int matrixSize = width * height;
        int[][] graph = new int[matrixSize + 2][];

        for (int row = 0; row < height - 1; ++row) {
            int rowShift = row * width;
            int nextRowShift = (row + 1) * width;

            graph[rowShift] = new int[]{
                    nextRowShift,
                    nextRowShift + 1,
            };

            graph[rowShift + (width - 1)] = new int[]{
                    nextRowShift + (width - 2),
                    nextRowShift + (width - 1),
            };

            for (int col = 1; col < width - 1; ++col)
                graph[rowShift + col] = new int[]{
                        nextRowShift + (col - 1),
                        nextRowShift + (col),
                        nextRowShift + (col + 1),
                };
        }

        graph[matrixSize] = new int[width];
        for (int col = 0; col < width; ++col) graph[matrixSize][col] = col;

        graph[matrixSize + 1] = new int[0];
        int rowShift = (height - 1) * width;
        for (int col = 0; col < width; ++col)
            graph[rowShift + col] = new int[]{matrixSize + 1};

        return graph;
    }

    /**
     * Build a sequence of vertex costs from a cost matrix, with nil-cost entry and exit vertices
     *
     * @param energy the cost matrix
     * @return a sequence of costs of the size (width * height + 2)
     */
    private static float[] buildVerticesCostSequence(float[][] energy) {
        int width = energy[0].length;
        int height = energy.length;
        int matrixSize = width * height;

        float[] costs = new float[matrixSize + 2];

        for (int row = 0; row < height; ++row)
            for (int col = 0; col < width; ++col)
                costs[row * width + col] = energy[row][col];

        costs[matrixSize] = 0;
        costs[matrixSize + 1] = 0;

        return costs;
    }

    /**
     * Compute shortest path between {@code from} and {@code to}
     *
     * @param successors adjacency list for all vertices
     * @param costs      weight for all vertices
     * @param from       first vertex
     * @param to         last vertex
     * @return a sequence of vertices, or {@code null} if no path exists
     */
    public static int[] path(int[][] successors, float[] costs, int from, int to) {
        int[] bestPredecessors = Seam.findBestPredecessors(successors, costs, from);

        int count = 0; // we could have used a Deque<Integer>, but we could not have returned an int[]; CC Pr. Odersky
        int predecessor = -1, newPredecessor = to;
        while (newPredecessor > -1) {
            predecessor = newPredecessor;
            newPredecessor = bestPredecessors[newPredecessor];
            ++count;
        }

        if (predecessor != from) return null; // "no way!"

        int[] path = new int[count];
        path[count - 1] = to;
        for (int v = count - 2; v >= 0; --v)
            path[v] = bestPredecessors[path[v + 1]];

        return path;
    }

    /**
     * Find best seam
     *
     * @param energy weight for all pixels
     * @return a sequence of x-coordinates (the y-coordinate is the index)
     */
    public static int[] find(float[][] energy) {
        int width = energy[0].length;
        int height = energy.length;
        int matrixSize = width * height;

        int[][] predecessors = Seam.buildPredecessorsGraph(width, height);
        float[] costs = Seam.buildVerticesCostSequence(energy);

        int[] path = Seam.path(predecessors, costs, matrixSize, matrixSize + 1);

        if (path == null) return null;

        int[] coordinates = new int[path.length - 2]; // ignore added beginning and ending vertices
        for (int x = 0; x < path.length - 2; ++x)
            coordinates[x] = path[x + 1] - x * width; // retrieve the y-coordinate

        return coordinates;
    }

    /**
     * Draw a seam on an image
     *
     * @param image original image
     * @param seam  a seam on this image
     * @return a new image with the seam in blue
     */
    public static int[][] merge(int[][] image, int[] seam) {
        // Copy image
        int width = image[0].length;
        int height = image.length;
        int[][] copy = new int[height][width];
        for (int row = 0; row < height; ++row)
            for (int col = 0; col < width; ++col)
                copy[row][col] = image[row][col];

        // Paint seam in blue
        for (int row = 0; row < height; ++row)
            copy[row][seam[row]] = 0x0000ff;

        return copy;
    }

    /**
     * Remove specified seam
     *
     * @param image original image
     * @param seam  a seam on this image
     * @return the new image (width is decreased by 1)
     */
    public static int[][] shrink(int[][] image, int[] seam) {
        int width = image[0].length;
        int height = image.length;
        int[][] result = new int[height][width - 1];
        for (int row = 0; row < height; ++row) {
            for (int col = 0; col < seam[row]; ++col)
                result[row][col] = image[row][col];
            for (int col = seam[row] + 1; col < width; ++col)
                result[row][col - 1] = image[row][col];
        }
        return result;
    }

}