xref: /constraintlayout/constraintlayout-core/src/main/java/androidx/constraintlayout/core/utils/GridEngine.java

/*
 * Copyright (C) 2022 The Android Open Source 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 androidx.constraintlayout.core.utils;

import java.util.Arrays;

/**
 * GridEngine class contains the main logic of the Grid Helper
 */
public class GridEngine {

    public static final int VERTICAL = 1;
    public static final int HORIZONTAL = 0;
    private static final int MAX_ROWS = 50; // maximum number of rows can be specified.
    private static final int MAX_COLUMNS = 50; // maximum number of columns can be specified.
    private static final int DEFAULT_SIZE = 3; // default rows and columns.

    /**
     * number of rows of the grid
     */
    private int mRows;

    /**
     * number of rows set by the XML or API
     */
    private int mRowsSet;

    /**
     * How many widgets need to be placed in the Grid
     */
    private int mNumWidgets;

    /**
     * number of columns of the grid
     */
    private int mColumns;

    /**
     * number of columns set by the XML or API
     */
    private int mColumnsSet;

    /**
     * string format of the input Spans
     */
    private String mStrSpans;

    /**
     * string format of the input Skips
     */
    private String mStrSkips;

    /**
     * orientation of the view arrangement - vertical or horizontal
     */
    private int mOrientation;

    /**
     * Indicates what is the next available position to place an widget
     */
    private int mNextAvailableIndex = 0;

    /**
     * A boolean matrix that tracks the positions that are occupied by skips and spans
     * true: available position
     * false: non-available position
     */
    private boolean[][] mPositionMatrix;

    /**
     * A int matrix that contains the positions where a widget would constraint to at each direction
     * Each row contains 4 values that indicate the position to constraint of a widget.
     * Example row: [left, top, right, bottom]
     */
    private int[][] mConstraintMatrix;

    public GridEngine() {}

    public GridEngine(int rows, int columns) {
        mRowsSet = rows;
        mColumnsSet = columns;
        if (rows > MAX_ROWS) {
            mRowsSet = DEFAULT_SIZE;
        }

        if (columns > MAX_COLUMNS) {
            mColumnsSet = DEFAULT_SIZE;
        }

        updateActualRowsAndColumns();
        initVariables();
    }

    public GridEngine(int rows, int columns, int numWidgets) {
        mRowsSet = rows;
        mColumnsSet = columns;
        mNumWidgets = numWidgets;

        if (rows > MAX_ROWS) {
            mRowsSet = DEFAULT_SIZE;
        }

        if (columns > MAX_COLUMNS) {
            mColumnsSet = DEFAULT_SIZE;
        }

        updateActualRowsAndColumns();

        if (numWidgets > mRows * mColumns || numWidgets < 1) {
            mNumWidgets = mRows * mColumns;
        }

        initVariables();
        fillConstraintMatrix(false);
    }

    /**
     * Initialize the relevant variables
     */
    private void initVariables() {
        mPositionMatrix = new boolean[mRows][mColumns];
        for (boolean[] row : mPositionMatrix) {
            Arrays.fill(row, true);
        }

        if (mNumWidgets > 0) {
            mConstraintMatrix = new int[mNumWidgets][4];
            for (int[] row : mConstraintMatrix) {
                Arrays.fill(row, -1);
            }
        }
    }

    /**
     * Convert a 1D index to a 2D index that has index for row and index for column
     *
     * @param index index in 1D
     * @return row as its values.
     */
    private int getRowByIndex(int index) {
        if (mOrientation == 1) {
            return index % mRows;

        } else {
            return index / mColumns;
        }
    }

    /**
     * Convert a 1D index to a 2D index that has index for row and index for column
     *
     * @param index index in 1D
     * @return column as its values.
     */
    private int getColByIndex(int index) {
        if (mOrientation == 1) {
            return index / mRows;
        } else {
            return index % mColumns;
        }
    }

    /**
     * Check if the value of the spans/skips is valid
     *
     * @param str spans/skips in string format
     * @return true if it is valid else false
     */
    private boolean isSpansValid(CharSequence str) {
        if (str == null) {
            return false;
        }
        return true;
    }

    /**
     * parse the skips/spans in the string format into a int matrix
     * that each row has the information - [index, row_span, col_span]
     * the format of the input string is index:row_spanxcol_span.
     * index - the index of the starting position
     * row_span - the number of rows to span
     * col_span- the number of columns to span
     *
     * @param str string format of skips or spans
     * @return a int matrix that contains skip information.
     */
    private int[][] parseSpans(String str) {
        if (!isSpansValid(str)) {
            return null;
        }

        String[] spans = str.split(",");
        int[][] spanMatrix = new int[spans.length][3];

        String[] indexAndSpan;
        String[] rowAndCol;
        for (int i = 0; i < spans.length; i++) {
            indexAndSpan = spans[i].trim().split(":");
            rowAndCol = indexAndSpan[1].split("x");
            spanMatrix[i][0] = Integer.parseInt(indexAndSpan[0]);
            spanMatrix[i][1] = Integer.parseInt(rowAndCol[0]);
            spanMatrix[i][2] = Integer.parseInt(rowAndCol[1]);
        }
        return spanMatrix;
    }

