# Redirecting arriving customers to the nearest empty queue

I have a task to make a checkout line controller. First it receives, as input, an amount of checkouts and commands. Then commands that are C for coming and L for leaving, and after those the number of the checkout they are coming/leaving. Also, if there is someone at the checkout, they should be sent to the nearest empty one. If 2 are equally near, the one with the lowest number is chosen.

Input could be:

3 5
C 1
C 2
L 1
C 1
C 1


As output it just tells the checkout where each arriving customer is served. So output would be:

1
2
1
3


Code:

#include <iostream>
#include <vector>
using namespace std;

int main () {
int n, m, checkout;
char action;
vector <int> output (0);

cin >> n >> m;

vector <bool> state (n,false); //

for (int i = 0; i < m; i++) {
cin >> action >> checkout;
checkout--; //Aligns checkout number with vectors number

if (action == 'C') { //If someone comes
if (state[checkout] == false) { //If the checkout he comes to is empty
state[checkout] = true; // If it is, it's not anymore
output.push_back(checkout + 1);
} else { // If it isn't, check which is the closest empty one
for (int i = 1; i < n; i++) { //Loops through below and above checkouts
if (checkout - i >= 0) {
if (state[checkout - i] == false) {
state[checkout - i] = true;
output.push_back(checkout - i + 1);
break;
}
}
if (checkout + i < n) {
if (state[checkout + i] == false) {
state[checkout + i] = true;
output.push_back(checkout + i + 1);
break;
}
}
}
}
}
if (action == 'L') {
state[checkout] = false;
}
}
for ( int j = 0; j < output.size(); j++) {
cout << output[j] << endl; //Outputs after all input is over (somone said I should do this)
}
}


My program runs too slowly. I use codejudge.net to check if it is working properly. I have already improved it a lot, from what I started with, but it still doesn't cut it.

This question was originally posted on Stack Overflow.

• Please never write if(boolean == true) but just write if(boolean). This is an equasion to much. – chillworld Feb 21 '16 at 7:32
• @chillworld Please write that as an answer. – 200_success Feb 21 '16 at 15:25

## Don't abuse using namespace std

Putting using namespace std within your program is generally a bad habit that you'd do well to avoid.

## Check for errors

It may not be part of your assignment, but you should know that real programs should check for errors and handle them appropriately.

## Use a function

Right now, everything is in main but we could make things a little more clear by creating a function. Specifically, as each customer arrives at a register, they need to find the nearest open register. This suggests a function: findNearestOpenRegister which could take a proposed register as an argument. However, this function would have to get a number of other things passed to it which suggests a further refinement, described in the next suggestion.

## Use an object

We can make the main code cleaner by using an object to represent the array of cashiers at a store. I'd probably write it like this:

// represents a linear array of checkout registers at a store
class Checkout {
public:
Checkout(int registerCount)
: unoccupied(registerCount, true)
{}
int arrive(int r) {
int lo, hi;
for (lo = hi = r; lo >= 0 || hi < unoccupied.size(); --lo, ++hi) {
if (lo >= 0 && unoccupied[lo]) {
unoccupied[lo] = false;
return lo;
} else if (hi < unoccupied.size() && unoccupied[hi]) {
unoccupied[hi] = false;
return hi;
}
}
return ERROR;   // this is an error condition!
}
int leave(int r) {
if (unoccupied[r])
return ERROR;
unoccupied[r] = true;
return r;
}
static constexpr int ERROR = -1;
private:
std::vector <bool> unoccupied;
};


Now the main function can use the object:

int main () {
int n;
int m;

std::cin >> n >> m;
Checkout reg(n);

for (int i = 0; i < m; ++i) {
int checkout;
char action;
std::cin >> action >> checkout;
--checkout; // checkout is 1-based in input, zero-based internally
switch(action) {
case 'C':  // someone comes to the register
checkout = reg.arrive(checkout);
if (checkout == Checkout::ERROR) {
std::cout << "Error: no free registers in line " << i+2 << ".\n";
return 1;
}
std::cout << ++checkout << '\n';
break;
case 'L':  // someone leaves the register
checkout = reg.leave(checkout);
if (checkout == Checkout::ERROR) {
std::cout << "Error: attempt to leave free register in line " << i+2 << ".\n";
return 1;
}
break;
default:
std::cout << "Error: unknown action '" << action << "' in line " << i+2 << ".\n";
return 1;
}
}
}


Note that error checking has been added, as per the earlier suggestion. Also note that rather than storing the output, this version simply emits it as it's generated, avoiding the additional data structure that is otherwise needed.

## Profile the program

If you find that the program is not performing as fast as you need, the first step should be to try to find out where the program is spending its time. This can be done by several different methods. I tend to use gprof. Among the possibilities are using a different data structure. See this question for an example. Another possibility is to execute std::ios_base::sync_with_stdio(false);, but whether that speeds thing up or not is uncertain until you measure.

• Ehm, okay. I am not very good at coding yet. There are numerous thing here I don't understand. In the object, what are you doing in line 4, 5 and 6? What does constexpr mean? – Rasmus Tollund Feb 21 '16 at 20:18
• No worries; we're all here to improve our coding skills. For constexpr see the link. Lines 4-6 are a constructor. – Edward Feb 21 '16 at 20:43
• Why did you change from "occupied" to "unoccupied"? – Deduplicator Feb 22 '16 at 0:13
• Because each time unoccupied is checked, it would have had to be negated if it were occupied. – Edward Feb 22 '16 at 0:15