001 /*
002 * Copyright 1998-2003 Sun Microsystems, Inc. All Rights Reserved.
003 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
004 *
005 * This code is free software; you can redistribute it and/or modify it
006 * under the terms of the GNU General Public License version 2 only, as
007 * published by the Free Software Foundation. Sun designates this
008 * particular file as subject to the "Classpath" exception as provided
009 * by Sun in the LICENSE file that accompanied this code.
010 *
011 * This code is distributed in the hope that it will be useful, but WITHOUT
012 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
013 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
014 * version 2 for more details (a copy is included in the LICENSE file that
015 * accompanied this code).
016 *
017 * You should have received a copy of the GNU General Public License version
018 * 2 along with this work; if not, write to the Free Software Foundation,
019 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
020 *
021 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
022 * CA 95054 USA or visit www.sun.com if you need additional information or
023 * have any questions.
024 */
025 package javax.swing.text;
026
027 import java.util.Vector;
028 import java.io.Serializable;
029 import javax.swing.undo.UndoableEdit;
030
031 /**
032 * An implementation of a gapped buffer similar to that used by
033 * emacs. The underlying storage is a java array of some type,
034 * which is known only by the subclass of this class. The array
035 * has a gap somewhere. The gap is moved to the location of changes
036 * to take advantage of common behavior where most changes occur
037 * in the same location. Changes that occur at a gap boundary are
038 * generally cheap and moving the gap is generally cheaper than
039 * moving the array contents directly to accomodate the change.
040 *
041 * @author Timothy Prinzing
042 * @version 1.19 05/05/07
043 * @see GapContent
044 */
045 abstract class GapVector implements Serializable {
046
047 /**
048 * Creates a new GapVector object. Initial size defaults to 10.
049 */
050 public GapVector() {
051 this (10);
052 }
053
054 /**
055 * Creates a new GapVector object, with the initial
056 * size specified.
057 *
058 * @param initialLength the initial size
059 */
060 public GapVector(int initialLength) {
061 array = allocateArray(initialLength);
062 g0 = 0;
063 g1 = initialLength;
064 }
065
066 /**
067 * Allocate an array to store items of the type
068 * appropriate (which is determined by the subclass).
069 */
070 protected abstract Object allocateArray(int len);
071
072 /**
073 * Get the length of the allocated array
074 */
075 protected abstract int getArrayLength();
076
077 /**
078 * Access to the array. The actual type
079 * of the array is known only by the subclass.
080 */
081 protected final Object getArray() {
082 return array;
083 }
084
085 /**
086 * Access to the start of the gap.
087 */
088 protected final int getGapStart() {
089 return g0;
090 }
091
092 /**
093 * Access to the end of the gap.
094 */
095 protected final int getGapEnd() {
096 return g1;
097 }
098
099 // ---- variables -----------------------------------
100
101 /**
102 * The array of items. The type is determined by the subclass.
103 */
104 private Object array;
105
106 /**
107 * start of gap in the array
108 */
109 private int g0;
110
111 /**
112 * end of gap in the array
113 */
114 private int g1;
115
116 // --- gap management -------------------------------
117
118 /**
119 * Replace the given logical position in the storage with
120 * the given new items. This will move the gap to the area
121 * being changed if the gap is not currently located at the
122 * change location.
123 *
124 * @param position the location to make the replacement. This
125 * is not the location in the underlying storage array, but
126 * the location in the contiguous space being modeled.
127 * @param rmSize the number of items to remove
128 * @param addItems the new items to place in storage.
129 */
130 protected void replace(int position, int rmSize, Object addItems,
131 int addSize) {
132 int addOffset = 0;
133 if (addSize == 0) {
134 close(position, rmSize);
135 return;
136 } else if (rmSize > addSize) {
137 /* Shrink the end. */
138 close(position + addSize, rmSize - addSize);
139 } else {
140 /* Grow the end, do two chunks. */
141 int endSize = addSize - rmSize;
142 int end = open(position + rmSize, endSize);
143 System.arraycopy(addItems, rmSize, array, end, endSize);
144 addSize = rmSize;
145 }
146 System.arraycopy(addItems, addOffset, array, position, addSize);
147 }
148
149 /**
150 * Delete nItems at position. Squeezes any marks
151 * within the deleted area to position. This moves
152 * the gap to the best place by minimizing it's
153 * overall movement. The gap must intersect the
154 * target block.
155 */
156 void close(int position, int nItems) {
157 if (nItems == 0)
158 return;
159
160 int end = position + nItems;
161 int new_gs = (g1 - g0) + nItems;
162 if (end <= g0) {
163 // Move gap to end of block.
164 if (g0 != end) {
165 shiftGap(end);
166 }
167 // Adjust g0.
168 shiftGapStartDown(g0 - nItems);
169 } else if (position >= g0) {
170 // Move gap to beginning of block.
171 if (g0 != position) {
172 shiftGap(position);
173 }
174 // Adjust g1.
175 shiftGapEndUp(g0 + new_gs);
176 } else {
177 // The gap is properly inside the target block.
178 // No data movement necessary, simply move both gap pointers.
179 shiftGapStartDown(position);
180 shiftGapEndUp(g0 + new_gs);
181 }
182 }
183
184 /**
185 * Make space for the given number of items at the given
186 * location.
187 *
188 * @return the location that the caller should fill in
189 */
190 int open(int position, int nItems) {
191 int gapSize = g1 - g0;
192 if (nItems == 0) {
193 if (position > g0)
194 position += gapSize;
195 return position;
196 }
197
198 // Expand the array if the gap is too small.
199 shiftGap(position);
200 if (nItems >= gapSize) {
201 // Pre-shift the gap, to reduce total movement.
202 shiftEnd(getArrayLength() - gapSize + nItems);
203 gapSize = g1 - g0;
204 }
205
206 g0 = g0 + nItems;
207 return position;
208 }
209
210 /**
211 * resize the underlying storage array to the
212 * given new size
213 */
214 void resize(int nsize) {
215 Object narray = allocateArray(nsize);
216 System.arraycopy(array, 0, narray, 0, Math.min(nsize,
217 getArrayLength()));
218 array = narray;
219 }
220
221 /**
222 * Make the gap bigger, moving any necessary data and updating
223 * the appropriate marks
224 */
225 protected void shiftEnd(int newSize) {
226 int oldSize = getArrayLength();
227 int oldGapEnd = g1;
228 int upperSize = oldSize - oldGapEnd;
229 int arrayLength = getNewArraySize(newSize);
230 int newGapEnd = arrayLength - upperSize;
231 resize(arrayLength);
232 g1 = newGapEnd;
233
234 if (upperSize != 0) {
235 // Copy array items to new end of array.
236 System.arraycopy(array, oldGapEnd, array, newGapEnd,
237 upperSize);
238 }
239 }
240
241 /**
242 * Calculates a new size of the storage array depending on required
243 * capacity.
244 * @param reqSize the size which is necessary for new content
245 * @return the new size of the storage array
246 */
247 int getNewArraySize(int reqSize) {
248 return (reqSize + 1) * 2;
249 }
250
251 /**
252 * Move the start of the gap to a new location,
253 * without changing the size of the gap. This
254 * moves the data in the array and updates the
255 * marks accordingly.
256 */
257 protected void shiftGap(int newGapStart) {
258 if (newGapStart == g0) {
259 return;
260 }
261 int oldGapStart = g0;
262 int dg = newGapStart - oldGapStart;
263 int oldGapEnd = g1;
264 int newGapEnd = oldGapEnd + dg;
265 int gapSize = oldGapEnd - oldGapStart;
266
267 g0 = newGapStart;
268 g1 = newGapEnd;
269 if (dg > 0) {
270 // Move gap up, move data down.
271 System.arraycopy(array, oldGapEnd, array, oldGapStart, dg);
272 } else if (dg < 0) {
273 // Move gap down, move data up.
274 System.arraycopy(array, newGapStart, array, newGapEnd, -dg);
275 }
276 }
277
278 /**
279 * Adjust the gap end downward. This doesn't move
280 * any data, but it does update any marks affected
281 * by the boundary change. All marks from the old
282 * gap start down to the new gap start are squeezed
283 * to the end of the gap (their location has been
284 * removed).
285 */
286 protected void shiftGapStartDown(int newGapStart) {
287 g0 = newGapStart;
288 }
289
290 /**
291 * Adjust the gap end upward. This doesn't move
292 * any data, but it does update any marks affected
293 * by the boundary change. All marks from the old
294 * gap end up to the new gap end are squeezed
295 * to the end of the gap (their location has been
296 * removed).
297 */
298 protected void shiftGapEndUp(int newGapEnd) {
299 g1 = newGapEnd;
300 }
301
302 }
|