Algorithms-II : 2-SeamCarving: fix energy update bug, use System.arraycopy to build new energies and pixels array

1 files changed, 121 insertions, 140 deletions

diff --git a/Algorithms/Part-II/2-SeamCarving/SeamCarver.java b/Algorithms/Part-II/2-SeamCarving/SeamCarver.java
index 70df587..b87a953 100644
--- a/Algorithms/Part-II/2-SeamCarving/SeamCarver.java
+++ b/Algorithms/Part-II/2-SeamCarving/SeamCarver.java
@@ -10,6 +10,9 @@ public class SeamCarver
 
     private int width;
     private int height;
+    // using a byte[3*w*h] array will reduce mem usage,
+    // and speed up cause there will be no need to rotate the matrix
+    // maybe enough to drop out energies cache matrix !?
     private int[][] pixels;
     private int[][] energies;
     private int[][] edgeTo;
@@ -25,7 +28,6 @@ public class SeamCarver
 
         copyPixels(picture);
         initEnergies();
-        initPaths();
     }
 
     private void copyPixels(Picture picture)
@@ -38,14 +40,33 @@ public class SeamCarver
         }
     }
 
+    private void initEnergies()
+    {
+        verticalE = true;
+        energies = new int[height][width];
+        for (int i = 0; i < width; i++)
+            energies[0][i] = MAX_ENERGY;
+
+        for (int i = 0; i < width; i++)
+            energies[height - 1][i] = MAX_ENERGY;
+
+        for (int i = 0; i < height; i++)
+            energies[i][0] = MAX_ENERGY;
+
+        for (int i = 0; i < height; i++)
+            energies[i][width - 1] = MAX_ENERGY;
+
+        for (int h = 1; h < (height - 1); h++)
+            for (int w = 1; w < (width - 1); w++)
+                energies[h][w] = energyPriv(h, w);
+    }
+
     public Picture picture()
     {
         Picture p = new Picture(width, height);
 
-        if (!verticalP) {
-            pixels = getRotatedMatrix(pixels, height, width);
-            verticalP = true;
-        }
+        if (!verticalP) rotateMatrix(pixels);
+
         for (int y = 0; y < height; y++) {
             for (int x = 0; x < width; x++) {
                 p.set(x, y, new Color(pixels[y][x]));
@@ -65,33 +86,34 @@ public class SeamCarver
         return height;
     }
 
-    private void initEnergies()
+    private void rotateMatrix(int[][] matrix)
     {
-        verticalE = true;
-        energies = new int[height][width];
-        for (int i = 0; i < width; i++)
-            energies[0][i] = MAX_ENERGY;
-
-        for (int i = 0; i < width; i++)
-            energies[height - 1][i] = MAX_ENERGY;
-
-        for (int i = 0; i < height; i++)
-            energies[i][0] = MAX_ENERGY;
-
-        for (int i = 0; i < height; i++)
-            energies[i][width - 1] = MAX_ENERGY;
+        int x, y;
 
-        for (int h = 1; h < (height - 1); h++)
-            for (int w = 1; w < (width - 1); w++)
-                energies[h][w] = energyPriv(h, w);
-    }
+        if (matrix == energies) {
+            if (verticalE) {
+                x = height;
+                y = width;
+            } else {
+                x = width;
+                y = height;
+            }
+            verticalE = !verticalE;
+        } else {
+            if (verticalP) {
+                x = height;
+                y = width;
+            } else {
+                x = width;
+                y = height;
+            }
+            verticalP = !verticalP;
+        }
 
-    private int[][] getRotatedMatrix(int[][] matrix, int y, int x)
-    {
         if (DEBUG) {
-            if (matrix == energies) System.out.println("rotate energies");
-            else System.out.println("rotate pixels");
-            System.out.println(" new ["+y+";"+x+"]");
+            if (matrix == energies) System.out.print("  rotate energies");
+            else System.out.print("  rotate pixels");
+            System.out.println(" -> ["+y+"]["+x+"]");
         }
 
         int[][] m = new int[y][x];
@@ -101,7 +123,10 @@ public class SeamCarver
             }
         }
 
-        return m;
+        if (matrix == energies)
+            energies = m;
+        else
+            pixels = m;
     }
 
     private int getRed(int rgb)     { return (rgb >> 16) & 0x0ff; }
@@ -125,27 +150,6 @@ public class SeamCarver
         return (rx * rx) + (gx * gx) + (bx * bx) + (ry * ry) + (gy * gy) + (by * by);
     }
 
-    private void initPaths()
-    {
-        int sz = Math.max(height, width);
-        edgeTo = new int[sz][sz];
-        distTo = new int[sz][sz];
-    }
-
-    private void clearPaths(int Y, int X)
-    {
-        for (int x = 0; x < X; x++) {
-            // edgeTo[0][x] = -1;
-            distTo[0][x] = MAX_ENERGY;
-        }
-
-        for (int y = 1; y < Y; y++) {
-            for (int x = 0; x < X; x++) {
-                distTo[y][x] = 0;
-            }
-        }
-    }
-
     public double energy(int x, int y)
     {
         int w = (width - 1);
@@ -179,7 +183,8 @@ public class SeamCarver
     {
         if (DEBUG) st = new Stopwatch();
 
-        clearPaths((Y + 1), (X + 1));
+        edgeTo = new int[Y + 1][X + 1];
+        distTo = new int[Y + 1][X + 1];
 
         int e, c, d, v;
         // from 0 to before last
@@ -229,27 +234,28 @@ public class SeamCarver
         }
         path[0] = x;
 
-        if (DEBUG) System.out.println("seam found in "+st.elapsedTime());
+        if (DEBUG) System.out.println("  seam found in "+st.elapsedTime());
+
+        edgeTo = null;
+        distTo = null;
 
         return path;
     }
 
     public int[] findHorizontalSeam()
     {
-        if (verticalE) {
-            energies = getRotatedMatrix(energies, width, height);
-            verticalE = false;
-        }
+        if (DEBUG) System.out.println("search horizontal seam");
+
+        if (verticalE) rotateMatrix(energies);
 
         return findMinPath((width - 1), (height - 1));
     }
 
     public int[] findVerticalSeam()
     {
-        if (!verticalE) {
-            energies = getRotatedMatrix(energies, height, width);
-            verticalE = true;
-        }
+        if (DEBUG) System.out.println("search vertical seam");
+
+        if (!verticalE) rotateMatrix(energies);
 
         return findMinPath((height - 1), (width - 1));
     }
@@ -275,72 +281,63 @@ public class SeamCarver
         }
     }
 
