import java.util.Iterator;
import java.util.Vector;

/**
   The ArrayList class implements the List interface by means of a circular 
   array.
  
   @author      Franck van Breugel
   @version     1.5    June 18, 2001
   @see Position
   @see ArrayPosition
*/
public class ArrayList implements List 
{
    public static final int CAPACITY = 1000; // default maximal capacity of array
 
    private int capacity;                    // maximal capacity of array
    private ArrayPosition[] sequence;        // holds elements of this list
    private int first;                       // index of the first position of this list
    private int last;                        // index of array cell immediate after the last position of this list
 
    /** Constructs a list of default capacity. */
    public ArrayList() 
    {
        this(CAPACITY);
    }

    /** 
       Constructs a list of specified capacity. 
      
       @param capacity The capacity of the list. 
    */
    public ArrayList(int capacity) 
    {
        this.capacity = capacity;
        this.sequence = new ArrayPosition[capacity];
        this.first = 0;
        this.last = 0;
    }

    /**
       Returns the specified position as an ArrayPosition.
       Throws an InvalidPositionException if the specified position
       is invalid: the specified position is not an ArrayPosition.
      
       @param position The position to be returned as ArrayPosition.
       @return The specified position as an ArrayPosition.
       @exception PositionalSequenceException if the specified position
       is invalid.
    */
    private ArrayPosition checkPosition(Position position) throws InvalidPositionException 
    {
        try 
        {
            return (ArrayPosition) position;
        } 
        catch (ClassCastException e) 
        {
            throw new InvalidPositionException("Position is of the wrong type for the sequence.");
        }
    }

    /**
       Returns the length of the segment of the circular array sequence
       starting from (and including) begin upto (and excluding) end.
      
       @param begin The begin of the segment the length of which is returned.
       @param end The end of the segment the length of which is returned.
       @return The length of the segment of the circular array sequence
       starting from (and including) begin upto (and excluding) end.
    */
    private int length(int begin, int end) 
    {
        return (capacity + end - begin) % capacity;
    }

    /**
       Returns the index of the cell of the circular array sequence to the
       left of the specified index.
      
       @param index The index of the circular array sequence.
       @return The index of the cell of the circular array sequence to the
       left of the specified index.
    */
    private int leftOf(int index) 
    {
        return (capacity + index - 1) % capacity;
    }

    /**
       Returns the index of the cell of the circular array sequence to the
       right of the specified index.
      
       @param index The index of the circular array sequence.
       @return The index of the cell of the circular array sequence to the
       right of the specified index.
    */
    private int rightOf(int index) 
    {
        return (index + 1) % capacity;
    }

    /**
       Moves the segment of the circular array sequence from (and including)
       begin upto (and excluding) end one position to the left.
      
       @param begin The begin of the segment which is moved.
       @param end The end of the segment wich is moved.
    */
    private void moveLeft(int begin, int end) 
    {
        int index = begin;
        while (index != end) 
        {
        /* sequence[begin],...,sequence[leftOf(index)] have been moved one
           position to the left */
            sequence[leftOf(index)] = sequence[index];
            sequence[leftOf(index)].setIndex(leftOf(index));
            index = rightOf(index);
        }
    }

    /**
       Moves the segment of the circular array sequence from (and including)
       begin upto (and excluding) end one position to the right.
      
       @param begin The begin of the segment which is moved.
       @param end The end of the segment wich is moved.
    */
    private void moveRight(int begin, int end) 
    {
        int index = end;
        while (index != begin) 
        {
        /* sequence[index],...,sequence[leftOf(end)] have been moved one
           position to the right */
            sequence[index] = sequence[leftOf(index)];
            sequence[index].setIndex(index);
            index = leftOf(index);
        }
    }
 
    public int size() 
    {
        return length(first, last);
    }

    public boolean isEmpty()  
    {
        return (first == last);
    }
 
    public Iterator elements()
    {
        Vector vector = new Vector();
        int index = first;
	while (index != last)
	{
	/* vector contains elements of sequence[first], ..., sequence[leftOf(index)] */
	    vector.add(sequence[index].element());
            index = rightOf(index);
	}
        return vector.iterator();
    }

    public Iterator positions()
    {
        Vector vector = new Vector();
        int index = first;
        while (index != last)
	    {
		/* vector contains positions sequence[first], ..., sequence[leftOf(index)] */
		vector.add(sequence[index]);
		index = rightOf(index);
	    }
        return vector.iterator();
    }

    public Position first() throws EmptyContainerException 
    {
        if (isEmpty()) 
        {
            throw new EmptyContainerException("Sequence is empty.");
        }
        return sequence[first];
    }

