1 /*
2 * Copyright (c) 1998, 2013, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation. Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25 package javax.swing.text;
26
27 import java.util.Vector;
28 import java.io.Serializable;
29 import javax.swing.undo.UndoableEdit;
30
31 /**
32 * An implementation of a gapped buffer similar to that used by
33 * emacs. The underlying storage is a java array of some type,
34 * which is known only by the subclass of this class. The array
35 * has a gap somewhere. The gap is moved to the location of changes
36 * to take advantage of common behavior where most changes occur
37 * in the same location. Changes that occur at a gap boundary are
38 * generally cheap and moving the gap is generally cheaper than
39 * moving the array contents directly to accommodate the change.
40 *
41 * @author Timothy Prinzing
42 * @see GapContent
43 */
44 abstract class GapVector implements Serializable {
45
46
47 /**
48 * Creates a new GapVector object. Initial size defaults to 10.
49 */
50 public GapVector() {
51 this(10);
52 }
53
54 /**
55 * Creates a new GapVector object, with the initial
56 * size specified.
57 *
58 * @param initialLength the initial size
59 */
60 public GapVector(int initialLength) {
61 array = allocateArray(initialLength);
62 g0 = 0;
63 g1 = initialLength;
64 }
65
66 /**
67 * Allocate an array to store items of the type
68 * appropriate (which is determined by the subclass).
69 */
70 protected abstract Object allocateArray(int len);
71
72 /**
73 * Get the length of the allocated array
74 */
75 protected abstract int getArrayLength();
76
77 /**
78 * Access to the array. The actual type
79 * of the array is known only by the subclass.
80 */
81 protected final Object getArray() {
82 return array;
83 }
84
85 /**
86 * Access to the start of the gap.
87 */
88 protected final int getGapStart() {
89 return g0;
90 }
91
92 /**
93 * Access to the end of the gap.
94 */
95 protected final int getGapEnd() {
96 return g1;
97 }
98
99 // ---- 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
117 // --- gap management -------------------------------
118
119 /**
120 * Replace the given logical position in the storage with
121 * the given new items. This will move the gap to the area
122 * being changed if the gap is not currently located at the
123 * change location.
124 *
125 * @param position the location to make the replacement. This
126 * is not the location in the underlying storage array, but
127 * the location in the contiguous space being modeled.
128 * @param rmSize the number of items to remove
129 * @param addItems the new items to place in storage.
130 */
131 protected void replace(int position, int rmSize, Object addItems, 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) return;
158
159 int end = position + nItems;
160 int new_gs = (g1 - g0) + nItems;
161 if (end <= g0) {
162 // Move gap to end of block.
163 if (g0 != end) {
164 shiftGap(end);
165 }
166 // Adjust g0.
167 shiftGapStartDown(g0 - nItems);
168 } else if (position >= g0) {
169 // Move gap to beginning of block.
170 if (g0 != position) {
171 shiftGap(position);
172 }
173 // Adjust g1.
174 shiftGapEndUp(g0 + new_gs);
175 } else {
176 // The gap is properly inside the target block.
177 // No data movement necessary, simply move both gap pointers.
178 shiftGapStartDown(position);
179 shiftGapEndUp(g0 + new_gs);
180 }
181 }
182
183 /**
184 * Make space for the given number of items at the given
185 * location.
186 *
187 * @return the location that the caller should fill in
188 */
189 int open(int position, int nItems) {
190 int gapSize = g1 - g0;
191 if (nItems == 0) {
192 if (position > g0)
193 position += gapSize;
194 return position;
195 }
196
197 // Expand the array if the gap is too small.
198 shiftGap(position);
199 if (nItems >= gapSize) {
200 // Pre-shift the gap, to reduce total movement.
201 shiftEnd(getArrayLength() - gapSize + nItems);
202 gapSize = g1 - g0;
203 }
204
205 g0 = g0 + nItems;
206 return position;
207 }
208
209 /**
210 * resize the underlying storage array to the
211 * given new size
212 */
213 void resize(int nsize) {
214 Object narray = allocateArray(nsize);
215 System.arraycopy(array, 0, narray, 0, Math.min(nsize, getArrayLength()));
216 array = narray;
217 }
218
219 /**
220 * Make the gap bigger, moving any necessary data and updating
221 * the appropriate marks
222 */
223 protected void shiftEnd(int newSize) {
224 int oldSize = getArrayLength();
225 int oldGapEnd = g1;
226 int upperSize = oldSize - oldGapEnd;
227 int arrayLength = getNewArraySize(newSize);
228 int newGapEnd = arrayLength - upperSize;
229 resize(arrayLength);
230 g1 = newGapEnd;
231
232 if (upperSize != 0) {
233 // Copy array items to new end of array.
234 System.arraycopy(array, oldGapEnd, array, newGapEnd, upperSize);
235 }
236 }
237
238 /**
239 * Calculates a new size of the storage array depending on required
240 * capacity.
241 * @param reqSize the size which is necessary for new content
242 * @return the new size of the storage array
243 */
244 int getNewArraySize(int reqSize) {
245 return (reqSize + 1) * 2;
246 }
247
248 /**
249 * Move the start of the gap to a new location,
250 * without changing the size of the gap. This
251 * moves the data in the array and updates the
252 * marks accordingly.
253 */
254 protected void shiftGap(int newGapStart) {
255 if (newGapStart == g0) {
256 return;
257 }
258 int oldGapStart = g0;
259 int dg = newGapStart - oldGapStart;
260 int oldGapEnd = g1;
261 int newGapEnd = oldGapEnd + dg;
262 int gapSize = oldGapEnd - oldGapStart;
263
264 g0 = newGapStart;
265 g1 = newGapEnd;
266 if (dg > 0) {
267 // Move gap up, move data down.
268 System.arraycopy(array, oldGapEnd, array, oldGapStart, dg);
269 } else if (dg < 0) {
270 // Move gap down, move data up.
271 System.arraycopy(array, newGapStart, array, newGapEnd, -dg);
272 }
273 }
274
275 /**
276 * Adjust the gap end downward. This doesn't move
277 * any data, but it does update any marks affected
278 * by the boundary change. All marks from the old
279 * gap start down to the new gap start are squeezed
280 * to the end of the gap (their location has been
281 * removed).
282 */
283 protected void shiftGapStartDown(int newGapStart) {
284 g0 = newGapStart;
285 }
286
287 /**
288 * Adjust the gap end upward. This doesn't move
289 * any data, but it does update any marks affected
290 * by the boundary change. All marks from the old
291 * gap end up to the new gap end are squeezed
292 * to the end of the gap (their location has been
293 * removed).
294 */
295 protected void shiftGapEndUp(int newGapEnd) {
296 g1 = newGapEnd;
297 }
298
299 }