Elevator

Design an elevator bank for a building, with multiple elevators

Solution

1. 当电梯处于停止状态，距离分等于当前楼层和需求楼层的差
2. 当电梯处于上升状态，如果需求楼层高于当前楼层，则距离分等于当前楼层和需求楼层的差， 否则不考虑当前电梯
3. 当电梯处于下降状态，如果需求楼层低于当前楼层，则距离分等于当前楼层和需求楼层的差， 否则不考虑当前电梯
4. 算法开始时先随机选择一部电梯，当存在更好的电梯选择时，替代当前的候选电梯，这样确保至少会有一部电梯响应(在少数情况下这样做不一定是最优的，可以设想更好的算法解决这个问题)。

Code

``````// define some constants
enum ErrorCode {
NO_ERROR,
ERROR
};

enum SpotType {
COMPACT,
SUV,
RESERVED
};
#define NO_PARKING (-1)

class Spot {
public:
bool     available;
SpotType type;
};

class Vehicle {
private:
int     length;
int     width;
bool    parked;
Spot    *spot;
public:
// omit some setters / getters
// virtual function here because subclasses will have different behavior
virtual SpotType getRequiredSpotType() = 0;
// no need for virtual functions here because subclasses will have the same "behavior"
bool isParked();
void parkVehicle(Spot *s);  // park at spot S;
Spot *removeVehicle();      // move the vehicle away, return parked spot
};

//every type of vehicle has default value of length and width;
class Motor:public Vehicle{};
class Car:public Vehicle{};
class SUV:public Vehicle{};

class Level {
private:
vector<Spot> spots;
public:
// find an available spot for a vehicle
// return NULL if all spots are taken
Spot *findASpot(Vehicle *v);
};

class ParkingLot {
private:
vector<Level> levels;
static ParkingLot *pInstance;
unordered_map<Vehicle *, time_t> parkingInfo;

ParkingLot();
// Stop the compiler generating methods of copy the object
ParkingLot(const ParkingLot &copy);    // Not Implemented
ParkingLot& operator = (const ParkingLot & copy);    // Not Implemented

time_t getCurrentTime();
double calculateFee(Vehicle *v);

public:
static ParkingLot *getInstance();
// NOTE: vehicleEnter and leave is not thread safe!
ErrorCode vehicleEnter(Vehicle *v);
ErrorCode vehicleLeave(Vehicle *v, double *fee);
};

ErrorCode ParkingLot::vehicleEnter(Vehicle *v) {
Spot *spot = NULL;
for (int i = 0; i < levels.size();i++) {
spot = levels[i].findASpot(v);
if (spot)
break;
}
if (!spot) {
return ERROR;
}
v->parkVehicle(spot);
spot->available = false;
parkingInfo[v] = getCurrentTime();
return NO_ERROR;
}

ErrorCode ParkingLot::vehicleLeave(Vehicle *v, double *fee) {
*fee = 0;
if (!v->isParked()) {
return ERROR;
}
Spot *spot = v->removeVehicle();
spot->available = true;
*fee = calculateFee(v);
parkingInfo.erase(v);
return NO_ERROR;
}
``````

Design an elevator bank for a building, with multiple elevators

1. 当电梯处于停止状态，距离分等于当前楼层和需求楼层的差
2. 当电梯处于上升状态，如果需求楼层高于当前楼层，则距离分等于当前楼层和需求楼层的差， 否则不考虑当前电梯
3. 当电梯处于下降状态，如果需求楼层低于当前楼层，则距离分等于当前楼层和需求楼层的差， 否则不考虑当前电梯
4. 算法开始时先随机选择一部电梯，当存在更好的电梯选择时，替代当前的候选电梯，这样确保至少会有一部电梯响应(在少数情况下这样做不一定是最优的，可以设想更好的算法解决这个问题)。

``````// define some constants
dispatch_queue_t printingQueue;
enum ElevatorState {
UP,           // moving up
DOWN,    // moving down
STAND    // stay at a level, waiting for request
};