    public Position last() throws EmptyContainerException 
    {
        if (isEmpty()) 
        {
            throw new EmptyContainerException("Sequence is empty.");
        }
        return sequence[leftOf(last)];
    }

    public Position before(Position position) throws InvalidPositionException, BoundaryViolationException 
    {
        ArrayPosition arrayPosition = checkPosition(position);
        if (arrayPosition == first()) 
        {
            throw new BoundaryViolationException("Cannot go past the beginning of the sequence.");
        }
        int index = arrayPosition.getIndex();
        return sequence[leftOf(index)];
    }

    public Position after(Position position) throws InvalidPositionException, BoundaryViolationException 
    {
        ArrayPosition arrayPosition = checkPosition(position);
        if (arrayPosition == last()) 
        {
            throw new BoundaryViolationException("Cannot go past the end of the sequence.");
        }
        int index = arrayPosition.getIndex();
        return sequence[rightOf(index)];
    }

    public boolean isFirst(Position position) throws InvalidPositionException 
    {
        ArrayPosition arrayPosition = checkPosition(position);
        return (arrayPosition == first());
    }

    public boolean isLast(Position position) throws InvalidPositionException 
    {
        ArrayPosition arrayPosition = checkPosition(position);
        return (arrayPosition == last());
    }

    public Object replaceElement(Position position, Object element) throws InvalidPositionException 
    {
        ArrayPosition arrayPosition = checkPosition(position);
        Object temp = arrayPosition.element();
        arrayPosition.setElement(element);
        return temp;
    }

    public void swapElements(Position firstPosition, Position secondPosition) throws InvalidPositionException 
    {
        ArrayPosition firstArrayPosition = checkPosition(firstPosition);
        ArrayPosition secondArrayPosition = checkPosition(secondPosition);
        Object temp = firstArrayPosition.element();
        firstArrayPosition.setElement(secondArrayPosition.element());
        secondArrayPosition.setElement(temp);
    }

    public Position insertFirst(Object element) throws ListFullException 
    {
        if (capacity - size() <= 1) 
        {
            throw new ListFullException("Sequence overflow.");
        }
        first = leftOf(first);
        ArrayPosition arrayPosition = new ArrayPosition(element, first);
        sequence[first] = arrayPosition;
        return arrayPosition;
    }

    public Position insertLast(Object element) throws ListFullException 
    {
        if (capacity - size() <= 1) 
        {
            throw new ListFullException("Sequence overflow.");
        }
        ArrayPosition arrayPosition = new ArrayPosition(element, last);
        sequence[last] = arrayPosition;
        last = rightOf(last);
        return arrayPosition;            
    }

    public Position insertBefore(Position position, Object element) throws InvalidPositionException, ListFullException 
    {
        if (capacity - size() <= 1) 
        {
            throw new ListFullException("Sequence overflow.");
        }
        ArrayPosition arrayPosition = checkPosition(position);
        int index = arrayPosition.getIndex();
        ArrayPosition temp;
        if (length(first, index) <= length(index, last)) 
        {
            moveLeft(first, index);
            first = leftOf(first);
            temp = new ArrayPosition(element, leftOf(index));
            sequence[leftOf(index)] = temp;
        } 
        else 
        {
            moveRight(index, last);
            last = rightOf(last);
            temp = new ArrayPosition(element, index);
            sequence[index] = temp;
        }
        return temp;
    }

    public Position insertAfter(Position position, Object element) throws InvalidPositionException, ListFullException 
    {
        Position temp;
        if (position == last()) 
        {
            temp = insertLast(element);
        } 
        else 
        {
            temp = insertBefore(after(position), element);
        }
        return temp;
    }

    public Object remove(Position position) throws InvalidPositionException 
    {
        ArrayPosition arrayPosition = checkPosition(position);
        int index = arrayPosition.getIndex();
        Object element = arrayPosition.element();
        if (length(first, index) <= length(rightOf(index), last)) 
        {
            moveRight(first, index);
            first = rightOf(first);
        } 
        else 
        {
            moveLeft(rightOf(index), last);
            last = leftOf(last);
        }
        return element;
    }    

    /**
       Returns a string representation of this list.
      
       @return A string representation of this list.
    */
    public String toString() 
    {
        String rep = "";
        int index = first;
        while (index != last) 
        {
        /* rep = sequence[first].toString() + "\n" + ... + sequence[leftOf(index)].toString() + "\n" */
            rep += sequence[index].toString();
            rep += "\n";
            index = rightOf(index);
        }
        return rep;
    }
}