PackGridDpSampler.java

// Copyright (c) 2015 boyw165
//
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
//
//    The above copyright notice and this permission notice shall be included in
// all copies or substantial portions of the Software.
//
//    THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
// THE SOFTWARE.

package boyw165.com.whatever.math;

import android.graphics.RectF;

import com.cardinalblue.android.piccollage.IPhoto;

import java.util.ArrayList;
import java.util.List;

/**
 * Packing images in a grid with rows of uniform widths. By using dynamic
 * programming a optimal solution for when to introduce line-break can be found,
 * and then each row can be scaled to meet the desired width.
 *
 *
 * Constraints
 * -----------
 * 1) All rows must be exactly the same width.
 * 2) All images within a row must have the same height.
 * 3) The ordering of the images must not change.
 * 4) All rows must be full - including the last row.
 *
 *
 * Formulas
 * --------
 * 1) The penalty of the row starting with image i, containing s images,
 * with desired width d.
 *
 *   P(i,s) = Math.abs(d - (sum(w(j)) + padding * (s - 1)))
 *
 * Where j = i ~ i + s
 *
 * 2) The cost of having a line-break is the combined cost of the current line
 * P(i,s) and the optimal cost of packing the remaining images C(i+s,1).
 *
 *   C(i,s) = Math.min(C(i,s+1), P(i,s) + C(i+s,1)) | i + s < n
 *          , P(i,s)                                | i + s = n
 *
 * 3) To even the difference out by scaling each row accordingly.
 *
 *   Scale(i,s) = (d - padding * (s - 1)) / P(i,s)
 *
 * Where d is desired width like above.
 *
 *
 * Authors
 * -------
 * Original author: https://github.com/fangel
 * Maintainer: [email protected], [email protected]
 *
 *
 * Reference
 * ---------
 * http://fangel.github.io/packing-images-in-a-grid/
 */
public class PackGridDpSampler {
    public static final int ALIGN_ROW_WIDTH     = 0;
    public static final int ALIGN_COL_HEIGHT    = 1;

    private static final float INFINITY         = Float.POSITIVE_INFINITY;

    /**
     * Given padding in between the image.
     */
    private float mPadding;

    /**
     * The desired row width and height.
     */
    private float mDesiredRowWidth;
    private float mDesiredRowHeight;

    /**
     * The desired column width and height.
     */
    private float mDesiredColWidth;
    private float mDesiredColHeight;

    /**
     * The costs table used to lookup the optimal packing.
     */
    private float mCosts[][];

    /**
     * The given images. The algorithm will refer to the width and height
     * of the images.
     */
    private List<IPhoto> mImages;

    /**
     * @param images The given images. The algorithm will refer to width/height
     *               of each images accordingly.
     * @param desiredWidth The desired width of a row/column.
     * @param desiredHeight The desired height of a row/column.
     * @param padding The padding.
     */
    public PackGridDpSampler(List<IPhoto> images, int policy,
                             float desiredWidth, float desiredHeight,
                             float padding) {
        if (images == null || images.isEmpty()) {
            throw new IllegalArgumentException("The given images is either null or empty.");
        }
        if (policy < ALIGN_ROW_WIDTH || policy > ALIGN_COL_HEIGHT) {
            throw new IllegalArgumentException("The given policy is invalid.");
        }
        if (desiredWidth <= 0 || desiredHeight <= 0) {
            throw new IllegalArgumentException("The given width/height is less or equal than zero.");
        }
        if (padding < 0) {
            throw new IllegalArgumentException("The given padding is negative.");
        }

        mCosts = new float[images.size()][images.size()];
        mImages = images;
        mPadding = padding;

        if (policy == ALIGN_ROW_WIDTH) {
            mDesiredRowWidth = desiredWidth;
            mDesiredRowHeight = desiredHeight;
        } else if (policy == ALIGN_COL_HEIGHT) {
            mDesiredColWidth = desiredWidth;
            mDesiredColHeight = desiredHeight;
        }
    }

    ///////////////////////////////////////////////////////////////////////////
    // Align Row Width ////////////////////////////////////////////////////////

    /**
     * The layout result which guarantees the width of rows is the same. But
     * the height of rows slightly very. The 1st dimension is rows; 2nd
     * dimension is columns.
     */
    public List<List<RectF>> sampleRow() {
        if (mDesiredRowWidth <= 0 || mDesiredRowHeight <= 0) {
            throw new IllegalArgumentException("The desired row width/height is invalid.");
        }

        // Initialize the costs table.
        initCostsTable();

        // Generate the costs.
        //
        // s +---+
        //   | 8 |
        //   +---+---+
        //   | 6 | 9 |
        //   +---+---+---+
        //   | 5 | 7 | 8 |
        //   +---+---+---+---+
        //   | 5 | 3 | 4 | ~ |
        //   +---+---+---+---+---+
        //   | 5 | 3 | 1 | ~ | ~ |
        //   +---+---+---+---+---+ i
        //
        // First dimension is the i, which denotes the row starting with image i.
        // Second dimension is the s, which denotes the row starting with image
        // i and end at s amount of images.
        //
        for (int i = mImages.size() - 1; i >= 0; --i) {
            for (int s = mImages.size() - 1; s >= 0; --s) {
                int s1 = s + 1;
                if (i + s1 == mImages.size()) {
                    mCosts[i][s] = rowPenaltyAt(i, s1);
                } else if (i + s1 < mImages.size()) {
                    float costOneMore = mCosts[i][s + 1];
                    float penalty = rowPenaltyAt(i, s1);
                    float costLineBreak = mCosts[i + s1][0];

                    mCosts[i][s] = Math.min(costOneMore,
                                            penalty + costLineBreak);
                }
            }
        }

        // Go through the costs table to find a cheapest solution.
        //
        // s +---+
        //   | 8 |
        //   +---+---+
        //   | 6 | 9 |
        //   +---+---+---+
        //   | 5 | 7 | 8 |
        //   +---+---+---+---+
        //   | 5 | 3 | 4 | ~ |
        //   +---+---+---+---+---+
        //   | 5 | 3 | 1 | ~ | ~ |
        //   +---+---+---+---+---+ i
        //     ^
        //   Start from i = 0, search every possible s (images in a row) that
        //   the cost stay the same. Advance i (i + s) once the cost increase.
        //
        float lastCost = mCosts[0][0];
        List<Float> rowWidths = new ArrayList<>();
        rowWidths.add(0f);
        List<List<RectF>> rows = new ArrayList<>();
        rows.add(new ArrayList<RectF>());
        for (int i = 0, costIndex = 0, amount = 1; i < mImages.size(); ++i) {
            if (lastCost != mCosts[costIndex][amount - 1]) {
                costIndex += (amount - 1);
                amount = 1;
                // Insert a line break.
                rows.add(new ArrayList<RectF>());
                rowWidths.add(0f);
                // Remember the new cost for next comparison.
                lastCost = mCosts[costIndex][0];
            } else {
                ++amount;
            }

            // Save the width and height.
            int last = rows.size() - 1;
            float width = widthAt(i);
            rows.get(last)
                .add(new RectF(0, 0,
                               width,
                               mDesiredRowHeight));

            // Accumulate the width.
            rowWidths.set(last, rowWidths.get(last) + width);
        }

        // Post processing to make sure every row's width is consistent.
        // And apply correct positions to them.
        for (float i = 0, currentX = 0, currentY = 0; i < rows.size(); ++i) {
            List<RectF> cols = rows.get((int) i);
            float rowWidth = rowWidths.get((int) i);
            float padding = mPadding * (cols.size() - 1);
            float scale = (mDesiredRowWidth - padding) / rowWidth;

            for (int j = 0; j < cols.size(); ++j) {
                float newWidth = cols.get(j).width() * scale;
                float newHeight = cols.get(j).height() * scale;

                cols.get(j).set(currentX, currentY,
                                currentX + newWidth,
                                currentY + newHeight);
                currentX += newWidth;
                // Add horizontal padding.
                if (j < cols.size() - 1) {
                    currentX += mPadding;
                }
            }

            currentX = 0;
            currentY += rows.get((int) i).get(0).height();
            // Add vertical padding.
            if (i < rows.size() - 1) {
                currentY += mPadding;
            }
        }

        return rows;
    }

    /**
     * Directly scale the layout so that it fits inside the given boundary.
     * NOTE: The widths of row might be slightly staggered.
     * @param bound The boundary containing the layout.
     */
    public List<List<RectF>> sampleRowAndFit(RectF bound) {
        if (bound == null ||
            bound.width() == 0 || bound.height() == 0) {
            throw new IllegalArgumentException("The given boundary is invalid.");
        }

        List<List<RectF>> layout = sampleRow();

        return fitCenter1(layout, bound);
    }

    /**
     * Iteratively reduce the desired row height and recalculate the layout so
     * that it fits inside the given boundary.
     * NOTE: The widths of row might be slightly staggered.
     * @param bound The boundary containing the layout.
     * @param descentHeight The negative value applying to the desired height
     *                      so that it can iteratively find the perfect layout
     *                      fitting in the boundary.
     */
    public List<List<RectF>> sampleRowAndFit(RectF bound, float descentHeight) {
        if (bound == null ||
            bound.width() == 0 || bound.height() == 0) {
            throw new IllegalArgumentException("The given boundary is invalid.");
        }
        if (descentHeight < 0) {
            throw new IllegalArgumentException("Descent height must not be negative.");
        }
        if (descentHeight > mDesiredRowHeight) {
            throw new IllegalArgumentException("Descent height must not be greater than desired row height.");
        }

        List<List<RectF>> layout = sampleRow();
        while (bound.height() < rowsHeight(layout, false) &&
               mDesiredRowHeight > 0) {
            mDesiredRowHeight -= descentHeight;
            layout = sampleRow();
        }

        return fitCenter1(layout, bound);
    }

    ///////////////////////////////////////////////////////////////////////////
    // Align Column Height ////////////////////////////////////////////////////

    /**
     * The layout result which guarantees the height of columns is the same.
     * But the width of rows slightly very. The 1st dimension is columns; 2nd
     * dimension is rows.
     */
    public List<List<RectF>> sampleCol() {
        if (mDesiredColWidth <= 0 || mDesiredColHeight <= 0) {
            throw new IllegalArgumentException("The desired row width/height is invalid.");
        }

        // Initialize the costs table.
        initCostsTable();

        // Generate the costs.
        //
        // s +---+
        //   | 8 |
        //   +---+---+
        //   | 6 | 9 |
        //   +---+---+---+
        //   | 5 | 7 | 8 |
        //   +---+---+---+---+
        //   | 5 | 3 | 4 | ~ |
        //   +---+---+---+---+---+
        //   | 5 | 3 | 1 | ~ | ~ |
        //   +---+---+---+---+---+ i
        //
        // First dimension is the i, which denotes the row starting with image i.
        // Second dimension is the s, which denotes the row starting with image
        // i and end at s amount of images.
        //
        for (int i = mImages.size() - 1; i >= 0; --i) {
            for (int s = mImages.size() - 1; s >= 0; --s) {
                int s1 = s + 1;
                if (i + s1 == mImages.size()) {
                    mCosts[i][s] = colPenaltyAt(i, s1);
                } else if (i + s1 < mImages.size()) {
                    float costOneMore = mCosts[i][s + 1];
                    float penalty = colPenaltyAt(i, s1);
                    float costLineBreak = mCosts[i + s1][0];

                    mCosts[i][s] = Math.min(costOneMore,
                                            penalty + costLineBreak);
                }
            }
        }

        // Go through the costs table to find a cheapest solution.
        //
        // s +---+
        //   | 8 |
        //   +---+---+
        //   | 6 | 9 |
        //   +---+---+---+
        //   | 5 | 7 | 8 |
        //   +---+---+---+---+
        //   | 5 | 3 | 4 | ~ |
        //   +---+---+---+---+---+
        //   | 5 | 3 | 1 | ~ | ~ |
        //   +---+---+---+---+---+ i
        //     ^
        //   Start from i = 0, search every possible s (images in a row) that
        //   the cost stay the same. Advance i (i + s) once the cost increase.
        //
        float lastCost = mCosts[0][0];
        List<Float> colHeights = new ArrayList<>();
        colHeights.add(0f);
        List<List<RectF>> cols = new ArrayList<>();
        cols.add(new ArrayList<RectF>());
        for (int i = 0, costIndex = 0, amount = 1; i < mImages.size(); ++i) {
            if (lastCost != mCosts[costIndex][amount - 1]) {
                costIndex += (amount - 1);
                amount = 1;
                // Insert a line break.
                cols.add(new ArrayList<RectF>());
                colHeights.add(0f);
                // Remember the new cost for next comparison.
                lastCost = mCosts[costIndex][0];
            } else {
                ++amount;
            }

            // Save the width and height.
            int last = cols.size() - 1;
            float height = heightAt(i);
            cols.get(last)
                .add(new RectF(0, 0,
                               mDesiredColWidth,
                               height));

            // Accumulate the column height.
            colHeights.set(last, colHeights.get(last) + height);
        }

        // Post processing to make sure every col's height is consistent.
        // And apply correct positions to them.
        for (float i = 0, currentX = 0, currentY = 0; i < cols.size(); ++i) {
            List<RectF> row = cols.get((int) i);
            float colHeight = colHeights.get((int) i);
            float padding = mPadding * (row.size() - 1);
            float scale = (mDesiredColHeight - padding) / colHeight;

            for (int j = 0; j < row.size(); ++j) {
                float newWidth = row.get(j).width() * scale;
                float newHeight = row.get(j).height() * scale;

                row.get(j).set(currentX, currentY,
                               currentX + newWidth,
                               currentY + newHeight);
                currentY += newHeight;
                // Add vertical padding.
                if (j < row.size() - 1) {
                    currentY += mPadding;
                }
            }

            currentX += cols.get((int) i).get(0).width();
            currentY = 0;
            // Add horizontal padding.
            if (i < cols.size() - 1) {
                currentX += mPadding;
            }
        }

        return cols;
    }

    /**
     * Directly scale the layout so that it fits inside the given boundary.
     * NOTE: The heights of column might be slightly staggered.
     * @param bound The boundary containing the layout.
     */
    public List<List<RectF>> sampleColAndFit(RectF bound) {
        if (bound == null ||
            bound.width() == 0 || bound.height() == 0) {
            throw new IllegalArgumentException("The given boundary is invalid.");
        }

        List<List<RectF>> layout = sampleCol();

        return fitCenter2(layout, bound);
    }

    /**
     * Iteratively reduce the desired column width and recalculate the layout so
     * that it fits inside the given boundary.
     * NOTE: The heights of column might be slightly staggered.
     * @param bound The boundary containing the layout.
     * @param descentWidth The negative value applying to the desired height
     *                     so that it can iteratively find the perfect layout
     *                     fitting in the boundary.
     */
    public List<List<RectF>> sampleColAndFit(RectF bound, float descentWidth) {
        if (bound == null ||
            bound.width() == 0 || bound.height() == 0) {
            throw new IllegalArgumentException("The given boundary is invalid.");
        }
        if (descentWidth < 0) {
            throw new IllegalArgumentException("Descent width must not be negative.");
        }
        if (descentWidth > mDesiredColWidth) {
            throw new IllegalArgumentException("Descent width must not be greater than desired column width.");
        }

        List<List<RectF>> layout = sampleCol();
        while (bound.height() < colsWidth(layout, false) &&
               mDesiredColWidth > 0) {
            mDesiredColWidth -= descentWidth;
            layout = sampleCol();
        }

        return fitCenter2(layout, bound);
    }

    ///////////////////////////////////////////////////////////////////////////
    // Static /////////////////////////////////////////////////////////////////

