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