Priority Queues

A priority queue is a dynamic data structure that always returns the entry in the queue with the highest priority. The lab this week is to create a priority queue based on a LinkedList data structure.

Documentation for Java 1.6 is located at: Java 1.6 SE API

---

Tasks

1. Create a new generic class MyPriorityQueue<T> that implements Iterable<T>. You can call it whatever you like, but PriorityQueue is a standard class in Java, so don't use that. As before, create a Node class that can hold something of the generic type T and a next pointer.
2. Either copy from your singly-linked LinkedList or just create a new implementation of the following methods using a singly-linked list structure. Note that, in addition to a head pointer and a counter, you will need a variable to hold the maximum size of the queue and a variable to hold a Comparator object.
   • public MyPriorityQueue( int maxSize, Comparator<T> comp ) - constructor that takes in the max size of the queue and a Comparator object that can be used to compare two elements of the queue.
   • boolean add( T item ) - adds the item to the queue, if possible. You can either shove it on the front or keep the list ordered. (Keeping the list ordered saves work in other functions such as getNext, remove, and toString.) This should also return a boolean indicating whether or not item was added. (You can't add the item if you've already hit the maxSize.)
   • void clear() - clears the queue.
   • T getNext() - returns a reference to the highest priority element in the queue.
   • int getSize() - returns the current size of the queue.
   • boolean isEmpty() - returns true if the queue is empty.
   • boolean isFull() - returns true if the queue is full.
   • T remove() - removes the item with highest priority given the Comparator.
   • String toString() - generate some text representation of the queue.
   • ArrayList toArrayList() - return an ArrayList of the elements in the queue.
   • void setComparator(Comparator comparator) - takes in a Comparator object that can compare to elements of type T and uses it for all future priority comparisons. Note that this function may need to re-order the existing elements in the queue.

3. Implement an iterator for the priority queue so it can implement the Iterable interface. The iterator does not need to traverse the elements in priority order (although it should).

When you are finished, you can run this test-bench file to see if your Priority Queue is working.

The project for this week is to build a Passenger agent, build a Passenger Group data structure (based on the Priority Queue in lab), get the basic elevator simulation running, and then plan out a strategy for managing a set of elevators in a building with N floors and M elevators.

The Documentation for the various simulation classes

Problem Description

This week you'll be provided with most of a simulation of an elevator system. Your task is to create the Passenger class (Cell child) and a PassengerGroup class (a priority queue). Once completed, you should be able to run the elevator simulation. Finally, examine the current Elevator agent code and come to lab next week with a strategy you want to implement for managing the elevators.

---

Tasks

1. Create a Passenger agent class that extends Cell. It will need five fields.
   • private boolean active - whether the Passenger is active in the simulation.
   • private boolean onboard - whether the Passenger is on an Elevator.
   • private final int startFloor - the starting floor of the passenger.
   • private final int targetFloor - the target floor of the passenger.
   • private int waitTime - the time the Passenger has been waiting.
   • private ElevatorBank elevatorBank - the ElevatorBank this Passenger is in. (You may use this later when you make improvements.)

   In addition to overriding the abstract methods, Passenger should have the following methods.

   • public Passenger(int start, int target) - constructor.
   • public int getStartFloor() - accessor for startFloor.
   • public int getTargetFloor() - accessor for targetFloor.
   • public int getWaitTime() - accessor for waitTime.
   • public boolean isActive() - accessor for active.
   • public void setActive(boolean active) - modifier for active.
   • public boolean isOnboard() - accessor for onboard.
   • public void setOnboard(boolean onboard) - modifier for onboard.
   • public String toString() - generates a useful string.
   • public boolean isNeighbor() - returns false.
   • public void setBank(ElevatorBank bank) - sets the elevatorBank field.
   • public void updateState() - increments waitTime.
   • public void draw( Graphics g, int x0, int y0, int scale ) - draws a circle of size scale.
2. Create two inner classes in Passenger that implement the Comparator<Passenger> interface. The classes should be called MaxFloor and MinFloor. Declare them as public static classes.

   The Comparator interface requires implementing one function.

   • int compare( Passenger A, Passenger B ) - returns -1 if A is less than B, 0 if A is equal to B, and 1 if A is greater than B.

   For the MaxFloor class, the compare function should return a positive value if the target floor of A is larger than the target floor of B. For the MinFloor class, the compare function should return a positive value if the target floor of A is smaller than the target floor of B.

3. Create a class PassengerGroup that extends MyPriorityQueue<Passenger> and implements Iterable<Passenger>. The class should also have the following methods.
   • public PassengerGroup(int capacity) - constructor, use MaxFloor as the default comparator.
   • public void useMaxFloors() - set the comparator to Passenger.MaxFloor().
   • public void useMinFloors() - set the comparator to Passenger.MinFloor().
   • public String toString() - generates a useful representation of a Passenger group.

   Write a useful test main function for the PassengerGroup class.

