/* Vector.java -- Class that provides growable arrays.
   Copyright (C) 1998, 1999, 2000, 2001, 2004, 2005  Free Software Foundation, Inc.

This file is part of GNU Classpath.

GNU Classpath is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2, or (at your option)
any later version.

GNU Classpath is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
General Public License for more details.

You should have received a copy of the GNU General Public License
along with GNU Classpath; see the file COPYING.  If not, write to the
Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
02110-1301 USA.

Linking this library statically or dynamically with other modules is
making a combined work based on this library.  Thus, the terms and
conditions of the GNU General Public License cover the whole
combination.

As a special exception, the copyright holders of this library give you
permission to link this library with independent modules to produce an
executable, regardless of the license terms of these independent
modules, and to copy and distribute the resulting executable under
terms of your choice, provided that you also meet, for each linked
independent module, the terms and conditions of the license of that
module.  An independent module is a module which is not derived from
or based on this library.  If you modify this library, you may extend
this exception to your version of the library, but you are not
obligated to do so.  If you do not wish to do so, delete this
exception statement from your version. */


package java.util;

/**
 * The <code>Vector</code> classes implements growable arrays of Objects.
 * You can access elements in a Vector with an index, just as you
 * can in a built in array, but Vectors can grow and shrink to accommodate
 * more or fewer objects.<p>
 *
 * Vectors try to mantain efficiency in growing by having a
 * <code>capacityIncrement</code> that can be specified at instantiation.
 * When a Vector can no longer hold a new Object, it grows by the amount
 * in <code>capacityIncrement</code>. If this value is 0, the vector doubles in
 * size.<p>
 *
 * Vector implements the JDK 1.2 List interface, and is therefore a fully
 * compliant Collection object. The Vector class is fully synchronized, but the
 * iterators are not. So, when iterating over a vector, be sure to synchronize
 * on the vector itself.  If you don't want the expense of synchronization, use
 * ArrayList instead. On the other hand, the Enumeration of elements() is not
 * thread-safe, nor is it fail-fast; so it can lead to undefined behavior even
 * in a single thread if you modify the vector during iteration.<p>
 *
 * Note: Some methods, especially those specified by List, specify throwing
 * <code>IndexOutOfBoundsException</code>, but it is easier to implement by
 * throwing the subclass <code>ArrayIndexOutOfBoundsException</code>. Others
 * directly specify this subclass.
 *
 * @author Scott G. Miller
 * @author Bryce McKinlay
 * @author Eric Blake (ebb9@email.byu.edu)
 */
public class Vector extends Object
{
    /**
     * The internal array used to hold members of a Vector. The elements are
     * in positions 0 through elementCount - 1, and all remaining slots are null.
     */
    protected Object[] elementData;

    /**
     * The number of elements currently in the vector, also returned by
     * {@link #size}.
     */
    protected int elementCount;

    /**
     * The amount the Vector's internal array should be increased in size when
     * a new element is added that exceeds the current size of the array,
     * or when {@link #ensureCapacity} is called. If &lt;= 0, the vector just
     * doubles in size.
     */
    protected int capacityIncrement;

    /**
     * Constructs an empty vector with an initial size of 10, and
     * a capacity increment of 0
     */
    public Vector()
    {
        this(10, 0);
    }

    /**
     * Constructs a Vector with the initial capacity specified, and a capacity
     * increment of 0 (double in size).
     *
     * @param initialCapacity the initial size of the Vector's internal array
     * @throws IllegalArgumentException if initialCapacity &lt; 0
     */
    public Vector(int initialCapacity)
    {
        this(initialCapacity, 0);
    }

    /**
     * Constructs a Vector with the initial capacity and capacity
     * increment specified.
     *
     * @param initialCapacity the initial size of the Vector's internal array
     * @param capacityIncrement the amount the internal array should be
     *        increased by when necessary, 0 to double the size
     * @throws IllegalArgumentException if initialCapacity &lt; 0
     */
    public Vector(int initialCapacity, int capacityIncrement)
    {
        if (initialCapacity < 0)
            throw new IllegalArgumentException();

        elementData = new Object[initialCapacity];
        this.capacityIncrement = capacityIncrement;
    }

