content: /*
   * Copyright (C) 2019 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.widgets.analyzer;
  
  import static androidx.constraintlayout.core.widgets.ConstraintWidget.DimensionBehaviour.FIXED;
  import static androidx.constraintlayout.core.widgets.ConstraintWidget.DimensionBehaviour.MATCH_CONSTRAINT;
  import static androidx.constraintlayout.core.widgets.ConstraintWidget.DimensionBehaviour.MATCH_PARENT;
  import static androidx.constraintlayout.core.widgets.ConstraintWidget.DimensionBehaviour.WRAP_CONTENT;
  import static androidx.constraintlayout.core.widgets.ConstraintWidget.GONE;
  import static androidx.constraintlayout.core.widgets.ConstraintWidget.HORIZONTAL;
  import static androidx.constraintlayout.core.widgets.ConstraintWidget.MATCH_CONSTRAINT_PERCENT;
  import static androidx.constraintlayout.core.widgets.ConstraintWidget.MATCH_CONSTRAINT_RATIO;
  import static androidx.constraintlayout.core.widgets.ConstraintWidget.MATCH_CONSTRAINT_SPREAD;
  import static androidx.constraintlayout.core.widgets.ConstraintWidget.MATCH_CONSTRAINT_WRAP;
  import static androidx.constraintlayout.core.widgets.ConstraintWidget.UNKNOWN;
  import static androidx.constraintlayout.core.widgets.ConstraintWidget.VERTICAL;
  
  import androidx.constraintlayout.core.widgets.Barrier;
  import androidx.constraintlayout.core.widgets.ConstraintWidget;
  import androidx.constraintlayout.core.widgets.ConstraintWidgetContainer;
  import androidx.constraintlayout.core.widgets.Guideline;
  import androidx.constraintlayout.core.widgets.HelperWidget;
  
  import java.util.ArrayList;
  import java.util.HashSet;
  
  public class DependencyGraph {
      private static final boolean USE_GROUPS = true;
      private ConstraintWidgetContainer mWidgetcontainer;
      private boolean mNeedBuildGraph = true;
      private boolean mNeedRedoMeasures = true;
      private ConstraintWidgetContainer mContainer;
      private ArrayList<WidgetRun> mRuns = new ArrayList<>();
      private static final boolean DEBUG = false;
  
      // TODO: Unused, should we delete?
      @SuppressWarnings("unused") private ArrayList<RunGroup> mRunGroups = new ArrayList<>();
  
      public DependencyGraph(ConstraintWidgetContainer container) {
          this.mWidgetcontainer = container;
          mContainer = container;
      }
  
      private BasicMeasure.Measurer mMeasurer = null;
      private BasicMeasure.Measure mMeasure = new BasicMeasure.Measure();
  
      public void setMeasurer(BasicMeasure.Measurer measurer) {
          mMeasurer = measurer;
      }
  
      private int computeWrap(ConstraintWidgetContainer container, int orientation) {
          final int count = mGroups.size();
          long wrapSize = 0;
          for (int i = 0; i < count; i++) {
              RunGroup run = mGroups.get(i);
              long size = run.computeWrapSize(container, orientation);
              wrapSize = Math.max(wrapSize, size);
          }
          return (int) wrapSize;
      }
  
      /**
       * Find and mark terminal widgets (trailing widgets) -- they are the only
       * ones we need to care for wrap_content checks
       */
      public void defineTerminalWidgets(ConstraintWidget.DimensionBehaviour horizontalBehavior,
              ConstraintWidget.DimensionBehaviour verticalBehavior) {
          if (mNeedBuildGraph) {
              buildGraph();
  
              if (USE_GROUPS) {
                  boolean hasBarrier = false;
                  for (ConstraintWidget widget : mWidgetcontainer.mChildren) {
                      widget.isTerminalWidget[HORIZONTAL] = true;
                      widget.isTerminalWidget[VERTICAL] = true;
                      if (widget instanceof Barrier) {
                          hasBarrier = true;
                      }
                  }
                  if (!hasBarrier) {
                      for (RunGroup group : mGroups) {
                          group.defineTerminalWidgets(horizontalBehavior == WRAP_CONTENT,
                                  verticalBehavior == WRAP_CONTENT);
                      }
                  }
              }
          }
      }
  
      /**
       * Try to measure the layout by solving the graph of constraints directly
       *
       * @param optimizeWrap use the wrap_content optimizer
       * @return true if all widgets have been resolved
       */
      public boolean directMeasure(boolean optimizeWrap) {
          optimizeWrap &= USE_GROUPS;
  
          if (mNeedBuildGraph || mNeedRedoMeasures) {
              for (ConstraintWidget widget : mWidgetcontainer.mChildren) {
                  widget.ensureWidgetRuns();
                  widget.measured = false;
                  widget.mHorizontalRun.reset();
                  widget.mVerticalRun.reset();
              }
              mWidgetcontainer.ensureWidgetRuns();
              mWidgetcontainer.measured = false;
              mWidgetcontainer.mHorizontalRun.reset();
              mWidgetcontainer.mVerticalRun.reset();
              mNeedRedoMeasures = false;
          }
  
          boolean avoid = basicMeasureWidgets(mContainer);
          if (avoid) {
              return false;
          }
  
          mWidgetcontainer.setX(0);
          mWidgetcontainer.setY(0);
  
          ConstraintWidget.DimensionBehaviour originalHorizontalDimension =
                  mWidgetcontainer.getDimensionBehaviour(HORIZONTAL);
          ConstraintWidget.DimensionBehaviour originalVerticalDimension =
                  mWidgetcontainer.getDimensionBehaviour(VERTICAL);
  
          if (mNeedBuildGraph) {
              buildGraph();
          }
  
          int x1 = mWidgetcontainer.getX();
          int y1 = mWidgetcontainer.getY();
  
          mWidgetcontainer.mHorizontalRun.start.resolve(x1);
          mWidgetcontainer.mVerticalRun.start.resolve(y1);
  
          // Let's do the easy steps first -- anything that can be immediately measured
          // Whatever is left for the dimension will be match_constraints.
          measureWidgets();
  
          // If we have to support wrap, let's see if we can compute it directly
          if (originalHorizontalDimension == WRAP_CONTENT
                  || originalVerticalDimension == WRAP_CONTENT) {
              if (optimizeWrap) {
                  for (WidgetRun run : mRuns) {
                      if (!run.supportsWrapComputation()) {
                          optimizeWrap = false;
                          break;
                      }
                  }
              }
  
              if (optimizeWrap && originalHorizontalDimension == WRAP_CONTENT) {
                  mWidgetcontainer.setHorizontalDimensionBehaviour(FIXED);
                  mWidgetcontainer.setWidth(computeWrap(mWidgetcontainer, HORIZONTAL));
                  mWidgetcontainer.mHorizontalRun.mDimension.resolve(mWidgetcontainer.getWidth());
              }
              if (optimizeWrap && originalVerticalDimension == WRAP_CONTENT) {
                  mWidgetcontainer.setVerticalDimensionBehaviour(FIXED);
                  mWidgetcontainer.setHeight(computeWrap(mWidgetcontainer, VERTICAL));
                  mWidgetcontainer.mVerticalRun.mDimension.resolve(mWidgetcontainer.getHeight());
              }
          }
  
          boolean checkRoot = false;
  
          // Now, depending on our own dimension behavior, we may want to solve
          // one dimension before the other
  
          if (mWidgetcontainer.mListDimensionBehaviors[HORIZONTAL]
                  == ConstraintWidget.DimensionBehaviour.FIXED
                  || mWidgetcontainer.mListDimensionBehaviors[HORIZONTAL]
                  == ConstraintWidget.DimensionBehaviour.MATCH_PARENT) {
  
              // solve horizontal dimension
              int x2 = x1 + mWidgetcontainer.getWidth();
              mWidgetcontainer.mHorizontalRun.end.resolve(x2);
              mWidgetcontainer.mHorizontalRun.mDimension.resolve(x2 - x1);
              measureWidgets();
              if (mWidgetcontainer.mListDimensionBehaviors[VERTICAL] == FIXED
                      || mWidgetcontainer.mListDimensionBehaviors[VERTICAL] == MATCH_PARENT) {
                  int y2 = y1 + mWidgetcontainer.getHeight();
                  mWidgetcontainer.mVerticalRun.end.resolve(y2);
                  mWidgetcontainer.mVerticalRun.mDimension.resolve(y2 - y1);
              }
              measureWidgets();
              checkRoot = true;
          } else {
              // we'll bail out to the solver...
          }
  
          // Let's apply what we did resolve
          for (WidgetRun run : mRuns) {
              if (run.mWidget == mWidgetcontainer && !run.mResolved) {
                  continue;
              }
              run.applyToWidget();
          }
  
          boolean allResolved = true;
          for (WidgetRun run : mRuns) {
              if (!checkRoot && run.mWidget == mWidgetcontainer) {
                  continue;
              }
              if (!run.start.resolved) {
                  allResolved = false;
                  break;
              }
              if (!run.end.resolved && !(run instanceof GuidelineReference)) {
                  allResolved = false;
                  break;
              }
              if (!run.mDimension.resolved
                      && !(run instanceof ChainRun) && !(run instanceof GuidelineReference)) {
                  allResolved = false;
                  break;
              }
          }
  
          mWidgetcontainer.setHorizontalDimensionBehaviour(originalHorizontalDimension);
          mWidgetcontainer.setVerticalDimensionBehaviour(originalVerticalDimension);
  
          return allResolved;
      }
  
      // @TODO: add description
      public boolean directMeasureSetup(boolean optimizeWrap) {
          if (mNeedBuildGraph) {
              for (ConstraintWidget widget : mWidgetcontainer.mChildren) {
                  widget.ensureWidgetRuns();
                  widget.measured = false;
                  widget.mHorizontalRun.mDimension.resolved = false;
                  widget.mHorizontalRun.mResolved = false;
                  widget.mHorizontalRun.reset();
                  widget.mVerticalRun.mDimension.resolved = false;
                  widget.mVerticalRun.mResolved = false;
                  widget.mVerticalRun.reset();
              }
              mWidgetcontainer.ensureWidgetRuns();
              mWidgetcontainer.measured = false;
              mWidgetcontainer.mHorizontalRun.mDimension.resolved = false;
              mWidgetcontainer.mHorizontalRun.mResolved = false;
              mWidgetcontainer.mHorizontalRun.reset();
              mWidgetcontainer.mVerticalRun.mDimension.resolved = false;
              mWidgetcontainer.mVerticalRun.mResolved = false;
              mWidgetcontainer.mVerticalRun.reset();
              buildGraph();
          }
  
          boolean avoid = basicMeasureWidgets(mContainer);
          if (avoid) {
              return false;
          }
  
          mWidgetcontainer.setX(0);
          mWidgetcontainer.setY(0);
          mWidgetcontainer.mHorizontalRun.start.resolve(0);
          mWidgetcontainer.mVerticalRun.start.resolve(0);
          return true;
      }
  
      // @TODO: add description
      public boolean directMeasureWithOrientation(boolean optimizeWrap, int orientation) {
          optimizeWrap &= USE_GROUPS;
  
          ConstraintWidget.DimensionBehaviour originalHorizontalDimension =
                  mWidgetcontainer.getDimensionBehaviour(HORIZONTAL);
          ConstraintWidget.DimensionBehaviour originalVerticalDimension =
                  mWidgetcontainer.getDimensionBehaviour(VERTICAL);
  
          int x1 = mWidgetcontainer.getX();
          int y1 = mWidgetcontainer.getY();
  
          // If we have to support wrap, let's see if we can compute it directly
          if (optimizeWrap && (originalHorizontalDimension == WRAP_CONTENT
                  || originalVerticalDimension == WRAP_CONTENT)) {
              for (WidgetRun run : mRuns) {
                  if (run.orientation == orientation
                          && !run.supportsWrapComputation()) {
                      optimizeWrap = false;
                      break;
                  }
              }
  
              if (orientation == HORIZONTAL) {
                  if (optimizeWrap && originalHorizontalDimension == WRAP_CONTENT) {
                      mWidgetcontainer.setHorizontalDimensionBehaviour(FIXED);
                      mWidgetcontainer.setWidth(computeWrap(mWidgetcontainer, HORIZONTAL));
                      mWidgetcontainer.mHorizontalRun.mDimension.resolve(mWidgetcontainer.getWidth());
                  }
              } else {
                  if (optimizeWrap && originalVerticalDimension == WRAP_CONTENT) {
                      mWidgetcontainer.setVerticalDimensionBehaviour(FIXED);
                      mWidgetcontainer.setHeight(computeWrap(mWidgetcontainer, VERTICAL));
                      mWidgetcontainer.mVerticalRun.mDimension.resolve(mWidgetcontainer.getHeight());
                  }
              }
          }
  
          boolean checkRoot = false;
  
          // Now, depending on our own dimension behavior, we may want to solve
          // one dimension before the other
  
          if (orientation == HORIZONTAL) {
              if (mWidgetcontainer.mListDimensionBehaviors[HORIZONTAL] == FIXED
                      || mWidgetcontainer.mListDimensionBehaviors[HORIZONTAL] == MATCH_PARENT) {
                  int x2 = x1 + mWidgetcontainer.getWidth();
                  mWidgetcontainer.mHorizontalRun.end.resolve(x2);
                  mWidgetcontainer.mHorizontalRun.mDimension.resolve(x2 - x1);
                  checkRoot = true;
              }
          } else {
              if (mWidgetcontainer.mListDimensionBehaviors[VERTICAL] == FIXED
                      || mWidgetcontainer.mListDimensionBehaviors[VERTICAL] == MATCH_PARENT) {
                  int y2 = y1 + mWidgetcontainer.getHeight();
                  mWidgetcontainer.mVerticalRun.end.resolve(y2);
                  mWidgetcontainer.mVerticalRun.mDimension.resolve(y2 - y1);
                  checkRoot = true;
              }
          }
          measureWidgets();
  
          // Let's apply what we did resolve
          for (WidgetRun run : mRuns) {
              if (run.orientation != orientation) {
                  continue;
              }
              if (run.mWidget == mWidgetcontainer && !run.mResolved) {
                  continue;
              }
              run.applyToWidget();
          }
  
          boolean allResolved = true;
          for (WidgetRun run : mRuns) {
              if (run.orientation != orientation) {
                  continue;
              }
              if (!checkRoot && run.mWidget == mWidgetcontainer) {
                  continue;
              }
              if (!run.start.resolved) {
                  allResolved = false;
                  break;
              }
              if (!run.end.resolved) {
                  allResolved = false;
                  break;
              }
              if (!(run instanceof ChainRun) && !run.mDimension.resolved) {
                  allResolved = false;
                  break;
              }
          }
  
          mWidgetcontainer.setHorizontalDimensionBehaviour(originalHorizontalDimension);
          mWidgetcontainer.setVerticalDimensionBehaviour(originalVerticalDimension);
  
          return allResolved;
      }
  
      /**
       * Convenience function to fill in the measure spec
       *
       * @param widget the widget to measure
       */
      private void measure(ConstraintWidget widget,
              ConstraintWidget.DimensionBehaviour horizontalBehavior,
              int horizontalDimension,
              ConstraintWidget.DimensionBehaviour verticalBehavior,
              int verticalDimension) {
          mMeasure.horizontalBehavior = horizontalBehavior;
          mMeasure.verticalBehavior = verticalBehavior;
          mMeasure.horizontalDimension = horizontalDimension;
          mMeasure.verticalDimension = verticalDimension;
          mMeasurer.measure(widget, mMeasure);
          widget.setWidth(mMeasure.measuredWidth);
          widget.setHeight(mMeasure.measuredHeight);
          widget.setHasBaseline(mMeasure.measuredHasBaseline);
          widget.setBaselineDistance(mMeasure.measuredBaseline);
      }
  
      private boolean basicMeasureWidgets(ConstraintWidgetContainer constraintWidgetContainer) {
          for (ConstraintWidget widget : constraintWidgetContainer.mChildren) {
              ConstraintWidget.DimensionBehaviour horizontal =
                      widget.mListDimensionBehaviors[HORIZONTAL];
              ConstraintWidget.DimensionBehaviour vertical = widget.mListDimensionBehaviors[VERTICAL];
  
              if (widget.getVisibility() == GONE) {
                  widget.measured = true;
                  continue;
              }
  
              // Basic validation
              // TODO: might move this earlier in the process
              if (widget.mMatchConstraintPercentWidth < 1 && horizontal == MATCH_CONSTRAINT) {
                  widget.mMatchConstraintDefaultWidth = MATCH_CONSTRAINT_PERCENT;
              }
              if (widget.mMatchConstraintPercentHeight < 1 && vertical == MATCH_CONSTRAINT) {
                  widget.mMatchConstraintDefaultHeight = MATCH_CONSTRAINT_PERCENT;
              }
              if (widget.getDimensionRatio() > 0) {
                  if (horizontal == MATCH_CONSTRAINT
                          && (vertical == WRAP_CONTENT || vertical == FIXED)) {
                      widget.mMatchConstraintDefaultWidth = MATCH_CONSTRAINT_RATIO;
                  } else if (vertical == MATCH_CONSTRAINT
                          && (horizontal == WRAP_CONTENT || horizontal == FIXED)) {
                      widget.mMatchConstraintDefaultHeight = MATCH_CONSTRAINT_RATIO;
                  } else if (horizontal == MATCH_CONSTRAINT && vertical == MATCH_CONSTRAINT) {
                      if (widget.mMatchConstraintDefaultWidth == MATCH_CONSTRAINT_SPREAD) {
                          widget.mMatchConstraintDefaultWidth = MATCH_CONSTRAINT_RATIO;
                      }
                      if (widget.mMatchConstraintDefaultHeight == MATCH_CONSTRAINT_SPREAD) {
                          widget.mMatchConstraintDefaultHeight = MATCH_CONSTRAINT_RATIO;
                      }
                  }
              }
  
              if (horizontal == MATCH_CONSTRAINT
                      && widget.mMatchConstraintDefaultWidth == MATCH_CONSTRAINT_WRAP) {
                  if (widget.mLeft.mTarget == null || widget.mRight.mTarget == null) {
                      horizontal = WRAP_CONTENT;
                  }
              }
              if (vertical == MATCH_CONSTRAINT
                      && widget.mMatchConstraintDefaultHeight == MATCH_CONSTRAINT_WRAP) {
                  if (widget.mTop.mTarget == null || widget.mBottom.mTarget == null) {
                      vertical = WRAP_CONTENT;
                  }
              }
  
              widget.mHorizontalRun.mDimensionBehavior = horizontal;
              widget.mHorizontalRun.matchConstraintsType = widget.mMatchConstraintDefaultWidth;
              widget.mVerticalRun.mDimensionBehavior = vertical;
              widget.mVerticalRun.matchConstraintsType = widget.mMatchConstraintDefaultHeight;
  
              if ((horizontal == MATCH_PARENT || horizontal == FIXED || horizontal == WRAP_CONTENT)
                      && (vertical == MATCH_PARENT
                      || vertical == FIXED || vertical == WRAP_CONTENT)) {
                  int width = widget.getWidth();
                  if (horizontal == MATCH_PARENT) {
                      width = constraintWidgetContainer.getWidth()
                              - widget.mLeft.mMargin - widget.mRight.mMargin;
                      horizontal = FIXED;
                  }
                  int height = widget.getHeight();
                  if (vertical == MATCH_PARENT) {
                      height = constraintWidgetContainer.getHeight()
                              - widget.mTop.mMargin - widget.mBottom.mMargin;
                      vertical = FIXED;
                  }
                  measure(widget, horizontal, width, vertical, height);
                  widget.mHorizontalRun.mDimension.resolve(widget.getWidth());
                  widget.mVerticalRun.mDimension.resolve(widget.getHeight());
                  widget.measured = true;
                  continue;
              }
  
              if (horizontal == MATCH_CONSTRAINT && (vertical == WRAP_CONTENT || vertical == FIXED)) {
                  if (widget.mMatchConstraintDefaultWidth == MATCH_CONSTRAINT_RATIO) {
                      if (vertical == WRAP_CONTENT) {
                          measure(widget, WRAP_CONTENT, 0, WRAP_CONTENT, 0);
                      }
                      int height = widget.getHeight();
                      int width = (int) (height * widget.mDimensionRatio + 0.5f);
                      measure(widget, FIXED, width, FIXED, height);
                      widget.mHorizontalRun.mDimension.resolve(widget.getWidth());
                      widget.mVerticalRun.mDimension.resolve(widget.getHeight());
                      widget.measured = true;
                      continue;
                  } else if (widget.mMatchConstraintDefaultWidth == MATCH_CONSTRAINT_WRAP) {
                      measure(widget, WRAP_CONTENT, 0, vertical, 0);
                      widget.mHorizontalRun.mDimension.wrapValue = widget.getWidth();
                      continue;
                  } else if (widget.mMatchConstraintDefaultWidth
                          == ConstraintWidget.MATCH_CONSTRAINT_PERCENT) {
                      if (constraintWidgetContainer.mListDimensionBehaviors[HORIZONTAL] == FIXED
                              || constraintWidgetContainer.mListDimensionBehaviors[HORIZONTAL]
                              == MATCH_PARENT) {
                          float percent = widget.mMatchConstraintPercentWidth;
                          int width = (int) (0.5f + percent * constraintWidgetContainer.getWidth());
                          int height = widget.getHeight();
                          measure(widget, FIXED, width, vertical, height);
                          widget.mHorizontalRun.mDimension.resolve(widget.getWidth());
                          widget.mVerticalRun.mDimension.resolve(widget.getHeight());
                          widget.measured = true;
                          continue;
                      }
                  } else {
                      // let's verify we have both constraints
                      if (widget.mListAnchors[ConstraintWidget.ANCHOR_LEFT].mTarget == null
                              || widget.mListAnchors[ConstraintWidget.ANCHOR_RIGHT].mTarget == null) {
                          measure(widget, WRAP_CONTENT, 0, vertical, 0);
                          widget.mHorizontalRun.mDimension.resolve(widget.getWidth());
                          widget.mVerticalRun.mDimension.resolve(widget.getHeight());
                          widget.measured = true;
                          continue;
                      }
                  }
              }
              if (vertical == MATCH_CONSTRAINT
                      && (horizontal == WRAP_CONTENT || horizontal == FIXED)) {
                  if (widget.mMatchConstraintDefaultHeight == MATCH_CONSTRAINT_RATIO) {
                      if (horizontal == WRAP_CONTENT) {
                          measure(widget, WRAP_CONTENT, 0, WRAP_CONTENT, 0);
                      }
                      int width = widget.getWidth();
                      float ratio = widget.mDimensionRatio;
                      if (widget.getDimensionRatioSide() == UNKNOWN) {
                          ratio = 1f / ratio;
                      }
                      int height = (int) (width * ratio + 0.5f);
  
                      measure(widget, FIXED, width, FIXED, height);
                      widget.mHorizontalRun.mDimension.resolve(widget.getWidth());
                      widget.mVerticalRun.mDimension.resolve(widget.getHeight());
                      widget.measured = true;
                      continue;
                  } else if (widget.mMatchConstraintDefaultHeight == MATCH_CONSTRAINT_WRAP) {
                      measure(widget, horizontal, 0, WRAP_CONTENT, 0);
                      widget.mVerticalRun.mDimension.wrapValue = widget.getHeight();
                      continue;
                  } else if (widget.mMatchConstraintDefaultHeight
                          == ConstraintWidget.MATCH_CONSTRAINT_PERCENT) {
                      if (constraintWidgetContainer.mListDimensionBehaviors[VERTICAL] == FIXED
                              || constraintWidgetContainer.mListDimensionBehaviors[VERTICAL]
                              == MATCH_PARENT) {
                          float percent = widget.mMatchConstraintPercentHeight;
                          int width = widget.getWidth();
                          int height = (int) (0.5f + percent * constraintWidgetContainer.getHeight());
                          measure(widget, horizontal, width, FIXED, height);
                          widget.mHorizontalRun.mDimension.resolve(widget.getWidth());
                          widget.mVerticalRun.mDimension.resolve(widget.getHeight());
                          widget.measured = true;
                          continue;
                      }
                  } else {
                      // let's verify we have both constraints
                      if (widget.mListAnchors[ConstraintWidget.ANCHOR_TOP].mTarget == null
                              || widget.mListAnchors[ConstraintWidget.ANCHOR_BOTTOM].mTarget
                              == null) {
                          measure(widget, WRAP_CONTENT, 0, vertical, 0);
                          widget.mHorizontalRun.mDimension.resolve(widget.getWidth());
                          widget.mVerticalRun.mDimension.resolve(widget.getHeight());
                          widget.measured = true;
                          continue;
                      }
                  }
              }
              if (horizontal == MATCH_CONSTRAINT && vertical == MATCH_CONSTRAINT) {
                  if (widget.mMatchConstraintDefaultWidth == MATCH_CONSTRAINT_WRAP
                          || widget.mMatchConstraintDefaultHeight == MATCH_CONSTRAINT_WRAP) {
                      measure(widget, WRAP_CONTENT, 0, WRAP_CONTENT, 0);
                      widget.mHorizontalRun.mDimension.wrapValue = widget.getWidth();
                      widget.mVerticalRun.mDimension.wrapValue = widget.getHeight();
                  } else if (widget.mMatchConstraintDefaultHeight
                          == ConstraintWidget.MATCH_CONSTRAINT_PERCENT
                          && widget.mMatchConstraintDefaultWidth
                          == ConstraintWidget.MATCH_CONSTRAINT_PERCENT
                          && constraintWidgetContainer.mListDimensionBehaviors[HORIZONTAL] == FIXED
                          && constraintWidgetContainer.mListDimensionBehaviors[VERTICAL] == FIXED) {
                      float horizPercent = widget.mMatchConstraintPercentWidth;
                      float vertPercent = widget.mMatchConstraintPercentHeight;
                      int width = (int) (0.5f + horizPercent * constraintWidgetContainer.getWidth());
                      int height = (int) (0.5f + vertPercent * constraintWidgetContainer.getHeight());
                      measure(widget, FIXED, width, FIXED, height);
                      widget.mHorizontalRun.mDimension.resolve(widget.getWidth());
                      widget.mVerticalRun.mDimension.resolve(widget.getHeight());
                      widget.measured = true;
                  }
              }
          }
          return false;
      }
  
      // @TODO: add description
      public void measureWidgets() {
          for (ConstraintWidget widget : mWidgetcontainer.mChildren) {
              if (widget.measured) {
                  continue;
              }
              ConstraintWidget.DimensionBehaviour horiz = widget.mListDimensionBehaviors[HORIZONTAL];
              ConstraintWidget.DimensionBehaviour vert = widget.mListDimensionBehaviors[VERTICAL];
              int horizMatchConstraintsType = widget.mMatchConstraintDefaultWidth;
              int vertMatchConstraintsType = widget.mMatchConstraintDefaultHeight;
  
              boolean horizWrap = horiz == WRAP_CONTENT
                      || (horiz == MATCH_CONSTRAINT
                      && horizMatchConstraintsType == MATCH_CONSTRAINT_WRAP);
  
              boolean vertWrap = vert == WRAP_CONTENT
                      || (vert == MATCH_CONSTRAINT
                      && vertMatchConstraintsType == MATCH_CONSTRAINT_WRAP);
  
              boolean horizResolved = widget.mHorizontalRun.mDimension.resolved;
              boolean vertResolved = widget.mVerticalRun.mDimension.resolved;
  
              if (horizResolved && vertResolved) {
                  measure(widget, FIXED, widget.mHorizontalRun.mDimension.value,
                          FIXED, widget.mVerticalRun.mDimension.value);
                  widget.measured = true;
              } else if (horizResolved && vertWrap) {
                  measure(widget, FIXED, widget.mHorizontalRun.mDimension.value,
                          WRAP_CONTENT, widget.mVerticalRun.mDimension.value);
                  if (vert == MATCH_CONSTRAINT) {
                      widget.mVerticalRun.mDimension.wrapValue = widget.getHeight();
                  } else {
                      widget.mVerticalRun.mDimension.resolve(widget.getHeight());
                      widget.measured = true;
                  }
              } else if (vertResolved && horizWrap) {
                  measure(widget, WRAP_CONTENT, widget.mHorizontalRun.mDimension.value,
                          FIXED, widget.mVerticalRun.mDimension.value);
                  if (horiz == MATCH_CONSTRAINT) {
                      widget.mHorizontalRun.mDimension.wrapValue = widget.getWidth();
                  } else {
                      widget.mHorizontalRun.mDimension.resolve(widget.getWidth());
                      widget.measured = true;
                  }
              }
              if (widget.measured && widget.mVerticalRun.mBaselineDimension != null) {
                  widget.mVerticalRun.mBaselineDimension.resolve(widget.getBaselineDistance());
              }
          }
      }
  
      /**
       * Invalidate the graph of constraints
       */
      public void invalidateGraph() {
          mNeedBuildGraph = true;
      }
  
      /**
       * Mark the widgets as needing to be remeasured
       */
      public void invalidateMeasures() {
          mNeedRedoMeasures = true;
      }
  
      ArrayList<RunGroup> mGroups = new ArrayList<>();
  
      // @TODO: add description
      public void buildGraph() {
          // First, let's identify the overall dependency graph
          buildGraph(mRuns);
  
          if (USE_GROUPS) {
              mGroups.clear();
              // Then get the horizontal and vertical groups
              RunGroup.index = 0;
              findGroup(mWidgetcontainer.mHorizontalRun, HORIZONTAL, mGroups);
              findGroup(mWidgetcontainer.mVerticalRun, VERTICAL, mGroups);
          }
          mNeedBuildGraph = false;
      }
  
      // @TODO: add description
      public void buildGraph(ArrayList<WidgetRun> runs) {
          runs.clear();
          mContainer.mHorizontalRun.clear();
          mContainer.mVerticalRun.clear();
          runs.add(mContainer.mHorizontalRun);
          runs.add(mContainer.mVerticalRun);
          HashSet<ChainRun> chainRuns = null;
          for (ConstraintWidget widget : mContainer.mChildren) {
              if (widget instanceof Guideline) {
                  runs.add(new GuidelineReference(widget));
                  continue;
              }
              if (widget.isInHorizontalChain()) {
                  if (widget.horizontalChainRun == null) {
                      // build the horizontal chain
                      widget.horizontalChainRun = new ChainRun(widget, HORIZONTAL);
                  }
                  if (chainRuns == null) {
                      chainRuns = new HashSet<>();
                  }
                  chainRuns.add(widget.horizontalChainRun);
              } else {
                  runs.add(widget.mHorizontalRun);
              }
              if (widget.isInVerticalChain()) {
                  if (widget.verticalChainRun == null) {
                      // build the vertical chain
                      widget.verticalChainRun = new ChainRun(widget, VERTICAL);
                  }
                  if (chainRuns == null) {
                      chainRuns = new HashSet<>();
                  }
                  chainRuns.add(widget.verticalChainRun);
              } else {
                  runs.add(widget.mVerticalRun);
              }
              if (widget instanceof HelperWidget) {
                  runs.add(new HelperReferences(widget));
              }
          }
          if (chainRuns != null) {
              runs.addAll(chainRuns);
          }
          for (WidgetRun run : runs) {
              run.clear();
          }
          for (WidgetRun run : runs) {
              if (run.mWidget == mContainer) {
                  continue;
              }
              run.apply();
          }
          if (DEBUG) {
              displayGraph();
          }
      }
  
  
      private void displayGraph() {
          String content = "digraph {\n";
          for (WidgetRun run : mRuns) {
              content = generateDisplayGraph(run, content);
          }
          content += "\n}\n";
          System.out.println("content:<<\n" + content + "\n>>");
      }
  
      private void applyGroup(DependencyNode node,
              int orientation,
              int direction,
              DependencyNode end,
              ArrayList<RunGroup> groups,
              RunGroup group) {
          WidgetRun run = node.mRun;
          if (run.mRunGroup != null
                  || run == mWidgetcontainer.mHorizontalRun || run == mWidgetcontainer.mVerticalRun) {
              return;
          }
  
          if (group == null) {
              group = new RunGroup(run, direction);
              groups.add(group);
          }
  
          run.mRunGroup = group;
          group.add(run);
          for (Dependency dependent : run.start.mDependencies) {
              if (dependent instanceof DependencyNode) {
                  applyGroup((DependencyNode) dependent,
                          orientation, RunGroup.START, end, groups, group);
              }
          }
          for (Dependency dependent : run.end.mDependencies) {
              if (dependent instanceof DependencyNode) {
                  applyGroup((DependencyNode) dependent,
                          orientation, RunGroup.END, end, groups, group);
              }
          }
          if (orientation == VERTICAL && run instanceof VerticalWidgetRun) {
              for (Dependency dependent : ((VerticalWidgetRun) run).baseline.mDependencies) {
                  if (dependent instanceof DependencyNode) {
                      applyGroup((DependencyNode) dependent,
                              orientation, RunGroup.BASELINE, end, groups, group);
                  }
              }
          }
          for (DependencyNode target : run.start.mTargets) {
              if (target == end) {
                  group.dual = true;
              }
              applyGroup(target, orientation, RunGroup.START, end, groups, group);
          }
          for (DependencyNode target : run.end.mTargets) {
              if (target == end) {
                  group.dual = true;
              }
              applyGroup(target, orientation, RunGroup.END, end, groups, group);
          }
          if (orientation == VERTICAL && run instanceof VerticalWidgetRun) {
              for (DependencyNode target : ((VerticalWidgetRun) run).baseline.mTargets) {
                  applyGroup(target, orientation, RunGroup.BASELINE, end, groups, group);
              }
          }
      }
  
      private void findGroup(WidgetRun run, int orientation, ArrayList<RunGroup> groups) {
          for (Dependency dependent : run.start.mDependencies) {
              if (dependent instanceof DependencyNode) {
                  DependencyNode node = (DependencyNode) dependent;
                  applyGroup(node, orientation, RunGroup.START, run.end, groups, null);
              } else if (dependent instanceof WidgetRun) {
                  WidgetRun dependentRun = (WidgetRun) dependent;
                  applyGroup(dependentRun.start, orientation, RunGroup.START, run.end, groups, null);
              }
          }
          for (Dependency dependent : run.end.mDependencies) {
              if (dependent instanceof DependencyNode) {
                  DependencyNode node = (DependencyNode) dependent;
                  applyGroup(node, orientation, RunGroup.END, run.start, groups, null);
              } else if (dependent instanceof WidgetRun) {
                  WidgetRun dependentRun = (WidgetRun) dependent;
                  applyGroup(dependentRun.end, orientation, RunGroup.END, run.start, groups, null);
              }
          }
          if (orientation == VERTICAL) {
              for (Dependency dependent : ((VerticalWidgetRun) run).baseline.mDependencies) {
                  if (dependent instanceof DependencyNode) {
                      DependencyNode node = (DependencyNode) dependent;
                      applyGroup(node, orientation, RunGroup.BASELINE, null, groups, null);
                  }
              }
          }
      }
  
  
      private String generateDisplayNode(DependencyNode node,
              boolean centeredConnection,
              String content) {
          StringBuilder contentBuilder = new StringBuilder(content);
          for (DependencyNode target : node.mTargets) {
              String constraint = "\n" + node.name();
              constraint += " -> " + target.name();
              if (node.mMargin > 0 || centeredConnection || node.mRun instanceof HelperReferences) {
                  constraint += "[";
                  if (node.mMargin > 0) {
                      constraint += "label=\"" + node.mMargin + "\"";
                      if (centeredConnection) {
                          constraint += ",";
                      }
                  }
                  if (centeredConnection) {
                      constraint += " style=dashed ";
                  }
                  if (node.mRun instanceof HelperReferences) {
                      constraint += " style=bold,color=gray ";
                  }
                  constraint += "]";
              }
              constraint += "\n";
              contentBuilder.append(constraint);
          }
          content = contentBuilder.toString();
  //        for (DependencyNode dependency : node.dependencies) {
  //            content = generateDisplayNode(dependency, content);
  //        }
          return content;
      }
  
      private String nodeDefinition(WidgetRun run) {
          int orientation = run instanceof VerticalWidgetRun ? VERTICAL : HORIZONTAL;
          String name = run.mWidget.getDebugName();
          StringBuilder definition = new StringBuilder(name);
          ConstraintWidget.DimensionBehaviour behaviour =
                  orientation == HORIZONTAL ? run.mWidget.getHorizontalDimensionBehaviour()
                          : run.mWidget.getVerticalDimensionBehaviour();
          RunGroup runGroup = run.mRunGroup;
  
          if (orientation == HORIZONTAL) {
              definition.append("_HORIZONTAL");
          } else {
              definition.append("_VERTICAL");
          }
          definition.append(" [shape=none, label=<");
          definition.append("<TABLE BORDER=\"0\" CELLSPACING=\"0\" CELLPADDING=\"2\">");
          definition.append("  <TR>");
          if (orientation == HORIZONTAL) {
              definition.append("    <TD ");
              if (run.start.resolved) {
                  definition.append(" BGCOLOR=\"green\"");
              }
              definition.append(" PORT=\"LEFT\" BORDER=\"1\">L</TD>");
          } else {
              definition.append("    <TD ");
              if (run.start.resolved) {
                  definition.append(" BGCOLOR=\"green\"");
              }
              definition.append(" PORT=\"TOP\" BORDER=\"1\">T</TD>");
          }
          definition.append("    <TD BORDER=\"1\" ");
          if (run.mDimension.resolved && !run.mWidget.measured) {
              definition.append(" BGCOLOR=\"green\" ");
          } else if (run.mDimension.resolved) {
              definition.append(" BGCOLOR=\"lightgray\" ");
          } else if (run.mWidget.measured) {
              definition.append(" BGCOLOR=\"yellow\" ");
          }
          if (behaviour == MATCH_CONSTRAINT) {
              definition.append("style=\"dashed\"");
          }
          definition.append(">");
          definition.append(name);
          if (runGroup != null) {
              definition.append(" [");
              definition.append(runGroup.mGroupIndex + 1);
              definition.append("/");
              definition.append(RunGroup.index);
              definition.append("]");
          }
          definition.append(" </TD>");
          if (orientation == HORIZONTAL) {
              definition.append("    <TD ");
              if (run.end.resolved) {
                  definition.append(" BGCOLOR=\"green\"");
              }
              definition.append(" PORT=\"RIGHT\" BORDER=\"1\">R</TD>");
          } else {
              definition.append("    <TD ");
              if (((VerticalWidgetRun) run).baseline.resolved) {
                  definition.append(" BGCOLOR=\"green\"");
              }
              definition.append(" PORT=\"BASELINE\" BORDER=\"1\">b</TD>");
              definition.append("    <TD ");
              if (run.end.resolved) {
                  definition.append(" BGCOLOR=\"green\"");
              }
              definition.append(" PORT=\"BOTTOM\" BORDER=\"1\">B</TD>");
          }
          definition.append("  </TR></TABLE>");
          definition.append(">];\n");
          return definition.toString();
      }
  
      private String generateChainDisplayGraph(ChainRun chain, String content) {
          int orientation = chain.orientation;
          StringBuilder subgroup = new StringBuilder("subgraph ");
          subgroup.append("cluster_");
          subgroup.append(chain.mWidget.getDebugName());
          if (orientation == HORIZONTAL) {
              subgroup.append("_h");
          } else {
              subgroup.append("_v");
          }
          subgroup.append(" {\n");
          String definitions = "";
          for (WidgetRun run : chain.mWidgets) {
              subgroup.append(run.mWidget.getDebugName());
              if (orientation == HORIZONTAL) {
                  subgroup.append("_HORIZONTAL");
              } else {
                  subgroup.append("_VERTICAL");
              }
              subgroup.append(";\n");
              definitions = generateDisplayGraph(run, definitions);
          }
          subgroup.append("}\n");
          return content + definitions + subgroup;
      }
  
      private boolean isCenteredConnection(DependencyNode start, DependencyNode end) {
          int startTargets = 0;
          int endTargets = 0;
          for (DependencyNode s : start.mTargets) {
              if (s != end) {
                  startTargets++;
              }
          }
          for (DependencyNode e : end.mTargets) {
              if (e != start) {
                  endTargets++;
              }
          }
          return startTargets > 0 && endTargets > 0;
      }
  
      private String generateDisplayGraph(WidgetRun root, String content) {
          DependencyNode start = root.start;
          DependencyNode end = root.end;
          StringBuilder sb = new StringBuilder(content);
  
          if (!(root instanceof HelperReferences) && start.mDependencies.isEmpty()
                  && end.mDependencies.isEmpty() && start.mTargets.isEmpty()
                  && end.mTargets.isEmpty()) {
              return content;
          }
          sb.append(nodeDefinition(root));
  
          boolean centeredConnection = isCenteredConnection(start, end);
          content = generateDisplayNode(start, centeredConnection, content);
          content = generateDisplayNode(end, centeredConnection, content);
          if (root instanceof VerticalWidgetRun) {
              DependencyNode baseline = ((VerticalWidgetRun) root).baseline;
              content = generateDisplayNode(baseline, centeredConnection, content);
          }
  
          if (root instanceof HorizontalWidgetRun
                  || (root instanceof ChainRun && ((ChainRun) root).orientation == HORIZONTAL)) {
              ConstraintWidget.DimensionBehaviour behaviour =
                      root.mWidget.getHorizontalDimensionBehaviour();
              if (behaviour == ConstraintWidget.DimensionBehaviour.FIXED
                      || behaviour == ConstraintWidget.DimensionBehaviour.WRAP_CONTENT) {
                  if (!start.mTargets.isEmpty() && end.mTargets.isEmpty()) {
                      sb.append("\n");
                      sb.append(end.name());
                      sb.append(" -> ");
                      sb.append(start.name());
                      sb.append("\n");
                  } else if (start.mTargets.isEmpty() && !end.mTargets.isEmpty()) {
                      sb.append("\n");
                      sb.append(start.name());
                      sb.append(" -> ");
                      sb.append(end.name());
                      sb.append("\n");
                  }
              } else {
                  if (behaviour == MATCH_CONSTRAINT && root.mWidget.getDimensionRatio() > 0) {
                      sb.append("\n");
                      sb.append(root.mWidget.getDebugName());
                      sb.append("_HORIZONTAL -> ");
                      sb.append(root.mWidget.getDebugName());
                      sb.append("_VERTICAL;\n");
                  }
              }
          } else if (root instanceof VerticalWidgetRun
                  || (root instanceof ChainRun && ((ChainRun) root).orientation == VERTICAL)) {
              ConstraintWidget.DimensionBehaviour behaviour =
                      root.mWidget.getVerticalDimensionBehaviour();
              if (behaviour == ConstraintWidget.DimensionBehaviour.FIXED
                      || behaviour == ConstraintWidget.DimensionBehaviour.WRAP_CONTENT) {
                  if (!start.mTargets.isEmpty() && end.mTargets.isEmpty()) {
                      sb.append("\n");
                      sb.append(end.name());
                      sb.append(" -> ");
                      sb.append(start.name());
                      sb.append("\n");
                  } else if (start.mTargets.isEmpty() && !end.mTargets.isEmpty()) {
                      sb.append("\n");
                      sb.append(start.name());
                      sb.append(" -> ");
                      sb.append(end.name());
                      sb.append("\n");
                  }
              } else {
                  if (behaviour == MATCH_CONSTRAINT && root.mWidget.getDimensionRatio() > 0) {
                      sb.append("\n");
                      sb.append(root.mWidget.getDebugName());
                      sb.append("_VERTICAL -> ");
                      sb.append(root.mWidget.getDebugName());
                      sb.append("_HORIZONTAL;\n");
                  }
              }
          }
          if (root instanceof ChainRun) {
              return generateChainDisplayGraph((ChainRun) root, content);
          }
          return sb.toString();
      }
  
  }
  