Discrete event simulation of a prioritized lunch queue in Java

Introduction

In this post, we will devise a discrete event simulation of a prioritized lunch queue using Java. We begin with the problem setting: We are considering a lunch queue in an university campus. There is four categories (listed in decreasing priority):

  1. doctors (PhD),
  2. masters (MSc),
  3. bachelors (BSc),
  4. undergraduates.

Now, whenever, say, a master arrives to the cafeteria, he skips all bachelors and undergraduates, and joins the tail of the subqueue of masters. As often, we want to find out the following statistics within each category:

  • the minimum waiting time,
  • the average waiting time,
  • the maximum waiting time,
  • the standard deviation of the waiting times.

The waiting times will include the actual service times. Also, we will consider idle time statistics of the cafeteria cashier.

Internals of a discrete event simulation program

In the simulation, we first create the population, which is a simple collection of persons and their arrival times to the cafeteria. We assume that the time points at which people go for a lunch exhibit a normal distribution. We sort the collection of persons by their arrival times. In case two or more persons arrive at precisely the same moment, we break the ties by their academic degree.

Since we are simulating a prioritized lunch queue, we need a simple priority queue data structure: it maintains a FIFO (first in, first out) queue for each privilege level (doctors, masters, and so on). Pushing a person to the queue will append her/him to the queue of its peers. Popping operation scans the queues from most privileged to least privileged, and pops the first non-empty queue.

The last important component of a simulation is the actual simulating procedure. In pseudocode it looks something like this:

let P be the empty prioritized queue
let Q be the queue of persons sorted by arrival times
current_clock = head(Q).arrival_time
persons_pending = Q.size

while persons_pending > 0:
    # Load the persons that arrived during the service 
    # of the previously served person
    while Q is not empty and head(Q).arrival_time <= current_clock:
        enqueue(P, dequeue(Q))

    if P is empty:
        # The cashier is being idle, jump forward in time
        head_event = dequeue(Q)
        current_clock = head_event.arrival_time
        enqueue(P, head_event)
    
    # Pop the most prioritized + earliest person
    current_event = pop(P)                
    service_time = get_service_time()
    current_clock += service_time
    persons_pending -= 1
    # Served!

At this point you might be asking why we need the internal queue (P in the above algorithm). Why we do not just sort the entire population first by privilege levels and each subportion by the arrival time. The answer should be obvious after considering an example: suppose the entire population consists of only two bachelors and a master; bachelors arrive earlier, and the master arrives while the second bachelor is being served. If we just had sorted the population, the master would “travel forward in time”. This issue requires us to simulate the actual lunch queue, i.e., the actual set of persons that are waiting in the queue, not entire population.

Now we are ready to start coding. It makes sense to start from the enumeration of academic degrees:

net.coderodde.simulation.lunch.AcademicDegree.java
package net.coderodde.simulation.lunch;

/**
 * This class implements an enumeration over academic degrees.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Dec 2, 2015) 
 */
public enum AcademicDegree {
   
    // The order denotes priority from highest to lowest.
    DOCTOR       ("PhD"),
    MASTER       ("MSc"),
    BACHELOR     ("BSc"),
    UNDERGRADUATE("Undergraduate");
    
    private final String description;
    
    @Override
    public String toString() {
        return description;
    }
    
    private AcademicDegree(String description) {
        this.description = description;
    }
}

In Java (since JDK 5), every enumeration is implicitly derived from the abstract class java.lang.Enum<E extends Enum<E>>. When you declare the constants in an enumeration, behind the scenes you create instances of that very enumeration type, so that there is only one enumeration instance for each constant. Also, the runtime associates with each constant an ordinal value: the very first declared (topmost) constant receives the value of zero, the second one receives one, and so on. Also, enumerations are java.lang.Comparable and comparing the constants relies on their respective ordinal values. Now, by declaring the constants in the way we did, we imply the order of the academic degrees, in which doctors preceed masters, masters preceed bachelors, and so on.

Next we need a class that represents a person:

net.coderodde.simulation.lunch.Person.java
package net.coderodde.simulation.lunch;

import java.util.Objects;

/**
 * This class implements a record for a person.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Dec 2, 2015)
 */
public final class Person implements Comparable<Person> {

    private final String firstName;
    private final String lastName;
    private final AcademicDegree academicDegree;
    private final String stringRepresentation;
    private final String identity;
    
    public static LastNameSelector withFirstName(String firstName) {
        Objects.requireNonNull(firstName, 
                               "The first name of a person is null.");
        Configuration configuration = new Configuration();
        configuration.firstName = firstName;
        return new LastNameSelector(configuration);
    }
    
    public static final class LastNameSelector {
        
        private final Configuration configuration;
        
        private LastNameSelector(Configuration configuration) {
            this.configuration = configuration;
        }
        
        public AcademicDegreeSelector withLastName(String lastName) {
            Objects.requireNonNull(lastName, 
                                   "The last name of a person is null.");
            configuration.lastName = lastName;
            return new AcademicDegreeSelector(configuration);
        }
    }
    
    public static final class AcademicDegreeSelector {
        
        private final Configuration configuration;
        
        AcademicDegreeSelector(Configuration configuration) {
            this.configuration = configuration;
        }
        
