Playing with elevator scheduling.

elevator.py

class ElevatorRequest(object):
    def __init__(self, from_floor, to_floor):
        self.from_floor = from_floor
        self.to_floor = to_floor

    def __cmp__(self, other):
        return self.from_floor == other.from_floor

    def __str__(self):
        return "<ElevatorRequest: From %d to %d>" % (self.from_floor, self.to_floor)

class ElevatorCar(object):
    UP, DOWN = 1, -1

    def __init__(self, capacity):
        self.direction = self.UP
        self.target_floor = 0
        self.current_floor = 0

        self.passengers = []
        self.capacity = capacity
        self.request_queue = []

    def post_request(self, request):
        self.request_queue.insert(0, request)

    def board(self, passenger):
        self.request_queue.remove(passenger)
        self.passengers.append(passenger)
        return passenger.from_floor

    def get_next_floor(self):
        passenger_count = len(self.passengers)
        if passenger_count < self.capacity and len(self.request_queue):
            if passenger_count == 0:
                # Empty car, service first request.
                # return self.request_queue[-1].from_floor
                return self.board(self.request_queue[-1])
            # Find next passenger in the current direction we're heading.
            # They must:
            #  - be waiting on a floor along our current direction
            #  - be going to a floor along our current direction relative to the from floor.

            #  EX:
            # Given an elevator on floor 3, going UP:
            #   a passenger on floor 2 will NOT be picked up. 
            #   a passenger on floor 5 going to floor 4 will NOT be picked up.
            #   a passenger on floor 4 going to floor 5 WILL be picked up.
            if self.direction == self.UP:
                requests_on_route = [p for p in self.request_queue if p.from_floor > self.current_floor]
                valid_requests = [p for p in requests_on_route if p.to_floor > p.from_floor]
                if len(valid_requests):
                    next = min([p for p in valid_requests])
                    return self.board(next)
            else:
                requests_on_route = [p for p in self.request_queue if p.from_floor < self.current_floor]
                valid_requests = [p.from_floor for p in requests_on_route if p.to_floor < p.from_floor] 
                if len(valid_requests):
                    next = max([p for p in valid_requests])
                    return self.board(next)
        if passenger_count > 0:
            # Not picking up passengers
            # Target the closest requested floor.
            if self.direction == self.UP:
                return min(self.passengers).to_floor
            else:
                return max(self.passengers).to_floor
        return 0  # Done, go to lobby

    def tick(self):
        next_floor = self.get_next_floor()
        if next_floor > self.current_floor:
            self.direction = self.UP
        elif next_floor < self.current_floor:
            self.direction = self.DOWN
        else:
            pass  # No change to direction when stopped.
        self.target_floor = next_floor

        # Unload passengers for this floor.
        self.passengers = [p for p in self.passengers if p.to_floor != car.current_floor]

        if self.current_floor != self.target_floor:
            self.current_floor += self.direction


if __name__ == '__main__':
    car = ElevatorCar(5)
    car.post_request(ElevatorRequest(5, 10))
    car.post_request(ElevatorRequest(2, 7))
    car.post_request(ElevatorRequest(4, 0))
    car.post_request(ElevatorRequest(6, 2))
    car.post_request(ElevatorRequest(1, 12))
    car.post_request(ElevatorRequest(0, 9))
    car.post_request(ElevatorRequest(5, 1))

    while len(car.request_queue) or len(car.passengers):
        def dir_to_str(direction):
            if direction == ElevatorCar.UP :
                return "up"
            else:
                return "down"

        print "On floor: %d, targeting: %d, going %s." % (
            car.current_floor, car.target_floor, dir_to_str(car.direction))
        car.tick()
        print "%d passengers." % len(car.passengers)
        print "%d requests waiting." % len(car.request_queue)
        if len(car.passengers) == 0 and len(car.request_queue):
            for req in car.request_queue:
                print req