1 /* This file is part of the Spring engine (GPL v2 or later), see LICENSE.html */
2
3 #include "TextWrap.h"
4 #include "glFont.h"
5 #include "FontLogSection.h"
6 #include "System/Log/ILog.h"
7 #include "System/myMath.h"
8 #include "System/Util.h"
9
10
11 static const char32_t ellipsisUTF16 = 0x2026;
12 static const std::string ellipsisUTF8 = UnicodeToUtf8(ellipsisUTF16);
13 static const char32_t spaceUTF16 = 0x20;
14
15
16 /*******************************************************************************/
17 /*******************************************************************************/
18
19 template <typename T>
SkipColorCodes(const std::u8string & text,T * pos,SColor * color)20 static inline int SkipColorCodes(const std::u8string& text, T* pos, SColor* color)
21 {
22 int colorFound = 0;
23 while (text[(*pos)] == CTextWrap::ColorCodeIndicator) {
24 (*pos) += 4;
25 if ((*pos) >= text.size()) {
26 return -(1 + colorFound);
27 } else {
28 color->r = text[(*pos)-3];
29 color->g = text[(*pos)-2];
30 color->b = text[(*pos)-1];
31 colorFound = 1;
32 }
33 }
34 return colorFound;
35 }
36
37
38 /*******************************************************************************/
39 /*******************************************************************************/
40
CTextWrap(const std::string & fontfile,int size,int outlinewidth,float outlineweight)41 CTextWrap::CTextWrap(const std::string& fontfile, int size, int outlinewidth, float outlineweight)
42 : CFontTexture(fontfile,size,outlinewidth,outlineweight)
43 {
44 }
45
46
47 /*******************************************************************************/
48 /*******************************************************************************/
49
50 /**
51 * @brief IsUpperCase
52 * @return true if the given char is an uppercase
53 */
IsUpperCase(const char32_t & c)54 static inline bool IsUpperCase(const char32_t& c)
55 {
56 // overkill to add unicode
57 return
58 (c >= 0x41 && c <= 0x5A) ||
59 (c >= 0xC0 && c <= 0xD6) ||
60 (c >= 0xD8 && c <= 0xDE) ||
61 (c == 0x8A) ||
62 (c == 0x8C) ||
63 (c == 0x8E) ||
64 (c == 0x9F);
65 }
66
IsLowerCase(const char32_t & c)67 static inline bool IsLowerCase(const char32_t& c)
68 {
69 // overkill to add unicode
70 return c >= 0x61 && c <= 0x7A; // only ascii (no latin-1!)
71 }
72
73
74 /**
75 * @brief GetPenalty
76 * @param c character at %strpos% in the word
77 * @param strpos position of c in the word
78 * @param strlen total length of the word
79 * @return penalty (smaller is better) to split a word at that position
80 */
GetPenalty(const char32_t & c,unsigned int strpos,unsigned int strlen)81 static inline float GetPenalty(const char32_t& c, unsigned int strpos, unsigned int strlen)
82 {
83 const float dist = strlen - strpos;
84
85 if (dist > (strlen / 2) && dist < 4) {
86 return 1e9;
87 } else if (IsLowerCase(c)) {
88 // lowercase char
89 return 1.0f + (strlen - strpos);
90 } else if (c >= 0x30 && c <= 0x39) {
91 // is number
92 return 1.0f + (strlen - strpos)*0.9;
93 } else if (IsUpperCase(c)) {
94 // uppercase char
95 return 1.0f + (strlen - strpos)*0.75;
96 } else {
97 // any special chars
98 return Square(dist / 4);
99 }
100 return Square(dist / 4);
101 }
102
103
SplitWord(CTextWrap::word & w,float wantedWidth,bool smart)104 CTextWrap::word CTextWrap::SplitWord(CTextWrap::word& w, float wantedWidth, bool smart)
105 {
106 // returns two pieces 'L'eft and 'R'ight of the split word (returns L, *wi becomes R)
107
108 word w2;
109 w2.pos = w.pos;
110
111 const float spaceAdvance = GetGlyph(spaceUTF16).advance;
112 if (w.isLineBreak) {
113 // shouldn't happen
114 w2 = w;
115 w.isSpace = true;
116 } else if (w.isSpace) {
117 const int split = (int)math::floor(wantedWidth / spaceAdvance);
118 w2.isSpace = true;
119 w2.numSpaces = split;
120 w2.width = spaceAdvance * w2.numSpaces;
121 w.numSpaces -= split;
122 w.width = spaceAdvance * w.numSpaces;
123 w.pos += split;
124 } else {
125 if (smart) {
126 if (
127 (wantedWidth < 8 * spaceAdvance) ||
128 (w.text.length() < 1)
129 ) {
130 w2.isSpace = true;
131 return w2;
132 }
133 }
134
135 float width = 0.0f;
136 int i = 0;
137 float min_penalty = 1e9;
138 unsigned int goodbreak = 0;
139 char32_t c = Utf8GetNextChar(w.text,i);
140 const GlyphInfo* curGlyph = &GetGlyph(c);
141 const GlyphInfo* nextGlyph = curGlyph;
142
143 do {
144 const int lastCharPos = i;
145 const char32_t co = c;
146 curGlyph = nextGlyph;
147 c = Utf8GetNextChar(w.text,i);
148 nextGlyph = &GetGlyph(c);
149 width += GetKerning(*curGlyph, *nextGlyph);
150
151 if (width > wantedWidth) {
152 break;
153 }
154
155 if (smart) {
156 const float penalty = GetPenalty(co, lastCharPos, w.text.length());
157 if (penalty < min_penalty) {
158 min_penalty = penalty;
159 goodbreak = lastCharPos;
160 }
161 } else {
162 goodbreak = i;
163 }
164 } while(i < w.text.length());
165
166 w2.text = toustring(w.text.substr(0,goodbreak));
167 w2.width = GetTextWidth(w2.text);
168 w.text.erase(0,goodbreak);
169 w.width = GetTextWidth(w.text);
170 w.pos += goodbreak;
171 }
172 return w2;
173 }
174
175
AddEllipsis(std::list<line> & lines,std::list<word> & words,float maxWidth)176 void CTextWrap::AddEllipsis(std::list<line>& lines, std::list<word>& words, float maxWidth)
177 {
178 const float ellipsisAdvance = GetGlyph(ellipsisUTF16).advance;
179 const float spaceAdvance = GetGlyph(spaceUTF16).advance;
180
181 if (ellipsisAdvance > maxWidth)
182 return;
183
184 line* l = &(lines.back());
185
186 // If the last line ends with a linebreak, remove it
187 std::list<word>::iterator wi_end = l->end;
188 if (wi_end->isLineBreak) {
189 if (l->start == l->end || l->end == words.begin()) {
190 // there is just the linebreak in that line, so replace linebreak with just a null space
191 word w;
192 w.pos = wi_end->pos;
193 w.isSpace = true;
194 w.numSpaces = 0;
195 l->start = words.insert(wi_end,w);
196 l->end = l->start;
197
198 words.erase(wi_end);
199 } else {
200 wi_end = words.erase(wi_end);
201 l->end = --wi_end;
202 }
203 }
204
205 // remove as many words until we have enough free space for the ellipsis
206 while (l->end != l->start) {
207 word& w = *l->end;
208
209 // we have enough free space
210 if (l->width + ellipsisAdvance < maxWidth)
211 break;
212
213 // we can cut the last word to get enough freespace (so show as many as possible characters of that word)
214 if (
215 ((l->width - w.width + ellipsisAdvance) < maxWidth) &&
216 (w.width > ellipsisAdvance)
217 ) {
218 break;
219 }
220
221 l->width -= w.width;
222 --(l->end);
223 }
224
225 // we don't even have enough space for the ellipsis
226 word& w = *l->end;
227 if ((l->width - w.width) + ellipsisAdvance > maxWidth)
228 return;
229
230 // sometimes words aren't hyphenated for visual aspects
231 // but if we put an ellipsis in there, it is better to show as many as possible characters of those words
232 std::list<word>::iterator nextwi(l->end);
233 ++nextwi;
234 if (
235 (!l->forceLineBreak) &&
236 (nextwi != words.end()) &&
237 (w.isSpace || w.isLineBreak) &&
238 (l->width + ellipsisAdvance < maxWidth) &&
239 !(nextwi->isSpace || nextwi->isLineBreak)
240 ) {
241 float spaceLeft = maxWidth - (l->width + ellipsisAdvance);
242 l->end = words.insert( nextwi, SplitWord(*nextwi, spaceLeft, false) );
243 l->width += l->end->width;
244 }
245
246 // the last word in the line needs to be cut
247 if (l->width + ellipsisAdvance > maxWidth) {
248 word& w = *l->end;
249 l->width -= w.width;
250 float spaceLeft = maxWidth - (l->width + ellipsisAdvance);
251 l->end = words.insert( l->end, SplitWord(w, spaceLeft, false) );
252 l->width += l->end->width;
253 }
254
255 // put in a space between words and the ellipsis (if there is enough space)
256 if (l->forceLineBreak && !l->end->isSpace) {
257 if (l->width + ellipsisAdvance + spaceAdvance <= maxWidth) {
258 word space;
259 space.isSpace = true;
260 space.numSpaces = 1;
261 space.width = spaceAdvance;
262 std::list<word>::iterator wi(l->end);
263 ++l->end;
264 if (l->end == words.end()) {
265 space.pos = wi->pos + wi->text.length() + 1;
266 } else {
267 space.pos = l->end->pos;
268 }
269 l->end = words.insert( l->end, space );
270 l->width += l->end->width;
271 }
272 }
273
274 // add our ellipsis
275 word ellipsis;
276 ellipsis.text = toustring(ellipsisUTF8);
277 ellipsis.width = ellipsisAdvance;
278 std::list<word>::iterator wi(l->end);
279 ++l->end;
280 if (l->end == words.end()) {
281 ellipsis.pos = wi->pos + wi->text.length() + 1;
282 } else {
283 ellipsis.pos = l->end->pos;
284 }
285 l->end = words.insert( l->end, ellipsis );
286 l->width += l->end->width;
287 }
288
289
WrapTextConsole(std::list<word> & words,float maxWidth,float maxHeight)290 void CTextWrap::WrapTextConsole(std::list<word>& words, float maxWidth, float maxHeight)
291 {
292 if (words.empty() || (GetLineHeight()<=0.0f))
293 return;
294 const bool splitAllWords = false;
295 const unsigned int maxLines = (unsigned int)math::floor(std::max(0.0f, maxHeight / GetLineHeight()));
296
297 line* currLine;
298 word linebreak;
299 linebreak.isLineBreak = true;
300
301 bool addEllipsis = false;
302 bool currLineValid = false; // true if there was added any data to the current line
303
304 std::list<word>::iterator wi = words.begin();
305
306 std::list<line> lines;
307 lines.push_back(line());
308 currLine = &(lines.back());
309 currLine->start = words.begin();
310
311 for (; ;) {
312 currLineValid = true;
313 if (wi->isLineBreak) {
314 currLine->forceLineBreak = true;
315 currLine->end = wi;
316
317 // start a new line after the '\n'
318 lines.push_back(line());
319 currLineValid = false;
320 currLine = &(lines.back());
321 currLine->start = wi;
322 ++currLine->start;
323 } else {
324 currLine->width += wi->width;
325 currLine->end = wi;
326
327 if (currLine->width > maxWidth) {
328 currLine->width -= wi->width;
329
330 // line grew too long by adding the last word, insert a LineBreak
331 const bool splitLastWord = (wi->width > (0.5 * maxWidth));
332 const float freeWordSpace = (maxWidth - currLine->width);
333
334 if (splitAllWords || splitLastWord) {
335 // last word W is larger than 0.5 * maxLineWidth, split it into
336 // get 'L'eft and 'R'ight parts of the split (wL becomes Left, *wi becomes R)
337
338 bool restart = (currLine->start == wi);
339 // turns *wi into R
340 word wL = SplitWord(*wi, freeWordSpace);
341
342 if (splitLastWord && wL.width == 0.0f) {
343 // With smart splitting it can happen that the word isn't split at all,
344 // this can cause a race condition when the word is longer than maxWidth.
345 // In this case we have to force an unaesthetic split.
346 wL = SplitWord(*wi, freeWordSpace, false);
347 }
348
349 // increase by the width of the L-part of *wi
350 currLine->width += wL.width;
351
352 // insert the L-part right before R
353 wi = words.insert(wi, wL);
354 if (restart)
355 currLine->start = wi;
356 ++wi;
357 }
358
359 // insert the forced linebreak (either after W or before R)
360 linebreak.pos = wi->pos;
361 currLine->end = words.insert(wi, linebreak);
362
363 while (wi != words.end() && wi->isSpace)
364 wi = words.erase(wi);
365
366 lines.push_back(line());
367 currLineValid = false;
368 currLine = &(lines.back());
369 currLine->start = wi;
370 --wi; // compensate the wi++ downwards
371 }
372 }
373
374 ++wi;
375
376 if (wi == words.end()) {
377 break;
378 }
379
380 if (lines.size() > maxLines) {
381 addEllipsis = true;
382 break;
383 }
384 }
385
386 // empty row
387 if (!currLineValid || (currLine->start == words.end() && !currLine->forceLineBreak)) {
388 lines.pop_back();
389 currLine = &(lines.back());
390 }
391
392 // if we had to cut the text because of missing space, add an ellipsis
393 if (addEllipsis)
394 AddEllipsis(lines, words, maxWidth);
395
396 wi = currLine->end;
397 ++wi;
398 wi = words.erase(wi, words.end());
399 }
400
401
SplitTextInWords(const std::u8string & text,std::list<word> * words,std::list<colorcode> * colorcodes)402 void CTextWrap::SplitTextInWords(const std::u8string& text, std::list<word>* words, std::list<colorcode>* colorcodes)
403 {
404 const unsigned int length = (unsigned int)text.length();
405 const float spaceAdvance = GetGlyph(spaceUTF16).advance;
406
407 words->push_back(word());
408 word* w = &(words->back());
409
410 unsigned int numChar = 0;
411 for (int pos = 0; pos < length; pos++) {
412 const char8_t& c = text[pos];
413 switch(c) {
414 // space
415 case spaceUTF16:
416 if (!w->isSpace) {
417 if (!w->isLineBreak) {
418 w->width = GetTextWidth(w->text);
419 }
420 words->push_back(word());
421 w = &(words->back());
422 w->isSpace = true;
423 w->pos = numChar;
424 }
425 w->numSpaces++;
426 w->width = spaceAdvance * w->numSpaces;
427 break;
428
429 // inlined colorcodes
430 case ColorCodeIndicator:
431 {
432 colorcodes->push_back(colorcode());
433 colorcode& cc = colorcodes->back();
434 cc.pos = numChar;
435 SkipColorCodes(text, &pos, &(cc.color));
436 if (pos<0) {
437 pos = length;
438 } else {
439 // SkipColorCodes jumps 1 too far (it jumps on the first non
440 // colorcode char, but our for-loop will still do "pos++;")
441 pos--;
442 }
443 } break;
444 case ColorResetIndicator:
445 {
446 colorcode* cc = &colorcodes->back();
447 if (cc->pos != numChar) {
448 colorcodes->push_back(colorcode());
449 cc = &colorcodes->back();
450 cc->pos = numChar;
451 }
452 cc->resetColor = true;
453 } break;
454
455 // newlines
456 case 0x0d: // CR+LF
457 if (pos+1 < length && text[pos+1] == 0x0a)
458 pos++;
459 case 0x0a: // LF
460 if (w->isSpace) {
461 w->width = spaceAdvance * w->numSpaces;
462 } else if (!w->isLineBreak) {
463 w->width = GetTextWidth(w->text);
464 }
465 words->push_back(word());
466 w = &(words->back());
467 w->isLineBreak = true;
468 w->pos = numChar;
469 break;
470
471 // printable chars
472 default:
473 if (w->isSpace || w->isLineBreak) {
474 if (w->isSpace) {
475 w->width = spaceAdvance * w->numSpaces;
476 } else if (!w->isLineBreak) {
477 w->width = GetTextWidth(w->text);
478 }
479 words->push_back(word());
480 w = &(words->back());
481 w->pos = numChar;
482 }
483 w->text += c;
484 numChar++;
485 }
486 }
487 if (w->isSpace) {
488 w->width = spaceAdvance * w->numSpaces;
489 } else if (!w->isLineBreak) {
490 w->width = GetTextWidth(w->text);
491 }
492 }
493
494
RemergeColorCodes(std::list<word> * words,std::list<colorcode> & colorcodes) const495 void CTextWrap::RemergeColorCodes(std::list<word>* words, std::list<colorcode>& colorcodes) const
496 {
497 auto wi = words->begin();
498 auto wi2 = words->begin();
499 for (auto& c: colorcodes) {
500 while(wi != words->end() && wi->pos <= c.pos) {
501 wi2 = wi;
502 ++wi;
503 }
504
505 word wc;
506 wc.pos = c.pos;
507 wc.isColorCode = true;
508 wc.text = toustring(c.tostring());
509
510 if (wi2->isSpace || wi2->isLineBreak) {
511 while(wi2 != words->end() && (wi2->isSpace || wi2->isLineBreak))
512 ++wi2;
513
514 if (wi == words->end() && (wi2->pos + wi2->numSpaces) < c.pos) {
515 return;
516 }
517
518 wi2 = words->insert(wi2, wc);
519 } else {
520 if (wi == words->end() && (wi2->pos + wi2->text.size()) < (c.pos + 1)) {
521 return;
522 }
523
524 size_t pos = c.pos - wi2->pos;
525 if (pos < wi2->text.size() && pos > 0) {
526 word w2;
527 w2.text = toustring(wi2->text.substr(0,pos));
528 w2.pos = wi2->pos;
529 wi2->text.erase(0,pos);
530 wi2->pos += pos;
531 wi2 = words->insert(wi2, wc);
532 wi2 = words->insert(wi2, w2);
533 } else {
534 wi2 = words->insert(wi2, wc);
535 }
536 }
537 wi = wi2;
538 ++wi;
539 }
540 }
541
542
WrapInPlace(std::u8string & text,float _fontSize,float maxWidth,float maxHeight)543 int CTextWrap::WrapInPlace(std::u8string& text, float _fontSize, float maxWidth, float maxHeight)
544 {
545 // TODO make an option to insert '-' for word wrappings (and perhaps try to syllabificate)
546
547 if (_fontSize <= 0.0f)
548 _fontSize = GetSize();
549
550 const float maxWidthf = maxWidth / _fontSize;
551 const float maxHeightf = maxHeight / _fontSize;
552
553 std::list<word> words;
554 std::list<colorcode> colorcodes;
555
556 SplitTextInWords(text, &words, &colorcodes);
557 WrapTextConsole(words, maxWidthf, maxHeightf);
558 //WrapTextKnuth(&lines, words, maxWidthf, maxHeightf);
559 RemergeColorCodes(&words, colorcodes);
560
561 // create the wrapped string
562 text = "";
563 if (words.empty())
564 return 0;
565 unsigned int numlines = 1;
566 for (auto& w: words) {
567 if (w.isSpace) {
568 for (unsigned int j = 0; j < w.numSpaces; ++j) {
569 text += " ";
570 }
571 } else if (w.isLineBreak) {
572 text += "\x0d\x0a";
573 numlines++;
574 } else {
575 text += w.text;
576 }
577 }
578 return numlines;
579 }
580
581
Wrap(const std::u8string & text,float _fontSize,float maxWidth,float maxHeight)582 std::u8string CTextWrap::Wrap(const std::u8string& text, float _fontSize, float maxWidth, float maxHeight)
583 {
584 std::u8string out(text);
585 WrapInPlace(out, _fontSize, maxWidth, maxHeight);
586 return out;
587 }
588
589 /*******************************************************************************/
590 /*******************************************************************************/
591