package closedlist;

import openlist.OpenList;

/**
 * OLQueue is a Queue constructed from two OpenLists.
 * @author Robert Keller
 */
public class OLQueue
{
OpenList incoming;
OpenList outgoing;

/**
 * Create an Empty OLQueue
 */
    public OLQueue()
      {
        clear();
      }
    
    /**
     * Add an object to the queue.
     * @param value the value to be added.
     */
    
    public void enqueue(Object value)
      {
        incoming = OpenList.cons(value, incoming);
      }
    
    
    /**
     * @return the object that has been in the queue the longest
     */
    
    public Object dequeue()
      { 
         adjust();
         Object value = outgoing.first();
         outgoing = outgoing.rest();
         return value;
      }
    
    /**
     * @return true if the queue is empty, false otherwise
     */
    
    public boolean isEmpty()
      {
        return outgoing.isEmpty() && incoming.isEmpty();
      }
    
    
    /**
     * @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()
      {
        incoming = OpenList.nil;
        outgoing = OpenList.nil;
     }
    
    /**
     * Adjust checks whether outgoing is empty.
     * If so, it moves objects from incoming, reversing them in the
     * process.
     */
    
    private void adjust()
      {
       if( outgoing.nonEmpty() )
          {
            return;
          }
       
       outgoing = incoming.reverse();
       incoming = OpenList.nil;
      }
    
    
    /**
     * Test program interleaves enqueuing and dequeuing
     * @param arg 
     */
    public static void main(String arg[])
      {
        OLQueue queue = new OLQueue();
        
        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++;
          }
      }
}