1/* GENERATED SOURCE. DO NOT MODIFY. */ 2// © 2017 and later: Unicode, Inc. and others. 3// License & terms of use: http://www.unicode.org/copyright.html#License 4package android.icu.text; 5 6import java.nio.BufferOverflowException; 7import java.util.Arrays; 8 9/** 10 * Records lengths of string edits but not replacement text. 11 * Supports replacements, insertions, deletions in linear progression. 12 * Does not support moving/reordering of text. 13 * 14 * @hide Only a subset of ICU is exposed in Android 15 * @hide draft / provisional / internal are hidden on Android 16 */ 17public final class Edits { 18 // 0000uuuuuuuuuuuu records u+1 unchanged text units. 19 private static final int MAX_UNCHANGED_LENGTH = 0x1000; 20 private static final int MAX_UNCHANGED = MAX_UNCHANGED_LENGTH - 1; 21 22 // 0mmmnnnccccccccc with m=1..6 records ccc+1 replacements of m:n text units. 23 private static final int MAX_SHORT_CHANGE_OLD_LENGTH = 6; 24 private static final int MAX_SHORT_CHANGE_NEW_LENGTH = 7; 25 private static final int SHORT_CHANGE_NUM_MASK = 0x1ff; 26 private static final int MAX_SHORT_CHANGE = 0x6fff; 27 28 // 0111mmmmmmnnnnnn records a replacement of m text units with n. 29 // m or n = 61: actual length follows in the next edits array unit. 30 // m or n = 62..63: actual length follows in the next two edits array units. 31 // Bit 30 of the actual length is in the head unit. 32 // Trailing units have bit 15 set. 33 private static final int LENGTH_IN_1TRAIL = 61; 34 private static final int LENGTH_IN_2TRAIL = 62; 35 36 private static final int STACK_CAPACITY = 100; 37 private char[] array; 38 private int length; 39 private int delta; 40 private int numChanges; 41 42 /** 43 * Constructs an empty object. 44 * @hide draft / provisional / internal are hidden on Android 45 */ 46 public Edits() { 47 array = new char[STACK_CAPACITY]; 48 } 49 50 /** 51 * Resets the data but may not release memory. 52 * @hide draft / provisional / internal are hidden on Android 53 */ 54 public void reset() { 55 length = delta = numChanges = 0; 56 } 57 58 private void setLastUnit(int last) { 59 array[length - 1] = (char)last; 60 } 61 private int lastUnit() { 62 return length > 0 ? array[length - 1] : 0xffff; 63 } 64 65 /** 66 * Adds a record for an unchanged segment of text. 67 * Normally called from inside ICU string transformation functions, not user code. 68 * @hide draft / provisional / internal are hidden on Android 69 */ 70 public void addUnchanged(int unchangedLength) { 71 if(unchangedLength < 0) { 72 throw new IllegalArgumentException( 73 "addUnchanged(" + unchangedLength + "): length must not be negative"); 74 } 75 // Merge into previous unchanged-text record, if any. 76 int last = lastUnit(); 77 if(last < MAX_UNCHANGED) { 78 int remaining = MAX_UNCHANGED - last; 79 if (remaining >= unchangedLength) { 80 setLastUnit(last + unchangedLength); 81 return; 82 } 83 setLastUnit(MAX_UNCHANGED); 84 unchangedLength -= remaining; 85 } 86 // Split large lengths into multiple units. 87 while(unchangedLength >= MAX_UNCHANGED_LENGTH) { 88 append(MAX_UNCHANGED); 89 unchangedLength -= MAX_UNCHANGED_LENGTH; 90 } 91 // Write a small (remaining) length. 92 if(unchangedLength > 0) { 93 append(unchangedLength - 1); 94 } 95 } 96 97 /** 98 * Adds a record for a text replacement/insertion/deletion. 99 * Normally called from inside ICU string transformation functions, not user code. 100 * @hide draft / provisional / internal are hidden on Android 101 */ 102 public void addReplace(int oldLength, int newLength) { 103 if(oldLength < 0 || newLength < 0) { 104 throw new IllegalArgumentException( 105 "addReplace(" + oldLength + ", " + newLength + 106 "): both lengths must be non-negative"); 107 } 108 if (oldLength == 0 && newLength == 0) { 109 return; 110 } 111 ++numChanges; 112 int newDelta = newLength - oldLength; 113 if (newDelta != 0) { 114 if ((newDelta > 0 && delta >= 0 && newDelta > (Integer.MAX_VALUE - delta)) || 115 (newDelta < 0 && delta < 0 && newDelta < (Integer.MIN_VALUE - delta))) { 116 // Integer overflow or underflow. 117 throw new IndexOutOfBoundsException(); 118 } 119 delta += newDelta; 120 } 121 122 if(0 < oldLength && oldLength <= MAX_SHORT_CHANGE_OLD_LENGTH && 123 newLength <= MAX_SHORT_CHANGE_NEW_LENGTH) { 124 // Merge into previous same-lengths short-replacement record, if any. 125 int u = (oldLength << 12) | (newLength << 9); 126 int last = lastUnit(); 127 if(MAX_UNCHANGED < last && last < MAX_SHORT_CHANGE && 128 (last & ~SHORT_CHANGE_NUM_MASK) == u && 129 (last & SHORT_CHANGE_NUM_MASK) < SHORT_CHANGE_NUM_MASK) { 130 setLastUnit(last + 1); 131 return; 132 } 133 append(u); 134 return; 135 } 136 137 int head = 0x7000; 138 if (oldLength < LENGTH_IN_1TRAIL && newLength < LENGTH_IN_1TRAIL) { 139 head |= oldLength << 6; 140 head |= newLength; 141 append(head); 142 } else if ((array.length - length) >= 5 || growArray()) { 143 int limit = length + 1; 144 if(oldLength < LENGTH_IN_1TRAIL) { 145 head |= oldLength << 6; 146 } else if(oldLength <= 0x7fff) { 147 head |= LENGTH_IN_1TRAIL << 6; 148 array[limit++] = (char)(0x8000 | oldLength); 149 } else { 150 head |= (LENGTH_IN_2TRAIL + (oldLength >> 30)) << 6; 151 array[limit++] = (char)(0x8000 | (oldLength >> 15)); 152 array[limit++] = (char)(0x8000 | oldLength); 153 } 154 if(newLength < LENGTH_IN_1TRAIL) { 155 head |= newLength; 156 } else if(newLength <= 0x7fff) { 157 head |= LENGTH_IN_1TRAIL; 158 array[limit++] = (char)(0x8000 | newLength); 159 } else { 160 head |= LENGTH_IN_2TRAIL + (newLength >> 30); 161 array[limit++] = (char)(0x8000 | (newLength >> 15)); 162 array[limit++] = (char)(0x8000 | newLength); 163 } 164 array[length] = (char)head; 165 length = limit; 166 } 167 } 168 169 private void append(int r) { 170 if(length < array.length || growArray()) { 171 array[length++] = (char)r; 172 } 173 } 174 175 private boolean growArray() { 176 int newCapacity; 177 if (array.length == STACK_CAPACITY) { 178 newCapacity = 2000; 179 } else if (array.length == Integer.MAX_VALUE) { 180 throw new BufferOverflowException(); 181 } else if (array.length >= (Integer.MAX_VALUE / 2)) { 182 newCapacity = Integer.MAX_VALUE; 183 } else { 184 newCapacity = 2 * array.length; 185 } 186 // Grow by at least 5 units so that a maximal change record will fit. 187 if ((newCapacity - array.length) < 5) { 188 throw new BufferOverflowException(); 189 } 190 array = Arrays.copyOf(array, newCapacity); 191 return true; 192 } 193 194 /** 195 * How much longer is the new text compared with the old text? 196 * @return new length minus old length 197 * @hide draft / provisional / internal are hidden on Android 198 */ 199 public int lengthDelta() { return delta; } 200 /** 201 * @return true if there are any change edits 202 * @hide draft / provisional / internal are hidden on Android 203 */ 204 public boolean hasChanges() { return numChanges != 0; } 205 206 /** 207 * @return the number of change edits 208 * @hide draft / provisional / internal are hidden on Android 209 */ 210 public int numberOfChanges() { return numChanges; } 211 212 /** 213 * Access to the list of edits. 214 * @see #getCoarseIterator 215 * @see #getFineIterator 216 * @hide draft / provisional / internal are hidden on Android 217 */ 218 public static final class Iterator { 219 private final char[] array; 220 private int index; 221 private final int length; 222 /** 223 * 0 if we are not within compressed equal-length changes. 224 * Otherwise the number of remaining changes, including the current one. 225 */ 226 private int remaining; 227 private final boolean onlyChanges_, coarse; 228 229 private int dir; // iteration direction: back(<0), initial(0), forward(>0) 230 private boolean changed; 231 private int oldLength_, newLength_; 232 private int srcIndex, replIndex, destIndex; 233 234 private Iterator(char[] a, int len, boolean oc, boolean crs) { 235 array = a; 236 length = len; 237 onlyChanges_ = oc; 238 coarse = crs; 239 } 240 241 private int readLength(int head) { 242 if (head < LENGTH_IN_1TRAIL) { 243 return head; 244 } else if (head < LENGTH_IN_2TRAIL) { 245 assert(index < length); 246 assert(array[index] >= 0x8000); 247 return array[index++] & 0x7fff; 248 } else { 249 assert((index + 2) <= length); 250 assert(array[index] >= 0x8000); 251 assert(array[index + 1] >= 0x8000); 252 int len = ((head & 1) << 30) | 253 ((array[index] & 0x7fff) << 15) | 254 (array[index + 1] & 0x7fff); 255 index += 2; 256 return len; 257 } 258 } 259 260 private void updateNextIndexes() { 261 srcIndex += oldLength_; 262 if (changed) { 263 replIndex += newLength_; 264 } 265 destIndex += newLength_; 266 } 267 268 private void updatePreviousIndexes() { 269 srcIndex -= oldLength_; 270 if (changed) { 271 replIndex -= newLength_; 272 } 273 destIndex -= newLength_; 274 } 275 276 private boolean noNext() { 277 // No change before or beyond the string. 278 dir = 0; 279 changed = false; 280 oldLength_ = newLength_ = 0; 281 return false; 282 } 283 284 /** 285 * Advances to the next edit. 286 * @return true if there is another edit 287 * @hide draft / provisional / internal are hidden on Android 288 */ 289 public boolean next() { 290 return next(onlyChanges_); 291 } 292 293 private boolean next(boolean onlyChanges) { 294 // Forward iteration: Update the string indexes to the limit of the current span, 295 // and post-increment-read array units to assemble a new span. 296 // Leaves the array index one after the last unit of that span. 297 if (dir > 0) { 298 updateNextIndexes(); 299 } else { 300 if (dir < 0) { 301 // Turn around from previous() to next(). 302 // Post-increment-read the same span again. 303 if (remaining > 0) { 304 // Fine-grained iterator: 305 // Stay on the current one of a sequence of compressed changes. 306 ++index; // next() rests on the index after the sequence unit. 307 dir = 1; 308 return true; 309 } 310 } 311 dir = 1; 312 } 313 if (remaining >= 1) { 314 // Fine-grained iterator: Continue a sequence of compressed changes. 315 if (remaining > 1) { 316 --remaining; 317 return true; 318 } 319 remaining = 0; 320 } 321 if (index >= length) { 322 return noNext(); 323 } 324 int u = array[index++]; 325 if (u <= MAX_UNCHANGED) { 326 // Combine adjacent unchanged ranges. 327 changed = false; 328 oldLength_ = u + 1; 329 while (index < length && (u = array[index]) <= MAX_UNCHANGED) { 330 ++index; 331 oldLength_ += u + 1; 332 } 333 newLength_ = oldLength_; 334 if (onlyChanges) { 335 updateNextIndexes(); 336 if (index >= length) { 337 return noNext(); 338 } 339 // already fetched u > MAX_UNCHANGED at index 340 ++index; 341 } else { 342 return true; 343 } 344 } 345 changed = true; 346 if (u <= MAX_SHORT_CHANGE) { 347 int oldLen = u >> 12; 348 int newLen = (u >> 9) & MAX_SHORT_CHANGE_NEW_LENGTH; 349 int num = (u & SHORT_CHANGE_NUM_MASK) + 1; 350 if (coarse) { 351 oldLength_ = num * oldLen; 352 newLength_ = num * newLen; 353 } else { 354 // Split a sequence of changes that was compressed into one unit. 355 oldLength_ = oldLen; 356 newLength_ = newLen; 357 if (num > 1) { 358 remaining = num; // This is the first of two or more changes. 359 } 360 return true; 361 } 362 } else { 363 assert(u <= 0x7fff); 364 oldLength_ = readLength((u >> 6) & 0x3f); 365 newLength_ = readLength(u & 0x3f); 366 if (!coarse) { 367 return true; 368 } 369 } 370 // Combine adjacent changes. 371 while (index < length && (u = array[index]) > MAX_UNCHANGED) { 372 ++index; 373 if (u <= MAX_SHORT_CHANGE) { 374 int num = (u & SHORT_CHANGE_NUM_MASK) + 1; 375 oldLength_ += (u >> 12) * num; 376 newLength_ += ((u >> 9) & MAX_SHORT_CHANGE_NEW_LENGTH) * num; 377 } else { 378 assert(u <= 0x7fff); 379 oldLength_ += readLength((u >> 6) & 0x3f); 380 newLength_ += readLength(u & 0x3f); 381 } 382 } 383 return true; 384 } 385 386 private boolean previous() { 387 // Backward iteration: Pre-decrement-read array units to assemble a new span, 388 // then update the string indexes to the start of that span. 389 // Leaves the array index on the head unit of that span. 390 if (dir >= 0) { 391 if (dir > 0) { 392 // Turn around from next() to previous(). 393 // Set the string indexes to the span limit and 394 // pre-decrement-read the same span again. 395 if (remaining > 0) { 396 // Fine-grained iterator: 397 // Stay on the current one of a sequence of compressed changes. 398 --index; // previous() rests on the sequence unit. 399 dir = -1; 400 return true; 401 } 402 updateNextIndexes(); 403 } 404 dir = -1; 405 } 406 if (remaining > 0) { 407 // Fine-grained iterator: Continue a sequence of compressed changes. 408 int u = array[index]; 409 assert(MAX_UNCHANGED < u && u <= MAX_SHORT_CHANGE); 410 if (remaining <= (u & SHORT_CHANGE_NUM_MASK)) { 411 ++remaining; 412 updatePreviousIndexes(); 413 return true; 414 } 415 remaining = 0; 416 } 417 if (index <= 0) { 418 return noNext(); 419 } 420 int u = array[--index]; 421 if (u <= MAX_UNCHANGED) { 422 // Combine adjacent unchanged ranges. 423 changed = false; 424 oldLength_ = u + 1; 425 while (index > 0 && (u = array[index - 1]) <= MAX_UNCHANGED) { 426 --index; 427 oldLength_ += u + 1; 428 } 429 newLength_ = oldLength_; 430 // No need to handle onlyChanges as long as previous() is called only from findIndex(). 431 updatePreviousIndexes(); 432 return true; 433 } 434 changed = true; 435 if (u <= MAX_SHORT_CHANGE) { 436 int oldLen = u >> 12; 437 int newLen = (u >> 9) & MAX_SHORT_CHANGE_NEW_LENGTH; 438 int num = (u & SHORT_CHANGE_NUM_MASK) + 1; 439 if (coarse) { 440 oldLength_ = num * oldLen; 441 newLength_ = num * newLen; 442 } else { 443 // Split a sequence of changes that was compressed into one unit. 444 oldLength_ = oldLen; 445 newLength_ = newLen; 446 if (num > 1) { 447 remaining = 1; // This is the last of two or more changes. 448 } 449 updatePreviousIndexes(); 450 return true; 451 } 452 } else { 453 if (u <= 0x7fff) { 454 // The change is encoded in u alone. 455 oldLength_ = readLength((u >> 6) & 0x3f); 456 newLength_ = readLength(u & 0x3f); 457 } else { 458 // Back up to the head of the change, read the lengths, 459 // and reset the index to the head again. 460 assert(index > 0); 461 while ((u = array[--index]) > 0x7fff) {} 462 assert(u > MAX_SHORT_CHANGE); 463 int headIndex = index++; 464 oldLength_ = readLength((u >> 6) & 0x3f); 465 newLength_ = readLength(u & 0x3f); 466 index = headIndex; 467 } 468 if (!coarse) { 469 updatePreviousIndexes(); 470 return true; 471 } 472 } 473 // Combine adjacent changes. 474 while (index > 0 && (u = array[index - 1]) > MAX_UNCHANGED) { 475 --index; 476 if (u <= MAX_SHORT_CHANGE) { 477 int num = (u & SHORT_CHANGE_NUM_MASK) + 1; 478 oldLength_ += (u >> 12) * num; 479 newLength_ += ((u >> 9) & MAX_SHORT_CHANGE_NEW_LENGTH) * num; 480 } else if (u <= 0x7fff) { 481 // Read the lengths, and reset the index to the head again. 482 int headIndex = index++; 483 oldLength_ += readLength((u >> 6) & 0x3f); 484 newLength_ += readLength(u & 0x3f); 485 index = headIndex; 486 } 487 } 488 updatePreviousIndexes(); 489 return true; 490 } 491 492 /** 493 * Finds the edit that contains the source index. 494 * The source index may be found in a non-change 495 * even if normal iteration would skip non-changes. 496 * Normal iteration can continue from a found edit. 497 * 498 * <p>The iterator state before this search logically does not matter. 499 * (It may affect the performance of the search.) 500 * 501 * <p>The iterator state after this search is undefined 502 * if the source index is out of bounds for the source string. 503 * 504 * @param i source index 505 * @return true if the edit for the source index was found 506 * @hide draft / provisional / internal are hidden on Android 507 */ 508 public boolean findSourceIndex(int i) { 509 return findIndex(i, true) == 0; 510 } 511 512 /** 513 * Finds the edit that contains the destination index. 514 * The destination index may be found in a non-change 515 * even if normal iteration would skip non-changes. 516 * Normal iteration can continue from a found edit. 517 * 518 * <p>The iterator state before this search logically does not matter. 519 * (It may affect the performance of the search.) 520 * 521 * <p>The iterator state after this search is undefined 522 * if the source index is out of bounds for the source string. 523 * 524 * @param i destination index 525 * @return true if the edit for the destination index was found 526 * @hide draft / provisional / internal are hidden on Android 527 */ 528 public boolean findDestinationIndex(int i) { 529 return findIndex(i, false) == 0; 530 } 531 532 /** @return -1: error or i<0; 0: found; 1: i>=string length */ 533 private int findIndex(int i, boolean findSource) { 534 if (i < 0) { return -1; } 535 int spanStart, spanLength; 536 if (findSource) { // find source index 537 spanStart = srcIndex; 538 spanLength = oldLength_; 539 } else { // find destination index 540 spanStart = destIndex; 541 spanLength = newLength_; 542 } 543 if (i < spanStart) { 544 if (i >= (spanStart / 2)) { 545 // Search backwards. 546 for (;;) { 547 boolean hasPrevious = previous(); 548 assert(hasPrevious); // because i>=0 and the first span starts at 0 549 spanStart = findSource ? srcIndex : destIndex; 550 if (i >= spanStart) { 551 // The index is in the current span. 552 return 0; 553 } 554 if (remaining > 0) { 555 // Is the index in one of the remaining compressed edits? 556 // spanStart is the start of the current span, first of the remaining ones. 557 spanLength = findSource ? oldLength_ : newLength_; 558 int u = array[index]; 559 assert(MAX_UNCHANGED < u && u <= MAX_SHORT_CHANGE); 560 int num = (u & SHORT_CHANGE_NUM_MASK) + 1 - remaining; 561 int len = num * spanLength; 562 if (i >= (spanStart - len)) { 563 int n = ((spanStart - i - 1) / spanLength) + 1; 564 // 1 <= n <= num 565 srcIndex -= n * oldLength_; 566 replIndex -= n * newLength_; 567 destIndex -= n * newLength_; 568 remaining += n; 569 return 0; 570 } 571 // Skip all of these edits at once. 572 srcIndex -= num * oldLength_; 573 replIndex -= num * newLength_; 574 destIndex -= num * newLength_; 575 remaining = 0; 576 } 577 } 578 } 579 // Reset the iterator to the start. 580 dir = 0; 581 index = remaining = oldLength_ = newLength_ = srcIndex = replIndex = destIndex = 0; 582 } else if (i < (spanStart + spanLength)) { 583 // The index is in the current span. 584 return 0; 585 } 586 while (next(false)) { 587 if (findSource) { 588 spanStart = srcIndex; 589 spanLength = oldLength_; 590 } else { 591 spanStart = destIndex; 592 spanLength = newLength_; 593 } 594 if (i < (spanStart + spanLength)) { 595 // The index is in the current span. 596 return 0; 597 } 598 if (remaining > 1) { 599 // Is the index in one of the remaining compressed edits? 600 // spanStart is the start of the current span, first of the remaining ones. 601 int len = remaining * spanLength; 602 if (i < (spanStart + len)) { 603 int n = (i - spanStart) / spanLength; // 1 <= n <= remaining - 1 604 srcIndex += n * oldLength_; 605 replIndex += n * newLength_; 606 destIndex += n * newLength_; 607 remaining -= n; 608 return 0; 609 } 610 // Make next() skip all of these edits at once. 611 oldLength_ *= remaining; 612 newLength_ *= remaining; 613 remaining = 0; 614 } 615 } 616 return 1; 617 } 618 619 /** 620 * Returns the destination index corresponding to the given source index. 621 * If the source index is inside a change edit (not at its start), 622 * then the destination index at the end of that edit is returned, 623 * since there is no information about index mapping inside a change edit. 624 * 625 * <p>(This means that indexes to the start and middle of an edit, 626 * for example around a grapheme cluster, are mapped to indexes 627 * encompassing the entire edit. 628 * The alternative, mapping an interior index to the start, 629 * would map such an interval to an empty one.) 630 * 631 * <p>This operation will usually but not always modify this object. 632 * The iterator state after this search is undefined. 633 * 634 * @param i source index 635 * @return destination index; undefined if i is not 0..string length 636 * @hide draft / provisional / internal are hidden on Android 637 */ 638 public int destinationIndexFromSourceIndex(int i) { 639 int where = findIndex(i, true); 640 if (where < 0) { 641 // Error or before the string. 642 return 0; 643 } 644 if (where > 0 || i == srcIndex) { 645 // At or after string length, or at start of the found span. 646 return destIndex; 647 } 648 if (changed) { 649 // In a change span, map to its end. 650 return destIndex + newLength_; 651 } else { 652 // In an unchanged span, offset 1:1 within it. 653 return destIndex + (i - srcIndex); 654 } 655 } 656 657 /** 658 * Returns the source index corresponding to the given destination index. 659 * If the destination index is inside a change edit (not at its start), 660 * then the source index at the end of that edit is returned, 661 * since there is no information about index mapping inside a change edit. 662 * 663 * <p>(This means that indexes to the start and middle of an edit, 664 * for example around a grapheme cluster, are mapped to indexes 665 * encompassing the entire edit. 666 * The alternative, mapping an interior index to the start, 667 * would map such an interval to an empty one.) 668 * 669 * <p>This operation will usually but not always modify this object. 670 * The iterator state after this search is undefined. 671 * 672 * @param i destination index 673 * @return source index; undefined if i is not 0..string length 674 * @hide draft / provisional / internal are hidden on Android 675 */ 676 public int sourceIndexFromDestinationIndex(int i) { 677 int where = findIndex(i, false); 678 if (where < 0) { 679 // Error or before the string. 680 return 0; 681 } 682 if (where > 0 || i == destIndex) { 683 // At or after string length, or at start of the found span. 684 return srcIndex; 685 } 686 if (changed) { 687 // In a change span, map to its end. 688 return srcIndex + oldLength_; 689 } else { 690 // In an unchanged span, offset within it. 691 return srcIndex + (i - destIndex); 692 } 693 } 694 695 /** 696 * @return true if this edit replaces oldLength() units with newLength() different ones. 697 * false if oldLength units remain unchanged. 698 * @hide draft / provisional / internal are hidden on Android 699 */ 700 public boolean hasChange() { return changed; } 701 /** 702 * @return the number of units in the original string which are replaced or remain unchanged. 703 * @hide draft / provisional / internal are hidden on Android 704 */ 705 public int oldLength() { return oldLength_; } 706 /** 707 * @return the number of units in the modified string, if hasChange() is true. 708 * Same as oldLength if hasChange() is false. 709 * @hide draft / provisional / internal are hidden on Android 710 */ 711 public int newLength() { return newLength_; } 712 713 /** 714 * @return the current index into the source string 715 * @hide draft / provisional / internal are hidden on Android 716 */ 717 public int sourceIndex() { return srcIndex; } 718 /** 719 * @return the current index into the replacement-characters-only string, 720 * not counting unchanged spans 721 * @hide draft / provisional / internal are hidden on Android 722 */ 723 public int replacementIndex() { return replIndex; } 724 /** 725 * @return the current index into the full destination string 726 * @hide draft / provisional / internal are hidden on Android 727 */ 728 public int destinationIndex() { return destIndex; } 729 }; 730 731 /** 732 * Returns an Iterator for coarse-grained changes for simple string updates. 733 * Skips non-changes. 734 * @return an Iterator that merges adjacent changes. 735 * @hide draft / provisional / internal are hidden on Android 736 */ 737 public Iterator getCoarseChangesIterator() { 738 return new Iterator(array, length, true, true); 739 } 740 741 /** 742 * Returns an Iterator for coarse-grained changes and non-changes for simple string updates. 743 * @return an Iterator that merges adjacent changes. 744 * @hide draft / provisional / internal are hidden on Android 745 */ 746 public Iterator getCoarseIterator() { 747 return new Iterator(array, length, false, true); 748 } 749 750 /** 751 * Returns an Iterator for fine-grained changes for modifying styled text. 752 * Skips non-changes. 753 * @return an Iterator that separates adjacent changes. 754 * @hide draft / provisional / internal are hidden on Android 755 */ 756 public Iterator getFineChangesIterator() { 757 return new Iterator(array, length, true, false); 758 } 759 760 /** 761 * Returns an Iterator for fine-grained changes and non-changes for modifying styled text. 762 * @return an Iterator that separates adjacent changes. 763 * @hide draft / provisional / internal are hidden on Android 764 */ 765 public Iterator getFineIterator() { 766 return new Iterator(array, length, false, false); 767 } 768 769 /** 770 * Merges the two input Edits and appends the result to this object. 771 * 772 * <p>Consider two string transformations (for example, normalization and case mapping) 773 * where each records Edits in addition to writing an output string.<br> 774 * Edits ab reflect how substrings of input string a 775 * map to substrings of intermediate string b.<br> 776 * Edits bc reflect how substrings of intermediate string b 777 * map to substrings of output string c.<br> 778 * This function merges ab and bc such that the additional edits 779 * recorded in this object reflect how substrings of input string a 780 * map to substrings of output string c. 781 * 782 * <p>If unrelated Edits are passed in where the output string of the first 783 * has a different length than the input string of the second, 784 * then an IllegalArgumentException is thrown. 785 * 786 * @param ab reflects how substrings of input string a 787 * map to substrings of intermediate string b. 788 * @param bc reflects how substrings of intermediate string b 789 * map to substrings of output string c. 790 * @return this, with the merged edits appended 791 * @hide draft / provisional / internal are hidden on Android 792 */ 793 public Edits mergeAndAppend(Edits ab, Edits bc) { 794 // Picture string a --(Edits ab)--> string b --(Edits bc)--> string c. 795 // Parallel iteration over both Edits. 796 Iterator abIter = ab.getFineIterator(); 797 Iterator bcIter = bc.getFineIterator(); 798 boolean abHasNext = true, bcHasNext = true; 799 // Copy iterator state into local variables, so that we can modify and subdivide spans. 800 // ab old & new length, bc old & new length 801 int aLength = 0, ab_bLength = 0, bc_bLength = 0, cLength = 0; 802 // When we have different-intermediate-length changes, we accumulate a larger change. 803 int pending_aLength = 0, pending_cLength = 0; 804 for (;;) { 805 // At this point, for each of the two iterators: 806 // Either we are done with the locally cached current edit, 807 // and its intermediate-string length has been reset, 808 // or we will continue to work with a truncated remainder of this edit. 809 // 810 // If the current edit is done, and the iterator has not yet reached the end, 811 // then we fetch the next edit. This is true for at least one of the iterators. 812 // 813 // Normally it does not matter whether we fetch from ab and then bc or vice versa. 814 // However, the result is observably different when 815 // ab deletions meet bc insertions at the same intermediate-string index. 816 // Some users expect the bc insertions to come first, so we fetch from bc first. 817 if (bc_bLength == 0) { 818 if (bcHasNext && (bcHasNext = bcIter.next())) { 819 bc_bLength = bcIter.oldLength(); 820 cLength = bcIter.newLength(); 821 if (bc_bLength == 0) { 822 // insertion 823 if (ab_bLength == 0 || !abIter.hasChange()) { 824 addReplace(pending_aLength, pending_cLength + cLength); 825 pending_aLength = pending_cLength = 0; 826 } else { 827 pending_cLength += cLength; 828 } 829 continue; 830 } 831 } 832 // else see if the other iterator is done, too. 833 } 834 if (ab_bLength == 0) { 835 if (abHasNext && (abHasNext = abIter.next())) { 836 aLength = abIter.oldLength(); 837 ab_bLength = abIter.newLength(); 838 if (ab_bLength == 0) { 839 // deletion 840 if (bc_bLength == bcIter.oldLength() || !bcIter.hasChange()) { 841 addReplace(pending_aLength + aLength, pending_cLength); 842 pending_aLength = pending_cLength = 0; 843 } else { 844 pending_aLength += aLength; 845 } 846 continue; 847 } 848 } else if (bc_bLength == 0) { 849 // Both iterators are done at the same time: 850 // The intermediate-string lengths match. 851 break; 852 } else { 853 throw new IllegalArgumentException( 854 "The ab output string is shorter than the bc input string."); 855 } 856 } 857 if (bc_bLength == 0) { 858 throw new IllegalArgumentException( 859 "The bc input string is shorter than the ab output string."); 860 } 861 // Done fetching: ab_bLength > 0 && bc_bLength > 0 862 863 // The current state has two parts: 864 // - Past: We accumulate a longer ac edit in the "pending" variables. 865 // - Current: We have copies of the current ab/bc edits in local variables. 866 // At least one side is newly fetched. 867 // One side might be a truncated remainder of an edit we fetched earlier. 868 869 if (!abIter.hasChange() && !bcIter.hasChange()) { 870 // An unchanged span all the way from string a to string c. 871 if (pending_aLength != 0 || pending_cLength != 0) { 872 addReplace(pending_aLength, pending_cLength); 873 pending_aLength = pending_cLength = 0; 874 } 875 int unchangedLength = aLength <= cLength ? aLength : cLength; 876 addUnchanged(unchangedLength); 877 ab_bLength = aLength -= unchangedLength; 878 bc_bLength = cLength -= unchangedLength; 879 // At least one of the unchanged spans is now empty. 880 continue; 881 } 882 if (!abIter.hasChange() && bcIter.hasChange()) { 883 // Unchanged a->b but changed b->c. 884 if (ab_bLength >= bc_bLength) { 885 // Split the longer unchanged span into change + remainder. 886 addReplace(pending_aLength + bc_bLength, pending_cLength + cLength); 887 pending_aLength = pending_cLength = 0; 888 aLength = ab_bLength -= bc_bLength; 889 bc_bLength = 0; 890 continue; 891 } 892 // Handle the shorter unchanged span below like a change. 893 } else if (abIter.hasChange() && !bcIter.hasChange()) { 894 // Changed a->b and then unchanged b->c. 895 if (ab_bLength <= bc_bLength) { 896 // Split the longer unchanged span into change + remainder. 897 addReplace(pending_aLength + aLength, pending_cLength + ab_bLength); 898 pending_aLength = pending_cLength = 0; 899 cLength = bc_bLength -= ab_bLength; 900 ab_bLength = 0; 901 continue; 902 } 903 // Handle the shorter unchanged span below like a change. 904 } else { // both abIter.hasChange() && bcIter.hasChange() 905 if (ab_bLength == bc_bLength) { 906 // Changes on both sides up to the same position. Emit & reset. 907 addReplace(pending_aLength + aLength, pending_cLength + cLength); 908 pending_aLength = pending_cLength = 0; 909 ab_bLength = bc_bLength = 0; 910 continue; 911 } 912 } 913 // Accumulate the a->c change, reset the shorter side, 914 // keep a remainder of the longer one. 915 pending_aLength += aLength; 916 pending_cLength += cLength; 917 if (ab_bLength < bc_bLength) { 918 bc_bLength -= ab_bLength; 919 cLength = ab_bLength = 0; 920 } else { // ab_bLength > bc_bLength 921 ab_bLength -= bc_bLength; 922 aLength = bc_bLength = 0; 923 } 924 } 925 if (pending_aLength != 0 || pending_cLength != 0) { 926 addReplace(pending_aLength, pending_cLength); 927 } 928 return this; 929 } 930} 931