1 /* GapContent.java -- 2 Copyright (C) 2002, 2004, 2005, 2006 Free Software Foundation, Inc. 3 4 This file is part of GNU Classpath. 5 6 GNU Classpath is free software; you can redistribute it and/or modify 7 it under the terms of the GNU General Public License as published by 8 the Free Software Foundation; either version 2, or (at your option) 9 any later version. 10 11 GNU Classpath is distributed in the hope that it will be useful, but 12 WITHOUT ANY WARRANTY; without even the implied warranty of 13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14 General Public License for more details. 15 16 You should have received a copy of the GNU General Public License 17 along with GNU Classpath; see the file COPYING. If not, write to the 18 Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 19 02110-1301 USA. 20 21 Linking this library statically or dynamically with other modules is 22 making a combined work based on this library. Thus, the terms and 23 conditions of the GNU General Public License cover the whole 24 combination. 25 26 As a special exception, the copyright holders of this library give you 27 permission to link this library with independent modules to produce an 28 executable, regardless of the license terms of these independent 29 modules, and to copy and distribute the resulting executable under 30 terms of your choice, provided that you also meet, for each linked 31 independent module, the terms and conditions of the license of that 32 module. An independent module is a module which is not derived from 33 or based on this library. If you modify this library, you may extend 34 this exception to your version of the library, but you are not 35 obligated to do so. If you do not wish to do so, delete this 36 exception statement from your version. */ 37 38 39 package javax.swing.text; 40 41 import java.io.Serializable; 42 import java.lang.ref.ReferenceQueue; 43 import java.lang.ref.WeakReference; 44 import java.util.ArrayList; 45 import java.util.Collections; 46 import java.util.Iterator; 47 import java.util.List; 48 import java.util.Vector; 49 50 import javax.swing.undo.AbstractUndoableEdit; 51 import javax.swing.undo.CannotRedoException; 52 import javax.swing.undo.CannotUndoException; 53 import javax.swing.undo.UndoableEdit; 54 55 /** 56 * This implementation of {@link AbstractDocument.Content} uses a gapped buffer. 57 * This takes advantage of the fact that text area content is mostly inserted 58 * sequentially. The buffer is a char array that maintains a gap at the current 59 * insertion point. If characters a inserted at gap boundaries, the cost is 60 * minimal (simple array access). The array only has to be shifted around when 61 * the insertion point moves (then the gap also moves and one array copy is 62 * necessary) or when the gap is filled up and the buffer has to be enlarged. 63 */ 64 public class GapContent 65 implements AbstractDocument.Content, Serializable 66 { 67 68 /** 69 * A {@link Position} implementation for <code>GapContent</code>. 70 */ 71 class GapContentPosition 72 implements Position 73 { 74 75 /** 76 * The index to the positionMarks array entry, which in turn holds the 77 * mark into the buffer array. 78 */ 79 Mark mark; 80 81 /** 82 * Returns the current offset of this Position within the content. 83 * 84 * @return the current offset of this Position within the content. 85 */ getOffset()86 public int getOffset() 87 { 88 return mark.getOffset(); 89 } 90 } 91 92 /** 93 * Holds a mark into the buffer that is used by GapContentPosition to find 94 * the actual offset of the position. This is pulled out of the 95 * GapContentPosition object so that the mark and position can be handled 96 * independently, and most important, so that the GapContentPosition can 97 * be garbage collected while we still hold a reference to the Mark object. 98 */ 99 private class Mark 100 extends WeakReference 101 { 102 /** 103 * The actual mark into the buffer. 104 */ 105 int mark; 106 107 /** 108 * Creates a new Mark object for the specified offset. 109 * 110 * @param offset the offset 111 */ Mark(int offset)112 Mark(int offset) 113 { 114 super(null); 115 mark = offset; 116 } 117 Mark(int offset, GapContentPosition pos, ReferenceQueue queue)118 Mark(int offset, GapContentPosition pos, ReferenceQueue queue) 119 { 120 super(pos, queue); 121 mark = offset; 122 } 123 124 /** 125 * Returns the offset of the mark. 126 * 127 * @return the offset of the mark 128 */ getOffset()129 int getOffset() 130 { 131 int res = mark; 132 if (mark >= gapStart) 133 res -= (gapEnd - gapStart); 134 return Math.max(0, res); 135 } 136 137 /** 138 * Returns the GapContentPosition that is associated ith this mark. 139 * This fetches the weakly referenced position object. 140 * 141 * @return the GapContentPosition that is associated ith this mark 142 */ getPosition()143 GapContentPosition getPosition() 144 { 145 return (GapContentPosition) get(); 146 } 147 148 } 149 150 /** 151 * Stores a reference to a mark that can be resetted to the original value 152 * after a mark has been moved. This is used for undoing actions. 153 */ 154 private class UndoPosRef 155 { 156 /** 157 * The mark that might need to be reset. 158 */ 159 private Mark mark; 160 161 /** 162 * The original offset to reset the mark to. 163 */ 164 private int undoOffset; 165 166 /** 167 * Creates a new UndoPosRef. 168 * 169 * @param m the mark 170 */ UndoPosRef(Mark m)171 UndoPosRef(Mark m) 172 { 173 mark = m; 174 undoOffset = mark.getOffset(); 175 } 176 177 /** 178 * Resets the position of the mark to the value that it had when 179 * creating this UndoPosRef. 180 */ reset()181 void reset() 182 { 183 if (undoOffset <= gapStart) 184 mark.mark = undoOffset; 185 else 186 mark.mark = (gapEnd - gapStart) + undoOffset; 187 } 188 } 189 190 private class InsertUndo extends AbstractUndoableEdit 191 { 192 public int where, length; 193 String text; 194 private Vector positions; 195 InsertUndo(int start, int len)196 public InsertUndo(int start, int len) 197 { 198 where = start; 199 length = len; 200 } 201 undo()202 public void undo () throws CannotUndoException 203 { 204 super.undo(); 205 try 206 { 207 positions = getPositionsInRange(null, where, length); 208 text = getString(where, length); 209 remove(where, length); 210 } 211 catch (BadLocationException ble) 212 { 213 throw new CannotUndoException(); 214 } 215 } 216 redo()217 public void redo () throws CannotUndoException 218 { 219 super.redo(); 220 try 221 { 222 insertString(where, text); 223 if (positions != null) 224 { 225 updateUndoPositions(positions, where, length); 226 positions = null; 227 } 228 } 229 catch (BadLocationException ble) 230 { 231 throw new CannotRedoException(); 232 } 233 } 234 235 } 236 237 private class UndoRemove extends AbstractUndoableEdit 238 { 239 public int where; 240 String text; 241 242 /** 243 * The positions in the removed range. 244 */ 245 private Vector positions; 246 UndoRemove(int start, String removedText)247 public UndoRemove(int start, String removedText) 248 { 249 where = start; 250 text = removedText; 251 positions = getPositionsInRange(null, start, removedText.length()); 252 } 253 undo()254 public void undo () throws CannotUndoException 255 { 256 super.undo(); 257 try 258 { 259 insertString(where, text); 260 if (positions != null) 261 updateUndoPositions(positions, where, text.length()); 262 } 263 catch (BadLocationException ble) 264 { 265 throw new CannotUndoException(); 266 } 267 } 268 redo()269 public void redo () throws CannotUndoException 270 { 271 super.redo(); 272 try 273 { 274 text = getString(where, text.length()); 275 positions = getPositionsInRange(null, where, text.length()); 276 remove(where, text.length()); 277 } 278 catch (BadLocationException ble) 279 { 280 throw new CannotRedoException(); 281 } 282 } 283 284 } 285 286 /** The serialization UID (compatible with JDK1.5). */ 287 private static final long serialVersionUID = -6226052713477823730L; 288 289 /** 290 * This is the default buffer size and the amount of bytes that a buffer is 291 * extended if it is full. 292 */ 293 static final int DEFAULT_BUFSIZE = 10; 294 295 /** 296 * The text buffer. 297 */ 298 char[] buffer; 299 300 /** 301 * The index of the first character of the gap. 302 */ 303 int gapStart; 304 305 /** 306 * The index of the character after the last character of the gap. 307 */ 308 int gapEnd; 309 310 // FIXME: We might want to track GC'ed GapContentPositions and remove their 311 // corresponding marks, or alternativly, perform some regular cleanup of 312 // the positionMarks array. 313 314 /** 315 * Holds the marks for positions. These marks are referenced by the 316 * GapContentPosition instances by an index into this array. 317 * 318 * This is package private to avoid accessor synthetic methods. 319 */ 320 ArrayList marks; 321 322 /** 323 * The number of unused marks. 324 */ 325 private int garbageMarks; 326 327 /** 328 * A 'static' mark that is used for searching. 329 */ 330 private Mark searchMark = new Mark(0); 331 332 /** 333 * Queues all references to GapContentPositions that are about to be 334 * GC'ed. This is used to remove the corresponding marks from the 335 * positionMarks array if the number of references to that mark reaches zero. 336 * 337 * This is package private to avoid accessor synthetic methods. 338 */ 339 ReferenceQueue queueOfDeath; 340 341 /** 342 * Creates a new GapContent object. 343 */ GapContent()344 public GapContent() 345 { 346 this(DEFAULT_BUFSIZE); 347 } 348 349 /** 350 * Creates a new GapContent object with a specified initial size. 351 * 352 * @param size the initial size of the buffer 353 */ GapContent(int size)354 public GapContent(int size) 355 { 356 size = Math.max(size, 2); 357 buffer = (char[]) allocateArray(size); 358 gapStart = 1; 359 gapEnd = size; 360 buffer[0] = '\n'; 361 marks = new ArrayList(); 362 queueOfDeath = new ReferenceQueue(); 363 } 364 365 /** 366 * Allocates an array of the specified length that can then be used as 367 * buffer. 368 * 369 * @param size the size of the array to be allocated 370 * 371 * @return the allocated array 372 */ allocateArray(int size)373 protected Object allocateArray(int size) 374 { 375 return new char[size]; 376 } 377 378 /** 379 * Returns the length of the allocated buffer array. 380 * 381 * @return the length of the allocated buffer array 382 */ getArrayLength()383 protected int getArrayLength() 384 { 385 return buffer.length; 386 } 387 388 /** 389 * Returns the length of the content. 390 * 391 * @return the length of the content 392 */ length()393 public int length() 394 { 395 return buffer.length - (gapEnd - gapStart); 396 } 397 398 /** 399 * Inserts a string at the specified position. 400 * 401 * @param where the position where the string is inserted 402 * @param str the string that is to be inserted 403 * 404 * @return an UndoableEdit object 405 * 406 * @throws BadLocationException if <code>where</code> is not a valid 407 * location in the buffer 408 */ insertString(int where, String str)409 public UndoableEdit insertString(int where, String str) 410 throws BadLocationException 411 { 412 // check arguments 413 int length = length(); 414 int strLen = str.length(); 415 416 if (where < 0) 417 throw new BadLocationException("The where argument cannot be smaller" 418 + " than the zero", where); 419 420 if (where > length) 421 throw new BadLocationException("The where argument cannot be greater" 422 + " than the content length", where); 423 424 InsertUndo undo = new InsertUndo(where, strLen); 425 replace(where, 0, str.toCharArray(), strLen); 426 427 return undo; 428 } 429 430 /** 431 * Removes a piece of content at th specified position. 432 * 433 * @param where the position where the content is to be removed 434 * @param nitems number of characters to be removed 435 * 436 * @return an UndoableEdit object 437 * 438 * @throws BadLocationException if <code>where</code> is not a valid 439 * location in the buffer 440 */ remove(int where, int nitems)441 public UndoableEdit remove(int where, int nitems) throws BadLocationException 442 { 443 // check arguments 444 int length = length(); 445 446 if ((where + nitems) >= length) 447 throw new BadLocationException("where + nitems cannot be greater" 448 + " than the content length", where + nitems); 449 450 String removedText = getString(where, nitems); 451 UndoRemove undoRemove = new UndoRemove(where, removedText); 452 replace(where, nitems, null, 0); 453 454 return undoRemove; 455 } 456 457 /** 458 * Returns a piece of content as String. 459 * 460 * @param where the start location of the fragment 461 * @param len the length of the fragment 462 * 463 * @throws BadLocationException if <code>where</code> or 464 * <code>where + len</code> are no valid locations in the buffer 465 */ getString(int where, int len)466 public String getString(int where, int len) throws BadLocationException 467 { 468 Segment seg = new Segment(); 469 try 470 { 471 getChars(where, len, seg); 472 return new String(seg.array, seg.offset, seg.count); 473 } 474 catch (StringIndexOutOfBoundsException ex) 475 { 476 int invalid = 0; 477 if (seg.offset < 0 || seg.offset >= seg.array.length) 478 invalid = seg.offset; 479 else 480 invalid = seg.offset + seg.count; 481 throw new BadLocationException("Illegal location: array.length = " 482 + seg.array.length + ", offset = " 483 + seg.offset + ", count = " 484 + seg.count, invalid); 485 } 486 } 487 488 /** 489 * Fetches a piece of content and stores it in a {@link Segment} object. 490 * 491 * If the requested piece of text spans the gap, the content is copied into a 492 * new array. If it doesn't then it is contiguous and the actual content 493 * store is returned. 494 * 495 * @param where the start location of the fragment 496 * @param len the length of the fragment 497 * @param txt the Segment object to store the fragment in 498 * 499 * @throws BadLocationException if <code>where</code> or 500 * <code>where + len</code> are no valid locations in the buffer 501 */ getChars(int where, int len, Segment txt)502 public void getChars(int where, int len, Segment txt) 503 throws BadLocationException 504 { 505 // check arguments 506 int length = length(); 507 if (where < 0) 508 throw new BadLocationException("the where argument may not be below zero", where); 509 if (where >= length) 510 throw new BadLocationException("the where argument cannot be greater" 511 + " than the content length", where); 512 if ((where + len) > length) 513 throw new BadLocationException("len plus where cannot be greater" 514 + " than the content length", len + where); 515 if (len < 0) 516 throw new BadLocationException("negative length not allowed: ", len); 517 518 // Optimized to copy only when really needed. 519 if (where + len <= gapStart) 520 { 521 // Simple case: completely before gap. 522 txt.array = buffer; 523 txt.offset = where; 524 txt.count = len; 525 } 526 else if (where > gapStart) 527 { 528 // Completely after gap, adjust offset. 529 txt.array = buffer; 530 txt.offset = gapEnd + where - gapStart; 531 txt.count = len; 532 } 533 else 534 { 535 // Spans the gap. 536 int beforeGap = gapStart - where; 537 if (txt.isPartialReturn()) 538 { 539 // Return the part before the gap when partial return is allowed. 540 txt.array = buffer; 541 txt.offset = where; 542 txt.count = beforeGap; 543 } 544 else 545 { 546 // Copy pieces together otherwise. 547 txt.array = new char[len]; 548 txt.offset = 0; 549 System.arraycopy(buffer, where, txt.array, 0, beforeGap); 550 System.arraycopy(buffer, gapEnd, txt.array, beforeGap, 551 len - beforeGap); 552 txt.count = len; 553 } 554 } 555 } 556 557 /** 558 * Creates and returns a mark at the specified position. 559 * 560 * @param offset the position at which to create the mark 561 * 562 * @return the create Position object for the mark 563 * 564 * @throws BadLocationException if the offset is not a valid position in the 565 * buffer 566 */ createPosition(final int offset)567 public Position createPosition(final int offset) throws BadLocationException 568 { 569 // Implementation note: We used to perform explicit check on the offset 570 // here. However, this makes some Mauve and Intel/Harmony tests fail 571 // and luckily enough the GapContent can very well deal with offsets 572 // outside the buffer bounds. So I removed that check. 573 574 // First do some garbage collections. 575 while (queueOfDeath.poll() != null) 576 garbageMarks++; 577 if (garbageMarks > Math.max(5, marks.size() / 10)) 578 garbageCollect(); 579 580 // We try to find a GapContentPosition at the specified offset and return 581 // that. Otherwise we must create a new one. 582 Mark m; 583 GapContentPosition pos; 584 int index = offset; 585 if (offset >= gapStart) 586 index += (gapEnd - gapStart); 587 searchMark.mark = index; 588 int insertIndex = search(searchMark); 589 if (!(insertIndex < marks.size() 590 && (m = (Mark) marks.get(insertIndex)).mark == index 591 && (pos = m.getPosition()) != null)) 592 { 593 // Create new position if none was found. 594 pos = new GapContentPosition(); 595 m = new Mark(index, pos, queueOfDeath); 596 pos.mark = m; 597 marks.add(insertIndex, m); 598 } 599 // Otherwise use the found position. 600 601 return pos; 602 } 603 604 /** 605 * Enlarges the gap. This allocates a new bigger buffer array, copy the 606 * segment before the gap as it is and the segment after the gap at the end 607 * of the new buffer array. This does change the gapEnd mark but not the 608 * gapStart mark. 609 * 610 * @param newSize the new size of the gap 611 */ shiftEnd(int newSize)612 protected void shiftEnd(int newSize) 613 { 614 assert newSize > (gapEnd - gapStart) : "The new gap size must be greater " 615 + "than the old gap size"; 616 617 int oldEnd = getGapEnd(); 618 int oldSize = getArrayLength(); 619 int upper = oldSize - oldEnd; 620 int size = (newSize + 1) * 2; 621 int newEnd = size - upper; 622 623 // Copy the data around. 624 char[] newBuf = (char[]) allocateArray(size); 625 System.arraycopy(buffer, 0, newBuf, 0, Math.min(size, oldSize)); 626 buffer = newBuf; 627 gapEnd = newEnd; 628 if (upper != 0) 629 System.arraycopy(buffer, oldEnd, buffer, newEnd, upper); 630 631 // Adjust marks. 632 int delta = gapEnd - oldEnd; 633 int adjIndex = searchFirst(oldEnd); 634 int count = marks.size(); 635 for (int i = adjIndex; i < count; i++) 636 { 637 Mark m = (Mark) marks.get(i); 638 m.mark += delta; 639 } 640 } 641 642 /** 643 * Shifts the gap to the specified position. 644 * 645 * @param newGapStart the new start position of the gap 646 */ shiftGap(int newGapStart)647 protected void shiftGap(int newGapStart) 648 { 649 int oldStart = gapStart; 650 int delta = newGapStart - oldStart; 651 int oldEnd = gapEnd; 652 int newGapEnd = oldEnd + delta; 653 int size = oldEnd - oldStart; 654 655 // Shift gap in array. 656 gapStart = newGapStart; 657 gapEnd = newGapEnd; 658 if (delta > 0) 659 System.arraycopy(buffer, oldEnd, buffer, oldStart, delta); 660 else 661 System.arraycopy(buffer, newGapStart, buffer, newGapEnd, -delta); 662 663 // Adjust marks. 664 if (delta > 0) 665 { 666 int adjIndex = searchFirst(oldStart); 667 int count = marks.size(); 668 for (int i = adjIndex; i < count; i++) 669 { 670 Mark m = (Mark) marks.get(i); 671 if (m.mark >= newGapEnd) 672 break; 673 m.mark -= size; 674 } 675 } 676 else if (delta < 0) 677 { 678 int adjIndex = searchFirst(newGapStart); 679 int count = marks.size(); 680 for (int i = adjIndex; i < count; i++) 681 { 682 Mark m = (Mark) marks.get(i); 683 if (m.mark >= oldEnd) 684 break; 685 m.mark += size; 686 } 687 } 688 resetMarksAtZero(); 689 } 690 691 /** 692 * Shifts the gap start downwards. This does not affect the content of the 693 * buffer. This only updates the gap start and all the marks that are between 694 * the old gap start and the new gap start. They all are squeezed to the start 695 * of the gap, because their location has been removed. 696 * 697 * @param newGapStart the new gap start 698 */ shiftGapStartDown(int newGapStart)699 protected void shiftGapStartDown(int newGapStart) 700 { 701 if (newGapStart == gapStart) 702 return; 703 704 assert newGapStart < gapStart : "The new gap start must be less than the " 705 + "old gap start."; 706 707 // Adjust positions. 708 int adjIndex = searchFirst(newGapStart); 709 int count = marks.size(); 710 for (int i = adjIndex; i < count; i++) 711 { 712 Mark m = (Mark) marks.get(i); 713 if (m.mark > gapStart) 714 break; 715 m.mark = gapEnd; 716 } 717 718 gapStart = newGapStart; 719 resetMarksAtZero(); 720 } 721 722 /** 723 * Shifts the gap end upwards. This does not affect the content of the 724 * buffer. This only updates the gap end and all the marks that are between 725 * the old gap end and the new end start. They all are squeezed to the end 726 * of the gap, because their location has been removed. 727 * 728 * @param newGapEnd the new gap start 729 */ 730 protected void shiftGapEndUp(int newGapEnd) 731 { 732 if (newGapEnd == gapEnd) 733 return; 734 735 assert newGapEnd > gapEnd : "The new gap end must be greater than the " 736 + "old gap end."; 737 738 // Adjust marks. 739 int adjIndex = searchFirst(gapEnd); 740 int count = marks.size(); 741 for (int i = adjIndex; i < count; i++) 742 { 743 Mark m = (Mark) marks.get(i); 744 if (m.mark >= newGapEnd) 745 break; 746 m.mark = newGapEnd; 747 } 748 749 750 gapEnd = newGapEnd; 751 resetMarksAtZero(); 752 } 753 754 /** 755 * Returns the allocated buffer array. 756 * 757 * @return the allocated buffer array 758 */ getArray()759 protected final Object getArray() 760 { 761 return buffer; 762 } 763 764 /** 765 * Replaces a portion of the storage with the specified items. 766 * 767 * @param position the position at which to remove items 768 * @param rmSize the number of items to remove 769 * @param addItems the items to add at location 770 * @param addSize the number of items to add 771 */ replace(int position, int rmSize, Object addItems, int addSize)772 protected void replace(int position, int rmSize, Object addItems, 773 int addSize) 774 { 775 if (addSize == 0) 776 { 777 removeImpl(position, rmSize); 778 return; 779 } 780 else if (rmSize > addSize) 781 { 782 removeImpl(position + addSize, rmSize - addSize); 783 } 784 else 785 { 786 int endSize = addSize - rmSize; 787 int end = addImpl(position + rmSize, endSize); 788 System.arraycopy(addItems, rmSize, buffer, end, endSize); 789 addSize = rmSize; 790 } 791 System.arraycopy(addItems, 0, buffer, position, addSize); 792 } 793 794 /** 795 * Adjusts the positions and gap in response to a remove operation. 796 * 797 * @param pos the position at which to remove 798 * @param num the number of removed items 799 */ removeImpl(int pos, int num)800 private void removeImpl(int pos, int num) 801 { 802 if (num > 0) 803 { 804 int end = pos + num; 805 int newGapSize = (gapEnd - gapStart) + num; 806 if (end <= gapStart) 807 { 808 if (gapStart != end) 809 { 810 shiftGap(end); 811 } 812 shiftGapStartDown(gapStart - num); 813 } 814 else if (pos >= gapStart) 815 { 816 if (gapStart != pos) 817 { 818 shiftGap(pos); 819 } 820 shiftGapEndUp(gapStart + newGapSize); 821 } 822 else 823 { 824 shiftGapStartDown(pos); 825 shiftGapEndUp(gapStart + newGapSize); 826 } 827 } 828 } 829 830 /** 831 * Adjusts the positions and gap in response to an add operation. 832 * 833 * @param pos the position at which to add 834 * @param num the number of added items 835 * 836 * @return the adjusted position 837 */ addImpl(int pos, int num)838 private int addImpl(int pos, int num) 839 { 840 int size = gapEnd - gapStart; 841 if (num == 0) 842 { 843 if (pos > gapStart) 844 pos += size; 845 return pos; 846 } 847 848 shiftGap(pos); 849 if (num >= size) 850 { 851 shiftEnd(getArrayLength() - size + num); 852 size = gapEnd - gapStart; 853 } 854 855 gapStart += num; 856 return pos; 857 } 858 859 /** 860 * Returns the start index of the gap within the buffer array. 861 * 862 * @return the start index of the gap within the buffer array 863 */ getGapStart()864 protected final int getGapStart() 865 { 866 return gapStart; 867 } 868 869 /** 870 * Returns the end index of the gap within the buffer array. 871 * 872 * @return the end index of the gap within the buffer array 873 */ getGapEnd()874 protected final int getGapEnd() 875 { 876 return gapEnd; 877 } 878 879 /** 880 * Returns all <code>Position</code>s that are in the range specified by 881 * <code>offset</code> and </code>length</code> within the buffer array. 882 * 883 * @param v the vector to use; if <code>null</code>, a new Vector is allocated 884 * @param offset the start offset of the range to search 885 * @param length the length of the range to search 886 * 887 * @return the positions within the specified range 888 */ getPositionsInRange(Vector v, int offset, int length)889 protected Vector getPositionsInRange(Vector v, int offset, int length) 890 { 891 int end = offset + length; 892 int startIndex; 893 int endIndex; 894 if (offset < gapStart) 895 { 896 if (offset == 0) 897 startIndex = 0; 898 else 899 startIndex = searchFirst(offset); 900 if (end >= gapStart) 901 endIndex = searchFirst(end + (gapEnd - gapStart) + 1); 902 else 903 endIndex = searchFirst(end + 1); 904 } 905 else 906 { 907 startIndex = searchFirst(offset + (gapEnd - gapStart)); 908 endIndex = searchFirst(end + (gapEnd - gapStart) + 1); 909 } 910 if (v == null) 911 v = new Vector(); 912 for (int i = startIndex; i < endIndex; i++) 913 { 914 v.add(new UndoPosRef((Mark) marks.get(i))); 915 } 916 return v; 917 } 918 919 /** 920 * Resets all <code>Position</code> that have an offset of <code>0</code>, 921 * to also have an array index of <code>0</code>. This might be necessary 922 * after a call to <code>shiftGap(0)</code>, since then the marks at offset 923 * <code>0</code> get shifted to <code>gapEnd</code>. 924 */ resetMarksAtZero()925 protected void resetMarksAtZero() 926 { 927 if (gapStart != 0) 928 return; 929 930 for (int i = 0; i < marks.size(); i++) 931 { 932 Mark m = (Mark) marks.get(i); 933 if (m.mark <= gapEnd) 934 m.mark = 0; 935 } 936 } 937 938 /** 939 * Resets the positions in the specified range to their original offset 940 * after a undo operation is performed. For example, after removing some 941 * content, the positions in the removed range will all be set to one 942 * offset. This method restores the positions to their original offsets 943 * after an undo. 944 * 945 * @param positions the positions to update 946 * @param offset 947 * @param length 948 */ updateUndoPositions(Vector positions, int offset, int length)949 protected void updateUndoPositions(Vector positions, int offset, int length) 950 { 951 for (Iterator i = positions.iterator(); i.hasNext();) 952 { 953 UndoPosRef undoPosRef = (UndoPosRef) i.next(); 954 undoPosRef.reset(); 955 } 956 957 // Resort marks. 958 Collections.sort(marks); 959 } 960 961 /** 962 * Outputs debugging info to System.err. It prints out the buffer array, 963 * the gapStart is marked by a < sign, the gapEnd is marked by a > 964 * sign and each position is marked by a # sign. 965 */ dump()966 private void dump() 967 { 968 System.err.println("GapContent debug information"); 969 System.err.println("buffer length: " + buffer.length); 970 System.err.println("gap start: " + gapStart); 971 System.err.println("gap end: " + gapEnd); 972 for (int i = 0; i < buffer.length; i++) 973 { 974 if (i == gapStart) 975 System.err.print('<'); 976 if (i == gapEnd) 977 System.err.print('>'); 978 979 if (!Character.isISOControl(buffer[i])) 980 System.err.print(buffer[i]); 981 else 982 System.err.print('.'); 983 } 984 System.err.println(); 985 } 986 987 /** 988 * Prints out the position marks. 989 */ dumpMarks()990 private void dumpMarks() 991 { 992 System.out.print("positionMarks: "); 993 for (int i = 0; i < marks.size(); i++) 994 System.out.print(((Mark) marks.get(i)).mark + ", "); 995 System.out.println(); 996 } 997 998 /** 999 * Searches the first occurance of object <code>o</code> in list 1000 * <code>l</code>. This performs a binary search by calling 1001 * {@link Collections#binarySearch(List, Object)} and when an object has been 1002 * found, it searches backwards to the first occurance of that object in the 1003 * list. The meaning of the return value is the same as in 1004 * <code>Collections.binarySearch()</code>. 1005 * 1006 * @param o the object to be searched 1007 * 1008 * @return the index of the first occurance of o in l, or -i + 1 if not found 1009 */ search(Mark o)1010 int search(Mark o) 1011 { 1012 int foundInd = 0; 1013 boolean found = false; 1014 int low = 0; 1015 int up = marks.size() - 1; 1016 int mid = 0; 1017 if (up > -1) 1018 { 1019 int cmp = 0; 1020 Mark last = (Mark) marks.get(up); 1021 cmp = compare(o, last); 1022 if (cmp > 0) 1023 { 1024 foundInd = up + 1; 1025 found = true; 1026 } 1027 else 1028 { 1029 while (low <= up && ! found) 1030 { 1031 mid = low + (up - low) / 2; 1032 Mark m = (Mark) marks.get(mid); 1033 cmp = compare(o, m); 1034 if (cmp == 0) 1035 { 1036 foundInd = mid; 1037 found = true; 1038 } 1039 else if (cmp < 0) 1040 up = mid - 1; 1041 else 1042 low = mid + 1; 1043 } 1044 1045 if (! found) 1046 foundInd = cmp < 0 ? mid : mid + 1; 1047 } 1048 } 1049 return foundInd; 1050 } 1051 1052 private int searchFirst(int index) 1053 { 1054 searchMark.mark = Math.max(index, 1); 1055 int i = search(searchMark); 1056 for (int j = i - 1; j >= 0; j--) 1057 { 1058 Mark m = (Mark) marks.get(j); 1059 if (m.mark != index) 1060 break; 1061 i--; 1062 } 1063 return i; 1064 } 1065 1066 /** 1067 * Compares two marks. 1068 * 1069 * @param m1 the first mark 1070 * @param m2 the second mark 1071 * 1072 * @return negative when m1 < m2, positive when m1 > m2 and 0 when equal 1073 */ compare(Mark m1, Mark m2)1074 private int compare(Mark m1, Mark m2) 1075 { 1076 return m1.mark - m2.mark; 1077 } 1078 1079 /** 1080 * Collects and frees unused marks. 1081 */ garbageCollect()1082 private void garbageCollect() 1083 { 1084 int count = marks.size(); 1085 ArrayList clean = new ArrayList(); 1086 for (int i = 0; i < count; i++) 1087 { 1088 Mark m = (Mark) marks.get(i); 1089 if (m.get() != null) 1090 clean.add(m); 1091 } 1092 marks = clean; 1093 garbageMarks = 0; 1094 } 1095 } 1096