core/java/android/text/SpannableStringBuilder.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.annotation.Nullable;
  20 import android.graphics.Canvas;
  21 import android.graphics.Paint;
  22 import android.text.style.ParagraphStyle;
  23 import android.util.Log;
  24
  25 import com.android.internal.util.ArrayUtils;
  26 import com.android.internal.util.GrowingArrayUtils;
  27
  28 import libcore.util.EmptyArray;
  29
  30 import java.lang.reflect.Array;
  31 import java.util.IdentityHashMap;
  32
  33 /**
  34  * This is the class for text whose content and markup can both be changed.
  35  */
  36 public class SpannableStringBuilder implements CharSequence, GetChars, Spannable, Editable,
  37         Appendable, GraphicsOperations {
  38     private final static String TAG = "SpannableStringBuilder";
  39     /**
  40      * Create a new SpannableStringBuilder with empty contents
  41      */
  42     public SpannableStringBuilder() {
  43         this("");
  44     }
  45
  46     /**
  47      * Create a new SpannableStringBuilder containing a copy of the
  48      * specified text, including its spans if any.
  49      */
  50     public SpannableStringBuilder(CharSequence text) {
  51         this(text, 0, text.length());
  52     }
  53
  54     /**
  55      * Create a new SpannableStringBuilder containing a copy of the
  56      * specified slice of the specified text, including its spans if any.
  57      */
  58     public SpannableStringBuilder(CharSequence text, int start, int end) {
  59         int srclen = end - start;
  60
  61         if (srclen < 0) throw new StringIndexOutOfBoundsException();
  62
  63         mText = ArrayUtils.newUnpaddedCharArray(GrowingArrayUtils.growSize(srclen));
  64         mGapStart = srclen;
  65         mGapLength = mText.length - srclen;
  66
  67         TextUtils.getChars(text, start, end, mText, 0);
  68
  69         mSpanCount = 0;
  70         mSpanInsertCount = 0;
  71         mSpans = EmptyArray.OBJECT;
  72         mSpanStarts = EmptyArray.INT;
  73         mSpanEnds = EmptyArray.INT;
  74         mSpanFlags = EmptyArray.INT;
  75         mSpanMax = EmptyArray.INT;
  76         mSpanOrder = EmptyArray.INT;
  77         mPrioSortBuffer = EmptyArray.INT;
  78         mOrderSortBuffer = EmptyArray.INT;
  79
  80         if (text instanceof Spanned) {
  81             Spanned sp = (Spanned) text;
  82             Object[] spans = sp.getSpans(start, end, Object.class);
  83
  84             for (int i = 0; i < spans.length; i++) {
  85                 if (spans[i] instanceof NoCopySpan) {
  86                     continue;
  87                 }
  88
  89                 int st = sp.getSpanStart(spans[i]) - start;
  90                 int en = sp.getSpanEnd(spans[i]) - start;
  91                 int fl = sp.getSpanFlags(spans[i]);
  92
  93                 if (st < 0)
  94                     st = 0;
  95                 if (st > end - start)
  96                     st = end - start;
  97
  98                 if (en < 0)
  99                     en = 0;
 100                 if (en > end - start)
 101                     en = end - start;
 102
 103                 setSpan(false, spans[i], st, en, fl);
 104             }
 105             restoreInvariants();
 106         }
 107     }
 108
 109     public static SpannableStringBuilder valueOf(CharSequence source) {
 110         if (source instanceof SpannableStringBuilder) {
 111             return (SpannableStringBuilder) source;
 112         } else {
 113             return new SpannableStringBuilder(source);
 114         }
 115     }
 116
 117     /**
 118      * Return the char at the specified offset within the buffer.
 119      */
 120     public char charAt(int where) {
 121         int len = length();
 122         if (where < 0) {
 123             throw new IndexOutOfBoundsException("charAt: " + where + " < 0");
 124         } else if (where >= len) {
 125             throw new IndexOutOfBoundsException("charAt: " + where + " >= length " + len);
 126         }
 127
 128         if (where >= mGapStart)
 129             return mText[where + mGapLength];
 130         else
 131             return mText[where];
 132     }
 133
 134     /**
 135      * Return the number of chars in the buffer.
 136      */
 137     public int length() {
 138         return mText.length - mGapLength;
 139     }
 140
 141     private void resizeFor(int size) {
 142         final int oldLength = mText.length;
 143         if (size + 1 <= oldLength) {
 144             return;
 145         }
 146
 147         char[] newText = ArrayUtils.newUnpaddedCharArray(GrowingArrayUtils.growSize(size));
 148         System.arraycopy(mText, 0, newText, 0, mGapStart);
 149         final int newLength = newText.length;
 150         final int delta = newLength - oldLength;
 151         final int after = oldLength - (mGapStart + mGapLength);
 152         System.arraycopy(mText, oldLength - after, newText, newLength - after, after);
 153         mText = newText;
 154
 155         mGapLength += delta;
 156         if (mGapLength < 1)
 157             new Exception("mGapLength < 1").printStackTrace();
 158
 159         if (mSpanCount != 0) {
 160             for (int i = 0; i < mSpanCount; i++) {
 161                 if (mSpanStarts[i] > mGapStart) mSpanStarts[i] += delta;
 162                 if (mSpanEnds[i] > mGapStart) mSpanEnds[i] += delta;
 163             }
 164             calcMax(treeRoot());
 165         }
 166     }
 167
 168     private void moveGapTo(int where) {
 169         if (where == mGapStart)
 170             return;
 171
 172         boolean atEnd = (where == length());
 173
 174         if (where < mGapStart) {
 175             int overlap = mGapStart - where;
 176             System.arraycopy(mText, where, mText, mGapStart + mGapLength - overlap, overlap);
 177         } else /* where > mGapStart */ {
 178             int overlap = where - mGapStart;
 179             System.arraycopy(mText, where + mGapLength - overlap, mText, mGapStart, overlap);
 180         }
 181
 182         // TODO: be more clever (although the win really isn't that big)
 183         if (mSpanCount != 0) {
 184             for (int i = 0; i < mSpanCount; i++) {
 185                 int start = mSpanStarts[i];
 186                 int end = mSpanEnds[i];
 187
 188                 if (start > mGapStart)
 189                     start -= mGapLength;
 190                 if (start > where)
 191                     start += mGapLength;
 192                 else if (start == where) {
 193                     int flag = (mSpanFlags[i] & START_MASK) >> START_SHIFT;
 194
 195                     if (flag == POINT || (atEnd && flag == PARAGRAPH))
 196                         start += mGapLength;
 197                 }
 198
 199                 if (end > mGapStart)
 200                     end -= mGapLength;
 201                 if (end > where)
 202                     end += mGapLength;
 203                 else if (end == where) {
 204                     int flag = (mSpanFlags[i] & END_MASK);
 205
 206                     if (flag == POINT || (atEnd && flag == PARAGRAPH))
 207                         end += mGapLength;
 208                 }
 209
 210                 mSpanStarts[i] = start;
 211                 mSpanEnds[i] = end;
 212             }
 213             calcMax(treeRoot());
 214         }
 215
 216         mGapStart = where;
 217     }
 218
 219     // Documentation from interface
 220     public SpannableStringBuilder insert(int where, CharSequence tb, int start, int end) {
 221         return replace(where, where, tb, start, end);
 222     }
 223
 224     // Documentation from interface
 225     public SpannableStringBuilder insert(int where, CharSequence tb) {
 226         return replace(where, where, tb, 0, tb.length());
 227     }
 228
 229     // Documentation from interface
 230     public SpannableStringBuilder delete(int start, int end) {
 231         SpannableStringBuilder ret = replace(start, end, "", 0, 0);
 232
 233         if (mGapLength > 2 * length())
 234             resizeFor(length());
 235
 236         return ret; // == this
 237     }
 238
 239     // Documentation from interface
 240     public void clear() {
 241         replace(0, length(), "", 0, 0);
 242         mSpanInsertCount = 0;
 243     }
 244
 245     // Documentation from interface
 246     public void clearSpans() {
 247         for (int i = mSpanCount - 1; i >= 0; i--) {
 248             Object what = mSpans[i];
 249             int ostart = mSpanStarts[i];
 250             int oend = mSpanEnds[i];
 251
 252             if (ostart > mGapStart)
 253                 ostart -= mGapLength;
 254             if (oend > mGapStart)
 255                 oend -= mGapLength;
 256
 257             mSpanCount = i;
 258             mSpans[i] = null;
 259
 260             sendSpanRemoved(what, ostart, oend);
 261         }
 262         if (mIndexOfSpan != null) {
 263             mIndexOfSpan.clear();
 264         }
 265         mSpanInsertCount = 0;
 266     }
 267
 268     // Documentation from interface
 269     public SpannableStringBuilder append(CharSequence text) {
 270         int length = length();
 271         return replace(length, length, text, 0, text.length());
 272     }
 273
 274     /**
 275      * Appends the character sequence {@code text} and spans {@code what} over the appended part.
 276      * See {@link Spanned} for an explanation of what the flags mean.
 277      * @param text the character sequence to append.
 278      * @param what the object to be spanned over the appended text.
 279      * @param flags see {@link Spanned}.
 280      * @return this {@code SpannableStringBuilder}.
 281      */
 282     public SpannableStringBuilder append(CharSequence text, Object what, int flags) {
 283         int start = length();
 284         append(text);
 285         setSpan(what, start, length(), flags);
 286         return this;
 287     }
 288
 289     // Documentation from interface
 290     public SpannableStringBuilder append(CharSequence text, int start, int end) {
 291         int length = length();
 292         return replace(length, length, text, start, end);
 293     }
 294
 295     // Documentation from interface
 296     public SpannableStringBuilder append(char text) {
 297         return append(String.valueOf(text));
 298     }
 299
 300     // Returns true if a node was removed (so we can restart search from root)
 301     private boolean removeSpansForChange(int start, int end, boolean textIsRemoved, int i) {
 302         if ((i & 1) != 0) {
 303             // internal tree node
 304             if (resolveGap(mSpanMax[i]) >= start &&
 305                     removeSpansForChange(start, end, textIsRemoved, leftChild(i))) {
 306                 return true;
 307             }
 308         }
 309         if (i < mSpanCount) {
 310             if ((mSpanFlags[i] & Spanned.SPAN_EXCLUSIVE_EXCLUSIVE) ==
 311                     Spanned.SPAN_EXCLUSIVE_EXCLUSIVE &&
 312                     mSpanStarts[i] >= start && mSpanStarts[i] < mGapStart + mGapLength &&
 313                     mSpanEnds[i] >= start && mSpanEnds[i] < mGapStart + mGapLength &&
 314                     // The following condition indicates that the span would become empty
 315                     (textIsRemoved || mSpanStarts[i] > start || mSpanEnds[i] < mGapStart)) {
 316                 mIndexOfSpan.remove(mSpans[i]);
 317                 removeSpan(i);
 318                 return true;
 319             }
 320             return resolveGap(mSpanStarts[i]) <= end && (i & 1) != 0 &&
 321                 removeSpansForChange(start, end, textIsRemoved, rightChild(i));
 322         }
 323         return false;
 324     }
 325
 326     private void change(int start, int end, CharSequence cs, int csStart, int csEnd) {
 327         // Can be negative
 328         final int replacedLength = end - start;
 329         final int replacementLength = csEnd - csStart;
 330         final int nbNewChars = replacementLength - replacedLength;
 331
 332         boolean changed = false;
 333         for (int i = mSpanCount - 1; i >= 0; i--) {
 334             int spanStart = mSpanStarts[i];
 335             if (spanStart > mGapStart)
 336                 spanStart -= mGapLength;
 337
 338             int spanEnd = mSpanEnds[i];
 339             if (spanEnd > mGapStart)
 340                 spanEnd -= mGapLength;
 341
 342             if ((mSpanFlags[i] & SPAN_PARAGRAPH) == SPAN_PARAGRAPH) {
 343                 int ost = spanStart;
 344                 int oen = spanEnd;
 345                 int clen = length();
 346
 347                 if (spanStart > start && spanStart <= end) {
 348                     for (spanStart = end; spanStart < clen; spanStart++)
 349                         if (spanStart > end && charAt(spanStart - 1) == '\n')
 350                             break;
 351                 }
 352
 353                 if (spanEnd > start && spanEnd <= end) {
 354                     for (spanEnd = end; spanEnd < clen; spanEnd++)
 355                         if (spanEnd > end && charAt(spanEnd - 1) == '\n')
 356                             break;
 357                 }
 358
 359                 if (spanStart != ost || spanEnd != oen) {
 360                     setSpan(false, mSpans[i], spanStart, spanEnd, mSpanFlags[i]);
 361                     changed = true;
 362                 }
 363             }
 364
 365             int flags = 0;
 366             if (spanStart == start) flags |= SPAN_START_AT_START;
 367             else if (spanStart == end + nbNewChars) flags |= SPAN_START_AT_END;
 368             if (spanEnd == start) flags |= SPAN_END_AT_START;
 369             else if (spanEnd == end + nbNewChars) flags |= SPAN_END_AT_END;
 370             mSpanFlags[i] |= flags;
 371         }
 372         if (changed) {
 373             restoreInvariants();
 374         }
 375
 376         moveGapTo(end);
 377
 378         if (nbNewChars >= mGapLength) {
 379             resizeFor(mText.length + nbNewChars - mGapLength);
 380         }
 381
 382         final boolean textIsRemoved = replacementLength == 0;
 383         // The removal pass needs to be done before the gap is updated in order to broadcast the
 384         // correct previous positions to the correct intersecting SpanWatchers
 385         if (replacedLength > 0) { // no need for span fixup on pure insertion
 386             while (mSpanCount > 0 &&
 387                     removeSpansForChange(start, end, textIsRemoved, treeRoot())) {
 388                 // keep deleting spans as needed, and restart from root after every deletion
 389                 // because deletion can invalidate an index.
 390             }
 391         }
 392
 393         mGapStart += nbNewChars;
 394         mGapLength -= nbNewChars;
 395
 396         if (mGapLength < 1)
 397             new Exception("mGapLength < 1").printStackTrace();
 398
 399         TextUtils.getChars(cs, csStart, csEnd, mText, start);
 400
 401         if (replacedLength > 0) { // no need for span fixup on pure insertion
 402             // TODO potential optimization: only update bounds on intersecting spans
 403             final boolean atEnd = (mGapStart + mGapLength == mText.length);
 404
 405             for (int i = 0; i < mSpanCount; i++) {
 406                 final int startFlag = (mSpanFlags[i] & START_MASK) >> START_SHIFT;
 407                 mSpanStarts[i] = updatedIntervalBound(mSpanStarts[i], start, nbNewChars, startFlag,
 408                         atEnd, textIsRemoved);
 409
 410                 final int endFlag = (mSpanFlags[i] & END_MASK);
 411                 mSpanEnds[i] = updatedIntervalBound(mSpanEnds[i], start, nbNewChars, endFlag,
 412                         atEnd, textIsRemoved);
 413             }
 414             // TODO potential optimization: only fix up invariants when bounds actually changed
 415             restoreInvariants();
 416         }
 417
 418         if (cs instanceof Spanned) {
 419             Spanned sp = (Spanned) cs;
 420             Object[] spans = sp.getSpans(csStart, csEnd, Object.class);
 421
 422             for (int i = 0; i < spans.length; i++) {
 423                 int st = sp.getSpanStart(spans[i]);
 424                 int en = sp.getSpanEnd(spans[i]);
 425
 426                 if (st < csStart) st = csStart;
 427                 if (en > csEnd) en = csEnd;
 428
 429                 // Add span only if this object is not yet used as a span in this string
 430                 if (getSpanStart(spans[i]) < 0) {
 431                     int copySpanStart = st - csStart + start;
 432                     int copySpanEnd = en - csStart + start;
 433                     int copySpanFlags = sp.getSpanFlags(spans[i]) | SPAN_ADDED;
 434
 435                     int flagsStart = (copySpanFlags & START_MASK) >> START_SHIFT;
 436                     int flagsEnd = copySpanFlags & END_MASK;
 437
 438                     if(!isInvalidParagraphStart(copySpanStart, flagsStart) &&
 439                             !isInvalidParagraphEnd(copySpanEnd, flagsEnd)) {
 440                         setSpan(false, spans[i], copySpanStart, copySpanEnd, copySpanFlags);
 441                     }
 442                 }
 443             }
 444             restoreInvariants();
 445         }
 446     }
 447
 448     private int updatedIntervalBound(int offset, int start, int nbNewChars, int flag, boolean atEnd,
 449             boolean textIsRemoved) {
 450         if (offset >= start && offset < mGapStart + mGapLength) {
 451             if (flag == POINT) {
 452                 // A POINT located inside the replaced range should be moved to the end of the
 453                 // replaced text.
 454                 // The exception is when the point is at the start of the range and we are doing a
 455                 // text replacement (as opposed to a deletion): the point stays there.
 456                 if (textIsRemoved || offset > start) {
 457                     return mGapStart + mGapLength;
 458                 }
 459             } else {
 460                 if (flag == PARAGRAPH) {
 461                     if (atEnd) {
 462                         return mGapStart + mGapLength;
 463                     }
 464                 } else { // MARK
 465                     // MARKs should be moved to the start, with the exception of a mark located at
 466                     // the end of the range (which will be < mGapStart + mGapLength since mGapLength
 467                     // is > 0, which should stay 'unchanged' at the end of the replaced text.
 468                     if (textIsRemoved || offset < mGapStart - nbNewChars) {
 469                         return start;
 470                     } else {
 471                         // Move to the end of replaced text (needed if nbNewChars != 0)
 472                         return mGapStart;
 473                     }
 474                 }
 475             }
 476         }
 477         return offset;
 478     }
 479
 480     // Note: caller is responsible for removing the mIndexOfSpan entry.
 481     private void removeSpan(int i) {
 482         Object object = mSpans[i];
 483
 484         int start = mSpanStarts[i];
 485         int end = mSpanEnds[i];
 486
 487         if (start > mGapStart) start -= mGapLength;
 488         if (end > mGapStart) end -= mGapLength;
 489
 490         int count = mSpanCount - (i + 1);
 491         System.arraycopy(mSpans, i + 1, mSpans, i, count);
 492         System.arraycopy(mSpanStarts, i + 1, mSpanStarts, i, count);
 493         System.arraycopy(mSpanEnds, i + 1, mSpanEnds, i, count);
 494         System.arraycopy(mSpanFlags, i + 1, mSpanFlags, i, count);
 495         System.arraycopy(mSpanOrder, i + 1, mSpanOrder, i, count);
 496
 497         mSpanCount--;
 498
 499         invalidateIndex(i);
 500         mSpans[mSpanCount] = null;
 501
 502         // Invariants must be restored before sending span removed notifications.
 503         restoreInvariants();
 504
 505         sendSpanRemoved(object, start, end);
 506     }
 507
 508     // Documentation from interface
 509     public SpannableStringBuilder replace(int start, int end, CharSequence tb) {
 510         return replace(start, end, tb, 0, tb.length());
 511     }
 512
 513     // Documentation from interface
 514     public SpannableStringBuilder replace(final int start, final int end,
 515             CharSequence tb, int tbstart, int tbend) {
 516         checkRange("replace", start, end);
 517
 518         int filtercount = mFilters.length;
 519         for (int i = 0; i < filtercount; i++) {
 520             CharSequence repl = mFilters[i].filter(tb, tbstart, tbend, this, start, end);
 521
 522             if (repl != null) {
 523                 tb = repl;
 524                 tbstart = 0;
 525                 tbend = repl.length();
 526             }
 527         }
 528
 529         final int origLen = end - start;
 530         final int newLen = tbend - tbstart;
 531
 532         if (origLen == 0 && newLen == 0 && !hasNonExclusiveExclusiveSpanAt(tb, tbstart)) {
 533             // This is a no-op iif there are no spans in tb that would be added (with a 0-length)
 534             // Early exit so that the text watchers do not get notified
 535             return this;
 536         }
 537
 538         TextWatcher[] textWatchers = getSpans(start, start + origLen, TextWatcher.class);
 539         sendBeforeTextChanged(textWatchers, start, origLen, newLen);
 540
 541         // Try to keep the cursor / selection at the same relative position during
 542         // a text replacement. If replaced or replacement text length is zero, this
 543         // is already taken care of.
 544         boolean adjustSelection = origLen != 0 && newLen != 0;
 545         int selectionStart = 0;
 546         int selectionEnd = 0;
 547         if (adjustSelection) {
 548             selectionStart = Selection.getSelectionStart(this);
 549             selectionEnd = Selection.getSelectionEnd(this);
 550         }
 551
 552         change(start, end, tb, tbstart, tbend);
 553
 554         if (adjustSelection) {
 555             boolean changed = false;
 556             if (selectionStart > start && selectionStart < end) {
 557                 final int offset = (selectionStart - start) * newLen / origLen;
 558                 selectionStart = start + offset;
 559
 560                 changed = true;
 561                 setSpan(false, Selection.SELECTION_START, selectionStart, selectionStart,
 562                         Spanned.SPAN_POINT_POINT);
 563             }
 564             if (selectionEnd > start && selectionEnd < end) {
 565                 final int offset = (selectionEnd - start) * newLen / origLen;
 566                 selectionEnd = start + offset;
 567
 568                 changed = true;
 569                 setSpan(false, Selection.SELECTION_END, selectionEnd, selectionEnd,
 570                         Spanned.SPAN_POINT_POINT);
 571             }
 572             if (changed) {
 573                 restoreInvariants();
 574             }
 575         }
 576
 577         sendTextChanged(textWatchers, start, origLen, newLen);
 578         sendAfterTextChanged(textWatchers);
 579
 580         // Span watchers need to be called after text watchers, which may update the layout
 581         sendToSpanWatchers(start, end, newLen - origLen);
 582
 583         return this;
 584     }
 585
 586     private static boolean hasNonExclusiveExclusiveSpanAt(CharSequence text, int offset) {
 587         if (text instanceof Spanned) {
 588             Spanned spanned = (Spanned) text;
 589             Object[] spans = spanned.getSpans(offset, offset, Object.class);
 590             final int length = spans.length;
 591             for (int i = 0; i < length; i++) {
 592                 Object span = spans[i];
 593                 int flags = spanned.getSpanFlags(span);
 594                 if (flags != Spanned.SPAN_EXCLUSIVE_EXCLUSIVE) return true;
 595             }
 596         }
 597         return false;
 598     }
 599
 600     private void sendToSpanWatchers(int replaceStart, int replaceEnd, int nbNewChars) {
 601         for (int i = 0; i < mSpanCount; i++) {
 602             int spanFlags = mSpanFlags[i];
 603
 604             // This loop handles only modified (not added) spans.
 605             if ((spanFlags & SPAN_ADDED) != 0) continue;
 606             int spanStart = mSpanStarts[i];
 607             int spanEnd = mSpanEnds[i];
 608             if (spanStart > mGapStart) spanStart -= mGapLength;
 609             if (spanEnd > mGapStart) spanEnd -= mGapLength;
 610
 611             int newReplaceEnd = replaceEnd + nbNewChars;
 612             boolean spanChanged = false;
 613
 614             int previousSpanStart = spanStart;
 615             if (spanStart > newReplaceEnd) {
 616                 if (nbNewChars != 0) {
 617                     previousSpanStart -= nbNewChars;
 618                     spanChanged = true;
 619                 }
 620             } else if (spanStart >= replaceStart) {
 621                 // No change if span start was already at replace interval boundaries before replace
 622                 if ((spanStart != replaceStart ||
 623                         ((spanFlags & SPAN_START_AT_START) != SPAN_START_AT_START)) &&
 624                         (spanStart != newReplaceEnd ||
 625                         ((spanFlags & SPAN_START_AT_END) != SPAN_START_AT_END))) {
 626                     // TODO A correct previousSpanStart cannot be computed at this point.
 627                     // It would require to save all the previous spans' positions before the replace
 628                     // Using an invalid -1 value to convey this would break the broacast range
 629                     spanChanged = true;
 630                 }
 631             }
 632
 633             int previousSpanEnd = spanEnd;
 634             if (spanEnd > newReplaceEnd) {
 635                 if (nbNewChars != 0) {
 636                     previousSpanEnd -= nbNewChars;
 637                     spanChanged = true;
 638                 }
 639             } else if (spanEnd >= replaceStart) {
 640                 // No change if span start was already at replace interval boundaries before replace
 641                 if ((spanEnd != replaceStart ||
 642                         ((spanFlags & SPAN_END_AT_START) != SPAN_END_AT_START)) &&
 643                         (spanEnd != newReplaceEnd ||
 644                         ((spanFlags & SPAN_END_AT_END) != SPAN_END_AT_END))) {
 645                     // TODO same as above for previousSpanEnd
 646                     spanChanged = true;
 647                 }
 648             }
 649
 650             if (spanChanged) {
 651                 sendSpanChanged(mSpans[i], previousSpanStart, previousSpanEnd, spanStart, spanEnd);
 652             }
 653             mSpanFlags[i] &= ~SPAN_START_END_MASK;
 654         }
 655
 656         // Handle added spans
 657         for (int i = 0; i < mSpanCount; i++) {
 658             int spanFlags = mSpanFlags[i];
 659             if ((spanFlags & SPAN_ADDED) != 0) {
 660                 mSpanFlags[i] &= ~SPAN_ADDED;
 661                 int spanStart = mSpanStarts[i];
 662                 int spanEnd = mSpanEnds[i];
 663                 if (spanStart > mGapStart) spanStart -= mGapLength;
 664                 if (spanEnd > mGapStart) spanEnd -= mGapLength;
 665                 sendSpanAdded(mSpans[i], spanStart, spanEnd);
 666             }
 667         }
 668     }
 669
 670     /**
 671      * Mark the specified range of text with the specified object.
 672      * The flags determine how the span will behave when text is
 673      * inserted at the start or end of the span's range.
 674      */
 675     public void setSpan(Object what, int start, int end, int flags) {
 676         setSpan(true, what, start, end, flags);
 677     }
 678
 679     // Note: if send is false, then it is the caller's responsibility to restore
 680     // invariants. If send is false and the span already exists, then this method
 681     // will not change the index of any spans.
 682     private void setSpan(boolean send, Object what, int start, int end, int flags) {
 683         checkRange("setSpan", start, end);
 684
 685         int flagsStart = (flags & START_MASK) >> START_SHIFT;
 686         if(isInvalidParagraphStart(start, flagsStart)) {
 687             throw new RuntimeException("PARAGRAPH span must start at paragraph boundary");
 688         }
 689
 690         int flagsEnd = flags & END_MASK;
 691         if(isInvalidParagraphEnd(end, flagsEnd)) {
 692             throw new RuntimeException("PARAGRAPH span must end at paragraph boundary");
 693         }
 694
 695         // 0-length Spanned.SPAN_EXCLUSIVE_EXCLUSIVE
 696         if (flagsStart == POINT && flagsEnd == MARK && start == end) {
 697             if (send) {
 698                 Log.e(TAG, "SPAN_EXCLUSIVE_EXCLUSIVE spans cannot have a zero length");
 699             }
 700             // Silently ignore invalid spans when they are created from this class.
 701             // This avoids the duplication of the above test code before all the
 702             // calls to setSpan that are done in this class
 703             return;
 704         }
 705
 706         int nstart = start;
 707         int nend = end;
 708
 709         if (start > mGapStart) {
 710             start += mGapLength;
 711         } else if (start == mGapStart) {
 712             if (flagsStart == POINT || (flagsStart == PARAGRAPH && start == length()))
 713                 start += mGapLength;
 714         }
 715
 716         if (end > mGapStart) {
 717             end += mGapLength;
 718         } else if (end == mGapStart) {
 719             if (flagsEnd == POINT || (flagsEnd == PARAGRAPH && end == length()))
 720                 end += mGapLength;
 721         }
 722
 723         if (mIndexOfSpan != null) {
 724             Integer index = mIndexOfSpan.get(what);
 725             if (index != null) {
 726                 int i = index;
 727                 int ostart = mSpanStarts[i];
 728                 int oend = mSpanEnds[i];
 729
 730                 if (ostart > mGapStart)
 731                     ostart -= mGapLength;
 732                 if (oend > mGapStart)
 733                     oend -= mGapLength;
 734
 735                 mSpanStarts[i] = start;
 736                 mSpanEnds[i] = end;
 737                 mSpanFlags[i] = flags;
 738
 739                 if (send) {
 740                     restoreInvariants();
 741                     sendSpanChanged(what, ostart, oend, nstart, nend);
 742                 }
 743
 744                 return;
 745             }
 746         }
 747
 748         mSpans = GrowingArrayUtils.append(mSpans, mSpanCount, what);
 749         mSpanStarts = GrowingArrayUtils.append(mSpanStarts, mSpanCount, start);
 750         mSpanEnds = GrowingArrayUtils.append(mSpanEnds, mSpanCount, end);
 751         mSpanFlags = GrowingArrayUtils.append(mSpanFlags, mSpanCount, flags);
 752         mSpanOrder = GrowingArrayUtils.append(mSpanOrder, mSpanCount, mSpanInsertCount);
 753         invalidateIndex(mSpanCount);
 754         mSpanCount++;
 755         mSpanInsertCount++;
 756         // Make sure there is enough room for empty interior nodes.
 757         // This magic formula computes the size of the smallest perfect binary
 758         // tree no smaller than mSpanCount.
 759         int sizeOfMax = 2 * treeRoot() + 1;
 760         if (mSpanMax.length < sizeOfMax) {
 761             mSpanMax = new int[sizeOfMax];
 762         }
 763
 764         if (send) {
 765             restoreInvariants();
 766             sendSpanAdded(what, nstart, nend);
 767         }
 768     }
 769
 770     private final boolean isInvalidParagraphStart(int start, int flagsStart) {
 771         if (flagsStart == PARAGRAPH) {
 772             if (start != 0 && start != length()) {
 773                 char c = charAt(start - 1);
 774
 775                 if (c != '\n') return true;
 776             }
 777         }
 778         return false;
 779     }
 780
 781     private final boolean isInvalidParagraphEnd(int end, int flagsEnd) {
 782         if (flagsEnd == PARAGRAPH) {
 783             if (end != 0 && end != length()) {
 784                 char c = charAt(end - 1);
 785
 786                 if (c != '\n') return true;
 787             }
 788         }
 789         return false;
 790     }
 791
 792     /**
 793      * Remove the specified markup object from the buffer.
 794      */
 795     public void removeSpan(Object what) {
 796         if (mIndexOfSpan == null) return;
 797         Integer i = mIndexOfSpan.remove(what);
 798         if (i != null) {
 799             removeSpan(i.intValue());
 800         }
 801     }
 802
 803     /**
 804      * Return externally visible offset given offset into gapped buffer.
 805      */
 806     private int resolveGap(int i) {
 807         return i > mGapStart ? i - mGapLength : i;
 808     }
 809
 810     /**
 811      * Return the buffer offset of the beginning of the specified
 812      * markup object, or -1 if it is not attached to this buffer.
 813      */
 814     public int getSpanStart(Object what) {
 815         if (mIndexOfSpan == null) return -1;
 816         Integer i = mIndexOfSpan.get(what);
 817         return i == null ? -1 : resolveGap(mSpanStarts[i]);
 818     }
 819
 820     /**
 821      * Return the buffer offset of the end of the specified
 822      * markup object, or -1 if it is not attached to this buffer.
 823      */
 824     public int getSpanEnd(Object what) {
 825         if (mIndexOfSpan == null) return -1;
 826         Integer i = mIndexOfSpan.get(what);
 827         return i == null ? -1 : resolveGap(mSpanEnds[i]);
 828     }
 829
 830     /**
 831      * Return the flags of the end of the specified
 832      * markup object, or 0 if it is not attached to this buffer.
 833      */
 834     public int getSpanFlags(Object what) {
 835         if (mIndexOfSpan == null) return 0;
 836         Integer i = mIndexOfSpan.get(what);
 837         return i == null ? 0 : mSpanFlags[i];
 838     }
 839
 840     /**
 841      * Return an array of the spans of the specified type that overlap
 842      * the specified range of the buffer.  The kind may be Object.class to get
 843      * a list of all the spans regardless of type.
 844      */
 845     @SuppressWarnings("unchecked")
 846     public <T> T[] getSpans(int queryStart, int queryEnd, @Nullable Class<T> kind) {
 847         return getSpans(queryStart, queryEnd, kind, true);
 848     }
 849
 850     /**
 851      * Return an array of the spans of the specified type that overlap
 852      * the specified range of the buffer.  The kind may be Object.class to get
 853      * a list of all the spans regardless of type.
 854      *
 855      * @param queryStart Start index.
 856      * @param queryEnd End index.
 857      * @param kind Class type to search for.
 858      * @param sort If true the results are sorted by the insertion order.
 859      * @param <T>
 860      * @return Array of the spans. Empty array if no results are found.
 861      *
 862      * @hide
 863      */
 864     public <T> T[] getSpans(int queryStart, int queryEnd, @Nullable Class<T> kind,
 865                                  boolean sort) {
 866         if (kind == null) return (T[]) ArrayUtils.emptyArray(Object.class);
 867         if (mSpanCount == 0) return ArrayUtils.emptyArray(kind);
 868         int count = countSpans(queryStart, queryEnd, kind, treeRoot());
 869         if (count == 0) {
 870             return ArrayUtils.emptyArray(kind);
 871         }
 872
 873         // Safe conversion, but requires a suppressWarning
 874         T[] ret = (T[]) Array.newInstance(kind, count);
 875         if (sort) {
 876             mPrioSortBuffer = checkSortBuffer(mPrioSortBuffer, count);
 877             mOrderSortBuffer = checkSortBuffer(mOrderSortBuffer, count);
 878         }
 879         getSpansRec(queryStart, queryEnd, kind, treeRoot(), ret, mPrioSortBuffer,
 880                 mOrderSortBuffer, 0, sort);
 881         if (sort) sort(ret, mPrioSortBuffer, mOrderSortBuffer);
 882         return ret;
 883     }
 884
 885     private int countSpans(int queryStart, int queryEnd, Class kind, int i) {
 886         int count = 0;
 887         if ((i & 1) != 0) {
 888             // internal tree node
 889             int left = leftChild(i);
 890             int spanMax = mSpanMax[left];
 891             if (spanMax > mGapStart) {
 892                 spanMax -= mGapLength;
 893             }
 894             if (spanMax >= queryStart) {
 895                 count = countSpans(queryStart, queryEnd, kind, left);
 896             }
 897         }
 898         if (i < mSpanCount) {
 899             int spanStart = mSpanStarts[i];
 900             if (spanStart > mGapStart) {
 901                 spanStart -= mGapLength;
 902             }
 903             if (spanStart <= queryEnd) {
 904                 int spanEnd = mSpanEnds[i];
 905                 if (spanEnd > mGapStart) {
 906                     spanEnd -= mGapLength;
 907                 }
 908                 if (spanEnd >= queryStart &&
 909                     (spanStart == spanEnd || queryStart == queryEnd ||
 910                         (spanStart != queryEnd && spanEnd != queryStart)) &&
 911                         (Object.class == kind || kind.isInstance(mSpans[i]))) {
 912                     count++;
 913                 }
 914                 if ((i & 1) != 0) {
 915                     count += countSpans(queryStart, queryEnd, kind, rightChild(i));
 916                 }
 917             }
 918         }
 919         return count;
 920     }
 921
 922     /**
 923      * Fills the result array with the spans found under the current interval tree node.
 924      *
 925      * @param queryStart Start index for the interval query.
 926      * @param queryEnd End index for the interval query.
 927      * @param kind Class type to search for.
 928      * @param i Index of the current tree node.
 929      * @param ret Array to be filled with results.
 930      * @param priority Buffer to keep record of the priorities of spans found.
 931      * @param insertionOrder Buffer to keep record of the insertion orders of spans found.
 932      * @param count The number of found spans.
 933      * @param sort Flag to fill the priority and insertion order buffers. If false then
 934      *             the spans with priority flag will be sorted in the result array.
 935      * @param <T>
 936      * @return The total number of spans found.
 937      */
 938     @SuppressWarnings("unchecked")
 939     private <T> int getSpansRec(int queryStart, int queryEnd, Class<T> kind,
 940             int i, T[] ret, int[] priority, int[] insertionOrder, int count, boolean sort) {
 941         if ((i & 1) != 0) {
 942             // internal tree node
 943             int left = leftChild(i);
 944             int spanMax = mSpanMax[left];
 945             if (spanMax > mGapStart) {
 946                 spanMax -= mGapLength;
 947             }
 948             if (spanMax >= queryStart) {
 949                 count = getSpansRec(queryStart, queryEnd, kind, left, ret, priority,
 950                         insertionOrder, count, sort);
 951             }
 952         }
 953         if (i >= mSpanCount) return count;
 954         int spanStart = mSpanStarts[i];
 955         if (spanStart > mGapStart) {
 956             spanStart -= mGapLength;
 957         }
 958         if (spanStart <= queryEnd) {
 959             int spanEnd = mSpanEnds[i];
 960             if (spanEnd > mGapStart) {
 961                 spanEnd -= mGapLength;
 962             }
 963             if (spanEnd >= queryStart &&
 964                     (spanStart == spanEnd || queryStart == queryEnd ||
 965                         (spanStart != queryEnd && spanEnd != queryStart)) &&
 966                         (Object.class == kind || kind.isInstance(mSpans[i]))) {
 967                 int spanPriority = mSpanFlags[i] & SPAN_PRIORITY;
 968                 if(sort) {
 969                     ret[count] = (T) mSpans[i];
 970                     priority[count] = spanPriority;
 971                     insertionOrder[count] = mSpanOrder[i];
 972                 } else if (spanPriority != 0) {
 973                     //insertion sort for elements with priority
 974                     int j = 0;
 975                     for (; j < count; j++) {
 976                         int p = getSpanFlags(ret[j]) & SPAN_PRIORITY;
 977                         if (spanPriority > p) break;
 978                     }
 979                     System.arraycopy(ret, j, ret, j + 1, count - j);
 980                     ret[j] = (T) mSpans[i];
 981                 }
 982                 count++;
 983             }
 984             if (count < ret.length && (i & 1) != 0) {
 985                 count = getSpansRec(queryStart, queryEnd, kind, rightChild(i), ret, priority,
 986                         insertionOrder, count, sort);
 987             }
 988         }
 989         return count;
 990     }
 991
 992     /**
 993      * Check the size of the buffer and grow if required.
 994      *
 995      * @param buffer Buffer to be checked.
 996      * @param size Required size.
 997      * @return Same buffer instance if the current size is greater than required size. Otherwise a
 998      * new instance is created and returned.
 999      */
1000     private final int[] checkSortBuffer(int[] buffer, int size) {
1001         if(size > buffer.length) {
1002             return ArrayUtils.newUnpaddedIntArray(GrowingArrayUtils.growSize(size));
1003         }
1004         return buffer;
1005     }
1006
1007     /**
1008      * An iterative heap sort implementation. It will sort the spans using first their priority
1009      * then insertion order. A span with higher priority will be before a span with lower
1010      * priority. If priorities are the same, the spans will be sorted with insertion order. A
1011      * span with a lower insertion order will be before a span with a higher insertion order.
1012      *
1013      * @param array Span array to be sorted.
1014      * @param priority Priorities of the spans
1015      * @param insertionOrder Insertion orders of the spans
1016      * @param <T> Span object type.
1017      * @param <T>
1018      */
1019     private final <T> void sort(T[] array, int[] priority, int[] insertionOrder) {
1020         int size = array.length;
1021         for (int i = size / 2 - 1; i >= 0; i--) {
1022             siftDown(i, array, size, priority, insertionOrder);
1023         }
1024
1025         for (int i = size - 1; i > 0; i--) {
1026             T v = array[0];
1027             int prio = priority[0];
1028             int insertOrder = insertionOrder[0];
1029             array[0] = array[i];
1030             priority[0] = priority[i];
1031             insertionOrder[0] = insertionOrder[i];
1032             siftDown(0, array, i, priority, insertionOrder);
1033             array[i] = v;
1034             priority[i] = prio;
1035             insertionOrder[i] = insertOrder;
1036         }
1037     }
1038
1039     /**
1040      * Helper function for heap sort.
1041      *
1042      * @param index Index of the element to sift down.
1043      * @param array Span array to be sorted.
1044      * @param size Current heap size.
1045      * @param priority Priorities of the spans
1046      * @param insertionOrder Insertion orders of the spans
1047      * @param <T> Span object type.
1048      */
1049     private final <T> void siftDown(int index, T[] array, int size, int[] priority,
1050                                     int[] insertionOrder) {
1051         T v = array[index];
1052         int prio = priority[index];
1053         int insertOrder = insertionOrder[index];
1054
1055         int left = 2 * index + 1;
1056         while (left < size) {
1057             if (left < size - 1 && compareSpans(left, left + 1, priority, insertionOrder) < 0) {
1058                 left++;
1059             }
1060             if (compareSpans(index, left, priority, insertionOrder) >= 0) {
1061                 break;
1062             }
1063             array[index] = array[left];
1064             priority[index] = priority[left];
1065             insertionOrder[index] = insertionOrder[left];
1066             index = left;
1067             left = 2 * index + 1;
1068         }
1069         array[index] = v;
1070         priority[index] = prio;
1071         insertionOrder[index] = insertOrder;
1072     }
1073
1074     /**
1075      * Compare two span elements in an array. Comparison is based first on the priority flag of
1076      * the span, and then the insertion order of the span.
1077      *
1078      * @param left Index of the element to compare.
1079      * @param right Index of the other element to compare.
1080      * @param priority Priorities of the spans
1081      * @param insertionOrder Insertion orders of the spans
1082      * @return
1083      */
1084     private final int compareSpans(int left, int right, int[] priority,
1085                                        int[] insertionOrder) {
1086         int priority1 = priority[left];
1087         int priority2 = priority[right];
1088         if (priority1 == priority2) {
1089             return Integer.compare(insertionOrder[left], insertionOrder[right]);
1090         }
1091         // since high priority has to be before a lower priority, the arguments to compare are
1092         // opposite of the insertion order check.
1093         return Integer.compare(priority2, priority1);
1094     }
1095
1096     /**
1097      * Return the next offset after <code>start</code> but less than or
1098      * equal to <code>limit</code> where a span of the specified type
1099      * begins or ends.
1100      */
1101     public int nextSpanTransition(int start, int limit, Class kind) {
1102         if (mSpanCount == 0) return limit;
1103         if (kind == null) {
1104             kind = Object.class;
1105         }
1106         return nextSpanTransitionRec(start, limit, kind, treeRoot());
1107     }
1108
1109     private int nextSpanTransitionRec(int start, int limit, Class kind, int i) {
1110         if ((i & 1) != 0) {
1111             // internal tree node
1112             int left = leftChild(i);
1113             if (resolveGap(mSpanMax[left]) > start) {
1114                 limit = nextSpanTransitionRec(start, limit, kind, left);
1115             }
1116         }
1117         if (i < mSpanCount) {
1118             int st = resolveGap(mSpanStarts[i]);
1119             int en = resolveGap(mSpanEnds[i]);
1120             if (st > start && st < limit && kind.isInstance(mSpans[i]))
1121                 limit = st;
1122             if (en > start && en < limit && kind.isInstance(mSpans[i]))
1123                 limit = en;
1124             if (st < limit && (i & 1) != 0) {
1125                 limit = nextSpanTransitionRec(start, limit, kind, rightChild(i));
1126             }
1127         }
1128
1129         return limit;
1130     }
1131
1132     /**
1133      * Return a new CharSequence containing a copy of the specified
1134      * range of this buffer, including the overlapping spans.
1135      */
1136     public CharSequence subSequence(int start, int end) {
1137         return new SpannableStringBuilder(this, start, end);
1138     }
1139
1140     /**
1141      * Copy the specified range of chars from this buffer into the
1142      * specified array, beginning at the specified offset.
1143      */
1144     public void getChars(int start, int end, char[] dest, int destoff) {
1145         checkRange("getChars", start, end);
1146
1147         if (end <= mGapStart) {
1148             System.arraycopy(mText, start, dest, destoff, end - start);
1149         } else if (start >= mGapStart) {
1150             System.arraycopy(mText, start + mGapLength, dest, destoff, end - start);
1151         } else {
1152             System.arraycopy(mText, start, dest, destoff, mGapStart - start);
1153             System.arraycopy(mText, mGapStart + mGapLength,
1154                     dest, destoff + (mGapStart - start),
1155                     end - mGapStart);
1156         }
1157     }
1158
1159     /**
1160      * Return a String containing a copy of the chars in this buffer.
1161      */
1162     @Override
1163     public String toString() {
1164         int len = length();
1165         char[] buf = new char[len];
1166
1167         getChars(0, len, buf, 0);
1168         return new String(buf);
1169     }
1170
1171     /**
1172      * Return a String containing a copy of the chars in this buffer, limited to the
1173      * [start, end[ range.
1174      * @hide
1175      */
1176     public String substring(int start, int end) {
1177         char[] buf = new char[end - start];
1178         getChars(start, end, buf, 0);
1179         return new String(buf);
1180     }
1181
1182     /**
1183      * Returns the depth of TextWatcher callbacks. Returns 0 when the object is not handling
1184      * TextWatchers. A return value greater than 1 implies that a TextWatcher caused a change that
1185      * recursively triggered a TextWatcher.
1186      */
1187     public int getTextWatcherDepth() {
1188         return mTextWatcherDepth;
1189     }
1190
1191     private void sendBeforeTextChanged(TextWatcher[] watchers, int start, int before, int after) {
1192         int n = watchers.length;
1193
1194         mTextWatcherDepth++;
1195         for (int i = 0; i < n; i++) {
1196             watchers[i].beforeTextChanged(this, start, before, after);
1197         }
1198         mTextWatcherDepth--;
1199     }
1200
1201     private void sendTextChanged(TextWatcher[] watchers, int start, int before, int after) {
1202         int n = watchers.length;
1203
1204         mTextWatcherDepth++;
1205         for (int i = 0; i < n; i++) {
1206             watchers[i].onTextChanged(this, start, before, after);
1207         }
1208         mTextWatcherDepth--;
1209     }
1210
1211     private void sendAfterTextChanged(TextWatcher[] watchers) {
1212         int n = watchers.length;
1213
1214         mTextWatcherDepth++;
1215         for (int i = 0; i < n; i++) {
1216             watchers[i].afterTextChanged(this);
1217         }
1218         mTextWatcherDepth--;
1219     }
1220
1221     private void sendSpanAdded(Object what, int start, int end) {
1222         SpanWatcher[] recip = getSpans(start, end, SpanWatcher.class);
1223         int n = recip.length;
1224
1225         for (int i = 0; i < n; i++) {
1226             recip[i].onSpanAdded(this, what, start, end);
1227         }
1228     }
1229
1230     private void sendSpanRemoved(Object what, int start, int end) {
1231         SpanWatcher[] recip = getSpans(start, end, SpanWatcher.class);
1232         int n = recip.length;
1233
1234         for (int i = 0; i < n; i++) {
1235             recip[i].onSpanRemoved(this, what, start, end);
1236         }
1237     }
1238
1239     private void sendSpanChanged(Object what, int oldStart, int oldEnd, int start, int end) {
1240         // The bounds of a possible SpanWatcher are guaranteed to be set before this method is
1241         // called, so that the order of the span does not affect this broadcast.
1242         SpanWatcher[] spanWatchers = getSpans(Math.min(oldStart, start),
1243                 Math.min(Math.max(oldEnd, end), length()), SpanWatcher.class);
1244         int n = spanWatchers.length;
1245         for (int i = 0; i < n; i++) {
1246             spanWatchers[i].onSpanChanged(this, what, oldStart, oldEnd, start, end);
1247         }
1248     }
1249
1250     private static String region(int start, int end) {
1251         return "(" + start + " ... " + end + ")";
1252     }
1253
1254     private void checkRange(final String operation, int start, int end) {
1255         if (end < start) {
1256             throw new IndexOutOfBoundsException(operation + " " +
1257                     region(start, end) + " has end before start");
1258         }
1259
1260         int len = length();
1261
1262         if (start > len || end > len) {
1263             throw new IndexOutOfBoundsException(operation + " " +
1264                     region(start, end) + " ends beyond length " + len);
1265         }
1266
1267         if (start < 0 || end < 0) {
1268             throw new IndexOutOfBoundsException(operation + " " +
1269                     region(start, end) + " starts before 0");
1270         }
1271     }
1272
1273     /*
1274     private boolean isprint(char c) { // XXX
1275         if (c >= ' ' && c <= '~')
1276             return true;
1277         else
1278             return false;
1279     }
1280
1281     private static final int startFlag(int flag) {
1282         return (flag >> 4) & 0x0F;
1283     }
1284
1285     private static final int endFlag(int flag) {
1286         return flag & 0x0F;
1287     }
1288
1289     public void dump() { // XXX
1290         for (int i = 0; i < mGapStart; i++) {
1291             System.out.print('|');
1292             System.out.print(' ');
1293             System.out.print(isprint(mText[i]) ? mText[i] : '.');
1294             System.out.print(' ');
1295         }
1296
1297         for (int i = mGapStart; i < mGapStart + mGapLength; i++) {
1298             System.out.print('|');
1299             System.out.print('(');
1300             System.out.print(isprint(mText[i]) ? mText[i] : '.');
1301             System.out.print(')');
1302         }
1303
1304         for (int i = mGapStart + mGapLength; i < mText.length; i++) {
1305             System.out.print('|');
1306             System.out.print(' ');
1307             System.out.print(isprint(mText[i]) ? mText[i] : '.');
1308             System.out.print(' ');
1309         }
1310
1311         System.out.print('\n');
1312
1313         for (int i = 0; i < mText.length + 1; i++) {
1314             int found = 0;
1315             int wfound = 0;
1316
1317             for (int j = 0; j < mSpanCount; j++) {
1318                 if (mSpanStarts[j] == i) {
1319                     found = 1;
1320                     wfound = j;
1321                     break;
1322                 }
1323
1324                 if (mSpanEnds[j] == i) {
1325                     found = 2;
1326                     wfound = j;
1327                     break;
1328                 }
1329             }
1330
1331             if (found == 1) {
1332                 if (startFlag(mSpanFlags[wfound]) == MARK)
1333                     System.out.print("(   ");
1334                 if (startFlag(mSpanFlags[wfound]) == PARAGRAPH)
1335                     System.out.print("<   ");
1336                 else
1337                     System.out.print("[   ");
1338             } else if (found == 2) {
1339                 if (endFlag(mSpanFlags[wfound]) == POINT)
1340                     System.out.print(")   ");
1341                 if (endFlag(mSpanFlags[wfound]) == PARAGRAPH)
1342                     System.out.print(">   ");
1343                 else
1344                     System.out.print("]   ");
1345             } else {
1346                 System.out.print("    ");
1347             }
1348         }
1349
1350         System.out.print("\n");
1351     }
1352     */
1353
1354     /**
1355      * Don't call this yourself -- exists for Canvas to use internally.
1356      * {@hide}
1357      */
1358     public void drawText(Canvas c, int start, int end, float x, float y, Paint p) {
1359         checkRange("drawText", start, end);
1360
1361         if (end <= mGapStart) {
1362             c.drawText(mText, start, end - start, x, y, p);
1363         } else if (start >= mGapStart) {
1364             c.drawText(mText, start + mGapLength, end - start, x, y, p);
1365         } else {
1366             char[] buf = TextUtils.obtain(end - start);
1367
1368             getChars(start, end, buf, 0);
1369             c.drawText(buf, 0, end - start, x, y, p);
1370             TextUtils.recycle(buf);
1371         }
1372     }
1373
1374
1375     /**
1376      * Don't call this yourself -- exists for Canvas to use internally.
1377      * {@hide}
1378      */
1379     public void drawTextRun(Canvas c, int start, int end, int contextStart, int contextEnd,
1380             float x, float y, boolean isRtl, Paint p) {
1381         checkRange("drawTextRun", start, end);
1382
1383         int contextLen = contextEnd - contextStart;
1384         int len = end - start;
1385         if (contextEnd <= mGapStart) {
1386             c.drawTextRun(mText, start, len, contextStart, contextLen, x, y, isRtl, p);
1387         } else if (contextStart >= mGapStart) {
1388             c.drawTextRun(mText, start + mGapLength, len, contextStart + mGapLength,
1389                     contextLen, x, y, isRtl, p);
1390         } else {
1391             char[] buf = TextUtils.obtain(contextLen);
1392             getChars(contextStart, contextEnd, buf, 0);
1393             c.drawTextRun(buf, start - contextStart, len, 0, contextLen, x, y, isRtl, p);
1394             TextUtils.recycle(buf);
1395         }
1396     }
1397
1398     /**
1399      * Don't call this yourself -- exists for Paint to use internally.
1400      * {@hide}
1401      */
1402     public float measureText(int start, int end, Paint p) {
1403         checkRange("measureText", start, end);
1404
1405         float ret;
1406
1407         if (end <= mGapStart) {
1408             ret = p.measureText(mText, start, end - start);
1409         } else if (start >= mGapStart) {
1410             ret = p.measureText(mText, start + mGapLength, end - start);
1411         } else {
1412             char[] buf = TextUtils.obtain(end - start);
1413
1414             getChars(start, end, buf, 0);
1415             ret = p.measureText(buf, 0, end - start);
1416             TextUtils.recycle(buf);
1417         }
1418
1419         return ret;
1420     }
1421
1422     /**
1423      * Don't call this yourself -- exists for Paint to use internally.
1424      * {@hide}
1425      */
1426     public int getTextWidths(int start, int end, float[] widths, Paint p) {
1427         checkRange("getTextWidths", start, end);
1428
1429         int ret;
1430
1431         if (end <= mGapStart) {
1432             ret = p.getTextWidths(mText, start, end - start, widths);
1433         } else if (start >= mGapStart) {
1434             ret = p.getTextWidths(mText, start + mGapLength, end - start, widths);
1435         } else {
1436             char[] buf = TextUtils.obtain(end - start);
1437
1438             getChars(start, end, buf, 0);
1439             ret = p.getTextWidths(buf, 0, end - start, widths);
1440             TextUtils.recycle(buf);
1441         }
1442
1443         return ret;
1444     }
1445
1446     /**
1447      * Don't call this yourself -- exists for Paint to use internally.
1448      * {@hide}
1449      */
1450     public float getTextRunAdvances(int start, int end, int contextStart, int contextEnd, boolean isRtl,
1451             float[] advances, int advancesPos, Paint p) {
1452
1453         float ret;
1454
1455         int contextLen = contextEnd - contextStart;
1456         int len = end - start;
1457
1458         if (end <= mGapStart) {
1459             ret = p.getTextRunAdvances(mText, start, len, contextStart, contextLen,
1460                     isRtl, advances, advancesPos);
1461         } else if (start >= mGapStart) {
1462             ret = p.getTextRunAdvances(mText, start + mGapLength, len,
1463                     contextStart + mGapLength, contextLen, isRtl, advances, advancesPos);
1464         } else {
1465             char[] buf = TextUtils.obtain(contextLen);
1466             getChars(contextStart, contextEnd, buf, 0);
1467             ret = p.getTextRunAdvances(buf, start - contextStart, len,
1468                     0, contextLen, isRtl, advances, advancesPos);
1469             TextUtils.recycle(buf);
1470         }
1471
1472         return ret;
1473     }
1474
1475     /**
1476      * Returns the next cursor position in the run.  This avoids placing the cursor between
1477      * surrogates, between characters that form conjuncts, between base characters and combining
1478      * marks, or within a reordering cluster.
1479      *
1480      * <p>The context is the shaping context for cursor movement, generally the bounds of the metric
1481      * span enclosing the cursor in the direction of movement.
1482      * <code>contextStart</code>, <code>contextEnd</code> and <code>offset</code> are relative to
1483      * the start of the string.</p>
1484      *
1485      * <p>If cursorOpt is CURSOR_AT and the offset is not a valid cursor position,
1486      * this returns -1.  Otherwise this will never return a value before contextStart or after
1487      * contextEnd.</p>
1488      *
1489      * @param contextStart the start index of the context
1490      * @param contextEnd the (non-inclusive) end index of the context
1491      * @param dir either DIRECTION_RTL or DIRECTION_LTR
1492      * @param offset the cursor position to move from
1493      * @param cursorOpt how to move the cursor, one of CURSOR_AFTER,
1494      * CURSOR_AT_OR_AFTER, CURSOR_BEFORE,
1495      * CURSOR_AT_OR_BEFORE, or CURSOR_AT
1496      * @param p the Paint object that is requesting this information
1497      * @return the offset of the next position, or -1
1498      * @deprecated This is an internal method, refrain from using it in your code
1499      */
1500     @Deprecated
1501     public int getTextRunCursor(int contextStart, int contextEnd, int dir, int offset,
1502             int cursorOpt, Paint p) {
1503
1504         int ret;
1505
1506         int contextLen = contextEnd - contextStart;
1507         if (contextEnd <= mGapStart) {
1508             ret = p.getTextRunCursor(mText, contextStart, contextLen,
1509                     dir, offset, cursorOpt);
1510         } else if (contextStart >= mGapStart) {
1511             ret = p.getTextRunCursor(mText, contextStart + mGapLength, contextLen,
1512                     dir, offset + mGapLength, cursorOpt) - mGapLength;
1513         } else {
1514             char[] buf = TextUtils.obtain(contextLen);
1515             getChars(contextStart, contextEnd, buf, 0);
1516             ret = p.getTextRunCursor(buf, 0, contextLen,
1517                     dir, offset - contextStart, cursorOpt) + contextStart;
1518             TextUtils.recycle(buf);
1519         }
1520
1521         return ret;
1522     }
1523
1524     // Documentation from interface
1525     public void setFilters(InputFilter[] filters) {
1526         if (filters == null) {
1527             throw new IllegalArgumentException();
1528         }
1529
1530         mFilters = filters;
1531     }
1532
1533     // Documentation from interface
1534     public InputFilter[] getFilters() {
1535         return mFilters;
1536     }
1537
1538     // Same as SpannableStringInternal
1539     @Override
1540     public boolean equals(Object o) {
1541         if (o instanceof Spanned &&
1542                 toString().equals(o.toString())) {
1543             Spanned other = (Spanned) o;
1544             // Check span data
1545             Object[] otherSpans = other.getSpans(0, other.length(), Object.class);
1546             if (mSpanCount == otherSpans.length) {
1547                 for (int i = 0; i < mSpanCount; ++i) {
1548                     Object thisSpan = mSpans[i];
1549                     Object otherSpan = otherSpans[i];
1550                     if (thisSpan == this) {
1551                         if (other != otherSpan ||
1552                                 getSpanStart(thisSpan) != other.getSpanStart(otherSpan) ||
1553                                 getSpanEnd(thisSpan) != other.getSpanEnd(otherSpan) ||
1554                                 getSpanFlags(thisSpan) != other.getSpanFlags(otherSpan)) {
1555                             return false;
1556                         }
1557                     } else if (!thisSpan.equals(otherSpan) ||
1558                             getSpanStart(thisSpan) != other.getSpanStart(otherSpan) ||
1559                             getSpanEnd(thisSpan) != other.getSpanEnd(otherSpan) ||
1560                             getSpanFlags(thisSpan) != other.getSpanFlags(otherSpan)) {
1561                         return false;
1562                     }
1563                 }
1564                 return true;
1565             }
1566         }
1567         return false;
1568     }
1569
1570     // Same as SpannableStringInternal
1571     @Override
1572     public int hashCode() {
1573         int hash = toString().hashCode();
1574         hash = hash * 31 + mSpanCount;
1575         for (int i = 0; i < mSpanCount; ++i) {
1576             Object span = mSpans[i];
1577             if (span != this) {
1578                 hash = hash * 31 + span.hashCode();
1579             }
1580             hash = hash * 31 + getSpanStart(span);
1581             hash = hash * 31 + getSpanEnd(span);
1582             hash = hash * 31 + getSpanFlags(span);
1583         }
1584         return hash;
1585     }
1586
1587     // Primitives for treating span list as binary tree
1588
1589     // The spans (along with start and end offsets and flags) are stored in linear arrays sorted
1590     // by start offset. For fast searching, there is a binary search structure imposed over these
1591     // arrays. This structure is inorder traversal of a perfect binary tree, a slightly unusual
1592     // but advantageous approach.
1593
1594     // The value-containing nodes are indexed 0 <= i < n (where n = mSpanCount), thus preserving
1595     // logic that accesses the values as a contiguous array. Other balanced binary tree approaches
1596     // (such as a complete binary tree) would require some shuffling of node indices.
1597
1598     // Basic properties of this structure: For a perfect binary tree of height m:
1599     // The tree has 2^(m+1) - 1 total nodes.
1600     // The root of the tree has index 2^m - 1.
1601     // All leaf nodes have even index, all interior nodes odd.
1602     // The height of a node of index i is the number of trailing ones in i's binary representation.
1603     // The left child of a node i of height h is i - 2^(h - 1).
1604     // The right child of a node i of height h is i + 2^(h - 1).
1605
1606     // Note that for arbitrary n, interior nodes of this tree may be >= n. Thus, the general
1607     // structure of a recursive traversal of node i is:
1608     // * traverse left child if i is an interior node
1609     // * process i if i < n
1610     // * traverse right child if i is an interior node and i < n
1611
1612     private int treeRoot() {
1613         return Integer.highestOneBit(mSpanCount) - 1;
1614     }
1615
1616     // (i+1) & ~i is equal to 2^(the number of trailing ones in i)
1617     private static int leftChild(int i) {
1618         return i - (((i + 1) & ~i) >> 1);
1619     }
1620
1621     private static int rightChild(int i) {
1622         return i + (((i + 1) & ~i) >> 1);
1623     }
1624
1625     // The span arrays are also augmented by an mSpanMax[] array that represents an interval tree
1626     // over the binary tree structure described above. For each node, the mSpanMax[] array contains
1627     // the maximum value of mSpanEnds of that node and its descendants. Thus, traversals can
1628     // easily reject subtrees that contain no spans overlapping the area of interest.
1629
1630     // Note that mSpanMax[] also has a valid valuefor interior nodes of index >= n, but which have
1631     // descendants of index < n. In these cases, it simply represents the maximum span end of its
1632     // descendants. This is a consequence of the perfect binary tree structure.
1633     private int calcMax(int i) {
1634         int max = 0;
1635         if ((i & 1) != 0) {
1636             // internal tree node
1637             max = calcMax(leftChild(i));
1638         }
1639         if (i < mSpanCount) {
1640             max = Math.max(max, mSpanEnds[i]);
1641             if ((i & 1) != 0) {
1642                 max = Math.max(max, calcMax(rightChild(i)));
1643             }
1644         }
1645         mSpanMax[i] = max;
1646         return max;
1647     }
1648
1649     // restores binary interval tree invariants after any mutation of span structure
1650     private void restoreInvariants() {
1651         if (mSpanCount == 0) return;
1652
1653         // invariant 1: span starts are nondecreasing
1654
1655         // This is a simple insertion sort because we expect it to be mostly sorted.
1656         for (int i = 1; i < mSpanCount; i++) {
1657             if (mSpanStarts[i] < mSpanStarts[i - 1]) {
1658                 Object span = mSpans[i];
1659                 int start = mSpanStarts[i];
1660                 int end = mSpanEnds[i];
1661                 int flags = mSpanFlags[i];
1662                 int insertionOrder = mSpanOrder[i];
1663                 int j = i;
1664                 do {
1665                     mSpans[j] = mSpans[j - 1];
1666                     mSpanStarts[j] = mSpanStarts[j - 1];
1667                     mSpanEnds[j] = mSpanEnds[j - 1];
1668                     mSpanFlags[j] = mSpanFlags[j - 1];
1669                     mSpanOrder[j] = mSpanOrder[j - 1];
1670                     j--;
1671                 } while (j > 0 && start < mSpanStarts[j - 1]);
1672                 mSpans[j] = span;
1673                 mSpanStarts[j] = start;
1674                 mSpanEnds[j] = end;
1675                 mSpanFlags[j] = flags;
1676                 mSpanOrder[j] = insertionOrder;
1677                 invalidateIndex(j);
1678             }
1679         }
1680
1681         // invariant 2: max is max span end for each node and its descendants
1682         calcMax(treeRoot());
1683
1684         // invariant 3: mIndexOfSpan maps spans back to indices
1685         if (mIndexOfSpan == null) {
1686             mIndexOfSpan = new IdentityHashMap<Object, Integer>();
1687         }
1688         for (int i = mLowWaterMark; i < mSpanCount; i++) {
1689             Integer existing = mIndexOfSpan.get(mSpans[i]);
1690             if (existing == null || existing != i) {
1691                 mIndexOfSpan.put(mSpans[i], i);
1692             }
1693         }
1694         mLowWaterMark = Integer.MAX_VALUE;
1695     }
1696
1697     // Call this on any update to mSpans[], so that mIndexOfSpan can be updated
1698     private void invalidateIndex(int i) {
1699         mLowWaterMark = Math.min(i, mLowWaterMark);
1700     }
1701
1702     private static final InputFilter[] NO_FILTERS = new InputFilter[0];
1703     private InputFilter[] mFilters = NO_FILTERS;
1704
1705     private char[] mText;
1706     private int mGapStart;
1707     private int mGapLength;
1708
1709     private Object[] mSpans;
1710     private int[] mSpanStarts;
1711     private int[] mSpanEnds;
1712     private int[] mSpanMax;  // see calcMax() for an explanation of what this array stores
1713     private int[] mSpanFlags;
1714     private int[] mSpanOrder;  // store the order of span insertion
1715     private int mSpanInsertCount;  // counter for the span insertion
1716     private int[] mPrioSortBuffer;  // buffer used to sort getSpans result
1717     private int[] mOrderSortBuffer;  // buffer used to sort getSpans result
1718
1719     private int mSpanCount;
1720     private IdentityHashMap<Object, Integer> mIndexOfSpan;
1721     private int mLowWaterMark;  // indices below this have not been touched
1722
1723     // TextWatcher callbacks may trigger changes that trigger more callbacks. This keeps track of
1724     // how deep the callbacks go.
1725     private int mTextWatcherDepth;
1726
1727     // TODO These value are tightly related to the public SPAN_MARK/POINT values in {@link Spanned}
1728     private static final int MARK = 1;
1729     private static final int POINT = 2;
1730     private static final int PARAGRAPH = 3;
1731
1732     private static final int START_MASK = 0xF0;
1733     private static final int END_MASK = 0x0F;
1734     private static final int START_SHIFT = 4;
1735
1736     // These bits are not (currently) used by SPANNED flags
1737     private static final int SPAN_ADDED = 0x800;
1738     private static final int SPAN_START_AT_START = 0x1000;
1739     private static final int SPAN_START_AT_END = 0x2000;
1740     private static final int SPAN_END_AT_START = 0x4000;
1741     private static final int SPAN_END_AT_END = 0x8000;
1742     private static final int SPAN_START_END_MASK = 0xF000;
1743 }