haiku.git

/*
 * Copyright 2001-2013, Haiku, Inc. All rights reserved.
 * Distributed under the terms of the MIT License.
 *
 * Authors:
 *		Stephan Aßmus, superstippi@gmx.de
 *		Stefano Ceccherini, stefano.ceccherini@gmail.com
 *		Marc Flerackers, mflerackers@androme.be
 *		Hiroshi Lockheimer (BTextView is based on his STEEngine)
 *		Oliver Tappe, zooey@hirschkaefer.de
 *      Andrew Lindesay, apl@lindesay.co.nz
 */

#include "ParagraphLayout.h"

#include <new>
#include <stdio.h>

#include <AutoDeleter.h>
#include <utf8_functions.h>
#include <View.h>


enum {
	CHAR_CLASS_DEFAULT,
	CHAR_CLASS_WHITESPACE,
	CHAR_CLASS_GRAPHICAL,
	CHAR_CLASS_QUOTE,
	CHAR_CLASS_PUNCTUATION,
	CHAR_CLASS_PARENS_OPEN,
	CHAR_CLASS_PARENS_CLOSE,
	CHAR_CLASS_END_OF_TEXT
};


inline uint32
get_char_classification(uint32 charCode)
{
	// TODO: Should check against a list of characters containing also
	// word breakers from other languages.

	switch (charCode) {
		case '\0':
			return CHAR_CLASS_END_OF_TEXT;

		case ' ':
		case '\t':
		case '\n':
			return CHAR_CLASS_WHITESPACE;

		case '=':
		case '+':
		case '@':
		case '#':
		case '$':
		case '%':
		case '^':
		case '&':
		case '*':
		case '\\':
		case '|':
		case '<':
		case '>':
		case '/':
		case '~':
			return CHAR_CLASS_GRAPHICAL;

		case '\'':
		case '"':
			return CHAR_CLASS_QUOTE;

		case ',':
		case '.':
		case '?':
		case '!':
		case ';':
		case ':':
		case '-':
			return CHAR_CLASS_PUNCTUATION;

		case '(':
		case '[':
		case '{':
			return CHAR_CLASS_PARENS_OPEN;

		case ')':
		case ']':
		case '}':
			return CHAR_CLASS_PARENS_CLOSE;

		default:
			return CHAR_CLASS_DEFAULT;
	}
}


inline bool
can_end_line(const std::vector<GlyphInfo>& glyphInfos, int offset)
{
	int count = static_cast<int>(glyphInfos.size());

	if (offset == count - 1)
		return true;

	if (offset < 0 || offset > count)
		return false;

	uint32 charCode = glyphInfos[offset].charCode;
	uint32 classification = get_char_classification(charCode);

	// wrapping is always allowed at end of text and at newlines
	if (classification == CHAR_CLASS_END_OF_TEXT || charCode == '\n')
		return true;

	uint32 nextCharCode = glyphInfos[offset + 1].charCode;
	uint32 nextClassification = get_char_classification(nextCharCode);

	// never separate a punctuation char from its preceding word
	if (classification == CHAR_CLASS_DEFAULT
		&& nextClassification == CHAR_CLASS_PUNCTUATION) {
		return false;
	}

	if ((classification == CHAR_CLASS_WHITESPACE
			&& nextClassification != CHAR_CLASS_WHITESPACE)
		|| (classification != CHAR_CLASS_WHITESPACE
			&& nextClassification == CHAR_CLASS_WHITESPACE)) {
		return true;
	}

	// allow wrapping after whitespace, unless more whitespace (except for
	// newline) follows
	if (classification == CHAR_CLASS_WHITESPACE
		&& (nextClassification != CHAR_CLASS_WHITESPACE
			|| nextCharCode == '\n')) {
		return true;
	}

	// allow wrapping after punctuation chars, unless more punctuation, closing
	// parenthesis or quotes follow
	if (classification == CHAR_CLASS_PUNCTUATION
		&& nextClassification != CHAR_CLASS_PUNCTUATION
		&& nextClassification != CHAR_CLASS_PARENS_CLOSE
		&& nextClassification != CHAR_CLASS_QUOTE) {
		return true;
	}

	// allow wrapping after quotes, graphical chars and closing parenthesis only
	// if whitespace follows (not perfect, but seems to do the right thing most
	// of the time)
	if ((classification == CHAR_CLASS_QUOTE
			|| classification == CHAR_CLASS_GRAPHICAL
			|| classification == CHAR_CLASS_PARENS_CLOSE)
		&& nextClassification == CHAR_CLASS_WHITESPACE) {
		return true;
	}

	return false;
}


