2 Copyright (C) 2002, 2004, 2005, 2006 Free Software Foundation, Inc.
4 This file is part of GNU Classpath.
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)
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.
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
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
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. */
39 package javax
.swing
.text
;
41 import java
.io
.Serializable
;
42 import java
.lang
.ref
.WeakReference
;
43 import java
.util
.ArrayList
;
44 import java
.util
.Collections
;
45 import java
.util
.Comparator
;
46 import java
.util
.Iterator
;
47 import java
.util
.ListIterator
;
48 import java
.util
.Vector
;
50 import javax
.swing
.undo
.AbstractUndoableEdit
;
51 import javax
.swing
.undo
.CannotRedoException
;
52 import javax
.swing
.undo
.CannotUndoException
;
53 import javax
.swing
.undo
.UndoableEdit
;
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.
64 * TODO: Implement UndoableEdit support stuff
66 public class GapContent
67 implements AbstractDocument
.Content
, Serializable
71 * A {@link Position} implementation for <code>GapContent</code>.
73 private class GapContentPosition
74 implements Position
, Comparable
77 /** The index within the buffer array. */
81 * Creates a new GapContentPosition object.
83 * @param mark the mark of this Position
85 GapContentPosition(int mark
)
91 * Comparable interface implementation. This is used to store all
92 * positions in an ordered fashion.
94 * @param o the object to be compared to this
96 * @return a negative integer if this is less than <code>o</code>, zero
97 * if both are equal or a positive integer if this is greater than
100 * @throws ClassCastException if <code>o</code> is not a
101 * GapContentPosition or Integer object
103 public int compareTo(Object o
)
105 if (o
instanceof Integer
)
107 int otherMark
= ((Integer
) o
).intValue();
108 return mark
- otherMark
;
112 GapContentPosition other
= (GapContentPosition
) o
;
113 return mark
- other
.mark
;
118 * Returns the current offset of this Position within the content.
120 * @return the current offset of this Position within the content.
122 public int getOffset()
124 // Check precondition.
125 assert mark
<= gapStart
|| mark
>= gapEnd
: "mark: " + mark
126 + ", gapStart: " + gapStart
127 + ", gapEnd: " + gapEnd
;
128 if (mark
<= gapStart
)
131 return mark
- (gapEnd
- gapStart
);
135 private class InsertUndo
extends AbstractUndoableEdit
137 public int where
, length
;
139 public InsertUndo(int start
, int len
)
145 public void undo () throws CannotUndoException
150 text
= getString(where
, length
);
151 remove(where
, length
);
153 catch (BadLocationException ble
)
155 throw new CannotUndoException();
159 public void redo () throws CannotUndoException
164 insertString(where
, text
);
166 catch (BadLocationException ble
)
168 throw new CannotRedoException();
174 private class UndoRemove
extends AbstractUndoableEdit
178 public UndoRemove(int start
, String removedText
)
184 public void undo () throws CannotUndoException
189 insertString(where
, text
);
191 catch (BadLocationException ble
)
193 throw new CannotUndoException();
197 public void redo () throws CannotUndoException
202 remove(where
, text
.length());
204 catch (BadLocationException ble
)
206 throw new CannotRedoException();
213 * Compares WeakReference objects in a List by comparing the referenced
216 * @author Roman Kennke (kennke@aicas.com)
218 private class WeakPositionComparator
219 implements Comparator
223 * Compares two objects of type WeakReference. The objects are compared
224 * using the referenced objects compareTo() method.
226 public int compare(Object o1
, Object o2
)
228 // Unwrap references.
229 if (o1
instanceof WeakReference
)
230 o1
= ((WeakReference
) o1
).get();
231 if (o2
instanceof WeakReference
)
232 o2
= ((WeakReference
) o2
).get();
234 GapContentPosition p1
= (GapContentPosition
) o1
;
235 GapContentPosition p2
= (GapContentPosition
) o2
;
238 if (p1
== null || p2
== null)
241 retVal
= p1
.compareTo(p2
);
246 /** The serialization UID (compatible with JDK1.5). */
247 private static final long serialVersionUID
= -6226052713477823730L;
250 * This is the default buffer size and the amount of bytes that a buffer is
251 * extended if it is full.
253 static final int DEFAULT_BUFSIZE
= 10;
261 * The index of the first character of the gap.
266 * The index of the character after the last character of the gap.
271 * The positions generated by this GapContent. They are kept in an ordered
272 * fashion, so they can be looked up easily. The value objects will be
273 * WeakReference objects that in turn hold GapContentPosition objects.
275 private ArrayList positions
;
278 * Creates a new GapContent object.
282 this(DEFAULT_BUFSIZE
);
286 * Creates a new GapContent object with a specified initial size.
288 * @param size the initial size of the buffer
290 public GapContent(int size
)
292 size
= Math
.max(size
, 2);
293 buffer
= (char[]) allocateArray(size
);
297 positions
= new ArrayList();
301 * Allocates an array of the specified length that can then be used as
304 * @param size the size of the array to be allocated
306 * @return the allocated array
308 protected Object
allocateArray(int size
)
310 return new char[size
];
314 * Returns the length of the allocated buffer array.
316 * @return the length of the allocated buffer array
318 protected int getArrayLength()
320 return buffer
.length
;
324 * Returns the length of the content.
326 * @return the length of the content
330 return buffer
.length
- (gapEnd
- gapStart
);
334 * Inserts a string at the specified position.
336 * @param where the position where the string is inserted
337 * @param str the string that is to be inserted
339 * @return an UndoableEdit object
341 * @throws BadLocationException if <code>where</code> is not a valid
342 * location in the buffer
344 public UndoableEdit
insertString(int where
, String str
)
345 throws BadLocationException
348 int length
= length();
349 int strLen
= str
.length();
352 throw new BadLocationException("The where argument cannot be smaller"
353 + " than the zero", where
);
356 throw new BadLocationException("The where argument cannot be greater"
357 + " than the content length", where
);
359 replace(where
, 0, str
.toCharArray(), strLen
);
361 return new InsertUndo(where
, strLen
);
365 * Removes a piece of content at th specified position.
367 * @param where the position where the content is to be removed
368 * @param nitems number of characters to be removed
370 * @return an UndoableEdit object
372 * @throws BadLocationException if <code>where</code> is not a valid
373 * location in the buffer
375 public UndoableEdit
remove(int where
, int nitems
) throws BadLocationException
378 int length
= length();
380 if ((where
+ nitems
) >= length
)
381 throw new BadLocationException("where + nitems cannot be greater"
382 + " than the content length", where
+ nitems
);
384 String removedText
= getString(where
, nitems
);
385 replace(where
, nitems
, null, 0);
387 return new UndoRemove(where
, removedText
);
391 * Returns a piece of content as String.
393 * @param where the start location of the fragment
394 * @param len the length of the fragment
396 * @throws BadLocationException if <code>where</code> or
397 * <code>where + len</code> are no valid locations in the buffer
399 public String
getString(int where
, int len
) throws BadLocationException
401 Segment seg
= new Segment();
404 getChars(where
, len
, seg
);
405 return new String(seg
.array
, seg
.offset
, seg
.count
);
407 catch (StringIndexOutOfBoundsException ex
)
410 if (seg
.offset
< 0 || seg
.offset
>= seg
.array
.length
)
411 invalid
= seg
.offset
;
413 invalid
= seg
.offset
+ seg
.count
;
414 throw new BadLocationException("Illegal location: array.length = "
415 + seg
.array
.length
+ ", offset = "
416 + seg
.offset
+ ", count = "
417 + seg
.count
, invalid
);
422 * Fetches a piece of content and stores it in a {@link Segment} object.
424 * If the requested piece of text spans the gap, the content is copied into a
425 * new array. If it doesn't then it is contiguous and the actual content
428 * @param where the start location of the fragment
429 * @param len the length of the fragment
430 * @param txt the Segment object to store the fragment in
432 * @throws BadLocationException if <code>where</code> or
433 * <code>where + len</code> are no valid locations in the buffer
435 public void getChars(int where
, int len
, Segment txt
)
436 throws BadLocationException
439 int length
= length();
441 throw new BadLocationException("the where argument may not be below zero", where
);
443 throw new BadLocationException("the where argument cannot be greater"
444 + " than the content length", where
);
445 if ((where
+ len
) > length
)
446 throw new BadLocationException("len plus where cannot be greater"
447 + " than the content length", len
+ where
);
449 // check if requested segment is contiguous
450 if ((where
< gapStart
) && ((gapStart
- where
) < len
))
452 // requested segment is not contiguous -> copy the pieces together
453 char[] copy
= new char[len
];
454 int lenFirst
= gapStart
- where
; // the length of the first segment
455 System
.arraycopy(buffer
, where
, copy
, 0, lenFirst
);
456 System
.arraycopy(buffer
, gapEnd
, copy
, lenFirst
, len
- lenFirst
);
463 // requested segment is contiguous -> we can simply return the
466 if (where
< gapStart
)
469 txt
.offset
= where
+ (gapEnd
- gapStart
);
475 * Creates and returns a mark at the specified position.
477 * @param offset the position at which to create the mark
479 * @return the create Position object for the mark
481 * @throws BadLocationException if the offset is not a valid position in the
484 public Position
createPosition(final int offset
) throws BadLocationException
486 if (offset
< 0 || offset
> length())
487 throw new BadLocationException("The offset was out of the bounds of this"
488 + " buffer", offset
);
490 clearPositionReferences();
492 // We store the actual array index in the GapContentPosition. The real
493 // offset is then calculated in the GapContentPosition.
495 if (offset
>= gapStart
)
496 mark
+= gapEnd
- gapStart
;
497 GapContentPosition pos
= new GapContentPosition(mark
);
498 WeakReference r
= new WeakReference(pos
);
500 // Add this into our list in a sorted fashion.
501 int index
= Collections
.binarySearch(positions
, r
,
502 new WeakPositionComparator());
504 index
= -(index
+ 1);
505 positions
.add(index
, r
);
510 * Enlarges the gap. This allocates a new bigger buffer array, copy the
511 * segment before the gap as it is and the segment after the gap at the end
512 * of the new buffer array. This does change the gapEnd mark but not the
515 * @param newSize the new size of the gap
517 protected void shiftEnd(int newSize
)
519 assert newSize
> (gapEnd
- gapStart
) : "The new gap size must be greater "
520 + "than the old gap size";
522 int delta
= newSize
- gapEnd
+ gapStart
;
523 // Update the marks after the gapEnd.
524 adjustPositionsInRange(gapEnd
, buffer
.length
- gapEnd
, delta
);
526 // Copy the data around.
527 char[] newBuf
= (char[]) allocateArray(length() + newSize
);
528 System
.arraycopy(buffer
, 0, newBuf
, 0, gapStart
);
529 System
.arraycopy(buffer
, gapEnd
, newBuf
, gapStart
+ newSize
, buffer
.length
531 gapEnd
= gapStart
+ newSize
;
537 * Shifts the gap to the specified position.
539 * @param newGapStart the new start position of the gap
541 protected void shiftGap(int newGapStart
)
543 if (newGapStart
== gapStart
)
546 int newGapEnd
= newGapStart
+ gapEnd
- gapStart
;
547 if (newGapStart
< gapStart
)
549 // Update the positions between newGapStart and (old) gapStart. The marks
550 // must be shifted by (gapEnd - gapStart).
551 adjustPositionsInRange(newGapStart
, gapStart
- newGapStart
, gapEnd
- gapStart
);
552 System
.arraycopy(buffer
, newGapStart
, buffer
, newGapEnd
, gapStart
554 gapStart
= newGapStart
;
559 // Update the positions between newGapEnd and (old) gapEnd. The marks
560 // must be shifted by (gapEnd - gapStart).
561 adjustPositionsInRange(gapEnd
, newGapEnd
- gapEnd
, -(gapEnd
- gapStart
));
562 System
.arraycopy(buffer
, gapEnd
, buffer
, gapStart
, newGapStart
564 gapStart
= newGapStart
;
572 * Shifts the gap start downwards. This does not affect the content of the
573 * buffer. This only updates the gap start and all the marks that are between
574 * the old gap start and the new gap start. They all are squeezed to the start
575 * of the gap, because their location has been removed.
577 * @param newGapStart the new gap start
579 protected void shiftGapStartDown(int newGapStart
)
581 if (newGapStart
== gapStart
)
584 assert newGapStart
< gapStart
: "The new gap start must be less than the "
586 setPositionsInRange(newGapStart
, gapStart
- newGapStart
, gapStart
);
587 gapStart
= newGapStart
;
591 * Shifts the gap end upwards. This does not affect the content of the
592 * buffer. This only updates the gap end and all the marks that are between
593 * the old gap end and the new end start. They all are squeezed to the end
594 * of the gap, because their location has been removed.
596 * @param newGapEnd the new gap start
598 protected void shiftGapEndUp(int newGapEnd
)
600 if (newGapEnd
== gapEnd
)
603 assert newGapEnd
> gapEnd
: "The new gap end must be greater than the "
605 setPositionsInRange(gapEnd
, newGapEnd
- gapEnd
, newGapEnd
);
610 * Returns the allocated buffer array.
612 * @return the allocated buffer array
614 protected final Object
getArray()
620 * Replaces a portion of the storage with the specified items.
622 * @param position the position at which to remove items
623 * @param rmSize the number of items to remove
624 * @param addItems the items to add at location
625 * @param addSize the number of items to add
627 protected void replace(int position
, int rmSize
, Object addItems
,
630 if (gapStart
!= position
)
635 shiftGapEndUp(gapEnd
+ rmSize
);
637 // If gap is too small, enlarge the gap.
638 if ((gapEnd
- gapStart
) <= addSize
)
639 shiftEnd((addSize
- gapEnd
+ gapStart
+ 1) * 2 + gapEnd
+ DEFAULT_BUFSIZE
);
641 // Add new items to the buffer.
642 if (addItems
!= null)
644 System
.arraycopy(addItems
, 0, buffer
, gapStart
, addSize
);
654 * Returns the start index of the gap within the buffer array.
656 * @return the start index of the gap within the buffer array
658 protected final int getGapStart()
664 * Returns the end index of the gap within the buffer array.
666 * @return the end index of the gap within the buffer array
668 protected final int getGapEnd()
674 * Returns all <code>Position</code>s that are in the range specified by
675 * <code>offset</code> and </code>length</code> within the buffer array.
677 * @param v the vector to use; if <code>null</code>, a new Vector is allocated
678 * @param offset the start offset of the range to search
679 * @param length the length of the range to search
681 * @return the positions within the specified range
683 protected Vector
getPositionsInRange(Vector v
, int offset
, int length
)
691 int endOffset
= offset
+ length
;
693 int index1
= Collections
.binarySearch(positions
,
694 new GapContentPosition(offset
),
695 new WeakPositionComparator());
697 index1
= -(index1
+ 1);
699 // Search the first index with the specified offset. The binarySearch does
700 // not necessarily find the first one.
703 WeakReference r
= (WeakReference
) positions
.get(index1
- 1);
704 GapContentPosition p
= (GapContentPosition
) r
.get();
705 if (p
!= null && p
.mark
== offset
|| p
== null)
711 for (ListIterator i
= positions
.listIterator(index1
); i
.hasNext();)
713 WeakReference r
= (WeakReference
) i
.next();
714 GapContentPosition p
= (GapContentPosition
) r
.get();
718 if (p
.mark
> endOffset
)
720 if (p
.mark
>= offset
&& p
.mark
<= endOffset
)
727 * Sets the mark of all <code>Position</code>s that are in the range
728 * specified by <code>offset</code> and </code>length</code> within
729 * the buffer array to <code>value</code>
731 * @param offset the start offset of the range to search
732 * @param length the length of the range to search
733 * @param value the new value for each mark
735 private void setPositionsInRange(int offset
, int length
, int value
)
737 int endOffset
= offset
+ length
;
739 int index1
= Collections
.binarySearch(positions
,
740 new GapContentPosition(offset
),
741 new WeakPositionComparator());
743 index1
= -(index1
+ 1);
745 // Search the first index with the specified offset. The binarySearch does
746 // not necessarily find the first one.
749 WeakReference r
= (WeakReference
) positions
.get(index1
- 1);
750 GapContentPosition p
= (GapContentPosition
) r
.get();
751 if (p
!= null && p
.mark
== offset
|| p
== null)
757 for (ListIterator i
= positions
.listIterator(index1
); i
.hasNext();)
759 WeakReference r
= (WeakReference
) i
.next();
760 GapContentPosition p
= (GapContentPosition
) r
.get();
764 if (p
.mark
> endOffset
)
767 if (p
.mark
>= offset
&& p
.mark
<= endOffset
)
773 * Adjusts the mark of all <code>Position</code>s that are in the range
774 * specified by <code>offset</code> and </code>length</code> within
775 * the buffer array by <code>increment</code>
777 * @param offset the start offset of the range to search
778 * @param length the length of the range to search
779 * @param incr the increment
781 private void adjustPositionsInRange(int offset
, int length
, int incr
)
783 int endOffset
= offset
+ length
;
785 int index1
= Collections
.binarySearch(positions
,
786 new GapContentPosition(offset
),
787 new WeakPositionComparator());
789 index1
= -(index1
+ 1);
791 // Search the first index with the specified offset. The binarySearch does
792 // not necessarily find the first one.
795 WeakReference r
= (WeakReference
) positions
.get(index1
- 1);
796 GapContentPosition p
= (GapContentPosition
) r
.get();
797 if (p
!= null && p
.mark
== offset
|| p
== null)
803 for (ListIterator i
= positions
.listIterator(index1
); i
.hasNext();)
805 WeakReference r
= (WeakReference
) i
.next();
806 GapContentPosition p
= (GapContentPosition
) r
.get();
810 if (p
.mark
> endOffset
)
813 if (p
.mark
>= offset
&& p
.mark
<= endOffset
)
819 * Resets all <code>Position</code> that have an offset of <code>0</code>,
820 * to also have an array index of <code>0</code>. This might be necessary
821 * after a call to <code>shiftGap(0)</code>, since then the marks at offset
822 * <code>0</code> get shifted to <code>gapEnd</code>.
824 protected void resetMarksAtZero()
829 setPositionsInRange(gapEnd
, 0, 0);
833 * @specnote This method is not very well specified and the positions vector
834 * is implementation specific. The undo positions are managed
835 * differently in this implementation, this method is only here
836 * for binary compatibility.
838 protected void updateUndoPositions(Vector positions
, int offset
, int length
)
840 // We do nothing here.
844 * Outputs debugging info to System.err. It prints out the buffer array,
845 * the gapStart is marked by a < sign, the gapEnd is marked by a >
846 * sign and each position is marked by a # sign.
850 System
.err
.println("GapContent debug information");
851 System
.err
.println("buffer length: " + buffer
.length
);
852 System
.err
.println("gap start: " + gapStart
);
853 System
.err
.println("gap end: " + gapEnd
);
854 for (int i
= 0; i
< buffer
.length
; i
++)
857 System
.err
.print('<');
859 System
.err
.print('>');
861 if (!Character
.isISOControl(buffer
[i
]))
862 System
.err
.print(buffer
[i
]);
864 System
.err
.print('.');
866 System
.err
.println();
869 private void dumpPositions()
871 for (Iterator i
= positions
.iterator(); i
.hasNext();)
873 WeakReference r
= (WeakReference
) i
.next();
874 GapContentPosition pos
= (GapContentPosition
) r
.get();
875 System
.err
.println("position at: " + pos
.mark
);
880 * Clears all GC'ed references in the positions array.
882 private void clearPositionReferences()
884 Iterator i
= positions
.iterator();
887 WeakReference r
= (WeakReference
) i
.next();