1 /*
2 * Copyright (c) 1998, 2014, 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 @SuppressWarnings("serial") // Data in fields not necessarily serializable
45 abstract class GapVector implements Serializable {
46
47
48 /**
49 * Creates a new GapVector object. Initial size defaults to 10.
50 */
51 public GapVector() {
52 this(10);
53 }
54
55 /**
56 * Creates a new GapVector object, with the initial
57 * size specified.
58 *
59 * @param initialLength the initial size
60 */
61 public GapVector(int initialLength) {
62 array = allocateArray(initialLength);
63 g0 = 0;
64 g1 = initialLength;
65 }
66
67 /**
68 * Allocate an array to store items of the type
69 * appropriate (which is determined by the subclass).
70 */
71 protected abstract Object allocateArray(int len);
72
73 /**
74 * Get the length of the allocated array
75 */
76 protected abstract int getArrayLength();
77
78 /**
79 * Access to the array. The actual type
80 * of the array is known only by the subclass.
81 */
82 protected final Object getArray() {
83 return array;
84 }
85
86 /**
87 * Access to the start of the gap.
88 */
89 protected final int getGapStart() {
90 return g0;
91 }
92
93 /**
94 * Access to the end of the gap.
95 */
96 protected final int getGapEnd() {
97 return g1;
98 }
99
100 // ---- variables -----------------------------------
101
102 /**
103 * The array of items. The type is determined by the subclass.
104 */
105 private Object array;
106
107 /**
108 * start of gap in the array
109 */
110 private int g0;
111
112 /**
113 * end of gap in the array
114 */
115 private int g1;
116
117
118 // --- gap management -------------------------------
119
120 /**
121 * Replace the given logical position in the storage with
122 * the given new items. This will move the gap to the area
123 * being changed if the gap is not currently located at the
124 * change location.
125 *
126 * @param position the location to make the replacement. This
127 * is not the location in the underlying storage array, but
128 * the location in the contiguous space being modeled.
129 * @param rmSize the number of items to remove
130 * @param addItems the new items to place in storage.
131 */
132 protected void replace(int position, int rmSize, Object addItems, int addSize) {
133 int addOffset = 0;
134 if (addSize == 0) {
135 close(position, rmSize);
136 return;
137 } else if (rmSize > addSize) {
138 /* Shrink the end. */
139 close(position+addSize, rmSize-addSize);
140 } else {
141 /* Grow the end, do two chunks. */
142 int endSize = addSize - rmSize;
143 int end = open(position + rmSize, endSize);
144 System.arraycopy(addItems, rmSize, array, end, endSize);
145 addSize = rmSize;
146 }
147 System.arraycopy(addItems, addOffset, array, position, addSize);
148 }
149
150 /**
151 * Delete nItems at position. Squeezes any marks
152 * within the deleted area to position. This moves
153 * the gap to the best place by minimizing it's
154 * overall movement. The gap must intersect the
155 * target block.
156 */
157 void close(int position, int nItems) {
158 if (nItems == 0) 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, getArrayLength()));
217 array = narray;
218 }
219
220 /**
221 * Make the gap bigger, moving any necessary data and updating
222 * the appropriate marks
223 */
224 protected void shiftEnd(int newSize) {
225 int oldSize = getArrayLength();
226 int oldGapEnd = g1;
227 int upperSize = oldSize - oldGapEnd;
228 int arrayLength = getNewArraySize(newSize);
229 int newGapEnd = arrayLength - upperSize;
230 resize(arrayLength);
231 g1 = newGapEnd;
232
233 if (upperSize != 0) {
234 // Copy array items to new end of array.
235 System.arraycopy(array, oldGapEnd, array, newGapEnd, upperSize);
236 }
237 }
238
239 /**
240 * Calculates a new size of the storage array depending on required
241 * capacity.
242 * @param reqSize the size which is necessary for new content
243 * @return the new size of the storage array
244 */
245 int getNewArraySize(int reqSize) {
246 return (reqSize + 1) * 2;
247 }
248
249 /**
250 * Move the start of the gap to a new location,
251 * without changing the size of the gap. This
252 * moves the data in the array and updates the
253 * marks accordingly.
254 */
255 protected void shiftGap(int newGapStart) {
256 if (newGapStart == g0) {
257 return;
258 }
259 int oldGapStart = g0;
260 int dg = newGapStart - oldGapStart;
261 int oldGapEnd = g1;
262 int newGapEnd = oldGapEnd + dg;
263 int gapSize = oldGapEnd - oldGapStart;
264
265 g0 = newGapStart;
266 g1 = newGapEnd;
267 if (dg > 0) {
268 // Move gap up, move data down.
269 System.arraycopy(array, oldGapEnd, array, oldGapStart, dg);
270 } else if (dg < 0) {
271 // Move gap down, move data up.
272 System.arraycopy(array, newGapStart, array, newGapEnd, -dg);
273 }
274 }
275
276 /**
277 * Adjust the gap end downward. This doesn't move
278 * any data, but it does update any marks affected
279 * by the boundary change. All marks from the old
280 * gap start down to the new gap start are squeezed
281 * to the end of the gap (their location has been
282 * removed).
283 */
284 protected void shiftGapStartDown(int newGapStart) {
285 g0 = newGapStart;
286 }
287
288 /**
289 * Adjust the gap end upward. This doesn't move
290 * any data, but it does update any marks affected
291 * by the boundary change. All marks from the old
292 * gap end up to the new gap end are squeezed
293 * to the end of the gap (their location has been
294 * removed).
295 */
296 protected void shiftGapEndUp(int newGapEnd) {
297 g1 = newGapEnd;
298 }
299
300 }