vector.java

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

     *
     * @pre vector contains an element
     * @post returns first value in vector
     * 
     * @return Access to the first element of the vector.
     */
    public Object firstElement()
    {
	return get(0);
    }

    /**
     * Assuming the data is not in order, find the index of a
     * value, or return -1 if not found.
     *
     * @post returns index of element equal to object, or -1; starts at 0
     * 
     * @param elem The value sought in vector.
     * @return The index of the first occurrence of the value.
     */
    public int indexOf(Object elem)
    {
	return indexOf(elem,0);
    }

    /**
     * Assuming the data is not in order, find the index of a value
     * or return -1 if the value is not found.  Search starts at index.
     *
     * @post returns index of element equal to object, or -1; starts at index
     * 
     * @param elem The value sought.
     * @param index The first location considered.
     * @return The index of the first location, or -1 if not found.
     */
    public int indexOf(Object elem, int index)
    {
	int i;
	for (i = index; i < elementCount; i++)
	{
	    if (elem.equals(elementData[i])) return i;
	}
	return -1;
    }

    /**
     * Insert an element at a particular location.
     * Vector is grown as needed
     *
     * @pre 0 <= index <= size()
     * @post inserts new value in vector with desired index,
     *   moving elements from index to size()-1 to right
     * 
     * @param obj The value to be inserted.
     * @param index The location of the new value.
     *
     */
    public void insertElementAt(Object obj, int index)
    {
	add(index,obj);
    }

    /**
     * Insert an element at a particular location.
     * Vector is grown as needed
     *
     * @pre 0 <= index <= size()
     * @post inserts new value in vector with desired index,
     *   moving elements from index to size()-1 to right
     * 
     * @param obj the value to be inserted.
     * @param index the location of the new value.
     */
    public void add(int index, Object obj)
    {
	int i;
	ensureCapacity(elementCount+1);
	// must copy from right to left to avoid destroying data
	for (i = elementCount; i > index; i--) {
	    elementData[i] = elementData[i-1];
	}
	// assertion: i == index and element[index] is available
	elementData[index] = obj;
	elementCount++;
    }
    /* A recursive version of insertion of element at
    public void add(int index, Object value)
    // pre: 0 <= index <= size()
    // post: inserts new value in vector with desired index
    //   moving elements from index to size()-1 to right
    {
        if (index >= size()) {
	    add(value); // base case: add at end
	} else {
    	    Object previous = get(index); // work
	    add(index+1,previous);  // progress through recursion
	    set(index,value);  // work
        }
    }
    */

    /**
     * Determine if the Vector contains no values.	
     *
     * @post returns true iff there are no elements in the vector
     * 
     * @return True iff the vector is empty.
     */
    public boolean isEmpty()
    {
	return size() == 0;
    }

    /**
     * Fetch a reference to the last value in the vector.
     *
     * @pre vector is not empty
     * @post returns last element of the vector
     * 
     * @return A reference to the last value.
     */
    public Object lastElement()
    {
	return get(elementCount-1);
    }

    /**
     * Search for the last occurrence of a value within the
     * vector.  If none is found, return -1.
     *
     * @post returns index of last occurrence of object in the vector, or -1
     * 
     * @param obj The value sought.
     * @return The index of the last occurrence in the vector.
     */
    public int lastIndexOf(Object obj)
    {
	return lastIndexOf(obj,elementCount-1);
    }

    /**
     * Find the index of the last occurrence of the value in the vector before
     * the indexth position.
     *
     * @pre index >= 0
     * @post returns the index of last occurrence of object at or before
     *       index
     * 
     * @param obj The value sought.
     * @param index The last acceptable index.
     * @return The index of the last occurrence of the value, or -1 if none.
     */
    public int lastIndexOf(Object obj, int index)
    {
	int i;
	for (i = index; i >= 0; i--) {
	    if (obj.equals(elementData[i])) return i;
	}
	return -1;
    }

    /**
     * Remove all the values of the vector.
     *
     * @post vector is empty
     */
    public void clear()
    {
	setSize(0);
    }

    /**
     * Remove all the elements of the vector.
     * Kept for compatibility with java.util.Vector.
     *
     * @post vector is empty
     *
     * @see #clear
     */
    public void removeAllElements()
    {
	setSize(0);
    }

    /*
     * Remove an element, by value, from vector.
     *
     * @post element equal to parameter is removed
     * 
     * @param element The element to be removed.
     * @return The element actually removed, or if none, null.

    public boolean removeElement(Object element)
    {
	int where = indexOf(element);
	if (where == -1) return false;
	remove(where);
	return true;
    }
*/

    /**
     * Remove an element at a particular location.
     *
     * @pre 0 <= where && where < size()
     * @post indicated element is removed, size decreases by 1
     * 
     * @param where The location of the element to be removed.
     */
    public void removeElementAt(int where)
    {
	remove(where);
    }

    /**
     * Remove an element at a particular location.
     *
     * @pre 0 <= where && where < size()
     * @post indicated element is removed, size decreases by 1
     * 
     * @param where The location of the element to be removed.
     */
    public Object remove(int where)
    {
	Object result = get(where);
	elementCount--;
	while (where < elementCount) {
	    elementData[where] = elementData[where+1];
	    where++;
	}
	elementData[elementCount] = null; // free reference
	return result;
    }

    /**
     * Change the value stored at location index.
     *
     * @pre 0 <= index && index < size()
     * @post element value is changed to obj
     * 
     * @param obj The new value to be stored.
     * @param index The index of the new value.
     */
    public void setElementAt(Object obj, int index)
    {
	set(index,obj);
    }

    /**
     * Change the value stored at location index.
     *
     * @pre 0 <= index && index < size()
     * @post element value is changed to obj; old value is returned
     * 
     * @param obj The new value to be stored.
     * @param index The index of the new value.
     */
    public Object set(int index, Object obj)
    {
	Object previous = elementData[index];
	elementData[index] = obj;
	return previous;
    }

    /**
     * Explicitly set the size of the array.
     * Any new elements are initialized to the default value.
     *
     * @pre newSize >= 0
     * @post vector is resized, any new elements are initialized
     * 
     * @param newSize The ultimate size of the vector.
     */
    public void setSize(int newSize)
    {
	int i;
	if (newSize < elementCount) {
	    for (i = newSize; i < elementCount; i++) elementData[i] = null;
	} else {
	    for (i = elementCount; i < newSize; i++)
	        elementData[i] = initialValue;
	}
	elementCount = newSize;
    }

    /**
     * Determine the number of elements in the vector.
     *
     * @post returns the size of the vector
     * 
     * @return The number of elements within the vector.
     */
    public int size()
    {
	return elementCount;
    }

    /**
     * Trim the vector to exactly the correct size.
     *
     * @post minimizes allocated size of vector
     */
    public void trimToSize()
    {
	Object newElementData[] = new Object[elementCount];
	copyInto(newElementData);
	elementData = newElementData;
    }

    /**
     * Determine a string representation for the vector.
     *
     * @post returns a string representation of vector
     * 
     * @return A string representation for the vector.
     */
    public String toString()
    {
	StringBuffer sb = new StringBuffer();
	int i;

	sb.append("<Vector:");
	for (i = 0; i < size(); i++)
	{
	    sb.append(" "+get(i));
	}
	sb.append(">");
	return sb.toString();
    }
    /*
    public void print()
    // post: print the elements of the vector
    {
	printFrom(0);
    }
    
    protected void printFrom(int index)
    // pre: index <= size()
    // post: print elements indexed between index and size()
    {
	if (index < size()) {
	    System.out.println(get(index));
	    printFrom(index+1);
	}
    }
    */
}