treeindexedD2< INDX > Class Template Reference

Binary tree with state. More...

#include <treeindexedD2.h>

Inheritance diagram for treeindexedD2< INDX >:

Collaboration diagram for treeindexedD2< INDX >:

List of all members.

Public Member Functions
void	construct ()
	Build the initial tree with root and two leafs.
	treeindexedD2 ()
	Set the counters with a value 1.
	~treeindexedD2 ()
	Memory cleanup.
void	reset ()
	Set current to top of tree.
boolc	operator! () const
	Is iteration possible?
treeindexedD2node< INDX > *	operator() ()
	Access the current node.
void	moveleft ()
	Move the current node left.
void	moveright ()
	Move the current node right.
void	move (INDX const bpath, INDX const bitlength)
	Move along a path.
template<typename W >
void	pathindex (W &container, INDX const bpath, INDX const bitlength)
	Print the tree as a tree in text.
void	addleft ()
	Assuming the current node is an internal node ( has two leafs), add a new node left.
void	addright ()
	At the current node add a new node right.
	operator stringc () const
	Serialize this object by writing it out as a string.
istream &	serializeInverse (istream &istr)
	Inverse of string serialization.
void	insert (bool &found, treeindexedD2node< INDX > &curr, treeindexedD2noderep< INDX > const &ndrep)
	Set found to false before use as this is recursive.
void	addroot (treeindexedD2noderep< INDX > const &ndrep)
	The first node inserted into the tree.
Public Attributes
INDX	nodecounter
	As nodes are created this index increases and assigns indexes to the new nodes.
INDX	regioncounter
	As regions are created this index increases and assignes indexes to the new regions.
treeindexedD2node< INDX > *	root
	The top node.
treeindexedD2node< INDX > *	current
	Current node.

---

Detailed Description

template<typename INDX>
class treeindexedD2< INDX >

Binary tree with state.

treeindexedD2 and treeindexedD2node are coupled, with functionality in whatever was convenient.

The tree has nodes and leafs. By design a node is locally balanced having a left and right node or leaf.

Definition at line 28 of file treeindexedD2.h.

---

Constructor & Destructor Documentation

template<typename INDX >

treeindexedD2< INDX >::treeindexedD2

(

)

[inline]

Set the counters with a value 1.

Build the root node and two leafs.

Definition at line 286 of file treeindexedD2.h.

References treeindexedD2< INDX >::construct().

  : nodecounter(0), regioncounter(0), root(0), current(0) 
{ 
  construct(); 
}

template<typename INDX >

treeindexedD2< INDX >::~treeindexedD2

(

)

[inline]

Memory cleanup.

Definition at line 260 of file treeindexedD2.h.

References treeindexedD2< INDX >::root.

{ 
  delete root; 
}

---

Member Function Documentation

template<typename INDX >

void treeindexedD2< INDX >::addleft

(

)

[inline]

Assuming the current node is an internal node ( has two leafs), add a new node left.

Definition at line 470 of file treeindexedD2.h.

References treeindexedD2< INDX >::current, treeindexedD2< INDX >::nodecounter, and treeindexedD2< INDX >::regioncounter.

Referenced by treeindexedD2test::test01(), treeindexedD2test::test02(), treeindexedD2test::test03(), and treeindexedD2test::unittest02().

{
  assert(current!=0); 
  // Balanced node.
  assert(current->left!=0); 
  assert(current->right!=0); 

  // left is a leaf.
  assert(current->isleaf()==false);
  assert(current->left->isleaf()==true);

  treeindexedD2node<INDX> * q = 
    new treeindexedD2node<INDX>(regioncounter++);
  treeindexedD2node<INDX> * p2 = 
    new treeindexedD2node<INDX>(current->left,q,nodecounter++);
  current->left = p2;
}

template<typename INDX >

void treeindexedD2< INDX >::addright

(

)

[inline]

At the current node add a new node right.

It is assumed that the current node has two leafs.

Definition at line 451 of file treeindexedD2.h.

References treeindexedD2< INDX >::current, treeindexedD2< INDX >::nodecounter, and treeindexedD2< INDX >::regioncounter.

Referenced by treeindexedD2test::test01(), treeindexedD2test::test02(), treeindexedD2test::test03(), and treeindexedD2test::unittest02().

{
  assert(current!=0); 
  // Balanced node.
  assert(current->left!=0); 
  assert(current->right!=0); 

  // right is a leaf.
  assert(current->isleaf()==false);
  assert(current->right->isleaf()==true);

  treeindexedD2node<INDX> * q = 
    new treeindexedD2node<INDX>(regioncounter++);
  treeindexedD2node<INDX> * p2 = 
    new treeindexedD2node<INDX>(current->right,q,nodecounter++);
  current->right = p2;
}

template<typename INDX>

void treeindexedD2< INDX >::addroot

(

treeindexedD2noderep< INDX > const &

ndrep

)

[inline]

The first node inserted into the tree.

Definition at line 338 of file treeindexedD2.h.

References treeindexedD2noderep< INDX >::nd.

Referenced by treeindexedD2< INDX >::serializeInverse().

{
  assert(root==0);

  root        = new treeindexedD2node<INDX>(ndrep.nd[0]);
  root->left  = new treeindexedD2node<INDX>(ndrep.nd[1]);
  root->right = new treeindexedD2node<INDX>(ndrep.nd[2]);

  current=root;
}

template<typename INDX >

void treeindexedD2< INDX >::construct

(

)

[inline]

Build the initial tree with root and two leafs.

Definition at line 513 of file treeindexedD2.h.

References treeindexedD2< INDX >::current, treeindexedD2< INDX >::nodecounter, treeindexedD2< INDX >::regioncounter, and treeindexedD2< INDX >::root.

Referenced by treeindexedD2< INDX >::treeindexedD2().

{
  nodecounter=1;
  regioncounter=1;

  delete root;

  root        = new treeindexedD2node<INDX>(nodecounter++);
  assert(root!=0);
  root->left  = new treeindexedD2node<INDX>(regioncounter++);
  root->right = new treeindexedD2node<INDX>(regioncounter++);
  current=root;
}

template<typename INDX>

void treeindexedD2< INDX >::insert	(	bool &	found,
		treeindexedD2node< INDX > &	curr,
		treeindexedD2noderep< INDX > const &	ndrep
	)			[inline]

Set found to false before use as this is recursive.

The root node must be inserted before use.

Definition at line 353 of file treeindexedD2.h.

References treeindexedD2noderep< INDX >::branch, treeindexedD2node< INDX >::index, treeindexedD2node< INDX >::isleaf(), treeindexedD2node< INDX >::left, treeindexedD2noderep< INDX >::nd, and treeindexedD2node< INDX >::right.

Referenced by treeindexedD2< INDX >::serializeInverse().

{
  // Only insert one node.
  if (found)
    return;

  // Is the current index the parent of the target node?
  if (curr.index != ndrep.nd[3])
  {
    if (curr.left!=0)
      insert(found,*curr.left,ndrep);
    if (curr.right!=0)
      insert(found,*curr.right,ndrep);

    return;
  }

  treeindexedD2node<INDX> * curr2;
  
  // Meet insertion condtions.  
  curr2 = curr.left;
  if ( (ndrep.branch==false) && (curr2!=0) )
  {
    if (curr2->isleaf())
    {
      if (curr2->index==ndrep.nd[0])
      {
        found = true;

        curr2->left  = new treeindexedD2node<INDX>(ndrep.nd[1]);
        curr2->right = new treeindexedD2node<INDX>(ndrep.nd[2]);

        return;
      }
    }
  }

  curr2 = curr.right;
  if ( (ndrep.branch==true) && (curr2!=0) )
  {
    if (curr2->isleaf())
    {
      if (curr2->index==ndrep.nd[0])
      {
        found = true;

        curr2->left  = new treeindexedD2node<INDX>(ndrep.nd[1]);
        curr2->right = new treeindexedD2node<INDX>(ndrep.nd[2]);

        return;
      }
    }
  }
}

template<typename INDX>

void treeindexedD2< INDX >::move	(	INDX const	bpath,
		INDX const	bitlength
	)			[inline]

Move along a path.

For example move(0*1+1*2+0*4,3) is move left, right, left.

Definition at line 311 of file treeindexedD2.h.

References treeindexedD2< INDX >::moveleft(), treeindexedD2< INDX >::moveright(), and treeindexedD2< INDX >::reset().

Referenced by treeindexedD2test::unittest04().

{
  reset();

//cout << SHOW(current->index) << endl;

  INDX u(bpath);
//cout << SHOW(bpath) << endl;
//cout << SHOW(bitlength) << endl;

  bool branch;
  for (INDX i=0; i<bitlength; ++i)
  {
    branch=(u%2);
//cout << SHOW(u) << "  " << SHOW(branch) << endl;
    u = (u >> 1);
 
    if (branch==false)
      moveleft();
    else
      moveright();
  }
}

template<typename INDX >

void treeindexedD2< INDX >::moveleft

(

)

[inline]

Move the current node left.

Definition at line 293 of file treeindexedD2.h.

References treeindexedD2< INDX >::current, and treeindexedD2< INDX >::root.

Referenced by bsptreeD2find< PT, PD, INDX >::find(), treeindexedD2< INDX >::move(), and treeindexedD2test::test02().

{ 
  assert(root!=0);
  assert(current!=0); 
  assert(current->left!=0); 
  current = current->left;
}

template<typename INDX >

void treeindexedD2< INDX >::moveright

(

)

[inline]

Move the current node right.

Definition at line 302 of file treeindexedD2.h.

References treeindexedD2< INDX >::current, and treeindexedD2< INDX >::root.

Referenced by bsptreeD2find< PT, PD, INDX >::find(), treeindexedD2< INDX >::move(), treeindexedD2test::test03(), and treeindexedD2test::unittest02().

{ 
  assert(root!=0);
  assert(current!=0); 
  assert(current->right!=0); 
  current = current->right;
}

template<typename INDX >

treeindexedD2< INDX >::operator stringc

(

)

const [inline]

Serialize this object by writing it out as a string.

