KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > netbeans > lib > editor > util > GapList


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 import java.util.AbstractList JavaDoc;
23 import java.util.Collection JavaDoc;
24 import java.util.List JavaDoc;
25 import java.util.RandomAccess JavaDoc;
26
27 /**
28  * List implementation that stores items in an array
29  * with a gap.
30  *
31  * @author Miloslav Metelka
32  * @version 1.00
33  */

34
35 public class GapList<E> extends AbstractList JavaDoc<E>
36 implements List JavaDoc<E>, RandomAccess JavaDoc, Cloneable JavaDoc, java.io.Serializable JavaDoc {
37
38     /**
39      * The array buffer into which the elements are stored.
40      * <br>
41      * The elements are stored in the whole array except
42      * the indexes starting at <code>gapStart</code>
43      * till <code>gapStart + gapLength - 1</code>.
44      */

45     private transient E[] elementData; // 16 bytes (12-super(modCount) + 4)
46

47     /**
48      * The start of the gap in the elementData array.
49      */

50     private int gapStart; // 20 bytes
51

52     /**
53      * Length of the gap in the elementData array starting at gapStart.
54      */

55     private int gapLength; // 24 bytes
56

57     /**
58      * Constructs an empty list with the specified initial capacity.
59      *
60      * @param initialCapacity the initial capacity of the list.
61      * @exception IllegalArgumentException if the specified initial capacity
62      * is negative
63      */

64     public GapList(int initialCapacity) {
65         if (initialCapacity < 0) {
66             throw new IllegalArgumentException JavaDoc("Illegal Capacity: " // NOI18N
67
+ initialCapacity);
68         }
69         this.elementData = allocateElementsArray(initialCapacity);
70         this.gapLength = initialCapacity;
71     }
72     
73     /**
74      * Constructs an empty list with an initial capacity of ten.
75      */

76     public GapList() {
77         this(10);
78     }
79     
80     /**
81      * Constructs a list containing the elements of the specified
82      * collection, in the order they are returned by the collection's
83      * iterator. The <tt>GapList</tt> instance has an initial capacity of
84      * 110% the size of the specified collection.
85      *
86      * @param c the collection whose elements are to be placed into this list.
87      * @throws NullPointerException if the specified collection is null.
88      */

89     public GapList(Collection JavaDoc<? extends E> c) {
90         int size = c.size();
91         // Allow 10% room for growth
92
int capacity = (int)Math.min((size*110L)/100,Integer.MAX_VALUE);
93         @SuppressWarnings JavaDoc("unchecked")
94         E[] data = (E[])c.toArray(new Object JavaDoc[capacity]);
95         elementData = data;
96         this.gapStart = size;
97         this.gapLength = elementData.length - size;
98     }
99     
100     /**
101      * Trims the capacity of this <tt>GapList</tt> instance to be the
102      * list's current size. An application can use this operation to minimize
103      * the storage of an <tt>GapList</tt> instance.
104      */

105     public void trimToSize() {
106         modCount++;
107         if (gapLength > 0) {
108             int newLength = elementData.length - gapLength;
109             E[] newElementData = allocateElementsArray(newLength);
110             copyAllData(newElementData);
111             elementData = newElementData;
112             // Leave gapStart as is
113
gapLength = 0;
114         }
115     }
116     
117     /**
118      * Increases the capacity of this <tt>GapList</tt> instance, if
119      * necessary, to ensure that it can hold at least the number of elements
120      * specified by the minimum capacity argument.
121      *
122      * @param minCapacity the desired minimum capacity.
123      */

124     public void ensureCapacity(int minCapacity) {
125         modCount++; // expected to always increment modCount (same in ArrayList)
126
int oldCapacity = elementData.length;
127         if (minCapacity > oldCapacity) {
128             int newCapacity = (oldCapacity * 3)/2 + 1;
129             if (newCapacity < minCapacity) {
130                 newCapacity = minCapacity;
131             }
132             int gapEnd = gapStart + gapLength;
133             int afterGapLength = (oldCapacity - gapEnd);
134             int newGapEnd = newCapacity - afterGapLength;
135             E[] newElementData = allocateElementsArray(newCapacity);
136             System.arraycopy(elementData, 0, newElementData, 0, gapStart);
137             System.arraycopy(elementData, gapEnd, newElementData, newGapEnd, afterGapLength);
138             elementData = newElementData;
139             gapLength = newGapEnd - gapStart;
140         }
141     }
142     
143     /**
144      * Returns the number of elements in this list.
145      *
146      * @return the number of elements in this list.
147      */

148     public int size() {
149         return elementData.length - gapLength;
150     }
151     
152     /**
153      * Tests if this list has no elements.
154      *
155      * @return <tt>true</tt> if this list has no elements;
156      * <tt>false</tt> otherwise.
157      */

158     public boolean isEmpty() {
159         return (elementData.length == gapLength);
160     }
161     
162     /**
163      * Returns <tt>true</tt> if this list contains the specified element.
164      *
165      * @param elem element whose presence in this List is to be tested.
166      * @return <code>true</code> if the specified element is present;
167      * <code>false</code> otherwise.
168      */

169     public boolean contains(Object JavaDoc elem) {
170         return indexOf(elem) >= 0;
171     }
172     
173     /**
174      * Searches for the first occurence of the given argument, testing
175      * for equality using the <tt>equals</tt> method.
176      *
177      * @param elem an object.
178      * @return the index of the first occurrence of the argument in this
179      * list; returns <tt>-1</tt> if the object is not found.
180      * @see Object#equals(Object)
181      */

182     public int indexOf(Object JavaDoc elem) {
183         if (elem == null) {
184             int i = 0;
185             while (i < gapStart) {
186                 if (elementData[i] == null) {
187                     return i;
188                 }
189                 i++;
190             }
191             i += gapLength;
192             int elementDataLength = elementData.length;
193             while (i < elementDataLength) {
194                 if (elementData[i] == null) {
195                     return i;
196                 }
197                 i++;
198             }
199             
200         } else { // elem not null
201
int i = 0;
202             while (i < gapStart) {
203                 if (elem.equals(elementData[i])) {
204                     return i;
205                 }
206                 i++;
207             }
208             i += gapLength;
209             int elementDataLength = elementData.length;
210             while (i < elementDataLength) {
211                 if (elem.equals(elementData[i])) {
212                     return i;
213                 }
214                 i++;
215             }
216         }
217         
218         return -1;
219     }
220     
221     /**
222      * Returns the index of the last occurrence of the specified object in
223      * this list.
224      *
225      * @param elem the desired element.
226      * @return the index of the last occurrence of the specified object in
227      * this list; returns -1 if the object is not found.
228      */

229     public int lastIndexOf(Object JavaDoc elem) {
230         if (elem == null) {
231             int i = elementData.length - 1;
232             int gapEnd = gapStart + gapLength;
233             while (i >= gapEnd) {
234                 if (elementData[i] == null) {
235                     return i;
236                 }
237                 i--;
238             }
239             i -= gapLength;
240             while (i >= 0) {
241                 if (elementData[i] == null) {
242                     return i;
243                 }
244                 i--;
245             }
246             
247         } else { // elem not null
248
int i = elementData.length - 1;
249             int gapEnd = gapStart + gapLength;
250             while (i >= gapEnd) {
251                 if (elem.equals(elementData[i])) {
252                     return i;
253                 }
254                 i--;
255             }
256             i -= gapLength;
257             while (i >= 0) {
258                 if (elem.equals(elementData[i])) {
259                     return i;
260                 }
261                 i--;
262             }
263         }
264         
265         return -1;
266     }
267     
268     /**
269      * Returns a shallow copy of this <tt>GapList</tt> instance. (The
270      * elements themselves are not copied.)
271      *
272      * @return a clone of this <tt>GapList</tt> instance.
273      */

274     public Object JavaDoc clone() {
275         try {
276             @SuppressWarnings JavaDoc("unchecked")
277             GapList<E> clonedList = (GapList<E>)super.clone();
278             int size = size();
279             E[] clonedElementData = allocateElementsArray(size);
280             copyAllData(clonedElementData);
281             clonedList.elementData = clonedElementData;
282             // Will retain gapStart - would have to call moved*() otherwise
283
clonedList.gapStart = size;
284             clonedList.resetModCount();
285             return clonedList;
286
287         } catch (CloneNotSupportedException JavaDoc e) {
288             // this shouldn't happen, since we are Cloneable
289
throw new InternalError JavaDoc();
290         }
291     }
292
293     /**
294      * @deprecated use {@link #copyElements(int, int, Object[], int)} which performs the same operation
295      */

296     public void copyItems(int startIndex, int endIndex,
297     Object JavaDoc[] dest, int destIndex) {
298         copyElements(startIndex, endIndex, dest, destIndex);
299     }
300
301     /**
302      * Copy elements of this list between the given index range to the given object array.
303      *
304      * @param startIndex start index of the region of this list to be copied.
305      * @param endIndex end index of the region of this list to be copied.
306      * @param dest collection to the end of which the items should be copied.
307      */

308     public void copyElements(int startIndex, int endIndex,
309     Object JavaDoc[] dest, int destIndex) {
310         
311         if (startIndex < 0 || endIndex < startIndex || endIndex > size()) {
312             throw new IndexOutOfBoundsException JavaDoc("startIndex=" + startIndex // NOI18N
313
+ ", endIndex=" + endIndex + ", size()=" + size()); // NOI18N
314
}
315         
316         if (endIndex < gapStart) { // fully below gap
317
System.arraycopy(elementData, startIndex,
318             dest, destIndex, endIndex - startIndex);
319             
320         } else { // above gap or spans the gap
321
if (startIndex >= gapStart) { // fully above gap
322
System.arraycopy(elementData, startIndex + gapLength, dest, destIndex,
323                 endIndex - startIndex);
324                 
325             } else { // spans gap
326
int beforeGap = gapStart - startIndex;
327                 System.arraycopy(elementData, startIndex, dest, destIndex, beforeGap);
328                 System.arraycopy(elementData, gapStart + gapLength, dest, destIndex + beforeGap,
329                 endIndex - startIndex - beforeGap);
330             }
331         }
332     }
333     
334     /**
335      * Copy elements of this list between the given index range
336      * to the end of the given collection.
337      *
338      * @param startIndex start index of the region of this list to be copied.
339      * @param endIndex end index of the region of this list to be copied.
340      * @param dest collection to the end of which the items should be copied.
341      */

342     public void copyElements(int startIndex, int endIndex, Collection JavaDoc<E> dest) {
343         
344         if (startIndex < 0 || endIndex < startIndex || endIndex > size()) {
345             throw new IndexOutOfBoundsException JavaDoc("startIndex=" + startIndex // NOI18N
346
+ ", endIndex=" + endIndex + ", size()=" + size()); // NOI18N
347
}
348         
349         if (endIndex < gapStart) { // fully below gap
350
while (startIndex < endIndex) {
351                 dest.add(elementData[startIndex++]);
352             }
353             
354         } else { // above gap or spans the gap
355
if (startIndex >= gapStart) { // fully above gap
356
startIndex += gapLength;
357                 endIndex += gapLength;
358                 while (startIndex < endIndex) {
359                     dest.add(elementData[startIndex++]);
360                 }
361                 
362             } else { // spans gap
363
while (startIndex < gapStart) {
364                     dest.add(elementData[startIndex++]);
365                 }
366                 startIndex += gapLength;
367                 endIndex += gapLength;
368                 while (startIndex < endIndex) {
369                     dest.add(elementData[startIndex++]);
370                 }
371             }
372         }
373     }
374     
375     /**
376      * Returns an array containing all of the elements in this list
377      * in the correct order.
378      *
379      * @return an array containing all of the elements in this list
380      * in the correct order.
381      */

382     public Object JavaDoc[] toArray() {
383         int size = size();
384         Object JavaDoc[] result = new Object JavaDoc[size];
385         copyAllData(result);
386         return result;
387     }
388     
389     /**
390      * Returns an array containing all of the elements in this list in the
391      * correct order; the runtime type of the returned array is that of the
392      * specified array. If the list fits in the specified array, it is
393      * returned therein. Otherwise, a new array is allocated with the runtime
394      * type of the specified array and the size of this list.<p>
395      *
396      * If the list fits in the specified array with room to spare (i.e., the
397      * array has more elements than the list), the element in the array
398      * immediately following the end of the collection is set to
399      * <tt>null</tt>. This is useful in determining the length of the list
400      * <i>only</i> if the caller knows that the list does not contain any
401      * <tt>null</tt> elements.
402      *
403      * @param a the array into which the elements of the list are to
404      * be stored, if it is big enough; otherwise, a new array of the
405      * same runtime type is allocated for this purpose.
406      * @return an array containing the elements of the list.
407      * @throws ArrayStoreException if the runtime type of a is not a supertype
408      * of the runtime type of every element in this list.
409      */

410     public <T> T[] toArray(T[] a) {
411         int size = size();
412         if (a.length < size) {
413             @SuppressWarnings JavaDoc("unchecked")
414             T[] tmp = (T[])java.lang.reflect.Array.newInstance(
415                 a.getClass().getComponentType(), size);
416             a = tmp;
417         }
418         copyAllData(a);
419         if (a.length > size)
420             a[size] = null;
421         
422         return a;
423     }
424     
425     // Positional Access Operations
426

427     /**
428      * Returns the element at the specified position in this list.
429      *
430      * @param index index of element to return.
431      * @return the element at the specified position in this list.
432      * @throws IndexOutOfBoundsException if index is out of range <tt>(index
433      * &lt; 0 || index &gt;= size())</tt>.
434      */

435     public E get(int index) {
436         // rangeCheck(index) not necessary - would fail with AIOOBE anyway
437
return elementData[(index < gapStart) ? index : (index + gapLength)];
438     }
439     
440     /**
441      * Replaces the element at the specified position in this list with
442      * the specified element.
443      *
444      * @param index index of element to replace.
445      * @param element element to be stored at the specified position.
446      * @return the element previously at the specified position.
447      * @throws IndexOutOfBoundsException if index out of range
448      * <tt>(index &lt; 0 || index &gt;= size())</tt>.
449      */

450     public E set(int index, E element) {
451         // rangeCheck(index) not necessary - would fail with AIOOBE anyway
452
if (index >= gapStart) {
453             index += gapLength;
454         }
455         E oldValue = elementData[index];
456         elementData[index] = element;
457         return oldValue;
458     }
459     
460     /**
461      * Swap elements at the given indexes.
462      */

463     public void swap(int index1, int index2) {
464         // rangeCheck(index) not necessary - would fail with AIOOBE anyway
465
// rangeCheck(byIndex) not necessary - would fail with AIOOBE anyway
466
if (index1 >= gapStart) {
467             index1 += gapLength;
468         }
469         if (index2 >= gapStart) {
470             index2 += gapLength;
471         }
472         E tmpValue = elementData[index1];
473         elementData[index1] = elementData[index2];
474         elementData[index2] = tmpValue;
475     }
476     
477     /**
478      * Appends the specified element to the end of this list.
479      *
480      * @param element non-null element to be appended to this list.
481      * @return <tt>true</tt> (as per the general contract of Collection.add).
482      */

483     public boolean add(E element) {
484         int size = size();
485         ensureCapacity(size + 1); // Increments modCount
486
addImpl(size, element);
487         return true;
488     }
489     
490     /**
491      * Inserts the specified element at the specified position in this
492      * list. Shifts the element currently at that position (if any) and
493      * any subsequent elements to the right (adds one to their indices).
494      *
495      * @param index index at which the specified element is to be inserted.
496      * @param element element to be inserted.
497      * @throws IndexOutOfBoundsException if index is out of range
498      * <tt>(index &lt; 0 || index &gt; size())</tt>.
499      */

500     public void add(int index, E element) {
501         int size = size();
502         if (index > size || index < 0) {
503             throw new IndexOutOfBoundsException JavaDoc(
504                 "Index: " + index + ", Size: " + size); // NOI18N
505
}
506         ensureCapacity(size + 1); // Increments modCount
507
addImpl(index, element);
508     }
509     
510     private void addImpl(int index, E element) {
511         moveGap(index);
512         elementData[gapStart++] = element;
513         gapLength--;
514     }
515     
516     /**
517      * Appends all of the elements in the specified Collection to the end of
518      * this list, in the order that they are returned by the
519      * specified Collection's Iterator. The behavior of this operation is
520      * undefined if the specified Collection is modified while the operation
521      * is in progress. (This implies that the behavior of this call is
522      * undefined if the specified Collection is this list, and this
523      * list is nonempty.)
524      *
525      * @param c the elements to be inserted into this list.
526      * @return <tt>true</tt> if this list changed as a result of the call.
527      * @throws NullPointerException if the specified collection is null.
528      */

529     public boolean addAll(Collection JavaDoc<? extends E> c) {
530         return addAll(size(), c);
531     }
532     
533     /**
534      * Inserts all of the elements in the specified Collection into this
535      * list, starting at the specified position. Shifts the element
536      * currently at that position (if any) and any subsequent elements to
537      * the right (increases their indices). The new elements will appear
538      * in the list in the order that they are returned by the
539      * specified Collection's iterator.
540      *
541      * @param index index at which to insert first element
542      * from the specified collection.
543      * @param c elements to be inserted into this list.
544      * @return <tt>true</tt> if this list changed as a result of the call.
545      * @throws IndexOutOfBoundsException if index out of range <tt>(index
546      * &lt; 0 || index &gt; size())</tt>.
547      * @throws NullPointerException if the specified Collection is null.
548      */

549     public boolean addAll(int index, Collection JavaDoc<? extends E> c) {
550         return addArray(index, c.toArray());
551     }
552
553     /*
554      * Inserts all elements from the given array into this list, starting
555      * at the given index.
556      *
557      * @param index index at which to insert first element from the array.
558      * @param elements array of elements to insert.
559      */

560     public boolean addArray(int index, Object JavaDoc[] elements) {
561         return addArray(index, elements, 0, elements.length);
562     }
563
564     /**
565      * Inserts elements from the given array into this list, starting
566      * at the given index.
567      *
568      * @param index index at which to insert first element.
569      * @param elements array of elements from which to insert elements.
570      * @param off offset in the elements pointing to first element to copy.
571      * @param len number of elements to copy from the elements array.
572      */

573     public boolean addArray(int index, Object JavaDoc[] elements, int off, int len) {
574         int size = size();
575         if (index > size || index < 0) {
576             throw new IndexOutOfBoundsException JavaDoc(
577                 "Index: " + index + ", Size: " + size); // NOI18N
578
}
579         
580         ensureCapacity(size + len); // Increments modCount
581

582         moveGap(index); // after that (index == gapStart)
583
System.arraycopy(elements, off, elementData, index, len);
584         gapStart += len;
585         gapLength -= len;
586
587         return (len != 0);
588     }
589     
590     /**
591      * Removes all of the elements from this list. The list will
592      * be empty after this call returns.
593      */

594     public void clear() {
595         removeRange(0, size());
596     }
597     
598     /**
599      * Removes the element at the specified position in this list.
600      * Shifts any subsequent elements to the left (subtracts one from their
601      * indices).
602      *
603      * @param index the index of the element to removed.
604      * @return the element that was removed from the list.
605      * @throws IndexOutOfBoundsException if index out of range <tt>(index
606      * &lt; 0 || index &gt;= size())</tt>.
607      */

608     public E remove(int index) {
609         int size = size();
610         if (index >= size || index < 0) {
611             throw new IndexOutOfBoundsException JavaDoc(
612                 "remove(): Index: " + index + ", Size: " + size); // NOI18N
613
}
614
615         modCount++;
616         moveGap(index + 1); // if previous were adds() - this should be no-op
617
E oldValue = elementData[index];
618         elementData[index] = null;
619         gapStart--;
620         gapLength++;
621         
622         return oldValue;
623     }
624
625     /**
626      * Removes elements at the given index.
627      *
628      * @param index index of the first element to be removed.
629      * @param count number of elements to remove.
630      */

631     public void remove(int index, int count) {
632         int toIndex = index + count;
633         if (index < 0 || toIndex < index || toIndex > size()) {
634             throw new IndexOutOfBoundsException JavaDoc("index=" + index // NOI18N
635
+ ", count=" + count + ", size()=" + size()); // NOI18N
636
}
637         removeRange(index, toIndex);
638     }
639     
640     /**
641      * Removes from this List all of the elements whose index is between
642      * fromIndex, inclusive and toIndex, exclusive. Shifts any succeeding
643      * elements to the left (reduces their index).
644      * This call shortens the list by <tt>(toIndex - fromIndex)</tt> elements.
645      * (If <tt>toIndex==fromIndex</tt>, this operation has no effect.)
646      *
647      * @param fromIndex index of first element to be removed.
648      * @param toIndex index after last element to be removed.
649      */

650     protected void removeRange(int fromIndex, int toIndex) {
651         modCount++;
652         if (fromIndex == toIndex) {
653             return;
654         }
655         
656         int removeCount = toIndex - fromIndex;
657         if (fromIndex >= gapStart) { // completely over gap
658
// Move gap to the start of the removed area
659
// (this should be the minimum necessary count of elements moved)
660
moveGap(fromIndex);
661             
662             // Allow GC of removed items
663
fromIndex += gapLength; // begining of abandoned area
664
toIndex += gapLength;
665             while (fromIndex < toIndex) {
666                 elementData[fromIndex] = null;
667                 fromIndex++;
668             }
669             
670         } else { // completely below gap or spans the gap
671
if (toIndex <= gapStart) {
672                 // Move gap to the end of the removed area
673
// (this should be the minimum necessary count of elements moved)
674
moveGap(toIndex);
675                 gapStart = fromIndex;
676                 
677             } else { // spans gap: gapStart > fromIndex but gapStart - fromIndex < removeCount
678
// Allow GC of removed items
679
for (int clearIndex = fromIndex; clearIndex < gapStart; clearIndex++) {
680                     elementData[clearIndex] = null;
681                 }
682                 
683                 fromIndex = gapStart + gapLength; // part above the gap
684
gapStart = toIndex - removeCount; // original value of fromIndex
685
toIndex += gapLength;
686             }
687             
688             // Allow GC of removed items
689
while (fromIndex < toIndex) {
690                 elementData[fromIndex++] = null;
691             }
692             
693         }
694         
695         gapLength += removeCount;
696     }
697     
698     private void moveGap(int index) {
699         if (index == gapStart) {
700             return; // do nothing
701
}
702
703         if (gapLength > 0) {
704             if (index < gapStart) { // move gap down
705
int moveSize = gapStart - index;
706                 System.arraycopy(elementData, index, elementData,
707                     gapStart + gapLength - moveSize, moveSize);
708                 clearEmpty(index, Math.min(moveSize, gapLength));
709
710             } else { // above gap
711
int gapEnd = gapStart + gapLength;
712                 int moveSize = index - gapStart;
713                 System.arraycopy(elementData, gapEnd, elementData, gapStart, moveSize);
714                 if (index < gapEnd) {
715                     clearEmpty(gapEnd, moveSize);
716                 } else {
717                     clearEmpty(index, gapLength);
718                 }
719             }
720         }
721         gapStart = index;
722     }
723     
724     private void copyAllData(Object JavaDoc[] toArray) {
725         if (gapLength != 0) {
726             int gapEnd = gapStart + gapLength;
727             System.arraycopy(elementData, 0, toArray, 0, gapStart);
728             System.arraycopy(elementData, gapEnd, toArray, gapStart,
729                 elementData.length - gapEnd);
730         } else { // no gap => single copy of everything
731
System.arraycopy(elementData, 0, toArray, 0, elementData.length);
732         }
733     }
734     
735     private void clearEmpty(int index, int length) {
736         while (--length >= 0) {
737             elementData[index++] = null; // allow GC
738
}
739     }
740     
741     private void resetModCount() {
742         modCount = 0;
743     }
744     
745     /**
746      * Save the state of the <tt>GapList</tt> instance to a stream (that
747      * is, serialize it).
748      *
749      * @serialData The length of the array backing the <tt>GapList</tt>
750      * instance is emitted (int), followed by all of its elements
751      * (each an <tt>Object</tt>) in the proper order.
752      */

753     private void writeObject(java.io.ObjectOutputStream JavaDoc s)
754     throws java.io.IOException JavaDoc{
755         // Write out element count, and any hidden stuff
756
s.defaultWriteObject();
757         
758         // Write out array length
759
s.writeInt(elementData.length);
760         
761         // Write out all elements in the proper order.
762
int i = 0;
763         while (i < gapStart) {
764             s.writeObject(elementData[i]);
765             i++;
766         }
767         i += gapLength;
768         int elementDataLength = elementData.length;
769         while (i < elementDataLength) {
770             s.writeObject(elementData[i]);
771             i++;
772         }
773     }
774     
775     /**
776      * Reconstitute the <tt>GapList</tt> instance from a stream (that is,
777      * deserialize it).
778      */

779     private void readObject(java.io.ObjectInputStream JavaDoc s)
780     throws java.io.IOException JavaDoc, ClassNotFoundException JavaDoc {
781         // Read in size, and any hidden stuff
782
s.defaultReadObject();
783         
784         // Read in array length and allocate array
785
int arrayLength = s.readInt();
786         elementData = allocateElementsArray(arrayLength);
787         
788         // Read in all elements in the proper order.
789
int i = 0;
790         while (i < gapStart) {
791             @SuppressWarnings JavaDoc("unchecked")
792             E e = (E)s.readObject();
793             elementData[i] = e;
794             i++;
795         }
796         i += gapLength;
797         int elementDataLength = elementData.length;
798         while (i < elementDataLength) {
799             @SuppressWarnings JavaDoc("unchecked")
800             E e = (E)s.readObject();
801             elementData[i] = e;
802             i++;
803         }
804     }
805     
806     /**
807      * Internal consistency check.
808      */

809     protected void consistencyCheck() {
810         if (gapStart < 0 || gapLength < 0
811             || gapStart + gapLength > elementData.length
812         ) {
813             consistencyError("Inconsistent gap"); // NOI18N
814
}
815         
816         // Check whether the whole gap contains only nulls
817
for (int i = gapStart + gapLength - 1; i >= gapStart; i--) {
818             if (elementData[i] != null) {
819                 consistencyError("Non-null value at raw-index i"); // NOI18N
820
}
821         }
822     }
823     
824     protected final void consistencyError(String JavaDoc s) {
825         throw new IllegalStateException JavaDoc(s + ": " + dumpDetails()); // NOI18N
826
}
827     
828     protected String JavaDoc dumpDetails() {
829         return dumpInternals() + "; DATA:\n" + toString(); // NOI18N
830
}
831     
832     protected String JavaDoc dumpInternals() {
833         return "elems: " + size() + '(' + elementData.length // NOI18N
834
+ "), gap(s=" + gapStart + ", l=" + gapLength + ')';// NOI18N
835
}
836     
837     @SuppressWarnings JavaDoc("unchecked")
838     private E[] allocateElementsArray(int capacity) {
839         return (E[])new Object JavaDoc[capacity];
840     }
841     
842     public String JavaDoc toString() {
843         return dumpElements(this);
844     }
845
846     public static String JavaDoc dumpElements(java.util.List JavaDoc l) {
847         StringBuffer JavaDoc sb = new StringBuffer JavaDoc();
848         int size = l.size();
849         int sizeDigitCount = indexDigitCount(size);
850         for (int i = 0; i < size; i++) {
851             sb.append('[');
852             int extraSpacesCount = sizeDigitCount - indexDigitCount(i);
853             while (extraSpacesCount > 0) {
854                 sb.append(' ');
855             }
856             sb.append(i);
857             sb.append("]: "); // NOI18N
858
sb.append(l.get(i));
859             sb.append("\n"); // NOI18N
860
}
861         return sb.toString();
862     }
863     
864     private static int indexDigitCount(int i) {
865         int digitCount = 1;
866         while (i >= 10) {
867             i /= 10;
868             digitCount++;
869         }
870         return digitCount;
871     }
872
873 }
874
Popular Tags