#ifndef GRAPH_ATTRIBUTES_H
#define GRAPH_ATTRIBUTES_H

#include <numeric>
#include "graph.hpp"

namespace ED
{
   struct GraphAttributes
   {
      explicit GraphAttributes(NodeId num_nodes);

      [[nodiscard]] NodeId num_nodes() const;

      [[nodiscard]] bool is_outer(NodeId id) const;

      [[nodiscard]] bool is_inner(NodeId id) const;

      [[nodiscard]] bool is_out_of_forest(NodeId id) const;

      void reset_forest();

      NodeId rho(NodeId id);

      void reset_matching();

      std::vector<NodeId> phi;
      std::vector<NodeId> rho_;
      std::vector<NodeId> mu;
      std::vector<bool> scanned;
   };

   inline
   GraphAttributes::GraphAttributes(const ED::NodeId num_nodes):
      phi(num_nodes),
      rho_(num_nodes),
      mu(num_nodes),
      scanned(num_nodes)
   {

   }

   inline
   NodeId GraphAttributes::num_nodes() const
   {
      assert(phi.size() == rho_.size());
      assert(phi.size() == mu.size());
      assert(phi.size() == scanned.size());
      return phi.size();
   }

   inline
   bool GraphAttributes::is_outer(NodeId const id) const {
      return mu[id] == id or phi[mu[id]] != mu[id];
   }

   inline
   bool GraphAttributes::is_inner(NodeId const id) const
   {
      return phi[id] != id and phi[mu[id]] == mu[id];
   }

   inline
   bool GraphAttributes::is_out_of_forest(const ED::NodeId id) const
   {
      return mu[id] != id and phi[id] == id and phi[mu[id]] == mu[id];
   }

   inline
   void GraphAttributes::reset_forest()
   {
      std::iota(phi.begin(), phi.end(), 0);
      std::iota(rho_.begin(), rho_.end(), 0);
      std::fill(scanned.begin(), scanned.end(), false);
   }

   inline
   NodeId GraphAttributes::rho(NodeId id)
   {
      while(rho_[id] != id)
      {
         rho_[id] = rho_[rho_[id]];
         id = rho_[id];
      }
      return id;
   }

   inline
   void GraphAttributes::reset_matching()
   {
      std::iota(mu.begin(), mu.end(), 0);
   }
}
#endif //GRAPH_ATTRIBUTES_H