Source for javax.swing.text.GapContent

   1: /* GapContent.java --
   2:    Copyright (C) 2002, 2004, 2005, 2006 Free Software Foundation, Inc.
   3: 
   4: This file is part of GNU Classpath.
   5: 
   6: GNU Classpath is free software; you can redistribute it and/or modify
   7: it under the terms of the GNU General Public License as published by
   8: the Free Software Foundation; either version 2, or (at your option)
   9: any later version.
  10: 
  11: GNU Classpath is distributed in the hope that it will be useful, but
  12: WITHOUT ANY WARRANTY; without even the implied warranty of
  13: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14: General Public License for more details.
  15: 
  16: You should have received a copy of the GNU General Public License
  17: along with GNU Classpath; see the file COPYING.  If not, write to the
  18: Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
  19: 02110-1301 USA.
  20: 
  21: Linking this library statically or dynamically with other modules is
  22: making a combined work based on this library.  Thus, the terms and
  23: conditions of the GNU General Public License cover the whole
  24: combination.
  25: 
  26: As a special exception, the copyright holders of this library give you
  27: permission to link this library with independent modules to produce an
  28: executable, regardless of the license terms of these independent
  29: modules, and to copy and distribute the resulting executable under
  30: terms of your choice, provided that you also meet, for each linked
  31: independent module, the terms and conditions of the license of that
  32: module.  An independent module is a module which is not derived from
  33: or based on this library.  If you modify this library, you may extend
  34: this exception to your version of the library, but you are not
  35: obligated to do so.  If you do not wish to do so, delete this
  36: exception statement from your version. */
  37: 
  38: 
  39: package javax.swing.text;
  40: 
  41: import java.io.Serializable;
  42: import java.lang.ref.ReferenceQueue;
  43: import java.lang.ref.WeakReference;
  44: import java.util.ArrayList;
  45: import java.util.Collections;
  46: import java.util.Iterator;
  47: import java.util.List;
  48: import java.util.Vector;
  49: 
  50: import javax.swing.undo.AbstractUndoableEdit;
  51: import javax.swing.undo.CannotRedoException;
  52: import javax.swing.undo.CannotUndoException;
  53: import javax.swing.undo.UndoableEdit;
  54: 
  55: /**
  56:  * This implementation of {@link AbstractDocument.Content} uses a gapped buffer.
  57:  * This takes advantage of the fact that text area content is mostly inserted
  58:  * sequentially. The buffer is a char array that maintains a gap at the current
  59:  * insertion point. If characters a inserted at gap boundaries, the cost is
  60:  * minimal (simple array access). The array only has to be shifted around when
  61:  * the insertion point moves (then the gap also moves and one array copy is
  62:  * necessary) or when the gap is filled up and the buffer has to be enlarged.
  63:  */
  64: public class GapContent
  65:     implements AbstractDocument.Content, Serializable
  66: {
  67:   
  68:   /**
  69:    * A {@link Position} implementation for <code>GapContent</code>.
  70:    */
  71:   class GapContentPosition
  72:     implements Position
  73:   {
  74: 
  75:     /**
  76:      * The index to the positionMarks array entry, which in turn holds the
  77:      * mark into the buffer array.
  78:      */
  79:     Mark mark;
  80: 
  81:     /**
  82:      * Returns the current offset of this Position within the content.
  83:      * 
  84:      * @return the current offset of this Position within the content.
  85:      */
  86:     public int getOffset()
  87:     {
  88:       return mark.getOffset();
  89:     }
  90:   }
  91: 
  92:   /**
  93:    * Holds a mark into the buffer that is used by GapContentPosition to find
  94:    * the actual offset of the position. This is pulled out of the
  95:    * GapContentPosition object so that the mark and position can be handled
  96:    * independently, and most important, so that the GapContentPosition can
  97:    * be garbage collected while we still hold a reference to the Mark object. 
  98:    */
  99:   private class Mark
 100:     extends WeakReference
 101:   {
 102:     /**
 103:      * The actual mark into the buffer.
 104:      */
 105:     int mark;
 106: 
 107:     /**
 108:      * Creates a new Mark object for the specified offset.
 109:      *
 110:      * @param offset the offset
 111:      */
 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: }