self_avoiding_polygon/exact/polygon.hpp

#ifndef POLYGON_HPP
#define POLYGON_HPP

#include <cstring>
#include <cassert>
#include <stack>
#include <map>

#include "config.hpp"
#include "coeffs.hpp"
#include "polygon_step.hpp"

#include "flint/fmpz_poly.h"
#include "flint/fmpz_poly_q.h"
#include "flint/fmpz_poly_mat.h"
#include "flint/fmpq_poly.h"

using namespace std;

//***********
//* Polygon *
//***********

//! Class for self avoiding polygon in the square lattice
//! Polygon are drown on a grid and hace length bounded
//! by max_len. The grid have a border prevent the polygon
//! to go too far. A typical example of the grid is
//! ##########
//! #        #
//! ####S    #
//! ##########
//! where S is the starting point and # is border.
//! Polygon will grow applyng step. A grid case contains
//! contains the path distance from the starting point.
//! We store the unique id of a step in an historic grid.
//! In order to perfoem backward without clearing the grid,
//! we associate the step id to the corresponding path
//! distance. Hence the case (i,j) of the grid contribute 
//! to the polygon if grid[(i,j)]=t and histo_grid[t]=s
//! and step_histo[s]=t.

class Polygon{
public:
  //! Width of the grid
  static const size_t grid_width=max_len-1;

  //! Height of the grid
  static const size_t grid_height=max_len/2+2;

  //! Size of the grid
  static const size_t grid_size=grid_width*grid_height;

  //! Position of the starting point
  static const int64 xinit=max_len/2-2;
  static const int64 yinit=1;

  //! Border value
  static const size_t border=0;

  //! Empty value
  static const size_t empty=-1;

  //! The living grid the polygon
  size_t grid[grid_size];

  //! The history grid of the polygon
  size_t grid_histo[grid_size];

  //! The history step of the polygon
  size_t step_histo[max_len+1];

  //! Head poistion on the grid
  size_t head;

  //! Lenght of the polygon
  size_t length;

  //! Empty constructor
  Polygon();

  //! Copy operator
  Polygon& operator=(const Polygon& P);
  
  //! Init data of the polygon
  void init();

  //! Display the polygon
  void display() const;
 
  //! Apply a step to the polygon
  //! \param s step to apply
  void apply(Step& s);

  //! Test is the case at position ind is admissible
  //! as the next case of the polygon; this at path
  //! length t.
  //! \param t path_length of the next case
  //! \param ind index of the case to test
  //! \param s last step applied to the polygon
  bool test(size_t t,size_t ind,Step* s) const;

  //! Test if the polygon is closed
  bool is_closed() const;

  //! Return indice of the next vertex of the polygon
  //! \param t path length of the current vertex
  //! \param c current vertex indice
  size_t next_vertex(size_t t,size_t c) const;
  
  //! Return the fp coefficient of the polygon
  void fp(fmpq_poly_t r) const;

  //------------------
  // Static functions
  //------------------

  //! Return x coordinate of the case with indice ind.
  //! \param ind indice of the case
  static int64 x(size_t ind);

  //! Return y coordinate of the case with indice ind.
  //! \param ind indice of the case
  static int64 y(size_t ind);

  //! Return indice of the case on the left of case with
  //! indice ind.
  //! \param ind indice of the case
  static size_t left(size_t ind);

  //! Return indice of the case on the right of case with
  //! indice ind.
  //! \param ind indice of the case
  static size_t right(size_t ind);
  
  //! Return indice of the case on the up of case with
  //! indice ind.
  //! \param ind indice of the case
  static size_t up(size_t ind);
  
  //! Return indice of the case on the down of case with
  //! indice ind.
  //! \param ind indice of the case
  static size_t down(size_t ind);
  
  //! Return indice of the case at position (x,y).
  //! \param x x-coordinate of the case
  //! \prama y y-coordiante of the case
  static size_t pos(size_t x,size_t y);
};

//**************
//* InfoVertex *
//**************

//! This class is used to obtained the adjacence matrix
//! of the haired polygon.

class InfoVertex{
public:
  //! Indice of the vertex
  size_t id;

  //! Coordinates of the vertex
  int64 x,y;
  
  //! Degree of the vertex
  size_t deg;

  //! Neighbhorhoods of the vertex
  size_t v[4];

  //! Empty constructor (not explicety used)
  InfoVertex();

  //! Constructor for a vertex with not yet detected neighbhors.
  //! \param id indice of the vertex
  //! \param x x-coordinate of the vertex
  //! \param y y-coordinate of the vertex
  InfoVertex(size_t id,int64 x,int64 y);

  //! Constructor for a vertex with four identified neighbhors.
  //! \param id indice of the vertex
  //! \param x x-coordinate of the vertex
  //! \param y y-coordinate of the vertex
  //! \param l indice of the vertex on the left
  //! \param r indice of the vertex on the right
  //! \param u indice of the vertex on the up
  //! \param d indice of the vertex on the dwon
  InfoVertex(size_t id,int64 x,int64 y,size_t l,size_t r,size_t u,size_t d);
};

//********************
//* Inline functions *
//********************

//---------
// Polygon 
//---------

inline
Polygon::Polygon(){
}

inline bool
Polygon::test(size_t t,size_t ind,Step* s) const{
  size_t v=grid[ind];
  if(v>s->t) return true;
  return grid_histo[ind]!=s->histo[v];
}

inline void
Polygon::apply(Step& step){
  length=step.t;
  grid[head=step.newh]=step.t;
  grid_histo[head]=step.num();
  memcpy(step_histo,step.histo,(step.t+1)*sizeof(size_t));
}

inline bool
Polygon::is_closed() const{
  return grid[down(head)]==1;
}

//----------------
// Static Polygon
//----------------

inline size_t
Polygon::left(size_t ind){
  return ind-1;
}

inline size_t
Polygon::right(size_t ind){
  return ind+1;
}

inline size_t
Polygon::up(size_t ind){
  return ind+grid_width;
}

inline size_t
Polygon::down(size_t ind){
  return ind-grid_width;
}

inline int64
Polygon::x(size_t ind){
  return ind%grid_width;
}

inline int64
Polygon::y(size_t ind){
  return ind/grid_width;
}

inline size_t 
Polygon::pos(size_t x,size_t y){
  return  x+y*grid_width;
}

//------------
// InfoVertex
//------------

inline
InfoVertex::InfoVertex(){
}

inline
InfoVertex::InfoVertex(size_t _id,int64 _x,int64 _y):
  id(_id),x(_x),y(_y),deg(0){
}

inline
InfoVertex::InfoVertex(size_t _id,int64 _x,int64 _y,size_t l,size_t r,size_t u,size_t d):
  id(_id),x(_x),y(_y),deg(4),v{l,r,u,d}{
}
  
#endif