J. Duke | 319a3b9 | 2007-12-01 00:00:00 +0000 | [diff] [blame^] | 1 | /* |
| 2 | * Copyright 1998-2003 Sun Microsystems, Inc. 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. Sun designates this |
| 8 | * particular file as subject to the "Classpath" exception as provided |
| 9 | * by Sun 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 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara, |
| 22 | * CA 95054 USA or visit www.sun.com if you need additional information or |
| 23 | * have any 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 accomodate 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 | } |