Implement line breaking in native code
The main purpose for this change is to prepare for adding support for
alternative line breaking algorithms (such as optimal line breaking).
The existing implementation of line breaking was intertwined with
measurement, so it wasn't structured in a way such that other line
breaking algorithms could be easily added. In addition to this,
algorithms (such as optimal line breaking) are usually fairly complex
and computation-intensive, so it is advantageous to implement them in
native code.
This has several other advantages:
* Unlike the Java code in the previous version of generate(), this
implementation separates line breaking from measurement. This
makes it easier to understand and modify the line breaking process
without affecting measurement (and vice versa).
* This native implementation of greedy line breaking is identical to
the Java version in terms of functionality, and it is similar in
terms of performance, depending on the use case. The performance
gains from this change are not significant due to increased JNI
overhead. However, this change is a step in the right direction in
terms of increasing performance. Once more code moves to C++,
there will be fewer JNI crossings per layout call and less data
will be passed from Java to C++, resulting in better performance.
This change moves line breaking from Java to native C++ code. Inspired
by the "Breaking Paragraphs into Lines" paper by Knuth and Plass (1981),
we express the line breaking problem in terms of 'box', 'glue', and
'penalty' primitives, along with a few others. Our implementation
differs in a couple ways:
* We do not want to clip text when words are wider than the view, so
we add a new primitive type to represent break opportunities
between letters. These breaks are avoided whenever possible, but
when single words do not fit on lines by themselves, they can be
broken so the entire word is visible.
* We have to support tab characters, along with user*specified tab
stops, so we add a new primitive type for that purpose.
* We are left*aligning text, and so we are not using shrinking /
stretching glue.
* We do not support hypenation, so we do not use penalties that have
widths.
Change-Id: Ia22d1d1275ef26ff3d7b41ee2658e4db525a0305
diff --git a/core/java/android/text/StaticLayout.java b/core/java/android/text/StaticLayout.java
index 2c653867..a03943d 100644
--- a/core/java/android/text/StaticLayout.java
+++ b/core/java/android/text/StaticLayout.java
@@ -28,6 +28,8 @@
import com.android.internal.util.ArrayUtils;
import com.android.internal.util.GrowingArrayUtils;
+import java.util.Arrays;
+
/**
* StaticLayout is a Layout for text that will not be edited after it
* is laid out. Use {@link DynamicLayout} for text that may change.
@@ -161,7 +163,12 @@
float spacingadd, boolean includepad,
boolean trackpad, float ellipsizedWidth,
TextUtils.TruncateAt ellipsize) {
- int[] breakOpp = null;
+ LineBreaks lineBreaks = new LineBreaks();
+ // store span end locations
+ int[] spanEndCache = new int[4];
+ // store fontMetrics per span range
+ // must be a multiple of 4 (and > 0) (store top, bottom, ascent, and descent per range)
+ int[] fmCache = new int[4 * 4];
final String localeLanguageTag = paint.getTextLocale().toLanguageTag();
mLineCount = 0;
@@ -186,7 +193,7 @@
else
paraEnd++;
- int firstWidthLineLimit = mLineCount + 1;
+ int firstWidthLineCount = 1;
int firstWidth = outerWidth;
int restWidth = outerWidth;
@@ -204,9 +211,8 @@
// leading margin spans, not just this particular one
if (lms instanceof LeadingMarginSpan2) {
LeadingMarginSpan2 lms2 = (LeadingMarginSpan2) lms;
- int lmsFirstLine = getLineForOffset(spanned.getSpanStart(lms2));
- firstWidthLineLimit = Math.max(firstWidthLineLimit,
- lmsFirstLine + lms2.getLeadingMarginLineCount());
+ firstWidthLineCount = Math.max(firstWidthLineCount,
+ lms2.getLeadingMarginLineCount());
}
}
@@ -242,32 +248,23 @@
int dir = measured.mDir;
boolean easy = measured.mEasy;
- breakOpp = nLineBreakOpportunities(localeLanguageTag, chs, paraEnd - paraStart, breakOpp);
- int breakOppIndex = 0;
-
- int width = firstWidth;
-
- float w = 0;
- // here is the offset of the starting character of the line we are currently measuring
- int here = paraStart;
-
- // ok is a character offset located after a word separator (space, tab, number...) where
- // we would prefer to cut the current line. Equals to here when no such break was found.
- int ok = paraStart;
- float okWidth = w;
- int okAscent = 0, okDescent = 0, okTop = 0, okBottom = 0;
-
- // fit is a character offset such that the [here, fit[ range fits in the allowed width.
- // We will cut the line there if no ok position is found.
- int fit = paraStart;
- float fitWidth = w;
- int fitAscent = 0, fitDescent = 0, fitTop = 0, fitBottom = 0;
-
- boolean hasTabOrEmoji = false;
- boolean hasTab = false;
- TabStops tabStops = null;
-
+ // measurement has to be done before performing line breaking
+ // but we don't want to recompute fontmetrics or span ranges the
+ // second time, so we cache those and then use those stored values
+ int fmCacheCount = 0;
+ int spanEndCacheCount = 0;
for (int spanStart = paraStart, spanEnd; spanStart < paraEnd; spanStart = spanEnd) {
+ if (fmCacheCount * 4 >= fmCache.length) {
+ int[] grow = new int[fmCacheCount * 4 * 2];
+ System.arraycopy(fmCache, 0, grow, 0, fmCacheCount * 4);
+ fmCache = grow;
+ }
+
+ if (spanEndCacheCount >= spanEndCache.length) {
+ int[] grow = new int[spanEndCacheCount * 2];
+ System.arraycopy(spanEndCache, 0, grow, 0, spanEndCacheCount);
+ spanEndCache = grow;
+ }
if (spanned == null) {
spanEnd = paraEnd;
@@ -283,197 +280,109 @@
measured.addStyleRun(paint, spans, spanLen, fm);
}
- int fmTop = fm.top;
- int fmBottom = fm.bottom;
- int fmAscent = fm.ascent;
- int fmDescent = fm.descent;
+ // the order of storage here (top, bottom, ascent, descent) has to match the code below
+ // where these values are retrieved
+ fmCache[fmCacheCount * 4 + 0] = fm.top;
+ fmCache[fmCacheCount * 4 + 1] = fm.bottom;
+ fmCache[fmCacheCount * 4 + 2] = fm.ascent;
+ fmCache[fmCacheCount * 4 + 3] = fm.descent;
+ fmCacheCount++;
- for (int j = spanStart; j < spanEnd; j++) {
- char c = chs[j - paraStart];
+ spanEndCache[spanEndCacheCount] = spanEnd;
+ spanEndCacheCount++;
+ }
- if (c == CHAR_NEW_LINE) {
- // intentionally left empty
- } else if (c == CHAR_TAB) {
- if (hasTab == false) {
- hasTab = true;
- hasTabOrEmoji = true;
- if (spanned != null) {
- // First tab this para, check for tabstops
- TabStopSpan[] spans = getParagraphSpans(spanned, paraStart,
- paraEnd, TabStopSpan.class);
- if (spans.length > 0) {
- tabStops = new TabStops(TAB_INCREMENT, spans);
- }
- }
- }
- if (tabStops != null) {
- w = tabStops.nextTab(w);
- } else {
- w = TabStops.nextDefaultStop(w, TAB_INCREMENT);
- }
- } else if (c >= CHAR_FIRST_HIGH_SURROGATE && c <= CHAR_LAST_LOW_SURROGATE
- && j + 1 < spanEnd) {
- int emoji = Character.codePointAt(chs, j - paraStart);
-
- if (emoji >= MIN_EMOJI && emoji <= MAX_EMOJI) {
- Bitmap bm = EMOJI_FACTORY.getBitmapFromAndroidPua(emoji);
-
- if (bm != null) {
- Paint whichPaint;
-
- if (spanned == null) {
- whichPaint = paint;
- } else {
- whichPaint = mWorkPaint;
- }
-
- float wid = bm.getWidth() * -whichPaint.ascent() / bm.getHeight();
-
- w += wid;
- hasTabOrEmoji = true;
- j++;
- } else {
- w += widths[j - paraStart];
- }
- } else {
- w += widths[j - paraStart];
- }
- } else {
- w += widths[j - paraStart];
+ // tab stop locations
+ int[] variableTabStops = null;
+ if (spanned != null) {
+ TabStopSpan[] spans = getParagraphSpans(spanned, paraStart,
+ paraEnd, TabStopSpan.class);
+ if (spans.length > 0) {
+ int[] stops = new int[spans.length];
+ for (int i = 0; i < spans.length; i++) {
+ stops[i] = spans[i].getTabStop();
}
-
- boolean isSpaceOrTab = c == CHAR_SPACE || c == CHAR_TAB || c == CHAR_ZWSP;
-
- if (w <= width || isSpaceOrTab) {
- fitWidth = w;
- fit = j + 1;
-
- if (fmTop < fitTop)
- fitTop = fmTop;
- if (fmAscent < fitAscent)
- fitAscent = fmAscent;
- if (fmDescent > fitDescent)
- fitDescent = fmDescent;
- if (fmBottom > fitBottom)
- fitBottom = fmBottom;
-
- while (breakOpp[breakOppIndex] != -1
- && breakOpp[breakOppIndex] < j - paraStart + 1) {
- breakOppIndex++;
- }
- boolean isLineBreak = breakOppIndex < breakOpp.length &&
- breakOpp[breakOppIndex] == j - paraStart + 1;
-
- if (isLineBreak) {
- okWidth = w;
- ok = j + 1;
-
- if (fitTop < okTop)
- okTop = fitTop;
- if (fitAscent < okAscent)
- okAscent = fitAscent;
- if (fitDescent > okDescent)
- okDescent = fitDescent;
- if (fitBottom > okBottom)
- okBottom = fitBottom;
- }
- } else {
- final boolean moreChars;
- int endPos;
- int above, below, top, bottom;
- float currentTextWidth;
-
- if (ok != here) {
- endPos = ok;
- above = okAscent;
- below = okDescent;
- top = okTop;
- bottom = okBottom;
- currentTextWidth = okWidth;
- moreChars = (j + 1 < spanEnd);
- } else if (fit != here) {
- endPos = fit;
- above = fitAscent;
- below = fitDescent;
- top = fitTop;
- bottom = fitBottom;
- currentTextWidth = fitWidth;
- moreChars = (j + 1 < spanEnd);
- } else {
- // must make progress, so take next character
- endPos = here + 1;
- // but to deal properly with clusters
- // take all zero width characters following that
- while (endPos < spanEnd && widths[endPos - paraStart] == 0) {
- endPos++;
- }
- above = fmAscent;
- below = fmDescent;
- top = fmTop;
- bottom = fmBottom;
- currentTextWidth = widths[here - paraStart];
- moreChars = (endPos < spanEnd);
- }
-
- v = out(source, here, endPos,
- above, below, top, bottom,
- v, spacingmult, spacingadd, chooseHt,chooseHtv, fm, hasTabOrEmoji,
- needMultiply, chdirs, dir, easy, bufEnd, includepad, trackpad,
- chs, widths, paraStart, ellipsize, ellipsizedWidth,
- currentTextWidth, paint, moreChars);
-
- here = endPos;
- j = here - 1; // restart j-span loop from here, compensating for the j++
- ok = fit = here;
- w = 0;
- fitAscent = fitDescent = fitTop = fitBottom = 0;
- okAscent = okDescent = okTop = okBottom = 0;
-
- if (--firstWidthLineLimit <= 0) {
- width = restWidth;
- }
-
- if (here < spanStart) {
- // The text was cut before the beginning of the current span range.
- // Exit the span loop, and get spanStart to start over from here.
- measured.setPos(here);
- spanEnd = here;
- break;
- }
-
- if (mLineCount >= mMaximumVisibleLineCount) {
- return;
- }
- }
+ Arrays.sort(stops, 0, stops.length);
+ variableTabStops = stops;
}
}
- if (paraEnd != here && mLineCount < mMaximumVisibleLineCount) {
- if ((fitTop | fitBottom | fitDescent | fitAscent) == 0) {
- paint.getFontMetricsInt(fm);
+ int breakCount = nComputeLineBreaks(localeLanguageTag, chs, widths, paraEnd - paraStart, firstWidth,
+ firstWidthLineCount, restWidth, variableTabStops, TAB_INCREMENT, lineBreaks,
+ lineBreaks.breaks, lineBreaks.widths, lineBreaks.flags, lineBreaks.breaks.length);
- fitTop = fm.top;
- fitBottom = fm.bottom;
- fitAscent = fm.ascent;
- fitDescent = fm.descent;
+ int[] breaks = lineBreaks.breaks;
+ float[] lineWidths = lineBreaks.widths;
+ boolean[] flags = lineBreaks.flags;
+
+
+ // here is the offset of the starting character of the line we are currently measuring
+ int here = paraStart;
+
+ int fmTop = 0, fmBottom = 0, fmAscent = 0, fmDescent = 0;
+ int fmCacheIndex = 0;
+ int spanEndCacheIndex = 0;
+ int breakIndex = 0;
+ for (int spanStart = paraStart, spanEnd; spanStart < paraEnd; spanStart = spanEnd) {
+ // retrieve end of span
+ spanEnd = spanEndCache[spanEndCacheIndex++];
+
+ // retrieve cached metrics, order matches above
+ fm.top = fmCache[fmCacheIndex * 4 + 0];
+ fm.bottom = fmCache[fmCacheIndex * 4 + 1];
+ fm.ascent = fmCache[fmCacheIndex * 4 + 2];
+ fm.descent = fmCache[fmCacheIndex * 4 + 3];
+ fmCacheIndex++;
+
+ if (fm.top < fmTop) {
+ fmTop = fm.top;
+ }
+ if (fm.ascent < fmAscent) {
+ fmAscent = fm.ascent;
+ }
+ if (fm.descent > fmDescent) {
+ fmDescent = fm.descent;
+ }
+ if (fm.bottom > fmBottom) {
+ fmBottom = fm.bottom;
}
- // Log.e("text", "output rest " + here + " to " + end);
+ // skip breaks ending before current span range
+ while (breakIndex < breakCount && paraStart + breaks[breakIndex] < spanStart) {
+ breakIndex++;
+ }
- v = out(source,
- here, paraEnd, fitAscent, fitDescent,
- fitTop, fitBottom,
- v,
- spacingmult, spacingadd, chooseHt,
- chooseHtv, fm, hasTabOrEmoji,
- needMultiply, chdirs, dir, easy, bufEnd,
- includepad, trackpad, chs,
- widths, paraStart, ellipsize,
- ellipsizedWidth, w, paint, paraEnd != bufEnd);
+ while (breakIndex < breakCount && paraStart + breaks[breakIndex] <= spanEnd) {
+ int endPos = paraStart + breaks[breakIndex];
+
+ boolean moreChars = (endPos < paraEnd); // XXX is this the right way to calculate this?
+
+ v = out(source, here, endPos,
+ fmAscent, fmDescent, fmTop, fmBottom,
+ v, spacingmult, spacingadd, chooseHt,chooseHtv, fm, flags[breakIndex],
+ needMultiply, chdirs, dir, easy, bufEnd, includepad, trackpad,
+ chs, widths, paraStart, ellipsize, ellipsizedWidth,
+ lineWidths[breakIndex], paint, moreChars);
+
+ if (endPos < spanEnd) {
+ // preserve metrics for current span
+ fmTop = fm.top;
+ fmBottom = fm.bottom;
+ fmAscent = fm.ascent;
+ fmDescent = fm.descent;
+ } else {
+ fmTop = fmBottom = fmAscent = fmDescent = 0;
+ }
+
+ here = endPos;
+ breakIndex++;
+
+ if (mLineCount >= mMaximumVisibleLineCount) {
+ return;
+ }
+ }
}
- paraStart = paraEnd;
-
if (paraEnd == bufEnd)
break;
}
@@ -847,10 +756,15 @@
mMeasured = MeasuredText.recycle(mMeasured);
}
- // returns an array with terminal sentinel value -1 to indicate end
- // this is so that arrays can be recycled instead of allocating new arrays
- // every time
- private static native int[] nLineBreakOpportunities(String locale, char[] text, int length, int[] recycle);
+ // populates LineBreaks and returns the number of breaks found
+ //
+ // the arrays inside the LineBreaks objects are passed in as well
+ // to reduce the number of JNI calls in the common case where the
+ // arrays do not have to be resized
+ private static native int nComputeLineBreaks(String locale, char[] text, float[] widths,
+ int length, float firstWidth, int firstWidthLineCount, float restWidth,
+ int[] variableTabStops, int defaultTabStop, LineBreaks recycle,
+ int[] recycleBreaks, float[] recycleWidths, boolean[] recycleFlags, int recycleLength);
private int mLineCount;
private int mTopPadding, mBottomPadding;
@@ -878,18 +792,23 @@
private static final int TAB_INCREMENT = 20; // same as Layout, but that's private
private static final char CHAR_NEW_LINE = '\n';
- private static final char CHAR_TAB = '\t';
- private static final char CHAR_SPACE = ' ';
- private static final char CHAR_ZWSP = '\u200B';
private static final double EXTRA_ROUNDING = 0.5;
- private static final int CHAR_FIRST_HIGH_SURROGATE = 0xD800;
- private static final int CHAR_LAST_LOW_SURROGATE = 0xDFFF;
-
/*
* This is reused across calls to generate()
*/
private MeasuredText mMeasured;
private Paint.FontMetricsInt mFontMetricsInt = new Paint.FontMetricsInt();
+
+ // This is used to return three arrays from a single JNI call when
+ // performing line breaking
+ private static class LineBreaks {
+ private static final int INITIAL_SIZE = 16;
+ public int[] breaks = new int[INITIAL_SIZE];
+ public float[] widths = new float[INITIAL_SIZE];
+ public boolean[] flags = new boolean[INITIAL_SIZE]; // hasTabOrEmoji
+ // breaks, widths, and flags should all have the same length
+ }
+
}
diff --git a/core/jni/android_text_StaticLayout.cpp b/core/jni/android_text_StaticLayout.cpp
index 9e20d18..d4a75022 100644
--- a/core/jni/android_text_StaticLayout.cpp
+++ b/core/jni/android_text_StaticLayout.cpp
@@ -24,16 +24,242 @@
#include "ScopedPrimitiveArray.h"
#include "JNIHelp.h"
#include <android_runtime/AndroidRuntime.h>
+#include <cstdint>
#include <vector>
+#include <list>
+#include <algorithm>
namespace android {
+struct JLineBreaksID {
+ jfieldID breaks;
+ jfieldID widths;
+ jfieldID flags;
+};
+
+static jclass gLineBreaks_class;
+static JLineBreaksID gLineBreaks_fieldID;
+
+static const int CHAR_SPACE = 0x20;
+static const int CHAR_TAB = 0x09;
+static const int CHAR_NEWLINE = 0x0a;
+static const int CHAR_ZWSP = 0x200b;
+
+class TabStops {
+ public:
+ // specified stops must be a sorted array (allowed to be null)
+ TabStops(JNIEnv* env, jintArray stops, jint defaultTabWidth) :
+ mStops(env), mTabWidth(defaultTabWidth) {
+ if (stops != NULL) {
+ mStops.reset(stops);
+ mNumStops = mStops.size();
+ } else {
+ mNumStops = 0;
+ }
+ }
+ float width(float widthSoFar) const {
+ const jint* mStopsArray = mStops.get();
+ for (int i = 0; i < mNumStops; i++) {
+ if (mStopsArray[i] > widthSoFar) {
+ return mStopsArray[i];
+ }
+ }
+ // find the next tabstop after widthSoFar
+ return static_cast<int>((widthSoFar + mTabWidth) / mTabWidth) * mTabWidth;
+ }
+ private:
+ ScopedIntArrayRO mStops;
+ const int mTabWidth;
+ int mNumStops;
+
+ // disable copying and assignment
+ TabStops(const TabStops&);
+ void operator=(const TabStops&);
+};
+
+enum PrimitiveType {
+ kPrimitiveType_Box,
+ kPrimitiveType_Glue,
+ kPrimitiveType_Penalty,
+ kPrimitiveType_Variable,
+ kPrimitiveType_Wordbreak
+};
+
+static const float PENALTY_INFINITY = 1e7; // forced non-break, negative infinity is forced break
+
+struct Primitive {
+ PrimitiveType type;
+ int location;
+ // 'Box' has width
+ // 'Glue' has width
+ // 'Penalty' has width and penalty
+ // 'Variable' has tabStop
+ // 'Wordbreak' has penalty
+ union {
+ struct {
+ float width;
+ float penalty;
+ };
+ const TabStops* tabStop;
+ };
+};
+
+class LineWidth {
+ public:
+ LineWidth(float firstWidth, int firstWidthLineCount, float restWidth) :
+ mFirstWidth(firstWidth), mFirstWidthLineCount(firstWidthLineCount),
+ mRestWidth(restWidth) {}
+ float getLineWidth(int line) const {
+ return (line < mFirstWidthLineCount) ? mFirstWidth : mRestWidth;
+ }
+ private:
+ const float mFirstWidth;
+ const int mFirstWidthLineCount;
+ const float mRestWidth;
+};
+
+class LineBreaker {
+ public:
+ LineBreaker(const std::vector<Primitive>& primitives,
+ const LineWidth& lineWidth) :
+ mPrimitives(primitives), mLineWidth(lineWidth) {}
+ virtual ~LineBreaker() {}
+ virtual void computeBreaks(std::vector<int>* breaks, std::vector<float>* widths,
+ std::vector<unsigned char>* flags) const = 0;
+ protected:
+ const std::vector<Primitive>& mPrimitives;
+ const LineWidth& mLineWidth;
+};
+
+class GreedyLineBreaker : public LineBreaker {
+ public:
+ GreedyLineBreaker(const std::vector<Primitive>& primitives, const LineWidth& lineWidth) :
+ LineBreaker(primitives, lineWidth) {}
+ void computeBreaks(std::vector<int>* breaks, std::vector<float>* widths,
+ std::vector<unsigned char>* flags) const {
+ int lineNum = 0;
+ float width = 0, printedWidth = 0;
+ bool breakFound = false, goodBreakFound = false;
+ int breakIndex = 0, goodBreakIndex = 0;
+ float breakWidth = 0, goodBreakWidth = 0;
+ int firstTabIndex = INT_MAX;
+
+ float maxWidth = mLineWidth.getLineWidth(lineNum);
+
+ const int numPrimitives = mPrimitives.size();
+ // greedily fit as many characters as possible on each line
+ // loop over all primitives, and choose the best break point
+ // (if possible, a break point without splitting a word)
+ // after going over the maximum length
+ for (int i = 0; i < numPrimitives; i++) {
+ const Primitive& p = mPrimitives[i];
+
+ // update the current line width
+ if (p.type == kPrimitiveType_Box || p.type == kPrimitiveType_Glue) {
+ width += p.width;
+ if (p.type == kPrimitiveType_Box) {
+ printedWidth = width;
+ }
+ } else if (p.type == kPrimitiveType_Variable) {
+ width = p.tabStop->width(width);
+ // keep track of first tab character in the region we are examining
+ // so we can determine whether or not a line contains a tab
+ firstTabIndex = std::min(firstTabIndex, i);
+ }
+
+ // find the best break point for the characters examined so far
+ if (printedWidth > maxWidth) {
+ if (breakFound || goodBreakFound) {
+ if (goodBreakFound) {
+ // a true line break opportunity existed in the characters examined so far,
+ // so there is no need to split a word
+ i = goodBreakIndex; // no +1 because of i++
+ lineNum++;
+ maxWidth = mLineWidth.getLineWidth(lineNum);
+ breaks->push_back(mPrimitives[goodBreakIndex].location);
+ widths->push_back(goodBreakWidth);
+ flags->push_back(firstTabIndex < goodBreakIndex);
+ firstTabIndex = SIZE_MAX;
+ } else {
+ // must split a word because there is no other option
+ i = breakIndex; // no +1 because of i++
+ lineNum++;
+ maxWidth = mLineWidth.getLineWidth(lineNum);
+ breaks->push_back(mPrimitives[breakIndex].location);
+ widths->push_back(breakWidth);
+ flags->push_back(firstTabIndex < breakIndex);
+ firstTabIndex = SIZE_MAX;
+ }
+ printedWidth = width = 0;
+ goodBreakFound = breakFound = false;
+ goodBreakWidth = breakWidth = 0;
+ continue;
+ } else {
+ // no choice, keep going... must make progress by putting at least one
+ // character on a line, even if part of that character is cut off --
+ // there is no other option
+ }
+ }
+
+ // update possible break points
+ if (p.type == kPrimitiveType_Penalty && p.penalty < PENALTY_INFINITY) {
+ // this does not handle penalties with width
+
+ // handle forced line break
+ if (p.penalty == -PENALTY_INFINITY) {
+ lineNum++;
+ maxWidth = mLineWidth.getLineWidth(lineNum);
+ breaks->push_back(p.location);
+ widths->push_back(printedWidth);
+ flags->push_back(firstTabIndex < i);
+ firstTabIndex = SIZE_MAX;
+ printedWidth = width = 0;
+ goodBreakFound = breakFound = false;
+ goodBreakWidth = breakWidth = 0;
+ continue;
+ }
+ if (i > breakIndex && (printedWidth <= maxWidth || breakFound == false)) {
+ breakFound = true;
+ breakIndex = i;
+ breakWidth = printedWidth;
+ }
+ if (i > goodBreakIndex && printedWidth <= maxWidth) {
+ goodBreakFound = true;
+ goodBreakIndex = i;
+ goodBreakWidth = printedWidth;
+ }
+ } else if (p.type == kPrimitiveType_Wordbreak) {
+ // only do this if necessary -- we don't want to break words
+ // when possible, but sometimes it is unavoidable
+ if (i > breakIndex && (printedWidth <= maxWidth || breakFound == false)) {
+ breakFound = true;
+ breakIndex = i;
+ breakWidth = printedWidth;
+ }
+ }
+ }
+
+ if (breakFound || goodBreakFound) {
+ // output last break if there are more characters to output
+ if (goodBreakFound) {
+ breaks->push_back(mPrimitives[goodBreakIndex].location);
+ widths->push_back(goodBreakWidth);
+ flags->push_back(firstTabIndex < goodBreakIndex);
+ } else {
+ breaks->push_back(mPrimitives[breakIndex].location);
+ widths->push_back(breakWidth);
+ flags->push_back(firstTabIndex < breakIndex);
+ }
+ }
+ }
+};
+
class ScopedBreakIterator {
public:
- ScopedBreakIterator(JNIEnv* env, BreakIterator* breakIterator, jcharArray inputText,
- jint length) : mBreakIterator(breakIterator), mChars(env, inputText) {
+ ScopedBreakIterator(JNIEnv* env, BreakIterator* breakIterator, const jchar* inputText,
+ jint length) : mBreakIterator(breakIterator), mChars(inputText) {
UErrorCode status = U_ZERO_ERROR;
- mUText = utext_openUChars(NULL, mChars.get(), length, &status);
+ mUText = utext_openUChars(NULL, mChars, length, &status);
if (mUText == NULL) {
return;
}
@@ -51,7 +277,7 @@
}
private:
BreakIterator* mBreakIterator;
- ScopedCharArrayRO mChars;
+ const jchar* mChars;
UText* mUText;
// disable copying and assignment
@@ -59,11 +285,83 @@
void operator=(const ScopedBreakIterator&);
};
-static jintArray nLineBreakOpportunities(JNIEnv* env, jclass, jstring javaLocaleName,
- jcharArray inputText, jint length,
- jintArray recycle) {
+static jint recycleCopy(JNIEnv* env, jobject recycle, jintArray recycleBreaks,
+ jfloatArray recycleWidths, jbooleanArray recycleFlags,
+ jint recycleLength, const std::vector<jint>& breaks,
+ const std::vector<jfloat>& widths, const std::vector<jboolean>& flags) {
+ int bufferLength = breaks.size();
+ if (recycleLength < bufferLength) {
+ // have to reallocate buffers
+ recycleBreaks = env->NewIntArray(bufferLength);
+ recycleWidths = env->NewFloatArray(bufferLength);
+ recycleFlags = env->NewBooleanArray(bufferLength);
+
+ env->SetObjectField(recycle, gLineBreaks_fieldID.breaks, recycleBreaks);
+ env->SetObjectField(recycle, gLineBreaks_fieldID.widths, recycleWidths);
+ env->SetObjectField(recycle, gLineBreaks_fieldID.flags, recycleFlags);
+ }
+ // copy data
+ env->SetIntArrayRegion(recycleBreaks, 0, breaks.size(), &breaks.front());
+ env->SetFloatArrayRegion(recycleWidths, 0, widths.size(), &widths.front());
+ env->SetBooleanArrayRegion(recycleFlags, 0, flags.size(), &flags.front());
+
+ return bufferLength;
+}
+
+void computePrimitives(const jchar* textArr, const jfloat* widthsArr, jint length, const std::vector<int>& breaks,
+ const TabStops& tabStopCalculator, std::vector<Primitive>* primitives) {
+ int breaksSize = breaks.size();
+ int breakIndex = 0;
+ Primitive p;
+ for (int i = 0; i < length; i++) {
+ p.location = i;
+ jchar c = textArr[i];
+ if (c == CHAR_SPACE || c == CHAR_ZWSP) {
+ p.type = kPrimitiveType_Glue;
+ p.width = widthsArr[i];
+ primitives->push_back(p);
+ } else if (c == CHAR_TAB) {
+ p.type = kPrimitiveType_Variable;
+ p.tabStop = &tabStopCalculator; // shared between all variable primitives
+ primitives->push_back(p);
+ } else if (c != CHAR_NEWLINE) {
+ while (breakIndex < breaksSize && breaks[breakIndex] < i) breakIndex++;
+ p.width = 0;
+ if (breakIndex < breaksSize && breaks[breakIndex] == i) {
+ p.type = kPrimitiveType_Penalty;
+ p.penalty = 0;
+ } else {
+ p.type = kPrimitiveType_Wordbreak;
+ }
+ if (widthsArr[i] != 0) {
+ primitives->push_back(p);
+ }
+
+ p.type = kPrimitiveType_Box;
+ p.width = widthsArr[i];
+ primitives->push_back(p);
+ }
+ }
+ // final break at end of everything
+ p.location = length;
+ p.type = kPrimitiveType_Penalty;
+ p.width = 0;
+ p.penalty = -PENALTY_INFINITY;
+ primitives->push_back(p);
+}
+
+static jint nComputeLineBreaks(JNIEnv* env, jclass, jstring javaLocaleName,
+ jcharArray inputText, jfloatArray widths, jint length,
+ jfloat firstWidth, jint firstWidthLineLimit, jfloat restWidth,
+ jintArray variableTabStops, jint defaultTabStop,
+ jobject recycle, jintArray recycleBreaks,
+ jfloatArray recycleWidths, jbooleanArray recycleFlags,
+ jint recycleLength) {
jintArray ret;
- std::vector<jint> breaks;
+ std::vector<int> breaks;
+
+ ScopedCharArrayRO textScopedArr(env, inputText);
+ ScopedFloatArrayRO widthsScopedArr(env, widths);
ScopedIcuLocale icuLocale(env, javaLocaleName);
if (icuLocale.valid()) {
@@ -74,35 +372,43 @@
delete it;
}
} else {
- ScopedBreakIterator breakIterator(env, it, inputText, length);
- for (int loc = breakIterator->first(); loc != BreakIterator::DONE;
- loc = breakIterator->next()) {
+ ScopedBreakIterator breakIterator(env, it, textScopedArr.get(), length);
+ int loc = breakIterator->first();
+ while ((loc = breakIterator->next()) != BreakIterator::DONE) {
breaks.push_back(loc);
}
}
}
- breaks.push_back(-1); // sentinel terminal value
+ std::vector<Primitive> primitives;
+ TabStops tabStops(env, variableTabStops, defaultTabStop);
+ computePrimitives(textScopedArr.get(), widthsScopedArr.get(), length, breaks, tabStops, &primitives);
- if (recycle != NULL && static_cast<size_t>(env->GetArrayLength(recycle)) >= breaks.size()) {
- ret = recycle;
- } else {
- ret = env->NewIntArray(breaks.size());
- }
+ LineWidth lineWidth(firstWidth, firstWidthLineLimit, restWidth);
+ std::vector<int> computedBreaks;
+ std::vector<float> computedWidths;
+ std::vector<unsigned char> computedFlags;
- if (ret != NULL) {
- env->SetIntArrayRegion(ret, 0, breaks.size(), &breaks.front());
- }
+ GreedyLineBreaker breaker(primitives, lineWidth);
+ breaker.computeBreaks(&computedBreaks, &computedWidths, &computedFlags);
- return ret;
+ return recycleCopy(env, recycle, recycleBreaks, recycleWidths, recycleFlags, recycleLength,
+ computedBreaks, computedWidths, computedFlags);
}
static JNINativeMethod gMethods[] = {
- {"nLineBreakOpportunities", "(Ljava/lang/String;[CI[I)[I", (void*) nLineBreakOpportunities}
+ {"nComputeLineBreaks", "(Ljava/lang/String;[C[FIFIF[IILandroid/text/StaticLayout$LineBreaks;[I[F[ZI)I", (void*) nComputeLineBreaks}
};
int register_android_text_StaticLayout(JNIEnv* env)
{
+ gLineBreaks_class = reinterpret_cast<jclass>(env->NewGlobalRef(
+ env->FindClass("android/text/StaticLayout$LineBreaks")));
+
+ gLineBreaks_fieldID.breaks = env->GetFieldID(gLineBreaks_class, "breaks", "[I");
+ gLineBreaks_fieldID.widths = env->GetFieldID(gLineBreaks_class, "widths", "[F");
+ gLineBreaks_fieldID.flags = env->GetFieldID(gLineBreaks_class, "flags", "[Z");
+
return AndroidRuntime::registerNativeMethods(env, "android/text/StaticLayout",
gMethods, NELEM(gMethods));
}
