simulation.java

国外的数据结构与算法分析用书

import java.io.*;
import dslib.base.*;
import dslib.dispenser.LinkedPqUos;
import dslib.exception.*;

/**	A simple discrete event-driven simulation of a waiting line.  There is one
	cashier who services customers who arrive to purchase tickets for a concert.
	There are two scheduled events: arrival of the next set of customers
	and finishing of the service of a customer. */
public class Simulation
{
	/**	The priority queue of events waiting to be executed. */
	public static LinkedPqUos eventslist = new LinkedPqUos();

	/**	The cashier from whom tickets are purchased. */
	public static Cashier cashier = new Cashier();

	/** The queue in which customers wait for service. */
	public static WaitingLine waitingLine = new WaitingLine();

	/**	The current time in the simulation. */
	public static int time = 0;

	/**	Initialize and run the simulation.
		Analysis: Time = O(number of events * maximum pq size), worst case */
	public Simulation() throws IOException
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		/*	Print the headers for the trace information. */
		System.out.println(FormatUos.pad("Time", 4, 'r') + FormatUos.pad("", 7, 'c') 
				+ FormatUos.pad("Event type", 14, 'l') 
				+ FormatUos.pad("Customer", 9, 'r')
				+ FormatUos.pad("Sched time", 12, 'r')
				+ FormatUos.pad("Wait time", 11, 'r')
				+ FormatUos.pad("Idle time", 11, 'r'));
	
		/*	Initialize the initial event: customers arriving at time 10. */
		NewArrivalEvent firstArrivalEvent = new NewArrivalEvent(10);
		eventslist.insert(firstArrivalEvent);
		System.out.println(FormatUos.pad(0, 4, 'r') + FormatUos.pad("sched", 7, 'c')
				+ FormatUos.pad("first arrivals", 14, 'l')
				+ FormatUos.pad("", 9, 'c')
				+ FormatUos.pad (10, 12, 'r') + "\n");

		while(!eventslist.isEmpty())
		{
			Event e = (Event)eventslist.minItem();
			eventslist.deleteMin();
			time = e.time;
			e.execute();
			/*	Used to pause the output so that the trace information can be read. */
			String temp = br.readLine();
		}
		System.out.print("\nThe average waiting time is ");
		System.out.println((double)Math.round(
				((double)waitingLine.summationWaitingTimes 
				/ NewArrivalEvent.numberOfCustomers) * 100) / 100);
		System.out.print("The percentage of the time that the cashier was idle is ");
		System.out.print((double)Math.round(((double)cashier.totalIdleTime / time)
				* 1000) / 10);
		System.out.println("%");
	}
}