    /**
     * @return The boundary of the layout.
     */
    public static RectF getBound(List<List<RectF>> list) {
        float left = 0;
        float top = 0;
        float right = 0;
        float bottom = 0;

        for (List<RectF> subList : list) {
            for (RectF rect : subList) {
                left = Math.min(left, rect.left);
                top = Math.min(top, rect.top);
                right = Math.max(right, rect.right);
                bottom = Math.max(bottom, rect.bottom);
            }
        }

        return new RectF(left, top, right, bottom);
    }

    /**
     * @param layout The layout returned by sampleRow() method.
     * @param isIncludePadding Whether to take padding into account.
     */
    public static float rowsHeight(List<List<RectF>> layout, boolean isIncludePadding) {
        float ret = 0;

        for (List<RectF> subList : layout) {
            if (isIncludePadding) {
                ret = Math.max(ret, subList.get(0).bottom);
            } else {
                ret += subList.get(0).height();
            }
        }

        return ret;
    }

    /**
     * @param layout The layout returned by sampleCol() method.
     * @param isIncludePadding Whether to take padding into account.
     */
    public static float colsWidth(List<List<RectF>> layout, boolean isIncludePadding) {
        float ret = 0;

        for (List<RectF> subList : layout) {
            if (isIncludePadding) {
                ret = Math.max(ret, subList.get(0).right);
            } else {
                ret += subList.get(0).width();
            }
        }

        return ret;
    }

    ///////////////////////////////////////////////////////////////////////////
    // Privates ///////////////////////////////////////////////////////////////

    private void initCostsTable() {
        for (int i = 0; i < mCosts.length; ++i) {
            for (int j = 0; j < mCosts[i].length; ++j) {
                mCosts[i][j] = INFINITY;
            }
        }
    }

    /**
     * @return Width of the image maintaining the same aspect ratio with the
     * desired row height.
     */
    private float widthAt(int index) {
        IPhoto photo = mImages.get(index);

        if (photo.getHeight() != mDesiredRowHeight) {
            return photo.getWidth() * (mDesiredRowHeight / photo.getHeight());
        } else {
            return photo.getWidth();
        }
    }

    /**
     * @return Height of the image maintaining the same aspect ratio with the
     * desired column width.
     */
    private float heightAt(int index) {
        IPhoto photo = mImages.get(index);

        if (photo.getWidth() != mDesiredColWidth) {
            return photo.getHeight() * (mDesiredColWidth / photo.getWidth());
        } else {
            return photo.getHeight();
        }
    }

    /**
     * The penalty of the row starting with image ${start}, containing
     * ${amount} images.
     */
    private float rowPenaltyAt(int start, int amount) {
        float widths = 0;

        for (int i = start; i < start + amount; ++i) {
            widths += widthAt(i);
        }

        float diff = mDesiredRowWidth - (widths + (amount - 1) * mPadding);

        return (diff < 0 ? diff * -1 : diff);
    }

    /**
     * The penalty of the column starting with image ${start}, containing
     * ${amount} images.
     */
    private float colPenaltyAt(int start, int amount) {
        float heights = 0;

        for (int i = start; i < start + amount; ++i) {
            heights += heightAt(i);
        }

        float diff = mDesiredColHeight - (heights + (amount - 1) * mPadding);

        return (diff < 0 ? diff * -1 : diff);
    }

