Parking lot

some typical questions should be clarified beforehand:

• what types of vehicles it can support?
• whether the parking lot has multiple levels?

based on the requirements, we can make some reasonable assumptions:

• 1) n levels, each level has m rows of spots and each row has k spots.So each level has m x k spots.

• 2) The parking lot can park motorcycles, cars and buses (enum vehicleType class)

• 3) The parking lot has motorcycle spots, compact spots, and large spots (enum spotsType class)

• 4) Each row, motorcycle spots id is in range [0,k/4)(0 is included, k/4 is not included), compact spots id is in range [k/4,k/4*3) and large spots id is in range [k/4*3,k).

• 5) A motorcycle can park in any spot

• 6) A car park in single compact spot or large spot

• 7) A bus can park in five large spots that are consecutive and within same row. it can not park in small spots

in the following implementation, we should create an abstract class Vehicle, from which Car, Bus, and Motorcycle inherit.

功能性 的OOD, like parking lot and elevator, vending machine，

最关键的是分析functionality， what is the core feature? what is the core API?

核心

• what is the input?
• what is the output?

game OOD, kind of complexity, blackjack

refer to: https://github.com/zxqiu/leetcode-lintcode/blob/master/OO design/Parking_Lot.java

ParkingLot:

• attributes:
  • Level[][] levels;
• methods:
  • ParkingLot() /// constructor
  • parkVehicle(Vehicle vehicle)
  • unParkVehicle(...)

Level:

• attributes:
  • Spot[][] spots;
  • Map<Vehicle, List<Spot>> map;
• methods:
  • Level() /// constructor, need to initialize the spot...
  • parkVehicle(Vehicle vehicle)
  • unParkVehicle(...)
  • register(Spot[] row, int idx, Vehicle vehicle)
  • unregister(Vehicle vehicle) // because we have hashmap, we can unregister only through vehicle
  • isParked(Vehicle vehicle)
  • getVehicleSpotList(Vehicle vehicle)

Spot:

• attributes:
  • vehicleSize size;
  • Vehicle vehicle;
• methods:
  • Spot() // constructor
  • isAvailable()
  • getSize()
  • setVehicle()

Vehicle:

• attribute:
  • none
• method:
  • abstract:
    • getSize();
    • fitSpot()
    • parkToSpot();
  • boolean park();
  • boolean unpark();

Motorcycle

• attribute:
  • none
• method:
  • override
    • getSize()
    • fitSpot()
    • parkToSpot()

// enum type for Vehicle
public enum VehicleSize {
    Motorcycle,
    Compact,
    Large,
    Bus
}

abstract class Vehicle {
    public abstract VehicleSize getSize();
    protected abstract boolean fitSpot(Spot[] row, int idx);
    protected abstract void parkToSpot(Spot[] row, int idx);

    public boolean park(Spot[] row, int idx) {
        if (!fitSpot(row, idx)) {
            return false;
        }

        parkToSpot(row, idx);
        return true;
    }

    public void unpark(List<Spot> spots) {
        for (Spot spot : spots) {
            spot.setVehicle(null);
        }
    }
}

class Motorcycle extends Vehicle {
    @Override
    public VehicleSize getSize() {
        return VehicleSize.Motorcycle;
    }

    @Override
    protected boolean fitSpot(Spot[] row, int idx) {
        return true;
    }

    @Override
    protected void parkToSpot(Spot[] row, int idx) {
        row[idx].setVehicle(this);
    }
}

class Car extends Vehicle {
    @Override
    public VehicleSize getSize() {
        return VehicleSize.Compact;
    }

    @Override
    protected boolean fitSpot(Spot[] row, int idx) {
        if (row[idx].getSize() == VehicleSize.Motorcycle) {
            return false;
        }

        return true;
    }

    @Override
    protected void parkToSpot(Spot[] row, int idx) {
        row[idx].setVehicle(this);
    }
}

