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