Definition at line 489 of file treeindexedD2.h.

References treeindexedD2< INDX >::root.

{
  string s;

  if (root==0)
  {
    s += "0";
    return s;
  }

  INDX count(0);
  root->nodecount(count);
  stringstream ss;
  ss << count;
  s += ss.str();
  s += "\n";

  root->printrecursive(s,0,false);
  
  return s;
}

template<typename INDX >

boolc treeindexedD2< INDX >::operator!

(

)

const [inline]

Is iteration possible?

Definition at line 272 of file treeindexedD2.h.

References treeindexedD2< INDX >::current.

{ 
  return current!=0; 
}

template<typename INDX >

treeindexedD2node< INDX > * treeindexedD2< INDX >::operator()

(

)

[inline]

Access the current node.

Definition at line 278 of file treeindexedD2.h.

References treeindexedD2< INDX >::current.

{ 
  assert(current!=0); 
  return current; 
}

template<typename INDX>

template<typename W >

void treeindexedD2< INDX >::pathindex	(	W &	container,
		INDX const	bpath,
		INDX const	bitlength
	)			[inline]

Print the tree as a tree in text.

This lets the tree be easily visualized for small trees.

Definition at line 232 of file treeindexedD2.h.

References reset().

{
  container.clear();

  reset();
  INDX u(bpath);

  bool branch;
  for (INDX i=0; i<bitlength; ++i)
  {
    branch=(u%2);
//cout << SHOW(u) << "  " << SHOW(branch) << endl;
    u = (u >> 1);

    container.push_back(current->index);
 
    if (branch==false)
      moveleft();
    else
      moveright();
  }
}

template<typename INDX >

void treeindexedD2< INDX >::reset

(

)

[inline]

Set current to top of tree.

Definition at line 266 of file treeindexedD2.h.

References treeindexedD2< INDX >::current, and treeindexedD2< INDX >::root.

Referenced by bsptreeD2find< PT, PD, INDX >::find(), treeindexedD2< INDX >::move(), treeindexedD2test::test02(), treeindexedD2test::test03(), and treeindexedD2test::unittest02().

{ 
  current=root; 
}

template<typename INDX >

istream & treeindexedD2< INDX >::serializeInverse

(

istream &

istr

)

[inline]

Inverse of string serialization.

O(n^2) complexity because the tree is unordered.

Definition at line 414 of file treeindexedD2.h.

References treeindexedD2< INDX >::addroot(), treeindexedD2< INDX >::insert(), and treeindexedD2< INDX >::root.

Referenced by operator>>().

{
  uint n;
  istr >> n;

  if (n==0)
    return istr;

  treeindexedD2noderep<INDX> vi[n];

  for (uint i=0; i<n; ++i)
    istr >> vi[i];

//cout << SHOW(n) << endl;
//cout << "Verify vi" << endl;
//cout << print(vi,vi+n,"\n") << endl << endl;

  addroot(vi[0]);
//cout << (stringc)*this << endl << endl;

  bool found;

  for (uint i=1; i<n; ++i)
  {
    found=false;
    
    insert(found,*root,vi[i]);
    assert(found==true); 

//cout << (stringc)*this << endl << endl;
  }

  return istr;
}

---

Member Data Documentation

template<typename INDX>

treeindexedD2node<INDX>* treeindexedD2< INDX >::current

Current node.

Definition at line 42 of file treeindexedD2.h.

Referenced by treeindexedD2< INDX >::addleft(), treeindexedD2< INDX >::addright(), treeindexedD2< INDX >::construct(), bsptreeD2find< PT, PD, INDX >::find(), treeindexedD2< INDX >::moveleft(), treeindexedD2< INDX >::moveright(), treeindexedD2< INDX >::operator!(), treeindexedD2< INDX >::operator()(), and treeindexedD2< INDX >::reset().

template<typename INDX>

INDX treeindexedD2< INDX >::nodecounter

As nodes are created this index increases and assigns indexes to the new nodes.

Definition at line 34 of file treeindexedD2.h.

Referenced by treeindexedD2< INDX >::addleft(), treeindexedD2< INDX >::addright(), and treeindexedD2< INDX >::construct().

template<typename INDX>

INDX treeindexedD2< INDX >::regioncounter

As regions are created this index increases and assignes indexes to the new regions.

Definition at line 37 of file treeindexedD2.h.

Referenced by treeindexedD2< INDX >::addleft(), treeindexedD2< INDX >::addright(), and treeindexedD2< INDX >::construct().

template<typename INDX>

treeindexedD2node<INDX>* treeindexedD2< INDX >::root

The top node.

Definition at line 40 of file treeindexedD2.h.

Referenced by treeindexedD2< INDX >::construct(), treeindexedD2< INDX >::moveleft(), treeindexedD2< INDX >::moveright(), treeindexedD2< INDX >::operator stringc(), treeindexedD2iter< T >::reset(), treeindexedD2< INDX >::reset(), treeindexedD2< INDX >::serializeInverse(), and treeindexedD2< INDX >::~treeindexedD2().

---

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

• bsptrees/treeindexedD2.h