PriorityGoalRow.java

/*
 * Copyright (C) 2020 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 java.util.Arrays;
import java.util.Comparator;

/**
 * Implements a row containing goals taking in account priorities.
 */
public class PriorityGoalRow extends ArrayRow {
    private static final float epsilon = 0.0001f;
    private static final boolean DEBUG = false;

    private int TABLE_SIZE = 128;
    private SolverVariable[] arrayGoals = new SolverVariable[TABLE_SIZE];
    private SolverVariable[] sortArray = new SolverVariable[TABLE_SIZE];
    private int numGoals = 0;
    GoalVariableAccessor accessor = new GoalVariableAccessor(this);

    class GoalVariableAccessor implements Comparable {
        SolverVariable variable;
        PriorityGoalRow row;

        public GoalVariableAccessor(PriorityGoalRow row) {
            this.row = row;
        }

        public void init(SolverVariable variable) {
            this.variable = variable;
        }

        public boolean addToGoal(SolverVariable other, float value) {
            if (variable.inGoal) {
                boolean empty = true;
                for (int i = 0; i < SolverVariable.MAX_STRENGTH; i++) {
                    variable.goalStrengthVector[i] += other.goalStrengthVector[i] * value;
                    float v = variable.goalStrengthVector[i];
                    if (Math.abs(v) < epsilon) {
                        variable.goalStrengthVector[i] = 0;
                    } else {
                        empty = false;
                    }
                }
                if (empty) {
                    removeGoal(variable);
                }
            } else {
                for (int i = 0; i < SolverVariable.MAX_STRENGTH; i++) {
                    float strength = other.goalStrengthVector[i];
                    if (strength != 0) {
                        float v = value * strength;
                        if (Math.abs(v) < epsilon) {
                            v = 0;
                        }
                        variable.goalStrengthVector[i] = v;
                    } else {
                        variable.goalStrengthVector[i] = 0;
                    }
                }
                return true;
            }
            return false;
        }

        public void add(SolverVariable other) {
            for (int i = 0; i < SolverVariable.MAX_STRENGTH; i++) {
                variable.goalStrengthVector[i] += other.goalStrengthVector[i];
                float value = variable.goalStrengthVector[i];
                if (Math.abs(value) < epsilon) {
                    variable.goalStrengthVector[i] = 0;
                }
            }
        }

        public final boolean isNegative() {
            for (int i = SolverVariable.MAX_STRENGTH - 1; i >= 0; i--) {
                float value = variable.goalStrengthVector[i];
                if (value > 0) {
                    return false;
                }
                if (value < 0) {
                    return true;
                }
            }
            return false;
        }

        public final boolean isSmallerThan(SolverVariable other) {
            for (int i = SolverVariable.MAX_STRENGTH - 1; i >= 0 ; i--) {
                float comparedValue = other.goalStrengthVector[i];
                float value = variable.goalStrengthVector[i];
                if (value == comparedValue) {
                    continue;
                }
                if (value < comparedValue) {
                    return true;
                } else {
                    return false;
                }
            }
            return false;
        }

        public final boolean isNull() {
            for (int i = 0; i < SolverVariable.MAX_STRENGTH; i++) {
                if (variable.goalStrengthVector[i] != 0) {
                    return false;
                }
            }
            return true;
        }

        @Override
        public int compareTo(Object o) {
            SolverVariable v = (SolverVariable) o;
            return variable.id - v.id;
        }

        public void reset() {
            Arrays.fill(variable.goalStrengthVector, 0);
        }

        public String toString() {
            String result = "[ ";
            if (variable != null) {
                for (int i = 0; i < SolverVariable.MAX_STRENGTH; i++) {
                    result += variable.goalStrengthVector[i] + " ";
                }
            }
            result += "] " + variable;
            return result;
        }

    }

    @Override
    public void clear() {
        numGoals = 0;
        constantValue = 0;
    }

    Cache mCache;

    public PriorityGoalRow(Cache cache) {
        super(cache);
        mCache = cache;
    }

    @Override
    public boolean isEmpty() {
        return numGoals == 0;
    }

    final static int NOT_FOUND = -1;

    @Override
    public SolverVariable getPivotCandidate(LinearSystem system, boolean[] avoid) {
        int pivot = NOT_FOUND;
        for (int i = 0; i < numGoals; i++) {
            SolverVariable variable = arrayGoals[i];
            if (avoid[variable.id]) {
                continue;
            }
            accessor.init(variable);
            if (pivot == NOT_FOUND) {
                if (accessor.isNegative())  {
                    pivot = i;
                }
            } else if (accessor.isSmallerThan(arrayGoals[pivot])) {
                pivot = i;
            }
        }
        if (pivot == NOT_FOUND) {
            return null;
        }
        return arrayGoals[pivot];
    }

    @Override
    public void addError(SolverVariable error) {
        accessor.init(error);
        accessor.reset();
        error.goalStrengthVector[error.strength] = 1;
        addToGoal(error);
    }

    private final void addToGoal(SolverVariable variable) {
        if (numGoals + 1> arrayGoals.length) {
            arrayGoals = Arrays.copyOf(arrayGoals, arrayGoals.length * 2);
            sortArray = Arrays.copyOf(arrayGoals, arrayGoals.length * 2);
        }
        arrayGoals[numGoals] = variable;
        numGoals++;

        if (numGoals > 1 && arrayGoals[numGoals - 1].id > variable.id) {
            for (int i = 0; i < numGoals; i++) {
                sortArray[i] = arrayGoals[i];
            }
            Arrays.sort(sortArray, 0, numGoals, new Comparator<SolverVariable>() {
                @Override
                public int compare(SolverVariable variable1, SolverVariable variable2) {
                    return variable1.id - variable2.id;
                }
            });
            for (int i = 0; i < numGoals; i++) {
                arrayGoals[i] = sortArray[i];
            }
        }

        variable.inGoal = true;
        variable.addToRow(this);
    }

    private final void removeGoal(SolverVariable variable) {
        for (int i = 0; i < numGoals; i++) {
            if (arrayGoals[i] == variable) {
                for (int j = i; j < numGoals - 1; j++) {
                    arrayGoals[j] = arrayGoals[j + 1];
                }
                numGoals--;
                variable.inGoal = false;
                return;
            }
        }
    }

    @Override
    public void updateFromRow(LinearSystem system, ArrayRow definition, boolean removeFromDefinition) {
        SolverVariable goalVariable = definition.variable;
        if (goalVariable == null) {
            return;
        }

        ArrayRowVariables rowVariables = definition.variables;
        int currentSize = rowVariables.getCurrentSize();
        for (int i = 0; i < currentSize; i++) {
            SolverVariable solverVariable = rowVariables.getVariable(i);
            float value = rowVariables.getVariableValue(i);
            accessor.init(solverVariable);
            if (accessor.addToGoal(goalVariable, value)) {
                addToGoal(solverVariable);
            }
            constantValue += definition.constantValue * value;
        }
        removeGoal(goalVariable);
    }

    @Override
    public String toString() {
        String result = "";
        result += " goal -> (" + constantValue + ") : ";
        for (int i = 0; i < numGoals; i++) {
            SolverVariable v = arrayGoals[i];
            accessor.init(v);
            result += accessor + " ";
        }
        return result;
    }
}