android/text/OptimizingLineBreaker.java

/*
 * Copyright (C) 2014 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.text;

import com.android.annotations.NonNull;

import android.text.Primitive.PrimitiveType;
import android.text.StaticLayout.LineBreaks;

import java.util.ArrayList;
import java.util.List;
import java.util.ListIterator;

import static android.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 LineBreaker {

    public OptimizingLineBreaker(@NonNull List<Primitive> primitives, @NonNull LineWidth lineWidth,
            @NonNull TabStops tabStops) {
        super(primitives, lineWidth, tabStops);
    }

    @Override
    public void computeBreaks(@NonNull LineBreaks breakInfo) {
        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;
            breakInfo.breaks = new int[]{0};
            breakInfo.widths = new float[]{p.width};
            breakInfo.flags = new boolean[]{false};
            return;
        }
        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;
        int count = opt[idx].mPrevCount;
        resize(breakInfo, count);
        while (opt[idx].mPrev != -1) {
            count--;
            assert count >=0;

            breakInfo.breaks[count] = mPrimitives.get(idx).location;
            breakInfo.widths[count] = opt[idx].mWidth;
            breakInfo.flags [count] = opt[idx].mHasTabs;
            idx = opt[idx].mPrev;
        }
    }

    private static void resize(LineBreaks lineBreaks, int size) {
        if (lineBreaks.breaks.length == size) {
            return;
        }
        int[] breaks = new int[size];
        float[] widths = new float[size];
        boolean[] flags = new boolean[size];

        int toCopy = Math.min(size, lineBreaks.breaks.length);
        System.arraycopy(lineBreaks.breaks, 0, breaks, 0, toCopy);
        System.arraycopy(lineBreaks.widths, 0, widths, 0, toCopy);
        System.arraycopy(lineBreaks.flags, 0, flags, 0, toCopy);

        lineBreaks.breaks = breaks;
        lineBreaks.widths = widths;
        lineBreaks.flags = flags;
    }

    @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;
        }
    }
}