import java.util.List;
import java.util.ArrayList;

/**
 * An input validation queue.
 * Performs basic syntactic validation of enqueued items.
 * Only valid items are available for dequeueing.
 * Syntax is checked for matching open and close markers.
 * Open markers checked include ( [ { < , matching close markers are ) ] } > 
 * @author Dr. Jody Paul
 * @version Fall 2005 - CSI 2050
 */
public class InputValidatorQueue
{
    ArrayList<String> incomingQ;
    ArrayList<String> outgoingQ;
    
    /**
     * Construct an object of class InputValidatorQueue.
     */
    public InputValidatorQueue() {
        incomingQ = new ArrayList<String>();
        outgoingQ = new ArrayList<String>();
    }

    /**
     * Attempt to enqueue a string.
     * Note that if the string is not syntactically valid, it will not be enqueued.
     * @param inputString the item to be enqueued
     * @return <code>true</code> if the item was valid and thus enqueued; <code>false</code> otherwise
     */
    public boolean enqueue(String inputString) {
        incomingQ.add(inputString);
        return validate(incomingQ,outgoingQ);
    }
    
    /**
     * Attempt to enqueue a list of strings.<BR><BR>
     * <b>Post-Conditions:</b> All valid strings in the list are enqueued; no invalid strings are enqueued
     * @param inputStringList the list of strings to be enqueued
     * @return <code>true</code> if all items in the list are valid; <code>false</code> if at least one item is not valid
     */
    public boolean enqueue(List<String> inputStringList) {
        boolean returnValue = true;
        for (String s : inputStringList)
            incomingQ.add(s);
        return validate(incomingQ,outgoingQ);
    }

    /**
     * Validate each item in the incoming queue parameter.
     * Add each valid item to the outgoing queue parameter.
     * @param inQueue the incoming queue
     * @param outQueue the outgoing queue
     * @return true if every item in the incoming queue is valid, false otherwise
     */
    private boolean validate(ArrayList<String> inQueue, ArrayList<String> outQueue) {
        boolean allValid = true;
        for (String s : inQueue) {
            if (isValid(s)) outQueue.add(s);
            else allValid = false;
        }
        inQueue.clear();
        return allValid;
    }
    /** Helper method to validate a given string. */
    private boolean isValid(String s) {
        ArrayList<Character> stack = new ArrayList<Character>();
        char[] characters = s.toCharArray();
        for (char c : characters) {
            switch (c) {
                case '[':
                case '{':
                case '(':
                case '<': stack.add(c);
                          break;
                case ']': if (stack.isEmpty() || !stack.remove(stack.size()-1).equals('[')) return false;
                          break;
                case '}': if (stack.isEmpty() || !stack.remove(stack.size()-1).equals('{')) return false;
                          break;
                case ')': if (stack.isEmpty() || !stack.remove(stack.size()-1).equals('(')) return false;
                          break;
                case '>': if (stack.isEmpty() || !stack.remove(stack.size()-1).equals('<')) return false;
                          break;
                default:  break;
            }
        }
        return stack.isEmpty();
    }
    /**
     * Dequeue an item if any exists in the queue.
     * @return the next item in the queue
     * @throw EmptyQueueException if this queue is empty
     */
    public String dequeue() throws EmptyQueueException {
        if (outgoingQ.isEmpty()) throw new EmptyQueueException();
        return outgoingQ.remove(0);
    }
    
    /**
     * Tests if this queue is empty.
     * @return <code>true</code> if this queue contains no items; <code>false</code> otherwise
     */
    public boolean isEmpty() {
        return outgoingQ.isEmpty();
    }
    
    public class EmptyQueueException extends Exception { }
}