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

package SoftwareInterfaces;

/**
 * A class that provides a doubly linked list implementation of the ranked 
 * sequence abstract data type.
 *
 * @author H. Conrad Cunningham
 * @version 1 June 1998
 */

public class DoubleLinkRankedSeq implements RankedSequence
{
    /**
     * Constructs an empty sequence.
     *
     * @throws AssertionViolation
     * <dt><b>Postcondition:</b> 
     * <dd>constructs an empty sequence (with debugging turned off)
     */
    public DoubleLinkRankedSeq() throws AssertionViolation
    {   seqLength = 0; frontSeq = null;  backSeq = null; 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);
        if (debugOn) { Assert.inv(invariantOK()); }
        if (r == 0) // includes empty sequences
        {   DoubleLink newLink = new DoubleLink(e,null,frontSeq); 
            if (frontSeq != null) { frontSeq.setPrev(newLink); }
	    frontSeq = newLink;
	    if (backSeq == null) { backSeq = newLink; }
	}
	else if (r == seqLength)
        {   DoubleLink newLink = new DoubleLink(e,backSeq,null); 
            backSeq.setNext(newLink);
	    backSeq = newLink;
	}
	else
	{   DoubleLink after = findLinkAtRank(r);
	    DoubleLink before = after.getPrev();
	    DoubleLink newLink = new DoubleLink(e,before,after);
	    before.setNext(newLink);
	    after.setPrev(newLink);
	}
	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 the element exists
        if (debugOn) { Assert.inv(invariantOK()); }
        DoubleLink deadLink;
        if (r == 0)  // includes one-element sequences
        {   deadLink = frontSeq;
	    DoubleLink after = frontSeq.getNext();
	    if (after != null) { after.setPrev(null); }
            frontSeq = after;
            if (after == null) { backSeq = null; }
        }
	else if (r == seqLength-1)
        {   deadLink = backSeq;
            DoubleLink before = backSeq.getPrev();
	    before.setNext(null);
	    backSeq = before;
	}
	else
	{   deadLink = findLinkAtRank(r);
	    DoubleLink before = deadLink.getPrev();
	    DoubleLink after  = deadLink.getNext();
	    before.setNext(after);
	    after.setPrev(before);
	}
	deadLink.setPrev(null);  // make sure any references to this node
	deadLink.setNext(null);  //   no longer links into sequence
        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 the element exists
        if (debugOn) { Assert.inv(invariantOK()); }
        DoubleLink modLink = findLinkAtRank(r);
	modLink.setElem(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 the element exists
        if (debugOn) { Assert.inv(invariantOK()); }
        DoubleLink elemLink = findLinkAtRank(r);
	return elemLink.getElem();
    }


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

    /**
     * Determine whether the sequence is empty.
     *
     * @return true if the sequence contains no elements;
     *     otherwise false.
     */
    public boolean isEmpty() throws AssertionViolation
    {   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
    {   if (debugOn) { Assert.inv(invariantOK()); }
        return new DoubleLinkRankedSeqEnum(frontSeq); 
    }


    /**
     * 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; }


    /**
     * Finds the node of the list that has the given rank.
     *
     * @param r the rank at which to insert the object
     * <dt><b>Preconditon:</b> 
     * <dd><code>0 <= r < length()</code>
     * 
     * @return the node of the list with the given rank
     * @throws AssertionViolation (e.g., if precondition not satisfied)
     */
    private DoubleLink findLinkAtRank(int r) throws AssertionViolation
    {   Assert.pre(0 <= r && r < seqLength);
        if (debugOn) { Assert.inv(invariantOK()); }
        DoubleLink curLink;
	int rank;
	if (r < (seqLength+1)/2)  // in lower half of list?
	{   curLink = frontSeq;
	    for (rank = 0; curLink != null && rank < r; rank++)
            {   curLink = curLink.getNext(); }
        }
        else  // in upper half of list
        {
            curLink = backSeq;
            for (rank = seqLength-1; curLink != null && rank > r; rank--)
            {   curLink = curLink.getPrev(); }
        }
        if (rank != r)
        {   throw new InvariantViolation
	        ("Linked list invalid in DoubleLinkRankedSeq.");
        }
        return curLink;
    }


    /**
     * Checks several aspects of the class invariant.
     *
     * @return false if any invariant check fails, true otherwise
     * <dt><b>Postcondition:</b> 
     * <dd>if debugging enabled, prints error message concerning problem found
     */
    private boolean invariantOK()
    {	int rank = 0;
	DoubleLink before = null;
        DoubleLink curLink;
        for (curLink = frontSeq; curLink != null; curLink = curLink.getNext())
        {   if (before != curLink.getPrev())
            {   if (debugOn) 
	        {   System.out.println("Internal error:  " +
		        "At rank " + rank + " previous link incorrect!"); 
		}
	        return false;
	    }
	    before = curLink;
	    rank++;
	}
	if (before != backSeq)
        {   if (debugOn) 
	    {   System.out.println("Internal error:  " +
                    "End-of-list pointer incorrect!");
	    }
	    return false;
	}
	if (rank != seqLength)
        {   if (debugOn) 
	    {   System.out.println("Internal error:  " +
		    "Sequence length " + seqLength + 
		     " not equal to actual list length." + rank); 
            }
	    return false;
        }
	return true;
    }
  

    /**
     * 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);
	int rank = 0;
	DoubleLink before = null;
        DoubleLink curLink;
        for (curLink = frontSeq; curLink != null; curLink = curLink.getNext())
        {   Object elem = curLink.getElem();
            System.out.println(rank + "\t" + 
	        (elem == null ? "NULL" : elem.toString()));
	    if (before != curLink.getPrev())
            {   System.out.println("At rank " + rank + 
		    " previous link incorrect!"); 
	    }
	    before = curLink;
	    rank++;
	}
	if (before != backSeq)
        {   System.out.println("End-of-list pointer incorrect!"); }
	if (rank != seqLength)
        {   System.out.println("seqLength not set to actual list length."); }
        System.out.println("***  END sequence display:  " + msg);
    }


    /* Invariant:  
           0 <= seqLength == the number of nodes in the list
           && the node at rank i is found by following the list beginning
	       with frontSeq and following the "next" links i steps
           && the node at rank i is also found by following the list beginning
	       with backSeq and following the "prev" links seqLength-i-1 steps
	   && frontSeq, backSeq, "next" node links, and "previous" node links 
	       are all null if not indicating a node of the list
     */

    private int seqLength;       // number of elements in the sequence
    private DoubleLink frontSeq; // front node of the list
    private DoubleLink backSeq;  // back node of the list
    private boolean debugOn;     // debugging option
}