class Elevator {
private:
ElevatorState state;
int id;
int currentLevel;
int maxLevel;
int minLevel;
// floor requests from low level to high level
vector<int> requests;
// runLoop is called on this thread

// utility methods to lock and unlock
void mutexLock();
void mutexUnlock();

// check if need to stop on current floor
bool needStop();
// switch to STAND if no request pending.
// go DOWN if currently going UP, and no further higher level requests
// go UP if currently going DOWN, and no further lower level requests

// move one floor up/down. Open door if needed. Update state
void move();
// open door and close door, delete request from array
void openDoor();
// thread safe operation, main logic for elevator operation (move, open door)
void runLoop();

static void *elevatorProc(void *parameter);

public:
Elevator(int id, int minLevel, int maxLevel);
~Elevator();

// thread safe operation, start elevatorProc to activate elevator
void startOperation();
// thread safe operation, stop elevatorProc to deactivate elevator
void stopOperation();
// thread safe operation, get elevator state
ElevatorState getState();
// thread safe operation, get elevator floor
int getCurrentLevel();

#pragma -mark Test Methods
void printRequests() {
// caller should have the data lock
dispatch_async(printingQueue, ^{
cout << "Elevator " << id << " current requests: ";
for (int i = 0 ; i < requests.size(); i++) {
cout << requests[i] << ' ';
}
cout << endl;
});
}
};

#pragma -mark Private Methods

bool Elevator::needStop() {
for (int i = 0; i < requests.size(); i++) {
if (requests[i] == currentLevel) {
return true;
}
}
return false;
}

switch (state) {
case UP:
if (requests.size() == 0) {
state = STAND;
} else {
if (requests.back() < currentLevel) {
state = DOWN;
}
}
break;
case DOWN:
if (requests.size() == 0) {
state = STAND;
} else {
if (requests.front() > currentLevel) {
state = UP;
}
}
break;
default:
break;
}

}

void Elevator::move() {
switch (state) {
case UP:
if (needStop()) {
openDoor();
// flip state
} else {
dispatch_async(printingQueue, ^{
cout << "Elevator " << id << " move from " << currentLevel
<< " to " << currentLevel + 1 << endl;
});
currentLevel++;
}
break;

case DOWN:
if (needStop()) {
openDoor();
// flip state
} else {
dispatch_async(printingQueue, ^{
cout << "Elevator " << id << " move from " << currentLevel
<< " to " << currentLevel - 1 << endl;
});
currentLevel--;
}
break;
default:
break;
}
}

void Elevator::openDoor() {
dispatch_async(printingQueue, ^{
cout << "Elevator " << id << " arriving at " << currentLevel << endl;
“        cout << "Elevator " << id << " door open" << endl;
});
for (vector<int>::iterator it = requests.begin(); it != requests.end(); ) {
if (*it == currentLevel) {
it = requests.erase(it);
} else {
++it;
}
}
dispatch_async(printingQueue, ^{
cout << "Elevator " << id << " door close" << endl;
});
printRequests();
}

void Elevator::runLoop() {
mutexLock();
switch (state) {
case UP:
case DOWN:
move();
break;
default:
break;
}
mutexUnlock();
}

void *Elevator::elevatorProc(void *parameter) {
Elevator *elevator = (Elevator *)parameter;
while (1) {
elevator->runLoop();
usleep(4000000);
}
return NULL;
}

#pragma -mark Public Methods

Elevator::Elevator(int inID, int inMinLevel, int inMaxLevel) {
state = STAND;
id = inID;
maxLevel = inMaxLevel;
minLevel = inMinLevel;
currentLevel = inMinLevel;
}

Elevator::~Elevator() {
stopOperation();
}

void Elevator::mutexLock() {
}

void Elevator::mutexUnlock() {
}

void Elevator::startOperation() {
mutexLock();
mutexUnlock();
}

void Elevator::stopOperation() {
mutexLock();
}
mutexUnlock();
}

