KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > netbeans > modules > editor > lib2 > highlighting > AbstractOffsetGapList


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.modules.editor.lib2.highlighting;
21
22 import java.util.Collection JavaDoc;
23 import org.netbeans.lib.editor.util.GapList;
24
25 /**
26  * The <code>OffsetGapList</code> is an extension of the gap list storing elements
27  * containing an integer offset.
28  *
29  * <p>In order to perform well the implementation of this list stores its elements
30  * in a sequential order sorted by their offset. This fact affects behavior of some
31  * methods you might be familiar with from the <code>List</code> interface.
32  *
33  * <p>The list updates offsets of elements that it contains according to changes
34  * notified by calling <code>defaultInsertUpdate</code> and <code>defaultRemoveUpdate</code>
35  * methods. Usually this list is used for storing offsets in a <code>java.swing.text.Document</code>
36  * and once an element with an offset is stored in the list the element's offset
37  * is automatically updated when those two methods are called. It is the responsibility
38  * of a user of this list to call the methods.
39  *
40  * <p>Updating offsets of many elements could be a time consuming task. In order
41  * to minimize the overhead the list maintains so called <i>offset gap</i>. The
42  * offset gap is a gap at the position of the last insert with the size of
43  * <code>Integer.MAX_VALUE / 2</code>. When an element is added to the list its
44  * offset gets adjusted and becomes so called <i>raw offset</i>. The relation
45  * between offsets and raw offsets is following:
46  *
47  * <ul>
48  * <li>offset < offsetGapStart : rawOffset = offset</li>
49  * <li>offset > offsetGapStart : rawOffset = offset + offsetGapLength
50  * </ul>
51  *
52  * The equivalent formulas give a recipe for computing an offset from rawOffset:
53  *
54  * <ul>
55  * <li>rawOffset < offsetGapStart : offset = rawOffset</li>
56  * <li>rawOffset > offsetGapStart : offset = rawOffset - offsetGapLength
57  * </ul>
58  *
59  * When characteres are inserted at the position of the gap start
60  * the gap simply gets shrinked and no offset have to be recomputed. Also, when
61  * characters are removed just in front of the gap start the gap gets extended
62  * and again no offset have to be recomputed. Offsets only have to be recomputed
63  * when an insertion/removal happens not at the begginig of the gap. In that case
64  * the gap has to be moved and offsets of any element, which is moved from 'behind'
65  * the gap to a positoin in front of the gap, have to be recalculated. This algorithm
66  * minimizes the number of recalculations needed for updating offsets when editing
67  * a document under normal circumstances.
68  *
69  * <p>The maximum gap size is +1GB (<code>Integer.MAX_VALUE / 2</code>), which
70  * should be enough for most of the cases. The gap size can't be bigger, because
71  * raw offsets of elements behind the gap (i.e. with offset > offsetGapStart)
72  * would exceed the maximum value of <code>Integer</code> and became negative
73  * (i.e. less the zero). If that happend the offsets comparision would get broken.
74  *
75  * <p>This class also supports negative offsets up to a limit of -2GB.
76  *
77  * @author Miloslav Metelka
78  * @version 1.00
79  */

