001 /* GapContent.java --
002 Copyright (C) 2002, 2004, 2005, 2006 Free Software Foundation, Inc.
003
004 This file is part of GNU Classpath.
005
006 GNU Classpath is free software; you can redistribute it and/or modify
007 it under the terms of the GNU General Public License as published by
008 the Free Software Foundation; either version 2, or (at your option)
009 any later version.
010
011 GNU Classpath is distributed in the hope that it will be useful, but
012 WITHOUT ANY WARRANTY; without even the implied warranty of
013 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
014 General Public License for more details.
015
016 You should have received a copy of the GNU General Public License
017 along with GNU Classpath; see the file COPYING. If not, write to the
018 Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
019 02110-1301 USA.
020
021 Linking this library statically or dynamically with other modules is
022 making a combined work based on this library. Thus, the terms and
023 conditions of the GNU General Public License cover the whole
024 combination.
025
026 As a special exception, the copyright holders of this library give you
027 permission to link this library with independent modules to produce an
028 executable, regardless of the license terms of these independent
029 modules, and to copy and distribute the resulting executable under
030 terms of your choice, provided that you also meet, for each linked
031 independent module, the terms and conditions of the license of that
032 module. An independent module is a module which is not derived from
033 or based on this library. If you modify this library, you may extend
034 this exception to your version of the library, but you are not
035 obligated to do so. If you do not wish to do so, delete this
036 exception statement from your version. */
037
038
039 package javax.swing.text;
040
041 import java.io.Serializable;
042 import java.lang.ref.ReferenceQueue;
043 import java.lang.ref.WeakReference;
044 import java.util.ArrayList;
045 import java.util.Collections;
046 import java.util.Iterator;
047 import java.util.List;
048 import java.util.Vector;
049
050 import javax.swing.undo.AbstractUndoableEdit;
051 import javax.swing.undo.CannotRedoException;
052 import javax.swing.undo.CannotUndoException;
053 import javax.swing.undo.UndoableEdit;
054
055 /**
056 * This implementation of {@link AbstractDocument.Content} uses a gapped buffer.
057 * This takes advantage of the fact that text area content is mostly inserted
058 * sequentially. The buffer is a char array that maintains a gap at the current
059 * insertion point. If characters a inserted at gap boundaries, the cost is
060 * minimal (simple array access). The array only has to be shifted around when
061 * the insertion point moves (then the gap also moves and one array copy is
062 * necessary) or when the gap is filled up and the buffer has to be enlarged.
063 */
064 public class GapContent
065 implements AbstractDocument.Content, Serializable
066 {
067
068 /**
069 * A {@link Position} implementation for <code>GapContent</code>.
070 */
071 class GapContentPosition
072 implements Position
073 {
074
075 /**
076 * The index to the positionMarks array entry, which in turn holds the
077 * mark into the buffer array.
078 */
079 Mark mark;
080
081 /**
082 * Returns the current offset of this Position within the content.
083 *
084 * @return the current offset of this Position within the content.
085 */
086 public int getOffset()
087 {
088 return mark.getOffset();
089 }
090 }
091
092 /**
093 * Holds a mark into the buffer that is used by GapContentPosition to find
094 * the actual offset of the position. This is pulled out of the
095 * GapContentPosition object so that the mark and position can be handled
096 * independently, and most important, so that the GapContentPosition can
097 * be garbage collected while we still hold a reference to the Mark object.
098 */
099 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 */
112 Mark(int offset)
113 {
114 super(null);
115 mark = offset;
116 }
117
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 */
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 */
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 */
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 */
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
196 public InsertUndo(int start, int len)
197 {
198 where = start;
199 length = len;
200 }
201
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
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
247 public UndoRemove(int start, String removedText)
248 {
249 where = start;
250 text = removedText;
251 positions = getPositionsInRange(null, start, removedText.length());
252 }
253
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
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 */
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 */
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 */
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 */
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 */
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 */
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 */
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 */
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 */
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 */
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 */
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 */
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 */
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 */
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 */
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 */
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 */
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 */
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 */
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 */
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 */
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 */
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 */
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 */
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 */
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 */
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 */
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 }