-    private void removeItem(int[] a, int index)
+    private void removeSeam(int[] a, boolean vertical)
     {
-        for (int i = index; i < a.length - 1; i++) {
-            a[i] = a[i+1];
+        int len;
+        int[][] p;
+        int[][] e;
+
+        if (vertical) {
+            if (!verticalP) rotateMatrix(pixels);
+            if (!verticalE) rotateMatrix(energies);
+            width -= 1;
+            len = width;
+            p = new int[height][width];
+            e = new int[height][width];
+        } else {
+            if (verticalP) rotateMatrix(pixels);
+            if (verticalE) rotateMatrix(energies);
+            height -= 1;
+            len = height;
+            p = new int[width][height];
+            e = new int[width][height];
         }
-    }
 
-    private void removeSeam(int[] a, int J, int[][] e, int[][] p)
-    {
-        for (int i = 0; i < a.length; i++)
-            removeItem(p[i], a[i]);
+        // copy pixels
+        for (int i = 0; i < a.length; i++) {
+            int  v = a[i];
+            if (v > 0) System.arraycopy(pixels[i], 0, p[i], 0, v);
+            if (v < len) System.arraycopy(pixels[i], (v + 1), p[i], v, (len - v));
+        }
+        pixels = p;
+
+        // copy energies
+        for (int i = 0; i < a.length; i++) {
+            int  v = a[i];
+            if (v > 0) System.arraycopy(energies[i], 0, e[i], 0, v);
+            if (v < len) System.arraycopy(energies[i], (v + 1), e[i], v, (len - v));
+        }
+        energies = e;
 
+        // update energies
+        int l = len - 1;
         for (int i = 1; i < (a.length - 1); i++) {
             int v = a[i];
             if (v == 0) {
                 e[i][0] = MAX_ENERGY;
-                removeItem(e[i], 1);
-            } else if (v == 1) {
-                e[i][1] = energyPriv(i, 1);
-                removeItem(e[i], 2);
             } else {
-                e[i][v - 1] = energyPriv(i, (v - 1));
-                if (v < (J - 1)) {
+                if (v < l) {
                     e[i][v] = energyPriv(i, v);
-                    removeItem(e[i], v+1);
-                } else {
+                } else if (v == l) {
                     e[i][v] = MAX_ENERGY;
                 }
-            }
-        }
-
-        if (!DEBUG) return;
-
-        String err;
-        for (int j = 0; j < J; j++) {
-            int i = 0;
-            if (e[i][j] != MAX_ENERGY) {
-                err = "["+a.length+" ; "+J+"] : "+i+" ; "+j+" != MAX";
-                throw new java.lang.IndexOutOfBoundsException(err);
-            }
-            i = a.length - 1;
-            if (e[i][j] != MAX_ENERGY) {
-                err = "["+a.length+" ; "+J+"] : "+i+" ; "+j+" != MAX";
-                throw new java.lang.IndexOutOfBoundsException(err);
-            }
-        }
-        for (int i = 0; i < a.length; i++) {
-            int j = 0;
-            if (e[i][j] != MAX_ENERGY) {
-                err = "["+a.length+" ; "+J+"] : "+i+" ; "+j+" != MAX";
-                throw new java.lang.IndexOutOfBoundsException(err);
-            }
-            j = J - 1;
-            if (e[i][j] != MAX_ENERGY) {
-                err = "["+a.length+" ; "+J+"] : "+i+" ; "+j+" != MAX";
-                throw new java.lang.IndexOutOfBoundsException(err);
-            }
-        }
-        for (int i = 1; i < (a.length - 1); i++) {
-            int[] ei = e[i];
-            for (int j = 1; j < (J - 1); j++) {
-                int v = ei[j];
-                int eij = energyPriv(i, j);
-                if (v != eij) {
-                    err = "["+a.length+" ; "+J+"] : "+i+" ; "+j+" != "+eij;
-                    throw new java.lang.IllegalArgumentException(err);
+                v -= 1;
+                if (v == 0) {
+                    e[i][0] = MAX_ENERGY;
+                } else if (v < l) {
+                    e[i][v] = energyPriv(i, v);
+                } else if (v == l) {
+                    e[i][v] = MAX_ENERGY;
                 }
             }
         }
@@ -351,22 +348,14 @@ public class SeamCarver
         if (width <= 1)
             throw new java.lang.IllegalArgumentException("image is to small");
 
-        if (DEBUG) st = new Stopwatch();
-
-        validateSeam(a, width, height);
-
-        if (verticalE) {
-            energies = getRotatedMatrix(energies, width, height);
-            verticalE = false;
+        if (DEBUG) {
+            st = new Stopwatch();
+            System.out.println("remove horizontal seam");
         }
 
-        if (verticalP) {
-            pixels = getRotatedMatrix(pixels, width, height);
-            verticalP = false;
-        }
+        validateSeam(a, width, height);
 
-        height -= 1;
-        removeSeam(a, height, energies, pixels);
+        removeSeam(a, false);
 
         if (DEBUG) System.out.println("["+width+" "+height+"] in "+st.elapsedTime());
     }
@@ -376,22 +365,14 @@ public class SeamCarver
         if (height <= 1)
             throw new java.lang.IllegalArgumentException("image is to small");
 
-        if (DEBUG) st = new Stopwatch();
-
-        validateSeam(a, height, width);
-
-        if (!verticalE) {
-            energies = getRotatedMatrix(energies, height, width);
-            verticalE = true;
+        if (DEBUG) {
+            st = new Stopwatch();
+            System.out.println("remove vertical seam");
         }
 
-        if (!verticalP) {
-            pixels = getRotatedMatrix(pixels, height, width);
-            verticalP = true;
-        }
+        validateSeam(a, height, width);
 
-        width -= 1;
-        removeSeam(a, width, energies, pixels);
+        removeSeam(a, true);
 
         if (DEBUG) System.out.println("["+width+" "+height+"] in "+st.elapsedTime());
     }