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.lib.editor.util;
043:
044: import java.util.AbstractList;
045: import java.util.Collection;
046: import java.util.List;
047: import java.util.RandomAccess;
048:
049: /**
050: * List implementation that stores items in an array
051: * with a gap.
052: *
053: * @author Miloslav Metelka
054: * @version 1.00
055: */
056:
057: public class GapList<E> extends AbstractList<E> implements List<E>,
058: RandomAccess, Cloneable, java.io.Serializable {
059:
060: /**
061: * The array buffer into which the elements are stored.
062: * <br>
063: * The elements are stored in the whole array except
064: * the indexes starting at <code>gapStart</code>
065: * till <code>gapStart + gapLength - 1</code>.
066: */
067: private transient E[] elementData; // 16 bytes (12-super(modCount) + 4)
068:
069: /**
070: * The start of the gap in the elementData array.
071: */
072: private int gapStart; // 20 bytes
073:
074: /**
075: * Length of the gap in the elementData array starting at gapStart.
076: */
077: private int gapLength; // 24 bytes
078:
079: /**
080: * Constructs an empty list with the specified initial capacity.
081: *
082: * @param initialCapacity the initial capacity of the list.
083: * @exception IllegalArgumentException if the specified initial capacity
084: * is negative
085: */
086: public GapList(int initialCapacity) {
087: if (initialCapacity < 0) {
088: throw new IllegalArgumentException("Illegal Capacity: " // NOI18N
089: + initialCapacity);
090: }
091: this .elementData = allocateElementsArray(initialCapacity);
092: this .gapLength = initialCapacity;
093: }
094:
095: /**
096: * Constructs an empty list with an initial capacity of ten.
097: */
098: public GapList() {
099: this (10);
100: }
101:
102: /**
103: * Constructs a list containing the elements of the specified
104: * collection, in the order they are returned by the collection's
105: * iterator. The <tt>GapList</tt> instance has an initial capacity of
106: * 110% the size of the specified collection.
107: *
108: * @param c the collection whose elements are to be placed into this list.
109: * @throws NullPointerException if the specified collection is null.
110: */
111: public GapList(Collection<? extends E> c) {
112: int size = c.size();
113: // Allow 10% room for growth
114: int capacity = (int) Math.min((size * 110L) / 100,
115: Integer.MAX_VALUE);
116: @SuppressWarnings("unchecked")
117: E[] data = (E[]) c.toArray(new Object[capacity]);
118: elementData = data;
119: this .gapStart = size;
120: this .gapLength = elementData.length - size;
121: }
122:
123: /**
124: * Trims the capacity of this <tt>GapList</tt> instance to be the
125: * list's current size. An application can use this operation to minimize
126: * the storage of an <tt>GapList</tt> instance.
127: */
128: public void trimToSize() {
129: modCount++;
130: if (gapLength > 0) {
131: int newLength = elementData.length - gapLength;
132: E[] newElementData = allocateElementsArray(newLength);
133: copyAllData(newElementData);
134: elementData = newElementData;
135: // Leave gapStart as is
136: gapLength = 0;
137: }
138: }
139:
140: /**
141: * Increases the capacity of this <tt>GapList</tt> instance, if
142: * necessary, to ensure that it can hold at least the number of elements
143: * specified by the minimum capacity argument.
144: *
145: * @param minCapacity the desired minimum capacity.
146: */
147: public void ensureCapacity(int minCapacity) {
148: modCount++; // expected to always increment modCount (same in ArrayList)
149: int oldCapacity = elementData.length;
150: if (minCapacity > oldCapacity) {
151: int newCapacity = (oldCapacity * 3) / 2 + 1;
152: if (newCapacity < minCapacity) {
153: newCapacity = minCapacity;
154: }
155: int gapEnd = gapStart + gapLength;
156: int afterGapLength = (oldCapacity - gapEnd);
157: int newGapEnd = newCapacity - afterGapLength;
158: E[] newElementData = allocateElementsArray(newCapacity);
159: System.arraycopy(elementData, 0, newElementData, 0,
160: gapStart);
161: System.arraycopy(elementData, gapEnd, newElementData,
162: newGapEnd, afterGapLength);
163: elementData = newElementData;
164: gapLength = newGapEnd - gapStart;
165: }
166: }
167:
168: /**
169: * Returns the number of elements in this list.
170: *
171: * @return the number of elements in this list.
172: */
173: public int size() {
174: return elementData.length - gapLength;
175: }
176:
177: /**
178: * Tests if this list has no elements.
179: *
180: * @return <tt>true</tt> if this list has no elements;
181: * <tt>false</tt> otherwise.
182: */
183: public boolean isEmpty() {
184: return (elementData.length == gapLength);
185: }
186:
187: /**
188: * Returns <tt>true</tt> if this list contains the specified element.
189: *
190: * @param elem element whose presence in this List is to be tested.
191: * @return <code>true</code> if the specified element is present;
192: * <code>false</code> otherwise.
193: */
194: public boolean contains(Object elem) {
195: return indexOf(elem) >= 0;
196: }
197:
198: /**
199: * Searches for the first occurence of the given argument, testing
200: * for equality using the <tt>equals</tt> method.
201: *
202: * @param elem an object.
203: * @return the index of the first occurrence of the argument in this
204: * list; returns <tt>-1</tt> if the object is not found.
205: * @see Object#equals(Object)
206: */
207: public int indexOf(Object elem) {
208: if (elem == null) {
209: int i = 0;
210: while (i < gapStart) {
211: if (elementData[i] == null) {
212: return i;
213: }
214: i++;
215: }
216: i += gapLength;
217: int elementDataLength = elementData.length;
218: while (i < elementDataLength) {
219: if (elementData[i] == null) {
220: return i;
221: }
222: i++;
223: }
224:
225: } else { // elem not null
226: int i = 0;
227: while (i < gapStart) {
228: if (elem.equals(elementData[i])) {
229: return i;
230: }
231: i++;
232: }
233: i += gapLength;
234: int elementDataLength = elementData.length;
235: while (i < elementDataLength) {
236: if (elem.equals(elementData[i])) {
237: return i;
238: }
239: i++;
240: }
241: }
242:
243: return -1;
244: }
245:
246: /**
247: * Returns the index of the last occurrence of the specified object in
248: * this list.
249: *
250: * @param elem the desired element.
251: * @return the index of the last occurrence of the specified object in
252: * this list; returns -1 if the object is not found.
253: */
254: public int lastIndexOf(Object elem) {
255: if (elem == null) {
256: int i = elementData.length - 1;
257: int gapEnd = gapStart + gapLength;
258: while (i >= gapEnd) {
259: if (elementData[i] == null) {
260: return i;
261: }
262: i--;
263: }
264: i -= gapLength;
265: while (i >= 0) {
266: if (elementData[i] == null) {
267: return i;
268: }
269: i--;
270: }
271:
272: } else { // elem not null
273: int i = elementData.length - 1;
274: int gapEnd = gapStart + gapLength;
275: while (i >= gapEnd) {
276: if (elem.equals(elementData[i])) {
277: return i;
278: }
279: i--;
280: }
281: i -= gapLength;
282: while (i >= 0) {
283: if (elem.equals(elementData[i])) {
284: return i;
285: }
286: i--;
287: }
288: }
289:
290: return -1;
291: }
292:
293: /**
294: * Returns a shallow copy of this <tt>GapList</tt> instance. (The
295: * elements themselves are not copied.)
296: *
297: * @return a clone of this <tt>GapList</tt> instance.
298: */
299: public Object clone() {
300: try {
301: @SuppressWarnings("unchecked")
302: GapList<E> clonedList = (GapList<E>) super .clone();
303: int size = size();
304: E[] clonedElementData = allocateElementsArray(size);
305: copyAllData(clonedElementData);
306: clonedList.elementData = clonedElementData;
307: // Will retain gapStart - would have to call moved*() otherwise
308: clonedList.gapStart = size;
309: clonedList.resetModCount();
310: return clonedList;
311:
312: } catch (CloneNotSupportedException e) {
313: // this shouldn't happen, since we are Cloneable
314: throw new InternalError();
315: }
316: }
317:
318: /**
319: * @deprecated use {@link #copyElements(int, int, Object[], int)} which performs the same operation
320: */
321: public void copyItems(int startIndex, int endIndex, Object[] dest,
322: int destIndex) {
323: copyElements(startIndex, endIndex, dest, destIndex);
324: }
325:
326: /**
327: * Copy elements of this list between the given index range to the given object array.
328: *
329: * @param startIndex start index of the region of this list to be copied.
330: * @param endIndex end index of the region of this list to be copied.
331: * @param dest collection to the end of which the items should be copied.
332: */
333: public void copyElements(int startIndex, int endIndex,
334: Object[] dest, int destIndex) {
335:
336: if (startIndex < 0 || endIndex < startIndex
337: || endIndex > size()) {
338: throw new IndexOutOfBoundsException("startIndex="
339: + startIndex // NOI18N
340: + ", endIndex=" + endIndex + ", size()=" + size()); // NOI18N
341: }
342:
343: if (endIndex < gapStart) { // fully below gap
344: System.arraycopy(elementData, startIndex, dest, destIndex,
345: endIndex - startIndex);
346:
347: } else { // above gap or spans the gap
348: if (startIndex >= gapStart) { // fully above gap
349: System.arraycopy(elementData, startIndex + gapLength,
350: dest, destIndex, endIndex - startIndex);
351:
352: } else { // spans gap
353: int beforeGap = gapStart - startIndex;
354: System.arraycopy(elementData, startIndex, dest,
355: destIndex, beforeGap);
356: System.arraycopy(elementData, gapStart + gapLength,
357: dest, destIndex + beforeGap, endIndex
358: - startIndex - beforeGap);
359: }
360: }
361: }
362:
363: /**
364: * Copy elements of this list between the given index range
365: * to the end of the given collection.
366: *
367: * @param startIndex start index of the region of this list to be copied.
368: * @param endIndex end index of the region of this list to be copied.
369: * @param dest collection to the end of which the items should be copied.
370: */
371: public void copyElements(int startIndex, int endIndex,
372: Collection<E> dest) {
373:
374: if (startIndex < 0 || endIndex < startIndex
375: || endIndex > size()) {
376: throw new IndexOutOfBoundsException("startIndex="
377: + startIndex // NOI18N
378: + ", endIndex=" + endIndex + ", size()=" + size()); // NOI18N
379: }
380:
381: if (endIndex < gapStart) { // fully below gap
382: while (startIndex < endIndex) {
383: dest.add(elementData[startIndex++]);
384: }
385:
386: } else { // above gap or spans the gap
387: if (startIndex >= gapStart) { // fully above gap
388: startIndex += gapLength;
389: endIndex += gapLength;
390: while (startIndex < endIndex) {
391: dest.add(elementData[startIndex++]);
392: }
393:
394: } else { // spans gap
395: while (startIndex < gapStart) {
396: dest.add(elementData[startIndex++]);
397: }
398: startIndex += gapLength;
399: endIndex += gapLength;
400: while (startIndex < endIndex) {
401: dest.add(elementData[startIndex++]);
402: }
403: }
404: }
405: }
406:
407: /**
408: * Returns an array containing all of the elements in this list
409: * in the correct order.
410: *
411: * @return an array containing all of the elements in this list
412: * in the correct order.
413: */
414: public Object[] toArray() {
415: int size = size();
416: Object[] result = new Object[size];
417: copyAllData(result);
418: return result;
419: }
420:
421: /**
422: * Returns an array containing all of the elements in this list in the
423: * correct order; the runtime type of the returned array is that of the
424: * specified array. If the list fits in the specified array, it is
425: * returned therein. Otherwise, a new array is allocated with the runtime
426: * type of the specified array and the size of this list.<p>
427: *
428: * If the list fits in the specified array with room to spare (i.e., the
429: * array has more elements than the list), the element in the array
430: * immediately following the end of the collection is set to
431: * <tt>null</tt>. This is useful in determining the length of the list
432: * <i>only</i> if the caller knows that the list does not contain any
433: * <tt>null</tt> elements.
434: *
435: * @param a the array into which the elements of the list are to
436: * be stored, if it is big enough; otherwise, a new array of the
437: * same runtime type is allocated for this purpose.
438: * @return an array containing the elements of the list.
439: * @throws ArrayStoreException if the runtime type of a is not a supertype
440: * of the runtime type of every element in this list.
441: */
442: public <T> T[] toArray(T[] a) {
443: int size = size();
444: if (a.length < size) {
445: @SuppressWarnings("unchecked")
446: T[] tmp = (T[]) java.lang.reflect.Array.newInstance(a
447: .getClass().getComponentType(), size);
448: a = tmp;
449: }
450: copyAllData(a);
451: if (a.length > size)
452: a[size] = null;
453:
454: return a;
455: }
456:
457: // Positional Access Operations
458:
459: /**
460: * Returns the element at the specified position in this list.
461: *
462: * @param index index of element to return.
463: * @return the element at the specified position in this list.
464: * @throws IndexOutOfBoundsException if index is out of range <tt>(index
465: * < 0 || index >= size())</tt>.
466: */
467: public E get(int index) {
468: // rangeCheck(index) not necessary - would fail with AIOOBE anyway
469: return elementData[(index < gapStart) ? index
470: : (index + gapLength)];
471: }
472:
473: /**
474: * Replaces the element at the specified position in this list with
475: * the specified element.
476: *
477: * @param index index of element to replace.
478: * @param element element to be stored at the specified position.
479: * @return the element previously at the specified position.
480: * @throws IndexOutOfBoundsException if index out of range
481: * <tt>(index < 0 || index >= size())</tt>.
482: */
483: public E set(int index, E element) {
484: // rangeCheck(index) not necessary - would fail with AIOOBE anyway
485: if (index >= gapStart) {
486: index += gapLength;
487: }
488: E oldValue = elementData[index];
489: elementData[index] = element;
490: return oldValue;
491: }
492:
493: /**
494: * Swap elements at the given indexes.
495: */
496: public void swap(int index1, int index2) {
497: // rangeCheck(index) not necessary - would fail with AIOOBE anyway
498: // rangeCheck(byIndex) not necessary - would fail with AIOOBE anyway
499: if (index1 >= gapStart) {
500: index1 += gapLength;
501: }
502: if (index2 >= gapStart) {
503: index2 += gapLength;
504: }
505: E tmpValue = elementData[index1];
506: elementData[index1] = elementData[index2];
507: elementData[index2] = tmpValue;
508: }
509:
510: /**
511: * Appends the specified element to the end of this list.
512: *
513: * @param element non-null element to be appended to this list.
514: * @return <tt>true</tt> (as per the general contract of Collection.add).
515: */
516: public boolean add(E element) {
517: int size = size();
518: ensureCapacity(size + 1); // Increments modCount
519: addImpl(size, element);
520: return true;
521: }
522:
523: /**
524: * Inserts the specified element at the specified position in this
525: * list. Shifts the element currently at that position (if any) and
526: * any subsequent elements to the right (adds one to their indices).
527: *
528: * @param index index at which the specified element is to be inserted.
529: * @param element element to be inserted.
530: * @throws IndexOutOfBoundsException if index is out of range
531: * <tt>(index < 0 || index > size())</tt>.
532: */
533: public void add(int index, E element) {
534: int size = size();
535: if (index > size || index < 0) {
536: throw new IndexOutOfBoundsException("Index: " + index
537: + ", Size: " + size); // NOI18N
538: }
539: ensureCapacity(size + 1); // Increments modCount
540: addImpl(index, element);
541: }
542:
543: private void addImpl(int index, E element) {
544: moveGap(index);
545: elementData[gapStart++] = element;
546: gapLength--;
547: }
548:
549: /**
550: * Appends all of the elements in the specified Collection to the end of
551: * this list, in the order that they are returned by the
552: * specified Collection's Iterator. The behavior of this operation is
553: * undefined if the specified Collection is modified while the operation
554: * is in progress. (This implies that the behavior of this call is
555: * undefined if the specified Collection is this list, and this
556: * list is nonempty.)
557: *
558: * @param c the elements to be inserted into this list.
559: * @return <tt>true</tt> if this list changed as a result of the call.
560: * @throws NullPointerException if the specified collection is null.
561: */
562: public boolean addAll(Collection<? extends E> c) {
563: return addAll(size(), c);
564: }
565:
566: /**
567: * Inserts all of the elements in the specified Collection into this
568: * list, starting at the specified position. Shifts the element
569: * currently at that position (if any) and any subsequent elements to
570: * the right (increases their indices). The new elements will appear
571: * in the list in the order that they are returned by the
572: * specified Collection's iterator.
573: *
574: * @param index index at which to insert first element
575: * from the specified collection.
576: * @param c elements to be inserted into this list.
577: * @return <tt>true</tt> if this list changed as a result of the call.
578: * @throws IndexOutOfBoundsException if index out of range <tt>(index
579: * < 0 || index > size())</tt>.
580: * @throws NullPointerException if the specified Collection is null.
581: */
582: public boolean addAll(int index, Collection<? extends E> c) {
583: return addArray(index, c.toArray());
584: }
585:
586: /*
587: * Inserts all elements from the given array into this list, starting
588: * at the given index.
589: *
590: * @param index index at which to insert first element from the array.
591: * @param elements array of elements to insert.
592: */
593: public boolean addArray(int index, Object[] elements) {
594: return addArray(index, elements, 0, elements.length);
595: }
596:
597: /**
598: * Inserts elements from the given array into this list, starting
599: * at the given index.
600: *
601: * @param index index at which to insert first element.
602: * @param elements array of elements from which to insert elements.
603: * @param off offset in the elements pointing to first element to copy.
604: * @param len number of elements to copy from the elements array.
605: */
606: public boolean addArray(int index, Object[] elements, int off,
607: int len) {
608: int size = size();
609: if (index > size || index < 0) {
610: throw new IndexOutOfBoundsException("Index: " + index
611: + ", Size: " + size); // NOI18N
612: }
613:
614: ensureCapacity(size + len); // Increments modCount
615:
616: moveGap(index); // after that (index == gapStart)
617: System.arraycopy(elements, off, elementData, index, len);
618: gapStart += len;
619: gapLength -= len;
620:
621: return (len != 0);
622: }
623:
624: /**
625: * Removes all of the elements from this list. The list will
626: * be empty after this call returns.
627: */
628: public void clear() {
629: removeRange(0, size());
630: }
631:
632: /**
633: * Removes the element at the specified position in this list.
634: * Shifts any subsequent elements to the left (subtracts one from their
635: * indices).
636: *
637: * @param index the index of the element to removed.
638: * @return the element that was removed from the list.
639: * @throws IndexOutOfBoundsException if index out of range <tt>(index
640: * < 0 || index >= size())</tt>.
641: */
642: public E remove(int index) {
643: int size = size();
644: if (index >= size || index < 0) {
645: throw new IndexOutOfBoundsException("remove(): Index: "
646: + index + ", Size: " + size); // NOI18N
647: }
648:
649: modCount++;
650: moveGap(index + 1); // if previous were adds() - this should be no-op
651: E oldValue = elementData[index];
652: elementData[index] = null;
653: gapStart--;
654: gapLength++;
655:
656: return oldValue;
657: }
658:
659: /**
660: * Removes elements at the given index.
661: *
662: * @param index index of the first element to be removed.
663: * @param count number of elements to remove.
664: */
665: public void remove(int index, int count) {
666: int toIndex = index + count;
667: if (index < 0 || toIndex < index || toIndex > size()) {
668: throw new IndexOutOfBoundsException("index=" + index // NOI18N
669: + ", count=" + count + ", size()=" + size()); // NOI18N
670: }
671: removeRange(index, toIndex);
672: }
673:
674: /**
675: * Removes from this List all of the elements whose index is between
676: * fromIndex, inclusive and toIndex, exclusive. Shifts any succeeding
677: * elements to the left (reduces their index).
678: * This call shortens the list by <tt>(toIndex - fromIndex)</tt> elements.
679: * (If <tt>toIndex==fromIndex</tt>, this operation has no effect.)
680: *
681: * @param fromIndex index of first element to be removed.
682: * @param toIndex index after last element to be removed.
683: */
684: protected void removeRange(int fromIndex, int toIndex) {
685: modCount++;
686: if (fromIndex == toIndex) {
687: return;
688: }
689:
690: int removeCount = toIndex - fromIndex;
691: if (fromIndex >= gapStart) { // completely over gap
692: // Move gap to the start of the removed area
693: // (this should be the minimum necessary count of elements moved)
694: moveGap(fromIndex);
695:
696: // Allow GC of removed items
697: fromIndex += gapLength; // begining of abandoned area
698: toIndex += gapLength;
699: while (fromIndex < toIndex) {
700: elementData[fromIndex] = null;
701: fromIndex++;
702: }
703:
704: } else { // completely below gap or spans the gap
705: if (toIndex <= gapStart) {
706: // Move gap to the end of the removed area
707: // (this should be the minimum necessary count of elements moved)
708: moveGap(toIndex);
709: gapStart = fromIndex;
710:
711: } else { // spans gap: gapStart > fromIndex but gapStart - fromIndex < removeCount
712: // Allow GC of removed items
713: for (int clearIndex = fromIndex; clearIndex < gapStart; clearIndex++) {
714: elementData[clearIndex] = null;
715: }
716:
717: fromIndex = gapStart + gapLength; // part above the gap
718: gapStart = toIndex - removeCount; // original value of fromIndex
719: toIndex += gapLength;
720: }
721:
722: // Allow GC of removed items
723: while (fromIndex < toIndex) {
724: elementData[fromIndex++] = null;
725: }
726:
727: }
728:
729: gapLength += removeCount;
730: }
731:
732: private void moveGap(int index) {
733: if (index == gapStart) {
734: return; // do nothing
735: }
736:
737: if (gapLength > 0) {
738: if (index < gapStart) { // move gap down
739: int moveSize = gapStart - index;
740: System.arraycopy(elementData, index, elementData,
741: gapStart + gapLength - moveSize, moveSize);
742: clearEmpty(index, Math.min(moveSize, gapLength));
743:
744: } else { // above gap
745: int gapEnd = gapStart + gapLength;
746: int moveSize = index - gapStart;
747: System.arraycopy(elementData, gapEnd, elementData,
748: gapStart, moveSize);
749: if (index < gapEnd) {
750: clearEmpty(gapEnd, moveSize);
751: } else {
752: clearEmpty(index, gapLength);
753: }
754: }
755: }
756: gapStart = index;
757: }
758:
759: private void copyAllData(Object[] toArray) {
760: if (gapLength != 0) {
761: int gapEnd = gapStart + gapLength;
762: System.arraycopy(elementData, 0, toArray, 0, gapStart);
763: System.arraycopy(elementData, gapEnd, toArray, gapStart,
764: elementData.length - gapEnd);
765: } else { // no gap => single copy of everything
766: System.arraycopy(elementData, 0, toArray, 0,
767: elementData.length);
768: }
769: }
770:
771: private void clearEmpty(int index, int length) {
772: while (--length >= 0) {
773: elementData[index++] = null; // allow GC
774: }
775: }
776:
777: private void resetModCount() {
778: modCount = 0;
779: }
780:
781: /**
782: * Save the state of the <tt>GapList</tt> instance to a stream (that
783: * is, serialize it).
784: *
785: * @serialData The length of the array backing the <tt>GapList</tt>
786: * instance is emitted (int), followed by all of its elements
787: * (each an <tt>Object</tt>) in the proper order.
788: */
789: private void writeObject(java.io.ObjectOutputStream s)
790: throws java.io.IOException {
791: // Write out element count, and any hidden stuff
792: s.defaultWriteObject();
793:
794: // Write out array length
795: s.writeInt(elementData.length);
796:
797: // Write out all elements in the proper order.
798: int i = 0;
799: while (i < gapStart) {
800: s.writeObject(elementData[i]);
801: i++;
802: }
803: i += gapLength;
804: int elementDataLength = elementData.length;
805: while (i < elementDataLength) {
806: s.writeObject(elementData[i]);
807: i++;
808: }
809: }
810:
811: /**
812: * Reconstitute the <tt>GapList</tt> instance from a stream (that is,
813: * deserialize it).
814: */
815: private void readObject(java.io.ObjectInputStream s)
816: throws java.io.IOException, ClassNotFoundException {
817: // Read in size, and any hidden stuff
818: s.defaultReadObject();
819:
820: // Read in array length and allocate array
821: int arrayLength = s.readInt();
822: elementData = allocateElementsArray(arrayLength);
823:
824: // Read in all elements in the proper order.
825: int i = 0;
826: while (i < gapStart) {
827: @SuppressWarnings("unchecked")
828: E e = (E) s.readObject();
829: elementData[i] = e;
830: i++;
831: }
832: i += gapLength;
833: int elementDataLength = elementData.length;
834: while (i < elementDataLength) {
835: @SuppressWarnings("unchecked")
836: E e = (E) s.readObject();
837: elementData[i] = e;
838: i++;
839: }
840: }
841:
842: /**
843: * Internal consistency check.
844: */
845: protected void consistencyCheck() {
846: if (gapStart < 0 || gapLength < 0
847: || gapStart + gapLength > elementData.length) {
848: consistencyError("Inconsistent gap"); // NOI18N
849: }
850:
851: // Check whether the whole gap contains only nulls
852: for (int i = gapStart + gapLength - 1; i >= gapStart; i--) {
853: if (elementData[i] != null) {
854: consistencyError("Non-null value at raw-index i"); // NOI18N
855: }
856: }
857: }
858:
859: protected final void consistencyError(String s) {
860: throw new IllegalStateException(s + ": " + dumpDetails()); // NOI18N
861: }
862:
863: protected String dumpDetails() {
864: return dumpInternals() + "; DATA:\n" + toString(); // NOI18N
865: }
866:
867: protected String dumpInternals() {
868: return "elems: " + size() + '(' + elementData.length // NOI18N
869: + "), gap(s=" + gapStart + ", l=" + gapLength + ')';// NOI18N
870: }
871:
872: @SuppressWarnings("unchecked")
873: private E[] allocateElementsArray(int capacity) {
874: return (E[]) new Object[capacity];
875: }
876:
877: public String toString() {
878: return dumpElements(this );
879: }
880:
881: public static String dumpElements(java.util.List l) {
882: StringBuffer sb = new StringBuffer();
883: int size = l.size();
884: int sizeDigitCount = indexDigitCount(size);
885: for (int i = 0; i < size; i++) {
886: sb.append('[');
887: int extraSpacesCount = sizeDigitCount - indexDigitCount(i);
888: while (extraSpacesCount > 0) {
889: sb.append(' ');
890: }
891: sb.append(i);
892: sb.append("]: "); // NOI18N
893: sb.append(l.get(i));
894: sb.append("\n"); // NOI18N
895: }
896: return sb.toString();
897: }
898:
899: private static int indexDigitCount(int i) {
900: int digitCount = 1;
901: while (i >= 10) {
902: i /= 10;
903: digitCount++;
904: }
905: return digitCount;
906: }
907:
908: }
|