This program implements the elevator algorithm.

The alogrithm is as below:

1. Continue traveling in the same direction while there are remaining requests in that same direction.
2. If there are no further requests in that direction, then stop and become idle, or change direction if there are requests in the opposite direction.

A single elevator gets the requests. And it simply prioritizes the request based on the direction it is currently travelling in.
For simplicity it doesn’t simulate the actual travel between floors. So we can’t test the cases where requests are made while elevator is completing a request.

First let’s see the three different types of requests which are possible.

• From inside the elevator, a request to go to a specific floor.
• From a floor (except the highest floor), a request to go up.
• From a floor (except the lowest floor), a request to go down.

Let’s define types ElevatorCommandType and ElevatorAction for these requests.

types.ts

export enum ElevatorCommandType {
  GO_TO_FLOOR = "GO_TO_FLOOR",
  GO_DOWN = "GO_DOWN",
  GO_UP = "GO_UP",
}

export type ElevatorAction = {
  /**
   * Elevator Command Type
   */
  type: ElevatorCommandType;
  /**
   * floor for which command is issues, it is 0-based index
   */
  floor: number;
};

Our elevator can be in one of the three states:

• Going Up
• Going Down
• Sitting Idle

So let’s define an enum called ElevatorDirection to represent this.
And combine that with floor to create a type called ElevatorState which will represent the current state of the elevator (say, 9 ⬇)

types.ts

export enum ElevatorDirection {
  UP = "UP",
  DOWN = "DOWN",
  IDLE = "IDLE",
}

export type ElevatorState = {
  direction: ElevatorDirection;
  floor: number;
};

At any moment, we can have multiple requests from different floors. I want to store these requests as an array of three boolean fields since we can only have three types of requests from each floor.

Lastly, based on the above image, following types would be clear.

types.ts

export type FloorRequest = {
  goUp: boolean;
  goDown: boolean;
  drop: boolean;
};

export type ElevatorData = {
  direction: ElevatorDirection;
  floor: number;
  requests: Array<FloorRequest>;
};

Low Level Implementation

We will start by defining the class and constructor for it. It will take the floors param to create the array of boolean values with default settings.

index.ts

import {
  ElevatorAction,
  ElevatorCommandType,
  ElevatorData,
  ElevatorDirection,
  ElevatorState,
  FloorRequest,
} from "./types";

export class Elevator {
  /**
   * Number of floors the elevator is configured to move
   */
  public floors: number;

  /**
   * Current Floor stores the last floor the elevator crossed.
   * Or if it is idle, then the current floor
   */
  private currentFloor: number;

  /**
   * The current direction in which elevator is moving
   */
  private currentDirection: ElevatorDirection;

  /**
   * requests is a list of floors storing boolean values.
   * While moving upwards, the elevator will stop
   * at a floor if the `goUp` or `drop` is true
   */
  protected requests: Array<FloorRequest>;

  /**
   * @param floors Number of floors elevator is configured to move
   */
  constructor(floors: number) {
    this.floors = floors;
    this.currentFloor = 0;
    this.currentDirection = ElevatorDirection.IDLE;

    this.requests = new Array(floors);

    for (let i = 0; i < this.requests.length; i++) {
      this.requests[i] = {
        goUp: false,
        goDown: false,
        drop: false,
      };
    }
  }

  // To be implemented
  public getRequests() {}
  public getCurrentState(): ElevatorState {}
  public getState(): ElevatorData {}
  public addCommand(command: ElevatorAction) {}
  private getCommandDirection(floor: number) {}
  private nextFloorInDirection(): {
    direction: ElevatorDirection;
    floor: number;
  } {}
  public getNextRequest(): ElevatorState {}
  public goToNextStep() {}
}

Here is the class diagram and we will implement rest of the functions now.

Below are some getter functions.

index.ts
export class Elevator {
  // ...

  /**
   * Get all requests
   */
  public getRequests() {
    return this.requests;
  }

  /**
   * Calculates the next state
   */
  public getCurrentState(): ElevatorState {
    return {
      direction: this.currentDirection,
      floor: this.currentFloor,
    };
  }

  /**
   * Returns the current elevator state
   * It's a combination of getCurrentState and getRequests
   */
  public getState(): ElevatorData {
    return {
      ...this.getCurrentState(),
      requests: [...this.requests],
    };
  }
}

We would need to implement getCommandDirection because we will use it inside addCommand.

index.ts
export class Elevator {
  // ...

  /**
   * Checks in which direction the given floor is based on the curernt fooor
   */
  private getCommandDirection(floor: number) {
    if (this.currentFloor > floor) {
      return ElevatorDirection.DOWN;
    } else if (this.currentFloor < floor) {
      return ElevatorDirection.UP;
    } else {
      return ElevatorDirection.IDLE;
    }
  }
}

Now let’s implement addCommand that updates either goDown, goUp, drop for the floor in the request.

