SeamCarver.java

/*
Aggregate score: 91.18%
Correctness:  34/34 tests passed
Memory:       0/6 tests passed
Timing:       18/17 tests passed


maximum allowed memory is ~ 12 n^2 bytes.

                 n       student (bytes)
-------------------------------------------
=> FAILED       16        18112
=> FAILED       32        77264
=> FAILED       64       319984
=> FAILED      128      1303088
=> FAILED      256      5125512
=> FAILED      512      9031208
==> 0/6 tests passed

Total: 0/6 tests passed!

Estimated student memory (bytes) = -5.39 n^2 + 22039.01 n - 742984.03   (R^2 = 0.984)
*/



import edu.princeton.cs.algs4.Bag;
import edu.princeton.cs.algs4.Picture;
import edu.princeton.cs.algs4.Stack;
import edu.princeton.cs.algs4.StdOut;

import java.awt.Color;
import java.util.ArrayList;
import java.util.Arrays;

public class SeamCarver {

    private double[][] energies;
    private int[][] colors;
    private int[] pixelTo;
    private double[] disTo;
    private boolean[] marked;
    private int width;
    private int height;
    private final int source;
    private int sink;
    private Stack<Integer> topologicalOrder;

    // create a seam carver object based on the given picture
    public SeamCarver(Picture picture) {
        if (picture == null) throw new IllegalArgumentException();
        height = picture.height();
        width = picture.width();
        int n = width * height + 2; // w * h pixels plus a source and a sink
        energies = new double[width][height];
        colors = new int[width][height];
        source = 0;
        sink = n - 1;
        buildColors(picture);
        buildEnergies();
    }

    // current picture
    public Picture picture() {
        int w = width();
        int h = height();
        Picture resizedPicture = new Picture(w, h);
        for (int x = 0; x < w; x++)
            for (int y = 0; y < h; y++) resizedPicture.set(x, y, new Color(colors[x][y]));
        return resizedPicture;
    }

    // width of current picture
    public int width() {
        return colors.length;
    }

    // height of current picture
    public int height() {
        return colors[0].length;
    }

    // energy of pixel at column x and row y
    public double energy(int x, int y) {
        if (!validate(x, y)) throw new IllegalArgumentException();
        if (x == 0 || y == 0 || x == width() - 1 || y == height() - 1)
            return 1000; // energy of border's pixels is 1000
        else
            return Math.sqrt(deltaX(x, y) + deltaY(x, y));
    }

    // sequence of indices for horizontal seam
    public int[] findHorizontalSeam() {
        transposePicture();
        int[] seams = findVerticalSeam();
        transposePicture();
        return seams;
    }

    // sequence of indices for vertical seam
    public int[] findVerticalSeam() {
        int h = height();
        int[] seam = new int[h];
        runDFS();
        ArrayList<Integer> path = pathTo(sink);
        for (int i = 0; i < path.size(); i++) {
            seam[i] = x(path.get(path.size() - 1 - i));
        }
        return seam;
    }

    // remove horizontal seam from current picture
    public void removeHorizontalSeam(int[] seam) {
        validate(seam, false);
        if (seam.length != width()) throw new IllegalArgumentException();
        shift(seam, width(), height());
        height--;
        sink -= seam.length;
        recomputeEnergies(seam, false);
    }

    // remove vertical seam from current picture
    public void removeVerticalSeam(int[] seam) {
        validate(seam, true);
        if (seam.length != height()) throw new IllegalArgumentException();
        transposePicture();
        shift(seam, width(), height());
        transposePicture();
        width--;
        sink -= seam.length;
        recomputeEnergies(seam, true);
    }

    //////////////////////////////////////////////////////////
    ////................... UTILITIES ....................////
    //////////////////////////////////////////////////////////

    private void runDFS() {
        int n = width() * height();
        disTo = new double[n + 2]; // the source and sink extra
        pixelTo = new int[n + 2];
        for (int p = 1; p <= sink; p++)
            disTo[p] = Double.POSITIVE_INFINITY; // all pixels are at an infinite distance from source
        Iterable<Integer> topOrder = topologicalOrder(); // build topological order
        for (int i : topOrder)
            if (i < sink) relax(i);
    }

    private Iterable<Integer> topologicalOrder() {
        topologicalOrder = new Stack<>();
        int size = width() * height() + 2;
        marked = new boolean[size];
        for (int p = 0; p < size; p++) if (!marked[p]) dfs(p);
        return topologicalOrder;
    }

    private void dfs(int p) {
        marked[p] = true;
        if (p != sink) // if sink hole reached just add it to stack. Ends recursive call.
            for (int i : adj(p)) if (!marked[i]) dfs(i);
        topologicalOrder.push(p);
    }

    private void relax(int i) {
        for (int p : adj(i)) {
            int[] xy = xy(p);
            int x = xy[0];
            int y = xy[1];
            double e = p == sink ? 0 : energies[x][y];
            if (disTo[p] > disTo[i] + e) {
                disTo[p] = disTo[i] + e;
                pixelTo[p] = i;
            }
        }
    }

    private ArrayList<Integer> pathTo(int pixel) {
        ArrayList<Integer> path = new ArrayList<>();
        for (int p = pixelTo[pixel]; p != source; p = pixelTo[p]) // starting from sink we go back until we reach source
            path.add(p);
        return path;
    }

    private Bag<Integer> adj(int pixel) {
        Bag<Integer> bag = new Bag<>();
        int w = width();
        int h = height();

        if (pixel == source)  //  all first row pixels are adjacent to source
            for (int p = 1; p <= w; p++) bag.add(p);
        else if (pixel > w * h - w) bag.add(sink); // bottom row
        else {
            int belowLeft = pixel + w - 1;
            int belowCenter = pixel + w;
            int belowRight = pixel + w + 1;
            if (pixel % w == 1) { // first column
                bag.add(belowCenter);
                bag.add(belowRight);
            } else if (pixel % w == 0) { // last column
                bag.add(belowLeft);
                bag.add(belowCenter);
            } else {
                bag.add(belowLeft);
                bag.add(belowCenter);
                bag.add(belowRight);
            }
        }
        return bag;
    }

    // used to remove a seam that is horizontal
    private void shift(int[] seam, int w, int h) {
        for (int x = 0; x < w; x++) { // for each column shift color by removing pixel located at position (x,seam[x])
            int[] dest1 = new int[h - 1];
            double[] dest2 = new double[h - 1];
            int srcPos = seam[x] + 1;
            int destPos = seam[x];
            int length1 = dest1.length - seam[x];
            int length2 = seam[x];

            System.arraycopy(colors[x], srcPos, dest1, destPos, length1); // copies from seam[x]+1 to end
            System.arraycopy(colors[x], 0, dest1, 0, length2); // copies from 0 to seam[x]-1
            colors[x] = dest1; // merge the result and in place update colors

            System.arraycopy(energies[x], srcPos, dest2, destPos, length1); // same for energies
            System.arraycopy(energies[x], 0, dest2, 0, length2);
            energies[x] = dest2;
        }
    }

    private void recomputeEnergies(int[] seam, boolean isVertical) {
        int y = 0;
        if (isVertical) {
            for (int s : seam) {
                if (validate(s - 1, y)) // does it have a neighbour on the left?
                    energies[s - 1][y] = energy(s - 1, y); // recompute its energy

                if (validate(s, y)) // same for right neighbour if exists
                    energies[s][y] = energy(s, y);
                y++; // and we go down to the next row
            }
        } else {
            for (int s : seam) {
                if (validate(y, s - 1)) { // does it have a top neighbour?
                    energies[y][s - 1] = energy(y, s - 1);
                }
                if (validate(y, s)) { // and a bottom one
                    energies[y][s] = energy(y, s);
                }
                y++;
            }
        }
    }

    private int x(int pixel) {
        return xy(pixel)[0];
    }

    private int[] xy(int pixel) {
        int w = width(); //energies.length;
        return new int[]{(pixel - 1) % w, (pixel - 1) / w};
    }

    private void transposePicture() {
        int w = width();
        int h = height();
        int[][] tColors = new int[h][w];
        double[][] tEnergies = new double[h][w];
        for (int x = 0; x < h; x++)
            for (int y = 0; y < w; y++) {
                tColors[x][y] = colors[y][x];
                tEnergies[x][y] = energies[y][x];
            }
        colors = tColors;
        energies = tEnergies;
    }

    private void buildColors(Picture picture) {
        for (int x = 0; x < width; x++)
            for (int y = 0; y < height; y++) colors[x][y] = picture.getRGB(x, y);
    }

    private void buildEnergies() {
        for (int x = 0; x < width; x++)
            for (int y = 0; y < height; y++) energies[x][y] = energy(x, y);
    }

    private double deltaX(int x, int y) {
        Color colorXPlusOne = new Color(colors[x + 1][y]);
        Color colorXMinusOne = new Color(colors[x - 1][y]);
        return Math.pow(colorXPlusOne.getRed() - colorXMinusOne.getRed(), 2)
                + Math.pow(colorXPlusOne.getGreen() - colorXMinusOne.getGreen(), 2)
                + Math.pow(colorXPlusOne.getBlue() - colorXMinusOne.getBlue(), 2);
    }

    private double deltaY(int x, int y) {
        Color colorYPlusOne = new Color(colors[x][y + 1]);
        Color colorYMinusOne = new Color(colors[x][y - 1]);
        return Math.pow(colorYPlusOne.getRed() - colorYMinusOne.getRed(), 2)
                + Math.pow(colorYPlusOne.getGreen() - colorYMinusOne.getGreen(), 2)
                + Math.pow(colorYPlusOne.getBlue() - colorYMinusOne.getBlue(), 2);
    }

    private void validate(int[] seam, boolean isVertical) {
        if (seam == null || seam.length < 1) throw new IllegalArgumentException();
        int size;
        if (isVertical) {
            size = width();
        } else {
            size = height();
        }
        for (int i = 0; i < seam.length; i++) { // seam within bounds
            if (seam[i] >= size || seam[i] < 0) throw new IllegalArgumentException();
            if (i < seam.length - 1) { // and gap no greater than 1
                if (Math.abs(seam[i] - seam[i + 1]) > 1) throw new IllegalArgumentException();
            }
        }
    }

    private boolean validate(int x, int y) {
        return (x >= 0 && x < width() && y >= 0 && y < height());
    }

    // unit testing (optional)
    public static void main(String[] args) {
        Picture picture = new Picture(6, 6);

        String[][] s1 = {
                {"#050208", "#070304", "#050809", "#070000", "#020309", "#010706"},
                {"#050204", "#080102", "#060000", "#010708", "#020907", "#080408"},
                {"#010502", "#080307", "#000200", "#090804", "#090106", "#060106"},
                {"#000403", "#070607", "#020306", "#070808", "#000205", "#060307"},
                {"#030703", "#010504", "#080608", "#050808", "#010907", "#050101"},
                {"#050808", "#080201", "#020008", "#080603", "#060709", "#050108"},
        };

        String[][] s2 = {
                {"#090503", "#090307", "#080003", "#020602", "#000304", "#000906"},
                {"#000702", "#040800", "#090809", "#070101", "#080307", "#000402"},
                {"#020904", "#030600", "#090000", "#040807", "#010702", "#090407"},
                {"#020403", "#010206", "#080703", "#060002", "#010107", "#090204"},
                {"#020202", "#070906", "#050509", "#030105", "#000507", "#020004"},
                {"#060109", "#090305", "#080309", "#070507", "#070707", "#090900"},
        };

        int w = picture.width();
        int h = picture.height();

        for (int i = 0; i < w; i++) {
            for (int j = 0; j < h; j++)
                picture.set(i, j, Color.decode(s2[i][j]));
        }

        SeamCarver carver = new SeamCarver(picture);

        int[] seam1 = carver.findVerticalSeam();
        StdOut.println("1st Seam = " + Arrays.toString(seam1));
        carver.removeVerticalSeam(seam1);
        carver.picture();

    }
}