aocpp/dlx/include/dlx.hpp

#ifndef DLX_DLX_HPP_
#define DLX_DLX_HPP_

#include <cstddef>
#include <functional>
#include <vector>
#include <utility>

namespace dlx {

struct Cell;

class Dlx final {
  std::vector<Cell*> ctab_;
  std::vector<Cell*> rtab_;
  Cell* root_;

  auto AddCol() -> void;
  auto AddRow() -> void;
  auto AllocCol(std::size_t n) -> void;
  auto AllocRow(std::size_t n) -> void;

public:
  Dlx();
  ~Dlx();

  Dlx(Dlx const&) = delete;
  auto operator=(Dlx const&) -> Dlx& = delete;

  Dlx(Dlx &&);
  auto operator=(Dlx &&) -> Dlx&;

  // Returns number of rows.
  auto Rows() const -> std::size_t;

  // Returns number of columns.
  auto Cols() const -> std::size_t;

  // Places a 1 in the given row and column.
  // Increases the number of rows and columns if necessary.
  auto Set(std::size_t row, std::size_t col) -> void;

  // Marks a column as optional: a solution need not cover the given column,
  // but it still must respect the constraints it entails.
  auto MarkOptional(std::size_t col) -> void;

  // Removes a row from consideration.
  // Should only be called after all dlx_set() calls.
  auto RemoveRow(std::size_t row) -> void;

  // Picks a row to be part of the solution.
  // Should only be called after all Set() calls and RemoveRows() calls.
  // TODO: Check the row can be legally chosen.
  auto PickRow(std::size_t row) -> void;

  auto Solve(
    std::function<bool(std::size_t, std::size_t, std::size_t)> try_cb,
    std::function<bool()> undo_cb,
    std::function<bool()> found_cb,
    std::function<bool(std::size_t)> stuck_cb) -> void;
};

auto ForallCover(Dlx& dlx, auto cb) {
  std::vector<std::size_t> sol;
  dlx.Solve(
    [&](std::size_t c, std::size_t s, std::size_t r) { sol.push_back(r); return false; },
    [&](){ sol.pop_back(); return false; },
    [&](){ return cb(std::as_const(sol)); },
    [](std::size_t){ return false; }
  );
}

} // namespace

#endif