| /* |
| * 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 android.support.constraint.solver; |
| |
| import android.support.constraint.solver.widgets.ConstraintAnchor; |
| import android.support.constraint.solver.widgets.ConstraintWidget; |
| |
| import java.util.Arrays; |
| import java.util.HashMap; |
| |
| /** |
| * Represents and solve a system of linear equations. |
| */ |
| public class LinearSystem { |
| |
| public static final boolean FULL_DEBUG = false; |
| |
| private static final boolean DEBUG = FULL_DEBUG; |
| |
| /* |
| * Default size for the object pools |
| */ |
| private static int POOL_SIZE = 1000; |
| |
| /* |
| * Variable counter |
| */ |
| int mVariablesID = 0; |
| |
| /* |
| * Store a map between name->SolverVariable and SolverVariable->Float for the resolution. |
| */ |
| private HashMap<String, SolverVariable> mVariables = null; |
| |
| /* |
| * The goal that is used when minimizing the system. |
| */ |
| private Row mGoal; |
| |
| private int TABLE_SIZE = 32; // default table size for the allocation |
| private int mMaxColumns = TABLE_SIZE; |
| ArrayRow[] mRows = null; |
| |
| // if true, will use graph optimizations |
| public boolean graphOptimizer = false; |
| |
| // Used in optimize() |
| private boolean[] mAlreadyTestedCandidates = new boolean[TABLE_SIZE]; |
| |
| int mNumColumns = 1; |
| int mNumRows = 0; |
| private int mMaxRows = TABLE_SIZE; |
| |
| final Cache mCache; |
| |
| private SolverVariable[] mPoolVariables = new SolverVariable[POOL_SIZE]; |
| private int mPoolVariablesCount = 0; |
| |
| private ArrayRow[] tempClientsCopy = new ArrayRow[TABLE_SIZE]; |
| public static Metrics sMetrics; |
| |
| private final Row mTempGoal; |
| |
| public LinearSystem() { |
| mRows = new ArrayRow[TABLE_SIZE]; |
| releaseRows(); |
| mCache = new Cache(); |
| mGoal = new GoalRow(mCache); |
| mTempGoal = new ArrayRow(mCache); |
| } |
| |
| public void fillMetrics(Metrics metrics) { |
| sMetrics = metrics; |
| } |
| |
| public static Metrics getMetrics() { |
| return sMetrics; |
| } |
| |
| interface Row { |
| SolverVariable getPivotCandidate(LinearSystem system, boolean[] avoid); |
| void clear(); |
| void initFromRow(Row row); |
| void addError(SolverVariable variable); |
| |
| SolverVariable getKey(); |
| boolean isEmpty(); |
| } |
| |
| /*--------------------------------------------------------------------------------------------*/ |
| // Memory management |
| /*--------------------------------------------------------------------------------------------*/ |
| |
| /** |
| * Reallocate memory to accommodate increased amount of variables |
| */ |
| private void increaseTableSize() { |
| TABLE_SIZE *= 2; |
| mRows = Arrays.copyOf(mRows, TABLE_SIZE); |
| mCache.mIndexedVariables = Arrays.copyOf(mCache.mIndexedVariables, TABLE_SIZE); |
| mAlreadyTestedCandidates = new boolean[TABLE_SIZE]; |
| mMaxColumns = TABLE_SIZE; |
| mMaxRows = TABLE_SIZE; |
| if (sMetrics != null) { |
| sMetrics.tableSizeIncrease++; |
| sMetrics.maxTableSize = Math.max(sMetrics.maxTableSize, TABLE_SIZE); |
| sMetrics.lastTableSize = sMetrics.maxTableSize; |
| } |
| } |
| |
| /** |
| * Release ArrayRows back to their pool |
| */ |
| private void releaseRows() { |
| for (int i = 0; i < mRows.length; i++) { |
| ArrayRow row = mRows[i]; |
| if (row != null) { |
| mCache.arrayRowPool.release(row); |
| } |
| mRows[i] = null; |
| } |
| } |
| |
| /** |
| * Reset the LinearSystem object so that it can be reused. |
| */ |
| public void reset() { |
| for (int i = 0; i < mCache.mIndexedVariables.length; i++) { |
| SolverVariable variable = mCache.mIndexedVariables[i]; |
| if (variable != null) { |
| variable.reset(); |
| } |
| } |
| mCache.solverVariablePool.releaseAll(mPoolVariables, mPoolVariablesCount); |
| mPoolVariablesCount = 0; |
| |
| Arrays.fill(mCache.mIndexedVariables, null); |
| if (mVariables != null) { |
| mVariables.clear(); |
| } |
| mVariablesID = 0; |
| mGoal.clear(); |
| mNumColumns = 1; |
| for (int i = 0; i < mNumRows; i++) { |
| mRows[i].used = false; |
| } |
| releaseRows(); |
| mNumRows = 0; |
| } |
| |
| /*--------------------------------------------------------------------------------------------*/ |
| // Creation of rows / variables / errors |
| /*--------------------------------------------------------------------------------------------*/ |
| |
| public SolverVariable createObjectVariable(Object anchor) { |
| if (anchor == null) { |
| return null; |
| } |
| if (mNumColumns + 1 >= mMaxColumns) { |
| increaseTableSize(); |
| } |
| SolverVariable variable = null; |
| if (anchor instanceof ConstraintAnchor) { |
| variable = ((ConstraintAnchor) anchor).getSolverVariable(); |
| if (variable == null) { |
| ((ConstraintAnchor) anchor).resetSolverVariable(mCache); |
| variable = ((ConstraintAnchor) anchor).getSolverVariable(); |
| } |
| if (variable.id == -1 |
| || variable.id > mVariablesID |
| || mCache.mIndexedVariables[variable.id] == null) { |
| if (variable.id != -1) { |
| variable.reset(); |
| } |
| mVariablesID++; |
| mNumColumns++; |
| variable.id = mVariablesID; |
| variable.mType = SolverVariable.Type.UNRESTRICTED; |
| mCache.mIndexedVariables[mVariablesID] = variable; |
| } |
| } |
| return variable; |
| } |
| |
| public ArrayRow createRow() { |
| ArrayRow row = mCache.arrayRowPool.acquire(); |
| if (row == null) { |
| row = new ArrayRow(mCache); |
| } else { |
| row.reset(); |
| } |
| SolverVariable.increaseErrorId(); |
| return row; |
| } |
| |
| public SolverVariable createSlackVariable() { |
| if (sMetrics != null) { |
| sMetrics.slackvariables++; |
| } |
| if (mNumColumns + 1 >= mMaxColumns) { |
| increaseTableSize(); |
| } |
| SolverVariable variable = acquireSolverVariable(SolverVariable.Type.SLACK, null); |
| mVariablesID++; |
| mNumColumns++; |
| variable.id = mVariablesID; |
| mCache.mIndexedVariables[mVariablesID] = variable; |
| return variable; |
| } |
| |
| public SolverVariable createExtraVariable() { |
| if (sMetrics != null) { |
| sMetrics.extravariables++; |
| } |
| if (mNumColumns + 1 >= mMaxColumns) { |
| increaseTableSize(); |
| } |
| SolverVariable variable = acquireSolverVariable(SolverVariable.Type.SLACK, null); |
| mVariablesID++; |
| mNumColumns++; |
| variable.id = mVariablesID; |
| mCache.mIndexedVariables[mVariablesID] = variable; |
| return variable; |
| } |
| |
| private void addError(ArrayRow row) { |
| row.addError(this, SolverVariable.STRENGTH_NONE); |
| } |
| |
| private void addSingleError(ArrayRow row, int sign) { |
| addSingleError(row, sign, SolverVariable.STRENGTH_NONE); |
| } |
| |
| void addSingleError(ArrayRow row, int sign, int strength) { |
| String prefix = null; |
| if (DEBUG) { |
| if (sign > 0) { |
| prefix = "ep"; |
| } else { |
| prefix = "em"; |
| } |
| prefix = "em"; |
| } |
| SolverVariable error = createErrorVariable(strength, prefix); |
| row.addSingleError(error, sign); |
| } |
| |
| private SolverVariable createVariable(String name, SolverVariable.Type type) { |
| if (sMetrics != null) { |
| sMetrics.variables++; |
| } |
| if (mNumColumns + 1 >= mMaxColumns) { |
| increaseTableSize(); |
| } |
| SolverVariable variable = acquireSolverVariable(type, null); |
| variable.setName(name); |
| mVariablesID++; |
| mNumColumns++; |
| variable.id = mVariablesID; |
| if (mVariables == null) { |
| mVariables = new HashMap<>(); |
| } |
| mVariables.put(name, variable); |
| mCache.mIndexedVariables[mVariablesID] = variable; |
| return variable; |
| } |
| |
| public SolverVariable createErrorVariable(int strength, String prefix) { |
| if (sMetrics != null) { |
| sMetrics.errors++; |
| } |
| if (mNumColumns + 1 >= mMaxColumns) { |
| increaseTableSize(); |
| } |
| SolverVariable variable = acquireSolverVariable(SolverVariable.Type.ERROR, prefix); |
| mVariablesID++; |
| mNumColumns++; |
| variable.id = mVariablesID; |
| variable.strength = strength; |
| mCache.mIndexedVariables[mVariablesID] = variable; |
| mGoal.addError(variable); |
| return variable; |
| } |
| |
| /** |
| * Returns a SolverVariable instance of the given type |
| * @param type type of the SolverVariable |
| * @return instance of SolverVariable |
| */ |
| private SolverVariable acquireSolverVariable(SolverVariable.Type type, String prefix) { |
| SolverVariable variable = mCache.solverVariablePool.acquire(); |
| if (variable == null) { |
| variable = new SolverVariable(type, prefix); |
| variable.setType(type, prefix); |
| } else { |
| variable.reset(); |
| variable.setType(type, prefix); |
| } |
| if (mPoolVariablesCount >= POOL_SIZE) { |
| POOL_SIZE *= 2; |
| mPoolVariables = Arrays.copyOf(mPoolVariables, POOL_SIZE); |
| } |
| mPoolVariables[mPoolVariablesCount++] = variable; |
| return variable; |
| } |
| |
| /*--------------------------------------------------------------------------------------------*/ |
| // Accessors of rows / variables / errors |
| /*--------------------------------------------------------------------------------------------*/ |
| |
| /** |
| * Simple accessor for the current goal. Used when minimizing the system's goal. |
| * @return the current goal. |
| */ |
| Row getGoal() { return mGoal; } |
| |
| ArrayRow getRow(int n) { |
| return mRows[n]; |
| } |
| |
| float getValueFor(String name) { |
| SolverVariable v = getVariable(name, SolverVariable.Type.UNRESTRICTED); |
| if (v == null) { |
| return 0; |
| } |
| return v.computedValue; |
| } |
| |
| public int getObjectVariableValue(Object anchor) { |
| SolverVariable variable = ((ConstraintAnchor) anchor).getSolverVariable(); |
| if (variable != null) { |
| return (int) (variable.computedValue + 0.5f); |
| } |
| return 0; |
| } |
| |
| /** |
| * Returns a SolverVariable instance given a name and a type. |
| * |
| * @param name name of the variable |
| * @param type {@link SolverVariable.Type type} of the variable |
| * @return a SolverVariable instance |
| */ |
| SolverVariable getVariable(String name, SolverVariable.Type type) { |
| if (mVariables == null) { |
| mVariables = new HashMap<>(); |
| } |
| SolverVariable variable = mVariables.get(name); |
| if (variable == null) { |
| variable = createVariable(name, type); |
| } |
| return variable; |
| } |
| |
| /*--------------------------------------------------------------------------------------------*/ |
| // System resolution |
| /*--------------------------------------------------------------------------------------------*/ |
| |
| /** |
| * Minimize the current goal of the system. |
| */ |
| public void minimize() throws Exception { |
| if (sMetrics != null) { |
| sMetrics.minimize++; |
| } |
| if (DEBUG) { |
| System.out.println("\n*** MINIMIZE ***\n"); |
| } |
| if (graphOptimizer) { |
| if (sMetrics != null) { |
| sMetrics.graphOptimizer++; |
| } |
| boolean fullySolved = true; |
| for (int i = 0; i < mNumRows; i++) { |
| ArrayRow r = mRows[i]; |
| if (!r.isSimpleDefinition) { |
| fullySolved = false; |
| break; |
| } |
| } |
| if (!fullySolved) { |
| minimizeGoal(mGoal); |
| } else { |
| if (sMetrics != null) { |
| sMetrics.fullySolved++; |
| } |
| computeValues(); |
| } |
| } else { |
| minimizeGoal(mGoal); |
| } |
| if (DEBUG) { |
| System.out.println("\n*** END MINIMIZE ***\n"); |
| } |
| } |
| |
| /** |
| * Minimize the given goal with the current system. |
| * @param goal the goal to minimize. |
| */ |
| void minimizeGoal(Row goal) throws Exception { |
| if (sMetrics != null) { |
| sMetrics.minimizeGoal++; |
| sMetrics.maxVariables = Math.max(sMetrics.maxVariables, mNumColumns); |
| sMetrics.maxRows = Math.max(sMetrics.maxRows, mNumRows); |
| } |
| // First, let's make sure that the system is in Basic Feasible Solved Form (BFS), i.e. |
| // all the constants of the restricted variables should be positive. |
| if (DEBUG) { |
| System.out.println("minimize goal: " + goal); |
| } |
| updateRowFromVariables((ArrayRow) goal); |
| if (DEBUG) { |
| displayReadableRows(); |
| } |
| enforceBFS(goal); |
| if (DEBUG) { |
| System.out.println("Goal after enforcing BFS " + goal); |
| displayReadableRows(); |
| } |
| optimize(goal, false); |
| if (DEBUG) { |
| System.out.println("Goal after optimization " + goal); |
| displayReadableRows(); |
| } |
| computeValues(); |
| } |
| |
| /** |
| * Update the equation with the variables already defined in the system |
| * @param row row to update |
| */ |
| private final void updateRowFromVariables(ArrayRow row) { |
| if (mNumRows > 0) { |
| row.variables.updateFromSystem(row, mRows); |
| if (row.variables.currentSize == 0) { |
| row.isSimpleDefinition = true; |
| } |
| } |
| } |
| |
| /** |
| * Add the equation to the system |
| * @param row the equation we want to add expressed as a system row. |
| */ |
| public void addConstraint(ArrayRow row) { |
| if (row == null) { |
| return; |
| } |
| if (sMetrics != null) { |
| sMetrics.constraints++; |
| if (row.isSimpleDefinition) { |
| sMetrics.simpleconstraints++; |
| } |
| } |
| if (mNumRows + 1 >= mMaxRows || mNumColumns + 1 >= mMaxColumns) { |
| increaseTableSize(); |
| } |
| if (DEBUG) { |
| System.out.println("addConstraint <" + row.toReadableString() + ">"); |
| } |
| |
| boolean added = false; |
| if (!row.isSimpleDefinition) { |
| // Update the equation with the variables already defined in the system |
| updateRowFromVariables(row); |
| |
| if (row.isEmpty()) { |
| return; |
| } |
| |
| // First, ensure that if we have a constant it's positive |
| row.ensurePositiveConstant(); |
| |
| if (DEBUG) { |
| System.out.println("addConstraint, updated row : " + row.toReadableString()); |
| } |
| |
| // Then pick a good variable to use for the row |
| if (row.chooseSubject(this)) { |
| // extra variable added... let's try to see if we can remove it |
| SolverVariable extra = createExtraVariable(); |
| row.variable = extra; |
| addRow(row); |
| added = true; |
| mTempGoal.initFromRow(row); |
| optimize(mTempGoal, true); |
| if (extra.definitionId == -1) { |
| if (DEBUG) { |
| System.out.println("row added is 0, so get rid of it"); |
| } |
| if (row.variable == extra) { |
| // move extra to be parametric |
| SolverVariable pivotCandidate = row.pickPivot(extra); |
| if (pivotCandidate != null) { |
| if (sMetrics != null) { |
| sMetrics.pivots++; |
| } |
| row.pivot(pivotCandidate); |
| } |
| } |
| if (!row.isSimpleDefinition) { |
| row.variable.updateReferencesWithNewDefinition(row); |
| } |
| mNumRows--; |
| } |
| } |
| |
| if (!row.hasKeyVariable()) { |
| // Can happen if row resolves to nil |
| if (DEBUG) { |
| System.out.println("No variable found to pivot on " + row.toReadableString()); |
| displayReadableRows(); |
| } |
| return; |
| } |
| } |
| if (!added) { |
| addRow(row); |
| } |
| } |
| |
| private final void addRow(ArrayRow row) { |
| if (mRows[mNumRows] != null) { |
| mCache.arrayRowPool.release(mRows[mNumRows]); |
| } |
| mRows[mNumRows] = row; |
| row.variable.definitionId = mNumRows; |
| mNumRows++; |
| row.variable.updateReferencesWithNewDefinition(row); |
| |
| if (DEBUG) { |
| System.out.println("Row added, here is the system:"); |
| displayReadableRows(); |
| } |
| } |
| |
| /** |
| * Optimize the system given a goal to minimize. The system should be in BFS form. |
| * @param goal goal to optimize. |
| * @param b |
| * @return number of iterations. |
| */ |
| private final int optimize(Row goal, boolean b) { |
| if (sMetrics != null) { |
| sMetrics.optimize++; |
| } |
| boolean done = false; |
| int tries = 0; |
| for (int i = 0; i < mNumColumns; i++) { |
| mAlreadyTestedCandidates[i] = false; |
| } |
| |
| if (DEBUG) { |
| System.out.println("\n****************************"); |
| System.out.println("* OPTIMIZATION *"); |
| System.out.println("* mNumColumns: " + mNumColumns); |
| System.out.println("* GOAL: " + goal); |
| System.out.println("****************************\n"); |
| } |
| |
| while (!done) { |
| if (sMetrics != null) { |
| sMetrics.iterations++; |
| } |
| tries++; |
| if (DEBUG) { |
| System.out.println("\n******************************"); |
| System.out.println("* iteration: " + tries); |
| } |
| if (tries >= 2*mNumColumns) { |
| return tries; |
| } |
| |
| if (goal.getKey() != null) { |
| mAlreadyTestedCandidates[goal.getKey().id] = true; |
| } |
| SolverVariable pivotCandidate = goal.getPivotCandidate(this, mAlreadyTestedCandidates); |
| if (DEBUG) { |
| System.out.println("* Pivot candidate: " + pivotCandidate); |
| System.out.println("******************************\n"); |
| } |
| if (pivotCandidate != null) { |
| if (mAlreadyTestedCandidates[pivotCandidate.id]) { |
| return tries; |
| } else { |
| mAlreadyTestedCandidates[pivotCandidate.id] = true; |
| } |
| } |
| |
| if (pivotCandidate != null) { |
| if (DEBUG) { |
| System.out.println("valid pivot candidate: " + pivotCandidate); |
| } |
| // there's a negative variable in the goal that we can pivot on. |
| // We now need to select which equation of the system we should do |
| // the pivot on. |
| |
| // Let's try to find the equation in the system that we can pivot on. |
| // The rules are simple: |
| // - only look at restricted variables equations (i.e. Cs) |
| // - only look at equations containing the column we are trying to pivot on (duh) |
| // - select preferably an equation with strong strength over weak strength |
| |
| float min = Float.MAX_VALUE; |
| int pivotRowIndex = -1; |
| |
| for (int i = 0; i < mNumRows; i++) { |
| ArrayRow current = mRows[i]; |
| SolverVariable variable = current.variable; |
| if (variable.mType == SolverVariable.Type.UNRESTRICTED) { |
| // skip unrestricted variables equations (to only look at Cs) |
| continue; |
| } |
| if (current.isSimpleDefinition) { |
| continue; |
| } |
| |
| if (current.hasVariable(pivotCandidate)) { |
| if (DEBUG) { |
| System.out.println("equation " + i + " " + current + " contains " + pivotCandidate); |
| } |
| // the current row does contains the variable |
| // we want to pivot on |
| float a_j = current.variables.get(pivotCandidate); |
| if (a_j < 0) { |
| float value = - current.constantValue / a_j; |
| if (value < min) { |
| min = value; |
| pivotRowIndex = i; |
| } |
| } |
| } |
| } |
| // At this point, we ought to have an equation to pivot on |
| |
| if (pivotRowIndex > -1) { |
| // We found an equation to pivot on |
| if (DEBUG) { |
| System.out.println("We pivot on " + pivotRowIndex); |
| } |
| ArrayRow pivotEquation = mRows[pivotRowIndex]; |
| pivotEquation.variable.definitionId = -1; |
| if (sMetrics != null) { |
| sMetrics.pivots++; |
| } |
| pivotEquation.pivot(pivotCandidate); |
| pivotEquation.variable.definitionId = pivotRowIndex; |
| pivotEquation.variable.updateReferencesWithNewDefinition(pivotEquation); |
| if (DEBUG) { |
| System.out.println("new system after pivot:"); |
| displayReadableRows(); |
| System.out.println("optimizing: " + goal); |
| } |
| /* |
| try { |
| enforceBFS(goal); |
| } catch (Exception e) { |
| System.out.println("### EXCEPTION " + e); |
| e.printStackTrace(); |
| } |
| */ |
| // now that we pivoted, we're going to continue looping on the next goal |
| // columns, until we exhaust all the possibilities of improving the system |
| } else { |
| // System.out.println("we couldn't find an equation to pivot upon"); |
| // We couldn't find an equation to pivot, we should exit the loop. |
| done = true; |
| } |
| |
| } else { |
| // There is no candidate goals columns we should try to pivot on, |
| // so let's exit the loop. |
| done = true; |
| } |
| } |
| return tries; |
| } |
| |
| /** |
| * Make sure that the system is in Basic Feasible Solved form (BFS). |
| * @param goal the row representing the system goal |
| * @return number of iterations |
| */ |
| private int enforceBFS(Row goal) throws Exception { |
| int tries = 0; |
| boolean done; |
| |
| if (DEBUG) { |
| System.out.println("\n#################"); |
| System.out.println("# ENFORCING BFS #"); |
| System.out.println("#################\n"); |
| } |
| |
| // At this point, we might not be in Basic Feasible Solved form (BFS), |
| // i.e. one of the restricted equation has a negative constant. |
| // Let's check if that's the case or not. |
| boolean infeasibleSystem = false; |
| for (int i = 0; i < mNumRows; i++) { |
| SolverVariable variable = mRows[i].variable; |
| if (variable.mType == SolverVariable.Type.UNRESTRICTED) { |
| continue; // C can be either positive or negative. |
| } |
| if (mRows[i].constantValue < 0) { |
| infeasibleSystem = true; |
| break; |
| } |
| } |
| |
| // The system happens to not be in BFS form, we need to go back to it to properly solve it. |
| if (infeasibleSystem) { |
| if (DEBUG) { |
| System.out.println("the current system is infeasible, let's try to fix this."); |
| } |
| |
| // Going back to BFS form can be done by selecting any equations in Cs containing |
| // a negative constant, then selecting a potential pivot variable that would remove |
| // this negative constant. Once we have |
| done = false; |
| tries = 0; |
| while (!done) { |
| if (sMetrics != null) { |
| sMetrics.bfs++; |
| } |
| tries++; |
| if (DEBUG) { |
| System.out.println("iteration on infeasible system " + tries); |
| } |
| float min = Float.MAX_VALUE; |
| int strength = 0; |
| int pivotRowIndex = -1; |
| int pivotColumnIndex = -1; |
| |
| for (int i = 0; i < mNumRows; i++) { |
| ArrayRow current = mRows[i]; |
| SolverVariable variable = current.variable; |
| if (variable.mType == SolverVariable.Type.UNRESTRICTED) { |
| // skip unrestricted variables equations, as C |
| // can be either positive or negative. |
| continue; |
| } |
| if (current.isSimpleDefinition) { |
| continue; |
| } |
| if (current.constantValue < 0) { |
| // let's examine this row, see if we can find a good pivot |
| if (DEBUG) { |
| System.out.println("looking at pivoting on row " + current); |
| } |
| for (int j = 1; j < mNumColumns; j++) { |
| SolverVariable candidate = mCache.mIndexedVariables[j]; |
| float a_j = current.variables.get(candidate); |
| if (a_j <= 0) { |
| continue; |
| } |
| if (DEBUG) { |
| System.out.println("candidate for pivot " + candidate); |
| } |
| for (int k = 0; k < SolverVariable.MAX_STRENGTH; k++) { |
| float value = candidate.strengthVector[k] / a_j; |
| if (value < min && k == strength || k > strength) { |
| min = value; |
| pivotRowIndex = i; |
| pivotColumnIndex = j; |
| strength = k; |
| } |
| } |
| } |
| } |
| } |
| |
| if (pivotRowIndex != -1) { |
| // We have a pivot! |
| ArrayRow pivotEquation = mRows[pivotRowIndex]; |
| if (DEBUG) { |
| System.out.println("Pivoting on " + pivotEquation.variable + " with " |
| + mCache.mIndexedVariables[pivotColumnIndex]); |
| } |
| pivotEquation.variable.definitionId = -1; |
| if (sMetrics != null) { |
| sMetrics.pivots++; |
| } |
| pivotEquation.pivot(mCache.mIndexedVariables[pivotColumnIndex]); |
| pivotEquation.variable.definitionId = pivotRowIndex; |
| pivotEquation.variable.updateReferencesWithNewDefinition(pivotEquation); |
| |
| if (DEBUG) { |
| System.out.println("new goal after pivot: " + goal); |
| displayRows(); |
| } |
| } else { |
| done = true; |
| } |
| if (tries > mNumColumns / 2) { |
| // failsafe -- tried too many times |
| done = true; |
| } |
| } |
| } |
| |
| if (DEBUG) { |
| System.out.println("the current system should now be feasible [" + infeasibleSystem + "] after " + tries + " iterations"); |
| displayReadableRows(); |
| |
| // Let's make sure the system is correct |
| //noinspection UnusedAssignment |
| infeasibleSystem = false; |
| for (int i = 0; i < mNumRows; i++) { |
| SolverVariable variable = mRows[i].variable; |
| if (variable.mType == SolverVariable.Type.UNRESTRICTED) { |
| continue; // C can be either positive or negative. |
| } |
| if (mRows[i].constantValue < 0) { |
| //noinspection UnusedAssignment |
| infeasibleSystem = true; |
| break; |
| } |
| } |
| |
| if (DEBUG && infeasibleSystem) { |
| System.out.println("IMPOSSIBLE SYSTEM, WTF"); |
| throw new Exception(); |
| } |
| if (infeasibleSystem) { |
| return tries; |
| } |
| } |
| |
| return tries; |
| } |
| |
| private void computeValues() { |
| for (int i = 0; i < mNumRows; i++) { |
| ArrayRow row = mRows[i]; |
| row.variable.computedValue = row.constantValue; |
| } |
| } |
| |
| /*--------------------------------------------------------------------------------------------*/ |
| // Display utility functions |
| /*--------------------------------------------------------------------------------------------*/ |
| |
| @SuppressWarnings("unused") |
| private void displayRows() { |
| displaySolverVariables(); |
| String s = ""; |
| for (int i = 0; i < mNumRows; i++) { |
| s += mRows[i]; |
| s += "\n"; |
| } |
| s += mGoal + "\n"; |
| System.out.println(s); |
| } |
| |
| void displayReadableRows() { |
| displaySolverVariables(); |
| String s = " # "; |
| for (int i = 0; i < mNumRows; i++) { |
| s += mRows[i].toReadableString(); |
| s += "\n # "; |
| } |
| if (mGoal != null) { |
| s += mGoal + "\n"; |
| } |
| System.out.println(s); |
| } |
| |
| @SuppressWarnings("unused") |
| public void displayVariablesReadableRows() { |
| displaySolverVariables(); |
| String s = ""; |
| for (int i = 0; i < mNumRows; i++) { |
| if (mRows[i].variable.mType == SolverVariable.Type.UNRESTRICTED) { |
| s += mRows[i].toReadableString(); |
| s += "\n"; |
| } |
| } |
| s += mGoal + "\n"; |
| System.out.println(s); |
| } |
| |
| @SuppressWarnings("unused") |
| public int getMemoryUsed() { |
| int actualRowSize = 0; |
| for (int i = 0; i < mNumRows; i++) { |
| if (mRows[i] != null) { |
| actualRowSize += mRows[i].sizeInBytes(); |
| } |
| } |
| return actualRowSize; |
| } |
| |
| @SuppressWarnings("unused") |
| public int getNumEquations() { return mNumRows; } |
| @SuppressWarnings("unused") |
| public int getNumVariables() { return mVariablesID; } |
| |
| /** |
| * Display current system informations |
| */ |
| void displaySystemInformations() { |
| int count = 0; |
| int rowSize = 0; |
| for (int i = 0; i < TABLE_SIZE; i++) { |
| if (mRows[i] != null) { |
| rowSize += mRows[i].sizeInBytes(); |
| } |
| } |
| int actualRowSize = 0; |
| for (int i = 0; i < mNumRows; i++) { |
| if (mRows[i] != null) { |
| actualRowSize += mRows[i].sizeInBytes(); |
| } |
| } |
| |
| System.out.println("Linear System -> Table size: " + TABLE_SIZE |
| + " (" + getDisplaySize(TABLE_SIZE * TABLE_SIZE) |
| + ") -- row sizes: " + getDisplaySize(rowSize) |
| + ", actual size: " + getDisplaySize(actualRowSize) |
| + " rows: " + mNumRows + "/" + mMaxRows |
| + " cols: " + mNumColumns + "/" + mMaxColumns |
| + " " + count + " occupied cells, " + getDisplaySize(count) |
| ); |
| } |
| |
| private void displaySolverVariables() { |
| String s = "Display Rows (" + mNumRows + "x" + mNumColumns + ")\n"; |
| /* |
| s += ":\n\t | C | "; |
| for (int i = 1; i <= mNumColumns; i++) { |
| SolverVariable v = mCache.mIndexedVariables[i]; |
| s += v; |
| s += " | "; |
| } |
| s += "\n"; |
| */ |
| System.out.println(s); |
| } |
| |
| private String getDisplaySize(int n) { |
| int mb = (n * 4) / 1024 / 1024; |
| if (mb > 0) { |
| return "" + mb + " Mb"; |
| } |
| int kb = (n * 4) / 1024; |
| if (kb > 0) { |
| return "" + kb + " Kb"; |
| } |
| return "" + (n * 4) + " bytes"; |
| } |
| |
| public Cache getCache() { |
| return mCache; |
| } |
| |
| private String getDisplayStrength(int strength) { |
| if (strength == SolverVariable.STRENGTH_LOW) { |
| return "LOW"; |
| } |
| if (strength == SolverVariable.STRENGTH_MEDIUM) { |
| return "MEDIUM"; |
| } |
| if (strength == SolverVariable.STRENGTH_HIGH) { |
| return "HIGH"; |
| } |
| if (strength == SolverVariable.STRENGTH_HIGHEST) { |
| return "HIGHEST"; |
| } |
| if (strength == SolverVariable.STRENGTH_EQUALITY) { |
| return "EQUALITY"; |
| } |
| if (strength == SolverVariable.STRENGTH_FIXED) { |
| return "FIXED"; |
| } |
| return "NONE"; |
| } |
| |
| /** |
| * Add an equation of the form a >= b + margin |
| * @param a variable a |
| * @param b variable b |
| * @param margin margin |
| * @param strength strength used |
| */ |
| public void addGreaterThan(SolverVariable a, SolverVariable b, int margin, int strength) { |
| if (DEBUG) { |
| System.out.println("-> " + a + " >= " + b + (margin != 0 ? " + " + margin : "") + " " + getDisplayStrength(strength)); |
| } |
| ArrayRow row = createRow(); |
| SolverVariable slack = createSlackVariable(); |
| slack.strength = 0; |
| row.createRowGreaterThan(a, b, slack, margin); |
| if (strength != SolverVariable.STRENGTH_FIXED) { |
| float slackValue = row.variables.get(slack); |
| addSingleError(row, (int) (-1 * slackValue), strength); |
| } |
| addConstraint(row); |
| } |
| |
| public void addGreaterThan(SolverVariable a, int b) { |
| if (DEBUG) { |
| System.out.println("-> " + a + " >= " + b); |
| } |
| ArrayRow row = createRow(); |
| SolverVariable slack = createSlackVariable(); |
| slack.strength = 0; |
| row.createRowGreaterThan(a, b, slack); |
| addConstraint(row); |
| } |
| |
| public void addGreaterBarrier(SolverVariable a, SolverVariable b, boolean hasMatchConstraintWidgets) { |
| if (DEBUG) { |
| System.out.println("-> Barrier " + a + " >= " + b); |
| } |
| ArrayRow row = createRow(); |
| SolverVariable slack = createSlackVariable(); |
| slack.strength = SolverVariable.STRENGTH_NONE; |
| row.createRowGreaterThan(a, b, slack, 0); |
| if (hasMatchConstraintWidgets) { |
| // We set it to low, as constrained widgets (0d) will have a strength of low in default wrap |
| float slackValue = row.variables.get(slack); |
| addSingleError(row, (int) (-1 * slackValue), SolverVariable.STRENGTH_LOW); |
| } |
| addConstraint(row); |
| } |
| |
| /** |
| * Add an equation of the form a <= b + margin |
| * @param a variable a |
| * @param b variable b |
| * @param margin margin |
| * @param strength strength used |
| */ |
| public void addLowerThan(SolverVariable a, SolverVariable b, int margin, int strength) { |
| if (DEBUG) { |
| System.out.println("-> " + a + " <= " + b + (margin != 0 ? " + " + margin : "") + " " + getDisplayStrength(strength)); |
| } |
| ArrayRow row = createRow(); |
| SolverVariable slack = createSlackVariable(); |
| slack.strength = 0; |
| row.createRowLowerThan(a, b, slack, margin); |
| if (strength != SolverVariable.STRENGTH_FIXED) { |
| float slackValue = row.variables.get(slack); |
| addSingleError(row, (int) (-1 * slackValue), strength); |
| } |
| addConstraint(row); |
| } |
| |
| public void addLowerBarrier(SolverVariable a, SolverVariable b, boolean hasMatchConstraintWidgets) { |
| if (DEBUG) { |
| System.out.println("-> Barrier " + a + " <= " + b); |
| } |
| ArrayRow row = createRow(); |
| SolverVariable slack = createSlackVariable(); |
| slack.strength = SolverVariable.STRENGTH_NONE; |
| row.createRowLowerThan(a, b, slack, 0); |
| if (hasMatchConstraintWidgets) { |
| // We set it to low, as constrained widgets (0d) will have a strength of low in default wrap |
| float slackValue = row.variables.get(slack); |
| addSingleError(row, (int) (-1 * slackValue), SolverVariable.STRENGTH_LOW); |
| } |
| addConstraint(row); |
| } |
| |
| /** |
| * Add an equation of the form (1 - bias) * (a - b) = bias * (c - d) |
| * @param a variable a |
| * @param b variable b |
| * @param m1 margin 1 |
| * @param bias bias between ab - cd |
| * @param c variable c |
| * @param d variable d |
| * @param m2 margin 2 |
| * @param strength strength used |
| */ |
| public void addCentering(SolverVariable a, SolverVariable b, int m1, float bias, |
| SolverVariable c, SolverVariable d, int m2, int strength) { |
| if (DEBUG) { |
| System.out.println("-> [center bias: " + bias + "] : " + a + " - " + b |
| + " - " + m1 |
| + " = " + c + " - " + d + " - " + m2 |
| + " " + getDisplayStrength(strength)); |
| } |
| ArrayRow row = createRow(); |
| row.createRowCentering(a, b, m1, bias, c, d, m2); |
| if (strength != SolverVariable.STRENGTH_FIXED) { |
| row.addError(this, strength); |
| } |
| addConstraint(row); |
| } |
| |
| public void addRatio(SolverVariable a, SolverVariable b, SolverVariable c, SolverVariable d, float ratio, int strength) { |
| if (DEBUG) { |
| System.out.println("-> [ratio: " + ratio + "] : " + a + " = " + b + " + (" + c + " - " + d + ") * " + ratio + " " + getDisplayStrength(strength)); |
| } |
| ArrayRow row = createRow(); |
| row.createRowDimensionRatio(a, b, c, d, ratio); |
| if (strength != SolverVariable.STRENGTH_FIXED) { |
| row.addError(this, strength); |
| } |
| addConstraint(row); |
| } |
| /** |
| * Add an equation of the form a = b + margin |
| * @param a variable a |
| * @param b variable b |
| * @param margin margin used |
| * @param strength strength used |
| */ |
| public ArrayRow addEquality(SolverVariable a, SolverVariable b, int margin, int strength) { |
| if (DEBUG) { |
| System.out.println("-> " + a + " = " + b + (margin != 0 ? " + " + margin : "") + " " + getDisplayStrength(strength)); |
| } |
| ArrayRow row = createRow(); |
| row.createRowEquals(a, b, margin); |
| if (strength != SolverVariable.STRENGTH_FIXED) { |
| row.addError(this, strength); |
| } |
| addConstraint(row); |
| return row; |
| } |
| |
| /** |
| * Add an equation of the form a = value |
| * @param a variable a |
| * @param value the value we set |
| */ |
| public void addEquality(SolverVariable a, int value) { |
| if (DEBUG) { |
| System.out.println("-> " + a + " = " + value); |
| } |
| int idx = a.definitionId; |
| if (a.definitionId != -1) { |
| ArrayRow row = mRows[idx]; |
| if (row.isSimpleDefinition) { |
| row.constantValue = value; |
| } else { |
| if (row.variables.currentSize == 0) { |
| row.isSimpleDefinition = true; |
| row.constantValue = value; |
| } else { |
| ArrayRow newRow = createRow(); |
| newRow.createRowEquals(a, value); |
| addConstraint(newRow); |
| } |
| } |
| } else { |
| ArrayRow row = createRow(); |
| row.createRowDefinition(a, value); |
| addConstraint(row); |
| } |
| } |
| |
| |
| /** |
| * Add an equation of the form a = value |
| * @param a variable a |
| * @param value the value we set |
| */ |
| public void addEquality(SolverVariable a, int value, int strength) { |
| if (DEBUG) { |
| System.out.println("-> " + a + " = " + value + " " + getDisplayStrength(strength)); |
| } |
| int idx = a.definitionId; |
| if (a.definitionId != -1) { |
| ArrayRow row = mRows[idx]; |
| if (row.isSimpleDefinition) { |
| row.constantValue = value; |
| } else { |
| ArrayRow newRow = createRow(); |
| newRow.createRowEquals(a, value); |
| newRow.addError(this, strength); |
| addConstraint(newRow); |
| } |
| } else { |
| ArrayRow row = createRow(); |
| row.createRowDefinition(a, value); |
| row.addError(this, strength); |
| addConstraint(row); |
| } |
| } |
| |
| public static ArrayRow createRowEquals(LinearSystem linearSystem, SolverVariable variableA, |
| SolverVariable variableB, int margin, boolean withError) { |
| // expression is: variableA = variableB + margin |
| // we turn it into row = margin - variableA + variableB |
| ArrayRow row = linearSystem.createRow(); |
| row.createRowEquals(variableA, variableB, margin); |
| if (withError) { |
| linearSystem.addSingleError(row, 1); |
| if (DEBUG) { |
| System.out.println( |
| "Add " + variableA.getName() + " = " + variableB + " + " + margin + " + e"); |
| } |
| } else { |
| if (DEBUG) { |
| System.out |
| .println("Add " + variableA.getName() + " = " + variableB + " + " + margin); |
| } |
| } |
| return row; |
| } |
| |
| /** |
| * Create a constraint to express A = B + (C - B) * percent |
| * @param linearSystem the system we create the row on |
| * @param variableA variable a |
| * @param variableB variable b |
| * @param variableC variable c |
| * @param percent the percent used |
| * @return the created row |
| */ |
| public static ArrayRow createRowDimensionPercent(LinearSystem linearSystem, |
| SolverVariable variableA, |
| SolverVariable variableB, SolverVariable variableC, float percent, boolean withError) { |
| ArrayRow row = linearSystem.createRow(); |
| if (withError) { |
| linearSystem.addError(row); |
| } |
| return row.createRowDimensionPercent(variableA, variableB, variableC, percent); |
| } |
| |
| public static ArrayRow createRowGreaterThan(LinearSystem linearSystem, SolverVariable variableA, |
| SolverVariable variableB, int margin, boolean withError) { |
| // expression is: variableA >= variableB + margin |
| // we turn it into: variableA - slack = variableB + margin |
| // row = margin - variableA + variableB + slack |
| SolverVariable slack = linearSystem.createSlackVariable(); |
| ArrayRow row = linearSystem.createRow(); |
| row.createRowGreaterThan(variableA, variableB, slack, margin); |
| if (withError) { |
| float slackValue = row.variables.get(slack); |
| linearSystem.addSingleError(row, (int) (-1 * slackValue)); |
| if (DEBUG) { |
| System.out.println( |
| "Add " + variableA.getName() + " >= " + variableB.getName() + " + " + |
| margin + " + e"); |
| } |
| } else { |
| if (DEBUG) { |
| System.out.println( |
| "Add " + variableA.getName() + " >= " + variableB.getName() + " + " + |
| margin); |
| } |
| } |
| return row; |
| } |
| |
| public static ArrayRow createRowLowerThan(LinearSystem linearSystem, SolverVariable variableA, |
| SolverVariable variableB, int margin, boolean withError) { |
| // expression is: variableA <= variableB + margin |
| // we turn it into: variableA + slack = variableB + margin |
| // row = margin - variableA + variableB - slack |
| SolverVariable slack = linearSystem.createSlackVariable(); |
| ArrayRow row = linearSystem.createRow(); |
| row.createRowLowerThan(variableA, variableB, slack, margin); |
| if (withError) { |
| float slackValue = row.variables.get(slack); |
| linearSystem.addSingleError(row, (int) (-1 * slackValue)); |
| if (DEBUG) { |
| System.out.println( |
| "Add " + variableA.getName() + " <= " + variableB.getName() + " + " + |
| margin + " + e"); |
| } |
| } else { |
| if (DEBUG) { |
| System.out.println( |
| "Add " + variableA.getName() + " <= " + variableB.getName() + " + " + |
| margin); |
| } |
| } |
| return row; |
| } |
| |
| public static ArrayRow createRowCentering(LinearSystem linearSystem, |
| SolverVariable variableA, SolverVariable variableB, int marginA, |
| float bias, |
| SolverVariable variableC, SolverVariable variableD, int marginB, |
| boolean withError) { |
| // expression is: (1 - bias) * (variableA - variableB) = bias * (variableC - variableD) |
| // we turn it into: |
| // row = (1 - bias) * variableA - (1 - bias) * variableB - bias * variableC + bias * variableD |
| ArrayRow row = linearSystem.createRow(); |
| row.createRowCentering(variableA, variableB, marginA, bias, |
| variableC, variableD, marginB); |
| if (withError) { |
| row.addError(linearSystem, SolverVariable.STRENGTH_HIGHEST); |
| if (DEBUG) { |
| System.out.println( |
| "Add centering " + variableA.getName() + " - " + variableB.getName() + |
| " = " + variableC.getName() + " - " + variableD.getName() + |
| " +/- e"); |
| } |
| } else { |
| if (DEBUG) { |
| System.out.println( |
| "Add centering " + variableA.getName() + " - " + variableB.getName() + |
| " = " + variableC.getName() + " - " + variableD.getName()); |
| } |
| } |
| return row; |
| } |
| |
| /** |
| * Add the equations constraining a widget center to another widget center, positioned |
| * on a circle, following an angle and radius |
| * |
| * @param widget |
| * @param target |
| * @param angle from 0 to 360 |
| * @param radius the distance between the two centers |
| */ |
| public void addCenterPoint(ConstraintWidget widget, ConstraintWidget target, float angle, int radius) { |
| |
| SolverVariable Al = createObjectVariable(widget.getAnchor(ConstraintAnchor.Type.LEFT)); |
| SolverVariable At = createObjectVariable(widget.getAnchor(ConstraintAnchor.Type.TOP)); |
| SolverVariable Ar = createObjectVariable(widget.getAnchor(ConstraintAnchor.Type.RIGHT)); |
| SolverVariable Ab = createObjectVariable(widget.getAnchor(ConstraintAnchor.Type.BOTTOM)); |
| |
| SolverVariable Bl = createObjectVariable(target.getAnchor(ConstraintAnchor.Type.LEFT)); |
| SolverVariable Bt = createObjectVariable(target.getAnchor(ConstraintAnchor.Type.TOP)); |
| SolverVariable Br = createObjectVariable(target.getAnchor(ConstraintAnchor.Type.RIGHT)); |
| SolverVariable Bb = createObjectVariable(target.getAnchor(ConstraintAnchor.Type.BOTTOM)); |
| |
| ArrayRow row = createRow(); |
| float angleComponent = (float) (Math.sin(angle) * radius); |
| row.createRowWithAngle(At, Ab, Bt, Bb, angleComponent); |
| addConstraint(row); |
| row = createRow(); |
| angleComponent = (float) (Math.cos(angle) * radius); |
| row.createRowWithAngle(Al, Ar, Bl, Br, angleComponent); |
| addConstraint(row); |
| } |
| |
| } |