80
81 public abstract class AbstractOffsetGapList<E> extends GapList<E> {
82     
83     private int offsetGapStart; // 28 bytes (24-super + 4)
84

85     private int offsetGapLength = Integer.MAX_VALUE / 2; // 32 bytes
86

87     public AbstractOffsetGapList() {
88     }
89
90     /**
91      * Adds an <code>element</code> to this list. The <code>element</code> is
92      * going to be added to at the position, which is appropriate for the
93      * <code>element</code>'s offset.
94      *
95      * @param element The element to add.
96      * @return Always <code>true</code>.
97      */

98     public final boolean add(E element) {
99         int originalOffset = attachElement(element);
100         setElementRawOffset(element, offset2raw(originalOffset));
101         int index = findOffsetIndex(originalOffset);
102         super.add(index, element);
103         return true;
104     }
105
106     /**
107      * Adds an <code>element</code> to this list at the given position. If the
108      * <code>index</code> is not an appropriate position for the <code>element</code>
109      * to be added at this method will throw an exception.
110      *
111      * @param element The element to add.
112      * @throws IndexOutOfBoundException If the <code>index</code> is not greater
113      * or equal to zero and less or equal to the size of the list.
114      * @throws IllegalStateException If adding the <code>element</code> at the
115      * the <code>index</code> position would break sorting of the list.
116      */

117     public final void add(int index, E element) {
118         if (index < 0 || index > size()) {
119             throw new IndexOutOfBoundsException JavaDoc("index = " + index + " size = " + size()); //NOI18N
120
}
121         
122         int originalOffset = attachElement(element);
123         setElementRawOffset(element, offset2raw(originalOffset));
124
125         boolean ok = true;
126         
127         // check offset of the element at (index - 1)
128
if (index > 0 && elementOffset(index - 1) > originalOffset) {
129             System.out.println("[" + (index - 1) + "] = " + elementOffset(index - 1) + " > {" + index + "} = "+ originalOffset);
130             ok = false;
131         }
132
133         // check offset of the element at index
134
if (index < size() && elementOffset(index) < originalOffset) {
135             System.out.println("[" + index + "] = " + elementOffset(index) + " < {" + index + "} = "+ originalOffset);
136             ok = false;
137         }
138         
139         if (ok) {
140             // the index is valid for the element
141
super.add(index, element);
142         } else {
143             // can't insert the element at this index, the list must remain sorted
144
detachElement(element);
145             throw new IllegalStateException JavaDoc("Can't insert element at index: " + index); //NOI18N
146
}
147     }
148
149     /**
150      * Adds all elements from a collection. Calling this method is equivalent to
151      * calling <code>add(E)</code> method for each element in the collection <code>c<code>.
152      *
153      * @return Always <code>true</code>.
154      */

155     public final boolean addAll(Collection JavaDoc<? extends E> c) {
156         for (E e : c) {
157             add(e);
158         }
159         return true;
160     }
161
162     /**
163      * This operation is not supported by this list.
164      *
165      * @throws UnsupportedOperationException
166      */

167     public final boolean addAll(int index, Collection JavaDoc<? extends E> c) {
168         throw new UnsupportedOperationException JavaDoc("This is an illegal operation on OffsetGapList."); //NOI18N
169
}
170
171     /**
172      * This operation is not supported by this list.
173      *
174      * @throws UnsupportedOperationException
175      */

176     public final boolean addArray(int index, Object JavaDoc[] elements) {
177         throw new UnsupportedOperationException JavaDoc("This is an illegal operation on OffsetGapList."); //NOI18N
178
}
179
180     /**
181      * This operation is not supported by this list.
182      *
183      * @throws UnsupportedOperationException
184      */

185     public final boolean addArray(int index, Object JavaDoc[] elements, int off, int len) {
186         throw new UnsupportedOperationException JavaDoc("This is an illegal operation on OffsetGapList."); //NOI18N
187
}
188
189     /**
190      * Finds the position of the <code>element</code> in this list.
191      *
192      * @return The index of the <code>element</code> or -1 if the element can't
193      * be find.
194      */

195     public final int indexOf(Object JavaDoc o) {
196         E element = getAttachedElement(o);
197         if (element != null) {
198             int offset = elementOffset(element);
199             int idx = findElementIndex(offset);
200             if (idx >= 0) {
201                 for (int i = idx; i < size() && elementOffset(i) == offset; i++) {
202                     if (element == get(i)) {
203                         return i;
204                     }
205                 }
206             }
207         }
208         return -1;
209     }
210
211     /**
212      * The same as the <code>indexOf(E)</code> method. The <code>OffsetGapList</code>
213      * does not allow adding one element twice.
214      *
215      * @return The index of the <code>element</code> or -1 if the element can't
216      * be find.
217      */

218     public final int lastIndexOf(Object JavaDoc element) {
219         return indexOf(element);
220     }
221
222     /**
223      * Replaces an element of this list at the given position with a new element.
224      * If the new <code>element</code> can't be placed at the <code>index</code>
225      * position this method will throw an exception.
226      *
227      * @param index The position to add the element at.
228      * @param element The element to add.
229      *
230      * @return The old elemet, which was originally stored at the <code>index</code>
231      * position.
232      */

233     public final E set(int index, E element) {
234         if (index < 0 || index >= size()) {
235             throw new IndexOutOfBoundsException JavaDoc("index = " + index + " size = " + size()); //NOI18N
236
}
237         
238         int originalOffset = attachElement(element);
239         setElementRawOffset(element, offset2raw(originalOffset));
240         
241         boolean ok = true;
242         
243         // check offset of the element at (index - 1)
244
if (index > 0 && elementOffset(index - 1) > originalOffset) {
245             System.out.println("[" + (index - 1) + "] = " + elementOffset(index - 1) + " > {" + index + "} = "+ originalOffset);
246             ok = false;
247         }
248
249         // check offset of the element at (index + 1)
250
if (index + 1 < size() && elementOffset(index + 1) < originalOffset) {
251             System.out.println("[" + (index + 1) + "] = " + elementOffset(index + 1) + " < {" + index + "} = "+ originalOffset);
252             ok = false;
253         }
254         
255         if (ok) {
256             // the index is valid for the element
257
E oldElement = super.set(index, element);
258             detachElement(oldElement);
259             return oldElement;
260         } else {
261             // can't insert the element at this index, the list must remain sorted
262
detachElement(element);
263             throw new IllegalStateException JavaDoc("Can't insert element at index: " + index); //NOI18N
264
}
265     }
266
267     /**
268      * This operation is not supported by this list.
269      *
270      * @throws UnsupportedOperationException
271      */

272     public final void swap(int index1, int index2) {
273         throw new UnsupportedOperationException JavaDoc("This is an illegal operation on OffsetGapList."); //NOI18N
274
}
275     
276     /**
277      * Gets the raw offset of the given element.
278      *
279      * @param elem The element to get the raw offset for.
280      * @return The raw offset of the element.
281      */

282     protected abstract int elementRawOffset(E elem);
283
284     /**
285      * Sets the raw offset of the given element currently stored in the list.
286      *
287      * @param elem element currently stored in the list.
288      * @param rawOffset raw offset to be stored in the given element.
289      */

290     protected abstract void setElementRawOffset(E elem, int rawOffset);
291
292     /**
293      * Gets called when an element is being added to the list. This is the first
294      * method that will be called when an element is added to the list. The method
295      * should return the original offset of the element. This offset will be
296      * used for calculating element's raw offset and setting it by calling
297      * the <code>setElementRawOffset</code>. Since that time the elemnt should
298      * only keep its raw offset and use the <code>raw2offset</code> method for
299      * translating it to the real offset again.
300      *
301      * @param elem The element being added to the list.
302      * @return The original offset of the element (i.e. offset at the time when
303      * the element is added to this list).
304      */

305     protected abstract int attachElement(E elem);
306
307     /**
308      * Gets called when an element is removed from this list. After this method
309      * is called the element should never try to use <code>raw2offset</code> to
310      * get its real offset. The element is removed from the list and its raw offset
311      * is no longer updated by the list and therefore can't be used for computing
312      * the real offset.
313      *
314      * @param elem The element to detach from the list.
315      */

316     protected abstract void detachElement(E elem);
317     
318     /**
319      * Recognizes an object as an element of this list. If the object passed in
320      * can be recognized as an element attached to this list the method should
321      * return its type-casted version. If the object is not of a right type or
322      * does not belong to this list the method should return <code>null</code>.
323      *
324      * @param o The object to recognize.
325      * @return The type-casted version of the object (i.e. an element of this list)
326      * or <code>null</code> if the element does not belong to the list.
327      */

328     protected abstract E getAttachedElement(Object JavaDoc o);
329     
330     /**
331      * Get the offset of the element stored in the list.
332      * <br>
333      * The raw offset stored in the element is preprocessed to become a real offset.
334      *
335      * @param elem element stored in the list.
336      * @return offset of the element.
337      */

338     protected int elementOffset(E elem) {
339         return raw2Offset(elementRawOffset(elem));
340     }
341     
342     /**
343      * Get the offset of the element stored in the list at the given index.
344      * <br>
345      * The raw offset stored in the element is preprocessed to become a real offset.
346      *
347      * @param index of the element in the list.
348      * @return offset of the element.
349      */

350     protected int elementOffset(int index) {
351         return elementOffset(get(index));
352     }
353     
354     /**
355      * Inform the list that there was an insert done into an underlying storage
356      * (e.g. a swing document) which should move up offsets of the elements that have
357      * their offset greater or equal to the insertion offset.
358      *
359      * <p>
360      * Subclasses can build their own way of updating
361      * and they are not required to use this method.
362      *
363      * @param offset offset at which the insertion occurred.
364      * @param length length of the inserted area.
365      */

366     public void defaultInsertUpdate(int offset, int length) {
367         assert (length >= 0);
368         if (offset != offsetGapStart()) {
369             moveOffsetGap(offset, findOffsetIndex(offset));
370         }
371         updateOffsetGapLength(-length); // Shrink the offset gap to simulate insertion
372
// Optimize for subsequent insert by moving gap start to the end
373
// of the just performed insertion.
374
// This way the subsequent insert will not need to call moveOffsetGap() at all.
375
// It's less optimal for insert-remove pairs (e.g. overwrite mode)
376
// but they should be less frequent.
377
updateOffsetGapStart(length);
378     }
379
380     /**
381      * Inform the list that there was a removal done into an underlying storage
382      * (e.g. a swing document) which should move down offsets of the elements
383      * that have their offsets greater than the removal offset.
384      * <br>
385      * The offsets inside the removal area will be moved to its begining.
386      * <p>
387      * Subclasses can build their own way of updating
388      * and they are not required to use this method.
389      *
390      * @param offset offset at which the removal occurred.
391      * @param length length of the removed area.
392      */

393     public void defaultRemoveUpdate(int offset, int length) {
394         assert (length >= 0);
395         int index = findOffsetIndex(offset);
396         if (offset != offsetGapStart()) {
397             moveOffsetGap(offset, index);
398         }
399         int size = size();
400         int removeAreaEndRawOffset = offset + offsetGapLength + length;
401         // Move all elements inside the removed area to its end
402
// so that after update of the offset gap length they appear
403
// at the begining of the removal offset area
404
while (index < size) {
405             E elem = get(index++);
406             if (elementRawOffset(elem) < removeAreaEndRawOffset) {
407                 setElementRawOffset(elem, removeAreaEndRawOffset);
408             } else { // all subsequent offsets are higher
409
break;
410             }
411         }
412         updateOffsetGapLength(+length);
413     }
414     
415     /**
416      * Move the offset gap so that it's on the requested offset.
417      * <br>
418      * This method can be used when the index of the first element
419      * at the given offset was precomputed already.
420      *
421      * <p>
422      * <b>Note:</b> Improper use of this may logically damage
423      * offsets of the elements contained in the list.
424      *
425      * @param offset offset to which the <code>offsetGapStart</code>
426      * should be assigned.
427      * @param index index of the first element in the list
428      * that has an offset that is greater or equal that the given offset parameter.
429      * <br>
430      * It may be computed by {@link #findElementIndex(int)}.
431      */

432     protected final void moveOffsetGap(int offset, int index) {
433         if (offset < offsetGapStart) { // need to check items above index
434
int bound = size();
435             for (int i = index; i < bound; i++) {
436                 E elem = get(i);
437                 int rawOffset = elementRawOffset(elem);
438                 if (rawOffset < offsetGapStart) {
439                     setElementRawOffset(elem, rawOffset + offsetGapLength);
440                 } else {
441                     break;
442                 }
443             }
444
445         } else { // check items below index
446
for (int i = index - 1; i >= 0; i--) {
447                 E elem = get(i);
448                 int rawOffset = elementRawOffset(elem);
449                 if (rawOffset >= offsetGapStart) {
450                     setElementRawOffset(elem, rawOffset - offsetGapLength);
451                 } else {
452                     break;
453                 }
454             }
455         }
456         offsetGapStart = offset;
457     }
458
459     /**
460      * Obtain the start of the offset gap.
461      *
462      * @return start of the offset gap.
463      */

464     protected final int offsetGapStart() {
465         return offsetGapStart;
466     }
467
468     /**
469      * Update the offset gap start by the given delta.
470      * <br>
471      * This may be needed e.g. after insertion/removal was done
472      * in the document.
473      *
474      * <p>
475      * <b>Note:</b> Improper use of this may logically damage
476      * offsets of the elements contained in the list.
477      */

478     protected final void updateOffsetGapStart(int offsetDelta) {
479         offsetGapStart += offsetDelta;
480     }
481
482     /**
483      * Obtain the length of the offset gap.
484      *
485      * @return length of the offset gap.
486      */

487     protected final int offsetGapLength() {
488         return offsetGapLength;
489     }
490
491     /**
492      * Update the offset gap length by the given delta.
493      * <br>
494      * This may be needed e.g. after insertion/removal was done
495      * in the document.
496      *
497      * <p>
498      * <b>Note:</b> Improper use of this may logically damage
499      * offsets of the elements contained in the list.
500      */

501     protected final void updateOffsetGapLength(int offsetGapLengthDelta) {
502         offsetGapLength += offsetGapLengthDelta;
503         assert (offsetGapLength >= 0); // prevent overflow to negative numbers
504
}
505
506     /**
507      * Find an index of the first element at the given offset in the list
508      * by using binary search.
509      *
510      * @param offset offset of the element
511      * @return index of the element. If there is no element with that
512      * index then the index of the next element (with the greater offset)
513      * (or size of the list) will be returned.
514      * <br>
515      * If there are multiple items with the same offset then the first one of them
516      * will be returned.
517      */

518     protected final int findOffsetIndex(int offset) {
519         int index = findElementIndex(offset);
520         return index < 0 ? -index - 1 : index;
521     }
522
523     /**
524      * Finds an index of the first element at the given offset in the list
525      * by using binary search.
526      *
527      * @param offset The offset of the element to find.
528      * @param lowIdx The lowest index to look at.
529      * @param highIdx The highest index to look at.
530      *
531      * @return index of the element with the given <code>offset</code>,
532      * if it is contained in the list;
533      * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
534      * <i>insertion point</i> is defined as the point at which an
535      * element the <code>offset</code> would be inserted into the list:
536      * the index of the first
537      * element with its offset greater than the <code>offset</code> prameter,
538      * or <tt>list.size()</tt>, if all
539      * elements in the list have offsets less than the specified <code>offset</code>.
540      * Note that this guarantees that the return value will be &gt;= 0 if
541      * and only if the element with the given <code>offset</code> is found.
542      */

543     public final int findElementIndex(int offset, int lowIdx, int highIdx) {
544         if (lowIdx < 0 || highIdx > size() - 1) {
545             throw new IndexOutOfBoundsException JavaDoc("lowIdx = " + lowIdx + ", highIdx = " + highIdx + ", size = " + size());
546         }
547         
548         int low = lowIdx;
549         int high = highIdx;
550
551         while (low <= high) {
552             int index = (low + high) >> 1; // mid in the binary search
553
int elemOffset = elementOffset(index);
554
555             if (elemOffset < offset) {
556                 low = index + 1;
557
558             } else if (elemOffset > offset) {
559                 high = index - 1;
560
561             } else { // exact offset found at index
562
while (index > 0) {
563                     index--;
564                     if (elementOffset(index) < offset) {
565                         index++;
566                         break;
567                     }
568                 }
569                 return index;
570             }
571         }
572         
573         return -(low + 1);
574     }
575
576     public final int findElementIndex(int offset) {
577         return findElementIndex(offset, 0, size() - 1);
578     }
579     
580     /**
581      * This method updates element's offset (shifts it above offset gap if necessary)
582      * before adding the element to the list.
583      * <bt/>
584      * This method should be called before (or after) the element is physically added
585      * to the list. If the element is added below the offset gap
586      * then calling of this method is not necessary.
587      */

588     protected void updateElementOffsetAdd(E elem) {
589         int rawOffset = elementRawOffset(elem);
590         if (rawOffset >= offsetGapStart) {
591             setElementRawOffset(elem, rawOffset + offsetGapLength);
592         }
593     }
594
595     /**
596      * This method updates element's offset (shifts it below offset gap if necessary)
597      * before (or after) the element gets removed from the list.
598      * <br/>
599      * This method should be called after the element is physically removed
600      * from the list and it's desired that it retains its natural offset
601      * (not possibly shifted by the offset gap length).
602      * <br/>
603      * If the element was located below the offset gap prior removal
604      * then calling of this method is not necessary.
605      */

606     protected void updateElementOffsetRemove(E elem) {
607         int rawOffset = elementRawOffset(elem);
608         if (rawOffset >= offsetGapStart) {
609             setElementRawOffset(elem, rawOffset - offsetGapLength);
610         }
611     }
612     
613     /**
614      * Translate raw offset into real offset.
615      *
616      * @param rawOffset raw offset stored in an element.
617      * @return real offset that the element is supposed to have.
618      */

619     protected final int raw2Offset(int rawOffset) {
620         return (rawOffset < offsetGapStart)
621             ? rawOffset
622             : rawOffset - offsetGapLength;
623     }
624     
625     /**
626      * Translate regular offset to raw offset.
627      *
628      * @param offset regular offset.
629      * @return raw offset that can be used in elements.
630      */

631     protected final int offset2raw(int offset) {
632         return (offset < offsetGapStart)
633             ? offset
634             : offset + offsetGapLength;
635     }
636     
637     protected void consistencyCheck() {
638         super.consistencyCheck();
639
640         if (offsetGapLength < 0) {
641             consistencyError("offsetGapLength < 0"); // NOI18N
642
}
643
644         int lastRawOffset = Integer.MIN_VALUE;
645         int lastOffset = Integer.MIN_VALUE;
646         int size = size();
647         for (int i = 0; i < size; i++) {
648             E elem = get(i);
649             int rawOffset = elementRawOffset(elem);
650             int offset = raw2Offset(rawOffset);
651             if (rawOffset < lastRawOffset) {
652                 consistencyError("Invalid rawOffset=" // NOI18N
653
+ rawOffset + " >= lastRawOffset=" + lastRawOffset // NOI18N
654
+ " at index=" + i // NOI18N
655
);
656             }
657             if (offset < lastOffset) {
658                 consistencyError("Invalid offset=" // NOI18N
659
+ offset + " >= lastOffset=" + lastOffset // NOI18N
660
+ " at index=" + i // NOI18N
661
);
662             }
663             lastRawOffset = rawOffset;
664             lastOffset = offset;
665         }
666     }
667     
668     protected String JavaDoc dumpInternals() {
669         return super.dumpInternals() + ", offGap(s=" + offsetGapStart
670         + ", l=" + offsetGapLength + ")";
671     }
672 }
673
Popular Tags