//////////////////////////////////////////////////////////////////////////
// SymmetricExtensionGraphNode.hh
// produced: 27/11/2020 jr
/////////////////////////////////////////////////////////////////////////
#ifndef SYMMETRICEXTENSIONGRAPHNODE_HH
#define SYMMETRICEXTENSIONGRAPHNODE_HH

#include <iostream>
#include <iomanip>
#include <vector>
#include <queue>
#include <unordered_map>
#include <mutex>

#include "ContainerIO.hh"
#include "HashKey.hh"
#include "LabelSet.hh"
#include "Symmetry.hh"
#include "SimplicialComplex.hh"
#include "Admissibles.hh"
#include "Incidences.hh"
#include "Volumes.hh"
#include "PartialTriang.hh"

namespace topcom {

  
  // the following type can store for each symmetry g
  // the minimal index of the symmetric difference of a partial triangulation T and its image g(T)
  // where the convention is that the critical simplex index is std::numeric_limits<size_type>::max() if S = g(S)
  // (the simplex with this index decides the lexicographic comparison);
  // in order to save memory, we store a vector of critical indices
  // where critical_element[idx] is the index of the critical simplex for symmetries[idx]:
  typedef std::vector<size_type> critical_simpidx_table_type;

  // for the case of scarce memory we offer a cache for the symmetries represented by images of
  // simplex indices; to this end, a pair of indices is defined with the necessary features
  // for an unordered map:
  class IndexPair : public std::pair<size_type, size_type> {
  public:
    inline IndexPair(const size_type simpidx, const size_type symidx) : std::pair<size_type, size_type>(simpidx, symidx) {}
    inline size_type keysize() const { return 2; }
    inline size_type key(const size_type n) const { return n == 0 ? first : second; }
    inline bool operator==(const IndexPair& ip) { return (second == ip.second) && (first == ip.first); }
  };

  // use if memory is not an issue:
  typedef std::vector<std::vector<size_type> >                            symmetry_table_type;

  // use if memory is scarce:
  typedef std::pair<IndexPair, size_type>                                 symmetry_cache_entry_type;
  typedef std::vector<symmetry_cache_entry_type>                          symmetry_cache_type;
  typedef std::queue<IndexPair>                                           symmetry_keyvec_type;

  // the following class supports reading the object-specific data of a
  // SymmetricExtensionGraphNode; the node cannot be read directly because
  // of pointers to global data (the same holds for a PartialTriang so that
  // a PartialTriangReader has to be read instead):
  class SymmetricExtensionGraphNodeReader {
  public:
    PartialTriangReader         partial_triang_reader; // cannot be a PartialTriang because of missing pointers to global data
    critical_simpidx_table_type critsimpidx_table;
  public:
    inline std::istream& read(std::istream& ist) {
      char c;
      
      // the expected syntax should be idential to the write syntax of PartialTriang:
      if (!(ist >> std::ws >> c >> std::ws) || (c != ContainerChars::list_start_char)) {
	MessageStreams::forced() << message::lock
				 << "SymmetricExtensionGraphNodeReader::read(std::istream& ist): error while reading - expected "
				 << ContainerChars::list_start_char
				 << " - exiting"
				 << std::endl
				 << message::unlock;
	exit(1);
      }
      if (!(ist >> partial_triang_reader)) {
	MessageStreams::forced() << message::lock
				 << "SymmetricExtensionGraphNodeReader::read(std::istream& ist): error while reading partial_triang_reader - exiting"
				 << std::endl
				 << message::unlock;
	exit(1);
      }
      if (!(ist >> std::ws >> c >> std::ws) || (c != ContainerChars::delim_char)) {
	MessageStreams::forced() << message::lock
				 << "SymmetricExtensionGraphNodeReader::read(std::istream& ist): error while reading - expected "
				 << ContainerChars::delim_char
				 << "after partial_triang_reader - exiting"
				 << std::endl
				 << message::unlock;
	exit(1);
      }
      if (!(ist >> critsimpidx_table)) {
	MessageStreams::forced() << message::lock
				 << "SymmetricExtensionGraphNodeReader::read(std::istream& ist): error while reading critsimpidx_table - exiting"
				 << std::endl
				 << message::unlock;
	exit(1);
      }
      if (!(ist >> std::ws >> c >> std::ws) || (c != ContainerChars::list_end_char)) {
	MessageStreams::forced() << "SymmetricExtensionGraphNodeReader::read(std::istream& ist): error while reading - expected "
				 << ContainerChars::list_end_char
				 << "at end of data record - exiting"
				 << std::endl
				 << message::unlock;
	exit(1);
      }
      return ist;
    }
    inline friend std::istream& operator>>(std::istream& ist, SymmetricExtensionGraphNodeReader& segnr) {
      return segnr.read(ist);
    }
  };
  
