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  ;
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  ("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  ("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  <? 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  <? extends E> c) {
168         throw new UnsupportedOperationException  ("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  [] elements) {
177         throw new UnsupportedOperationException  ("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  [] elements, int off, int len) {
186         throw new UnsupportedOperationException  ("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   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   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  ("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  ("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  ("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   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  ("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   dumpInternals() {
669         return super.dumpInternals() + ", offGap(s=" + offsetGapStart
670         + ", l=" + offsetGapLength + ")";
671     }
672 }
673
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags