libjava/classpath/javax/swing/text/GapContent.java

   1 /* GapContent.java --
   2    Copyright (C) 2002, 2004, 2005 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.util.ArrayList;
  43 import java.util.Collections;
  44 import java.util.Iterator;
  45 import java.util.ListIterator;
  46 import java.util.Vector;
  47
  48 import javax.swing.undo.AbstractUndoableEdit;
  49 import javax.swing.undo.CannotRedoException;
  50 import javax.swing.undo.CannotUndoException;
  51 import javax.swing.undo.UndoableEdit;
  52
  53 /**
  54  * This implementation of {@link AbstractDocument.Content} uses a gapped buffer.
  55  * This takes advantage of the fact that text area content is mostly inserted
  56  * sequentially. The buffer is a char array that maintains a gap at the current
  57  * insertion point. If characters a inserted at gap boundaries, the cost is
  58  * minimal (simple array access). The array only has to be shifted around when
  59  * the insertion point moves (then the gap also moves and one array copy is
  60  * necessary) or when the gap is filled up and the buffer has to be enlarged.
  61  *
  62  * TODO: Implement UndoableEdit support stuff
  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, Comparable
  73   {
  74
  75     /** The index within the buffer array. */
  76     int mark;
  77
  78     /**
  79      * Creates a new GapContentPosition object.
  80      *
  81      * @param mark the mark of this Position
  82      */
  83     GapContentPosition(int mark)
  84     {
  85       this.mark = mark;
  86     }
  87
  88     /**
  89      * Comparable interface implementation. This is used to store all
  90      * positions in an ordered fashion.
  91      *
  92      * @param o the object to be compared to this
  93      *
  94      * @return a negative integer if this is less than <code>o</code>, zero
  95      *         if both are equal or a positive integer if this is greater than
  96      *         <code>o</code>
  97      *
  98      * @throws ClassCastException if <code>o</code> is not a
  99      *         GapContentPosition or Integer object
 100      */
 101     public int compareTo(Object o)
 102     {
 103       if (o instanceof Integer)
 104         {
 105           int otherMark = ((Integer) o).intValue();
 106           return mark - otherMark;
 107         }
 108       else
 109         {
 110           GapContentPosition other = (GapContentPosition) o;
 111           return mark - other.mark;
 112         }
 113     }
 114
 115     /**
 116      * Returns the current offset of this Position within the content.
 117      *
 118      * @return the current offset of this Position within the content.
 119      */
 120     public int getOffset()
 121     {
 122       // Check precondition.
 123       assert mark <= gapStart || mark >= gapEnd : "mark: " + mark
 124                                                + ", gapStart: " + gapStart
 125                                                + ", gapEnd: " + gapEnd;
 126       if (mark <= gapStart)
 127         return mark;
 128       else
 129         return mark - (gapEnd - gapStart);
 130     }
 131   }
 132
 133   class InsertUndo extends AbstractUndoableEdit
 134   {
 135     public int where, length;
 136     String text;
 137     public InsertUndo(int start, int len)
 138     {
 139       where = start;
 140       length = len;
 141     }
 142
 143     public void undo () throws CannotUndoException
 144     {
 145       super.undo();
 146       try
 147       {
 148         text = getString(where, length);
 149         remove(where, length);
 150       }
 151       catch (BadLocationException ble)
 152       {
 153         throw new CannotUndoException();
 154       }
 155     }
 156
 157     public void redo () throws CannotUndoException
 158     {
 159       super.redo();
 160       try
 161       {
 162         insertString(where, text);
 163       }
 164       catch (BadLocationException ble)
 165       {
 166         throw new CannotRedoException();
 167       }
 168     }
 169
 170   }
 171
 172   class UndoRemove extends AbstractUndoableEdit
 173   {
 174     public int where;
 175     String text;
 176     public UndoRemove(int start, String removedText)
 177     {
 178       where = start;
 179       text = removedText;
 180     }
 181
 182     public void undo () throws CannotUndoException
 183     {
 184       super.undo();
 185       try
 186       {
 187         insertString(where, text);
 188       }
 189       catch (BadLocationException ble)
 190       {
 191         throw new CannotUndoException();
 192       }
 193     }
 194
 195     public void redo () throws CannotUndoException
 196     {
 197       super.redo();
 198       try
 199       {
 200         remove(where, text.length());
 201       }
 202       catch (BadLocationException ble)
 203       {
 204         throw new CannotRedoException();
 205       }
 206     }
 207
 208   }
 209
 210   /** The serialization UID (compatible with JDK1.5). */
 211   private static final long serialVersionUID = -6226052713477823730L;
 212
 213   /**
 214    * This is the default buffer size and the amount of bytes that a buffer is
 215    * extended if it is full.
 216    */
 217   static final int DEFAULT_BUFSIZE = 10;
 218
 219   /**
 220    * The text buffer.
 221    */
 222   char[] buffer;
 223
 224   /**
 225    * The index of the first character of the gap.
 226    */
 227   int gapStart;
 228
 229   /**
 230    * The index of the character after the last character of the gap.
 231    */
 232   int gapEnd;
 233
 234   /**
 235    * The positions generated by this GapContent. They are kept in an ordered
 236    * fashion, so they can be looked up easily.
 237    */
 238   ArrayList positions;
 239
 240   /**
 241    * Creates a new GapContent object.
 242    */
 243   public GapContent()
 244   {
 245     this(DEFAULT_BUFSIZE);
 246   }
 247
 248   /**
 249    * Creates a new GapContent object with a specified initial size.
 250    *
 251    * @param size the initial size of the buffer
 252    */
 253   public GapContent(int size)
 254   {
 255     buffer = (char[]) allocateArray(size);
 256     gapStart = 1;
 257     gapEnd = size;
 258     buffer[0] = '\n';
 259     positions = new ArrayList();
 260   }
 261
 262   /**
 263    * Allocates an array of the specified length that can then be used as
 264    * buffer.
 265    *
 266    * @param size the size of the array to be allocated
 267    *
 268    * @return the allocated array
 269    */
 270   protected Object allocateArray(int size)
 271   {
 272     return new char[size];
 273   }
 274
 275   /**
 276    * Returns the length of the allocated buffer array.
 277    *
 278    * @return the length of the allocated buffer array
 279    */
 280   protected int getArrayLength()
 281   {
 282     return buffer.length;
 283   }
 284
 285   /**
 286    * Returns the length of the content.
 287    *
 288    * @return the length of the content
 289    */
 290   public int length()
 291   {
 292     return buffer.length - (gapEnd - gapStart);
 293   }
 294
 295   /**
 296    * Inserts a string at the specified position.
 297    *
 298    * @param where the position where the string is inserted
 299    * @param str the string that is to be inserted
 300    *
 301    * @return an UndoableEdit object
 302    *
 303    * @throws BadLocationException if <code>where</code> is not a valid
 304    *         location in the buffer
 305    */
 306   public UndoableEdit insertString(int where, String str)
 307       throws BadLocationException
 308   {
 309     // check arguments
 310     int length = length();
 311     int strLen = str.length();
 312
 313     if (where >= length)
 314       throw new BadLocationException("the where argument cannot be greater"
 315           + " than the content length", where);
 316
 317     replace(where, 0, str.toCharArray(), strLen);
 318
 319     return new InsertUndo(where, strLen);
 320   }
 321
 322   /**
 323    * Removes a piece of content at th specified position.
 324    *
 325    * @param where the position where the content is to be removed
 326    * @param nitems number of characters to be removed
 327    *
 328    * @return an UndoableEdit object
 329    *
 330    * @throws BadLocationException if <code>where</code> is not a valid
 331    *         location in the buffer
 332    */
 333   public UndoableEdit remove(int where, int nitems) throws BadLocationException
 334   {
 335     // check arguments
 336     int length = length();
 337
 338     if (where >= length)
 339       throw new BadLocationException("the where argument cannot be greater"
 340           + " than the content length", where);
 341     if ((where + nitems) > length)
 342       throw new BadLocationException("where + nitems cannot be greater"
 343           + " than the content length", where + nitems);
 344
 345     String removedText = getString(where, nitems);
 346     replace(where, nitems, null, 0);
 347
 348     return new UndoRemove(where, removedText);
 349   }
 350
 351   /**
 352    * Returns a piece of content as String.
 353    *
 354    * @param where the start location of the fragment
 355    * @param len the length of the fragment
 356    *
 357    * @throws BadLocationException if <code>where</code> or
 358    *         <code>where + len</code> are no valid locations in the buffer
 359    */
 360   public String getString(int where, int len) throws BadLocationException
 361   {
 362     Segment seg = new Segment();
 363     try
 364       {
 365         getChars(where, len, seg);
 366         return new String(seg.array, seg.offset, seg.count);
 367       }
 368     catch (StringIndexOutOfBoundsException ex)
 369       {
 370         int invalid = 0;
 371         if (seg.offset < 0 || seg.offset >= seg.array.length)
 372           invalid = seg.offset;
 373         else
 374           invalid = seg.offset + seg.count;
 375         throw new BadLocationException("Illegal location: array.length = "
 376                                        + seg.array.length + ", offset = "
 377                                        + seg.offset + ", count = "
 378                                        + seg.count, invalid);
 379       }
 380   }
 381
 382   /**
 383    * Fetches a piece of content and stores it in a {@link Segment} object.
 384    *
 385    * If the requested piece of text spans the gap, the content is copied into a
 386    * new array. If it doesn't then it is contiguous and the actual content
 387    * store is returned.
 388    *
 389    * @param where the start location of the fragment
 390    * @param len the length of the fragment
 391    * @param txt the Segment object to store the fragment in
 392    *
 393    * @throws BadLocationException if <code>where</code> or
 394    *         <code>where + len</code> are no valid locations in the buffer
 395    */
 396   public void getChars(int where, int len, Segment txt)
 397       throws BadLocationException
 398   {
 399     // check arguments
 400     int length = length();
 401     if (where >= length)
 402       throw new BadLocationException("the where argument cannot be greater"
 403           + " than the content length", where);
 404     if ((where + len) > length)
 405       throw new BadLocationException("len plus where cannot be greater"
 406           + " than the content length", len + where);
 407
 408     // check if requested segment is contiguous
 409     if ((where < gapStart) && ((gapStart - where) < len))
 410     {
 411       // requested segment is not contiguous -> copy the pieces together
 412       char[] copy = new char[len];
 413       int lenFirst = gapStart - where; // the length of the first segment
 414       System.arraycopy(buffer, where, copy, 0, lenFirst);
 415       System.arraycopy(buffer, gapEnd, copy, lenFirst, len - lenFirst);
 416       txt.array = copy;
 417       txt.offset = 0;
 418       txt.count = len;
 419     }
 420     else
 421     {
 422       // requested segment is contiguous -> we can simply return the
 423       // actual content
 424       txt.array = buffer;
 425       if (where < gapStart)
 426         txt.offset = where;
 427       else
 428         txt.offset = where + (gapEnd - gapStart);
 429       txt.count = len;
 430     }
 431   }
 432
 433   /**
 434    * Creates and returns a mark at the specified position.
 435    *
 436    * @param offset the position at which to create the mark
 437    *
 438    * @return the create Position object for the mark
 439    *
 440    * @throws BadLocationException if the offset is not a valid position in the
 441    *         buffer
 442    */
 443   public Position createPosition(final int offset) throws BadLocationException
 444   {
 445     if (offset < 0 || offset > length())
 446       throw new BadLocationException("The offset was out of the bounds of this"
 447           + " buffer", offset);
 448
 449     // We store the actual array index in the GapContentPosition. The real
 450     // offset is then calculated in the GapContentPosition.
 451     int mark = offset;
 452     if (offset >= gapStart)
 453       mark += gapEnd - gapStart;
 454     GapContentPosition pos = new GapContentPosition(mark);
 455
 456     // Add this into our list in a sorted fashion.
 457     int index = Collections.binarySearch(positions, pos);
 458     if (index < 0)
 459       index = -(index + 1);
 460     positions.add(index, pos);
 461     return pos;
 462   }
 463
 464   /**
 465    * Enlarges the gap. This allocates a new bigger buffer array, copy the
 466    * segment before the gap as it is and the segment after the gap at the end
 467    * of the new buffer array. This does change the gapEnd mark but not the
 468    * gapStart mark.
 469    *
 470    * @param newSize the new size of the gap
 471    */
 472   protected void shiftEnd(int newSize)
 473   {
 474     assert newSize > (gapEnd - gapStart) : "The new gap size must be greater "
 475                                            + "than the old gap size";
 476
 477     int delta = newSize - gapEnd + gapStart;
 478     // Update the marks after the gapEnd.
 479     adjustPositionsInRange(gapEnd, buffer.length - gapEnd, delta);
 480
 481     // Copy the data around.
 482     char[] newBuf = (char[]) allocateArray(length() + newSize);
 483     System.arraycopy(buffer, 0, newBuf, 0, gapStart);
 484     System.arraycopy(buffer, gapEnd, newBuf, gapStart + newSize, buffer.length
 485         - gapEnd);
 486     gapEnd = gapStart + newSize;
 487     buffer = newBuf;
 488
 489   }
 490
 491   /**
 492    * Shifts the gap to the specified position.
 493    *
 494    * @param newGapStart the new start position of the gap
 495    */
 496   protected void shiftGap(int newGapStart)
 497   {
 498     if (newGapStart == gapStart)
 499       return;
 500
 501     int newGapEnd = newGapStart + gapEnd - gapStart;
 502     if (newGapStart < gapStart)
 503       {
 504         // Update the positions between newGapStart and (old) gapStart. The marks
 505         // must be shifted by (gapEnd - gapStart).
 506         adjustPositionsInRange(newGapStart, gapStart - newGapStart, gapEnd - gapStart);
 507         System.arraycopy(buffer, newGapStart, buffer, newGapEnd, gapStart
 508                          - newGapStart);
 509         gapStart = newGapStart;
 510         gapEnd = newGapEnd;
 511       }
 512     else
 513       {
 514         // Update the positions between newGapEnd and (old) gapEnd. The marks
 515         // must be shifted by (gapEnd - gapStart).
 516         adjustPositionsInRange(gapEnd, newGapEnd - gapEnd, -(gapEnd - gapStart));
 517         System.arraycopy(buffer, gapEnd, buffer, gapStart, newGapStart
 518                          - gapStart);
 519         gapStart = newGapStart;
 520         gapEnd = newGapEnd;
 521       }
 522     if (gapStart == 0)
 523       resetMarksAtZero();
 524   }
 525
 526   /**
 527    * Shifts the gap start downwards. This does not affect the content of the
 528    * buffer. This only updates the gap start and all the marks that are between
 529    * the old gap start and the new gap start. They all are squeezed to the start
 530    * of the gap, because their location has been removed.
 531    *
 532    * @param newGapStart the new gap start
 533    */
 534   protected void shiftGapStartDown(int newGapStart)
 535   {
 536     if (newGapStart == gapStart)
 537       return;
 538
 539     assert newGapStart < gapStart : "The new gap start must be less than the "
 540                                     + "old gap start.";
 541     setPositionsInRange(newGapStart, gapStart - newGapStart, gapStart);
 542     gapStart = newGapStart;
 543   }
 544
 545   /**
 546    * Shifts the gap end upwards. This does not affect the content of the
 547    * buffer. This only updates the gap end and all the marks that are between
 548    * the old gap end and the new end start. They all are squeezed to the end
 549    * of the gap, because their location has been removed.
 550    *
 551    * @param newGapEnd the new gap start
 552    */
 553   protected void shiftGapEndUp(int newGapEnd)
 554   {
 555     if (newGapEnd == gapEnd)
 556       return;
 557
 558     assert newGapEnd > gapEnd : "The new gap end must be greater than the "
 559                                 + "old gap end.";
 560     setPositionsInRange(gapEnd, newGapEnd - gapEnd, newGapEnd + 1);
 561     gapEnd = newGapEnd;
 562   }
 563
 564   /**
 565    * Returns the allocated buffer array.
 566    *
 567    * @return the allocated buffer array
 568    */
 569   protected Object getArray()
 570   {
 571     return buffer;
 572   }
 573
 574   /**
 575    * Replaces a portion of the storage with the specified items.
 576    *
 577    * @param position the position at which to remove items
 578    * @param rmSize the number of items to remove
 579    * @param addItems the items to add at location
 580    * @param addSize the number of items to add
 581    */
 582   protected void replace(int position, int rmSize, Object addItems,
 583                          int addSize)
 584   {
 585     if (gapStart != position)
 586       shiftGap(position);
 587
 588     // Remove content
 589     if (rmSize > 0)
 590       shiftGapEndUp(gapEnd + rmSize);
 591
 592     // If gap is too small, enlarge the gap.
 593     if ((gapEnd - gapStart) <= addSize)
 594       shiftEnd((addSize - gapEnd + gapStart + 1) * 2 + gapEnd + DEFAULT_BUFSIZE);
 595
 596     // Add new items to the buffer.
 597     if (addItems != null)
 598       {
 599         System.arraycopy(addItems, 0, buffer, gapStart, addSize);
 600         gapStart += addSize;
 601       }
 602   }
 603
 604   /**
 605    * Returns the start index of the gap within the buffer array.
 606    *
 607    * @return the start index of the gap within the buffer array
 608    */
 609   protected final int getGapStart()
 610   {
 611     return gapStart;
 612   }
 613
 614   /**
 615    * Returns the end index of the gap within the buffer array.
 616    *
 617    * @return the end index of the gap within the buffer array
 618    */
 619   protected final int getGapEnd()
 620   {
 621     return gapEnd;
 622   }
 623
 624   /**
 625    * Returns all <code>Position</code>s that are in the range specified by
 626    * <code>offset</code> and </code>length</code> within the buffer array.
 627    *
 628    * @param v the vector to use; if <code>null</code>, a new Vector is allocated
 629    * @param offset the start offset of the range to search
 630    * @param length the length of the range to search
 631    *
 632    * @return the positions within the specified range
 633    */
 634   protected Vector getPositionsInRange(Vector v, int offset, int length)
 635   {
 636     Vector res = v;
 637     if (res == null)
 638       res = new Vector();
 639     else
 640       res.clear();
 641
 642     int endOffset = offset + length;
 643
 644     int index1 = Collections.binarySearch(positions,
 645                                           new GapContentPosition(offset));
 646     if (index1 < 0)
 647       index1 = -(index1 + 1);
 648
 649     // Search the first index with the specified offset. The binarySearch does
 650     // not necessarily find the first one.
 651     while (index1 > 0
 652         && ((GapContentPosition) positions.get(index1 - 1)).mark == offset)
 653       index1--;
 654
 655     for (ListIterator i = positions.listIterator(index1); i.hasNext();)
 656       {
 657         GapContentPosition p = (GapContentPosition) i.next();
 658         if (p.mark > endOffset)
 659           break;
 660         if (p.mark >= offset && p.mark <= endOffset)
 661           res.add(p);
 662       }
 663     return res;
 664   }
 665
 666   /**
 667    * Sets the mark of all <code>Position</code>s that are in the range
 668    * specified by <code>offset</code> and </code>length</code> within
 669    * the buffer array to <code>value</code>
 670    *
 671    * @param offset the start offset of the range to search
 672    * @param length the length of the range to search
 673    * @param value the new value for each mark
 674    */
 675   void setPositionsInRange(int offset, int length, int value)
 676   {
 677     int endOffset = offset + length;
 678
 679     int index1 = Collections.binarySearch(positions,
 680                                           new GapContentPosition(offset));
 681     if (index1 < 0)
 682       index1 = -(index1 + 1);
 683
 684     // Search the first index with the specified offset. The binarySearch does
 685     // not necessarily find the first one.
 686     while (index1 > 0
 687         && ((GapContentPosition) positions.get(index1 - 1)).mark == offset)
 688       index1--;
 689
 690     for (ListIterator i = positions.listIterator(index1); i.hasNext();)
 691       {
 692         GapContentPosition p = (GapContentPosition) i.next();
 693         if (p.mark > endOffset)
 694           break;
 695
 696         if (p.mark >= offset && p.mark <= endOffset)
 697           p.mark = value;
 698       }
 699   }
 700
 701   /**
 702    * Adjusts the mark of all <code>Position</code>s that are in the range
 703    * specified by <code>offset</code> and </code>length</code> within
 704    * the buffer array by <code>increment</code>
 705    *
 706    * @param offset the start offset of the range to search
 707    * @param length the length of the range to search
 708    * @param incr the increment
 709    */
 710   void adjustPositionsInRange(int offset, int length, int incr)
 711   {
 712     int endOffset = offset + length;
 713
 714     int index1 = Collections.binarySearch(positions,
 715                                           new GapContentPosition(offset));
 716     if (index1 < 0)
 717       index1 = -(index1 + 1);
 718
 719     // Search the first index with the specified offset. The binarySearch does
 720     // not necessarily find the first one.
 721     while (index1 > 0
 722         && ((GapContentPosition) positions.get(index1 - 1)).mark == offset)
 723       index1--;
 724     for (ListIterator i = positions.listIterator(index1); i.hasNext();)
 725       {
 726         GapContentPosition p = (GapContentPosition) i.next();
 727         if (p.mark > endOffset)
 728           break;
 729
 730         if (p.mark >= offset && p.mark <= endOffset)
 731           p.mark += incr;
 732       }
 733   }
 734
 735   /**
 736    * Resets all <code>Position</code> that have an offset of <code>0</code>,
 737    * to also have an array index of <code>0</code>. This might be necessary
 738    * after a call to <code>shiftGap(0)</code>, since then the marks at offset
 739    * <code>0</code> get shifted to <code>gapEnd</code>.
 740    */
 741   protected void resetMarksAtZero()
 742   {
 743     if (gapStart != 0)
 744       return;
 745
 746     setPositionsInRange(gapEnd, 0, 0);
 747   }
 748
 749   /**
 750    * Outputs debugging info to System.err. It prints out the buffer array,
 751    * the gapStart is marked by a &lt; sign, the gapEnd is marked by a &gt;
 752    * sign and each position is marked by a # sign.
 753    */
 754   private void dump()
 755   {
 756     System.err.println("GapContent debug information");
 757     System.err.println("buffer length: " + buffer.length);
 758     System.err.println("gap start: " + gapStart);
 759     System.err.println("gap end: " + gapEnd);
 760     for (int i = 0; i < buffer.length; i++)
 761       {
 762         if (i == gapStart)
 763           System.err.print('<');
 764         if (i == gapEnd)
 765           System.err.print('>');
 766
 767         if (!Character.isISOControl(buffer[i]))
 768           System.err.print(buffer[i]);
 769         else
 770           System.err.print('.');
 771       }
 772     System.err.println();
 773   }
 774
 775   private void dumpPositions()
 776   {
 777     for (Iterator i = positions.iterator(); i.hasNext();)
 778       {
 779         GapContentPosition pos = (GapContentPosition) i.next();
 780         System.err.println("position at: " + pos.mark);
 781       }
 782   }
 783 }