svn-gvsig-desktop / trunk / org.gvsig.desktop / org.gvsig.desktop.compat.cdc / org.gvsig.fmap.dal / org.gvsig.fmap.dal.impl / src / main / java / org / gvsig / fmap / dal / feature / impl / indexes / memorybasictypes / ArrayListOfLong.java @ 44158
History | View | Annotate | Download (41.5 KB)
1 |
package org.gvsig.fmap.dal.feature.impl.indexes.memorybasictypes; |
---|---|
2 |
|
3 |
import java.util.AbstractList; |
4 |
import java.util.Arrays; |
5 |
import java.util.BitSet; |
6 |
import java.util.Collection; |
7 |
import java.util.Collections; |
8 |
import java.util.Comparator; |
9 |
import java.util.ConcurrentModificationException; |
10 |
import java.util.Iterator; |
11 |
import java.util.List; |
12 |
import java.util.ListIterator; |
13 |
import java.util.NoSuchElementException; |
14 |
import java.util.Objects; |
15 |
import java.util.RandomAccess; |
16 |
import java.util.Spliterator; |
17 |
import java.util.function.Consumer; |
18 |
import java.util.function.Predicate; |
19 |
import java.util.function.UnaryOperator; |
20 |
|
21 |
/**
|
22 |
*
|
23 |
* @author jjdelcerro
|
24 |
*/
|
25 |
public class ArrayListOfLong extends AbstractList<Long> |
26 |
implements ListOfLong, RandomAccess, Cloneable { |
27 |
|
28 |
private static final long serialVersionUID = 8683452581122892189L; |
29 |
|
30 |
/**
|
31 |
* Default initial capacity.
|
32 |
*/
|
33 |
private static final int DEFAULT_CAPACITY = 10; |
34 |
|
35 |
/**
|
36 |
* Shared empty array instance used for empty instances.
|
37 |
*/
|
38 |
private static final long[] EMPTY_ELEMENTDATA = {}; |
39 |
|
40 |
/**
|
41 |
* Shared empty array instance used for default sized empty instances. We
|
42 |
* distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
|
43 |
* first element is added.
|
44 |
*/
|
45 |
private static final long[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; |
46 |
|
47 |
/**
|
48 |
* The array buffer into which the elements of the ArrayList are stored.
|
49 |
* The capacity of the ArrayList is the length of this array buffer. Any
|
50 |
* empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
|
51 |
* will be expanded to DEFAULT_CAPACITY when the first element is added.
|
52 |
*/
|
53 |
transient long[] elementData; // non-private to simplify nested class access |
54 |
|
55 |
/**
|
56 |
* The size of the ArrayList (the number of elements it contains).
|
57 |
*
|
58 |
* @serial
|
59 |
*/
|
60 |
private int size; |
61 |
|
62 |
/**
|
63 |
* Constructs an empty list with the specified initial capacity.
|
64 |
*
|
65 |
* @param initialCapacity the initial capacity of the list
|
66 |
* @throws IllegalArgumentException if the specified initial capacity
|
67 |
* is negative
|
68 |
*/
|
69 |
public ArrayListOfLong(int initialCapacity) { |
70 |
if (initialCapacity > 0) { |
71 |
this.elementData = new long[initialCapacity]; |
72 |
} else if (initialCapacity == 0) { |
73 |
this.elementData = EMPTY_ELEMENTDATA;
|
74 |
} else {
|
75 |
throw new IllegalArgumentException("Illegal Capacity: "+ |
76 |
initialCapacity); |
77 |
} |
78 |
} |
79 |
|
80 |
/**
|
81 |
* Constructs an empty list with an initial capacity of ten.
|
82 |
*/
|
83 |
public ArrayListOfLong() {
|
84 |
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
|
85 |
} |
86 |
|
87 |
/**
|
88 |
* Constructs a list containing the elements of the specified
|
89 |
* collection, in the order they are returned by the collection's
|
90 |
* iterator.
|
91 |
*
|
92 |
* @param c the collection whose elements are to be placed into this list
|
93 |
* @throws NullPointerException if the specified collection is null
|
94 |
*/
|
95 |
public ArrayListOfLong(Collection<? extends Long> c) { |
96 |
if ((size = c.size()) != 0) { |
97 |
this.grow(c.size());
|
98 |
int i=0; |
99 |
for (Long e : c) { |
100 |
this.elementData[i++] = e;
|
101 |
} |
102 |
} else {
|
103 |
// replace with empty array.
|
104 |
this.elementData = EMPTY_ELEMENTDATA;
|
105 |
} |
106 |
} |
107 |
|
108 |
/**
|
109 |
* Trims the capacity of this <tt>ArrayList</tt> instance to be the
|
110 |
* list's current size. An application can use this operation to minimize
|
111 |
* the storage of an <tt>ArrayList</tt> instance.
|
112 |
*/
|
113 |
public void trimToSize() { |
114 |
modCount++; |
115 |
if (size < elementData.length) {
|
116 |
elementData = (size == 0)
|
117 |
? EMPTY_ELEMENTDATA |
118 |
: Arrays.copyOf(elementData, size);
|
119 |
} |
120 |
} |
121 |
|
122 |
/**
|
123 |
* Increases the capacity of this <tt>ArrayList</tt> instance, if
|
124 |
* necessary, to ensure that it can hold at least the number of elements
|
125 |
* specified by the minimum capacity argument.
|
126 |
*
|
127 |
* @param minCapacity the desired minimum capacity
|
128 |
*/
|
129 |
public void ensureCapacity(int minCapacity) { |
130 |
int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
|
131 |
// any size if not default element table
|
132 |
? 0
|
133 |
// larger than default for default empty table. It's already
|
134 |
// supposed to be at default size.
|
135 |
: DEFAULT_CAPACITY; |
136 |
|
137 |
if (minCapacity > minExpand) {
|
138 |
ensureExplicitCapacity(minCapacity); |
139 |
} |
140 |
} |
141 |
|
142 |
private static int calculateCapacity(long[] elementData, int minCapacity) { |
143 |
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
|
144 |
return Math.max(DEFAULT_CAPACITY, minCapacity); |
145 |
} |
146 |
return minCapacity;
|
147 |
} |
148 |
|
149 |
private void ensureCapacityInternal(int minCapacity) { |
150 |
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); |
151 |
} |
152 |
|
153 |
private void ensureExplicitCapacity(int minCapacity) { |
154 |
modCount++; |
155 |
|
156 |
// overflow-conscious code
|
157 |
if (minCapacity - elementData.length > 0) |
158 |
grow(minCapacity); |
159 |
} |
160 |
|
161 |
/**
|
162 |
* The maximum size of array to allocate.
|
163 |
* Some VMs reserve some header words in an array.
|
164 |
* Attempts to allocate larger arrays may result in
|
165 |
* OutOfMemoryError: Requested array size exceeds VM limit
|
166 |
*/
|
167 |
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; |
168 |
|
169 |
/**
|
170 |
* Increases the capacity to ensure that it can hold at least the
|
171 |
* number of elements specified by the minimum capacity argument.
|
172 |
*
|
173 |
* @param minCapacity the desired minimum capacity
|
174 |
*/
|
175 |
private void grow(int minCapacity) { |
176 |
// overflow-conscious code
|
177 |
int oldCapacity = elementData.length;
|
178 |
int newCapacity = oldCapacity + (oldCapacity >> 1); |
179 |
if (newCapacity - minCapacity < 0) |
180 |
newCapacity = minCapacity; |
181 |
if (newCapacity - MAX_ARRAY_SIZE > 0) |
182 |
newCapacity = hugeCapacity(minCapacity); |
183 |
// minCapacity is usually close to size, so this is a win:
|
184 |
elementData = Arrays.copyOf(elementData, newCapacity);
|
185 |
} |
186 |
|
187 |
private static int hugeCapacity(int minCapacity) { |
188 |
if (minCapacity < 0) // overflow |
189 |
throw new OutOfMemoryError(); |
190 |
return (minCapacity > MAX_ARRAY_SIZE) ?
|
191 |
Integer.MAX_VALUE :
|
192 |
MAX_ARRAY_SIZE; |
193 |
} |
194 |
|
195 |
/**
|
196 |
* Returns the number of elements in this list.
|
197 |
*
|
198 |
* @return the number of elements in this list
|
199 |
*/
|
200 |
public int size() { |
201 |
return size;
|
202 |
} |
203 |
|
204 |
/**
|
205 |
* Returns <tt>true</tt> if this list contains no elements.
|
206 |
*
|
207 |
* @return <tt>true</tt> if this list contains no elements
|
208 |
*/
|
209 |
public boolean isEmpty() { |
210 |
return size == 0; |
211 |
} |
212 |
|
213 |
/**
|
214 |
* Returns <tt>true</tt> if this list contains the specified element.
|
215 |
* More formally, returns <tt>true</tt> if and only if this list contains
|
216 |
* at least one element <tt>e</tt> such that
|
217 |
* <tt>(o==null ? e==null : o.equals(e))</tt>.
|
218 |
*
|
219 |
* @param o element whose presence in this list is to be tested
|
220 |
* @return <tt>true</tt> if this list contains the specified element
|
221 |
*/
|
222 |
public boolean contains(Object o) { |
223 |
return indexOf(o) >= 0; |
224 |
} |
225 |
|
226 |
/**
|
227 |
* Returns the index of the first occurrence of the specified element
|
228 |
* in this list, or -1 if this list does not contain the element.
|
229 |
* More formally, returns the lowest index <tt>i</tt> such that
|
230 |
* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>,
|
231 |
* or -1 if there is no such index.
|
232 |
*/
|
233 |
public int indexOf(Object o) { |
234 |
if (o == null) { |
235 |
return -1; |
236 |
} else {
|
237 |
for (int i = 0; i < size; i++) |
238 |
if (o.equals(elementData[i]))
|
239 |
return i;
|
240 |
} |
241 |
return -1; |
242 |
} |
243 |
|
244 |
/**
|
245 |
* Returns the index of the last occurrence of the specified element
|
246 |
* in this list, or -1 if this list does not contain the element.
|
247 |
* More formally, returns the highest index <tt>i</tt> such that
|
248 |
* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>,
|
249 |
* or -1 if there is no such index.
|
250 |
*/
|
251 |
public int lastIndexOf(Object o) { |
252 |
if (o == null) { |
253 |
return -1; |
254 |
} else {
|
255 |
for (int i = size-1; i >= 0; i--) |
256 |
if (o.equals(elementData[i]))
|
257 |
return i;
|
258 |
} |
259 |
return -1; |
260 |
} |
261 |
|
262 |
/**
|
263 |
* Returns a shallow copy of this <tt>ArrayList</tt> instance. (The
|
264 |
* elements themselves are not copied.)
|
265 |
*
|
266 |
* @return a clone of this <tt>ArrayList</tt> instance
|
267 |
*/
|
268 |
public Object clone() { |
269 |
try {
|
270 |
ArrayListOfLong v = (ArrayListOfLong) super.clone();
|
271 |
v.elementData = Arrays.copyOf(elementData, size);
|
272 |
v.modCount = 0;
|
273 |
return v;
|
274 |
} catch (CloneNotSupportedException e) { |
275 |
// this shouldn't happen, since we are Cloneable
|
276 |
throw new InternalError(e); |
277 |
} |
278 |
} |
279 |
|
280 |
public Long[] toArray() { |
281 |
return toArray(null); |
282 |
} |
283 |
|
284 |
public Long[] toArray(Long[] a) { |
285 |
if (a==null || a.length < size) { |
286 |
a = new Long[size]; |
287 |
} |
288 |
for (int i = 0; i < size; i++) { |
289 |
a[i] = this.elementData[i];
|
290 |
} |
291 |
return a;
|
292 |
} |
293 |
|
294 |
// Positional Access Operations
|
295 |
|
296 |
@SuppressWarnings("unchecked") |
297 |
long elementData(int index) { |
298 |
return elementData[index];
|
299 |
} |
300 |
|
301 |
public Long get(int index) { |
302 |
return this.getLong(index); |
303 |
} |
304 |
|
305 |
public long getLong(int index) { |
306 |
rangeCheck(index); |
307 |
|
308 |
return elementData(index);
|
309 |
} |
310 |
|
311 |
/**
|
312 |
* Replaces the element at the specified position in this list with
|
313 |
* the specified element.
|
314 |
*
|
315 |
* @param index index of the element to replace
|
316 |
* @param element element to be stored at the specified position
|
317 |
* @return the element previously at the specified position
|
318 |
* @throws IndexOutOfBoundsException {@inheritDoc}
|
319 |
*/
|
320 |
public Long set(int index, Long element) { |
321 |
rangeCheck(index); |
322 |
|
323 |
Long oldValue = elementData(index);
|
324 |
elementData[index] = element; |
325 |
return oldValue;
|
326 |
} |
327 |
|
328 |
public boolean add(Long e) { |
329 |
return this.add((long)e); |
330 |
} |
331 |
|
332 |
public boolean add(long e) { |
333 |
ensureCapacityInternal(size + 1); // Increments modCount!! |
334 |
elementData[size++] = e; |
335 |
return true; |
336 |
} |
337 |
|
338 |
public void add(int index, Long element) { |
339 |
this.add(index, (long)element); |
340 |
} |
341 |
|
342 |
public void add(int index, long element) { |
343 |
rangeCheckForAdd(index); |
344 |
|
345 |
ensureCapacityInternal(size + 1); // Increments modCount!! |
346 |
System.arraycopy(elementData, index, elementData, index + 1, |
347 |
size - index); |
348 |
elementData[index] = element; |
349 |
size++; |
350 |
} |
351 |
|
352 |
public Long remove(int index) { |
353 |
rangeCheck(index); |
354 |
|
355 |
modCount++; |
356 |
Long oldValue = elementData(index);
|
357 |
|
358 |
int numMoved = size - index - 1; |
359 |
if (numMoved > 0) |
360 |
System.arraycopy(elementData, index+1, elementData, index, |
361 |
numMoved); |
362 |
return oldValue;
|
363 |
} |
364 |
|
365 |
public boolean remove(Object o) { |
366 |
if (o == null) { |
367 |
return true; |
368 |
} |
369 |
return this.removeLong((long)o); |
370 |
} |
371 |
|
372 |
public boolean removeLong(long o) { |
373 |
for (int index = 0; index < size; index++) |
374 |
if (o == elementData[index]) {
|
375 |
this.remove(index);
|
376 |
return true; |
377 |
} |
378 |
return false; |
379 |
} |
380 |
|
381 |
/*
|
382 |
* Private remove method that skips bounds checking and does not
|
383 |
* return the value removed.
|
384 |
*/
|
385 |
private void fastRemove(int index) { |
386 |
modCount++; |
387 |
int numMoved = size - index - 1; |
388 |
if (numMoved > 0) |
389 |
System.arraycopy(elementData, index+1, elementData, index, |
390 |
numMoved); |
391 |
} |
392 |
|
393 |
/**
|
394 |
* Removes all of the elements from this list. The list will
|
395 |
* be empty after this call returns.
|
396 |
*/
|
397 |
public void clear() { |
398 |
modCount++; |
399 |
size = 0;
|
400 |
} |
401 |
|
402 |
/**
|
403 |
* Appends all of the elements in the specified collection to the end of
|
404 |
* this list, in the order that they are returned by the
|
405 |
* specified collection's Iterator. The behavior of this operation is
|
406 |
* undefined if the specified collection is modified while the operation
|
407 |
* is in progress. (This implies that the behavior of this call is
|
408 |
* undefined if the specified collection is this list, and this
|
409 |
* list is nonempty.)
|
410 |
*
|
411 |
* @param c collection containing elements to be added to this list
|
412 |
* @return <tt>true</tt> if this list changed as a result of the call
|
413 |
* @throws NullPointerException if the specified collection is null
|
414 |
*/
|
415 |
public boolean addAll(Collection<? extends Long> c) { |
416 |
Object[] a = c.toArray(); |
417 |
int numNew = a.length;
|
418 |
ensureCapacityInternal(size + numNew); // Increments modCount
|
419 |
System.arraycopy(a, 0, elementData, size, numNew); |
420 |
size += numNew; |
421 |
return numNew != 0; |
422 |
} |
423 |
|
424 |
/**
|
425 |
* Inserts all of the elements in the specified collection into this
|
426 |
* list, starting at the specified position. Shifts the element
|
427 |
* currently at that position (if any) and any subsequent elements to
|
428 |
* the right (increases their indices). The new elements will appear
|
429 |
* in the list in the order that they are returned by the
|
430 |
* specified collection's iterator.
|
431 |
*
|
432 |
* @param index index at which to insert the first element from the
|
433 |
* specified collection
|
434 |
* @param c collection containing elements to be added to this list
|
435 |
* @return <tt>true</tt> if this list changed as a result of the call
|
436 |
* @throws IndexOutOfBoundsException {@inheritDoc}
|
437 |
* @throws NullPointerException if the specified collection is null
|
438 |
*/
|
439 |
public boolean addAll(int index, Collection<? extends Long> c) { |
440 |
rangeCheckForAdd(index); |
441 |
|
442 |
Object[] a = c.toArray(); |
443 |
int numNew = a.length;
|
444 |
ensureCapacityInternal(size + numNew); // Increments modCount
|
445 |
|
446 |
int numMoved = size - index;
|
447 |
if (numMoved > 0) |
448 |
System.arraycopy(elementData, index, elementData, index + numNew,
|
449 |
numMoved); |
450 |
|
451 |
System.arraycopy(a, 0, elementData, index, numNew); |
452 |
size += numNew; |
453 |
return numNew != 0; |
454 |
} |
455 |
|
456 |
/**
|
457 |
* Removes from this list all of the elements whose index is between
|
458 |
* {@code fromIndex}, inclusive, and {@code toIndex}, exclusive.
|
459 |
* Shifts any succeeding elements to the left (reduces their index).
|
460 |
* This call shortens the list by {@code (toIndex - fromIndex)} elements.
|
461 |
* (If {@code toIndex==fromIndex}, this operation has no effect.)
|
462 |
*
|
463 |
* @throws IndexOutOfBoundsException if {@code fromIndex} or
|
464 |
* {@code toIndex} is out of range
|
465 |
* ({@code fromIndex < 0 ||
|
466 |
* fromIndex >= size() ||
|
467 |
* toIndex > size() ||
|
468 |
* toIndex < fromIndex})
|
469 |
*/
|
470 |
protected void removeRange(int fromIndex, int toIndex) { |
471 |
modCount++; |
472 |
int numMoved = size - toIndex;
|
473 |
System.arraycopy(elementData, toIndex, elementData, fromIndex,
|
474 |
numMoved); |
475 |
int newSize = size - (toIndex-fromIndex);
|
476 |
size = newSize; |
477 |
} |
478 |
|
479 |
/**
|
480 |
* Checks if the given index is in range. If not, throws an appropriate
|
481 |
* runtime exception. This method does *not* check if the index is
|
482 |
* negative: It is always used immediately prior to an array access,
|
483 |
* which throws an ArrayIndexOutOfBoundsException if index is negative.
|
484 |
*/
|
485 |
private void rangeCheck(int index) { |
486 |
if (index >= size)
|
487 |
throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); |
488 |
} |
489 |
|
490 |
/**
|
491 |
* A version of rangeCheck used by add and addAll.
|
492 |
*/
|
493 |
private void rangeCheckForAdd(int index) { |
494 |
if (index > size || index < 0) |
495 |
throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); |
496 |
} |
497 |
|
498 |
/**
|
499 |
* Constructs an IndexOutOfBoundsException detail message.
|
500 |
* Of the many possible refactorings of the error handling code,
|
501 |
* this "outlining" performs best with both server and client VMs.
|
502 |
*/
|
503 |
private String outOfBoundsMsg(int index) { |
504 |
return "Index: "+index+", Size: "+size; |
505 |
} |
506 |
|
507 |
/**
|
508 |
* Removes from this list all of its elements that are contained in the
|
509 |
* specified collection.
|
510 |
*
|
511 |
* @param c collection containing elements to be removed from this list
|
512 |
* @return {@code true} if this list changed as a result of the call
|
513 |
* @throws ClassCastException if the class of an element of this list
|
514 |
* is incompatible with the specified collection
|
515 |
* (<a href="Collection.html#optional-restrictions">optional</a>)
|
516 |
* @throws NullPointerException if this list contains a null element and the
|
517 |
* specified collection does not permit null elements
|
518 |
* (<a href="Collection.html#optional-restrictions">optional</a>),
|
519 |
* or if the specified collection is null
|
520 |
* @see Collection#contains(Object)
|
521 |
*/
|
522 |
public boolean removeAll(Collection<?> c) { |
523 |
Objects.requireNonNull(c); |
524 |
return batchRemove(c, false); |
525 |
} |
526 |
|
527 |
/**
|
528 |
* Retains only the elements in this list that are contained in the
|
529 |
* specified collection. In other words, removes from this list all
|
530 |
* of its elements that are not contained in the specified collection.
|
531 |
*
|
532 |
* @param c collection containing elements to be retained in this list
|
533 |
* @return {@code true} if this list changed as a result of the call
|
534 |
* @throws ClassCastException if the class of an element of this list
|
535 |
* is incompatible with the specified collection
|
536 |
* (<a href="Collection.html#optional-restrictions">optional</a>)
|
537 |
* @throws NullPointerException if this list contains a null element and the
|
538 |
* specified collection does not permit null elements
|
539 |
* (<a href="Collection.html#optional-restrictions">optional</a>),
|
540 |
* or if the specified collection is null
|
541 |
* @see Collection#contains(Object)
|
542 |
*/
|
543 |
public boolean retainAll(Collection<?> c) { |
544 |
Objects.requireNonNull(c); |
545 |
return batchRemove(c, true); |
546 |
} |
547 |
|
548 |
private boolean batchRemove(Collection<?> c, boolean complement) { |
549 |
final long[] elementData = this.elementData; |
550 |
int r = 0, w = 0; |
551 |
boolean modified = false; |
552 |
try {
|
553 |
for (; r < size; r++)
|
554 |
if (c.contains(elementData[r]) == complement)
|
555 |
elementData[w++] = elementData[r]; |
556 |
} finally {
|
557 |
// Preserve behavioral compatibility with AbstractCollection,
|
558 |
// even if c.contains() throws.
|
559 |
if (r != size) {
|
560 |
System.arraycopy(elementData, r,
|
561 |
elementData, w, |
562 |
size - r); |
563 |
w += size - r; |
564 |
} |
565 |
if (w != size) {
|
566 |
modCount += size - w; |
567 |
size = w; |
568 |
modified = true;
|
569 |
} |
570 |
} |
571 |
return modified;
|
572 |
} |
573 |
|
574 |
/**
|
575 |
* Returns a list iterator over the elements in this list (in proper
|
576 |
* sequence), starting at the specified position in the list.
|
577 |
* The specified index indicates the first element that would be
|
578 |
* returned by an initial call to {@link ListIterator#next next}.
|
579 |
* An initial call to {@link ListIterator#previous previous} would
|
580 |
* return the element with the specified index minus one.
|
581 |
*
|
582 |
* <p>The returned list iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
|
583 |
*
|
584 |
* @throws IndexOutOfBoundsException {@inheritDoc}
|
585 |
*/
|
586 |
public ListIterator<Long> listIterator(int index) { |
587 |
if (index < 0 || index > size) |
588 |
throw new IndexOutOfBoundsException("Index: "+index); |
589 |
return new ListItr(index); |
590 |
} |
591 |
|
592 |
/**
|
593 |
* Returns a list iterator over the elements in this list (in proper
|
594 |
* sequence).
|
595 |
*
|
596 |
* <p>The returned list iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
|
597 |
*
|
598 |
* @see #listIterator(int)
|
599 |
*/
|
600 |
public ListIterator<Long> listIterator() { |
601 |
return new ListItr(0); |
602 |
} |
603 |
|
604 |
/**
|
605 |
* Returns an iterator over the elements in this list in proper sequence.
|
606 |
*
|
607 |
* <p>The returned iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
|
608 |
*
|
609 |
* @return an iterator over the elements in this list in proper sequence
|
610 |
*/
|
611 |
public Iterator<Long> iterator() { |
612 |
return new Itr(); |
613 |
} |
614 |
|
615 |
/**
|
616 |
* An optimized version of AbstractList.Itr
|
617 |
*/
|
618 |
private class Itr implements Iterator<Long> { |
619 |
int cursor; // index of next element to return |
620 |
int lastRet = -1; // index of last element returned; -1 if no such |
621 |
int expectedModCount = modCount;
|
622 |
|
623 |
Itr() {} |
624 |
|
625 |
public boolean hasNext() { |
626 |
return cursor != size;
|
627 |
} |
628 |
|
629 |
@SuppressWarnings("unchecked") |
630 |
public Long next() { |
631 |
checkForComodification(); |
632 |
int i = cursor;
|
633 |
if (i >= size)
|
634 |
throw new NoSuchElementException(); |
635 |
long[] elementData = ArrayListOfLong.this.elementData; |
636 |
if (i >= elementData.length)
|
637 |
throw new ConcurrentModificationException(); |
638 |
cursor = i + 1;
|
639 |
return (Long) elementData[lastRet = i]; |
640 |
} |
641 |
|
642 |
public void remove() { |
643 |
if (lastRet < 0) |
644 |
throw new IllegalStateException(); |
645 |
checkForComodification(); |
646 |
|
647 |
try {
|
648 |
ArrayListOfLong.this.remove(lastRet); |
649 |
cursor = lastRet; |
650 |
lastRet = -1;
|
651 |
expectedModCount = modCount; |
652 |
} catch (IndexOutOfBoundsException ex) { |
653 |
throw new ConcurrentModificationException(); |
654 |
} |
655 |
} |
656 |
|
657 |
@Override
|
658 |
@SuppressWarnings("unchecked") |
659 |
public void forEachRemaining(Consumer<? super Long> consumer) { |
660 |
Objects.requireNonNull(consumer); |
661 |
final int size = ArrayListOfLong.this.size; |
662 |
int i = cursor;
|
663 |
if (i >= size) {
|
664 |
return;
|
665 |
} |
666 |
final long[] elementData = ArrayListOfLong.this.elementData; |
667 |
if (i >= elementData.length) {
|
668 |
throw new ConcurrentModificationException(); |
669 |
} |
670 |
while (i != size && modCount == expectedModCount) {
|
671 |
consumer.accept((Long) elementData[i++]);
|
672 |
} |
673 |
// update once at end of iteration to reduce heap write traffic
|
674 |
cursor = i; |
675 |
lastRet = i - 1;
|
676 |
checkForComodification(); |
677 |
} |
678 |
|
679 |
final void checkForComodification() { |
680 |
if (modCount != expectedModCount)
|
681 |
throw new ConcurrentModificationException(); |
682 |
} |
683 |
} |
684 |
|
685 |
/**
|
686 |
* An optimized version of AbstractList.ListItr
|
687 |
*/
|
688 |
private class ListItr extends Itr implements ListIterator<Long> { |
689 |
ListItr(int index) {
|
690 |
super();
|
691 |
cursor = index; |
692 |
} |
693 |
|
694 |
public boolean hasPrevious() { |
695 |
return cursor != 0; |
696 |
} |
697 |
|
698 |
public int nextIndex() { |
699 |
return cursor;
|
700 |
} |
701 |
|
702 |
public int previousIndex() { |
703 |
return cursor - 1; |
704 |
} |
705 |
|
706 |
@SuppressWarnings("unchecked") |
707 |
public Long previous() { |
708 |
checkForComodification(); |
709 |
int i = cursor - 1; |
710 |
if (i < 0) |
711 |
throw new NoSuchElementException(); |
712 |
long[] elementData = ArrayListOfLong.this.elementData; |
713 |
if (i >= elementData.length)
|
714 |
throw new ConcurrentModificationException(); |
715 |
cursor = i; |
716 |
return (Long) elementData[lastRet = i]; |
717 |
} |
718 |
|
719 |
public void set(Long e) { |
720 |
if (lastRet < 0) |
721 |
throw new IllegalStateException(); |
722 |
checkForComodification(); |
723 |
|
724 |
try {
|
725 |
ArrayListOfLong.this.set(lastRet, e); |
726 |
} catch (IndexOutOfBoundsException ex) { |
727 |
throw new ConcurrentModificationException(); |
728 |
} |
729 |
} |
730 |
|
731 |
public void add(Long e) { |
732 |
checkForComodification(); |
733 |
|
734 |
try {
|
735 |
int i = cursor;
|
736 |
ArrayListOfLong.this.add(i, e); |
737 |
cursor = i + 1;
|
738 |
lastRet = -1;
|
739 |
expectedModCount = modCount; |
740 |
} catch (IndexOutOfBoundsException ex) { |
741 |
throw new ConcurrentModificationException(); |
742 |
} |
743 |
} |
744 |
} |
745 |
|
746 |
/**
|
747 |
* Returns a view of the portion of this list between the specified
|
748 |
* {@code fromIndex}, inclusive, and {@code toIndex}, exclusive. (If
|
749 |
* {@code fromIndex} and {@code toIndex} are equal, the returned list is
|
750 |
* empty.) The returned list is backed by this list, so non-structural
|
751 |
* changes in the returned list are reflected in this list, and vice-versa.
|
752 |
* The returned list supports all of the optional list operations.
|
753 |
*
|
754 |
* <p>This method eliminates the need for explicit range operations (of
|
755 |
* the sort that commonly exist for arrays). Any operation that expects
|
756 |
* a list can be used as a range operation by passing a subList view
|
757 |
* instead of a whole list. For example, the following idiom
|
758 |
* removes a range of elements from a list:
|
759 |
* <pre>
|
760 |
* list.subList(from, to).clear();
|
761 |
* </pre>
|
762 |
* Similar idioms may be constructed for {@link #indexOf(Object)} and
|
763 |
* {@link #lastIndexOf(Object)}, and all of the algorithms in the
|
764 |
* {@link Collections} class can be applied to a subList.
|
765 |
*
|
766 |
* <p>The semantics of the list returned by this method become undefined if
|
767 |
* the backing list (i.e., this list) is <i>structurally modified</i> in
|
768 |
* any way other than via the returned list. (Structural modifications are
|
769 |
* those that change the size of this list, or otherwise perturb it in such
|
770 |
* a fashion that iterations in progress may yield incorrect results.)
|
771 |
*
|
772 |
* @throws IndexOutOfBoundsException {@inheritDoc}
|
773 |
* @throws IllegalArgumentException {@inheritDoc}
|
774 |
*/
|
775 |
public List<Long> subList(int fromIndex, int toIndex) { |
776 |
subListRangeCheck(fromIndex, toIndex, size); |
777 |
return new SubList(this, 0, fromIndex, toIndex); |
778 |
} |
779 |
|
780 |
static void subListRangeCheck(int fromIndex, int toIndex, int size) { |
781 |
if (fromIndex < 0) |
782 |
throw new IndexOutOfBoundsException("fromIndex = " + fromIndex); |
783 |
if (toIndex > size)
|
784 |
throw new IndexOutOfBoundsException("toIndex = " + toIndex); |
785 |
if (fromIndex > toIndex)
|
786 |
throw new IllegalArgumentException("fromIndex(" + fromIndex + |
787 |
") > toIndex(" + toIndex + ")"); |
788 |
} |
789 |
|
790 |
private class SubList extends ArrayListOfLong implements RandomAccess { |
791 |
private final ArrayListOfLong parent; |
792 |
private final int parentOffset; |
793 |
private final int offset; |
794 |
int size;
|
795 |
|
796 |
SubList(ArrayListOfLong parent, |
797 |
int offset, int fromIndex, int toIndex) { |
798 |
this.parent = parent;
|
799 |
this.parentOffset = fromIndex;
|
800 |
this.offset = offset + fromIndex;
|
801 |
this.size = toIndex - fromIndex;
|
802 |
this.modCount = ArrayListOfLong.this.modCount;
|
803 |
} |
804 |
|
805 |
public Long set(int index, Long e) { |
806 |
rangeCheck(index); |
807 |
checkForComodification(); |
808 |
Long oldValue = ArrayListOfLong.this.elementData(offset + index);
|
809 |
ArrayListOfLong.this.elementData[offset + index] = e; |
810 |
return oldValue;
|
811 |
} |
812 |
|
813 |
public Long get(int index) { |
814 |
rangeCheck(index); |
815 |
checkForComodification(); |
816 |
return ArrayListOfLong.this.elementData(offset + index);
|
817 |
} |
818 |
|
819 |
public int size() { |
820 |
checkForComodification(); |
821 |
return this.size; |
822 |
} |
823 |
|
824 |
public void add(int index, Long e) { |
825 |
rangeCheckForAdd(index); |
826 |
checkForComodification(); |
827 |
parent.add(parentOffset + index, e); |
828 |
this.modCount = parent.modCount;
|
829 |
this.size++;
|
830 |
} |
831 |
|
832 |
public Long remove(int index) { |
833 |
rangeCheck(index); |
834 |
checkForComodification(); |
835 |
Long result = parent.remove(parentOffset + index);
|
836 |
this.modCount = parent.modCount;
|
837 |
this.size--;
|
838 |
return result;
|
839 |
} |
840 |
|
841 |
protected void removeRange(int fromIndex, int toIndex) { |
842 |
checkForComodification(); |
843 |
parent.removeRange(parentOffset + fromIndex, |
844 |
parentOffset + toIndex); |
845 |
this.modCount = parent.modCount;
|
846 |
this.size -= toIndex - fromIndex;
|
847 |
} |
848 |
|
849 |
public boolean addAll(Collection<? extends Long> c) { |
850 |
return addAll(this.size, c); |
851 |
} |
852 |
|
853 |
public boolean addAll(int index, Collection<? extends Long> c) { |
854 |
rangeCheckForAdd(index); |
855 |
int cSize = c.size();
|
856 |
if (cSize==0) |
857 |
return false; |
858 |
|
859 |
checkForComodification(); |
860 |
parent.addAll(parentOffset + index, c); |
861 |
this.modCount = parent.modCount;
|
862 |
this.size += cSize;
|
863 |
return true; |
864 |
} |
865 |
|
866 |
public Iterator<Long> iterator() { |
867 |
return listIterator();
|
868 |
} |
869 |
|
870 |
public ListIterator<Long> listIterator(final int index) { |
871 |
checkForComodification(); |
872 |
rangeCheckForAdd(index); |
873 |
final int offset = this.offset; |
874 |
|
875 |
return new ListIterator<Long>() { |
876 |
int cursor = index;
|
877 |
int lastRet = -1; |
878 |
int expectedModCount = ArrayListOfLong.this.modCount;
|
879 |
|
880 |
public boolean hasNext() { |
881 |
return cursor != SubList.this.size;
|
882 |
} |
883 |
|
884 |
@SuppressWarnings("unchecked") |
885 |
public Long next() { |
886 |
checkForComodification(); |
887 |
int i = cursor;
|
888 |
if (i >= SubList.this.size)
|
889 |
throw new NoSuchElementException(); |
890 |
long[] elementData = ArrayListOfLong.this.elementData; |
891 |
if (offset + i >= elementData.length)
|
892 |
throw new ConcurrentModificationException(); |
893 |
cursor = i + 1;
|
894 |
return (Long) elementData[offset + (lastRet = i)]; |
895 |
} |
896 |
|
897 |
public boolean hasPrevious() { |
898 |
return cursor != 0; |
899 |
} |
900 |
|
901 |
@SuppressWarnings("unchecked") |
902 |
public Long previous() { |
903 |
checkForComodification(); |
904 |
int i = cursor - 1; |
905 |
if (i < 0) |
906 |
throw new NoSuchElementException(); |
907 |
long[] elementData = ArrayListOfLong.this.elementData; |
908 |
if (offset + i >= elementData.length)
|
909 |
throw new ConcurrentModificationException(); |
910 |
cursor = i; |
911 |
return (Long) elementData[offset + (lastRet = i)]; |
912 |
} |
913 |
|
914 |
@SuppressWarnings("unchecked") |
915 |
public void forEachRemaining(Consumer<? super Long> consumer) { |
916 |
Objects.requireNonNull(consumer); |
917 |
final int size = SubList.this.size; |
918 |
int i = cursor;
|
919 |
if (i >= size) {
|
920 |
return;
|
921 |
} |
922 |
final long[] elementData = ArrayListOfLong.this.elementData; |
923 |
if (offset + i >= elementData.length) {
|
924 |
throw new ConcurrentModificationException(); |
925 |
} |
926 |
while (i != size && modCount == expectedModCount) {
|
927 |
consumer.accept((Long) elementData[offset + (i++)]);
|
928 |
} |
929 |
// update once at end of iteration to reduce heap write traffic
|
930 |
lastRet = cursor = i; |
931 |
checkForComodification(); |
932 |
} |
933 |
|
934 |
public int nextIndex() { |
935 |
return cursor;
|
936 |
} |
937 |
|
938 |
public int previousIndex() { |
939 |
return cursor - 1; |
940 |
} |
941 |
|
942 |
public void remove() { |
943 |
if (lastRet < 0) |
944 |
throw new IllegalStateException(); |
945 |
checkForComodification(); |
946 |
|
947 |
try {
|
948 |
SubList.this.remove(lastRet); |
949 |
cursor = lastRet; |
950 |
lastRet = -1;
|
951 |
expectedModCount = ArrayListOfLong.this.modCount; |
952 |
} catch (IndexOutOfBoundsException ex) { |
953 |
throw new ConcurrentModificationException(); |
954 |
} |
955 |
} |
956 |
|
957 |
public void set(Long e) { |
958 |
if (lastRet < 0) |
959 |
throw new IllegalStateException(); |
960 |
checkForComodification(); |
961 |
|
962 |
try {
|
963 |
ArrayListOfLong.this.set(offset + lastRet, e); |
964 |
} catch (IndexOutOfBoundsException ex) { |
965 |
throw new ConcurrentModificationException(); |
966 |
} |
967 |
} |
968 |
|
969 |
public void add(Long e) { |
970 |
checkForComodification(); |
971 |
|
972 |
try {
|
973 |
int i = cursor;
|
974 |
SubList.this.add(i, e); |
975 |
cursor = i + 1;
|
976 |
lastRet = -1;
|
977 |
expectedModCount = ArrayListOfLong.this.modCount; |
978 |
} catch (IndexOutOfBoundsException ex) { |
979 |
throw new ConcurrentModificationException(); |
980 |
} |
981 |
} |
982 |
|
983 |
final void checkForComodification() { |
984 |
if (expectedModCount != ArrayListOfLong.this.modCount)
|
985 |
throw new ConcurrentModificationException(); |
986 |
} |
987 |
}; |
988 |
} |
989 |
|
990 |
public List<Long> subList(int fromIndex, int toIndex) { |
991 |
subListRangeCheck(fromIndex, toIndex, size); |
992 |
return new SubList(this, offset, fromIndex, toIndex); |
993 |
} |
994 |
|
995 |
private void rangeCheck(int index) { |
996 |
if (index < 0 || index >= this.size) |
997 |
throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); |
998 |
} |
999 |
|
1000 |
private void rangeCheckForAdd(int index) { |
1001 |
if (index < 0 || index > this.size) |
1002 |
throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); |
1003 |
} |
1004 |
|
1005 |
private String outOfBoundsMsg(int index) { |
1006 |
return "Index: "+index+", Size: "+this.size; |
1007 |
} |
1008 |
|
1009 |
private void checkForComodification() { |
1010 |
if (ArrayListOfLong.this.modCount != this.modCount) |
1011 |
throw new ConcurrentModificationException(); |
1012 |
} |
1013 |
|
1014 |
public Spliterator<Long> spliterator() { |
1015 |
checkForComodification(); |
1016 |
return new ArrayListSpliterator(ArrayListOfLong.this, offset, |
1017 |
offset + this.size, this.modCount); |
1018 |
} |
1019 |
} |
1020 |
|
1021 |
@Override
|
1022 |
public void forEach(Consumer<? super Long> action) { |
1023 |
Objects.requireNonNull(action); |
1024 |
final int expectedModCount = modCount; |
1025 |
@SuppressWarnings("unchecked") |
1026 |
final long[] elementData = this.elementData; |
1027 |
final int size = this.size; |
1028 |
for (int i=0; modCount == expectedModCount && i < size; i++) { |
1029 |
action.accept(elementData[i]); |
1030 |
} |
1031 |
if (modCount != expectedModCount) {
|
1032 |
throw new ConcurrentModificationException(); |
1033 |
} |
1034 |
} |
1035 |
|
1036 |
/**
|
1037 |
* Creates a <em><a href="Spliterator.html#binding">late-binding</a></em>
|
1038 |
* and <em>fail-fast</em> {@link Spliterator} over the elements in this
|
1039 |
* list.
|
1040 |
*
|
1041 |
* <p>The {@code Spliterator} reports {@link Spliterator#SIZED},
|
1042 |
* {@link Spliterator#SUBSIZED}, and {@link Spliterator#ORDERED}.
|
1043 |
* Overriding implementations should document the reporting of additional
|
1044 |
* characteristic values.
|
1045 |
*
|
1046 |
* @return a {@code Spliterator} over the elements in this list
|
1047 |
* @since 1.8
|
1048 |
*/
|
1049 |
@Override
|
1050 |
public Spliterator<Long> spliterator() { |
1051 |
return new ArrayListSpliterator(this, 0, -1, 0); |
1052 |
} |
1053 |
|
1054 |
static final class ArrayListSpliterator implements Spliterator<Long> { |
1055 |
private final ArrayListOfLong list; |
1056 |
private int index; // current index, modified on advance/split |
1057 |
private int fence; // -1 until used; then one past last index |
1058 |
private int expectedModCount; // initialized when fence set |
1059 |
|
1060 |
/** Create new spliterator covering the given range */
|
1061 |
ArrayListSpliterator(ArrayListOfLong list, int origin, int fence, |
1062 |
int expectedModCount) {
|
1063 |
this.list = list; // OK if null unless traversed |
1064 |
this.index = origin;
|
1065 |
this.fence = fence;
|
1066 |
this.expectedModCount = expectedModCount;
|
1067 |
} |
1068 |
|
1069 |
private int getFence() { // initialize fence to size on first use |
1070 |
int hi; // (a specialized variant appears in method forEach) |
1071 |
ArrayListOfLong lst; |
1072 |
if ((hi = fence) < 0) { |
1073 |
if ((lst = list) == null) |
1074 |
hi = fence = 0;
|
1075 |
else {
|
1076 |
expectedModCount = lst.modCount; |
1077 |
hi = fence = lst.size; |
1078 |
} |
1079 |
} |
1080 |
return hi;
|
1081 |
} |
1082 |
|
1083 |
public ArrayListSpliterator trySplit() {
|
1084 |
int hi = getFence(), lo = index, mid = (lo + hi) >>> 1; |
1085 |
return (lo >= mid) ? null : // divide range in half unless too small |
1086 |
new ArrayListSpliterator(list, lo, index = mid,
|
1087 |
expectedModCount); |
1088 |
} |
1089 |
|
1090 |
public boolean tryAdvance(Consumer<? super Long> action) { |
1091 |
if (action == null) |
1092 |
throw new NullPointerException(); |
1093 |
int hi = getFence(), i = index;
|
1094 |
if (i < hi) {
|
1095 |
index = i + 1;
|
1096 |
Long e = list.elementData[i];
|
1097 |
action.accept(e); |
1098 |
if (list.modCount != expectedModCount)
|
1099 |
throw new ConcurrentModificationException(); |
1100 |
return true; |
1101 |
} |
1102 |
return false; |
1103 |
} |
1104 |
|
1105 |
public void forEachRemaining(Consumer<? super Long> action) { |
1106 |
int i, hi, mc; // hoist accesses and checks from loop |
1107 |
ArrayListOfLong lst; long[] a; |
1108 |
if (action == null) |
1109 |
throw new NullPointerException(); |
1110 |
if ((lst = list) != null && (a = lst.elementData) != null) { |
1111 |
if ((hi = fence) < 0) { |
1112 |
mc = lst.modCount; |
1113 |
hi = lst.size; |
1114 |
} |
1115 |
else
|
1116 |
mc = expectedModCount; |
1117 |
if ((i = index) >= 0 && (index = hi) <= a.length) { |
1118 |
for (; i < hi; ++i) {
|
1119 |
action.accept(a[i]); |
1120 |
} |
1121 |
if (lst.modCount == mc)
|
1122 |
return;
|
1123 |
} |
1124 |
} |
1125 |
throw new ConcurrentModificationException(); |
1126 |
} |
1127 |
|
1128 |
public long estimateSize() { |
1129 |
return (long) (getFence() - index); |
1130 |
} |
1131 |
|
1132 |
public int characteristics() { |
1133 |
return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED;
|
1134 |
} |
1135 |
} |
1136 |
|
1137 |
@Override
|
1138 |
public boolean removeIf(Predicate<? super Long> filter) { |
1139 |
Objects.requireNonNull(filter); |
1140 |
// figure out which elements are to be removed
|
1141 |
// any exception thrown from the filter predicate at this stage
|
1142 |
// will leave the collection unmodified
|
1143 |
int removeCount = 0; |
1144 |
final BitSet removeSet = new BitSet(size); |
1145 |
final int expectedModCount = modCount; |
1146 |
final int size = this.size; |
1147 |
for (int i=0; modCount == expectedModCount && i < size; i++) { |
1148 |
@SuppressWarnings("unchecked") |
1149 |
final Long element = (Long) elementData[i]; |
1150 |
if (filter.test(element)) {
|
1151 |
removeSet.set(i); |
1152 |
removeCount++; |
1153 |
} |
1154 |
} |
1155 |
if (modCount != expectedModCount) {
|
1156 |
throw new ConcurrentModificationException(); |
1157 |
} |
1158 |
|
1159 |
// shift surviving elements left over the spaces left by removed elements
|
1160 |
final boolean anyToRemove = removeCount > 0; |
1161 |
if (anyToRemove) {
|
1162 |
final int newSize = size - removeCount; |
1163 |
for (int i=0, j=0; (i < size) && (j < newSize); i++, j++) { |
1164 |
i = removeSet.nextClearBit(i); |
1165 |
elementData[j] = elementData[i]; |
1166 |
} |
1167 |
this.size = newSize;
|
1168 |
if (modCount != expectedModCount) {
|
1169 |
throw new ConcurrentModificationException(); |
1170 |
} |
1171 |
modCount++; |
1172 |
} |
1173 |
|
1174 |
return anyToRemove;
|
1175 |
} |
1176 |
|
1177 |
@Override
|
1178 |
@SuppressWarnings("unchecked") |
1179 |
public void replaceAll(UnaryOperator<Long> operator) { |
1180 |
Objects.requireNonNull(operator); |
1181 |
final int expectedModCount = modCount; |
1182 |
final int size = this.size; |
1183 |
for (int i=0; modCount == expectedModCount && i < size; i++) { |
1184 |
elementData[i] = operator.apply((Long) elementData[i]);
|
1185 |
} |
1186 |
if (modCount != expectedModCount) {
|
1187 |
throw new ConcurrentModificationException(); |
1188 |
} |
1189 |
modCount++; |
1190 |
} |
1191 |
|
1192 |
@Override
|
1193 |
@SuppressWarnings("unchecked") |
1194 |
public void sort(Comparator<? super Long> c) { |
1195 |
final int expectedModCount = modCount; |
1196 |
Arrays.sort(elementData);
|
1197 |
// Arrays.sort(elementData, 0, size, c);
|
1198 |
if (modCount != expectedModCount) {
|
1199 |
throw new ConcurrentModificationException(); |
1200 |
} |
1201 |
modCount++; |
1202 |
} |
1203 |
|
1204 |
} |