mutexLock();
if (newRequest > maxLevel || newRequest < minLevel) {
cerr << "Invalid request " << newRequest << endl;
return ERROR;
}
if (requests.size() == 0) {
requests.push_back(newRequest);
if (newRequest > currentLevel) {
dispatch_async(printingQueue, ^{
cout << "Elevator " << id << " moving up" << endl;
});
state = UP;
} else if (newRequest == currentLevel) {
state = STAND;
openDoor();
} else {
dispatch_async(printingQueue, ^{
cout << "Elevator " << id << " moving down" << endl;
});
state = DOWN;
}
goto Done;
}

for (vector<int>::iterator i = requests.begin(); i != requests.end(); i++) {
if (newRequest == *i) {
goto Done;
}
if(*i > newRequest) {
requests.insert(i, newRequest);
goto Done;
}
}
requests.push_back(newRequest);
Done:
printRequests();
mutexUnlock();
return NO_ERROR;
}

ElevatorState Elevator::getState() {
mutexLock();
ElevatorState currentState = state;
mutexUnlock();
return currentState;
}

int Elevator::getCurrentLevel() {
mutexLock();
int level = currentLevel;
mutexUnlock();
return level;
}

class ElevatorBank {
private:
int numberOfElevators;
vector<Elevator> elevators;
int calculateScore(int index, int level);
bool isBetterNewCandidate(int currentCandidateIndex, int newCandidateIndex, int level);
int selectAnElevator(int level);
“public:
ElevatorBank(int numberOfElevators, int minFloor, int maxFloor);
~ElevatorBank();
// index start from 0
ErrorCode startAnElevator(int index);
// index start from 0
ErrorCode stopAnElevator(int index);
ErrorCode setARequest(int level);
};

#pragma -mark Private Methods
int ElevatorBank::calculateScore(int index, int level) {
if (elevators[index].getState() == STAND) {
return abs(elevators[index].getCurrentLevel() - level);
}

if (elevators[index].getCurrentLevel() > level
&& elevators[index].getState() == DOWN) {
return elevators[index].getCurrentLevel() - level;
}

if (elevators[index].getCurrentLevel() < level
&& elevators[index].getState() == UP) {
return level - elevators[index].getCurrentLevel();
}
return INT_MAX;
}

bool ElevatorBank::isBetterNewCandidate(int currentCandidateIndex, int newCandidateIndex, int level) {
return calculateScore(currentCandidateIndex, level) > calculateScore(newCandidateIndex, level);
}

int ElevatorBank::selectAnElevator(int level) {
int selectedIndex = 0;
for (int i = 1; i < numberOfElevators; i++) {
if (isBetterNewCandidate(selectedIndex, i, level)) {
selectedIndex = i;
}
}
return selectedIndex;
}

#pragma -mark Public Methods

ElevatorBank::ElevatorBank(int inNumberOfElevators, int minFloor, int maxFloor) {
numberOfElevators = inNumberOfElevators;
for (int i = 0; i < inNumberOfElevators; i++) {
elevators.push_back(Elevator(i, minFloor, maxFloor));
}
}

ElevatorBank::~ElevatorBank() {
elevators.clear();
}

ErrorCode ElevatorBank::startAnElevator(int index) {
if (index > numberOfElevators || index < 0) {
cerr << "Index " << index << " invalid!" << endl;
return ERROR;
}
elevators[index].startOperation();
return NO_ERROR;
}

ErrorCode ElevatorBank::stopAnElevator(int index) {
if (index > numberOfElevators || index < 0) {
cerr << "Index " << index << " invalid!" << endl;
return ERROR;
}
elevators[index].stopOperation();
return NO_ERROR;
}

ErrorCode ElevatorBank::setARequest(int level) {
int index = selectAnElevator(level);
}

int main() {
printingQueue = dispatch_queue_create("elevatorBank.printingQueue", NULL);
ElevatorBank elevatorBank = ElevatorBank(2, 1, 10);
for (int i = 0; i < 2; i++) {
elevatorBank.startAnElevator(i);
}
int request;
while (cin >> request) {
elevatorBank.setARequest(request);
};
return 0;
}
``````