    /**
     * Copies the contents of the Vector into the provided array.  If the
     * array is too small to fit all the elements in the Vector, an 
     * <code>IndexOutOfBoundsException</code> is thrown without modifying the
     * array.  
     * Old elements in the array are overwritten by the new elements.
     *
     * @param a target array for the copy
     * @throws IndexOutOfBoundsException the array is not large enough
     * @throws NullPointerException the array is null
     */
    public synchronized void copyInto(Object[] a)
    {
        System.arraycopy(elementData, 0, a, 0, elementCount);
    }

    /**
     * Trims the Vector down to size.  If the internal data array is larger
     * than the number of Objects its holding, a new array is constructed
     * that precisely holds the elements. Otherwise this does nothing.
     */
    public synchronized void trimToSize()
    {
        // Don't bother checking for the case where size() == the capacity of the
        // vector since that is a much less likely case; it's more efficient to
        // not do the check and lose a bit of performance in that infrequent case

        Object[] newArray = new Object[elementCount];
        System.arraycopy(elementData, 0, newArray, 0, elementCount);
        elementData = newArray;
    }

    /**
     * Ensures that <code>minCapacity</code> elements can fit within this Vector.
     * If <code>elementData</code> is too small, it is expanded as follows:
     * If the <code>elementCount + capacityIncrement</code> is adequate, that
     * is the new size. If <code>capacityIncrement</code> is non-zero, the
     * candidate size is double the current. If that is not enough, the new
     * size is <code>minCapacity</code>.
     *
     * @param minCapacity the desired minimum capacity, negative values ignored
     */
    public synchronized void ensureCapacity(int minCapacity)
    {
        if (elementData.length >= minCapacity)
            return;

        int newCapacity;
    
        if (capacityIncrement <= 0)
            newCapacity = elementData.length * 2;
        else
            newCapacity = elementData.length + capacityIncrement;

        Object[] newArray = new Object[Math.max(newCapacity, minCapacity)];

        System.arraycopy(elementData, 0, newArray, 0, elementCount);
        elementData = newArray;
    }

    /**
     * Explicitly sets the size of the vector (but not necessarily the size of
     * the internal data array). If the new size is smaller than the old one,
     * old values that don't fit are lost. If the new size is larger than the
     * old one, the vector is padded with null entries.
     *
     * @param newSize The new size of the internal array
     * @throws ArrayIndexOutOfBoundsException if the new size is negative
     */
    public synchronized void setSize(int newSize)
    {
        // Don't bother checking for the case where size() == the capacity of the
        // vector since that is a much less likely case; it's more efficient to
        // not do the check and lose a bit of performance in that infrequent case
        ensureCapacity(newSize);
      
        if (newSize < elementCount)
        {
            for (int i = newSize; i < elementCount; i++)
                elementData[i] = null;
        } /* if */
     
        elementCount = newSize;
    }

    /**
     * Returns the size of the internal data array (not the amount of elements
     * contained in the Vector).
     *
     * @return capacity of the internal data array
     */
    public synchronized int capacity()
    {
        return elementData.length;
    }

    /**
     * Returns the number of elements stored in this Vector.
     *
     * @return the number of elements in this Vector
     */
    public synchronized int size()
    {
        return elementCount;
    }

    /**
     * Returns true if this Vector is empty, false otherwise
     *
     * @return true if the Vector is empty, false otherwise
     */
    public synchronized boolean isEmpty()
    {
        return elementCount == 0;
    }

    /**
     * Returns an Enumeration of the elements of this Vector. The enumeration
     * visits the elements in increasing index order, but is NOT thread-safe.
     *
     * @returns an Enumeration
     */
     // No need to synchronize as the Enumeration is not thread-safe!
    public Enumeration elements()
    {
        return new Enumeration()
        {
            private int i = 0;

            public boolean hasMoreElements()
            {
                return i < elementCount;
            }

            public Object nextElement()
            {
                if (i >= elementCount)
                    throw new NoSuchElementException();
        
                return elementData[i++];
            }
        };
    }

