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 19476e582d2ffdf25102d4c55f8c242baa3d21d37fDeepanshu Guptaimport android.annotation.NonNull; 207053919a3a55ad1b58e6db701afda18850037732Deepanshu Guptaimport android.text.Primitive.PrimitiveType; 217053919a3a55ad1b58e6db701afda18850037732Deepanshu Guptaimport android.text.StaticLayout.LineBreaks; 227053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta 237053919a3a55ad1b58e6db701afda18850037732Deepanshu Guptaimport java.util.ArrayList; 247053919a3a55ad1b58e6db701afda18850037732Deepanshu Guptaimport java.util.List; 257053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta 267053919a3a55ad1b58e6db701afda18850037732Deepanshu Guptaimport static android.text.Primitive.PrimitiveType.PENALTY_INFINITY; 277053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta 287053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta// Based on the native implementation of GreedyLineBreaker in 297053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta// frameworks/base/core/jni/android_text_StaticLayout.cpp revision b808260 307053919a3a55ad1b58e6db701afda18850037732Deepanshu Guptapublic class GreedyLineBreaker extends LineBreaker { 317053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta 327053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta public GreedyLineBreaker(@NonNull List<Primitive> primitives, @NonNull LineWidth lineWidth, 337053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta @NonNull TabStops tabStops) { 347053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta super(primitives, lineWidth, tabStops); 357053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta } 367053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta 377053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta @Override 38d77b9ed7dcc42efca33b225c4594a30aab9e709cDeepanshu Gupta public void computeBreaks(@NonNull LineBreaks lineBreaks) { 397053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta BreakInfo breakInfo = new BreakInfo(); 407053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta int lineNum = 0; 417053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta float width = 0, printedWidth = 0; 427053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta boolean breakFound = false, goodBreakFound = false; 437053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta int breakIndex = 0, goodBreakIndex = 0; 447053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta float breakWidth = 0, goodBreakWidth = 0; 457053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta int firstTabIndex = Integer.MAX_VALUE; 467053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta 477053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta float maxWidth = mLineWidth.getLineWidth(lineNum); 487053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta 497053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta int numPrimitives = mPrimitives.size(); 507053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta // greedily fit as many characters as possible on each line 517053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta // loop over all primitives, and choose the best break point 527053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta // (if possible, a break point without splitting a word) 537053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta // after going over the maximum length 547053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta for (int i = 0; i < numPrimitives; i++) { 557053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta Primitive p = mPrimitives.get(i); 567053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta 577053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta // update the current line width 587053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta if (p.type == PrimitiveType.BOX || p.type == PrimitiveType.GLUE) { 597053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta width += p.width; 607053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta if (p.type == PrimitiveType.BOX) { 617053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta printedWidth = width; 627053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta } 637053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta } else if (p.type == PrimitiveType.VARIABLE) { 647053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta width = mTabStops.width(width); 657053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta // keep track of first tab character in the region we are examining 667053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta // so we can determine whether or not a line contains a tab 677053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta firstTabIndex = Math.min(firstTabIndex, i); 687053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta } 697053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta 707053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta // find the best break point for the characters examined so far 717053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta if (printedWidth > maxWidth) { 727053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta //noinspection StatementWithEmptyBody 737053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta if (breakFound || goodBreakFound) { 747053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta if (goodBreakFound) { 757053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta // a true line break opportunity existed in the characters examined so far, 767053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta // so there is no need to split a word 777053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta i = goodBreakIndex; // no +1 because of i++ 787053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta lineNum++; 797053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta maxWidth = mLineWidth.getLineWidth(lineNum); 807053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta breakInfo.mBreaksList.add(mPrimitives.get(goodBreakIndex).location); 817053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta breakInfo.mWidthsList.add(goodBreakWidth); 827053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta breakInfo.mFlagsList.add(firstTabIndex < goodBreakIndex); 837053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta firstTabIndex = Integer.MAX_VALUE; 847053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta } else { 857053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta // must split a word because there is no other option 867053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta i = breakIndex; // no +1 because of i++ 877053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta lineNum++; 887053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta maxWidth = mLineWidth.getLineWidth(lineNum); 897053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta breakInfo.mBreaksList.add(mPrimitives.get(breakIndex).location); 907053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta breakInfo.mWidthsList.add(breakWidth); 917053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta breakInfo.mFlagsList.add(firstTabIndex < breakIndex); 927053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta firstTabIndex = Integer.MAX_VALUE; 937053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta } 947053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta printedWidth = width = 0; 957053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta goodBreakFound = breakFound = false; 967053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta goodBreakWidth = breakWidth = 0; 977053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta continue; 987053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta } else { 997053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta // no choice, keep going... must make progress by putting at least one 1007053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta // character on a line, even if part of that character is cut off -- 1017053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta // there is no other option 1027053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta } 1037053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta } 1047053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta 1057053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta // update possible break points 1067053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta if (p.type == PrimitiveType.PENALTY && 1077053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta p.penalty < PENALTY_INFINITY) { 1087053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta // this does not handle penalties with width 1097053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta 1107053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta // handle forced line break 1117053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta if (p.penalty == -PENALTY_INFINITY) { 1127053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta lineNum++; 1137053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta maxWidth = mLineWidth.getLineWidth(lineNum); 1147053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta breakInfo.mBreaksList.add(p.location); 1157053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta breakInfo.mWidthsList.add(printedWidth); 1167053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta breakInfo.mFlagsList.add(firstTabIndex < i); 1177053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta firstTabIndex = Integer.MAX_VALUE; 1187053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta printedWidth = width = 0; 1197053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta goodBreakFound = breakFound = false; 1207053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta goodBreakWidth = breakWidth = 0; 1217053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta continue; 1227053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta } 1237053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta if (i > breakIndex && (printedWidth <= maxWidth || !breakFound)) { 1247053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta breakFound = true; 1257053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta breakIndex = i; 1267053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta breakWidth = printedWidth; 1277053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta } 1287053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta if (i > goodBreakIndex && printedWidth <= maxWidth) { 1297053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta goodBreakFound = true; 1307053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta goodBreakIndex = i; 1317053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta goodBreakWidth = printedWidth; 1327053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta } 1337053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta } else if (p.type == PrimitiveType.WORD_BREAK) { 1347053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta // only do this if necessary -- we don't want to break words 1357053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta // when possible, but sometimes it is unavoidable 1367053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta if (i > breakIndex && (printedWidth <= maxWidth || !breakFound)) { 1377053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta breakFound = true; 1387053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta breakIndex = i; 1397053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta breakWidth = printedWidth; 1407053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta } 1417053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta } 1427053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta } 1437053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta 1447053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta if (breakFound || goodBreakFound) { 1457053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta // output last break if there are more characters to output 1467053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta if (goodBreakFound) { 1477053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta breakInfo.mBreaksList.add(mPrimitives.get(goodBreakIndex).location); 1487053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta breakInfo.mWidthsList.add(goodBreakWidth); 1497053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta breakInfo.mFlagsList.add(firstTabIndex < goodBreakIndex); 1507053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta } else { 1517053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta breakInfo.mBreaksList.add(mPrimitives.get(breakIndex).location); 1527053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta breakInfo.mWidthsList.add(breakWidth); 1537053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta breakInfo.mFlagsList.add(firstTabIndex < breakIndex); 1547053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta } 1557053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta } 1567053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta breakInfo.copyTo(lineBreaks); 1577053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta } 1587053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta 1597053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta private static class BreakInfo { 1607053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta List<Integer> mBreaksList = new ArrayList<Integer>(); 1617053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta List<Float> mWidthsList = new ArrayList<Float>(); 1627053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta List<Boolean> mFlagsList = new ArrayList<Boolean>(); 1637053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta 1647053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta public void copyTo(LineBreaks lineBreaks) { 1657053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta if (lineBreaks.breaks.length != mBreaksList.size()) { 1667053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta lineBreaks.breaks = new int[mBreaksList.size()]; 1677053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta lineBreaks.widths = new float[mWidthsList.size()]; 16826d443aee4ee5a8791417b4ca09e8c78ba8dc78bRaph Levien lineBreaks.flags = new int[mFlagsList.size()]; 1697053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta } 1707053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta 1717053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta int i = 0; 1727053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta for (int b : mBreaksList) { 1737053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta lineBreaks.breaks[i] = b; 1747053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta i++; 1757053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta } 1767053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta i = 0; 1777053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta for (float b : mWidthsList) { 1787053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta lineBreaks.widths[i] = b; 1797053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta i++; 1807053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta } 1817053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta i = 0; 1827053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta for (boolean b : mFlagsList) { 18326d443aee4ee5a8791417b4ca09e8c78ba8dc78bRaph Levien lineBreaks.flags[i] = b ? TAB_MASK : 0; 1847053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta i++; 1857053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta } 1867053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta 1877053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta mBreaksList = null; 1887053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta mWidthsList = null; 1897053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta mFlagsList = null; 1907053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta } 1917053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta } 1927053919a3a55ad1b58e6db701afda18850037732Deepanshu Gupta} 193