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.editor;
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  public class GapObjectArray implements ObjectArray, ObjectArray.CopyItems {
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      public int getItemCount() {
71          return array.length - gapLength;
72      }
73      
74      public Object   getItem(int index) {
75          return array[(index < gapStart) ? index : (index + gapLength)];
76      }
77  
78      public void copyItems(int srcStartIndex, int srcEndIndex,
79      Object  [] dest, int destIndex) {
80  
81          rangeCheck(srcStartIndex, srcEndIndex - srcStartIndex);
82  
83          if (srcEndIndex < gapStart) { // fully below gap
84              System.arraycopy(array, srcStartIndex,
85                  dest, destIndex, srcEndIndex - srcStartIndex);
86  
87          } else { // above gap or spans the gap
88              if (srcStartIndex >= gapStart) { // fully above gap
89                  System.arraycopy(array, srcStartIndex + gapLength, dest, destIndex,
90                      srcEndIndex - srcStartIndex);
91  
92              } else { // spans gap
93                  int beforeGap = gapStart - srcStartIndex;
94                  System.arraycopy(array, srcStartIndex, dest, destIndex, beforeGap);
95                  System.arraycopy(array, gapStart + gapLength, dest, destIndex + beforeGap,
96                      srcEndIndex - srcStartIndex - beforeGap);
97              }
98          }
99      }
100 
101     public void replace(int index, int removeCount, Object  [] newItems) {
102         remove(index, removeCount);
103         insertAll(index, newItems);
104     }
105     
106     public void insertItem(int index, Object   item) {
107         indexCheck(index);
108         
109         if (gapLength == 0) {
110             enlargeGap(1);
111         }
112         if (index != gapStart) {
113             moveGap(index);
114         }
115         array[gapStart++] = item;
116         gapLength--;
117     }
118 
119     public void insertAll(int index, Object  [] items) {
120         insertAll(index, items, 0, items.length);
121     }
122     
123     public void insertAll(int index, Object  [] items, int off, int len) {
124         indexCheck(index);
125         
126         if (items.length == 0) {
127             return;
128         }
129 
130         int extraLength = len - gapLength;
131         if (extraLength > 0) {
132             enlargeGap(extraLength);
133         }
134         if (index != gapStart) {
135             moveGap(index);
136         }
137         System.arraycopy(items, off, array, gapStart, len);
138         gapStart += len;
139         gapLength -= len;
140     }
141     
142     public void remove(int index, int count) {
143         remove(index, count, null);
144     }
145     
146     public void remove(int index, int count, RemoveUpdater removeUpdater) {
147         rangeCheck(index, count);
148 
149         if (count == 0) {
150             return;
151         }
152 
153         if (index >= gapStart) { // completely over gap
154             if (index > gapStart) {
155                 moveGap(index);
156             }
157 
158             // Allow GC of removed items
159             index += gapLength; // begining of abandoned area
160             for (int endIndex = index + count; index < endIndex; index++) {
161                 if (removeUpdater != null) {
162                     removeUpdater.removeUpdate(array[index]);
163                 }
164                 array[index] = null;
165             }
166 
167         } else { // completely below gap or spans the gap
168             int endIndex = index + count;
169             if (endIndex <= gapStart) {
170                 if (endIndex < gapStart) {
171                     moveGap(endIndex);
172                 }
173                 gapStart = index;
174 
175             } else { // spans gap: gapStart > index but gapStart - index < count
176                 // Allow GC of removed items
177                 for (int clearIndex = index; clearIndex < gapStart; clearIndex++) {
178                     if (removeUpdater != null) {
179                         removeUpdater.removeUpdate(array[clearIndex]);
180                     }
181                     array[clearIndex] = null;
182                 }
183                 
184                 index = gapStart + gapLength; // part above the gap
185                 gapStart = endIndex - count; // original value of index
186                 endIndex += gapLength;
187 
188             }
189 
190             // Allow GC of removed items
191             while (index < endIndex) {
192                 if (removeUpdater != null) {
193                     removeUpdater.removeUpdate(array[index]);
194                 }
195                 array[index++] = null;
196             }
197                 
198         }
199 
200         gapLength += count;
201     }
202 
203     protected void unoptimizedRemove(int index, int count, RemoveUpdater removeUpdater) {
204         rangeCheck(index, count);
205         
206         int endIndex = index + count;
207         if (gapStart != endIndex) {
208             moveGap(endIndex);
209         }
210 
211         // Null the cleared items to allow possible GC of those objects
212         for (int i = endIndex - 1; i >= index; i--) {
213             if (removeUpdater != null) {
214                 removeUpdater.removeUpdate(array[i]);
215             }
216             array[i] = null;
217         }
218 
219         gapStart = index;
220     }
221 
222     public void compact() {
223         if (gapLength > 0) {
224             int newLength = array.length - gapLength;
225             Object  [] newArray = new Object  [newLength];
226             int gapEnd = gapStart + gapLength;
227             System.arraycopy(array, 0, newArray, 0, gapStart);
228             System.arraycopy(array, gapEnd, newArray, gapStart, 
229                 array.length - gapEnd);
230             array = newArray;
231             gapStart = array.length;
232             gapLength = 0;
233         }
234     }
235     
236     protected void movedAboveGapUpdate(Object  [] array, int index, int count) {
237     }
238     
239     protected void movedBelowGapUpdate(Object  [] array, int index, int count) {
240     }
241     
242     private void moveGap(int index) {
243         if (index <= gapStart) { // move gap down
244             int moveSize = gapStart - index;
245             System.arraycopy(array, index, array,
246                 gapStart + gapLength - moveSize, moveSize);
247             clearEmpty(index, Math.min(moveSize, gapLength));
248             gapStart = index;
249             movedAboveGapUpdate(array, gapStart + gapLength, moveSize);
250 
251         } else { // above gap
252             int gapEnd = gapStart + gapLength;
253             int moveSize = index - gapStart;
254             System.arraycopy(array, gapEnd, array, gapStart, moveSize);
255             if (index < gapEnd) {
256                 clearEmpty(gapEnd, moveSize);
257             } else {
258                 clearEmpty(index, gapLength);
259             }
260             movedBelowGapUpdate(array, gapStart, moveSize);
261             gapStart += moveSize;
262         }
263     }
264     
265     private void clearEmpty(int index, int length) {
266         while (--length >= 0) {
267             array[index++] = null; // allow GC
268         }
269     }
270     
271     private void enlargeGap(int extraLength) {
272         int newLength = Math.max(4,
273             Math.max(array.length * 2, array.length + extraLength));
274 
275         int gapEnd = gapStart + gapLength;
276         int afterGapLength = (array.length - gapEnd);
277         int newGapEnd = newLength - afterGapLength;
278         Object  [] newArray = new Object  [newLength];
279         System.arraycopy(array, 0, newArray, 0, gapStart);
280         System.arraycopy(array, gapEnd, newArray, newGapEnd, afterGapLength);
281         array = newArray;
282         gapLength = newGapEnd - gapStart;
283     }
284 
285     private void rangeCheck(int index, int count) {
286         if (index < 0 || count < 0 || index + count > getItemCount()) {
287             throw new IndexOutOfBoundsException  ("index=" + index // NOI18N
288                 + ", count=" + count + ", getItemCount()=" + getItemCount()); // NOI18N
289         }
290     } 
291 
292     private void indexCheck(int index) {
293         if (index > getItemCount()) {
294             throw new IndexOutOfBoundsException  ("index=" + index // NOI18N
295                 + ", getItemCount()=" + getItemCount()); // NOI18N
296         }
297     }
298 
299     /**
300      * Internal consistency check.
301      */
302     void check() {
303         if (gapStart < 0 || gapLength < 0
304             || gapStart + gapLength > array.length
305         ) {
306             throw new IllegalStateException  ();
307         }
308         
309         // Check whether the whole gap contains only nulls
310         for (int i = gapStart + gapLength - 1; i >= gapStart; i--) {
311             if (array[i] != null) {
312                 throw new IllegalStateException  ();
313             }
314         }
315     }
316     
317     public String   toStringDetail() {
318         return "gapStart=" + gapStart + ", gapLength=" + gapLength // NOI18N
319             + ", array.length=" + array.length; // NOI18N
320     }
321         
322         
323     public interface RemoveUpdater {
324         
325         public void removeUpdate(Object   removedItem);
326         
327     }
328 
329 }
330
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags