/* Copyright (C) 1998 H. Conrad Cunningham.  All rights reserved.  */

package SoftwareInterfaces;

/**
 * A class that provides a dynamic, array-based implementation of the ranked 
 * sequence abstract data type.
 *
 * <p> This implementation uses an array to store the sequence of elements.
 * The rank of an element in the sequence is its index in the array.  If the 
 * insertion of a new element overflows the allocated size of the array, 
 * a new larger array is allocated to store the sequence.
 *
 * @author H. Conrad Cunningham
 * @version 1 June 1998
 */

public class ArrayRankedSeq implements RankedSequence
{

    /**
     * Constructs an empty sequence (with the default initial capacity and 
     * incrementing policy).
     *
     * @throws AssertionViolation (e.g., if precondition not satisfied)
     * <dt><b>Postcondition:</b> 
     * <dd>constructs an empty sequence with initial capacity
     *     <code>DEFAULT_INITIAL_CAPACITY</code> and an incrementing policy
     *     such that the size is doubled on each expansion
     */
    public ArrayRankedSeq() throws AssertionViolation
    {   this(DEFAULT_INITIAL_CAPACITY, DEFAULT_CAPACITY_INCREMENT); }


    /**
     * Constructs an empty sequence with the given initial capacity (and 
     * default incrementing policy).
     *
     * @param initialCapacity the number of (empty) slots in the sequence 
     *      initially 
     * <dt><b>Preconditon:</b> 
     * <dd><code>initialCapacity >= 0</code>
     *
     * @throws AssertionViolation (e.g., if precondition not satisfied)
     * <dt><b>Postcondition:</b> 
     * <dd>constructs an empty sequence with initial capacity
     *     <code>initialCapacity</code> and an incrementing policy such that 
     *     the size is doubled on each expansion
     */
    public ArrayRankedSeq(int initialCapacity) throws AssertionViolation
    {   this(initialCapacity,DEFAULT_CAPACITY_INCREMENT); }


    /**
     * Constructs an empty sequence with the given initial capacity and 
     * increment.
     *
     * @param initialCapacity the number of (empty) slots in the sequence 
     *      initially 
     * @param capacityIncrement capacityIncrement if positive, the number of 
     *     slots to add when the capacity needs to be increased; if zero, 
     *     double the capacity.
     * <dt><b>Preconditon:</b> 
     * <dd><code>initialCapacity >= 0 && capacityIncrement >= 0</code>
     *
     * @throws AssertionViolation (e.g., if precondition not satisfied)
     * <dt><b>Postcondition:</b> 
     * <dd>constructs an empty sequence with initial capacity
     *     <code>initialCapacity</code> and capacity increment 
     *     <code>capacityIncrement</code>
     */
    public ArrayRankedSeq(int initialCapacity, int capacityIncrement)
        throws AssertionViolation
    {   Assert.pre(initialCapacity >= 0 && capacityIncrement >= 0);
        theSeq = new Object[initialCapacity];
        capacityIncr = capacityIncrement;
	seqLength = 0;
	debugOn = false;



    }


    /**
     * Insert a new element at the given rank into the sequence.
     *
     * @param r the rank at which to insert the object
     * @param e the object to be inserted
     * <dt><b>Preconditon:</b> 
     * <dd><code>0 <= r <= length()</code>
     * 
     * @throws AssertionViolation (e.g., if precondition not satisfied)
     * <dt><b>Postcondition:</b> 
     * <dd>object <code>e</code> added as element at rank <code>r</code>.
     *     Ranks of all elements (if any) with old ranks >= <code>r</code>
     *     are increased by one.
     */
    public void insertAtRank(int r, Object e) throws AssertionViolation
    {   Assert.pre(0 <= r && r <= seqLength);
        addSlot(r);
	theSeq[r] = e;
	seqLength++;
    }
        