    /**
     * Returns true when <code>elem</code> is contained in this Vector.
     *
     * @param elem the element to check
     * @return true if the object is contained in this Vector, false otherwise
     */
    public boolean contains(Object elem)
    {
        return indexOf(elem, 0) >= 0;
    }

    /**
     * Returns the first occurrence of <code>elem</code> in the Vector, or -1 if
     * <code>elem</code> is not found.
     *
     * @param elem the object to search for
     * @return the index of the first occurrence, or -1 if not found
     */
    public int indexOf(Object elem)
    {
        return indexOf(elem, 0);
    }

    /**
     * Searches the vector starting at <code>index</code> for object
     * <code>elem</code> and returns the index of the first occurrence of this
     * Object.  If the object is not found, or index is larger than the size
     * of the vector, -1 is returned.
     *
     * @param e the Object to search for
     * @param index start searching at this index
     * @return the index of the next occurrence, or -1 if it is not found
     */
    public synchronized int indexOf(Object e, int index)
    {
        for (int i = index; i < elementCount; i++)
            if (e.equals(elementData[i]))
                return i;

       return -1;
    }

    /**
     * Returns the last index of <code>elem</code> within this Vector, or -1
     * if the object is not within the Vector.
     *
     * @param elem the object to search for
     * @return the last index of the object, or -1 if not found
     */
    public int lastIndexOf(Object elem)
    {
        return lastIndexOf(elem, elementCount - 1);
    }

    /**
     * Returns the index of the first occurrence of <code>elem</code>, when
     * searching backwards from <code>index</code>.  If the object does not
     * occur in this Vector, or index is less than 0, -1 is returned.
     *
     * @param e the object to search for
     * @param index the index to start searching in reverse from
     * @return the index of the Object if found, -1 otherwise
     * @throws IndexOutOfBoundsException if index &gt;= size()
     */
    public synchronized int lastIndexOf(Object e, int index)
        throws IndexOutOfBoundsException
    {
        checkBoundExclusive(index);

        for (int i = index; i >= 0; i--)
            if (e.equals(elementData[i]))
                return i;
    
        return -1;
    }

    /**
     * Returns the Object stored at <code>index</code>.
     *
     * @param index the index of the Object to retrieve
     * @return the object at <code>index</code>
     * @throws ArrayIndexOutOfBoundsException index &lt; 0 || index &gt;= size()
     */
    public synchronized Object elementAt(int index)
        throws ArrayIndexOutOfBoundsException
    {
        checkBoundExclusive(index);
      
        return elementData[index];
    }

    /**
     * Returns the first element (index 0) in the Vector.
     *
     * @return the first Object in the Vector
     * @throws NoSuchElementException the Vector is empty
     */
    public synchronized Object firstElement()
    {
        if (elementCount == 0)
            throw new NoSuchElementException();

        return elementData[0];
    }

    /**
     * Returns the last element in the Vector.
     *
     * @return the last Object in the Vector
     * @throws NoSuchElementException the Vector is empty
     */
    public synchronized Object lastElement()
    {
        if (elementCount == 0)
            throw new NoSuchElementException();

        return elementData[elementCount - 1];
    }

    /**
     * Changes the element at <code>index</code> to be <code>obj</code>
     *
     * @param obj the object to store
     * @param index the position in the Vector to store the object
     * @throws ArrayIndexOutOfBoundsException the index is out of range
     */
    public void setElementAt(Object obj, int index)
    {
        set(index, obj);
    }

    /**
     * Removes the element at <code>index</code>, and shifts all elements at
     * positions greater than index to their index - 1.
     *
     * @param index the index of the element to remove
     * @throws ArrayIndexOutOfBoundsException index &lt; 0 || index &gt;= size();
     */
    public void removeElementAt(int index)
    {
        remove(index);
    }

