1/*
2 * Copyright (C) 2015 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
17/**
18 * A module for breaking paragraphs into lines, supporting high quality
19 * hyphenation and justification.
20 */
21
22#ifndef MINIKIN_LINE_BREAKER_H
23#define MINIKIN_LINE_BREAKER_H
24
25#include "unicode/brkiter.h"
26#include "unicode/locid.h"
27#include <cmath>
28#include <vector>
29#include "minikin/Hyphenator.h"
30#include "minikin/WordBreaker.h"
31
32namespace android {
33
34enum BreakStrategy {
35    kBreakStrategy_Greedy = 0,
36    kBreakStrategy_HighQuality = 1,
37    kBreakStrategy_Balanced = 2
38};
39
40enum HyphenationFrequency {
41    kHyphenationFrequency_None = 0,
42    kHyphenationFrequency_Normal = 1,
43    kHyphenationFrequency_Full = 2
44};
45
46// TODO: want to generalize to be able to handle array of line widths
47class LineWidths {
48    public:
49        void setWidths(float firstWidth, int firstWidthLineCount, float restWidth) {
50            mFirstWidth = firstWidth;
51            mFirstWidthLineCount = firstWidthLineCount;
52            mRestWidth = restWidth;
53        }
54        void setIndents(const std::vector<float>& indents) {
55            mIndents = indents;
56        }
57        bool isConstant() const {
58            // technically mFirstWidthLineCount == 0 would count too, but doesn't actually happen
59            return mRestWidth == mFirstWidth && mIndents.empty();
60        }
61        float getLineWidth(int line) const {
62            float width = (line < mFirstWidthLineCount) ? mFirstWidth : mRestWidth;
63            if (!mIndents.empty()) {
64                if ((size_t)line < mIndents.size()) {
65                    width -= mIndents[line];
66                } else {
67                    width -= mIndents.back();
68                }
69            }
70            return width;
71        }
72        void clear() {
73            mIndents.clear();
74        }
75    private:
76        float mFirstWidth;
77        int mFirstWidthLineCount;
78        float mRestWidth;
79        std::vector<float> mIndents;
80};
81
82class TabStops {
83    public:
84        void set(const int* stops, size_t nStops, int tabWidth) {
85            if (stops != nullptr) {
86                mStops.assign(stops, stops + nStops);
87            } else {
88                mStops.clear();
89            }
90            mTabWidth = tabWidth;
91        }
92        float nextTab(float widthSoFar) const {
93            for (size_t i = 0; i < mStops.size(); i++) {
94                if (mStops[i] > widthSoFar) {
95                    return mStops[i];
96                }
97            }
98            return floor(widthSoFar / mTabWidth + 1) * mTabWidth;
99        }
100    private:
101        std::vector<int> mStops;
102        int mTabWidth;
103};
104
105class LineBreaker {
106    public:
107        const static int kTab_Shift = 29;  // keep synchronized with TAB_MASK in StaticLayout.java
108
109        // Note: Locale persists across multiple invocations (it is not cleaned up by finish()),
110        // explicitly to avoid the cost of creating ICU BreakIterator objects. It should always
111        // be set on the first invocation, but callers are encouraged not to call again unless
112        // locale has actually changed.
113        // That logic could be here but it's better for performance that it's upstream because of
114        // the cost of constructing and comparing the ICU Locale object.
115        // Note: caller is responsible for managing lifetime of hyphenator
116        void setLocale(const icu::Locale& locale, Hyphenator* hyphenator);
117
118        void resize(size_t size) {
119            mTextBuf.resize(size);
120            mCharWidths.resize(size);
121        }
122
123        size_t size() const {
124            return mTextBuf.size();
125        }
126
127        uint16_t* buffer() {
128            return mTextBuf.data();
129        }
130
131        float* charWidths() {
132            return mCharWidths.data();
133        }
134
135        // set text to current contents of buffer
136        void setText();
137
138        void setLineWidths(float firstWidth, int firstWidthLineCount, float restWidth);
139
140        void setIndents(const std::vector<float>& indents);
141
142        void setTabStops(const int* stops, size_t nStops, int tabWidth) {
143            mTabStops.set(stops, nStops, tabWidth);
144        }
145
146        BreakStrategy getStrategy() const { return mStrategy; }
147
148        void setStrategy(BreakStrategy strategy) { mStrategy = strategy; }
149
150        HyphenationFrequency getHyphenationFrequency() const { return mHyphenationFrequency; }
151
152        void setHyphenationFrequency(HyphenationFrequency frequency) {
153            mHyphenationFrequency = frequency;
154        }
155
156        // TODO: this class is actually fairly close to being general and not tied to using
157        // Minikin to do the shaping of the strings. The main thing that would need to be changed
158        // is having some kind of callback (or virtual class, or maybe even template), which could
159        // easily be instantiated with Minikin's Layout. Future work for when needed.
160        float addStyleRun(MinikinPaint* paint, const FontCollection* typeface, FontStyle style,
161                size_t start, size_t end, bool isRtl);
162
163        void addReplacement(size_t start, size_t end, float width);
164
165        size_t computeBreaks();
166
167        const int* getBreaks() const {
168            return mBreaks.data();
169        }
170
171        const float* getWidths() const {
172            return mWidths.data();
173        }
174
175        const int* getFlags() const {
176            return mFlags.data();
177        }
178
179        void finish();
180
181    private:
182        // ParaWidth is used to hold cumulative width from beginning of paragraph. Note that for
183        // very large paragraphs, accuracy could degrade using only 32-bit float. Note however
184        // that float is used extensively on the Java side for this. This is a typedef so that
185        // we can easily change it based on performance/accuracy tradeoff.
186        typedef double ParaWidth;
187
188        // A single candidate break
189        struct Candidate {
190            size_t offset;  // offset to text buffer, in code units
191            size_t prev;  // index to previous break
192            ParaWidth preBreak;
193            ParaWidth postBreak;
194            float penalty;  // penalty of this break (for example, hyphen penalty)
195            float score;  // best score found for this break
196            size_t lineNumber;  // only updated for non-constant line widths
197            uint8_t hyphenEdit;
198        };
199
200        float currentLineWidth() const;
201
202        void addWordBreak(size_t offset, ParaWidth preBreak, ParaWidth postBreak, float penalty,
203                uint8_t hyph);
204
205        void addCandidate(Candidate cand);
206
207        // push an actual break to the output. Takes care of setting flags for tab
208        void pushBreak(int offset, float width, uint8_t hyph);
209
210        void computeBreaksGreedy();
211
212        void computeBreaksOptimal(bool isRectangular);
213
214        void finishBreaksOptimal();
215
216        WordBreaker mWordBreaker;
217        std::vector<uint16_t>mTextBuf;
218        std::vector<float>mCharWidths;
219
220        Hyphenator* mHyphenator;
221        std::vector<uint8_t> mHyphBuf;
222
223        // layout parameters
224        BreakStrategy mStrategy = kBreakStrategy_Greedy;
225        HyphenationFrequency mHyphenationFrequency = kHyphenationFrequency_Normal;
226        LineWidths mLineWidths;
227        TabStops mTabStops;
228
229        // result of line breaking
230        std::vector<int> mBreaks;
231        std::vector<float> mWidths;
232        std::vector<int> mFlags;
233
234        ParaWidth mWidth = 0;
235        std::vector<Candidate> mCandidates;
236        float mLinePenalty = 0.0f;
237
238        // the following are state for greedy breaker (updated while adding style runs)
239        size_t mLastBreak;
240        size_t mBestBreak;
241        float mBestScore;
242        ParaWidth mPreBreak;  // prebreak of last break
243        int mFirstTabIndex;
244};
245
246}  // namespace android
247
248#endif  // MINIKIN_LINE_BREAKER_H
249