content: /*
   * Copyright (C) 2018 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 android.graphics.text;
  
  import android.annotation.NonNull;
  import android.graphics.text.Primitive.PrimitiveType;
  
  import java.util.ArrayList;
  import java.util.Collections;
  import java.util.List;
  import java.util.ListIterator;
  
  import static android.graphics.text.Primitive.PrimitiveType.PENALTY_INFINITY;
  
  
  // Based on the native implementation of OptimizingLineBreaker in
  // frameworks/base/core/jni/android_text_StaticLayout.cpp revision b808260
  /**
   * A more complex version of line breaking where we try to prevent the right edge from being too
   * jagged.
   */
  public class OptimizingLineBreaker extends BaseLineBreaker {
  
      public OptimizingLineBreaker(@NonNull List<Primitive> primitives, @NonNull LineWidth lineWidth,
              @NonNull TabStops tabStops) {
          super(primitives, lineWidth, tabStops);
      }
  
      @Override
      public Result computeBreaks() {
          Result result = new Result();
          int numBreaks = mPrimitives.size();
          assert numBreaks > 0;
          if (numBreaks == 1) {
              // This can be true only if it's an empty paragraph.
              Primitive p = mPrimitives.get(0);
              assert p.type == PrimitiveType.PENALTY;
              result.mLineBreakOffset.add(0);
              result.mLineWidths.add(p.width);
              result.mLineAscents.add(0f);
              result.mLineDescents.add(0f);
              result.mLineFlags.add(0);
              return result;
          }
          Node[] opt = new Node[numBreaks];
          opt[0] = new Node(-1, 0, 0, 0, false);
          opt[numBreaks - 1] = new Node(-1, 0, 0, 0, false);
  
          ArrayList<Integer> active = new ArrayList<Integer>();
          active.add(0);
          int lastBreak = 0;
          for (int i = 0; i < numBreaks; i++) {
              Primitive p = mPrimitives.get(i);
              if (p.type == PrimitiveType.PENALTY) {
                  boolean finalBreak = (i + 1 == numBreaks);
                  Node bestBreak = null;
  
                  for (ListIterator<Integer> it = active.listIterator(); it.hasNext();
                          /* incrementing done in loop */) {
                      int pos = it.next();
                      int lines = opt[pos].mPrevCount;
                      float maxWidth = mLineWidth.getLineWidth(lines);
                      // we have to compute metrics every time --
                      // we can't really pre-compute this stuff and just deal with breaks
                      // because of the way tab characters work, this makes it computationally
                      // harder, but this way, we can still optimize while treating tab characters
                      // correctly
                      LineMetrics lineMetrics = computeMetrics(pos, i);
                      if (lineMetrics.mPrintedWidth <= maxWidth) {
                          float demerits = computeDemerits(maxWidth, lineMetrics.mPrintedWidth,
                                  finalBreak, p.penalty) + opt[pos].mDemerits;
                          if (bestBreak == null || demerits < bestBreak.mDemerits) {
                              if (bestBreak == null) {
                                  bestBreak = new Node(pos, opt[pos].mPrevCount + 1, demerits,
                                          lineMetrics.mPrintedWidth, lineMetrics.mHasTabs);
                              } else {
                                  bestBreak.mPrev = pos;
                                  bestBreak.mPrevCount = opt[pos].mPrevCount + 1;
                                  bestBreak.mDemerits = demerits;
                                  bestBreak.mWidth = lineMetrics.mPrintedWidth;
                                  bestBreak.mHasTabs = lineMetrics.mHasTabs;
                              }
                          }
                      } else {
                          it.remove();
                      }
                  }
                  if (p.penalty == -PENALTY_INFINITY) {
                      active.clear();
                  }
                  if (bestBreak != null) {
                      opt[i] = bestBreak;
                      active.add(i);
                      lastBreak = i;
                  }
                  if (active.isEmpty()) {
                      // we can't give up!
                      LineMetrics lineMetrics = new LineMetrics();
                      int lines = opt[lastBreak].mPrevCount;
                      float maxWidth = mLineWidth.getLineWidth(lines);
                      int breakIndex = desperateBreak(lastBreak, numBreaks, maxWidth, lineMetrics);
                      opt[breakIndex] = new Node(lastBreak, lines + 1, 0 /*doesn't matter*/,
                              lineMetrics.mWidth, lineMetrics.mHasTabs);
                      active.add(breakIndex);
                      lastBreak = breakIndex;
                      i = breakIndex; // incremented by i++
                  }
              }
          }
  
          int idx = numBreaks - 1;
          while (opt[idx].mPrev != -1) {
              result.mLineBreakOffset.add(mPrimitives.get(idx).location);
              result.mLineWidths.add(opt[idx].mWidth);
              result.mLineAscents.add(0f);
              result.mLineDescents.add(0f);
              result.mLineFlags.add(opt[idx].mHasTabs ? TAB_MASK : 0);
              idx = opt[idx].mPrev;
          }
  
          Collections.reverse(result.mLineBreakOffset);
          Collections.reverse(result.mLineWidths);
          Collections.reverse(result.mLineAscents);
          Collections.reverse(result.mLineDescents);
          Collections.reverse(result.mLineFlags);
          return result;
      }
  
      @NonNull
      private LineMetrics computeMetrics(int start, int end) {
          boolean f = false;
          float w = 0, pw = 0;
          for (int i = start; i < end; i++) {
              Primitive p = mPrimitives.get(i);
              if (p.type == PrimitiveType.BOX || p.type == PrimitiveType.GLUE) {
                  w += p.width;
                  if (p.type == PrimitiveType.BOX) {
                      pw = w;
                  }
              } else if (p.type == PrimitiveType.VARIABLE) {
                  w = mTabStops.width(w);
                  f = true;
              }
          }
          return new LineMetrics(w, pw, f);
      }
  
      private static float computeDemerits(float maxWidth, float width, boolean finalBreak,
              float penalty) {
          float deviation = finalBreak ? 0 : maxWidth - width;
          return (deviation * deviation) + penalty;
      }
  
      /**
       * @return the last break position or -1 if failed.
       */
      @SuppressWarnings("ConstantConditions")  // method too complex to be analyzed.
      private int desperateBreak(int start, int limit, float maxWidth,
              @NonNull LineMetrics lineMetrics) {
          float w = 0, pw = 0;
          boolean breakFound = false;
          int breakIndex = 0, firstTabIndex = Integer.MAX_VALUE;
          for (int i = start; i < limit; i++) {
              Primitive p = mPrimitives.get(i);
  
              if (p.type == PrimitiveType.BOX || p.type == PrimitiveType.GLUE) {
                  w += p.width;
                  if (p.type == PrimitiveType.BOX) {
                      pw = w;
                  }
              } else if (p.type == PrimitiveType.VARIABLE) {
                  w = mTabStops.width(w);
                  firstTabIndex = Math.min(firstTabIndex, i);
              }
  
              if (pw > maxWidth && breakFound) {
                  break;
              }
  
              // must make progress
              if (i > start &&
                      (p.type == PrimitiveType.PENALTY || p.type == PrimitiveType.WORD_BREAK)) {
                  breakFound = true;
                  breakIndex = i;
              }
          }
  
          if (breakFound) {
              lineMetrics.mWidth = w;
              lineMetrics.mPrintedWidth = pw;
              lineMetrics.mHasTabs = (start <= firstTabIndex && firstTabIndex < breakIndex);
              return breakIndex;
          } else {
              return -1;
          }
      }
  
      private static class LineMetrics {
          /** Actual width of the line. */
          float mWidth;
          /** Width of the line minus trailing whitespace. */
          float mPrintedWidth;
          boolean mHasTabs;
  
          public LineMetrics() {
          }
  
          public LineMetrics(float width, float printedWidth, boolean hasTabs) {
              mWidth = width;
              mPrintedWidth = printedWidth;
              mHasTabs = hasTabs;
          }
      }
  
      /**
       * A struct to store the info about a break.
       */
      @SuppressWarnings("SpellCheckingInspection")  // For the word struct.
      private static class Node {
          // -1 for the first node.
          int mPrev;
          // number of breaks so far.
          int mPrevCount;
          float mDemerits;
          float mWidth;
          boolean mHasTabs;
  
          public Node(int prev, int prevCount, float demerits, float width, boolean hasTabs) {
              mPrev = prev;
              mPrevCount = prevCount;
              mDemerits = demerits;
              mWidth = width;
              mHasTabs = hasTabs;
          }
      }
  }
  