CS 261 Homework 6 - Space Port Simulator

Due Wed Apr 24 at 11:59pm

Overview

In this assignment, you will be able to practice and experiment with implementing HashMaps, looking at the effects of different hashing algorithms and techniques for dealing with collisions.

But in an attempt to make things a little more interesting, you'll be using an implemented HashMap to model the underlying engine of a program that simulates a Intergalactic Space Port! Your SpacePort will function as a ship valet service: spaceships will arrive at your port, you will dock them in your port, and then later retrieve them for the pilots. Your port will charge pilots based on how long they stay docked. Your port is basically a HashTable, which is good because pilots are impatient folk (they feel the need--the need for speed) and you promise them a price discount based on how long it takes to takes to park and retrieve their vehicle. In addition, your SpacePort will be charged for each "collision" that occurs when parking the vehicles (you have to pay for damages). Finally, there is a cost associated with the amount of space required for your spaceport--your parking garage is on prime galactic real estate.

By the end of this assignment, you will have implemented a few variations of HashMaps, in order to support a working simulation. Computer simulations are a common and useful kind of program, and are particularly good at demonstrating why efficient code and data structures are helpful!

This assignment should be completed individually. Note that this assignment is intentionally written to be both straightforward and somewhat vague. Implementing different HashMaps should be pretty clear (you are welcome to adapt code from lecture or from the book). However, what you do with the simulation is up to you: feel free to be creative! Take ownership of your own programming! If you have questions or ideas I'm happy to discuss them, but you should be able to start adding ideas and functionality on your own!

Objectives

To practice implementing HashMaps
To practice using inheritance and polymorphism in developing larger simulations
To develop another vaguely interesting simulation.

Necessary Files

You will want a copy of the Hwk6.zip file which contains a pile of classes to help get you started. Since the goal of this assignment is primarily to play with HashMaps, I've provided a lot of supporting code to let you hit the ground running. These classes include:

SpaceShip A simple class to represent a SpaceShip. Ships currently have a "license" (a 'unique' id) and a cargo.
SpaceShipValet A wrapper class to act as a valet for a SpaceShip. The valet keeps track of when ships arrive and leave the dock. Note that you can easily modify the SpaceShip, leaving the valet the same.
SpaceSport An interface that represents a SpacePort (basically a HashMap). The SpacePorts you create should implement this interface.
SpacePortAuthority A class that monitors your SpacePort and helps keep track of costs and such. This class acts as an interface between the HashMap and the overall simulation, making it easy to try out different kinds of HashMaps!
SpacePortSimulation A very simple example of a simulation (like a tester class). You will want to modify this and make it more interesting.
ShipHasher Another interface for an object that has one purpose: to calculate HashCodes for ships. By creating different implementions of this interface, it should be easy to swap out the hashing algorithm used by different ports at the level of the Tester, rather than needing to modify the source code.

Be sure to look over all of these classes carefully, and feel free to modify them as needed to support your simulation (though be sure to include notes about what you modify in your README!)

I have also included a small file listing random spaceships for your simulation to use (ships.txt). I've also included the grammar file used to produce this list of random ships via the RandomSentenceGenerator from the last homework (spaceship_grammar.txt); this should demonstrate how useful the previous assignment was, and you can use the grammar to make longer lists of random SpaceShips (you can also of course modify the grammar if you wish to make more interesting/varied cargoes).

Last but not least, the zip contains the README for the assignment, which you will need to fill out!

Details

There are basically two pieces to this assignment. The first part involves implementing SpacePorts (i.e., HashMaps) to form the basis of your simulation. The second (smaller) part involves adapting and customizing the provided simulation to make it more detailed, interesting, or otherwise logical.

The SpacePort

You will develop a few different class that model a SpacePort for your simulation (each run of the simulation you can specify which SpacePort to use). A SpacePort is basically a HashMap, just with some of the method names tweaked. You are welcome to either build the SpacePort directly out of the HashMap data structure, or to use a HashMap as a member variable of the SpacePort (making the SpacePort a kind of wrapper class).
- You are NOT allowed to use the java.util.HashMap class (or any of its relatives) in this program. You should develop your HashMap from scratch!
- Except it won't really be from scratch; the textbook has lots of example code (see Chapter 7) that you can adapt, and we will be going over some of the code in class (again, which you can adapt).
You will need to develop at least two (2) different kinds of SpacePorts. Note that these SpacePorts will likely share some functionality--it is a good idea to use inheritance to avoid code duplication!
- BasicSpacePort This should be your (ahem) basic SpacePort class, implementing a standard HashMap. This SpacePort should use linear probing to deal with collisions
  - It is pretty trivial to make a QuadraticSpacePort class that uses quadratic probing to deal with collisions. You can do this as an extension.
  - You should also support different load factors and initial sizes (for choosing when to increase size). These parameters could be passed through the constructor.
