001/* GapContent.java --
002   Copyright (C) 2002, 2004, 2005, 2006 Free Software Foundation, Inc.
003
004This file is part of GNU Classpath.
005
006GNU Classpath is free software; you can redistribute it and/or modify
007it under the terms of the GNU General Public License as published by
008the Free Software Foundation; either version 2, or (at your option)
009any later version.
010
011GNU Classpath is distributed in the hope that it will be useful, but
012WITHOUT ANY WARRANTY; without even the implied warranty of
013MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
014General Public License for more details.
015
016You should have received a copy of the GNU General Public License
017along with GNU Classpath; see the file COPYING.  If not, write to the
018Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
01902110-1301 USA.
020
021Linking this library statically or dynamically with other modules is
022making a combined work based on this library.  Thus, the terms and
023conditions of the GNU General Public License cover the whole
024combination.
025
026As a special exception, the copyright holders of this library give you
027permission to link this library with independent modules to produce an
028executable, regardless of the license terms of these independent
029modules, and to copy and distribute the resulting executable under
030terms of your choice, provided that you also meet, for each linked
031independent module, the terms and conditions of the license of that
032module.  An independent module is a module which is not derived from
033or based on this library.  If you modify this library, you may extend
034this exception to your version of the library, but you are not
035obligated to do so.  If you do not wish to do so, delete this
036exception statement from your version. */
037
038
039package javax.swing.text;
040
041import java.io.Serializable;
042import java.lang.ref.ReferenceQueue;
043import java.lang.ref.WeakReference;
044import java.util.ArrayList;
045import java.util.Collections;
046import java.util.Iterator;
047import java.util.List;
048import java.util.Vector;
049
050import javax.swing.undo.AbstractUndoableEdit;
051import javax.swing.undo.CannotRedoException;
052import javax.swing.undo.CannotUndoException;
053import 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 */
064public 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}