CS 231: Data Structures and Algorithms (Lab Page)

Title image Project 3
Fall 2016

Spatial Simulation: Parking Cars

The main purpose of this project is to use stacks to simulate the arrangement of cars in a parking garage. The simulated garage is modeled after Stephanie's favorite parking garage in Boston and is designed to maximize the number of cars that can park - not to facilitate easy movement of cars. Cars are parked in lanes, such that the first car in may have many cars parked behind it. It will need to be the last one out. In other words, each lane is a stack. The simulation of the parking garage will have 5 stacks representing 5 parking lanes. It will also have a sixth stack, representing a temporary parking lane (we will call it a holding area). This way, if a driver is demanding their car, the attendant can put all the cars behind it into the temporary lane, remove the driver's car, then put the other back in the lane.


Tasks

  1. Car: create a Car object to represents a car that is being parked or moved around in a parking garage. The Car class is modeled after the Cell class from the previous project, but it will not have an updateState method -- cars are passive agents. The Car class should store its color, store the time it wants to be retrieved from the garage (an int that indicates at which time step it should be removed), and implement the following methods.
    • public Car(int timeToLeave) - constructor method. timeToLeave indicates at which timestep the car should be retrieved from the garage. By default, the car is red.
    • public Car(int timeToLeave, Color color) - constructor method.
    • public int getTimeToLeave() - accessor that returns the time at which the car should leave.
    • public String toString() - returns a string that indicates the color and time the car will be retrieved from the garage.

    Implement the above methods and test them with a main method.

  2. CarStack: create a CarStack class to store a stack of Cars, modeling after IntStack. It should store the index of the top of the stack, an array of Cars, and implement the following methods:
    • public CarStack( ) - constructor method. Make an array of 10 Cars and initialize the top index to be 0.
    • public void push( Car new_item ) - push a new item onto the stack.
    • public Car pop() - pop and item off the stack and return it.
    • public Car elementAt( int index ) - return the element at the given position (do not modify the stack).
    • public int size() - return the number of items in the stack.
    • public boolean isEmpty() - returns true if the stack is empty.

    Implement the above methods and test them with a main method.

  3. ParkingGarage: create a ParkingGarage class to store lanes (stacks) of Cars. The ParkingGarage class is modeled after the Landscape class from the previous project, but, instead of having a simple advance method, has specific methods to park and unpark cars. The ParkingGarage is a smart object in that the logic for moving around cars belongs in its methods. Think of the ParkingGarage as indirectly simulating the parking attendants. It should have fields to store the lanes (an array of CarStacks), the holding area (a CarStack), and the maximum number of cars in any lane, including the holding area (an int). Start by implementing these methods:
    • public ParkingGarage( int numLanes, int maxLaneSize ) - initializes numLanes CarStacks to act as lanes, a holding area, and sets the maximum lane size.
    • public int getNumLanes() - return the number of lanes in the garage (not including the holding area)
    • public int getMaxLaneSize() - return the maximum number of cars that will fit in each lane.
    • public boolean parkCar( Car car ) - If there is a lane with an available spot, then park the car in that spot and return true. Otherwise, return false. It is up to you to determine a strategy for finding a spot. You may want to fill in the cars one lane at a time or you may want to cycle through the lanes. At this point, your strategy should not ask Car what time it wants to leave.

      Note that the CarStack object does not have a maximum size. It is up to the code in parkCar to enforce the maximum lane size. A lane is full is the CarStack's size is equal to max lane size.

    • public String toString() - Return a string indicating how many cars are currently in the holding area, along with how many cars are parked in each lane.

    Implement the above methods and test them with a main method.

  4. Make it possible to visualize your ParkingGarage.
    1. Copy LandscapeDisplay.java from last week, making ParkingGarageDisplay.java. Update it so that it stores a ParkingGarage instead of a Landscape.
    2. Add a method to your Car class:

      public void draw(Graphics g, int x, int y, int w, int h) - Draw a car in the rectangle that is rooted at (x,y) and has width w, and height h. Be sure to use the color field of the Car to set the color.

    3. Add a method to your ParkingGarage class:

      public void draw(Graphics g, int scale) - Draw the parking garage at the given scale. Use information about the location of each lane to determine the location of each car. At a minimum, this should draw the set of parking lanes. It could also include the holding area, but that may not be interesting (spoiler: the holding area is emptied at the end of every time step, so there will be nothing to draw).

    Test your visualization by running ParkingGarageDisplay as your main program. You will need to update the main program to create new Cars, create a ParkingGarage, and park the cars.

  5. Add a method to the ParkingGarage class:

    public void retrieveCar( Car car ) - Remove the car from the lane its is parked in. If there are cars behind it, move those cars into the holding area, then remove the car, then put the others back into the lane.

    Test the method by adding code to your main method in LandscapeDisplay. Display a full garage, then display one with one of the cars removed. Note that you can create, park, and remove a car with the following code

            Car c1 = new Car( 10, new Color( 1.0f, 0.0f, 0.0f ) );
            Car c2 = new Car( 3, new Color( 0.0f, 1.0f, 0.0f ));
            parkingGarage.parkCar( c1 );
            parkingGarage.parkCar( c2 );
            parkingGarage.retrieveCar( c1 );
        
  6. ParkingSimulation - create a class that will simulate Cars being parked an retrieved. This class will be modeled after LifeSimulation, but will have more logic in it. Implement a method:

    public void run(double probabilityToPark) - run a simulation. At each time step, at most two new cars are parked, each with proability probabilityToPark (i.e. at each time step, 0, 1, or 2 cars will drive into the ParkingGarage to be parked).

    The simulation will need to generate new cars, park them, and ask for them to be retrieved. That means that whenever a new car is parked, the simulation can't lose its reference to it. It will need to maintain a master list of parked cars. On each time step, it should cycle through that list, and check its timeToLeave. If it is time for that car to be retrieved, then the simulation should retrieve the car and remove it from the master list.

    The outline of the simulation is:

    • Initialize your variables. You will need a ParkingGarage (with 5 lanes and a maximum of 10 cars in each lane), a random number generator (Random gen = new Random();), a ParkingGarageDisplay (I used a scale of 20), a master list of cars (an ArrayList<Car>), a list of cars that have been retrieved (an ArrayList<Car>), the number of cars who failed to park, and the number of cars who tried to park.
    • Loop over the time steps. For each time step
      • Loop twice
        • If a randomly chosen value between 0.0 and 1.0 (use nextFloat()) is less than the probabilitytoPark, then
          • Generate a new Car with a randomly chosen timeToLeave value between current time step (which I have called i) and 100 time steps after it and with a randomly chosen color:
                                       Car c = new Car( i + 1 + gen.nextInt(100), 
                                                                 new Color( gen.nextFloat(), 
                                                                    gen.nextFloat(), 
                                                                    gen.nextFloat() ) );
                        
          • Increment the counter associated with the number of cars that have tried to park.
          • Park the car in the garage. If it is successful, add that car to the master list. If not, increment the counter associated with cars that fail to park,
      • Loop through the cars in the master list, to see if any of them need to be retrieved. If a Car's timeToLeave value matches the current time step, then ask the garage to retrieve the car, and remove the car from the master list. But be careful how you do this. If you try to modify a list while you are looping through it using an iterator, then Java will object.

        Here is an example with an ArrayList of Integers. Our goal is to loop through the list and remove all the 3's as we go. There are two options shown. The first works. The second will throw a java.util.ConcurrentModificationException.

                ArrayList<Integer> a = new ArrayList<Integer>();
                a.add( 3 );
                a.add( 1 );
                a.add( 2 );
                a.add( 3 );
                a.add( 3 );
                a.add( 4 );
                a.add( 3 );
                
                // Option 1 - use indices directly
                for (int idx = 0; idx < a.size(); idx++) {
                    if (a.get(idx) == 3) {
                        a.remove(idx);
                        idx--;
                    }
                }
        
                // Option 2 (doesn't work) - use an iterator
                for (Integer int_obj: a) {
                    if (int_obj == 3) {
                        a.remove( int_obj ); // can't modify list as you iterate through it.
                    }
                }
                
      • Repaint the display, save the image, and make the thread sleep
    • Finally, print out the statistics (the number of cars that tried to park and the number of cars that failed to park.)

