/*
* 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 androidx.constraintlayout.core.widgets.Chain;
import androidx.constraintlayout.core.widgets.ConstraintAnchor;
import androidx.constraintlayout.core.widgets.ConstraintWidget;
import java.util.Arrays;
import java.util.HashMap;
/**
* Represents and solves a system of linear equations.
*/
public class LinearSystem {
public static final boolean FULL_DEBUG = false;
public static final boolean DEBUG = false;
private static final boolean DO_NOT_USE = false;
public static final boolean MEASURE = false;
private static final boolean DEBUG_CONSTRAINTS = FULL_DEBUG;
public static boolean USE_DEPENDENCY_ORDERING = false;
public static boolean USE_BASIC_SYNONYMS = true;
public static boolean SIMPLIFY_SYNONYMS = true;
public static boolean USE_SYNONYMS = true;
public static boolean SKIP_COLUMNS = true;
public static boolean OPTIMIZED_ENGINE = false;
/*
* Default size for the object pools
*/
private static int sPoolSize = 1000;
public boolean hasSimpleDefinition = false;
/*
* 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 mTableSize = 32; // default table size for the allocation
private int mMaxColumns = mTableSize;
ArrayRow[] mRows = null;
// if true, will use graph optimizations
public boolean graphOptimizer = false;
public boolean newgraphOptimizer = false;
// Used in optimize()
private boolean[] mAlreadyTestedCandidates = new boolean[mTableSize];
int mNumColumns = 1;
int mNumRows = 0;
private int mMaxRows = mTableSize;
final Cache mCache;
private SolverVariable[] mPoolVariables = new SolverVariable[sPoolSize];
private int mPoolVariablesCount = 0;
public static Metrics sMetrics;
private Row mTempGoal;
class ValuesRow extends ArrayRow {
ValuesRow(Cache cache) {
variables = new SolverVariableValues(this, cache);
}
}
public LinearSystem() {
mRows = new ArrayRow[mTableSize];
releaseRows();
mCache = new Cache();
mGoal = new PriorityGoalRow(mCache);
if (OPTIMIZED_ENGINE) {
mTempGoal = new ValuesRow(mCache);
} else {
mTempGoal = new ArrayRow(mCache);
}
}
/**
* @TODO: add description
*/
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);
void updateFromSystem(LinearSystem system);
SolverVariable getKey();
boolean isEmpty();
void updateFromRow(LinearSystem system, ArrayRow definition, boolean b);
void updateFromFinalVariable(LinearSystem system,
SolverVariable variable,
boolean removeFromDefinition);
}
/*--------------------------------------------------------------------------------------------*/
// Memory management
/*--------------------------------------------------------------------------------------------*/
/**
* Reallocate memory to accommodate increased amount of variables
*/
private void increaseTableSize() {
if (DEBUG) {
System.out.println("###########################");
System.out.println("### INCREASE TABLE TO " + (mTableSize * 2) + " (num rows: "
+ mNumRows + ", num cols: " + mNumColumns + "/" + mMaxColumns + ")");
System.out.println("###########################");
}
mTableSize *= 2;
mRows = Arrays.copyOf(mRows, mTableSize);
mCache.mIndexedVariables = Arrays.copyOf(mCache.mIndexedVariables, mTableSize);
mAlreadyTestedCandidates = new boolean[mTableSize];
mMaxColumns = mTableSize;
mMaxRows = mTableSize;
if (sMetrics != null) {
sMetrics.tableSizeIncrease++;
sMetrics.maxTableSize = Math.max(sMetrics.maxTableSize, mTableSize);
sMetrics.lastTableSize = sMetrics.maxTableSize;
}
}
/**
* Release ArrayRows back to their pool
*/
private void releaseRows() {
if (OPTIMIZED_ENGINE) {
for (int i = 0; i < mNumRows; i++) {
ArrayRow row = mRows[i];
if (row != null) {
mCache.mOptimizedArrayRowPool.release(row);
}
mRows[i] = null;
}
} else {
for (int i = 0; i < mNumRows; i++) {
ArrayRow row = mRows[i];
if (row != null) {
mCache.mArrayRowPool.release(row);
}
mRows[i] = null;
}
}
}
/**
* Reset the LinearSystem object so that it can be reused.
*/
public void reset() {
if (DEBUG) {
System.out.println("##################");
System.out.println("## RESET SYSTEM ##");
System.out.println("##################");
}
for (int i = 0; i < mCache.mIndexedVariables.length; i++) {
SolverVariable variable = mCache.mIndexedVariables[i];
if (variable != null) {
variable.reset();
}
}
mCache.mSolverVariablePool.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++) {
if (mRows[i] != null) {
mRows[i].mUsed = false;
}
}
releaseRows();
mNumRows = 0;
if (OPTIMIZED_ENGINE) {
mTempGoal = new ValuesRow(mCache);
} else {
mTempGoal = new ArrayRow(mCache);
}
}
/*--------------------------------------------------------------------------------------------*/
// Creation of rows / variables / errors
/*--------------------------------------------------------------------------------------------*/
/**
* @TODO: add description
*/
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 static long ARRAY_ROW_CREATION = 0;
public static long OPTIMIZED_ARRAY_ROW_CREATION = 0;
/**
* @TODO: add description
*/
public ArrayRow createRow() {
ArrayRow row;
if (OPTIMIZED_ENGINE) {
row = mCache.mOptimizedArrayRowPool.acquire();
if (row == null) {
row = new ValuesRow(mCache);
OPTIMIZED_ARRAY_ROW_CREATION++;
} else {
row.reset();
}
} else {
row = mCache.mArrayRowPool.acquire();
if (row == null) {
row = new ArrayRow(mCache);
ARRAY_ROW_CREATION++;
} else {
row.reset();
}
}
SolverVariable.increaseErrorId();
return row;
}
/**
* @TODO: add description
*/
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;
}
/**
* @TODO: add description
*/
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;
}
/**
* @TODO: add description
*/
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.mSolverVariablePool.acquire();
if (variable == null) {
variable = new SolverVariable(type, prefix);
variable.setType(type, prefix);
} else {
variable.reset();
variable.setType(type, prefix);
}
if (mPoolVariablesCount >= sPoolSize) {
sPoolSize *= 2;
mPoolVariables = Arrays.copyOf(mPoolVariables, sPoolSize);
}
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;
}
/**
* @TODO: add description
*/
public int getObjectVariableValue(Object object) {
ConstraintAnchor anchor = (ConstraintAnchor) object;
if (Chain.USE_CHAIN_OPTIMIZATION) {
if (anchor.hasFinalValue()) {
return anchor.getFinalValue();
}
}
SolverVariable variable = 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 (mGoal.isEmpty()) {
if (DEBUG) {
System.out.println("\n*** SKIPPING MINIMIZE! ***\n");
}
computeValues();
return;
}
if (DEBUG) {
System.out.println("\n*** MINIMIZE ***\n");
}
if (graphOptimizer || newgraphOptimizer) {
if (sMetrics != null) {
sMetrics.graphOptimizer++;
}
boolean fullySolved = true;
for (int i = 0; i < mNumRows; i++) {
ArrayRow r = mRows[i];
if (!r.mIsSimpleDefinition) {
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);
}
// we don't need this for now as we incrementally built the system
// goal.updateFromSystem(this);
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();
}
final void cleanupRows() {
int i = 0;
while (i < mNumRows) {
ArrayRow current = mRows[i];
if (current.variables.getCurrentSize() == 0) {
current.mIsSimpleDefinition = true;
}
if (current.mIsSimpleDefinition) {
current.mVariable.computedValue = current.mConstantValue;
current.mVariable.removeFromRow(current);
for (int j = i; j < mNumRows - 1; j++) {
mRows[j] = mRows[j + 1];
}
mRows[mNumRows - 1] = null;
mNumRows--;
i--;
if (OPTIMIZED_ENGINE) {
mCache.mOptimizedArrayRowPool.release(current);
} else {
mCache.mArrayRowPool.release(current);
}
}
i++;
}
}
/**
* 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.mIsSimpleDefinition) {
sMetrics.simpleconstraints++;
}
}
if (mNumRows + 1 >= mMaxRows || mNumColumns + 1 >= mMaxColumns) {
increaseTableSize();
}
if (DEBUG) {
System.out.println("addConstraint <" + row.toReadableString() + ">");
displayReadableRows();
}
boolean added = false;
if (!row.mIsSimpleDefinition) {
// Update the equation with the variables already defined in the system
row.updateFromSystem(this);
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.mVariable = extra;
int numRows = mNumRows;
addRow(row);
if (mNumRows == numRows + 1) {
added = true;
mTempGoal.initFromRow(row);
optimize(mTempGoal, true);
if (extra.mDefinitionId == -1) {
if (DEBUG) {
System.out.println("row added is 0, so get rid of it");
}
if (row.mVariable == extra) {
// move extra to be parametric
SolverVariable pivotCandidate = row.pickPivot(extra);
if (pivotCandidate != null) {
if (sMetrics != null) {
sMetrics.pivots++;
}
row.pivot(pivotCandidate);
}
}
if (!row.mIsSimpleDefinition) {
row.mVariable.updateReferencesWithNewDefinition(this, row);
}
if (OPTIMIZED_ENGINE) {
mCache.mOptimizedArrayRowPool.release(row);
} else {
mCache.mArrayRowPool.release(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 void addRow(ArrayRow row) {
if (SIMPLIFY_SYNONYMS && row.mIsSimpleDefinition) {
row.mVariable.setFinalValue(this, row.mConstantValue);
} else {
mRows[mNumRows] = row;
row.mVariable.mDefinitionId = mNumRows;
mNumRows++;
row.mVariable.updateReferencesWithNewDefinition(this, row);
}
if (DEBUG) {
System.out.println("Row added: " + row);
System.out.println("here is the system:");
displayReadableRows();
}
if (SIMPLIFY_SYNONYMS && hasSimpleDefinition) {
// compact the rows...
for (int i = 0; i < mNumRows; i++) {
if (mRows[i] == null) {
System.out.println("WTF");
}
if (mRows[i] != null && mRows[i].mIsSimpleDefinition) {
ArrayRow removedRow = mRows[i];
removedRow.mVariable.setFinalValue(this, removedRow.mConstantValue);
if (OPTIMIZED_ENGINE) {
mCache.mOptimizedArrayRowPool.release(removedRow);
} else {
mCache.mArrayRowPool.release(removedRow);
}
mRows[i] = null;
int lastRow = i + 1;
for (int j = i + 1; j < mNumRows; j++) {
mRows[j - 1] = mRows[j];
if (mRows[j - 1].mVariable.mDefinitionId == j) {
mRows[j - 1].mVariable.mDefinitionId = j - 1;
}
lastRow = j;
}
if (lastRow < mNumRows) {
mRows[lastRow] = null;
}
mNumRows--;
i--;
}
}
hasSimpleDefinition = false;
}
}
/**
* @TODO: add description
*/
public void removeRow(ArrayRow row) {
if (row.mIsSimpleDefinition && row.mVariable != null) {
if (row.mVariable.mDefinitionId != -1) {
for (int i = row.mVariable.mDefinitionId; i < mNumRows - 1; i++) {
SolverVariable rowVariable = mRows[i + 1].mVariable;
if (rowVariable.mDefinitionId == i + 1) {
rowVariable.mDefinitionId = i;
}
mRows[i] = mRows[i + 1];
}
mNumRows--;
}
if (!row.mVariable.isFinalValue) {
row.mVariable.setFinalValue(this, row.mConstantValue);
}
if (OPTIMIZED_ENGINE) {
mCache.mOptimizedArrayRowPool.release(row);
} else {
mCache.mArrayRowPool.release(row);
}
}
}
/**
* Optimize the system given a goal to minimize. The system should be in BFS form.
*
* @param goal goal to optimize.
* @return number of iterations.
*/
private 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) {
if (DEBUG) {
System.out.println("=> Exit optimization because tries "
+ 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]) {
if (DEBUG) {
System.out.println("* Pivot candidate " + pivotCandidate
+ " already tested, let's bail");
}
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.mVariable;
if (variable.mType == SolverVariable.Type.UNRESTRICTED) {
// skip unrestricted variables equations (to only look at Cs)
continue;
}
if (current.mIsSimpleDefinition) {
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.mConstantValue / 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.mVariable.mDefinitionId = -1;
if (sMetrics != null) {
sMetrics.pivots++;
}
pivotEquation.pivot(pivotCandidate);
pivotEquation.mVariable.mDefinitionId = pivotRowIndex;
pivotEquation.mVariable.updateReferencesWithNewDefinition(this, 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 {
if (DEBUG) {
System.out.println("we couldn't find an equation to pivot upon");
}
}
} else {
// There is no candidate goals columns we should try to pivot on,
// so let's exit the loop.
if (DEBUG) {
System.out.println("no more candidate goals to pivot on, let's exit");
}
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].mVariable;
if (variable.mType == SolverVariable.Type.UNRESTRICTED) {
continue; // C can be either positive or negative.
}
if (mRows[i].mConstantValue < 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.mVariable;
if (variable.mType == SolverVariable.Type.UNRESTRICTED) {
// skip unrestricted variables equations, as C
// can be either positive or negative.
continue;
}
if (current.mIsSimpleDefinition) {
continue;
}
if (current.mConstantValue < 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);
}
if (SKIP_COLUMNS) {
final int size = current.variables.getCurrentSize();
for (int j = 0; j < size; j++) {
SolverVariable candidate = current.variables.getVariable(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.mStrengthVector[k] / a_j;
if ((value < min && k == strength) || k > strength) {
min = value;
pivotRowIndex = i;
pivotColumnIndex = candidate.id;
strength = k;
}
}
}
} else {
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.mStrengthVector[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.mVariable + " with "
+ mCache.mIndexedVariables[pivotColumnIndex]);
}
pivotEquation.mVariable.mDefinitionId = -1;
if (sMetrics != null) {
sMetrics.pivots++;
}
pivotEquation.pivot(mCache.mIndexedVariables[pivotColumnIndex]);
pivotEquation.mVariable.mDefinitionId = pivotRowIndex;
pivotEquation.mVariable.updateReferencesWithNewDefinition(this, pivotEquation);
if (DEBUG) {
System.out.println("new goal after pivot: " + goal);
displayRows();
}
} else {
done = true;
}
if (tries > mNumColumns / 2) {
// fail safe -- 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].mVariable;
if (variable.mType == SolverVariable.Type.UNRESTRICTED) {
continue; // C can be either positive or negative.
}
if (mRows[i].mConstantValue < 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.mVariable.computedValue = row.mConstantValue;
}
}
/*--------------------------------------------------------------------------------------------*/
// 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);
}
/**
* @TODO: add description
*/
public void displayReadableRows() {
displaySolverVariables();
String s = " num vars " + mVariablesID + "\n";
for (int i = 0; i < mVariablesID + 1; i++) {
SolverVariable variable = mCache.mIndexedVariables[i];
if (variable != null && variable.isFinalValue) {
s += " $[" + i + "] => " + variable + " = " + variable.computedValue + "\n";
}
}
s += "\n";
for (int i = 0; i < mVariablesID + 1; i++) {
SolverVariable variable = mCache.mIndexedVariables[i];
if (variable != null && variable.mIsSynonym) {
SolverVariable synonym = mCache.mIndexedVariables[variable.mSynonym];
s += " ~[" + i + "] => " + variable + " = "
+ synonym + " + " + variable.mSynonymDelta + "\n";
}
}
s += "\n\n # ";
for (int i = 0; i < mNumRows; i++) {
s += mRows[i].toReadableString();
s += "\n # ";
}
if (mGoal != null) {
s += "Goal: " + mGoal + "\n";
}
System.out.println(s);
}
/**
* @TODO: add description
*/
@SuppressWarnings("unused")
public void displayVariablesReadableRows() {
displaySolverVariables();
String s = "";
for (int i = 0; i < mNumRows; i++) {
if (mRows[i].mVariable.mType == SolverVariable.Type.UNRESTRICTED) {
s += mRows[i].toReadableString();
s += "\n";
}
}
s += mGoal + "\n";
System.out.println(s);
}
/**
* @TODO: add description
*/
@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 information
*/
void displaySystemInformation() {
int count = 0;
int rowSize = 0;
for (int i = 0; i < mTableSize; 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: " + mTableSize
+ " (" + getDisplaySize(mTableSize * mTableSize)
+ ") -- 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";
}
if (strength == SolverVariable.STRENGTH_BARRIER) {
return "BARRIER";
}
return "NONE";
}
////////////////////////////////////////////////////////////////////////////////////////
// Equations
////////////////////////////////////////////////////////////////////////////////////////
/**
* 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_CONSTRAINTS) {
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);
}
/**
* @TODO: add description
*/
public void addGreaterBarrier(SolverVariable a,
SolverVariable b,
int margin,
boolean hasMatchConstraintWidgets) {
if (DEBUG_CONSTRAINTS) {
System.out.println("-> Barrier " + a + " >= " + b);
}
ArrayRow row = createRow();
SolverVariable slack = createSlackVariable();
slack.strength = 0;
row.createRowGreaterThan(a, b, slack, margin);
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_CONSTRAINTS) {
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);
}
/**
* @TODO: add description
*/
public void addLowerBarrier(SolverVariable a,
SolverVariable b,
int margin,
boolean hasMatchConstraintWidgets) {
if (DEBUG_CONSTRAINTS) {
System.out.println("-> Barrier " + a + " <= " + b);
}
ArrayRow row = createRow();
SolverVariable slack = createSlackVariable();
slack.strength = 0;
row.createRowLowerThan(a, b, slack, margin);
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_CONSTRAINTS) {
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);
}
/**
* @TODO: add description
*/
public void addRatio(SolverVariable a,
SolverVariable b,
SolverVariable c,
SolverVariable d,
float ratio,
int strength) {
if (DEBUG_CONSTRAINTS) {
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);
}
/**
* @TODO: add description
*/
public void addSynonym(SolverVariable a, SolverVariable b, int margin) {
if (a.mDefinitionId == -1 && margin == 0) {
if (DEBUG_CONSTRAINTS) {
System.out.println("(S) -> " + a + " = " + b + (margin != 0 ? " + " + margin : ""));
}
if (b.mIsSynonym) {
margin += b.mSynonymDelta;
b = mCache.mIndexedVariables[b.mSynonym];
}
if (a.mIsSynonym) {
margin -= a.mSynonymDelta;
a = mCache.mIndexedVariables[a.mSynonym];
} else {
a.setSynonym(this, b, 0);
}
} else {
addEquality(a, b, margin, SolverVariable.STRENGTH_FIXED);
}
}
/**
* 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 (USE_BASIC_SYNONYMS && strength == SolverVariable.STRENGTH_FIXED
&& b.isFinalValue && a.mDefinitionId == -1) {
if (DEBUG_CONSTRAINTS) {
System.out.println("=> " + a + " = " + b + (margin != 0 ? " + " + margin : "")
+ " = " + (b.computedValue + margin) + " (Synonym)");
}
a.setFinalValue(this, b.computedValue + margin);
return null;
}
if (DO_NOT_USE && USE_SYNONYMS && strength == SolverVariable.STRENGTH_FIXED
&& a.mDefinitionId == -1 && margin == 0) {
if (DEBUG_CONSTRAINTS) {
System.out.println("(S) -> " + a + " = " + b + (margin != 0 ? " + " + margin : "")
+ " " + getDisplayStrength(strength));
}
if (b.mIsSynonym) {
margin += b.mSynonymDelta;
b = mCache.mIndexedVariables[b.mSynonym];
}
if (a.mIsSynonym) {
margin -= a.mSynonymDelta;
a = mCache.mIndexedVariables[a.mSynonym];
} else {
a.setSynonym(this, b, margin);
return null;
}
}
if (DEBUG_CONSTRAINTS) {
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 (USE_BASIC_SYNONYMS && a.mDefinitionId == -1) {
if (DEBUG_CONSTRAINTS) {
System.out.println("=> " + a + " = " + value + " (Synonym)");
}
a.setFinalValue(this, value);
for (int i = 0; i < mVariablesID + 1; i++) {
SolverVariable variable = mCache.mIndexedVariables[i];
if (variable != null && variable.mIsSynonym && variable.mSynonym == a.id) {
variable.setFinalValue(this, value + variable.mSynonymDelta);
}
}
return;
}
if (DEBUG_CONSTRAINTS) {
System.out.println("-> " + a + " = " + value);
}
int idx = a.mDefinitionId;
if (a.mDefinitionId != -1) {
ArrayRow row = mRows[idx];
if (row.mIsSimpleDefinition) {
row.mConstantValue = value;
} else {
if (row.variables.getCurrentSize() == 0) {
row.mIsSimpleDefinition = true;
row.mConstantValue = value;
} else {
ArrayRow newRow = createRow();
newRow.createRowEquals(a, value);
addConstraint(newRow);
}
}
} else {
ArrayRow row = createRow();
row.createRowDefinition(a, value);
addConstraint(row);
}
}
/**
* Create a constraint to express A = C * percent
*
* @param linearSystem the system we create the row on
* @param variableA variable a
* @param variableC variable c
* @param percent the percent used
* @return the created row
*/
public static ArrayRow createRowDimensionPercent(LinearSystem linearSystem,
SolverVariable variableA,
SolverVariable variableC,
float percent) {
if (DEBUG_CONSTRAINTS) {
System.out.println("-> " + variableA + " = " + variableC + " * " + percent);
}
ArrayRow row = linearSystem.createRow();
return row.createRowDimensionPercent(variableA, variableC, percent);
}
/**
* Add the equations constraining a widget center to another widget center, positioned
* on a circle, following an angle and radius
*
* @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);
}
}