#include 

#include 
#include 

#include "cycles.hpp"

namespace cycles_util {

NodeState::NodeState(std::size_t number_of_nodes) {
  visited.resize(number_of_nodes, false);
  parent.resize(number_of_nodes, std::nullopt);
  depth.resize(number_of_nodes, 0);
}

void NodeState::SetVisited(std::uint64_t node_id) { visited[node_id] = true; }

bool NodeState::IsVisited(std::uint64_t node_id) const { return visited[node_id]; }

void NodeState::SetParent(std::uint64_t parent_id, std::uint64_t node_id) { parent[parent_id] = node_id; }

std::optional NodeState::GetParent(std::uint64_t node_id) const { return parent[node_id]; }

void NodeState::SetDepth(std::uint64_t node_id, std::uint64_t node_depth) { depth[node_id] = node_depth; }

std::uint64_t NodeState::GetDepth(std::uint64_t node_id) const { return depth[node_id]; }

void FindNonSpanningTreeEdges(std::uint64_t node_id, const mg_graph::GraphView &graph, NodeState *state,
                              std::set *non_st_edges) {
  std::unordered_set unique_neighbour;
  state->SetVisited(node_id);
  for (const auto &neigh : graph.Neighbours(node_id)) {
    auto next_id = neigh.node_id;

    // Check if is returning edge or already visited neighbour
    if (const auto parent = state->GetParent(node_id);
        parent && (next_id == *parent || unique_neighbour.find(next_id) != unique_neighbour.end())) {
      continue;
    }

    unique_neighbour.insert(next_id);

    if (state->IsVisited(next_id)) {
      auto sorted_edge = std::minmax(node_id, next_id);
      non_st_edges->insert(sorted_edge);
      continue;
    }

    // Set depth and parent for the next ST iteration
    state->SetParent(next_id, node_id);
    state->SetDepth(next_id, state->GetDepth(node_id) + 1);
    FindNonSpanningTreeEdges(next_id, graph, state, non_st_edges);
  }
}

void FindFundamentalCycles(const std::set &non_st_edges,
                           const NodeState &state, std::vector *fundamental_cycles) {
  for (const auto &[from, to] : non_st_edges) {
    fundamental_cycles->emplace_back(FindFundamentalCycle(from, to, state));
  }
}

std::vector FindFundamentalCycle(std::uint64_t node_a, std::uint64_t node_b, const NodeState &state) {
  std::vector cycle;
  if (state.depth[node_a] < state.depth[node_b]) {
    std::swap(node_a, node_b);
  }

  // climb until a and b reach the same depth:
  //
  //       ()               ()
  //      /  \             /  \.
  //    ()   (b)   -->   (a)  (b)
  //   /  \             /   \.
  // (a)  ()           ()   ()
  cycle.emplace_back(node_a);
  while (state.depth[node_a] > state.depth[node_b]) {
    const auto maybe_parent = state.GetParent(node_a);
    if (!maybe_parent) {
      throw mg_exception::InvalidIDException();
    }
    node_a = *maybe_parent;
    cycle.emplace_back(node_a);
  }

  if (node_a != node_b) {
    throw std::runtime_error("There should be no cross edges in DFS tree of an undirected graph.");
  }

  // Close the cycle
  cycle.emplace_back(cycle[0]);
  return cycle;
}

void CombineCycles(std::uint32_t mask, const std::vector &fundamental_cycles,
                   const mg_graph::GraphView &graph, std::vector *cycles) {
  std::map edge_cnt;
  for (std::size_t i = 0; i < fundamental_cycles.size(); ++i) {
    if ((mask & (1  2) {
    cycles->emplace_back(cycle);
  }
}

void GetCyclesFromFundamentals(const std::vector &fundamental_cycles,
                               const mg_graph::GraphView &graph, std::vector *cycles) {
  std::uint32_t size = 1  1 || from == to) {
      cycles.push_back({{from}, {to}});
    }
  }

  return cycles;
}

}  // namespace cycles_alg