1366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka/* 2366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka * Copyright (C) 2015 The Android Open Source Project 3366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka * 4366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka * Licensed under the Apache License, Version 2.0 (the "License"); 5366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka * you may not use this file except in compliance with the License. 6366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka * You may obtain a copy of the License at 7366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka * 8366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka * http://www.apache.org/licenses/LICENSE-2.0 9366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka * 10366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka * Unless required by applicable law or agreed to in writing, software 11366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka * distributed under the License is distributed on an "AS IS" BASIS, 12366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka * See the License for the specific language governing permissions and 14366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka * limitations under the License. 15366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka */ 16366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka 17366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka#include "OptimalLineBreaker.h" 18366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka 19366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka#include <algorithm> 20366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka#include <limits> 21366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka 22366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka#include "minikin/Characters.h" 23366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka#include "minikin/Layout.h" 24366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka#include "minikin/Range.h" 25366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka#include "minikin/U16StringPiece.h" 26366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka 27366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka#include "HyphenatorMap.h" 28366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka#include "LayoutUtils.h" 29366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka#include "LineBreakerUtil.h" 30366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka#include "Locale.h" 31366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka#include "LocaleListCache.h" 32366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka#include "MinikinInternal.h" 33366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka#include "WordBreaker.h" 34366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka 35366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonakanamespace minikin { 36366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka 37366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonakanamespace { 38366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka 39366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka// Large scores in a hierarchy; we prefer desperate breaks to an overfull line. All these 40366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka// constants are larger than any reasonable actual width score. 41366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonakaconstexpr float SCORE_INFTY = std::numeric_limits<float>::max(); 42366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonakaconstexpr float SCORE_OVERFULL = 1e12f; 43366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonakaconstexpr float SCORE_DESPERATE = 1e10f; 44366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka 45366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka// Multiplier for hyphen penalty on last line. 46366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonakaconstexpr float LAST_LINE_PENALTY_MULTIPLIER = 4.0f; 47366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka// Penalty assigned to each line break (to try to minimize number of lines) 48366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka// TODO: when we implement full justification (so spaces can shrink and stretch), this is 49366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka// probably not the most appropriate method. 50366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonakaconstexpr float LINE_PENALTY_MULTIPLIER = 2.0f; 51366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka 52366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka// Penalty assigned to shrinking the whitepsace. 53366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonakaconstexpr float SHRINK_PENALTY_MULTIPLIER = 4.0f; 54366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka 55366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka// Maximum amount that spaces can shrink, in justified text. 56366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonakaconstexpr float SHRINKABILITY = 1.0 / 3.0; 57366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka 58366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka// A single candidate break 59366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonakastruct Candidate { 60366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka uint32_t offset; // offset to text buffer, in code units 61366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka 62366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka ParaWidth preBreak; // width of text until this point, if we decide to not break here: 63366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka // preBreak is used as an optimized way to calculate the width 64366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka // between two candidates. The line width between two line break 65366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka // candidates i and j is calculated as postBreak(j) - preBreak(i). 66366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka ParaWidth postBreak; // width of text until this point, if we decide to break here 67366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka float penalty; // penalty of this break (for example, hyphen penalty) 68366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka uint32_t preSpaceCount; // preceding space count before breaking 69366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka uint32_t postSpaceCount; // preceding space count after breaking 70366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka HyphenationType hyphenType; 71366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka bool isRtl; // The direction of the bidi run containing or ending in this candidate 72366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka 73366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka Candidate(uint32_t offset, ParaWidth preBreak, ParaWidth postBreak, float penalty, 74366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka uint32_t preSpaceCount, uint32_t postSpaceCount, HyphenationType hyphenType, 75366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka bool isRtl) 76366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka : offset(offset), 77366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka preBreak(preBreak), 78366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka postBreak(postBreak), 79366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka penalty(penalty), 80366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka preSpaceCount(preSpaceCount), 81366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka postSpaceCount(postSpaceCount), 82366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka hyphenType(hyphenType), 83366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka isRtl(isRtl) {} 84366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka}; 85366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka 86366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka// A context of line break optimization. 87366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonakastruct OptimizeContext { 88366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka // The break candidates. 89366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka std::vector<Candidate> candidates; 90366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka 91366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka // The penalty for the number of lines. 92366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka float linePenalty = 0.0f; 93366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka 94366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka // The width of a space. May be 0 if there are no spaces. 95366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka // Note: if there are multiple different widths for spaces (for example, because of mixing of 96366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka // fonts), it's only guaranteed to pick one. 97366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka float spaceWidth = 0.0f; 98366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka 99366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka // Append desperate break point to the candidates. 100366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka inline void pushDesperate(uint32_t offset, ParaWidth sumOfCharWidths, uint32_t spaceCount, 101366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka bool isRtl) { 102366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka candidates.emplace_back(offset, sumOfCharWidths, sumOfCharWidths, SCORE_DESPERATE, 103366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka spaceCount, spaceCount, 104366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka HyphenationType::BREAK_AND_DONT_INSERT_HYPHEN, isRtl); 105366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka } 106366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka 107366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka // Append hyphenation break point to the candidates. 108366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka inline void pushHyphenation(uint32_t offset, ParaWidth preBreak, ParaWidth postBreak, 109366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka float penalty, uint32_t spaceCount, HyphenationType type, 110366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka bool isRtl) { 111366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka candidates.emplace_back(offset, preBreak, postBreak, penalty, spaceCount, spaceCount, type, 112366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka isRtl); 113366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka } 114366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka 115366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka // Append word break point to the candidates. 116366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka inline void pushWordBreak(uint32_t offset, ParaWidth preBreak, ParaWidth postBreak, 117366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka float penalty, uint32_t preSpaceCount, uint32_t postSpaceCount, 118366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka bool isRtl) { 119366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka candidates.emplace_back(offset, preBreak, postBreak, penalty, preSpaceCount, postSpaceCount, 120366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka HyphenationType::DONT_BREAK, isRtl); 121366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka } 122366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka 123366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka OptimizeContext() { 124366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka candidates.emplace_back(0, 0.0f, 0.0f, 0.0f, 0, 0, HyphenationType::DONT_BREAK, false); 125366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka } 126366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka}; 127366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka 128366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka// Compute the penalty for the run and returns penalty for hyphenation and number of lines. 129366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonakastd::pair<float, float> computePenalties(const Run& run, const LineWidth& lineWidth, 130366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka HyphenationFrequency frequency, bool justified) { 131366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka float linePenalty = 0.0; 132366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka const MinikinPaint* paint = run.getPaint(); 133366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka // a heuristic that seems to perform well 134366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka float hyphenPenalty = 0.5 * paint->size * paint->scaleX * lineWidth.getAt(0); 135366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka if (frequency == HyphenationFrequency::Normal) { 136366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka hyphenPenalty *= 4.0; // TODO: Replace with a better value after some testing 137366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka } 138366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka 139366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka if (justified) { 140366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka // Make hyphenation more aggressive for fully justified text (so that "normal" in 141366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka // justified mode is the same as "full" in ragged-right). 142366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka hyphenPenalty *= 0.25; 143366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka } else { 144366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka // Line penalty is zero for justified text. 145366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka linePenalty = hyphenPenalty * LINE_PENALTY_MULTIPLIER; 146366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka } 147366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka 148366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka return std::make_pair(hyphenPenalty, linePenalty); 149366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka} 150366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka 151366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka// Represents a desperate break point. 152366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonakastruct DesperateBreak { 153366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka // The break offset. 154366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka uint32_t offset; 155366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka 156366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka // The sum of the character width from the beginning of the word. 157366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka ParaWidth sumOfChars; 158366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka 159366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka DesperateBreak(uint32_t offset, ParaWidth sumOfChars) 160366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka : offset(offset), sumOfChars(sumOfChars){}; 161366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka}; 162366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka 163366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka// Retrieves desperate break points from a word. 164366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonakastd::vector<DesperateBreak> populateDesperatePoints(const MeasuredText& measured, 165366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka const Range& range) { 166366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka std::vector<DesperateBreak> out; 167366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka ParaWidth width = measured.widths[range.getStart()]; 168366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka for (uint32_t i = range.getStart() + 1; i < range.getEnd(); ++i) { 169366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka const float w = measured.widths[i]; 170366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka if (w == 0) { 171366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka continue; // w == 0 means here is not a grapheme bounds. Don't break here. 172366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka } 173366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka out.emplace_back(i, width); 174366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka width += w; 175366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka } 176366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka return out; 177366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka} 178366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka 179366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka// Append hyphenation break points and desperate break points. 180366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka// If an offset is a both candidate for hyphenation and desperate break points, place desperate 181366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka// break candidate first and hyphenation break points second since the result width of the desperate 182366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka// break is shorter than hyphenation break. 183366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka// This is important since DP in computeBreaksOptimal assumes that the result line width is 184366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka// increased by break offset. 185c9611626465f9e11817854f554e7b7d0c6cee905Seigo Nonakavoid appendWithMerging(std::vector<HyphenBreak>::const_iterator hyIter, 186c9611626465f9e11817854f554e7b7d0c6cee905Seigo Nonaka std::vector<HyphenBreak>::const_iterator endHyIter, 187366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka const std::vector<DesperateBreak>& desperates, const CharProcessor& proc, 188366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka float hyphenPenalty, bool isRtl, OptimizeContext* out) { 189366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka auto d = desperates.begin(); 190c9611626465f9e11817854f554e7b7d0c6cee905Seigo Nonaka while (hyIter != endHyIter || d != desperates.end()) { 191c9611626465f9e11817854f554e7b7d0c6cee905Seigo Nonaka // If both hyphen breaks and desperate breaks point to the same offset, push desperate 192c9611626465f9e11817854f554e7b7d0c6cee905Seigo Nonaka // breaks first. 193c9611626465f9e11817854f554e7b7d0c6cee905Seigo Nonaka if (d != desperates.end() && (hyIter == endHyIter || d->offset <= hyIter->offset)) { 194366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka out->pushDesperate(d->offset, proc.sumOfCharWidthsAtPrevWordBreak + d->sumOfChars, 195366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka proc.effectiveSpaceCount, isRtl); 196366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka d++; 197366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka } else { 198c9611626465f9e11817854f554e7b7d0c6cee905Seigo Nonaka out->pushHyphenation(hyIter->offset, proc.sumOfCharWidths - hyIter->second, 199c9611626465f9e11817854f554e7b7d0c6cee905Seigo Nonaka proc.sumOfCharWidthsAtPrevWordBreak + hyIter->first, hyphenPenalty, 200c9611626465f9e11817854f554e7b7d0c6cee905Seigo Nonaka proc.effectiveSpaceCount, hyIter->type, isRtl); 201c9611626465f9e11817854f554e7b7d0c6cee905Seigo Nonaka hyIter++; 202366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka } 203366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka } 204366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka} 205366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka 206366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka// Enumerate all line break candidates. 207366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo NonakaOptimizeContext populateCandidates(const U16StringPiece& textBuf, const MeasuredText& measured, 208366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka const LineWidth& lineWidth, HyphenationFrequency frequency, 209366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka bool isJustified) { 210366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka const ParaWidth minLineWidth = lineWidth.getMin(); 211366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka CharProcessor proc(textBuf); 212366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka 213366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka OptimizeContext result; 214366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka 215c9611626465f9e11817854f554e7b7d0c6cee905Seigo Nonaka const bool doHyphenation = frequency != HyphenationFrequency::None; 216c9611626465f9e11817854f554e7b7d0c6cee905Seigo Nonaka auto hyIter = std::begin(measured.hyphenBreaks); 217c9611626465f9e11817854f554e7b7d0c6cee905Seigo Nonaka 218366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka for (const auto& run : measured.runs) { 219366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka const bool isRtl = run->isRtl(); 220366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka const Range& range = run->getRange(); 221366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka 222366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka // Compute penalty parameters. 223366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka float hyphenPenalty = 0.0f; 224366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka if (run->canHyphenate()) { 225366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka auto penalties = computePenalties(*run, lineWidth, frequency, isJustified); 226366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka hyphenPenalty = penalties.first; 227366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka result.linePenalty = std::max(penalties.second, result.linePenalty); 228366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka } 229366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka 230366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka proc.updateLocaleIfNecessary(*run); 231366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka 232366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka for (uint32_t i = range.getStart(); i < range.getEnd(); ++i) { 233c9611626465f9e11817854f554e7b7d0c6cee905Seigo Nonaka MINIKIN_ASSERT(textBuf[i] != CHAR_TAB, "TAB is not supported in optimal line breaker"); 234366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka proc.feedChar(i, textBuf[i], measured.widths[i]); 235366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka 236366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka const uint32_t nextCharOffset = i + 1; 237366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka if (nextCharOffset != proc.nextWordBreak) { 238366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka continue; // Wait until word break point. 239366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka } 240366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka 241366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka // Add hyphenation and desperate break points. 242366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka std::vector<HyphenBreak> hyphenedBreaks; 243366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka std::vector<DesperateBreak> desperateBreaks; 244366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka const Range contextRange = proc.contextRange(); 245c9611626465f9e11817854f554e7b7d0c6cee905Seigo Nonaka 246c9611626465f9e11817854f554e7b7d0c6cee905Seigo Nonaka auto beginHyIter = hyIter; 247c9611626465f9e11817854f554e7b7d0c6cee905Seigo Nonaka while (hyIter != std::end(measured.hyphenBreaks) && 248c9611626465f9e11817854f554e7b7d0c6cee905Seigo Nonaka hyIter->offset < contextRange.getEnd()) { 249c9611626465f9e11817854f554e7b7d0c6cee905Seigo Nonaka hyIter++; 250366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka } 251366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka if (proc.widthFromLastWordBreak() > minLineWidth) { 252366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka desperateBreaks = populateDesperatePoints(measured, contextRange); 253366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka } 254c9611626465f9e11817854f554e7b7d0c6cee905Seigo Nonaka appendWithMerging(beginHyIter, doHyphenation ? hyIter : beginHyIter, desperateBreaks, 255c9611626465f9e11817854f554e7b7d0c6cee905Seigo Nonaka proc, hyphenPenalty, isRtl, &result); 256366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka 257366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka // We skip breaks for zero-width characters inside replacement spans. 258366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka if (nextCharOffset == range.getEnd() || measured.widths[nextCharOffset] > 0) { 259366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka const float penalty = hyphenPenalty * proc.wordBreakPenalty(); 260366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka result.pushWordBreak(nextCharOffset, proc.sumOfCharWidths, proc.effectiveWidth, 261366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka penalty, proc.rawSpaceCount, proc.effectiveSpaceCount, isRtl); 262366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka } 263366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka } 264366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka } 265366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka result.spaceWidth = proc.spaceWidth; 266366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka return result; 267366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka} 268366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka 269366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonakaclass LineBreakOptimizer { 270366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonakapublic: 271366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka LineBreakOptimizer() {} 272366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka 2738e60b6f3a6bed9ece5608847f7dab7c3359c9a67Seigo Nonaka LineBreakResult computeBreaks(const OptimizeContext& context, const U16StringPiece& textBuf, 2748e60b6f3a6bed9ece5608847f7dab7c3359c9a67Seigo Nonaka const MeasuredText& measuredText, const LineWidth& lineWidth, 2758e60b6f3a6bed9ece5608847f7dab7c3359c9a67Seigo Nonaka BreakStrategy strategy, bool justified); 276366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka 277366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonakaprivate: 278366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka // Data used to compute optimal line breaks 279366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka struct OptimalBreaksData { 280366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka float score; // best score found for this break 281366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka uint32_t prev; // index to previous break 282366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka uint32_t lineNumber; // the computed line number of the candidate 283366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka }; 2848e60b6f3a6bed9ece5608847f7dab7c3359c9a67Seigo Nonaka LineBreakResult finishBreaksOptimal(const U16StringPiece& textBuf, const MeasuredText& measured, 285366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka const std::vector<OptimalBreaksData>& breaksData, 286366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka const std::vector<Candidate>& candidates); 287366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka 2888e60b6f3a6bed9ece5608847f7dab7c3359c9a67Seigo Nonaka MinikinExtent computeMaxExtent(const U16StringPiece& textBuf, const MeasuredText& measured, 2898e60b6f3a6bed9ece5608847f7dab7c3359c9a67Seigo Nonaka uint32_t start, uint32_t end) const; 290366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka}; 291366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka 292366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka// Find the needed extent between the start and end ranges. start is inclusive and end is exclusive. 293366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka// Both are indices of the source string. 2948e60b6f3a6bed9ece5608847f7dab7c3359c9a67Seigo NonakaMinikinExtent LineBreakOptimizer::computeMaxExtent(const U16StringPiece& textBuf, 2958e60b6f3a6bed9ece5608847f7dab7c3359c9a67Seigo Nonaka const MeasuredText& measured, uint32_t start, 296366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka uint32_t end) const { 297366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka MinikinExtent res = {0.0, 0.0, 0.0}; 298366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka for (uint32_t j = start; j < end; j++) { 2998e60b6f3a6bed9ece5608847f7dab7c3359c9a67Seigo Nonaka if (!isLineSpaceExcludeChar(textBuf[j])) { 3008e60b6f3a6bed9ece5608847f7dab7c3359c9a67Seigo Nonaka res.extendBy(measured.extents[j]); 3018e60b6f3a6bed9ece5608847f7dab7c3359c9a67Seigo Nonaka } 302366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka } 303366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka return res; 304366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka} 305366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka 306366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka// Follow "prev" links in candidates array, and copy to result arrays. 307366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo NonakaLineBreakResult LineBreakOptimizer::finishBreaksOptimal( 3088e60b6f3a6bed9ece5608847f7dab7c3359c9a67Seigo Nonaka const U16StringPiece& textBuf, const MeasuredText& measured, 3098e60b6f3a6bed9ece5608847f7dab7c3359c9a67Seigo Nonaka const std::vector<OptimalBreaksData>& breaksData, 310366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka const std::vector<Candidate>& candidates) { 311366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka LineBreakResult result; 312366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka const uint32_t nCand = candidates.size(); 313366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka uint32_t prevIndex; 314366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka for (uint32_t i = nCand - 1; i > 0; i = prevIndex) { 315366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka prevIndex = breaksData[i].prev; 316366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka const Candidate& cand = candidates[i]; 317366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka const Candidate& prev = candidates[prevIndex]; 318366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka 319366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka result.breakPoints.push_back(cand.offset); 320366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka result.widths.push_back(cand.postBreak - prev.preBreak); 3218e60b6f3a6bed9ece5608847f7dab7c3359c9a67Seigo Nonaka MinikinExtent extent = computeMaxExtent(textBuf, measured, prev.offset, cand.offset); 322366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka result.ascents.push_back(extent.ascent); 323366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka result.descents.push_back(extent.descent); 324366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka 325366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka const HyphenEdit edit = 326366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka packHyphenEdit(editForNextLine(prev.hyphenType), editForThisLine(cand.hyphenType)); 327366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka result.flags.push_back(static_cast<int>(edit)); 328366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka } 329366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka result.reverse(); 330366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka return result; 331366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka} 332366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka 333366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo NonakaLineBreakResult LineBreakOptimizer::computeBreaks(const OptimizeContext& context, 3348e60b6f3a6bed9ece5608847f7dab7c3359c9a67Seigo Nonaka const U16StringPiece& textBuf, 335366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka const MeasuredText& measured, 336366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka const LineWidth& lineWidth, 337366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka BreakStrategy strategy, bool justified) { 338366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka const std::vector<Candidate>& candidates = context.candidates; 339366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka uint32_t active = 0; 340366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka const uint32_t nCand = candidates.size(); 341366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka const float maxShrink = justified ? SHRINKABILITY * context.spaceWidth : 0.0f; 342366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka 343366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka std::vector<OptimalBreaksData> breaksData; 344366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka breaksData.reserve(nCand); 345366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka breaksData.push_back({0.0, 0, 0}); // The first candidate is always at the first line. 346366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka 347366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka // "i" iterates through candidates for the end of the line. 348366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka for (uint32_t i = 1; i < nCand; i++) { 349366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka const bool atEnd = i == nCand - 1; 350366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka float best = SCORE_INFTY; 351366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka uint32_t bestPrev = 0; 352366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka 353366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka uint32_t lineNumberLast = breaksData[active].lineNumber; 354366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka float width = lineWidth.getAt(lineNumberLast); 355366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka 356366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka ParaWidth leftEdge = candidates[i].postBreak - width; 357366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka float bestHope = 0; 358366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka 359366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka // "j" iterates through candidates for the beginning of the line. 360366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka for (uint32_t j = active; j < i; j++) { 361366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka const uint32_t lineNumber = breaksData[j].lineNumber; 362366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka if (lineNumber != lineNumberLast) { 363366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka const float widthNew = lineWidth.getAt(lineNumber); 364366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka if (widthNew != width) { 365366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka leftEdge = candidates[i].postBreak - width; 366366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka bestHope = 0; 367366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka width = widthNew; 368366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka } 369366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka lineNumberLast = lineNumber; 370366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka } 371366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka const float jScore = breaksData[j].score; 372366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka if (jScore + bestHope >= best) continue; 373366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka const float delta = candidates[j].preBreak - leftEdge; 374366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka 375366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka // compute width score for line 376366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka 377366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka // Note: the "bestHope" optimization makes the assumption that, when delta is 378366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka // non-negative, widthScore will increase monotonically as successive candidate 379366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka // breaks are considered. 380366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka float widthScore = 0.0f; 381366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka float additionalPenalty = 0.0f; 382366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka if ((atEnd || !justified) && delta < 0) { 383366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka widthScore = SCORE_OVERFULL; 384366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka } else if (atEnd && strategy != BreakStrategy::Balanced) { 385366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka // increase penalty for hyphen on last line 386366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka additionalPenalty = LAST_LINE_PENALTY_MULTIPLIER * candidates[j].penalty; 387366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka } else { 388366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka widthScore = delta * delta; 389366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka if (delta < 0) { 390366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka if (-delta < 391366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka maxShrink * (candidates[i].postSpaceCount - candidates[j].preSpaceCount)) { 392366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka widthScore *= SHRINK_PENALTY_MULTIPLIER; 393366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka } else { 394366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka widthScore = SCORE_OVERFULL; 395366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka } 396366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka } 397366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka } 398366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka 399366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka if (delta < 0) { 400366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka active = j + 1; 401366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka } else { 402366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka bestHope = widthScore; 403366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka } 404366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka 405366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka const float score = jScore + widthScore + additionalPenalty; 406366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka if (score <= best) { 407366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka best = score; 408366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka bestPrev = j; 409366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka } 410366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka } 411366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka breaksData.push_back({best + candidates[i].penalty + context.linePenalty, // score 412366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka bestPrev, // prev 413366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka breaksData[bestPrev].lineNumber + 1}); // lineNumber 414366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka } 4158e60b6f3a6bed9ece5608847f7dab7c3359c9a67Seigo Nonaka return finishBreaksOptimal(textBuf, measured, breaksData, candidates); 416366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka} 417366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka 418366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka} // namespace 419366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka 420366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo NonakaLineBreakResult breakLineOptimal(const U16StringPiece& textBuf, const MeasuredText& measured, 421366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka const LineWidth& lineWidth, BreakStrategy strategy, 422366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka HyphenationFrequency frequency, bool justified) { 423366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka if (textBuf.size() == 0) { 424366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka return LineBreakResult(); 425366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka } 426366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka const OptimizeContext context = 427366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka populateCandidates(textBuf, measured, lineWidth, frequency, justified); 428366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka LineBreakOptimizer optimizer; 4298e60b6f3a6bed9ece5608847f7dab7c3359c9a67Seigo Nonaka return optimizer.computeBreaks(context, textBuf, measured, lineWidth, strategy, justified); 430366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka} 431366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka 432366f57fb4efd0ddf5d48cd232cd88d3777517ea2Seigo Nonaka} // namespace minikin 433