ArrayRow.java

/*
 * Copyright (C) 2015 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;

import static androidx.constraintlayout.core.SolverVariable.STRENGTH_EQUALITY;
import static androidx.constraintlayout.core.SolverVariable.STRENGTH_HIGH;
import static androidx.constraintlayout.core.SolverVariable.STRENGTH_HIGHEST;
import static androidx.constraintlayout.core.SolverVariable.STRENGTH_LOW;
import static androidx.constraintlayout.core.SolverVariable.STRENGTH_MEDIUM;

import java.util.ArrayList;

public class ArrayRow implements LinearSystem.Row {
    private static final boolean DEBUG = false;

    SolverVariable mVariable = null;
    float mConstantValue = 0;
    boolean mUsed = false;
    private static final boolean FULL_NEW_CHECK = false; // full validation (debug purposes)

    ArrayList<SolverVariable> mVariablesToUpdate = new ArrayList<>();

    public ArrayRowVariables variables;

    public interface ArrayRowVariables {

        // @TODO: add description
        int getCurrentSize();

        // @TODO: add description
        SolverVariable getVariable(int index);

        // @TODO: add description
        float getVariableValue(int index);

        // @TODO: add description
        float get(SolverVariable variable);

        // @TODO: add description
        int indexOf(SolverVariable variable);

        // @TODO: add description
        void display();

        // @TODO: add description
        void clear();

        // @TODO: add description
        boolean contains(SolverVariable variable);

        // @TODO: add description
        void put(SolverVariable variable, float value);

        // @TODO: add description
        int sizeInBytes();

        // @TODO: add description
        void invert();

        // @TODO: add description
        float remove(SolverVariable v, boolean removeFromDefinition);

        // @TODO: add description
        void divideByAmount(float amount);

        // @TODO: add description
        void add(SolverVariable v, float value, boolean removeFromDefinition);

        // @TODO: add description
        float use(ArrayRow definition, boolean removeFromDefinition);
    }

    boolean mIsSimpleDefinition = false;

    public ArrayRow() {
    }

    public ArrayRow(Cache cache) {
        variables = new ArrayLinkedVariables(this, cache);
        //variables = new OptimizedSolverVariableValues(this, cache);
    }

    boolean hasKeyVariable() {
        return !(
                (mVariable == null)
                        || (mVariable.mType != SolverVariable.Type.UNRESTRICTED
                        && mConstantValue < 0)
        );
    }

    // @TODO: add description
    @Override
    public String toString() {
        return toReadableString();
    }

    String toReadableString() {
        String s = "";
        if (mVariable == null) {
            s += "0";
        } else {
            s += mVariable;
        }
        s += " = ";
        boolean addedVariable = false;
        if (mConstantValue != 0) {
            s += mConstantValue;
            addedVariable = true;
        }
        int count = variables.getCurrentSize();
        for (int i = 0; i < count; i++) {
            SolverVariable v = variables.getVariable(i);
            if (v == null) {
                continue;
            }
            float amount = variables.getVariableValue(i);
            if (amount == 0) {
                continue;
            }
            String name = v.toString();
            if (!addedVariable) {
                if (amount < 0) {
                    s += "- ";
                    amount *= -1;
                }
            } else {
                if (amount > 0) {
                    s += " + ";
                } else {
                    s += " - ";
                    amount *= -1;
                }
            }
            if (amount == 1) {
                s += name;
            } else {
                s += amount + " " + name;
            }
            addedVariable = true;
        }
        if (!addedVariable) {
            s += "0.0";
        }
        if (DEBUG) {
            variables.display();
        }
        return s;
    }

    // @TODO: add description
    public void reset() {
        mVariable = null;
        variables.clear();
        mConstantValue = 0;
        mIsSimpleDefinition = false;
    }

    boolean hasVariable(SolverVariable v) {
        return variables.contains(v);
    }

    ArrayRow createRowDefinition(SolverVariable variable, int value) {
        this.mVariable = variable;
        variable.computedValue = value;
        mConstantValue = value;
        mIsSimpleDefinition = true;
        return this;
    }

    // @TODO: add description
    public ArrayRow createRowEquals(SolverVariable variable, int value) {
        if (value < 0) {
            mConstantValue = -1 * value;
            variables.put(variable, 1);
        } else {
            mConstantValue = value;
            variables.put(variable, -1);
        }
        return this;
    }

    // @TODO: add description
    public ArrayRow createRowEquals(SolverVariable variableA,
            SolverVariable variableB,
            int margin) {
        boolean inverse = false;
        if (margin != 0) {
            int m = margin;
            if (m < 0) {
                m = -1 * m;
                inverse = true;
            }
            mConstantValue = m;
        }
        if (!inverse) {
            variables.put(variableA, -1);
            variables.put(variableB, 1);
        } else {
            variables.put(variableA, 1);
            variables.put(variableB, -1);
        }
        return this;
    }

    // @TODO: add description
    ArrayRow addSingleError(SolverVariable error, int sign) {
        variables.put(error, (float) sign);
        return this;
    }

    // @TODO: add description
    public ArrayRow createRowGreaterThan(SolverVariable variableA,
            SolverVariable variableB, SolverVariable slack,
            int margin) {
        boolean inverse = false;
        if (margin != 0) {
            int m = margin;
            if (m < 0) {
                m = -1 * m;
                inverse = true;
            }
            mConstantValue = m;
        }
        if (!inverse) {
            variables.put(variableA, -1);
            variables.put(variableB, 1);
            variables.put(slack, 1);
        } else {
            variables.put(variableA, 1);
            variables.put(variableB, -1);
            variables.put(slack, -1);
        }
        return this;
    }

    // @TODO: add description
    public ArrayRow createRowGreaterThan(SolverVariable a, int b, SolverVariable slack) {
        mConstantValue = b;
        variables.put(a, -1);
        return this;
    }

    // @TODO: add description
    public ArrayRow createRowLowerThan(SolverVariable variableA, SolverVariable variableB,
            SolverVariable slack, int margin) {
        boolean inverse = false;
        if (margin != 0) {
            int m = margin;
            if (m < 0) {
                m = -1 * m;
                inverse = true;
            }
            mConstantValue = m;
        }
        if (!inverse) {
            variables.put(variableA, -1);
            variables.put(variableB, 1);
            variables.put(slack, -1);
        } else {
            variables.put(variableA, 1);
            variables.put(variableB, -1);
            variables.put(slack, 1);
        }
        return this;
    }

    // @TODO: add description
    public ArrayRow createRowEqualMatchDimensions(float currentWeight,
            float totalWeights, float nextWeight,
            SolverVariable variableStartA,
            SolverVariable variableEndA,
            SolverVariable variableStartB,
            SolverVariable variableEndB) {
        mConstantValue = 0;
        if (totalWeights == 0 || (currentWeight == nextWeight)) {
            // endA - startA == endB - startB
            // 0 = startA - endA + endB - startB
            variables.put(variableStartA, 1);
            variables.put(variableEndA, -1);
            variables.put(variableEndB, 1);
            variables.put(variableStartB, -1);
        } else {
            if (currentWeight == 0) {
                variables.put(variableStartA, 1);
                variables.put(variableEndA, -1);
            } else if (nextWeight == 0) {
                variables.put(variableStartB, 1);
                variables.put(variableEndB, -1);
            } else {
                float cw = currentWeight / totalWeights;
                float nw = nextWeight / totalWeights;
                float w = cw / nw;

                // endA - startA == w * (endB - startB)
                // 0 = startA - endA + w * (endB - startB)
                variables.put(variableStartA, 1);
                variables.put(variableEndA, -1);
                variables.put(variableEndB, w);
                variables.put(variableStartB, -w);
            }
        }
        return this;
    }

    // @TODO: add description
    public ArrayRow createRowEqualDimension(float currentWeight,
            float totalWeights, float nextWeight,
            SolverVariable variableStartA, int marginStartA,
            SolverVariable variableEndA, int marginEndA,
            SolverVariable variableStartB, int marginStartB,
            SolverVariable variableEndB, int marginEndB) {
        if (totalWeights == 0 || (currentWeight == nextWeight)) {
            // endA - startA + marginStartA + marginEndA
            //      == endB - startB + marginStartB + marginEndB
            // 0 = startA - endA - marginStartA - marginEndA
            //      + endB - startB + marginStartB + marginEndB
            // 0 = (- marginStartA - marginEndA + marginStartB + marginEndB)
            //      + startA - endA + endB - startB
            mConstantValue = -marginStartA - marginEndA + marginStartB + marginEndB;
            variables.put(variableStartA, 1);
            variables.put(variableEndA, -1);
            variables.put(variableEndB, 1);
            variables.put(variableStartB, -1);
        } else {
            float cw = currentWeight / totalWeights;
            float nw = nextWeight / totalWeights;
            float w = cw / nw;
            // (endA - startA + marginStartA + marginEndA) =
            //      w * (endB - startB) + marginStartB + marginEndB;
            // 0 = (startA - endA - marginStartA - marginEndA)
            //      + w * (endB - startB) + marginStartB + marginEndB
            // 0 = (- marginStartA - marginEndA + marginStartB + marginEndB)
            //      + startA - endA + w * endB - w * startB
            mConstantValue = -marginStartA - marginEndA + w * marginStartB + w * marginEndB;
            variables.put(variableStartA, 1);
            variables.put(variableEndA, -1);
            variables.put(variableEndB, w);
            variables.put(variableStartB, -w);
        }
        return this;
    }

    ArrayRow createRowCentering(SolverVariable variableA, SolverVariable variableB,
            int marginA, float bias, SolverVariable variableC,
            SolverVariable variableD, int marginB) {
        if (variableB == variableC) {
            // centering on the same position
            // B - A == D - B
            // 0 = A + D - 2 * B
            variables.put(variableA, 1);
            variables.put(variableD, 1);
            variables.put(variableB, -2);
            return this;
        }
        if (bias == 0.5f) {
            // don't bother applying the bias, we are centered
            // A - B = C - D
            // 0 = A - B - C + D
            // with margin:
            // A - B - Ma = C - D - Mb
            // 0 = A - B - C + D - Ma + Mb
            variables.put(variableA, 1f);
            variables.put(variableB, -1f);
            variables.put(variableC, -1f);
            variables.put(variableD, 1f);
            if (marginA > 0 || marginB > 0) {
                mConstantValue = -marginA + marginB;
            }
        } else if (bias <= 0) {
            // A = B + m
            variables.put(variableA, -1);
            variables.put(variableB, 1);
            mConstantValue = marginA;
        } else if (bias >= 1) {
            // D = C - m
            variables.put(variableD, -1);
            variables.put(variableC, 1);
            mConstantValue = -marginB;
        } else {
            variables.put(variableA, 1 * (1 - bias));
            variables.put(variableB, -1 * (1 - bias));
            variables.put(variableC, -1 * bias);
            variables.put(variableD, 1 * bias);
            if (marginA > 0 || marginB > 0) {
                mConstantValue = -marginA * (1 - bias) + marginB * bias;
            }
        }
        return this;
    }

    // @TODO: add description
    public ArrayRow addError(LinearSystem system, int strength) {
        variables.put(system.createErrorVariable(strength, "ep"), 1);
        variables.put(system.createErrorVariable(strength, "em"), -1);
        return this;
    }

    ArrayRow createRowDimensionPercent(SolverVariable variableA,
            SolverVariable variableC, float percent) {
        variables.put(variableA, -1);
        variables.put(variableC, percent);
        return this;
    }

    /**
     * Create a constraint to express {@code A = B + (C - D)} * ratio
     * We use this for ratio, where for example {@code Right = Left + (Bottom - Top) * percent}
     *
     * @param variableA variable A
     * @param variableB variable B
     * @param variableC variable C
     * @param variableD variable D
     * @param ratio     ratio between AB and CD
     * @return the row
     */
    public ArrayRow createRowDimensionRatio(SolverVariable variableA, SolverVariable variableB,
            SolverVariable variableC, SolverVariable variableD,
            float ratio) {
        // A = B + (C - D) * ratio
        variables.put(variableA, -1);
        variables.put(variableB, 1);
        variables.put(variableC, ratio);
        variables.put(variableD, -ratio);
        return this;
    }

    /**
     * Create a constraint to express At + (Ab-At)/2 = Bt + (Bb-Bt)/2 - angle
     */
    public ArrayRow createRowWithAngle(SolverVariable at,
            SolverVariable ab,
            SolverVariable bt,
            SolverVariable bb,
            float angleComponent) {
        variables.put(bt, 0.5f);
        variables.put(bb, 0.5f);
        variables.put(at, -0.5f);
        variables.put(ab, -0.5f);
        mConstantValue = -angleComponent;
        return this;
    }

    int sizeInBytes() {
        int size = 0;
        if (mVariable != null) {
            size += 4; // object
        }
        size += 4; // constantValue
        size += 4; // used

        size += variables.sizeInBytes();
        return size;
    }

    void ensurePositiveConstant() {
        // Ensure that if we have a constant it's positive
        if (mConstantValue < 0) {
            // If not, simply multiply the equation by -1
            mConstantValue *= -1;
            variables.invert();
        }
    }

    /**
     * Pick a subject variable out of the existing ones.
     * - if a variable is unrestricted
     * - or if it's a negative new variable (not found elsewhere)
     * - otherwise we have to add a new additional variable
     *
     * @return true if we added an extra variable to the system
     */
    boolean chooseSubject(LinearSystem system) {
        boolean addedExtra = false;
        SolverVariable pivotCandidate = chooseSubjectInVariables(system);
        if (pivotCandidate == null) {
            // need to add extra variable
            addedExtra = true;
        } else {
            pivot(pivotCandidate);
        }
        if (variables.getCurrentSize() == 0) {
            mIsSimpleDefinition = true;
        }
        return addedExtra;
    }

    /**
     * Pick a subject variable out of the existing ones.
     * - if a variable is unrestricted
     * - or if it's a negative new variable (not found elsewhere)
     * - otherwise we return null
     *
     * @return a candidate variable we can pivot on or null if not found
     */
    SolverVariable chooseSubjectInVariables(LinearSystem system) {
        // if unrestricted, pick it
        // if restricted, needs to be < 0 and new
        //
        SolverVariable restrictedCandidate = null;
        SolverVariable unrestrictedCandidate = null;
        float unrestrictedCandidateAmount = 0;
        float restrictedCandidateAmount = 0;
        boolean unrestrictedCandidateIsNew = false;
        boolean restrictedCandidateIsNew = false;

        final int currentSize = variables.getCurrentSize();
        for (int i = 0; i < currentSize; i++) {
            float amount = variables.getVariableValue(i);
            SolverVariable variable = variables.getVariable(i);
            if (variable.mType == SolverVariable.Type.UNRESTRICTED) {
                if (unrestrictedCandidate == null) {
                    unrestrictedCandidate = variable;
                    unrestrictedCandidateAmount = amount;
                    unrestrictedCandidateIsNew = isNew(variable, system);
                } else if (unrestrictedCandidateAmount > amount) {
                    unrestrictedCandidate = variable;
                    unrestrictedCandidateAmount = amount;
                    unrestrictedCandidateIsNew = isNew(variable, system);
                } else if (!unrestrictedCandidateIsNew && isNew(variable, system)) {
                    unrestrictedCandidate = variable;
                    unrestrictedCandidateAmount = amount;
                    unrestrictedCandidateIsNew = true;
                }
            } else if (unrestrictedCandidate == null) {
                if (amount < 0) {
                    if (restrictedCandidate == null) {
                        restrictedCandidate = variable;
                        restrictedCandidateAmount = amount;
                        restrictedCandidateIsNew = isNew(variable, system);
                    } else if (restrictedCandidateAmount > amount) {
                        restrictedCandidate = variable;
                        restrictedCandidateAmount = amount;
                        restrictedCandidateIsNew = isNew(variable, system);
                    } else if (!restrictedCandidateIsNew && isNew(variable, system)) {
                        restrictedCandidate = variable;
                        restrictedCandidateAmount = amount;
                        restrictedCandidateIsNew = true;
                    }
                }
            }
        }

        if (unrestrictedCandidate != null) {
            return unrestrictedCandidate;
        }
        return restrictedCandidate;
    }

    /**
     * Returns true if the variable is new to the system, i.e. is already present
     * in one of the rows. This function is called while choosing the subject of a new row.
     *
     * @param variable the variable to check for
     * @param system   the linear system we check
     */
    private boolean isNew(SolverVariable variable, LinearSystem system) {
        if (FULL_NEW_CHECK) {
            boolean isNew = true;
            for (int i = 0; i < system.mNumRows; i++) {
                ArrayRow row = system.mRows[i];
                if (row.hasVariable(variable)) {
                    isNew = false;
                }
            }
            if (variable.usageInRowCount <= 1 != isNew) {
                System.out.println("Problem with usage tracking");
            }
            return isNew;
        }
        // We maintain a usage count -- variables are ref counted if they are present
        // in the right side of a row or not. If the count is zero or one, the variable
        // is new (if one, it means it exist in a row, but this is the row we insert)
        return variable.usageInRowCount <= 1;
    }

    void pivot(SolverVariable v) {
        if (mVariable != null) {
            // first, move back the variable to its column
            variables.put(mVariable, -1f);
            mVariable.mDefinitionId = -1;
            mVariable = null;
        }

        float amount = variables.remove(v, true) * -1;
        mVariable = v;
        if (amount == 1) {
            return;
        }
        mConstantValue = mConstantValue / amount;
        variables.divideByAmount(amount);
    }

    // Row compatibility

    @Override
    public boolean isEmpty() {
        return (mVariable == null && mConstantValue == 0 && variables.getCurrentSize() == 0);
    }

    @Override
    public void updateFromRow(LinearSystem system,
            ArrayRow definition,
            boolean removeFromDefinition) {
        float value = variables.use(definition, removeFromDefinition);

        mConstantValue += definition.mConstantValue * value;
        if (removeFromDefinition) {
            definition.mVariable.removeFromRow(this);
        }
        if (LinearSystem.SIMPLIFY_SYNONYMS
                && mVariable != null && variables.getCurrentSize() == 0) {
            mIsSimpleDefinition = true;
            system.hasSimpleDefinition = true;
        }
    }

    // @TODO: add description
    @Override
    public void updateFromFinalVariable(LinearSystem system,
            SolverVariable variable,
            boolean removeFromDefinition) {
        if (variable == null || !variable.isFinalValue) {
            return;
        }
        float value = variables.get(variable);
        mConstantValue += variable.computedValue * value;
        variables.remove(variable, removeFromDefinition);
        if (removeFromDefinition) {
            variable.removeFromRow(this);
        }
        if (LinearSystem.SIMPLIFY_SYNONYMS
                && variables.getCurrentSize() == 0) {
            mIsSimpleDefinition = true;
            system.hasSimpleDefinition = true;
        }
    }

    // @TODO: add description
    public void updateFromSynonymVariable(LinearSystem system,
            SolverVariable variable,
            boolean removeFromDefinition) {
        if (variable == null || !variable.mIsSynonym) {
            return;
        }
        float value = variables.get(variable);
        mConstantValue += variable.mSynonymDelta * value;
        variables.remove(variable, removeFromDefinition);
        if (removeFromDefinition) {
            variable.removeFromRow(this);
        }
        variables.add(system.mCache.mIndexedVariables[variable.mSynonym],
                value, removeFromDefinition);
        if (LinearSystem.SIMPLIFY_SYNONYMS
                && variables.getCurrentSize() == 0) {
            mIsSimpleDefinition = true;
            system.hasSimpleDefinition = true;
        }
    }

    private SolverVariable pickPivotInVariables(boolean[] avoid, SolverVariable exclude) {
        boolean all = true;
        float value = 0;
        SolverVariable pivot = null;
        SolverVariable pivotSlack = null;
        float valueSlack = 0;

        final int currentSize = variables.getCurrentSize();
        for (int i = 0; i < currentSize; i++) {
            float currentValue = variables.getVariableValue(i);
            if (currentValue < 0) {
                // We can return the first negative candidate as in ArrayLinkedVariables
                // they are already sorted by id
                SolverVariable v = variables.getVariable(i);
                if (!((avoid != null && avoid[v.id]) || (v == exclude))) {
                    if (all) {
                        if (v.mType == SolverVariable.Type.SLACK
                                || v.mType == SolverVariable.Type.ERROR) {
                            if (currentValue < value) {
                                value = currentValue;
                                pivot = v;
                            }
                        }
                    } else {
                        if (v.mType == SolverVariable.Type.SLACK) {
                            if (currentValue < valueSlack) {
                                valueSlack = currentValue;
                                pivotSlack = v;
                            }
                        } else if (v.mType == SolverVariable.Type.ERROR) {
                            if (currentValue < value) {
                                value = currentValue;
                                pivot = v;
                            }
                        }
                    }
                }
            }
        }
        if (all) {
            return pivot;
        }
        return pivot != null ? pivot : pivotSlack;
    }

    // @TODO: add description
    public SolverVariable pickPivot(SolverVariable exclude) {
        return pickPivotInVariables(null, exclude);
    }

    @Override
    public SolverVariable getPivotCandidate(LinearSystem system, boolean[] avoid) {
        return pickPivotInVariables(avoid, null);
    }

    @Override
    public void clear() {
        variables.clear();
        mVariable = null;
        mConstantValue = 0;
    }

    /**
     * Used to initiate a goal from a given row (to see if we can remove an extra var)
     */
    @Override
    public void initFromRow(@SuppressWarnings("HiddenTypeParameter") LinearSystem.Row row) {
        if (row instanceof ArrayRow) {
            ArrayRow copiedRow = (ArrayRow) row;
            mVariable = null;
            variables.clear();
            for (int i = 0; i < copiedRow.variables.getCurrentSize(); i++) {
                SolverVariable var = copiedRow.variables.getVariable(i);
                float val = copiedRow.variables.getVariableValue(i);
                variables.add(var, val, true);
            }
        }
    }

    @Override
    public void addError(SolverVariable error) {
        float weight = 1;
        if (error.strength == STRENGTH_LOW) {
            weight = 1F;
        } else if (error.strength == STRENGTH_MEDIUM) {
            weight = 1E3F;
        } else if (error.strength == STRENGTH_HIGH) {
            weight = 1E6F;
        } else if (error.strength == STRENGTH_HIGHEST) {
            weight = 1E9F;
        } else if (error.strength == STRENGTH_EQUALITY) {
            weight = 1E12F;
        }
        variables.put(error, weight);
    }

    @Override
    public SolverVariable getKey() {
        return mVariable;
    }

    @Override
    public void updateFromSystem(LinearSystem system) {
        if (system.mRows.length == 0) {
            return;
        }

        boolean done = false;
        while (!done) {
            int currentSize = variables.getCurrentSize();
            for (int i = 0; i < currentSize; i++) {
                SolverVariable variable = variables.getVariable(i);
                if (variable.mDefinitionId != -1 || variable.isFinalValue || variable.mIsSynonym) {
                    mVariablesToUpdate.add(variable);
                }
            }
            final int size = mVariablesToUpdate.size();
            if (size > 0) {
                for (int i = 0; i < size; i++) {
                    SolverVariable variable = mVariablesToUpdate.get(i);
                    if (variable.isFinalValue) {
                        updateFromFinalVariable(system, variable, true);
                    } else if (variable.mIsSynonym) {
                        updateFromSynonymVariable(system, variable, true);
                    } else {
                        updateFromRow(system, system.mRows[variable.mDefinitionId], true);
                    }
                }
                mVariablesToUpdate.clear();
            } else {
                done = true;
            }
        }
        if (LinearSystem.SIMPLIFY_SYNONYMS
                && mVariable != null && variables.getCurrentSize() == 0) {
            mIsSimpleDefinition = true;
            system.hasSimpleDefinition = true;
        }
    }
}