        public Person withAcademicDegree(AcademicDegree degree) {
            Objects.requireNonNull(degree, "The academic degree is null.");
            return new Person(configuration.firstName,
                              configuration.lastName,
                              degree);
        }
    }
    
    private Person(String firstName, 
                   String lastName, 
                   AcademicDegree academicDegree) {
        this.firstName      = firstName;
        this.lastName       = lastName;
        this.academicDegree = academicDegree;
        this.stringRepresentation = "[" + firstName + " " + lastName + ", " + 
                                          academicDegree + "]";
        this.identity = firstName + " " + lastName;
    }
    
    public String getFirstName() {
        return firstName;
    }
    
    public String getLastName() {
        return lastName;
    }
    
    public AcademicDegree getAcademicDegree() {
        return academicDegree;
    }
    
    @Override
    public String toString() {
        return stringRepresentation;
    }
    
    @Override
    public int compareTo(Person o) {
        return this.academicDegree.compareTo(o.getAcademicDegree());
    }
    
    @Override
    public int hashCode() {
        return identity.hashCode();
    }

    @Override
    public boolean equals(Object obj) {
        if (obj == null) {
            return false;
        }
        
        if (getClass() != obj.getClass()) {
            return false;
        }
        
        Person other = (Person) obj;
        return Objects.equals(identity, other.identity);
    }
    
    private static final class Configuration {
        private String firstName;
        private String lastName;
    }
}

The identity of each person consists of two attributes: the first name and the last name. Once again, we make the Person a Comparable so that the persons are ordered by their respective academic degrees. Also, we opt to use strong fluent API for constructing instances of Person:

Person person = Person.withFirstName("Jack")
                      .withLastName("Cooley")
                      .withAcademicDegree(AcademicDegree.BACHELOR);

In a weak fluent API, the order in which the user fills out the attributes (first name, last name, academic degree) is not fixed, which makes it possible that the user may forget to specify some attributes. In a strong fluent API, the order of filling the attributes is fixed, which ensures that the client programmer will not omit any required attribute. Regardless of whether we use a strong or weak fluent API, sticking to one makes code more self-explanatory.

Since we will put Persons in a couple of hash tables, we must implement Person.equals(Object) and Person.hashCode() in the way that takes the identity (first and last names) into account.

Next, we proceed to the class that represents a cashier. We do not attach any identity information to a Cashier. All a Cashier knows is its mean service time and the standard deviation of the service time:

net.coderodde.simulation.lunch.Cashier.java
package net.coderodde.simulation.lunch;

import java.util.Objects;
import java.util.Random;
import static net.coderodde.simulation.lunch.Utils.checkMean;
import static net.coderodde.simulation.lunch.Utils.checkStandardDeviation;

/**
 * This class models the action of a cashier.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Dec 4, 2015)
 */
public final class Cashier {
    
    private final double meanServiceTime;
    private final double standardDeviationOfServiceTime;
    private final Random random;
    
    /**
     * Initiates a strong fluent API for creating a {@code Cashier}.
     * 
     * @param  random the random number generator to use.
     * @return the mean service time selector.
     */
    public static MeanServiceTimeSelector withRandom(Random random) {
        Objects.requireNonNull(random, "The input Random is null.");
        Configuration configuration = new Configuration();
        configuration.random = random;
        return new MeanServiceTimeSelector(configuration);
    }
    
    /**
     * Initiates a strong fluent API for creating a {@code Cashier} using a 
     * default random number generator.
     * 
     * @return the mean service time selector. 
     */
    public static MeanServiceTimeSelector withDefaultRandom() {
        return withRandom(new Random());
    }
    
    public final static class MeanServiceTimeSelector {
        
        private final Configuration configuration;
        
        private MeanServiceTimeSelector(Configuration configuration) {
            this.configuration = configuration;
        }
        
        /**
         * Selects the mean service time and returns a standard deviation 
         * selector.
         * 
         * @param  meanServiceTime the mean service time in seconds.
         * @return a standard deviation selector.
         */
        public StandardDeviationSelector 
            withMeanServiceTime(double meanServiceTime) {
            checkMean(meanServiceTime);
            configuration.meanServiceTime = meanServiceTime;
            return new StandardDeviationSelector(configuration);
        }
    }
    
    public final static class StandardDeviationSelector {
        
        private final Configuration configuration;
        
        private StandardDeviationSelector(Configuration configuration) {
            this.configuration = configuration;
        }
        
        /**
         * Selects a standard deviation for the service time and returns the 
         * {@code Cashier} using the gathered parameters.
         * 
         * @param  standardDeviationOfServiceTime the standard deviation of the
         *                                        service time in seconds.
         * @return a {@code Cashier} object.
         */
        public Cashier withStandardDeviationOfServiceTime(
                double standardDeviationOfServiceTime) {
            checkStandardDeviation(standardDeviationOfServiceTime);
            return new Cashier(configuration.meanServiceTime,
                               standardDeviationOfServiceTime,
                               configuration.random);
        }
    }
    
    private Cashier(double meanServiceTime, 
                    double standardDeviationOfServiceTime,
                    Random random) {
        this.meanServiceTime = meanServiceTime;
        this.standardDeviationOfServiceTime = standardDeviationOfServiceTime;
        this.random = random;
    }
    
    public int getServiceTime() {
        return (int)(Math.round(meanServiceTime + 
                                    standardDeviationOfServiceTime * 
                                    random.nextGaussian()));
    }
    
