1 /* 2 * Copyright (C) 2015 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 package androidx.constraintlayout.core; 18 19 import androidx.constraintlayout.core.widgets.Chain; 20 import androidx.constraintlayout.core.widgets.ConstraintAnchor; 21 import androidx.constraintlayout.core.widgets.ConstraintWidget; 22 23 import java.util.Arrays; 24 import java.util.HashMap; 25 26 /** 27 * Represents and solves a system of linear equations. 28 */ 29 public class LinearSystem { 30 31 public static final boolean FULL_DEBUG = false; 32 public static final boolean DEBUG = false; 33 private static final boolean DO_NOT_USE = false; 34 35 private static final boolean DEBUG_CONSTRAINTS = FULL_DEBUG; 36 37 public static boolean USE_DEPENDENCY_ORDERING = false; 38 public static boolean USE_BASIC_SYNONYMS = true; 39 public static boolean SIMPLIFY_SYNONYMS = true; 40 public static boolean USE_SYNONYMS = true; 41 public static boolean SKIP_COLUMNS = true; 42 public static boolean OPTIMIZED_ENGINE = false; 43 44 /* 45 * Default size for the object pools 46 */ 47 private int mPoolSize = 1000; 48 public boolean hasSimpleDefinition = false; 49 50 /* 51 * Variable counter 52 */ 53 int mVariablesID = 0; 54 55 /* 56 * Store a map between name->SolverVariable and SolverVariable->Float for the resolution. 57 */ 58 private HashMap<String, SolverVariable> mVariables = null; 59 60 /* 61 * The goal that is used when minimizing the system. 62 */ 63 private Row mGoal; 64 65 private int mTableSize = 32; // default table size for the allocation 66 private int mMaxColumns = mTableSize; 67 ArrayRow[] mRows = null; 68 69 // if true, will use graph optimizations 70 public boolean graphOptimizer = false; 71 public boolean newgraphOptimizer = false; 72 73 // Used in optimize() 74 private boolean[] mAlreadyTestedCandidates = new boolean[mTableSize]; 75 76 int mNumColumns = 1; 77 int mNumRows = 0; 78 private int mMaxRows = mTableSize; 79 80 final Cache mCache; 81 82 private SolverVariable[] mPoolVariables = new SolverVariable[mPoolSize]; 83 private int mPoolVariablesCount = 0; 84 85 public static Metrics sMetrics; 86 private Row mTempGoal; 87 88 static class ValuesRow extends ArrayRow { ValuesRow(Cache cache)89 ValuesRow(Cache cache) { 90 variables = new SolverVariableValues(this, cache); 91 } 92 } 93 LinearSystem()94 public LinearSystem() { 95 mRows = new ArrayRow[mTableSize]; 96 releaseRows(); 97 mCache = new Cache(); 98 mGoal = new PriorityGoalRow(mCache); 99 if (OPTIMIZED_ENGINE) { 100 mTempGoal = new ValuesRow(mCache); 101 } else { 102 mTempGoal = new ArrayRow(mCache); 103 } 104 } 105 106 // @TODO: add description fillMetrics(Metrics metrics)107 public void fillMetrics(Metrics metrics) { 108 sMetrics = metrics; 109 } 110 getMetrics()111 public static Metrics getMetrics() { 112 return sMetrics; 113 } 114 115 interface Row { getPivotCandidate(LinearSystem system, boolean[] avoid)116 SolverVariable getPivotCandidate(LinearSystem system, boolean[] avoid); 117 clear()118 void clear(); 119 initFromRow(Row row)120 void initFromRow(Row row); 121 addError(SolverVariable variable)122 void addError(SolverVariable variable); 123 updateFromSystem(LinearSystem system)124 void updateFromSystem(LinearSystem system); 125 getKey()126 SolverVariable getKey(); 127 isEmpty()128 boolean isEmpty(); 129 updateFromRow(LinearSystem system, ArrayRow definition, boolean b)130 void updateFromRow(LinearSystem system, ArrayRow definition, boolean b); 131 updateFromFinalVariable(LinearSystem system, SolverVariable variable, boolean removeFromDefinition)132 void updateFromFinalVariable(LinearSystem system, 133 SolverVariable variable, 134 boolean removeFromDefinition); 135 } 136 137 /*--------------------------------------------------------------------------------------------*/ 138 // Memory management 139 /*--------------------------------------------------------------------------------------------*/ 140 141 /** 142 * Reallocate memory to accommodate increased amount of variables 143 */ increaseTableSize()144 private void increaseTableSize() { 145 if (DEBUG) { 146 System.out.println("###########################"); 147 System.out.println("### INCREASE TABLE TO " + (mTableSize * 2) + " (num rows: " 148 + mNumRows + ", num cols: " + mNumColumns + "/" + mMaxColumns + ")"); 149 System.out.println("###########################"); 150 } 151 mTableSize *= 2; 152 mRows = Arrays.copyOf(mRows, mTableSize); 153 mCache.mIndexedVariables = Arrays.copyOf(mCache.mIndexedVariables, mTableSize); 154 mAlreadyTestedCandidates = new boolean[mTableSize]; 155 mMaxColumns = mTableSize; 156 mMaxRows = mTableSize; 157 if (sMetrics != null) { 158 sMetrics.tableSizeIncrease++; 159 sMetrics.maxTableSize = Math.max(sMetrics.maxTableSize, mTableSize); 160 sMetrics.lastTableSize = sMetrics.maxTableSize; 161 } 162 } 163 164 /** 165 * Release ArrayRows back to their pool 166 */ releaseRows()167 private void releaseRows() { 168 if (OPTIMIZED_ENGINE) { 169 for (int i = 0; i < mNumRows; i++) { 170 ArrayRow row = mRows[i]; 171 if (row != null) { 172 mCache.mOptimizedArrayRowPool.release(row); 173 } 174 mRows[i] = null; 175 } 176 } else { 177 for (int i = 0; i < mNumRows; i++) { 178 ArrayRow row = mRows[i]; 179 if (row != null) { 180 mCache.mArrayRowPool.release(row); 181 } 182 mRows[i] = null; 183 } 184 } 185 } 186 187 /** 188 * Reset the LinearSystem object so that it can be reused. 189 */ reset()190 public void reset() { 191 if (DEBUG) { 192 System.out.println("##################"); 193 System.out.println("## RESET SYSTEM ##"); 194 System.out.println("##################"); 195 } 196 for (int i = 0; i < mCache.mIndexedVariables.length; i++) { 197 SolverVariable variable = mCache.mIndexedVariables[i]; 198 if (variable != null) { 199 variable.reset(); 200 } 201 } 202 mCache.mSolverVariablePool.releaseAll(mPoolVariables, mPoolVariablesCount); 203 mPoolVariablesCount = 0; 204 205 Arrays.fill(mCache.mIndexedVariables, null); 206 if (mVariables != null) { 207 mVariables.clear(); 208 } 209 mVariablesID = 0; 210 mGoal.clear(); 211 mNumColumns = 1; 212 for (int i = 0; i < mNumRows; i++) { 213 if (mRows[i] != null) { 214 mRows[i].mUsed = false; 215 } 216 } 217 releaseRows(); 218 mNumRows = 0; 219 if (OPTIMIZED_ENGINE) { 220 mTempGoal = new ValuesRow(mCache); 221 } else { 222 mTempGoal = new ArrayRow(mCache); 223 } 224 } 225 226 /*--------------------------------------------------------------------------------------------*/ 227 // Creation of rows / variables / errors 228 /*--------------------------------------------------------------------------------------------*/ 229 230 // @TODO: add description createObjectVariable(Object anchor)231 public SolverVariable createObjectVariable(Object anchor) { 232 if (anchor == null) { 233 return null; 234 } 235 if (mNumColumns + 1 >= mMaxColumns) { 236 increaseTableSize(); 237 } 238 SolverVariable variable = null; 239 if (anchor instanceof ConstraintAnchor) { 240 variable = ((ConstraintAnchor) anchor).getSolverVariable(); 241 if (variable == null) { 242 ((ConstraintAnchor) anchor).resetSolverVariable(mCache); 243 variable = ((ConstraintAnchor) anchor).getSolverVariable(); 244 } 245 if (variable.id == -1 246 || variable.id > mVariablesID 247 || mCache.mIndexedVariables[variable.id] == null) { 248 if (variable.id != -1) { 249 variable.reset(); 250 } 251 mVariablesID++; 252 mNumColumns++; 253 variable.id = mVariablesID; 254 variable.mType = SolverVariable.Type.UNRESTRICTED; 255 mCache.mIndexedVariables[mVariablesID] = variable; 256 } 257 } 258 return variable; 259 } 260 261 public static long ARRAY_ROW_CREATION = 0; 262 public static long OPTIMIZED_ARRAY_ROW_CREATION = 0; 263 264 // @TODO: add description createRow()265 public ArrayRow createRow() { 266 ArrayRow row; 267 if (OPTIMIZED_ENGINE) { 268 row = mCache.mOptimizedArrayRowPool.acquire(); 269 if (row == null) { 270 row = new ValuesRow(mCache); 271 OPTIMIZED_ARRAY_ROW_CREATION++; 272 } else { 273 row.reset(); 274 } 275 } else { 276 row = mCache.mArrayRowPool.acquire(); 277 if (row == null) { 278 row = new ArrayRow(mCache); 279 ARRAY_ROW_CREATION++; 280 } else { 281 row.reset(); 282 } 283 } 284 SolverVariable.increaseErrorId(); 285 return row; 286 } 287 288 // @TODO: add description createSlackVariable()289 public SolverVariable createSlackVariable() { 290 if (sMetrics != null) { 291 sMetrics.slackvariables++; 292 } 293 if (mNumColumns + 1 >= mMaxColumns) { 294 increaseTableSize(); 295 } 296 SolverVariable variable = acquireSolverVariable(SolverVariable.Type.SLACK, null); 297 mVariablesID++; 298 mNumColumns++; 299 variable.id = mVariablesID; 300 mCache.mIndexedVariables[mVariablesID] = variable; 301 return variable; 302 } 303 304 // @TODO: add description createExtraVariable()305 public SolverVariable createExtraVariable() { 306 if (sMetrics != null) { 307 sMetrics.extravariables++; 308 } 309 if (mNumColumns + 1 >= mMaxColumns) { 310 increaseTableSize(); 311 } 312 SolverVariable variable = acquireSolverVariable(SolverVariable.Type.SLACK, null); 313 mVariablesID++; 314 mNumColumns++; 315 variable.id = mVariablesID; 316 mCache.mIndexedVariables[mVariablesID] = variable; 317 return variable; 318 } 319 320 // private void addError(ArrayRow row) 321 // row.addError(this, SolverVariable.STRENGTH_NONE); 322 // 323 // 324 // private void addSingleError(ArrayRow row, int sign) 325 // addSingleError(row, sign, SolverVariable.STRENGTH_NONE); 326 // 327 addSingleError(ArrayRow row, int sign, int strength)328 void addSingleError(ArrayRow row, int sign, int strength) { 329 String prefix = null; 330 if (DEBUG) { 331 if (sign > 0) { 332 prefix = "ep"; 333 } else { 334 prefix = "em"; 335 } 336 prefix = "em"; 337 } 338 SolverVariable error = createErrorVariable(strength, prefix); 339 row.addSingleError(error, sign); 340 } 341 createVariable(String name, SolverVariable.Type type)342 private SolverVariable createVariable(String name, SolverVariable.Type type) { 343 if (sMetrics != null) { 344 sMetrics.variables++; 345 } 346 if (mNumColumns + 1 >= mMaxColumns) { 347 increaseTableSize(); 348 } 349 SolverVariable variable = acquireSolverVariable(type, null); 350 variable.setName(name); 351 mVariablesID++; 352 mNumColumns++; 353 variable.id = mVariablesID; 354 if (mVariables == null) { 355 mVariables = new HashMap<>(); 356 } 357 mVariables.put(name, variable); 358 mCache.mIndexedVariables[mVariablesID] = variable; 359 return variable; 360 } 361 362 // @TODO: add description createErrorVariable(int strength, String prefix)363 public SolverVariable createErrorVariable(int strength, String prefix) { 364 if (sMetrics != null) { 365 sMetrics.errors++; 366 } 367 if (mNumColumns + 1 >= mMaxColumns) { 368 increaseTableSize(); 369 } 370 SolverVariable variable = acquireSolverVariable(SolverVariable.Type.ERROR, prefix); 371 mVariablesID++; 372 mNumColumns++; 373 variable.id = mVariablesID; 374 variable.strength = strength; 375 mCache.mIndexedVariables[mVariablesID] = variable; 376 mGoal.addError(variable); 377 return variable; 378 } 379 380 /** 381 * Returns a SolverVariable instance of the given type 382 * 383 * @param type type of the SolverVariable 384 * @return instance of SolverVariable 385 */ acquireSolverVariable(SolverVariable.Type type, String prefix)386 private SolverVariable acquireSolverVariable(SolverVariable.Type type, String prefix) { 387 SolverVariable variable = mCache.mSolverVariablePool.acquire(); 388 if (variable == null) { 389 variable = new SolverVariable(type, prefix); 390 variable.setType(type, prefix); 391 } else { 392 variable.reset(); 393 variable.setType(type, prefix); 394 } 395 if (mPoolVariablesCount >= mPoolSize) { 396 mPoolSize *= 2; 397 mPoolVariables = Arrays.copyOf(mPoolVariables, mPoolSize); 398 } 399 mPoolVariables[mPoolVariablesCount++] = variable; 400 return variable; 401 } 402 403 /*--------------------------------------------------------------------------------------------*/ 404 // Accessors of rows / variables / errors 405 /*--------------------------------------------------------------------------------------------*/ 406 407 /** 408 * Simple accessor for the current goal. Used when minimizing the system's goal. 409 * 410 * @return the current goal. 411 */ getGoal()412 Row getGoal() { 413 return mGoal; 414 } 415 getRow(int n)416 ArrayRow getRow(int n) { 417 return mRows[n]; 418 } 419 getValueFor(String name)420 float getValueFor(String name) { 421 SolverVariable v = getVariable(name, SolverVariable.Type.UNRESTRICTED); 422 if (v == null) { 423 return 0; 424 } 425 return v.computedValue; 426 } 427 428 // @TODO: add description getObjectVariableValue(Object object)429 public int getObjectVariableValue(Object object) { 430 ConstraintAnchor anchor = (ConstraintAnchor) object; 431 if (Chain.USE_CHAIN_OPTIMIZATION) { 432 if (anchor.hasFinalValue()) { 433 return anchor.getFinalValue(); 434 } 435 } 436 SolverVariable variable = anchor.getSolverVariable(); 437 if (variable != null) { 438 return (int) (variable.computedValue + 0.5f); 439 } 440 return 0; 441 } 442 443 /** 444 * Returns a SolverVariable instance given a name and a type. 445 * 446 * @param name name of the variable 447 * @param type {@link SolverVariable.Type type} of the variable 448 * @return a SolverVariable instance 449 */ getVariable(String name, SolverVariable.Type type)450 SolverVariable getVariable(String name, SolverVariable.Type type) { 451 if (mVariables == null) { 452 mVariables = new HashMap<>(); 453 } 454 SolverVariable variable = mVariables.get(name); 455 if (variable == null) { 456 variable = createVariable(name, type); 457 } 458 return variable; 459 } 460 461 /*--------------------------------------------------------------------------------------------*/ 462 // System resolution 463 /*--------------------------------------------------------------------------------------------*/ 464 465 /** 466 * Minimize the current goal of the system. 467 */ minimize()468 public void minimize() throws Exception { 469 if (sMetrics != null) { 470 sMetrics.minimize++; 471 } 472 if (mGoal.isEmpty()) { 473 if (DEBUG) { 474 System.out.println("\n*** SKIPPING MINIMIZE! ***\n"); 475 } 476 computeValues(); 477 return; 478 } 479 if (DEBUG) { 480 System.out.println("\n*** MINIMIZE ***\n"); 481 } 482 if (graphOptimizer || newgraphOptimizer) { 483 if (sMetrics != null) { 484 sMetrics.graphOptimizer++; 485 } 486 boolean fullySolved = true; 487 for (int i = 0; i < mNumRows; i++) { 488 ArrayRow r = mRows[i]; 489 if (!r.mIsSimpleDefinition) { 490 fullySolved = false; 491 break; 492 } 493 } 494 if (!fullySolved) { 495 minimizeGoal(mGoal); 496 } else { 497 if (sMetrics != null) { 498 sMetrics.fullySolved++; 499 } 500 computeValues(); 501 } 502 } else { 503 minimizeGoal(mGoal); 504 } 505 if (DEBUG) { 506 System.out.println("\n*** END MINIMIZE ***\n"); 507 } 508 } 509 510 /** 511 * Minimize the given goal with the current system. 512 * 513 * @param goal the goal to minimize. 514 */ minimizeGoal(Row goal)515 void minimizeGoal(Row goal) throws Exception { 516 if (sMetrics != null) { 517 sMetrics.minimizeGoal++; 518 sMetrics.maxVariables = Math.max(sMetrics.maxVariables, mNumColumns); 519 sMetrics.maxRows = Math.max(sMetrics.maxRows, mNumRows); 520 } 521 // First, let's make sure that the system is in Basic Feasible Solved Form (BFS), i.e. 522 // all the constants of the restricted variables should be positive. 523 if (DEBUG) { 524 System.out.println("minimize goal: " + goal); 525 } 526 // we don't need this for now as we incrementally built the system 527 // goal.updateFromSystem(this); 528 if (DEBUG) { 529 displayReadableRows(); 530 } 531 enforceBFS(goal); 532 if (DEBUG) { 533 System.out.println("Goal after enforcing BFS " + goal); 534 displayReadableRows(); 535 } 536 optimize(goal, false); 537 if (DEBUG) { 538 System.out.println("Goal after optimization " + goal); 539 displayReadableRows(); 540 } 541 computeValues(); 542 } 543 cleanupRows()544 final void cleanupRows() { 545 int i = 0; 546 while (i < mNumRows) { 547 ArrayRow current = mRows[i]; 548 if (current.variables.getCurrentSize() == 0) { 549 current.mIsSimpleDefinition = true; 550 } 551 if (current.mIsSimpleDefinition) { 552 current.mVariable.computedValue = current.mConstantValue; 553 current.mVariable.removeFromRow(current); 554 for (int j = i; j < mNumRows - 1; j++) { 555 mRows[j] = mRows[j + 1]; 556 } 557 mRows[mNumRows - 1] = null; 558 mNumRows--; 559 i--; 560 if (OPTIMIZED_ENGINE) { 561 mCache.mOptimizedArrayRowPool.release(current); 562 } else { 563 mCache.mArrayRowPool.release(current); 564 } 565 } 566 i++; 567 } 568 } 569 570 /** 571 * Add the equation to the system 572 * 573 * @param row the equation we want to add expressed as a system row. 574 */ addConstraint(ArrayRow row)575 public void addConstraint(ArrayRow row) { 576 if (row == null) { 577 return; 578 } 579 if (sMetrics != null) { 580 sMetrics.constraints++; 581 if (row.mIsSimpleDefinition) { 582 sMetrics.simpleconstraints++; 583 } 584 } 585 if (mNumRows + 1 >= mMaxRows || mNumColumns + 1 >= mMaxColumns) { 586 increaseTableSize(); 587 } 588 if (DEBUG) { 589 System.out.println("addConstraint <" + row.toReadableString() + ">"); 590 displayReadableRows(); 591 } 592 593 boolean added = false; 594 if (!row.mIsSimpleDefinition) { 595 // Update the equation with the variables already defined in the system 596 row.updateFromSystem(this); 597 598 if (row.isEmpty()) { 599 return; 600 } 601 602 // First, ensure that if we have a constant it's positive 603 row.ensurePositiveConstant(); 604 605 if (DEBUG) { 606 System.out.println("addConstraint, updated row : " + row.toReadableString()); 607 } 608 609 // Then pick a good variable to use for the row 610 if (row.chooseSubject(this)) { 611 // extra variable added... let's try to see if we can remove it 612 SolverVariable extra = createExtraVariable(); 613 row.mVariable = extra; 614 int numRows = mNumRows; 615 addRow(row); 616 if (mNumRows == numRows + 1) { 617 added = true; 618 mTempGoal.initFromRow(row); 619 optimize(mTempGoal, true); 620 if (extra.mDefinitionId == -1) { 621 if (DEBUG) { 622 System.out.println("row added is 0, so get rid of it"); 623 } 624 if (row.mVariable == extra) { 625 // move extra to be parametric 626 SolverVariable pivotCandidate = row.pickPivot(extra); 627 if (pivotCandidate != null) { 628 if (sMetrics != null) { 629 sMetrics.pivots++; 630 } 631 row.pivot(pivotCandidate); 632 } 633 } 634 if (!row.mIsSimpleDefinition) { 635 row.mVariable.updateReferencesWithNewDefinition(this, row); 636 } 637 if (OPTIMIZED_ENGINE) { 638 mCache.mOptimizedArrayRowPool.release(row); 639 } else { 640 mCache.mArrayRowPool.release(row); 641 } 642 mNumRows--; 643 } 644 } 645 } 646 647 if (!row.hasKeyVariable()) { 648 // Can happen if row resolves to nil 649 if (DEBUG) { 650 System.out.println("No variable found to pivot on " + row.toReadableString()); 651 displayReadableRows(); 652 } 653 return; 654 } 655 } 656 if (!added) { 657 addRow(row); 658 } 659 } 660 addRow(ArrayRow row)661 private void addRow(ArrayRow row) { 662 if (SIMPLIFY_SYNONYMS && row.mIsSimpleDefinition) { 663 row.mVariable.setFinalValue(this, row.mConstantValue); 664 } else { 665 mRows[mNumRows] = row; 666 row.mVariable.mDefinitionId = mNumRows; 667 mNumRows++; 668 row.mVariable.updateReferencesWithNewDefinition(this, row); 669 } 670 if (DEBUG) { 671 System.out.println("Row added: " + row); 672 System.out.println("here is the system:"); 673 displayReadableRows(); 674 } 675 if (SIMPLIFY_SYNONYMS && hasSimpleDefinition) { 676 // compact the rows... 677 for (int i = 0; i < mNumRows; i++) { 678 if (mRows[i] == null) { 679 System.out.println("WTF"); 680 } 681 if (mRows[i] != null && mRows[i].mIsSimpleDefinition) { 682 ArrayRow removedRow = mRows[i]; 683 removedRow.mVariable.setFinalValue(this, removedRow.mConstantValue); 684 if (OPTIMIZED_ENGINE) { 685 mCache.mOptimizedArrayRowPool.release(removedRow); 686 } else { 687 mCache.mArrayRowPool.release(removedRow); 688 } 689 mRows[i] = null; 690 int lastRow = i + 1; 691 for (int j = i + 1; j < mNumRows; j++) { 692 mRows[j - 1] = mRows[j]; 693 if (mRows[j - 1].mVariable.mDefinitionId == j) { 694 mRows[j - 1].mVariable.mDefinitionId = j - 1; 695 } 696 lastRow = j; 697 } 698 if (lastRow < mNumRows) { 699 mRows[lastRow] = null; 700 } 701 mNumRows--; 702 i--; 703 } 704 } 705 hasSimpleDefinition = false; 706 } 707 } 708 709 // @TODO: add description removeRow(ArrayRow row)710 public void removeRow(ArrayRow row) { 711 if (row.mIsSimpleDefinition && row.mVariable != null) { 712 if (row.mVariable.mDefinitionId != -1) { 713 for (int i = row.mVariable.mDefinitionId; i < mNumRows - 1; i++) { 714 SolverVariable rowVariable = mRows[i + 1].mVariable; 715 if (rowVariable.mDefinitionId == i + 1) { 716 rowVariable.mDefinitionId = i; 717 } 718 mRows[i] = mRows[i + 1]; 719 } 720 mNumRows--; 721 } 722 if (!row.mVariable.isFinalValue) { 723 row.mVariable.setFinalValue(this, row.mConstantValue); 724 } 725 if (OPTIMIZED_ENGINE) { 726 mCache.mOptimizedArrayRowPool.release(row); 727 } else { 728 mCache.mArrayRowPool.release(row); 729 } 730 } 731 } 732 733 /** 734 * Optimize the system given a goal to minimize. The system should be in BFS form. 735 * 736 * @param goal goal to optimize. 737 * @return number of iterations. 738 */ optimize(Row goal, boolean b)739 private int optimize(Row goal, boolean b) { 740 if (sMetrics != null) { 741 sMetrics.optimize++; 742 } 743 boolean done = false; 744 int tries = 0; 745 for (int i = 0; i < mNumColumns; i++) { 746 mAlreadyTestedCandidates[i] = false; 747 } 748 749 if (DEBUG) { 750 System.out.println("\n****************************"); 751 System.out.println("* OPTIMIZATION *"); 752 System.out.println("* mNumColumns: " + mNumColumns); 753 System.out.println("* GOAL: " + goal + " " + b); 754 System.out.println("****************************\n"); 755 } 756 757 while (!done) { 758 if (sMetrics != null) { 759 sMetrics.iterations++; 760 } 761 tries++; 762 if (DEBUG) { 763 System.out.println("\n******************************"); 764 System.out.println("* iteration: " + tries); 765 } 766 if (tries >= 2 * mNumColumns) { 767 if (DEBUG) { 768 System.out.println("=> Exit optimization because tries " 769 + tries + " >= " + (2 * mNumColumns)); 770 } 771 return tries; 772 } 773 774 if (goal.getKey() != null) { 775 mAlreadyTestedCandidates[goal.getKey().id] = true; 776 } 777 SolverVariable pivotCandidate = goal.getPivotCandidate(this, mAlreadyTestedCandidates); 778 if (DEBUG) { 779 System.out.println("* Pivot candidate: " + pivotCandidate); 780 System.out.println("******************************\n"); 781 } 782 if (pivotCandidate != null) { 783 if (mAlreadyTestedCandidates[pivotCandidate.id]) { 784 if (DEBUG) { 785 System.out.println("* Pivot candidate " + pivotCandidate 786 + " already tested, let's bail"); 787 } 788 return tries; 789 } else { 790 mAlreadyTestedCandidates[pivotCandidate.id] = true; 791 } 792 } 793 794 if (pivotCandidate != null) { 795 if (DEBUG) { 796 System.out.println("valid pivot candidate: " + pivotCandidate); 797 } 798 // there's a negative variable in the goal that we can pivot on. 799 // We now need to select which equation of the system we should do 800 // the pivot on. 801 802 // Let's try to find the equation in the system that we can pivot on. 803 // The rules are simple: 804 // - only look at restricted variables equations (i.e. Cs) 805 // - only look at equations containing the column we are trying to pivot on (duh) 806 // - select preferably an equation with strong strength over weak strength 807 808 float min = Float.MAX_VALUE; 809 int pivotRowIndex = -1; 810 811 for (int i = 0; i < mNumRows; i++) { 812 ArrayRow current = mRows[i]; 813 SolverVariable variable = current.mVariable; 814 if (variable.mType == SolverVariable.Type.UNRESTRICTED) { 815 // skip unrestricted variables equations (to only look at Cs) 816 continue; 817 } 818 if (current.mIsSimpleDefinition) { 819 continue; 820 } 821 822 if (current.hasVariable(pivotCandidate)) { 823 if (DEBUG) { 824 System.out.println("equation " + i + " " 825 + current + " contains " + pivotCandidate); 826 } 827 // the current row does contains the variable 828 // we want to pivot on 829 float a_j = current.variables.get(pivotCandidate); 830 if (a_j < 0) { 831 float value = -current.mConstantValue / a_j; 832 if (value < min) { 833 min = value; 834 pivotRowIndex = i; 835 } 836 } 837 } 838 } 839 // At this point, we ought to have an equation to pivot on 840 841 if (pivotRowIndex > -1) { 842 // We found an equation to pivot on 843 if (DEBUG) { 844 System.out.println("We pivot on " + pivotRowIndex); 845 } 846 ArrayRow pivotEquation = mRows[pivotRowIndex]; 847 pivotEquation.mVariable.mDefinitionId = -1; 848 if (sMetrics != null) { 849 sMetrics.pivots++; 850 } 851 pivotEquation.pivot(pivotCandidate); 852 pivotEquation.mVariable.mDefinitionId = pivotRowIndex; 853 pivotEquation.mVariable.updateReferencesWithNewDefinition(this, pivotEquation); 854 if (DEBUG) { 855 System.out.println("new system after pivot:"); 856 displayReadableRows(); 857 System.out.println("optimizing: " + goal); 858 } 859 /* 860 try { 861 enforceBFS(goal); 862 } catch (Exception e) { 863 System.out.println("### EXCEPTION " + e); 864 e.printStackTrace(); 865 } 866 */ 867 // now that we pivoted, we're going to continue looping on the next goal 868 // columns, until we exhaust all the possibilities of improving the system 869 } else { 870 if (DEBUG) { 871 System.out.println("we couldn't find an equation to pivot upon"); 872 } 873 } 874 875 } else { 876 // There is no candidate goals columns we should try to pivot on, 877 // so let's exit the loop. 878 if (DEBUG) { 879 System.out.println("no more candidate goals to pivot on, let's exit"); 880 } 881 done = true; 882 } 883 } 884 return tries; 885 } 886 887 /** 888 * Make sure that the system is in Basic Feasible Solved form (BFS). 889 * 890 * @param goal the row representing the system goal 891 * @return number of iterations 892 */ enforceBFS(Row goal)893 private int enforceBFS(Row goal) throws Exception { 894 int tries = 0; 895 boolean done; 896 897 if (DEBUG) { 898 System.out.println("\n#################"); 899 System.out.println("# ENFORCING BFS #"); 900 System.out.println("#################\n"); 901 } 902 903 // At this point, we might not be in Basic Feasible Solved form (BFS), 904 // i.e. one of the restricted equation has a negative constant. 905 // Let's check if that's the case or not. 906 boolean infeasibleSystem = false; 907 for (int i = 0; i < mNumRows; i++) { 908 SolverVariable variable = mRows[i].mVariable; 909 if (variable.mType == SolverVariable.Type.UNRESTRICTED) { 910 continue; // C can be either positive or negative. 911 } 912 if (mRows[i].mConstantValue < 0) { 913 infeasibleSystem = true; 914 break; 915 } 916 } 917 918 // The system happens to not be in BFS form, we need to go back to it to properly solve it. 919 if (infeasibleSystem) { 920 if (DEBUG) { 921 System.out.println("the current system is infeasible, let's try to fix this."); 922 } 923 924 // Going back to BFS form can be done by selecting any equations in Cs containing 925 // a negative constant, then selecting a potential pivot variable that would remove 926 // this negative constant. Once we have 927 done = false; 928 tries = 0; 929 while (!done) { 930 if (sMetrics != null) { 931 sMetrics.bfs++; 932 } 933 tries++; 934 if (DEBUG) { 935 System.out.println("iteration on infeasible system " + tries); 936 } 937 float min = Float.MAX_VALUE; 938 int strength = 0; 939 int pivotRowIndex = -1; 940 int pivotColumnIndex = -1; 941 942 for (int i = 0; i < mNumRows; i++) { 943 ArrayRow current = mRows[i]; 944 SolverVariable variable = current.mVariable; 945 if (variable.mType == SolverVariable.Type.UNRESTRICTED) { 946 // skip unrestricted variables equations, as C 947 // can be either positive or negative. 948 continue; 949 } 950 if (current.mIsSimpleDefinition) { 951 continue; 952 } 953 if (current.mConstantValue < 0) { 954 // let's examine this row, see if we can find a good pivot 955 if (DEBUG) { 956 System.out.println("looking at pivoting on row " + current); 957 } 958 if (SKIP_COLUMNS) { 959 final int size = current.variables.getCurrentSize(); 960 for (int j = 0; j < size; j++) { 961 SolverVariable candidate = current.variables.getVariable(j); 962 float a_j = current.variables.get(candidate); 963 if (a_j <= 0) { 964 continue; 965 } 966 if (DEBUG) { 967 System.out.println("candidate for pivot " + candidate); 968 } 969 for (int k = 0; k < SolverVariable.MAX_STRENGTH; k++) { 970 float value = candidate.mStrengthVector[k] / a_j; 971 if ((value < min && k == strength) || k > strength) { 972 min = value; 973 pivotRowIndex = i; 974 pivotColumnIndex = candidate.id; 975 strength = k; 976 } 977 } 978 } 979 } else { 980 for (int j = 1; j < mNumColumns; j++) { 981 SolverVariable candidate = mCache.mIndexedVariables[j]; 982 float a_j = current.variables.get(candidate); 983 if (a_j <= 0) { 984 continue; 985 } 986 if (DEBUG) { 987 System.out.println("candidate for pivot " + candidate); 988 } 989 for (int k = 0; k < SolverVariable.MAX_STRENGTH; k++) { 990 float value = candidate.mStrengthVector[k] / a_j; 991 if ((value < min && k == strength) || k > strength) { 992 min = value; 993 pivotRowIndex = i; 994 pivotColumnIndex = j; 995 strength = k; 996 } 997 } 998 } 999 } 1000 } 1001 } 1002 1003 if (pivotRowIndex != -1) { 1004 // We have a pivot! 1005 ArrayRow pivotEquation = mRows[pivotRowIndex]; 1006 if (DEBUG) { 1007 System.out.println("Pivoting on " + pivotEquation.mVariable + " with " 1008 + mCache.mIndexedVariables[pivotColumnIndex]); 1009 } 1010 pivotEquation.mVariable.mDefinitionId = -1; 1011 if (sMetrics != null) { 1012 sMetrics.pivots++; 1013 } 1014 pivotEquation.pivot(mCache.mIndexedVariables[pivotColumnIndex]); 1015 pivotEquation.mVariable.mDefinitionId = pivotRowIndex; 1016 pivotEquation.mVariable.updateReferencesWithNewDefinition(this, pivotEquation); 1017 1018 if (DEBUG) { 1019 System.out.println("new goal after pivot: " + goal); 1020 displayRows(); 1021 } 1022 } else { 1023 done = true; 1024 } 1025 if (tries > mNumColumns / 2) { 1026 // fail safe -- tried too many times 1027 done = true; 1028 } 1029 } 1030 } 1031 1032 if (DEBUG) { 1033 System.out.println("the current system should now be feasible [" 1034 + infeasibleSystem + "] after " + tries + " iterations"); 1035 displayReadableRows(); 1036 1037 // Let's make sure the system is correct 1038 //noinspection UnusedAssignment 1039 infeasibleSystem = false; 1040 for (int i = 0; i < mNumRows; i++) { 1041 SolverVariable variable = mRows[i].mVariable; 1042 if (variable.mType == SolverVariable.Type.UNRESTRICTED) { 1043 continue; // C can be either positive or negative. 1044 } 1045 if (mRows[i].mConstantValue < 0) { 1046 //noinspection UnusedAssignment 1047 infeasibleSystem = true; 1048 break; 1049 } 1050 } 1051 1052 if (DEBUG && infeasibleSystem) { 1053 System.out.println("IMPOSSIBLE SYSTEM, WTF"); 1054 throw new Exception(); 1055 } 1056 if (infeasibleSystem) { 1057 return tries; 1058 } 1059 } 1060 1061 return tries; 1062 } 1063 computeValues()1064 private void computeValues() { 1065 for (int i = 0; i < mNumRows; i++) { 1066 ArrayRow row = mRows[i]; 1067 row.mVariable.computedValue = row.mConstantValue; 1068 } 1069 } 1070 1071 /*--------------------------------------------------------------------------------------------*/ 1072 // Display utility functions 1073 /*--------------------------------------------------------------------------------------------*/ 1074 1075 @SuppressWarnings("unused") displayRows()1076 private void displayRows() { 1077 displaySolverVariables(); 1078 String s = ""; 1079 for (int i = 0; i < mNumRows; i++) { 1080 s += mRows[i]; 1081 s += "\n"; 1082 } 1083 s += mGoal + "\n"; 1084 System.out.println(s); 1085 } 1086 1087 // @TODO: add description displayReadableRows()1088 public void displayReadableRows() { 1089 displaySolverVariables(); 1090 String s = " num vars " + mVariablesID + "\n"; 1091 for (int i = 0; i < mVariablesID + 1; i++) { 1092 SolverVariable variable = mCache.mIndexedVariables[i]; 1093 if (variable != null && variable.isFinalValue) { 1094 s += " $[" + i + "] => " + variable + " = " + variable.computedValue + "\n"; 1095 } 1096 } 1097 s += "\n"; 1098 for (int i = 0; i < mVariablesID + 1; i++) { 1099 SolverVariable variable = mCache.mIndexedVariables[i]; 1100 if (variable != null && variable.mIsSynonym) { 1101 SolverVariable synonym = mCache.mIndexedVariables[variable.mSynonym]; 1102 s += " ~[" + i + "] => " + variable + " = " 1103 + synonym + " + " + variable.mSynonymDelta + "\n"; 1104 } 1105 } 1106 s += "\n\n # "; 1107 for (int i = 0; i < mNumRows; i++) { 1108 s += mRows[i].toReadableString(); 1109 s += "\n # "; 1110 } 1111 if (mGoal != null) { 1112 s += "Goal: " + mGoal + "\n"; 1113 } 1114 System.out.println(s); 1115 } 1116 1117 // @TODO: add description 1118 @SuppressWarnings("unused") displayVariablesReadableRows()1119 public void displayVariablesReadableRows() { 1120 displaySolverVariables(); 1121 String s = ""; 1122 for (int i = 0; i < mNumRows; i++) { 1123 if (mRows[i].mVariable.mType == SolverVariable.Type.UNRESTRICTED) { 1124 s += mRows[i].toReadableString(); 1125 s += "\n"; 1126 } 1127 } 1128 s += mGoal + "\n"; 1129 System.out.println(s); 1130 } 1131 1132 1133 // @TODO: add description 1134 @SuppressWarnings("unused") getMemoryUsed()1135 public int getMemoryUsed() { 1136 int actualRowSize = 0; 1137 for (int i = 0; i < mNumRows; i++) { 1138 if (mRows[i] != null) { 1139 actualRowSize += mRows[i].sizeInBytes(); 1140 } 1141 } 1142 return actualRowSize; 1143 } 1144 1145 @SuppressWarnings("unused") getNumEquations()1146 public int getNumEquations() { 1147 return mNumRows; 1148 } 1149 1150 @SuppressWarnings("unused") getNumVariables()1151 public int getNumVariables() { 1152 return mVariablesID; 1153 } 1154 1155 /** 1156 * Display current system information 1157 */ displaySystemInformation()1158 void displaySystemInformation() { 1159 int count = 0; 1160 int rowSize = 0; 1161 for (int i = 0; i < mTableSize; i++) { 1162 if (mRows[i] != null) { 1163 rowSize += mRows[i].sizeInBytes(); 1164 } 1165 } 1166 int actualRowSize = 0; 1167 for (int i = 0; i < mNumRows; i++) { 1168 if (mRows[i] != null) { 1169 actualRowSize += mRows[i].sizeInBytes(); 1170 } 1171 } 1172 1173 System.out.println("Linear System -> Table size: " + mTableSize 1174 + " (" + getDisplaySize(mTableSize * mTableSize) 1175 + ") -- row sizes: " + getDisplaySize(rowSize) 1176 + ", actual size: " + getDisplaySize(actualRowSize) 1177 + " rows: " + mNumRows + "/" + mMaxRows 1178 + " cols: " + mNumColumns + "/" + mMaxColumns 1179 + " " + count + " occupied cells, " + getDisplaySize(count) 1180 ); 1181 } 1182 displaySolverVariables()1183 private void displaySolverVariables() { 1184 String s = "Display Rows (" + mNumRows + "x" + mNumColumns + ")\n"; 1185 /* 1186 s += ":\n\t | C | "; 1187 for (int i = 1; i <= mNumColumns; i++) { 1188 SolverVariable v = mCache.mIndexedVariables[i]; 1189 s += v; 1190 s += " | "; 1191 } 1192 s += "\n"; 1193 */ 1194 System.out.println(s); 1195 } 1196 getDisplaySize(int n)1197 private String getDisplaySize(int n) { 1198 int mb = (n * 4) / 1024 / 1024; 1199 if (mb > 0) { 1200 return "" + mb + " Mb"; 1201 } 1202 int kb = (n * 4) / 1024; 1203 if (kb > 0) { 1204 return "" + kb + " Kb"; 1205 } 1206 return "" + (n * 4) + " bytes"; 1207 } 1208 getCache()1209 public Cache getCache() { 1210 return mCache; 1211 } 1212 getDisplayStrength(int strength)1213 private String getDisplayStrength(int strength) { 1214 if (strength == SolverVariable.STRENGTH_LOW) { 1215 return "LOW"; 1216 } 1217 if (strength == SolverVariable.STRENGTH_MEDIUM) { 1218 return "MEDIUM"; 1219 } 1220 if (strength == SolverVariable.STRENGTH_HIGH) { 1221 return "HIGH"; 1222 } 1223 if (strength == SolverVariable.STRENGTH_HIGHEST) { 1224 return "HIGHEST"; 1225 } 1226 if (strength == SolverVariable.STRENGTH_EQUALITY) { 1227 return "EQUALITY"; 1228 } 1229 if (strength == SolverVariable.STRENGTH_FIXED) { 1230 return "FIXED"; 1231 } 1232 if (strength == SolverVariable.STRENGTH_BARRIER) { 1233 return "BARRIER"; 1234 } 1235 return "NONE"; 1236 } 1237 1238 //////////////////////////////////////////////////////////////////////////////////////// 1239 // Equations 1240 //////////////////////////////////////////////////////////////////////////////////////// 1241 1242 /** 1243 * Add an equation of the form a >= b + margin 1244 * 1245 * @param a variable a 1246 * @param b variable b 1247 * @param margin margin 1248 * @param strength strength used 1249 */ addGreaterThan(SolverVariable a, SolverVariable b, int margin, int strength)1250 public void addGreaterThan(SolverVariable a, SolverVariable b, int margin, int strength) { 1251 if (DEBUG_CONSTRAINTS) { 1252 System.out.println("-> " + a + " >= " + b + (margin != 0 ? " + " + margin : "") 1253 + " " + getDisplayStrength(strength)); 1254 } 1255 ArrayRow row = createRow(); 1256 SolverVariable slack = createSlackVariable(); 1257 slack.strength = 0; 1258 row.createRowGreaterThan(a, b, slack, margin); 1259 if (strength != SolverVariable.STRENGTH_FIXED) { 1260 float slackValue = row.variables.get(slack); 1261 addSingleError(row, (int) (-1 * slackValue), strength); 1262 } 1263 addConstraint(row); 1264 } 1265 1266 // @TODO: add description addGreaterBarrier(SolverVariable a, SolverVariable b, int margin, boolean hasMatchConstraintWidgets)1267 public void addGreaterBarrier(SolverVariable a, 1268 SolverVariable b, 1269 int margin, 1270 boolean hasMatchConstraintWidgets) { 1271 if (DEBUG_CONSTRAINTS) { 1272 System.out.println("-> Barrier " + a + " >= " + b); 1273 } 1274 ArrayRow row = createRow(); 1275 SolverVariable slack = createSlackVariable(); 1276 slack.strength = 0; 1277 row.createRowGreaterThan(a, b, slack, margin); 1278 addConstraint(row); 1279 } 1280 1281 /** 1282 * Add an equation of the form a <= b + margin 1283 * 1284 * @param a variable a 1285 * @param b variable b 1286 * @param margin margin 1287 * @param strength strength used 1288 */ addLowerThan(SolverVariable a, SolverVariable b, int margin, int strength)1289 public void addLowerThan(SolverVariable a, SolverVariable b, int margin, int strength) { 1290 if (DEBUG_CONSTRAINTS) { 1291 System.out.println("-> " + a + " <= " + b + (margin != 0 ? " + " + margin : "") 1292 + " " + getDisplayStrength(strength)); 1293 } 1294 ArrayRow row = createRow(); 1295 SolverVariable slack = createSlackVariable(); 1296 slack.strength = 0; 1297 row.createRowLowerThan(a, b, slack, margin); 1298 if (strength != SolverVariable.STRENGTH_FIXED) { 1299 float slackValue = row.variables.get(slack); 1300 addSingleError(row, (int) (-1 * slackValue), strength); 1301 } 1302 addConstraint(row); 1303 } 1304 1305 // @TODO: add description addLowerBarrier(SolverVariable a, SolverVariable b, int margin, boolean hasMatchConstraintWidgets)1306 public void addLowerBarrier(SolverVariable a, 1307 SolverVariable b, 1308 int margin, 1309 boolean hasMatchConstraintWidgets) { 1310 if (DEBUG_CONSTRAINTS) { 1311 System.out.println("-> Barrier " + a + " <= " + b); 1312 } 1313 ArrayRow row = createRow(); 1314 SolverVariable slack = createSlackVariable(); 1315 slack.strength = 0; 1316 row.createRowLowerThan(a, b, slack, margin); 1317 addConstraint(row); 1318 } 1319 1320 /** 1321 * Add an equation of the form (1 - bias) * (a - b) = bias * (c - d) 1322 * 1323 * @param a variable a 1324 * @param b variable b 1325 * @param m1 margin 1 1326 * @param bias bias between ab - cd 1327 * @param c variable c 1328 * @param d variable d 1329 * @param m2 margin 2 1330 * @param strength strength used 1331 */ addCentering(SolverVariable a, SolverVariable b, int m1, float bias, SolverVariable c, SolverVariable d, int m2, int strength)1332 public void addCentering(SolverVariable a, SolverVariable b, int m1, float bias, 1333 SolverVariable c, SolverVariable d, int m2, int strength) { 1334 if (DEBUG_CONSTRAINTS) { 1335 System.out.println("-> [center bias: " + bias + "] : " + a + " - " + b 1336 + " - " + m1 1337 + " = " + c + " - " + d + " - " + m2 1338 + " " + getDisplayStrength(strength)); 1339 } 1340 ArrayRow row = createRow(); 1341 row.createRowCentering(a, b, m1, bias, c, d, m2); 1342 if (strength != SolverVariable.STRENGTH_FIXED) { 1343 row.addError(this, strength); 1344 } 1345 addConstraint(row); 1346 } 1347 1348 // @TODO: add description addRatio(SolverVariable a, SolverVariable b, SolverVariable c, SolverVariable d, float ratio, int strength)1349 public void addRatio(SolverVariable a, 1350 SolverVariable b, 1351 SolverVariable c, 1352 SolverVariable d, 1353 float ratio, 1354 int strength) { 1355 if (DEBUG_CONSTRAINTS) { 1356 System.out.println("-> [ratio: " + ratio + "] : " + a + " = " + b 1357 + " + (" + c + " - " + d + ") * " + ratio + " " + getDisplayStrength(strength)); 1358 } 1359 ArrayRow row = createRow(); 1360 row.createRowDimensionRatio(a, b, c, d, ratio); 1361 if (strength != SolverVariable.STRENGTH_FIXED) { 1362 row.addError(this, strength); 1363 } 1364 addConstraint(row); 1365 } 1366 1367 // @TODO: add description addSynonym(SolverVariable a, SolverVariable b, int margin)1368 public void addSynonym(SolverVariable a, SolverVariable b, int margin) { 1369 if (a.mDefinitionId == -1 && margin == 0) { 1370 if (DEBUG_CONSTRAINTS) { 1371 System.out.println("(S) -> " + a + " = " + b + (margin != 0 ? " + " + margin : "")); 1372 } 1373 if (b.mIsSynonym) { 1374 margin += (int) b.mSynonymDelta; 1375 b = mCache.mIndexedVariables[b.mSynonym]; 1376 } 1377 if (a.mIsSynonym) { 1378 margin -= (int) a.mSynonymDelta; 1379 a = mCache.mIndexedVariables[a.mSynonym]; 1380 } else { 1381 a.setSynonym(this, b, 0); 1382 } 1383 } else { 1384 addEquality(a, b, margin, SolverVariable.STRENGTH_FIXED); 1385 } 1386 } 1387 1388 /** 1389 * Add an equation of the form a = b + margin 1390 * 1391 * @param a variable a 1392 * @param b variable b 1393 * @param margin margin used 1394 * @param strength strength used 1395 */ addEquality(SolverVariable a, SolverVariable b, int margin, int strength)1396 public ArrayRow addEquality(SolverVariable a, SolverVariable b, int margin, int strength) { 1397 if (sMetrics != null) { 1398 sMetrics.mSimpleEquations++; 1399 } 1400 if (USE_BASIC_SYNONYMS && strength == SolverVariable.STRENGTH_FIXED 1401 && b.isFinalValue && a.mDefinitionId == -1) { 1402 if (DEBUG_CONSTRAINTS) { 1403 System.out.println("=> " + a + " = " + b + (margin != 0 ? " + " + margin : "") 1404 + " = " + (b.computedValue + margin) + " (Synonym)"); 1405 } 1406 a.setFinalValue(this, b.computedValue + margin); 1407 return null; 1408 } 1409 if (DO_NOT_USE && USE_SYNONYMS && strength == SolverVariable.STRENGTH_FIXED 1410 && a.mDefinitionId == -1 && margin == 0) { 1411 if (DEBUG_CONSTRAINTS) { 1412 System.out.println("(S) -> " + a + " = " + b + (margin != 0 ? " + " + margin : "") 1413 + " " + getDisplayStrength(strength)); 1414 } 1415 if (b.mIsSynonym) { 1416 margin += (int) b.mSynonymDelta; 1417 b = mCache.mIndexedVariables[b.mSynonym]; 1418 } 1419 if (a.mIsSynonym) { 1420 margin -= (int) a.mSynonymDelta; 1421 a = mCache.mIndexedVariables[a.mSynonym]; 1422 } else { 1423 a.setSynonym(this, b, margin); 1424 return null; 1425 } 1426 } 1427 if (DEBUG_CONSTRAINTS) { 1428 System.out.println("-> " + a + " = " + b + (margin != 0 ? " + " + margin : "") 1429 + " " + getDisplayStrength(strength)); 1430 } 1431 ArrayRow row = createRow(); 1432 row.createRowEquals(a, b, margin); 1433 if (strength != SolverVariable.STRENGTH_FIXED) { 1434 row.addError(this, strength); 1435 } 1436 addConstraint(row); 1437 return row; 1438 } 1439 1440 /** 1441 * Add an equation of the form a = value 1442 * 1443 * @param a variable a 1444 * @param value the value we set 1445 */ addEquality(SolverVariable a, int value)1446 public void addEquality(SolverVariable a, int value) { 1447 if (sMetrics != null) { 1448 sMetrics.mSimpleEquations++; 1449 } 1450 if (USE_BASIC_SYNONYMS && a.mDefinitionId == -1) { 1451 if (DEBUG_CONSTRAINTS) { 1452 System.out.println("=> " + a + " = " + value + " (Synonym)"); 1453 } 1454 a.setFinalValue(this, value); 1455 for (int i = 0; i < mVariablesID + 1; i++) { 1456 SolverVariable variable = mCache.mIndexedVariables[i]; 1457 if (variable != null && variable.mIsSynonym && variable.mSynonym == a.id) { 1458 variable.setFinalValue(this, value + variable.mSynonymDelta); 1459 } 1460 } 1461 return; 1462 } 1463 if (DEBUG_CONSTRAINTS) { 1464 System.out.println("-> " + a + " = " + value); 1465 } 1466 int idx = a.mDefinitionId; 1467 if (a.mDefinitionId != -1) { 1468 ArrayRow row = mRows[idx]; 1469 if (row.mIsSimpleDefinition) { 1470 row.mConstantValue = value; 1471 } else { 1472 if (row.variables.getCurrentSize() == 0) { 1473 row.mIsSimpleDefinition = true; 1474 row.mConstantValue = value; 1475 } else { 1476 ArrayRow newRow = createRow(); 1477 newRow.createRowEquals(a, value); 1478 addConstraint(newRow); 1479 } 1480 } 1481 } else { 1482 ArrayRow row = createRow(); 1483 row.createRowDefinition(a, value); 1484 addConstraint(row); 1485 } 1486 } 1487 1488 /** 1489 * Create a constraint to express A = C * percent 1490 * 1491 * @param linearSystem the system we create the row on 1492 * @param variableA variable a 1493 * @param variableC variable c 1494 * @param percent the percent used 1495 * @return the created row 1496 */ createRowDimensionPercent(LinearSystem linearSystem, SolverVariable variableA, SolverVariable variableC, float percent)1497 public static ArrayRow createRowDimensionPercent(LinearSystem linearSystem, 1498 SolverVariable variableA, 1499 SolverVariable variableC, 1500 float percent) { 1501 if (DEBUG_CONSTRAINTS) { 1502 System.out.println("-> " + variableA + " = " + variableC + " * " + percent); 1503 } 1504 ArrayRow row = linearSystem.createRow(); 1505 return row.createRowDimensionPercent(variableA, variableC, percent); 1506 } 1507 1508 /** 1509 * Add the equations constraining a widget center to another widget center, positioned 1510 * on a circle, following an angle and radius 1511 * 1512 * @param widget the constrained widget 1513 * @param target the constrained-to widget 1514 * @param angle from 0 to 360 1515 * @param radius the distance between the two centers 1516 */ addCenterPoint(ConstraintWidget widget, ConstraintWidget target, float angle, int radius)1517 public void addCenterPoint(ConstraintWidget widget, 1518 ConstraintWidget target, 1519 float angle, 1520 int radius) { 1521 1522 SolverVariable Al = createObjectVariable(widget.getAnchor(ConstraintAnchor.Type.LEFT)); 1523 SolverVariable At = createObjectVariable(widget.getAnchor(ConstraintAnchor.Type.TOP)); 1524 SolverVariable Ar = createObjectVariable(widget.getAnchor(ConstraintAnchor.Type.RIGHT)); 1525 SolverVariable Ab = createObjectVariable(widget.getAnchor(ConstraintAnchor.Type.BOTTOM)); 1526 1527 SolverVariable Bl = createObjectVariable(target.getAnchor(ConstraintAnchor.Type.LEFT)); 1528 SolverVariable Bt = createObjectVariable(target.getAnchor(ConstraintAnchor.Type.TOP)); 1529 SolverVariable Br = createObjectVariable(target.getAnchor(ConstraintAnchor.Type.RIGHT)); 1530 SolverVariable Bb = createObjectVariable(target.getAnchor(ConstraintAnchor.Type.BOTTOM)); 1531 1532 ArrayRow row = createRow(); 1533 float angleComponent = (float) (Math.sin(angle) * radius); 1534 row.createRowWithAngle(At, Ab, Bt, Bb, angleComponent); 1535 addConstraint(row); 1536 row = createRow(); 1537 angleComponent = (float) (Math.cos(angle) * radius); 1538 row.createRowWithAngle(Al, Ar, Bl, Br, angleComponent); 1539 addConstraint(row); 1540 } 1541 1542 } 1543