#ifndef MAZEMATRIXD2CREATEMAZE_H
#define MAZEMATRIXD2CREATEMAZE_H

#include <queue>
using namespace std;

#include <mazematrixD2.h>
#include <point.h>
#include <random.h>


/*!
\brief Create maze given mazematrixD2 data structure.
*/
template< typename T >
class mazematrixD2createmaze
{
public:

  /** Maze data structure. */
  mazematrixD2<T> & mz;

  /** Process queue where from and to links are added.*/
  deque< point2<T> > process;

  /** Constructor. */
  mazematrixD2createmaze(mazematrixD2<T> & mz_)
    : mz(mz_) {}

  /** Build the maze, the data structure holds the dimensions. */
  void buildpropermaze();

  /** Given maze, visit each cell and randomly delete walls on delwall ratio. */
  void impropermaze01(doublec deletewall);

};


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


template< typename T >
void mazematrixD2createmaze<T>::buildpropermaze()
{
  T m=mz.dim[0];
  T n=mz.dim[1];

  T i;
  T j;

  i=1+(rand()%(m*n));

  process.clear();
  vector< T > unvisited;

  mz.neighboursunvisited(unvisited,i);
  random_shuffle(unvisited.begin(),unvisited.end());
  assert(unvisited.size()!=0);
  process.push_back( point2<T>(i,unvisited[0]) );

  point2<T> current;

  bool res;
  for ( ; !process.empty(); )
  {
    current = process.front();
    process.pop_front();

    i = current.x;
    j = current.y;
//cout << "(" << i << "," << j << ")" << endl;

    if (mz.vi[j].unvisited())
    {
      mz.linkadjacent(res,i,j);
      assert(res);

      mz.neighboursunvisited(unvisited,j);
      random_shuffle(unvisited.begin(),unvisited.end());

/*
cout << j << ": ";
for (uint k=0; k<unvisited.size(); ++k)
  cout << unvisited[k] << " ";
cout << endl;
*/

      //random_shuffle(unvisited.begin(),unvisited.end());
      if (unvisited.size()!=0)
      {
        process.push_front( point2<T>(j,unvisited[0]) );
        for (uint k=1; k<unvisited.size(); ++k)
          process.push_back( point2<T>(j,unvisited[k]) );
      }
    }

/*
cout << "process: ";
typename deque< point2<T> >::iterator i2;
i2=process.begin();
for ( ; i2!=process.end(); ++i2)
  cout << *i2 << " ";
cout << endl;
*/

  }

}


template< typename T >
void mazematrixD2createmaze<T>::impropermaze01(doublec deletewall)
{
  assert(deletewall<1.0);
  assert(deletewall >= 0.0);

  T m=mz.dim[0];
  T n=mz.dim[1];
  T mn=m*n;

  vector<T> ki(mn);

  for (T i=0; i<mn; ++i)
    ki[i]=i+1;

  // Help randomize things a bit, may not matter.
  random_shuffle(ki.begin(),ki.end());

  T k2;
  bool res;
 
  random11<> r;

  for (T i=0; i<mn; ++i)
  {

    for (uint j=0; j<4; ++j)
    {
      if (mz.vi[ki[i]].ni[j]!=0)
        continue;

      mz.move(res,k2,j,ki[i]);
      if (res==false)
        continue;
      
      if (r()<deletewall)
      {
        mz.linkadjacent(res,k2,ki[i]);
        assert(res==true);
      }
    }
  }
}




#endif