Mercurial > projects > dwt-addons

comparison dwtx/jface/text/GapTextStore.d @ 129:eb30df5ca28b

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Added JFace Text sources
author Frank Benoit <benoit@tionex.de>
date Sat, 23 Aug 2008 19:10:48 +0200
parents
children c4fb132a086c
comparison
equal deleted inserted replaced
128:8df1d4193877 129:eb30df5ca28b
1 /*******************************************************************************
2 * Copyright (c) 2000, 2008 IBM Corporation and others.
3 * All rights reserved. This program and the accompanying materials
4 * are made available under the terms of the Eclipse Public License v1.0
5 * which accompanies this distribution, and is available at
6 * http://www.eclipse.org/legal/epl-v10.html
7 *
8 * Contributors:
9 * IBM Corporation - initial API and implementation
10 * Port to the D programming language:
11 * Frank Benoit <benoit@tionex.de>
12 *******************************************************************************/
13 module dwtx.jface.text.GapTextStore;
14
15 import dwt.dwthelper.utils;
16
17 import dwtx.core.runtime.Assert;
18
19
20 /**
21 * Implements a gap managing text store. The gap text store relies on the assumption that
22 * consecutive changes to a document are co-located. The start of the gap is always moved to the
23 * location of the last change.
24 * <p>
25 * <strong>Performance:</strong> Typing-style changes perform in constant time unless re-allocation
26 * becomes necessary. Generally, a change that does not cause re-allocation will cause at most one
27 * {@linkplain System#arraycopy(Object, int, Object, int, int) arraycopy} operation of a length of
28 * about <var>d</var>, where <var>d</var> is the distance from the previous change. Let <var>a(x)</var>
29 * be the algorithmic performance of an <code>arraycopy</code> operation of the length <var>x</var>,
30 * then such a change then performs in <i>O(a(x))</i>,
31 * {@linkplain #get(int, int) get(int, <var>length</var>)} performs in <i>O(a(length))</i>,
32 * {@link #get(int)} in <i>O(1)</i>.
33 * <p>
34 * How frequently the array needs re-allocation is controlled by the constructor parameters.
35 * </p>
36 * <p>
37 * This class is not intended to be subclassed.
38 * </p>
39 *
40 * @see CopyOnWriteTextStore for a copy-on-write text store wrapper
41 * @noextend This class is not intended to be subclassed by clients.
42 */
43 public class GapTextStore : ITextStore {
44 /**
45 * The minimum gap size allocated when re-allocation occurs.
46 * @since 3.3
47 */
48 private final int fMinGapSize;
49 /**
50 * The maximum gap size allocated when re-allocation occurs.
51 * @since 3.3
52 */
53 private final int fMaxGapSize;
54 /**
55 * The multiplier to compute the array size from the content length
56 * (1&nbsp;&lt;=&nbsp;fSizeMultiplier&nbsp;&lt;=&nbsp;2).
57 *
58 * @since 3.3
59 */
60 private final float fSizeMultiplier;
61
62 /** The store's content */
63 private char[] fContent= new char[0];
64 /** Starting index of the gap */
65 private int fGapStart= 0;
66 /** End index of the gap */
67 private int fGapEnd= 0;
68 /**
69 * The current high water mark. If a change would cause the gap to grow larger than this, the
70 * array is re-allocated.
71 * @since 3.3
72 */
73 private int fThreshold= 0;
74
75 /**
76 * Creates a new empty text store using the specified low and high watermarks.
77 *
78 * @param lowWatermark unused - at the lower bound, the array is only resized when the content
79 * does not fit
80 * @param highWatermark if the gap is ever larger than this, it will automatically be shrunken
81 * (&gt;=&nbsp;0)
82 * @deprecated use {@link GapTextStore#GapTextStore(int, int, float)} instead
83 */
84 public GapTextStore(int lowWatermark, int highWatermark) {
85 /*
86 * Legacy constructor. The API contract states that highWatermark is the upper bound for the
87 * gap size. Albeit this contract was not previously adhered to, it is now: The allocated
88 * gap size is fixed at half the highWatermark. Since the threshold is always twice the
89 * allocated gap size, the gap will never grow larger than highWatermark. Previously, the
90 * gap size was initialized to highWatermark, causing re-allocation if the content length
91 * shrunk right after allocation. The fixed gap size is now only half of the previous value,
92 * circumventing that problem (there was no API contract specifying the initial gap size).
93 *
94 * The previous implementation did not allow the gap size to become smaller than
95 * lowWatermark, which doesn't make any sense: that area of the gap was simply never ever
96 * used.
97 */
98 this(highWatermark / 2, highWatermark / 2, 0f);
99 }
100
101 /**
102 * Equivalent to
103 * {@linkplain GapTextStore#GapTextStore(int, int, float) new GapTextStore(256, 4096, 0.1f)}.
104 *
105 * @since 3.3
106 */
107 public GapTextStore() {
108 this(256, 4096, 0.1f);
109 }
110
111 /**
112 * Creates an empty text store that uses re-allocation thresholds relative to the content
113 * length. Re-allocation is controlled by the <em>gap factor</em>, which is the quotient of
114 * the gap size and the array size. Re-allocation occurs if a change causes the gap factor to go
115 * outside <code>[0,&nbsp;maxGapFactor]</code>. When re-allocation occurs, the array is sized
116 * such that the gap factor is <code>0.5 * maxGapFactor</code>. The gap size computed in this
117 * manner is bounded by the <code>minSize</code> and <code>maxSize</code> parameters.
118 * <p>
119 * A <code>maxGapFactor</code> of <code>0</code> creates a text store that never has a gap
120 * at all (if <code>minSize</code> is 0); a <code>maxGapFactor</code> of <code>1</code>
121 * creates a text store that doubles its size with every re-allocation and that never shrinks.
122 * </p>
123 * <p>
124 * The <code>minSize</code> and <code>maxSize</code> parameters are absolute bounds to the
125 * allocated gap size. Use <code>minSize</code> to avoid frequent re-allocation for small
126 * documents. Use <code>maxSize</code> to avoid a huge gap being allocated for large
127 * documents.
128 * </p>
129 *
130 * @param minSize the minimum gap size to allocate (&gt;=&nbsp;0; use 0 for no minimum)
131 * @param maxSize the maximum gap size to allocate (&gt;=&nbsp;minSize; use
132 * {@link Integer#MAX_VALUE} for no maximum)
133 * @param maxGapFactor is the maximum fraction of the array that is occupied by the gap (<code>0&nbsp;&lt;=&nbsp;maxGapFactor&nbsp;&lt;=&nbsp;1</code>)
134 * @since 3.3
135 */
136 public GapTextStore(int minSize, int maxSize, float maxGapFactor) {
137 Assert.isLegal(0f <= maxGapFactor && maxGapFactor <= 1f);
138 Assert.isLegal(0 <= minSize && minSize <= maxSize);
139 fMinGapSize= minSize;
140 fMaxGapSize= maxSize;
141 fSizeMultiplier= 1 / (1 - maxGapFactor / 2);
142 }
143
144 /*
145 * @see dwtx.jface.text.ITextStore#get(int)
146 */
147 public final char get(int offset) {
148 if (offset < fGapStart)
149 return fContent[offset];
150
151 return fContent[offset + gapSize()];
152 }
153
154 /*
155 * @see dwtx.jface.text.ITextStore#get(int, int)
156 */
157 public final String get(int offset, int length) {
158 if (fGapStart <= offset)
159 return new String(fContent, offset + gapSize() , length);
160
161 final int end= offset + length;
162
163 if (end <= fGapStart)
164 return new String(fContent, offset, length);
165
166 StringBuffer buf= new StringBuffer(length);
167 buf.append(fContent, offset, fGapStart - offset);
168 buf.append(fContent, fGapEnd, end - fGapStart);
169 return buf.toString();
170 }
171
172 /*
173 * @see dwtx.jface.text.ITextStore#getLength()
174 */
175 public final int getLength() {
176 return fContent.length - gapSize();
177 }
178
179 /*
180 * @see dwtx.jface.text.ITextStore#set(java.lang.String)
181 */
182 public final void set(String text) {
183 /*
184 * Moves the gap to the end of the content. There is no sensible prediction of where the
185 * next change will occur, but at least the next change will not trigger re-allocation. This
186 * is especially important when using the GapTextStore within a CopyOnWriteTextStore, where
187 * the GTS is only initialized right before a modification.
188 */
189 replace(0, getLength(), text);
190 }
191
192 /*
193 * @see dwtx.jface.text.ITextStore#replace(int, int, java.lang.String)
194 */
195 public final void replace(int offset, int length, String text) {
196 if (text is null) {
197 adjustGap(offset, length, 0);
198 } else {
199 int textLength= text.length();
200 adjustGap(offset, length, textLength);
201 if (textLength !is 0)
202 text.getChars(0, textLength, fContent, offset);
203 }
204 }
205
206 /**
207 * Moves the gap to <code>offset + add</code>, moving any content after
208 * <code>offset + remove</code> behind the gap. The gap size is kept between 0 and
209 * {@link #fThreshold}, leading to re-allocation if needed. The content between
210 * <code>offset</code> and <code>offset + add</code> is undefined after this operation.
211 *
212 * @param offset the offset at which a change happens
213 * @param remove the number of character which are removed or overwritten at <code>offset</code>
214 * @param add the number of character which are inserted or overwriting at <code>offset</code>
215 */
216 private void adjustGap(int offset, int remove, int add) {
217 final int oldGapSize= gapSize();
218 final int newGapSize= oldGapSize - add + remove;
219 final bool reuseArray= 0 <= newGapSize && newGapSize <= fThreshold;
220
221 final int newGapStart= offset + add;
222 final int newGapEnd;
223
224 if (reuseArray)
225 newGapEnd= moveGap(offset, remove, oldGapSize, newGapSize, newGapStart);
226 else
227 newGapEnd= reallocate(offset, remove, oldGapSize, newGapSize, newGapStart);
228
229 fGapStart= newGapStart;
230 fGapEnd= newGapEnd;
231 }
232
233 /**
234 * Moves the gap to <code>newGapStart</code>.
235 *
236 * @param offset the change offset
237 * @param remove the number of removed / overwritten characters
238 * @param oldGapSize the old gap size
239 * @param newGapSize the gap size after the change
240 * @param newGapStart the offset in the array to move the gap to
241 * @return the new gap end
242 * @since 3.3
243 */
244 private int moveGap(int offset, int remove, int oldGapSize, int newGapSize, int newGapStart) {
245 /*
246 * No re-allocation necessary. The area between the change offset and gap can be copied
247 * in at most one operation. Don't copy parts that will be overwritten anyway.
248 */
249 final int newGapEnd= newGapStart + newGapSize;
250 if (offset < fGapStart) {
251 int afterRemove= offset + remove;
252 if (afterRemove < fGapStart) {
253 final int betweenSize= fGapStart - afterRemove;
254 arrayCopy(afterRemove, fContent, newGapEnd, betweenSize);
255 }
256 // otherwise, only the gap gets enlarged
257 } else {
258 final int offsetShifted= offset + oldGapSize;
259 final int betweenSize= offsetShifted - fGapEnd; // in the typing case, betweenSize is 0
260 arrayCopy(fGapEnd, fContent, fGapStart, betweenSize);
261 }
262 return newGapEnd;
263 }
264
265 /**
266 * Reallocates a new array and copies the data from the previous one.
267 *
268 * @param offset the change offset
269 * @param remove the number of removed / overwritten characters
270 * @param oldGapSize the old gap size
271 * @param newGapSize the gap size after the change if no re-allocation would occur (can be negative)
272 * @param newGapStart the offset in the array to move the gap to
273 * @return the new gap end
274 * @since 3.3
275 */
276 private int reallocate(int offset, int remove, final int oldGapSize, int newGapSize, final int newGapStart) {
277 // the new content length (without any gap)
278 final int newLength= fContent.length - newGapSize;
279 // the new array size based on the gap factor
280 int newArraySize= (int) (newLength * fSizeMultiplier);
281 newGapSize= newArraySize - newLength;
282
283 // bound the gap size within min/max
284 if (newGapSize < fMinGapSize) {
285 newGapSize= fMinGapSize;
286 newArraySize= newLength + newGapSize;
287 } else if (newGapSize > fMaxGapSize) {
288 newGapSize= fMaxGapSize;
289 newArraySize= newLength + newGapSize;
290 }
291
292 // the upper threshold is always twice the gapsize
293 fThreshold= newGapSize * 2;
294 final char[] newContent= allocate(newArraySize);
295 final int newGapEnd= newGapStart + newGapSize;
296
297 /*
298 * Re-allocation: The old content can be copied in at most 3 operations to the newly allocated
299 * array. Either one of change offset and the gap may come first.
300 * - unchanged area before the change offset / gap
301 * - area between the change offset and the gap (either one may be first)
302 * - rest area after the change offset / after the gap
303 */
304 if (offset < fGapStart) {
305 // change comes before gap
306 arrayCopy(0, newContent, 0, offset);
307 int afterRemove= offset + remove;
308 if (afterRemove < fGapStart) {
309 // removal is completely before the gap
310 final int betweenSize= fGapStart - afterRemove;
311 arrayCopy(afterRemove, newContent, newGapEnd, betweenSize);
312 final int restSize= fContent.length - fGapEnd;
313 arrayCopy(fGapEnd, newContent, newGapEnd + betweenSize, restSize);
314 } else {
315 // removal encompasses the gap
316 afterRemove += oldGapSize;
317 final int restSize= fContent.length - afterRemove;
318 arrayCopy(afterRemove, newContent, newGapEnd, restSize);
319 }
320 } else {
321 // gap comes before change
322 arrayCopy(0, newContent, 0, fGapStart);
323 final int offsetShifted= offset + oldGapSize;
324 final int betweenSize= offsetShifted - fGapEnd;
325 arrayCopy(fGapEnd, newContent, fGapStart, betweenSize);
326 final int afterRemove= offsetShifted + remove;
327 final int restSize= fContent.length - afterRemove;
328 arrayCopy(afterRemove, newContent, newGapEnd, restSize);
329 }
330
331 fContent= newContent;
332 return newGapEnd;
333 }
334
335 /**
336 * Allocates a new <code>char[size]</code>.
337 *
338 * @param size the length of the new array.
339 * @return a newly allocated char array
340 * @since 3.3
341 */
342 private char[] allocate(int size) {
343 return new char[size];
344 }
345
346 /*
347 * Executes System.arraycopy if length !is 0. A length < 0 cannot happen -> don't hide coding
348 * errors by checking for negative lengths.
349 * @since 3.3
350 */
351 private void arrayCopy(int srcPos, char[] dest, int destPos, int length) {
352 if (length !is 0)
353 System.arraycopy(fContent, srcPos, dest, destPos, length);
354 }
355
356 /**
357 * Returns the gap size.
358 *
359 * @return the gap size
360 * @since 3.3
361 */
362 private int gapSize() {
363 return fGapEnd - fGapStart;
364 }
365
366 /**
367 * Returns a copy of the content of this text store.
368 * For internal use only.
369 *
370 * @return a copy of the content of this text store
371 */
372 protected String getContentAsString() {
373 return new String(fContent);
374 }
375
376 /**
377 * Returns the start index of the gap managed by this text store.
378 * For internal use only.
379 *
380 * @return the start index of the gap managed by this text store
381 */
382 protected int getGapStartIndex() {
383 return fGapStart;
384 }
385
386 /**
387 * Returns the end index of the gap managed by this text store.
388 * For internal use only.
389 *
390 * @return the end index of the gap managed by this text store
391 */
392 protected int getGapEndIndex() {
393 return fGapEnd;
394 }
395 }