package stacks;

import java.util.Enumeration;

/**
 * A stack implemented using arrays.
 *
 * A stack manages its objects in a Last In, First Out (LIFO) order. 
 *
 * @author Alan L. Cox
 * @since 03/15/01
 */
public class ArrayStack implements IStack
{
    private int _firstEmptyObject = 0;
    private Object[] _objects = new Object[1];
    
    /**
     * Adds a new object to the stack.
     * @param data the object to add to the stack.
     *
     * Worst Case: O(n) since it has to copy the whole list when it fills up.
     */
    public void push(Object data)
    {
	if (_firstEmptyObject == _objects.length)
	    {
		int j;

		Object[] newObjects = new Object[2*_objects.length];

		for (j = 0; j < _objects.length; j++)
		    newObjects[j] = _objects[j];

		_objects = newObjects;
	    }
	_objects[_firstEmptyObject] = data;
	_firstEmptyObject++;
    }

    /**
     * Removes and returns the newest object from the stack.
     *
     * @return the popped object
     *
     * This pop method takes O(1) time. Just take the top element from the stack
     */
    public Object pop()
    {
	if (_firstEmptyObject == 0)
	    throw new java.util.NoSuchElementException("The stack is empty.");

	Object object = _objects[_firstEmptyObject - 1];
       
	_firstEmptyObject--;

	_objects[_firstEmptyObject] = null;

	return object;
    }

    /**
     * Enumerates the stack from oldest to newest object.
     *
     * @return an Enumeration of the stack.
     *
     * All operations are O(1), since only updating of a counter or single 
     * access of the top of the stack is done
     */
    public Enumeration enumeration()
    {
	return new Enumeration()
	    {
		private int _nextObject = 0;

		public boolean hasMoreElements()
		{
		    return _nextObject < _firstEmptyObject;
		}

		public Object nextElement()
		{
		    return _objects[_nextObject++];
		}
	    };
    }
}