shoeshop.cpp

#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <map>
#include <random>
#include <sstream>
#include <vector>

/* Holds data from the command line arguments */
struct Args {
  double lambda;
  double mu_1;
  double mu_2;
  double max_time;
};

Args parse_args(int argc, char *argv[]) {
  auto usage = [&]() {
    std::cerr << "Usage: " << argv[0] << " <λ> <μ1> <μ2> <max_time>" << std::endl;
    exit(EXIT_FAILURE);
  };

  if (argc < 5) {
    usage();
  }

  auto parse_arg = [&](int n) {
    char *endp = NULL;
    double ret = strtod(argv[n], &endp);
    if (endp == argv[n] || *endp != '\0') {
      usage();
    }
    return ret;
  };

  Args args;
  args.lambda = parse_arg(1);
  args.mu_1 = parse_arg(2);
  args.mu_2 = parse_arg(3);
  args.max_time = parse_arg(4);

  return args;
}

enum class EventKind {
  Arrival,
  FirstFinished,
  SecondFinished,
};

template <typename CharT>
std::basic_ostream<CharT> &operator<<(std::basic_ostream<CharT> &out, EventKind k) {
  out << "Event::";
  if (k == EventKind::Arrival) {
    out << "Arrival";
  } else if (k == EventKind::FirstFinished) {
    out << "FirstFinished";
  } else if (k == EventKind::SecondFinished) {
    out << "SecondFinished";
  }
  return out;
}

/* Obviously, in Rust this could be a plain `enum` */
using Event = std::pair<double, EventKind>;

class EventQueue {
public:
  /* Creates an event queue and pre-populates it with customer arrivals. */
  EventQueue(Args &args, std::mt19937_64 &rng) : events() {
    // insert the initial arrivals
    std::exponential_distribution<double> distr(args.lambda);
    double t = 0.0;
    while (t < args.max_time) {
      t += distr(rng);
      events.emplace_back(t, EventKind::Arrival);
      std::push_heap(events.begin(), events.end(), min_cmp);
    }
  }

  /* Pops an event off the queue and returns it. */
  Event get() {
    // The queue should always have at least one arrival in it when this function is called.
    if (events.empty()) {
      throw std::logic_error("No more events in queue");
    }
    std::pop_heap(events.begin(), events.end(), min_cmp);
    Event ret = events.back();
    events.pop_back();
    return ret;
  }

  /* Inserts an event into the queue. */
  void put(Event e) {
    events.push_back(e);
    std::push_heap(events.begin(), events.end(), min_cmp);
  }

private:
  std::vector<Event> events;
  static bool min_cmp(Event &a, Event &b) { return a.first > b.first; }
};

/* The state register. */
enum class State {
  Empty,
  FirstBusy,
  SecondBusy,
  BothBusy,
  FirstWaiting,
};

template <typename CharT>
std::basic_ostream<CharT> &operator<<(std::basic_ostream<CharT> &out, State s) {
  out << "State::";
  if (s == State::Empty) {
    out << "Empty";
  } else if (s == State::FirstBusy) {
    out << "FirstBusy";
  } else if (s == State::SecondBusy) {
    out << "SecondBusy";
  } else if (s == State::BothBusy) {
    out << "BothBusy";
  } else if (s == State::FirstWaiting) {
    out << "FirstWaiting";
  }
  return out;
}

/* Holds data about a Shop. */
struct Statistics {
  std::map<State, unsigned long> state_counts;
  unsigned long dropped_clients = 0;
  unsigned long arrived_clients = 0;
};

template <typename CharT>
static std::basic_ostream<CharT> &operator<<(std::basic_ostream<CharT> &out, Statistics s) {
  // amenable to some templating / macroing but I got bored and only did one statistic
  out << "entries in states: " << std::endl;
  auto total = std::accumulate(s.state_counts.begin(), s.state_counts.end(), 0.0,
                               [](double a, auto b) { return a + b.second; });
  for (auto &[state, count] : s.state_counts) {
    out << "  " << state << ": " << (count / total) << std::endl;
  }
  std::cout << "dropout: " << s.dropped_clients * 1.0 / s.arrived_clients << std::endl;
  return out;
}

/* The actual state machine. */
class Shop {
public:
  Statistics stats;

  Shop(Args &args, std::mt19937_64 &&gen)
      : state(State::Empty), rng(gen), distr_m1(args.mu_1), distr_m2(args.mu_2) {}

