1 /*
2 * Copyright (C) 2017 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 #include "LineBreakerUtil.h"
18
19 namespace minikin {
20
21 // Very long words trigger O(n^2) behavior in hyphenation, so we disable hyphenation for
22 // unreasonably long words. This is somewhat of a heuristic because extremely long words are
23 // possible in some languages. This does mean that very long real words can get broken by
24 // desperate breaks, with no hyphens.
25 constexpr size_t LONGEST_HYPHENATED_WORD = 45;
26
27 // Hyphenates a string potentially containing non-breaking spaces.
hyphenate(const U16StringPiece & str,const Hyphenator & hyphenator)28 std::vector<HyphenationType> hyphenate(const U16StringPiece& str, const Hyphenator& hyphenator) {
29 std::vector<HyphenationType> out;
30 const size_t len = str.size();
31 out.resize(len);
32
33 // A word here is any consecutive string of non-NBSP characters.
34 bool inWord = false;
35 size_t wordStart = 0; // The initial value will never be accessed, but just in case.
36 for (size_t i = 0; i <= len; i++) {
37 if (i == len || str[i] == CHAR_NBSP) {
38 if (inWord) {
39 // A word just ended. Hyphenate it.
40 const U16StringPiece word = str.substr(Range(wordStart, i));
41 if (word.size() <= LONGEST_HYPHENATED_WORD) {
42 hyphenator.hyphenate(word, out.data() + wordStart);
43 } else { // Word is too long. Inefficient to hyphenate.
44 out.insert(out.end(), word.size(), HyphenationType::DONT_BREAK);
45 }
46 inWord = false;
47 }
48 if (i < len) {
49 // Insert one DONT_BREAK for the NBSP.
50 out.push_back(HyphenationType::DONT_BREAK);
51 }
52 } else if (!inWord) {
53 inWord = true;
54 wordStart = i;
55 }
56 }
57 return out;
58 }
59
60 } // namespace minikin
61