CSCI 146: Lab 11 Materials

BRING YOUR TEXTBOOK TO THIS LAB!

The goal of Lab 11 is to enhance the students' understanding of queue operations and of discrete event simulation using queues.

Enhance the car wash simulation program of pp.333-346 as specified in programming project 3 on p.369 of your textbook.
You do not need to embed your method in an interactive program as described in the last sentence of the programming project.
You do not need to read in an expression: you are allowed to hardcode in the infix expression to be converted.
Use the integer queue (IntQueue class) implementation linked here.
Modify the Averager class.
Modify CarWash.java file, containg the CarWash application and and the carWashSimulate method.

The BooleanSource and the Washer classes are provided for your use, but do not need to be modified.


// File: IntQueue.java from the package edu.colorado.collections
// Complete documentation is available from the IntQueue link in:
//   http://www.cs.colorado.edu/~main/docs/

//package edu.colorado.collections;
import java.util.NoSuchElementException;

/******************************************************************************
* An IntQueue is a queue of int values.
*
* Limitations:
*   

*   (1) The capacity of one of these queues can change after it's created, but
*   the maximum capacity is limited by the amount of free memory on the 
*   machine. The constructor, add, clone, 
*   and union will result in an 
*   OutOfMemoryError when free memory is exhausted.
*   

*   (2) A queue's capacity cannot exceed the maximum integer 2,147,483,647
*   (Integer.MAX_VALUE). Any attempt to create a larger capacity
*   results in a failure due to an arithmetic overflow. 
* 
*
* Java Source Code for this class:

*   
*   http://www.cs.colorado.edu/~main/edu/colorado/collections/IntQueue.java
*   
*
* @author Michael Main 
*    (main@colorado.edu) 
*
* @version
*   Jun 12, 1998
*
* @see IntLinkedQueue
* @see ObjectQueue
* @see BooleanQueue
* @see ByteQueue
* @see CharQueue
* @see DoubleQueue
* @see FloatQueue
* @see LongQueue
* @see ShortQueue
******************************************************************************/
public class IntQueue implements Cloneable
{
   // Invariant of the IntQueue class:
   //   1. The number of items in the queue is in the instance variable manyItems.
   //   2. For a non-empty queue, the items are stored in a circular array
   //      beginning at data[front] and continuing through data[rear].
   //   3. For an empty queue, manyItems is zero and data is a reference to an
   //      array, but we don't care about front and rear.
   private int[ ] data;
   private int manyItems; 
   private int front;
   private int rear;


