Disposition Preference Layout (#1)

Signed-off-by: Jorge Ruesga <jorge@ruesga.com>

2 files changed, 231 insertions, 0 deletions

diff --git a/src/org/cyanogenmod/wallpapers/photophase/utils/DispositionUtil.java b/src/org/cyanogenmod/wallpapers/photophase/utils/DispositionUtil.java
new file mode 100644
index 0000000..ddd8d3a
--- /dev/null
+++ b/src/org/cyanogenmod/wallpapers/photophase/utils/DispositionUtil.java
@@ -0,0 +1,115 @@
+/*
+ * Copyright (C) 2013 The CyanogenMod Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.cyanogenmod.wallpapers.photophase.utils;
+
+import android.graphics.Rect;
+
+import org.cyanogenmod.wallpapers.photophase.model.Disposition;
+
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.List;
+
+/**
+ * A helper class with disposition utils
+ */
+public final class DispositionUtil {
+
+    /**
+     * Method that converts a disposition string to a disposition reference
+     *
+     * @param value The value to convert
+     * @return List<Disposition> The  dispositions reference
+     */
+    public static List<Disposition> toDispositions(String value) {
+        String[] v = value.split("\\|");
+        List<Disposition> dispositions = new ArrayList<Disposition>(v.length);
+        for (String s : v) {
+            String[] s1 = s.split(":");
+            String[] s2 = s1[0].split("x");
+            String[] s3 = s1[1].split("x");
+            Disposition disposition = new Disposition();
+            disposition.x = Integer.parseInt(s2[0]);
+            disposition.y = Integer.parseInt(s2[1]);
+            disposition.w = Integer.parseInt(s3[0]) - disposition.x + 1;
+            disposition.h = Integer.parseInt(s3[1]) - disposition.y + 1;
+            dispositions.add(disposition);
+        }
+        Collections.sort(dispositions);
+        return dispositions;
+    }
+
+    /**
+     * Method that converts a disposition reference to a disposition string
+     *
+     * @param dispositions The value to convert
+     * @return String The dispositions string
+     */
+    public static String fromDispositions(List<Disposition> dispositions) {
+        Collections.sort(dispositions);
+        StringBuilder sb = new StringBuilder();
+        int count = dispositions.size();
+        for (int i = 0; i < count; i++) {
+            Disposition disposition = dispositions.get(i);
+            sb.append(disposition.x)
+              .append("x")
+              .append(disposition.y)
+              .append(":")
+              .append(disposition.x + disposition.w - 1)
+              .append("x")
+              .append(disposition.y + disposition.h - 1);
+            if (i < (count - 1)) {
+                sb.append("|");
+            }
+        }
+        return sb.toString();
+    }
+
+    /**
+     * Method that transform the disposition to a byte matrix
+     *
+     * @param dispositions The
+     * @return byte[][] The boolean matrix of the disposition
+     */
+    public static byte[][] toMatrix(List<Disposition> dispositions, int cols, int rows) {
+        byte[][] matrix = new byte[rows][cols];
+        for (Disposition disposition : dispositions) {
+            int count = disposition.y + disposition.h;
+            for (int row = disposition.y; row < count; row++) {
+                int count2 = disposition.x + disposition.w;
+                for (int col = disposition.x; col < count2; col++) {
+                    matrix[row][col]  = 1;
+                }
+            }
+        }
+        return matrix;
+    }
+
+    /**
+     * Method that returns a disposition from a {@link Rect} reference
+     *
+     * @return Disposition The disposition
+     */
+    public static Disposition fromRect(Rect r) {
+        Disposition disposition = new Disposition();
+        disposition.x = r.left;
+        disposition.y = r.top;
+        disposition.w = r.width();
+        disposition.h = r.height();
+        return disposition;
+    }
+}
diff --git a/src/org/cyanogenmod/wallpapers/photophase/utils/MERAlgorithm.java b/src/org/cyanogenmod/wallpapers/photophase/utils/MERAlgorithm.java
new file mode 100644
index 0000000..bd29235
--- /dev/null
+++ b/src/org/cyanogenmod/wallpapers/photophase/utils/MERAlgorithm.java
@@ -0,0 +1,116 @@
+/*
+ * Copyright (C) 2013 The CyanogenMod Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.cyanogenmod.wallpapers.photophase.utils;
+
+import android.graphics.Rect;
+import java.util.Stack;
+
+/**
+ * The maximal empty rectangle algorithm that allows to find the rectangle with the maximal
+ * area that could be create in empty areas (in this case 0 in a byte matrix)
+ */
+public final class MERAlgorithm {
+
+    /**
+     * Method that returns the maximal empty rectangle (MER) for a matrix of bytes (1/0)
+     *
+     * @param matrix The matrix
+     * @return Rect The maximal empty rectangle
+     */
+    public static Rect getMaximalEmptyRectangle(byte[][] matrix) {
+        // Check matrix
+        int rows = matrix.length;
+        if (rows == 0) return null;
+
+        // Convert to histogram
+        int[][] histogram = toHistogram(matrix);
+
+        // Find the maximal area of every histogram
+        Rect maxRect = new Rect();
+        for (int i = 0; i < rows; ++i) {
+            Rect rect = maximalRectangle(histogram[i], i);
+            if ((maxRect.width() * maxRect.height()) < (rect.width() * rect.height())) {
+                maxRect = rect;
+            }
+        }
+        return maxRect;
+    }
+
+    /**
+     * Method that returns the maximal rectangle for an histogram of areas
+     *
+     * @return Rect The maximal rectangle histogram/area
+     */
+    @SuppressWarnings("boxing")
+    private static Rect maximalRectangle(int[] histogram, int row) {
+        Stack<Integer> stack = new Stack<Integer>();
+        int length = histogram.length;
+        Rect maxRect = new Rect();
+        int i = 0;
+        while (i < length) {
+            if (stack.isEmpty() || histogram[i] >= histogram[stack.peek()]) {
+                stack.push(i++);
+            } else {
+                Rect rect = new Rect();
+                rect.left = stack.pop();
+                rect.right = rect.left + (stack.isEmpty() ? i : (i - stack.peek() - 1));
+                rect.top = row - histogram[rect.left] + 1;
+                rect.bottom = rect.top + histogram[rect.left];
+                if ((maxRect.width() * maxRect.height()) < (rect.width() * rect.height())) {
+                    maxRect = rect;
+                }
+            }
+        }
+        while (!stack.isEmpty()) {
+            Rect rect = new Rect();
+            rect.left = stack.pop();
+            rect.right = rect.left + (stack.isEmpty() ? i : (i - stack.peek() - 1));
+            rect.top = row - histogram[rect.left] + 1;
+            rect.bottom = rect.top + histogram[rect.left];
+            if ((maxRect.width() * maxRect.height()) < (rect.width() * rect.height())) {
+                maxRect = rect;
+            }
+        }
+        return maxRect;
+    }
+
+    /**
+     * Method that converts the empty areas to a histogram
+     *
+     * @param matrix The matrix where to find the MER
+     * return int[][] The histogram of empty areas
+     */
+    private static int[][] toHistogram(byte[][] matrix) {
+        int rows = matrix.length;
+        int cols = matrix[0].length;
+        int[][] histogram = new int[rows][cols];
+        for (int h=0; h < cols; h++) {
+            if (matrix[0][h] == 0) {
+                histogram[0][h] = 1;
+            }
+        }
+        for (int w=1; w < rows; w++) {
+            for (int h=0; h < cols; h++) {
+                if (matrix[w][h] == 1) {
+                    continue;
+                }
+                histogram[w][h] = histogram[w-1][h] + 1;
+            }
+        }
+        return histogram;
+    }
+}