// #pragma mark - ParagraphLayout


ParagraphLayout::ParagraphLayout()
	:
	fTextSpans(),
	fParagraphStyle(),

	fWidth(0.0f),
	fLayoutValid(false),

	fGlyphInfos(),
	fLineInfos()
{
}


ParagraphLayout::ParagraphLayout(const Paragraph& paragraph)
	:
	fTextSpans(),
	fParagraphStyle(paragraph.Style()),

	fWidth(0.0f),
	fLayoutValid(false),

	fGlyphInfos(),
	fLineInfos()
{
	_AppendTextSpans(paragraph);
	_Init();
}


ParagraphLayout::ParagraphLayout(const ParagraphLayout& other)
	:
	fTextSpans(other.fTextSpans),
	fParagraphStyle(other.fParagraphStyle),

	fWidth(other.fWidth),
	fLayoutValid(false),

	fGlyphInfos(other.fGlyphInfos),
	fLineInfos()
{
}


ParagraphLayout::~ParagraphLayout()
{
}


void
ParagraphLayout::SetParagraph(const Paragraph& paragraph)
{
	fTextSpans.clear();
	_AppendTextSpans(paragraph);
	fParagraphStyle = paragraph.Style();

	_Init();

	fLayoutValid = false;
}


void
ParagraphLayout::SetWidth(float width)
{
	if (fWidth != width) {
		fWidth = width;
		fLayoutValid = false;
	}
}


float
ParagraphLayout::Height()
{
	_ValidateLayout();

	float height = 0.0f;

	if (!fLineInfos.empty()) {
		const LineInfo& lastLine = fLineInfos[fLineInfos.size() - 1];
		height = lastLine.y + lastLine.height;
	}

	return height;
}


void
ParagraphLayout::Draw(BView* view, const BPoint& offset)
{
	_ValidateLayout();

	int lineCount = static_cast<int>(fLineInfos.size());
	for (int i = 0; i < lineCount; i++) {
		const LineInfo& line = fLineInfos[i];
		_DrawLine(view, offset, line);
	}

	const Bullet& bullet = fParagraphStyle.Bullet();
	if (bullet.Spacing() > 0.0f && bullet.String().Length() > 0) {
		// Draw bullet at offset
		view->SetHighUIColor(B_PANEL_TEXT_COLOR);
		BPoint bulletPos(offset);
		bulletPos.x += fParagraphStyle.FirstLineInset()
			+ fParagraphStyle.LineInset();
		bulletPos.y += fLineInfos[0].maxAscent;
		view->DrawString(bullet.String(), bulletPos);
	}
}


int32
ParagraphLayout::CountGlyphs() const
{
	return static_cast<int32>(fGlyphInfos.size());
}


int32
ParagraphLayout::CountLines()
{
	_ValidateLayout();
	return static_cast<int32>(fLineInfos.size());
}


int32
ParagraphLayout::LineIndexForOffset(int32 textOffset)
{
	_ValidateLayout();

	if (fGlyphInfos.empty())
		return 0;

	if (textOffset >= static_cast<int32>(fGlyphInfos.size())) {
		const GlyphInfo& glyph = fGlyphInfos[fGlyphInfos.size() - 1];
		return glyph.lineIndex;
	}

	if (textOffset < 0)
		textOffset = 0;

	const GlyphInfo& glyph = fGlyphInfos[textOffset];
	return glyph.lineIndex;
}


int32
ParagraphLayout::FirstOffsetOnLine(int32 lineIndex)
{
	_ValidateLayout();

	if (lineIndex < 0)
		lineIndex = 0;
	int32 countLineInfos = static_cast<int32>(fLineInfos.size());
	if (lineIndex >= countLineInfos)
		lineIndex = countLineInfos - 1;

	return fLineInfos[lineIndex].textOffset;
}