class Bus extends Vehicle {
    @Override
    public VehicleSize getSize() {
        return VehicleSize.Bus;
    }

    @Override
    protected boolean fitSpot(Spot[] row, int idx) {
        int k;

        if (row[idx].getSize() != VehicleSize.Large) {
            return false;
        }

        for (k = idx; k < row.length && row[k].vehicle == null; k++);

        if (k - idx >= 5) {
            return true;
        }

        return false;
    }

    @Override
    protected void parkToSpot(Spot[] row, int idx) {
        for (int i = idx; i < idx + 5; i++) {
            row[i].setVehicle(this);
        }
    }
}

class Spot {
    VehicleSize size;
    Vehicle vehicle;

    public Spot(VehicleSize size) {
        this.size = size;
        vehicle = null;
    }

    public boolean isAvailable() {
        return vehicle == null;
    }

    public VehicleSize getSize() {
        return size;
    }

    public void setVehicle(Vehicle vehicle) {
        this.vehicle = vehicle;
    }
}

/* Represents a level in a parking garage */
class Level {
    Spot[][] spots;
    HashMap<Vehicle, List<Spot>> map;

    public Level(int m, int n) {
        map = new HashMap<Vehicle, List<Spot>>();
        spots = new Spot[m][n];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (j < n / 4) {
                    spots[i][j] = new Spot(VehicleSize.Motorcycle);
                } else if (j >= n / 4 * 3) {
                    spots[i][j] = new Spot(VehicleSize.Large);
                } else {
                    spots[i][j] = new Spot(VehicleSize.Compact);
                }
            }
        }
    }

    public boolean parkVehicle(Vehicle vehicle) {
        for (int i = 0; i < spots.length; i++) {
            for (int j = 0; j < spots[i].length; j++) {
                Spot spot = spots[i][j];

                if (!spot.isAvailable()) {
                    continue;
                }

                if (vehicle.park(spots[i], j)) {
                    register(spots[i], j, vehicle);
                    return true;
                }
            }
        }

        return false;
    }

    private void register(Spot[] row, int idx, Vehicle vehicle) {
        if (!map.containsKey(vehicle)) {
            map.put(vehicle, new ArrayList<Spot>());
        }

        if (vehicle.getSize() == VehicleSize.Bus) {
            for (int i = idx; i < idx + 5; i++) {
                map.get(vehicle).add(row[i]);
            }
        } else {
            map.get(vehicle).add(row[idx]);
        }
    }

    public boolean unparkVehicle(Vehicle vehicle) {
        if (isParked(vehicle)) {
            vehicle.unpark(getVehicleSpotList(vehicle));
            unregister(vehicle);
            return true;
        }

        return false;
    }

    private void unregister(Vehicle vehicle) {
        map.remove(vehicle);
    }

    private boolean isParked(Vehicle vehicle) {
        return map.containsKey(vehicle);
    }

    private List<Spot> getVehicleSpotList(Vehicle vehicle) {
        return map.get(vehicle);
    }
}

public class ParkingLot {

    Level[] levels;

    // @param n number of leves
    // @param num_rows  each level has num_rows rows of spots
    // @param spots_per_row each row has spots_per_row spots
    public ParkingLot(int n, int num_rows, int spots_per_row) {
        levels = new Level[n];

        for (int i = 0; i < levels.length; i++) {
            levels[i] = new Level(num_rows, spots_per_row);
        }
    }

    // Park the vehicle in a spot (or multiple spots)
    // Return false if failed
    public boolean parkVehicle(Vehicle vehicle) {
        for (Level level : levels) {
            if (level.parkVehicle(vehicle)) {
                return true;
            }
        }

        return false;
    }

    // unPark the vehicle
    public void unParkVehicle(Vehicle vehicle) {
        for (Level level : levels) {
            if (level.unparkVehicle(vehicle)) {
                return;
            }
        }
    }
}