Also, notice that we have used EventEmitter class to extend the Elevator class because we may want to notify subscribers (such as UI) for each state change.

index.ts

export const ELEVATOR_STATE_CHANGE = "ELEVATOR_STATE_CHANGE";

// Add event emitter to emit state change event
export class Elevator extends EventEmitter {
  // ...

  /**
   * Updates `goDown`, `goUp`, `drop` for the floor in the request
   */
  public addCommand(command: ElevatorAction) {
    const previousState = this.getState();

    let { floor, type } = command;

    if (floor < 0) {
      throw new Error("Floor must be 0 - " + (this.floors - 1));
    }

    if (floor > this.floors - 1) {
      throw new Error("Floor must be 0 - " + (this.floors - 1));
    }

    if (type === ElevatorCommandType.GO_DOWN) {
      // pick request for going down
      this.requests[floor].goDown = true;
    } else if (type === ElevatorCommandType.GO_UP) {
      // pick request for going up
      this.requests[floor].goUp = true;
    } else {
      // drop request
      let inDirection = this.getCommandDirection(floor);

      if (inDirection !== ElevatorDirection.IDLE) {
        this.requests[floor].drop = true;
      }
    }

    const newState = this.getState();

    this.emit(ELEVATOR_STATE_CHANGE, {
      previousState,
      newState,
    });
  }
}

The nextFloorInDirection function is probably the most important and deciding function of this algorithm.
It decides the next floor to stop at, with the direction the elevator would have to move in. We will use this regularly to take decisions for the elevator to stop.
It takes two params: direction and fromFloor.

If we are moving downards, then we want to check for the following requests from Floor fromFloor - 1 to Floor 0:

• a request to go down
• a request to drop

If no such request is present then we must check for the following request from floor 0 to the highest floor

• a request to go up
• a request to drop

Again if no such request is present then we must check for the following request from the highest floor to the fromFloor

• a request to go down
• a request to drop

The order is very crucial, because of the natual traversal of the elevator.

Similarly we can think of handling requests while moving in upwards direction.

If there is no request, then we can simply bring the elevator to the idle state.

index.ts

// Add event emitter to emit state change event
export class Elevator extends EventEmitter {
  // ...

  /**
   * Get the next floor to stop at
   */
  private nextFloorInDirection(
    direction: ElevatorDirection,
    fromFloor: number
  ) {
    // If elevator is going down - then we check from current to 0
    // then from 0 to top for going up
    if (
      direction === ElevatorDirection.DOWN ||
      direction === ElevatorDirection.IDLE
    ) {
      // from (fromFloor - 1) to 0
      for (let floor = fromFloor - 1; floor >= 0; floor--) {
        if (this.requests[floor].goDown === true) {
          return { direction: ElevatorDirection.DOWN, floor };
        }

        if (this.requests[floor].drop === true) {
          return { direction: ElevatorDirection.DOWN, floor };
        }
      }

      // from 0 to the top floor
      for (let floor = 0; floor < this.floors; floor++) {
        if (this.requests[floor].goUp === true) {
          return { direction: ElevatorDirection.UP, floor };
        }
        if (this.requests[floor].drop === true) {
          return { direction: ElevatorDirection.UP, floor };
        }
      }

      // from the top floor to the given floor
      for (let floor = this.floors - 1; floor >= fromFloor; floor--) {
        if (this.requests[floor].goDown === true) {
          return { direction: ElevatorDirection.DOWN, floor };
        }

        if (this.requests[floor].drop === true) {
          return { direction: ElevatorDirection.DOWN, floor };
        }
      }
    }

    // If elevator is going up - then we check from current + 1 to top
    // then we check from top to 0
    if (
      direction === ElevatorDirection.UP ||
      direction === ElevatorDirection.IDLE
    ) {
      // from the given floor to the top floor
      for (let floor = fromFloor + 1; floor < this.floors; floor++) {
        if (this.requests[floor].goUp === true) {
          return { direction: ElevatorDirection.UP, floor };
        }

        if (this.requests[floor].drop === true) {
          return { direction: ElevatorDirection.UP, floor };
        }
      }

      // from the top floor to floor 0
      for (let floor = this.floors - 1; floor >= 0; floor--) {
        if (this.requests[floor].goDown === true) {
          return { direction: ElevatorDirection.DOWN, floor };
        }

        if (this.requests[floor].drop === true) {
          return { direction: ElevatorDirection.DOWN, floor };
        }
      }

      // from floor 0 to the given floor
      for (let floor = 0; floor < fromFloor; floor++) {
        if (this.requests[floor].goUp === true) {
          return { direction: ElevatorDirection.UP, floor };
        }

        if (this.requests[floor].drop === true) {
          return { direction: ElevatorDirection.UP, floor };
        }
      }
    }

    return { direction: ElevatorDirection.IDLE, floor: -1 };
  }
}

The getNextRequest function is very simple and uses nextFloorInDirection to get the next request to serve.

index.ts

// Add event emitter to emit state change event
export class Elevator extends EventEmitter {
  // ...

  /**
   * Calculates the next state - direction and floor that elevator should go to
   */
  public getNextRequest(): ElevatorState {
    let { direction: nextDirection, floor: nextFloor } =
      this.nextFloorInDirection(this.currentDirection, this.currentFloor);

    // No next step
    if (nextFloor === -1) {
      return {
        direction: ElevatorDirection.IDLE,
        floor: this.currentFloor,
      };
    }

    return {
      direction: nextDirection,
      floor: nextFloor,
    };
  }
}

Now we can also implement the goToNextStep function.
It just gets the next request and updates the elevator state.

Ideally we should choose to simulate the elevator movement to each floor in sequence but that is also dependent on hardware or some UI capability to notify us as soon as the floor reaches each floor. Hence we are going to skip that part.

index.ts

// Add event emitter to emit state change event
export class Elevator extends EventEmitter {
  // ...

  /**
   * Updates the state to the next state,
   * Then updates the direction but not the floor
   */
  public goToNextStep() {
    let nextState = this.getNextRequest();

    const previousState = this.getState();

    this.currentDirection = nextState.direction;
    this.currentFloor = nextState.floor;

    // Mark the command complete
    // Alternatively we can loop from current floor to the nextState floor
    // to simulate the actual movement of the elevator
    if (this.currentDirection === ElevatorDirection.DOWN) {
      this.requests[this.currentFloor].goDown = false;
      // completed both picking to go down or dropping
      this.requests[this.currentFloor].drop = false;
    } else {
      this.requests[this.currentFloor].goUp = false;
      // completed both picking to go up or dropping
      this.requests[this.currentFloor].drop = false;
    }

    nextState = this.getNextRequest();
    this.currentDirection = nextState.direction;

    const newState = this.getState();

    this.emit(ELEVATOR_STATE_CHANGE, {
      previousState,
      newState,
    });
  }
}

We can now start to test this.
I am going to use jest for testing.

elevator.test.ts

import { Elevator } from "./Elevator";
import {
  ElevatorCommandType,
  ElevatorData,
  ElevatorDirection,
  ELEVATOR_STATE_CHANGE,
} from "./types";

it("test add command and pick from 8th floor and drop on 3rd floor ", () => {
  const elevator = new Elevator(10);

  elevator.addListener(ELEVATOR_STATE_CHANGE, (data) => {
    previousState = data.previousState;
    newState = data.newState;

    console.log(newState);
  });

  // Command to pick up from 8th Floor
  elevator.addCommand({
    floor: pickUpFloor,
    type: ElevatorCommandType.GO_DOWN,
  });

  // Check requests are updated properly by addCommand function
  let requests = elevator.getRequests();
  expect(requests[pickUpFloor].goDown).toBe(true);

  // Check next step function is giving correct data
  let nextStep = elevator.getNextRequest();
  expect(nextStep.direction).toBe(ElevatorDirection.DOWN);
  expect(nextStep.floor).toBe(pickUpFloor);

  // Move to the 8th floor
  elevator.goToNextStep();

  // After reaching the 8th floor, elevator is idle at the 8th floor
  requests = elevator.getRequests();
  expect(requests[pickUpFloor].goDown).toBe(false);
  expect(requests[pickUpFloor].drop).toBe(false);
  expect(newState!.floor).toBe(pickUpFloor);
  expect(newState!.direction).toBe(ElevatorDirection.IDLE);

  // Check next step function is giving correct data again
  nextStep = elevator.getNextRequest();
  expect(nextStep.direction).toBe(ElevatorDirection.IDLE);
  expect(nextStep.floor).toBe(pickUpFloor);

  // Command to drop to the 5th Floor
  elevator.addCommand({
    floor: dropFloor,
    type: ElevatorCommandType.GO_TO_FLOOR,
  });

  // Check stations are updated properly by addCommand function
  requests = elevator.getRequests();
  expect(requests[dropFloor].drop).toBe(true);

  // Check next step function is giving correct data again
  nextStep = elevator.getNextRequest();
  expect(nextStep.direction).toBe(ElevatorDirection.DOWN);
  expect(nextStep.floor).toBe(dropFloor);

  elevator.goToNextStep();

  // After reaching the 3rd floor, elevator is idle at the 3rd floor
  requests = elevator.getRequests();
  expect(requests[dropFloor].drop).toBe(false);
  expect(newState!.floor).toBe(dropFloor);
  expect(newState!.direction).toBe(ElevatorDirection.IDLE);

  // Check next step function is giving correct data again
  nextStep = elevator.getNextRequest();
  expect(nextStep.direction).toBe(ElevatorDirection.IDLE);
  expect(nextStep.floor).toBe(dropFloor);
});

I have also implemented this in React, you can check it out here.

If you have reached this point, thank you so much for reading this blog. Please share your thoughts in the comments.