    /**
     * Delete the element at the given rank from the sequence.
     *
     * @param r the rank at which to delete the object
     * <dt><b>Preconditon:</b> 
     * <dd> <code> 0 <= r < length() </code>
     *
     * @throws AssertionViolation (e.g., if precondition not satisfied)
     * <dt><b>Postcondition:</b> 
     * <dd>element at rank <code>r</code> is removed.
     *     Ranks of all elements (if any) with old ranks > <code>r</code>
     *     are decreased by one.
     */
    public void deleteAtRank(int r) throws AssertionViolation
    {   Assert.pre(0 <= r && r < seqLength);  // thus at least one exists
        removeSlot(r);
	seqLength--;
    }
	      

    /**
     * Replace the element at the given rank in the sequence.
     *
     * @param r the rank at which to replace the object
     * @param e the replacement object
     * <dt><b>Preconditon:</b> 
     * <dd><code>0 <= r < length()</code>
     *
     * @throws AssertionViolation (e.g., if precondition not satisfied)
     * <dt><b>Postcondition:</b> 
     * <dd>element at rank <code>r</code> is replaced by object <code>e</code>.
     */
    public void replaceAtRank(int r, Object e) throws AssertionViolation
    {   Assert.pre(0 <= r && r < seqLength);  // thus at least one exists
        theSeq[r] = e; 
    }


    /**
     * Retrieve the element at the given rank from the sequence.
     *
     * @param r the rank whose value is to be returned
     * <dt><b>Preconditon:</b> 
     * <dd><code>0 <= r < length()</code>
     *
     * @return the element at rank <code>r</code>
     * @throws AssertionViolation (e.g., if precondition not satisfied)
     *     
     */
    public Object elementAtRank(int r) throws AssertionViolation
    {   Assert.pre(0 <= r && r < seqLength);  // thus at least one exists
        return theSeq[r]; 
    }


    /**
     * Determine the length of (i.e., number of elements in) the sequence.
     *
     * @return the number of elements in the sequence.
     */
    public int length()
    {   return seqLength; }


    /**
     * Determine whether the sequence is empty.
     *
     * @return true if the sequence contains no elements;
     *     otherwise false.
     */
    public boolean isEmpty()
    {   return (seqLength == 0); }


    /**
     * Construct an enumeration iterator for the sequence.
     *
     * @return an enumeration iterator for the sequence
     * @throws AssertionViolation
     */
    public java.util.Enumeration elements() throws AssertionViolation
    {   Object[] seq = copyArraySegment(theSeq,0,seqLength);
        return new ArrayRankedSeqEnum(seq,seqLength); 
    }

    /**
     * Release the unused capacity of the sequence.
     *
     * @throws AssertionViolation (e.g., if precondition not satisfied)
     * <dt><b>Postcondition:</b> 
     * <dd>frees any unused capacity, making the capacity equal to the
     *     sequence length.
     */
    public void trimToLength() throws AssertionViolation
    {   if (seqLength < theSeq.length)
        {   theSeq = copyArraySegment(theSeq,0,seqLength); }
    }


    /**
     * Enables debugging option.
     *
     * <dt><b>Postcondition:</b> 
     * <dd>internal debugging option turned on
     */
    public void enableDebug()
    {  debugOn = true; }


    /**
     * Disables debugging option.
     *
     * <dt><b>Postcondition:</b> 
     * <dd>internal debugging option turned off
     */
    public void disableDebug()
    {   debugOn = false; }


    /**
     * Internal method that adds a new "empty" array slot at the given rank.
     *
     * @param r the rank at which to add a new slot
     * <dt><b>Preconditon:</b
     * <dd><code>0 <= r <= length()</code>
     *
     * @throws AssertionViolation (e.g., if precondition not satisfied)
     * <dt><b>Postcondition:</b> 
     * <dd>array elements with old indexes in range <code>[r..seqLength)</code>
     *     moved one index higher.  A new array slot opened at index 
     *     <code>r</code>.  More capacity is  allocated if current array full.
     */
    private void addSlot(int rank) throws AssertionViolation
    {   Assert.pre(0 <= rank && rank <= seqLength);
        if (seqLength < theSeq.length)
        {   for (int i = seqLength ; i > rank; i--)
            {  theSeq[i] = theSeq[i-1]; }
	    theSeq[rank] = null;
	}
        else // seqLength == theSeq.length
	{   Object[] temp = new Object[determineNewCapacity()];
	    int i;
	    for (i = seqLength ; i > rank; i--)
	    {   temp[i] = theSeq[i-1]; }
	    for (i-- ; i >= 0; i--)
	    {   temp[i] = theSeq[i]; }
	    theSeq = temp;
	}
    }