    private static final class Configuration {
        private Random random;
        private double meanServiceTime;
    }
}

Once again, as Cashier is exposed to a potential client programmer, we opt to a strong fluent API for creating instances of Cashier:

Cashier cashier = Cashier.withRandom(random)
                         .withMeanServiceTime(15.0)
                         .withStandardDeviationOfServiceTime(2.0);

Next, we need a class for representing a population:

net.coderodde.simulation.lunch.Population.java
package net.coderodde.simulation.lunch;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import java.util.Queue;
import java.util.Set;
import static net.coderodde.simulation.lunch.Utils.checkTime;

/**
 * This class represents simulated population.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Dec 3, 2015)
 */
public final class Population {
    
    private final Map<Person, Integer> arrivalTimeMap = new HashMap<>();
    
    public final class ArrivalTimeSelector {
        private final Person person;

        ArrivalTimeSelector(Person person) {
            this.person = Objects.requireNonNull(person,
                                                 "The input person is null.");
        }
        
        public boolean withArrivalTime(int arrivalTime) {
            checkTime(arrivalTime);
            
            if (arrivalTimeMap.containsKey(person)) {
                return false;
            }
            
            arrivalTimeMap.put(person, arrivalTime);
            return true;
        }
    }
    
    public ArrivalTimeSelector addPerson(Person person) {
        return new ArrivalTimeSelector(person);
    }
    
    public int size() {
        return arrivalTimeMap.size();
    }
   
    Set<Person> getPersonSet() {
        return Collections.<Person>unmodifiableSet(arrivalTimeMap.keySet());
    }
    
    Queue<LunchQueueEvent> toEventQueue() {
        List<LunchQueueEvent> eventList = new ArrayList<>(size());
        
        getPersonSet().stream().forEach((person) -> {
            eventList.add(new LunchQueueEvent(person, 
                                              arrivalTimeMap.get(person)));
        });
        
        Collections.sort(eventList, 
                        (event1, event2) -> {
            // Try to compare by the time stamps of the events.
            int cmp = event1.compareTo(event2);
            
            if (cmp != 0) {
                return cmp;
            }
            
            // The two input events have same time stamp, break ties by person
            // priority.
            return event1.getPerson().compareTo(event2.getPerson());
        });
        
        return new ArrayDeque<>(eventList);
    }
}

Basically, all Population does is keep track of all the persons and their respective arrival times. Adding a person to the population:

Person person = Person.withFirstName("Jack")
                      .withLastName("Cooley")
                      .withAcademicDegree(AcademicDegree.BACHELOR);
        Population population = new Population();
        population.addPerson(person)
                  .withArrivalTime(100);

Since it would be really laborous to construct manually a large population, we need a class for generating random populations:

net.coderodde.simulation.lunch.RandomPopulationGenerator.java
package net.coderodde.simulation.lunch;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import java.util.Random;
import static net.coderodde.simulation.lunch.Utils.checkMean;
import static net.coderodde.simulation.lunch.Utils.checkStandardDeviation;

/**
 * This class facilitates random generation of population.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Dec 2, 2015)
 */
public final class RandomPopulationGenerator {
    
    private final Random random;
    private final Map<AcademicDegree, Integer> distribution;
    private final double meanLunchTime;
    private final double standardDeviationOfLunchTime;
    
    /**
     * Initiates the strong fluent API for constructing a 
     * {@code RandomPopulationGenerator}.
     * 
     * @param  random the random number generator to use.
     * @return a degree selector.
     */
    public static DegreeCountSelector withRandom(Random random) {
        Objects.requireNonNull(random, "The input Random is null.");
        Configuration configuration = new Configuration();
        configuration.random = random;
        return new DegreeCountSelector(configuration);
    }
    
    /**
     * Initiates the strong fluent API for constructing a 
     * {@code RandomPopulationGenerator} using a default {@code Random}.
     * 
     * @return a degree selector.
     */
    public static DegreeCountSelector withDefaultRandom() {
        return withRandom(new Random());
    }
    
    public static final class DegreeCountSelector {
        
        private final Configuration configuration;
        
        DegreeCountSelector(Configuration configuration) {
            this.configuration = configuration;
        }
        
        /**
         * Starts constructing a population  wit selected academic degree.
         * 
         * @param  count the number of persons for a degree group.
         * @return a degree selector for the group being constructed.
         */
        public DegreeSelector with(int count) {
            if (count < 0) {
                throw new IllegalArgumentException(
                        "The people count is negative: " + count);
            }
            
            return new DegreeSelector(configuration, count);
        }
        
        /**
         * Terminates creation of groups and selects a mean time at which people
         * go for a lunch. (Lunch time does not mean the duration of a lunch.)
         * 
         * @param  meanLunchTime the mean of lunch times 
         * @return a standard deviation selector.
         */
        public StandardDeviationSelector 
            withMeanLunchTime(double meanLunchTime) {
            checkMean(meanLunchTime);
            configuration.meanLunchTime = meanLunchTime;
            return new StandardDeviationSelector(configuration);
        }
    }
    
    public static final class DegreeSelector {
        
        private final Configuration configuration;
        private final int count;
        
        DegreeSelector(Configuration configuration, int count) {
            this.configuration = configuration;
            this.count = count;
        }
        