    /**
     * Inserts a new element into the Vector at <code>index</code>.  Any elements
     * at or greater than index are shifted up one position.
     *
     * @param obj the object to insert
     * @param index the index at which the object is inserted
     * @throws ArrayIndexOutOfBoundsException index &lt; 0 || index &gt; size()
     */
    public synchronized void insertElementAt(Object obj, int index)
    {
        checkBoundInclusive(index);
      
        if (elementCount == elementData.length)
            ensureCapacity(elementCount + 1);
  
        System.arraycopy(elementData, index, elementData, index + 1,
            elementCount - index);
        elementCount++;
        elementData[index] = obj;
    }

    /**
     * Adds an element to the Vector at the end of the Vector.  The vector
     * is increased by ensureCapacity(size() + 1) if needed.
     *
     * @param obj the object to add to the Vector
     */
    public synchronized void addElement(Object obj)
    {
        if (elementCount == elementData.length)
            ensureCapacity(elementCount + 1);
   
        elementData[elementCount++] = obj;
    }

    /**
     * Removes the first (the lowestindex) occurance of the given object from
     * the Vector. If such a remove was performed (the object was found), true
     * is returned. If there was no such object, false is returned.
     *
     * @param obj the object to remove from the Vector
     * @return true if the Object was in the Vector, false otherwise
     */
    public synchronized boolean removeElement(Object obj)
    {
        int idx = indexOf(obj, 0);
      
        if (idx >= 0)
        {
            remove(idx);
            return true;
        }
      
        return false;
    }

    /**
     * Removes all elements from the Vector.  Note that this does not
     * resize the internal data array.
     */
    public synchronized void removeAllElements()
    {
        if (elementCount == 0)
            return;

        for (int i = 0; i < elementCount; i++)
            elementData[i] = null;

        elementCount = 0;
    }

    /**
     * Puts <code>element</code> into the Vector at position <code>index</code>
     * and returns the Object that previously occupied that position.
     *
     * @param index the index within the Vector to place the Object
     * @param element the Object to store in the Vector
     * @return the previous object at the specified index
     * @throws ArrayIndexOutOfBoundsException index &lt; 0 || index &gt;= size()
     * @since 1.2
     */
    private synchronized Object set(int index, Object element)
    {
        checkBoundExclusive(index);
        Object temp = elementData[index];
        elementData[index] = element;
        return temp;
    }

    /**
     * Removes the element at the specified index, and returns it.
     *
     * @param index the position from which to remove the element
     * @return the object removed
     * @throws ArrayIndexOutOfBoundsException index &lt; 0 || index &gt;= size()
     * @since 1.2
     */
    private synchronized Object remove(int index)
    {
        checkBoundExclusive(index);
        Object temp = elementData[index];
        elementCount--;

        if (index < elementCount)
        {
            System.arraycopy(elementData, index + 1, elementData, index,
                 elementCount - index);
        }
    
        elementData[elementCount] = null;

        return temp;
    }

    /**
     * Returns a string representation of this Vector in the form
     * "[element0, element1, ... elementN]".
     *
     * @return the String representation of this Vector
     */
    public synchronized String toString()
    {
        // Here just for the sychronization.
        return super.toString();
    }

    /**
     * Checks that the index is in the range of possible elements (inclusive).
     *
     * @param index the index to check
     * @throws ArrayIndexOutOfBoundsException if index &gt; size
     */
    private void checkBoundInclusive(int index)
    {
        // Implementation note: we do not check for negative ranges here, since
        // use of a negative index will cause an ArrayIndexOutOfBoundsException
        // with no effort on our part.
        if (index > elementCount)
            throw new ArrayIndexOutOfBoundsException(
                index + " > " + elementCount
                );
    }

    /**
     * Checks that the index is in the range of existing elements (exclusive).
     *
     * @param index the index to check
     * @throws ArrayIndexOutOfBoundsException if index &gt;= size
     */
    private void checkBoundExclusive(int index)
    {
        // Implementation note: we do not check for negative ranges here, since
        // use of a negative index will cause an ArrayIndexOutOfBoundsException
        // with no effort on our part.
        if (index >= elementCount)
            throw new ArrayIndexOutOfBoundsException(
                index + " >= " + elementCount
                );
    }
}
