/**
 * @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;
    }

    /**
     * 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) {
        // TODO find
        return null;
    }

    /**
     * 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;
    }

}