LineBreaker.cpp revision 0261224adbab3a3735d37b41a38bdea046248406
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#define LOG_TAG "Minikin" 18 19#include <limits> 20 21#include <log/log.h> 22 23#include "LayoutUtils.h" 24#include "StringPiece.h" 25#include "WordBreaker.h" 26#include <minikin/Layout.h> 27#include <minikin/LineBreaker.h> 28 29using std::vector; 30 31namespace minikin { 32 33constexpr uint16_t CHAR_TAB = 0x0009; 34constexpr uint16_t CHAR_NBSP = 0x00A0; 35 36// Large scores in a hierarchy; we prefer desperate breaks to an overfull line. All these 37// constants are larger than any reasonable actual width score. 38const float SCORE_INFTY = std::numeric_limits<float>::max(); 39const float SCORE_OVERFULL = 1e12f; 40const float SCORE_DESPERATE = 1e10f; 41 42// Multiplier for hyphen penalty on last line. 43const float LAST_LINE_PENALTY_MULTIPLIER = 4.0f; 44// Penalty assigned to each line break (to try to minimize number of lines) 45// TODO: when we implement full justification (so spaces can shrink and stretch), this is 46// probably not the most appropriate method. 47const float LINE_PENALTY_MULTIPLIER = 2.0f; 48 49// Penalty assigned to shrinking the whitepsace. 50const float SHRINK_PENALTY_MULTIPLIER = 4.0f; 51 52// Very long words trigger O(n^2) behavior in hyphenation, so we disable hyphenation for 53// unreasonably long words. This is somewhat of a heuristic because extremely long words 54// are possible in some languages. This does mean that very long real words can get 55// broken by desperate breaks, with no hyphens. 56const size_t LONGEST_HYPHENATED_WORD = 45; 57 58// When the text buffer is within this limit, capacity of vectors is retained at finish(), 59// to avoid allocation. 60const size_t MAX_TEXT_BUF_RETAIN = 32678; 61 62// Maximum amount that spaces can shrink, in justified text. 63const float SHRINKABILITY = 1.0 / 3.0; 64 65LineBreaker::LineBreaker() : mWordBreaker(std::make_unique<WordBreaker>()) { } 66 67LineBreaker::LineBreaker(std::unique_ptr<WordBreaker>&& breaker) 68 : mWordBreaker(std::move(breaker)) { } 69 70LineBreaker::~LineBreaker() {} 71 72void LineBreaker::setLocales(const char* locales, const std::vector<Hyphenator*>& hyphenators, 73 size_t restartFrom) { 74 // For now, we ignore all locales except the first valid one. 75 // TODO: Support selecting the locale based on the script of the text. 76 SplitIterator it(locales, ','); 77 for (size_t i = 0; it.hasNext(); i++) { 78 StringPiece localeStr = it.next(); 79 icu::Locale locale = icu::Locale::createFromName(localeStr.toString().c_str()); 80 if (!locale.isBogus()) { // found a good locale 81 mHyphenator = hyphenators[i]; // The number of locales and hyphenators are the same. 82 mWordBreaker->followingWithLocale(locale, restartFrom); 83 return; 84 } 85 } 86 87 // No good locale found. Use Root locale. 88 mWordBreaker->followingWithLocale(icu::Locale::getRoot(), restartFrom); 89 mHyphenator = nullptr; 90} 91 92void LineBreaker::setText() { 93 mWordBreaker->setText(mTextBuf.data(), mTextBuf.size()); 94 95 // handle initial break here because addStyleRun may never be called 96 mCandidates.clear(); 97 Candidate cand = { 98 0, 0, 0.0, 0.0, 0.0, 0.0, 0, 0, {0.0, 0.0, 0.0}, HyphenationType::DONT_BREAK}; 99 mCandidates.push_back(cand); 100 101 // reset greedy breaker state 102 mBreaks.clear(); 103 mWidths.clear(); 104 mAscents.clear(); 105 mDescents.clear(); 106 mFlags.clear(); 107 mLastBreak = 0; 108 mBestBreak = 0; 109 mBestScore = SCORE_INFTY; 110 mPreBreak = 0; 111 mLastHyphenation = HyphenEdit::NO_EDIT; 112 mFirstTabIndex = INT_MAX; 113 mSpaceCount = 0; 114} 115 116// This function determines whether a character is a space that disappears at end of line. 117// It is the Unicode set: [[:General_Category=Space_Separator:]-[:Line_Break=Glue:]], 118// plus '\n'. 119// Note: all such characters are in the BMP, so it's ok to use code units for this. 120static bool isLineEndSpace(uint16_t c) { 121 return c == '\n' || c == ' ' || c == 0x1680 || (0x2000 <= c && c <= 0x200A && c != 0x2007) || 122 c == 0x205F || c == 0x3000; 123} 124 125// Hyphenates a string potentially containing non-breaking spaces. 126std::vector<HyphenationType> LineBreaker::hyphenate(const uint16_t* str, size_t len) { 127 std::vector<HyphenationType> out; 128 out.reserve(len); 129 130 // A word here is any consecutive string of non-NBSP characters. 131 bool inWord = false; 132 size_t wordStart = 0; // The initial value will never be accessed, but just in case. 133 for (size_t i = 0; i <= len; i++) { 134 if (i == len || str[i] == CHAR_NBSP) { 135 if (inWord) { 136 // A word just ended. Hyphenate it. 137 const size_t wordLen = i - wordStart; 138 if (wordLen <= LONGEST_HYPHENATED_WORD) { 139 if (wordStart == 0) { 140 // The string starts with a word. Use out directly. 141 mHyphenator->hyphenate(&out, str, wordLen); 142 } else { 143 std::vector<HyphenationType> wordVec; 144 mHyphenator->hyphenate(&wordVec, str + wordStart, wordLen); 145 out.insert(out.end(), wordVec.cbegin(), wordVec.cend()); 146 } 147 } else { // Word is too long. Inefficient to hyphenate. 148 out.insert(out.end(), wordLen, HyphenationType::DONT_BREAK); 149 } 150 inWord = false; 151 } 152 if (i < len) { 153 // Insert one DONT_BREAK for the NBSP. 154 out.push_back(HyphenationType::DONT_BREAK); 155 } 156 } else if (!inWord) { 157 inWord = true; 158 wordStart = i; 159 } 160 } 161 return out; 162} 163 164// Compute the total overhang of text based on per-cluster advances and overhangs. 165// The two input vectors are expected to be of the same size. 166/* static */ LayoutOverhang LineBreaker::computeOverhang(float totalAdvance, 167 const std::vector<float>& advances, const std::vector<LayoutOverhang>& overhangs, 168 bool isRtl) { 169 ParaWidth left = 0.0; 170 ParaWidth right = 0.0; 171 ParaWidth seenAdvance = 0.0; 172 const size_t len = advances.size(); 173 if (isRtl) { 174 for (size_t i = 0; i < len; i++) { 175 right = std::max(right, overhangs[i].right - seenAdvance); 176 seenAdvance += advances[i]; 177 left = std::max(left, overhangs[i].left - (totalAdvance - seenAdvance)); 178 } 179 } else { 180 for (size_t i = 0; i < len; i++) { 181 left = std::max(left, overhangs[i].left - seenAdvance); 182 seenAdvance += advances[i]; 183 right = std::max(right, overhangs[i].right - (totalAdvance - seenAdvance)); 184 } 185 } 186 return {static_cast<float>(left), static_cast<float>(right)}; 187} 188 189// This adds all the hyphenation candidates for a given word by first finding all the hyphenation 190// points and then calling addWordBreak for each. 191// 192// paint and typeface will be used for measuring the text and paint must not be null. 193// runStart is the beginning of the whole run, and is used for making sure we don't hyphenated words 194// that go outside the run. 195// afterWord is the index of last code unit seen that's not a line-ending space, plus one. In other 196// words, the index of the first code unit after a word. 197// lastBreak is the index of the previous break point and lastBreakWidth is the width seen until 198// that point. 199// extent is a pointer to the variable that keeps track of the maximum vertical extents seen since 200// the last time addWordBreak() was called. It will be reset to 0 after every call. 201// bidiFlags keep the bidi flags to determine the direction of text for layout and other 202// calculations. It may only be kBidi_Force_RTL or kBidi_Force_LTR. 203// 204// The following parameters are needed to be passed to addWordBreak: 205// postBreak is the width that would be seen if we decide to break at the end of the word (so it 206// doesn't count any line-ending space after the word). 207// postSpaceCount is the number of spaces that would be seen if we decide to break at the end of the 208// word (and like postBreak it doesn't count any line-ending space after the word). 209// hyphenPenalty is the amount of penalty for hyphenation. 210void LineBreaker::addHyphenationCandidates(MinikinPaint* paint, 211 const std::shared_ptr<FontCollection>& typeface, FontStyle style, size_t runStart, 212 size_t afterWord, size_t lastBreak, ParaWidth lastBreakWidth, ParaWidth postBreak, 213 size_t postSpaceCount, MinikinExtent* extent, float hyphenPenalty, int bidiFlags) { 214 const bool isRtl = (bidiFlags == kBidi_Force_RTL); 215 const size_t wordStart = mWordBreaker->wordStart(); 216 const size_t wordEnd = mWordBreaker->wordEnd(); 217 if (wordStart < runStart || wordEnd <= wordStart) { 218 return; 219 } 220 std::vector<HyphenationType> hyphenResult = 221 hyphenate(&mTextBuf[wordStart], wordEnd - wordStart); 222 223 std::vector<float> advances; 224 std::vector<LayoutOverhang> overhangs; 225 const size_t bufferSize = std::max(wordEnd - 1 - lastBreak, afterWord - wordStart); 226 advances.reserve(bufferSize); 227 overhangs.reserve(bufferSize); 228 // measure hyphenated substrings 229 for (size_t j = wordStart; j < wordEnd; j++) { 230 HyphenationType hyph = hyphenResult[j - wordStart]; 231 if (hyph == HyphenationType::DONT_BREAK) { 232 continue; 233 } 234 235 paint->hyphenEdit = HyphenEdit::editForThisLine(hyph); 236 const size_t firstPartLen = j - lastBreak; 237 advances.resize(firstPartLen); 238 overhangs.resize(firstPartLen); 239 const float firstPartWidth = Layout::measureText(mTextBuf.data(), lastBreak, firstPartLen, 240 mTextBuf.size(), bidiFlags, style, *paint, typeface, advances.data(), 241 nullptr /* extent */, overhangs.data()); 242 LayoutOverhang overhang = computeOverhang(firstPartWidth, advances, overhangs, isRtl); 243 const ParaWidth hyphPostBreak = lastBreakWidth 244 + (firstPartWidth + (isRtl ? overhang.left : overhang.right)); 245 246 paint->hyphenEdit = HyphenEdit::editForNextLine(hyph); 247 const size_t secondPartLen = afterWord - j; 248 advances.resize(secondPartLen); 249 overhangs.resize(secondPartLen); 250 const float secondPartWidth = Layout::measureText(mTextBuf.data(), j, secondPartLen, 251 mTextBuf.size(), bidiFlags, style, *paint, typeface, advances.data(), 252 nullptr /* extent */, overhangs.data()); 253 overhang = computeOverhang(secondPartWidth, advances, overhangs, isRtl); 254 // hyphPreBreak is calculated like this so that when the line width for a future line break 255 // is being calculated, the width of the whole word would be subtracted and the width of the 256 // second part would be added. 257 const ParaWidth hyphPreBreak = postBreak 258 - (secondPartWidth + (isRtl ? overhang.right : overhang.left)); 259 260 addWordBreak(j, hyphPreBreak, hyphPostBreak, postSpaceCount, postSpaceCount, *extent, 261 hyphenPenalty, hyph); 262 extent->reset(); 263 264 paint->hyphenEdit = HyphenEdit::NO_EDIT; 265 } 266} 267 268// Ordinarily, this method measures the text in the range given. However, when paint is nullptr, it 269// assumes the character widths, extents, and overhangs have already been calculated and stored in 270// the mCharWidths, mCharExtents, and mCharOverhangs buffers. 271// 272// This method finds the candidate word breaks (using the ICU break iterator) and sends them 273// to addCandidate. 274float LineBreaker::addStyleRun(MinikinPaint* paint, const std::shared_ptr<FontCollection>& typeface, 275 FontStyle style, size_t start, size_t end, bool isRtl, const char* langTags, 276 const std::vector<Hyphenator*>& hyphenators) { 277 float width = 0.0f; 278 const int bidiFlags = isRtl ? kBidi_Force_RTL : kBidi_Force_LTR; 279 280 float hyphenPenalty = 0.0; 281 if (paint != nullptr) { 282 width = Layout::measureText(mTextBuf.data(), start, end - start, mTextBuf.size(), bidiFlags, 283 style, *paint, typeface, mCharWidths.data() + start, mCharExtents.data() + start, 284 mCharOverhangs.data() + start); 285 286 // a heuristic that seems to perform well 287 hyphenPenalty = 0.5 * paint->size * paint->scaleX * mLineWidthDelegate->getLineWidth(0); 288 if (mHyphenationFrequency == kHyphenationFrequency_Normal) { 289 hyphenPenalty *= 4.0; // TODO: Replace with a better value after some testing 290 } 291 292 if (mJustified) { 293 // Make hyphenation more aggressive for fully justified text (so that "normal" in 294 // justified mode is the same as "full" in ragged-right). 295 hyphenPenalty *= 0.25; 296 } else { 297 // Line penalty is zero for justified text. 298 mLinePenalty = std::max(mLinePenalty, hyphenPenalty * LINE_PENALTY_MULTIPLIER); 299 } 300 } 301 302 // Caller passes nullptr for langTag if language is not changed. 303 if (langTags != nullptr) { 304 setLocales(langTags, hyphenators, start); 305 } 306 size_t current = (size_t) mWordBreaker->current(); 307 // This will keep the index of last code unit seen that's not a line-ending space, plus one. 308 // In other words, the index of the first code unit after a word. 309 size_t afterWord = start; 310 311 size_t lastBreak = start; // The index of the previous break point. 312 ParaWidth lastBreakWidth = mWidth; // The width of the text as of the previous break point. 313 ParaWidth postBreak = mWidth; // The width of text seen if we decide to break here 314 size_t postSpaceCount = mSpaceCount; 315 MinikinExtent extent = {0.0, 0.0, 0.0}; 316 const bool hyphenate = (paint != nullptr && mHyphenator != nullptr && 317 mHyphenationFrequency != kHyphenationFrequency_None); 318 for (size_t i = start; i < end; i++) { 319 const uint16_t c = mTextBuf[i]; 320 if (c == CHAR_TAB) { 321 mWidth = mPreBreak + mTabStops.nextTab(mWidth - mPreBreak); 322 if (mFirstTabIndex == INT_MAX) { 323 mFirstTabIndex = (int)i; 324 } 325 // fall back to greedy; other modes don't know how to deal with tabs 326 mStrategy = kBreakStrategy_Greedy; 327 } else { 328 if (isWordSpace(c)) { 329 mSpaceCount += 1; 330 } 331 mWidth += mCharWidths[i]; 332 extent.extendBy(mCharExtents[i]); 333 if (isLineEndSpace(c)) { 334 // If we break a line on a line-ending space, that space goes away. So postBreak 335 // and postSpaceCount, which keep the width and number of spaces if we decide to 336 // break at this point, don't need to get adjusted. 337 } else { 338 postBreak = mWidth; 339 postSpaceCount = mSpaceCount; 340 afterWord = i + 1; 341 } 342 } 343 if (i + 1 == current) { // We are at the end of a word. 344 if (hyphenate) { 345 addHyphenationCandidates(paint, typeface, style, start, afterWord, lastBreak, 346 lastBreakWidth, postBreak, postSpaceCount, &extent, hyphenPenalty, 347 bidiFlags); 348 } 349 350 // We skip breaks for zero-width characters inside replacement spans. 351 if (paint != nullptr || current == end || mCharWidths[current] > 0) { 352 const float penalty = hyphenPenalty * mWordBreaker->breakBadness(); 353 addWordBreak(current, mWidth, postBreak, mSpaceCount, postSpaceCount, extent, 354 penalty, HyphenationType::DONT_BREAK); 355 extent.reset(); 356 } 357 lastBreak = current; 358 lastBreakWidth = mWidth; 359 current = (size_t)mWordBreaker->next(); 360 } 361 } 362 363 return width; 364} 365 366// Add desperate breaks. 367// Note: these breaks are based on the shaping of the (non-broken) original text; they 368// are imprecise especially in the presence of kerning, ligatures, and Arabic shaping. 369void LineBreaker::addDesperateBreaks(ParaWidth width, size_t start, size_t end, 370 size_t postSpaceCount) { 371 for (size_t i = start; i < end; i++) { 372 const float w = mCharWidths[i]; 373 if (w > 0) { // Add desperate breaks only before grapheme clusters. 374 Candidate cand; 375 cand.offset = i; 376 cand.preBreak = width; 377 cand.postBreak = width; 378 // postSpaceCount doesn't include trailing spaces 379 cand.preSpaceCount = postSpaceCount; 380 cand.postSpaceCount = postSpaceCount; 381 cand.extent = mCharExtents[i]; 382 cand.penalty = SCORE_DESPERATE; 383 cand.hyphenType = HyphenationType::BREAK_AND_DONT_INSERT_HYPHEN; 384 addCandidate(cand); 385 width += w; 386 } 387 } 388} 389 390// add a word break (possibly for a hyphenated fragment), and add desperate breaks if 391// needed (ie when word exceeds current line width) 392void LineBreaker::addWordBreak(size_t offset, ParaWidth preBreak, ParaWidth postBreak, 393 size_t preSpaceCount, size_t postSpaceCount, MinikinExtent extent, 394 float penalty, HyphenationType hyph) { 395 const ParaWidth lastPreBreak = mCandidates.back().preBreak; 396 if (postBreak - lastPreBreak > currentLineWidth()) { // The line doesn't fit 397 const size_t lastBreak = mCandidates.back().offset; 398 // Add desperate breaks starting immediately after the last break 399 addDesperateBreaks(lastPreBreak + mCharWidths[lastBreak], 400 lastBreak + 1 /* start */, offset /* end */, postSpaceCount); 401 } 402 Candidate cand; 403 cand.offset = offset; 404 cand.preBreak = preBreak; 405 cand.postBreak = postBreak; 406 cand.penalty = penalty; 407 cand.preSpaceCount = preSpaceCount; 408 cand.postSpaceCount = postSpaceCount; 409 cand.extent = extent; 410 cand.hyphenType = hyph; 411 addCandidate(cand); 412} 413 414// Find the needed extent between the start and end ranges. start and end are inclusive. 415MinikinExtent LineBreaker::computeMaxExtent(size_t start, size_t end) const { 416 MinikinExtent res = mCandidates[end].extent; 417 for (size_t j = start; j < end; j++) { 418 res.extendBy(mCandidates[j].extent); 419 } 420 return res; 421} 422 423// Helper method for addCandidate() 424void LineBreaker::pushGreedyBreak() { 425 const Candidate& bestCandidate = mCandidates[mBestBreak]; 426 pushBreak(bestCandidate.offset, bestCandidate.postBreak - mPreBreak, 427 computeMaxExtent(mLastBreak + 1, mBestBreak), 428 mLastHyphenation | HyphenEdit::editForThisLine(bestCandidate.hyphenType)); 429 mBestScore = SCORE_INFTY; 430 mLastBreak = mBestBreak; 431 mPreBreak = bestCandidate.preBreak; 432 mLastHyphenation = HyphenEdit::editForNextLine(bestCandidate.hyphenType); 433} 434 435// TODO performance: could avoid populating mCandidates if greedy only 436void LineBreaker::addCandidate(Candidate cand) { 437 const size_t candIndex = mCandidates.size(); 438 mCandidates.push_back(cand); 439 440 // mLastBreak is the index of the last line break we decided to do in mCandidates, 441 // and mPreBreak is its preBreak value. mBestBreak is the index of the best line breaking 442 // candidate we have found since then, and mBestScore is its penalty. 443 if (cand.postBreak - mPreBreak > currentLineWidth()) { 444 // This break would create an overfull line, pick the best break and break there (greedy) 445 if (mBestBreak == mLastBreak) { 446 // No good break has been found since last break. Break here. 447 mBestBreak = candIndex; 448 } 449 pushGreedyBreak(); 450 } 451 452 while (mLastBreak != candIndex && cand.postBreak - mPreBreak > currentLineWidth()) { 453 // We should rarely come here. But if we are here, we have broken the line, but the 454 // remaining part still doesn't fit. We now need to break at the second best place after the 455 // last break, but we have not kept that information, so we need to go back and find it. 456 // 457 // In some really rare cases, postBreak - preBreak of a candidate itself may be over the 458 // current line width. We protect ourselves against an infinite loop in that case by 459 // checking that we have not broken the line at this candidate already. 460 for (size_t i = mLastBreak + 1; i < candIndex; i++) { 461 const float penalty = mCandidates[i].penalty; 462 if (penalty <= mBestScore) { 463 mBestBreak = i; 464 mBestScore = penalty; 465 } 466 } 467 if (mBestBreak == mLastBreak) { 468 // We didn't find anything good. Break here. 469 mBestBreak = candIndex; 470 } 471 pushGreedyBreak(); 472 } 473 474 if (cand.penalty <= mBestScore) { 475 mBestBreak = candIndex; 476 mBestScore = cand.penalty; 477 } 478} 479 480void LineBreaker::pushBreak(int offset, float width, MinikinExtent extent, uint8_t hyphenEdit) { 481 mBreaks.push_back(offset); 482 mWidths.push_back(width); 483 mAscents.push_back(extent.ascent); 484 mDescents.push_back(extent.descent); 485 int flags = (mFirstTabIndex < mBreaks.back()) << kTab_Shift; 486 flags |= hyphenEdit; 487 mFlags.push_back(flags); 488 mFirstTabIndex = INT_MAX; 489} 490 491void LineBreaker::addReplacement(size_t start, size_t end, float width, const char* langTags, 492 const std::vector<Hyphenator*>& hyphenators) { 493 mCharWidths[start] = width; 494 std::fill(&mCharWidths[start + 1], &mCharWidths[end], 0.0f); 495 // TODO: Get the extents information from the caller. 496 std::fill(&mCharExtents[start], &mCharExtents[end], (MinikinExtent) {0.0f, 0.0f, 0.0f}); 497 addStyleRun(nullptr, nullptr, FontStyle(), start, end, false, langTags, hyphenators); 498} 499 500// Get the width of a space. May return 0 if there are no spaces. 501// Note: if there are multiple different widths for spaces (for example, because of mixing of 502// fonts), it's only guaranteed to pick one. 503float LineBreaker::getSpaceWidth() const { 504 for (size_t i = 0; i < mTextBuf.size(); i++) { 505 if (isWordSpace(mTextBuf[i])) { 506 return mCharWidths[i]; 507 } 508 } 509 return 0.0f; 510} 511 512float LineBreaker::currentLineWidth() const { 513 return mLineWidthDelegate->getLineWidth(mBreaks.size()); 514} 515 516void LineBreaker::computeBreaksGreedy() { 517 // All breaks but the last have been added in addCandidate already. 518 size_t nCand = mCandidates.size(); 519 if (nCand == 1 || mLastBreak != nCand - 1) { 520 pushBreak(mCandidates[nCand - 1].offset, mCandidates[nCand - 1].postBreak - mPreBreak, 521 computeMaxExtent(mLastBreak + 1, nCand - 1), 522 mLastHyphenation); 523 // don't need to update mBestScore, because we're done 524 } 525} 526 527// Follow "prev" links in mCandidates array, and copy to result arrays. 528void LineBreaker::finishBreaksOptimal() { 529 // clear existing greedy break result 530 mBreaks.clear(); 531 mWidths.clear(); 532 mAscents.clear(); 533 mDescents.clear(); 534 mFlags.clear(); 535 536 size_t nCand = mCandidates.size(); 537 size_t prev; 538 for (size_t i = nCand - 1; i > 0; i = prev) { 539 prev = mCandidates[i].prev; 540 mBreaks.push_back(mCandidates[i].offset); 541 mWidths.push_back(mCandidates[i].postBreak - mCandidates[prev].preBreak); 542 MinikinExtent extent = computeMaxExtent(prev + 1, i); 543 mAscents.push_back(extent.ascent); 544 mDescents.push_back(extent.descent); 545 int flags = HyphenEdit::editForThisLine(mCandidates[i].hyphenType); 546 if (prev > 0) { 547 flags |= HyphenEdit::editForNextLine(mCandidates[prev].hyphenType); 548 } 549 mFlags.push_back(flags); 550 } 551 std::reverse(mBreaks.begin(), mBreaks.end()); 552 std::reverse(mWidths.begin(), mWidths.end()); 553 std::reverse(mFlags.begin(), mFlags.end()); 554} 555 556void LineBreaker::computeBreaksOptimal() { 557 size_t active = 0; 558 size_t nCand = mCandidates.size(); 559 float width = mLineWidthDelegate->getLineWidth(0); 560 float maxShrink = mJustified ? SHRINKABILITY * getSpaceWidth() : 0.0f; 561 std::vector<size_t> lineNumbers; 562 lineNumbers.reserve(nCand); 563 lineNumbers.push_back(0); // The first candidate is always at the first line. 564 565 // "i" iterates through candidates for the end of the line. 566 for (size_t i = 1; i < nCand; i++) { 567 bool atEnd = i == nCand - 1; 568 float best = SCORE_INFTY; 569 size_t bestPrev = 0; 570 571 size_t lineNumberLast = lineNumbers[active]; 572 width = mLineWidthDelegate->getLineWidth(lineNumberLast); 573 574 ParaWidth leftEdge = mCandidates[i].postBreak - width; 575 float bestHope = 0; 576 577 // "j" iterates through candidates for the beginning of the line. 578 for (size_t j = active; j < i; j++) { 579 size_t lineNumber = lineNumbers[j]; 580 if (lineNumber != lineNumberLast) { 581 float widthNew = mLineWidthDelegate->getLineWidth(lineNumber); 582 if (widthNew != width) { 583 leftEdge = mCandidates[i].postBreak - width; 584 bestHope = 0; 585 width = widthNew; 586 } 587 lineNumberLast = lineNumber; 588 } 589 float jScore = mCandidates[j].score; 590 if (jScore + bestHope >= best) continue; 591 float delta = mCandidates[j].preBreak - leftEdge; 592 593 // compute width score for line 594 595 // Note: the "bestHope" optimization makes the assumption that, when delta is 596 // non-negative, widthScore will increase monotonically as successive candidate 597 // breaks are considered. 598 float widthScore = 0.0f; 599 float additionalPenalty = 0.0f; 600 if ((atEnd || !mJustified) && delta < 0) { 601 widthScore = SCORE_OVERFULL; 602 } else if (atEnd && mStrategy != kBreakStrategy_Balanced) { 603 // increase penalty for hyphen on last line 604 additionalPenalty = LAST_LINE_PENALTY_MULTIPLIER * mCandidates[j].penalty; 605 } else { 606 widthScore = delta * delta; 607 if (delta < 0) { 608 if (-delta < maxShrink * 609 (mCandidates[i].postSpaceCount - mCandidates[j].preSpaceCount)) { 610 widthScore *= SHRINK_PENALTY_MULTIPLIER; 611 } else { 612 widthScore = SCORE_OVERFULL; 613 } 614 } 615 } 616 617 if (delta < 0) { 618 active = j + 1; 619 } else { 620 bestHope = widthScore; 621 } 622 623 float score = jScore + widthScore + additionalPenalty; 624 if (score <= best) { 625 best = score; 626 bestPrev = j; 627 } 628 } 629 mCandidates[i].score = best + mCandidates[i].penalty + mLinePenalty; 630 mCandidates[i].prev = bestPrev; 631 lineNumbers.push_back(lineNumbers[bestPrev] + 1); 632 } 633 finishBreaksOptimal(); 634} 635 636size_t LineBreaker::computeBreaks() { 637 if (mStrategy == kBreakStrategy_Greedy) { 638 computeBreaksGreedy(); 639 } else { 640 computeBreaksOptimal(); 641 } 642 return mBreaks.size(); 643} 644 645void LineBreaker::finish() { 646 mWordBreaker->finish(); 647 mWidth = 0; 648 mCandidates.clear(); 649 mBreaks.clear(); 650 mWidths.clear(); 651 mAscents.clear(); 652 mDescents.clear(); 653 mFlags.clear(); 654 if (mTextBuf.size() > MAX_TEXT_BUF_RETAIN) { 655 mTextBuf.clear(); 656 mTextBuf.shrink_to_fit(); 657 mCharWidths.clear(); 658 mCharWidths.shrink_to_fit(); 659 mCharExtents.clear(); 660 mCharExtents.shrink_to_fit(); 661 mCandidates.shrink_to_fit(); 662 mBreaks.shrink_to_fit(); 663 mWidths.shrink_to_fit(); 664 mAscents.shrink_to_fit(); 665 mDescents.shrink_to_fit(); 666 mFlags.shrink_to_fit(); 667 } 668 mStrategy = kBreakStrategy_Greedy; 669 mHyphenationFrequency = kHyphenationFrequency_Normal; 670 mLinePenalty = 0.0f; 671 mJustified = false; 672 mLineWidthDelegate.reset(); 673} 674 675} // namespace minikin 676