1 /*
2 * Copyright (c) 1994, 2011, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation. Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25
26 package java.util;
27
28 import java.util.function.Block;
29 import java.util.function.Predicate;
30 import java.util.function.UnaryOperator;
31
32 /**
33 * The {@code Vector} class implements a growable array of
34 * objects. Like an array, it contains components that can be
35 * accessed using an integer index. However, the size of a
36 * {@code Vector} can grow or shrink as needed to accommodate
37 * adding and removing items after the {@code Vector} has been created.
38 *
39 * <p>Each vector tries to optimize storage management by maintaining a
40 * {@code capacity} and a {@code capacityIncrement}. The
41 * {@code capacity} is always at least as large as the vector
42 * size; it is usually larger because as components are added to the
43 * vector, the vector's storage increases in chunks the size of
44 * {@code capacityIncrement}. An application can increase the
45 * capacity of a vector before inserting a large number of
46 * components; this reduces the amount of incremental reallocation.
47 *
48 * <p><a name="fail-fast"/>
49 * The iterators returned by this class's {@link #iterator() iterator} and
50 * {@link #listIterator(int) listIterator} methods are <em>fail-fast</em>:
51 * if the vector is structurally modified at any time after the iterator is
52 * created, in any way except through the iterator's own
53 * {@link ListIterator#remove() remove} or
54 * {@link ListIterator#add(Object) add} methods, the iterator will throw a
55 * {@link ConcurrentModificationException}. Thus, in the face of
56 * concurrent modification, the iterator fails quickly and cleanly, rather
57 * than risking arbitrary, non-deterministic behavior at an undetermined
58 * time in the future. The {@link Enumeration Enumerations} returned by
59 * the {@link #elements() elements} method are <em>not</em> fail-fast.
60 *
61 * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
62 * as it is, generally speaking, impossible to make any hard guarantees in the
63 * presence of unsynchronized concurrent modification. Fail-fast iterators
64 * throw {@code ConcurrentModificationException} on a best-effort basis.
65 * Therefore, it would be wrong to write a program that depended on this
66 * exception for its correctness: <i>the fail-fast behavior of iterators
67 * should be used only to detect bugs.</i>
68 *
69 * <p>As of the Java 2 platform v1.2, this class was retrofitted to
70 * implement the {@link List} interface, making it a member of the
71 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
72 * Java Collections Framework</a>. Unlike the new collection
73 * implementations, {@code Vector} is synchronized. If a thread-safe
74 * implementation is not needed, it is recommended to use {@link
75 * ArrayList} in place of {@code Vector}.
76 *
77 * @author Lee Boynton
78 * @author Jonathan Payne
79 * @see Collection
80 * @see LinkedList
81 * @since JDK1.0
82 */
83 public class Vector<E>
84 extends AbstractList<E>
85 implements List<E>, RandomAccess, Cloneable, java.io.Serializable
86 {
87 /**
88 * The array buffer into which the components of the vector are
89 * stored. The capacity of the vector is the length of this array buffer,
90 * and is at least large enough to contain all the vector's elements.
91 *
92 * <p>Any array elements following the last element in the Vector are null.
93 *
94 * @serial
95 */
96 protected Object[] elementData;
97
98 /**
99 * The number of valid components in this {@code Vector} object.
100 * Components {@code elementData[0]} through
101 * {@code elementData[elementCount-1]} are the actual items.
102 *
103 * @serial
104 */
105 protected int elementCount;
106
107 /**
108 * The amount by which the capacity of the vector is automatically
109 * incremented when its size becomes greater than its capacity. If
110 * the capacity increment is less than or equal to zero, the capacity
111 * of the vector is doubled each time it needs to grow.
112 *
113 * @serial
114 */
115 protected int capacityIncrement;
116
117 /** use serialVersionUID from JDK 1.0.2 for interoperability */
118 private static final long serialVersionUID = -2767605614048989439L;
119
120 /**
121 * Constructs an empty vector with the specified initial capacity and
122 * capacity increment.
123 *
124 * @param initialCapacity the initial capacity of the vector
125 * @param capacityIncrement the amount by which the capacity is
126 * increased when the vector overflows
127 * @throws IllegalArgumentException if the specified initial capacity
128 * is negative
129 */
130 public Vector(int initialCapacity, int capacityIncrement) {
131 super();
132 if (initialCapacity < 0)
133 throw new IllegalArgumentException("Illegal Capacity: "+
134 initialCapacity);
135 this.elementData = new Object[initialCapacity];
136 this.capacityIncrement = capacityIncrement;
137 }
138
139 /**
140 * Constructs an empty vector with the specified initial capacity and
141 * with its capacity increment equal to zero.
142 *
143 * @param initialCapacity the initial capacity of the vector
144 * @throws IllegalArgumentException if the specified initial capacity
145 * is negative
146 */
147 public Vector(int initialCapacity) {
148 this(initialCapacity, 0);
149 }
150
151 /**
152 * Constructs an empty vector so that its internal data array
153 * has size {@code 10} and its standard capacity increment is
154 * zero.
155 */
156 public Vector() {
157 this(10);
158 }
159
160 /**
161 * Constructs a vector containing the elements of the specified
162 * collection, in the order they are returned by the collection's
163 * iterator.
164 *
165 * @param c the collection whose elements are to be placed into this
166 * vector
167 * @throws NullPointerException if the specified collection is null
168 * @since 1.2
169 */
170 public Vector(Collection<? extends E> c) {
171 elementData = c.toArray();
172 elementCount = elementData.length;
173 // c.toArray might (incorrectly) not return Object[] (see 6260652)
174 if (elementData.getClass() != Object[].class)
175 elementData = Arrays.copyOf(elementData, elementCount, Object[].class);
176 }
177
178 /**
179 * Copies the components of this vector into the specified array.
180 * The item at index {@code k} in this vector is copied into
181 * component {@code k} of {@code anArray}.
182 *
183 * @param anArray the array into which the components get copied
184 * @throws NullPointerException if the given array is null
185 * @throws IndexOutOfBoundsException if the specified array is not
186 * large enough to hold all the components of this vector
187 * @throws ArrayStoreException if a component of this vector is not of
188 * a runtime type that can be stored in the specified array
189 * @see #toArray(Object[])
190 */
191 public synchronized void copyInto(Object[] anArray) {
192 System.arraycopy(elementData, 0, anArray, 0, elementCount);
193 }
194
195 /**
196 * Trims the capacity of this vector to be the vector's current
197 * size. If the capacity of this vector is larger than its current
198 * size, then the capacity is changed to equal the size by replacing
199 * its internal data array, kept in the field {@code elementData},
200 * with a smaller one. An application can use this operation to
201 * minimize the storage of a vector.
202 */
203 public synchronized void trimToSize() {
204 modCount++;
205 int oldCapacity = elementData.length;
206 if (elementCount < oldCapacity) {
207 elementData = Arrays.copyOf(elementData, elementCount);
208 }
209 }
210
211 /**
212 * Increases the capacity of this vector, if necessary, to ensure
213 * that it can hold at least the number of components specified by
214 * the minimum capacity argument.
215 *
216 * <p>If the current capacity of this vector is less than
217 * {@code minCapacity}, then its capacity is increased by replacing its
218 * internal data array, kept in the field {@code elementData}, with a
219 * larger one. The size of the new data array will be the old size plus
220 * {@code capacityIncrement}, unless the value of
221 * {@code capacityIncrement} is less than or equal to zero, in which case
222 * the new capacity will be twice the old capacity; but if this new size
223 * is still smaller than {@code minCapacity}, then the new capacity will
224 * be {@code minCapacity}.
225 *
226 * @param minCapacity the desired minimum capacity
227 */
228 public synchronized void ensureCapacity(int minCapacity) {
229 if (minCapacity > 0) {
230 modCount++;
231 ensureCapacityHelper(minCapacity);
232 }
233 }
234
235 /**
236 * This implements the unsynchronized semantics of ensureCapacity.
237 * Synchronized methods in this class can internally call this
238 * method for ensuring capacity without incurring the cost of an
239 * extra synchronization.
240 *
241 * @see #ensureCapacity(int)
242 */
243 private void ensureCapacityHelper(int minCapacity) {
244 // overflow-conscious code
245 if (minCapacity - elementData.length > 0)
246 grow(minCapacity);
247 }
248
249 /**
250 * The maximum size of array to allocate.
251 * Some VMs reserve some header words in an array.
252 * Attempts to allocate larger arrays may result in
253 * OutOfMemoryError: Requested array size exceeds VM limit
254 */
255 private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
256
257 private void grow(int minCapacity) {
258 // overflow-conscious code
259 int oldCapacity = elementData.length;
260 int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
261 capacityIncrement : oldCapacity);
262 if (newCapacity - minCapacity < 0)
263 newCapacity = minCapacity;
264 if (newCapacity - MAX_ARRAY_SIZE > 0)
265 newCapacity = hugeCapacity(minCapacity);
266 elementData = Arrays.copyOf(elementData, newCapacity);
267 }
268
269 private static int hugeCapacity(int minCapacity) {
270 if (minCapacity < 0) // overflow
271 throw new OutOfMemoryError();
272 return (minCapacity > MAX_ARRAY_SIZE) ?
273 Integer.MAX_VALUE :
274 MAX_ARRAY_SIZE;
275 }
276
277 /**
278 * Sets the size of this vector. If the new size is greater than the
279 * current size, new {@code null} items are added to the end of
280 * the vector. If the new size is less than the current size, all
281 * components at index {@code newSize} and greater are discarded.
282 *
283 * @param newSize the new size of this vector
284 * @throws ArrayIndexOutOfBoundsException if the new size is negative
285 */
286 public synchronized void setSize(int newSize) {
287 modCount++;
288 if (newSize > elementCount) {
289 ensureCapacityHelper(newSize);
290 } else {
291 for (int i = newSize ; i < elementCount ; i++) {
292 elementData[i] = null;
293 }
294 }
295 elementCount = newSize;
296 }
297
298 /**
299 * Returns the current capacity of this vector.
300 *
301 * @return the current capacity (the length of its internal
302 * data array, kept in the field {@code elementData}
303 * of this vector)
304 */
305 public synchronized int capacity() {
306 return elementData.length;
307 }
308
309 /**
310 * Returns the number of components in this vector.
311 *
312 * @return the number of components in this vector
313 */
314 public synchronized int size() {
315 return elementCount;
316 }
317
318 /**
319 * Tests if this vector has no components.
320 *
321 * @return {@code true} if and only if this vector has
322 * no components, that is, its size is zero;
323 * {@code false} otherwise.
324 */
325 public synchronized boolean isEmpty() {
326 return elementCount == 0;
327 }
328
329 /**
330 * Returns an enumeration of the components of this vector. The
331 * returned {@code Enumeration} object will generate all items in
332 * this vector. The first item generated is the item at index {@code 0},
333 * then the item at index {@code 1}, and so on.
334 *
335 * @return an enumeration of the components of this vector
336 * @see Iterator
337 */
338 public Enumeration<E> elements() {
339 return new Enumeration<E>() {
340 int count = 0;
341
342 public boolean hasMoreElements() {
343 return count < elementCount;
344 }
345
346 public E nextElement() {
347 synchronized (Vector.this) {
348 if (count < elementCount) {
349 return elementData(count++);
350 }
351 }
352 throw new NoSuchElementException("Vector Enumeration");
353 }
354 };
355 }
356
357 /**
358 * Returns {@code true} if this vector contains the specified element.
359 * More formally, returns {@code true} if and only if this vector
360 * contains at least one element {@code e} such that
361 * <tt>(o==null ? e==null : o.equals(e))</tt>.
362 *
363 * @param o element whose presence in this vector is to be tested
364 * @return {@code true} if this vector contains the specified element
365 */
366 public boolean contains(Object o) {
367 return indexOf(o, 0) >= 0;
368 }
369
370 /**
371 * Returns the index of the first occurrence of the specified element
372 * in this vector, or -1 if this vector does not contain the element.
373 * More formally, returns the lowest index {@code i} such that
374 * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>,
375 * or -1 if there is no such index.
376 *
377 * @param o element to search for
378 * @return the index of the first occurrence of the specified element in
379 * this vector, or -1 if this vector does not contain the element
380 */
381 public int indexOf(Object o) {
382 return indexOf(o, 0);
383 }
384
385 /**
386 * Returns the index of the first occurrence of the specified element in
387 * this vector, searching forwards from {@code index}, or returns -1 if
388 * the element is not found.
389 * More formally, returns the lowest index {@code i} such that
390 * <tt>(i >= index && (o==null ? get(i)==null : o.equals(get(i))))</tt>,
391 * or -1 if there is no such index.
392 *
393 * @param o element to search for
394 * @param index index to start searching from
395 * @return the index of the first occurrence of the element in
396 * this vector at position {@code index} or later in the vector;
397 * {@code -1} if the element is not found.
398 * @throws IndexOutOfBoundsException if the specified index is negative
399 * @see Object#equals(Object)
400 */
401 public synchronized int indexOf(Object o, int index) {
402 if (o == null) {
403 for (int i = index ; i < elementCount ; i++)
404 if (elementData[i]==null)
405 return i;
406 } else {
407 for (int i = index ; i < elementCount ; i++)
408 if (o.equals(elementData[i]))
409 return i;
410 }
411 return -1;
412 }
413
414 /**
415 * Returns the index of the last occurrence of the specified element
416 * in this vector, or -1 if this vector does not contain the element.
417 * More formally, returns the highest index {@code i} such that
418 * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>,
419 * or -1 if there is no such index.
420 *
421 * @param o element to search for
422 * @return the index of the last occurrence of the specified element in
423 * this vector, or -1 if this vector does not contain the element
424 */
425 public synchronized int lastIndexOf(Object o) {
426 return lastIndexOf(o, elementCount-1);
427 }
428
429 /**
430 * Returns the index of the last occurrence of the specified element in
431 * this vector, searching backwards from {@code index}, or returns -1 if
432 * the element is not found.
433 * More formally, returns the highest index {@code i} such that
434 * <tt>(i <= index && (o==null ? get(i)==null : o.equals(get(i))))</tt>,
435 * or -1 if there is no such index.
436 *
437 * @param o element to search for
438 * @param index index to start searching backwards from
439 * @return the index of the last occurrence of the element at position
440 * less than or equal to {@code index} in this vector;
441 * -1 if the element is not found.
442 * @throws IndexOutOfBoundsException if the specified index is greater
443 * than or equal to the current size of this vector
444 */
445 public synchronized int lastIndexOf(Object o, int index) {
446 if (index >= elementCount)
447 throw new IndexOutOfBoundsException(index + " >= "+ elementCount);
448
449 if (o == null) {
450 for (int i = index; i >= 0; i--)
451 if (elementData[i]==null)
452 return i;
453 } else {
454 for (int i = index; i >= 0; i--)
455 if (o.equals(elementData[i]))
456 return i;
457 }
458 return -1;
459 }
460
461 /**
462 * Returns the component at the specified index.
463 *
464 * <p>This method is identical in functionality to the {@link #get(int)}
465 * method (which is part of the {@link List} interface).
466 *
467 * @param index an index into this vector
468 * @return the component at the specified index
469 * @throws ArrayIndexOutOfBoundsException if the index is out of range
470 * ({@code index < 0 || index >= size()})
471 */
472 public synchronized E elementAt(int index) {
473 if (index >= elementCount) {
474 throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount);
475 }
476
477 return elementData(index);
478 }
479
480 /**
481 * Returns the first component (the item at index {@code 0}) of
482 * this vector.
483 *
484 * @return the first component of this vector
485 * @throws NoSuchElementException if this vector has no components
486 */
487 public synchronized E firstElement() {
488 if (elementCount == 0) {
489 throw new NoSuchElementException();
490 }
491 return elementData(0);
492 }
493
494 /**
495 * Returns the last component of the vector.
496 *
497 * @return the last component of the vector, i.e., the component at index
498 * <code>size() - 1</code>.
499 * @throws NoSuchElementException if this vector is empty
500 */
501 public synchronized E lastElement() {
502 if (elementCount == 0) {
503 throw new NoSuchElementException();
504 }
505 return elementData(elementCount - 1);
506 }
507
508 /**
509 * Sets the component at the specified {@code index} of this
510 * vector to be the specified object. The previous component at that
511 * position is discarded.
512 *
513 * <p>The index must be a value greater than or equal to {@code 0}
514 * and less than the current size of the vector.
515 *
516 * <p>This method is identical in functionality to the
517 * {@link #set(int, Object) set(int, E)}
518 * method (which is part of the {@link List} interface). Note that the
519 * {@code set} method reverses the order of the parameters, to more closely
520 * match array usage. Note also that the {@code set} method returns the
521 * old value that was stored at the specified position.
522 *
523 * @param obj what the component is to be set to
524 * @param index the specified index
525 * @throws ArrayIndexOutOfBoundsException if the index is out of range
526 * ({@code index < 0 || index >= size()})
527 */
528 public synchronized void setElementAt(E obj, int index) {
529 if (index >= elementCount) {
530 throw new ArrayIndexOutOfBoundsException(index + " >= " +
531 elementCount);
532 }
533 elementData[index] = obj;
534 }
535
536 /**
537 * Deletes the component at the specified index. Each component in
538 * this vector with an index greater or equal to the specified
539 * {@code index} is shifted downward to have an index one
540 * smaller than the value it had previously. The size of this vector
541 * is decreased by {@code 1}.
542 *
543 * <p>The index must be a value greater than or equal to {@code 0}
544 * and less than the current size of the vector.
545 *
546 * <p>This method is identical in functionality to the {@link #remove(int)}
547 * method (which is part of the {@link List} interface). Note that the
548 * {@code remove} method returns the old value that was stored at the
549 * specified position.
550 *
551 * @param index the index of the object to remove
552 * @throws ArrayIndexOutOfBoundsException if the index is out of range
553 * ({@code index < 0 || index >= size()})
554 */
555 public synchronized void removeElementAt(int index) {
556 modCount++;
557 if (index >= elementCount) {
558 throw new ArrayIndexOutOfBoundsException(index + " >= " +
559 elementCount);
560 }
561 else if (index < 0) {
562 throw new ArrayIndexOutOfBoundsException(index);
563 }
564 int j = elementCount - index - 1;
565 if (j > 0) {
566 System.arraycopy(elementData, index + 1, elementData, index, j);
567 }
568 elementCount--;
569 elementData[elementCount] = null; /* to let gc do its work */
570 }
571
572 /**
573 * Inserts the specified object as a component in this vector at the
574 * specified {@code index}. Each component in this vector with
575 * an index greater or equal to the specified {@code index} is
576 * shifted upward to have an index one greater than the value it had
577 * previously.
578 *
579 * <p>The index must be a value greater than or equal to {@code 0}
580 * and less than or equal to the current size of the vector. (If the
581 * index is equal to the current size of the vector, the new element
582 * is appended to the Vector.)
583 *
584 * <p>This method is identical in functionality to the
585 * {@link #add(int, Object) add(int, E)}
586 * method (which is part of the {@link List} interface). Note that the
587 * {@code add} method reverses the order of the parameters, to more closely
588 * match array usage.
589 *
590 * @param obj the component to insert
591 * @param index where to insert the new component
592 * @throws ArrayIndexOutOfBoundsException if the index is out of range
593 * ({@code index < 0 || index > size()})
594 */
595 public synchronized void insertElementAt(E obj, int index) {
596 modCount++;
597 if (index > elementCount) {
598 throw new ArrayIndexOutOfBoundsException(index
599 + " > " + elementCount);
600 }
601 ensureCapacityHelper(elementCount + 1);
602 System.arraycopy(elementData, index, elementData, index + 1, elementCount - index);
603 elementData[index] = obj;
604 elementCount++;
605 }
606
607 /**
608 * Adds the specified component to the end of this vector,
609 * increasing its size by one. The capacity of this vector is
610 * increased if its size becomes greater than its capacity.
611 *
612 * <p>This method is identical in functionality to the
613 * {@link #add(Object) add(E)}
614 * method (which is part of the {@link List} interface).
615 *
616 * @param obj the component to be added
617 */
618 public synchronized void addElement(E obj) {
619 modCount++;
620 ensureCapacityHelper(elementCount + 1);
621 elementData[elementCount++] = obj;
622 }
623
624 /**
625 * Removes the first (lowest-indexed) occurrence of the argument
626 * from this vector. If the object is found in this vector, each
627 * component in the vector with an index greater or equal to the
628 * object's index is shifted downward to have an index one smaller
629 * than the value it had previously.
630 *
631 * <p>This method is identical in functionality to the
632 * {@link #remove(Object)} method (which is part of the
633 * {@link List} interface).
634 *
635 * @param obj the component to be removed
636 * @return {@code true} if the argument was a component of this
637 * vector; {@code false} otherwise.
638 */
639 public synchronized boolean removeElement(Object obj) {
640 modCount++;
641 int i = indexOf(obj);
642 if (i >= 0) {
643 removeElementAt(i);
644 return true;
645 }
646 return false;
647 }
648
649 /**
650 * Removes all components from this vector and sets its size to zero.
651 *
652 * <p>This method is identical in functionality to the {@link #clear}
653 * method (which is part of the {@link List} interface).
654 */
655 public synchronized void removeAllElements() {
656 modCount++;
657 // Let gc do its work
658 for (int i = 0; i < elementCount; i++)
659 elementData[i] = null;
660
661 elementCount = 0;
662 }
663
664 /**
665 * Returns a clone of this vector. The copy will contain a
666 * reference to a clone of the internal data array, not a reference
667 * to the original internal data array of this {@code Vector} object.
668 *
669 * @return a clone of this vector
670 */
671 public synchronized Object clone() {
672 try {
673 @SuppressWarnings("unchecked")
674 Vector<E> v = (Vector<E>) super.clone();
675 v.elementData = Arrays.copyOf(elementData, elementCount);
676 v.modCount = 0;
677 return v;
678 } catch (CloneNotSupportedException e) {
679 // this shouldn't happen, since we are Cloneable
680 throw new InternalError(e);
681 }
682 }
683
684 /**
685 * Returns an array containing all of the elements in this Vector
686 * in the correct order.
687 *
688 * @since 1.2
689 */
690 public synchronized Object[] toArray() {
691 return Arrays.copyOf(elementData, elementCount);
692 }
693
694 /**
695 * Returns an array containing all of the elements in this Vector in the
696 * correct order; the runtime type of the returned array is that of the
697 * specified array. If the Vector fits in the specified array, it is
698 * returned therein. Otherwise, a new array is allocated with the runtime
699 * type of the specified array and the size of this Vector.
700 *
701 * <p>If the Vector fits in the specified array with room to spare
702 * (i.e., the array has more elements than the Vector),
703 * the element in the array immediately following the end of the
704 * Vector is set to null. (This is useful in determining the length
705 * of the Vector <em>only</em> if the caller knows that the Vector
706 * does not contain any null elements.)
707 *
708 * @param a the array into which the elements of the Vector are to
709 * be stored, if it is big enough; otherwise, a new array of the
710 * same runtime type is allocated for this purpose.
711 * @return an array containing the elements of the Vector
712 * @throws ArrayStoreException if the runtime type of a is not a supertype
713 * of the runtime type of every element in this Vector
714 * @throws NullPointerException if the given array is null
715 * @since 1.2
716 */
717 @SuppressWarnings("unchecked")
718 public synchronized <T> T[] toArray(T[] a) {
719 if (a.length < elementCount)
720 return (T[]) Arrays.copyOf(elementData, elementCount, a.getClass());
721
722 System.arraycopy(elementData, 0, a, 0, elementCount);
723
724 if (a.length > elementCount)
725 a[elementCount] = null;
726
727 return a;
728 }
729
730 // Positional Access Operations
731
732 @SuppressWarnings("unchecked")
733 E elementData(int index) {
734 return (E) elementData[index];
735 }
736
737 /**
738 * Returns the element at the specified position in this Vector.
739 *
740 * @param index index of the element to return
741 * @return object at the specified index
742 * @throws ArrayIndexOutOfBoundsException if the index is out of range
743 * ({@code index < 0 || index >= size()})
744 * @since 1.2
745 */
746 public synchronized E get(int index) {
747 if (index >= elementCount)
748 throw new ArrayIndexOutOfBoundsException(index);
749
750 return elementData(index);
751 }
752
753 /**
754 * Replaces the element at the specified position in this Vector with the
755 * specified element.
756 *
757 * @param index index of the element to replace
758 * @param element element to be stored at the specified position
759 * @return the element previously at the specified position
760 * @throws ArrayIndexOutOfBoundsException if the index is out of range
761 * ({@code index < 0 || index >= size()})
762 * @since 1.2
763 */
764 public synchronized E set(int index, E element) {
765 if (index >= elementCount)
766 throw new ArrayIndexOutOfBoundsException(index);
767
768 E oldValue = elementData(index);
769 elementData[index] = element;
770 return oldValue;
771 }
772
773 /**
774 * Appends the specified element to the end of this Vector.
775 *
776 * @param e element to be appended to this Vector
777 * @return {@code true} (as specified by {@link Collection#add})
778 * @since 1.2
779 */
780 public synchronized boolean add(E e) {
781 modCount++;
782 ensureCapacityHelper(elementCount + 1);
783 elementData[elementCount++] = e;
784 return true;
785 }
786
787 /**
788 * Removes the first occurrence of the specified element in this Vector
789 * If the Vector does not contain the element, it is unchanged. More
790 * formally, removes the element with the lowest index i such that
791 * {@code (o==null ? get(i)==null : o.equals(get(i)))} (if such
792 * an element exists).
793 *
794 * @param o element to be removed from this Vector, if present
795 * @return true if the Vector contained the specified element
796 * @since 1.2
797 */
798 public boolean remove(Object o) {
799 return removeElement(o);
800 }
801
802 /**
803 * Inserts the specified element at the specified position in this Vector.
804 * Shifts the element currently at that position (if any) and any
805 * subsequent elements to the right (adds one to their indices).
806 *
807 * @param index index at which the specified element is to be inserted
808 * @param element element to be inserted
809 * @throws ArrayIndexOutOfBoundsException if the index is out of range
810 * ({@code index < 0 || index > size()})
811 * @since 1.2
812 */
813 public void add(int index, E element) {
814 insertElementAt(element, index);
815 }
816
817 /**
818 * Removes the element at the specified position in this Vector.
819 * Shifts any subsequent elements to the left (subtracts one from their
820 * indices). Returns the element that was removed from the Vector.
821 *
822 * @throws ArrayIndexOutOfBoundsException if the index is out of range
823 * ({@code index < 0 || index >= size()})
824 * @param index the index of the element to be removed
825 * @return element that was removed
826 * @since 1.2
827 */
828 public synchronized E remove(int index) {
829 modCount++;
830 if (index >= elementCount)
831 throw new ArrayIndexOutOfBoundsException(index);
832 E oldValue = elementData(index);
833
834 int numMoved = elementCount - index - 1;
835 if (numMoved > 0)
836 System.arraycopy(elementData, index+1, elementData, index,
837 numMoved);
838 elementData[--elementCount] = null; // Let gc do its work
839
840 return oldValue;
841 }
842
843 /**
844 * Removes all of the elements from this Vector. The Vector will
845 * be empty after this call returns (unless it throws an exception).
846 *
847 * @since 1.2
848 */
849 public void clear() {
850 removeAllElements();
851 }
852
853 // Bulk Operations
854
855 /**
856 * Returns true if this Vector contains all of the elements in the
857 * specified Collection.
858 *
859 * @param c a collection whose elements will be tested for containment
860 * in this Vector
861 * @return true if this Vector contains all of the elements in the
862 * specified collection
863 * @throws NullPointerException if the specified collection is null
864 */
865 public synchronized boolean containsAll(Collection<?> c) {
866 return super.containsAll(c);
867 }
868
869 /**
870 * Appends all of the elements in the specified Collection to the end of
871 * this Vector, in the order that they are returned by the specified
872 * Collection's Iterator. The behavior of this operation is undefined if
873 * the specified Collection is modified while the operation is in progress.
874 * (This implies that the behavior of this call is undefined if the
875 * specified Collection is this Vector, and this Vector is nonempty.)
876 *
877 * @param c elements to be inserted into this Vector
878 * @return {@code true} if this Vector changed as a result of the call
879 * @throws NullPointerException if the specified collection is null
880 * @since 1.2
881 */
882 public synchronized boolean addAll(Collection<? extends E> c) {
883 modCount++;
884 Object[] a = c.toArray();
885 int numNew = a.length;
886 ensureCapacityHelper(elementCount + numNew);
887 System.arraycopy(a, 0, elementData, elementCount, numNew);
888 elementCount += numNew;
889 return numNew != 0;
890 }
891
892 /**
893 * Removes from this Vector all of its elements that are contained in the
894 * specified Collection.
895 *
896 * @param c a collection of elements to be removed from the Vector
897 * @return true if this Vector changed as a result of the call
898 * @throws ClassCastException if the types of one or more elements
899 * in this vector are incompatible with the specified
900 * collection
901 * (<a href="Collection.html#optional-restrictions">optional</a>)
902 * @throws NullPointerException if this vector contains one or more null
903 * elements and the specified collection does not support null
904 * elements
905 * (<a href="Collection.html#optional-restrictions">optional</a>),
906 * or if the specified collection is null
907 * @since 1.2
908 */
909 public synchronized boolean removeAll(Collection<?> c) {
910 return super.removeAll(c);
911 }
912
913 /**
914 * Retains only the elements in this Vector that are contained in the
915 * specified Collection. In other words, removes from this Vector all
916 * of its elements that are not contained in the specified Collection.
917 *
918 * @param c a collection of elements to be retained in this Vector
919 * (all other elements are removed)
920 * @return true if this Vector changed as a result of the call
921 * @throws ClassCastException if the types of one or more elements
922 * in this vector are incompatible with the specified
923 * collection
924 * (<a href="Collection.html#optional-restrictions">optional</a>)
925 * @throws NullPointerException if this vector contains one or more null
926 * elements and the specified collection does not support null
927 * elements
928 * (<a href="Collection.html#optional-restrictions">optional</a>),
929 * or if the specified collection is null
930 * @since 1.2
931 */
932 public synchronized boolean retainAll(Collection<?> c) {
933 return super.retainAll(c);
934 }
935
936 /**
937 * Inserts all of the elements in the specified Collection into this
938 * Vector at the specified position. Shifts the element currently at
939 * that position (if any) and any subsequent elements to the right
940 * (increases their indices). The new elements will appear in the Vector
941 * in the order that they are returned by the specified Collection's
942 * iterator.
943 *
944 * @param index index at which to insert the first element from the
945 * specified collection
946 * @param c elements to be inserted into this Vector
947 * @return {@code true} if this Vector changed as a result of the call
948 * @throws ArrayIndexOutOfBoundsException if the index is out of range
949 * ({@code index < 0 || index > size()})
950 * @throws NullPointerException if the specified collection is null
951 * @since 1.2
952 */
953 public synchronized boolean addAll(int index, Collection<? extends E> c) {
954 modCount++;
955 if (index < 0 || index > elementCount)
956 throw new ArrayIndexOutOfBoundsException(index);
957
958 Object[] a = c.toArray();
959 int numNew = a.length;
960 ensureCapacityHelper(elementCount + numNew);
961
962 int numMoved = elementCount - index;
963 if (numMoved > 0)
964 System.arraycopy(elementData, index, elementData, index + numNew,
965 numMoved);
966
967 System.arraycopy(a, 0, elementData, index, numNew);
968 elementCount += numNew;
969 return numNew != 0;
970 }
971
972 /**
973 * Compares the specified Object with this Vector for equality. Returns
974 * true if and only if the specified Object is also a List, both Lists
975 * have the same size, and all corresponding pairs of elements in the two
976 * Lists are <em>equal</em>. (Two elements {@code e1} and
977 * {@code e2} are <em>equal</em> if {@code (e1==null ? e2==null :
978 * e1.equals(e2))}.) In other words, two Lists are defined to be
979 * equal if they contain the same elements in the same order.
980 *
981 * @param o the Object to be compared for equality with this Vector
982 * @return true if the specified Object is equal to this Vector
983 */
984 public synchronized boolean equals(Object o) {
985 return super.equals(o);
986 }
987
988 /**
989 * Returns the hash code value for this Vector.
990 */
991 public synchronized int hashCode() {
992 return super.hashCode();
993 }
994
995 /**
996 * Returns a string representation of this Vector, containing
997 * the String representation of each element.
998 */
999 public synchronized String toString() {
1000 return super.toString();
1001 }
1002
1003 /**
1004 * Returns a view of the portion of this List between fromIndex,
1005 * inclusive, and toIndex, exclusive. (If fromIndex and toIndex are
1006 * equal, the returned List is empty.) The returned List is backed by this
1007 * List, so changes in the returned List are reflected in this List, and
1008 * vice-versa. The returned List supports all of the optional List
1009 * operations supported by this List.
1010 *
1011 * <p>This method eliminates the need for explicit range operations (of
1012 * the sort that commonly exist for arrays). Any operation that expects
1013 * a List can be used as a range operation by operating on a subList view
1014 * instead of a whole List. For example, the following idiom
1015 * removes a range of elements from a List:
1016 * <pre>
1017 * list.subList(from, to).clear();
1018 * </pre>
1019 * Similar idioms may be constructed for indexOf and lastIndexOf,
1020 * and all of the algorithms in the Collections class can be applied to
1021 * a subList.
1022 *
1023 * <p>The semantics of the List returned by this method become undefined if
1024 * the backing list (i.e., this List) is <i>structurally modified</i> in
1025 * any way other than via the returned List. (Structural modifications are
1026 * those that change the size of the List, or otherwise perturb it in such
1027 * a fashion that iterations in progress may yield incorrect results.)
1028 *
1029 * @param fromIndex low endpoint (inclusive) of the subList
1030 * @param toIndex high endpoint (exclusive) of the subList
1031 * @return a view of the specified range within this List
1032 * @throws IndexOutOfBoundsException if an endpoint index value is out of range
1033 * {@code (fromIndex < 0 || toIndex > size)}
1034 * @throws IllegalArgumentException if the endpoint indices are out of order
1035 * {@code (fromIndex > toIndex)}
1036 */
1037 public synchronized List<E> subList(int fromIndex, int toIndex) {
1038 return Collections.synchronizedList(super.subList(fromIndex, toIndex),
1039 this);
1040 }
1041
1042 /**
1043 * Removes from this list all of the elements whose index is between
1044 * {@code fromIndex}, inclusive, and {@code toIndex}, exclusive.
1045 * Shifts any succeeding elements to the left (reduces their index).
1046 * This call shortens the list by {@code (toIndex - fromIndex)} elements.
1047 * (If {@code toIndex==fromIndex}, this operation has no effect.)
1048 */
1049 protected synchronized void removeRange(int fromIndex, int toIndex) {
1050 modCount++;
1051 int numMoved = elementCount - toIndex;
1052 System.arraycopy(elementData, toIndex, elementData, fromIndex,
1053 numMoved);
1054
1055 // Let gc do its work
1056 int newElementCount = elementCount - (toIndex-fromIndex);
1057 while (elementCount != newElementCount)
1058 elementData[--elementCount] = null;
1059 }
1060
1061 /**
1062 * Save the state of the {@code Vector} instance to a stream (that
1063 * is, serialize it).
1064 * This method performs synchronization to ensure the consistency
1065 * of the serialized data.
1066 */
1067 private void writeObject(java.io.ObjectOutputStream s)
1068 throws java.io.IOException {
1069 final java.io.ObjectOutputStream.PutField fields = s.putFields();
1070 final Object[] data;
1071 synchronized (this) {
1072 fields.put("capacityIncrement", capacityIncrement);
1073 fields.put("elementCount", elementCount);
1074 data = elementData.clone();
1075 }
1076 fields.put("elementData", data);
1077 s.writeFields();
1078 }
1079
1080 /**
1081 * Returns a list iterator over the elements in this list (in proper
1082 * sequence), starting at the specified position in the list.
1083 * The specified index indicates the first element that would be
1084 * returned by an initial call to {@link ListIterator#next next}.
1085 * An initial call to {@link ListIterator#previous previous} would
1086 * return the element with the specified index minus one.
1087 *
1088 * <p>The returned list iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
1089 *
1090 * @throws IndexOutOfBoundsException {@inheritDoc}
1091 */
1092 public synchronized ListIterator<E> listIterator(int index) {
1093 if (index < 0 || index > elementCount)
1094 throw new IndexOutOfBoundsException("Index: "+index);
1095 return new ListItr(index);
1096 }
1097
1098 /**
1099 * Returns a list iterator over the elements in this list (in proper
1100 * sequence).
1101 *
1102 * <p>The returned list iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
1103 *
1104 * @see #listIterator(int)
1105 */
1106 public synchronized ListIterator<E> listIterator() {
1107 return new ListItr(0);
1108 }
1109
1110 /**
1111 * Returns an iterator over the elements in this list in proper sequence.
1112 *
1113 * <p>The returned iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
1114 *
1115 * @return an iterator over the elements in this list in proper sequence
1116 */
1117 public synchronized Iterator<E> iterator() {
1118 return new Itr();
1119 }
1120
1121 /**
1122 * An optimized version of AbstractList.Itr
1123 */
1124 private class Itr implements Iterator<E> {
1125 int cursor; // index of next element to return
1126 int lastRet = -1; // index of last element returned; -1 if no such
1127 int expectedModCount = modCount;
1128
1129 public boolean hasNext() {
1130 // Racy but within spec, since modifications are checked
1131 // within or after synchronization in next/previous
1132 return cursor != elementCount;
1133 }
1134
1135 public E next() {
1136 synchronized (Vector.this) {
1137 checkForComodification();
1138 int i = cursor;
1139 if (i >= elementCount)
1140 throw new NoSuchElementException();
1141 cursor = i + 1;
1142 return elementData(lastRet = i);
1143 }
1144 }
1145
1146 public void remove() {
1147 if (lastRet == -1)
1148 throw new IllegalStateException();
1149 synchronized (Vector.this) {
1150 checkForComodification();
1151 Vector.this.remove(lastRet);
1152 expectedModCount = modCount;
1153 }
1154 cursor = lastRet;
1155 lastRet = -1;
1156 }
1157
1158 final void checkForComodification() {
1159 if (modCount != expectedModCount)
1160 throw new ConcurrentModificationException();
1161 }
1162 }
1163
1164 /**
1165 * An optimized version of AbstractList.ListItr
1166 */
1167 final class ListItr extends Itr implements ListIterator<E> {
1168 ListItr(int index) {
1169 super();
1170 cursor = index;
1171 }
1172
1173 public boolean hasPrevious() {
1174 return cursor != 0;
1175 }
1176
1177 public int nextIndex() {
1178 return cursor;
1179 }
1180
1181 public int previousIndex() {
1182 return cursor - 1;
1183 }
1184
1185 public E previous() {
1186 synchronized (Vector.this) {
1187 checkForComodification();
1188 int i = cursor - 1;
1189 if (i < 0)
1190 throw new NoSuchElementException();
1191 cursor = i;
1192 return elementData(lastRet = i);
1193 }
1194 }
1195
1196 public void set(E e) {
1197 if (lastRet == -1)
1198 throw new IllegalStateException();
1199 synchronized (Vector.this) {
1200 checkForComodification();
1201 Vector.this.set(lastRet, e);
1202 }
1203 }
1204
1205 public void add(E e) {
1206 int i = cursor;
1207 synchronized (Vector.this) {
1208 checkForComodification();
1209 Vector.this.add(i, e);
1210 expectedModCount = modCount;
1211 }
1212 cursor = i + 1;
1213 lastRet = -1;
1214 }
1215 }
1216
1217 @Override
1218 public synchronized void forEach(Block<? super E> block) {
1219 Objects.requireNonNull(block);
1220 final E[] elementData = (E[]) this.elementData;
1221 final int expectedModCount = modCount;
1222 final int size = elementCount;
1223 for (int i=0; modCount == expectedModCount && i < size; i++) {
1224 block.accept(elementData[i]);
1225 }
1226 if (modCount != expectedModCount) {
1227 throw new ConcurrentModificationException();
1228 }
1229 }
1230
1231 @Override
1232 @SuppressWarnings("unchecked")
1233 public synchronized boolean removeAll(Predicate<? super E> filter) {
1234 Objects.requireNonNull(filter);
1235 // figure out which elements are to be removed
1236 // any exception thrown from the filter predicate at this stage
1237 // will leave the collection unmodified
1238 int removeCount = 0;
1239 final int size = elementCount;
1240 final BitSet removeSet = new BitSet(size);
1241 final int expectedModCount = modCount;
1242 for (int i=0; modCount == expectedModCount && i < size; i++) {
1243 @SuppressWarnings("unchecked")
1244 final E element = (E) elementData[i];
1245 if (filter.test(element)) {
1246 removeSet.set(i);
1247 removeCount++;
1248 }
1249 }
1250
1251 if (modCount != expectedModCount) {
1252 throw new ConcurrentModificationException();
1253 }
1254
1255 // shift surviving elements left over the spaces left by removed elements
1256 final boolean anyToRemove = removeCount > 0;
1257 if (anyToRemove) {
1258 final int newSize = size - removeCount;
1259 for (int i=0, j=0; modCount == expectedModCount &&
1260 (i < size) && (j < newSize); i++, j++) {
1261 i = removeSet.nextClearBit(i);
1262 elementData[j] = elementData[i];
1263 }
1264 for (int k=newSize; modCount == expectedModCount && k < size; k++) {
1265 elementData[k] = null; // Let gc do its work
1266 }
1267 elementCount = newSize;
1268 if (modCount != expectedModCount) {
1269 throw new ConcurrentModificationException();
1270 }
1271 modCount++;
1272 }
1273
1274 return anyToRemove;
1275 }
1276
1277 @Override
1278 @SuppressWarnings("unchecked")
1279 public synchronized void replaceAll(UnaryOperator<E> operator) {
1280 Objects.requireNonNull(operator);
1281 final int expectedModCount = modCount;
1282 final int size = elementCount;
1283 for (int i=0; modCount == expectedModCount && i < size; i++) {
1284 elementData[i] = operator.operate((E) elementData[i]);
1285 }
1286 if (modCount != expectedModCount) {
1287 throw new ConcurrentModificationException();
1288 }
1289 modCount++;
1290 }
1291
1292 @Override
1293 @SuppressWarnings("unchecked")
1294 public synchronized void sort(Comparator<? super E> c) {
1295 Objects.requireNonNull(c);
1296 final int expectedModCount = modCount;
1297 Arrays.sort((E[]) elementData, 0, elementCount, c);
1298 if (modCount != expectedModCount) {
1299 throw new ConcurrentModificationException();
1300 }
1301 modCount++;
1302 }
1303 }