  class SymmetricExtensionGraphNode {
  public:
    static symmetry_table_type               _symmetry_images_by_element;
    static thread_local symmetry_cache_type  _symmetry_images_by_element_cache;
    // static thread_local symmetry_keyvec_type _symmetry_images_by_element_keyvec;
  private:
    const SymmetryGroup*        _symmetriesptr;
    PartialTriang               _partial_triang;
    critical_simpidx_table_type _critsimpidx_table;
  private:
    SymmetricExtensionGraphNode() = delete;
  public:
    // initializer for static data:
    inline static void init_simpidx_table(const SymmetryGroup*, const size_type);
    inline static void init_simpidx_cache(const SymmetryGroup*);
    
    // constructors:
    inline SymmetricExtensionGraphNode(const SymmetricExtensionGraphNode&);
    inline SymmetricExtensionGraphNode(const SymmetricExtensionGraphNode&&);
    inline SymmetricExtensionGraphNode(const SymmetricExtensionGraphNode&,
				       const PartialTriang&,
				       const critical_simpidx_table_type&);
    inline SymmetricExtensionGraphNode(const SymmetricExtensionGraphNode&,
				       PartialTriang&&,
				       critical_simpidx_table_type&&);

    // compute a node from scratch for double-check purposes
    // (the root node is computed for pt = empty partial triangulation):
    SymmetricExtensionGraphNode(const SymmetryGroup*,
				const PartialTriang&);
    SymmetricExtensionGraphNode(const SymmetryGroup*,
				PartialTriang&&);

    // construct a node from global data and local reader data
    // whose members are moved into the node:
    inline SymmetricExtensionGraphNode(const SymmetryGroup*,
				       const parameter_type, 
				       const parameter_type, 
				       const Admissibles*, 
				       const Incidences*,
				       const Volumes*,
				       SymmetricExtensionGraphNodeReader&&);
    
    // destructor:
    inline ~SymmetricExtensionGraphNode();

    // assignment:
    inline SymmetricExtensionGraphNode& operator=(const SymmetricExtensionGraphNode&);
    inline SymmetricExtensionGraphNode& operator=(const SymmetricExtensionGraphNode&&);

    // functions:
 
    // the following is the core function:
    // it checks whether the child node of this node by extending partial triangulation by a new simplex
    // is lex-minimal; it is assumed that the new simplex has an index that is larger than all the existing
    // simplices in the partial triangulation; the critical simplex table is updated during the checking process
    // in the second non-const reference argument, and the stabilizer count is stored in the third non-const
    // reference argument:
    bool child_is_lexmin(const Simplex&, critical_simpidx_table_type*, size_type*) const;
    
    // the same, but based on the symmetry group representation on points:
    bool child_is_lexmin_lean(const Simplex&, critical_simpidx_table_type*, size_type*) const;

    // auxiliary function to compute critical simplex from scratch for a symmetry:
    size_type critical_simpidx(const SimplicialComplex&, const Symmetry&) const;
    
    // the same, but based on the symmetry group representation on points:
    size_type critical_simpidx_lean(const SimplicialComplex&, const Symmetry&, const size_type) const;

    // accessors:
    inline const SymmetryGroup*               symmetries_ptr()          const { return _symmetriesptr; }
    inline const PartialTriang&               partial_triang()          const { return _partial_triang; }
    inline const critical_simpidx_table_type& critsimpidx_table()       const { return _critsimpidx_table; }

    // stream input/output (plain input is not supported because of the pointers to additional global data):
    inline std::istream& read(std::istream&);
    inline friend std::istream& operator>>(std::istream&, SymmetricExtensionGraphNode&);
    inline std::ostream& write(std::ostream&) const;
    inline friend std::ostream& operator<<(std::ostream&, const SymmetricExtensionGraphNode&);
  };

  // initializer for static data:
  inline void SymmetricExtensionGraphNode::init_simpidx_table(const SymmetryGroup* sgptr, const size_type n) {
    if (CommandlineOptions::simpidx_symmetries()) {

      // here, we simply reorganize the symmetries in a more cache coherent way in a new table:
      try {
	_symmetry_images_by_element.resize(sgptr->n(), std::vector<size_type>(sgptr->size(), std::numeric_limits<size_type>::max()));
      }
      catch (...) {
	MessageStreams::forced() << message::lock
				 << "SymmetricExtensionGraphNode::SymmetricExtensionGraphNode(const SymmetryGroup&, const PartialTriang&): "
				 << "allocation of " << sgptr->size() * sgptr->n() << " int elements failed - exiting"
				 << std::endl
				 << message::unlock;
	exit(1);
      }
      for (size_type symidx = 0; symidx < sgptr->size(); ++symidx) {
	for (parameter_type elm = 0; elm < sgptr->n(); ++elm) {
	  _symmetry_images_by_element[elm][symidx] = (*sgptr)[symidx][elm];
	}
      }
    }
    else {
      if (!CommandlineOptions::memopt()) {

	// here, we prepare a complete table that is populated on the fly when needed:
	try {
	  _symmetry_images_by_element.resize(n, std::vector<size_type>(sgptr->size(), std::numeric_limits<size_type>::max()));
	}
	catch (...) {
	  MessageStreams::forced() << message::lock
				   << "SymmetricExtensionGraphNode::SymmetricExtensionGraphNode(const SymmetryGroup&, const PartialTriang&): "
				   << "allocation of " << sgptr->size() * n << " int elements failed - exiting"
				   << std::endl
				   << message::unlock;
	  exit(1);
	}
      }
      else if (!CommandlineOptions::parallel_enumeration()) {

	// in this case, the main thread needs to initialize the thread_local cache:
	init_simpidx_cache(sgptr);
      }
    }      
  }

  inline void SymmetricExtensionGraphNode::init_simpidx_cache(const SymmetryGroup* sgptr) {
    if (!CommandlineOptions::simpidx_symmetries() && CommandlineOptions::memopt()) {
      if (CommandlineOptions::localcache() > 0) {
	MessageStreams::forced() << message::lock
				 << "init cache:" << std::endl
				 << message::unlock;
	_symmetry_images_by_element_cache.resize(CommandlineOptions::localcache() / CommandlineOptions::no_of_threads() + 1,
						 std::pair<IndexPair, size_type>(IndexPair(std::numeric_limits<size_type>::max(),
											   std::numeric_limits<size_type>::max()),
										 std::numeric_limits<size_type>::max()));
      }
    }
  }
  
  // constructors:
  inline SymmetricExtensionGraphNode::SymmetricExtensionGraphNode(const SymmetricExtensionGraphNode& segn) :
    _symmetriesptr(segn._symmetriesptr),
    _partial_triang(segn._partial_triang),
    _critsimpidx_table(segn._critsimpidx_table) {
  }

  inline SymmetricExtensionGraphNode::SymmetricExtensionGraphNode(const SymmetricExtensionGraphNode&& segn) :
    _symmetriesptr(segn._symmetriesptr),
    _partial_triang(std::move(segn._partial_triang)),
    _critsimpidx_table(std::move(segn._critsimpidx_table)) {
  }

  inline SymmetricExtensionGraphNode::SymmetricExtensionGraphNode(const SymmetricExtensionGraphNode&  node,
								  const PartialTriang&                partial_triang,
								  const critical_simpidx_table_type&  critsimpidx_table) :
    _symmetriesptr(node._symmetriesptr),
    _partial_triang(partial_triang),
    _critsimpidx_table(critsimpidx_table) {
  }
  
  inline SymmetricExtensionGraphNode::SymmetricExtensionGraphNode(const SymmetricExtensionGraphNode&  node,
								  PartialTriang&&                     partial_triang,
								  critical_simpidx_table_type&&       critsimpidx_table) :
    _symmetriesptr(node._symmetriesptr),
    _partial_triang(std::move(partial_triang)),
    _critsimpidx_table(std::move(critsimpidx_table)) {
  }
  
  inline SymmetricExtensionGraphNode::SymmetricExtensionGraphNode(const SymmetryGroup*                sgptr,
								  const parameter_type                no, 
								  const parameter_type                rank, 
								  const Admissibles*                  admtableptr, 
								  const Incidences*                   inctableptr,
								  const Volumes*                      voltableptr,
								  SymmetricExtensionGraphNodeReader&& segnr) :
    _symmetriesptr(sgptr),
    _partial_triang(no, rank, admtableptr, inctableptr, voltableptr, std::move(segnr.partial_triang_reader)),
    _critsimpidx_table(std::move(segnr.critsimpidx_table)) {
  }
  
  // destructor:
  inline SymmetricExtensionGraphNode::~SymmetricExtensionGraphNode() {
#ifdef DEBUG
    MessageStreams::debug() << message::lock;
    size_type max_bucket_size = 0;
    for (size_type n = 0; n < _symmetry_images_by_element_cache.bucket_count(); ++n) {
      if (max_bucket_size < _symmetry_images_by_element_cache.bucket_size(n)) {
	max_bucket_size = _symmetry_images_by_element_cache.bucket_size(n);
      }
    }
    MessageStreams::debug() << "max bucket size of cache is " << max_bucket_size << std::endl
			    << message::unlock;
#endif
  }

  // assignment:
  inline SymmetricExtensionGraphNode& SymmetricExtensionGraphNode::operator=(const SymmetricExtensionGraphNode& segn) {
    if (this == &segn) {
      return *this;
    }
    _symmetriesptr           = segn._symmetriesptr;
    _partial_triang          = segn._partial_triang;
    _critsimpidx_table       = segn._critsimpidx_table;
    return *this;
  }

  inline SymmetricExtensionGraphNode& SymmetricExtensionGraphNode::operator=(const SymmetricExtensionGraphNode&& segn) {
    if (this == &segn) {
      return *this;
    }
    _symmetriesptr           = segn._symmetriesptr;
    _partial_triang          = std::move(segn._partial_triang);
    _critsimpidx_table       = std::move(segn._critsimpidx_table);
    return *this;
  }

  // stream input/output:
  inline std::istream& SymmetricExtensionGraphNode::read(std::istream& ist) {
    MessageStreams::forced() << message::lock
			     << "std::istream& SymmetricExtensionGraphNode::read(std::ostream& ist) const: "
			     << "reading from stream not supported because pointers to global data are required - exiting"
			     << std::endl
			     << message::unlock;
    exit(1);
    return ist;
  }

  inline std::istream& operator>>(std::istream& ist, SymmetricExtensionGraphNode& ssgn) {
    return ssgn.read(ist);
  }
    
  inline std::ostream& SymmetricExtensionGraphNode::write(std::ostream& ost) const {
    ost << ContainerChars::list_start_char
	<< _partial_triang
	<< ContainerChars::delim_char
	<< _critsimpidx_table
	<< ContainerChars::list_end_char;
    return ost;
  }

  inline std::ostream& operator<<(std::ostream& ost, const SymmetricExtensionGraphNode& ssgn) {
    return ssgn.write(ost);
  }

}; // namespace topcom

#endif

// eof SymmetricExtensionGraphNode.hh