OffsetGapList


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   * Extension of the gap list which is expected to store elements
24   * that have an integer offset stored in them.
25   * <br>
26   * The elements must be stored in the list in an ascending order.
27   * <br>
28   * To efficiently manage offsets that need to change upon
29   * inserts and removes into an underlying storage (e.g. a swing document)
30   * the list maintains an offset gap that gets moved
31   * and shrinked/extended according to inserts/removals.
32   *
33   * <p>
34   * The physical raw offset stored in the element needs to be preprocessed
35   * to get the real offset value.
36   * <br>
37   * In short the raw offset is either the actual offset in case
38   * the offset gap is above it (greater or equal to <code>offsetGapStart</code> value)
39   * or, it's the actual offset plus the offset gap length otherwise.
40   *
41   * <p>
42   * Offsets up to +1GB (<code>Integer.MAX_VALUE / 2</code>)
43   * can be handled by this class which should be sufficient
44   * for most uses.
45   * <br>
46   * It's not +2GB as then the offsets shifted above the offset gap
47   * would overflow and be below zero which would break
48   * the comparisons whether the offset is below offset gap start.
49   * <br>
50   * Negative offsets are supported as well with a limit of -2GB.
51   *
52   * @author Miloslav Metelka
53   * @version 1.00
54   */
55  
56  public abstract class OffsetGapList<E> extends GapList<E> {
57      
58      private int offsetGapStart; // 28 bytes (24-super + 4)
59  
60      private int offsetGapLength = Integer.MAX_VALUE / 2; // 32 bytes
61  
62      public OffsetGapList() {
63      }
64      
65      /**
66       * Get the raw offset of the given element currently stored in the list.
67       *
68       * @param elem element currently stored in the list.
69       * @return raw offset of the element. It needs to be preprocessed
70       * by {@link #raw2Offset(int)} to become the real offset.
71       */
72      protected abstract int elementRawOffset(E elem);
73  
74      /**
75       * Set the raw offset of the given element currently stored in the list.
76       *
77       * @param elem element currently stored in the list.
78       * @param rawOffset raw offset to be stored in the given element.
79       */
80      protected abstract void setElementRawOffset(E elem, int rawOffset);
81      
82      /**
83       * Get the offset of the element stored in the list.
84       * <br>
85       * The raw offset stored in the element is preprocessed to become a real offset.
86       *
87       * @param elem element stored in the list.
88       * @return offset of the element.
89       */
90      protected int elementOffset(E elem) {
91          return raw2Offset(elementRawOffset(elem));
92      }
93      
94      /**
95       * Get the offset of the 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       *
99       * @param index of the element in the list.
100      * @return offset of the element.
101      * @throws IndexOutOfBoundsException if index >= size() or lower than zero
102      */
103     protected int elementOffset(int index) {
104         return elementOffset(get(index));
105     }
106     
107     /**
108      * Inform the list that there was an insert done into an underlying storage
109      * (e.g. a swing document) which should move up offsets of the elements that have
110      * their offset greater or equal to the insertion offset.
111      *
112      * <p>
113      * Subclasses can build their own way of updating
114      * and they are not required to use this method.
115      *
116      * @param offset offset at which the insertion occurred.
117      * @param length length of the inserted area.
118      */
119     public void defaultInsertUpdate(int offset, int length) {
120         assert (length >= 0);
121         if (offset != offsetGapStart()) {
122             moveOffsetGap(offset, findElementIndex(offset));
123         }
124         updateOffsetGapLength(-length); // Shrink the offset gap to simulate insertion
125         // Optimize for subsequent insert by moving gap start to the end
126         // of the just performed insertion.
127         // This way the subsequent insert will not need to call moveOffsetGap() at all.
128         // It's less optimal for insert-remove pairs (e.g. overwrite mode)
129         // but they should be less frequent.
130         updateOffsetGapStart(length);
131     }
132 
133     /**
134      * Inform the list that there was a removal done into an underlying storage
135      * (e.g. a swing document) which should move down offsets of the elements
136      * that have their offsets greater than the removal offset.
137      * <br>
138      * The offsets inside the removal area will be moved to its begining.
139      * <p>
140      * Subclasses can build their own way of updating
141      * and they are not required to use this method.
142      *
143      * @param offset offset at which the removal occurred.
144      * @param length length of the removed area.
145      */
146     public void defaultRemoveUpdate(int offset, int length) {
147         assert (length >= 0);
148         int index = findElementIndex(offset);
149         if (offset != offsetGapStart()) {
150             moveOffsetGap(offset, index);
151         }
152         int size = size();
153         int removeAreaEndRawOffset = offset + offsetGapLength + length;
154         // Move all elements inside the removed area to its end
155         // so that after update of the offset gap length they appear
156         // at the begining of the removal offset area
157         while (index < size) {
158             E elem = get(index++);
159             if (elementRawOffset(elem) < removeAreaEndRawOffset) {
160                 setElementRawOffset(elem, removeAreaEndRawOffset);
161             } else { // all subsequent offsets are higher
162                 break;
163             }
164         }
165         updateOffsetGapLength(+length);
166     }
167     
168     /**
169      * Move the offset gap so that it's on the requested offset.
170      * <br>
171      * This method can be used when the index of the first element
172      * at the given offset was precomputed already.
173      *
174      * <p>
175      * <b>Note:</b> Improper use of this may logically damage
176      * offsets of the elements contained in the list.
177      *
178      * @param offset offset to which the <code>offsetGapStart</code>
179      *  should be assigned.
180      * @param index index of the first element in the list
181      *  that has an offset that is greater or equal that the given offset parameter.
182      *  <br>
183      *  It may be computed by {@link #findElementIndex(int)}.
184      */
185     protected final void moveOffsetGap(int offset, int index) {
186         if (offset < offsetGapStart) { // need to check items above index
187             int bound = size();
188             for (int i = index; i < bound; i++) {
189                 E elem = get(i);
190                 int rawOffset = elementRawOffset(elem);
191                 if (rawOffset < offsetGapStart) {
192                     setElementRawOffset(elem, rawOffset + offsetGapLength);
193                 } else {
194                     break;
195                 }
196             }
197 
198         } else {  // check items below index
199             for (int i = index - 1; i >= 0; i--) {
200                 E elem = get(i);
201                 int rawOffset = elementRawOffset(elem);
202                 if (rawOffset >= offsetGapStart) {
203                     setElementRawOffset(elem, rawOffset - offsetGapLength);
204                 } else {
205                     break;
206                 }
207             }
208         }
209         offsetGapStart = offset;
210     }
211 
212     /**
213      * Obtain the start of the offset gap.
214      *
215      * @return start of the offset gap.
216      */
217     protected final int offsetGapStart() {
218         return offsetGapStart;
219     }
220 
221     /**
222      * Update the offset gap start by the given delta.
223      * <br>
224      * This may be needed e.g. after insertion/removal was done
225      * in the document.
226      *
227      * <p>
228      * <b>Note:</b> Improper use of this may logically damage
229      * offsets of the elements contained in the list.
230      */ 
231     protected final void updateOffsetGapStart(int offsetDelta) {
232         offsetGapStart += offsetDelta;
233     }
234 
235     /**
236      * Obtain the length of the offset gap.
237      *
238      * @return length of the offset gap.
239      */
240     protected final int offsetGapLength() {
241         return offsetGapLength;
242     }
243 
244     /**
245      * Update the offset gap length by the given delta.
246      * <br>
247      * This may be needed e.g. after insertion/removal was done
248      * in the document.
249      *
250      * <p>
251      * <b>Note:</b> Improper use of this may logically damage
252      * offsets of the elements contained in the list.
253      */ 
254     protected final void updateOffsetGapLength(int offsetGapLengthDelta) {
255         offsetGapLength += offsetGapLengthDelta;
256         assert (offsetGapLength >= 0); // prevent overflow to negative numbers
257     }
258 
259     /**
260      * Find an index of the first element at the given offset in the list
261      * by using binary search.
262      *
263      * @param offset offset of the element
264      * @return index of the element. If there is no element with that
265      *  index then the index of the next element (with the greater offset)
266      *  (or size of the list) will be returned.
267      *  <br>
268      *  If there are multiple items with the same offset then the first one of them
269      *  will be returned.
270      */
271     protected final int findElementIndex(int offset) {
272         int low = 0;
273         int high = size() - 1;
274 
275         while (low <= high) {
276             int index = (low + high) / 2; // mid in the binary search
277             int elemOffset = elementOffset(index);
278 
279             if (elemOffset < offset) {
280                 low = index + 1;
281 
282             } else if (elemOffset > offset) {
283                 high = index - 1;
284 
285             } else { // exact offset found at index
286                 while (index > 0) {
287                     index--;
288                     if (elementOffset(index) < offset) {
289                         index++;
290                         break;
291                     }
292                 }
293                 low = index;
294                 break;
295             }
296         }
297         return low;
298     }
299 
300     /**
301      * This method updates element's offset (shifts it above offset gap if necessary)
302      * before adding the element to the list.
303      * <bt/>
304      * This method should be called before (or after) the element is physically added
305      * to the list. If the element is added below the offset gap
306      * then calling of this method is not necessary.
307      */
308     protected void updateElementOffsetAdd(E elem) {
309         int rawOffset = elementRawOffset(elem);
310         if (rawOffset >= offsetGapStart) {
311             setElementRawOffset(elem, rawOffset + offsetGapLength);
312         }
313     }
314 
315     /**
316      * This method updates element's offset (shifts it below offset gap if necessary)
317      * before (or after) the element gets removed from the list.
318      * <br/>
319      * This method should be called after the element is physically removed
320      * from the list and it's desired that it retains its natural offset
321      * (not possibly shifted by the offset gap length).
322      * <br/>
323      * If the element was located below the offset gap prior removal
324      * then calling of this method is not necessary.
325      */
326     protected void updateElementOffsetRemove(E elem) {
327         int rawOffset = elementRawOffset(elem);
328         if (rawOffset >= offsetGapStart) {
329             setElementRawOffset(elem, rawOffset - offsetGapLength);
330         }
331     }
332     
333     /**
334      * Translate raw offset into real offset.
335      *
336      * @param rawOffset raw offset stored in an element.
337      * @return real offset that the element is supposed to have.
338      */
339     protected final int raw2Offset(int rawOffset) {
340         return (rawOffset < offsetGapStart)
341             ? rawOffset
342             : rawOffset - offsetGapLength;
343     }
344     
345     /**
346      * Translate regular offset to raw offset.
347      *
348      * @param offset regular offset.
349      * @return raw offset that can be used in elements.
350      */
351     protected final int offset2raw(int offset) {
352         return (offset < offsetGapStart)
353             ? offset
354             : offset + offsetGapLength;
355     }
356     
357     protected void consistencyCheck() {
358         super.consistencyCheck();
359 
360         if (offsetGapLength < 0) {
361             consistencyError("offsetGapLength < 0"); // NOI18N
362         }
363 
364         int lastRawOffset = Integer.MIN_VALUE;
365         int lastOffset = Integer.MIN_VALUE;
366         int size = size();
367         for (int i = 0; i < size; i++) {
368             E elem = get(i);
369             int rawOffset = elementRawOffset(elem);
370             int offset = raw2Offset(rawOffset);
371             if (rawOffset < lastRawOffset) {
372                 consistencyError("Invalid rawOffset=" // NOI18N
373                     + rawOffset + " >= lastRawOffset=" + lastRawOffset // NOI18N
374                     + " at index=" + i // NOI18N
375                 );
376             }
377             if (offset < lastOffset) {
378                 consistencyError("Invalid offset=" // NOI18N
379                     + offset + " >= lastOffset=" + lastOffset // NOI18N
380                     + " at index=" + i // NOI18N
381                 );
382             }
383             lastRawOffset = rawOffset;
384             lastOffset = offset;
385         }
386     }
387     
388     protected String   dumpInternals() {
389         return super.dumpInternals() + ", offGap(s=" + offsetGapStart
390         + ", l=" + offsetGapLength + ")";
391     }
392 
393 }
394
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags