src/apps/haikudepot/textview/ParagraphLayout.cpp

   1 /*
   2  * Copyright 2001-2013, Haiku, Inc. All rights reserved.
   3  * Distributed under the terms of the MIT License.
   4  *
   5  * Authors:
   6  *              Stephan Aßmus, superstippi@gmx.de
   7  *              Stefano Ceccherini, stefano.ceccherini@gmail.com
   8  *              Marc Flerackers, mflerackers@androme.be
   9  *              Hiroshi Lockheimer (BTextView is based on his STEEngine)
  10  *              Oliver Tappe, zooey@hirschkaefer.de
  11  */
  12
  13 #include "ParagraphLayout.h"
  14
  15 #include <new>
  16 #include <stdio.h>
  17
  18 #include <AutoDeleter.h>
  19 #include <utf8_functions.h>
  20 #include <View.h>
  21
  22
  23 enum {
  24         CHAR_CLASS_DEFAULT,
  25         CHAR_CLASS_WHITESPACE,
  26         CHAR_CLASS_GRAPHICAL,
  27         CHAR_CLASS_QUOTE,
  28         CHAR_CLASS_PUNCTUATION,
  29         CHAR_CLASS_PARENS_OPEN,
  30         CHAR_CLASS_PARENS_CLOSE,
  31         CHAR_CLASS_END_OF_TEXT
  32 };
  33
  34
  35 inline uint32
  36 get_char_classification(uint32 charCode)
  37 {
  38         // TODO: Should check against a list of characters containing also
  39         // word breakers from other languages.
  40
  41         switch (charCode) {
  42                 case '\0':
  43                         return CHAR_CLASS_END_OF_TEXT;
  44
  45                 case ' ':
  46                 case '\t':
  47                 case '\n':
  48                         return CHAR_CLASS_WHITESPACE;
  49
  50                 case '=':
  51                 case '+':
  52                 case '@':
  53                 case '#':
  54                 case '$':
  55                 case '%':
  56                 case '^':
  57                 case '&':
  58                 case '*':
  59                 case '\\':
  60                 case '|':
  61                 case '<':
  62                 case '>':
  63                 case '/':
  64                 case '~':
  65                         return CHAR_CLASS_GRAPHICAL;
  66
  67                 case '\'':
  68                 case '"':
  69                         return CHAR_CLASS_QUOTE;
  70
  71                 case ',':
  72                 case '.':
  73                 case '?':
  74                 case '!':
  75                 case ';':
  76                 case ':':
  77                 case '-':
  78                         return CHAR_CLASS_PUNCTUATION;
  79
  80                 case '(':
  81                 case '[':
  82                 case '{':
  83                         return CHAR_CLASS_PARENS_OPEN;
  84
  85                 case ')':
  86                 case ']':
  87                 case '}':
  88                         return CHAR_CLASS_PARENS_CLOSE;
  89
  90                 default:
  91                         return CHAR_CLASS_DEFAULT;
  92         }
  93 }
  94
  95
  96 inline bool
  97 can_end_line(const GlyphInfoList& glyphInfos, int offset)
  98 {
  99         int count = glyphInfos.CountItems();
 100
 101         if (offset == count - 1)
 102                 return true;
 103
 104         if (offset < 0 || offset > count)
 105                 return false;
 106
 107         uint32 charCode = glyphInfos.ItemAtFast(offset).charCode;
 108         uint32 classification = get_char_classification(charCode);
 109
 110         // wrapping is always allowed at end of text and at newlines
 111         if (classification == CHAR_CLASS_END_OF_TEXT || charCode == '\n')
 112                 return true;
 113
 114         uint32 nextCharCode = glyphInfos.ItemAtFast(offset + 1).charCode;
 115         uint32 nextClassification = get_char_classification(nextCharCode);
 116
 117         // never separate a punctuation char from its preceding word
 118         if (classification == CHAR_CLASS_DEFAULT
 119                 && nextClassification == CHAR_CLASS_PUNCTUATION) {
 120                 return false;
 121         }
 122
 123         if ((classification == CHAR_CLASS_WHITESPACE
 124                         && nextClassification != CHAR_CLASS_WHITESPACE)
 125                 || (classification != CHAR_CLASS_WHITESPACE
 126                         && nextClassification == CHAR_CLASS_WHITESPACE)) {
 127                 return true;
 128         }
 129
 130         // allow wrapping after whitespace, unless more whitespace (except for
 131         // newline) follows
 132         if (classification == CHAR_CLASS_WHITESPACE
 133                 && (nextClassification != CHAR_CLASS_WHITESPACE
 134                         || nextCharCode == '\n')) {
 135                 return true;
 136         }
 137
 138         // allow wrapping after punctuation chars, unless more punctuation, closing
 139         // parenthesis or quotes follow
 140         if (classification == CHAR_CLASS_PUNCTUATION
 141                 && nextClassification != CHAR_CLASS_PUNCTUATION
 142                 && nextClassification != CHAR_CLASS_PARENS_CLOSE
 143                 && nextClassification != CHAR_CLASS_QUOTE) {
 144                 return true;
 145         }
 146
 147         // allow wrapping after quotes, graphical chars and closing parenthesis only
 148         // if whitespace follows (not perfect, but seems to do the right thing most
 149         // of the time)
 150         if ((classification == CHAR_CLASS_QUOTE
 151                         || classification == CHAR_CLASS_GRAPHICAL
 152                         || classification == CHAR_CLASS_PARENS_CLOSE)
 153                 && nextClassification == CHAR_CLASS_WHITESPACE) {
 154                 return true;
 155         }
 156
 157         return false;
 158 }
 159
 160
 161 // #pragma mark - ParagraphLayout
 162
 163
 164 ParagraphLayout::ParagraphLayout()
 165         :
 166         fTextSpans(),
 167         fParagraphStyle(),
 168
 169         fWidth(0.0f),
 170         fLayoutValid(false),
 171
 172         fGlyphInfos(),
 173         fLineInfos()
 174 {
 175 }
 176
 177
 178 ParagraphLayout::ParagraphLayout(const Paragraph& paragraph)
 179         :
 180         fTextSpans(paragraph.TextSpans()),
 181         fParagraphStyle(paragraph.Style()),
 182
 183         fWidth(0.0f),
 184         fLayoutValid(false),
 185
 186         fGlyphInfos(),
 187         fLineInfos()
 188 {
 189         _Init();
 190 }
 191
 192
 193 ParagraphLayout::ParagraphLayout(const ParagraphLayout& other)
 194         :
 195         fTextSpans(other.fTextSpans),
 196         fParagraphStyle(other.fParagraphStyle),
 197
 198         fWidth(other.fWidth),
 199         fLayoutValid(false),
 200
 201         fGlyphInfos(other.fGlyphInfos),
 202         fLineInfos()
 203 {
 204 }
 205
 206
 207 ParagraphLayout::~ParagraphLayout()
 208 {
 209 }
 210
 211
 212 void
 213 ParagraphLayout::SetParagraph(const Paragraph& paragraph)
 214 {
 215         fTextSpans = paragraph.TextSpans();
 216         fParagraphStyle = paragraph.Style();
 217
 218         _Init();
 219
 220         fLayoutValid = false;
 221 }
 222
 223
 224 void
 225 ParagraphLayout::SetWidth(float width)
 226 {
 227         if (fWidth != width) {
 228                 fWidth = width;
 229                 fLayoutValid = false;
 230         }
 231 }
 232
 233
 234 float
 235 ParagraphLayout::Height()
 236 {
 237         _ValidateLayout();
 238
 239         float height = 0.0f;
 240
 241         if (fLineInfos.CountItems() > 0) {
 242                 const LineInfo& lastLine = fLineInfos.LastItem();
 243                 height = lastLine.y + lastLine.height;
 244         }
 245
 246         return height;
 247 }
 248
 249
 250 void
 251 ParagraphLayout::Draw(BView* view, const BPoint& offset)
 252 {
 253         _ValidateLayout();
 254
 255         int lineCount = fLineInfos.CountItems();
 256         for (int i = 0; i < lineCount; i++) {
 257                 const LineInfo& line = fLineInfos.ItemAtFast(i);
 258                 _DrawLine(view, offset, line);
 259         }
 260
 261         const Bullet& bullet = fParagraphStyle.Bullet();
 262         if (bullet.Spacing() > 0.0f && bullet.String().Length() > 0) {
 263                 // Draw bullet at offset
 264                 view->SetHighUIColor(B_PANEL_TEXT_COLOR);
 265                 BPoint bulletPos(offset);
 266                 bulletPos.x += fParagraphStyle.FirstLineInset()
 267                         + fParagraphStyle.LineInset();
 268                 bulletPos.y += fLineInfos.ItemAt(0).maxAscent;
 269                 view->DrawString(bullet.String(), bulletPos);
 270         }
 271 }
 272
 273
 274 int32
 275 ParagraphLayout::CountGlyphs() const
 276 {
 277         return fGlyphInfos.CountItems();
 278 }
 279
 280
 281 int32
 282 ParagraphLayout::CountLines()
 283 {
 284         _ValidateLayout();
 285         return fLineInfos.CountItems();
 286 }
 287
 288
 289 int32
 290 ParagraphLayout::LineIndexForOffset(int32 textOffset)
 291 {
 292         _ValidateLayout();
 293
 294         if (fGlyphInfos.CountItems() == 0)
 295                 return 0;
 296
 297         if (textOffset >= fGlyphInfos.CountItems()) {
 298                 const GlyphInfo& glyph = fGlyphInfos.LastItem();
 299                 return glyph.lineIndex;
 300         }
 301
 302         if (textOffset < 0)
 303                 textOffset = 0;
 304
 305         const GlyphInfo& glyph = fGlyphInfos.ItemAtFast(textOffset);
 306         return glyph.lineIndex;
 307 }
 308
 309
 310 int32
 311 ParagraphLayout::FirstOffsetOnLine(int32 lineIndex)
 312 {
 313         _ValidateLayout();
 314
 315         if (lineIndex < 0)
 316                 lineIndex = 0;
 317         if (lineIndex >= fLineInfos.CountItems())
 318                 lineIndex = fLineInfos.CountItems() - 1;
 319
 320         return fLineInfos.ItemAt(lineIndex).textOffset;
 321 }
 322
 323
 324 int32
 325 ParagraphLayout::LastOffsetOnLine(int32 lineIndex)
 326 {
 327         _ValidateLayout();
 328
 329         if (lineIndex < 0)
 330                 lineIndex = 0;
 331
 332         if (lineIndex >= fLineInfos.CountItems() - 1)
 333                 return CountGlyphs() - 1;
 334
 335         return fLineInfos.ItemAt(lineIndex + 1).textOffset - 1;
 336 }
 337
 338
 339 void
 340 ParagraphLayout::GetLineBounds(int32 lineIndex, float& x1, float& y1,
 341         float& x2, float& y2)
 342 {
 343         _ValidateLayout();
 344
 345         if (fGlyphInfos.CountItems() == 0) {
 346                 _GetEmptyLayoutBounds(x1, y1, x2, y2);
 347                 return;
 348         }
 349
 350         if (lineIndex < 0)
 351                 lineIndex = 0;
 352         if (lineIndex >= fLineInfos.CountItems())
 353                 lineIndex = fLineInfos.CountItems() - 1;
 354
 355         const LineInfo& lineInfo = fLineInfos.ItemAt(lineIndex);
 356         int32 firstGlyphIndex = lineInfo.textOffset;
 357
 358         int32 lastGlyphIndex;
 359         if (lineIndex < fLineInfos.CountItems() - 1)
 360                 lastGlyphIndex = fLineInfos.ItemAt(lineIndex + 1).textOffset - 1;
 361         else
 362                 lastGlyphIndex = fGlyphInfos.CountItems() - 1;
 363
 364         const GlyphInfo& firstInfo = fGlyphInfos.ItemAtFast(firstGlyphIndex);
 365         const GlyphInfo& lastInfo = fGlyphInfos.ItemAtFast(lastGlyphIndex);
 366
 367         x1 = firstInfo.x;
 368         y1 = lineInfo.y;
 369         x2 = lastInfo.x + lastInfo.width;
 370         y2 = lineInfo.y + lineInfo.height;
 371 }
 372
 373
 374 void
 375 ParagraphLayout::GetTextBounds(int32 textOffset, float& x1, float& y1,
 376         float& x2, float& y2)
 377 {
 378         _ValidateLayout();
 379
 380         if (fGlyphInfos.CountItems() == 0) {
 381                 _GetEmptyLayoutBounds(x1, y1, x2, y2);
 382                 return;
 383         }
 384
 385         if (textOffset >= fGlyphInfos.CountItems()) {
 386                 const GlyphInfo& glyph = fGlyphInfos.LastItem();
 387                 const LineInfo& line = fLineInfos.ItemAt(glyph.lineIndex);
 388
 389                 x1 = glyph.x + glyph.width;
 390                 x2 = x1;
 391                 y1 = line.y;
 392                 y2 = y1 + line.height;
 393
 394                 return;
 395         }
 396
 397         if (textOffset < 0)
 398                 textOffset = 0;
 399
 400         const GlyphInfo& glyph = fGlyphInfos.ItemAtFast(textOffset);
 401         const LineInfo& line = fLineInfos.ItemAt(glyph.lineIndex);
 402
 403         x1 = glyph.x;
 404         x2 = x1 + glyph.width;
 405         y1 = line.y;
 406         y2 = y1 + line.height;
 407 }
 408
 409
 410 int32
 411 ParagraphLayout::TextOffsetAt(float x, float y, bool& rightOfCenter)
 412 {
 413         _ValidateLayout();
 414
 415         rightOfCenter = false;
 416
 417         int32 lineCount = fLineInfos.CountItems();
 418         if (fGlyphInfos.CountItems() == 0 || lineCount == 0
 419                 || fLineInfos.ItemAtFast(0).y > y) {
 420                 // Above first line or empty text
 421                 return 0;
 422         }
 423
 424         int32 lineIndex = 0;
 425         if (floorf(fLineInfos.LastItem().y
 426                         + fLineInfos.LastItem().height + 0.5) > y) {
 427                 // TODO: Optimize, can binary search line here:
 428                 for (; lineIndex < lineCount; lineIndex++) {
 429                         const LineInfo& line = fLineInfos.ItemAtFast(lineIndex);
 430                         float lineBottom = floorf(line.y + line.height + 0.5);
 431                         if (lineBottom > y)
 432                                 break;
 433                 }
 434         } else {
 435                 lineIndex = lineCount - 1;
 436         }
 437
 438         // Found line
 439         const LineInfo& line = fLineInfos.ItemAtFast(lineIndex);
 440         int32 textOffset = line.textOffset;
 441         int32 end;
 442         if (lineIndex < lineCount - 1)
 443                 end = fLineInfos.ItemAtFast(lineIndex + 1).textOffset - 1;
 444         else
 445                 end = fGlyphInfos.CountItems() - 1;
 446
 447         // TODO: Optimize, can binary search offset here:
 448         for (; textOffset <= end; textOffset++) {
 449                 const GlyphInfo& glyph = fGlyphInfos.ItemAtFast(textOffset);
 450                 float x1 = glyph.x;
 451                 if (x1 > x)
 452                         return textOffset;
 453
 454                 // x2 is the location at the right bounding box of the glyph
 455                 float x2 = x1 + glyph.width;
 456
 457                 // x3 is the location of the next glyph, which may be different from
 458                 // x2 in case the line is justified.
 459                 float x3;
 460                 if (textOffset < end - 1)
 461                         x3 = fGlyphInfos.ItemAtFast(textOffset + 1).x;
 462                 else
 463                         x3 = x2;
 464
 465                 if (x3 > x) {
 466                         rightOfCenter = x > (x1 + x2) / 2.0f;
 467                         return textOffset;
 468                 }
 469         }
 470
 471         // Account for trailing line break at end of line, the
 472         // returned offset should be before that.
 473         rightOfCenter = fGlyphInfos.ItemAtFast(end).charCode != '\n';
 474
 475         return end;
 476 }
 477
 478
 479 // #pragma mark - private
 480
 481
 482 void
 483 ParagraphLayout::_Init()
 484 {
 485         fGlyphInfos.Clear();
 486
 487         int spanCount = fTextSpans.CountItems();
 488         for (int i = 0; i < spanCount; i++) {
 489                 const TextSpan& span = fTextSpans.ItemAtFast(i);
 490                 if (!_AppendGlyphInfos(span)) {
 491                         fprintf(stderr, "%p->ParagraphLayout::_Init() - Out of memory\n",
 492                                 this);
 493                         return;
 494                 }
 495         }
 496 }
 497
 498
 499 void
 500 ParagraphLayout::_ValidateLayout()
 501 {
 502         if (!fLayoutValid) {
 503                 _Layout();
 504                 fLayoutValid = true;
 505         }
 506 }
 507
 508
 509 void
 510 ParagraphLayout::_Layout()
 511 {
 512         fLineInfos.Clear();
 513
 514         const Bullet& bullet = fParagraphStyle.Bullet();
 515
 516         float x = fParagraphStyle.LineInset() + fParagraphStyle.FirstLineInset()
 517                 + bullet.Spacing();
 518         float y = 0.0f;
 519         int lineIndex = 0;
 520         int lineStart = 0;
 521
 522         int glyphCount = fGlyphInfos.CountItems();
 523         for (int i = 0; i < glyphCount; i++) {
 524                 GlyphInfo glyph = fGlyphInfos.ItemAtFast(i);
 525
 526                 uint32 charClassification = get_char_classification(glyph.charCode);
 527
 528                 float advanceX = glyph.width;
 529                 float advanceY = 0.0f;
 530
 531                 bool nextLine = false;
 532                 bool lineBreak = false;
 533
 534 //              if (glyph.charCode == '\t') {
 535 //                      // Figure out tab width, it's the width between the last two tab
 536 //                      // stops.
 537 //                      float tabWidth = 0.0f;
 538 //                      if (fTabCount > 0)
 539 //                              tabWidth = fTabBuffer[fTabCount - 1];
 540 //                      if (fTabCount > 1)
 541 //                              tabWidth -= fTabBuffer[fTabCount - 2];
 542 //
 543 //                      // Try to find a tab stop that is farther than the current x
 544 //                      // offset
 545 //                      double tabOffset = 0.0;
 546 //                      for (unsigned tabIndex = 0; tabIndex < fTabCount; tabIndex++) {
 547 //                              tabOffset = fTabBuffer[tabIndex];
 548 //                              if (tabOffset > x)
 549 //                                      break;
 550 //                      }
 551 //
 552 //                      // If no tab stop has been found, make the tab stop a multiple of
 553 //                      // the tab width
 554 //                      if (tabOffset <= x && tabWidth > 0.0)
 555 //                              tabOffset = ((int) (x / tabWidth) + 1) * tabWidth;
 556 //
 557 //                      if (tabOffset - x > 0.0)
 558 //                              advanceX = tabOffset - x;
 559 //              }
 560
 561                 if (glyph.charCode == '\n') {
 562                         nextLine = true;
 563                         lineBreak = true;
 564                         glyph.x = x;
 565                         fGlyphInfos.Replace(i, glyph);
 566                 } else if (fWidth > 0.0f && x + advanceX > fWidth) {
 567                         fGlyphInfos.Replace(i, glyph);
 568                         if (charClassification == CHAR_CLASS_WHITESPACE) {
 569                                 advanceX = 0.0f;
 570                         } else if (i > lineStart) {
 571                                 nextLine = true;
 572                                 // The current glyph extends outside the width, we need to wrap
 573                                 // to the next line. See what previous offset can be the end
 574                                 // of the line.
 575                                 int lineEnd = i - 1;
 576                                 while (lineEnd > lineStart
 577                                         && !can_end_line(fGlyphInfos, lineEnd)) {
 578                                         lineEnd--;
 579                                 }
 580
 581                                 if (lineEnd > lineStart) {
 582                                         // Found a place to perform a line break.
 583                                         i = lineEnd + 1;
 584
 585                                         // Adjust the glyph info to point at the changed buffer
 586                                         // position
 587                                         glyph = fGlyphInfos.ItemAtFast(i);
 588                                         advanceX = glyph.width;
 589                                 } else {
 590                                         // Just break where we are.
 591                                 }
 592                         }
 593                 }
 594
 595                 if (nextLine) {
 596                         // * Initialize the max ascent/descent of all preceding glyph infos
 597                         // on the current/last line
 598                         // * Adjust the baseline offset according to the max ascent
 599                         // * Fill in the line index.
 600                         unsigned lineEnd;
 601                         if (lineBreak)
 602                                 lineEnd = i;
 603                         else
 604                                 lineEnd = i - 1;
 605
 606                         float lineHeight = 0.0;
 607                         _FinalizeLine(lineStart, lineEnd, lineIndex, y, lineHeight);
 608
 609                         // Start position of the next line
 610                         x = fParagraphStyle.LineInset() + bullet.Spacing();
 611                         y += lineHeight + fParagraphStyle.LineSpacing();
 612
 613                         if (lineBreak)
 614                                 lineStart = i + 1;
 615                         else
 616                                 lineStart = i;
 617
 618                         lineIndex++;
 619                 }
 620
 621                 if (!lineBreak && i < glyphCount) {
 622                         glyph.x = x;
 623                         fGlyphInfos.Replace(i, glyph);
 624                 }
 625
 626                 x += advanceX;
 627                 y += advanceY;
 628         }
 629
 630         // The last line may not have been appended and initialized yet.
 631         if (lineStart <= glyphCount - 1 || glyphCount == 0) {
 632                 float lineHeight;
 633                 _FinalizeLine(lineStart, glyphCount - 1, lineIndex, y, lineHeight);
 634         }
 635
 636         _ApplyAlignment();
 637 }
 638
 639
 640 void
 641 ParagraphLayout::_ApplyAlignment()
 642 {
 643         Alignment alignment = fParagraphStyle.Alignment();
 644         bool justify = fParagraphStyle.Justify();
 645
 646         if (alignment == ALIGN_LEFT && !justify)
 647                 return;
 648
 649         int glyphCount = fGlyphInfos.CountItems();
 650         if (glyphCount == 0)
 651                 return;
 652
 653         int lineIndex = -1;
 654         float spaceLeft = 0.0f;
 655         float charSpace = 0.0f;
 656         float whiteSpace = 0.0f;
 657         bool seenChar = false;
 658
 659         // Iterate all glyphs backwards. On the last character of the next line,
 660         // the position of the character determines the available space to be
 661         // distributed (spaceLeft).
 662         for (int i = glyphCount - 1; i >= 0; i--) {
 663                 GlyphInfo glyph = fGlyphInfos.ItemAtFast(i);
 664
 665                 if (glyph.lineIndex != lineIndex) {
 666                         bool lineBreak = glyph.charCode == '\n' || i == glyphCount - 1;
 667                         lineIndex = glyph.lineIndex;
 668
 669                         // The position of the last character determines the available
 670                         // space.
 671                         spaceLeft = fWidth - glyph.x;
 672
 673                         // If the character is visible, the width of the character needs to
 674                         // be subtracted from the available space, otherwise it would be
 675                         // pushed outside the line.
 676                         uint32 charClassification = get_char_classification(glyph.charCode);
 677                         if (charClassification != CHAR_CLASS_WHITESPACE)
 678                                 spaceLeft -= glyph.width;
 679
 680                         charSpace = 0.0f;
 681                         whiteSpace = 0.0f;
 682                         seenChar = false;
 683
 684                         if (lineBreak || !justify) {
 685                                 if (alignment == ALIGN_CENTER)
 686                                         spaceLeft /= 2.0f;
 687                                 else if (alignment == ALIGN_LEFT)
 688                                         spaceLeft = 0.0f;
 689                         } else {
 690                                 // Figure out how much chars and white space chars are on the
 691                                 // line. Don't count trailing white space.
 692                                 int charCount = 0;
 693                                 int spaceCount = 0;
 694                                 for (int j = i; j >= 0; j--) {
 695                                         const GlyphInfo& previousGlyph = fGlyphInfos.ItemAtFast(j);
 696                                         if (previousGlyph.lineIndex != lineIndex) {
 697                                                 j++;
 698                                                 break;
 699                                         }
 700                                         uint32 classification = get_char_classification(
 701                                                 previousGlyph.charCode);
 702                                         if (classification == CHAR_CLASS_WHITESPACE) {
 703                                                 if (charCount > 0)
 704                                                         spaceCount++;
 705                                                 else if (j < i)
 706                                                         spaceLeft += glyph.width;
 707                                         } else {
 708                                                 charCount++;
 709                                         }
 710                                 }
 711
 712                                 // The first char is not shifted when justifying, so it doesn't
 713                                 // contribute.
 714                                 if (charCount > 0)
 715                                         charCount--;
 716
 717                                 // Check if it looks better if both whitespace and chars get
 718                                 // some space distributed, in case there are only 1 or two
 719                                 // space chars on the line.
 720                                 float spaceLeftForSpace = spaceLeft;
 721                                 float spaceLeftForChars = spaceLeft;
 722
 723                                 if (spaceCount > 0) {
 724                                         float spaceCharRatio = (float) spaceCount / charCount;
 725                                         if (spaceCount < 3 && spaceCharRatio < 0.4f) {
 726                                                 spaceLeftForSpace = spaceLeft * 2.0f * spaceCharRatio;
 727                                                 spaceLeftForChars = spaceLeft - spaceLeftForSpace;
 728                                         } else
 729                                                 spaceLeftForChars = 0.0f;
 730                                 }
 731
 732                                 if (spaceCount > 0)
 733                                         whiteSpace = spaceLeftForSpace / spaceCount;
 734                                 if (charCount > 0)
 735                                         charSpace = spaceLeftForChars / charCount;
 736
 737                                 LineInfo line = fLineInfos.ItemAtFast(lineIndex);
 738                                 line.extraGlyphSpacing = charSpace;
 739                                 line.extraWhiteSpacing = whiteSpace;
 740
 741                                 fLineInfos.Replace(lineIndex, line);
 742                         }
 743                 }
 744
 745                 // Each character is pushed towards the right by the space that is
 746                 // still available. When justification is performed, the shift is
 747                 // gradually decreased. This works since the iteration is backwards
 748                 // and the characters on the right are pushed farthest.
 749                 glyph.x += spaceLeft;
 750
 751                 unsigned classification = get_char_classification(glyph.charCode);
 752
 753                 if (i < glyphCount - 1) {
 754                         GlyphInfo nextGlyph = fGlyphInfos.ItemAtFast(i + 1);
 755                         if (nextGlyph.lineIndex == lineIndex) {
 756                                 uint32 nextClassification
 757                                         = get_char_classification(nextGlyph.charCode);
 758                                 if (nextClassification == CHAR_CLASS_WHITESPACE
 759                                         && classification != CHAR_CLASS_WHITESPACE) {
 760                                         // When a space character is right of a regular character,
 761                                         // add the additional space to the space instead of the
 762                                         // character
 763                                         float shift = (nextGlyph.x - glyph.x) - glyph.width;
 764                                         nextGlyph.x -= shift;
 765                                         fGlyphInfos.Replace(i + 1, nextGlyph);
 766                                 }
 767                         }
 768                 }
 769
 770                 fGlyphInfos.Replace(i, glyph);
 771
 772                 // The shift (spaceLeft) is reduced depending on the character
 773                 // classification.
 774                 if (classification == CHAR_CLASS_WHITESPACE) {
 775                         if (seenChar)
 776                                 spaceLeft -= whiteSpace;
 777                 } else {
 778                         seenChar = true;
 779                         spaceLeft -= charSpace;
 780                 }
 781         }
 782 }
 783
 784
 785 bool
 786 ParagraphLayout::_AppendGlyphInfos(const TextSpan& span)
 787 {
 788         int charCount = span.CountChars();
 789         if (charCount == 0)
 790                 return true;
 791
 792         const BString& text = span.Text();
 793         const BFont& font = span.Style().Font();
 794
 795         // Allocate arrays
 796         float* escapementArray = new (std::nothrow) float[charCount];
 797         if (escapementArray == NULL)
 798                 return false;
 799         ArrayDeleter<float> escapementDeleter(escapementArray);
 800
 801         // Fetch glyph spacing information
 802         font.GetEscapements(text, charCount, escapementArray);
 803
 804         // Append to glyph buffer and convert escapement scale
 805         float size = font.Size();
 806         const char* c = text.String();
 807         for (int i = 0; i < charCount; i++) {
 808                 if (!_AppendGlyphInfo(UTF8ToCharCode(&c), escapementArray[i] * size,
 809                                 span.Style())) {
 810                         return false;
 811                 }
 812         }
 813
 814         return true;
 815 }
 816
 817
 818 bool
 819 ParagraphLayout::_AppendGlyphInfo(uint32 charCode, float width,
 820         const CharacterStyle& style)
 821 {
 822         if (style.Width() >= 0.0f) {
 823                 // Use the metrics provided by the CharacterStyle and override
 824                 // the font provided metrics passed in "width"
 825                 width = style.Width();
 826         }
 827
 828         width += style.GlyphSpacing();
 829
 830         return fGlyphInfos.Add(GlyphInfo(charCode, 0.0f, width, 0));
 831 }
 832
 833
 834 bool
 835 ParagraphLayout::_FinalizeLine(int lineStart, int lineEnd, int lineIndex,
 836         float y, float& lineHeight)
 837 {
 838         LineInfo line(lineStart, y, 0.0f, 0.0f, 0.0f);
 839
 840         int spanIndex = -1;
 841         int spanStart = 0;
 842         int spanEnd = 0;
 843
 844         for (int i = lineStart; i <= lineEnd; i++) {
 845                 // Mark line index in glyph
 846                 GlyphInfo glyph = fGlyphInfos.ItemAtFast(i);
 847                 glyph.lineIndex = lineIndex;
 848                 fGlyphInfos.Replace(i, glyph);
 849
 850                 // See if the next sub-span needs to be added to the LineInfo
 851                 bool addSpan = false;
 852
 853                 while (i >= spanEnd) {
 854                         spanIndex++;
 855                         const TextSpan& span = fTextSpans.ItemAt(spanIndex);
 856                         spanStart = spanEnd;
 857                         spanEnd += span.CountChars();
 858                         addSpan = true;
 859                 }
 860
 861                 if (addSpan) {
 862                         const TextSpan& span = fTextSpans.ItemAt(spanIndex);
 863                         TextSpan subSpan = span.SubSpan(i - spanStart,
 864                                 (lineEnd - spanStart + 1) - (i - spanStart));
 865                         line.layoutedSpans.Add(subSpan);
 866                         _IncludeStyleInLine(line, span.Style());
 867                 }
 868         }
 869
 870         if (fGlyphInfos.CountItems() == 0 && fTextSpans.CountItems() > 0) {
 871                 // When the layout contains no glyphs, but there is at least one
 872                 // TextSpan in the paragraph, use the font info from that span
 873                 // to calculate the height of the first LineInfo.
 874                 const TextSpan& span = fTextSpans.ItemAtFast(0);
 875                 line.layoutedSpans.Add(span);
 876                 _IncludeStyleInLine(line, span.Style());
 877         }
 878
 879         lineHeight = line.height;
 880
 881         return fLineInfos.Add(line);
 882 }
 883
 884
 885 void
 886 ParagraphLayout::_IncludeStyleInLine(LineInfo& line,
 887         const CharacterStyle& style)
 888 {
 889         float ascent = style.Ascent();
 890         if (ascent > line.maxAscent)
 891                 line.maxAscent = ascent;
 892
 893         float descent = style.Descent();
 894         if (descent > line.maxDescent)
 895                 line.maxDescent = descent;
 896
 897         float height = ascent + descent;
 898         if (style.Font().Size() > height)
 899                 height = style.Font().Size();
 900
 901         if (height > line.height)
 902                 line.height = height;
 903 }
 904
 905
 906 void
 907 ParagraphLayout::_DrawLine(BView* view, const BPoint& offset,
 908         const LineInfo& line) const
 909 {
 910         int textOffset = line.textOffset;
 911         int spanCount = line.layoutedSpans.CountItems();
 912         for (int i = 0; i < spanCount; i++) {
 913                 const TextSpan& span = line.layoutedSpans.ItemAtFast(i);
 914                 _DrawSpan(view, offset, span, textOffset);
 915                 textOffset += span.CountChars();
 916         }
 917 }
 918
 919
 920 void
 921 ParagraphLayout::_DrawSpan(BView* view, BPoint offset,
 922         const TextSpan& span, int32 textOffset) const
 923 {
 924         const BString& text = span.Text();
 925         if (text.Length() == 0)
 926                 return;
 927
 928         const GlyphInfo& glyph = fGlyphInfos.ItemAtFast(textOffset);
 929         const LineInfo& line = fLineInfos.ItemAtFast(glyph.lineIndex);
 930
 931         offset.x += glyph.x;
 932         offset.y += line.y + line.maxAscent;
 933
 934         const CharacterStyle& style = span.Style();
 935
 936         view->SetFont(&style.Font());
 937
 938         if (style.WhichForegroundColor() != B_NO_COLOR)
 939                 view->SetHighUIColor(style.WhichForegroundColor());
 940         else
 941                 view->SetHighColor(style.ForegroundColor());
 942
 943         // TODO: Implement other style properties
 944
 945         escapement_delta delta;
 946         delta.nonspace = line.extraGlyphSpacing;
 947         delta.space = line.extraWhiteSpacing;
 948
 949         view->DrawString(span.Text(), offset, &delta);
 950 }
 951
 952
 953 void
 954 ParagraphLayout::_GetEmptyLayoutBounds(float& x1, float& y1, float& x2,
 955         float& y2) const
 956 {
 957         if (fLineInfos.CountItems() == 0) {
 958                 x1 = 0.0f;
 959                 y1 = 0.0f;
 960                 x2 = 0.0f;
 961                 y2 = 0.0f;
 962
 963                 return;
 964         }
 965
 966         // If the paragraph had at least a single empty TextSpan, the layout
 967         // can compute some meaningful bounds.
 968         const Bullet& bullet = fParagraphStyle.Bullet();
 969         x1 = fParagraphStyle.LineInset() + fParagraphStyle.FirstLineInset()
 970                 + bullet.Spacing();
 971         x2 = x1;
 972         const LineInfo& lineInfo = fLineInfos.ItemAt(0);
 973         y1 = lineInfo.y;
 974         y2 = lineInfo.y + lineInfo.height;
 975 }