#ifndef MAZEMATRIXD2_H
#define MAZEMATRIXD2_H

#include <cassert>
#include <vector>
using namespace std;

#include <cellD2.h>
#include <print.h>
#include <stringconvert.h>
#include <stringtagparser.h>

/*!
\brief Linked square cell structure.

A linked structure that has a few interpretations.

* Links are fixed in meaning. 0 is up, 1 is right,
  2 is down, 3 is left.

This structure can be any shape with cells, or it
 could be restricted to a 2D matrix.

As long as the data structure is consistent anything
 goes.

* Links are to any other nodes, and the structure
 becomes a graph with each node having 4 possible 
 neighbours.
   
I made the data structure with the aim of converting
 it from the fixed links structure to a node graph.
 For example in maze nodes with two neighbours could
 be deleted.  Then the mazes associated node graph
 is formed. 
*/
template< typename T >
class mazematrixD2
{
public:

  /** Rows and columns dimensions and total number of cells. */
  uint dim[3];

  /** Set the maze dimensions. */
  void dimset(uintc rows, uintc columns);

  /** The first cell is ignored as it is zero/no cell. */
  vector< cellD2<T> > vi;

  /** Uninitialized state. */
  mazematrixD2();

  /** Build non connected matrix. */
  mazematrixD2(uintc rows, uintc columns);

  /** Pushes a new cell onto vi, assigning it an id. */
  uintc add();

  /** Access neighbours id. */
  T neib(T id, uintc k) const;

  /** Link two adjacent neighbours, k is id's local ni position pointing to id2. */
  void link( T id, uintc k, T id2);

  /** Link two neighbours. */
  void link(T id, uintc k, T id2, uintc k2);

  /** Iterate over cells except 0, checking double linkage. */
  boolc valid() const;

  /** Interpret and access as a 2D matrix. */
  cellD2<T> & access(uintc r, uintc c) 
    { return vi[c+r*dim[0]+1]; }

  /** Access outside the range will fail. */
  void access(bool & res, cellD2<T>& x, uintc r, uintc c);

  /** Given position k and direction mv it may be possible to move to k2. */
  void move(bool & res, T& k2, uintc mv, T const k) const;

  /** Looks for unvisited neighbours. */ 
  void neighboursunvisited( vector<T> & v, T const k);

  /** Given id's if these cells next to eachother link them. */
  void linkadjacent(bool & res, T const id1, T const id2);

  /** Serialize object. */
  operator stringc () const;

  /** Construct object from string. */
  void serializeInverse(stringc & str);

};


//----------------------------------------------------------
// Implementation


template< typename T >
void mazematrixD2<T>::access(bool & res, cellD2<T>& x, uintc r, uintc c)
{
  res=false;
  T k=c+r*dim[0]+1;
  if (k < dim[2]+1)
  {
    if (k!=0)
    {
      x=vi[k];
      res=true;
    }
  }
}

template< typename T >
void mazematrixD2<T>::dimset(uintc rows, uintc columns)
{
  dim[0]=rows;
  dim[1]=columns;
  dim[2]=rows*columns;

  vi.resize(rows*columns+1);
  for (T i=0; i<vi.size(); ++i)
    vi[i].id=i;
}


template< typename T >
uintc mazematrixD2<T>::add()  
{
  assert(dim[0]*dim[1]!=0); // dimset must be called

  uint k=vi.size();
  cellD2<T> x;
  x.id=k;
  vi.push_back(x);

  return k;
}


template< typename T >
mazematrixD2<T>::mazematrixD2(uintc rows, uintc columns)
{
  dimset(rows,columns);
}


template< typename T >
mazematrixD2<T>::mazematrixD2()
{
  dim[0]=0;
  dim[1]=0;
  dim[2]=0;
}

template< typename T >
T mazematrixD2<T>::neib(T id, uintc k) const
{
  assert(id!=0);
  assert(id<=dim[2]);
  assert(k<4);

  uint n=dim[1];

  // Up.
  if (k==0)
  {
    if (id<=n)
      return 0;
    return id-n;
  }

  // Down.
  if (k==2)
  {
    if (id+n>dim[2])
      return 0;
    return id+n;
  }

  // Right.
  if (k==1)
  {
    if ((id%n)==0)
      return 0;

    return id+1;
  }
 
  // Left.
  if (k==3)
  {
    if (((id+n-1)%n)==0)
      return 0;

    return id-1;
  }

  assert(false);

  return 0;
}

template< typename T >
void mazematrixD2<T>::link( T id, uintc k, T id2)
{
  assert(dim[0]*dim[1]!=0); // dimset must be called
  assert(k<4);
  assert(id!=0);
  assert(id2!=0);
  //assert(id<=dim[2]);
  //assert(id2<=dim[2]);

  uint k2=(k+2)%4;

  vi[id].ni[k] = id2;
  vi[id2].ni[k2] = id;
}


