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 @ 44922
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 |
@Override
|
281 |
public Long[] toArray() { |
282 |
return toArray((Long[])null); |
283 |
} |
284 |
|
285 |
public Long[] toArray(Long[] a) { |
286 |
if (a==null || a.length < size) { |
287 |
a = new Long[size]; |
288 |
} |
289 |
for (int i = 0; i < size; i++) { |
290 |
a[i] = this.elementData[i];
|
291 |
} |
292 |
return a;
|
293 |
} |
294 |
|
295 |
// Positional Access Operations
|
296 |
|
297 |
@SuppressWarnings("unchecked") |
298 |
long elementData(int index) { |
299 |
return elementData[index];
|
300 |
} |
301 |
|
302 |
public Long get(int index) { |
303 |
return this.getLong(index); |
304 |
} |
305 |
|
306 |
public long getLong(int index) { |
307 |
rangeCheck(index); |
308 |
|
309 |
return elementData(index);
|
310 |
} |
311 |
|
312 |
/**
|
313 |
* Replaces the element at the specified position in this list with
|
314 |
* the specified element.
|
315 |
*
|
316 |
* @param index index of the element to replace
|
317 |
* @param element element to be stored at the specified position
|
318 |
* @return the element previously at the specified position
|
319 |
* @throws IndexOutOfBoundsException {@inheritDoc}
|
320 |
*/
|
321 |
public Long set(int index, Long element) { |
322 |
rangeCheck(index); |
323 |
|
324 |
Long oldValue = elementData(index);
|
325 |
elementData[index] = element; |
326 |
return oldValue;
|
327 |
} |
328 |
|
329 |
public boolean add(Long e) { |
330 |
return this.add((long)e); |
331 |
} |
332 |
|
333 |
public boolean add(long e) { |
334 |
ensureCapacityInternal(size + 1); // Increments modCount!! |
335 |
elementData[size++] = e; |
336 |
return true; |
337 |
} |
338 |
|
339 |
public void add(int index, Long element) { |
340 |
this.add(index, (long)element); |
341 |
} |
342 |
|
343 |
public void add(int index, long element) { |
344 |
rangeCheckForAdd(index); |
345 |
|
346 |
ensureCapacityInternal(size + 1); // Increments modCount!! |
347 |
System.arraycopy(elementData, index, elementData, index + 1, |
348 |
size - index); |
349 |
elementData[index] = element; |
350 |
size++; |
351 |
} |
352 |
|
353 |
public Long remove(int index) { |
354 |
rangeCheck(index); |
355 |
|
356 |
modCount++; |
357 |
Long oldValue = elementData(index);
|
358 |
|
359 |
int numMoved = size - index - 1; |
360 |
if (numMoved > 0) |
361 |
System.arraycopy(elementData, index+1, elementData, index, |
362 |
numMoved); |
363 |
return oldValue;
|
364 |
} |
365 |
|
366 |
public boolean remove(Object o) { |
367 |
if (o == null) { |
368 |
return true; |
369 |
} |
370 |
return this.removeLong((long)o); |
371 |
} |
372 |
|
373 |
public boolean removeLong(long o) { |
374 |
for (int index = 0; index < size; index++) |
375 |
if (o == elementData[index]) {
|
376 |
this.remove(index);
|
377 |
return true; |
378 |
} |
379 |
return false; |
380 |
} |
381 |
|
382 |
/*
|
383 |
* Private remove method that skips bounds checking and does not
|
384 |
* return the value removed.
|
385 |
*/
|
386 |
private void fastRemove(int index) { |
387 |
modCount++; |
388 |
int numMoved = size - index - 1; |
389 |
if (numMoved > 0) |
390 |
System.arraycopy(elementData, index+1, elementData, index, |
391 |
numMoved); |
392 |
} |
393 |
|
394 |
/**
|
395 |
* Removes all of the elements from this list. The list will
|
396 |
* be empty after this call returns.
|
397 |
*/
|
398 |
public void clear() { |
399 |
modCount++; |
400 |
size = 0;
|
401 |
} |
402 |
|
403 |
/**
|
404 |
* Appends all of the elements in the specified collection to the end of
|
405 |
* this list, in the order that they are returned by the
|
406 |
* specified collection's Iterator. The behavior of this operation is
|
407 |
* undefined if the specified collection is modified while the operation
|
408 |
* is in progress. (This implies that the behavior of this call is
|
409 |
* undefined if the specified collection is this list, and this
|
410 |
* list is nonempty.)
|
411 |
*
|
412 |
* @param c collection containing elements to be added to this list
|
413 |
* @return <tt>true</tt> if this list changed as a result of the call
|
414 |
* @throws NullPointerException if the specified collection is null
|
415 |
*/
|
416 |
public boolean addAll(Collection<? extends Long> c) { |
417 |
Object[] a = c.toArray(); |
418 |
int numNew = a.length;
|
419 |
ensureCapacityInternal(size + numNew); // Increments modCount
|
420 |
System.arraycopy(a, 0, elementData, size, numNew); |
421 |
size += numNew; |
422 |
return numNew != 0; |
423 |
} |
424 |
|
425 |
/**
|
426 |
* Inserts all of the elements in the specified collection into this
|
427 |
* list, starting at the specified position. Shifts the element
|
428 |
* currently at that position (if any) and any subsequent elements to
|
429 |
* the right (increases their indices). The new elements will appear
|
430 |
* in the list in the order that they are returned by the
|
431 |
* specified collection's iterator.
|
432 |
*
|
433 |
* @param index index at which to insert the first element from the
|
434 |
* specified collection
|
435 |
* @param c collection containing elements to be added to this list
|
436 |
* @return <tt>true</tt> if this list changed as a result of the call
|
437 |
* @throws IndexOutOfBoundsException {@inheritDoc}
|
438 |
* @throws NullPointerException if the specified collection is null
|
439 |
*/
|
440 |
public boolean addAll(int index, Collection<? extends Long> c) { |
441 |
rangeCheckForAdd(index); |
442 |
|
443 |
Object[] a = c.toArray(); |
444 |
int numNew = a.length;
|
445 |
ensureCapacityInternal(size + numNew); // Increments modCount
|
446 |
|
447 |
int numMoved = size - index;
|
448 |
if (numMoved > 0) |
449 |
System.arraycopy(elementData, index, elementData, index + numNew,
|
450 |
numMoved); |
451 |
|
452 |
System.arraycopy(a, 0, elementData, index, numNew); |
453 |
size += numNew; |
454 |
return numNew != 0; |
455 |
} |
456 |
|
457 |
/**
|
458 |
* Removes from this list all of the elements whose index is between
|
459 |
* {@code fromIndex}, inclusive, and {@code toIndex}, exclusive.
|
460 |
* Shifts any succeeding elements to the left (reduces their index).
|
461 |
* This call shortens the list by {@code (toIndex - fromIndex)} elements.
|
462 |
* (If {@code toIndex==fromIndex}, this operation has no effect.)
|
463 |
*
|
464 |
* @throws IndexOutOfBoundsException if {@code fromIndex} or
|
465 |
* {@code toIndex} is out of range
|
466 |
* ({@code fromIndex < 0 ||
|
467 |
* fromIndex >= size() ||
|
468 |
* toIndex > size() ||
|
469 |
* toIndex < fromIndex})
|
470 |
*/
|
471 |
protected void removeRange(int fromIndex, int toIndex) { |
472 |
modCount++; |
473 |
int numMoved = size - toIndex;
|
474 |
System.arraycopy(elementData, toIndex, elementData, fromIndex,
|
475 |
numMoved); |
476 |
int newSize = size - (toIndex-fromIndex);
|
477 |
size = newSize; |
478 |
} |
479 |
|
480 |
/**
|
481 |
* Checks if the given index is in range. If not, throws an appropriate
|
482 |
* runtime exception. This method does *not* check if the index is
|
483 |
* negative: It is always used immediately prior to an array access,
|
484 |
* which throws an ArrayIndexOutOfBoundsException if index is negative.
|
485 |
*/
|
486 |
private void rangeCheck(int index) { |
487 |
if (index >= size)
|
488 |
throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); |
489 |
} |
490 |
|
491 |
/**
|
492 |
* A version of rangeCheck used by add and addAll.
|
493 |
*/
|
494 |
private void rangeCheckForAdd(int index) { |
495 |
if (index > size || index < 0) |
496 |
throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); |
497 |
} |
498 |
|
499 |
/**
|
500 |
* Constructs an IndexOutOfBoundsException detail message.
|
501 |
* Of the many possible refactorings of the error handling code,
|
502 |
* this "outlining" performs best with both server and client VMs.
|
503 |
*/
|
504 |
private String outOfBoundsMsg(int index) { |
505 |
return "Index: "+index+", Size: "+size; |
506 |
} |
507 |
|
508 |
/**
|
509 |
* Removes from this list all of its elements that are contained in the
|
510 |
* specified collection.
|
511 |
*
|
512 |
* @param c collection containing elements to be removed from this list
|
513 |
* @return {@code true} if this list changed as a result of the call
|
514 |
* @throws ClassCastException if the class of an element of this list
|
515 |
* is incompatible with the specified collection
|
516 |
* (<a href="Collection.html#optional-restrictions">optional</a>)
|
517 |
* @throws NullPointerException if this list contains a null element and the
|
518 |
* specified collection does not permit null elements
|
519 |
* (<a href="Collection.html#optional-restrictions">optional</a>),
|
520 |
* or if the specified collection is null
|
521 |
* @see Collection#contains(Object)
|
522 |
*/
|
523 |
public boolean removeAll(Collection<?> c) { |
524 |
Objects.requireNonNull(c); |
525 |
return batchRemove(c, false); |
526 |
} |
527 |
|
528 |
/**
|
529 |
* Retains only the elements in this list that are contained in the
|
530 |
* specified collection. In other words, removes from this list all
|
531 |
* of its elements that are not contained in the specified collection.
|
532 |
*
|
533 |
* @param c collection containing elements to be retained in this list
|
534 |
* @return {@code true} if this list changed as a result of the call
|
535 |
* @throws ClassCastException if the class of an element of this list
|
536 |
* is incompatible with the specified collection
|
537 |
* (<a href="Collection.html#optional-restrictions">optional</a>)
|
538 |
* @throws NullPointerException if this list contains a null element and the
|
539 |
* specified collection does not permit null elements
|
540 |
* (<a href="Collection.html#optional-restrictions">optional</a>),
|
541 |
* or if the specified collection is null
|
542 |
* @see Collection#contains(Object)
|
543 |
*/
|
544 |
public boolean retainAll(Collection<?> c) { |
545 |
Objects.requireNonNull(c); |
546 |
return batchRemove(c, true); |
547 |
} |
548 |
|
549 |
private boolean batchRemove(Collection<?> c, boolean complement) { |
550 |
final long[] elementData = this.elementData; |
551 |
int r = 0, w = 0; |
552 |
boolean modified = false; |
553 |
try {
|
554 |
for (; r < size; r++)
|
555 |
if (c.contains(elementData[r]) == complement)
|
556 |
elementData[w++] = elementData[r]; |
557 |
} finally {
|
558 |
// Preserve behavioral compatibility with AbstractCollection,
|
559 |
// even if c.contains() throws.
|
560 |
if (r != size) {
|
561 |
System.arraycopy(elementData, r,
|
562 |
elementData, w, |
563 |
size - r); |
564 |
w += size - r; |
565 |
} |
566 |
if (w != size) {
|
567 |
modCount += size - w; |
568 |
size = w; |
569 |
modified = true;
|
570 |
} |
571 |
} |
572 |
return modified;
|
573 |
} |
574 |
|
575 |
/**
|
576 |
* Returns a list iterator over the elements in this list (in proper
|
577 |
* sequence), starting at the specified position in the list.
|
578 |
* The specified index indicates the first element that would be
|
579 |
* returned by an initial call to {@link ListIterator#next next}.
|
580 |
* An initial call to {@link ListIterator#previous previous} would
|
581 |
* return the element with the specified index minus one.
|
582 |
*
|
583 |
* <p>The returned list iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
|
584 |
*
|
585 |
* @throws IndexOutOfBoundsException {@inheritDoc}
|
586 |
*/
|
587 |
public ListIterator<Long> listIterator(int index) { |
588 |
if (index < 0 || index > size) |
589 |
throw new IndexOutOfBoundsException("Index: "+index); |
590 |
return new ListItr(index); |
591 |
} |
592 |
|
593 |
/**
|
594 |
* Returns a list iterator over the elements in this list (in proper
|
595 |
* sequence).
|
596 |
*
|
597 |
* <p>The returned list iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
|
598 |
*
|
599 |
* @see #listIterator(int)
|
600 |
*/
|
601 |
public ListIterator<Long> listIterator() { |
602 |
return new ListItr(0); |
603 |
} |
604 |
|
605 |
/**
|
606 |
* Returns an iterator over the elements in this list in proper sequence.
|
607 |
*
|
608 |
* <p>The returned iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
|
609 |
*
|
610 |
* @return an iterator over the elements in this list in proper sequence
|
611 |
*/
|
612 |
public Iterator<Long> iterator() { |
613 |
return new Itr(); |
614 |
} |
615 |
|
616 |
/**
|
617 |
* An optimized version of AbstractList.Itr
|
618 |
*/
|
619 |
private class Itr implements Iterator<Long> { |
620 |
int cursor; // index of next element to return |
621 |
int lastRet = -1; // index of last element returned; -1 if no such |
622 |
int expectedModCount = modCount;
|
623 |
|
624 |
Itr() {} |
625 |
|
626 |
public boolean hasNext() { |
627 |
return cursor != size;
|
628 |
} |
629 |
|
630 |
@SuppressWarnings("unchecked") |
631 |
public Long next() { |
632 |
checkForComodification(); |
633 |
int i = cursor;
|
634 |
if (i >= size)
|
635 |
throw new NoSuchElementException(); |
636 |
long[] elementData = ArrayListOfLong.this.elementData; |
637 |
if (i >= elementData.length)
|
638 |
throw new ConcurrentModificationException(); |
639 |
cursor = i + 1;
|
640 |
return (Long) elementData[lastRet = i]; |
641 |
} |
642 |
|
643 |
public void remove() { |
644 |
if (lastRet < 0) |
645 |
throw new IllegalStateException(); |
646 |
checkForComodification(); |
647 |
|
648 |
try {
|
649 |
ArrayListOfLong.this.remove(lastRet); |
650 |
cursor = lastRet; |
651 |
lastRet = -1;
|
652 |
expectedModCount = modCount; |
653 |
} catch (IndexOutOfBoundsException ex) { |
654 |
throw new ConcurrentModificationException(); |
655 |
} |
656 |
} |
657 |
|
658 |
@Override
|
659 |
@SuppressWarnings("unchecked") |
660 |
public void forEachRemaining(Consumer<? super Long> consumer) { |
661 |
Objects.requireNonNull(consumer); |
662 |
final int size = ArrayListOfLong.this.size; |
663 |
int i = cursor;
|
664 |
if (i >= size) {
|
665 |
return;
|
666 |
} |
667 |
final long[] elementData = ArrayListOfLong.this.elementData; |
668 |
if (i >= elementData.length) {
|
669 |
throw new ConcurrentModificationException(); |
670 |
} |
671 |
while (i != size && modCount == expectedModCount) {
|
672 |
consumer.accept((Long) elementData[i++]);
|
673 |
} |
674 |
// update once at end of iteration to reduce heap write traffic
|
675 |
cursor = i; |
676 |
lastRet = i - 1;
|
677 |
checkForComodification(); |
678 |
} |
679 |
|
680 |
final void checkForComodification() { |
681 |
if (modCount != expectedModCount)
|
682 |
throw new ConcurrentModificationException(); |
683 |
} |
684 |
} |
685 |
|
686 |
/**
|
687 |
* An optimized version of AbstractList.ListItr
|
688 |
*/
|
689 |
private class ListItr extends Itr implements ListIterator<Long> { |
690 |
ListItr(int index) {
|
691 |
super();
|
692 |
cursor = index; |
693 |
} |
694 |
|
695 |
public boolean hasPrevious() { |
696 |
return cursor != 0; |
697 |
} |
698 |
|
699 |
public int nextIndex() { |
700 |
return cursor;
|
701 |
} |
702 |
|
703 |
public int previousIndex() { |
704 |
return cursor - 1; |
705 |
} |
706 |
|
707 |
@SuppressWarnings("unchecked") |
708 |
public Long previous() { |
709 |
checkForComodification(); |
710 |
int i = cursor - 1; |
711 |
if (i < 0) |
712 |
throw new NoSuchElementException(); |
713 |
long[] elementData = ArrayListOfLong.this.elementData; |
714 |
if (i >= elementData.length)
|
715 |
throw new ConcurrentModificationException(); |
716 |
cursor = i; |
717 |
return (Long) elementData[lastRet = i]; |
718 |
} |
719 |
|
720 |
public void set(Long e) { |
721 |
if (lastRet < 0) |
722 |
throw new IllegalStateException(); |
723 |
checkForComodification(); |
724 |
|
725 |
try {
|
726 |
ArrayListOfLong.this.set(lastRet, e); |
727 |
} catch (IndexOutOfBoundsException ex) { |
728 |
throw new ConcurrentModificationException(); |
729 |
} |
730 |
} |
731 |
|
732 |
public void add(Long e) { |
733 |
checkForComodification(); |
734 |
|
735 |
try {
|
736 |
int i = cursor;
|
737 |
ArrayListOfLong.this.add(i, e); |
738 |
cursor = i + 1;
|
739 |
lastRet = -1;
|
740 |
expectedModCount = modCount; |
741 |
} catch (IndexOutOfBoundsException ex) { |
742 |
throw new ConcurrentModificationException(); |
743 |
} |
744 |
} |
745 |
} |
746 |
|
747 |
/**
|
748 |
* Returns a view of the portion of this list between the specified
|
749 |
* {@code fromIndex}, inclusive, and {@code toIndex}, exclusive. (If
|
750 |
* {@code fromIndex} and {@code toIndex} are equal, the returned list is
|
751 |
* empty.) The returned list is backed by this list, so non-structural
|
752 |
* changes in the returned list are reflected in this list, and vice-versa.
|
753 |
* The returned list supports all of the optional list operations.
|
754 |
*
|
755 |
* <p>This method eliminates the need for explicit range operations (of
|
756 |
* the sort that commonly exist for arrays). Any operation that expects
|
757 |
* a list can be used as a range operation by passing a subList view
|
758 |
* instead of a whole list. For example, the following idiom
|
759 |
* removes a range of elements from a list:
|
760 |
* <pre>
|
761 |
* list.subList(from, to).clear();
|
762 |
* </pre>
|
763 |
* Similar idioms may be constructed for {@link #indexOf(Object)} and
|
764 |
* {@link #lastIndexOf(Object)}, and all of the algorithms in the
|
765 |
* {@link Collections} class can be applied to a subList.
|
766 |
*
|
767 |
* <p>The semantics of the list returned by this method become undefined if
|
768 |
* the backing list (i.e., this list) is <i>structurally modified</i> in
|
769 |
* any way other than via the returned list. (Structural modifications are
|
770 |
* those that change the size of this list, or otherwise perturb it in such
|
771 |
* a fashion that iterations in progress may yield incorrect results.)
|
772 |
*
|
773 |
* @throws IndexOutOfBoundsException {@inheritDoc}
|
774 |
* @throws IllegalArgumentException {@inheritDoc}
|
775 |
*/
|
776 |
public List<Long> subList(int fromIndex, int toIndex) { |
777 |
subListRangeCheck(fromIndex, toIndex, size); |
778 |
return new SubList(this, 0, fromIndex, toIndex); |
779 |
} |
780 |
|
781 |
static void subListRangeCheck(int fromIndex, int toIndex, int size) { |
782 |
if (fromIndex < 0) |
783 |
throw new IndexOutOfBoundsException("fromIndex = " + fromIndex); |
784 |
if (toIndex > size)
|
785 |
throw new IndexOutOfBoundsException("toIndex = " + toIndex); |
786 |
if (fromIndex > toIndex)
|
787 |
throw new IllegalArgumentException("fromIndex(" + fromIndex + |
788 |
") > toIndex(" + toIndex + ")"); |
789 |
} |
790 |
|
791 |
private class SubList extends ArrayListOfLong implements RandomAccess { |
792 |
private final ArrayListOfLong parent; |
793 |
private final int parentOffset; |
794 |
private final int offset; |
795 |
int size;
|
796 |
|
797 |
SubList(ArrayListOfLong parent, |
798 |
int offset, int fromIndex, int toIndex) { |
799 |
this.parent = parent;
|
800 |
this.parentOffset = fromIndex;
|
801 |
this.offset = offset + fromIndex;
|
802 |
this.size = toIndex - fromIndex;
|
803 |
this.modCount = ArrayListOfLong.this.modCount;
|
804 |
} |
805 |
|
806 |
public Long set(int index, Long e) { |
807 |
rangeCheck(index); |
808 |
checkForComodification(); |
809 |
Long oldValue = ArrayListOfLong.this.elementData(offset + index);
|
810 |
ArrayListOfLong.this.elementData[offset + index] = e; |
811 |
return oldValue;
|
812 |
} |
813 |
|
814 |
public Long get(int index) { |
815 |
rangeCheck(index); |
816 |
checkForComodification(); |
817 |
return ArrayListOfLong.this.elementData(offset + index);
|
818 |
} |
819 |
|
820 |
public int size() { |
821 |
checkForComodification(); |
822 |
return this.size; |
823 |
} |
824 |
|
825 |
public void add(int index, Long e) { |
826 |
rangeCheckForAdd(index); |
827 |
checkForComodification(); |
828 |
parent.add(parentOffset + index, e); |
829 |
this.modCount = parent.modCount;
|
830 |
this.size++;
|
831 |
} |
832 |
|
833 |
public Long remove(int index) { |
834 |
rangeCheck(index); |
835 |
checkForComodification(); |
836 |
Long result = parent.remove(parentOffset + index);
|
837 |
this.modCount = parent.modCount;
|
838 |
this.size--;
|
839 |
return result;
|
840 |
} |
841 |
|
842 |
protected void removeRange(int fromIndex, int toIndex) { |
843 |
checkForComodification(); |
844 |
parent.removeRange(parentOffset + fromIndex, |
845 |
parentOffset + toIndex); |
846 |
this.modCount = parent.modCount;
|
847 |
this.size -= toIndex - fromIndex;
|
848 |
} |
849 |
|
850 |
public boolean addAll(Collection<? extends Long> c) { |
851 |
return addAll(this.size, c); |
852 |
} |
853 |
|
854 |
public boolean addAll(int index, Collection<? extends Long> c) { |
855 |
rangeCheckForAdd(index); |
856 |
int cSize = c.size();
|
857 |
if (cSize==0) |
858 |
return false; |
859 |
|
860 |
checkForComodification(); |
861 |
parent.addAll(parentOffset + index, c); |
862 |
this.modCount = parent.modCount;
|
863 |
this.size += cSize;
|
864 |
return true; |
865 |
} |
866 |
|
867 |
public Iterator<Long> iterator() { |
868 |
return listIterator();
|
869 |
} |
870 |
|
871 |
public ListIterator<Long> listIterator(final int index) { |
872 |
checkForComodification(); |
873 |
rangeCheckForAdd(index); |
874 |
final int offset = this.offset; |
875 |
|
876 |
return new ListIterator<Long>() { |
877 |
int cursor = index;
|
878 |
int lastRet = -1; |
879 |
int expectedModCount = ArrayListOfLong.this.modCount;
|
880 |
|
881 |
public boolean hasNext() { |
882 |
return cursor != SubList.this.size;
|
883 |
} |
884 |
|
885 |
@SuppressWarnings("unchecked") |
886 |
public Long next() { |
887 |
checkForComodification(); |
888 |
int i = cursor;
|
889 |
if (i >= SubList.this.size)
|
890 |
throw new NoSuchElementException(); |
891 |
long[] elementData = ArrayListOfLong.this.elementData; |
892 |
if (offset + i >= elementData.length)
|
893 |
throw new ConcurrentModificationException(); |
894 |
cursor = i + 1;
|
895 |
return (Long) elementData[offset + (lastRet = i)]; |
896 |
} |
897 |
|
898 |
public boolean hasPrevious() { |
899 |
return cursor != 0; |
900 |
} |
901 |
|
902 |
@SuppressWarnings("unchecked") |
903 |
public Long previous() { |
904 |
checkForComodification(); |
905 |
int i = cursor - 1; |
906 |
if (i < 0) |
907 |
throw new NoSuchElementException(); |
908 |
long[] elementData = ArrayListOfLong.this.elementData; |
909 |
if (offset + i >= elementData.length)
|
910 |
throw new ConcurrentModificationException(); |
911 |
cursor = i; |
912 |
return (Long) elementData[offset + (lastRet = i)]; |
913 |
} |
914 |
|
915 |
@SuppressWarnings("unchecked") |
916 |
public void forEachRemaining(Consumer<? super Long> consumer) { |
917 |
Objects.requireNonNull(consumer); |
918 |
final int size = SubList.this.size; |
919 |
int i = cursor;
|
920 |
if (i >= size) {
|
921 |
return;
|
922 |
} |
923 |
final long[] elementData = ArrayListOfLong.this.elementData; |
924 |
if (offset + i >= elementData.length) {
|
925 |
throw new ConcurrentModificationException(); |
926 |
} |
927 |
while (i != size && modCount == expectedModCount) {
|
928 |
consumer.accept((Long) elementData[offset + (i++)]);
|
929 |
} |
930 |
// update once at end of iteration to reduce heap write traffic
|
931 |
lastRet = cursor = i; |
932 |
checkForComodification(); |
933 |
} |
934 |
|
935 |
public int nextIndex() { |
936 |
return cursor;
|
937 |
} |
938 |
|
939 |
public int previousIndex() { |
940 |
return cursor - 1; |
941 |
} |
942 |
|
943 |
public void remove() { |
944 |
if (lastRet < 0) |
945 |
throw new IllegalStateException(); |
946 |
checkForComodification(); |
947 |
|
948 |
try {
|
949 |
SubList.this.remove(lastRet); |
950 |
cursor = lastRet; |
951 |
lastRet = -1;
|
952 |
expectedModCount = ArrayListOfLong.this.modCount; |
953 |
} catch (IndexOutOfBoundsException ex) { |
954 |
throw new ConcurrentModificationException(); |
955 |
} |
956 |
} |
957 |
|
958 |
public void set(Long e) { |
959 |
if (lastRet < 0) |
960 |
throw new IllegalStateException(); |
961 |
checkForComodification(); |
962 |
|
963 |
try {
|
964 |
ArrayListOfLong.this.set(offset + lastRet, e); |
965 |
} catch (IndexOutOfBoundsException ex) { |
966 |
throw new ConcurrentModificationException(); |
967 |
} |
968 |
} |
969 |
|
970 |
public void add(Long e) { |
971 |
checkForComodification(); |
972 |
|
973 |
try {
|
974 |
int i = cursor;
|
975 |
SubList.this.add(i, e); |
976 |
cursor = i + 1;
|
977 |
lastRet = -1;
|
978 |
expectedModCount = ArrayListOfLong.this.modCount; |
979 |
} catch (IndexOutOfBoundsException ex) { |
980 |
throw new ConcurrentModificationException(); |
981 |
} |
982 |
} |
983 |
|
984 |
final void checkForComodification() { |
985 |
if (expectedModCount != ArrayListOfLong.this.modCount)
|
986 |
throw new ConcurrentModificationException(); |
987 |
} |
988 |
}; |
989 |
} |
990 |
|
991 |
public List<Long> subList(int fromIndex, int toIndex) { |
992 |
subListRangeCheck(fromIndex, toIndex, size); |
993 |
return new SubList(this, offset, fromIndex, toIndex); |
994 |
} |
995 |
|
996 |
private void rangeCheck(int index) { |
997 |
if (index < 0 || index >= this.size) |
998 |
throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); |
999 |
} |
1000 |
|
1001 |
private void rangeCheckForAdd(int index) { |
1002 |
if (index < 0 || index > this.size) |
1003 |
throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); |
1004 |
} |
1005 |
|
1006 |
private String outOfBoundsMsg(int index) { |
1007 |
return "Index: "+index+", Size: "+this.size; |
1008 |
} |
1009 |
|
1010 |
private void checkForComodification() { |
1011 |
if (ArrayListOfLong.this.modCount != this.modCount) |
1012 |
throw new ConcurrentModificationException(); |
1013 |
} |
1014 |
|
1015 |
public Spliterator<Long> spliterator() { |
1016 |
checkForComodification(); |
1017 |
return new ArrayListSpliterator(ArrayListOfLong.this, offset, |
1018 |
offset + this.size, this.modCount); |
1019 |
} |
1020 |
} |
1021 |
|
1022 |
@Override
|
1023 |
public void forEach(Consumer<? super Long> action) { |
1024 |
Objects.requireNonNull(action); |
1025 |
final int expectedModCount = modCount; |
1026 |
@SuppressWarnings("unchecked") |
1027 |
final long[] elementData = this.elementData; |
1028 |
final int size = this.size; |
1029 |
for (int i=0; modCount == expectedModCount && i < size; i++) { |
1030 |
action.accept(elementData[i]); |
1031 |
} |
1032 |
if (modCount != expectedModCount) {
|
1033 |
throw new ConcurrentModificationException(); |
1034 |
} |
1035 |
} |
1036 |
|
1037 |
/**
|
1038 |
* Creates a <em><a href="Spliterator.html#binding">late-binding</a></em>
|
1039 |
* and <em>fail-fast</em> {@link Spliterator} over the elements in this
|
1040 |
* list.
|
1041 |
*
|
1042 |
* <p>The {@code Spliterator} reports {@link Spliterator#SIZED},
|
1043 |
* {@link Spliterator#SUBSIZED}, and {@link Spliterator#ORDERED}.
|
1044 |
* Overriding implementations should document the reporting of additional
|
1045 |
* characteristic values.
|
1046 |
*
|
1047 |
* @return a {@code Spliterator} over the elements in this list
|
1048 |
* @since 1.8
|
1049 |
*/
|
1050 |
@Override
|
1051 |
public Spliterator<Long> spliterator() { |
1052 |
return new ArrayListSpliterator(this, 0, -1, 0); |
1053 |
} |
1054 |
|
1055 |
static final class ArrayListSpliterator implements Spliterator<Long> { |
1056 |
private final ArrayListOfLong list; |
1057 |
private int index; // current index, modified on advance/split |
1058 |
private int fence; // -1 until used; then one past last index |
1059 |
private int expectedModCount; // initialized when fence set |
1060 |
|
1061 |
/** Create new spliterator covering the given range */
|
1062 |
ArrayListSpliterator(ArrayListOfLong list, int origin, int fence, |
1063 |
int expectedModCount) {
|
1064 |
this.list = list; // OK if null unless traversed |
1065 |
this.index = origin;
|
1066 |
this.fence = fence;
|
1067 |
this.expectedModCount = expectedModCount;
|
1068 |
} |
1069 |
|
1070 |
private int getFence() { // initialize fence to size on first use |
1071 |
int hi; // (a specialized variant appears in method forEach) |
1072 |
ArrayListOfLong lst; |
1073 |
if ((hi = fence) < 0) { |
1074 |
if ((lst = list) == null) |
1075 |
hi = fence = 0;
|
1076 |
else {
|
1077 |
expectedModCount = lst.modCount; |
1078 |
hi = fence = lst.size; |
1079 |
} |
1080 |
} |
1081 |
return hi;
|
1082 |
} |
1083 |
|
1084 |
public ArrayListSpliterator trySplit() {
|
1085 |
int hi = getFence(), lo = index, mid = (lo + hi) >>> 1; |
1086 |
return (lo >= mid) ? null : // divide range in half unless too small |
1087 |
new ArrayListSpliterator(list, lo, index = mid,
|
1088 |
expectedModCount); |
1089 |
} |
1090 |
|
1091 |
public boolean tryAdvance(Consumer<? super Long> action) { |
1092 |
if (action == null) |
1093 |
throw new NullPointerException(); |
1094 |
int hi = getFence(), i = index;
|
1095 |
if (i < hi) {
|
1096 |
index = i + 1;
|
1097 |
Long e = list.elementData[i];
|
1098 |
action.accept(e); |
1099 |
if (list.modCount != expectedModCount)
|
1100 |
throw new ConcurrentModificationException(); |
1101 |
return true; |
1102 |
} |
1103 |
return false; |
1104 |
} |
1105 |
|
1106 |
public void forEachRemaining(Consumer<? super Long> action) { |
1107 |
int i, hi, mc; // hoist accesses and checks from loop |
1108 |
ArrayListOfLong lst; long[] a; |
1109 |
if (action == null) |
1110 |
throw new NullPointerException(); |
1111 |
if ((lst = list) != null && (a = lst.elementData) != null) { |
1112 |
if ((hi = fence) < 0) { |
1113 |
mc = lst.modCount; |
1114 |
hi = lst.size; |
1115 |
} |
1116 |
else
|
1117 |
mc = expectedModCount; |
1118 |
if ((i = index) >= 0 && (index = hi) <= a.length) { |
1119 |
for (; i < hi; ++i) {
|
1120 |
action.accept(a[i]); |
1121 |
} |
1122 |
if (lst.modCount == mc)
|
1123 |
return;
|
1124 |
} |
1125 |
} |
1126 |
throw new ConcurrentModificationException(); |
1127 |
} |
1128 |
|
1129 |
public long estimateSize() { |
1130 |
return (long) (getFence() - index); |
1131 |
} |
1132 |
|
1133 |
public int characteristics() { |
1134 |
return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED;
|
1135 |
} |
1136 |
} |
1137 |
|
1138 |
@Override
|
1139 |
public boolean removeIf(Predicate<? super Long> filter) { |
1140 |
Objects.requireNonNull(filter); |
1141 |
// figure out which elements are to be removed
|
1142 |
// any exception thrown from the filter predicate at this stage
|
1143 |
// will leave the collection unmodified
|
1144 |
int removeCount = 0; |
1145 |
final BitSet removeSet = new BitSet(size); |
1146 |
final int expectedModCount = modCount; |
1147 |
final int size = this.size; |
1148 |
for (int i=0; modCount == expectedModCount && i < size; i++) { |
1149 |
@SuppressWarnings("unchecked") |
1150 |
final Long element = (Long) elementData[i]; |
1151 |
if (filter.test(element)) {
|
1152 |
removeSet.set(i); |
1153 |
removeCount++; |
1154 |
} |
1155 |
} |
1156 |
if (modCount != expectedModCount) {
|
1157 |
throw new ConcurrentModificationException(); |
1158 |
} |
1159 |
|
1160 |
// shift surviving elements left over the spaces left by removed elements
|
1161 |
final boolean anyToRemove = removeCount > 0; |
1162 |
if (anyToRemove) {
|
1163 |
final int newSize = size - removeCount; |
1164 |
for (int i=0, j=0; (i < size) && (j < newSize); i++, j++) { |
1165 |
i = removeSet.nextClearBit(i); |
1166 |
elementData[j] = elementData[i]; |
1167 |
} |
1168 |
this.size = newSize;
|
1169 |
if (modCount != expectedModCount) {
|
1170 |
throw new ConcurrentModificationException(); |
1171 |
} |
1172 |
modCount++; |
1173 |
} |
1174 |
|
1175 |
return anyToRemove;
|
1176 |
} |
1177 |
|
1178 |
@Override
|
1179 |
@SuppressWarnings("unchecked") |
1180 |
public void replaceAll(UnaryOperator<Long> operator) { |
1181 |
Objects.requireNonNull(operator); |
1182 |
final int expectedModCount = modCount; |
1183 |
final int size = this.size; |
1184 |
for (int i=0; modCount == expectedModCount && i < size; i++) { |
1185 |
elementData[i] = operator.apply((Long) elementData[i]);
|
1186 |
} |
1187 |
if (modCount != expectedModCount) {
|
1188 |
throw new ConcurrentModificationException(); |
1189 |
} |
1190 |
modCount++; |
1191 |
} |
1192 |
|
1193 |
@Override
|
1194 |
@SuppressWarnings("unchecked") |
1195 |
public void sort(Comparator<? super Long> c) { |
1196 |
final int expectedModCount = modCount; |
1197 |
Arrays.sort(elementData);
|
1198 |
// Arrays.sort(elementData, 0, size, c);
|
1199 |
if (modCount != expectedModCount) {
|
1200 |
throw new ConcurrentModificationException(); |
1201 |
} |
1202 |
modCount++; |
1203 |
} |
1204 |
|
1205 |
} |