GreedyLineBreaker.java revision 7053919a3a55ad1b58e6db701afda18850037732
17053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta/* 27053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta * Copyright (C) 2014 The Android Open Source Project 37053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta * 47053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta * Licensed under the Apache License, Version 2.0 (the "License"); 57053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta * you may not use this file except in compliance with the License. 67053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta * You may obtain a copy of the License at 77053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta * 87053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta * http://www.apache.org/licenses/LICENSE-2.0 97053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta * 107053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta * Unless required by applicable law or agreed to in writing, software 117053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta * distributed under the License is distributed on an "AS IS" BASIS, 127053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 137053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta * See the License for the specific language governing permissions and 147053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta * limitations under the License. 157053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta */ 167053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta 177053919a3a55ad1b58e6db701afda18850037732Deepanshu Guptapackage android.text; 187053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta 197053919a3a55ad1b58e6db701afda18850037732Deepanshu Guptaimport com.android.annotations.NonNull; 207053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta 217053919a3a55ad1b58e6db701afda18850037732Deepanshu Guptaimport android.text.Primitive.PrimitiveType; 227053919a3a55ad1b58e6db701afda18850037732Deepanshu Guptaimport android.text.StaticLayout.LineBreaks; 237053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta 247053919a3a55ad1b58e6db701afda18850037732Deepanshu Guptaimport java.util.ArrayList; 257053919a3a55ad1b58e6db701afda18850037732Deepanshu Guptaimport java.util.List; 267053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta 277053919a3a55ad1b58e6db701afda18850037732Deepanshu Guptaimport static android.text.Primitive.PrimitiveType.PENALTY_INFINITY; 287053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta 297053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta// Based on the native implementation of GreedyLineBreaker in 307053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta// frameworks/base/core/jni/android_text_StaticLayout.cpp revision b808260 317053919a3a55ad1b58e6db701afda18850037732Deepanshu Guptapublic class GreedyLineBreaker extends LineBreaker { 327053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta 337053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta public GreedyLineBreaker(@NonNull List<Primitive> primitives, @NonNull LineWidth lineWidth, 347053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta @NonNull TabStops tabStops) { 357053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta super(primitives, lineWidth, tabStops); 367053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta } 377053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta 387053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta @Override 397053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta public void computeBreaks(LineBreaks lineBreaks) { 407053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta BreakInfo breakInfo = new BreakInfo(); 417053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta int lineNum = 0; 427053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta float width = 0, printedWidth = 0; 437053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta boolean breakFound = false, goodBreakFound = false; 447053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta int breakIndex = 0, goodBreakIndex = 0; 457053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta float breakWidth = 0, goodBreakWidth = 0; 467053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta int firstTabIndex = Integer.MAX_VALUE; 477053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta 487053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta float maxWidth = mLineWidth.getLineWidth(lineNum); 497053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta 507053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta int numPrimitives = mPrimitives.size(); 517053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta // greedily fit as many characters as possible on each line 527053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta // loop over all primitives, and choose the best break point 537053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta // (if possible, a break point without splitting a word) 547053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta // after going over the maximum length 557053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta for (int i = 0; i < numPrimitives; i++) { 567053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta Primitive p = mPrimitives.get(i); 577053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta 587053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta // update the current line width 597053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta if (p.type == PrimitiveType.BOX || p.type == PrimitiveType.GLUE) { 607053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta width += p.width; 617053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta if (p.type == PrimitiveType.BOX) { 627053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta printedWidth = width; 637053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta } 647053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta } else if (p.type == PrimitiveType.VARIABLE) { 657053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta width = mTabStops.width(width); 667053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta // keep track of first tab character in the region we are examining 677053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta // so we can determine whether or not a line contains a tab 687053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta firstTabIndex = Math.min(firstTabIndex, i); 697053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta } 707053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta 717053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta // find the best break point for the characters examined so far 727053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta if (printedWidth > maxWidth) { 737053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta //noinspection StatementWithEmptyBody 747053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta if (breakFound || goodBreakFound) { 757053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta if (goodBreakFound) { 767053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta // a true line break opportunity existed in the characters examined so far, 777053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta // so there is no need to split a word 787053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta i = goodBreakIndex; // no +1 because of i++ 797053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta lineNum++; 807053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta maxWidth = mLineWidth.getLineWidth(lineNum); 817053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta breakInfo.mBreaksList.add(mPrimitives.get(goodBreakIndex).location); 827053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta breakInfo.mWidthsList.add(goodBreakWidth); 837053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta breakInfo.mFlagsList.add(firstTabIndex < goodBreakIndex); 847053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta firstTabIndex = Integer.MAX_VALUE; 857053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta } else { 867053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta // must split a word because there is no other option 877053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta i = breakIndex; // no +1 because of i++ 887053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta lineNum++; 897053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta maxWidth = mLineWidth.getLineWidth(lineNum); 907053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta breakInfo.mBreaksList.add(mPrimitives.get(breakIndex).location); 917053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta breakInfo.mWidthsList.add(breakWidth); 927053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta breakInfo.mFlagsList.add(firstTabIndex < breakIndex); 937053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta firstTabIndex = Integer.MAX_VALUE; 947053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta } 957053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta printedWidth = width = 0; 967053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta goodBreakFound = breakFound = false; 977053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta goodBreakWidth = breakWidth = 0; 987053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta continue; 997053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta } else { 1007053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta // no choice, keep going... must make progress by putting at least one 1017053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta // character on a line, even if part of that character is cut off -- 1027053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta // there is no other option 1037053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta } 1047053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta } 1057053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta 1067053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta // update possible break points 1077053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta if (p.type == PrimitiveType.PENALTY && 1087053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta p.penalty < PENALTY_INFINITY) { 1097053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta // this does not handle penalties with width 1107053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta 1117053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta // handle forced line break 1127053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta if (p.penalty == -PENALTY_INFINITY) { 1137053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta lineNum++; 1147053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta maxWidth = mLineWidth.getLineWidth(lineNum); 1157053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta breakInfo.mBreaksList.add(p.location); 1167053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta breakInfo.mWidthsList.add(printedWidth); 1177053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta breakInfo.mFlagsList.add(firstTabIndex < i); 1187053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta firstTabIndex = Integer.MAX_VALUE; 1197053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta printedWidth = width = 0; 1207053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta goodBreakFound = breakFound = false; 1217053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta goodBreakWidth = breakWidth = 0; 1227053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta continue; 1237053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta } 1247053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta if (i > breakIndex && (printedWidth <= maxWidth || !breakFound)) { 1257053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta breakFound = true; 1267053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta breakIndex = i; 1277053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta breakWidth = printedWidth; 1287053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta } 1297053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta if (i > goodBreakIndex && printedWidth <= maxWidth) { 1307053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta goodBreakFound = true; 1317053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta goodBreakIndex = i; 1327053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta goodBreakWidth = printedWidth; 1337053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta } 1347053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta } else if (p.type == PrimitiveType.WORD_BREAK) { 1357053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta // only do this if necessary -- we don't want to break words 1367053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta // when possible, but sometimes it is unavoidable 1377053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta if (i > breakIndex && (printedWidth <= maxWidth || !breakFound)) { 1387053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta breakFound = true; 1397053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta breakIndex = i; 1407053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta breakWidth = printedWidth; 1417053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta } 1427053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta } 1437053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta } 1447053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta 1457053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta if (breakFound || goodBreakFound) { 1467053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta // output last break if there are more characters to output 1477053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta if (goodBreakFound) { 1487053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta breakInfo.mBreaksList.add(mPrimitives.get(goodBreakIndex).location); 1497053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta breakInfo.mWidthsList.add(goodBreakWidth); 1507053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta breakInfo.mFlagsList.add(firstTabIndex < goodBreakIndex); 1517053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta } else { 1527053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta breakInfo.mBreaksList.add(mPrimitives.get(breakIndex).location); 1537053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta breakInfo.mWidthsList.add(breakWidth); 1547053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta breakInfo.mFlagsList.add(firstTabIndex < breakIndex); 1557053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta } 1567053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta } 1577053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta breakInfo.copyTo(lineBreaks); 1587053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta } 1597053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta 1607053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta private static class BreakInfo { 1617053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta List<Integer> mBreaksList = new ArrayList<Integer>(); 1627053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta List<Float> mWidthsList = new ArrayList<Float>(); 1637053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta List<Boolean> mFlagsList = new ArrayList<Boolean>(); 1647053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta 1657053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta public void copyTo(LineBreaks lineBreaks) { 1667053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta if (lineBreaks.breaks.length != mBreaksList.size()) { 1677053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta lineBreaks.breaks = new int[mBreaksList.size()]; 1687053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta lineBreaks.widths = new float[mWidthsList.size()]; 1697053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta lineBreaks.flags = new boolean[mFlagsList.size()]; 1707053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta } 1717053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta 1727053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta int i = 0; 1737053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta for (int b : mBreaksList) { 1747053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta lineBreaks.breaks[i] = b; 1757053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta i++; 1767053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta } 1777053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta i = 0; 1787053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta for (float b : mWidthsList) { 1797053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta lineBreaks.widths[i] = b; 1807053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta i++; 1817053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta } 1827053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta i = 0; 1837053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta for (boolean b : mFlagsList) { 1847053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta lineBreaks.flags[i] = b; 1857053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta i++; 1867053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta } 1877053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta 1887053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta mBreaksList = null; 1897053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta mWidthsList = null; 1907053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta mFlagsList = null; 1917053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta } 1927053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta } 1937053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta} 194