template< typename T >
void mazematrixD2<T>::link( T id, uintc k, T id2, uintc k2)
{
  assert(dim[0]*dim[1]!=0); // dimset must be called
  assert(k<4);
  assert(k2<4);
  assert(id!=0);
  assert(id2!=0);

  vi[id].ni[k] = id2;
  vi[id2].ni[k2] = id;
}

template< typename T >
boolc mazematrixD2<T>::valid() const
{
  assert(dim[0]*dim[1]!=0); // dimset must be called
  if (dim[0]*dim[1]==0)
    return false;

  uint imax=vi.size();
  T nb;
  T nb2local;
  for (uint i=1; i<imax; ++i)
  {
//    cout << "error: " << (string)vi[i] << endl;

    assert(!(vi[i].id!=i));
    if (vi[i].id!=i)
      return false;

    for (uint k=0; k<4; ++k)
    {
//cout << SHOW(k) << endl;
      nb=vi[i].ni[k];
//cout << SHOW(nb) << endl;
      if (nb!=0)
      {
        assert(!(nb>=imax));
        if (nb>=imax)
          return false;

        nb2local = vi[nb].niInv(i);
        assert(!(nb2local==4));
        if (nb2local==4)
          return false;
        assert(!(vi[nb].ni[nb2local]!=i));
        if (vi[nb].ni[nb2local]!=i)
          return false;
      }
    }

  } 

  return true;
}

template< typename T >
void mazematrixD2<T>::move
(
  bool & res, 
  T& k2, 
  uintc mv, 
  T const k
) const
{
  uintc m=dim[0];
  uintc n=dim[1];

  assert(mv<4);

  if (mv==3)
  {
    res=(((k-1)%n)!=0);
    k2=k-1;
    return;
  }

  if (mv==1)
  {
    res=((k%n)!=0);
    k2=k+1;
    return;
  }

  if (mv==0)
  {
    res=(k>n);
    k2=k-n;
    return;
  }

  if (mv==2)
  {
    res=((k+n-1)<m*n);
    k2=k+n;
    return;
  }


/*

  // Shift so counting from 0.
  // I could easily put the substitutions in, but
  // that would make the code less clear.
  T w = k-1;
  
  if (mv==3)
  {
    res=((w%n)!=0);
    k2=w-1;
    ++k2;
    return;
  }

  if (mv==1)
  {
    res=(((w+n-1)%n)!=0);
    k2=w+1;
    ++k2;
    return;
  }

  if (mv==0)
  {
    res=(w>=n);
    k2=w-n;
    ++k2;
    return;
  }

  if (mv==2)
  {
    res=((w+n)<m*n);
    k2=w+n;
    ++k2;
    return;
  }
*/


}

template< typename T >
void mazematrixD2<T>::neighboursunvisited
( 
  vector<T> & v, 
  T const k
)
{
//cout << SHOW(k) << endl;
  v.clear();
  bool res;
  T k2;
  for (uint i=0; i<4; ++i)
  {
    move(res,k2,i,k);
//cout << SHOW(k2) << endl;
    if (res)
    {
      if (vi[k2].unvisited())
        v.push_back(k2);
    }
  }
}

template< typename T >
void mazematrixD2<T>::linkadjacent
(
  bool & res, 
  T const id1, 
  T const id2
)
{
  res=false;

  if (id1==id2)
    return;

  T a;
  T b;

  if (id1<id2)
    { a=id1; b=id2; }
  else
    { a=id2; b=id1; };

  // Horizontal linkage
  if (a+1==b)
  {
    link(a,1,b,3);  
    res=true;
    return;
  }

  // Vertical linkage
  if (a+dim[1]==b)
  {
    link(a,2,b,0);
    res=true;
    return;
  }
}


template< typename T >
mazematrixD2<T>::operator stringc () const
{
  string s1="<mazematrixD2>\n";
  s1 += "<dim>";
  s1 += stringto(dim[0]);
  s1 += " ";
  s1 += stringto(dim[1]);
  s1 += "</dim>\n";
  s1 += stringtag(vi.size(),"visize");
  s1 += "<vi>\n";
  for (uint i=0; i<vi.size(); ++i)
  {
    s1 += (stringc)vi[i];
    s1 += " \n";
  }
  
  s1 += "</vi>\n";
  s1 += "</mazematrixD2>\n";
  
  return s1;
}


template< typename T >
void mazematrixD2<T>::serializeInverse(stringc & str)
{
  string s2(stringtagparser(str).data("mazematrixD2"));

  { 
    stringstream ss(stringtagparser(s2).data("dim")); 
    ss >> dim[0] >> dim[1];
    dim[2]=dim[0]*dim[1];
  }

  T n;
  stringfrom(n,stringtagparser(s2).data("visize"));
  {
    vi.resize(n);
    stringstream ss(stringtagparser(s2).data("vi"));
    for (T i=0; i<n; ++i)
    {
      vi[i].serializeInverse(ss); 
    }
  }

}


#endif