Nice code. Your function names are very clear, and it's great to see the unit tests included with the code.
Some tests I'm surprised not to see:
- see the trivial test, with no passengers waiting. That's the first test I would have written. Writing this test first helps get a good testable interface that can then be used to write the next-simplest test get that passing.
- tests of capacity other than 5. Do we know that other capacities work?
- tests with up passengers waiting behind down passengers, and vice versa.
Here's a couple of extra tests:
// nothing to do
queues = { {} };
result = {0};
assert(the_lift(queues, 1) == result);
// lift full up and down, but don't block passengers
queues = { {}, {3,3,3,0,0,0,0,0,3}, {}, {1,1,1}, };
result = {0, 1, 3, 1, 0, 1, 3, 1, 0, 1, 0};
assert(the_lift(queues, 2) == result);
And some that expose fragility in the code:
// no floors (seg fault)
queues = { };
result = {0};
assert(the_lift(queues, 1) == result);
// no capacity (infinite loop)
queues = { {1}, {} };
result = {0};
assert(the_lift(queues, 0) == result);
// passenger not changing floor (infinite loop)
queues = { {0} };
result = {0};
assert(the_lift(queues, 1) == result);
One thing I would change about the tests is that they currently abort (using assert()) at the first failure. When writing or refactoring code, it's likely to cause multiple tests to fail, and that's useful information to identify the cause. I'd like to see all failures reported to std::cerr and the return value indicate whether all tests succeeded. That's what the usual test frameworks manage, and it's not hard to do.
I get a few compiler warnings that could easily be fixed:
g++ -std=c++2a -fconcepts -fPIC -g -Wall -Wextra -Wwrite-strings -Wno-parentheses -Wpedantic -Warray-bounds -Weffc++ 254000.cpp -o 254000
254000.cpp: In function ‘std::optional<int> highestFloorAboveLiftPushedDown(int, const Queues&)’:
254000.cpp:43:17: warning: comparison of integer expressions of different signedness: ‘const int’ and ‘std::size_t’ {aka ‘long unsigned int’} [-Wsign-compare]
if(person < i) { // person wants to go down
~~~~~~~^~~
254000.cpp: In function ‘std::optional<int> nextFloorAboveLiftPushedUp(int, const Queues&)’:
254000.cpp:59:17: warning: comparison of integer expressions of different signedness: ‘const int’ and ‘std::size_t’ {aka ‘long unsigned int’} [-Wsign-compare]
if(person > i) {
~~~~~~~^~~
254000.cpp: In function ‘std::optional<int> nextFloorUnderLiftPushedDown(int, const Queues&)’:
254000.cpp:75:17: warning: comparison of integer expressions of different signedness: ‘const int’ and ‘std::size_t’ {aka ‘long unsigned int’} [-Wsign-compare]
if(person < i) {
~~~~~~~^~~
254000.cpp: In function ‘std::optional<int> lowestFloorUnderLiftPushedUp(int, const Queues&)’:
254000.cpp:90:17: warning: comparison of integer expressions of different signedness: ‘const int’ and ‘std::size_t’ {aka ‘long unsigned int’} [-Wsign-compare]
if(person > i) { // person wants to go up
~~~~~~~^~~
254000.cpp: In constructor ‘Lift::Lift(const Queues&, int)’:
254000.cpp:172:10: warning: ‘Lift::mQueues’ will be initialized after [-Wreorder]
Queues mQueues;
^~~~~~~
254000.cpp:170:7: warning: ‘int Lift::mCapacity’ [-Wreorder]
int mCapacity;
^~~~~~~~~
254000.cpp:175:1: warning: when initialized here [-Wreorder]
Lift::Lift(const Queues& queues, int capacity)
^~~~
254000.cpp: In member function ‘void Lift::addPeopleWhoWantToGoUp(std::vector<int>&)’:
254000.cpp:240:50: warning: comparison of integer expressions of different signedness: ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} and ‘int’ [-Wsign-compare]
if(newPassengers.size() + mPassangers.size() >= mCapacity) {
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
254000.cpp: In member function ‘void Lift::addPeopleWhoWantToGoDown(std::vector<int>&)’:
254000.cpp:326:50: warning: comparison of integer expressions of different signedness: ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} and ‘int’ [-Wsign-compare]
if(newPassengers.size() + mPassangers.size() >= mCapacity) {
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
I think we should use an unsigned type for the floor number throughout (probably std::size_t; it might be worth writing a type alias, using Floor = std::size_t;).
There's quite a bit of duplication between "up" and "down" functions that could be reduced. For example,
int Lift::getNextFloorUpWithPerson() const
{
auto itPosPassengerUp = std::find_if(mPassangers.cbegin(), mPassangers.cend(),
[curr = mCurrentFloor](const auto& val)
{
return val > curr;
}
);
// there should be always a person who wants to get higher
assert(itPosPassengerUp != mPassangers.cend());
auto optPosUp = nextFloorAboveLiftPushedUp(
mCurrentFloor, mQueues);
if(optPosUp && *optPosUp < *itPosPassengerUp) {
return *optPosUp;
}
return *itPosPassengerUp;
}
int Lift::getNextFloorDownWithPerson() const
{
auto itPosPassengerDown = std::find_if(mPassangers.crbegin(), mPassangers.crend(),
[curr = mCurrentFloor](const auto& val)
{
return val < curr;
}
);
// there should be always a person who wants to get down
assert(itPosPassengerDown != mPassangers.crend());
auto optPosDown = nextFloorUnderLiftPushedDown(
mCurrentFloor, mQueues);
if(optPosDown && *optPosDown > *itPosPassengerDown) {
return *optPosDown;
}
return *itPosPassengerDown;
}
These could be combined with a small helper function, especially if we change Direction to be integer-based and define up as 1 and down as -1:
enum Direction{
up = 1,
down = -1,
};
template<typename Iter>
int Lift::getNextFloorWithPerson(Iter first, Iter last) const
{
auto const next_passenger_iter =
std::find_if(first, last,
[this](const auto& val) { return val * mDirection > mCurrentFloor * mDirection; });
// there should be always a person who wants to get higher
assert(next_passenger_iter != last);
for (int i = mCurrentFloor + mDirection; i != *next_passenger_iter; i += mDirection) {
// is there a person waiting between, going our direction?
if (std::any_of(mQueues[i].cbegin(), mQueues[i].cend(),
[i,this](auto const& person){ return person * mDirection > i * mDirection; })) {
return i;
}
}
return *next_passenger_iter;
}
And we can inline the uses in the one place each they are called:
void Lift::goUpWithPassengers()
{
auto higherFloor = getNextFloorWithPerson(mPassangers.cbegin(), mPassangers.cend());
arriveToFloor(higherFloor);
}
void Lift::goDownWithPassengers()
{
auto lowerFloor = getNextFloorWithPerson(mPassangers.crbegin(), mPassangers.crend());
arriveToFloor(lowerFloor);
}
There might be value in splitting the queues at each floor into two: one for upward passengers, and one for downward passengers.
Trivial: spelling mPassangers → mPassengers.