/*
 * 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);
    }

}