    /**
     * fill the constraintMatrix based on the input attributes
     *
     * @param isUpdate whether to update the existing grid (true) or create a new one (false)
     */
    private void fillConstraintMatrix(boolean isUpdate) {
        if (isUpdate) {
            for (int i = 0; i < mPositionMatrix.length; i++) {
                for (int j = 0; j < mPositionMatrix[0].length; j++) {
                    mPositionMatrix[i][j] = true;
                }
            }

            for (int i = 0; i < mConstraintMatrix.length; i++) {
                for (int j = 0; j < mConstraintMatrix[0].length; j++) {
                    mConstraintMatrix[i][j] = -1;
                }
            }
        }

        mNextAvailableIndex = 0;

        if (mStrSkips != null && !mStrSkips.trim().isEmpty()) {
            int[][] mSkips = parseSpans(mStrSkips);
            if (mSkips != null) {
                handleSkips(mSkips);
            }
        }

        if (mStrSpans != null && !mStrSpans.trim().isEmpty()) {
            int[][] mSpans = parseSpans(mStrSpans);
            if (mSpans != null) {
                handleSpans(mSpans);
            }
        }

        addAllConstraintPositions();
    }

    /**
     * Get the next available position for widget arrangement.
     * @return int[] -> [row, column]
     */
    private int getNextPosition() {
        int position = 0;
        boolean positionFound = false;

        while (!positionFound) {
            if (mNextAvailableIndex >= mRows * mColumns) {
                return -1;
            }

            position = mNextAvailableIndex;
            int row = getRowByIndex(mNextAvailableIndex);
            int col = getColByIndex(mNextAvailableIndex);
            if (mPositionMatrix[row][col]) {
                mPositionMatrix[row][col] = false;
                positionFound = true;
            }

            mNextAvailableIndex++;
        }
        return position;
    }

    /**
     * add the constraint position info of a widget based on the input params
     *
     * @param widgetId the Id of the widget
     * @param row row position to place the view
     * @param column column position to place the view
     */
    private void addConstraintPosition(int widgetId, int row, int column,
                                       int rowSpan, int columnSpan) {

        mConstraintMatrix[widgetId][0] = column;
        mConstraintMatrix[widgetId][1] = row;
        mConstraintMatrix[widgetId][2] = column + columnSpan - 1;
        mConstraintMatrix[widgetId][3] = row + rowSpan - 1;
    }

    /**
     * Handle the span use cases
     *
     * @param spansMatrix a int matrix that contains span information
     */
    private void handleSpans(int[][] spansMatrix) {
        for (int i = 0; i < spansMatrix.length; i++) {
            int row = getRowByIndex(spansMatrix[i][0]);
            int col = getColByIndex(spansMatrix[i][0]);
            if (!invalidatePositions(row, col,
                    spansMatrix[i][1], spansMatrix[i][2])) {
                return;
            }
            addConstraintPosition(i, row, col,
                    spansMatrix[i][1], spansMatrix[i][2]);
        }
    }

    /**
     * Make positions in the grid unavailable based on the skips attr
     *
     * @param skipsMatrix a int matrix that contains skip information
     */
    private void handleSkips(int[][] skipsMatrix) {
        for (int i = 0; i < skipsMatrix.length; i++) {
            int row = getRowByIndex(skipsMatrix[i][0]);
            int col = getColByIndex(skipsMatrix[i][0]);
            if (!invalidatePositions(row, col,
                    skipsMatrix[i][1], skipsMatrix[i][2])) {
                return;
            }
        }
    }

    /**
     * Make the specified positions in the grid unavailable.
     *
     * @param startRow the row of the staring position
     * @param startColumn the column of the staring position
     * @param rowSpan how many rows to span
     * @param columnSpan how many columns to span
     * @return true if we could properly invalidate the positions else false
     */
    private boolean invalidatePositions(int startRow, int startColumn,
                                        int rowSpan, int columnSpan) {
        for (int i = startRow; i < startRow + rowSpan; i++) {
            for (int j = startColumn; j < startColumn + columnSpan; j++) {
                if (i >= mPositionMatrix.length || j >= mPositionMatrix[0].length
                        || !mPositionMatrix[i][j]) {
                    // the position is already occupied.
                    return false;
                }
                mPositionMatrix[i][j] = false;
            }
        }
        return true;
    }