   /**
   * Initialize an empty queue with an initial capacity of 10.  Note that the
   * insert method works efficiently (without needing more
   * memory) until this capacity is reached.
   * @param - none
   * 
Postcondition:

   *   This queue is empty and has an initial capacity of 10.
   * @exception OutOfMemoryError
   *   Indicates insufficient memory for: 
   *   new int[10].
   **/   
   public IntQueue( )
   {
      final int INITIAL_CAPACITY = 10;
      manyItems = 0;
      data = new int[INITIAL_CAPACITY];
      // We don't care about front and rear for an empty queue.
   }

   
   /**
   * Initialize an empty queue with a specified initial capacity. Note that the
   * insert method works efficiently (without needing more
   * memory) until this capacity is reached.
   * @param initialCapacity
   *   the initial capacity of this queue
   * 
Precondition:

   *   initialCapacity is non-negative.
   * 
Postcondition:

   *   This queue is empty and has the given initial capacity.
   * @exception IllegalArgumentException
   *   Indicates that initialCapacity is negative.
   * @exception OutOfMemoryError
   *   Indicates insufficient memory for:
   *   new int[initialCapacity].
   **/   
   public IntQueue(int initialCapacity)
   {
      if (initialCapacity < 0)
         throw new IllegalArgumentException
         ("initialCapacity is negative: " + initialCapacity);
      manyItems = 0;
      data = new int[initialCapacity];
      // We don't care about front and rear for an empty queue.
   }

   
   /**
   * Generate a copy of this queue.
   * @param - none
   * @return
   *   The return value is a copy of this queue. Subsequent changes to the
   *   copy will not affect the original, nor vice versa. Note that the return
   *   value must be type cast to an IntQueue before it can be used.
   * @exception OutOfMemoryError
   *   Indicates insufficient memory for creating the clone.
   **/ 
   public Object clone( )       
   {  // Clone an IntQueue.
      IntQueue answer;
      
      try
      {
         answer = (IntQueue) super.clone( );
      }
      catch (CloneNotSupportedException e)
      { 
         // This exception should not occur. But if it does, it would probably indicate a
         // programming error that made super.clone unavailable. The most comon error
         // The most common error would be forgetting the "Implements Cloneable"
         // clause at the start of this class.
         throw new RuntimeException
         ("This class does not implement Cloneable");
     }
      
      answer.data = (int [ ]) data.clone( );
      
      return answer;
   }        
 
   
   /**
   * Change the current capacity of this queue.
   * @param minimumCapacity
   *   the new capacity for this queue
   * 
Postcondition:

   *   This queue's capacity has been changed to at least minimumCapacity.
   *   If the capacity was already at or greater than minimumCapacity,
   *   then the capacity is left unchanged.
   * @exception OutOfMemoryError
   *   Indicates insufficient memory for: new int[minimumCapacity]. 
   **/
   public void ensureCapacity(int minimumCapacity)
   {
      int biggerArray[ ];
      int n1, n2;
      
      if (data.length >= minimumCapacity)
         // No change needed.
         return;
      else if (manyItems == 0)
         // Just increase the size of the array because the queue is empty.
         data = new int[minimumCapacity];
      else if (front <= rear)
      {  // Create larger array and copy data[front]...data[rear] into it.
         biggerArray = new int[minimumCapacity];
         System.arraycopy(data, front, biggerArray, front, manyItems);
         data = biggerArray;
      }
      else
      {  // Create a bigger array, but be careful about copying items into it. The queue items
         // occur in two segments. The first segment goes from data[front] to the end of the 
         // array, and the second segment goes from data[0] to data[rear]. The variables n1 
         // and n2 will be set to the number of items in these two segments. We will copy
         // these segments to biggerArray[0...manyItems-1].
         biggerArray = new int[minimumCapacity];
         n1 = data.length - front;
         n2 = rear + 1;
         System.arraycopy(data, front, biggerArray, 0, n1);
         System.arraycopy(data, 0, biggerArray, n1, n2);
         front = 0;
         rear = manyItems-1;  
         data = biggerArray;
      }
   }


   /**
   * Accessor method to get the current capacity of this queue. 
   * The insert method works efficiently (without needing
   * more memory) until this capacity is reached.
   * @param - none
   * @return
   *   the current capacity of this queue
   **/
   public int getCapacity( )   
   {
      return data.length;
   }

 
   /**
   * Get the front item, removing it from this queue.
   * @param - none
   * 
Precondition:

   *   This queue is not empty.
   * 
Postcondition:

   *   The return value is the front item of this queue, and the item has
   *   been removed.
   * @exception NoSuchElementException
   *   Indicates that this queue is empty.
   **/    
   public int getFront( )
   {
      int answer;
      
      if (manyItems == 0)
         throw new NoSuchElementException("Queue underflow");
      answer = data[front];
      front = nextIndex(front);
      manyItems--;
      return answer;
   }
   
   
   /**
   * Insert a new item in this queue.  If the addition
   * would take this queue beyond its current capacity, then the capacity is 
   * increased before adding the new item. The new item may be the null
   * reference.
   * @param item
   *   the item to be pushed onto this queue 
   * 
Postcondition:

   *   The item has been pushed onto this queue.
   * @exception OutOfMemoryError
   *   Indicates insufficient memory for increasing the queue's capacity.
   * 
Note:

   *   An attempt to increase the capacity beyond
   *   Integer.MAX_VALUE will cause the queue to fail with an
   *   arithmetic overflow.
   **/    
   public void insert(int item)
   {
      if (manyItems == data.length)
      {
         // Double the capacity and add 1; this works even if manyItems is 0. However, in
         // case that manyItems*2 + 1 is beyond Integer.MAX_VALUE, there will be an 
         // arithmetic overflow and the bag will fail.
         ensureCapacity(manyItems*2 + 1);
      }
      
      if (manyItems == 0)
      {
         front = 0;
         rear = 0;
      }
      else
         rear = nextIndex(rear);
         
      data[rear] = item;
      manyItems++;
   }
              

   /**
   * Determine whether this queue is empty.
   * @param - none
   * @return
   *   true if this queue is empty;
   *   false otherwise. 
   **/
   public boolean isEmpty( )
   {
      return (manyItems == 0);
   }


   private int nextIndex(int i)
   // Precondition: 0 <= i and i < data.length
   // Postcondition: If i+1 is data.length, 
   // then the return value is zero; otherwise
   // the return value is i+1.
   {
      if (++i == data.length)
         return 0;
      else
         return i;
   }

       
   /**
   * Accessor method to determine the number of items in this queue.
   * @param - none
   * @return
   *   the number of items in this queue
   **/ 
   public int size( )   
   {
      return manyItems;
   }

   
   /**
   * Reduce the current capacity of this queue to its actual size (i.e., the
   * number of items it contains).
   * @param - none
   * 
Postcondition:

   *   This queue's capacity has been changed to its current size.
   * @exception OutOfMemoryError
   *   Indicates insufficient memory for altering the capacity. 
   **/   
   public void trimToSize( )
   {
      int trimmedArray[ ];
      int n1, n2;
      
      if (data.length == manyItems)
         // No change needed.
         return;
      else if (manyItems == 0)
         // Just change the size of the array to 0 because the queue is empty.
         data = new int[0];
      else if (front <= rear)
      {  // Create trimmed array and copy data[front]...data[rear] into it.
         trimmedArray = new int[manyItems];
         System.arraycopy(data, front, trimmedArray, front, manyItems);
         data = trimmedArray;
      }
      else
      {  // Create a trimmed array, but be careful about copying items into it. The queue items
         // occur in two segments. The first segment goes from data[front] to the end of the 
         // array, and the second segment goes from data[0] to data[rear]. The variables n1 
         // and n2 will be set to the number of items in these two segments. We will copy
         // these segments to trimmedArray[0...manyItems-1].
         trimmedArray = new int[manyItems];
         n1 = data.length - front;
         n2 = rear + 1;
         System.arraycopy(data, front, trimmedArray, 0, n1);
         System.arraycopy(data, 0, trimmedArray, n1, n2);
         front = 0;
         rear = manyItems-1;  
         data = trimmedArray;
      }
   } 
}


// File: Averager.java from the package edu.colorado.simulations
// Additional javadoc documentation is available from the Averager link at
//   http://www.cs.colorado.edu/~main/docs/

//package edu.colorado.simulations;

/******************************************************************************
* An Averager computes an average of a group of numbers.
*
* Java Source Code for this class:

*   
*   http://www.cs.colorado.edu/~main/edu/colorado/simulations/Averager.java
*   
*
* @author Michael Main 
*    (main@colorado.edu) 
*
* @version
*   Jun 12, 1998
******************************************************************************/
public class Averager
{
   private int count;  // How many numbers have been given to this averager
   private double sum; // Sum of all the numbers given to this averager
                      
   /**
   * Initialize an Averager.
   * param - none
   * 
Postcondition:

   *   This Averager has been initialized and is ready to accept numbers.
   **/
   public Averager( )
   {
       count =0;
       sum = 0;
   }


   /**
   * Give another number to this Averager.
   * @param value
   *   the next number to give to this Averager
   * 
Precondition:

   *   howManyNumbers() < Integer.MAX_VALUE.
   * 
Postcondition:

   *   This Averager has accepted value as the next number.
   * @exceptions IllegalStateException
   *   Indicates that howManyNumbers() is 
   *   Integer.MAX_VALUE.
   **/   
   public void addNumber(double value)
   {
      if (count == Integer.MAX_VALUE)
         throw new IllegalStateException("Too many numbers");
      count++;
      sum += value;
   }
 

