JavaScript: Parking lot simplified OOD

Question

I was trying to designing a simplified parking lot management system. It has three types of slots (s,m,l). The goal here is that we want to make the placement/release of cars as efficient as possible, ideally O(1).

The way I implemented is to use 3 separate stacks to hold empty spots for small, medium and large vehicles and whenever we have a vehicle to place, we check the stack of its size, if there is no empty spots for its size, we upgrade to the next stack of a larger size. So adding and releasing cars would be popping/pushing onto a stack so constant time complexity is guaranteed. And I also maintained a hash map to map the vehicle license id to the actual spot so we can do a constant time lookup when we need to retrieve a car.

Here is my code.

class Spot {
  constructor({ size, vehicle } = {}) {
    this.size = size
    this.vehicle = vehicle
  }

  addVehicle(vehicle) {
    if(this.isOccupied()) return false
    this.vehicle = vehicle
    return true
  }

  isOccupied() {
      return !!this.vehicle
  }

  getVehicle() {
    return this.vehicle
  }

  releaseVehicle() {
    const currentVehicle = this.vehicle
    this.vehicle = null

    return currentVehicle
  }
}

class ParkingLotManager {
  constructor({ size: { numOfSmallSpot, numOfMediumSpot, numOfLargeSpot } }) {
    this.emptySpots = Array.from({ length: 3 }, (_, i) => {
        if(this._getSizeIndex(1) === i) return Array.from({length: numOfSmallSpot}, () => (new Spot({size: 1})))
        if(this._getSizeIndex(2) === i) return Array.from({length: numOfMediumSpot}, () => (new Spot({size: 2})))
        if(this._getSizeIndex(3) === i) return Array.from({length: numOfLargeSpot}, () => (new Spot({size: 3})))
    })

    this.vehicles = new Map()
  }

  placeVehicle(vehicle) {
      if(this.hasVehicle(vehicle.licenseId)) throw new Error('duplicate vehicle found')
    const sizeIndex = this._getSizeIndex(vehicle.size)
    for (let i = sizeIndex; i < this.emptySpots.length; i++) {
      if (this.emptySpots[i].length > 0) {
        const spot = this.emptySpots[i].pop()
        spot.addVehicle(vehicle)
        this.vehicles.set(vehicle.licenseId, spot)
        return true
      }
    }

    return false
  }

  _getSizeIndex(size) {
    return size - 1
  }

  hasVehicle(licenseId) {
      return this.vehicles.has(licenseId)
  }

  removeVehicle(vehicle) {
    if (!this.hasVehicle(vehicle.licenseId)) return false
    const spot = this.vehicles.get(vehicle)
    spot.releaseVehicle()
    this.vehicles.delete(vehicle)
    this.emptySpots[this._getSizeIndex(this.spot.size)].push(spot)

    return true
  }
}

class Vehicle {
  constructor(id) {
    this.licenseId = id
  }
}

class Motorcycle extends Vehicle {
  constructor(id) {
    super(id)
    this.size = 1
  }
}

class Car extends Vehicle {
  constructor(id) {
    super(id)
    this.size = 2
  }
}

class Truck extends Vehicle {
  constructor(id) {
    super(id)
    this.size = 3
  }
}

const parkingLotManager = new ParkingLotManager({
    size: {
        numOfSmallSpot: 2,
        numOfMediumSpot: 2,
        numOfLargeSpot: 2
    }
})

const car1 = new Car('car1')
const car2 = new Car('car2')
const car3 = new Car('car3')

parkingLotManager.placeVehicle(car1)
parkingLotManager.placeVehicle(car2)
parkingLotManager.placeVehicle(car3)

const car4 = new Truck('car4')
const car5 = new Truck('car5')

parkingLotManager.placeVehicle(car4)



console.log(parkingLotManager);

Feel free to give me any feedback - including naming, design, encapsulation, extensibility etc.

Specifically, I hope I can improve these following aspects:

1. I am not particular clear on when I should throw an exception or return false for unsuccessful operation. For example, for placeVehicle method, if there is no empty spots, should I return false to indicate that the operation failed or should I just throw an exception? I guess it depends. but I wonder under which specific situation one approach is favorable than the other?