int32
ParagraphLayout::LastOffsetOnLine(int32 lineIndex)
{
	_ValidateLayout();

	if (lineIndex < 0)
		lineIndex = 0;

	if (lineIndex >= static_cast<int32>(fLineInfos.size()) - 1)
		return CountGlyphs() - 1;

	return fLineInfos[lineIndex + 1].textOffset - 1;
}


void
ParagraphLayout::GetLineBounds(int32 lineIndex, float& x1, float& y1,
	float& x2, float& y2)
{
	_ValidateLayout();

	if (fGlyphInfos.empty()) {
		_GetEmptyLayoutBounds(x1, y1, x2, y2);
		return;
	}

	if (lineIndex < 0)
		lineIndex = 0;
	int32 countLineInfos = static_cast<int32>(fLineInfos.size());
	if (lineIndex >= countLineInfos)
		lineIndex = countLineInfos - 1;

	const LineInfo& lineInfo = fLineInfos[lineIndex];
	int32 firstGlyphIndex = lineInfo.textOffset;

	int32 lastGlyphIndex;
	if (lineIndex < countLineInfos - 1)
		lastGlyphIndex = fLineInfos[lineIndex + 1].textOffset - 1;
	else
		lastGlyphIndex = static_cast<int32>(fGlyphInfos.size()) - 1;

	const GlyphInfo& firstInfo = fGlyphInfos[firstGlyphIndex];
	const GlyphInfo& lastInfo = fGlyphInfos[lastGlyphIndex];

	x1 = firstInfo.x;
	y1 = lineInfo.y;
	x2 = lastInfo.x + lastInfo.width;
	y2 = lineInfo.y + lineInfo.height;
}


void
ParagraphLayout::GetTextBounds(int32 textOffset, float& x1, float& y1,
	float& x2, float& y2)
{
	_ValidateLayout();

	if (fGlyphInfos.empty()) {
		_GetEmptyLayoutBounds(x1, y1, x2, y2);
		return;
	}

	if (textOffset >= static_cast<int32>(fGlyphInfos.size())) {
		const GlyphInfo& glyph = fGlyphInfos[fGlyphInfos.size() - 1];
		const LineInfo& line = fLineInfos[glyph.lineIndex];

		x1 = glyph.x + glyph.width;
		x2 = x1;
		y1 = line.y;
		y2 = y1 + line.height;

		return;
	}

	if (textOffset < 0)
		textOffset = 0;

	const GlyphInfo& glyph = fGlyphInfos[textOffset];
	const LineInfo& line = fLineInfos[glyph.lineIndex];

	x1 = glyph.x;
	x2 = x1 + glyph.width;
	y1 = line.y;
	y2 = y1 + line.height;
}


int32
ParagraphLayout::TextOffsetAt(float x, float y, bool& rightOfCenter)
{
	_ValidateLayout();

	rightOfCenter = false;

	int32 lineCount = static_cast<int32>(fLineInfos.size());
	if (fGlyphInfos.empty() || lineCount == 0
		|| fLineInfos[0].y > y) {
		// Above first line or empty text
		return 0;
	}

	int32 lineIndex = 0;
	LineInfo lastLineInfo = fLineInfos[fLineInfos.size() - 1];
	if (floorf(lastLineInfo.y + lastLineInfo.height + 0.5) > y) {
		// TODO: Optimize, can binary search line here:
		for (; lineIndex < lineCount; lineIndex++) {
			const LineInfo& line = fLineInfos[lineIndex];
			float lineBottom = floorf(line.y + line.height + 0.5);
			if (lineBottom > y)
				break;
		}
	} else {
		lineIndex = lineCount - 1;
	}

	// Found line
	const LineInfo& line = fLineInfos[lineIndex];
	int32 textOffset = line.textOffset;
	int32 end;
	if (lineIndex < lineCount - 1)
		end = fLineInfos[lineIndex + 1].textOffset - 1;
	else
		end = fGlyphInfos.size() - 1;

	// TODO: Optimize, can binary search offset here:
	for (; textOffset <= end; textOffset++) {
		const GlyphInfo& glyph = fGlyphInfos[textOffset];
		float x1 = glyph.x;
		if (x1 > x)
			return textOffset;

		// x2 is the location at the right bounding box of the glyph
		float x2 = x1 + glyph.width;

		// x3 is the location of the next glyph, which may be different from
		// x2 in case the line is justified.
		float x3;
		if (textOffset < end - 1)
			x3 = fGlyphInfos[textOffset + 1].x;
		else
			x3 = x2;

		if (x3 > x) {
			rightOfCenter = x > (x1 + x2) / 2.0f;
			return textOffset;
		}
	}

	// Account for trailing line break at end of line, the
	// returned offset should be before that.
	rightOfCenter = fGlyphInfos[end].charCode != '\n';

	return end;
}


// #pragma mark - private


void
ParagraphLayout::_Init()
{
	fGlyphInfos.clear();

	std::vector<TextSpan>::const_iterator it;
	for (it = fTextSpans.begin(); it != fTextSpans.end(); it++) {
		const TextSpan& span = *it;
		if (!_AppendGlyphInfos(span)) {
			fprintf(stderr, "%p->ParagraphLayout::_Init() - Out of memory\n",
				this);
			return;
		}
	}
}


void
ParagraphLayout::_ValidateLayout()
{
	if (!fLayoutValid) {
		_Layout();
		fLayoutValid = true;
	}
}


void
ParagraphLayout::_Layout()
{
	fLineInfos.clear();

	const Bullet& bullet = fParagraphStyle.Bullet();

	float x = fParagraphStyle.LineInset() + fParagraphStyle.FirstLineInset()
		+ bullet.Spacing();
	float y = 0.0f;
	int lineIndex = 0;
	int lineStart = 0;

	int glyphCount = static_cast<int>(fGlyphInfos.size());
	for (int i = 0; i < glyphCount; i++) {
		GlyphInfo glyph = fGlyphInfos[i];

		uint32 charClassification = get_char_classification(glyph.charCode);

		float advanceX = glyph.width;
		float advanceY = 0.0f;

		bool nextLine = false;
		bool lineBreak = false;

//		if (glyph.charCode == '\t') {
//			// Figure out tab width, it's the width between the last two tab
//			// stops.
//			float tabWidth = 0.0f;
//			if (fTabCount > 0)
//				tabWidth = fTabBuffer[fTabCount - 1];
//			if (fTabCount > 1)
//				tabWidth -= fTabBuffer[fTabCount - 2];
//
//			// Try to find a tab stop that is farther than the current x
//			// offset
//			double tabOffset = 0.0;
//			for (unsigned tabIndex = 0; tabIndex < fTabCount; tabIndex++) {
//				tabOffset = fTabBuffer[tabIndex];
//				if (tabOffset > x)
//					break;
//			}
//
//			// If no tab stop has been found, make the tab stop a multiple of
//			// the tab width
//			if (tabOffset <= x && tabWidth > 0.0)
//				tabOffset = ((int) (x / tabWidth) + 1) * tabWidth;
//
//			if (tabOffset - x > 0.0)
//				advanceX = tabOffset - x;
//		}

		if (glyph.charCode == '\n') {
			nextLine = true;
			lineBreak = true;
			glyph.x = x;
			fGlyphInfos[i] = glyph;
		} else if (fWidth > 0.0f && x + advanceX > fWidth) {
			fGlyphInfos[i] = glyph;
			if (charClassification == CHAR_CLASS_WHITESPACE) {
				advanceX = 0.0f;
			} else if (i > lineStart) {
				nextLine = true;
				// The current glyph extends outside the width, we need to wrap
				// to the next line. See what previous offset can be the end
				// of the line.
				int lineEnd = i - 1;
				while (lineEnd > lineStart
					&& !can_end_line(fGlyphInfos, lineEnd)) {
					lineEnd--;
				}

				if (lineEnd > lineStart) {
					// Found a place to perform a line break.
					i = lineEnd + 1;

					// Adjust the glyph info to point at the changed buffer
					// position
					glyph = fGlyphInfos[i];
					advanceX = glyph.width;
				} else {
					// Just break where we are.
				}
			}
		}

		if (nextLine) {
			// * Initialize the max ascent/descent of all preceding glyph infos
			// on the current/last line
			// * Adjust the baseline offset according to the max ascent
			// * Fill in the line index.
			unsigned lineEnd;
			if (lineBreak)
				lineEnd = i;
			else
				lineEnd = i - 1;

			float lineHeight = 0.0;
			_FinalizeLine(lineStart, lineEnd, lineIndex, y, lineHeight);

			// Start position of the next line
			x = fParagraphStyle.LineInset() + bullet.Spacing();
			y += lineHeight + fParagraphStyle.LineSpacing();

			if (lineBreak)
				lineStart = i + 1;
			else
				lineStart = i;

			lineIndex++;
		}

		if (!lineBreak && i < glyphCount) {
			glyph.x = x;
			fGlyphInfos[i] = glyph;
		}

		x += advanceX;
		y += advanceY;
	}

	// The last line may not have been appended and initialized yet.
	if (lineStart <= glyphCount - 1 || glyphCount == 0) {
		float lineHeight;
		_FinalizeLine(lineStart, glyphCount - 1, lineIndex, y, lineHeight);
	}

	_ApplyAlignment();
}


