{
private final T t;
private final U u;
/**
* Creates a {@code Pair} of items.
*
* @param t first item of the pair
* @param u second item of the pair
**/
public Pair(T t, U u) {
this.t = t;
this.u = u;
}
/**
* Returns the first item of the pair.
*
* @return the first item of the pair
*/
public T first() {
return this.t;
}
/**
* Returns the second item of the pair.
*
* @return the second item of the pair
*/
public U second() {
return this.u;
}
/**
* Returns a string representation of this pair enclosed in ({@code "()"}).
* The two elements are separated by the characters {@code ", "} (comma and space).
* Elements are converted to strings as by {@link String#valueOf(Object)}.
*
* @return a string representation of this list
*/
@Override
public String toString() {
return "(" + this.t + ", " + this.u + ")";
}
}
import java.util.Comparator;
import java.util.PriorityQueue;
/**
* An immutable and unbounded priority queue based on a priority heap.
* The elements of the priority queue are ordered according to their
* a {@link Comparator} provided at queue construction time. A priority
* queue does not permit {@code null} elements.
*
* The head of this queue is the least element
* with respect to the specified ordering. If multiple elements are
* tied for least value, the head is one of those elements -- ties are
* broken arbitrarily. The queue retrieval operation {@code poll},
* access the element at the head of the queue.
*
*
A priority queue is unbounded, but has an internal
* capacity governing the size of an array used to store the
* elements on the queue. It is always at least as large as the queue
* size. As elements are added to a priority queue, its capacity
* grows automatically. The details of the growth policy are not
* specified.
*
* @author cs2030
* @param the type of elements held in this queue
*/
public class PQ {
private final PriorityQueue pq;
/**
* Creates a {@code PQ} with the default initial capacity and
* whose elements are ordered according to the specified comparator.
*
* @param comparator the comparator that will be used to order this
* priority queue.
*/
public PQ(Comparator comparator) {
this.pq = new PriorityQueue(comparator);
}
private PQ(PQ source) {
this.pq = new PriorityQueue(source.pq);
}
/**
* Returns {@code true} if this collection contains no elements.
*
* @return {@code true} if this collection contains no elements
*/
public boolean isEmpty() {
return this.pq.isEmpty();
}
/**
* Inserts the specified element into this priority queue.
*
* @param element the element to be added to the priority queue
* @return the priority queue with the element added
*/
public PQ add(E element) {
PQ copy = new PQ(this);
copy.pq.add(element);
return copy;
}
/**
* Retrieves and removes the head of this queue,
* or returns {@code null} if this queue is empty.
*
* @return the head of this queue, and the resulting priority queue
* after removal as a {@code Pair}
*/
public Pair> poll() {
PQ copy = new PQ(this);
E t = copy.pq.poll();
return new Pair>(t, copy);
}
/**
* Returns a string representation of this priority queue. The string
* representation consists of a list of elements in the order they are
* returned by its iterator, enclosed in square brackets ({@code "[]"}).
* Adjacent elements are separated by the characters {@code ", "} (comma and space).
* Elements are converted to strings as by {@link String#valueOf(Object)}.
*
* @return a string representation of this list
*/
@Override
public String toString() {
return this.pq.toString();
}
}
import java.util.List;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.Iterator;
/**
* An immutable implementation of the {@code ArrayList} using an
* immutable delegation design pattern.
*
* @author cs2030
* @param the type of elements in this list
*/
public class ImList implements Iterable {
private final List elems;
/**
* Constructs an empty list.
*/
public ImList() {
this.elems = new ArrayList();
}
/**
* Constructs a list containing the elements of the specified list of
* type {@code List}, in the order they are returned by the latter's
* iterator.
*
* @param list the list whose elements are to be placed into this list
* @throws NullPointerException if the specified list is null
*/
public ImList(List list) {
this.elems = new ArrayList(list);
}
/**
* Appends the specified element to the end of this list.
*
* @param elem element to be appended to this list
* @return the list with the element added
*/
public ImList add(E elem) {
ImList newList = new ImList(this.elems);
newList.elems.add(elem);
return newList;
}
/**
* Appends all of the elements in the specified immutable list to
* the end of this list, in the order that they are returned by the
* specified list's Iterator.
*
* @param list list containing elements to be added to this list
* @return the list with the all elements of the specified list appended
* @throws NullPointerException if the specified collection is null
*/
public ImList addAll(ImList list) {
return this.addAll(list.elems);
}
/**
* Appends all of the elements in the specified (@code List) list to
* the end of this list, in the order that they are returned by the
* specified list's Iterator.
*
* @param list list containing elements to be added to this list
* @return the list with the all elements of the specified list appended
* @throws NullPointerException if the specified collection is null
*/
public ImList addAll(List list) {
ImList newList = new ImList(this.elems);
newList.elems.addAll(list);
return newList;
}
/**
* Returns the element at the specified position in this list.
*
* @param index index of the element to return
* @return the element at the specified position in this list
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E get(int index) {
return this.elems.get(index);
}
/**
* Returns the index of the first occurrence of the specified element
* in this list, or -1 if this list does not contain the element.
* More formally, returns the lowest index {@code i} such that
* {@code Objects.equals(obj, get(i))},
* or -1 if there is no such index.
*
* @param obj element to search for
* @return the index of the first occurrence of the specified element in
* this list, or -1 if this list does not contain the element
*/
public int indexOf(Object obj) {
return this.elems.indexOf(obj);
}
/**
* Returns {@code true} if this list contains no elements.
*
* @return {@code true} if this list contains no elements
*/
public boolean isEmpty() {
return this.elems.isEmpty();
}
/**
* Returns an iterator over the elements in this list in proper sequence.
*
* @return an iterator over the elements in this list in proper sequence
*/
public Iterator iterator() {
return this.elems.iterator();
}
/**
* Removes the element at the specified position in this list.
*
* @param index the index of the element to be removed
* @return the list after removal of the element
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public ImList remove(int index) {
if (index < 0 || index >= this.size()) {
return this;
}
ImList newList = new ImList(this.elems);
newList.elems.remove(index);
return newList;
}
/**
* Replaces the element at the specified position in this list with
* the specified element.
*
* @param index index of the element to replace
* @param elem element to be stored at the specified position
* @return the list after replacement of the element
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public ImList set(int index, E elem) {
if (index < 0 || index >= this.size()) {
return this;
}
ImList newList = new ImList(this.elems);
newList.elems.set(index, elem);
return newList;
}
/**
* Returns the number of elements in this list.
*
* @return the number of elements in this list
*/
public int size() {
return this.elems.size();
}
/**
* Sorts this list according to the order induced by the specified
* {@link Comparator}. The sort is stable: this method must not
* reorder equal elements.
*
* All elements in this list must be mutually comparable using the
* specified comparator (that is, {@code c.compare(e1, e2)} must not throw
* a {@code ClassCastException} for any elements {@code e1} and {@code e2}
* in the list).
*
*
If the specified comparator is {@code null} then all elements in this
* list must implement the {@link Comparable} interface and the elements'
* {@linkplain Comparable natural ordering} should be used.
*
* @param cmp the {@code Comparator} used to compare list elements.
* A {@code null} value indicates that the elements'
* {@linkplain Comparable natural ordering} should be used
* @return the sorted list
* @throws ClassCastException if the list contains elements that are not
* mutually comparable using the specified comparator
* @throws UnsupportedOperationException if the list's list-iterator does
* not support the {@code set} operation
* @throws IllegalArgumentException
* (optional)
* if the comparator is found to violate the {@link Comparator}
* contract
*/
public ImList sort(Comparator cmp) {
ImList newList = new ImList(this.elems);
newList.elems.sort(cmp);
return newList;
}
/**
* Returns a string representation of this list. The string
* representation consists of a list of elements in the order they are
* returned by its iterator, enclosed in square brackets ({@code "[]"}).
* Adjacent elements are separated by the characters {@code ", "} (comma and space).
* Elements are converted to strings as by {@link String#valueOf(Object)}.
*
* @return a string representation of this list
*/
@Override
public String toString() {
return this.elems.toString();
}
}
import java.util.Scanner;
import java.util.function.Supplier;
class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
ImList arrivalTimes = new ImList();
Supplier serviceTime = new DefaultServiceTime();
int numOfServers = sc.nextInt();
int qmax = sc.nextInt();
while (sc.hasNextDouble()) {
arrivalTimes = arrivalTimes.add(sc.nextDouble());
}
Simulator sim = new Simulator(numOfServers, qmax, arrivalTimes, serviceTime);
System.out.println(sim.simulate());
sc.close();
}
}
import java.util.function.Supplier;
class DefaultServiceTime implements Supplier {
public Double get() {
return 1.0;
}
}
import java.util.Scanner;
import java.util.function.Supplier;
class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
ImList arrivalTimes = new ImList();
Supplier serviceTime = new DefaultServiceTime();
int numOfServers = sc.nextInt();
int qmax = sc.nextInt();
while (sc.hasNextDouble()) {
arrivalTimes = arrivalTimes.add(sc.nextDouble());
}
Simulator sim = new Simulator(numOfServers, qmax, arrivalTimes, serviceTime);
System.out.println(sim.simulate());
sc.close();
}
}
Sample runs of the program is given below. All of them assumes a default service time of 1.0. You should create your
own input files using vim. You may also create other implementations of Supplier to test out different service
times. Note that your program will be tested against test cases where the service times could be different when
serving different customers.
$ cat 1.in
1 1
0.500
0.600
0.700
$ java Main < 1.in
0.500 1 arrives
0.500 1 serves by 1
0.600 2 arrives
0.600 2 waits at 1
0.700 3 arrives
0.700 3 leaves
1.500 1 done serving by 1
1.500 2 serves by 1
2.500 2 done serving by 1
[0.450 2 1]
$ cat 2.in
1 1
0.500
0.600
0.700
1.500
1.600
1.700
$ java Main < 2.in
0.500 1 arrives
0.500 1 serves by 1
0.600 2 arrives
0.600 2 waits at 1
0.700 3 arrives
0.700 3 leaves
1.500 1 done serving by 1
1.500 2 serves by 1
1.500 4 arrives
1.500 4 waits at 1
1.600 5 arrives
1.600 5 leaves
1.700 6 arrives
1.700 6 leaves
2.500 2 done serving by 1
2.500 4 serves by 1
3.500 4 done serving by 1
[0.633 3 3]
$ cat 3.in
2 1
0.500
0.600
0.700
1.500
1.600
1.700
$ java Main < 3.in
0.500 1 arrives
0.500 1 serves by 1
0.600 2 arrives
0.600 2 serves by 2
0.700 3 arrives
0.700 3 waits at 1
1.500 1 done serving by 1
1.500 3 serves by 1
1.500 4 arrives
1.500 4 waits at 1
1.600 2 done serving by 2
1.600 5 arrives
1.600 5 serves by 2
1.700 6 arrives
1.700 6 waits at 2
2.500 3 done serving by 1
2.500 4 serves by 1
2.600 5 done serving by 2
2.600 6 serves by 2
3.500 4 done serving by 1
3.600 6 done serving by 2
[0.450 6 0]
$ cat 4.in
2 2
0.500
0.600
0.700
1.500
1.600
1.700
$ java Main < 4.in
0.500 1 arrives
0.500 1 serves by 1
0.600 2 arrives
0.600 2 serves by 2
0.700 3 arrives
0.700 3 waits at 1
1.500 1 done serving by 1
1.500 3 serves by 1
1.500 4 arrives
1.500 4 waits at 1
1.600 2 done serving by 2
1.600 5 arrives
1.600 5 serves by 2
1.700 6 arrives
1.700 6 waits at 1
2.500 3 done serving by 1
2.500 4 serves by 1
2.600 5 done serving by 2
3.500 4 done serving by 1
3.500 6 serves by 1
4.500 6 done serving by 1
[0.600 6 0]
Some design tips...
● Make use of polymorphism instead of checking the type of event in the simulator class:
○ Your event class should have a method that returns another type of event. If you need to return
more values, consider putting into a pair.
○ Each event will transit into the next event, e.g. a serve will transit to a done event after running the
method above.
○ Terminating events (done and leave) can return itself since there is no event to transit to.
● In your design, only invoke getServiceTime() in one location. Invoking in multiple locations may result in
wrong service time.
● Consider how you would emulate a queue for each server.
● Avoid having multiple events with the same customer in the PQ, i.e. the PQ should contain only one event
per customer.