package closedlist;

/**
 * OLQueue is a Queue constructed from two OpenLists.
 * @author Robert Keller
 */
public class BoxQueue
{
/**
 * head points to the Box containing the oldest Object in the queue
 */
Box head;

/**
 * tail points to the Box containing the newest Object in the queue
 */
Box tail;


  /**
   * Box is an inner class representing a single box in a linked list.
   * Because it is inner, we do go to great lengths to provide encapsulation.
   * However, a construct makes for convenient coding.
   */
  class Box
    {
       /**
        * The value part of the Box.
        */

       Object value;
       
       /**
        * A pointer to the next newer Box in the list, or null if there is none
        */
       
       Box next;
       
       /**
        * Create a Box containing a value and a pointer to the next Box
        * in the list.
        * @param value
        * @param next 
        */
       
       Box(Object value, Box next)
         {
           this.value = value;
           this.next = next;
         }
    }


    /**
     * Create an Empty OLQueue
     */
    public BoxQueue()
      {
        clear();
      }
    
    
    /**
     * Add an object to the queue.
     * @param value the value to be added.
     */
    
    public void enqueue(Object value)
      {
        if( isEmpty() )
          {
            // The queue was empty, so we start it with a single box
            // containing the new value, to which both head and tail will point.
            
            head = tail = new Box(value, null);
            return;
          }
        
        // The queue was not empty, so add to the tail a new Box containing
        // the new value, to which the old tail will now point.
        // Note that these chained assignments are executed from right to left.
        
        tail = tail.next = new Box(value, null);
     }
    
    
    /**
     * @return the object that has been in the queue the longest
     */
    
    public Object dequeue()
      { 
         Object value = head.value;
         
         // After reserving the value in the head box, replace the head
         // with the box to which the head points.
         // "Make head point to where head.next" points. 
         // The new head could be null, in which case the queue is considered
         // empty.
         head = head.next;
         return value;
      }
    
    
    /**
     * @return true if the queue is empty, false otherwise
     */
    
    public boolean isEmpty()
      {
        return head == null;
      }
    
    
    /**
     * @return true if the queue is non-empty, false otherwise
     */
     
    public boolean nonEmpty()
      {
        return !isEmpty();
      }
    
    
    /**
     * Clear all objects from the queue.
     */
    
    public final void clear()
      {
        head = tail = null;
     }
    
   
    /**
     * Test program interleaves enqueuing and dequeuing
     * @param arg 
     */
    
    public static void main(String arg[])
      {
        BoxQueue queue = new BoxQueue();
        
        int expectedOut = 0;
 
        for( int i = 0; i < 100; i++ )
          {
            queue.enqueue(i);
            if( (i/10)%2 == 1 )
              {
                for( int j = 0; queue.nonEmpty() && j < i/10; j++ )
                  {
                  int actualOut = (Integer)queue.dequeue();
                  if( actualOut != expectedOut++ )
                    {
                     System.out.println("Queue test fails at " + expectedOut
                                       + ", actualOut = " + actualOut);
                     break;
                     }
                  }
              }
          }
        
         while( queue.nonEmpty() )
          {
            int actualOut = (Integer)queue.dequeue();
            if( actualOut != expectedOut++ )
              {
                System.out.println("Queue test fails at " + expectedOut
                                 + ", actualOut = " + actualOut);
                break;
              }
            expectedOut++;
          }
      }
}