  /* Processes the incoming event, advances the state, and updates all statistics. Returns the next
   * event to be inserted into the queue, if any. */
  std::optional<Event> next(Event event) {
    if (event.second == EventKind::Arrival) {
      ++stats.arrived_clients;
    }
    auto new_event = output(event);
    if (dropping(event)) {
      ++stats.dropped_clients;
    }
    state = next_state(event);
    ++stats.state_counts[state];
    return new_event;
  }

private:
  State state;
  // Honestly this might be a bad idea in real C++ code. I want them mutable because I want
  // next_state and output to be const methods, but event has to call the RNG which means it has to
  // be mutable. In Rust `rng` would be a `Mutex` or `RefCell`.
  mutable std::mt19937_64 rng;
  mutable std::exponential_distribution<double> distr_m1, distr_m2;

  /* Computes the next state. Does not mutate this. */
  State next_state(const Event &event) const {
    /* The following would be much cleaner in Rust, like:
     *     use EventKind as E;
     *     use State as S;
     *     Ok(match (event.second, state) {
     *         (E::Arrival,        S::Empty       ) => S::FirstBusy,
     *         (E::Arrival,        S::SecondBusy  ) => S::BothBusy,
     *         (E::Arrival,        _              ) => state,
     *         (E::FirstFinished,  S::FirstBusy   ) => S::SecondBusy,
     *         (E::FirstFinished,  S::BothBusy    ) => S::FirstWaiting,
     *         (E::SecondFinished, S::SecondBusy  ) => S::Empty,
     *         (E::SecondFinished, S::BothBusy    ) => S::FirstBusy,
     *         (E::SecondFinished, S::FirstWaiting) => S::SecondBusy,
     *         (e, s) => return Err(format!("Invalid {:?} in {:?}", e, s)),
     *     })
     * It's formatted like a state table, but if you want it to look like a transition table, it's
     * pretty easy to macroize (you'll probably want the macro to expand into a nested `match`
     * rather than a single `match` on a tuple, though).
     */
    if (event.second == EventKind::Arrival) {
      // arrivals may happen in any state
      if (state == State::Empty) {
        return State::FirstBusy;
      } else if (state == State::SecondBusy) {
        return State::BothBusy;
      } else {
        return state;
      }
    } else if (event.second == EventKind::FirstFinished) {
      // first may finish only in FirstBusy or BothBusy
      if (state == State::FirstBusy) {
        return State::SecondBusy;
      } else if (state == State::BothBusy) {
        return State::FirstWaiting;
      }
    } else if (event.second == EventKind::SecondFinished) {
      // second may finish only in SecondBusy, BothBusy or FirstWaiting
      if (state == State::SecondBusy) {
        return State::Empty;
      } else if (state == State::BothBusy) {
        return State::FirstBusy;
      } else if (state == State::FirstWaiting) {
        return State::SecondBusy;
      }
    }
    std::stringstream errmsg;
    errmsg << "Invalid " << event.second << " in " << state;
    throw std::logic_error(errmsg.str());
  }

  /* Computes the output, which is an optional Event. (This is a Mealy-type output because the
   * method takes an input other than the current state.)
   */
  std::optional<Event> output(const Event &event) const {
    // In Rust, this could be cleaned up with a match, much like in next_state
    if (event.second == EventKind::Arrival &&
        (state == State::Empty || state == State::SecondBusy)) {
      return std::make_optional<Event>(event.first + distr_m1(rng), EventKind::FirstFinished);
    } else if ((state == State::FirstBusy && event.second == EventKind::FirstFinished) ||
               (state == State::FirstWaiting && event.second == EventKind::SecondFinished)) {
      return std::make_optional<Event>(event.first + distr_m2(rng), EventKind::SecondFinished);
    }
    return std::nullopt;
  }

  /* Another Mealy-type output. In general you can do multiple outputs one of two ways. Either you
   * have one big function that computes all your outputs, which can cut down on the amount of
   * repetitive branching (e.g., this function could be an `else` inside `output` above) or you
   * calculate each separate output in a different function as I'm doing here, which helps with
   * separation of concerns. Many small functions are easier to read than one big function, and I
   * consider it the compiler's job to merge separate concerns, so I did it this way.
   *
   * I also come from a hardware (Verilog/VHDL) background and in a hardware state machine each
   * output would be calculated concurrently, which is more explicit with separate processes, even
   * if the synthesizer munges it all into one big cloud of logic. So maybe my background informs
   * this decision. */
  bool dropping(const Event &event) const {
    return (
        event.second == EventKind::Arrival &&
        (state == State::FirstBusy || state == State::SecondBusy || state == State::FirstWaiting));
  }
};

int main(int argc, char *argv[]) {
  auto args = parse_args(argc, argv);

  std::mt19937_64 rng(std::random_device{}());

  EventQueue event_q(args, rng);
  Shop shop(args, std::move(rng));
  while (true) {
    auto event = event_q.get();
    if (event.first > args.max_time) {
      break;
    }
    auto new_event = shop.next(event);
    if (new_event) {
      event_q.put(*new_event);
    }
  }
  std::cout << shop.stats;
}