#ifndef MAZEMATRIXD3_H
#define MAZEMATRIXD3_H

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

#include <cellD3.h>
#include <print.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, 4 is front, 5 is back.

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 mazematrixD3
{
public:

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

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

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

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

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

  /** 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. */
  cellD3<T> & access(uintc r, uintc c, uintc depth) 
    { return vi[c+r*dim[0]+depth*dim[0]*dim[1]+1]; }

  /** Access outside the range will fail. */
  void access(bool & res, cellD3<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;
      }
    }
  }

  /** 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);

};


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

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

  vi.resize(dim[3]+1);
  for (T i=0; i<vi.size(); ++i)
    vi[i].id=i;
}


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

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

  return k;
}


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


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

template< typename T >
T mazematrixD3<T>::neib(T id, uintc k) const
{
  assert(id!=0);
  assert(id<=dim[3]);
  assert(k<6);

  uint m=dim[0];
  uint n=dim[1];

  uint mn=m*n;
  T w=(id-1)%mn;

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

  // Down.
  if (k==2)
  {
    if (w+n>mn)
      return 0;
    return id+n;
  }

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

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

    return id-1;
  }

  // Forward 
  if (k==4)
  {
    if (id-1+mn>=mn*dim[2])
      return 0;
    return id+mn;
  }

  // Back
  if (k==5)
  {
    if (id-1<mn)
      return 0;
    return id-mn;
  }

  return 0;
}

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

  uint k2;
  switch (k)
  {
    case 0: k2=2; break;
    case 1: k2=3; break;
    case 2: k2=0; break;
    case 3: k2=1; break;
    case 4: k2=5; break;
    case 5: k2=4; break;
  }

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


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

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

template< typename T >
boolc mazematrixD3<T>::valid() const
{
  assertreturnfalse(dim[0]*dim[1]*dim[2]!=0); // dimset must be called

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

    assertreturnfalse(!(vi[i].id!=i));

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

        nb2local = vi[nb].niInv(i);
        assertreturnfalse(!(nb2local==6));
        assertreturnfalse(!(vi[nb].ni[nb2local]!=i));
      }
    }

  } 

  return true;
}

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

  assert(mv<6);

  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)
  {
    uint i = (k-1)%(m*n);
    res=(i>=n);
    k2=k-n;
    return;
  }

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

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

  if (mv==5)
  {
    res=(k-1>m*n);
    k2=k-m*n;
    return;
  }
}

template< typename T >
void mazematrixD3<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 mazematrixD3<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;
  }
}



#endif