mazematrixD3< T > Class Template Reference

Linked square cell structure. More...

#include <mazematrixD3.h>

Collaboration diagram for mazematrixD3< T >:

List of all members.

Public Member Functions
void	dimset (uintc rows, uintc columns, uintc depth)
	Set the maze dimensions.
	mazematrixD3 ()
	Uninitialized state.
	mazematrixD3 (uintc rows, uintc columns, uintc depth)
	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.
cellD3< T > &	access (uintc r, uintc c, uintc depth)
	Interpret and access as a 2D matrix.
void	access (bool &res, cellD3< 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.
Public Attributes
uint	dim [4]
	Rows, columns, depth dimensions and total number of cells.
vector< cellD3< T > >	vi
	The first cell is ignored as it is zero/no cell.

---

Detailed Description

template<typename T>
class mazematrixD3< 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, 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.

Definition at line 36 of file mazematrixD3.h.

---

Constructor & Destructor Documentation

template<typename T >

mazematrixD3< T >::mazematrixD3

(

)

[inline]

Uninitialized state.

Definition at line 140 of file mazematrixD3.h.

References mazematrixD3< T >::dim.

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

template<typename T >

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

Build non connected matrix.

Definition at line 133 of file mazematrixD3.h.

References mazematrixD3< T >::dimset().

{
  dimset(rows,columns,depth);
}

---

Member Function Documentation

template<typename T>

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

Access outside the range will fail.

Definition at line 75 of file mazematrixD3.h.

References mazematrixD3< T >::dim, and mazematrixD3< 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>

cellD3<T>& mazematrixD3< T >::access	(	uintc	r,
		uintc	c,
		uintc	depth
	)			[inline]

Interpret and access as a 2D matrix.

Definition at line 71 of file mazematrixD3.h.

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

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

template<typename T >

uintc mazematrixD3< T >::add

(

)

[inline]

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

Definition at line 119 of file mazematrixD3.h.

References mazematrixD3< T >::dim, cellD3< T >::id, and mazematrixD3< T >::vi.

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

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

Set the maze dimensions.

Definition at line 105 of file mazematrixD3.h.

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

Referenced by mazematrixD3< T >::mazematrixD3().

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

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

Link two neighbours.

Definition at line 239 of file mazematrixD3.h.

References assertreturn, mazematrixD3< T >::dim, and mazematrixD3< T >::vi.

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

void mazematrixD3< 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 215 of file mazematrixD3.h.

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

Referenced by mazematrixD3test::test01(), and mazematrixD3test::test02().

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

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

Definition at line 370 of file mazematrixD3.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 mazematrixD3< 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 287 of file mazematrixD3.h.

Referenced by mazematrixD3test::test03().

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

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

Access neighbours id.

Definition at line 149 of file mazematrixD3.h.

References mazematrixD3< T >::dim.

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

Looks for unvisited neighbours.

Definition at line 347 of file mazematrixD3.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 >

boolc mazematrixD3< T >::valid

(

)

const [inline]

Iterate over cells except 0, checking double linkage.

Definition at line 252 of file mazematrixD3.h.

References assertreturnfalse, mazematrixD3< T >::dim, and mazematrixD3< T >::vi.

Referenced by mazematrixD3test::test01(), and mazematrixD3test::test02().

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

---

Member Data Documentation

template<typename T>

uint mazematrixD3< T >::dim[4]

Rows, columns, depth dimensions and total number of cells.

Definition at line 41 of file mazematrixD3.h.

Referenced by mazematrixD3< T >::access(), mazematrixD3< T >::add(), mazematrixD3< T >::dimset(), mazematrixD3< T >::link(), mazematrixD3< T >::mazematrixD3(), mazematrixD3< T >::neib(), and mazematrixD3< T >::valid().

template<typename T>

vector< cellD3<T> > mazematrixD3< T >::vi

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

Definition at line 47 of file mazematrixD3.h.

Referenced by mazematrixD3< T >::access(), mazematrixD3< T >::add(), mazematrixD3< T >::dimset(), mazematrixD3< T >::link(), and mazematrixD3< T >::valid().

---

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

• maze/mazematrixD3.h