vector.java

赫夫曼编译码器： 用哈夫曼编码进行通信可以大大提高信道利用率

// An implementation of extensible arrays.
// (c) 1998, 2001 duane a. bailey

package structure;
import java.util.Iterator;
import java.util.Collection;

/**
 * An implementation of extensible arrays, similar to that of {@link java.util.Vector java.util.Vector}.
 *
 * This vector class implements a basic extensible array.  It does not implement
 * any of the additional features of the Sun class, including list-like operations.
 * Those operations are available in other implementors of {@link List} in this
 * package.
 * <p>
 * Example usage:
 *
 * To put a program's parameters into a Vector, we would use the following:
 * <pre>
 * public static void main(String[] arguments)
 * {
 *    {@link Vector} argVec = new {@link #Vector()};
 *    for (int i = 0; i < arguments.length; i++)
 *    {
 *       argVec.{@link #add(Object) add(arguments[i])};
 *    }
 *    System.out.println({@link #toString argVec});
 * }
 * </pre>
 *
 * @version $Id: Vector.java,v 4.1 2000/12/29 02:25:16 bailey Exp bailey $
 * @since JavaStructures 1.0
 */
public class Vector extends AbstractList implements Cloneable
{
    /**
     * The data associated with the vector.  The size of the
     * array is always at least as large as the vector.  The array
     * is only extended when necessary.
     */
    protected Object elementData[];	// the data
    /**
     * The actual number of elements logically stored within the
     * vector.  May be smaller than the actual length of the array.
     */
    protected int elementCount;		// number of elements in vector
    /**
     * The size of size increment, should the vector become full.
     * 0 indicates the vector should be doubled when capacity of
     * the array is reached.
     */
    protected int capacityIncrement;	// the rate of growth for vector
    /**
     * The initial value of any new elements that are appended to the
     * vector.  Normally null.  Be aware that references used in this
     * way will result in multiple references to a single object.
     */
    protected Object initialValue;	// new elements have this value
    /**
     * The default size of the vector; may be overridden in
     * the {@link #Vector(int)} constructor.
     */
    protected final static int defaultCapacity = 10; // def't capacity, must be>0

    /**
     * Construct an empty vector.
     * 
     * @post constructs a vector with capacity for 10 elements
     */
    public Vector()
    {
	this(10); // call one-parameter constructor
    }
    
    /**
     * Construct an empty vector capable of storing <code>initialCapacity</code>
     * values before the vector must be extended.
     *
     * @pre initialCapacity >= 0
     * @post constructs an empty vector with initialCapacity capacity
     * @param initialCapacity The size of vector before reallocation is necessary
     */
    public Vector(int initialCapacity)
    {
	Assert.pre(initialCapacity >= 0,"Nonnegative capacity.");
	elementData = new Object[initialCapacity];
	elementCount = 0;
	capacityIncrement = 0;
	initialValue = null;
    }

    /**
     * Construct a vector with initial capacity, and growth characteristic.
     *
     * @pre initialCapacity >= 0, capacityIncr >= 0
     * @post constructs an empty vector with initialCapacity capacity
     *    that extends capacity by capacityIncr, or doubles if 0
     * 
     * @param initialCapacity The initial number of slots in vector.
     * @param capacityIncr The size of growth of vector.
     * @see #capacityIncrement
     */
    public Vector(int initialCapacity, int capacityIncr)
    {
	Assert.pre(initialCapacity >= 0, "Nonnegative capacity.");
	elementData = new Object[initialCapacity];
	elementCount = 0;
	capacityIncrement = capacityIncr;
	initialValue = null;
    }

    /**
     * Construct a vector with initial size, growth rate and default
     * value.
     *
     * @pre initialCapacity, capacityIncr >= 0
     * @post constructs empty vector with capacity that begins at
     *       initialCapacity and extends by capacityIncr or doubles
     *       if 0.  New entries in vector are initialized to initValue.
     * 
     * @param initialCapacity The initial number of slots in vector.
     * @param capacityIncr The size of the increment when vector grows.
     * @param initValue The initial value stored in vector elements.
     */
    public Vector(int initialCapacity, int capacityIncr, Object initValue)
    {
	Assert.pre(initialCapacity >= 0, "Nonnegative capacity.");
	capacityIncrement = capacityIncr;
	elementData = new Object[initialCapacity];
	elementCount = 0;
	initialValue = initValue;
    }
    
    public Vector(Vector that)
    {
	this(that.values());
    }

    public Vector(Collection c)
    {
	this(c.size());
	Iterator i = c.iterator();
	int pos = 0;
	while (i.hasNext())
	{
	    set(pos++,i.next());
	}
    }


