CS 261 Homework 8 - Space Port Simulation

Due Mon Apr 28 at 11:59pm

Overview

In this assignment, you will have a chance to experiment with different implementations of HashMaps, testing the effects of different hashing algorithms, methods for dealing with collisions, and other parameters.

But in order to make things a little more interesting, you'll be experimenting with the effects of HashMap implementations in the context of a system simulation. Simulations are one of the most common uses of computer programs and advanced data structures--we develop a "model" (like an ADT) of the system at work, and then test that model with a sequence of sample inputs to see how it behaves and changes over time. This is very helpful both for understanding the model, understanding the phenomenon the model represents, and even testing whether the model is accurate or not!

For this assignment, you will be implementing HashMaps to model a few different Intergalactic Space Ports! Ships will arrive and be "docked" at your space port in a particular berth, eventually leaving when the pilot's business is concluded. You'll be keeping track of how many "collisions" occur between ships, either when bringing a ship into dock, or ferrying people to the proper berth. Furthermore, the Authorities who run the space port are highly worried about piracy and the transporation of dangerous goods, and so have a policy that involves random "inspections" of docked ships for illegally smuggled goods. (Of course, the security theater means that the inspections aren't implemented very cleanly, and they Authorities have a habit of trying to inspect ships that aren't actually in port---and searching for the non-existent ship involves colliding with those already docked!) Finally, you'll keep trac of the amount of space required for berths in your spaceport, since your parking garage is on prime galactic real estate.

In other words, by the end of the assignment you'll have implemented a few different HashMaps, and be able to report statistics about their usage!

