GapVector


1   /*
2    * @(#)GapVector.java   1.12 03/12/19
3    *
4    * Copyright 2004 Sun Microsystems, Inc. All rights reserved.
5    * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
6    */
7   package javax.swing.text;
8   
9   import java.util.Vector  ;
10  import java.io.Serializable  ;
11  import javax.swing.undo.UndoableEdit  ;
12  
13  /**
14   * An implementation of a gapped buffer similar to that used by 
15   * emacs.  The underlying storage is a java array of some type,
16   * which is known only by the subclass of this class.  The array
17   * has a gap somewhere.  The gap is moved to the location of changes
18   * to take advantage of common behavior where most changes occur
19   * in the same location.  Changes that occur at a gap boundary are
20   * generally cheap and moving the gap is generally cheaper than
21   * moving the array contents directly to accomodate the change.
22   *
23   * @author  Timothy Prinzing
24   * @version 1.12 12/19/03
25   * @see GapContent
26   */
27  abstract class GapVector implements Serializable   {
28  
29  
30      /**
31       * Creates a new GapVector object.  Initial size defaults to 10.
32       */
33      public GapVector() {
34      this(10);
35      }
36  
37      /**
38       * Creates a new GapVector object, with the initial
39       * size specified.
40       *
41       * @param initialLength the initial size
42       */
43      public GapVector(int initialLength) {
44      array = allocateArray(initialLength);
45      g0 = 0;
46      g1 = initialLength;
47      }
48  
49      /**
50       * Allocate an array to store items of the type
51       * appropriate (which is determined by the subclass).
52       */
53      protected abstract Object   allocateArray(int len);
54      
55      /**
56       * Get the length of the allocated array
57       */
58      protected abstract int getArrayLength();
59  
60      /**
61       * Access to the array.  The actual type
62       * of the array is known only by the subclass.
63       */
64      protected final Object   getArray() {
65      return array;
66      }
67  
68      /**
69       * Access to the start of the gap.
70       */
71      protected final int getGapStart() {
72      return g0;
73      }
74  
75      /**
76       * Access to the end of the gap.
77       */
78      protected final int getGapEnd() {
79      return g1;
80      }
81  
82      // ---- variables -----------------------------------
83  
84      /**
85       * The array of items.  The type is determined by the subclass.
86       */
87      private Object   array;
88  
89      /**
90       * start of gap in the array
91       */
92      private int g0;
93  
94      /**
95       * end of gap in the array
96       */
97      private int g1;
98  
99  
100     // --- gap management -------------------------------
101 
102     /**
103      * Replace the given logical position in the storage with
104      * the given new items.  This will move the gap to the area
105      * being changed if the gap is not currently located at the
106      * change location.
107      *
108      * @param position the location to make the replacement.  This
109      *  is not the location in the underlying storage array, but
110      *  the location in the contiguous space being modeled.
111      * @param rmSize the number of items to remove
112      * @param addItems the new items to place in storage.
113      */
114     protected void replace(int position, int rmSize, Object   addItems, int addSize) {
115     int addOffset = 0;
116     if (addSize == 0) {
117         close(position, rmSize);
118         return;
119     } else if (rmSize > addSize) {
120         /* Shrink the end. */
121         close(position+addSize, rmSize-addSize);
122     } else {
123         /* Grow the end, do two chunks. */
124         int endSize = addSize - rmSize;
125         int end = open(position + rmSize, endSize);
126         System.arraycopy(addItems, rmSize, array, end, endSize);
127         addSize = rmSize;
128     }
129     System.arraycopy(addItems, addOffset, array, position, addSize);
130     }
131 
132     /** 
133      * Delete nItems at position.  Squeezes any marks 
134      * within the deleted area to position.  This moves
135      * the gap to the best place by minimizing it's 
136      * overall movement.  The gap must intersect the
137      * target block.
138      */
139     void close(int position, int nItems) {
140     if (nItems == 0)  return;
141 
142     int end = position + nItems;
143     int new_gs = (g1 - g0) + nItems;
144     if (end <= g0) {
145         // Move gap to end of block.
146         if (g0 != end) {
147         shiftGap(end);
148         }
149         // Adjust g0.
150         shiftGapStartDown(g0 - nItems);
151     } else if (position >= g0) {
152         // Move gap to beginning of block.
153         if (g0 != position) {
154         shiftGap(position);
155         }
156         // Adjust g1. 
157         shiftGapEndUp(g0 + new_gs);
158     } else {
159         // The gap is properly inside the target block.
160         // No data movement necessary, simply move both gap pointers.
161         shiftGapStartDown(position);
162         shiftGapEndUp(g0 + new_gs);
163     }
164     }
165 
166     /**
167      * Make space for the given number of items at the given
168      * location.  
169      *
170      * @return the location that the caller should fill in
171      */
172     int open(int position, int nItems) {
173     int gapSize = g1 - g0;
174     if (nItems == 0) {
175         if (position > g0)  
176         position += gapSize;
177         return position;
178     }
179 
180     // Expand the array if the gap is too small.
181     shiftGap(position);
182     if (nItems >= gapSize) {
183         // Pre-shift the gap, to reduce total movement.
184         shiftEnd(getArrayLength() - gapSize + nItems);
185         gapSize = g1 - g0;
186     }
187 
188     g0 = g0 + nItems;
189     return position;
190     }
191 
192     /** 
193      * resize the underlying storage array to the 
194      * given new size
195      */
196     void resize(int nsize) {
197     Object   narray = allocateArray(nsize);
198     System.arraycopy(array, 0, narray, 0, Math.min(nsize, getArrayLength()));
199     array = narray;
200     }
201 
202     /**
203      * Make the gap bigger, moving any necessary data and updating 
204      * the appropriate marks
205      */
206     protected void shiftEnd(int newSize) {
207     int oldSize = getArrayLength();
208     int oldGapEnd = g1;
209     int upperSize = oldSize - oldGapEnd;
210     int arrayLength = getNewArraySize(newSize);
211     int newGapEnd = arrayLength - upperSize;
212     resize(arrayLength);
213     g1 = newGapEnd;
214 
215     if (upperSize != 0) {
216         // Copy array items to new end of array.
217         System.arraycopy(array, oldGapEnd, array, newGapEnd, upperSize);
218     }
219     }
220 
221     /**
222      * Calculates a new size of the storage array depending on required
223      * capacity.
224      * @param reqSize the size which is necessary for new content
225      * @return the new size of the storage array
226      */
227     int getNewArraySize(int reqSize) {
228         return (reqSize + 1) * 2;
229     }
230 
231     /**
232      * Move the start of the gap to a new location,
233      * without changing the size of the gap.  This 
234      * moves the data in the array and updates the
235      * marks accordingly.
236      */
237     protected void shiftGap(int newGapStart) {
238     if (newGapStart == g0) {
239         return;
240     }
241     int oldGapStart = g0;
242     int dg = newGapStart - oldGapStart;
243     int oldGapEnd = g1;
244     int newGapEnd = oldGapEnd + dg;
245     int gapSize = oldGapEnd - oldGapStart;
246 
247     g0 = newGapStart;
248     g1 = newGapEnd;
249     if (dg > 0) {
250         // Move gap up, move data down.
251         System.arraycopy(array, oldGapEnd, array, oldGapStart, dg);
252     } else if (dg < 0) {
253         // Move gap down, move data up.
254         System.arraycopy(array, newGapStart, array, newGapEnd, -dg);
255     }
256     }
257 
258     /**
259      * Adjust the gap end downward.  This doesn't move
260      * any data, but it does update any marks affected 
261      * by the boundary change.  All marks from the old
262      * gap start down to the new gap start are squeezed
263      * to the end of the gap (their location has been
264      * removed).
265      */
266     protected void shiftGapStartDown(int newGapStart) {
267     g0 = newGapStart;
268     }
269 
270     /**
271      * Adjust the gap end upward.  This doesn't move
272      * any data, but it does update any marks affected 
273      * by the boundary change. All marks from the old
274      * gap end up to the new gap end are squeezed
275      * to the end of the gap (their location has been
276      * removed).
277      */
278     protected void shiftGapEndUp(int newGapEnd) {
279     g1 = newGapEnd;
280     }
281 
282 }
283 
284 
285
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags