#ifndef MAZEMATRIXMAPD2_H
#define MAZEMATRIXMAPD2_H

#include <deque>
#include <map>
using namespace std;

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

/*!
\brief Build a map relative to a cell. 

This is an iterator, where the cells neighbours are interpreted from
 top in a clockwise direction.  The change is added and subtracted
 when a link is transversed.

Two types of iteration - map iteration and movement.
*/
template< typename T, typename W >
class mazematrixmapD2
{
public:

  typedef map< T, point2<W> > mapping;
  typedef typename mapping::iterator mappingiterator;

  /** Index to point mapping. */
  mapping ipt;
  /** Actual iterator used. */
  mappingiterator iter;
  /** Origin cell. */
  T zeroindex;

  /** Data structure which a map relative to a cell is created. */
  mazematrixD2<T> & mz;

  /** Change in x. */
  W dx;
  /** Change in y. */
  W dy;

  /** Create a new map from ith cell as zero (0,0). */ 
  void relativeto(T i); 

  /** Build the map, called after reset(i); */
  void eval(); 

  /** Set the change relative to positive x and positive y axes. */
  void changeSet(W dx_, W dy_)
    { dx=dx_; dy=dy_; }

  /** Constructor. */
  mazematrixmapD2( mazematrixD2<T> & mz_, W dx_, W dy_ )
    : zeroindex(0), mz(mz_)
    { changeSet(dx_,dy_); }

  /** Reset the iterator. */
  void reset()
    { iter=ipt.begin(); }

  /** Access the current index. */
  T currentIndex()
    { return (*iter).first; }
  /** Access the current cell. */
  cellD2<T>& currentCell()
    { return mz.vi[(*iter).first]; }
  /** Access the current position. */
  point2<W>& currentPosition()
    { return (*iter).second; }
  
  /** Is this iterator valid? */
  boolc operator ! () 
    { return iter != ipt.end(); } 
  /** Increment iterator. */
  void operator ++()
    { ++iter; }
  
  /** The id must already be in the map ipt. */
  boolc add( T id );

};



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

template< typename T, typename W >
void mazematrixmapD2<T,W>::relativeto(T i)
{
  ipt.clear();
  assert(i<mz.vi.size());
  cellD2<T> & x = mz.vi[i];
  ipt.insert( make_pair(x.id,point2<W>(0,0)) ); 

  zeroindex=i;
}

template< typename T, typename W >
void mazematrixmapD2<T,W>::eval()
{
  iter = ipt.begin();
  cellD2<T>& x(currentCell());

  deque<T> process;
  process.push_back(x.id);
/*
  for (uint k=0; k<4; ++k)
  {
    if (x.ni[k]!=0)
      process.push_back(x.ni[k]);
  }
*/

  T id;
  for ( ; ! process.empty(); )
  {
    id = process.front();
//cout << SHOW(id) << endl;
    process.pop_front();

    assert(id < mz.vi.size());

    cellD2<T>& x2(mz.vi[id]);

    for (uint k=0; k<4; ++k)
    {
      if (x2.ni[k]!=0)
      {
        if (ipt.find(x2.ni[k])==ipt.end())
          process.push_back(x2.ni[k]);
      }
    }

    add(id);
  }
  
}

template< typename T, typename W >
boolc mazematrixmapD2<T,W>::add(T id)
{
  assert(id!=0);
  assert(id<mz.vi.size());

  if (id==0)
    return false;
  if (id >= mz.vi.size())
    return false;

  iter = ipt.find(id); 

  assert(iter!=ipt.end());
  if (iter==ipt.end())
    return false;
  
  point2<W> k((*iter).second);

  // Assume uniqueness of cells. 

  mappingiterator i2;
  cellD2<T> & x(mz.vi[id]);

  if (x.ni[0]!=0)
  {
    i2=ipt.find(x.ni[0]);
    if (i2==ipt.end())
    {
      ipt.insert( make_pair(x.ni[0],point2<W>(k.x,k.y+dy)) );
    }
  }

  if (x.ni[2]!=0)
  {
    i2=ipt.find(x.ni[2]);
    if (i2==ipt.end())
    {
      ipt.insert( make_pair(x.ni[2],point2<W>(k.x,k.y-dy)) );
    }
  }

  if (x.ni[1]!=0)
  {
    i2=ipt.find(x.ni[1]);
    if (i2==ipt.end())
    {
      ipt.insert( make_pair(x.ni[1],point2<W>(k.x+dx,k.y)) );
    }
  }

  if (x.ni[3]!=0)
  {
    i2=ipt.find(x.ni[3]);
    if (i2==ipt.end())
    {
      ipt.insert( make_pair(x.ni[3],point2<W>(k.x-dx,k.y)) );
    }
  }

  return true;
}


/*
template< typename T >
uint mazematrixmapD2<W>::indexInv( point2<W> const & x ) const
{
  uint imax=index.size();
  for (uint i=0; i<imax; ++i)
  {
    if (index[i]==x)
      return i;
  }

  return 0;
}
*/


#endif