← Back to branch summary

~ubuntu-branches/ubuntu/quantal/netbeans/quantal

« back to all changes in this revision

Viewing changes to editor/util/src/org/netbeans/lib/editor/util/GapList.java

  • Committer: Bazaar Package Importer
  • Author(s): Marek Slama
  • Date: 2008-01-29 14:11:22 UTC
  • Revision ID: james.westby@ubuntu.com-20080129141122-fnzjbo11ntghxfu7
Tags: upstream-6.0.1
Import upstream version 6.0.1

Show diffs side-by-side

added added

removed removed

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