Note
This post is a continuation of Discrete event simulation of a prioritized lunch queue in Java (Data structures). Please refer to it for problem description.
This part about "algorithms": all classes that are more about doing rather than representing information.
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.");
}
}
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"
};
}
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 void initWaitingTimeStructures() {
for (AcademicDegree degree : groupCounts.keySet()) {
mapMinimumWaitTime.put(degree, Integer.MAX_VALUE);
mapMaximumWaitTime.put(degree, Integer.MIN_VALUE);
mapWaitTimeSum.put(degree, 0);
}
}
private void precomputeWaitingTimes() {
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);
}
}
private void precomputeDeviationsPhase1() {
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);
}
}
private void precomputeDeviationsPhase2() {
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);
}
}
private void computeStandardDeviations() {
for (AcademicDegree degree : groupCounts.keySet()) {
int sum = mapWaitTimeDeviation.get(degree);
mapWaitTimeDeviation.put(degree,
(int) Math.round(
Math.sqrt(sum /
groupCounts
.get(degree))));
}
}
private void loadStatistics(SimulationResult result) {
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));
}
}
private void computeCashierStatistics(SimulationResult result) {
if (cashierIdleIntervals.isEmpty()) {
return;
}
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);
}
private SimulationResult postprocess() {
initWaitingTimeStructures();
precomputeWaitingTimes();
precomputeDeviationsPhase1();
precomputeDeviationsPhase2();
computeStandardDeviations();
SimulationResult result = new SimulationResult(arrivalEventMap,
servedEventMap);
loadStatistics(result);
computeCashierStatistics(result);
return result;
}
}
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);
}
}
Is my coding style/naming conventions/API design reasonable on this part? Any critique much appreciated!
