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 32 namespace android { 33 34 enum BreakStrategy { 35 kBreakStrategy_Greedy = 0, 36 kBreakStrategy_HighQuality = 1, 37 kBreakStrategy_Balanced = 2 38 }; 39 40 enum 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 47 class 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 82 class 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 105 class 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