Extensions

Each assignment will have a set of suggested extensions. The required tasks constitute about 85% of the assignment, and if you do only the required tasks and do them well you will earn a B+. To earn a higher grade, you need to undertake at least one extension. The difficulty and quality of the extension or extensions will determine your final grade for the assignment. One significant extension, or 2-3 smaller ones, done well, is typical.

  1. Compute and report additional information. For example, it would be interesting to know how many times cars need to be placed in the holding area.
  2. Develop more than one parking strategy and compare their performance. The best performance will use the holding area for the fewest number of cars.
  3. Develop a parking strategy that asks each Car what time it wants to leave. Will it outperform "blind" strategies?
  4. For any assignment, a good extension will be to implement a Java class yourself and demonstrate that it has the same functionality as the Java class. For example, you could implement your own ArrayList class for this assignment.
  5. For any assignment, a good extension will be to annotate your code to indicate all places where memory is "lost" (in other words, each place where the last remaining reference to an object is either destroyed or is given a new value). If you do this extension, please indicate so in your write-up.

Handin

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.

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

cs231f16project3

You can give any wiki page a label using the label field at the bottom of the page. The label is different from the title.

Do not put code on your writeup page or anywhere it can be publicly accessed. To hand in code, put it in your folder on the Courses fileserver. Create a directory for each project inside the private folder inside your username folder.