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  ;
23  import java.util.Collection  ;
24  import java.util.List  ;
25  import java.util.RandomAccess  ;
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  <E>
36  implements List  <E>, RandomAccess  , Cloneable  , java.io.Serializable   {
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  ("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  <? 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  ("unchecked")
94          E[] data = (E[])c.toArray(new Object  [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   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   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   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   clone() {
275         try {
276             @SuppressWarnings  ("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   e) {
288             // this shouldn't happen, since we are Cloneable
289             throw new InternalError  ();
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  [] 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  [] dest, int destIndex) {
310         
311         if (startIndex < 0 || endIndex < startIndex || endIndex > size()) {
312             throw new IndexOutOfBoundsException  ("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  <E> dest) {
343         
344         if (startIndex < 0 || endIndex < startIndex || endIndex > size()) {
345             throw new IndexOutOfBoundsException  ("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  [] toArray() {
383         int size = size();
384         Object  [] result = new Object  [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  ("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  (
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  <? 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  <? 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  [] 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  [] elements, int off, int len) {
574         int size = size();
575         if (index > size || index < 0) {
576             throw new IndexOutOfBoundsException  (
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  (
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  ("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  [] 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   s)
754     throws java.io.IOException  {
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   s)
780     throws java.io.IOException  , ClassNotFoundException   {
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  ("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  ("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   s) {
825         throw new IllegalStateException  (s + ": " + dumpDetails()); // NOI18N
826     }
827     
828     protected String   dumpDetails() {
829         return dumpInternals() + "; DATA:\n" + toString(); // NOI18N
830     }
831     
832     protected String   dumpInternals() {
833         return "elems: " + size() + '(' + elementData.length // NOI18N
834             + "), gap(s=" + gapStart + ", l=" + gapLength + ')';// NOI18N
835     }
836     
837     @SuppressWarnings  ("unchecked")
838     private E[] allocateElementsArray(int capacity) {
839         return (E[])new Object  [capacity];
840     }
841     
842     public String   toString() {
843         return dumpElements(this);
844     }
845 
846     public static String   dumpElements(java.util.List   l) {
847         StringBuffer   sb = new StringBuffer  ();
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
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags