001: /*
002: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
003: *
004: * Copyright 1997-2007 Sun Microsystems, Inc. All rights reserved.
005: *
006: * The contents of this file are subject to the terms of either the GNU
007: * General Public License Version 2 only ("GPL") or the Common
008: * Development and Distribution License("CDDL") (collectively, the
009: * "License"). You may not use this file except in compliance with the
010: * License. You can obtain a copy of the License at
011: * http://www.netbeans.org/cddl-gplv2.html
012: * or nbbuild/licenses/CDDL-GPL-2-CP. See the License for the
013: * specific language governing permissions and limitations under the
014: * License. When distributing the software, include this License Header
015: * Notice in each file and include the License file at
016: * nbbuild/licenses/CDDL-GPL-2-CP. Sun designates this
017: * particular file as subject to the "Classpath" exception as provided
018: * by Sun in the GPL Version 2 section of the License file that
019: * accompanied this code. If applicable, add the following below the
020: * License Header, with the fields enclosed by brackets [] replaced by
021: * your own identifying information:
022: * "Portions Copyrighted [year] [name of copyright owner]"
023: *
024: * Contributor(s):
025: *
026: * The Original Software is NetBeans. The Initial Developer of the Original
027: * Software is Sun Microsystems, Inc. Portions Copyright 1997-2006 Sun
028: * Microsystems, Inc. All Rights Reserved.
029: *
030: * If you wish your version of this file to be governed by only the CDDL
031: * or only the GPL Version 2, indicate your decision by adding
032: * "[Contributor] elects to include this software in this distribution
033: * under the [CDDL or GPL Version 2] license." If you do not indicate a
034: * single choice of license, a recipient has the option to distribute
035: * your version of this file under either the CDDL, the GPL Version 2 or
036: * to extend the choice of license to its licensees as provided above.
037: * However, if you add GPL Version 2 code and therefore, elected the GPL
038: * Version 2 license, then the option applies only if the new code is
039: * made subject to such option by the copyright holder.
040: */
041:
042: package org.netbeans.editor;
043:
044: /**
045: * Implementation of {@link ObjectArray} that
046: * contains a gap which helps to speed up inserts/removals
047: * close to the gap.
048: * <P><strong>Note that this implementation is not synchronized.</strong> If
049: * multiple threads access an instance of this class concurrently, and at
050: * least one of the threads inserts/removes items, the whole access <i>must</i> be
051: * synchronized externally.
052: *
053: * @author Miloslav Metelka
054: * @version 1.00
055: */
056:
057: public class GapObjectArray implements ObjectArray,
058: ObjectArray.CopyItems {
059:
060: private static final Object[] EMPTY_ARRAY = new Object[0];
061:
062: /**
063: * Array holding the elements with the gap starting at the <CODE>gapStart</CODE>
064: * being <CODE>gapLength</CODE> long.
065: */
066: private Object[] array;
067:
068: /** Starting index of the gap in the array. */
069: private int gapStart;
070:
071: /** Length of the gap */
072: private int gapLength;
073:
074: public GapObjectArray() {
075: this .array = EMPTY_ARRAY;
076: }
077:
078: /**
079: * Construct new gap array of objects.
080: * @param array use this array as an initial array for processing.
081: * The array will be modified by subsequent changes. If the array
082: * contents should be preserved the array must be cloned first
083: * before processing.
084: * @param length length of the valid part of the array that contains
085: * the objects to be managed. The area must start at the index 0.
086: */
087: public GapObjectArray(Object[] array, int length) {
088: this .array = array;
089: this .gapStart = length;
090: this .gapLength = array.length - length;
091: }
092:
093: public int getItemCount() {
094: return array.length - gapLength;
095: }
096:
097: public Object getItem(int index) {
098: return array[(index < gapStart) ? index : (index + gapLength)];
099: }
100:
101: public void copyItems(int srcStartIndex, int srcEndIndex,
102: Object[] dest, int destIndex) {
103:
104: rangeCheck(srcStartIndex, srcEndIndex - srcStartIndex);
105:
106: if (srcEndIndex < gapStart) { // fully below gap
107: System.arraycopy(array, srcStartIndex, dest, destIndex,
108: srcEndIndex - srcStartIndex);
109:
110: } else { // above gap or spans the gap
111: if (srcStartIndex >= gapStart) { // fully above gap
112: System.arraycopy(array, srcStartIndex + gapLength,
113: dest, destIndex, srcEndIndex - srcStartIndex);
114:
115: } else { // spans gap
116: int beforeGap = gapStart - srcStartIndex;
117: System.arraycopy(array, srcStartIndex, dest, destIndex,
118: beforeGap);
119: System.arraycopy(array, gapStart + gapLength, dest,
120: destIndex + beforeGap, srcEndIndex
121: - srcStartIndex - beforeGap);
122: }
123: }
124: }
125:
126: public void replace(int index, int removeCount, Object[] newItems) {
127: remove(index, removeCount);
128: insertAll(index, newItems);
129: }
130:
131: public void insertItem(int index, Object item) {
132: indexCheck(index);
133:
134: if (gapLength == 0) {
135: enlargeGap(1);
136: }
137: if (index != gapStart) {
138: moveGap(index);
139: }
140: array[gapStart++] = item;
141: gapLength--;
142: }
143:
144: public void insertAll(int index, Object[] items) {
145: insertAll(index, items, 0, items.length);
146: }
147:
148: public void insertAll(int index, Object[] items, int off, int len) {
149: indexCheck(index);
150:
151: if (items.length == 0) {
152: return;
153: }
154:
155: int extraLength = len - gapLength;
156: if (extraLength > 0) {
157: enlargeGap(extraLength);
158: }
159: if (index != gapStart) {
160: moveGap(index);
161: }
162: System.arraycopy(items, off, array, gapStart, len);
163: gapStart += len;
164: gapLength -= len;
165: }
166:
167: public void remove(int index, int count) {
168: remove(index, count, null);
169: }
170:
171: public void remove(int index, int count, RemoveUpdater removeUpdater) {
172: rangeCheck(index, count);
173:
174: if (count == 0) {
175: return;
176: }
177:
178: if (index >= gapStart) { // completely over gap
179: if (index > gapStart) {
180: moveGap(index);
181: }
182:
183: // Allow GC of removed items
184: index += gapLength; // begining of abandoned area
185: for (int endIndex = index + count; index < endIndex; index++) {
186: if (removeUpdater != null) {
187: removeUpdater.removeUpdate(array[index]);
188: }
189: array[index] = null;
190: }
191:
192: } else { // completely below gap or spans the gap
193: int endIndex = index + count;
194: if (endIndex <= gapStart) {
195: if (endIndex < gapStart) {
196: moveGap(endIndex);
197: }
198: gapStart = index;
199:
200: } else { // spans gap: gapStart > index but gapStart - index < count
201: // Allow GC of removed items
202: for (int clearIndex = index; clearIndex < gapStart; clearIndex++) {
203: if (removeUpdater != null) {
204: removeUpdater.removeUpdate(array[clearIndex]);
205: }
206: array[clearIndex] = null;
207: }
208:
209: index = gapStart + gapLength; // part above the gap
210: gapStart = endIndex - count; // original value of index
211: endIndex += gapLength;
212:
213: }
214:
215: // Allow GC of removed items
216: while (index < endIndex) {
217: if (removeUpdater != null) {
218: removeUpdater.removeUpdate(array[index]);
219: }
220: array[index++] = null;
221: }
222:
223: }
224:
225: gapLength += count;
226: }
227:
228: protected void unoptimizedRemove(int index, int count,
229: 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: if (gapLength > 0) {
250: int newLength = array.length - gapLength;
251: Object[] newArray = new Object[newLength];
252: int gapEnd = gapStart + gapLength;
253: System.arraycopy(array, 0, newArray, 0, gapStart);
254: System.arraycopy(array, gapEnd, newArray, gapStart,
255: array.length - gapEnd);
256: array = newArray;
257: gapStart = array.length;
258: gapLength = 0;
259: }
260: }
261:
262: protected void movedAboveGapUpdate(Object[] array, int index,
263: int count) {
264: }
265:
266: protected void movedBelowGapUpdate(Object[] array, int index,
267: int count) {
268: }
269:
270: private void moveGap(int index) {
271: if (index <= gapStart) { // move gap down
272: int moveSize = gapStart - index;
273: System.arraycopy(array, index, array, gapStart + gapLength
274: - moveSize, moveSize);
275: clearEmpty(index, Math.min(moveSize, gapLength));
276: gapStart = index;
277: movedAboveGapUpdate(array, gapStart + gapLength, moveSize);
278:
279: } else { // above gap
280: int gapEnd = gapStart + gapLength;
281: int moveSize = index - gapStart;
282: System.arraycopy(array, gapEnd, array, gapStart, moveSize);
283: if (index < gapEnd) {
284: clearEmpty(gapEnd, moveSize);
285: } else {
286: clearEmpty(index, gapLength);
287: }
288: movedBelowGapUpdate(array, gapStart, moveSize);
289: gapStart += moveSize;
290: }
291: }
292:
293: private void clearEmpty(int index, int length) {
294: while (--length >= 0) {
295: array[index++] = null; // allow GC
296: }
297: }
298:
299: private void enlargeGap(int extraLength) {
300: int newLength = Math.max(4, Math.max(array.length * 2,
301: array.length + extraLength));
302:
303: int gapEnd = gapStart + gapLength;
304: int afterGapLength = (array.length - gapEnd);
305: int newGapEnd = newLength - afterGapLength;
306: Object[] newArray = new Object[newLength];
307: System.arraycopy(array, 0, newArray, 0, gapStart);
308: System.arraycopy(array, gapEnd, newArray, newGapEnd,
309: afterGapLength);
310: array = newArray;
311: gapLength = newGapEnd - gapStart;
312: }
313:
314: private void rangeCheck(int index, int count) {
315: if (index < 0 || count < 0 || index + count > getItemCount()) {
316: throw new IndexOutOfBoundsException("index="
317: + index // NOI18N
318: + ", count=" + count + ", getItemCount()="
319: + getItemCount()); // NOI18N
320: }
321: }
322:
323: private void indexCheck(int index) {
324: if (index > getItemCount()) {
325: throw new IndexOutOfBoundsException("index=" + index // NOI18N
326: + ", getItemCount()=" + getItemCount()); // NOI18N
327: }
328: }
329:
330: /**
331: * Internal consistency check.
332: */
333: void check() {
334: if (gapStart < 0 || gapLength < 0
335: || gapStart + gapLength > array.length) {
336: throw new IllegalStateException();
337: }
338:
339: // Check whether the whole gap contains only nulls
340: for (int i = gapStart + gapLength - 1; i >= gapStart; i--) {
341: if (array[i] != null) {
342: throw new IllegalStateException();
343: }
344: }
345: }
346:
347: public String toStringDetail() {
348: return "gapStart=" + gapStart + ", gapLength=" + gapLength // NOI18N
349: + ", array.length=" + array.length; // NOI18N
350: }
351:
352: public interface RemoveUpdater {
353:
354: public void removeUpdate(Object removedItem);
355:
356: }
357:
358: }
|