mazematrixD2< T > Class Template Reference

Linked square cell structure. More...

#include <mazematrixD2.h>

Inheritance diagram for mazematrixD2< T >:

Collaboration diagram for mazematrixD2< T >:

List of all members.

Public Member Functions
void	dimset (uintc rows, uintc columns)
	Set the maze dimensions.
	mazematrixD2 ()
	Uninitialized state.
	mazematrixD2 (uintc rows, uintc columns)
	Build non connected matrix.
uintc	add ()
	Pushes a new cell onto vi, assigning it an id.
T	neib (T id, uintc k) const
	Access neighbours id.
void	link (T id, uintc k, T id2)
	Link two adjacent neighbours, k is id's local ni position pointing to id2.
void	link (T id, uintc k, T id2, uintc k2)
	Link two neighbours.
boolc	valid () const
	Iterate over cells except 0, checking double linkage.
cellD2< T > &	access (uintc r, uintc c)
	Interpret and access as a 2D matrix.
void	access (bool &res, cellD2< T > &x, uintc r, uintc c)
	Access outside the range will fail.
void	move (bool &res, T &k2, uintc mv, T const k) const
	Given position k and direction mv it may be possible to move to k2.
void	neighboursunvisited (vector< T > &v, T const k)
	Looks for unvisited neighbours.
void	linkadjacent (bool &res, T const id1, T const id2)
	Given id's if these cells next to eachother link them.
	operator stringc () const
	Serialize object.
void	serializeInverse (stringc &str)
	Construct object from string.
Public Attributes
uint	dim [3]
	Rows and columns dimensions and total number of cells.
vector< cellD2< T > >	vi
	The first cell is ignored as it is zero/no cell.

---

Detailed Description

template<typename T>
class mazematrixD2< T >

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.

Definition at line 38 of file mazematrixD2.h.

---

Constructor & Destructor Documentation

template<typename T >

mazematrixD2< T >::mazematrixD2

(

)

[inline]

Uninitialized state.

Definition at line 151 of file mazematrixD2.h.

References mazematrixD2< T >::dim.

{
  dim[0]=0;
  dim[1]=0;
  dim[2]=0;
}

template<typename T >

mazematrixD2< T >::mazematrixD2	(	uintc	rows,
		uintc	columns
	)			[inline]

Build non connected matrix.

Definition at line 144 of file mazematrixD2.h.

References mazematrixD2< T >::dimset().

{
  dimset(rows,columns);
}

---

Member Function Documentation

template<typename T>

void mazematrixD2< T >::access	(	bool &	res,
		cellD2< T > &	x,
		uintc	r,
		uintc	c
	)			[inline]

Access outside the range will fail.

Definition at line 102 of file mazematrixD2.h.

References mazematrixD2< T >::dim, and mazematrixD2< T >::vi.

{
  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>

cellD2<T>& mazematrixD2< T >::access	(	uintc	r,
		uintc	c
	)			[inline]

Interpret and access as a 2D matrix.

Definition at line 73 of file mazematrixD2.h.

    { return vi[c+r*dim[0]+1]; }

template<typename T >

uintc mazematrixD2< T >::add

(

)

[inline]

Pushes a new cell onto vi, assigning it an id.

Definition at line 130 of file mazematrixD2.h.

References mazematrixD2< T >::dim, cellD2< T >::id, and mazematrixD2< T >::vi.

Referenced by maze001::maze001(), maze002::maze002(), mazematrixD2test::test01(), mazematrixD2test::test02(), and mazematrixD2test::unittest01().

{
  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 >

void mazematrixD2< T >::dimset	(	uintc	rows,
		uintc	columns
	)			[inline]

Set the maze dimensions.

Definition at line 117 of file mazematrixD2.h.

References mazematrixD2< T >::dim, and mazematrixD2< T >::vi.

Referenced by mazegameD2state01::game01(), and mazematrixD2< T >::mazematrixD2().

{
  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>

void mazematrixD2< T >::link	(	T	id,
		uintc	k,
		T	id2,
		uintc	k2
	)			[inline]

Link two neighbours.

Definition at line 224 of file mazematrixD2.h.

References mazematrixD2< T >::dim, and mazematrixD2< T >::vi.

{
  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>

void mazematrixD2< T >::link	(	T	id,
		uintc	k,
		T	id2
	)			[inline]

Link two adjacent neighbours, k is id's local ni position pointing to id2.

Definition at line 207 of file mazematrixD2.h.

References mazematrixD2< T >::dim, and mazematrixD2< T >::vi.

Referenced by maze001::maze001(), maze002::maze002(), mazematrixD2test::test01(), mazematrixD2test::test02(), and mazematrixD2test::unittest01().

{
  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 >::linkadjacent	(	bool &	res,
		T const	id1,
		T const	id2
	)			[inline]

Given id's if these cells next to eachother link them.

Definition at line 391 of file mazematrixD2.h.

{
  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>

void mazematrixD2< T >::move	(	bool &	res,
		T &	k2,
		uintc	mv,
		T const	k
	)			const [inline]

Given position k and direction mv it may be possible to move to k2.

Definition at line 282 of file mazematrixD2.h.

{
  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>

T mazematrixD2< T >::neib	(	T	id,
		uintc	k
	)			const [inline]

Access neighbours id.

Definition at line 159 of file mazematrixD2.h.

References mazematrixD2< T >::dim.

{
  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 >::neighboursunvisited	(	vector< T > &	v,
		T const	k
	)			[inline]

Looks for unvisited neighbours.

Definition at line 368 of file mazematrixD2.h.

{
//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 >

mazematrixD2< T >::operator stringc

(

)

const [inline]

Serialize object.

Definition at line 429 of file mazematrixD2.h.

References mazematrixD2< T >::dim, stringtag(), stringto(), and mazematrixD2< T >::vi.

{
  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

)

[inline]

Construct object from string.

Definition at line 453 of file mazematrixD2.h.

References mazematrixD2< T >::dim, stringfrom(), and mazematrixD2< T >::vi.

Referenced by mazegameD2state01::serializeInverse(), and mazematrixD2test::unittest02().

{
  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); 
    }
  }

}

template<typename T >

boolc mazematrixD2< T >::valid

(

)

const [inline]

Iterate over cells except 0, checking double linkage.

Definition at line 237 of file mazematrixD2.h.

References mazematrixD2< T >::dim, and mazematrixD2< T >::vi.

Referenced by mazedisp02::draw(), mazedisp01::draw(), maze001::maze001(), maze002::maze002(), maze003::maze003(), mazedisp03::staticgraphics(), mazematrixD2test::test01(), mazematrixD2test::test02(), mazematrixD2test::unittest01(), and mazegameD2state01::valid().

{
  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;
}

---

Member Data Documentation

template<typename T>

uint mazematrixD2< T >::dim[3]

Rows and columns dimensions and total number of cells.

Definition at line 43 of file mazematrixD2.h.

Referenced by mazematrixD2< T >::access(), mazematrixD2< uint >::access(), mazematrixD2< T >::add(), mazedisp03::cellmidpoint(), mazematrixD2< T >::dimset(), mazedisp02::draw(), mazematrixD2< T >::link(), mazematrixD2< T >::mazematrixD2(), mazematrixD2< T >::neib(), mazematrixD2< T >::operator stringc(), mazematrixD2< T >::serializeInverse(), mazedisp03::staticgraphics(), mazematrixD2< T >::valid(), and mazegameD2state01::valid().

template<typename T>

vector< cellD2<T> > mazematrixD2< T >::vi

The first cell is ignored as it is zero/no cell.

Definition at line 49 of file mazematrixD2.h.

Referenced by mazematrixD2< T >::access(), mazematrixD2< uint >::access(), mazematrixD2< T >::add(), maze001::constructgraphics(), mazegameD2state01::currentmove(), mazematrixD2< T >::dimset(), mazedisp02::draw(), mazedisp01::draw(), mazematrixD2< T >::link(), mazematrixD2< T >::operator stringc(), mazematrixD2< T >::serializeInverse(), mazedisp03::staticgraphics(), mazematrixD2test::test01(), mazematrixD2test::test02(), mazematrixD2test::unittest01(), and mazematrixD2< T >::valid().

---

The documentation for this class was generated from the following file:

• maze/mazematrixD2.h