        public DegreeCountSelector peopleWithDegree(AcademicDegree degree) {
            Objects.requireNonNull(degree, "The input degree is null.");
            configuration.distribution.put(degree, count);
            return new DegreeCountSelector(configuration);
        }
    }
    
    public static final class StandardDeviationSelector {
        
        private final Configuration configuration;
        
        StandardDeviationSelector(Configuration configuration) {
            this.configuration = configuration;
        }
        
        /**
         * Selects the standard deviation and generates a population with
         * specified parameters.
         * 
         * @param  lunchTimeStandardDeviation the standard deviation of the 
         *                                    times at which people go to lunch.
         * @return a population.
         */
        public Population withLunchTimeStandardDeviation(
                double lunchTimeStandardDeviation) {
            checkStandardDeviation(lunchTimeStandardDeviation);
            return new RandomPopulationGenerator(
                    configuration.random,
                    configuration.distribution,
                    configuration.meanLunchTime,
                    lunchTimeStandardDeviation).generate();
        }
    }
    
    private RandomPopulationGenerator(Random random, 
                                      Map<AcademicDegree, Integer> distribution,
                                      double meanLunchTime,
                                      double standardDeviationOfLunchTime) {
        this.random       = random;
        this.distribution = distribution;
        this.meanLunchTime = meanLunchTime;
        this.standardDeviationOfLunchTime = standardDeviationOfLunchTime;
    }
    
    public Population generate() {
        int populationSize = 0;
        
        for (Map.Entry<AcademicDegree, Integer> entry : distribution.entrySet()) {
            populationSize += entry.getValue();
        }
        
        List<Person> allPersonList = 
                new ArrayList<>(FIRST_NAMES.length * LAST_NAMES.length);
        
        List<AcademicDegree> degreeList = new ArrayList<>(populationSize);
        
        for (AcademicDegree degree : AcademicDegree.values()) {
            int count = distribution.getOrDefault(degree, 0);
            
            for (int i = 0; i < count; ++i) {
                degreeList.add(degree);
            }
        }
        
        
        Collections.<AcademicDegree>shuffle(degreeList, random);
        int i = 0;
        
        outer:
        for (String firstName : FIRST_NAMES) {
            for (String lastName : LAST_NAMES) {
                if (i == degreeList.size()) {
                    break outer;
                }
                
                allPersonList.add(Person.withFirstName(firstName)
                                        .withLastName(lastName)
                                        .withAcademicDegree(degreeList.get(i)));
                ++i;
            }
        }
        
        Collections.shuffle(allPersonList, random);
        populationSize = Math.min(populationSize, allPersonList.size());
        
        Population population = new Population();
        
        for (i = 0; i < populationSize; ++i) {
            population.addPerson(allPersonList.get(i))
                      .withArrivalTime(getRandomLunchTime());
        }
        
        return population;
    }
    
    private int getRandomLunchTime() {
        return (int)(meanLunchTime + standardDeviationOfLunchTime * 
                                     random.nextGaussian());
    }
    
    private static final class Configuration {
        private final Map<AcademicDegree, Integer> distribution = 
                new HashMap<>();
        
        private Random random;
        private double meanLunchTime;
    }
    
    private static final String[] FIRST_NAMES = {
        "Ada",
        "Alice",
        "Al",
        "Alma",
        "Alvin",
        "Amanda",
        "Bob",
        "Brandon",
        "Brooke",
        "Bruce",
        "Camilla",
        "Cecilia",
        "Carl",
        "David",
        "Elsa",
        "Ida",
        "Jack",
        "John",
        "Nathan",
        "Nick",
        "Phoebe",
        "Rachel",
        "Richard",
        "Rodion",
        "Roger",
        "Roland",
        "Rolf",
        "Roy",
        "Terence",
        "Terry",
        "Viola"
    };
    
    private static final String[] LAST_NAMES = {
        "Abbey",
        "Ackerman",
        "Bonham",
        "Bradly",
        "Cantrell",
        "Carter",
        "Dawkins",
        "Dawson",
        "Edison",
        "Efremov",
        "Fay",
        "Fleming",
        "Garrett",
        "Hallman",
        "Irvine",
        "Jacobson",
        "Kidd",
        "Lacey",
        "Marlow",
        "Nelson",
        "Oliver",
        "Parks",
        "Pearson",
        "Peterson",
        "Quincey",
        "Ridley",
        "Saunders",
        "Thompson",
        "Walton",
        "Wilkerson"
    };
}

A sample call to the generator looks like this:

Population population = 
                RandomPopulationGenerator 
                .withRandom(random)
                .with(15).peopleWithDegree(AcademicDegree.DOCTOR)
                .with(40).peopleWithDegree(AcademicDegree.MASTER)
                .with(100).peopleWithDegree(AcademicDegree.BACHELOR)
                .with(250).peopleWithDegree(AcademicDegree.UNDERGRADUATE)
                .withMeanLunchTime(10800.0)
                .withLunchTimeStandardDeviation(1200.0);

Next, we need a class for representing events:

net.coderodde.simulation.lunch.LunchQueueEvent.java
package net.coderodde.simulation.lunch;

/**
 * This class describes a lunch queue event.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Dec 2, 2015).
 */