2. The way I handle the mapping from size to the index of the stack which holds the empty spots isn't very elegant. I am an integar to indicate different sizes because I cannot think of a better way. If I am writing TypeScript I guess I can use enum or union types for Size. but even with enum, I still need to translate it into the actual index. I wonder how I can achieve this gracefully and it is also easily extensible so in the future, if I wanted to expand the parking lot, can I easily add a forth size?

3. If I have multiple entrances for this parking lot and there is one car coming into this spot in the parking lot and at the same time, another car will be out of the spot. Then there is a deadlock, how can I avoid or resolve that?

Answer 1

Update: Added the hasVehicle() function, and added notes about performance.

Code Quality

Remove the fluff

As I understand it, the Spot class exists purely to help implement the ParkingLotManager class. It exposes a couple of public functions that never get used by ParkingLotManager() and can be removed or made private. The constructor to Spot() current allows you to set a starting vehicle, but no code is using that feature either, so this ability can be removed.

for-of

Instead of

for (let i = sizeIndex; i < this.emptySpots.length; i++) {
  if (this.emptySpots[i].length > 0) { ... }
}

you can use a for-of loop

for (const emptySpotGroup of this.emptySpots) {
  if (emptySpotGroup.length > 0) { ... }
}

Inheritance

I wouldn't say that it's always bad to use inheritance, but it certainly gets overused and often there's a better way to achieve the same objective. You can look up "Composition vs Inheritance" to learn more about this subject. In this scenario, instead of using inheritance to share information, you can use a factory function as follows:

const vehicleFactory = size => ({ licenseId }) => Object.freeze({ size, licenseId })
const createMotorcycle = vehicleFactory(0)
const createCar = vehicleFactory(1)
const createTruck = vehicleFactory(2)

Answering Questions

1. When to throw errors vs return a boolean (or other error-values)?

