frameworks/base/core/java/android/text/StaticLayout.java

   1 /*
   2  * Copyright (C) 2006 The Android Open Source Project
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *      http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 package android.text;
  18
  19 import android.graphics.Bitmap;
  20 import android.graphics.Paint;
  21 import com.android.internal.util.ArrayUtils;
  22 import android.util.Log;
  23 import android.text.style.LeadingMarginSpan;
  24 import android.text.style.LineHeightSpan;
  25 import android.text.style.MetricAffectingSpan;
  26 import android.text.style.ReplacementSpan;
  27
  28 /**
  29  * StaticLayout is a Layout for text that will not be edited after it
  30  * is laid out.  Use {@link DynamicLayout} for text that may change.
  31  * <p>This is used by widgets to control text layout. You should not need
  32  * to use this class directly unless you are implementing your own widget
  33  * or custom display object, or would be tempted to call
  34  * {@link android.graphics.Canvas#drawText(java.lang.CharSequence, int, int, float, float, android.graphics.Paint)
  35  *  Canvas.drawText()} directly.</p>
  36  */
  37 public class
  38 StaticLayout
  39 extends Layout
  40 {
  41     public StaticLayout(CharSequence source, TextPaint paint,
  42                         int width,
  43                         Alignment align, float spacingmult, float spacingadd,
  44                         boolean includepad) {
  45         this(source, 0, source.length(), paint, width, align,
  46              spacingmult, spacingadd, includepad);
  47     }
  48
  49     public StaticLayout(CharSequence source, int bufstart, int bufend,
  50                         TextPaint paint, int outerwidth,
  51                         Alignment align,
  52                         float spacingmult, float spacingadd,
  53                         boolean includepad) {
  54         this(source, bufstart, bufend, paint, outerwidth, align,
  55              spacingmult, spacingadd, includepad, null, 0);
  56     }
  57
  58     public StaticLayout(CharSequence source, int bufstart, int bufend,
  59                         TextPaint paint, int outerwidth,
  60                         Alignment align,
  61                         float spacingmult, float spacingadd,
  62                         boolean includepad,
  63                         TextUtils.TruncateAt ellipsize, int ellipsizedWidth) {
  64         super((ellipsize == null)
  65                 ? source
  66                 : (source instanceof Spanned)
  67                     ? new SpannedEllipsizer(source)
  68                     : new Ellipsizer(source),
  69               paint, outerwidth, align, spacingmult, spacingadd);
  70
  71         /*
  72          * This is annoying, but we can't refer to the layout until
  73          * superclass construction is finished, and the superclass
  74          * constructor wants the reference to the display text.
  75          *
  76          * This will break if the superclass constructor ever actually
  77          * cares about the content instead of just holding the reference.
  78          */
  79         if (ellipsize != null) {
  80             Ellipsizer e = (Ellipsizer) getText();
  81
  82             e.mLayout = this;
  83             e.mWidth = ellipsizedWidth;
  84             e.mMethod = ellipsize;
  85             mEllipsizedWidth = ellipsizedWidth;
  86
  87             mColumns = COLUMNS_ELLIPSIZE;
  88         } else {
  89             mColumns = COLUMNS_NORMAL;
  90             mEllipsizedWidth = outerwidth;
  91         }
  92
  93         mLines = new int[ArrayUtils.idealIntArraySize(2 * mColumns)];
  94         mLineDirections = new Directions[
  95                              ArrayUtils.idealIntArraySize(2 * mColumns)];
  96
  97         generate(source, bufstart, bufend, paint, outerwidth, align,
  98                  spacingmult, spacingadd, includepad, includepad,
  99                  ellipsize != null, ellipsizedWidth, ellipsize);
 100
 101         mChdirs = null;
 102         mChs = null;
 103         mWidths = null;
 104         mFontMetricsInt = null;
 105     }
 106
 107     /* package */ StaticLayout(boolean ellipsize) {
 108         super(null, null, 0, null, 0, 0);
 109
 110         mColumns = COLUMNS_ELLIPSIZE;
 111         mLines = new int[ArrayUtils.idealIntArraySize(2 * mColumns)];
 112         mLineDirections = new Directions[
 113                              ArrayUtils.idealIntArraySize(2 * mColumns)];
 114     }
 115
 116     /* package */ void generate(CharSequence source, int bufstart, int bufend,
 117                         TextPaint paint, int outerwidth,
 118                         Alignment align,
 119                         float spacingmult, float spacingadd,
 120                         boolean includepad, boolean trackpad,
 121                         boolean breakOnlyAtSpaces,
 122                         float ellipsizedWidth, TextUtils.TruncateAt where) {
 123         mLineCount = 0;
 124
 125         int v = 0;
 126         boolean needMultiply = (spacingmult != 1 || spacingadd != 0);
 127
 128         Paint.FontMetricsInt fm = mFontMetricsInt;
 129         int[] choosehtv = null;
 130
 131         int end = TextUtils.indexOf(source, '\n', bufstart, bufend);
 132         int bufsiz = end >= 0 ? end - bufstart : bufend - bufstart;
 133         boolean first = true;
 134
 135         if (mChdirs == null) {
 136             mChdirs = new byte[ArrayUtils.idealByteArraySize(bufsiz + 1)];
 137             mChs = new char[ArrayUtils.idealCharArraySize(bufsiz + 1)];
 138             mWidths = new float[ArrayUtils.idealIntArraySize((bufsiz + 1) * 2)];
 139         }
 140
 141         byte[] chdirs = mChdirs;
 142         char[] chs = mChs;
 143         float[] widths = mWidths;
 144
 145         AlteredCharSequence alter = null;
 146         Spanned spanned = null;
 147
 148         if (source instanceof Spanned)
 149             spanned = (Spanned) source;
 150
 151         int DEFAULT_DIR = DIR_LEFT_TO_RIGHT; // XXX
 152
 153         for (int start = bufstart; start <= bufend; start = end) {
 154             if (first)
 155                 first = false;
 156             else
 157                 end = TextUtils.indexOf(source, '\n', start, bufend);
 158
 159             if (end < 0)
 160                 end = bufend;
 161             else
 162                 end++;
 163
 164             int firstWidthLineCount = 1;
 165             int firstwidth = outerwidth;
 166             int restwidth = outerwidth;
 167
 168             LineHeightSpan[] chooseht = null;
 169
 170             if (spanned != null) {
 171                 LeadingMarginSpan[] sp;
 172
 173                 sp = spanned.getSpans(start, end, LeadingMarginSpan.class);
 174                 for (int i = 0; i < sp.length; i++) {
 175                     LeadingMarginSpan lms = sp[i];
 176                     firstwidth -= sp[i].getLeadingMargin(true);
 177                     restwidth -= sp[i].getLeadingMargin(false);
 178                     if (lms instanceof LeadingMarginSpan.LeadingMarginSpan2) {
 179                         firstWidthLineCount = ((LeadingMarginSpan.LeadingMarginSpan2)lms).getLeadingMarginLineCount();
 180                     }
 181                 }
 182
 183                 chooseht = spanned.getSpans(start, end, LineHeightSpan.class);
 184
 185                 if (chooseht.length != 0) {
 186                     if (choosehtv == null ||
 187                         choosehtv.length < chooseht.length) {
 188                         choosehtv = new int[ArrayUtils.idealIntArraySize(
 189                                             chooseht.length)];
 190                     }
 191
 192                     for (int i = 0; i < chooseht.length; i++) {
 193                         int o = spanned.getSpanStart(chooseht[i]);
 194
 195                         if (o < start) {
 196                             // starts in this layout, before the
 197                             // current paragraph
 198
 199                             choosehtv[i] = getLineTop(getLineForOffset(o));
 200                         } else {
 201                             // starts in this paragraph
 202
 203                             choosehtv[i] = v;
 204                         }
 205                     }
 206                 }
 207             }
 208
 209             if (end - start > chdirs.length) {
 210                 chdirs = new byte[ArrayUtils.idealByteArraySize(end - start)];
 211                 mChdirs = chdirs;
 212             }
 213             if (end - start > chs.length) {
 214                 chs = new char[ArrayUtils.idealCharArraySize(end - start)];
 215                 mChs = chs;
 216             }
 217             if ((end - start) * 2 > widths.length) {
 218                 widths = new float[ArrayUtils.idealIntArraySize((end - start) * 2)];
 219                 mWidths = widths;
 220             }
 221
 222             TextUtils.getChars(source, start, end, chs, 0);
 223             final int n = end - start;
 224
 225             boolean easy = true;
 226             boolean altered = false;
 227             int dir = DEFAULT_DIR; // XXX
 228
 229             for (int i = 0; i < n; i++) {
 230                 if (chs[i] >= FIRST_RIGHT_TO_LEFT) {
 231                     easy = false;
 232                     break;
 233                 }
 234             }
 235
 236             // Ensure that none of the underlying characters are treated
 237             // as viable breakpoints, and that the entire run gets the
 238             // same bidi direction.
 239
 240             if (source instanceof Spanned) {
 241                 Spanned sp = (Spanned) source;
 242                 ReplacementSpan[] spans = sp.getSpans(start, end, ReplacementSpan.class);
 243
 244                 for (int y = 0; y < spans.length; y++) {
 245                     int a = sp.getSpanStart(spans[y]);
 246                     int b = sp.getSpanEnd(spans[y]);
 247
 248                     for (int x = a; x < b; x++) {
 249                         chs[x - start] = '\uFFFC';
 250                     }
 251                 }
 252             }
 253
 254             if (!easy) {
 255                 // XXX put override flags, etc. into chdirs
 256                 dir = bidi(dir, chs, chdirs, n, false);
 257
 258                 // Do mirroring for right-to-left segments
 259
 260                 for (int i = 0; i < n; i++) {
 261                     if (chdirs[i] == Character.DIRECTIONALITY_RIGHT_TO_LEFT) {
 262                         int j;
 263
 264                         for (j = i; j < n; j++) {
 265                             if (chdirs[j] !=
 266                                 Character.DIRECTIONALITY_RIGHT_TO_LEFT)
 267                                 break;
 268                         }
 269
 270                         if (AndroidCharacter.mirror(chs, i, j - i))
 271                             altered = true;
 272
 273                         i = j - 1;
 274                     }
 275                 }
 276             }
 277
 278             CharSequence sub;
 279
 280             if (altered) {
 281                 if (alter == null)
 282                     alter = AlteredCharSequence.make(source, chs, start, end);
 283                 else
 284                     alter.update(chs, start, end);
 285
 286                 sub = alter;
 287             } else {
 288                 sub = source;
 289             }
 290
 291             int width = firstwidth;
 292
 293             float w = 0;
 294             int here = start;
 295
 296             int ok = start;
 297             float okwidth = w;
 298             int okascent = 0, okdescent = 0, oktop = 0, okbottom = 0;
 299
 300             int fit = start;
 301             float fitwidth = w;
 302             int fitascent = 0, fitdescent = 0, fittop = 0, fitbottom = 0;
 303
 304             boolean tab = false;
 305
 306             int next;
 307             for (int i = start; i < end; i = next) {
 308                 if (spanned == null)
 309                     next = end;
 310                 else
 311                     next = spanned.nextSpanTransition(i, end,
 312                                                       MetricAffectingSpan.
 313                                                       class);
 314
 315                 if (spanned == null) {
 316                     paint.getTextWidths(sub, i, next, widths);
 317                     System.arraycopy(widths, 0, widths,
 318                                      end - start + (i - start), next - i);
 319
 320                     paint.getFontMetricsInt(fm);
 321                 } else {
 322                     mWorkPaint.baselineShift = 0;
 323
 324                     Styled.getTextWidths(paint, mWorkPaint,
 325                                          spanned, i, next,
 326                                          widths, fm);
 327                     System.arraycopy(widths, 0, widths,
 328                                      end - start + (i - start), next - i);
 329
 330                     if (mWorkPaint.baselineShift < 0) {
 331                         fm.ascent += mWorkPaint.baselineShift;
 332                         fm.top += mWorkPaint.baselineShift;
 333                     } else {
 334                         fm.descent += mWorkPaint.baselineShift;
 335                         fm.bottom += mWorkPaint.baselineShift;
 336                     }
 337                 }
 338
 339                 int fmtop = fm.top;
 340                 int fmbottom = fm.bottom;
 341                 int fmascent = fm.ascent;
 342                 int fmdescent = fm.descent;
 343
 344                 if (false) {
 345                     StringBuilder sb = new StringBuilder();
 346                     for (int j = i; j < next; j++) {
 347                         sb.append(widths[j - start + (end - start)]);
 348                         sb.append(' ');
 349                     }
 350
 351                     Log.e("text", sb.toString());
 352                 }
 353
 354                 for (int j = i; j < next; j++) {
 355                     char c = chs[j - start];
 356                     float before = w;
 357
 358                     if (c == '\n') {
 359                         ;
 360                     } else if (c == '\t') {
 361                         w = Layout.nextTab(sub, start, end, w, null);
 362                         tab = true;
 363                     } else if (c >= 0xD800 && c <= 0xDFFF && j + 1 < next) {
 364                         int emoji = Character.codePointAt(chs, j - start);
 365
 366                         if (emoji >= MIN_EMOJI && emoji <= MAX_EMOJI) {
 367                             Bitmap bm = EMOJI_FACTORY.
 368                                 getBitmapFromAndroidPua(emoji);
 369
 370                             if (bm != null) {
 371                                 Paint whichPaint;
 372
 373                                 if (spanned == null) {
 374                                     whichPaint = paint;
 375                                 } else {
 376                                     whichPaint = mWorkPaint;
 377                                 }
 378
 379                                 float wid = (float) bm.getWidth() *
 380                                             -whichPaint.ascent() /
 381                                             bm.getHeight();
 382
 383                                 w += wid;
 384                                 tab = true;
 385                                 j++;
 386                             } else {
 387                                 w += widths[j - start + (end - start)];
 388                             }
 389                         } else {
 390                             w += widths[j - start + (end - start)];
 391                         }
 392                     } else {
 393                         w += widths[j - start + (end - start)];
 394                     }
 395
 396                     // Log.e("text", "was " + before + " now " + w + " after " + c + " within " + width);
 397
 398                     if (w <= width) {
 399                         fitwidth = w;
 400                         fit = j + 1;
 401
 402                         if (fmtop < fittop)
 403                             fittop = fmtop;
 404                         if (fmascent < fitascent)
 405                             fitascent = fmascent;
 406                         if (fmdescent > fitdescent)
 407                             fitdescent = fmdescent;
 408                         if (fmbottom > fitbottom)
 409                             fitbottom = fmbottom;
 410
 411                         /*
 412                          * From the Unicode Line Breaking Algorithm:
 413                          * (at least approximately)
 414                          *
 415                          * .,:; are class IS: breakpoints
 416                          *      except when adjacent to digits
 417                          * /    is class SY: a breakpoint
 418                          *      except when followed by a digit.
 419                          * -    is class HY: a breakpoint
 420                          *      except when followed by a digit.
 421                          *
 422                          * Ideographs are class ID: breakpoints when adjacent,
 423                          * except for NS (non-starters), which can be broken
 424                          * after but not before.
 425                          */
 426
 427                         if (c == ' ' || c == '\t' ||
 428                             ((c == '.'  || c == ',' || c == ':' || c == ';') &&
 429                              (j - 1 < here || !Character.isDigit(chs[j - 1 - start])) &&
 430                              (j + 1 >= next || !Character.isDigit(chs[j + 1 - start]))) ||
 431                             ((c == '/' || c == '-') &&
 432                              (j + 1 >= next || !Character.isDigit(chs[j + 1 - start]))) ||
 433                             (c >= FIRST_CJK && isIdeographic(c, true) &&
 434                              j + 1 < next && isIdeographic(chs[j + 1 - start], false))) {
 435                             okwidth = w;
 436                             ok = j + 1;
 437
 438                             if (fittop < oktop)
 439                                 oktop = fittop;
 440                             if (fitascent < okascent)
 441                                 okascent = fitascent;
 442                             if (fitdescent > okdescent)
 443                                 okdescent = fitdescent;
 444                             if (fitbottom > okbottom)
 445                                 okbottom = fitbottom;
 446                         }
 447                     } else if (breakOnlyAtSpaces) {
 448                         if (ok != here) {
 449                             // Log.e("text", "output ok " + here + " to " +ok);
 450
 451                             while (ok < next && chs[ok - start] == ' ') {
 452                                 ok++;
 453                             }
 454
 455                             v = out(source,
 456                                     here, ok,
 457                                     okascent, okdescent, oktop, okbottom,
 458                                     v,
 459                                     spacingmult, spacingadd, chooseht,
 460                                     choosehtv, fm, tab,
 461                                     needMultiply, start, chdirs, dir, easy,
 462                                     ok == bufend, includepad, trackpad,
 463                                     widths, start, end - start,
 464                                     where, ellipsizedWidth, okwidth,
 465                                     paint);
 466
 467                             here = ok;
 468                         } else {
 469                             // Act like it fit even though it didn't.
 470
 471                             fitwidth = w;
 472                             fit = j + 1;
 473
 474                             if (fmtop < fittop)
 475                                 fittop = fmtop;
 476                             if (fmascent < fitascent)
 477                                 fitascent = fmascent;
 478                             if (fmdescent > fitdescent)
 479                                 fitdescent = fmdescent;
 480                             if (fmbottom > fitbottom)
 481                                 fitbottom = fmbottom;
 482                         }
 483                     } else {
 484                         if (ok != here) {
 485                             // Log.e("text", "output ok " + here + " to " +ok);
 486
 487                             while (ok < next && chs[ok - start] == ' ') {
 488                                 ok++;
 489                             }
 490
 491                             v = out(source,
 492                                     here, ok,
 493                                     okascent, okdescent, oktop, okbottom,
 494                                     v,
 495                                     spacingmult, spacingadd, chooseht,
 496                                     choosehtv, fm, tab,
 497                                     needMultiply, start, chdirs, dir, easy,
 498                                     ok == bufend, includepad, trackpad,
 499                                     widths, start, end - start,
 500                                     where, ellipsizedWidth, okwidth,
 501                                     paint);
 502
 503                             here = ok;
 504                         } else if (fit != here) {
 505                             // Log.e("text", "output fit " + here + " to " +fit);
 506                             v = out(source,
 507                                     here, fit,
 508                                     fitascent, fitdescent,
 509                                     fittop, fitbottom,
 510                                     v,
 511                                     spacingmult, spacingadd, chooseht,
 512                                     choosehtv, fm, tab,
 513                                     needMultiply, start, chdirs, dir, easy,
 514                                     fit == bufend, includepad, trackpad,
 515                                     widths, start, end - start,
 516                                     where, ellipsizedWidth, fitwidth,
 517                                     paint);
 518
 519                             here = fit;
 520                         } else {
 521                             // Log.e("text", "output one " + here + " to " +(here + 1));
 522                             measureText(paint, mWorkPaint,
 523                                         source, here, here + 1, fm, tab,
 524                                         null);
 525
 526                             v = out(source,
 527                                     here, here+1,
 528                                     fm.ascent, fm.descent,
 529                                     fm.top, fm.bottom,
 530                                     v,
 531                                     spacingmult, spacingadd, chooseht,
 532                                     choosehtv, fm, tab,
 533                                     needMultiply, start, chdirs, dir, easy,
 534                                     here + 1 == bufend, includepad,
 535                                     trackpad,
 536                                     widths, start, end - start,
 537                                     where, ellipsizedWidth,
 538                                     widths[here - start], paint);
 539
 540                             here = here + 1;
 541                         }
 542
 543                         if (here < i) {
 544                             j = next = here; // must remeasure
 545                         } else {
 546                             j = here - 1;    // continue looping
 547                         }
 548
 549                         ok = fit = here;
 550                         w = 0;
 551                         fitascent = fitdescent = fittop = fitbottom = 0;
 552                         okascent = okdescent = oktop = okbottom = 0;
 553
 554                         if (--firstWidthLineCount <= 0) {
 555                             width = restwidth;
 556                         }
 557                     }
 558                 }
 559             }
 560
 561             if (end != here) {
 562                 if ((fittop | fitbottom | fitdescent | fitascent) == 0) {
 563                     paint.getFontMetricsInt(fm);
 564
 565                     fittop = fm.top;
 566                     fitbottom = fm.bottom;
 567                     fitascent = fm.ascent;
 568                     fitdescent = fm.descent;
 569                 }
 570
 571                 // Log.e("text", "output rest " + here + " to " + end);
 572
 573                 v = out(source,
 574                         here, end, fitascent, fitdescent,
 575                         fittop, fitbottom,
 576                         v,
 577                         spacingmult, spacingadd, chooseht,
 578                         choosehtv, fm, tab,
 579                         needMultiply, start, chdirs, dir, easy,
 580                         end == bufend, includepad, trackpad,
 581                         widths, start, end - start,
 582                         where, ellipsizedWidth, w, paint);
 583             }
 584
 585             start = end;
 586
 587             if (end == bufend)
 588                 break;
 589         }
 590
 591         if (bufend == bufstart || source.charAt(bufend - 1) == '\n') {
 592             // Log.e("text", "output last " + bufend);
 593
 594             paint.getFontMetricsInt(fm);
 595
 596             v = out(source,
 597                     bufend, bufend, fm.ascent, fm.descent,
 598                     fm.top, fm.bottom,
 599                     v,
 600                     spacingmult, spacingadd, null,
 601                     null, fm, false,
 602                     needMultiply, bufend, chdirs, DEFAULT_DIR, true,
 603                     true, includepad, trackpad,
 604                     widths, bufstart, 0,
 605                     where, ellipsizedWidth, 0, paint);
 606         }
 607     }
 608
 609     /**
 610      * Runs the unicode bidi algorithm on the first n chars in chs, returning
 611      * the char dirs in chInfo and the base line direction of the first
 612      * paragraph.
 613      *
 614      * XXX change result from dirs to levels
 615      *
 616      * @param dir the direction flag, either DIR_REQUEST_LTR,
 617      * DIR_REQUEST_RTL, DIR_REQUEST_DEFAULT_LTR, or DIR_REQUEST_DEFAULT_RTL.
 618      * @param chs the text to examine
 619      * @param chInfo on input, if hasInfo is true, override and other flags
 620      * representing out-of-band embedding information. On output, the generated
 621      * dirs of the text.
 622      * @param n the length of the text/information in chs and chInfo
 623      * @param hasInfo true if chInfo has input information, otherwise the
 624      * input data in chInfo is ignored.
 625      * @return the resolved direction level of the first paragraph, either
 626      * DIR_LEFT_TO_RIGHT or DIR_RIGHT_TO_LEFT.
 627      */
 628     /* package */ static int bidi(int dir, char[] chs, byte[] chInfo, int n,
 629             boolean hasInfo) {
 630
 631         AndroidCharacter.getDirectionalities(chs, chInfo, n);
 632
 633         /*
 634          * Determine primary paragraph direction if not specified
 635          */
 636         if (dir != DIR_REQUEST_LTR && dir != DIR_REQUEST_RTL) {
 637             // set up default
 638             dir = dir >= 0 ? DIR_LEFT_TO_RIGHT : DIR_RIGHT_TO_LEFT;
 639             for (int j = 0; j < n; j++) {
 640                 int d = chInfo[j];
 641
 642                 if (d == Character.DIRECTIONALITY_LEFT_TO_RIGHT) {
 643                     dir = DIR_LEFT_TO_RIGHT;
 644                     break;
 645                 }
 646                 if (d == Character.DIRECTIONALITY_RIGHT_TO_LEFT) {
 647                     dir = DIR_RIGHT_TO_LEFT;
 648                     break;
 649                 }
 650             }
 651         }
 652
 653         final byte SOR = dir == DIR_LEFT_TO_RIGHT ?
 654                 Character.DIRECTIONALITY_LEFT_TO_RIGHT :
 655                 Character.DIRECTIONALITY_RIGHT_TO_LEFT;
 656
 657         /*
 658          * XXX Explicit overrides should go here
 659          */
 660
 661         /*
 662          * Weak type resolution
 663          */
 664
 665         // dump(chdirs, n, "initial");
 666
 667         // W1 non spacing marks
 668         for (int j = 0; j < n; j++) {
 669             if (chInfo[j] == Character.NON_SPACING_MARK) {
 670                 if (j == 0)
 671                     chInfo[j] = SOR;
 672                 else
 673                     chInfo[j] = chInfo[j - 1];
 674             }
 675         }
 676
 677         // dump(chdirs, n, "W1");
 678
 679         // W2 european numbers
 680         byte cur = SOR;
 681         for (int j = 0; j < n; j++) {
 682             byte d = chInfo[j];
 683
 684             if (d == Character.DIRECTIONALITY_LEFT_TO_RIGHT ||
 685                 d == Character.DIRECTIONALITY_RIGHT_TO_LEFT ||
 686                 d == Character.DIRECTIONALITY_RIGHT_TO_LEFT_ARABIC)
 687                 cur = d;
 688             else if (d == Character.DIRECTIONALITY_EUROPEAN_NUMBER) {
 689                  if (cur ==
 690                     Character.DIRECTIONALITY_RIGHT_TO_LEFT_ARABIC)
 691                     chInfo[j] = Character.DIRECTIONALITY_ARABIC_NUMBER;
 692             }
 693         }
 694
 695         // dump(chdirs, n, "W2");
 696
 697         // W3 arabic letters
 698         for (int j = 0; j < n; j++) {
 699             if (chInfo[j] == Character.DIRECTIONALITY_RIGHT_TO_LEFT_ARABIC)
 700                 chInfo[j] = Character.DIRECTIONALITY_RIGHT_TO_LEFT;
 701         }
 702
 703         // dump(chdirs, n, "W3");
 704
 705         // W4 single separator between numbers
 706         for (int j = 1; j < n - 1; j++) {
 707             byte d = chInfo[j];
 708             byte prev = chInfo[j - 1];
 709             byte next = chInfo[j + 1];
 710
 711             if (d == Character.DIRECTIONALITY_EUROPEAN_NUMBER_SEPARATOR) {
 712                 if (prev == Character.DIRECTIONALITY_EUROPEAN_NUMBER &&
 713                     next == Character.DIRECTIONALITY_EUROPEAN_NUMBER)
 714                     chInfo[j] = Character.DIRECTIONALITY_EUROPEAN_NUMBER;
 715             } else if (d == Character.DIRECTIONALITY_COMMON_NUMBER_SEPARATOR) {
 716                 if (prev == Character.DIRECTIONALITY_EUROPEAN_NUMBER &&
 717                     next == Character.DIRECTIONALITY_EUROPEAN_NUMBER)
 718                     chInfo[j] = Character.DIRECTIONALITY_EUROPEAN_NUMBER;
 719                 if (prev == Character.DIRECTIONALITY_ARABIC_NUMBER &&
 720                     next == Character.DIRECTIONALITY_ARABIC_NUMBER)
 721                     chInfo[j] = Character.DIRECTIONALITY_ARABIC_NUMBER;
 722             }
 723         }
 724
 725         // dump(chdirs, n, "W4");
 726
 727         // W5 european number terminators
 728         boolean adjacent = false;
 729         for (int j = 0; j < n; j++) {
 730             byte d = chInfo[j];
 731
 732             if (d == Character.DIRECTIONALITY_EUROPEAN_NUMBER)
 733                 adjacent = true;
 734             else if (d == Character.DIRECTIONALITY_EUROPEAN_NUMBER_TERMINATOR && adjacent)
 735                 chInfo[j] = Character.DIRECTIONALITY_EUROPEAN_NUMBER;
 736             else
 737                 adjacent = false;
 738         }
 739
 740         //dump(chdirs, n, "W5");
 741
 742         // W5 european number terminators part 2,
 743         // W6 separators and terminators
 744         adjacent = false;
 745         for (int j = n - 1; j >= 0; j--) {
 746             byte d = chInfo[j];
 747
 748             if (d == Character.DIRECTIONALITY_EUROPEAN_NUMBER)
 749                 adjacent = true;
 750             else if (d == Character.DIRECTIONALITY_EUROPEAN_NUMBER_TERMINATOR) {
 751                 if (adjacent)
 752                     chInfo[j] = Character.DIRECTIONALITY_EUROPEAN_NUMBER;
 753                 else
 754                     chInfo[j] = Character.DIRECTIONALITY_OTHER_NEUTRALS;
 755             }
 756             else {
 757                 adjacent = false;
 758
 759                 if (d == Character.DIRECTIONALITY_EUROPEAN_NUMBER_SEPARATOR ||
 760                     d == Character.DIRECTIONALITY_COMMON_NUMBER_SEPARATOR ||
 761                     d == Character.DIRECTIONALITY_PARAGRAPH_SEPARATOR ||
 762                     d == Character.DIRECTIONALITY_SEGMENT_SEPARATOR)
 763                     chInfo[j] = Character.DIRECTIONALITY_OTHER_NEUTRALS;
 764             }
 765         }
 766
 767         // dump(chdirs, n, "W6");
 768
 769         // W7 strong direction of european numbers
 770         cur = SOR;
 771         for (int j = 0; j < n; j++) {
 772             byte d = chInfo[j];
 773
 774             if (d == SOR ||
 775                 d == Character.DIRECTIONALITY_LEFT_TO_RIGHT ||
 776                 d == Character.DIRECTIONALITY_RIGHT_TO_LEFT)
 777                 cur = d;
 778
 779             if (d == Character.DIRECTIONALITY_EUROPEAN_NUMBER)
 780                 chInfo[j] = cur;
 781         }
 782
 783         // dump(chdirs, n, "W7");
 784
 785         // N1, N2 neutrals
 786         cur = SOR;
 787         for (int j = 0; j < n; j++) {
 788             byte d = chInfo[j];
 789
 790             if (d == Character.DIRECTIONALITY_LEFT_TO_RIGHT ||
 791                 d == Character.DIRECTIONALITY_RIGHT_TO_LEFT) {
 792                 cur = d;
 793             } else if (d == Character.DIRECTIONALITY_EUROPEAN_NUMBER ||
 794                        d == Character.DIRECTIONALITY_ARABIC_NUMBER) {
 795                 cur = Character.DIRECTIONALITY_RIGHT_TO_LEFT;
 796             } else {
 797                 byte dd = SOR;
 798                 int k;
 799
 800                 for (k = j + 1; k < n; k++) {
 801                     dd = chInfo[k];
 802
 803                     if (dd == Character.DIRECTIONALITY_LEFT_TO_RIGHT ||
 804                         dd == Character.DIRECTIONALITY_RIGHT_TO_LEFT) {
 805                         break;
 806                     }
 807                     if (dd == Character.DIRECTIONALITY_EUROPEAN_NUMBER ||
 808                         dd == Character.DIRECTIONALITY_ARABIC_NUMBER) {
 809                         dd = Character.DIRECTIONALITY_RIGHT_TO_LEFT;
 810                         break;
 811                     }
 812                 }
 813
 814                 for (int y = j; y < k; y++) {
 815                     if (dd == cur)
 816                         chInfo[y] = cur;
 817                     else
 818                         chInfo[y] = SOR;
 819                 }
 820
 821                 j = k - 1;
 822             }
 823         }
 824
 825         // dump(chdirs, n, "final");
 826
 827         // extra: enforce that all tabs and surrogate characters go the
 828         // primary direction
 829         // TODO: actually do directions right for surrogates
 830
 831         for (int j = 0; j < n; j++) {
 832             char c = chs[j];
 833
 834             if (c == '\t' || (c >= 0xD800 && c <= 0xDFFF)) {
 835                 chInfo[j] = SOR;
 836             }
 837         }
 838
 839         return dir;
 840     }
 841
 842     private static final char FIRST_CJK = '\u2E80';
 843     /**
 844      * Returns true if the specified character is one of those specified
 845      * as being Ideographic (class ID) by the Unicode Line Breaking Algorithm
 846      * (http://www.unicode.org/unicode/reports/tr14/), and is therefore OK
 847      * to break between a pair of.
 848      *
 849      * @param includeNonStarters also return true for category NS
 850      *                           (non-starters), which can be broken
 851      *                           after but not before.
 852      */
 853     private static final boolean isIdeographic(char c, boolean includeNonStarters) {
 854         if (c >= '\u2E80' && c <= '\u2FFF') {
 855             return true; // CJK, KANGXI RADICALS, DESCRIPTION SYMBOLS
 856         }
 857         if (c == '\u3000') {
 858             return true; // IDEOGRAPHIC SPACE
 859         }
 860         if (c >= '\u3040' && c <= '\u309F') {
 861             if (!includeNonStarters) {
 862                 switch (c) {
 863                 case '\u3041': //  # HIRAGANA LETTER SMALL A
 864                 case '\u3043': //  # HIRAGANA LETTER SMALL I
 865                 case '\u3045': //  # HIRAGANA LETTER SMALL U
 866                 case '\u3047': //  # HIRAGANA LETTER SMALL E
 867                 case '\u3049': //  # HIRAGANA LETTER SMALL O
 868                 case '\u3063': //  # HIRAGANA LETTER SMALL TU
 869                 case '\u3083': //  # HIRAGANA LETTER SMALL YA
 870                 case '\u3085': //  # HIRAGANA LETTER SMALL YU
 871                 case '\u3087': //  # HIRAGANA LETTER SMALL YO
 872                 case '\u308E': //  # HIRAGANA LETTER SMALL WA
 873                 case '\u3095': //  # HIRAGANA LETTER SMALL KA
 874                 case '\u3096': //  # HIRAGANA LETTER SMALL KE
 875                 case '\u309B': //  # KATAKANA-HIRAGANA VOICED SOUND MARK
 876                 case '\u309C': //  # KATAKANA-HIRAGANA SEMI-VOICED SOUND MARK
 877                 case '\u309D': //  # HIRAGANA ITERATION MARK
 878                 case '\u309E': //  # HIRAGANA VOICED ITERATION MARK
 879                     return false;
 880                 }
 881             }
 882             return true; // Hiragana (except small characters)
 883         }
 884         if (c >= '\u30A0' && c <= '\u30FF') {
 885             if (!includeNonStarters) {
 886                 switch (c) {
 887                 case '\u30A0': //  # KATAKANA-HIRAGANA DOUBLE HYPHEN
 888                 case '\u30A1': //  # KATAKANA LETTER SMALL A
 889                 case '\u30A3': //  # KATAKANA LETTER SMALL I
 890                 case '\u30A5': //  # KATAKANA LETTER SMALL U
 891                 case '\u30A7': //  # KATAKANA LETTER SMALL E
 892                 case '\u30A9': //  # KATAKANA LETTER SMALL O
 893                 case '\u30C3': //  # KATAKANA LETTER SMALL TU
 894                 case '\u30E3': //  # KATAKANA LETTER SMALL YA
 895                 case '\u30E5': //  # KATAKANA LETTER SMALL YU
 896                 case '\u30E7': //  # KATAKANA LETTER SMALL YO
 897                 case '\u30EE': //  # KATAKANA LETTER SMALL WA
 898                 case '\u30F5': //  # KATAKANA LETTER SMALL KA
 899                 case '\u30F6': //  # KATAKANA LETTER SMALL KE
 900                 case '\u30FB': //  # KATAKANA MIDDLE DOT
 901                 case '\u30FC': //  # KATAKANA-HIRAGANA PROLONGED SOUND MARK
 902                 case '\u30FD': //  # KATAKANA ITERATION MARK
 903                 case '\u30FE': //  # KATAKANA VOICED ITERATION MARK
 904                     return false;
 905                 }
 906             }
 907             return true; // Katakana (except small characters)
 908         }
 909         if (c >= '\u3400' && c <= '\u4DB5') {
 910             return true; // CJK UNIFIED IDEOGRAPHS EXTENSION A
 911         }
 912         if (c >= '\u4E00' && c <= '\u9FBB') {
 913             return true; // CJK UNIFIED IDEOGRAPHS
 914         }
 915         if (c >= '\uF900' && c <= '\uFAD9') {
 916             return true; // CJK COMPATIBILITY IDEOGRAPHS
 917         }
 918         if (c >= '\uA000' && c <= '\uA48F') {
 919             return true; // YI SYLLABLES
 920         }
 921         if (c >= '\uA490' && c <= '\uA4CF') {
 922             return true; // YI RADICALS
 923         }
 924         if (c >= '\uFE62' && c <= '\uFE66') {
 925             return true; // SMALL PLUS SIGN to SMALL EQUALS SIGN
 926         }
 927         if (c >= '\uFF10' && c <= '\uFF19') {
 928             return true; // WIDE DIGITS
 929         }
 930
 931         return false;
 932     }
 933
 934 /*
 935     private static void dump(byte[] data, int count, String label) {
 936         if (false) {
 937             System.out.print(label);
 938
 939             for (int i = 0; i < count; i++)
 940                 System.out.print(" " + data[i]);
 941
 942             System.out.println();
 943         }
 944     }
 945 */
 946
 947     private static int getFit(TextPaint paint,
 948                               TextPaint workPaint,
 949                        CharSequence text, int start, int end,
 950                        float wid) {
 951         int high = end + 1, low = start - 1, guess;
 952
 953         while (high - low > 1) {
 954             guess = (high + low) / 2;
 955
 956             if (measureText(paint, workPaint,
 957                             text, start, guess, null, true, null) > wid)
 958                 high = guess;
 959             else
 960                 low = guess;
 961         }
 962
 963         if (low < start)
 964             return start;
 965         else
 966             return low;
 967     }
 968
 969     private int out(CharSequence text, int start, int end,
 970                       int above, int below, int top, int bottom, int v,
 971                       float spacingmult, float spacingadd,
 972                       LineHeightSpan[] chooseht, int[] choosehtv,
 973                       Paint.FontMetricsInt fm, boolean tab,
 974                       boolean needMultiply, int pstart, byte[] chdirs,
 975                       int dir, boolean easy, boolean last,
 976                       boolean includepad, boolean trackpad,
 977                       float[] widths, int widstart, int widoff,
 978                       TextUtils.TruncateAt ellipsize, float ellipsiswidth,
 979                       float textwidth, TextPaint paint) {
 980         int j = mLineCount;
 981         int off = j * mColumns;
 982         int want = off + mColumns + TOP;
 983         int[] lines = mLines;
 984
 985         // Log.e("text", "line " + start + " to " + end + (last ? "===" : ""));
 986
 987         if (want >= lines.length) {
 988             int nlen = ArrayUtils.idealIntArraySize(want + 1);
 989             int[] grow = new int[nlen];
 990             System.arraycopy(lines, 0, grow, 0, lines.length);
 991             mLines = grow;
 992             lines = grow;
 993
 994             Directions[] grow2 = new Directions[nlen];
 995             System.arraycopy(mLineDirections, 0, grow2, 0,
 996                              mLineDirections.length);
 997             mLineDirections = grow2;
 998         }
 999
1000         if (chooseht != null) {
1001             fm.ascent = above;
1002             fm.descent = below;
1003             fm.top = top;
1004             fm.bottom = bottom;
1005
1006             for (int i = 0; i < chooseht.length; i++) {
1007                 if (chooseht[i] instanceof LineHeightSpan.WithDensity) {
1008                     ((LineHeightSpan.WithDensity) chooseht[i]).
1009                         chooseHeight(text, start, end, choosehtv[i], v, fm, paint);
1010
1011                 } else {
1012                     chooseht[i].chooseHeight(text, start, end, choosehtv[i], v, fm);
1013                 }
1014             }
1015
1016             above = fm.ascent;
1017             below = fm.descent;
1018             top = fm.top;
1019             bottom = fm.bottom;
1020         }
1021
1022         if (j == 0) {
1023             if (trackpad) {
1024                 mTopPadding = top - above;
1025             }
1026
1027             if (includepad) {
1028                 above = top;
1029             }
1030         }
1031         if (last) {
1032             if (trackpad) {
1033                 mBottomPadding = bottom - below;
1034             }
1035
1036             if (includepad) {
1037                 below = bottom;
1038             }
1039         }
1040
1041         int extra;
1042
1043         if (needMultiply) {
1044             double ex = (below - above) * (spacingmult - 1) + spacingadd;
1045             if (ex >= 0) {
1046                 extra = (int)(ex + 0.5);
1047             } else {
1048                 extra = -(int)(-ex + 0.5);
1049             }
1050         } else {
1051             extra = 0;
1052         }
1053
1054         lines[off + START] = start;
1055         lines[off + TOP] = v;
1056         lines[off + DESCENT] = below + extra;
1057
1058         v += (below - above) + extra;
1059         lines[off + mColumns + START] = end;
1060         lines[off + mColumns + TOP] = v;
1061
1062         if (tab)
1063             lines[off + TAB] |= TAB_MASK;
1064
1065         {
1066             lines[off + DIR] |= dir << DIR_SHIFT;
1067
1068             int cur = Character.DIRECTIONALITY_LEFT_TO_RIGHT;
1069             int count = 0;
1070
1071             if (!easy) {
1072                 for (int k = start; k < end; k++) {
1073                     if (chdirs[k - pstart] != cur) {
1074                         count++;
1075                         cur = chdirs[k - pstart];
1076                     }
1077                 }
1078             }
1079
1080             Directions linedirs;
1081
1082             if (count == 0) {
1083                 linedirs = DIRS_ALL_LEFT_TO_RIGHT;
1084             } else {
1085                 short[] ld = new short[count + 1];
1086
1087                 cur = Character.DIRECTIONALITY_LEFT_TO_RIGHT;
1088                 count = 0;
1089                 int here = start;
1090
1091                 for (int k = start; k < end; k++) {
1092                     if (chdirs[k - pstart] != cur) {
1093                         // XXX check to make sure we don't
1094                         //     overflow short
1095                         ld[count++] = (short) (k - here);
1096                         cur = chdirs[k - pstart];
1097                         here = k;
1098                     }
1099                 }
1100
1101                 ld[count] = (short) (end - here);
1102
1103                 if (count == 1 && ld[0] == 0) {
1104                     linedirs = DIRS_ALL_RIGHT_TO_LEFT;
1105                 } else {
1106                     linedirs = new Directions(ld);
1107                 }
1108             }
1109
1110             mLineDirections[j] = linedirs;
1111
1112             // If ellipsize is in marquee mode, do not apply ellipsis on the first line
1113             if (ellipsize != null && (ellipsize != TextUtils.TruncateAt.MARQUEE || j != 0)) {
1114                 calculateEllipsis(start, end, widths, widstart, widoff,
1115                                   ellipsiswidth, ellipsize, j,
1116                                   textwidth, paint);
1117             }
1118         }
1119
1120         mLineCount++;
1121         return v;
1122     }
1123
1124     private void calculateEllipsis(int linestart, int lineend,
1125                                    float[] widths, int widstart, int widoff,
1126                                    float avail, TextUtils.TruncateAt where,
1127                                    int line, float textwidth, TextPaint paint) {
1128         int len = lineend - linestart;
1129
1130         if (textwidth <= avail) {
1131             // Everything fits!
1132             mLines[mColumns * line + ELLIPSIS_START] = 0;
1133             mLines[mColumns * line + ELLIPSIS_COUNT] = 0;
1134             return;
1135         }
1136
1137         float ellipsiswid = paint.measureText("\u2026");
1138         int ellipsisStart, ellipsisCount;
1139
1140         if (where == TextUtils.TruncateAt.START) {
1141             float sum = 0;
1142             int i;
1143
1144             for (i = len; i >= 0; i--) {
1145                 float w = widths[i - 1 + linestart - widstart + widoff];
1146
1147                 if (w + sum + ellipsiswid > avail) {
1148                     break;
1149                 }
1150
1151                 sum += w;
1152             }
1153
1154             ellipsisStart = 0;
1155             ellipsisCount = i;
1156         } else if (where == TextUtils.TruncateAt.END || where == TextUtils.TruncateAt.MARQUEE) {
1157             float sum = 0;
1158             int i;
1159
1160             for (i = 0; i < len; i++) {
1161                 float w = widths[i + linestart - widstart + widoff];
1162
1163                 if (w + sum + ellipsiswid > avail) {
1164                     break;
1165                 }
1166
1167                 sum += w;
1168             }
1169
1170             ellipsisStart = i;
1171             ellipsisCount = len - i;
1172         } else /* where = TextUtils.TruncateAt.MIDDLE */ {
1173             float lsum = 0, rsum = 0;
1174             int left = 0, right = len;
1175
1176             float ravail = (avail - ellipsiswid) / 2;
1177             for (right = len; right >= 0; right--) {
1178                 float w = widths[right - 1 + linestart - widstart + widoff];
1179
1180                 if (w + rsum > ravail) {
1181                     break;
1182                 }
1183
1184                 rsum += w;
1185             }
1186
1187             float lavail = avail - ellipsiswid - rsum;
1188             for (left = 0; left < right; left++) {
1189                 float w = widths[left + linestart - widstart + widoff];
1190
1191                 if (w + lsum > lavail) {
1192                     break;
1193                 }
1194
1195                 lsum += w;
1196             }
1197
1198             ellipsisStart = left;
1199             ellipsisCount = right - left;
1200         }
1201
1202         mLines[mColumns * line + ELLIPSIS_START] = ellipsisStart;
1203         mLines[mColumns * line + ELLIPSIS_COUNT] = ellipsisCount;
1204     }
1205
1206     // Override the baseclass so we can directly access our members,
1207     // rather than relying on member functions.
1208     // The logic mirrors that of Layout.getLineForVertical
1209     // FIXME: It may be faster to do a linear search for layouts without many lines.
1210     public int getLineForVertical(int vertical) {
1211         int high = mLineCount;
1212         int low = -1;
1213         int guess;
1214         int[] lines = mLines;
1215         while (high - low > 1) {
1216             guess = (high + low) >> 1;
1217             if (lines[mColumns * guess + TOP] > vertical){
1218                 high = guess;
1219             } else {
1220                 low = guess;
1221             }
1222         }
1223         if (low < 0) {
1224             return 0;
1225         } else {
1226             return low;
1227         }
1228     }
1229
1230     public int getLineCount() {
1231         return mLineCount;
1232     }
1233
1234     public int getLineTop(int line) {
1235         return mLines[mColumns * line + TOP];
1236     }
1237
1238     public int getLineDescent(int line) {
1239         return mLines[mColumns * line + DESCENT];
1240     }
1241
1242     public int getLineStart(int line) {
1243         return mLines[mColumns * line + START] & START_MASK;
1244     }
1245
1246     public int getParagraphDirection(int line) {
1247         return mLines[mColumns * line + DIR] >> DIR_SHIFT;
1248     }
1249
1250     public boolean getLineContainsTab(int line) {
1251         return (mLines[mColumns * line + TAB] & TAB_MASK) != 0;
1252     }
1253
1254     public final Directions getLineDirections(int line) {
1255         return mLineDirections[line];
1256     }
1257
1258     public int getTopPadding() {
1259         return mTopPadding;
1260     }
1261
1262     public int getBottomPadding() {
1263         return mBottomPadding;
1264     }
1265
1266     @Override
1267     public int getEllipsisCount(int line) {
1268         if (mColumns < COLUMNS_ELLIPSIZE) {
1269             return 0;
1270         }
1271
1272         return mLines[mColumns * line + ELLIPSIS_COUNT];
1273     }
1274
1275     @Override
1276     public int getEllipsisStart(int line) {
1277         if (mColumns < COLUMNS_ELLIPSIZE) {
1278             return 0;
1279         }
1280
1281         return mLines[mColumns * line + ELLIPSIS_START];
1282     }
1283
1284     @Override
1285     public int getEllipsizedWidth() {
1286         return mEllipsizedWidth;
1287     }
1288
1289     private int mLineCount;
1290     private int mTopPadding, mBottomPadding;
1291     private int mColumns;
1292     private int mEllipsizedWidth;
1293
1294     private static final int COLUMNS_NORMAL = 3;
1295     private static final int COLUMNS_ELLIPSIZE = 5;
1296     private static final int START = 0;
1297     private static final int DIR = START;
1298     private static final int TAB = START;
1299     private static final int TOP = 1;
1300     private static final int DESCENT = 2;
1301     private static final int ELLIPSIS_START = 3;
1302     private static final int ELLIPSIS_COUNT = 4;
1303
1304     private int[] mLines;
1305     private Directions[] mLineDirections;
1306
1307     private static final int START_MASK = 0x1FFFFFFF;
1308     private static final int DIR_MASK   = 0xC0000000;
1309     private static final int DIR_SHIFT  = 30;
1310     private static final int TAB_MASK   = 0x20000000;
1311
1312     private static final char FIRST_RIGHT_TO_LEFT = '\u0590';
1313
1314     /*
1315      * These are reused across calls to generate()
1316      */
1317     private byte[] mChdirs;
1318     private char[] mChs;
1319     private float[] mWidths;
1320     private Paint.FontMetricsInt mFontMetricsInt = new Paint.FontMetricsInt();
1321 }