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