    /**
     * Arrange the views in the constraint_referenced_ids
     */
    private void addAllConstraintPositions() {
        int position;

        for (int i = 0; i < mNumWidgets; i++) {

            // Already added ConstraintPosition
            if (leftOfWidget(i) != -1) {
                continue;
            }

            position = getNextPosition();
            int row = getRowByIndex(position);
            int col = getColByIndex(position);
            if (position == -1) {
                // no more available position.
                return;
            }
            addConstraintPosition(i, row, col, 1, 1);
        }
    }

    /**
     * Compute the actual rows and columns given what was set
     * if 0,0 find the most square rows and columns that fits
     * if 0,n or n,0 scale to fit
     */
    private void updateActualRowsAndColumns() {
        if (mRowsSet == 0 || mColumnsSet == 0) {
            if (mColumnsSet > 0) {
                mColumns = mColumnsSet;
                mRows = (mNumWidgets + mColumns - 1) / mColumnsSet; // round up
            } else  if (mRowsSet > 0) {
                mRows = mRowsSet;
                mColumns = (mNumWidgets + mRowsSet - 1) / mRowsSet; // round up
            } else { // as close to square as possible favoring more rows
                mRows = (int)  (1.5 + Math.sqrt(mNumWidgets));
                mColumns = (mNumWidgets + mRows - 1) / mRows;
            }
        } else {
            mRows = mRowsSet;
            mColumns = mColumnsSet;
        }
    }

    /**
     * Set up the Grid engine.
     */
    public void setup() {
        boolean isUpdate = true;

        if (mConstraintMatrix == null
                || mConstraintMatrix.length != mNumWidgets
                || mPositionMatrix == null
                || mPositionMatrix.length != mRows
                || mPositionMatrix[0].length != mColumns) {
            isUpdate = false;
        }

        if (!isUpdate) {
            initVariables();
        }

        fillConstraintMatrix(isUpdate);
    }

    /**
     * set new spans value
     *
     * @param spans new spans value
     */
    public void setSpans(CharSequence spans) {
        if (mStrSpans != null && mStrSpans.equals(spans.toString())) {
            return;
        }

        mStrSpans = spans.toString();
    }

    /**
     * set new skips value
     *
     * @param skips new spans value
     */
    public void setSkips(String skips) {
        if (mStrSkips != null && mStrSkips.equals(skips)) {
            return;
        }

        mStrSkips = skips;

    }

    /**
     * set new orientation value
     *
     * @param orientation new orientation value
     */
    public void setOrientation(int orientation) {
        if (!(orientation == HORIZONTAL || orientation == VERTICAL)) {
            return;
        }

        if (mOrientation == orientation) {
            return;
        }

        mOrientation = orientation;
    }

    /**
     * Set new NumWidgets value
     * @param num how many widgets to be arranged in Grid
     */
    public void setNumWidgets(int num) {
        if (num > mRows * mColumns) {
            return;
        }

        mNumWidgets = num;
    }

    /**
     * set new rows value
     *
     * @param rows new rows value
     */
    public void setRows(int rows) {
        if (rows > MAX_ROWS) {
            return;
        }

        if (mRowsSet == rows) {
            return;
        }

        mRowsSet = rows;
        updateActualRowsAndColumns();

    }

    /**
     * set new columns value
     *
     * @param columns new rows value
     */
    public void setColumns(int columns) {
        if (columns > MAX_COLUMNS) {
            return;
        }

        if (mColumnsSet == columns) {
            return;
        }

        mColumnsSet = columns;
        updateActualRowsAndColumns();
    }

    /**
     * Get the boxView for the widget i to add a constraint on the left
     *
     * @param i the widget that has the order as i in the constraint_reference_ids
     * @return the boxView to add a constraint on the left
     */
    public int leftOfWidget(int i) {
        if (mConstraintMatrix == null || i >= mConstraintMatrix.length) {
            return 0;
        }
        return mConstraintMatrix[i][0];
    }

    /**
     * Get the boxView for the widget i to add a constraint on the top
     *
     * @param i the widget that has the order as i in the constraint_reference_ids
     * @return the boxView to add a constraint on the top
     */
    public int topOfWidget(int i) {
        if (mConstraintMatrix == null || i >= mConstraintMatrix.length) {
            return 0;
        }
        return mConstraintMatrix[i][1];
    }

    /**
     * Get the boxView for the widget i to add a constraint on the right
     *
     * @param i the widget that has the order as i in the constraint_reference_ids
     * @return the boxView to add a constraint on the right
     */
    public int rightOfWidget(int i) {
        if (mConstraintMatrix == null || i >= mConstraintMatrix.length) {
            return 0;
        }
        return mConstraintMatrix[i][2];
    }

    /**
     * Get the boxView for the widget i to add a constraint on the bottom
     *
     * @param i the widget that has the order as i in the constraint_reference_ids
     * @return the boxView to add a constraint on the bottom
     */
    public int bottomOfWidget(int i) {
        if (mConstraintMatrix == null || i >= mConstraintMatrix.length) {
            return 0;
        }
        return mConstraintMatrix[i][3];
    }
}