KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > netbeans > lib > editor > util > FlyOffsetGapList


1 /*
2  * The contents of this file are subject to the terms of the Common Development
3  * and Distribution License (the License). You may not use this file except in
4  * compliance with the License.
5  *
6  * You can obtain a copy of the License at http://www.netbeans.org/cddl.html
7  * or http://www.netbeans.org/cddl.txt.
8  *
9  * When distributing Covered Code, include this CDDL Header Notice in each file
10  * and include the License file at http://www.netbeans.org/cddl.txt.
11  * If applicable, add the following below the CDDL Header, with the fields
12  * enclosed by brackets [] replaced by your own identifying information:
13  * "Portions Copyrighted [year] [name of copyright owner]"
14  *
15  * The Original Software is NetBeans. The Initial Developer of the Original
16  * Software is Sun Microsystems, Inc. Portions Copyright 1997-2006 Sun
17  * Microsystems, Inc. All Rights Reserved.
18  */
19
20 package org.netbeans.lib.editor.util;
21
22 /**
23  * A variant of {@link OffsetGapList} additionally supporting
24  * flyweight (non-modifiable) elements.
25  * <br>
26  * Flyweight elements may not be modified during update operations
27  * when offset gap is moved and the raw offset must be updated
28  * or when the flyweight element is added or removed from the list.
29  *
30  * @author Miloslav Metelka
31  * @version 1.00
32  */
33
34 public abstract class FlyOffsetGapList<E> extends GapList<E> {
35
36     private int offsetGapStart; // 28 bytes (24-super + 4)
37
38     private int offsetGapLength = Integer.MAX_VALUE / 2; // 32 bytes
39
40     public FlyOffsetGapList() {
41     }
42     
43     /**
44      * Get the raw offset of the given element currently stored in the list.
45      *
46      * @param elem element currently stored in the list.
47      * @return raw offset of the element. It needs to be preprocessed
48      * by {@link #raw2RelOffset(int)} to become the real offset.
49      */
50     protected abstract int elementRawOffset(E elem);
51
52     /**
53      * Set the raw offset of the given element currently stored in the list.
54      *
55      * @param elem element currently stored in the list.
56      * @param rawOffset raw offset to be stored in the given element.
57      */
58     protected abstract void setElementRawOffset(E elem, int rawOffset);
59     
60     /**
61      * Check whether the given element is flyweight and therefore skipped
62      * during update operations.
63      *
64      * @return true if the given element is flyweight or false otherwise.
65      */
66     protected abstract boolean isElementFlyweight(E elem);
67     
68     /**
69      * Get length of an element (assuming it has a length when it has
70      * an offset).
71      * <br>
72      * As there can be flyweight elements it's assumed that the flyweight
73      * elements occupy certain offset area.
74      * <br>
75      * This method is primarily used for measuring of flyweight elements
76      * (except consistency check) but subclasses may extend its use to any element.
77      */
78     protected abstract int elementLength(E elem);
79
80     /**
81      * Return base starting offset to which all the tokens contained in this list
82      * are related. The absolute token's offset is a sum of this start offset plus
83      * token's offset.
84      * <br/>
85      * There may be just flyweight element(s) at the begining of the list
86      * so the start offset gives the necessary basing.
87      * <br/>
88      * By default it's zero.
89      */
90     protected int startOffset() {
91         return 0;
92     }
93     
94     /**
95      * Get the offset of an element stored in the list at the given index.
96      * <br>
97      * The raw offset stored in the element is preprocessed to become a real offset.
98      * <br>
99      * Flyweight elements are supported and they are asked for occupied length
100      * by {@link #elementLength(Object)} and its sum
101      * plus the first preceding non-flyweight element's offset is returned.
102      * <br>
103      * If there is no preceding non-flyweight element a zero offset
104      * is used as a base.
105      *
106      * @param index of the element in the list.
107      * @return offset of the element.
108      * @throws IndexOutOfBoundsException if index >= size() or lower than zero
109      */
110     protected final int elementOffset(int index) {
111         E elem = get(index);
112         int offset;
113         if (isElementFlyweight(elem)) {
114             offset = 0;
115             while (--index >= 0) {
116                 elem = get(index);
117                 offset += elementLength(elem);
118                 if (!isElementFlyweight(elem)) {
119                     // non-flyweight element
120 offset += raw2RelOffset(elementRawOffset(elem));
121                     break;
122                 }
123             }
124             
125         } else { // non-flyweight
126 offset = raw2RelOffset(elementRawOffset(elem));
127         }
128         return startOffset() + offset;
129     }
130     
131     /**
132      * Get the offset of an element stored in the list at the given index
133      * like {@link #elementOffset(int)} does or get end offset of the last element
134      * if {@link #size()} is passed as index parameter.
135      *
136      * @param index of the element in the list.
137      * Index equal to <code>size()</code> can be used
138      * @return offset of the element.
139      * @throws IndexOutOfBoundsException if index > size() or lower than zero
140      */
141     protected final int elementOrEndOffset(int indexOrSize) {
142         E elem;
143         int offset;
144         // Fail for index > size() and for == size() use end of the last element
145 if (indexOrSize == size() || isElementFlyweight(elem = get(indexOrSize))) {
146             offset = 0;
147             while (--indexOrSize >= 0) {
148                 elem = get(indexOrSize);
149                 offset += elementLength(elem);
150                 if (!isElementFlyweight(elem)) {
151                     // non-flyweight element
152 offset += raw2RelOffset(elementRawOffset(elem));
153                     break;
154                 }
155             }
156             
157         } else { // non-flyweight
158 offset = raw2RelOffset(elementRawOffset(elem));
159         }
160         return startOffset() + offset;
161     }
162     
163     /**
164      * Inform the list that there was an insert done into an underlying storage
165      * (e.g. a swing document) which should move up offsets of the elements that have
166      * their offset greater or equal to the insertion offset.
167      *
168      * <p>
169      * Subclasses can build their own way of updating
170      * and they are not required to use this method.
171      *
172      * @param offset offset at which the insertion occurred.
173      * @param length length of the inserted area.
174      */
175     public void defaultInsertUpdate(int offset, int length) {
176         assert (length >= 0);
177         if (offset != offsetGapStart()) {
178             moveOffsetGap(offset, findElementIndex(offset));
179         }
180         updateOffsetGapLength(-length);
181         // Optimize for subsequent insert by moving gap start to the end
182 // of the just performed insertion.
183 // This way the subsequent insert will not need to call moveOffsetGap() at all.
184 // It's less optimal for insert-remove pairs (e.g. overwrite mode)
185 // but they should be less frequent.
186 updateOffsetGapStart(length);
187     }
188
189     /**
190      * Inform the list that there was a removal done into an underlying storage
191      * (e.g. a swing document) which should move down offsets of the elements
192      * that have their offsets greater than the removal offset.
193      * <br>
194      * The offsets inside the removal area will be moved to its begining.
195      * <p>
196      * Subclasses can build their own way of updating
197      * and they are not required to use this method.
198      *
199      * @param offset offset at which the removal occurred.
200      * @param length length of the removed area.
201      */
202     public void defaultRemoveUpdate(int offset, int length) {
203         assert (length >= 0);
204         int index = findElementIndex(offset);
205         if (offset != offsetGapStart()) {
206             moveOffsetGap(offset, index);
207         }
208         int size = size();
209         int removeAreaEndRawOffset = offset + offsetGapLength + length;
210         // Move all elements inside the removed area to its end
211 // so that after update of the offset gap length they appear
212 // at the begining of the removal offset area
213 while (index < size) {
214             E elem = get(index++);
215             if (!isElementFlyweight(elem)) {
216                 if (elementRawOffset(elem) < removeAreaEndRawOffset) {
217                     setElementRawOffset(elem, removeAreaEndRawOffset);
218                 } else { // all subsequent offsets are higher
219 break;
220                 }
221             }
222         }
223         updateOffsetGapLength(+length);
224     }
225     
226     /**
227      * Move the offset gap so that it's on the requested offset.
228      * <br>
229      * This method can be used when the index of the first element
230      * at the given offset was precomputed already.
231      *
232      * <p>
233      * <b>Note:</b> Improper use of this may logically damage
234      * offsets of the elements contained in the list.
235      *
236      * @param offset offset to which the <code>offsetGapStart</code>
237      * should be assigned.
238      * @param index index of the first element at the given offset in the list.
239      * <br>
240      * It may be computed by {@link #findElementIndex(int)}.
241      */
242     protected final void moveOffsetGap(int offset, int index) {
243         if (offset < offsetGapStart) { // need to check items above index
244 int bound = size();
245             for (int i = index; i < bound; i++) {
246                 E elem = get(i);
247                 if (!isElementFlyweight(elem)) {
248                     int rawOffset = elementRawOffset(elem);
249                     if (rawOffset < offsetGapStart) {
250                         setElementRawOffset(elem, rawOffset + offsetGapLength);
251                     } else {
252                         break;
253                     }
254                 }
255             }
256
257         } else { // check items below index
258 for (int i = index - 1; i >= 0; i--) {
259                 E elem = get(i);
260                 if (!isElementFlyweight(elem)) {
261                     int rawOffset = elementRawOffset(elem);
262                     if (rawOffset >= offsetGapStart) {
263                         setElementRawOffset(elem, rawOffset - offsetGapLength);
264                     } else {
265                         break;
266                     }
267                 }
268             }
269         }
270         offsetGapStart = offset;
271     }
272
273     protected final int offsetGapStart() {
274         return offsetGapStart;
275     }
276
277     /**
278      * Update the offset gap length by the given delta.
279      * <br>
280      * This may be needed e.g. after insertion/removal was done
281      * in the document.
282      *
283      * <p>
284      * <b>Note:</b> Improper use of this may logically damage
285      * offsets of the elements contained in the list.
286      */
287     protected final void updateOffsetGapStart(int offsetDelta) {
288         offsetGapStart += offsetDelta;
289     }
290
291     protected final int offsetGapLength() {
292         return offsetGapLength;
293     }
294
295     /**
296      * Update the offset gap length by the given delta.
297      * <br>
298      * This may be needed e.g. after insertion/removal was done
299      * in the document.
300      *
301      * <p>
302      * <b>Note:</b> Improper use of this may logically damage
303      * offsets of the elements contained in the list.
304      */
305     protected final void updateOffsetGapLength(int offsetGapLengthDelta) {
306         offsetGapLength += offsetGapLengthDelta;
307         assert (offsetGapLength >= 0); // prevent overflow to negative numbers
308 }
309
310     /**
311      * Find an index of the first element at the given offset in the list
312      * by using binary search.
313      *
314      * @param offset offset of the element
315      * @return index of the element. If there is no element with that
316      * index then the index of the next element (with the greater offset)
317      * (or size of the list) will be returned.
318      * <br>
319      * If there are multiple items with the same offset then the first one of them
320      * will be returned.
321      */
322     protected final int findElementIndex(int offset) {
323         int low = 0;
324         int high = size() - 1;
325
326         while (low <= high) {
327             int index = (low + high) / 2; // mid in the binary search
328 int elemOffset = elementOffset(index);
329
330             if (elemOffset < offset) {
331                 low = index + 1;
332
333             } else if (elemOffset > offset) {
334                 high = index - 1;
335
336             } else { // exact offset found at index
337 while (index > 0) {
338                     index--;
339                     if (elementOffset(index) < offset) {
340                         index++;
341                         break;
342                     }
343                 }
344                 low = index;
345                 break;
346             }
347         }
348         return low;
349     }
350
351     /**
352      * This method updates element's offset (shifts it above offset gap if necessary)
353      * before adding the element to the list.
354      * <bt/>
355      * This method should be called before (or after) the element is physically added
356      * to the list. If the element is added below the offset gap
357      * then calling of this method is not necessary.
358      */
359     protected void updateElementOffsetAdd(E elem) {
360         if (!isElementFlyweight(elem)) {
361             int offset = elementRawOffset(elem); // not raw yet
362 setElementRawOffset(elem, offset2Raw(offset));
363         }
364     }
365
366     /**
367      * This method updates element's offset (shifts it below offset gap if necessary)
368      * before (or after) the element gets removed from the list.
369      * <br/>
370      * This method should be called after the element is physically removed
371      * from the list and it's desired that it retains its natural offset
372      * (not possibly shifted by the offset gap length).
373      * <br/>
374      * If the element was located below the offset gap prior removal
375      * then calling of this method is not necessary.
376      */
377     protected void updateElementOffsetRemove(E elem) {
378         if (!isElementFlyweight(elem)) {
379             int rawOffset = raw2RelOffset(elementRawOffset(elem));
380             rawOffset += startOffset();
381             setElementRawOffset(elem, rawOffset);
382         }
383     }
384     
385     /**
386      * Translate raw offset into real offset.
387      *
388      * @param rawOffset raw offset stored in an element.
389      * @return real offset that the element is supposed to have.
390      */
391     private int raw2RelOffset(int rawOffset) {
392         return (rawOffset < offsetGapStart)
393             ? rawOffset
394             : rawOffset - offsetGapLength;
395     }
396     
397     /**
398      * Convert the given offset into raw form suitable for storing in this list.
399      *
400      * @param offset >=0 absolute offset.
401      * @return corresponding raw offset.
402      */
403     protected final int offset2Raw(int offset) {
404         offset -= startOffset();
405         if (offset >= offsetGapStart) {
406             offset += offsetGapLength;
407         }
408         return offset;
409     }
410     
411     /**
412      * Check consistency of this list.
413      *
414      * @param checkElementLength whether {@link #elementLength(Object)}
415      * should be called to check lengths of the elements and verify
416      * that the offsets are in concert with the offsets.
417      */
418     protected void consistencyCheck(boolean checkElementLength) {
419         super.consistencyCheck();
420
421         if (offsetGapLength < 0) {
422             consistencyError("offsetGapLength < 0"); // NOI18N
423 }
424
425         int lastRawOffset = Integer.MIN_VALUE;
426         int lastOffset = Integer.MIN_VALUE;
427         int lastEndOffset = lastOffset;
428         int size = size();
429         for (int i = 0; i < size; i++) {
430             E elem = get(i);
431             if (!isElementFlyweight(elem)) {
432                 int rawOffset = elementRawOffset(elem);
433                 int offset = raw2RelOffset(rawOffset);
434                 if (rawOffset < lastRawOffset) {
435                     consistencyError("Invalid rawOffset=" // NOI18N
436 + rawOffset + " >= lastRawOffset=" + lastRawOffset // NOI18N
437 + " at index=" + i // NOI18N
438 );
439                 }
440                 if (offset < lastOffset) {
441                     consistencyError("Invalid offset=" // NOI18N
442 + offset + " >= lastOffset=" + lastOffset // NOI18N
443 + " at index=" + i // NOI18N
444 );
445                 }
446                 if (checkElementLength) { // Use the element's length
447 int length = elementLength(elem);
448                     if (i == 0) {
449                         lastEndOffset = offset;
450                     }
451                     if (offset != lastEndOffset) {
452                         consistencyError("Offset=" + offset // NOI18N
453 + " differs from lastEndOffset=" + lastEndOffset // NOI18N
454 + " at index=" + i // NOI18N
455 );
456                     }
457                     lastEndOffset += length;
458                 }
459                 lastRawOffset = rawOffset;
460                 lastOffset = offset;
461
462             } else { // Flyweight element
463 if (checkElementLength) {
464                     if (i == 0) {
465                         // Assume zero as the base offset when flyweight element is first
466 lastEndOffset = 0;
467                     }
468                     int length = elementLength(elem);
469                     lastEndOffset += length;
470                 }
471             }
472         }
473     }
474     
475     protected String JavaDoc dumpInternals() {
476         return super.dumpInternals() + ", offGap(s=" + offsetGapStart
477         + ", l=" + offsetGapLength + ")";
478     }
479
480 }
481
Popular Tags