    /**
     * Ensure that the vector is capable of holding at least
     * minCapacity values without expansion.
     *
     * @post the capacity of this vector is at least minCapacity
     * 
     * @param minCapacity The minimum size of array before expansion.
     */
    public void ensureCapacity(int minCapacity)
    {
	if (elementData.length < minCapacity) {
	    int newLength = elementData.length; // initial guess
	    if (capacityIncrement == 0) {
		// increment of 0 suggests doubling (default)
		if (newLength == 0) newLength = 1;
		while (newLength < minCapacity) {
		    newLength *= 2;
		}
	    } else {
		// increment != 0 suggests incremental increase
		while (newLength < minCapacity)
		{
		    newLength += capacityIncrement;
		}
	    }
	    // assertion: newLength > elementData.length.
    	    Object newElementData[] = new Object[newLength];
	    int i;
	    // copy old data to array
	    for (i = 0; i < elementCount; i++) {
		newElementData[i] = elementData[i];
	    }
	    elementData = newElementData;
	    // garbage collector will (eventually) pick up old elementData
	}
	// assertion: capacity is at least minCapacity
    }

    /**
     * Add an element to the high end of the array, possibly expanding
     * vector.
     *
     * @post adds new element to end of possibly extended vector
     * 
     * @param obj The object to be added to the end of the vector.
     */
    public void add(Object obj)
    {
	ensureCapacity(elementCount+1);
	elementData[elementCount] = obj;
	elementCount++;
    }
    
    /**
     * Add an element to the high end of the array, possibly expanding
     * vector.
     *
     * @post adds new element to end of possibly extended vector
     * 
     * @param obj The object to be added to the end of the vector.
     */
    public void addElement(Object o)
    {
	add(o);
    }
    
    /**
     * Remove an element, by value, from vector.
     *
     * @post element equal to parameter is removed and returned
     * @param element the element to be removed.
     * @return the element actually removed, or if none, null.
     */
    public Object remove(Object element)
    {
	Object result = null;
	int i = indexOf(element);
	if (i >= 0)
	{
	    result = get(i);
	    remove(i);
	}
	return result;
    }

    /**
     * Determine the capacity of the vector.  The capacity is always
     * at least as large as its size.
     *
     * @post returns allocated size of the vector
     * 
     * @return The size of the array underlying the vector.
     */
    public int capacity()
    {
	return elementData.length;
    }

    /**
     * Construct a shallow copy of the vector.  The vector
     * store is copied, but the individual elements are shared
     * objects.
     *
     * @post returns a copy of the vector, using same objects
     * 
     * @return A copy of the original vector.
     */
    public Object clone()
    {
	Vector copy = null;
	try {
	    copy = (Vector)super.clone();
	    copy.elementData = (Object[])elementData.clone();
	} catch (java.lang.CloneNotSupportedException e) { Assert.fail("Vector cannot be cloned."); }
	return copy;
    }

    /**
     * Determine if a value appears in a vector.
     *
     * @post returns true iff Vector contains the value
     *       (could be faster, if orderedVector is used)
     * 
     * @param elem The value sought.
     * @return True iff the value appears in the vector.
     */
    public boolean contains(Object elem)
    {
	int i;
	for (i = 0; i < elementCount; i++) {
	    if (elem.equals(elementData[i])) return true;
	}
	return false;
    }

    /**
     * Copy the contents of the vector into an array.
     * The array must be large enough to accept all the values in
     * the vector.
     *
     * @pre dest has at least size() elements
     * @post a copy of the vector is stored in the dest array
     * 
     * @param dest An array of size at least size(). 
     */
    public void copyInto(Object dest[])
    {
	int i;
	for (i = 0; i < elementCount; i++) {
	    dest[i] = elementData[i];
	}
    }

    /**
     * Fetch the element at a particular index.
     * The index of the first element is zero.
     *
     * @pre 0 <= index && index < size()
     * @post returns the element stored in location index
     * 
     * @param index The index of the value sought.
     * @return A reference to the value found in the vector.
     */
    public Object elementAt(int index)
    {
	return get(index);
    }


    /**
     * Fetch the element at a particular index.
     * The index of the first element is zero.
     *
     * @pre 0 <= index && index < size()
     * @post returns the element stored in location index
     * 
     * @param index The index of the value sought.
     * @return A reference to the value found in the vector.
     */
    public Object get(int index)
    {
	return elementData[index];
    }

    /**
     * Construct a iterator over the elements of the vector.
     * The iterator considers elements with increasing
     * index.
     *
     * @post returns an iterator allowing one to
     *       view elements of vector
     * @return an iterator to traverse the vector.
     */
    public Iterator iterator()
    {
	return new VectorIterator(this);
    }

    /**
     * Get access to the first element of the vector.