4. Download the Elevator code bundle. Add your MyPriorityQueue, PassengerGroup, and Passenger classes to the directory and then compile everything. You will also need to add your LinkedList implementation as the class MyLinkedList.

   Run ElevatorSimulation and test the simulation.

5. Read through the Elevator.java file so you have some understanding of how the Agent is managing its path. Design a strategy for managing an Elevator agent and bring it to lab next week.

---

This is a 2-week lab. During the second lab you need to show the professor your test functions for the MyPriorityQueue and PassengerGroup classes. You also need to be prepared to discuss your elevator strategy. During the second week of the lab (below) you will implement your strategy.

---

Managing Elevators: Second Half of the Awesomeness

The documentation for the various simulation classes

Problem Description

The task this week is to implement one or more new strategies for the elevator set, attempting to reduce the overall average wait time.

So what needs fixing? If you run the simulation with all the default parameters, you may notice a few things.

Another problem is that empty elevators pick up passengers as soon as they can. For example, if there are two passengers waiting to go down on two different floors and an empty elevator below both these passengers, the elevator will rise to pick up the lower passenger and take it to its target floor. A better solution might be to send idle elevators to pick up passengers that are waiting further away, and then pick up the other passengers on the return trip.

Elevators with passengers on board do not stop to pick up waiting passengers as they move past. A better solution may be to pick up passengers while the elevator is moving past them. However, opening the doors too much may also increase the overall average simulation time.

Currently, the elevator strategies are completely static; the simulation will operate in the same way every time it is run on the same data. Introducing some amount of randomness may actually improve the overall performance of the control code!

This is by no means an exhaustive list, and you might find many other issues by watching the simulation or looking through the code.

---

Tasks

1. Set up the elevator simulation to use 8 elevators, 25 floors, and up to 8 passengers per elevator.
2. You will need to implement at least one different control algorithm and describe it in your write up, even if it does not improve passenger wait times.

   So, how do you start modifying the control code? First, think about the problem you want to address. What sort of information do you need to collect to address the issue?

   For example, some of the problems mentioned above stem from the fact that each elevator operates independently and makes a new movement decision at each iteration based on the current state of the simulation. If you wanted to add a more centralized control and a memory to the elevators, you might want to add some data or functionality to the ElevatorBank class. Maybe make ElevatorBank extend Cell and add it to the landscape. Include in the ElevatorBank.updateState() method a computation that determines where each Elevator in the bank should try to move to. The Elevator.updateState() method would then just move the elevator in that direction, if possible.

   Or, you could adopt a completely different strategy. Have the elevators each take trips up and down the entire set of floors, picking up passengers as they go.

   Note that some control strategies could use data structures and algorithms discussed in this course. You are welcome to use any of the Java collections classes (java.util) or build your own. Make note of what you do in your write up—using data structures and algorithms well will count as extensions.

3. Download the High Volume data set to your working directory. Run the ElevatorSimulation using the following command.

   $ java ElevatorSimulation -i eldata-high.txt

   Running the simulation with a dataset file means the same passengers appear each time you run it. That lets you make direct comparisons between strategies. Try to minimize the average time on this data.

   Running this file on the standard simulation should produce an average wait time of just over 71 time steps.

---

Extensions

• Change the way the elevators and/or passengers display in a creative way (more than just changing colors).
• Modify the keyboard controls (the Control class) in some useful way, or do something else with the display using Swing controls or Java events.
• Make good use of data structures or algorithms in the elevator control code.
• Come up with multiple elevator control algorithms and compare them.
• Model some aspect of real world elevators (e.g. express elevators or maximum load limits). These could either help your timings or be separate from the timing.

Handin

Before handing in your code, double check that it is well-styled:

• All variable names and function names use camelCase.
• All class names are in PascalCase.
• All public classes and methods use complete JavaDoc. (Double-check this by hand; the javadoc will only point out malformed Javadoc, not alert you to missing documentation!)
• All private class members (fields and methods) have their own descriptive comment (but not JavaDoc).
• Comments are added to explain complicated code blocks.
• All variable and function names are appropriately descriptive.
• All indenting and squigly-braces are properly placed.
• Each concrete (non-abstract) class should have a unit test (main method) that calls and tests all methods in the class.

Make your writeup for the project a wiki page in your personal space. If you have questions about making a wiki page, stop by my office or ask in lab.

Your writeup should have a simple format.

• A brief description of the overall task, in your own words.
• As explanation of your solution, focusing on the interesting bits. The interesting bits here are how you modified the basic design and implemented different simulations.
• Printouts, pictures, animations, or results to show what you did.
• Other results to demonstrate extensions you undertook.
• A brief conclusion and description of what you learned.

Once you have written up your assignment, give the page the label:

cs231f13project7

You can give any page a label when you're editing it using the label field at the bottom of the page.

Do not put code on your writeup page or anywhere it can be publicly accessed. To hand in code, put it on the Courses volume in your folder within the COMP/CS231 directory.