Removed
Link Here
|
1 |
/* |
2 |
* Sun Public License Notice |
3 |
* |
4 |
* The contents of this file are subject to the Sun Public License |
5 |
* Version 1.0 (the "License"). You may not use this file except in |
6 |
* compliance with the License. A copy of the License is available at |
7 |
* http://www.sun.com/ |
8 |
* |
9 |
* The Original Code is NetBeans. The Initial Developer of the Original |
10 |
* Code is Sun Microsystems, Inc. Portions Copyright 1997-2000 Sun |
11 |
* Microsystems, Inc. All Rights Reserved. |
12 |
*/ |
13 |
|
14 |
package org.netbeans.modules.editor.util; |
15 |
|
16 |
import java.util.AbstractList; |
17 |
import java.util.Collection; |
18 |
import java.util.RandomAccess; |
19 |
|
20 |
/** |
21 |
* List implementation that stores items in an array |
22 |
* with a gap. |
23 |
* |
24 |
* @author Miloslav Metelka |
25 |
* @version 1.00 |
26 |
*/ |
27 |
|
28 |
public class GapList extends AbstractList |
29 |
implements RandomAccess, Cloneable, java.io.Serializable { |
30 |
|
31 |
private static final Object[] EMPTY_ELEMENT_ARRAY = new Object[0]; |
32 |
|
33 |
/** |
34 |
* The array buffer into which the elements are stored. |
35 |
* <br> |
36 |
* The elements are stored in the whole array except |
37 |
* the indexes starting at <code>gapStart</code> |
38 |
* till <code>gapStart + gapLength - 1</code>. |
39 |
*/ |
40 |
private transient Object elementData[]; |
41 |
|
42 |
/** |
43 |
* The start of the gap in the elementData array. |
44 |
*/ |
45 |
private int gapStart; |
46 |
|
47 |
/** |
48 |
* Length of the gap in the elementData array starting at gapStart. |
49 |
*/ |
50 |
private int gapLength; |
51 |
|
52 |
/** |
53 |
* Constructs an empty list with the specified initial capacity. |
54 |
* |
55 |
* @param initialCapacity the initial capacity of the list. |
56 |
* @exception IllegalArgumentException if the specified initial capacity |
57 |
* is negative |
58 |
*/ |
59 |
public GapList(int initialCapacity) { |
60 |
if (initialCapacity < 0) { |
61 |
throw new IllegalArgumentException("Illegal Capacity: " // NOI18N |
62 |
+ initialCapacity); |
63 |
} |
64 |
this.elementData = new Object[initialCapacity]; |
65 |
this.gapLength = initialCapacity; |
66 |
} |
67 |
|
68 |
/** |
69 |
* Constructs an empty list. |
70 |
*/ |
71 |
public GapList() { |
72 |
elementData = EMPTY_ELEMENT_ARRAY; |
73 |
} |
74 |
|
75 |
/** |
76 |
* Constructs a list containing the elements of the specified |
77 |
* collection, in the order they are returned by the collection's |
78 |
* iterator. The <tt>GapList</tt> instance has an initial capacity of |
79 |
* 110% the size of the specified collection. |
80 |
* |
81 |
* @param c the collection whose elements are to be placed into this list. |
82 |
* @throws NullPointerException if the specified collection is null. |
83 |
*/ |
84 |
public GapList(Collection c) { |
85 |
int size = c.size(); |
86 |
// Allow 10% room for growth |
87 |
elementData = new Object[ |
88 |
(int)Math.min((size*110L)/100,Integer.MAX_VALUE)]; |
89 |
c.toArray(elementData); |
90 |
this.gapStart = size; |
91 |
this.gapLength = elementData.length - size; |
92 |
} |
93 |
|
94 |
/** |
95 |
* Trims the capacity of this <tt>GapList</tt> instance to be the |
96 |
* list's current size. An application can use this operation to minimize |
97 |
* the storage of an <tt>GapList</tt> instance. |
98 |
*/ |
99 |
public void trimToSize() { |
100 |
modCount++; |
101 |
if (gapLength > 0) { |
102 |
int newLength = elementData.length - gapLength; |
103 |
Object[] newElementData = new Object[newLength]; |
104 |
copyAllData(newElementData); |
105 |
elementData = newElementData; |
106 |
// Leave gapStart as is |
107 |
gapLength = 0; |
108 |
} |
109 |
} |
110 |
|
111 |
/** |
112 |
* Increases the capacity of this <tt>GapList</tt> instance, if |
113 |
* necessary, to ensure that it can hold at least the number of elements |
114 |
* specified by the minimum capacity argument. |
115 |
* |
116 |
* @param minCapacity the desired minimum capacity. |
117 |
*/ |
118 |
public void ensureCapacity(int minCapacity) { |
119 |
modCount++; // expected to always increment modCount - see add() operations |
120 |
int oldCapacity = elementData.length; |
121 |
if (minCapacity > oldCapacity) { |
122 |
int newCapacity = (oldCapacity * 3)/2 + 1; |
123 |
if (newCapacity < minCapacity) { |
124 |
newCapacity = minCapacity; |
125 |
} |
126 |
int gapEnd = gapStart + gapLength; |
127 |
int afterGapLength = (oldCapacity - gapEnd); |
128 |
// Must ensure the gap will not be logically moved |
129 |
// (would have to call movedAbove/BeforeGapUpdate() methods) |
130 |
int newGapEnd = newCapacity - afterGapLength; |
131 |
Object[] newElementData = new Object[newCapacity]; |
132 |
System.arraycopy(elementData, 0, newElementData, 0, gapStart); |
133 |
System.arraycopy(elementData, gapEnd, newElementData, newGapEnd, afterGapLength); |
134 |
elementData = newElementData; |
135 |
gapLength = newGapEnd - gapStart; |
136 |
} |
137 |
} |
138 |
|
139 |
/** |
140 |
* Returns the number of elements in this list. |
141 |
* |
142 |
* @return the number of elements in this list. |
143 |
*/ |
144 |
public int size() { |
145 |
return elementData.length - gapLength; |
146 |
} |
147 |
|
148 |
/** |
149 |
* Tests if this list has no elements. |
150 |
* |
151 |
* @return <tt>true</tt> if this list has no elements; |
152 |
* <tt>false</tt> otherwise. |
153 |
*/ |
154 |
public boolean isEmpty() { |
155 |
return (elementData.length == gapLength); |
156 |
} |
157 |
|
158 |
/** |
159 |
* Returns <tt>true</tt> if this list contains the specified element. |
160 |
* |
161 |
* @param elem element whose presence in this List is to be tested. |
162 |
* @return <code>true</code> if the specified element is present; |
163 |
* <code>false</code> otherwise. |
164 |
*/ |
165 |
public boolean contains(Object elem) { |
166 |
return indexOf(elem) >= 0; |
167 |
} |
168 |
|
169 |
/** |
170 |
* Searches for the first occurence of the given argument, testing |
171 |
* for equality using the <tt>equals</tt> method. |
172 |
* |
173 |
* @param elem an object. |
174 |
* @return the index of the first occurrence of the argument in this |
175 |
* list; returns <tt>-1</tt> if the object is not found. |
176 |
* @see Object#equals(Object) |
177 |
*/ |
178 |
public int indexOf(Object elem) { |
179 |
if (elem == null) { |
180 |
int i = 0; |
181 |
while (i < gapStart) { |
182 |
if (elementData[i] == null) { |
183 |
return i; |
184 |
} |
185 |
i++; |
186 |
} |
187 |
i += gapLength; |
188 |
int elementDataLength = elementData.length; |
189 |
while (i < elementDataLength) { |
190 |
if (elementData[i] == null) { |
191 |
return i; |
192 |
} |
193 |
i++; |
194 |
} |
195 |
|
196 |
} else { // elem not null |
197 |
int i = 0; |
198 |
while (i < gapStart) { |
199 |
if (elem.equals(elementData[i])) { |
200 |
return i; |
201 |
} |
202 |
i++; |
203 |
} |
204 |
i += gapLength; |
205 |
int elementDataLength = elementData.length; |
206 |
while (i < elementDataLength) { |
207 |
if (elem.equals(elementData[i])) { |
208 |
return i; |
209 |
} |
210 |
i++; |
211 |
} |
212 |
} |
213 |
|
214 |
return -1; |
215 |
} |
216 |
|
217 |
/** |
218 |
* Returns the index of the last occurrence of the specified object in |
219 |
* this list. |
220 |
* |
221 |
* @param elem the desired element. |
222 |
* @return the index of the last occurrence of the specified object in |
223 |
* this list; returns -1 if the object is not found. |
224 |
*/ |
225 |
public int lastIndexOf(Object elem) { |
226 |
if (elem == null) { |
227 |
int i = elementData.length - 1; |
228 |
int gapEnd = gapStart + gapLength; |
229 |
while (i >= gapEnd) { |
230 |
if (elementData[i] == null) { |
231 |
return i; |
232 |
} |
233 |
i--; |
234 |
} |
235 |
i -= gapLength; |
236 |
while (i >= 0) { |
237 |
if (elementData[i] == null) { |
238 |
return i; |
239 |
} |
240 |
i--; |
241 |
} |
242 |
|
243 |
} else { // elem not null |
244 |
int i = elementData.length - 1; |
245 |
int gapEnd = gapStart + gapLength; |
246 |
while (i >= gapEnd) { |
247 |
if (elem.equals(elementData[i])) { |
248 |
return i; |
249 |
} |
250 |
i--; |
251 |
} |
252 |
i -= gapLength; |
253 |
while (i >= 0) { |
254 |
if (elem.equals(elementData[i])) { |
255 |
return i; |
256 |
} |
257 |
i--; |
258 |
} |
259 |
} |
260 |
|
261 |
return -1; |
262 |
} |
263 |
|
264 |
/** |
265 |
* Returns a shallow copy of this <tt>GapList</tt> instance. (The |
266 |
* elements themselves are not copied.) |
267 |
* |
268 |
* @return a clone of this <tt>GapList</tt> instance. |
269 |
*/ |
270 |
public Object clone() { |
271 |
try { |
272 |
GapList clonedList = (GapList)super.clone(); |
273 |
int size = size(); |
274 |
Object[] clonedElementData = new Object[size]; |
275 |
copyAllData(clonedElementData); |
276 |
clonedList.elementData = clonedElementData; |
277 |
// Will retain gapStart - would have to call moved*() otherwise |
278 |
clonedList.gapStart = size; |
279 |
clonedList.resetModCount(); |
280 |
return clonedList; |
281 |
|
282 |
} catch (CloneNotSupportedException e) { |
283 |
// this shouldn't happen, since we are Cloneable |
284 |
throw new InternalError(); |
285 |
} |
286 |
} |
287 |
|
288 |
public void copyItems(int srcStartIndex, int srcEndIndex, |
289 |
Object[] dest, int destIndex) { |
290 |
|
291 |
if (srcStartIndex < 0 || srcEndIndex < srcStartIndex || srcEndIndex > size()) { |
292 |
throw new IndexOutOfBoundsException("srcStartIndex=" + srcStartIndex // NOI18N |
293 |
+ ", srcEndIndex=" + srcEndIndex + ", size()=" + size()); // NOI18N |
294 |
} |
295 |
|
296 |
if (srcEndIndex < gapStart) { // fully below gap |
297 |
System.arraycopy(elementData, srcStartIndex, |
298 |
dest, destIndex, srcEndIndex - srcStartIndex); |
299 |
|
300 |
} else { // above gap or spans the gap |
301 |
if (srcStartIndex >= gapStart) { // fully above gap |
302 |
System.arraycopy(elementData, srcStartIndex + gapLength, dest, destIndex, |
303 |
srcEndIndex - srcStartIndex); |
304 |
|
305 |
} else { // spans gap |
306 |
int beforeGap = gapStart - srcStartIndex; |
307 |
System.arraycopy(elementData, srcStartIndex, dest, destIndex, beforeGap); |
308 |
System.arraycopy(elementData, gapStart + gapLength, dest, destIndex + beforeGap, |
309 |
srcEndIndex - srcStartIndex - beforeGap); |
310 |
} |
311 |
} |
312 |
} |
313 |
|
314 |
/** |
315 |
* Returns an array containing all of the elements in this list |
316 |
* in the correct order. |
317 |
* |
318 |
* @return an array containing all of the elements in this list |
319 |
* in the correct order. |
320 |
*/ |
321 |
public Object[] toArray() { |
322 |
int size = size(); |
323 |
Object[] result = new Object[size]; |
324 |
copyAllData(result); |
325 |
return result; |
326 |
} |
327 |
|
328 |
/** |
329 |
* Returns an array containing all of the elements in this list in the |
330 |
* correct order; the runtime type of the returned array is that of the |
331 |
* specified array. If the list fits in the specified array, it is |
332 |
* returned therein. Otherwise, a new array is allocated with the runtime |
333 |
* type of the specified array and the size of this list.<p> |
334 |
* |
335 |
* If the list fits in the specified array with room to spare (i.e., the |
336 |
* array has more elements than the list), the element in the array |
337 |
* immediately following the end of the collection is set to |
338 |
* <tt>null</tt>. This is useful in determining the length of the list |
339 |
* <i>only</i> if the caller knows that the list does not contain any |
340 |
* <tt>null</tt> elements. |
341 |
* |
342 |
* @param a the array into which the elements of the list are to |
343 |
* be stored, if it is big enough; otherwise, a new array of the |
344 |
* same runtime type is allocated for this purpose. |
345 |
* @return an array containing the elements of the list. |
346 |
* @throws ArrayStoreException if the runtime type of a is not a supertype |
347 |
* of the runtime type of every element in this list. |
348 |
*/ |
349 |
public Object[] toArray(Object a[]) { |
350 |
int size = size(); |
351 |
if (a.length < size) { |
352 |
a = (Object[])java.lang.reflect.Array.newInstance( |
353 |
a.getClass().getComponentType(), size); |
354 |
} |
355 |
copyAllData(a); |
356 |
if (a.length > size) |
357 |
a[size] = null; |
358 |
|
359 |
return a; |
360 |
} |
361 |
|
362 |
// Positional Access Operations |
363 |
|
364 |
/** |
365 |
* Returns the element at the specified position in this list. |
366 |
* |
367 |
* @param index index of element to return. |
368 |
* @return the element at the specified position in this list. |
369 |
* @throws IndexOutOfBoundsException if index is out of range <tt>(index |
370 |
* < 0 || index >= size())</tt>. |
371 |
*/ |
372 |
public Object get(int index) { |
373 |
// rangeCheck(index) not necessary - would fail with AIOOBE anyway |
374 |
return elementData[(index < gapStart) ? index : (index + gapLength)]; |
375 |
} |
376 |
|
377 |
/** |
378 |
* Replaces the element at the specified position in this list with |
379 |
* the specified element. |
380 |
* |
381 |
* @param index index of element to replace. |
382 |
* @param element element to be stored at the specified position. |
383 |
* @return the element previously at the specified position. |
384 |
* @throws IndexOutOfBoundsException if index out of range |
385 |
* <tt>(index < 0 || index >= size())</tt>. |
386 |
*/ |
387 |
public Object set(int index, Object element) { |
388 |
// rangeCheck(index) not necessary - would fail with AIOOBE anyway |
389 |
if (index >= gapStart) { |
390 |
index += gapLength; |
391 |
} |
392 |
Object oldValue = elementData[index]; |
393 |
elementData[index] = element; |
394 |
return oldValue; |
395 |
} |
396 |
|
397 |
/** |
398 |
* Appends the specified element to the end of this list. |
399 |
* |
400 |
* @param o element to be appended to this list. |
401 |
* @return <tt>true</tt> (as per the general contract of Collection.add). |
402 |
*/ |
403 |
public boolean add(Object o) { |
404 |
add(size(), o); |
405 |
return true; |
406 |
} |
407 |
|
408 |
/** |
409 |
* Inserts the specified element at the specified position in this |
410 |
* list. Shifts the element currently at that position (if any) and |
411 |
* any subsequent elements to the right (adds one to their indices). |
412 |
* |
413 |
* @param index index at which the specified element is to be inserted. |
414 |
* @param element element to be inserted. |
415 |
* @throws IndexOutOfBoundsException if index is out of range |
416 |
* <tt>(index < 0 || index > size())</tt>. |
417 |
*/ |
418 |
public void add(int index, Object element) { |
419 |
int size = size(); |
420 |
if (index > size || index < 0) { |
421 |
throw new IndexOutOfBoundsException( |
422 |
"Index: " + index + ", Size: " + size); // NOI18N |
423 |
} |
424 |
|
425 |
ensureCapacity(size + 1); // Increments modCount!! |
426 |
moveGap(index); |
427 |
|
428 |
elementData[gapStart++] = element; |
429 |
gapLength--; |
430 |
} |
431 |
|
432 |
/** |
433 |
* Appends all of the elements in the specified Collection to the end of |
434 |
* this list, in the order that they are returned by the |
435 |
* specified Collection's Iterator. The behavior of this operation is |
436 |
* undefined if the specified Collection is modified while the operation |
437 |
* is in progress. (This implies that the behavior of this call is |
438 |
* undefined if the specified Collection is this list, and this |
439 |
* list is nonempty.) |
440 |
* |
441 |
* @param c the elements to be inserted into this list. |
442 |
* @return <tt>true</tt> if this list changed as a result of the call. |
443 |
* @throws NullPointerException if the specified collection is null. |
444 |
*/ |
445 |
public boolean addAll(Collection c) { |
446 |
return addAll(size(), c); |
447 |
} |
448 |
|
449 |
/** |
450 |
* Inserts all of the elements in the specified Collection into this |
451 |
* list, starting at the specified position. Shifts the element |
452 |
* currently at that position (if any) and any subsequent elements to |
453 |
* the right (increases their indices). The new elements will appear |
454 |
* in the list in the order that they are returned by the |
455 |
* specified Collection's iterator. |
456 |
* |
457 |
* @param index index at which to insert first element |
458 |
* from the specified collection. |
459 |
* @param c elements to be inserted into this list. |
460 |
* @return <tt>true</tt> if this list changed as a result of the call. |
461 |
* @throws IndexOutOfBoundsException if index out of range <tt>(index |
462 |
* < 0 || index > size())</tt>. |
463 |
* @throws NullPointerException if the specified Collection is null. |
464 |
*/ |
465 |
public boolean addAll(int index, Collection c) { |
466 |
return addArray(index, c.toArray()); |
467 |
} |
468 |
|
469 |
/* |
470 |
* Inserts all elements from the given array into this list, starting |
471 |
* at the given index. |
472 |
* |
473 |
* @param index index at which to insert first element from the array. |
474 |
* @param elements array of elements to insert. |
475 |
*/ |
476 |
public boolean addArray(int index, Object[] elements) { |
477 |
return addArray(index, elements, 0, elements.length); |
478 |
} |
479 |
|
480 |
/** |
481 |
* Inserts elements from the given array into this list, starting |
482 |
* at the given index. |
483 |
* |
484 |
* @param index index at which to insert first element. |
485 |
* @param elements array of elements from which to insert elements. |
486 |
* @param off offset in the elements pointing to first element to copy. |
487 |
* @param len number of elements to copy from the elements array. |
488 |
*/ |
489 |
public boolean addArray(int index, Object[] elements, int off, int len) { |
490 |
int size = size(); |
491 |
if (index > size || index < 0) { |
492 |
throw new IndexOutOfBoundsException( |
493 |
"Index: " + index + ", Size: " + size); // NOI18N |
494 |
} |
495 |
|
496 |
ensureCapacity(size + len); // Increments modCount |
497 |
|
498 |
moveGap(index); |
499 |
System.arraycopy(elements, off, elementData, gapStart, len); |
500 |
gapStart += len; |
501 |
gapLength -= len; |
502 |
|
503 |
return (len != 0); |
504 |
} |
505 |
|
506 |
|
507 |
|
508 |
/** |
509 |
* Removes all of the elements from this list. The list will |
510 |
* be empty after this call returns. |
511 |
*/ |
512 |
public void clear() { |
513 |
removeRange(0, size()); |
514 |
} |
515 |
|
516 |
/** |
517 |
* Removes the element at the specified position in this list. |
518 |
* Shifts any subsequent elements to the left (subtracts one from their |
519 |
* indices). |
520 |
* |
521 |
* @param index the index of the element to removed. |
522 |
* @return the element that was removed from the list. |
523 |
* @throws IndexOutOfBoundsException if index out of range <tt>(index |
524 |
* < 0 || index >= size())</tt>. |
525 |
*/ |
526 |
public Object remove(int index) { |
527 |
int size = size(); |
528 |
if (index >= size || index < 0) { |
529 |
throw new IndexOutOfBoundsException( |
530 |
"remove(): Index: " + index + ", Size: " + size); // NOI18N |
531 |
} |
532 |
|
533 |
modCount++; |
534 |
moveGap(index + 1); // if previous were adds() - this should be no-op |
535 |
Object oldValue = elementData[index]; |
536 |
removeUpdate(index, elementData, index, index + 1); |
537 |
elementData[index] = null; |
538 |
gapStart--; |
539 |
gapLength++; |
540 |
|
541 |
return oldValue; |
542 |
} |
543 |
|
544 |
/** |
545 |
* Removes elements at the given index. |
546 |
* |
547 |
* @param index index of the first element to be removed. |
548 |
* @param count number of elements to remove. |
549 |
*/ |
550 |
public void remove(int index, int count) { |
551 |
int toIndex = index + count; |
552 |
if (index < 0 || toIndex < index || toIndex > size()) { |
553 |
throw new IndexOutOfBoundsException("index=" + index // NOI18N |
554 |
+ ", count=" + count + ", size()=" + size()); // NOI18N |
555 |
} |
556 |
removeRange(index, toIndex); |
557 |
} |
558 |
|
559 |
/** |
560 |
* Removes from this List all of the elements whose index is between |
561 |
* fromIndex, inclusive and toIndex, exclusive. Shifts any succeeding |
562 |
* elements to the left (reduces their index). |
563 |
* This call shortens the list by <tt>(toIndex - fromIndex)</tt> elements. |
564 |
* (If <tt>toIndex==fromIndex</tt>, this operation has no effect.) |
565 |
* |
566 |
* @param fromIndex index of first element to be removed. |
567 |
* @param toIndex index after last element to be removed. |
568 |
*/ |
569 |
protected void removeRange(int fromIndex, int toIndex) { |
570 |
modCount++; |
571 |
if (fromIndex == toIndex) { |
572 |
return; |
573 |
} |
574 |
|
575 |
int removeCount = toIndex - fromIndex; |
576 |
if (fromIndex >= gapStart) { // completely over gap |
577 |
// Move gap to the start of the removed area |
578 |
// (this should be the minimum necessary count of elements moved) |
579 |
moveGap(fromIndex); |
580 |
|
581 |
// Allow GC of removed items |
582 |
fromIndex += gapLength; // begining of abandoned area |
583 |
toIndex += gapLength; |
584 |
removeUpdate(fromIndex - gapLength, elementData, fromIndex, toIndex); |
585 |
while (fromIndex < toIndex) { |
586 |
elementData[fromIndex] = null; |
587 |
fromIndex++; |
588 |
} |
589 |
|
590 |
} else { // completely below gap or spans the gap |
591 |
if (toIndex <= gapStart) { |
592 |
// Move gap to the end of the removed area |
593 |
// (this should be the minimum necessary count of elements moved) |
594 |
moveGap(toIndex); |
595 |
gapStart = fromIndex; |
596 |
// Call removeUpdate() for items that will be physically removed soon |
597 |
removeUpdate(fromIndex, elementData, fromIndex, toIndex); |
598 |
|
599 |
} else { // spans gap: gapStart > fromIndex but gapStart - fromIndex < removeCount |
600 |
removeUpdate(fromIndex, elementData, fromIndex, gapStart); |
601 |
// Allow GC of removed items |
602 |
for (int clearIndex = fromIndex; clearIndex < gapStart; clearIndex++) { |
603 |
elementData[clearIndex] = null; |
604 |
} |
605 |
|
606 |
fromIndex = gapStart + gapLength; // part above the gap |
607 |
gapStart = toIndex - removeCount; // original value of fromIndex |
608 |
toIndex += gapLength; |
609 |
removeUpdate(gapStart, elementData, fromIndex, toIndex); |
610 |
} |
611 |
|
612 |
// Allow GC of removed items |
613 |
while (fromIndex < toIndex) { |
614 |
elementData[fromIndex++] = null; |
615 |
} |
616 |
|
617 |
} |
618 |
|
619 |
gapLength += removeCount; |
620 |
} |
621 |
|
622 |
/** |
623 |
* Called prior physical removing of the data from the list. |
624 |
* <br> |
625 |
* The implementation can possibly update the elements in the removed area. |
626 |
* <br> |
627 |
* After this method finishes the whole removed area will be |
628 |
* <code>null</code>-ed. |
629 |
* |
630 |
* @param index index in the list of the first item being removed. |
631 |
* @param data array of objects from which the data are being removed. |
632 |
* The next two parameters define the indexes at which the elements |
633 |
* can be updated. |
634 |
* <br> |
635 |
* Absolutely no changes should be done outside of |
636 |
* <code><startOff, endOff)</code> area. |
637 |
* @param startOff offset in the data array of the first element that |
638 |
* will be removed. |
639 |
* @param endOff offset in the data array following the last item that will |
640 |
* be removed. |
641 |
*/ |
642 |
protected void removeUpdate(int index, Object[] data, int startOff, int endOff) { |
643 |
} |
644 |
|
645 |
/* |
646 |
protected void movedAboveGapUpdate(Object[] array, int index, int count) { |
647 |
} |
648 |
|
649 |
protected void movedBelowGapUpdate(Object[] array, int index, int count) { |
650 |
} |
651 |
*/ |
652 |
|
653 |
private void moveGap(int index) { |
654 |
if (index == gapStart) { |
655 |
return; // do nothing |
656 |
} |
657 |
|
658 |
if (index < gapStart) { // move gap down |
659 |
int moveSize = gapStart - index; |
660 |
System.arraycopy(elementData, index, elementData, |
661 |
gapStart + gapLength - moveSize, moveSize); |
662 |
clearEmpty(index, Math.min(moveSize, gapLength)); |
663 |
gapStart = index; |
664 |
// movedAboveGapUpdate(elementData, gapStart + gapLength, moveSize); |
665 |
|
666 |
} else { // above gap |
667 |
int gapEnd = gapStart + gapLength; |
668 |
int moveSize = index - gapStart; |
669 |
System.arraycopy(elementData, gapEnd, elementData, gapStart, moveSize); |
670 |
if (index < gapEnd) { |
671 |
clearEmpty(gapEnd, moveSize); |
672 |
} else { |
673 |
clearEmpty(index, gapLength); |
674 |
} |
675 |
// movedBelowGapUpdate(elementData, gapStart, moveSize); |
676 |
gapStart += moveSize; |
677 |
} |
678 |
} |
679 |
|
680 |
private void copyAllData(Object[] toArray) { |
681 |
if (gapLength != 0) { |
682 |
int gapEnd = gapStart + gapLength; |
683 |
System.arraycopy(elementData, 0, toArray, 0, gapStart); |
684 |
System.arraycopy(elementData, gapEnd, toArray, gapStart, |
685 |
elementData.length - gapEnd); |
686 |
} else { // no gap => single copy of everything |
687 |
System.arraycopy(elementData, 0, toArray, 0, elementData.length); |
688 |
} |
689 |
} |
690 |
|
691 |
private void clearEmpty(int index, int length) { |
692 |
while (--length >= 0) { |
693 |
elementData[index++] = null; // allow GC |
694 |
} |
695 |
} |
696 |
|
697 |
private void resetModCount() { |
698 |
modCount = 0; |
699 |
} |
700 |
|
701 |
/** |
702 |
* Save the state of the <tt>GapList</tt> instance to a stream (that |
703 |
* is, serialize it). |
704 |
* |
705 |
* @serialData The length of the array backing the <tt>GapList</tt> |
706 |
* instance is emitted (int), followed by all of its elements |
707 |
* (each an <tt>Object</tt>) in the proper order. |
708 |
*/ |
709 |
private void writeObject(java.io.ObjectOutputStream s) |
710 |
throws java.io.IOException{ |
711 |
// Write out element count, and any hidden stuff |
712 |
s.defaultWriteObject(); |
713 |
|
714 |
// Write out array length |
715 |
s.writeInt(elementData.length); |
716 |
|
717 |
// Write out all elements in the proper order. |
718 |
int i = 0; |
719 |
while (i < gapStart) { |
720 |
s.writeObject(elementData[i]); |
721 |
i++; |
722 |
} |
723 |
i += gapLength; |
724 |
int elementDataLength = elementData.length; |
725 |
while (i < elementDataLength) { |
726 |
s.writeObject(elementData[i]); |
727 |
i++; |
728 |
} |
729 |
} |
730 |
|
731 |
/** |
732 |
* Reconstitute the <tt>GapList</tt> instance from a stream (that is, |
733 |
* deserialize it). |
734 |
*/ |
735 |
private void readObject(java.io.ObjectInputStream s) |
736 |
throws java.io.IOException, ClassNotFoundException { |
737 |
// Read in size, and any hidden stuff |
738 |
s.defaultReadObject(); |
739 |
|
740 |
// Read in array length and allocate array |
741 |
int arrayLength = s.readInt(); |
742 |
elementData = new Object[arrayLength]; |
743 |
|
744 |
// Read in all elements in the proper order. |
745 |
int i = 0; |
746 |
while (i < gapStart) { |
747 |
elementData[i] = s.readObject(); |
748 |
i++; |
749 |
} |
750 |
i += gapLength; |
751 |
int elementDataLength = elementData.length; |
752 |
while (i < elementDataLength) { |
753 |
elementData[i] = s.readObject(); |
754 |
i++; |
755 |
} |
756 |
} |
757 |
|
758 |
/** |
759 |
* Internal consistency check. |
760 |
*/ |
761 |
void consistencyCheck() { |
762 |
if (gapStart < 0 || gapLength < 0 |
763 |
|| gapStart + gapLength > elementData.length |
764 |
) { |
765 |
consistencyError("Inconsistent gap"); // NOI18N |
766 |
} |
767 |
|
768 |
// Check whether the whole gap contains only nulls |
769 |
for (int i = gapStart + gapLength - 1; i >= gapStart; i--) { |
770 |
if (elementData[i] != null) { |
771 |
consistencyError("Non-null value at raw-index i"); // NOI18N |
772 |
} |
773 |
} |
774 |
} |
775 |
|
776 |
private void consistencyError(String s) { |
777 |
throw new IllegalStateException(s + ": " + toStringInternals()); // NOI18N |
778 |
} |
779 |
|
780 |
String toStringInternals() { |
781 |
return "elementData.length=" + elementData.length // NOI18N |
782 |
+ ", gapStart=" + gapStart + ", gapLength=" + gapLength; // NOI18N |
783 |
} |
784 |
|
785 |
} |