final class LunchQueueEvent implements Comparable<LunchQueueEvent> {
    
    private final Person person;
    private final int timeStamp;
    
    LunchQueueEvent(Person person, int timeStamp) {
        this.person = person;
        this.timeStamp = timeStamp;
    }
    
    Person getPerson() {
        return person;
    }
    
    int getTimestamp() {
        return timeStamp;
    }
    
    @Override
    public int compareTo(LunchQueueEvent anotherEvent) {
        return Double.compare(timeStamp, anotherEvent.timeStamp);
    }
}

Note that the lunch queue event comprises only a person and an arrival time. You might ask: Aren’t we supposed to have a third attribute that indicates which one of the two possible events (arrival, being served) is in question? No, we will maintain two distinct data structures holding the events: one for arrival events and the other one for service events. Also, since LunchQueueEvent is not supposed to be exposed to the client programmer, its access modifier is package private.

Now, the actual prioritized queue:

net.coderodde.simulation.lunch.PrioritizedQueue.java
package net.coderodde.simulation.lunch;

import java.util.ArrayDeque;
import java.util.EnumMap;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.Queue;

/**
 * This class implements a FIFO queue over priority categories. Not to be 
 * confused with a priority queue.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Dec 3, 2015)
 */
final class PrioritizedQueue {
   
    private final Map<AcademicDegree, Queue<LunchQueueEvent>> map 
            = new EnumMap<>(AcademicDegree.class);
    
    private int size;
    
    void push(LunchQueueEvent event) {
        AcademicDegree degree = event.getPerson().getAcademicDegree();
        map.putIfAbsent(degree, new ArrayDeque<>());
        map.get(degree).add(event);
        ++size;
    }
    
    boolean isEmpty() {
        return size == 0;
    }
    
    LunchQueueEvent pop() {
        if (isEmpty()) {
            throw new NoSuchElementException(
                    "Popping from an empty prioritized queue.");
        }
        
        for (Queue<LunchQueueEvent> queue : map.values()) {
            if (!queue.isEmpty()) {
                --size;
                return queue.remove();
            }
        }
        
        throw new IllegalStateException(
                "This should never happend. Please debug.");
    }
}

The implementation is trivial, yet if we were to add new privilige levels to the simulation, the above implementation would not had to be modified; only recompilation would suffice. At this point we are ready to proceed to the actual simulator class:

net.coderodde.simulation.lunch.Simulator.java
package net.coderodde.simulation.lunch;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import java.util.Queue;

/**
 * This class runs the lunch queue simulation.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Dec 2, 2015)
 */
public final class Simulator {

    //// Internals.
    private final Map<Person, LunchQueueEvent> arrivalEventMap = 
            new HashMap<>();
    private final Map<Person, LunchQueueEvent> servedEventMap = 
            new HashMap<>();
    private final Map<AcademicDegree, Integer> groupCounts = new HashMap<>();
    
    private final Map<AcademicDegree, Integer> mapMinimumWaitTime = 
            new HashMap<>();
    private final Map<AcademicDegree, Integer> mapMaximumWaitTime = 
            new HashMap<>();
    private final Map<AcademicDegree, Integer> mapAverageWaitTime = 
            new HashMap<>();
    private final Map<AcademicDegree, Integer> mapWaitTimeSum     = 
            new HashMap<>();
    private final Map<AcademicDegree, Integer> mapWaitTimeDeviation = 
            new HashMap<>();
    
    private final List<Integer> cashierIdleIntervals = new ArrayList<>();
    private Population population;
    
    public static PopulationSelector simulate() {
        
        return new PopulationSelector();
    }
    
    public static final class PopulationSelector {
        
        public CashierSelector withPopulation(Population population) {
            Objects.requireNonNull(population, "The input population is null.");
            return new CashierSelector(population);
        }
    }
    
    public static final class CashierSelector {
        
        private final Population population;
        
        CashierSelector(Population population) {
            this.population = population;
        }
        
        public SimulationResult withCashier(Cashier cashier) {
            Objects.requireNonNull(cashier, "The input cashier is null.");
            return new Simulator().simulate(population, cashier);
        }
    }
    
    private SimulationResult simulate(Population population, Cashier cashier) {
        this.population = population;
        Queue<LunchQueueEvent> inputEventQueue = population.toEventQueue();
        preprocess(inputEventQueue);
        
        if (population.size() == 0) {
            return new SimulationResult(arrivalEventMap, servedEventMap);
        }
        
        PrioritizedQueue QUEUE = new PrioritizedQueue();
        int currentClock = inputEventQueue.peek().getTimestamp();
        
        for (int personsPending = population.size();
                personsPending > 0;
                personsPending--) {
            // Load all hungry people that arrived during the service of the 
            // previously served person.
            while (!inputEventQueue.isEmpty()
                    && inputEventQueue.peek().getTimestamp() 
                    <= currentClock) {
                QUEUE.push(inputEventQueue.remove());
            }
            
            if (QUEUE.isEmpty()) {
                LunchQueueEvent headEvent = inputEventQueue.remove();
                cashierIdleIntervals.add(headEvent.getTimestamp() - 
                                         currentClock);
                currentClock = headEvent.getTimestamp();
                QUEUE.push(headEvent);
            } else {
                cashierIdleIntervals.add(0);
            }
            
            // Admit an earliest + highest priority person to the cashier.
            LunchQueueEvent currentEvent = QUEUE.pop();
            Person currentPerson = currentEvent.getPerson();
            
            // Serving...
            int serviceTime = cashier.getServiceTime();
            currentClock += serviceTime;
            LunchQueueEvent servedEvent = new LunchQueueEvent(currentPerson, 
                                                              currentClock);
            servedEventMap.put(currentPerson, servedEvent);
            // Served!
        }
        
        return postprocess();
    }
    
    private void preprocess(Queue<LunchQueueEvent> inputEventQueue) {
        // groupCounts.keySet() will now list only those academic degrees that
        // are present in the population.
        for (LunchQueueEvent event : inputEventQueue) {
            Person person = event.getPerson();
            arrivalEventMap.put(person, event);
            AcademicDegree degree = person.getAcademicDegree();
            groupCounts.put(degree, groupCounts.getOrDefault(degree, 0) + 1);
        }
    }
    
    private SimulationResult postprocess() {
        // Start computing system statistics.
        
        for (AcademicDegree degree : groupCounts.keySet()) {
            mapMinimumWaitTime.put(degree, Integer.MAX_VALUE);
            mapMaximumWaitTime.put(degree, Integer.MIN_VALUE);
            mapWaitTimeSum.put(degree, 0);
        }
        
        // Computing minimum/maximum wait time for each academic degree.
        for (Person person : population.getPersonSet()) {
            LunchQueueEvent arrivalEvent = arrivalEventMap.get(person);
            LunchQueueEvent servedEvent  = servedEventMap.get(person);
            
            int waitTime = servedEvent.getTimestamp() - 
                           arrivalEvent.getTimestamp();
            
            AcademicDegree degree = person.getAcademicDegree();
            
            if (mapMinimumWaitTime.get(degree) > waitTime) {
                mapMinimumWaitTime.put(degree, waitTime);
            }
            
            if (mapMaximumWaitTime.get(degree) < waitTime) {
                mapMaximumWaitTime.put(degree, waitTime);
            }
            
            mapWaitTimeSum.put(degree, mapWaitTimeSum.get(degree) + waitTime);
        }
        
        // Computing the average waiting time for each academic degree.
        for (AcademicDegree degree : groupCounts.keySet()) {
            int average = (int) Math.round(1.0 * mapWaitTimeSum.get(degree) / 
                                           groupCounts.get(degree));
            
            mapAverageWaitTime.put(degree, average);
            mapWaitTimeDeviation.put(degree, 0);
        }
        
        for (Person person : population.getPersonSet()) {
            AcademicDegree degree = person.getAcademicDegree();
            
            int duration = servedEventMap.get(person).getTimestamp() -
                          arrivalEventMap.get(person).getTimestamp();
            
            int contribution = duration - mapAverageWaitTime.get(degree);
            
            contribution *= contribution;
            mapWaitTimeDeviation.put(degree, 
                                     mapWaitTimeDeviation.get(degree) +
                                             contribution);
        }
        
        for (AcademicDegree degree : groupCounts.keySet()) {
            int sum = mapWaitTimeDeviation.get(degree);
            mapWaitTimeDeviation.put(degree, 
                                     (int) Math.round(
                                             Math.sqrt(sum / 
                                                       groupCounts
                                                               .get(degree))));
        }
        
        SimulationResult result = new SimulationResult(arrivalEventMap, 
                                                       servedEventMap);
        
        for (AcademicDegree degree : groupCounts.keySet()) {
            result.putWaitMinimumTime(degree, mapMinimumWaitTime.get(degree));
            result.putWaitMaximumTime(degree, mapMaximumWaitTime.get(degree));
            result.putAverageWaitTime(degree, mapAverageWaitTime.get(degree));
            result.putWaitTimeStandardDeviation(degree,
                                                mapWaitTimeDeviation
                                                        .get(degree));
        }
        
        // Process cashier idle time statistics:
        if (cashierIdleIntervals.isEmpty()) {
            return result;
        }
        
        int sum = 0;
        int min = cashierIdleIntervals.get(0);
        int max = cashierIdleIntervals.get(0);
        
        for (int value : cashierIdleIntervals) {
            sum += value;
            
            if (min > value) {
                min = value;
            } else if (max < value) {
                max = value;
            }
        }
        
        double average = 1.0 * sum / cashierIdleIntervals.size();
        
        sum = 0;
        
        // Compute standard deviation:
        for (int value : cashierIdleIntervals) {
            double diff = average - value;
            diff *= diff;
            sum += diff;
        }
        
        int standardDeviation = 
                (int)(Math.round(
                        Math.sqrt(1.0 *sum / cashierIdleIntervals.size())));
        
        result.putCashierMinimumIdleTime(min);
        result.putCashierAverageIdleTime((int)(Math.round(average)));
        result.putCashierMaximumIdleTime(max);
        result.putCashierStandardDeviation(standardDeviation);
        
        return result;
    }
}

Of course, we need a class for holding the simulation statistics:

net.coderodde.simulation.lunch.SimulationResult.java
package net.coderodde.simulation.lunch;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * This class holds the statistics of a simulation.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Dec 2, 2015)
 */
public final class SimulationResult {

    private static final String NL = "\n";
    private static final String SKIP = "    ";
    private static final int NO_DATA = -1;
    
    private final Map<AcademicDegree, Integer> waitAverageMap = new HashMap<>();
    private final Map<AcademicDegree, Integer> waitStandardDeviationMap = 
            new HashMap<>();
    
    private final Map<AcademicDegree, Integer> waitMinMap = new HashMap<>();
    private final Map<AcademicDegree, Integer> waitMaxMap = new HashMap<>();
    
    private final Map<Person, LunchQueueEvent> arrivalEventMap;
    private final Map<Person, LunchQueueEvent> servedEventMap;
    
    private int cashierMinimumIdleTime = NO_DATA;
    private int cashierAverageIdleTime = NO_DATA;
    private int cashierMaximumIdleTime = NO_DATA;
    private int cashierStandardDeviation = NO_DATA;
    
    public int getMinimumWaitTime(AcademicDegree degree) {
        return waitMinMap.getOrDefault(degree, NO_DATA);
    }
    
    public int getWaitAverage(AcademicDegree degree) {
        return waitAverageMap.getOrDefault(degree, NO_DATA);
    }
    
    public int getMaximumWaitTime(AcademicDegree degree) {
        return waitMaxMap.getOrDefault(degree, NO_DATA);
    }
    
    public int getWaitStandardDeviation(AcademicDegree degree) {
        return waitStandardDeviationMap.getOrDefault(degree, NO_DATA);
    }
    
    public int getCashierMinimumIdleTime() {
        return cashierMinimumIdleTime;
    }
    
    public int getCashierAverageIdleTime() {
        return cashierAverageIdleTime;
    }
    
    public int getCashierMaximumIdleTime() {
        return cashierMaximumIdleTime;
    }
    
    public int getCashierStandardDeviation() {
        return cashierStandardDeviation;
    }
    
    SimulationResult(Map<Person, LunchQueueEvent> arrivalEventMap,
                     Map<Person, LunchQueueEvent> servedEventMap) {
        this.arrivalEventMap = arrivalEventMap;
        this.servedEventMap = servedEventMap;
    }
    
    void putWaitMinimumTime(AcademicDegree degree, int minimumWaitTime) {
        waitMinMap.put(degree, minimumWaitTime);
    }
    
    void putAverageWaitTime(AcademicDegree degree, int averageTime) {
        waitAverageMap.put(degree, averageTime);
    }
    
    void putWaitMaximumTime(AcademicDegree degree, int maximumWaitTime) {
        waitMaxMap.put(degree, maximumWaitTime);
    }
    
    void putWaitTimeStandardDeviation(AcademicDegree degree, 
                                      int timeStandardDeviation) {
        waitStandardDeviationMap.put(degree, timeStandardDeviation);
    }
    
    void putCashierMinimumIdleTime(int cashierMinimumIdleTime) {
        this.cashierMinimumIdleTime = cashierMinimumIdleTime;
    }
    
    void putCashierAverageIdleTime(int cashierAverageIdleTime) {
        this.cashierAverageIdleTime = cashierAverageIdleTime;
    }
    
    void putCashierMaximumIdleTime(int cashierMaximumIdleTime) {
        this.cashierMaximumIdleTime = cashierMaximumIdleTime;
    }
    
    void putCashierStandardDeviation(int cashierStandardDeviation) {
        this.cashierStandardDeviation = cashierStandardDeviation;
    }
    
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        List<Person> personList = new ArrayList<>(arrivalEventMap.keySet());
        
        Collections.<Person>sort(personList, 
                                (p1, p2) -> {
            double arrivalTime1 = arrivalEventMap.get(p1).getTimestamp();
            double servedTime1 = servedEventMap.get(p1).getTimestamp();

            double arrivalTime2 = arrivalEventMap.get(p2).getTimestamp();
            double servedTime2 = servedEventMap.get(p2).getTimestamp();
            
            return Double.compare(servedTime1 - arrivalTime1, 
                                  servedTime2 - arrivalTime2);
        });
        
        for (Person person : personList) {
            sb.append(person.toString())
              .append(", wait time: ")
              .append((int)(servedEventMap.get(person).getTimestamp() -
                            arrivalEventMap.get(person).getTimestamp()))
              .append(" seconds.")
              .append(NL);
        }
        
        toString(sb, AcademicDegree.DOCTOR);
        toString(sb, AcademicDegree.MASTER);
        toString(sb, AcademicDegree.BACHELOR);
        toString(sb, AcademicDegree.UNDERGRADUATE);
        
        sb.append("Cashier:")
          .append(NL)
          .append(SKIP)
          .append("Minimum idle time:  ")
          .append(getCashierMinimumIdleTime())
          .append(" seconds.")
          .append(NL)
          .append(SKIP)
          .append("Average idle time:  ")
          .append(getCashierAverageIdleTime())
          .append(" seconds.")
          .append(NL)
          .append(SKIP)
          .append("Maximum idle time:  ")
          .append(getCashierMaximumIdleTime())
          .append(" seconds.")
          .append(NL)
          .append(SKIP)
          .append("Standard deviation: ")
          .append(getCashierStandardDeviation())
          .append(" seconds.");
        