void
ParagraphLayout::_ApplyAlignment()
{
	Alignment alignment = fParagraphStyle.Alignment();
	bool justify = fParagraphStyle.Justify();

	if (alignment == ALIGN_LEFT && !justify)
		return;

	int glyphCount = static_cast<int>(fGlyphInfos.size());
	if (glyphCount == 0)
		return;

	int lineIndex = -1;
	float spaceLeft = 0.0f;
	float charSpace = 0.0f;
	float whiteSpace = 0.0f;
	bool seenChar = false;

	// Iterate all glyphs backwards. On the last character of the next line,
	// the position of the character determines the available space to be
	// distributed (spaceLeft).
	for (int i = glyphCount - 1; i >= 0; i--) {
		GlyphInfo glyph = fGlyphInfos[i];

		if (glyph.lineIndex != lineIndex) {
			bool lineBreak = glyph.charCode == '\n' || i == glyphCount - 1;
			lineIndex = glyph.lineIndex;

			// The position of the last character determines the available
			// space.
			spaceLeft = fWidth - glyph.x;

			// If the character is visible, the width of the character needs to
			// be subtracted from the available space, otherwise it would be
			// pushed outside the line.
			uint32 charClassification = get_char_classification(glyph.charCode);
			if (charClassification != CHAR_CLASS_WHITESPACE)
				spaceLeft -= glyph.width;

			charSpace = 0.0f;
			whiteSpace = 0.0f;
			seenChar = false;

			if (lineBreak || !justify) {
				if (alignment == ALIGN_CENTER)
					spaceLeft /= 2.0f;
				else if (alignment == ALIGN_LEFT)
					spaceLeft = 0.0f;
			} else {
				// Figure out how much chars and white space chars are on the
				// line. Don't count trailing white space.
				int charCount = 0;
				int spaceCount = 0;
				for (int j = i; j >= 0; j--) {
					const GlyphInfo& previousGlyph = fGlyphInfos[j];
					if (previousGlyph.lineIndex != lineIndex) {
						j++;
						break;
					}
					uint32 classification = get_char_classification(
						previousGlyph.charCode);
					if (classification == CHAR_CLASS_WHITESPACE) {
						if (charCount > 0)
							spaceCount++;
						else if (j < i)
							spaceLeft += glyph.width;
					} else {
						charCount++;
					}
				}

				// The first char is not shifted when justifying, so it doesn't
				// contribute.
				if (charCount > 0)
					charCount--;

				// Check if it looks better if both whitespace and chars get
				// some space distributed, in case there are only 1 or two
				// space chars on the line.
				float spaceLeftForSpace = spaceLeft;
				float spaceLeftForChars = spaceLeft;

				if (spaceCount > 0) {
					float spaceCharRatio = (float) spaceCount / charCount;
					if (spaceCount < 3 && spaceCharRatio < 0.4f) {
						spaceLeftForSpace = spaceLeft * 2.0f * spaceCharRatio;
						spaceLeftForChars = spaceLeft - spaceLeftForSpace;
					} else
						spaceLeftForChars = 0.0f;
				}

				if (spaceCount > 0)
					whiteSpace = spaceLeftForSpace / spaceCount;
				if (charCount > 0)
					charSpace = spaceLeftForChars / charCount;

				LineInfo line = fLineInfos[lineIndex];
				line.extraGlyphSpacing = charSpace;
				line.extraWhiteSpacing = whiteSpace;

				fLineInfos[lineIndex] = line;
			}
		}

		// Each character is pushed towards the right by the space that is
		// still available. When justification is performed, the shift is
		// gradually decreased. This works since the iteration is backwards
		// and the characters on the right are pushed farthest.
		glyph.x += spaceLeft;

		unsigned classification = get_char_classification(glyph.charCode);

		if (i < glyphCount - 1) {
			GlyphInfo nextGlyph = fGlyphInfos[i + 1];
			if (nextGlyph.lineIndex == lineIndex) {
				uint32 nextClassification
					= get_char_classification(nextGlyph.charCode);
				if (nextClassification == CHAR_CLASS_WHITESPACE
					&& classification != CHAR_CLASS_WHITESPACE) {
					// When a space character is right of a regular character,
					// add the additional space to the space instead of the
					// character
					float shift = (nextGlyph.x - glyph.x) - glyph.width;
					nextGlyph.x -= shift;
					fGlyphInfos[i + 1] = nextGlyph;
				}
			}
		}

		fGlyphInfos[i] = glyph;

		// The shift (spaceLeft) is reduced depending on the character
		// classification.
		if (classification == CHAR_CLASS_WHITESPACE) {
			if (seenChar)
				spaceLeft -= whiteSpace;
		} else {
			seenChar = true;
			spaceLeft -= charSpace;
		}
	}
}