   /**
   * Provide an average of all numbers given to this Averager.
   * @param - none
   * @return
   *   the average of all the numbers that have been given to this
   *   Averager
   *   the next number to give to this Averager
   * 
Postcondition:

   *   If howManyNumbers() is zero, then the answer is
   *   Double.NaN ("not a number"). The answer may also be
   *   Double.POSITIVE_INFINITY or
   *   Double.NEGATIVE_INFINITY if there has been an arithmetic
   *   overflow during the summing of all the numbers.
   **/
   public double average( )
   {
      if (count == 0)
         return Double.NaN;
      else
         return sum/count;
   } 


   /**
   * Provide a count of how many numbers have been given to this Averager.
   * @param - none
   * @return
   *   the count of how many numbers have been given to this Averager
   **/
   public int howManyNumbers( )
   {
      return count;
   }
}


// FILE: Carwash.java
// This program illustrates the use of the carWashSimulate method which uses
// a simple queue to simulate cars waiting at a car wash.

import java.io.IOException;
//import edu.colorado.collections.IntQueue;
//import edu.colorado.simulations.BooleanSource;
//import edu.colorado.simulations.Washer;
//import edu.colorado.simulations.Averager;

/******************************************************************************
* The CarWash Java application illustrates the use of
* the carWashSimulate method with the following values:
*   
*   
washTime = 240
*   
arrivalTime = 0.0025
*   
totalTime = 6000
*   
*
* 
Java Source Code for this class:

*   
*   http://www.cs.colorado.edu/~main/applications/CarWash.java
*   
*
* @author Michael Main 
*    (main@colorado.edu) 
*
* @version
*   Jun 12, 1998
******************************************************************************/
public class CarWash
{
   /**
   * The main method activates carWashSimulate with the values:
   *   
   *   
washTime = 240
   *   
arrivalTime = 0.0025
   *   
totalTime = 6000
   *   
   * 
The String argument (args) is not used in
   * this implementation.
   **/
   public static void main(String[ ] args)
   {
      final int WASHTIME = 240;
      final double ARRIVALPROB = 0.0025;
      final int TOTALTIME = 6000;
      
      carWashSimulate(WASHTIME, ARRIVALPROB, TOTALTIME);
   }
    
   
   /**
   * Simulate the running of a car washer for a specified amount of time.
   * @param washTime
   *   the number of seconds required to wash one car
   * @param arrivalProb
   *   the probability of a customer arriving in any second, for example
   *   0.1 is 10%
   * @param totalTime
   *   the total number of seconds for the simulation
   * 
Precondition:

   *   washTime and totalTime are positive;
   *   arrivalProb lies in the range 0 to 1.
   * 
Postcondition:

   *   The method has simulated a car wash where washTime is the
   *   number of seconds needed to wash one car, arrivalProb is
   *   the probability of a customer arriving in any second, and
   *   totalTime is the total number of seconds for the
   *   simulation. Before the simulation, the method has written its three
   *   parameters to System.out. After the simulation, the method
   *   has written two pieces of information to System.out:
   *   (1) The number of cars washed, and (2) The average waiting time for
   *   customers that had their cars washed. (Customers that are still in the 
   *   queue are not included in this average).
   * @exception java.lang.IllegalArgumentException
   *   Indicates that one of the arguments violates the precondition.
   **/
   public static void carWashSimulate
   (int washTime, double arrivalProb, int totalTime)

   {
      IntQueue arrivalTimes = new IntQueue( );  
      int next;
      BooleanSource arrival = new BooleanSource(arrivalProb);
      Washer machine = new Washer(washTime);
      Averager waitTimes = new Averager( );
      int currentSecond;
  
      // Write the parameters to System.out.
      System.out.println("Seconds to wash one car: " + washTime);
      System.out.print("Probability of customer arrival during a second: ");
      System.out.println(arrivalProb);
      System.out.println("Total simulation seconds: " + totalTime); 
   
      // Check the precondition:
      if (washTime <= 0 || arrivalProb < 0 || arrivalProb > 1 || totalTime < 0)
         throw new IllegalArgumentException("Values out of range"); 

      for (currentSecond = 0; currentSecond < totalTime; currentSecond++)
      {  // Simulate the passage of one second of time.

         // Check whether a new customer has arrived.
         if (arrival.query( ))
            arrivalTimes.insert(currentSecond);
  
         // Check whether we can start washing another car.
         if ((!machine.isBusy( ))  &&  (!arrivalTimes.isEmpty( )))
         {
            next = arrivalTimes.getFront( );
            waitTimes.addNumber(currentSecond - next);
            machine.startWashing( );
         }

         // Subtract one second from the remaining time in the current wash cycle.
         machine.reduceRemainingTime( );
      }

      // Write the summary information about the simulation.
      System.out.println("Customers served: " + waitTimes.howManyNumbers( )); 
      if (waitTimes.howManyNumbers( ) > 0)
         System.out.println("Average wait: " + waitTimes.average( ) + " sec");
   }
    
}