Javascript's error system isn't very great (it's very verbose to throw or catch errors of a specific subclass), which means there's some trade-offs to consider that largely depend on how defensively you want to program. Generally, its good to favor throwing errors as that can make it easier to track down bugs involving the program being in a bad state. If there's the ocasional rare case where you might need to catch the thrown error, then throw a subclass of Error instead of a normal Error object. If handling this exceptional case is somewhat common, then it can be more convenient to just return what's needed and let the user choose how to handle the result.

2. Dealing with vehicle sizes

Having integer-based sizes makes a lot of sense in this system, as it automatically provides an ordering to them. You can make your life even easier if you simply choose to make the sizes 0-based (small = 0, medium = 1, large = 2).

In the places in code where you wish to refer to a size by name, you can provide an object that translates names to numbers, providing enum-like behavior. (i.e. const SIZES = { small: 0, medium: 1, large: 2 })

3. How to avoid deadlocks?

By doing nothing. Javascript is single-threaded. In your implementation, you're never going to have a scenario where the javascript engine is executing one piece of code that's trying to put a vehicle into a stall while simultaneously executing different code that's taking a vehicle out. It always runs one task all the way to the end before starting the next one. This pattern of execution is referred to as javascript's event queue.

Performance

You wanted to make all of the functions run in O(1) time - I presume this is mostly to help exercise yourself in writing fast code. I just want to add a warning not to go overboard with performance in production applications - if you were building real parking-spot management software, there would be no reason to achieve O(1) lookup time, O(n) is good enough as there are only so many parking spots a lot can have. Development time is better spent improving other parts of the application.

Rewrite

Here's a rewrite of your code. You'll find that parts of the underlying logic are still very similar (I'm still using a 2d-array), but there's also a few fundamental changes (I took out the Spot class entirely). I have also chosen to assign ids to each parking spot. When you park a vehicle object, you get back the parking-spot id where it got stored. When it's time to drive it away, you get it back using that id.

You'll notice I'm using three different data-structures to hold parking spot/vehicle information. If this wasn't trying to achieve O(1) performance, then only one data-structure would be needed, greatly simplifying the code further.

const randomId = () => Math.random().toString().slice(2, 8)

// spotCountBySizes is an object of the shape
// { <size numb>: <number of spots with that size>, ... }
function createParkingLot(spotCountBySizes) {
  const spotSizes = Object.keys(spotCountBySizes).map(Number).sort()

  const occupiedSpots = {}
  const licenseIdsInLot = new Set()
  const freeSpotsBySize = spotSizes.map(
    size => Array.from({ length: spotCountBySizes[size] }, randomId)
  )

  return Object.freeze({
    placeVehicle(vehicle) {
      for (const size of spotSizes) {
        if (size >= vehicle.size && freeSpotsBySize[size].length > 0) {
          const spotId = freeSpotsBySize[size].pop()
          occupiedSpots[spotId] = { vehicle, spotSize: size }
          licenseIdsInLot.add(vehicle.licenseId)
          return spotId
        }
      }
      return null
    },
    removeVehicle(spotId) {
      const { vehicle, spotSize } = occupiedSpots[spotId]
      if (!vehicle) throw new Error(`The spot ${spotId} does not contain a vehicle.`)
      delete occupiedSpots[spotId]
      freeSpotsBySize[spotSize].push(spotId)
      licenseIdsInLot.delete(vehicle.licenseId)
      return vehicle
    },
    hasVehicle: licenseId => licenseIdsInLot.has(licenseId),
  })
}

const vehicleFactory = size => ({ licenseId }) => Object.freeze({ size, licenseId })
const createMotorcycle = vehicleFactory(0)
const createCar = vehicleFactory(1)
const createTruck = vehicleFactory(2)

Example usage:

const randomId = () => Math.random().toString().slice(2, 8)

// spotCountBySizes is an object of the shape
// { <size numb>: <number of spots with that size>, ... }
function createParkingLot(spotCountBySizes) {
  const spotSizes = Object.keys(spotCountBySizes).map(Number).sort()

  const occupiedSpots = {}
  const licenseIdsInLot = new Set()
  const freeSpotsBySize = spotSizes.map(
    size => Array.from({ length: spotCountBySizes[size] }, randomId)
  )

  return Object.freeze({
    placeVehicle(vehicle) {
      for (const size of spotSizes) {
        if (size >= vehicle.size && freeSpotsBySize[size].length > 0) {
          const spotId = freeSpotsBySize[size].pop()
          occupiedSpots[spotId] = { vehicle, spotSize: size }
          licenseIdsInLot.add(vehicle.licenseId)
          return spotId
        }
      }
      return null
    },
    removeVehicle(spotId) {
      const { vehicle, spotSize } = occupiedSpots[spotId]
      if (!vehicle) throw new Error(`The spot ${spotId} does not contain a vehicle.`)
      delete occupiedSpots[spotId]
      freeSpotsBySize[spotSize].push(spotId)
      licenseIdsInLot.delete(vehicle.licenseId)
      return vehicle
    },
    hasVehicle: licenseId => licenseIdsInLot.has(licenseId),
  })
}

const vehicleFactory = size => ({ licenseId }) => Object.freeze({ size, licenseId })
const createMotorcycle = vehicleFactory(0)
const createCar = vehicleFactory(1)
const createTruck = vehicleFactory(2)


// Example Usage

const SIZES = { small: 0, medium: 1, large: 2 }
const parkingLot = createParkingLot({
  [SIZES.small]: 2,
  [SIZES.medium]: 2,
  [SIZES.large]: 2,
})

const car1 = createCar({ licenseId: 'car1' })
const car2 = createCar({ licenseId: 'car2' })
const car3 = createCar({ licenseId: 'car3' })
const truck4 = createTruck({ licenseId: 'truck4' })
const truck5 = createTruck({ licenseId: 'truck5' })

const id1 = parkingLot.placeVehicle(car1)
const id2 = parkingLot.placeVehicle(car2)
const id3 = parkingLot.placeVehicle(car3)
const id4 = parkingLot.placeVehicle(truck4)
console.log(
  'Attempting to add vehicle when lot is full. Spot id returned:',
  parkingLot.placeVehicle(truck5)
)
parkingLot.removeVehicle(id3)
console.log(
  'Attempting to add vehicle again now that there is room. Spot id returned:',
  parkingLot.placeVehicle(truck5)
)

Answer 2

In no particular order;

• If your constructor takes an object and then applies the key/pairs of that object you might as well go for Object.assign(target, source); like this;

  constructor(template) {
    Object.assign(this, template);
  }
  

• I feel like you release a spot, not a vehicle. I would rename releaseVehicle to simply release. Furthermore it is super convenient for release to provide the vehicle that was there, but it makes the function name lie a bit? But then again, so does Array.pop() which does more than just popping. Final thought, since you have a ParkingLotManager anyway, I would let that class do a 'getVehicle' if needed, and then a release.

• I would use the aptly named Array.find() to find an empty spot instead of a loop

• I would separate the spot finding logic in to 'findFreeSpot(size)' unless it can be rewritten in to a one-liner

• I would rename addVehicle to setVehicle, you can only add 1 vehicle to a spot

• In the end, since vehicle is not private. I am not even sure I would encapsulate getters and setters

• This is a parking lot system, for sure O(1) is impossible, it sounds like this code falls in to the trap of premature optimization, my counter proposal will be 'slower' but should be more readable and more extensible

• However, in removeVehicle you go for hasVehicle which does the lookup, and then you go for vehicles.get which does the lookup again. You can drop one lookup by going straight for vehicles.get and checking for undefined

This is my counter proposal.

class Spot {
  constructor(template) {
    Object.assign(this, template);
  }

  fill(vehicle) {
    this.vehicle = vehicle
  }
  
  isFree(){
    return !this.vehicle
  }

  getVehicle() {
    return this.vehicle
  }

  release() {
    this.vehicle = undefined;
  }
}

class ParkingLotManager {
  
  constructor(vehicleTypes){
    this.spots = [];
    this.vehicles = new Map();
  }
  
  addSpots(vehicleType, idList){
    idList.forEach(id =>{
      this.spots.push(new Spot({vehicleType, id}));
    });
  }
  
  hasVehicle(licenseId){
    return this.vehicles.has(licenseId);
  }

  placeVehicle(vehicle) {
    if(this.hasVehicle(vehicle.licenseId)){ //Do some UI stuff here, dont throw..
      console.log(`There is already a vehicle here with id ${vehicle.licenseId}`);
      return;
    } 
        
    const spot = this.spots.find(spot => (vehicle instanceof spot.vehicleType && spot.isFree()));
    
    if(spot){
      spot.fill(vehicle)
      this.vehicles.set(vehicle.licenseId, spot);
      console.log(`Vehicle parked at ${spot.id}`)
    }else{
      console.log(`There is no free spot for ${vehicle.licenseId}`);
    }
  }

  removeVehicle(vehicle) {
    const spot = this.vehicles.get(vehicle.licenseId);
    if (spot){
      spot.release();
      this.vehicles.delete(vehicle.licenseId);      
    }else{
      console.log("There is no vehicle with that license id")  
    }
  }
 
}

class Vehicle {
  constructor(id) {
    this.licenseId = id
  }
}

class Motorcycle extends Vehicle {
  constructor(id) {
    super(id)
    this.size = 1
  }
}

class Car extends Vehicle {
  constructor(id) {
    super(id)
    this.size = 2
  }
}

class VIP extends Vehicle {
  constructor(id) {
    super(id)
    this.size = 2
  }
}

class Truck extends Vehicle {
  constructor(id) {
    super(id)
    this.size = 3
  }
}

const parkingLotManager = new ParkingLotManager();

parkingLotManager.addSpots(Motorcycle, ['M1', 'M2']);
parkingLotManager.addSpots(Truck, ['T1', 'T2']);
parkingLotManager.addSpots(Car, ['C1','C2']);
parkingLotManager.addSpots(VIP, ['V1']);

const car1 = new Car('car1')
const car2 = new Car('car2')
const car3 = new Car('car3')

parkingLotManager.placeVehicle(car1)
parkingLotManager.placeVehicle(car1)
parkingLotManager.placeVehicle(car2)
parkingLotManager.placeVehicle(car3)

const car4 = new Truck('car4')
const car5 = new Truck('car5')

parkingLotManager.placeVehicle(car4)

console.log(parkingLotManager);