        return sb.toString();
    }
    
    private void toString(StringBuilder sb, AcademicDegree degree) {
        sb.append(degree.toString()).append(":").append(NL);
        
        sb.append(SKIP)
          .append("Minimum wait time:  ")
          .append(getMinimumWaitTime(degree))
          .append(" seconds.")
          .append(NL);
        
        sb.append(SKIP)
          .append("Average wait time:  ")
          .append(getWaitAverage(degree))
          .append(" seconds.")
          .append(NL);
        
        sb.append(SKIP)
          .append("Maximum wait time:  ")
          .append(getMaximumWaitTime(degree))
          .append(" seconds.")
          .append(NL);
        
        sb.append(SKIP)
          .append("Standard deviation: ")
          .append(getWaitStandardDeviation(degree))
          .append(" seconds.")
          .append(NL);
    }
}

Validating your input is a good practice. The next class provides for some miscellaneous validation routines:

net.coderodde.simulation.lunch.Utils.java
package net.coderodde.simulation.lunch;

/**
 * This class contains miscellaneous utilities.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Dec 2, 2015)
 */
final class Utils {
   
    public static void checkMean(double mean) {
        if (Double.isNaN(mean)) {
            throw new IllegalArgumentException(
                    "The mean is NaN (not-a-number):");
        }
        
        if (Double.isInfinite(mean)) {
            throw new IllegalArgumentException("The mean is infinite: " + mean);
        }
    }
    
    public static void checkStandardDeviation(double deviation) {
        if (Double.isNaN(deviation)) {
            throw new IllegalArgumentException(
                    "The standard deviation is NaN (not-a-number):");
        }
        
        if (Double.isInfinite(deviation)) {
            throw new IllegalArgumentException(
                    "The standard deviation is infinite: " + deviation);
        }
        
        if (deviation < 0.0) {
            throw new IllegalArgumentException(
                    "The standard deviation is negative: " + deviation);
        }
    }
    
    public static void checkTime(double time) {
        if (Double.isNaN(time)) {
            throw new IllegalArgumentException(
                    "The input time is NaN (not-a-number).");
        }
        
        if (Double.isInfinite(time)) {
            throw new IllegalArgumentException(
                    "The input time is infinite: " + time);
        }
    }
}

Finally, the only missing block is the actual demonstration program:

Demo.java
import java.util.Random;
import net.coderodde.simulation.lunch.AcademicDegree;
import net.coderodde.simulation.lunch.Cashier;
import net.coderodde.simulation.lunch.Population;
import net.coderodde.simulation.lunch.RandomPopulationGenerator;
import net.coderodde.simulation.lunch.SimulationResult;
import net.coderodde.simulation.lunch.Simulator;

public class Demo {
    
    public static void main(final String... args) {
        long seed = System.nanoTime();
        Random random = new Random(seed);
        
        Population population = 
                RandomPopulationGenerator 
                .withRandom(random)
                .with(15).peopleWithDegree(AcademicDegree.DOCTOR)
                .with(40).peopleWithDegree(AcademicDegree.MASTER)
                .with(100).peopleWithDegree(AcademicDegree.BACHELOR)
                .with(250).peopleWithDegree(AcademicDegree.UNDERGRADUATE)
                .withMeanLunchTime(10800.0)
                .withLunchTimeStandardDeviation(1200.0);
                        
        // Cashier serves in average in 15 seconds, s.d. 2 seconds.
        Cashier cashier = Cashier.withRandom(random)
                                 .withMeanServiceTime(15.0)
                                 .withStandardDeviationOfServiceTime(2.0);
        
        System.out.println("Seed = " + seed);
        
        long startTime = System.nanoTime();
        SimulationResult result = Simulator.simulate()
                                           .withPopulation(population)
                                           .withCashier(cashier);
        long endTime = System.nanoTime();
        
        System.out.printf("Simulated in %.2f milliseconds.\n", 
                          (endTime - startTime) / 1e6);
        
        System.out.println(result);
    }
}

After running the above demonstration, you may get something like

Seed = 389000045239110
Simulated in 334.89 milliseconds.
[Bob Carter, Undergraduate], wait time: 11 seconds.
[Brandon Peterson, BSc], wait time: 11 seconds.
[Alice Efremov, Undergraduate], wait time: 12 seconds.
.
.
.
[Alma Marlow, Undergraduate], wait time: 2250 seconds.
[Brandon Fay, Undergraduate], wait time: 2251 seconds.
[Carl Walton, Undergraduate], wait time: 2253 seconds.
PhD:
    Minimum wait time:  12 seconds.
    Average wait time:  20 seconds.
    Maximum wait time:  31 seconds.
    Standard deviation: 5 seconds.
MSc:
    Minimum wait time:  15 seconds.
    Average wait time:  26 seconds.
    Maximum wait time:  50 seconds.
    Standard deviation: 8 seconds.
BSc:
    Minimum wait time:  11 seconds.
    Average wait time:  40 seconds.
    Maximum wait time:  133 seconds.
    Standard deviation: 26 seconds.
Undergraduate:
    Minimum wait time:  11 seconds.
    Average wait time:  1408 seconds.
    Maximum wait time:  2253 seconds.
    Standard deviation: 813 seconds.
Cashier:
    Minimum idle time:  0 seconds.
    Average idle time:  4 seconds.
    Maximum idle time:  644 seconds.
    Standard deviation: 37 seconds.

Now, we are ready for simulation. Please feel free to give me some feedback or ask a question!

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s