- DimensionalSpacePort This SpacePort uses small wormholes to store multiple Spaceships in the same location. This SpacePort should use chaining to store SpaceShips that would otherwise collide. Note that you will need to report to the PortAuthority that you have increased the amount of extradimensional space you have used; they monitor stuff like that.
Your SpacePort should take a ShipHasher object as a parameter to its constructor. Then instead of calling .hashcode() on the key in order to calculate the hashcode, you can pass the key to the ShipHasher and have that object do the hashing. This will let you easily try out different hashing functions
- You should try out at least two (2) different hashing algorithms. One of these can be the built-in Java hashCode method. The other should be one of your devising. Do you see any difference between the efficiencies of the two algorithms? Can you come up with something that is comparable to Java's version?
Be sure to read the Javadoc comments explaining the SpacePort interface carefully. They detail what the method should do in order for your simulation to work.
- In particular, you need to be sure to report to the PortAuthority whenever you increase the size of your Port (e.g., when you rehash), as well as whenever a collision occurs while docking. This means your SpacePort will need to keep a reference to a SpacePortAuthority as a member variable, so that you can call its report methods.
Feel free to include whatever other helper methods you feel are appropriate. The key is to practice implementing these data structures from scratch!
Be sure to test your code extensively. Test all the edge cases: when the table is empty, when the table is full, when there is a collision, when there is not a collision, when a ship has already been removed, etc.
Check the text and ask lots of questions if you get stuck!

The Simulation

The second piece of the assignment is much more open-ended: your task is to improve upon and develop a better simulation of the SpacePort. Your simulation might be "better" some or all of the following ways:
- A more extensive test of the HashMap. Maybe your simulation works with much larger data sets (or run for much longer periods of time). Can you develop the system so that you are able to easily see the differences between different HashMap implementations?
  - You might want to put a small "pause" call between ship entries/exits or during searches to slow down the execution of the program (e.g., so that ships aren't docked for 0 milliseconds). You can do this using the static Thread.sleep() method (be sure to wrap it in a try/catch statement!)
- A more sensible sequence of ship arrivals and exits. The simulation currently picks a random ship from the list to either arrive or leave, but it would make more sense to only have ships that are currently docked want to leave. Maybe each ship (or each cargo?) is associated with a particular loading time, which specifies how long it stays docked or away from the port.
- A more sensible measure of time. Currently the program uses the clock's millisecond counter to measure "time". Implementing a separate counter (maybe representing number of time units), which can increase for each step of the simulation, may make the simulation more informative.
- Extending the simulation to multiple HashMap types. Implement further hashing algorithms or different chaining procedures, and see what happens!
My simulation is just a simple test. Your simulation should be a more solid model of how this (admittedly fantastic) system works!

Submitting

BEFORE YOU SUBMIT: make sure your code is fully documented and functional! If your code doesn't run, I can't give you credit!

In particular, make sure that your HashMaps are fully commented (particularly if you adapted code from the book)--this will help demonstrate that you understand what is going on!

Also make sure you that have filled out the README.txt! There are actually some questions of note here that you will need to answer.

Submit your program to the Hwk6 submission folder on hedwig, following the instructions detailed in Lab A. You should upload all you classes, as well as the README.txt.

The homework is due at midnight on Wed Apr 24.

Extensions

The simulation advancements themselves are a kind of extension. Nevertheless, there are a few "above and beyond" things you might consider (and may earn extra credit for):

The SpacePort interface doesn't have to be a HashMap! Can you implement a Tree or an ArrayList that supports the interface? How does that affect the simulation?
Can you make a simple GUI/animation that represents and illustrates the simulation? Chuck developed a simple example in the original version of the assignment; can you do him one better?

Grading

This assignment will be graded based on approximately the following criteria:

Your simulation includes at least two different hashing algorithms [10%]
Your program implements a basic HashMap for the SpacePort (adding, deleting, etc.) [30%]
Your program implements a chaining HashMap for the SpacePort [15%]
Your HashMaps support the basic simulation requirements (e.g., reporting collisions, etc) [10%]
Your simulation improves upon the provided skeleton [10%]
Your program demonstrates good Java style. Coupling & cohesion remain particularly relevant [10%]
Program is fully documented with complete Javadoc comments [10%]
The README is completed [5%]