import java.util.*;

/**
 * A thread-safe implementation of a queue that offers blocking and deterministic delivery to waiting threads.
 * <BR><BR>
 * If thread A goes into a waiting state (because no object is immediately available) before thread B, thread A is guaranteed
 * to receive an object from the queue before thread B.
 * <BR><BR>
 * The methods {@link #readFirst() readFirst() } and {@link #readLast() readLast() } block indefinitely, if necessary, until
 * objects are added to the queue or the queue is closed.  If it is desired that calls to the queue return immediately (whether
 * or not content is available), methods such as readFirst(long timeout) should be used with a timeout
 * of zero milliseconds.
 * <BR><BR>
 * Methods named ...First and ...Last have been included so that the queue may be considered double-ended.  Convenience methods have
 * also been included for use when the queue can be considered single-ended: <BR>
 * add(Object) executes the same logic as addLast(Object) <BR>
 * remove() executes the same logic as removeFirst() <BR>
 * peek() executes the same logic as peekFirst() <BR> (etc.)
 */
public final class Queue {
    // Canonical value for returning no results (for use when the removeAll() method is called and there are no
    // elements in the queue)
    private static final Object[] EMPTY_OBJECT_ARRAY        = {};

    // Holds the open/closed state of the queue
    private boolean closed                                  = false;
    
    // The header (and tail) node for the doubly-linked circular list of elements
    private Node header                                     = new Node();
    {
        header.previous = header;
        header.next = header;   
    }
    
    // the current number of elements in the queue
    private int size                                        = 0; 
    
    // A cache to hold element nodes when they're not in use.  This saves on object creation at a slight space penalty.
    // A singly-linked list is used because the objects being cached are linked-list nodes
    private Node nodeCacheHeader                            = new Node();
    private int nodeCacheSize                               = 0; // The current number of cached nodes
    private int maximumNodeCacheSize                        = 10000; // Prevents the node cache from growing too large due to 
    // unusual circumstances (such as seldom-repeated influxes of large amounts of data)
    
    
    // The header (and tail) node for the doubly-linked circular list of threads waiting for output
    private WaitingThreadNode waitingThreadHeader           = new WaitingThreadNode();
    {
        waitingThreadHeader.next = waitingThreadHeader;
        waitingThreadHeader.previous = waitingThreadHeader;   
    }


    // A cache to hold waiting-thread nodes when they're not in use.  This saves on object creation at a slight space penalty.
    // A singly-linked list is used because the objects being cached are linked-list nodes
    private WaitingThreadNode waitingThreadCacheHeader      = new WaitingThreadNode();
    private int waitingThreadCacheSize                      = 0; // The current number of cached nodes
    private int maximumWaitingThreadCacheSize               = 10000; // Prevents the cache from growing too large; 10,000
    // threads in the same VM is not often seen anyway
    

    // Used to synchronize access to the list of elements
    private Object lock = new Object();

    /**
     * Constructs a new, empty Queue instance
     */
    public Queue() {
    }

    /**
     * Returns the number of objects currently held in the queue
     */
    public int getSize() {
        synchronized (lock) {
            return size;
        }
    }

    /**
     * Removes and returns the first object from the front of the queue.  If no object is available, blocks indefinitely until
     * an object becomes available (in which case it returns the object) or the Queue instance is closed (in which case it
     * returns null)
     * @see #removeLast()
     * @see #removeFirst(long)
     * @see #close()
     */
    public Object removeFirst() {
        // The node that will hold the current thread in a list for ordering purposes if there is nothing to return from
        // the queue.  This needs to be assigned inside the main synchronized block and used outside of it, hence its
        // declaration here.
        WaitingThreadNode waitingThreadNode; 
        
        synchronized (lock) {
            if (size > 0) { // if there is something in the queue, we will immediately return it
                
                // Get the node containing the element to return
                Node node = header.next;
                Object data = node.data; // the return value
                
                // Remove the node containing the element from the list of elements
                node.next.previous = node.previous;
                node.previous.next = node.next;
                size--;
                
                // If appropriate, cache the node instead of discarding it, so that it may be used during the next
                // insertion
                if (nodeCacheSize < maximumNodeCacheSize) {
                    node.next = nodeCacheHeader.next;
                    nodeCacheHeader.next = node;
                    
                    // this is a necessary step to ensure that the previous node can be garbage collected;
                    // otherwise, the cache could grow indefinitely
                    node.previous = null; 
                    
                    node.data = null;
                    nodeCacheSize++;
                }
                
                return data;
            }
            else if (closed) { // Note that if there is something in the queue, we will return it even if the queue is closed
                return null;
            }
            
            
            // If we have reached this point, the queue currently contains no elements.  Our next step is to insert the waiting
            // thread into a list of waiting threads, so that we can return future queue input to waiting threads in the 
            // appropriate order.  A doubly-linked list is used for this, so that if the thread's wait time expires before it 
            // has received data, it can easily remove ITSELF from the list of waiting threads without damaging the structure.
            
            
            // Acquire a node to hold the waiting thread, either from the cache of such nodes or by creating a new one
            synchronized (waitingThreadCacheHeader) {
                if (waitingThreadCacheSize > 0) {
                    waitingThreadNode = waitingThreadCacheHeader.next;
                    waitingThreadCacheHeader.next = waitingThreadNode.next;
                    waitingThreadCacheSize--;
                }
                else {
                    waitingThreadNode = new WaitingThreadNode();
                }
            }
            
            waitingThreadNode.thread = Thread.currentThread();
            waitingThreadNode.awaitingRemove = true; // Indicates that this thread is waiting to remove a value (versus peek at it)
            waitingThreadNode.receivedOutput = false; // update flag
            
            // Since modification of the waiting-thread list may occur outside of code synchronized on the
            // main monitor (the 'lock' object), we must synchronize on the list separately during modification
            synchronized (waitingThreadHeader) {
                // this list is circular, so the header node's previous link points to the current last item in the list
                waitingThreadNode.previous = waitingThreadHeader.previous;
                waitingThreadNode.previous.next = waitingThreadNode;
                waitingThreadNode.next = waitingThreadHeader;
                waitingThreadHeader.previous = waitingThreadNode;
            }
        }
        
        // Since the current thread itself is guaranteed to have a unique monitor, we use that for the wait/notify mechanism.
        // This allows us to guarantee that the thread we wake up is the one we're after (see the addXXX methods)
        synchronized (waitingThreadNode.thread) {
            // This first check is necessary because the thread may have already received some output
            // (since we're now outside the main synchronized block)
            if (!waitingThreadNode.receivedOutput) {
                try {
                    // May be notified by the addXXX and close methods, or may be externally interrupted-- in
                    // any case, it will be time to wake up
                    waitingThreadNode.thread.wait();
                } catch (InterruptedException ie) {}  
            }
        
            // This is either the next input to the queue, or null if the thread awoke before there was an object to return
            Object returnValue = waitingThreadNode.data;
    
            if (!waitingThreadNode.receivedOutput) { // If this is true, the thread awoke before the next input to the queue
                // The node is still in the list of waiting threads, and must be removed
                synchronized (waitingThreadHeader) {
                    waitingThreadNode.previous.next = waitingThreadNode.next;
                    waitingThreadNode.next.previous = waitingThreadNode.previous;
                }
            }
            
            // Return the waiting-thread node to the cache
            synchronized (waitingThreadCacheHeader) {
                if (waitingThreadCacheSize < maximumWaitingThreadCacheSize) {
                    waitingThreadNode.previous = null;
                    waitingThreadNode.data = null;
                    waitingThreadNode.next = waitingThreadCacheHeader.next;
                    waitingThreadCacheHeader.next = waitingThreadNode;
                    waitingThreadCacheSize++;
                }
            }
                    
            return returnValue;
            
        }

    }
    
    /**
     * Removes and returns the first object from the front of the queue.  If no object is available, blocks indefinitely until
     * an object becomes available (in which case it returns the object) or the Queue instance is closed (in which case it
     * returns null).  A convenience method for use when the queue is single-ended
     * @see #remove(long)
     * @see #peek()
     * @see #removeFirst()
     * @see #close()
     */
    public Object remove() {
        return removeFirst();
    }
    
    /**
     * Removes and returns the first object from the back of the queue.  If no object is available, blocks indefinitely until
     * an object becomes available (in which case it returns the object) or the Queue instance is closed (in which case it
     * returns null)
     * @see #removeFirst()
     * @see #removeLast(long)
     * @see #close()
     */
    public Object removeLast() {
        // The node that will hold the current thread in a list for ordering purposes if there is nothing to return from
        // the queue.  This needs to be assigned inside the main synchronized block and used outside of it, hence its
        // declaration here.
        WaitingThreadNode waitingThreadNode; 
        
        synchronized (lock) {
            if (size > 0) { // if there is something in the queue, we will immediately return it
                
                // Get the node containing the element to return
                Node node = header.previous;
                Object data = node.data; // the return value
                
                // Remove the node containing the element from the list of elements
                node.next.previous = node.previous;
                node.previous.next = node.next;
                size--;
                
                // If appropriate, cache the node instead of discarding it, so that it may be used during the next
                // insertion
                if (nodeCacheSize < maximumNodeCacheSize) {
                    node.next = nodeCacheHeader.next;
                    nodeCacheHeader.next = node;
                    
                    // this is a necessary step to ensure that the previous node can be garbage collected;
                    // otherwise, the cache could grow indefinitely
                    node.previous = null; 
                    
                    node.data = null;
                    nodeCacheSize++;
                }
                
                return data;
            }
            else if (closed) { // Note that if there is something in the queue, we will return it even if the queue is closed
                return null;
            }
            
            
            // If we have reached this point, the queue currently contains no elements.  Our next step is to insert the waiting
            // thread into a list of waiting threads, so that we can return future queue input to waiting threads in the 
            // appropriate order.  A doubly-linked list is used for this, so that if the thread's wait time expires before it 
            // has received data, it can easily remove ITSELF from the list of waiting threads without damaging the structure.
            
            
            // Acquire a node to hold the waiting thread, either from the cache of such nodes or by creating a new one
            synchronized (waitingThreadCacheHeader) {
                if (waitingThreadCacheSize > 0) {
                    waitingThreadNode = waitingThreadCacheHeader.next;
                    waitingThreadCacheHeader.next = waitingThreadNode.next;
                    waitingThreadCacheSize--;
                }
                else {
                    waitingThreadNode = new WaitingThreadNode();
                }
            }
            
            waitingThreadNode.thread = Thread.currentThread();
            waitingThreadNode.awaitingRemove = true; // Indicates that this thread is waiting to remove a value (versus peek at it)
            waitingThreadNode.receivedOutput = false; // update flag
            
            // Since modification of the waiting-thread list may occur outside of code synchronized on the
            // main monitor (the 'lock' object), we must synchronize on the list separately during modification
            synchronized (waitingThreadHeader) {
                // this list is circular, so the header node's previous link points to the current last item in the list
                waitingThreadNode.previous = waitingThreadHeader.previous;
                waitingThreadNode.previous.next = waitingThreadNode;
                waitingThreadNode.next = waitingThreadHeader;
                waitingThreadHeader.previous = waitingThreadNode;
            }
        }
        
        // Since the current thread itself is guaranteed to have a unique monitor, we use that for the wait/notify mechanism.
        // This allows us to guarantee that the thread we wake up is the one we're after (see the addXXX methods)
        synchronized (waitingThreadNode.thread) {
            // This first check is necessary because the thread may have already received some output
            // (since we're now outside the synchronized block)
            if (!waitingThreadNode.receivedOutput) {
                try {
                    // May be notified by the addXXX and close methods, or may be externally interrupted-- in
                    // any case, it will be time to wake up
                    waitingThreadNode.thread.wait();
                } catch (InterruptedException ie) {}  
            }
        
            // This is either the next input to the queue, or null if the thread awoke before there was an object to return
            Object returnValue = waitingThreadNode.data;
    
            if (!waitingThreadNode.receivedOutput) { // If this is true, the thread awoke before the next input to the queue
                // The node is still in the list of waiting threads, and must be removed
                synchronized (waitingThreadHeader) {
                    waitingThreadNode.previous.next = waitingThreadNode.next;
                    waitingThreadNode.next.previous = waitingThreadNode.previous;
                }
            }
            
            // Return the waiting-thread node to the cache
            synchronized (waitingThreadCacheHeader) {
                if (waitingThreadCacheSize < maximumWaitingThreadCacheSize) {
                    waitingThreadNode.previous = null;
                    waitingThreadNode.data = null;
                    waitingThreadNode.next = waitingThreadCacheHeader.next;
                    waitingThreadCacheHeader.next = waitingThreadNode;
                    waitingThreadCacheSize++;
                }
            }
                    
            return returnValue;
        }
    }
    
    /**
     * Removes and returns the first object from the front of the queue.  If no object is available, waits for the specified
     * number of milliseconds until an object becomes available (in which case it returns the object) or the Queue
     * instance is closed (in which case it returns null)
     * @see #removeLast(long)
     * @see #remove()
     * @see #close()
     */
    public Object removeFirst(long _timeout) {
        if (_timeout < 0) {
            throw new IllegalArgumentException("Invalid argument");
        }
       
        // The node that will hold the current thread in a list for ordering purposes if there is nothing to return from
        // the queue.  This needs to be assigned inside the main synchronized block and used outside of it, hence its
        // declaration here.
        WaitingThreadNode waitingThreadNode; 
        
        synchronized (lock) {
            if (size > 0) { // if there is something in the queue, we will immediately return it
                
                // Get the node containing the element to return
                Node node = header.next;
                Object data = node.data; // the return value
                
                // Remove the node containing the element from the list of elements
                node.next.previous = node.previous;
                node.previous.next = node.next;
                size--;
                
                // If appropriate, cache the node instead of discarding it, so that it may be used during the next
                // insertion
                if (nodeCacheSize < maximumNodeCacheSize) {
                    node.next = nodeCacheHeader.next;
                    nodeCacheHeader.next = node;
                    
                    // this is a necessary step to ensure that the previous node can be garbage collected;
                    // otherwise, the cache could grow indefinitely
                    node.previous = null; 
                    
                    node.data = null;
                    nodeCacheSize++;
                }
                
                return data;
            }
            else if (closed) { // Note that if there is something in the queue, we will return it even if the queue is closed
                return null;
            }
            else if (_timeout < 0) { 
                return null;
            }
            
            
            // If we have reached this point, the queue currently contains no elements.  Our next step is to insert the waiting
            // thread into a list of waiting threads, so that we can return future queue input to waiting threads in the 
            // appropriate order.  A doubly-linked list is used for this, so that if the thread's wait time expires before it 
            // has received data, it can easily remove ITSELF from the list of waiting threads without damaging the structure.
            
            
            // Acquire a node to hold the waiting thread, either from the cache of such nodes or by creating a new one
            synchronized (waitingThreadCacheHeader) {
                if (waitingThreadCacheSize > 0) {
                    waitingThreadNode = waitingThreadCacheHeader.next;
                    waitingThreadCacheHeader.next = waitingThreadNode.next;
                    waitingThreadCacheSize--;
                }
                else {
                    waitingThreadNode = new WaitingThreadNode();
                }
            }
            
            waitingThreadNode.thread = Thread.currentThread();
            waitingThreadNode.awaitingRemove = true; // Indicates that this thread is waiting to remove a value (versus peek at it)
            waitingThreadNode.receivedOutput = false; // update flag
            
            // Since modification of the waiting-thread list may occur outside of code synchronized on the
            // main monitor (the 'lock' object), we must synchronize on the list separately during modification
            synchronized (waitingThreadHeader) {
                // this list is circular, so the header node's previous link points to the current last item in the list
                waitingThreadNode.previous = waitingThreadHeader.previous;
                waitingThreadNode.previous.next = waitingThreadNode;
                waitingThreadNode.next = waitingThreadHeader;
                waitingThreadHeader.previous = waitingThreadNode;
            }
        }
        
        // Since the current thread itself is guaranteed to have a unique monitor, we use that for the wait/notify mechanism.
        // This allows us to guarantee that the thread we wake up is the one we're after (see the addXXX methods)
        synchronized (waitingThreadNode.thread) {
            // This first check is necessary because the thread may have already received some output
            // (since we're now outside the synchronized block)
            if (!waitingThreadNode.receivedOutput) {
                try {
                    // May be notified by the addXXX and close methods, or may be externally interrupted-- in
                    // any case, it will be time to wake up
                    waitingThreadNode.thread.wait(_timeout);
                } catch (InterruptedException ie) {}  
            }
        
            // This is either the next input to the queue, or null if the thread awoke before there was an object to return
            Object returnValue = waitingThreadNode.data;
    
            if (!waitingThreadNode.receivedOutput) { // If this is true, the thread awoke before the next input to the queue
                // The node is still in the list of waiting threads, and must be removed
                synchronized (waitingThreadHeader) {
                    waitingThreadNode.previous.next = waitingThreadNode.next;
                    waitingThreadNode.next.previous = waitingThreadNode.previous;
                }
            }
            
            // Return the waiting-thread node to the cache
            synchronized (waitingThreadCacheHeader) {
                if (waitingThreadCacheSize < maximumWaitingThreadCacheSize) {
                    waitingThreadNode.previous = null;
                    waitingThreadNode.data = null;
                    waitingThreadNode.next = waitingThreadCacheHeader.next;
                    waitingThreadCacheHeader.next = waitingThreadNode;
                    waitingThreadCacheSize++;
                }
            }
                    
            return returnValue;
            
        }

    }

    /**
     * Removes and returns the first object from the front of the queue.  If no object is available, waits for the specified
     * number of milliseconds until an object becomes available (in which case it returns the object) or the Queue
     * instance is closed (in which case it returns null).  A convenience method for use when the queue is single-ended
     * @see #remove()
     * @see #peek(long)
     * @see #removeFirst(long)
     * @see #close()
     */
    public Object remove(long _timeout) {
        return removeFirst(_timeout);
    }

    /**
     * Removes and returns the first object from the back of the queue.  If no object is available, waits for the specified
     * number of milliseconds until an object becomes available (in which case it returns the object) or the Queue
     * instance is closed (in which case it returns null)
     * @see #removeFirst(long)
     * @see #remove()
     * @see #close()
     */
    public Object removeLast(long _timeout) {
        if (_timeout < 0) {
            throw new IllegalArgumentException("Invalid argument");
        }
       
        // The node that will hold the current thread in a list for ordering purposes if there is nothing to return from
        // the queue.  This needs to be assigned inside the main synchronized block and used outside of it, hence its
        // declaration here.
        WaitingThreadNode waitingThreadNode; 
        
        synchronized (lock) {
            if (size > 0) { // if there is something in the queue, we will immediately return it
                
                // Get the node containing the element to return
                Node node = header.previous;
                Object data = node.data; // the return value
                
                // Remove the node containing the element from the list of elements
                node.next.previous = node.previous;
                node.previous.next = node.next;
                size--;
                
                // If appropriate, cache the node instead of discarding it, so that it may be used during the next
                // insertion
                if (nodeCacheSize < maximumNodeCacheSize) {
                    node.next = nodeCacheHeader.next;
                    nodeCacheHeader.next = node;
                    
                    // this is a necessary step to ensure that the previous node can be garbage collected;
                    // otherwise, the cache could grow indefinitely
                    node.previous = null; 
                    
                    node.data = null;
                    nodeCacheSize++;
                }
                
                return data;
            }
            else if (closed) { // Note that if there is something in the queue, we will return it even if the queue is closed
                return null;
            }
            else if (_timeout < 0) { 
                return null;
            }
            
            
            // If we have reached this point, the queue currently contains no elements.  Our next step is to insert the waiting
            // thread into a list of waiting threads, so that we can return future queue input to waiting threads in the 
            // appropriate order.  A doubly-linked list is used for this, so that if the thread's wait time expires before it 
            // has received data, it can easily remove ITSELF from the list of waiting threads without damaging the structure.
            
            
            // Acquire a node to hold the waiting thread, either from the cache of such nodes or by creating a new one
            synchronized (waitingThreadCacheHeader) {
                if (waitingThreadCacheSize > 0) {
                    waitingThreadNode = waitingThreadCacheHeader.next;
                    waitingThreadCacheHeader.next = waitingThreadNode.next;
                    waitingThreadCacheSize--;
                }
                else {
                    waitingThreadNode = new WaitingThreadNode();
                }
            }
            
            waitingThreadNode.thread = Thread.currentThread();
            waitingThreadNode.awaitingRemove = true; // Indicates that this thread is waiting to remove a value (versus peek at it)
            waitingThreadNode.receivedOutput = false; // update flag
            
            // Since modification of the waiting-thread list may occur outside of code synchronized on the
            // main monitor (the 'lock' object), we must synchronize on the list separately during modification
            synchronized (waitingThreadHeader) {
                // this list is circular, so the header node's previous link points to the current last item in the list
                waitingThreadNode.previous = waitingThreadHeader.previous;
                waitingThreadNode.previous.next = waitingThreadNode;
                waitingThreadNode.next = waitingThreadHeader;
                waitingThreadHeader.previous = waitingThreadNode;
            }
        }
        
        // Since the current thread itself is guaranteed to have a unique monitor, we use that for the wait/notify mechanism.
        // This allows us to guarantee that the thread we wake up is the one we're after (see the addXXX methods)
        synchronized (waitingThreadNode.thread) {
            // This first check is necessary because the thread may have already received some output
            // (since we're now outside the synchronized block)
            if (!waitingThreadNode.receivedOutput) {
                try {
                    // May be notified by the addXXX and close methods, or may be externally interrupted-- in
                    // any case, it will be time to wake up
                    waitingThreadNode.thread.wait(_timeout);
                } catch (InterruptedException ie) {}  
            }
            
            // This is either the next input to the queue, or null if the thread awoke before there was an object to return
            Object returnValue = waitingThreadNode.data;
    
            if (!waitingThreadNode.receivedOutput) { // If this is true, the thread awoke before the next input to the queue
                // The node is still in the list of waiting threads, and must be removed
                synchronized (waitingThreadHeader) {
                    waitingThreadNode.previous.next = waitingThreadNode.next;
                    waitingThreadNode.next.previous = waitingThreadNode.previous;
                }
            }
            
            // Return the waiting-thread node to the cache
            synchronized (waitingThreadCacheHeader) {
                if (waitingThreadCacheSize < maximumWaitingThreadCacheSize) {
                    waitingThreadNode.previous = null;
                    waitingThreadNode.data = null;
                    waitingThreadNode.next = waitingThreadCacheHeader.next;
                    waitingThreadCacheHeader.next = waitingThreadNode;
                    waitingThreadCacheSize++;
                }
            }
                    
            return returnValue;
        }
    }

    /**
     * Removes and returns all objects from the queue.  If no object is available, immediately returns an empty array
     * @see #close()
     */
    public Object[] removeAll() {
        synchronized (lock) {
            if (size == 0) {
                return EMPTY_OBJECT_ARRAY;
            }
            Object[] returnValue = new Object[size];
            
            
            
            return returnValue;
        }
    }

    /**
     * Returns the first object from the front of the queue without removing it.  If no object is available, blocks
     * indefinitely until an object becomes available (in which case it returns the object) or the Queue instance is
     * closed (in which case it returns null)
     * @see #peekLast()
     * @see #removeFirst()
     * @see #peekFirst(long)
     * @see #close()
     */
    public Object peekFirst() {
        // The node that will hold the current thread in a list for ordering purposes if there is nothing to return from
        // the queue.  This needs to be assigned inside the main synchronized block and used outside of it, hence its
        // declaration here.
        WaitingThreadNode waitingThreadNode; 
        
        synchronized (lock) {
            if (size > 0) { // if there is something in the queue, we will immediately return it
                return header.next.data;
            }
            else if (closed) { // Note that if there is something in the queue, we will return it even if the queue is closed
                return null;
            }
            
            
            // If we have reached this point, the queue currently contains no elements.  Our next step is to insert the waiting
            // thread into a list of waiting threads, so that we can return future queue input to waiting threads in the 
            // appropriate order.  A doubly-linked list is used for this, so that if the thread's wait time expires before it 
            // has received data, it can easily remove ITSELF from the list of waiting threads without damaging the structure.
            
            
            // Acquire a node to hold the waiting thread, either from the cache of such nodes or by creating a new one
            synchronized (waitingThreadCacheHeader) {
                if (waitingThreadCacheSize > 0) {
                    waitingThreadNode = waitingThreadCacheHeader.next;
                    waitingThreadCacheHeader.next = waitingThreadNode.next;
                    waitingThreadCacheSize--;
                }
                else {
                    waitingThreadNode = new WaitingThreadNode();
                }
            }
            
            waitingThreadNode.thread = Thread.currentThread();
            waitingThreadNode.awaitingRemove = false; // Indicates that this thread is waiting to peek at a value (versus remove it)
            waitingThreadNode.receivedOutput = false; // update flag
            
            // Since modification of the waiting-thread list may occur outside of code synchronized on the
            // main monitor (the 'lock' object), we must synchronize on the list separately during modification
            synchronized (waitingThreadHeader) {
                // this list is circular, so the header node's previous link points to the current last item in the list
                waitingThreadNode.previous = waitingThreadHeader.previous;
                waitingThreadNode.previous.next = waitingThreadNode;
                waitingThreadNode.next = waitingThreadHeader;
                waitingThreadHeader.previous = waitingThreadNode;
            }
        }
        
        // Since the current thread itself is guaranteed to have a unique monitor, we use that for the wait/notify mechanism.
        // This allows us to guarantee that the thread we wake up is the one we're after (see the addXXX methods)
        synchronized (waitingThreadNode.thread) {
            // This first check is necessary because the thread may have already received some output
            // (since we're now outside the synchronized block)
            if (!waitingThreadNode.receivedOutput) {
                try {
                    // May be notified by the addXXX and close methods, or may be externally interrupted-- in
                    // any case, it will be time to wake up
                    waitingThreadNode.thread.wait();
                } catch (InterruptedException ie) {}  
            }
        
            // This is either the next input to the queue, or null if the thread awoke before there was an object to return
            Object returnValue = waitingThreadNode.data;
    
            if (!waitingThreadNode.receivedOutput) { // If this is true, the thread awoke before the next input to the queue
                // The node is still in the list of waiting threads, and must be removed
                synchronized (waitingThreadHeader) {
                    waitingThreadNode.previous.next = waitingThreadNode.next;
                    waitingThreadNode.next.previous = waitingThreadNode.previous;
                }
            }
            
            // Return the waiting-thread node to the cache
            synchronized (waitingThreadCacheHeader) {
                if (waitingThreadCacheSize < maximumWaitingThreadCacheSize) {
                    waitingThreadNode.previous = null;
                    waitingThreadNode.data = null;
                    waitingThreadNode.next = waitingThreadCacheHeader.next;
                    waitingThreadCacheHeader.next = waitingThreadNode;
                    waitingThreadCacheSize++;
                }
            }
                    
            return returnValue;
        }
    }

    /**
     * Returns the first object from the front of the queue without removing it.  If no object is available, blocks
     * indefinitely until an object becomes available (in which case it returns the object) or the Queue instance is
     * closed (in which case it returns null).  A convenience method for use when the queue is single-ended
     * @see #peekFirst()
     * @see #remove()
     * @see #peek(long)
     * @see #close()
     */
    public Object peek() {
        return peekFirst();
    }

    /**
     * Returns the first object from the back of the queue without removing it.  If no object is available, blocks
     * indefinitely until an object becomes available (in which case it returns the object) or the Queue instance is
     * closed (in which case it returns null)
     * @see #peekFirst()
     * @see #removeLast()
     * @see #peekLast(long)
     * @see #close()
     */
    public Object peekLast() {
        // The node that will hold the current thread in a list for ordering purposes if there is nothing to return from
        // the queue.  This needs to be assigned inside the main synchronized block and used outside of it, hence its
        // declaration here.
        WaitingThreadNode waitingThreadNode; 
        
        synchronized (lock) {
            if (size > 0) { // if there is something in the queue, we will immediately return it
                return header.previous.data;
            }
            else if (closed) { // Note that if there is something in the queue, we will return it even if the queue is closed
                return null;
            }
            
            
            // If we have reached this point, the queue currently contains no elements.  Our next step is to insert the waiting
            // thread into a list of waiting threads, so that we can return future queue input to waiting threads in the 
            // appropriate order.  A doubly-linked list is used for this, so that if the thread's wait time expires before it 
            // has received data, it can easily remove ITSELF from the list of waiting threads without damaging the structure.
            
            
            // Acquire a node to hold the waiting thread, either from the cache of such nodes or by creating a new one
            synchronized (waitingThreadCacheHeader) {
                if (waitingThreadCacheSize > 0) {
                    waitingThreadNode = waitingThreadCacheHeader.next;
                    waitingThreadCacheHeader.next = waitingThreadNode.next;
                    waitingThreadCacheSize--;
                }
                else {
                    waitingThreadNode = new WaitingThreadNode();
                }
            }
            
            waitingThreadNode.thread = Thread.currentThread();
            waitingThreadNode.awaitingRemove = false; // Indicates that this thread is waiting to peek at a value (versus remove it)
            waitingThreadNode.receivedOutput = false; // update flag
            
            // Since modification of the waiting-thread list may occur outside of code synchronized on the
            // main monitor (the 'lock' object), we must synchronize on the list separately during modification
            synchronized (waitingThreadHeader) {
                // this list is circular, so the header node's previous link points to the current last item in the list
                waitingThreadNode.previous = waitingThreadHeader.previous;
                waitingThreadNode.previous.next = waitingThreadNode;
                waitingThreadNode.next = waitingThreadHeader;
                waitingThreadHeader.previous = waitingThreadNode;
            }
        }
        
        // Since the current thread itself is guaranteed to have a unique monitor, we use that for the wait/notify mechanism.
        // This allows us to guarantee that the thread we wake up is the one we're after (see the addXXX methods)
        synchronized (waitingThreadNode.thread) {
            // This first check is necessary because the thread may have already received some output
            // (since we're now outside the synchronized block)
            if (!waitingThreadNode.receivedOutput) {
                try {
                    // May be notified by the addXXX and close methods, or may be externally interrupted-- in
                    // any case, it will be time to wake up
                    waitingThreadNode.thread.wait();
                } catch (InterruptedException ie) {}  
            }
        
            // This is either the next input to the queue, or null if the thread awoke before there was an object to return
            Object returnValue = waitingThreadNode.data;
    
            if (!waitingThreadNode.receivedOutput) { // If this is true, the thread awoke before the next input to the queue
                // The node is still in the list of waiting threads, and must be removed
                synchronized (waitingThreadHeader) {
                    waitingThreadNode.previous.next = waitingThreadNode.next;
                    waitingThreadNode.next.previous = waitingThreadNode.previous;
                }
            }
            
            // Return the waiting-thread node to the cache
            synchronized (waitingThreadCacheHeader) {
                if (waitingThreadCacheSize < maximumWaitingThreadCacheSize) {
                    waitingThreadNode.previous = null;
                    waitingThreadNode.data = null;
                    waitingThreadNode.next = waitingThreadCacheHeader.next;
                    waitingThreadCacheHeader.next = waitingThreadNode;
                    waitingThreadCacheSize++;
                }
            }
                    
            return returnValue;
        }
    }

    /**
     * Returns the first object from the front of the queue without removing it.  If no object is available, waits
     * for the specified number of milliseconds until an object becomes available (in which case it returns the 
     * object) or the Queue instance is closed (in which case it returns null)
     * @see #peekLast(long)
     * @see #removeFirst(long)
     * @see #peekFirst()
     * @see #close()
     */
    public Object peekFirst(long _timeout) {
        if (_timeout < 0) {
            throw new IllegalArgumentException("Invalid timeout");   
        }
        
        // The node that will hold the current thread in a list for ordering purposes if there is nothing to return from
        // the queue.  This needs to be assigned inside the main synchronized block and used outside of it, hence its
        // declaration here.
        WaitingThreadNode waitingThreadNode; 
        
        synchronized (lock) {
            if (size > 0) { // if there is something in the queue, we will immediately return it
                return header.next.data;
            }
            else if (closed) { // Note that if there is something in the queue, we will return it even if the queue is closed
                return null;
            }
            else if (_timeout == 0) {
                return null;
            }
            
            // If we have reached this point, the queue currently contains no elements.  Our next step is to insert the waiting
            // thread into a list of waiting threads, so that we can return future queue input to waiting threads in the 
            // appropriate order.  A doubly-linked list is used for this, so that if the thread's wait time expires before it 
            // has received data, it can easily remove ITSELF from the list of waiting threads without damaging the structure.
            
            
            // Acquire a node to hold the waiting thread, either from the cache of such nodes or by creating a new one
            synchronized (waitingThreadCacheHeader) {
                if (waitingThreadCacheSize > 0) {
                    waitingThreadNode = waitingThreadCacheHeader.next;
                    waitingThreadCacheHeader.next = waitingThreadNode.next;
                    waitingThreadCacheSize--;
                }
                else {
                    waitingThreadNode = new WaitingThreadNode();
                }
            }
            
            waitingThreadNode.thread = Thread.currentThread();
            waitingThreadNode.awaitingRemove = false; // Indicates that this thread is waiting to peek at a value (versus remove it)
            waitingThreadNode.receivedOutput = false; // update flag
            
            // Since modification of the waiting-thread list may occur outside of code synchronized on the
            // main monitor (the 'lock' object), we must synchronize on the list separately during modification
            synchronized (waitingThreadHeader) {
                // this list is circular, so the header node's previous link points to the current last item in the list
                waitingThreadNode.previous = waitingThreadHeader.previous;
                waitingThreadNode.previous.next = waitingThreadNode;
                waitingThreadNode.next = waitingThreadHeader;
                waitingThreadHeader.previous = waitingThreadNode;
            }
        }
        
        // Since the current thread itself is guaranteed to have a unique monitor, we use that for the wait/notify mechanism.
        // This allows us to guarantee that the thread we wake up is the one we're after (see the addXXX methods)
        synchronized (waitingThreadNode.thread) {
            // This first check is necessary because the thread may have already received some output
            // (since we're now outside the synchronized block)
            if (!waitingThreadNode.receivedOutput) {
                try {
                    // May be notified by the addXXX and close methods, or may be externally interrupted-- in
                    // any case, it will be time to wake up
                    waitingThreadNode.thread.wait(_timeout);
                } catch (InterruptedException ie) {}  
            }
        
            // This is either the next input to the queue, or null if the thread awoke before there was an object to return
            Object returnValue = waitingThreadNode.data;
    
            if (!waitingThreadNode.receivedOutput) { // If this is true, the thread awoke before the next input to the queue
                // The node is still in the list of waiting threads, and must be removed
                synchronized (waitingThreadHeader) {
                    waitingThreadNode.previous.next = waitingThreadNode.next;
                    waitingThreadNode.next.previous = waitingThreadNode.previous;
                }
            }
            
            // Return the waiting-thread node to the cache
            synchronized (waitingThreadCacheHeader) {
                if (waitingThreadCacheSize < maximumWaitingThreadCacheSize) {
                    waitingThreadNode.previous = null;
                    waitingThreadNode.data = null;
                    waitingThreadNode.next = waitingThreadCacheHeader.next;
                    waitingThreadCacheHeader.next = waitingThreadNode;
                    waitingThreadCacheSize++;
                }
            }
                    
            return returnValue;
        }
    }
    /**
     * Returns the first object from the front of the queue without removing it.  If no object is available, waits
     * for the specified number of milliseconds until an object becomes available (in which case it returns the 
     * object) or the Queue instance is closed (in which case it returns null).  A convenience method for use when
     * the queue is single-ended
     * @see #peekFirst(long)
     */
    public Object peek(long _timeout) {
        return peek(_timeout);
    }
    

    /**
     * Returns the first object from the back of the queue without removing it.  If no object is available, waits
     * for the specified number of milliseconds until an object becomes available (in which case it returns the 
     * object) or the Queue instance is closed (in which case it returns null)
     * @see #peekFirst(long)
     * @see #removeLast(long)
     * @see #peekLast()
     * @see #close()
     */
    public Object peekLast(long _timeout) {
        if (_timeout < 0) {
            throw new IllegalArgumentException("Invalid timeout");   
        }
        
        // The node that will hold the current thread in a list for ordering purposes if there is nothing to return from
        // the queue.  This needs to be assigned inside the main synchronized block and used outside of it, hence its
        // declaration here.
        WaitingThreadNode waitingThreadNode; 
        
        synchronized (lock) {
            if (size > 0) { // if there is something in the queue, we will immediately return it
                return header.previous.data;
            }
            else if (closed) { // Note that if there is something in the queue, we will return it even if the queue is closed
                return null;
            }
            else if (_timeout == 0) {
                return null;
            }
            
            // If we have reached this point, the queue currently contains no elements.  Our next step is to insert the waiting
            // thread into a list of waiting threads, so that we can return future queue input to waiting threads in the 
            // appropriate order.  A doubly-linked list is used for this, so that if the thread's wait time expires before it 
            // has received data, it can easily remove ITSELF from the list of waiting threads without damaging the structure.
            
            
            // Acquire a node to hold the waiting thread, either from the cache of such nodes or by creating a new one
            synchronized (waitingThreadCacheHeader) {
                if (waitingThreadCacheSize > 0) {
                    waitingThreadNode = waitingThreadCacheHeader.next;
                    waitingThreadCacheHeader.next = waitingThreadNode.next;
                    waitingThreadCacheSize--;
                }
                else {
                    waitingThreadNode = new WaitingThreadNode();
                }
            }
            
            waitingThreadNode.thread = Thread.currentThread();
            waitingThreadNode.awaitingRemove = false; // Indicates that this thread is waiting to peek at a value (versus remove it)
            waitingThreadNode.receivedOutput = false; // update flag
            
            // Since modification of the waiting-thread list may occur outside of code synchronized on the
            // main monitor (the 'lock' object), we must synchronize on the list separately during modification
            synchronized (waitingThreadHeader) {
                // this list is circular, so the header node's previous link points to the current last item in the list
                waitingThreadNode.previous = waitingThreadHeader.previous;
                waitingThreadNode.previous.next = waitingThreadNode;
                waitingThreadNode.next = waitingThreadHeader;
                waitingThreadHeader.previous = waitingThreadNode;
            }
        }
        
        // Since the current thread itself is guaranteed to have a unique monitor, we use that for the wait/notify mechanism.
        // This allows us to guarantee that the thread we wake up is the one we're after (see the addXXX methods)
        synchronized (waitingThreadNode.thread) {
            // This first check is necessary because the thread may have already received some output
            // (since we're now outside the synchronized block)
            if (!waitingThreadNode.receivedOutput) {
                try {
                    // May be notified by the addXXX and close methods, or may be externally interrupted-- in
                    // any case, it will be time to wake up
                    waitingThreadNode.thread.wait(_timeout);
                } catch (InterruptedException ie) {}  
            }
        
            // This is either the next input to the queue, or null if the thread awoke before there was an object to return
            Object returnValue = waitingThreadNode.data;
    
            if (!waitingThreadNode.receivedOutput) { // If this is true, the thread awoke before the next input to the queue
                // The node is still in the list of waiting threads, and must be removed
                synchronized (waitingThreadHeader) {
                    waitingThreadNode.previous.next = waitingThreadNode.next;
                    waitingThreadNode.next.previous = waitingThreadNode.previous;
                }
            }
            
            // Return the waiting-thread node to the cache
            synchronized (waitingThreadCacheHeader) {
                if (waitingThreadCacheSize < maximumWaitingThreadCacheSize) {
                    waitingThreadNode.previous = null;
                    waitingThreadNode.data = null;
                    waitingThreadNode.next = waitingThreadCacheHeader.next;
                    waitingThreadCacheHeader.next = waitingThreadNode;
                    waitingThreadCacheSize++;
                }
            }
            return returnValue;
        }
    }

    /**
     * If a thread is waiting to remove an object from the queue, sends the argument to that thread; otherwise, adds the argument
     * to the end of the queue.  If a thread is waiting to peek at an element, this method adds the argument to the queue AND
     * returns it to the waiting thread.
     * @see #removeLast()
     * @see #isClosed()
     * @throws IllegalStateException if this instance is closed
     */
    public void addLast(Object _object) {
        synchronized (lock) {
            if (closed) {
                throw new IllegalStateException("This instance is closed, and cannot accept input");
            }
            
            synchronized (waitingThreadHeader) {
                if (waitingThreadHeader.next == waitingThreadHeader) { 
                    // if this is true, there are no waiting threads
                    
                    Node node;
                    // Acquire a node in which to store the element
                    // If one is available in the cache, use it; otherwise, create a new node
                    if (nodeCacheSize > 0) {
                        node = nodeCacheHeader.next;
                        nodeCacheHeader.next = node.next;
                        nodeCacheSize--;
                    }
                    else {
                        node = new Node();   
                    }
                    
                    // Populate the node and insert it into the list
                    // The list of elements is a doubly-linked circular list
                    node.data = _object;
                    node.previous = header.previous;
                    node.next = header;
                    node.previous.next = node;
                    node.next.previous = node;
                    size++;
                }
                else { // pass the value to the first waiting thread
                    WaitingThreadNode waitingThreadNode = waitingThreadHeader.next;
                    
                    synchronized (waitingThreadNode.thread) {
                        // Remove the waiting thread from the list of waiting threads                        
                        waitingThreadNode.previous.next = waitingThreadNode.next;
                        waitingThreadNode.next.previous = waitingThreadNode.previous;
                        
                        if (!waitingThreadNode.awaitingRemove) { 
                            // If this is true, the thread is awaiting a peek, so we must still insert the value

                            Node node;
                            // Acquire a node in which to store the element
                            // If one is available in the cache, use it; otherwise, create a new node
                            if (nodeCacheSize > 0) {
                                node = nodeCacheHeader.next;
                                nodeCacheHeader.next = node.next;
                                nodeCacheSize--;
                            }
                            else {
                                node = new Node();   
                            }
                            
                            // Populate the node and insert it into the list
                            // The list of elements is a doubly-linked circular list
                            node.data = _object;
                            node.previous = header.previous;
                            node.next = header;
                            node.previous.next = node;
                            node.next.previous = node;
                            size++;
                        }

                        // The waiting thread will retrieve its data from this field, not directly from the element list
                        waitingThreadNode.data = _object;
                        
                        // Set the update flag on the waiting thread's node
                        // The waiting thread checks this value when it awakes to see if it has returned data
                        // If it hasn't received data, the thread then knows it must remove itself from the list
                        // of waiting threads before exiting
                        waitingThreadNode.receivedOutput = true;  
                        
                        // Wake up the thread so that it can pick up its data
                        waitingThreadNode.thread.notify();
                    }
                }
            }
        }
    }

    /**
     * If a thread is waiting to remove an object from the queue, sends the argument to that thread; otherwise, adds the argument
     * to the end of the queue.  If a thread is waiting to peek at an element, this method adds the argument to the queue AND
     * returns it to the waiting thread.
     * @see #removeLast()
     * @see #isClosed()
     * @throws IllegalStateException if this instance is closed
    */
    public void add(Object _object) {
        addLast(_object);
    }

    /**
     * If a thread is waiting to remove an object from the queue, sends the argument to that thread; otherwise, adds the argument
     * to the front of the queue.  If a thread is waiting to peek at an element, this method adds the argument to the queue AND
     * returns it to the waiting thread.
     * @see #removeLast()
     * @see #isClosed()
     * @throws IllegalStateException if this instance is closed
    */
    public void addFirst(Object _object) {
        synchronized (lock) {
            if (closed) {
                throw new IllegalStateException("This instance is closed, and cannot accept input");
            }
            synchronized (waitingThreadHeader) {
                if (waitingThreadHeader.next == waitingThreadHeader) { 
                    // if this is true, there are no waiting threads
                    
                    Node node;
                    // Acquire a node in which to store the element
                    // If one is available in the cache, use it; otherwise, create a new node
                    if (nodeCacheSize > 0) {
                        node = nodeCacheHeader.next;
                        nodeCacheHeader.next = node.next;
                        nodeCacheSize--;
                    }
                    else {
                        node = new Node();   
                    }
                    
                    // Populate the node and insert it into the list
                    // The list of elements is a doubly-linked circular list
                    node.data = _object;
                    node.next = header.next;
                    node.previous = header;
                    header.next = node;
                    node.next.previous = node;
                    size++;
                }
                else { // pass the value to the first waiting thread
                    WaitingThreadNode waitingThreadNode = waitingThreadHeader.next;
                    
                    synchronized (waitingThreadNode.thread) {
                        waitingThreadNode.previous.next = waitingThreadNode.next;
                        waitingThreadNode.next.previous = waitingThreadNode.previous;
                        
                        if (!waitingThreadNode.awaitingRemove) { 
                            // If this is true, the thread is awaiting a peek, so we must still insert the value

                            Node node;
                            // Acquire a node in which to store the element
                            // If one is available in the cache, use it; otherwise, create a new node
                            if (nodeCacheSize > 0) {
                                node = nodeCacheHeader.next;
                                nodeCacheHeader.next = node.next;
                                nodeCacheSize--;
                            }
                            else {
                                node = new Node();   
                            }
                            
                            // Populate the node and insert it into the list
                            // The list of elements is a doubly-linked circular list
                            node.data = _object;
                            node.next = header.next;
                            node.previous = header;
                            header.next = node;
                            node.next.previous = node;
                            size++;
                        }
                        
                        // The waiting thread will retrieve its data from this field, not directly from the element list
                        waitingThreadNode.data = _object;
                        
                        // Set the update flag on the waiting thread's node
                        // The waiting thread checks this value when it awakes to see if it has returned data
                        // If it hasn't received data, the thread then knows it must remove itself from the list
                        // of waiting threads before exiting
                        waitingThreadNode.receivedOutput = true;  
                        
                        // Wake up the thread so that it can pick up its data
                        waitingThreadNode.thread.notify();
                    }
                }
            }
        }
    }
    
    /**
     * Deletes all contents of the queue.  If the queue is empty, any waiting threads are allowed to continue to wait.
     * To force waiting threads to immediately receive null values, use the {@link #close() close} method
     * @see #close()
     */
    public void clear() {
        synchronized (lock) {
            if (size > 0) {
                // It isn't worth the work of caching the nodes containing elements that are being discarded,
                // so we just throw away all element nodes except the header/tail node
                header.next = header;
                header.previous = header;
                size = 0;
            }
        }
    }

    /**
     * Makes it possible for the queue to accept objects again after it has been closed
     * @see #close()
     * @see #isClosed()
     */
    public void open() {
        synchronized (lock) {
            if (!closed) {
                return;
            }
            closed = false;
        }
    }

    /**
     * Makes it impossible for the queue to accept objects, and wakes up any waiting threads (that will then immediately receive
     * null as return values).  Does NOT clear any elements out of the queue.  Remove and peek operations will still succeed on the
     * queue after it has been closed
     * @see #clear()
     * @see #open()
     * @see #isClosed()
     */
    public void close() {
        synchronized (lock) {
            if (closed) {
                return;
            }
            closed = true;
            if (size == 0) {
                // notify waiting threads
            }
        }
    }

    /**
     * Indicates whether this Queue is currently able to receive objects
     * @see #open()
     * @see #close()
     */
    public boolean isClosed() {
        synchronized (lock) {
            return closed;
        }
    }

    /**
     * Instances of this class hold data elements in the queue.  A separate class is used for data elements and waiting
     * threads to avoid unnecessary overhead (waiting thread nodes contain more data)
     */
    private static final class Node {
        /** The data element being contained in the queue */
        Object data = null;
        /** The next node in the list */
        Node next;
        /** The previous node in the list */
        Node previous;

        Node() {}
    }
    
    private static final class WaitingThreadNode {
        /** The data element to be returned to the waiting thread */
        Object data;
        /** The thread that is awaiting data from the queue */
        Object thread;
        /** The next node in the list */
        WaitingThreadNode next;
        /** The previous node in the list */
        WaitingThreadNode previous;
        /** If this is true, the thread is waiting to remove the next input to the queue-- otherwise, to peek at it */
        boolean awaitingRemove;
        /** If this is true, the data element has been filled and the node has already been removed from the waiting-thread list */
        boolean receivedOutput;

        WaitingThreadNode() {}
    }

}