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 &lt; sign, the gapEnd is marked by a &gt;
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    }