GapObjectArray


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.view;
21  
22  /**
23   * Implementation of {@link ObjectArray} that
24   * contains a gap which helps to speed up inserts/removals
25   * close to the gap.
26   * <P><strong>Note that this implementation is not synchronized.</strong> If
27   * multiple threads access an instance of this class concurrently, and at
28   * least one of the threads inserts/removes items, the whole access <i>must</i> be
29   * synchronized externally.
30   *
31   * @author Miloslav Metelka
32   * @version 1.00
33   */
34  
35  class GapObjectArray {
36  
37      private static final Object  [] EMPTY_ARRAY = new Object  [0];
38  
39      /**
40       * Array holding the elements with the gap starting at the <CODE>gapStart</CODE>
41       * being <CODE>gapLength</CODE> long.
42       */
43      private Object  [] array;
44      
45      /** Starting index of the gap in the array. */
46      private int gapStart;
47      
48      /** Length of the gap */
49      private int gapLength;
50      
51      public GapObjectArray() {
52          this.array = EMPTY_ARRAY;
53      }
54      
55      /**
56       * Construct new gap array of objects.
57       * @param array use this array as an initial array for processing.
58       *  The array will be modified by subsequent changes. If the array
59       *  contents should be preserved the array must be cloned first
60       *  before processing.
61       * @param length length of the valid part of the array that contains
62       *  the objects to be managed. The area must start at the index 0.
63       */
64      public GapObjectArray(Object  [] array, int length) {
65          this.array = array;
66          this.gapStart = length;
67          this.gapLength = array.length - length;
68      }
69      
70      /**
71       * Get total number of items in this object array.
72       */
73      public int getItemCount() {
74          return array.length - gapLength;
75      }
76      
77      /**
78       * Get item at the given index.
79       * @param index &gt=0 and &lt{@link #getItemCount()} index from which
80       *  the item should be returned.
81       * @return item at the given index.
82       */
83      public Object   getItem(int index) {
84          return array[(index < gapStart) ? index : (index + gapLength)];
85      }
86  
87      public void copyItems(int srcStartIndex, int srcEndIndex,
88      Object  [] dest, int destIndex) {
89  
90          rangeCheck(srcStartIndex, srcEndIndex - srcStartIndex);
91  
92          if (srcEndIndex < gapStart) { // fully below gap
93              System.arraycopy(array, srcStartIndex,
94                  dest, destIndex, srcEndIndex - srcStartIndex);
95  
96          } else { // above gap or spans the gap
97              if (srcStartIndex >= gapStart) { // fully above gap
98                  System.arraycopy(array, srcStartIndex + gapLength, dest, destIndex,
99                      srcEndIndex - srcStartIndex);
100 
101             } else { // spans gap
102                 int beforeGap = gapStart - srcStartIndex;
103                 System.arraycopy(array, srcStartIndex, dest, destIndex, beforeGap);
104                 System.arraycopy(array, gapStart + gapLength, dest, destIndex + beforeGap,
105                     srcEndIndex - srcStartIndex - beforeGap);
106             }
107         }
108     }
109     
110     public final int getGapStart() { // to implement GapStart interface
111         return gapStart;
112     }
113 
114     public void replace(int index, int removeCount, Object  [] newItems) {
115         remove(index, removeCount);
116         insertAll(index, newItems);
117     }
118     
119     public void insertItem(int index, Object   item) {
120         indexCheck(index);
121         
122         if (gapLength == 0) {
123             enlargeGap(1);
124         }
125         if (index != gapStart) {
126             moveGap(index);
127         }
128         array[gapStart++] = item;
129         gapLength--;
130     }
131 
132     public void insertAll(int index, Object  [] items) {
133         insertAll(index, items, 0, items.length);
134     }
135     
136     public void insertAll(int index, Object  [] items, int off, int len) {
137         indexCheck(index);
138         
139         if (items.length == 0) {
140             return;
141         }
142 
143         int extraLength = len - gapLength;
144         if (extraLength > 0) {
145             enlargeGap(extraLength);
146         }
147         if (index != gapStart) {
148             moveGap(index);
149         }
150         System.arraycopy(items, off, array, gapStart, len);
151         gapStart += len;
152         gapLength -= len;
153     }
154     
155     public void ensureCapacity(int minCapacity) {
156         if (minCapacity < 0) {
157             throw new IllegalArgumentException  ("minCapacity=" + minCapacity + " < 0"); // NOI18N
158         }
159         
160         int capacity = array.length;
161         if (capacity == 0) { // use exactly what requested if empty now
162             setCapacity(minCapacity);
163         } else if (minCapacity > capacity) { // some items already exist
164             enlargeGap(minCapacity - capacity);
165         }
166     }
167     
168     public void remove(int index, int count) {
169         remove(index, count, null);
170     }
171     
172     public void remove(int index, int count, RemoveUpdater removeUpdater) {
173         rangeCheck(index, count);
174 
175         if (count == 0) {
176             return;
177         }
178 
179         if (index >= gapStart) { // completely over gap
180             if (index > gapStart) {
181                 moveGap(index);
182             }
183 
184             // Allow GC of removed items
185             index += gapLength; // begining of abandoned area
186             for (int endIndex = index + count; index < endIndex; index++) {
187                 if (removeUpdater != null) {
188                     removeUpdater.removeUpdate(array[index]);
189                 }
190                 array[index] = null;
191             }
192 
193         } else { // completely below gap or spans the gap
194             int endIndex = index + count;
195             if (endIndex <= gapStart) {
196                 if (endIndex < gapStart) {
197                     moveGap(endIndex);
198                 }
199                 gapStart = index;
200 
201             } else { // spans gap: gapStart > index but gapStart - index < count
202                 // Allow GC of removed items
203                 for (int clearIndex = index; clearIndex < gapStart; clearIndex++) {
204                     if (removeUpdater != null) {
205                         removeUpdater.removeUpdate(array[clearIndex]);
206                     }
207                     array[clearIndex] = null;
208                 }
209                 
210                 index = gapStart + gapLength; // part above the gap
211                 gapStart = endIndex - count; // original value of index
212                 endIndex += gapLength;
213 
214             }
215 
216             // Allow GC of removed items
217             while (index < endIndex) {
218                 if (removeUpdater != null) {
219                     removeUpdater.removeUpdate(array[index]);
220                 }
221                 array[index++] = null;
222             }
223                 
224         }
225 
226         gapLength += count;
227     }
228 
229     protected void unoptimizedRemove(int index, int count, RemoveUpdater removeUpdater) {
230         rangeCheck(index, count);
231         
232         int endIndex = index + count;
233         if (gapStart != endIndex) {
234             moveGap(endIndex);
235         }
236 
237         // Null the cleared items to allow possible GC of those objects
238         for (int i = endIndex - 1; i >= index; i--) {
239             if (removeUpdater != null) {
240                 removeUpdater.removeUpdate(array[i]);
241             }
242             array[i] = null;
243         }
244 
245         gapStart = index;
246     }
247 
248     public void compact() {
249         setCapacity(getItemCount());
250     }
251     
252     protected void movedAboveGapUpdate(Object  [] array, int index, int count) {
253     }
254     
255     protected void movedBelowGapUpdate(Object  [] array, int index, int count) {
256     }
257     
258     private void moveGap(int index) {
259         if (index <= gapStart) { // move gap down
260             int moveSize = gapStart - index;
261             System.arraycopy(array, index, array,
262                 gapStart + gapLength - moveSize, moveSize);
263             clearEmpty(index, Math.min(moveSize, gapLength));
264             gapStart = index;
265             movedAboveGapUpdate(array, gapStart + gapLength, moveSize);
266 
267         } else { // above gap
268             int gapEnd = gapStart + gapLength;
269             int moveSize = index - gapStart;
270             System.arraycopy(array, gapEnd, array, gapStart, moveSize);
271             if (index < gapEnd) {
272                 clearEmpty(gapEnd, moveSize);
273             } else {
274                 clearEmpty(index, gapLength);
275             }
276             movedBelowGapUpdate(array, gapStart, moveSize);
277             gapStart += moveSize;
278         }
279     }
280     
281     private void clearEmpty(int index, int length) {
282         while (--length >= 0) {
283             array[index++] = null; // allow GC
284         }
285     }
286     
287     private void enlargeGap(int extraLength) {
288         int newLength = Math.max(4,
289             Math.max(array.length * 2, array.length + extraLength));
290         setCapacity(newLength);
291     }
292     
293     private void setCapacity(int newCapacity) {
294         int gapEnd = gapStart + gapLength;
295         int afterGapLength = (array.length - gapEnd);
296         int newGapEnd = newCapacity - afterGapLength;
297         Object  [] newArray = new Object  [newCapacity];
298         if (newCapacity < gapStart + afterGapLength) { // to small capacity
299             throw new IllegalArgumentException  ("newCapacity=" + newCapacity // NOI18N
300                 + " < itemCount=" + (gapStart + afterGapLength)); // NOI18N
301         }
302 
303         System.arraycopy(array, 0, newArray, 0, gapStart);
304         System.arraycopy(array, gapEnd, newArray, newGapEnd, afterGapLength);
305         array = newArray;
306         gapLength = newGapEnd - gapStart;
307     }
308 
309     private void rangeCheck(int index, int count) {
310         if (index < 0 || count < 0 || index + count > getItemCount()) {
311             throw new IndexOutOfBoundsException  ("index=" + index // NOI18N
312                 + ", count=" + count + ", getItemCount()=" + getItemCount()); // NOI18N
313         }
314     } 
315 
316     private void indexCheck(int index) {
317         if (index > getItemCount()) {
318             throw new IndexOutOfBoundsException  ("index=" + index // NOI18N
319                 + ", getItemCount()=" + getItemCount()); // NOI18N
320         }
321     }
322 
323     /**
324      * Internal consistency check.
325      */
326     void check() {
327         if (gapStart < 0 || gapLength < 0
328             || gapStart + gapLength > array.length
329         ) {
330             throw new IllegalStateException  ();
331         }
332         
333         // Check whether the whole gap contains only nulls
334         for (int i = gapStart + gapLength - 1; i >= gapStart; i--) {
335             if (array[i] != null) {
336                 throw new IllegalStateException  ();
337             }
338         }
339     }
340     
341     public String   toStringDetail() {
342         return "gapStart=" + gapStart + ", gapLength=" + gapLength // NOI18N
343             + ", array.length=" + array.length; // NOI18N
344     }
345         
346     /**
347      * Updater of the removed items after the given item was removed
348      * from the array.
349      */   
350     public interface RemoveUpdater {
351         
352         /**
353          * Update the item after it was removed
354          * from the array.
355          */
356         public void removeUpdate(Object   removedItem);
357         
358     }
359 
360 }
361
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags