/* 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.
-----------------------------------------------------------------------------
*/

//////////////////////////////////////////////////////////////////////////
// ReverseSearchTriangulations.hh
// This is a refactor of a copy of SymmetricBFS.hh
/////////////////////////////////////////////////////////////////////////
#ifndef REVERSE_SEARCH_TRIANGULATIONS_HH
#define REVERSE_SEARCH_TRIANGULATIONS_HH

#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <cstdlib>
#include <ctime>

#include <assert.h>
#include <set>
#include <map>

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


#include "FlipDataSimple.hh"
#include "FlipDataNoSym.hh"
#include "FlipDataSym.hh"
#include "TreeGraph.hh"
#include "SimplicialComplex.hh"

#include "CommandlineOptions.hh"

#include "Chirotope.hh"
#include "Flip.hh"
#include "TriangNode.hh"
#include "Symmetry.hh"
#include "RegularityCheck.hh"
#include "FineTriang.hh"

#include "mptopcom_typedefs.hh"
#include "FlipChecker.hh"
#include "FlipDataSimple.hh"
#include "InitialTriang.hh"
#include "ReverseSearch-copy.hh"
#include "RandomBFS.hh"

#include "AugmentedPointConfiguration.hh"
#include "AugmentedTriangulation.hh"
#include "TriangulationLogger.hh"
#include "TriangulationOracle.hh"

#include "FlipDataCyclic.hh"
#include "AugmentedPointConfigurationCyclic.hh"
#include "DummyTreeGraph.hh"



class ReverseSearchWrapper{
   public:
      virtual ~ReverseSearchWrapper() {}

      virtual size_type totalcount() = 0;
      
      virtual TriangNode get_initial_triang(
         const parameter_type      no,
         const parameter_type      rank,
         const SimplicialComplex&  seed
         ) = 0;

      virtual TriangNode find_max_triang(const TriangNode& initial_triang) = 0;

      virtual long generic_reverse_search(const TriangNode& initial,
            long max_nodes, long max_depth) = 0;
      
      virtual void auto_reverse_search(
          const parameter_type      no,
            const parameter_type      rank,
            const SimplicialComplex&  seed
      ) = 0;

      virtual int size() const = 0;

      virtual void randomized_bfs(const TriangNode& initial) const = 0;

};


template<bool _make_tree, bool all_edges, typename FlipDataType, typename APCType, typename TGType>
class ReverseSearch : public ReverseSearchWrapper{
   private:
      using TriangulationType = AugmentedTriangulation<TriangulationOracle<FlipDataType, APCType>>;
      using OracleType = TriangulationOracle<FlipDataType, APCType>;
      size_type                       _symcount;
      // Order is important, apc needs to be initialized before sbb and pfc.
      const TriangulationOracle<FlipDataType, APCType> to;
      using Logger = TriangulationLogger<TriangulationType, OracleType, TGType>;
      Logger logger;

      ReverseSearchTemplate<TriangulationType, Logger, _make_tree, all_edges> rst;

   public:
      // results:
      size_type totalcount() { return logger.get_totalcount(); }
      inline const size_type symcount()   const { return _symcount; }
      inline int size() const { return to.size(); }

      
      long generic_reverse_search(const TriangNode& initial,
            long max_nodes, long max_depth){
         TriangulationType t(to, initial);
         return rst.generic_reverse_search(t, max_nodes, max_depth);
      }
      
      void randomized_bfs(const TriangNode& initial) const {
         TriangulationType t(to, initial);
         ::randomized_bfs(t);
      }
      
      TriangNode get_initial_triang(
         const parameter_type      no,
         const parameter_type      rank,
         const SimplicialComplex&  seed
         ) {
         return to.get_initial_triang(no, rank, seed);
      }

      // Find the triangulation without any further upflips.
      TriangNode find_max_triang(const TriangNode& initial) {
         return to.find_max_triang(initial);
      }


      /* Hall-Knuth estimate for number of nodes in subtree rooted at
       * initial using one random probe.
       * TODO: estimate number of triangulations for --regular ?
       */
      unsigned long long estimate(const TriangNode& initial){
         TriangulationType t(to, initial);
         return rst.estimate(t);
      }
      

      // For the single threaded case:
      // 1. Create initial triangulation
      // 2. Find lex maximal triangulation
      // 3. Run reverse search
      // This method was created to avoid duplication of the constructors used
      // for mptopcom1 and mptopcom.
      void auto_reverse_search(
         const parameter_type      no,
         const parameter_type      rank,
         const SimplicialComplex&  seed
      ){
         int estimates = CommandlineOptions::estimates();

         if (CommandlineOptions::verbose()) {
            cerrFirstWorker << "TrivialSymmetry: " << APCType::trivialSymmetry::value << std::endl;
         }
         TriangNode initial_triang = to.get_initial_triang(no, rank, seed);
         TriangNode lex_optimal = to.find_max_triang(initial_triang);
         if (estimates == 0){
            TriangulationType start(to, lex_optimal);
            rst.auto_reverse_search(start);
            to.print_pfc_stat();
            cerrWrap << "Totalcount: " << logger.get_totalcount() << std::endl;
         }
         else{
           unsigned long long tot = 0;
           srand(time(NULL));
           for (int i=0; i<estimates; i++){
             tot += estimate(lex_optimal);
           }
           cerrWrap << "Estimate: " << tot / estimates << " nodes" << std::endl;
         }

      }

      //ReverseSearch(const AugmentedPointConfiguration<trivialSymmetry, checkFine, smallGroup> apc_in) :
      ReverseSearch(
            const PointConfiguration& points_in,
            const Chirotope&          chiro_in,
            const SymmetryGroup&      symmetries_in) :
         _symcount(0),
         to(points_in, chiro_in, symmetries_in),
         logger(to), rst(logger)
   {}

};

template<bool makeTree, bool allEdges, typename smallGroup, typename checkFine, typename FlipCheckerType>
inline ReverseSearchWrapper * constructReverseSearch_trivialSymmetry(
      const PointConfiguration& points,
      const Chirotope&          chiro,
      const SymmetryGroup&      symmetries){
   bool trivialSymmetry = symmetries.size() == 0;
   using checkRegularBool = typename FlipCheckerType::checkRegular;
   bool checkRegular = checkRegularBool::value;
   trivialSymmetry |= CommandlineOptions::make_marked_tree();
   if(trivialSymmetry && !checkRegular && !checkFine::value){
      typedef AugmentedPointConfigurationNoSym<checkFine, smallGroup> APCType;
      typedef FlipDataSimple<FlipCheckerType, APCType> FlipDataType;
      typedef TreeGraph<FlipDataType, APCType> TGType;
      return new ReverseSearch<makeTree, allEdges, FlipDataType, APCType, TGType>(points, chiro, symmetries);
   } else {
      if(trivialSymmetry){
         typedef AugmentedPointConfigurationNoSym<checkFine, smallGroup> APCType;
         typedef FlipDataNoSym<FlipCheckerType, APCType> FlipDataType;
         typedef TreeGraph<FlipDataType, APCType> TGType;
         return new ReverseSearch<makeTree, allEdges, FlipDataType, APCType, TGType>(points, chiro, symmetries);
      } else {
         typedef AugmentedPointConfigurationSym<checkFine, smallGroup> APCType;
         typedef FlipDataSym<FlipCheckerType, APCType> FlipDataType;
         typedef TreeGraph<FlipDataType, APCType> TGType;
         return new ReverseSearch<makeTree, allEdges, FlipDataType, APCType, TGType>(points, chiro, symmetries);
      }
   }
}

template<bool makeTree, typename smallGroup, typename checkFine, typename FlipCheckerType>
inline ReverseSearchWrapper * constructReverseSearch_allEdges(
      const PointConfiguration& points,
      const Chirotope&          chiro,
      const SymmetryGroup&      symmetries){
   bool allEdges = CommandlineOptions::all_edges();
   if(allEdges){
      return constructReverseSearch_trivialSymmetry<makeTree, true, smallGroup, checkFine, FlipCheckerType>(points, chiro, symmetries);
   } else {
      return constructReverseSearch_trivialSymmetry<makeTree, false, smallGroup, checkFine, FlipCheckerType>(points, chiro, symmetries);
   }
}


template<bool maxGKZ, bool makeTree, typename checkFine, typename smallGroup>
inline ReverseSearchWrapper * constructReverseSearch_checkRegular(
      const PointConfiguration& points,
      const Chirotope&          chiro,
      const SymmetryGroup&      symmetries){
   bool checkRegular = CommandlineOptions::check_regular();
   if(checkRegular){
      return constructReverseSearch_allEdges<makeTree, smallGroup, checkFine, RegularChecker<checkFine, maxGKZ>>(points, chiro, symmetries);
   } else {
      return constructReverseSearch_allEdges<makeTree, smallGroup, checkFine, NonRegularChecker<checkFine, maxGKZ>>(points, chiro, symmetries);
   }
}

template<bool makeTree, typename checkFine, typename smallGroup>
inline ReverseSearchWrapper * constructReverseSearch_maxGKZ(
      const PointConfiguration& points,
      const Chirotope&          chiro,
      const SymmetryGroup&      symmetries){
   bool maxGKZ = CommandlineOptions::central();
   if(maxGKZ){
      return constructReverseSearch_checkRegular<true, makeTree, checkFine, smallGroup>(points, chiro, symmetries);
   } else {
      return constructReverseSearch_checkRegular<false, makeTree, checkFine, smallGroup>(points, chiro, symmetries);
   }
}  


template<typename checkFine, typename smallGroup>
inline ReverseSearchWrapper * constructReverseSearch_makeTree(
      const PointConfiguration& points,
      const Chirotope&          chiro,
      const SymmetryGroup&      symmetries){
   bool makeTree = CommandlineOptions::make_tree();
   if(makeTree){
      return constructReverseSearch_maxGKZ<true, checkFine, smallGroup>(points, chiro, symmetries);
   } else {
      return constructReverseSearch_maxGKZ<false, checkFine, smallGroup>(points, chiro, symmetries);
   }
}


template<typename smallGroup>
inline ReverseSearchWrapper * constructReverseSearch_checkFine(
      const PointConfiguration& points,
      const Chirotope&          chiro,
      const SymmetryGroup&      symmetries){
   bool checkFine = CommandlineOptions::fine_only();
   if(checkFine){
      return constructReverseSearch_makeTree<std::true_type, smallGroup>(points, chiro, symmetries);
   } else {
      return constructReverseSearch_makeTree<std::false_type, smallGroup>(points, chiro, symmetries);
   }
}


inline ReverseSearchWrapper * constructReverseSearch_smallGroup(
      const PointConfiguration& points,
      const Chirotope&          chiro,
      const SymmetryGroup&      symmetries){
   bool smallGroup = true;
   bool sg = CommandlineOptions::small_group();
   bool lg = CommandlineOptions::large_group();
   int n = symmetries.card();
   if (CommandlineOptions::verbose()) {
      // TOPCOM does not count the identity.
      n++;  
      cerrFirstWorker << "Group size is N = " << n << std::endl;
   }
   if(sg && !lg){
      smallGroup = true;
   } else if (!sg && lg){
      smallGroup = false;
   } else {
      if(n > 20){
         smallGroup = false;
      }
   }
   if(smallGroup){
      return constructReverseSearch_checkFine<std::true_type>(points, chiro, symmetries);
   } else {
      return constructReverseSearch_checkFine<std::false_type>(points, chiro, symmetries);
   }
}


inline ReverseSearchWrapper * constructReverseSearch(
      const PointConfiguration& points,
      const Chirotope&          chiro,
      const SymmetryGroup&      symmetries){
   if(CommandlineOptions::cyclic_flips()){
      typedef NonRegularChecker<std::false_type, false> FlipCheckerType;
      typedef AugmentedPointConfigurationCyclic<std::false_type, std::false_type> APCType;
      typedef FlipDataCyclic<FlipCheckerType, APCType> FlipDataType;
      typedef DummyTreeGraph<FlipDataType, APCType> TGType;
      return new ReverseSearch<false, false, FlipDataType, APCType, TGType>(points, chiro, symmetries);
   } else {
      return constructReverseSearch_smallGroup(points, chiro, symmetries);
   }
}



#endif

// eof ReverseSearchTriangulations.hh
