1/*
2 * Copyright (C) 2014 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
17package android.text;
18
19import android.annotation.NonNull;
20import android.text.Primitive.PrimitiveType;
21import android.text.StaticLayout.LineBreaks;
22
23import java.util.ArrayList;
24import java.util.List;
25import java.util.ListIterator;
26
27import static android.text.Primitive.PrimitiveType.PENALTY_INFINITY;
28
29
30// Based on the native implementation of OptimizingLineBreaker in
31// frameworks/base/core/jni/android_text_StaticLayout.cpp revision b808260
32/**
33 * A more complex version of line breaking where we try to prevent the right edge from being too
34 * jagged.
35 */
36public class OptimizingLineBreaker extends LineBreaker {
37
38    public OptimizingLineBreaker(@NonNull List<Primitive> primitives, @NonNull LineWidth lineWidth,
39            @NonNull TabStops tabStops) {
40        super(primitives, lineWidth, tabStops);
41    }
42
43    @Override
44    public void computeBreaks(@NonNull LineBreaks breakInfo) {
45        int numBreaks = mPrimitives.size();
46        assert numBreaks > 0;
47        if (numBreaks == 1) {
48            // This can be true only if it's an empty paragraph.
49            Primitive p = mPrimitives.get(0);
50            assert p.type == PrimitiveType.PENALTY;
51            breakInfo.breaks = new int[]{0};
52            breakInfo.widths = new float[]{p.width};
53            breakInfo.flags = new int[]{0};
54            return;
55        }
56        Node[] opt = new Node[numBreaks];
57        opt[0] = new Node(-1, 0, 0, 0, false);
58        opt[numBreaks - 1] = new Node(-1, 0, 0, 0, false);
59
60        ArrayList<Integer> active = new ArrayList<Integer>();
61        active.add(0);
62        int lastBreak = 0;
63        for (int i = 0; i < numBreaks; i++) {
64            Primitive p = mPrimitives.get(i);
65            if (p.type == PrimitiveType.PENALTY) {
66                boolean finalBreak = (i + 1 == numBreaks);
67                Node bestBreak = null;
68
69                for (ListIterator<Integer> it = active.listIterator(); it.hasNext();
70                        /* incrementing done in loop */) {
71                    int pos = it.next();
72                    int lines = opt[pos].mPrevCount;
73                    float maxWidth = mLineWidth.getLineWidth(lines);
74                    // we have to compute metrics every time --
75                    // we can't really pre-compute this stuff and just deal with breaks
76                    // because of the way tab characters work, this makes it computationally
77                    // harder, but this way, we can still optimize while treating tab characters
78                    // correctly
79                    LineMetrics lineMetrics = computeMetrics(pos, i);
80                    if (lineMetrics.mPrintedWidth <= maxWidth) {
81                        float demerits = computeDemerits(maxWidth, lineMetrics.mPrintedWidth,
82                                finalBreak, p.penalty) + opt[pos].mDemerits;
83                        if (bestBreak == null || demerits < bestBreak.mDemerits) {
84                            if (bestBreak == null) {
85                                bestBreak = new Node(pos, opt[pos].mPrevCount + 1, demerits,
86                                        lineMetrics.mPrintedWidth, lineMetrics.mHasTabs);
87                            } else {
88                                bestBreak.mPrev = pos;
89                                bestBreak.mPrevCount = opt[pos].mPrevCount + 1;
90                                bestBreak.mDemerits = demerits;
91                                bestBreak.mWidth = lineMetrics.mPrintedWidth;
92                                bestBreak.mHasTabs = lineMetrics.mHasTabs;
93                            }
94                        }
95                    } else {
96                        it.remove();
97                    }
98                }
99                if (p.penalty == -PENALTY_INFINITY) {
100                    active.clear();
101                }
102                if (bestBreak != null) {
103                    opt[i] = bestBreak;
104                    active.add(i);
105                    lastBreak = i;
106                }
107                if (active.isEmpty()) {
108                    // we can't give up!
109                    LineMetrics lineMetrics = new LineMetrics();
110                    int lines = opt[lastBreak].mPrevCount;
111                    float maxWidth = mLineWidth.getLineWidth(lines);
112                    int breakIndex = desperateBreak(lastBreak, numBreaks, maxWidth, lineMetrics);
113                    opt[breakIndex] = new Node(lastBreak, lines + 1, 0 /*doesn't matter*/,
114                            lineMetrics.mWidth, lineMetrics.mHasTabs);
115                    active.add(breakIndex);
116                    lastBreak = breakIndex;
117                    i = breakIndex; // incremented by i++
118                }
119            }
120        }
121
122        int idx = numBreaks - 1;
123        int count = opt[idx].mPrevCount;
124        resize(breakInfo, count);
125        while (opt[idx].mPrev != -1) {
126            count--;
127            assert count >=0;
128
129            breakInfo.breaks[count] = mPrimitives.get(idx).location;
130            breakInfo.widths[count] = opt[idx].mWidth;
131            breakInfo.flags [count] = opt[idx].mHasTabs ? TAB_MASK : 0;
132            idx = opt[idx].mPrev;
133        }
134    }
135
136    private static void resize(LineBreaks lineBreaks, int size) {
137        if (lineBreaks.breaks.length == size) {
138            return;
139        }
140        int[] breaks = new int[size];
141        float[] widths = new float[size];
142        int[] flags = new int[size];
143
144        int toCopy = Math.min(size, lineBreaks.breaks.length);
145        System.arraycopy(lineBreaks.breaks, 0, breaks, 0, toCopy);
146        System.arraycopy(lineBreaks.widths, 0, widths, 0, toCopy);
147        System.arraycopy(lineBreaks.flags, 0, flags, 0, toCopy);
148
149        lineBreaks.breaks = breaks;
150        lineBreaks.widths = widths;
151        lineBreaks.flags = flags;
152    }
153
154    @NonNull
155    private LineMetrics computeMetrics(int start, int end) {
156        boolean f = false;
157        float w = 0, pw = 0;
158        for (int i = start; i < end; i++) {
159            Primitive p = mPrimitives.get(i);
160            if (p.type == PrimitiveType.BOX || p.type == PrimitiveType.GLUE) {
161                w += p.width;
162                if (p.type == PrimitiveType.BOX) {
163                    pw = w;
164                }
165            } else if (p.type == PrimitiveType.VARIABLE) {
166                w = mTabStops.width(w);
167                f = true;
168            }
169        }
170        return new LineMetrics(w, pw, f);
171    }
172
173    private static float computeDemerits(float maxWidth, float width, boolean finalBreak,
174            float penalty) {
175        float deviation = finalBreak ? 0 : maxWidth - width;
176        return (deviation * deviation) + penalty;
177    }
178
179    /**
180     * @return the last break position or -1 if failed.
181     */
182    @SuppressWarnings("ConstantConditions")  // method too complex to be analyzed.
183    private int desperateBreak(int start, int limit, float maxWidth,
184            @NonNull LineMetrics lineMetrics) {
185        float w = 0, pw = 0;
186        boolean breakFound = false;
187        int breakIndex = 0, firstTabIndex = Integer.MAX_VALUE;
188        for (int i = start; i < limit; i++) {
189            Primitive p = mPrimitives.get(i);
190
191            if (p.type == PrimitiveType.BOX || p.type == PrimitiveType.GLUE) {
192                w += p.width;
193                if (p.type == PrimitiveType.BOX) {
194                    pw = w;
195                }
196            } else if (p.type == PrimitiveType.VARIABLE) {
197                w = mTabStops.width(w);
198                firstTabIndex = Math.min(firstTabIndex, i);
199            }
200
201            if (pw > maxWidth && breakFound) {
202                break;
203            }
204
205            // must make progress
206            if (i > start &&
207                    (p.type == PrimitiveType.PENALTY || p.type == PrimitiveType.WORD_BREAK)) {
208                breakFound = true;
209                breakIndex = i;
210            }
211        }
212
213        if (breakFound) {
214            lineMetrics.mWidth = w;
215            lineMetrics.mPrintedWidth = pw;
216            lineMetrics.mHasTabs = (start <= firstTabIndex && firstTabIndex < breakIndex);
217            return breakIndex;
218        } else {
219            return -1;
220        }
221    }
222
223    private static class LineMetrics {
224        /** Actual width of the line. */
225        float mWidth;
226        /** Width of the line minus trailing whitespace. */
227        float mPrintedWidth;
228        boolean mHasTabs;
229
230        public LineMetrics() {
231        }
232
233        public LineMetrics(float width, float printedWidth, boolean hasTabs) {
234            mWidth = width;
235            mPrintedWidth = printedWidth;
236            mHasTabs = hasTabs;
237        }
238    }
239
240    /**
241     * A struct to store the info about a break.
242     */
243    @SuppressWarnings("SpellCheckingInspection")  // For the word struct.
244    private static class Node {
245        // -1 for the first node.
246        int mPrev;
247        // number of breaks so far.
248        int mPrevCount;
249        float mDemerits;
250        float mWidth;
251        boolean mHasTabs;
252
253        public Node(int prev, int prevCount, float demerits, float width, boolean hasTabs) {
254            mPrev = prev;
255            mPrevCount = prevCount;
256            mDemerits = demerits;
257            mWidth = width;
258            mHasTabs = hasTabs;
259        }
260    }
261}
262