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 */
25package javax.swing.text;
26
27import java.util.Vector;
28import java.io.Serializable;
29import 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
45abstract 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}
301