bool
ParagraphLayout::_AppendGlyphInfos(const TextSpan& span)
{
	int charCount = span.CountChars();
	if (charCount == 0)
		return true;

	const BString& text = span.Text();
	const BFont& font = span.Style().Font();

	// Allocate arrays
	float* escapementArray = new (std::nothrow) float[charCount];
	if (escapementArray == NULL)
		return false;
	ArrayDeleter<float> escapementDeleter(escapementArray);

	// Fetch glyph spacing information
	font.GetEscapements(text, charCount, escapementArray);

	// Append to glyph buffer and convert escapement scale
	float size = font.Size();
	const char* c = text.String();
	for (int i = 0; i < charCount; i++) {
		if (!_AppendGlyphInfo(UTF8ToCharCode(&c), escapementArray[i] * size,
				span.Style())) {
			return false;
		}
	}

	return true;
}


bool
ParagraphLayout::_AppendGlyphInfo(uint32 charCode, float width,
	const CharacterStyle& style)
{
	if (style.Width() >= 0.0f) {
		// Use the metrics provided by the CharacterStyle and override
		// the font provided metrics passed in "width"
		width = style.Width();
	}

	width += style.GlyphSpacing();

	try {
		fGlyphInfos.push_back(GlyphInfo(charCode, 0.0f, width, 0));
	}
	catch (std::bad_alloc& ba) {
		fprintf(stderr, "bad_alloc occurred adding glyph info to a "
			"paragraph\n");
		return false;
	}

	return true;
}


