#ifndef __GROUP_CONNECTIVITY_H__
#define __GROUP_CONNECTIVITY_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;

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< 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;

  size_t numForb;
  int edges;

  std::vector<EdgeId> classEdges;
  std::vector< std::pair<EdgeId, Mapping> > nonClassEdges;

  virtual void init(
    int edges_,
    std::vector<EdgeId> spanningTree,
    std::vector<TwoCut> twoCuts,
    std::vector< std::vector<DirectedEdgeId> > elementaryCycles
  ) {
    edges = edges_;
    numForb = 1;
    while (edges_-- > 0) numForb *= (Ring::size - 1);

    size_t num_classes = 1;
    edges_ = spanningTree.size();
    while (edges_-- > 0) num_classes *= Ring::size;
    ClassesType C(num_classes, 0);
    C.swap(classes);

    for (auto e : spanningTree)
      classEdges.push_back(e - 1);

    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_NEXT_FORB
  bool nextForb(Mapping& forb) {
    for (size_t i = 0; i < edges; i++) {
      T v = forb[i] + 1;
      if (v >= Ring::size) {
        forb.assign(i, 1);
      } else {
        forb.assign(i, v);
        return true;
      }
    }

    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& cannonize(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];
    }

    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);

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

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

    return (isConnected = true);
#   undef INC
  }

  virtual ~Tester() {}
};

#endif