/* Copyright (c) 2018
   Charles Jordan (Hokkaido University, Sapporo, Japan),
   Michael Joswig, Lars Kastner (Technische Universitaet Berlin, Germany)

   This program is free software; you can redistribute it and/or modify it
   under the terms of the GNU General Public License as published by the
   Free Software Foundation; either version 3, or (at your option) any
   later version: http://www.gnu.org/licenses/gpl.txt.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.
-----------------------------------------------------------------------------
*/

///////////////////////////////////////////////////////////////////////////////
// GroupDecomposer.hh
//
// This file decomposes the given symmetry group in a way that makes it easy to
// compute the canonical representative of an equivalence class.
///////////////////////////////////////////////////////////////////////////////
#ifndef GROUPDECOMPOSER_HH
#define GROUPDECOMPOSER_HH

#include "TriangNode.hh"
#include "Symmetry.hh"
#include "GKZ.hh"
#include "mptopcom_typedefs.hh"
#include "CerrWrappers.hh"
#include "SymmetryConverter.hh"
#include "helpers.hh"

#include <map>
#include <list>

#include <polymake/Map.h>
#include <polymake/Set.h>

// Trying to deal with permlib
#include <polymake/group/permlib.h>
#include "switch_table-copy.h"

class GroupDecomposer;



// Check whether a permutation (non-)fixes entry n(=i).
struct non_fixed {
   int i;
   non_fixed(int n): i(n){}
   bool operator() (const Symmetry& s) { return s[i] != i; }
};


// Save group elements as pairs of g and the inverse to avoid recomputing.
typedef Symmetry gp_elem;

class GroupDecomposer {
   private:
      const gkz_type& gkz;
      pm::Array<int> identity;
      pm::Array<pm::Array<int>> all;
      std::map<int, std::map<int, std::map<signature_vector_type, pm::Array<int>>>> partitionStableSwitchTable;
      const pm::Map<basis_type, int>& basis2int;
      const pm::Map<int, basis_type>& int2basis;
      polymake::group::SwitchTable ST;

      bool fixes(int i, const gp_elem& g){
         const basis_type& b = int2basis[i];
         const basis_type image = g(b);
         return b == image;
      }

      int nFixedPts(const gp_elem& g){
         int result = 0;
         while(fixes(result, g)){
            result++;
         }
         return result;
      }
      
      // TODO: 
      // - Use pm::Array<int> as input
      // - Do not use iterators manually
      bool insert_element(const Symmetry& g){
         int i = nFixedPts(g);
         int j = i;
         while(basis2int[g(int2basis[j])] != i){
            j = basis2int[g(int2basis[j])];
         };
         signature_vector_type sig(signature(g));
         if(partitionStableSwitchTable.count(i) == 0){
           partitionStableSwitchTable[i] = std::map<int, std::map<signature_vector_type, pm::Array<int>>>();
         }
         if(partitionStableSwitchTable[i].count(j) == 0){
            (partitionStableSwitchTable[i])[j] = std::map<signature_vector_type, pm::Array<int>>();
            ((partitionStableSwitchTable[i])[j])[sig] = symmetry2array(g);
         } else {
            if(((partitionStableSwitchTable[i])[j]).count(sig)==0){
               bool toadd = true;
               for(const auto c:(partitionStableSwitchTable[i])[j]){
                  if(refines(c.first, sig)){
                     toadd = false;
                     return false;
                  }
               }
               std::map<signature_vector_type, pm::Array<int>>::iterator iter = ((partitionStableSwitchTable[i])[j]).begin();
               std::map<signature_vector_type, pm::Array<int>>::iterator endIter = ((partitionStableSwitchTable[i])[j]).end();
               for(; iter != endIter;)
               {
                  if (refines(sig, iter->first) ){
                     ((partitionStableSwitchTable[i])[j]).erase(iter++);
                  } else {
                     ++iter;
                  }
               }
               if(toadd){
                  ((partitionStableSwitchTable[i])[j])[sig] = symmetry2array(g);
                  return true;
               }
            }
         }
         return false;
      }


      void init(const SymmetryGroup& group){
         int k=0;
         // Filter group by signature.
         // Populate first stage of filter by fixed pts.
         all = pm::Array<pm::Array<int>>(group.load());
         for(SymmetryGroup::const_iterator sym_iter = group.begin();
               sym_iter != group.end();
               ++sym_iter){
            Symmetry g(*sym_iter);
            insert_element(g);
            all[k] = symmetry2array(g);
            k++;
         }
         ST = polymake::group::SwitchTable(all);
         // get_finest_signatures(all);

         // Make identity element.
         identity = pm::Array<int>(all[0].size());
         for(int i=0; i<identity.size(); i++){
            identity[i] = i;
         }
      }


   public:
      GroupDecomposer(const SymmetryGroup& group,
            const gkz_type& gkz_in):
         gkz(gkz_in), 
         basis2int(gkz_in.get_basis2int()),
         int2basis(gkz_in.get_int2basis()) {
            if(group.size() == 0){return;}
            init(group);
            if(CommandlineOptions::verbose()){
               cerrFirstWorker << "Final depth: " << partitionStableSwitchTable.size()-1 << std::endl;
               for(int i=0; i<partitionStableSwitchTable.size(); i++){
                  int n = partitionStableSwitchTable[i].size();
                  int total = 0;
                  for(const auto& s : partitionStableSwitchTable[i]){
                     total += (s.second).size();
                  }
                  cerrFirstWorker << "Level: " << i << " - signatures: " << n << " elements: " << total << std::endl;
               }
            }
         }

      GroupDecomposer(const GroupDecomposer&) = delete;
      
      const polymake::group::SwitchTable& get_switch_table() const {
         return ST;
      }

      const pm::Array<int>& get_identity() const {
         return identity;
      }
      
      bool populate_partition_stabilizer(const signature_vector_type& sig, std::map<int, std::map<int, const pm::Array<int>*>>& refST) const {
         // std::cout << " get_stabilizer_st(const signature_vector_type& sig, const TriangNode& t) const {" << std::endl;
         bool needsOpt = false;
         int i,j, maxj=0;
         for(const auto& level : partitionStableSwitchTable){
            for(const auto& sublevel : level.second){
               for(const auto& element : sublevel.second){
                  if(refines(element.first, sig)){
                     needsOpt = true;
                     i = level.first;
                     j = sublevel.first;
                     maxj = j>maxj ? j : maxj;
                     refST[i][j] = &element.second;
                     goto elementfound;
                  }
               }
               elementfound:;
            }
         }
         if(needsOpt){
            // for(i=0; i<=maxj; i++){
            //    refST[i][i] = &identity;
            // }
            return true;
         } else {
            return false;
         }
      }

      void print_signature(const Symmetry& g) const{
         std::cout << pmVector2string(signature(g)) << std::endl;
      }
      

};



#endif
