//////////////////////////////////////////////////////////////////////////////// // Author: Julie Petrusa (991339) // // Program 4, Due date: April 3, 2001 // // This program simulates a simplified version of Bishop's registration. // // Known bugs: none // //////////////////////////////////////////////////////////////////////////////// import java.io.*; // needed in order to do I/O import java.lang.Integer; // needed in order to do parseInt() import java.util.Random; // nedded in order to do Random class RegiSim { //--------------------------------------------------------------------------- // fields private int maxSize; // maximum size of any array private double clock; // holds the time private Student newStudent; // holds a new student private Student CSC_desk; // holds a CSC desk private Student MATH_desk; // holds a MATH desk private StudentQueue CSCqueue; // holds a queue for CSC desk private StudentQueue MATHqueue; // holds a queue for MATH desk private EventQueue toDo; // holds the event queue private Statistics stats; // to do the statistics private RandBox newRB; // to do the random private final double INTERARRIVAL_TIME = 120.0; private final double AVG_COURSE_SIGNUP_TIME = 40.0; //--------------------------------------------------------------------------- // constructor public RegiSim() { maxSize = 1000; // maximum size of any array clock = 0.0; // initialize clock CSC_desk = null; // initialize CSC desk MATH_desk = null; // initialize MATH desk CSCqueue = new StudentQueue(maxSize); // create CSC desk queue MATHqueue = new StudentQueue(maxSize); // create MATH desk queue toDo = new EventQueue(maxSize); // create event queue stats = new Statistics(); // create statistics newRB = new RandBox(); // create random } //--------------------------------------------------------------------------- // method run // -runs the simulation public void run(double simulation_time) { Event removedEvent; // to store event removed from queue CSC_Arrival CSCA = new CSC_Arrival(clock); // create CSC arrival toDo.insert(CSCA); // store on event queue while(clock < simulation_time) // while simulation time { // not finished if(!toDo.isEmpty()) // if queue not empty { removedEvent = toDo.remove(); // get an event removedEvent.process(); // process it } } System.out.println(""); // print average waiting time at the end System.out.print("The average waiting time is: "); System.out.print(stats.get_average_waiting_time()); System.out.println(" seconds"); } //--------------------------------------------------------------------------- //****************************************************************************** //****************************************************************************** class Student { //--------------------------------------------------------------------------- // fields private double time; // stores the time the student arrived //--------------------------------------------------------------------------- // constructor public Student(double arrivalTime) { time = arrivalTime; // time the student arrived } //--------------------------------------------------------------------------- // method CSCcourses // -returns a random number of CSC courses public int CSCcourses() { return 3; } //--------------------------------------------------------------------------- } // end class Student //****************************************************************************** //****************************************************************************** class StudentQueue { //--------------------------------------------------------------------------- // fields private int maxSize; // maximum size of the array private Student[] queueArray; // holds the queue of students private int front; // index number of the first student private int rear; // index number of the last student private int nStudents; // the number of students in the queue //--------------------------------------------------------------------------- // constructor public StudentQueue(int ms) { maxSize = ms; // set the size of the array queueArray = new Student[maxSize]; // create a new array front = 0; // the array is empty rear = -1; // the array is empty nStudents = 0; // no students in the queue yet } //--------------------------------------------------------------------------- // method insert // -inserts a student at the rear of the queue public boolean insert(Student s) { if(isFull()) // check if queue is full return false; if(rear == maxSize-1) // deal with wraparound rear = -1; queueArray[++rear] = s; // increment rear and insert nStudents++; // one more student return true; } //--------------------------------------------------------------------------- // method remove // -removes a student from the front of the queue public Student remove() { Student temp = queueArray[front++]; // get value, increment front if(front == maxSize) // deal with wraparound front = 0; nStudents--; // one less student return temp; } //--------------------------------------------------------------------------- // method isEmpty // -returns true if queue is empty, false otherwise public boolean isEmpty() { return (nStudents==0); } //--------------------------------------------------------------------------- // method isFull // -returns true if queue is full, false otherwise public boolean isFull() { return (nStudents==maxSize); } //--------------------------------------------------------------------------- // method size // -returns the number of students in the queue public int size() { return nStudents; } //--------------------------------------------------------------------------- } // end class StudentQueue //****************************************************************************** //****************************************************************************** abstract class Event { //--------------------------------------------------------------------------- // fields double time; // holds time event takes place //--------------------------------------------------------------------------- // constructor public Event(double t) { time = t; // time event takes place } //--------------------------------------------------------------------------- // method process // -processes the event public abstract void process(); //--------------------------------------------------------------------------- } // end abstract class Event //****************************************************************************** //****************************************************************************** class CSC_Arrival extends Event { //--------------------------------------------------------------------------- // constructor public CSC_Arrival(double t) { super(t); // time event takes place } //--------------------------------------------------------------------------- // method process public void process() { clock = clock + time; // move clock to time of arrival event double NOW; // to hold a temporary time Student newStudent = new Student(clock); // create a new student if(!(CSC_desk == null)) // if the CSC Desk is busy, CSCqueue.insert(newStudent); // insert student in StudentQueue else // else the CSC Desk is free, { CSC_desk = newStudent; // place the student in CSC desk double ranST = AVG_COURSE_SIGNUP_TIME * newStudent.CSCcourses(); NOW = clock + newRB.expo(ranST); // schedule a departure CSC_Departure CSCD = new CSC_Departure(NOW); toDo.insert(CSCD); // store on event queue } NOW = clock + newRB.expo(INTERARRIVAL_TIME); CSC_Arrival CSCA = new CSC_Arrival(NOW); // schedule an arrival toDo.insert(CSCA); // store on event queue System.out.println("Arrival time: " + clock + " seconds");// steps } //--------------------------------------------------------------------------- } // end class CSC_Arrival //****************************************************************************** //****************************************************************************** class CSC_Departure extends Event { //--------------------------------------------------------------------------- // constructor public CSC_Departure(double t) { super(t); // time event takes place } //--------------------------------------------------------------------------- // method process public void process() { clock = clock + time; // update clock double NOW; // to hold temporary value double aTime = CSC_desk.time; // get time student got there double waitingTime = clock - aTime; // time student waited stats.save(waitingTime); // save time CSC_desk = null; // empty the CSC desk if(!CSCqueue.isEmpty()) // if CSC queue is not empty { Student remStudent = CSCqueue.remove(); // get a student CSC_desk = remStudent; // place student at desk double ranST = AVG_COURSE_SIGNUP_TIME * remStudent.CSCcourses(); NOW = clock + newRB.expo(ranST); // schedule a departure CSC_Departure CSCD = new CSC_Departure(NOW); toDo.insert(CSCD); // store event on event queue } System.out.println("Departure time: " + clock + " seconds");// steps } //--------------------------------------------------------------------------- } // end class CSC_Departure //****************************************************************************** //****************************************************************************** class MATH_Arrival extends Event { //--------------------------------------------------------------------------- // constructor public MATH_Arrival(double t) { super(t); // time event takes place } //--------------------------------------------------------------------------- // method process public void process() { // not used because this program assumes that the student only // registers for CSC courses } //--------------------------------------------------------------------------- } // end class MATH_Arrival //****************************************************************************** //****************************************************************************** class MATH_Departure extends Event { //--------------------------------------------------------------------------- // constructor public MATH_Departure(double t) { super(t); // time event takes place } //--------------------------------------------------------------------------- // method process public void process() { // not used because this program assumes that the student only // registers for CSC courses } //--------------------------------------------------------------------------- } // end class MATH_Departure //****************************************************************************** //****************************************************************************** class EventQueue { //--------------------------------------------------------------------------- // fields private Event[] heapArray; // holds the priority queue of events private int maxSize; // maximum size of the array private int size; // number of events in the priority queue //--------------------------------------------------------------------------- // constructor public EventQueue(int ms) { maxSize = ms; // set the size of the array heapArray = new Event[maxSize]; // create a new array size = 0; // no events in priority queue yet } //--------------------------------------------------------------------------- // method isEmpty // -returns true if the priority queue is empty, false otherwise public boolean isEmpty() { return size==0; } //--------------------------------------------------------------------------- // method insert // -inserts an event into the priority queue according to its priority public boolean insert(Event e) { if(size==maxSize) // if array is full, return false; // failure heapArray[size] = e; // insert the new event at the end trickleUp(size++); // trickle it up, one more event return true; // success } //--------------------------------------------------------------------------- // method remove // -removes the event with the highest priority from the priority queue public Event remove() { Event root = heapArray[0]; // save the root heapArray[0] = heapArray[--size]; // root <-- last, one less event trickleDown(0); // trickle down the root return root; // return the removed event } //--------------------------------------------------------------------------- // method trickleUp // -moves the new event up to its proper position public void trickleUp(int index) { int parent = (index-1) / 2; Event bottom = heapArray[index]; while(index > 0 && bottom.time < heapArray[parent].time) { heapArray[index] = heapArray[parent]; // move event down index = parent; // move index up parent = (parent-1) / 2; // parent <-- its parent } heapArray[index] = bottom; } //--------------------------------------------------------------------------- // method trickleDown // -moves the new root down to its proper position public void trickleDown(int index) { int smallerChild; Event top = heapArray[index]; // save the root while(index < size/2) // while event has at least 1 child, { int leftChild = 2*index+1; int rightChild = leftChild+1; // find smaller child if(rightChild < size && heapArray[rightChild].time < heapArray[leftChild].time) smallerChild = rightChild; // (rightChild exists?) else smallerChild = leftChild; // top <= smallerChild? if(heapArray[smallerChild].time >= top.time) break; heapArray[index] = heapArray[smallerChild]; // shift child up index = smallerChild; // go down } heapArray[index] = top; // index <-- root } //--------------------------------------------------------------------------- } // end class EventQueue //****************************************************************************** //****************************************************************************** class Statistics { //--------------------------------------------------------------------------- // fields private int maxSize; // holds maximum size of array private double[] statArray; // holds the array private int size; // holds number of waiting times //--------------------------------------------------------------------------- // constructor public Statistics() { maxSize = 1000; // max size of array statArray = new double[maxSize]; // create array size = 0; // no waited times yet } //--------------------------------------------------------------------------- // method save // -saves each student's waiting time in the array public void save(double waitingTime) { statArray[size] = waitingTime; // save waited time in the array size++; // increment number of waited times } //--------------------------------------------------------------------------- // method get_average_waiting_time // -returns the average waiting time public double get_average_waiting_time() { double total = 0.0; // holds the total double average; // holds the average for(int j=0; j Simulate Bishop's Registration"); System.out.println(" 2 --> Exit the program"); System.out.print("Answer: "); // prompt user for answer System.out.flush(); int answer = getInt(); // read in the user's answer switch (answer) // do what the user wants { case 1: System.out.println(""); RegiSim b = new RegiSim(); // create simulator b.run(5*60*60); // set simulation time break; case 2: value = false; // to end do-while loop break; default: // invalid answer, display error message System.out.println(""); System.out.println("Invalid answer!"); break; } // end switch } while (value != false); System.in.read(); // to view console } // end try catch (IOException e) { System.out.println("IOException"); } // end catch } //--------------------------------------------------------------------------- /* method getString -reads in a string -precondition: -the user has typed in a valid string -postcondition: -if valid string, string is read in -if not valid string, throws IOException -return: -static */ public static String getString() throws IOException { InputStreamReader isr = new InputStreamReader(System.in); BufferedReader br = new BufferedReader(isr); String s = br.readLine(); return s; } //--------------------------------------------------------------------------- /* method getInt -reads in an integer -precondition: -the user has typed in a valid integer -postcondition: -if valid integer, integer is read in -if not valid integer, throws IOException -return: -static */ public static int getInt() throws IOException { String s = getString(); return Integer.parseInt(s); } //--------------------------------------------------------------------------- } // end class RegistrationSimulation