#ifndef __GROUP_CONNECTIVITY_H__
#define __GROUP_CONNECTIVITY_H__

#include <stdlib.h>
#include <stdint.h>
#include <vector>
#include "options.h"
#include "rings.h"
#include "fast-array.h"

typedef int EdgeId;
typedef int DirectedEdgeId;
typedef std::pair<DirectedEdgeId, DirectedEdgeId> TwoCut;
typedef std::vector<EdgeId> DoubleSubdivision;

struct AbstractTester {
  bool isConnected;
#if SAVE_MEMORY
  typedef std::vector<bool> ClassesType;
#else
  typedef std::vector<size_t> ClassesType;
#endif
  ClassesType classes;

  virtual void init(
    int edges,
    std::vector<EdgeId> spanningTree,
    std::vector<TwoCut> twoCuts,
    std::vector<DoubleSubdivision> dSub,
    std::vector< std::vector<DirectedEdgeId> > elementaryCycles
  ) =0;
  virtual std::vector<size_t> getClasses() =0;
  virtual bool run() =0;

  virtual ~AbstractTester() {}
};


template < typename Ring_ >
struct Tester : public AbstractTester {
  typedef Ring_ Ring;
  typedef typename Ring::T T;
  typedef ::Mapping<Ring> Mapping;

# include "twoCuts.h"

# if !USE_NEXT_FORB
  size_t numForb;
# endif
  size_t edges;

  std::vector<EdgeId> classEdges;
  std::vector< std::pair<EdgeId, Mapping> > nonClassEdges;
# if EXPLICIT_NORMAL_EDGES
  std::vector< EdgeId > normalEdges;
# endif
# if USE_TWO_CUTS
  std::vector< TwoCutInt > twoCuts;
# endif
# if USE_DOUBLE_SUBDIVISIONS
  std::vector< EdgeId > doubleSubdividedEdges;
# endif

  virtual void init(
    int edges_,
    std::vector<EdgeId> spanningTree,
    std::vector<TwoCut> twoCuts_,
    std::vector<DoubleSubdivision> dSub,
    std::vector< std::vector<DirectedEdgeId> > elementaryCycles
  ) {
    edges = edges_;
#   if !USE_NEXT_FORB
    numForb = 1;
    while (edges_-- > 0) numForb *= (Ring::size - 1);
#   endif

#   if EXPLICIT_NORMAL_EDGES
    std::vector<bool> edgeList(edges, 1);
#   endif

    for (const auto& elemCycle : elementaryCycles) {
      nonClassEdges.push_back(std::make_pair(elemCycle[0] - 1, Mapping(edges)));
      Mapping &map = nonClassEdges.back().second;

      for (auto edge : elemCycle) {
        bool neg = (edge < 0);
        edge = neg ? -edge : edge;
        edge -= 1;
        map.assign(edge, neg ? Ring::one : Ring::negate(Ring::one));
      }
    }

#   if USE_DOUBLE_SUBDIVISIONS
    if (Ring::size == 4) {
      for (const auto& i : dSub) {
        for (auto e : i) edgeList[e - 1] = false;
        classEdges.push_back(i[0] - 1);
        doubleSubdividedEdges.push_back(i[0] - 1);
      }
    }
#   endif

#   if USE_TWO_CUTS
    for (auto cut : twoCuts_) {
      if (cut.first < 0) {
        cut.first *= -1;
        cut.second *= -1;
      }

      TwoCutInt intCut;
      intCut.a = cut.first - 1;
      intCut.flip = (cut.second < 0);
      intCut.b = (intCut.flip ? - cut.second : cut.second) - 1;

      twoCuts.push_back(intCut);
      edgeList[intCut.a] = false;
      edgeList[intCut.b] = false;
    }
#   endif

#   if EXPLICIT_NORMAL_EDGES
    for (auto e : spanningTree)
      if (edgeList[e - 1]) classEdges.push_back(e - 1);

    for (size_t i = 0; i < edges; i++)
      if (edgeList[i]) normalEdges.push_back(i);
#   else
    for (auto e : spanningTree)
      classEdges.push_back(e - 1);
#   endif

    size_t num_classes = 1;
    edges_ = classEdges.size();
    while (edges_-- > 0) num_classes *= Ring::size;
#   if USE_TWO_CUTS
    for (const auto& cut : twoCuts) num_classes *= cut.num_classes;
#   endif
    ClassesType C(num_classes, 0);
    C.swap(classes);
  }


#if USE_NEXT_FORB
  bool nextForb(Mapping& forb) {
#   if EXPLICIT_NORMAL_EDGES
    for (auto i : normalEdges) {
#   else
    for (size_t i = 0; i < edges; i++) {
#   endif
      T v = forb[i] + 1;
      if (v >= Ring::size) {
        forb.assign(i, 1);
      } else {
        forb.assign(i, v);
        return true;
      }
    }

#   if USE_TWO_CUTS
    for (const auto& cut : twoCuts) {
      int val = cut.getValue(forb) + 1;
      if (val >= cut.max_value) {
        cut.encode(forb, 0);
      } else {
        cut.encode(forb, val);
        return true;
      }
    }
#   endif

    return false;
  }
#else // !USE_NEXT_FORB
  Mapping& unpack(size_t index, Mapping& ret) {
    size_t m = Ring::size - 1;

    for (size_t i = 0; i < edges; i++) {
      ret.assign(i, (index % m) + 1);
      index /= m;
    }

    return ret;
  }
#endif


  Mapping& canonize(Mapping& map) {
    for (const auto &i : nonClassEdges) {
#if OPTIMIZE_COMBINE
      if (map[i.first] != Ring::zero)
#endif
        map.combine(map[i.first], i.second);
    }

    return map;
  }

  size_t pack(const Mapping& map) {
    size_t index = 0;
    for (auto i : classEdges) {
      index *= Ring::size;
      index += map[i];
    }

#   if USE_TWO_CUTS
    for (const auto& c : twoCuts) {
      index *= c.num_classes;
      index += c.getClass(map);
    }
#   endif

    return index;
  }


  virtual std::vector<size_t> getClasses() {
#if SAVE_MEMORY
    std::vector<size_t> ret(classes.size());
    for (size_t i = 0; i < classes.size(); i++) ret[i] = classes[i];
    return ret;
#else
    return classes;
#endif
  }



  virtual bool run() {
#   if SAVE_MEMORY
#     define INC(a) a = true
#   else
#     define INC(a) a++
#   endif

    Mapping forb(edges);

#   if USE_NEXT_FORB
      for (size_t i = 0; i < edges; i++) forb.assign(i, 1);

#     if USE_TWO_CUTS
      for (const auto& cut : twoCuts) cut.encode(forb, 0);
#     endif
#     if USE_DOUBLE_SUBDIVISIONS
      for (const auto& e : doubleSubdividedEdges) forb.assign(e, 0);
#     endif

      do {
        Mapping copy(forb);
        INC(classes[pack(canonize(copy))]);
      } while (nextForb(forb));
#   else
      for (size_t i = 0; i < numForb; i++)
        INC(classes[pack(canonize(unpack(i, forb)))]);
#   endif

    for (const auto &c : classes) if (!c) return (isConnected = false);

    return (isConnected = true);
#   undef INC
  }

  virtual ~Tester() {}
};

#if USE_TWO_CUTS
template < typename R >
const typename Tester<R>::TwoCutInt::Tables Tester<R>::TwoCutInt::S;
#endif

#endif