This assignment should be completed individually. You are welcome to ask for help from me, or from your classmates (but remember to follow the Gilligan's Island rule)! Note that much of the code for this assignment can be adapted from chapter 7 of the textbook or from class lecture code, so it should be straightforward to write (and doable in the relatively short time provided).

Objectives

To practice implementing HashMaps
To experiment with the effects of different hashing algorithms and collision resolution techniques
To practice measuring the efficiency of a data structure's implementation

Necessary Files

You will need a copy of the Hwk8.zip file. This file contains a pile of classes to get you started. Since the goal of this assignment is to experiment with HashMaps, I've provided the framework for running the simulation---however, you can improve this simulation as an extension to the assignment!

The zip file contains the following classes:

SpaceShip A simple ADT to represent a SpaceShip. Ships have a "license" (a unique id, like a registration number or a license plate) and a cargo.
SpaceSport An interface that represents a SpacePort (basically a HashMap). The SpacePorts you create should implement this interface.
LicenseHasher Another interface for an object that has one purpose: to calculate hash codes for ship licenses. By creating different implementions of this interface, it becomes easy to swap out the hashing algorithm used by different ports without needing to modify the ADT's source code!
SpacePortSimulation A launcher class that will run the simulation. This class reads in a simulation procedure from a file, and then executes that procedure and prints the results. Note that you will need to modify the main() method in this class to test different space ports (though it should be trivial to make such tests user-specifiable!)

The zip file also contains a couple of simulations to test with--these are squences of "events" (arrivals, departures, etc) that your simulation will run. simulation0.txt contains the most basic example of events--you are also welcome to modify this to test other cases (e.g., when particular ships arrive/leave/etc.). simulation1.txt contains a sequence of ~1000 "events" (arrivals, departures, etc), and simulation2.txt contains ~15000.

Lastly, the zip contains the README for the assignment, which you will need to fill out. You will need to do some actual analysis and writing for this readme, so don't forget it!

Assignment Details

You will be creating a number of new classes for this assignment. However, they should be pretty straightforward, and you can use inheritance to avoid code duplication!

The majority of the work you'll be doing is developing classes to represent different kinds of SpacePorts for your simulation--each run of the simulation will be specified on a different SpacePort. A SpacePort is basically a HashMap, just with some of the method names tweaked. I recommend you build the SpacePort directly as an implementation of the HashMap data structure (the same way that the DecomposableShape was a linked-list), but you can also use an implemenetd HashMap as a member variable of the SpacePort, thereby making the SpacePort a kind of wrapper class (with a different public interface).
- Note that you won't be able to just use the built-in java.util.HashMap class, as you're going to need to keep track of what is going on underneath the public interface. So you'll need to 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 much of the implementation in class (again, which you can adapt). You are welcome to use this code in your program---just be sure and to credit the source of your code, and to add copious comments to demonstrate you understand how it works!
You will need to develop at least two (2) different kinds of SpacePorts, each of which implement the SpacePort interface. These SpacePorts will likely share some functionality--it is a good idea to use inheritance to avoid code duplication (e.g., have one be a subclass of the other, or both be subclasses of some abstract class).
- BasicSpacePort This should be your (ahem) basic SpacePort class, which uses a long line of berths to store SpaceShips. It should implement a standard HashMap using open addressing and linear probing to deal with collisions. We will talk about this method in class, and further details are in the textbook.
  - It is pretty trivial to make a QuadraticSpacePort class that uses quadratic probing to deal with collisions. You can do this as an extra-credit extension.
  - You could also make a DoubleSpacePort that uses double hashing instead. Again, this is a good extra-credit extension.
- DimensionalSpacePort This SpacePort uses small wormholes to store multiple Spaceships in the same location. Thus this SpacePort should use chaining to store SpaceShips that would otherwise collide. Note that you will still need to keep track of the amount of extradimensional space you have used; the authorities monitor stuff like that.
All of your SpacePorts will need to implement the SpacePort interface. However, since constructors can't be specified in an interface, and an abstract class wouldn't be appropriate (why not?), the required constructor is detailed below:
```
/**
 * Constructor for a SpacePort
 * @param hasher A LicenseHasher that will be used to determine berths for incoming SpaceShips
 * @param loadThreshold The maximum "load" the SpaceSport can support before it needs to expand, in double precision
 */
public MySpacePort(LicenseHasher hasher, double loadThreshold)
```
The LicenseHasher class is described directly below, and more details about the loadThreshold can be found in the text and will be discussed in class.
- As per the text, 0.75 is a generally a good load threshold for testing the BasicSpacePort (referring to the "percentage of berths filled", and 3.0 is generally a good load threshold for testing the DimensionalSpacePort (referring to the "number of ships per wormhole").
- As an optional component, you can also have the constructor take in an initial number of berths. For this simulation, you'll get the most interesting results if you start with around 11 initial berths.
- It's worth noting that since ships keep track of their own keys, it's possible (and more space efficient) to simply store the SpaceShips rather than (key, value) Entries; but either method is acceptable.(Using Entries would allow for keys that might NOT be ship licenses!)
The other constructor parameter is for a Licensehasher. This is a simple object that is able to take in ship's licenses and "hash" them into a version that can be used by the tiny robots that help dock ships in the port.
- By specifying an object that does key hashing, you can easily swap out different methods---including custom methods---for calculate hashcodes. Thus rather than calling .hashCode() on the key in order to get a hashcode, you pass that key to the Hasher's hash() method in order to get the hashcode.
- You will need to provide at least two (2) different LicenseHasher classes with different hashing algorithms. One of these can be the built-in Java hashCode method. The other should be one of your devising.
  - Free free to get creative with different ways to convert a license String into a (positive) integer. You might also look at using pieces similar to other, cryptographic hashing functions
  - Watch for any impacts on your SpacePort's usage and statistics when using different hashing functions!
Make sure to give both your LicenseHashers and your SpacePorts appropriate toString() methods. These should be able to provide details about the type of SpacePort, the LicenseHasher used, and the port's load threshold, and so forth. This will help with viewing the statistics of your final simulation.
- You probably don't actually want to list out the contents of the SpacePort!
Your SpacePorts are basically HashMaps, though some of the methods have been renamed:
Note that you want or need other private helper methods to ease the implementation of your SpacePort and reduce code duplication. You should be able to determine their appropriateness or not!
- Similarly, there may be further instance variables or attributes that you need to keep track of. If you find you need to track something, do so!
In addition to implementing these different HashMaps and Hashing functions, you will need to keep track of some statistics about the usage of your SpacePort.
- These statistics will be reported via the getStatistics() method. This method will return a HashMap (yes, the one from java.util) that lets you look up the statistical value by a key. That key is a SpacePortSimulation.Statistic enumerated type--you can think of this as a "String" describing the statistic, but we're using constants for those Strings! This is a not a bad way to group lots of information in a single object that makes it easy to look things up.
Your SpacePorts will need to report the following statistics:
1. Current number of ships docked
2. Maximum number of ships docked (over the lifetime of the SpacePort)
3. Current number of available berths.
  - For the DimensionalSpacePort, count each ship in the "wormhole" as a single berthing, as well as any empty wormholes as single available berth.
4. Average number of collisions for a successful ship locating, per operation (e.g., method call). This should include the collisions that occur while docking, accessing, and removing a ship---but only if you actually find the ship!
  - For the BasicSpacePort, a collision occurs whenever you check if a berth is available and find that it is not. If the entry given by the hash function is free, there is no collision. If the entry given by the hash function is already taken, but checking the next berth finds that it is free, there was 1 collision. And so forth. Note finding that the berth contains the ship you are searching for does NOT count as a collision!
  - For the DimensionalSpacePort, the same rules apply--however, each item you need to "check" inside the wormhole also counts as a collision.
  - Statistics should be given in integer precision; round up (hint: try the Math.ceil() method!)
  - Bonus hint: you can only calculate the average once you've figure out how many method calls there have been! Try to keep track of the running total of collisions, as well as the number of method calls, then divide to find the average. You might need to use a long to count collisions if there are a lot!
5. Maximum number of collisions for successful ship locating, per operation (e.g., method call). This should include the collisions that occur while docking, accessing, and removing a ship.
  - Collisions should be determined the same way as above
  - You'll need to keep track of the current maximum of each method call. If this method call included more collisions, then update the maximum!
6. Average number of collisions for unsuccessful ship locating (includes removing and accessing). This means the average if you tried to find a ship but it wasn't actually there!
  - Same rules and hints as statistic 4 apply!
7. Maximum number of collisions for unsuccessful ship locating (includes removing and accessing)
8. Average number of collisions for all ship locating (includes docking, removing, and accessing)
  - This is basically the combination of the previous statistics
9. Maximum number of collisions for all ship locating (includes docking, removing, and accessing)
If you have any questions on what you should be counting, please let me know!
After you have implemented your SpacePorts, run them through the simulation with different Hashers and load thresholds. The README.txt has a number of questions you will need to address analyzing the results of your simulation---be sure and fill this out!
- You should compare the number of collisions (based on the load factor) with the number of "probes" detailed in the textbook on page 381. If your numbers don't quite match, consider what might be the cause of the discrepancy!
- Note that testing your SpacePorts with small, well-defined simulation files will help make sure that results are as expected and not due to a programming error.

Timeline

This assignment involves a few moving parts, but most of the work (implementing HashMaps) can be adapted from the textbook and the lecture code, allowing you to focus in on tracking the statistics of the simulation. But since we'll be continuing to talk about HashMaps, you may consider completing this assignment in the following order:

Start by reading through the assignment and inspect the provided classes. Create the skeletons of the required classes so you can run the simulation (it should mostly run, though it will report a lot of errors). Then focus on implementing your LicenseHasher classes; this involved writing hash functions similar to the one(s) we talked about in class. You should be able to do this by Mon 04/21
Next, implement the BasicSpacePort class (using open addressing and linear probing). We will start implementing this on Monday in class, and more details are in the text. You should be able to get most of it finished by Wed 04/23
- This implementation should include tracking the statistics!
You can implement the DimensionalSpacePort by Fri 04/25, as it only involves a few changes from the basic model!
This leaves you until Mon 04/28 to clear up any problems, do your tests and analysis of the simulaion, and otherwise finish up the assignment.

Extensions

There are a number of extensions you can include, for possible 10 pts of extra credit this time!

Implement a QuadraticSpacePort that uses quadratic probing to resolve collisions, or a DoubleSpacePort that uses double hashing to resolve collisions. Be sure and include an analysis of how this SpacePort compares to the basic!
You can also implement a SpacePort using an underlying ArrayList or Tree data structure. In this case "collisions" would measure the number of comparisons performed to access SpaceShips. Again, be sure and discuss this SpacePort in your analysis.
You might try modifying the simulation to make it more complex. For example, the provided simulation files include a couple of random numbers after each ship; you can have these represent things like the amount or value of the cargo, the speed of the ship, the size of the ship (so berthing should "cost" more), etc. Can you even make a "SimSpacePort" version of this program, where the goal is to design a SpacePort that handles the SpaceShips with the least cost?
- You may need code that randomly generates SpaceShips for this
Finally, can you develop a graphical UI or animation that illustrates what is happening in the simulation--or at least provides an easy way to run the simulation with different parameters?

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! Your name should be in the class comment at the top of each class.

Submit all your classes to the Hwk8 submission folder on hedwig. Make sure you upload your work to the correct folder!. You should upload your entire src folder with all your classes. Be sure to complete the provided README.txt file with details about your program--this is a really important part of the assignment!

The homework is due at midnight on Monday, Apr 28.

Grading

This assignment will be graded on approximately the following criteria:

You have included two different hashing algorithms [10%]
You have implemented the BasicSpacePort [20%]
You have implemented the DimensionalSpacePort [20%]
Your SpacePorts track usage statistics (e.g., the number of collisions) [25%]
Your program demonstrates good object-oriented style [5%]
Your program is fully documented, including explanative inline comments [5%]
The README is completed, including analysis of the simulations [15%]