bool
ParagraphLayout::_FinalizeLine(int lineStart, int lineEnd, int lineIndex,
	float y, float& lineHeight)
{
	LineInfo line(lineStart, y, 0.0f, 0.0f, 0.0f);

	int spanIndex = -1;
	int spanStart = 0;
	int spanEnd = 0;

	for (int i = lineStart; i <= lineEnd; i++) {
		// Mark line index in glyph
		GlyphInfo glyph = fGlyphInfos[i];
		glyph.lineIndex = lineIndex;
		fGlyphInfos[i] = glyph;

		// See if the next sub-span needs to be added to the LineInfo
		bool addSpan = false;

		while (i >= spanEnd) {
			spanIndex++;
			const TextSpan& span = fTextSpans[spanIndex];
			spanStart = spanEnd;
			spanEnd += span.CountChars();
			addSpan = true;
		}

		if (addSpan) {
			const TextSpan& span = fTextSpans[spanIndex];
			TextSpan subSpan = span.SubSpan(i - spanStart,
				(lineEnd - spanStart + 1) - (i - spanStart));
			line.layoutedSpans.push_back(subSpan);
			_IncludeStyleInLine(line, span.Style());
		}
	}

	if (fGlyphInfos.empty() && !fTextSpans.empty()) {
		// When the layout contains no glyphs, but there is at least one
		// TextSpan in the paragraph, use the font info from that span
		// to calculate the height of the first LineInfo.
		const TextSpan& span = fTextSpans[0];
		line.layoutedSpans.push_back(span);
		_IncludeStyleInLine(line, span.Style());
	}

	lineHeight = line.height;

	try {
		fLineInfos.push_back(line);
	}
	catch (std::bad_alloc& ba) {
		fprintf(stderr, "bad_alloc occurred adding line to line infos\n");
		return false;
	}

	return true;
}


void
ParagraphLayout::_IncludeStyleInLine(LineInfo& line,
	const CharacterStyle& style)
{
	float ascent = style.Ascent();
	if (ascent > line.maxAscent)
		line.maxAscent = ascent;

	float descent = style.Descent();
	if (descent > line.maxDescent)
		line.maxDescent = descent;

	float height = ascent + descent;
	if (style.Font().Size() > height)
		height = style.Font().Size();

	if (height > line.height)
		line.height = height;
}


void
ParagraphLayout::_DrawLine(BView* view, const BPoint& offset,
	const LineInfo& line) const
{
	int textOffset = line.textOffset;
	int spanCount = static_cast<int>(line.layoutedSpans.size());
	for (int i = 0; i < spanCount; i++) {
		const TextSpan& span = line.layoutedSpans[i];
		_DrawSpan(view, offset, span, textOffset);
		textOffset += span.CountChars();
	}
}


void
ParagraphLayout::_DrawSpan(BView* view, BPoint offset,
	const TextSpan& span, int32 textOffset) const
{
	const BString& text = span.Text();
	if (text.Length() == 0)
		return;

	const GlyphInfo& glyph = fGlyphInfos[textOffset];
	const LineInfo& line = fLineInfos[glyph.lineIndex];

	offset.x += glyph.x;
	offset.y += line.y + line.maxAscent;

	const CharacterStyle& style = span.Style();

	view->SetFont(&style.Font());

	if (style.WhichForegroundColor() != B_NO_COLOR)
		view->SetHighUIColor(style.WhichForegroundColor());
	else
		view->SetHighColor(style.ForegroundColor());

	// TODO: Implement other style properties

	escapement_delta delta;
	delta.nonspace = line.extraGlyphSpacing;
	delta.space = line.extraWhiteSpacing;

	view->DrawString(span.Text(), offset, &delta);
}


void
ParagraphLayout::_GetEmptyLayoutBounds(float& x1, float& y1, float& x2,
	float& y2) const
{
	if (fLineInfos.empty()) {
		x1 = 0.0f;
		y1 = 0.0f;
		x2 = 0.0f;
		y2 = 0.0f;

		return;
	}

	// If the paragraph had at least a single empty TextSpan, the layout
	// can compute some meaningful bounds.
	const Bullet& bullet = fParagraphStyle.Bullet();
	x1 = fParagraphStyle.LineInset() + fParagraphStyle.FirstLineInset()
		+ bullet.Spacing();
	x2 = x1;
	const LineInfo& lineInfo = fLineInfos[0];
	y1 = lineInfo.y;
	y2 = lineInfo.y + lineInfo.height;
}


void
ParagraphLayout::_AppendTextSpans(const Paragraph& paragraph)
{
	int32 countTextSpans = paragraph.CountTextSpans();
	for (int32 i = 0; i< countTextSpans; i++)
		fTextSpans.push_back(paragraph.TextSpanAtIndex(i));
}