// File: BooleanSource.java from the package edu.colorado.simulations
// Additional javadoc documentation is available from the BooleanSource link at
//   http://www.cs.colorado.edu/~main/docs/

//package edu.colorado.simulations;

/******************************************************************************
* A BooleanSource provides a random sequence of boolean values.
* Java Source Code for this class:

*   
*   http://www.cs.colorado.edu/~main/edu/colorado/simulations/BooleanSource.java
*   
*
* @author Michael Main 
*    (main@colorado.edu) 
*
* @version
*   Jun 12, 1998
******************************************************************************/
public class BooleanSource
{
   private double probability; // The approximate probability of query( ) returning true.
                      
   /**
   * Initialize a BooleanSource.
   * @param p
   *   a probability
   * 
Precondition:

   *   0 <= p and p <= 1.
   * 
Postcondition:

   *   This BooleanSource has been initialized so that
   *   p is the approximate probability of returning
   *   true in any subsequent activation of the
    *  query method.
   * @exceptions IllegalArgumentException
   *   Indicates that p is outside of its legal range.
   **/
   public BooleanSource(double p)
   {
       if ((p < 0) || (1 < p))
           throw new IllegalArgumentException("Illegal p: " + p);
       probability = p;
   }

   /**
   * Get the next value from this BooleanSource.
   * @param - none
   * @return
   *   The return value is either true or false,
   *   with the probability of a true value being determined
   *   by the argument that was given to the constructor.
   **/   
   public boolean query( )
   {
      return (Math.random( ) < probability);
   }
 
}



// File: Washer.java from the package edu.colorado.simulations
// Additional javadoc documentation is available from the Washer link at
//   http://www.cs.colorado.edu/~main/docs/

//package edu.colorado.simulations;

/******************************************************************************
* An Washer simulates a simple washing machine.
*
* Java Source Code for this class:

*   
*   http://www.cs.colorado.edu/~main/edu/colorado/simulations/Washer.java
*   
*
* @author Michael Main 
*    (main@colorado.edu) 
*
* @version
*   Jun 12, 1998
******************************************************************************/
public class Washer
{
   private int secondsForWash; // Seconds for a single wash
   private int washTimeLeft;   // Seconds until this washer is no longer busy

                      
   /**
   * Initialize a washer.
   * param s
   *   the number of seconds required for one wash cyle of this washer
   * 
Postcondition:

   *   This washer has been initialized so that it takes strue if this washer is busy (in a wash cycle);
   *   otherwise false
   **/   
   public boolean isBusy( )
   {
      return (washTimeLeft > 0);
   }
 

   /**
   * Reduce the remaining time in the current wash cycle by one second.
   * @param - none
   * 
Postcondition:

   *   If a car is being washed, then the remaining time in the current
   *   wash cycle has been reduced by one second.
   **/
   public void reduceRemainingTime( )
   {
      if (washTimeLeft > 0)
         washTimeLeft--;
   } 


   /**
   * Start a wash cycle going for this washer.
   * @param - none
   * 
Precondition:

   *   isBusy() is false.
   * 
Postcondition:

   *   This washer has started simulating one wash cycle. Therefore, 
   *   isBusy() will return true until the required
   *   number of simulated seonds have passed.
   * @exceptions IllegalStateException
   *   Indicates that this washer is busy.
   **/
   public void startWashing( )
   {
      if (washTimeLeft > 0)
         throw new IllegalStateException("Washer is already busy.");
      washTimeLeft = secondsForWash;
   }
   
}