    /**
     * Internal method that determines the desired new size of the array
     * when increasing it is necessary.
     *
     * @return the number of slots needed in the increased size array
     * <dt><b>>Postcondition:</b> 
     * <dd>return is <code>capacityIncr</code> if it is positiv; 
     *     otherwise it is the current capacity multiplied by 
     *     the factor <code>CAPACITY_MULTIPLIER</code>.  
     */
    private int determineNewCapacity()
    {   int incr = Math.max(0,capacityIncr);
        if (capacityIncr == 0)
	{   incr = (int) ((double) theSeq.length 
	                      * (CAPACITY_MULTIPLIER - 1.0));
	    incr = Math.max(1,incr);
	}
	return (theSeq.length + incr);
    }


    /**
     * Internal method that removes the array slot at the given rank.
     *
     * @param r the rank at which to remove the slot
     * <dt><b>Preconditon:</b> 
     * <dd><code>0 <= r < length()</code>
     * 
     * @throws AssertionViolation (e.g., if precondition not satisfied)
     * <dt><b>Postcondition:</b> 
     * <dd>array elements with old indexes in range 
     *     <code>[r+1..seqLength)</code> are moved one index lower. 
     */
    private void removeSlot(int rank) throws AssertionViolation
    {   Assert.pre(0 <= rank && rank < seqLength); // thus at least one exists
        for (int i = rank ; i < seqLength-1; i++)
        {  theSeq[i] = theSeq[i+1]; }
	theSeq[seqLength-1] = null;
    }
  

    /**
     * Internal method that creates a copy of a segment of an array.
     *
     * @param oldArr the array of objects to copy from
     * @param beg the beginning (i.e., smallest) index of the array segment 
     * to copy 
     * @param len the length of the segment to copy
     * <dt><b>Preconditon:</b> 
     * <dd> <code>0 <= beg < oldArr.length && 0 <= len && </code>
     *     <code>beg + len <= oldArr.length</code>
     * 
     * @return the new array of size <code>len</code> containing 
     * references to elements <code>[beg..beg+len)</code> of 
     * <code>oldArr</code>
     * @throws AssertionViolation (e.g., if precondition not satisfied)
     */
    private Object[] copyArraySegment(Object[] oldArr, int beg, int len)
        throws AssertionViolation
    {   Assert.pre(0 <= beg && beg < oldArr.length && 
		   0 <= len && beg + len <= oldArr.length);
        Object[] newArr = new Object[len];
	int j = beg;
        for (int i = 0; i < len; i++)
	{   newArr[i] = oldArr[j];
	    j++;
	}
	return newArr;
    }


    /**
     * Debugging method that displays internal information from the instance
     * on the standard output.
     */
    public void DEBUG_showSequence(String msg)
    {   System.out.println("***  BEGIN sequence display:  " + msg);
        System.out.println("Length = " + seqLength + ",  " +
			   "Capacity = " + theSeq.length  + ",  " +
                           "Increment = " + capacityIncr );
	for (int i = 0; i < seqLength; i++)
        {   System.out.println(i + "\t" + 
                (theSeq[i] == null ? "NULL" : theSeq[i].toString()));
	}
        System.out.println("***  END sequence display:  " + msg);
    }

    /* Invariant:  0 <= seqLength <= theSeq.length && 0 <= capacityIncr &&
                   (for 0 <= r < seqLength, 
                       theSeq[r] == element at rank r of the sequence)
    */

    private int seqLength;    // number of elements in the sequence
    private Object[] theSeq;  // array to store the sequence elements
    private int capacityIncr; // amount to increment the array size 
                              //     when expanded 
    private boolean debugOn;  // debugging option


    private static final int DEFAULT_INITIAL_CAPACITY = 2;
    private static final int DEFAULT_CAPACITY_INCREMENT = 0;
    private static final double CAPACITY_MULTIPLIER = 2.0;
}