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;
25
26import static android.text.Primitive.PrimitiveType.PENALTY_INFINITY;
27
28// Based on the native implementation of GreedyLineBreaker in
29// frameworks/base/core/jni/android_text_StaticLayout.cpp revision b808260
30public class GreedyLineBreaker extends LineBreaker {
31
32    public GreedyLineBreaker(@NonNull List<Primitive> primitives, @NonNull LineWidth lineWidth,
33            @NonNull TabStops tabStops) {
34        super(primitives, lineWidth, tabStops);
35    }
36
37    @Override
38    public void computeBreaks(@NonNull LineBreaks lineBreaks) {
39        BreakInfo breakInfo = new BreakInfo();
40        int lineNum = 0;
41        float width = 0, printedWidth = 0;
42        boolean breakFound = false, goodBreakFound = false;
43        int breakIndex = 0, goodBreakIndex = 0;
44        float breakWidth = 0, goodBreakWidth = 0;
45        int firstTabIndex = Integer.MAX_VALUE;
46
47        float maxWidth = mLineWidth.getLineWidth(lineNum);
48
49        int numPrimitives = mPrimitives.size();
50        // greedily fit as many characters as possible on each line
51        // loop over all primitives, and choose the best break point
52        // (if possible, a break point without splitting a word)
53        // after going over the maximum length
54        for (int i = 0; i < numPrimitives; i++) {
55            Primitive p = mPrimitives.get(i);
56
57            // update the current line width
58            if (p.type == PrimitiveType.BOX || p.type == PrimitiveType.GLUE) {
59                width += p.width;
60                if (p.type == PrimitiveType.BOX) {
61                    printedWidth = width;
62                }
63            } else if (p.type == PrimitiveType.VARIABLE) {
64                width = mTabStops.width(width);
65                // keep track of first tab character in the region we are examining
66                // so we can determine whether or not a line contains a tab
67                firstTabIndex = Math.min(firstTabIndex, i);
68            }
69
70            // find the best break point for the characters examined so far
71            if (printedWidth > maxWidth) {
72                //noinspection StatementWithEmptyBody
73                if (breakFound || goodBreakFound) {
74                    if (goodBreakFound) {
75                        // a true line break opportunity existed in the characters examined so far,
76                        // so there is no need to split a word
77                        i = goodBreakIndex; // no +1 because of i++
78                        lineNum++;
79                        maxWidth = mLineWidth.getLineWidth(lineNum);
80                        breakInfo.mBreaksList.add(mPrimitives.get(goodBreakIndex).location);
81                        breakInfo.mWidthsList.add(goodBreakWidth);
82                        breakInfo.mFlagsList.add(firstTabIndex < goodBreakIndex);
83                        firstTabIndex = Integer.MAX_VALUE;
84                    } else {
85                        // must split a word because there is no other option
86                        i = breakIndex; // no +1 because of i++
87                        lineNum++;
88                        maxWidth = mLineWidth.getLineWidth(lineNum);
89                        breakInfo.mBreaksList.add(mPrimitives.get(breakIndex).location);
90                        breakInfo.mWidthsList.add(breakWidth);
91                        breakInfo.mFlagsList.add(firstTabIndex < breakIndex);
92                        firstTabIndex = Integer.MAX_VALUE;
93                    }
94                    printedWidth = width = 0;
95                    goodBreakFound = breakFound = false;
96                    goodBreakWidth = breakWidth = 0;
97                    continue;
98                } else {
99                    // no choice, keep going... must make progress by putting at least one
100                    // character on a line, even if part of that character is cut off --
101                    // there is no other option
102                }
103            }
104
105            // update possible break points
106            if (p.type == PrimitiveType.PENALTY &&
107                    p.penalty < PENALTY_INFINITY) {
108                // this does not handle penalties with width
109
110                // handle forced line break
111                if (p.penalty == -PENALTY_INFINITY) {
112                    lineNum++;
113                    maxWidth = mLineWidth.getLineWidth(lineNum);
114                    breakInfo.mBreaksList.add(p.location);
115                    breakInfo.mWidthsList.add(printedWidth);
116                    breakInfo.mFlagsList.add(firstTabIndex < i);
117                    firstTabIndex = Integer.MAX_VALUE;
118                    printedWidth = width = 0;
119                    goodBreakFound = breakFound = false;
120                    goodBreakWidth = breakWidth = 0;
121                    continue;
122                }
123                if (i > breakIndex && (printedWidth <= maxWidth || !breakFound)) {
124                    breakFound = true;
125                    breakIndex = i;
126                    breakWidth = printedWidth;
127                }
128                if (i > goodBreakIndex && printedWidth <= maxWidth) {
129                    goodBreakFound = true;
130                    goodBreakIndex = i;
131                    goodBreakWidth = printedWidth;
132                }
133            } else if (p.type == PrimitiveType.WORD_BREAK) {
134                // only do this if necessary -- we don't want to break words
135                // when possible, but sometimes it is unavoidable
136                if (i > breakIndex && (printedWidth <= maxWidth || !breakFound)) {
137                    breakFound = true;
138                    breakIndex = i;
139                    breakWidth = printedWidth;
140                }
141            }
142        }
143
144        if (breakFound || goodBreakFound) {
145            // output last break if there are more characters to output
146            if (goodBreakFound) {
147                breakInfo.mBreaksList.add(mPrimitives.get(goodBreakIndex).location);
148                breakInfo.mWidthsList.add(goodBreakWidth);
149                breakInfo.mFlagsList.add(firstTabIndex < goodBreakIndex);
150            } else {
151                breakInfo.mBreaksList.add(mPrimitives.get(breakIndex).location);
152                breakInfo.mWidthsList.add(breakWidth);
153                breakInfo.mFlagsList.add(firstTabIndex < breakIndex);
154            }
155        }
156        breakInfo.copyTo(lineBreaks);
157    }
158
159    private static class BreakInfo {
160        List<Integer> mBreaksList = new ArrayList<Integer>();
161        List<Float> mWidthsList = new ArrayList<Float>();
162        List<Boolean> mFlagsList = new ArrayList<Boolean>();
163
164        public void copyTo(LineBreaks lineBreaks) {
165            if (lineBreaks.breaks.length != mBreaksList.size()) {
166                lineBreaks.breaks = new int[mBreaksList.size()];
167                lineBreaks.widths = new float[mWidthsList.size()];
168                lineBreaks.flags = new int[mFlagsList.size()];
169            }
170
171            int i = 0;
172            for (int b : mBreaksList) {
173                lineBreaks.breaks[i] = b;
174                i++;
175            }
176            i = 0;
177            for (float b : mWidthsList) {
178                lineBreaks.widths[i] = b;
179                i++;
180            }
181            i = 0;
182            for (boolean b : mFlagsList) {
183                lineBreaks.flags[i] = b ? TAB_MASK : 0;
184                i++;
185            }
186
187            mBreaksList = null;
188            mWidthsList = null;
189            mFlagsList = null;
190        }
191    }
192}
193