#ifndef BA_GRAPH_SNARK_MROZEK_HPP
#define BA_GRAPH_SNARK_MROZEK_HPP

#include <set>
#include <stdexcept>
#include <vector>

#include <snarks/colouring_pd.hpp>

#include <algorithms/path_decomposition/shortest_path_heuristic.hpp>
#include <invariants/connectivity.hpp>
#include <io/print_nice.hpp>
#include <util/math.hpp>

#include <mrozek.hpp>

namespace ba_graph {
// takes: first graph's terminalIds and ColouringBitArray, second's
// ColouringBitArray returns pair: bool => if they can be joined into a snark
// vector<int> => terminalIds of first graph in order in which it is possible to
// create a snark, or original order if impossible
std::pair<std::vector<int>, bool>
canCreateSnark(std::vector<int> &terminalIdsFirst, ColouringBitArray &first,
               ColouringBitArray &second) {
  // treba spravit permutaciu jedneho cba
  // ak je medzi permutaciami taky, ktory nema ziadny spolocny kladny bit
  // tak ich vieme spojit do snarku
  if (first.size() != second.size()) {
    throw std::runtime_error("ColouringBitArrays are not same size");
  }
  if (first.all_false() || second.all_false()) {
    return std::pair(terminalIdsFirst, true);
  }
  auto perm = internal::permutations(terminalIdsFirst, first);

  auto secondMin = internal::minimalColouringBitArray(second);
  for (int j = 0; j < perm.second.size(); j++) {
    auto cba = internal::minimalColouringBitArray(perm.second[j]);
    bool res = true;
    for (ColouringBitArray::Index i(0, 0); i < cba.size(); i++) {
      if (cba[i] && secondMin[i]) {
        res = false;
        break;
      }
    }
    if (res) {
      return std::pair(perm.first[j], true);
    }
  }
  return std::pair(terminalIdsFirst, false);
}

// takes 2 graphs
// returns pair: bool => if they can be joined into a snark
// vector<int> => terminalIds of first graph in order in which it is possible to
// create a snark, or original order if impossible
std::pair<std::vector<int>, bool> canCreateSnark(Graph &first, Graph &second) {
  // get cba for both multipoles and terminal ids for first
  auto cbaFirst = getAllColourings(first);
  auto cbaSecond = getAllColourings(second);

  auto terminals = internal::getTerminals(first);
  std::vector<int> terminalIds;
  for (auto &v : terminals) {
    terminalIds.push_back(v.to_int());
  }

  return canCreateSnark(terminalIds, cbaFirst, cbaSecond);
}

} // namespace ba_graph

#endif