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.Reference;
  43: import java.lang.ref.ReferenceQueue;
  44: import java.lang.ref.WeakReference;
  45: import java.util.ArrayList;
  46: import java.util.Collections;
  47: import java.util.Iterator;
  48: import java.util.List;
  49: import java.util.Set;
  50: import java.util.Vector;
  51: import java.util.WeakHashMap;
  52: 
  53: import javax.swing.undo.AbstractUndoableEdit;
  54: import javax.swing.undo.CannotRedoException;
  55: import javax.swing.undo.CannotUndoException;
  56: import javax.swing.undo.UndoableEdit;
  57: 
  58: /**
  59:  * This implementation of {@link AbstractDocument.Content} uses a gapped buffer.
  60:  * This takes advantage of the fact that text area content is mostly inserted
  61:  * sequentially. The buffer is a char array that maintains a gap at the current
  62:  * insertion point. If characters a inserted at gap boundaries, the cost is
  63:  * minimal (simple array access). The array only has to be shifted around when
  64:  * the insertion point moves (then the gap also moves and one array copy is
  65:  * necessary) or when the gap is filled up and the buffer has to be enlarged.
  66:  */
  67: public class GapContent
  68:     implements AbstractDocument.Content, Serializable
  69: {
  70:   
  71:   /**
  72:    * A {@link Position} implementation for <code>GapContent</code>.
  73:    */
  74:   private class GapContentPosition
  75:     implements Position
  76:   {
  77: 
  78:     /**
  79:      * The index to the positionMarks array entry, which in turn holds the
  80:      * mark into the buffer array.
  81:      */
  82:     Mark mark;
  83: 
  84:     /**
  85:      * Creates a new GapContentPosition object.
  86:      * 
  87:      * @param offset the offset of this Position
  88:      */
  89:     GapContentPosition(int offset)
  90:     {
  91:       // Try to find the mark in the positionMarks array, and store the index
  92:       // to it.
  93:       synchronized (GapContent.this)
  94:         {
  95:           // Try to make space.
  96:           garbageCollect();
  97:           Mark m = new Mark(offset);
  98:           int i = search(marks, m);
  99:           if (i >= 0) // mark found
 100:             {
 101:               m = (Mark) marks.get(i);
 102:             }
 103:           else
 104:             {
 105:               i = -i - 1;
 106:               marks.add(i, m);
 107:             }
 108:           m.refCount++;
 109:           mark = m;
 110:         }
 111: 
 112:       // Register this position in the death queue, so we can cleanup the marks
 113:       // when this position object gets GC'ed.
 114:       new WeakReference(this, queueOfDeath);
 115:     }
 116: 
 117:     /**
 118:      * Returns the current offset of this Position within the content.
 119:      * 
 120:      * @return the current offset of this Position within the content.
 121:      */
 122:     public int getOffset()
 123:     {
 124:       return mark.getOffset();
 125:     }
 126:   }
 127: 
 128:   /**
 129:    * Holds a mark into the buffer that is used by GapContentPosition to find
 130:    * the actual offset of the position. This is pulled out of the
 131:    * GapContentPosition object so that the mark and position can be handled
 132:    * independently, and most important, so that the GapContentPosition can
 133:    * be garbage collected while we still hold a reference to the Mark object. 
 134:    */
 135:   private class Mark
 136:     implements Comparable
 137:   {
 138:     /**
 139:      * The actual mark into the buffer.
 140:      */
 141:     int mark;
 142: 
 143:     /**
 144:      * The number of GapContentPosition object that reference this mark. If
 145:      * it reaches zero, it get's deleted by {@link GapContent#garbageCollect()}.
 146:      */
 147:     int refCount;
 148: 
 149:     /**
 150:      * Creates a new Mark object for the specified offset.
 151:      *
 152:      * @param offset the offset
 153:      */
 154:     Mark(int offset)
 155:     {
 156:       mark = offset;
 157:       if (mark >= gapStart && mark != 0)
 158:         mark += (gapEnd - gapStart);
 159:     }
 160: 
 161:     /**
 162:      * Returns the offset of the mark.
 163:      *
 164:      * @return the offset of the mark
 165:      */
 166:     int getOffset()
 167:     {
 168:       assert mark == 0 || mark < gapStart || mark >= gapEnd :
 169:              "Invalid mark: " + mark + ", gapStart: " + gapStart
 170:              + ", gapEnd: " + gapEnd;
 171: 
 172:       int res = mark;
 173:       if (mark >= gapEnd)
 174:         res -= (gapEnd - gapStart);
 175:       return res;
 176:     }
 177: 
 178:     /**
 179:      * Implementation of Comparable.
 180:      */
 181:     public int compareTo(Object o)
 182:     {
 183:       Mark other = (Mark) o;
 184:       return mark - other.mark;
 185:     }
 186:     /**
 187:      * Adjustment for equals().
 188:      */
 189:     public boolean equals(Object o)
 190:     {
 191:       if (o == null || !(o instanceof Mark))
 192:         return false;
 193:       else
 194:         return ((Mark) o).mark == mark;
 195:     }
 196:   }
 197: 
 198:   private class InsertUndo extends AbstractUndoableEdit
 199:   {
 200:     public int where, length;
 201:     String text;
 202:     public InsertUndo(int start, int len)
 203:     {
 204:       where = start;
 205:       length = len;
 206:     }
 207: 
 208:     public void undo () throws CannotUndoException
 209:     {
 210:       super.undo();
 211:       try
 212:       {
 213:         text = getString(where, length);
 214:         remove(where, length);
 215:       }
 216:       catch (BadLocationException ble)
 217:       {
 218:         throw new CannotUndoException();
 219:       }
 220:     }
 221:     
 222:     public void redo () throws CannotUndoException
 223:     {
 224:       super.redo();
 225:       try
 226:       {
 227:         insertString(where, text);
 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:     public UndoRemove(int start, String removedText)
 242:     {
 243:       where = start;
 244:       text = removedText;
 245:     }
 246: 
 247:     public void undo () throws CannotUndoException
 248:     {
 249:       super.undo();
 250:       try
 251:       {
 252:         insertString(where, text);
 253:       }
 254:       catch (BadLocationException ble)
 255:       {
 256:         throw new CannotUndoException();
 257:       }
 258:     }
 259:     
 260:     public void redo () throws CannotUndoException
 261:     {
 262:       super.redo();
 263:       try
 264:       {
 265:         remove(where, text.length());
 266:       }
 267:       catch (BadLocationException ble)
 268:       {
 269:         throw new CannotRedoException();
 270:       }
 271:     }
 272:     
 273:   }
 274: 
 275:   /** The serialization UID (compatible with JDK1.5). */
 276:   private static final long serialVersionUID = -6226052713477823730L;
 277: 
 278:   /**
 279:    * This is the default buffer size and the amount of bytes that a buffer is
 280:    * extended if it is full.
 281:    */
 282:   static final int DEFAULT_BUFSIZE = 10;
 283: 
 284:   /**
 285:    * The text buffer.
 286:    */
 287:   char[] buffer;
 288: 
 289:   /**
 290:    * The index of the first character of the gap.
 291:    */
 292:   int gapStart;
 293: 
 294:   /**
 295:    * The index of the character after the last character of the gap.
 296:    */
 297:   int gapEnd;
 298: 
 299:   // FIXME: We might want to track GC'ed GapContentPositions and remove their
 300:   // corresponding marks, or alternativly, perform some regular cleanup of
 301:   // the positionMarks array.
 302: 
 303:   /**
 304:    * Holds the marks for positions. These marks are referenced by the
 305:    * GapContentPosition instances by an index into this array.
 306:    *
 307:    * This is package private to avoid accessor synthetic methods.
 308:    */
 309:   ArrayList marks;
 310: 
 311:   WeakHashMap positions;
 312: 
 313:   /**
 314:    * Queues all references to GapContentPositions that are about to be
 315:    * GC'ed. This is used to remove the corresponding marks from the
 316:    * positionMarks array if the number of references to that mark reaches zero.
 317:    *
 318:    * This is package private to avoid accessor synthetic methods.
 319:    */
 320:   ReferenceQueue queueOfDeath;
 321: 
 322:   /**
 323:    * Creates a new GapContent object.
 324:    */
 325:   public GapContent()
 326:   {
 327:     this(DEFAULT_BUFSIZE);
 328:   }
 329: 
 330:   /**
 331:    * Creates a new GapContent object with a specified initial size.
 332:    * 
 333:    * @param size the initial size of the buffer
 334:    */
 335:   public GapContent(int size)
 336:   {
 337:     size = Math.max(size, 2);
 338:     buffer = (char[]) allocateArray(size);
 339:     gapStart = 1;
 340:     gapEnd = size;
 341:     buffer[0] = '\n';
 342:     positions = new WeakHashMap();
 343:     marks = new ArrayList();
 344:     queueOfDeath = new ReferenceQueue();
 345:   }
 346: 
 347:   /**
 348:    * Allocates an array of the specified length that can then be used as
 349:    * buffer.
 350:    * 
 351:    * @param size the size of the array to be allocated
 352:    * 
 353:    * @return the allocated array
 354:    */
 355:   protected Object allocateArray(int size)
 356:   {
 357:     return new char[size];
 358:   }
 359: 
 360:   /**
 361:    * Returns the length of the allocated buffer array.
 362:    * 
 363:    * @return the length of the allocated buffer array
 364:    */
 365:   protected int getArrayLength()
 366:   {
 367:     return buffer.length;
 368:   }
 369: 
 370:   /**
 371:    * Returns the length of the content.
 372:    * 
 373:    * @return the length of the content
 374:    */
 375:   public int length()
 376:   {
 377:     return buffer.length - (gapEnd - gapStart);
 378:   }
 379: 
 380:   /**
 381:    * Inserts a string at the specified position.
 382:    * 
 383:    * @param where the position where the string is inserted
 384:    * @param str the string that is to be inserted
 385:    * 
 386:    * @return an UndoableEdit object
 387:    * 
 388:    * @throws BadLocationException if <code>where</code> is not a valid
 389:    *         location in the buffer
 390:    */
 391:   public UndoableEdit insertString(int where, String str)
 392:       throws BadLocationException
 393:   {
 394:     // check arguments
 395:     int length = length();
 396:     int strLen = str.length();
 397: 
 398:     if (where < 0)
 399:       throw new BadLocationException("The where argument cannot be smaller"
 400:                                      + " than the zero", where);
 401: 
 402:     if (where > length)
 403:       throw new BadLocationException("The where argument cannot be greater"
 404:           + " than the content length", where);
 405: 
 406:     replace(where, 0, str.toCharArray(), strLen);
 407: 
 408:     return new InsertUndo(where, strLen);
 409:   }
 410: 
 411:   /**
 412:    * Removes a piece of content at th specified position.
 413:    * 
 414:    * @param where the position where the content is to be removed
 415:    * @param nitems number of characters to be removed
 416:    * 
 417:    * @return an UndoableEdit object
 418:    * 
 419:    * @throws BadLocationException if <code>where</code> is not a valid
 420:    *         location in the buffer
 421:    */
 422:   public UndoableEdit remove(int where, int nitems) throws BadLocationException
 423:   {
 424:     // check arguments
 425:     int length = length();
 426:     
 427:     if ((where + nitems) >= length)
 428:       throw new BadLocationException("where + nitems cannot be greater"
 429:           + " than the content length", where + nitems);
 430:     
 431:     String removedText = getString(where, nitems);
 432:     replace(where, nitems, null, 0);
 433: 
 434:     return new UndoRemove(where, removedText);
 435:   }
 436: 
 437:   /**
 438:    * Returns a piece of content as String.
 439:    * 
 440:    * @param where the start location of the fragment
 441:    * @param len the length of the fragment
 442:    * 
 443:    * @throws BadLocationException if <code>where</code> or
 444:    *         <code>where + len</code> are no valid locations in the buffer
 445:    */
 446:   public String getString(int where, int len) throws BadLocationException
 447:   {
 448:     Segment seg = new Segment();
 449:     try
 450:       {
 451:         getChars(where, len, seg);
 452:         return new String(seg.array, seg.offset, seg.count);
 453:       }
 454:     catch (StringIndexOutOfBoundsException ex)
 455:       {
 456:         int invalid = 0;
 457:         if (seg.offset < 0 || seg.offset >= seg.array.length)
 458:           invalid = seg.offset;
 459:         else
 460:           invalid = seg.offset + seg.count;
 461:         throw new BadLocationException("Illegal location: array.length = "
 462:                                        + seg.array.length + ", offset = "
 463:                                        + seg.offset + ", count = "
 464:                                        + seg.count, invalid);
 465:       }
 466:   }
 467: 
 468:   /**
 469:    * Fetches a piece of content and stores it in a {@link Segment} object.
 470:    * 
 471:    * If the requested piece of text spans the gap, the content is copied into a
 472:    * new array. If it doesn't then it is contiguous and the actual content
 473:    * store is returned.
 474:    * 
 475:    * @param where the start location of the fragment
 476:    * @param len the length of the fragment
 477:    * @param txt the Segment object to store the fragment in
 478:    * 
 479:    * @throws BadLocationException if <code>where</code> or
 480:    *         <code>where + len</code> are no valid locations in the buffer
 481:    */
 482:   public void getChars(int where, int len, Segment txt)
 483:       throws BadLocationException
 484:   {
 485:     // check arguments
 486:     int length = length();
 487:     if (where < 0)
 488:       throw new BadLocationException("the where argument may not be below zero", where);
 489:     if (where >= length)
 490:       throw new BadLocationException("the where argument cannot be greater"
 491:           + " than the content length", where);
 492:     if ((where + len) > length)
 493:       throw new BadLocationException("len plus where cannot be greater"
 494:           + " than the content length", len + where);
 495:     if (len < 0)
 496:       throw new BadLocationException("negative length not allowed: ", len);
 497: 
 498:     // check if requested segment is contiguous
 499:     if ((where < gapStart) && ((gapStart - where) < len))
 500:     {
 501:       // requested segment is not contiguous -> copy the pieces together
 502:       char[] copy = new char[len];
 503:       int lenFirst = gapStart - where; // the length of the first segment
 504:       System.arraycopy(buffer, where, copy, 0, lenFirst);
 505:       System.arraycopy(buffer, gapEnd, copy, lenFirst, len - lenFirst);
 506:       txt.array = copy;
 507:       txt.offset = 0;
 508:       txt.count = len;
 509:     }
 510:     else
 511:     {
 512:       // requested segment is contiguous -> we can simply return the
 513:       // actual content
 514:       txt.array = buffer;
 515:       if (where < gapStart)
 516:         txt.offset = where;
 517:       else
 518:         txt.offset = where + (gapEnd - gapStart);
 519:       txt.count = len;
 520:     }
 521:   }
 522: 
 523:   /**
 524:    * Creates and returns a mark at the specified position.
 525:    * 
 526:    * @param offset the position at which to create the mark
 527:    * 
 528:    * @return the create Position object for the mark
 529:    * 
 530:    * @throws BadLocationException if the offset is not a valid position in the
 531:    *         buffer
 532:    */
 533:   public Position createPosition(final int offset) throws BadLocationException
 534:   {
 535:     // Implementation note: We used to perform explicit check on the offset
 536:     // here. However, this makes some Mauve and Intel/Harmony tests fail
 537:     // and luckily enough the GapContent can very well deal with offsets
 538:     // outside the buffer bounds. So I removed that check.
 539: 
 540:     // We try to find a GapContentPosition at the specified offset and return
 541:     // that. Otherwise we must create a new one.
 542:     GapContentPosition pos = null;
 543:     Set positionSet = positions.keySet();
 544:     for (Iterator i = positionSet.iterator(); i.hasNext();)
 545:       {
 546:         GapContentPosition p = (GapContentPosition) i.next();
 547:         if (p.getOffset() == offset)
 548:           {
 549:             pos = p;
 550:             break;
 551:           }
 552:       }
 553: 
 554:     // If none was found, then create and return a new one.
 555:     if (pos == null)
 556:       {
 557:         pos = new GapContentPosition(offset);
 558:         positions.put(pos, null);
 559:       }
 560: 
 561:     return pos;
 562:   }
 563: 
 564:   /**
 565:    * Enlarges the gap. This allocates a new bigger buffer array, copy the
 566:    * segment before the gap as it is and the segment after the gap at the end
 567:    * of the new buffer array. This does change the gapEnd mark but not the
 568:    * gapStart mark.
 569:    * 
 570:    * @param newSize the new size of the gap
 571:    */
 572:   protected void shiftEnd(int newSize)
 573:   {
 574:     assert newSize > (gapEnd - gapStart) : "The new gap size must be greater "
 575:                                            + "than the old gap size";
 576: 
 577:     int delta = newSize - gapEnd + gapStart;
 578:     // Update the marks after the gapEnd.
 579:     adjustPositionsInRange(gapEnd, -1, delta);
 580: 
 581:     // Copy the data around.
 582:     char[] newBuf = (char[]) allocateArray(length() + newSize);
 583:     System.arraycopy(buffer, 0, newBuf, 0, gapStart);
 584:     System.arraycopy(buffer, gapEnd, newBuf, gapStart + newSize, buffer.length
 585:         - gapEnd);
 586:     gapEnd = gapStart + newSize;
 587:     buffer = newBuf;
 588: 
 589:   }
 590: 
 591:   /**
 592:    * Shifts the gap to the specified position.
 593:    * 
 594:    * @param newGapStart the new start position of the gap
 595:    */
 596:   protected void shiftGap(int newGapStart)
 597:   {
 598:     if (newGapStart == gapStart)
 599:       return;
 600:     int newGapEnd = newGapStart + gapEnd - gapStart;
 601:     if (newGapStart < gapStart)
 602:       {
 603:         // Update the positions between newGapStart and (old) gapStart. The marks
 604:         // must be shifted by (gapEnd - gapStart).
 605:         adjustPositionsInRange(newGapStart, gapStart, gapEnd - gapStart);
 606:         System.arraycopy(buffer, newGapStart, buffer, newGapEnd, gapStart
 607:                          - newGapStart);
 608:         gapStart = newGapStart;
 609:         gapEnd = newGapEnd;
 610:       }
 611:     else
 612:       {
 613:         // Update the positions between newGapEnd and (old) gapEnd. The marks
 614:         // must be shifted by (gapEnd - gapStart).
 615:         adjustPositionsInRange(gapEnd, newGapEnd, -(gapEnd - gapStart));
 616:         System.arraycopy(buffer, gapEnd, buffer, gapStart, newGapStart
 617:                          - gapStart);
 618:         gapStart = newGapStart;
 619:         gapEnd = newGapEnd;
 620:       }
 621:     resetMarksAtZero();
 622:   }
 623: 
 624:   /**
 625:    * Shifts the gap start downwards. This does not affect the content of the
 626:    * buffer. This only updates the gap start and all the marks that are between
 627:    * the old gap start and the new gap start. They all are squeezed to the start
 628:    * of the gap, because their location has been removed.
 629:    *
 630:    * @param newGapStart the new gap start
 631:    */
 632:   protected void shiftGapStartDown(int newGapStart)
 633:   {
 634:     if (newGapStart == gapStart)
 635:       return;
 636: 
 637:     assert newGapStart < gapStart : "The new gap start must be less than the "
 638:                                     + "old gap start.";
 639:     setPositionsInRange(newGapStart, gapStart, false);
 640:     gapStart = newGapStart;
 641:     resetMarksAtZero();
 642:   }
 643: 
 644:   /**
 645:    * Shifts the gap end upwards. This does not affect the content of the
 646:    * buffer. This only updates the gap end and all the marks that are between
 647:    * the old gap end and the new end start. They all are squeezed to the end
 648:    * of the gap, because their location has been removed.
 649:    *
 650:    * @param newGapEnd the new gap start
 651:    */
 652:   protected void shiftGapEndUp(int newGapEnd)
 653:   {
 654:     if (newGapEnd == gapEnd)
 655:       return;
 656: 
 657:     assert newGapEnd > gapEnd : "The new gap end must be greater than the "
 658:                                 + "old gap end.";
 659:     setPositionsInRange(gapEnd, newGapEnd, false);
 660:     gapEnd = newGapEnd;
 661:     resetMarksAtZero();
 662:   }
 663: 
 664:   /**
 665:    * Returns the allocated buffer array.
 666:    * 
 667:    * @return the allocated buffer array
 668:    */
 669:   protected final Object getArray()
 670:   {
 671:     return buffer;
 672:   }
 673: 
 674:   /**
 675:    * Replaces a portion of the storage with the specified items.
 676:    * 
 677:    * @param position the position at which to remove items
 678:    * @param rmSize the number of items to remove
 679:    * @param addItems the items to add at location
 680:    * @param addSize the number of items to add
 681:    */
 682:   protected void replace(int position, int rmSize, Object addItems,
 683:                          int addSize)
 684:   {
 685:     if (gapStart != position)
 686:       shiftGap(position);
 687:       
 688:     // Remove content
 689:     if (rmSize > 0) 
 690:       shiftGapEndUp(gapEnd + rmSize);
 691: 
 692:     // If gap is too small, enlarge the gap.
 693:     if ((gapEnd - gapStart) <= addSize)
 694:       shiftEnd((addSize - gapEnd + gapStart + 1) * 2 + gapEnd + DEFAULT_BUFSIZE);
 695: 
 696:     // Add new items to the buffer.
 697:     if (addItems != null)
 698:       {
 699:         System.arraycopy(addItems, 0, buffer, gapStart, addSize);
 700:         gapStart += addSize;
 701:       }
 702:   }
 703: 
 704:   /**
 705:    * Returns the start index of the gap within the buffer array.
 706:    *
 707:    * @return the start index of the gap within the buffer array
 708:    */
 709:   protected final int getGapStart()
 710:   {
 711:     return gapStart;
 712:   }
 713: 
 714:   /**
 715:    * Returns the end index of the gap within the buffer array.
 716:    *
 717:    * @return the end index of the gap within the buffer array
 718:    */
 719:   protected final int getGapEnd()
 720:   {
 721:     return gapEnd;
 722:   }
 723: 
 724:   /**
 725:    * Returns all <code>Position</code>s that are in the range specified by
 726:    * <code>offset</code> and </code>length</code> within the buffer array.
 727:    *
 728:    * @param v the vector to use; if <code>null</code>, a new Vector is allocated
 729:    * @param offset the start offset of the range to search
 730:    * @param length the length of the range to search
 731:    *
 732:    * @return the positions within the specified range
 733:    */
 734:   protected Vector getPositionsInRange(Vector v, int offset, int length)
 735:   {
 736:     Vector res = v;
 737:     if (res == null)
 738:       res = new Vector();
 739:     else
 740:       res.clear();
 741: 
 742:     int endOffs = offset + length;
 743: 
 744:     Set positionSet = positions.keySet();
 745:     for (Iterator i = positionSet.iterator(); i.hasNext();)
 746:       {
 747:         GapContentPosition p = (GapContentPosition) i.next();
 748:         int offs = p.getOffset();
 749:         if (offs >= offset && offs < endOffs)
 750:           res.add(p);
 751:       }
 752: 
 753:     return res;
 754:   }
 755:   
 756:   /**
 757:    * Crunches all positions in the specified range to either the start or
 758:    * end of that interval. The interval boundaries are meant to be inclusive
 759:    * [start, end].
 760:    *
 761:    * @param start the start offset of the range
 762:    * @param end the end offset of the range
 763:    * @param toStart a boolean indicating if the positions should be crunched
 764:    *        to the start (true) or to the end (false)
 765:    */
 766:   private void setPositionsInRange(int start, int end, boolean toStart)
 767:   {
 768:     synchronized (this)
 769:       {
 770:         // Find the start and end indices in the positionMarks array.
 771:         Mark m = new Mark(0); // For comparison / search only.
 772:         m.mark = start;
 773:         int startIndex = search(marks, m);
 774:         if (startIndex < 0) // Translate to insertion index, if not found.
 775:           startIndex = - startIndex - 1;
 776:         m.mark = end;
 777:         int endIndex = search(marks, m);
 778:         if (endIndex < 0) // Translate to insertion index - 1, if not found.
 779:           endIndex = - endIndex - 2;
 780: 
 781:         // Actually adjust the marks.
 782:         for (int i = startIndex; i <= endIndex; i++)
 783:           ((Mark) marks.get(i)).mark = toStart ? start : end;
 784:       }
 785: 
 786:   }
 787: 
 788:   /**
 789:    * Adjusts the mark of all <code>Position</code>s that are in the range 
 790:    * specified by <code>offset</code> and </code>length</code> within 
 791:    * the buffer array by <code>increment</code>
 792:    *
 793:    * @param startOffs the start offset of the range to search
 794:    * @param endOffs the length of the range to search, -1 means all to the end
 795:    * @param incr the increment
 796:    */
 797:   private void adjustPositionsInRange(int startOffs, int endOffs, int incr)
 798:   {
 799:     synchronized (this)
 800:       {
 801:         // Find the start and end indices in the positionMarks array.
 802:         Mark m = new Mark(0); // For comparison / search only.
 803: 
 804:         m.mark = startOffs;
 805:         int startIndex = search(marks, m);
 806:         if (startIndex < 0) // Translate to insertion index, if not found.
 807:           startIndex = - startIndex - 1;
 808: 
 809:         m.mark = endOffs;
 810:         int endIndex;
 811:         if (endOffs == -1)
 812:           endIndex = marks.size() - 1;
 813:         else
 814:           {
 815:             endIndex = search(marks, m);
 816:             if (endIndex < 0) // Translate to insertion index - 1, if not found.
 817:               endIndex = - endIndex - 2;
 818:           }
 819:         // Actually adjust the marks.
 820:         for (int i = startIndex; i <= endIndex; i++) {
 821:           ((Mark) marks.get(i)).mark += incr;
 822:         }
 823:       }
 824: 
 825:   }
 826: 
 827:   /**
 828:    * Resets all <code>Position</code> that have an offset of <code>0</code>,
 829:    * to also have an array index of <code>0</code>. This might be necessary
 830:    * after a call to <code>shiftGap(0)</code>, since then the marks at offset
 831:    * <code>0</code> get shifted to <code>gapEnd</code>.
 832:    */
 833:   protected void resetMarksAtZero()
 834:   {
 835:     if (gapStart != 0)
 836:       return;
 837: 
 838:     for (int i = 0; i < marks.size(); i++)
 839:       {
 840:         Mark m = (Mark) marks.get(i);
 841:         if (m.mark <= gapEnd)
 842:           m.mark = 0;
 843:       }
 844:   }
 845: 
 846:   /**
 847:    * @specnote This method is not very well specified and the positions vector
 848:    *           is implementation specific. The undo positions are managed
 849:    *           differently in this implementation, this method is only here
 850:    *           for binary compatibility.
 851:    */
 852:   protected void updateUndoPositions(Vector positions, int offset, int length)
 853:   {
 854:     // We do nothing here.
 855:   }
 856: 
 857:   /**
 858:    * Outputs debugging info to System.err. It prints out the buffer array,
 859:    * the gapStart is marked by a &lt; sign, the gapEnd is marked by a &gt;
 860:    * sign and each position is marked by a # sign.
 861:    */
 862:   private void dump()
 863:   {
 864:     System.err.println("GapContent debug information");
 865:     System.err.println("buffer length: " + buffer.length);
 866:     System.err.println("gap start: " + gapStart);
 867:     System.err.println("gap end: " + gapEnd);
 868:     for (int i = 0; i < buffer.length; i++)
 869:       {
 870:         if (i == gapStart)
 871:           System.err.print('<');
 872:         if (i == gapEnd)
 873:           System.err.print('>');
 874: 
 875:         if (!Character.isISOControl(buffer[i]))
 876:           System.err.print(buffer[i]);
 877:         else
 878:           System.err.print('.');
 879:       }
 880:     System.err.println();
 881:   }
 882: 
 883:   /**
 884:    * Prints out the position marks.
 885:    */
 886:   private void dumpMarks()
 887:   {
 888:     System.out.print("positionMarks: ");
 889:     for (int i = 0; i < marks.size(); i++)
 890:       System.out.print(((Mark) marks.get(i)).mark + ", ");
 891:     System.out.println();
 892:   }
 893: 
 894:   /**
 895:    * Polls the queue of death for GapContentPositions, updates the
 896:    * corresponding reference count and removes the corresponding mark
 897:    * if the refcount reaches zero.
 898:    *
 899:    * This is package private to avoid accessor synthetic methods.
 900:    */
 901:   void garbageCollect()
 902:   {
 903:     Reference ref = queueOfDeath.poll();
 904:     while (ref != null)
 905:       {
 906:         if (ref != null)
 907:           {
 908:             GapContentPosition pos = (GapContentPosition) ref.get();
 909:             Mark m = pos.mark;
 910:             m.refCount--;
 911:             if (m.refCount == 0)
 912:               marks.remove(m);
 913:           }
 914:         ref = queueOfDeath.poll();
 915:       }
 916:   }
 917: 
 918:   /**
 919:    * Searches the first occurance of object <code>o</code> in list
 920:    * <code>l</code>. This performs a binary search by calling
 921:    * {@link Collections#binarySearch(List, Object)} and when an object has been
 922:    * found, it searches backwards to the first occurance of that object in the
 923:    * list. The meaning of the return value is the same as in
 924:    * <code>Collections.binarySearch()</code>.
 925:    *
 926:    * @param l the list to search through
 927:    * @param o the object to be searched
 928:    *
 929:    * @return the index of the first occurance of o in l, or -i + 1 if not found
 930:    */
 931:   private int search(List l, Object o)
 932:   {
 933:     int i = Collections.binarySearch(l, o);
 934:     while (i > 0)
 935:       {
 936:         Object o2 = l.get(i - 1);
 937:         if (o2.equals(o))
 938:           i--;
 939:         else
 940:           break;
 941:       }
 942:     return i;
 943:   }
 944: }