content: /*
   * Copyright (C) 2015 The Android Open Source Project
   *
   * Licensed under the Apache License, Version 2.0 (the "License");
   * you may not use this file except in compliance with the License.
   * You may obtain a copy of the License at
   *
   *      http://www.apache.org/licenses/LICENSE-2.0
   *
   * Unless required by applicable law or agreed to in writing, software
   * distributed under the License is distributed on an "AS IS" BASIS,
   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   * See the License for the specific language governing permissions and
   * limitations under the License.
   */
  
  package androidx.constraintlayout.core;
  
  import static androidx.constraintlayout.core.SolverVariable.STRENGTH_EQUALITY;
  import static androidx.constraintlayout.core.SolverVariable.STRENGTH_HIGH;
  import static androidx.constraintlayout.core.SolverVariable.STRENGTH_HIGHEST;
  import static androidx.constraintlayout.core.SolverVariable.STRENGTH_LOW;
  import static androidx.constraintlayout.core.SolverVariable.STRENGTH_MEDIUM;
  
  import java.util.ArrayList;
  
  public class ArrayRow implements LinearSystem.Row {
      private static final boolean DEBUG = false;
  
      SolverVariable mVariable = null;
      float mConstantValue = 0;
      boolean mUsed = false;
      private static final boolean FULL_NEW_CHECK = false; // full validation (debug purposes)
  
      ArrayList<SolverVariable> mVariablesToUpdate = new ArrayList<>();
  
      public ArrayRowVariables variables;
  
      public interface ArrayRowVariables {
  
          // @TODO: add description
          int getCurrentSize();
  
          // @TODO: add description
          SolverVariable getVariable(int index);
  
          // @TODO: add description
          float getVariableValue(int index);
  
          // @TODO: add description
          float get(SolverVariable variable);
  
          // @TODO: add description
          int indexOf(SolverVariable variable);
  
          // @TODO: add description
          void display();
  
          // @TODO: add description
          void clear();
  
          // @TODO: add description
          boolean contains(SolverVariable variable);
  
          // @TODO: add description
          void put(SolverVariable variable, float value);
  
          // @TODO: add description
          int sizeInBytes();
  
          // @TODO: add description
          void invert();
  
          // @TODO: add description
          float remove(SolverVariable v, boolean removeFromDefinition);
  
          // @TODO: add description
          void divideByAmount(float amount);
  
          // @TODO: add description
          void add(SolverVariable v, float value, boolean removeFromDefinition);
  
          // @TODO: add description
          float use(ArrayRow definition, boolean removeFromDefinition);
      }
  
      boolean mIsSimpleDefinition = false;
  
      public ArrayRow() {
      }
  
      public ArrayRow(Cache cache) {
          variables = new ArrayLinkedVariables(this, cache);
          //variables = new OptimizedSolverVariableValues(this, cache);
      }
  
      boolean hasKeyVariable() {
          return !(
                  (mVariable == null)
                          || (mVariable.mType != SolverVariable.Type.UNRESTRICTED
                          && mConstantValue < 0)
          );
      }
  
      // @TODO: add description
      @Override
      public String toString() {
          return toReadableString();
      }
  
      String toReadableString() {
          String s = "";
          if (mVariable == null) {
              s += "0";
          } else {
              s += mVariable;
          }
          s += " = ";
          boolean addedVariable = false;
          if (mConstantValue != 0) {
              s += mConstantValue;
              addedVariable = true;
          }
          int count = variables.getCurrentSize();
          for (int i = 0; i < count; i++) {
              SolverVariable v = variables.getVariable(i);
              if (v == null) {
                  continue;
              }
              float amount = variables.getVariableValue(i);
              if (amount == 0) {
                  continue;
              }
              String name = v.toString();
              if (!addedVariable) {
                  if (amount < 0) {
                      s += "- ";
                      amount *= -1;
                  }
              } else {
                  if (amount > 0) {
                      s += " + ";
                  } else {
                      s += " - ";
                      amount *= -1;
                  }
              }
              if (amount == 1) {
                  s += name;
              } else {
                  s += amount + " " + name;
              }
              addedVariable = true;
          }
          if (!addedVariable) {
              s += "0.0";
          }
          if (DEBUG) {
              variables.display();
          }
          return s;
      }
  
      // @TODO: add description
      public void reset() {
          mVariable = null;
          variables.clear();
          mConstantValue = 0;
          mIsSimpleDefinition = false;
      }
  
      boolean hasVariable(SolverVariable v) {
          return variables.contains(v);
      }
  
      ArrayRow createRowDefinition(SolverVariable variable, int value) {
          this.mVariable = variable;
          variable.computedValue = value;
          mConstantValue = value;
          mIsSimpleDefinition = true;
          return this;
      }
  
      // @TODO: add description
      public ArrayRow createRowEquals(SolverVariable variable, int value) {
          if (value < 0) {
              mConstantValue = -1 * value;
              variables.put(variable, 1);
          } else {
              mConstantValue = value;
              variables.put(variable, -1);
          }
          return this;
      }
  
      // @TODO: add description
      public ArrayRow createRowEquals(SolverVariable variableA,
              SolverVariable variableB,
              int margin) {
          boolean inverse = false;
          if (margin != 0) {
              int m = margin;
              if (m < 0) {
                  m = -1 * m;
                  inverse = true;
              }
              mConstantValue = m;
          }
          if (!inverse) {
              variables.put(variableA, -1);
              variables.put(variableB, 1);
          } else {
              variables.put(variableA, 1);
              variables.put(variableB, -1);
          }
          return this;
      }
  
      // @TODO: add description
      ArrayRow addSingleError(SolverVariable error, int sign) {
          variables.put(error, (float) sign);
          return this;
      }
  
      // @TODO: add description
      public ArrayRow createRowGreaterThan(SolverVariable variableA,
              SolverVariable variableB, SolverVariable slack,
              int margin) {
          boolean inverse = false;
          if (margin != 0) {
              int m = margin;
              if (m < 0) {
                  m = -1 * m;
                  inverse = true;
              }
              mConstantValue = m;
          }
          if (!inverse) {
              variables.put(variableA, -1);
              variables.put(variableB, 1);
              variables.put(slack, 1);
          } else {
              variables.put(variableA, 1);
              variables.put(variableB, -1);
              variables.put(slack, -1);
          }
          return this;
      }
  
      // @TODO: add description
      public ArrayRow createRowGreaterThan(SolverVariable a, int b, SolverVariable slack) {
          mConstantValue = b;
          variables.put(a, -1);
          return this;
      }
  
      // @TODO: add description
      public ArrayRow createRowLowerThan(SolverVariable variableA, SolverVariable variableB,
              SolverVariable slack, int margin) {
          boolean inverse = false;
          if (margin != 0) {
              int m = margin;
              if (m < 0) {
                  m = -1 * m;
                  inverse = true;
              }
              mConstantValue = m;
          }
          if (!inverse) {
              variables.put(variableA, -1);
              variables.put(variableB, 1);
              variables.put(slack, -1);
          } else {
              variables.put(variableA, 1);
              variables.put(variableB, -1);
              variables.put(slack, 1);
          }
          return this;
      }
  
      // @TODO: add description
      public ArrayRow createRowEqualMatchDimensions(float currentWeight,
              float totalWeights, float nextWeight,
              SolverVariable variableStartA,
              SolverVariable variableEndA,
              SolverVariable variableStartB,
              SolverVariable variableEndB) {
          mConstantValue = 0;
          if (totalWeights == 0 || (currentWeight == nextWeight)) {
              // endA - startA == endB - startB
              // 0 = startA - endA + endB - startB
              variables.put(variableStartA, 1);
              variables.put(variableEndA, -1);
              variables.put(variableEndB, 1);
              variables.put(variableStartB, -1);
          } else {
              if (currentWeight == 0) {
                  variables.put(variableStartA, 1);
                  variables.put(variableEndA, -1);
              } else if (nextWeight == 0) {
                  variables.put(variableStartB, 1);
                  variables.put(variableEndB, -1);
              } else {
                  float cw = currentWeight / totalWeights;
                  float nw = nextWeight / totalWeights;
                  float w = cw / nw;
  
                  // endA - startA == w * (endB - startB)
                  // 0 = startA - endA + w * (endB - startB)
                  variables.put(variableStartA, 1);
                  variables.put(variableEndA, -1);
                  variables.put(variableEndB, w);
                  variables.put(variableStartB, -w);
              }
          }
          return this;
      }
  
      // @TODO: add description
      public ArrayRow createRowEqualDimension(float currentWeight,
              float totalWeights, float nextWeight,
              SolverVariable variableStartA, int marginStartA,
              SolverVariable variableEndA, int marginEndA,
              SolverVariable variableStartB, int marginStartB,
              SolverVariable variableEndB, int marginEndB) {
          if (totalWeights == 0 || (currentWeight == nextWeight)) {
              // endA - startA + marginStartA + marginEndA
              //      == endB - startB + marginStartB + marginEndB
              // 0 = startA - endA - marginStartA - marginEndA
              //      + endB - startB + marginStartB + marginEndB
              // 0 = (- marginStartA - marginEndA + marginStartB + marginEndB)
              //      + startA - endA + endB - startB
              mConstantValue = -marginStartA - marginEndA + marginStartB + marginEndB;
              variables.put(variableStartA, 1);
              variables.put(variableEndA, -1);
              variables.put(variableEndB, 1);
              variables.put(variableStartB, -1);
          } else {
              float cw = currentWeight / totalWeights;
              float nw = nextWeight / totalWeights;
              float w = cw / nw;
              // (endA - startA + marginStartA + marginEndA) =
              //      w * (endB - startB) + marginStartB + marginEndB;
              // 0 = (startA - endA - marginStartA - marginEndA)
              //      + w * (endB - startB) + marginStartB + marginEndB
              // 0 = (- marginStartA - marginEndA + marginStartB + marginEndB)
              //      + startA - endA + w * endB - w * startB
              mConstantValue = -marginStartA - marginEndA + w * marginStartB + w * marginEndB;
              variables.put(variableStartA, 1);
              variables.put(variableEndA, -1);
              variables.put(variableEndB, w);
              variables.put(variableStartB, -w);
          }
          return this;
      }
  
      ArrayRow createRowCentering(SolverVariable variableA, SolverVariable variableB,
              int marginA, float bias, SolverVariable variableC,
              SolverVariable variableD, int marginB) {
          if (variableB == variableC) {
              // centering on the same position
              // B - A == D - B
              // 0 = A + D - 2 * B
              variables.put(variableA, 1);
              variables.put(variableD, 1);
              variables.put(variableB, -2);
              return this;
          }
          if (bias == 0.5f) {
              // don't bother applying the bias, we are centered
              // A - B = C - D
              // 0 = A - B - C + D
              // with margin:
              // A - B - Ma = C - D - Mb
              // 0 = A - B - C + D - Ma + Mb
              variables.put(variableA, 1f);
              variables.put(variableB, -1f);
              variables.put(variableC, -1f);
              variables.put(variableD, 1f);
              if (marginA > 0 || marginB > 0) {
                  mConstantValue = -marginA + marginB;
              }
          } else if (bias <= 0) {
              // A = B + m
              variables.put(variableA, -1);
              variables.put(variableB, 1);
              mConstantValue = marginA;
          } else if (bias >= 1) {
              // D = C - m
              variables.put(variableD, -1);
              variables.put(variableC, 1);
              mConstantValue = -marginB;
          } else {
              variables.put(variableA, 1 * (1 - bias));
              variables.put(variableB, -1 * (1 - bias));
              variables.put(variableC, -1 * bias);
              variables.put(variableD, 1 * bias);
              if (marginA > 0 || marginB > 0) {
                  mConstantValue = -marginA * (1 - bias) + marginB * bias;
              }
          }
          return this;
      }
  
      // @TODO: add description
      public ArrayRow addError(LinearSystem system, int strength) {
          variables.put(system.createErrorVariable(strength, "ep"), 1);
          variables.put(system.createErrorVariable(strength, "em"), -1);
          return this;
      }
  
      ArrayRow createRowDimensionPercent(SolverVariable variableA,
              SolverVariable variableC, float percent) {
          variables.put(variableA, -1);
          variables.put(variableC, percent);
          return this;
      }
  
      /**
       * Create a constraint to express {@code A = B + (C - D)} * ratio
       * We use this for ratio, where for example {@code Right = Left + (Bottom - Top) * percent}
       *
       * @param variableA variable A
       * @param variableB variable B
       * @param variableC variable C
       * @param variableD variable D
       * @param ratio     ratio between AB and CD
       * @return the row
       */
      public ArrayRow createRowDimensionRatio(SolverVariable variableA, SolverVariable variableB,
              SolverVariable variableC, SolverVariable variableD,
              float ratio) {
          // A = B + (C - D) * ratio
          variables.put(variableA, -1);
          variables.put(variableB, 1);
          variables.put(variableC, ratio);
          variables.put(variableD, -ratio);
          return this;
      }
  
      /**
       * Create a constraint to express At + (Ab-At)/2 = Bt + (Bb-Bt)/2 - angle
       */
      public ArrayRow createRowWithAngle(SolverVariable at,
              SolverVariable ab,
              SolverVariable bt,
              SolverVariable bb,
              float angleComponent) {
          variables.put(bt, 0.5f);
          variables.put(bb, 0.5f);
          variables.put(at, -0.5f);
          variables.put(ab, -0.5f);
          mConstantValue = -angleComponent;
          return this;
      }
  
      int sizeInBytes() {
          int size = 0;
          if (mVariable != null) {
              size += 4; // object
          }
          size += 4; // constantValue
          size += 4; // used
  
          size += variables.sizeInBytes();
          return size;
      }
  
      void ensurePositiveConstant() {
          // Ensure that if we have a constant it's positive
          if (mConstantValue < 0) {
              // If not, simply multiply the equation by -1
              mConstantValue *= -1;
              variables.invert();
          }
      }
  
      /**
       * Pick a subject variable out of the existing ones.
       * - if a variable is unrestricted
       * - or if it's a negative new variable (not found elsewhere)
       * - otherwise we have to add a new additional variable
       *
       * @return true if we added an extra variable to the system
       */
      boolean chooseSubject(LinearSystem system) {
          boolean addedExtra = false;
          SolverVariable pivotCandidate = chooseSubjectInVariables(system);
          if (pivotCandidate == null) {
              // need to add extra variable
              addedExtra = true;
          } else {
              pivot(pivotCandidate);
          }
          if (variables.getCurrentSize() == 0) {
              mIsSimpleDefinition = true;
          }
          return addedExtra;
      }
  
      /**
       * Pick a subject variable out of the existing ones.
       * - if a variable is unrestricted
       * - or if it's a negative new variable (not found elsewhere)
       * - otherwise we return null
       *
       * @return a candidate variable we can pivot on or null if not found
       */
      SolverVariable chooseSubjectInVariables(LinearSystem system) {
          // if unrestricted, pick it
          // if restricted, needs to be < 0 and new
          //
          SolverVariable restrictedCandidate = null;
          SolverVariable unrestrictedCandidate = null;
          float unrestrictedCandidateAmount = 0;
          float restrictedCandidateAmount = 0;
          boolean unrestrictedCandidateIsNew = false;
          boolean restrictedCandidateIsNew = false;
  
          final int currentSize = variables.getCurrentSize();
          for (int i = 0; i < currentSize; i++) {
              float amount = variables.getVariableValue(i);
              SolverVariable variable = variables.getVariable(i);
              if (variable.mType == SolverVariable.Type.UNRESTRICTED) {
                  if (unrestrictedCandidate == null) {
                      unrestrictedCandidate = variable;
                      unrestrictedCandidateAmount = amount;
                      unrestrictedCandidateIsNew = isNew(variable, system);
                  } else if (unrestrictedCandidateAmount > amount) {
                      unrestrictedCandidate = variable;
                      unrestrictedCandidateAmount = amount;
                      unrestrictedCandidateIsNew = isNew(variable, system);
                  } else if (!unrestrictedCandidateIsNew && isNew(variable, system)) {
                      unrestrictedCandidate = variable;
                      unrestrictedCandidateAmount = amount;
                      unrestrictedCandidateIsNew = true;
                  }
              } else if (unrestrictedCandidate == null) {
                  if (amount < 0) {
                      if (restrictedCandidate == null) {
                          restrictedCandidate = variable;
                          restrictedCandidateAmount = amount;
                          restrictedCandidateIsNew = isNew(variable, system);
                      } else if (restrictedCandidateAmount > amount) {
                          restrictedCandidate = variable;
                          restrictedCandidateAmount = amount;
                          restrictedCandidateIsNew = isNew(variable, system);
                      } else if (!restrictedCandidateIsNew && isNew(variable, system)) {
                          restrictedCandidate = variable;
                          restrictedCandidateAmount = amount;
                          restrictedCandidateIsNew = true;
                      }
                  }
              }
          }
  
          if (unrestrictedCandidate != null) {
              return unrestrictedCandidate;
          }
          return restrictedCandidate;
      }
  
      /**
       * Returns true if the variable is new to the system, i.e. is already present
       * in one of the rows. This function is called while choosing the subject of a new row.
       *
       * @param variable the variable to check for
       * @param system   the linear system we check
       */
      private boolean isNew(SolverVariable variable, LinearSystem system) {
          if (FULL_NEW_CHECK) {
              boolean isNew = true;
              for (int i = 0; i < system.mNumRows; i++) {
                  ArrayRow row = system.mRows[i];
                  if (row.hasVariable(variable)) {
                      isNew = false;
                  }
              }
              if (variable.usageInRowCount <= 1 != isNew) {
                  System.out.println("Problem with usage tracking");
              }
              return isNew;
          }
          // We maintain a usage count -- variables are ref counted if they are present
          // in the right side of a row or not. If the count is zero or one, the variable
          // is new (if one, it means it exist in a row, but this is the row we insert)
          return variable.usageInRowCount <= 1;
      }
  
      void pivot(SolverVariable v) {
          if (mVariable != null) {
              // first, move back the variable to its column
              variables.put(mVariable, -1f);
              mVariable.mDefinitionId = -1;
              mVariable = null;
          }
  
          float amount = variables.remove(v, true) * -1;
          mVariable = v;
          if (amount == 1) {
              return;
          }
          mConstantValue = mConstantValue / amount;
          variables.divideByAmount(amount);
      }
  
      // Row compatibility
  
      @Override
      public boolean isEmpty() {
          return (mVariable == null && mConstantValue == 0 && variables.getCurrentSize() == 0);
      }
  
      @Override
      public void updateFromRow(LinearSystem system,
              ArrayRow definition,
              boolean removeFromDefinition) {
          float value = variables.use(definition, removeFromDefinition);
  
          mConstantValue += definition.mConstantValue * value;
          if (removeFromDefinition) {
              definition.mVariable.removeFromRow(this);
          }
          if (LinearSystem.SIMPLIFY_SYNONYMS
                  && mVariable != null && variables.getCurrentSize() == 0) {
              mIsSimpleDefinition = true;
              system.hasSimpleDefinition = true;
          }
      }
  
      // @TODO: add description
      @Override
      public void updateFromFinalVariable(LinearSystem system,
              SolverVariable variable,
              boolean removeFromDefinition) {
          if (variable == null || !variable.isFinalValue) {
              return;
          }
          float value = variables.get(variable);
          mConstantValue += variable.computedValue * value;
          variables.remove(variable, removeFromDefinition);
          if (removeFromDefinition) {
              variable.removeFromRow(this);
          }
          if (LinearSystem.SIMPLIFY_SYNONYMS
                  && variables.getCurrentSize() == 0) {
              mIsSimpleDefinition = true;
              system.hasSimpleDefinition = true;
          }
      }
  
      // @TODO: add description
      public void updateFromSynonymVariable(LinearSystem system,
              SolverVariable variable,
              boolean removeFromDefinition) {
          if (variable == null || !variable.mIsSynonym) {
              return;
          }
          float value = variables.get(variable);
          mConstantValue += variable.mSynonymDelta * value;
          variables.remove(variable, removeFromDefinition);
          if (removeFromDefinition) {
              variable.removeFromRow(this);
          }
          variables.add(system.mCache.mIndexedVariables[variable.mSynonym],
                  value, removeFromDefinition);
          if (LinearSystem.SIMPLIFY_SYNONYMS
                  && variables.getCurrentSize() == 0) {
              mIsSimpleDefinition = true;
              system.hasSimpleDefinition = true;
          }
      }
  
      private SolverVariable pickPivotInVariables(boolean[] avoid, SolverVariable exclude) {
          boolean all = true;
          float value = 0;
          SolverVariable pivot = null;
          SolverVariable pivotSlack = null;
          float valueSlack = 0;
  
          final int currentSize = variables.getCurrentSize();
          for (int i = 0; i < currentSize; i++) {
              float currentValue = variables.getVariableValue(i);
              if (currentValue < 0) {
                  // We can return the first negative candidate as in ArrayLinkedVariables
                  // they are already sorted by id
                  SolverVariable v = variables.getVariable(i);
                  if (!((avoid != null && avoid[v.id]) || (v == exclude))) {
                      if (all) {
                          if (v.mType == SolverVariable.Type.SLACK
                                  || v.mType == SolverVariable.Type.ERROR) {
                              if (currentValue < value) {
                                  value = currentValue;
                                  pivot = v;
                              }
                          }
                      } else {
                          if (v.mType == SolverVariable.Type.SLACK) {
                              if (currentValue < valueSlack) {
                                  valueSlack = currentValue;
                                  pivotSlack = v;
                              }
                          } else if (v.mType == SolverVariable.Type.ERROR) {
                              if (currentValue < value) {
                                  value = currentValue;
                                  pivot = v;
                              }
                          }
                      }
                  }
              }
          }
          if (all) {
              return pivot;
          }
          return pivot != null ? pivot : pivotSlack;
      }
  
      // @TODO: add description
      public SolverVariable pickPivot(SolverVariable exclude) {
          return pickPivotInVariables(null, exclude);
      }
  
      @Override
      public SolverVariable getPivotCandidate(LinearSystem system, boolean[] avoid) {
          return pickPivotInVariables(avoid, null);
      }
  
      @Override
      public void clear() {
          variables.clear();
          mVariable = null;
          mConstantValue = 0;
      }
  
      /**
       * Used to initiate a goal from a given row (to see if we can remove an extra var)
       */
      @Override
      public void initFromRow(@SuppressWarnings("HiddenTypeParameter") LinearSystem.Row row) {
          if (row instanceof ArrayRow) {
              ArrayRow copiedRow = (ArrayRow) row;
              mVariable = null;
              variables.clear();
              for (int i = 0; i < copiedRow.variables.getCurrentSize(); i++) {
                  SolverVariable var = copiedRow.variables.getVariable(i);
                  float val = copiedRow.variables.getVariableValue(i);
                  variables.add(var, val, true);
              }
          }
      }
  
      @Override
      public void addError(SolverVariable error) {
          float weight = 1;
          if (error.strength == STRENGTH_LOW) {
              weight = 1F;
          } else if (error.strength == STRENGTH_MEDIUM) {
              weight = 1E3F;
          } else if (error.strength == STRENGTH_HIGH) {
              weight = 1E6F;
          } else if (error.strength == STRENGTH_HIGHEST) {
              weight = 1E9F;
          } else if (error.strength == STRENGTH_EQUALITY) {
              weight = 1E12F;
          }
          variables.put(error, weight);
      }
  
      @Override
      public SolverVariable getKey() {
          return mVariable;
      }
  
      @Override
      public void updateFromSystem(LinearSystem system) {
          if (system.mRows.length == 0) {
              return;
          }
  
          boolean done = false;
          while (!done) {
              int currentSize = variables.getCurrentSize();
              for (int i = 0; i < currentSize; i++) {
                  SolverVariable variable = variables.getVariable(i);
                  if (variable.mDefinitionId != -1 || variable.isFinalValue || variable.mIsSynonym) {
                      mVariablesToUpdate.add(variable);
                  }
              }
              final int size = mVariablesToUpdate.size();
              if (size > 0) {
                  for (int i = 0; i < size; i++) {
                      SolverVariable variable = mVariablesToUpdate.get(i);
                      if (variable.isFinalValue) {
                          updateFromFinalVariable(system, variable, true);
                      } else if (variable.mIsSynonym) {
                          updateFromSynonymVariable(system, variable, true);
                      } else {
                          updateFromRow(system, system.mRows[variable.mDefinitionId], true);
                      }
                  }
                  mVariablesToUpdate.clear();
              } else {
                  done = true;
              }
          }
          if (LinearSystem.SIMPLIFY_SYNONYMS
                  && mVariable != null && variables.getCurrentSize() == 0) {
              mIsSimpleDefinition = true;
              system.hasSimpleDefinition = true;
          }
      }
  }
  