    /**
     * Fit/Center for layout where 1st dimension is rows.
<<<<<<< 433b078ac6414423fb1146e52877f75149797fca
=======
     * WARNING: The trade-off of this is that the widths of row might be
>>>>>>> Apply pack-grid algorithm to scraps from gallery picker. #5869
     * staggered.
     */
    private List<List<RectF>> fitCenter1(List<List<RectF>> layout, RectF bound) {
        RectF layoutBound = getBound(layout);
        float layoutHeight = layoutBound.height();

        if (layoutHeight > bound.height()) {
            // Scale to just fit and center the given boundary.
//            float padding = mPadding * (layout.size() - 1);
//            float scale = (bound.height() - padding) / rowsHeight(layout, false);
            float scale = bound.height() / layoutHeight;
            List<List<RectF>> newLayout = new ArrayList<>();
            float x = 0, y = 0;
            float left = 0, top = 0, right = 0, bottom = 0;

            // Scale layout so that it fits in the given boundary.
            for (int i = 0; i < layout.size(); ++i) {
                List<RectF> subLayout = layout.get(i);
                List<RectF> newSubLayout = new ArrayList<>();

                for (RectF rect : subLayout) {
                    float newWidth = scale * rect.width();
                    float newHeight = scale * rect.height();
                    RectF newRect = new RectF(x, y,
                                              x + newWidth,
                                              y + newHeight);

                    newSubLayout.add(newRect);

                    left = Math.min(left, newRect.left);
                    top = Math.min(top, newRect.top);
                    right = Math.max(right, newRect.right);
                    bottom = Math.max(bottom, newRect.bottom);

                    x += newWidth;
                    if (subLayout.indexOf(rect) < subLayout.size() - 1) {
                        x += scale * mPadding;
                    }
                }

                x = 0;
                y += newSubLayout.get(0).height();
                if (layout.indexOf(subLayout) < layout.size() - 1) {
                    y += scale * mPadding;
                }

                newLayout.add(newSubLayout);
            }

            layout = newLayout;

            // Update the boundary.
            layoutBound = new RectF(left, top,
                                    right, bottom);
        }

        // Center layout in the given boundary.
        float tx = bound.left + (bound.width() - layoutBound.width()) / 2;
        float ty = bound.top + (bound.height() - layoutBound.height()) / 2;
        for (List<RectF> subLayout : layout) {
            for (RectF rect : subLayout) {
                rect.offset(tx, ty);
            }
        }

        return layout;
    }

    /**
     * Fit/Center for layout where 1st dimension is columns.
<<<<<<< 433b078ac6414423fb1146e52877f75149797fca
=======
     * WARNING: The trade-off of this is that the heights of column might be
>>>>>>> Apply pack-grid algorithm to scraps from gallery picker. #5869
     * staggered.
     */
    private List<List<RectF>> fitCenter2(List<List<RectF>> layout, RectF bound) {
        RectF layoutBound = getBound(layout);
        float layoutWidth = layoutBound.width();

        if (layoutWidth > bound.width()) {
            // Scale to just fit and center the given boundary.
//            float padding = mPadding * (layout.size() - 1);
//            float scale = (bound.width() - padding) / colsWidth(layout, false);
            float scale = bound.width() / layoutWidth;
            List<List<RectF>> newLayout = new ArrayList<>();
            float x = 0, y = 0;
            float left = 0, top = 0, right = 0, bottom = 0;

            // Scale layout so that it fits in the given boundary.
            for (int i = 0; i < layout.size(); ++i) {
                List<RectF> subLayout = layout.get(i);
                List<RectF> newSubLayout = new ArrayList<>();

                for (RectF rect : subLayout) {
                    float newWidth = scale * rect.width();
                    float newHeight = scale * rect.height();
                    RectF newRect = new RectF(x, y,
                                              x + newWidth,
                                              y + newHeight);

                    newSubLayout.add(newRect);

                    left = Math.min(left, newRect.left);
                    top = Math.min(top, newRect.top);
                    right = Math.max(right, newRect.right);
                    bottom = Math.max(bottom, newRect.bottom);

                    y += newHeight;
                    if (subLayout.indexOf(rect) < subLayout.size() - 1) {
                        y += scale * mPadding;
                    }
                }

                x += newSubLayout.get(0).width();
                y = 0;
                if (layout.indexOf(subLayout) < layout.size() - 1) {
                    x += scale * mPadding;
                }

                newLayout.add(newSubLayout);
            }

            layout = newLayout;

            // Update the boundary.
            layoutBound = new RectF(left, top,
                                    right, bottom);
        }

        // Center layout in the given boundary.
        float tx = bound.left + (bound.width() - layoutBound.width()) / 2;
        float ty = bound.top + (bound.height() - layoutBound.height()) / 2;
        for (List<RectF> subLayout : layout) {
            for (RectF rect : subLayout) {
                rect.offset(tx, ty);
            }
        }

        return layout;
    }
}