treeindexedD2.h

Go to the documentation of this file.

#ifndef TREEINDEXEDD2_H
#define TREEINDEXEDD2_H

#include <iostream>
#include <sstream>
using namespace std;

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

template <typename INDX>
class treeindexedD2node;

template< typename INDX >
class treeindexedD2noderep;

template <typename INDX>
class treeindexedD2
{
public:

  INDX nodecounter;
  INDX regioncounter;

  treeindexedD2node<INDX> * root;
  treeindexedD2node<INDX> * current;

  void construct();
  treeindexedD2();
  ~treeindexedD2(); 

  inline void reset(); 
  inline boolc operator ! () const; 
  inline treeindexedD2node<INDX> * operator()(); 

  void moveleft();
  void moveright();
  void move(INDX const bpath, INDX const bitlength);
  /* Given a path get the indexes of the nodes along the path. */
  template< typename W >
  void pathindex( W & container, INDX const bpath, INDX const bitlength);
  
  void addleft();
  void addright();

  operator stringc () const;
  istream & serializeInverse(istream & istr);

  void insert
  (
    bool & found,
    treeindexedD2node<INDX> & curr,
    treeindexedD2noderep<INDX> const & ndrep
  );
  void addroot(treeindexedD2noderep<INDX> const & ndrep);
};

template< typename INDX >
istream & operator >> (istream & istr, treeindexedD2<INDX> & x)
  { return x.serializeInverse(istr); }

template <typename INDX>
class treeindexedD2node
{
public:

  treeindexedD2node * left;
  treeindexedD2node * right;
  INDX index;

  boolc isleaf() const;
  boolc isleft(INDX index2 ) const;
  boolc isright(INDX index2) const;
  boolc isleftinternal(INDX index2) const;
  boolc isrightinternal(INDX index2) const;

  treeindexedD2node();
  treeindexedD2node(INDX const index_);
  treeindexedD2node
  (
    treeindexedD2node * left_,
    treeindexedD2node * right_,
    INDX index_
  );
  ~treeindexedD2node();

  void unlink();
  operator stringc () const;
  void printrecursive
  (
    string & s, 
    INDX const parentindex, 
    boolc branch
  ) const;
  void swap();
  void nodecount( INDX & n );

};


/*
\brief Uniquely identifies a node as a three indexes for the node, 
 left and right, and its position in the tree. 

The position is a parent index and a boolean of false 
 for left parent branch, true for right parent branch. 
*/
template< typename INDX >
class treeindexedD2noderep
{
public:

  point4<INDX> nd;
  bool branch;

  operator stringc () const;

  istream & serializeInverse(istream & istr);
};

template< typename INDX >
istream & operator >> (istream & istr, treeindexedD2noderep<INDX> & x)
  { return x.serializeInverse(istr); }

template< typename INDX >
ostream & operator << 
(
  ostream & os, treeindexedD2noderep<INDX> const & x
)
  { return os << (stringc)x; }



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


  //<TODO>
//1-2
// -2-4-5 
//     -3  
//   -3-4
//     -1
    
  //stringc printtree() const;



template <typename INDX>
template< typename W >
void treeindexedD2<INDX>::pathindex
( 
  W & container, 
  INDX const bpath, 
  INDX const bitlength
)
{
  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>
treeindexedD2<INDX>::~treeindexedD2() 
{ 
  delete root; 
}

template <typename INDX>
void treeindexedD2<INDX>::reset() 
{ 
  current=root; 
}

template <typename INDX>
boolc treeindexedD2<INDX>::operator ! () const 
{ 
  return current!=0; 
}

template <typename INDX>
treeindexedD2node<INDX> * treeindexedD2<INDX>::operator()() 
{ 
  assert(current!=0); 
  return current; 
}


template <typename INDX>
treeindexedD2<INDX>::treeindexedD2()
  : nodecounter(0), regioncounter(0), root(0), current(0) 
{ 
  construct(); 
}

template <typename INDX>
void treeindexedD2<INDX>::moveleft()  
{ 
  assert(root!=0);
  assert(current!=0); 
  assert(current->left!=0); 
  current = current->left;
}

template <typename INDX>
void treeindexedD2<INDX>::moveright()  
{ 
  assert(root!=0);
  assert(current!=0); 
  assert(current->right!=0); 
  current = current->right;
}

template <typename INDX>
void treeindexedD2<INDX>::move(INDX const bpath, INDX const bitlength)
{
  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>::addroot
(
  treeindexedD2noderep<INDX> const & ndrep
)
{
  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>::insert
(
  bool & found,
  treeindexedD2node<INDX> & curr,
  treeindexedD2noderep<INDX> const & ndrep
)
{
  // 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>
istream & treeindexedD2<INDX>::serializeInverse(istream & istr)
{
  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;
}
  

template <typename INDX>
void treeindexedD2<INDX>::addright()
{
  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>::addleft()
{
  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>
treeindexedD2<INDX>::operator stringc () const
{
  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>
void treeindexedD2<INDX>::construct()
{
  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>
treeindexedD2<INDX>::treeindexedD2
( 
  INDX const nodecounter_,
  INDX const regioncounter_
)
  : nodecounter(nodecounter_), regioncounter(regioncounter_)
{
  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 treeindexedD2node<INDX>::unlink()
{
  treeindexedD2node<INDX> * p;
  p = left;
  if (left!=0)
  {
    left=0;
    p->unlink();
  }
  p = right;
  if (right!=0)
  {
    right=0;
    p->unlink();
  }
}

template <typename INDX>
treeindexedD2node<INDX>::operator stringc () const
{
  stringstream ss;
  ss << index << " ";
  if (left)
  {
    ss << left->index;

    if (right)
    {
      ss << " " << right->index;
    }
    else
    {
      ss << " 0";
    }
  }
  else
  {
    ss << "0 ";
    if (right)
    {
      ss << " " << right->index;
    }
    else
    {
      ss << " 0";
    }
  }

  return ss.str();
}

template <typename INDX>
void treeindexedD2node<INDX>::printrecursive
(
  string & s, 
  INDX const parentindex,
  boolc branch
) const
{
  s += (stringc)*this;

  {
    stringstream ss;
    ss << parentindex;

    s += " ";
    s += ss.str();
  }

  if (branch==false)
    s += " 0";
  else
    s += " 1";

  if ((left!=0)||(right!=0))
    s += '\n';
  if (left!=0)
  {
    if (left->isleaf()==false)
      left->printrecursive(s,index,false);
  }
  if (right!=0)
  {
    if (right->isleaf()==false)
      right->printrecursive(s,index,true);
  }
}

template <typename INDX>    
void treeindexedD2node<INDX>::nodecount( INDX & n )
{
  if (isleaf())
    return;

  ++n;
  if (left!=0)
    left->nodecount(n);
  if (right!=0)
    right->nodecount(n);
}

template <typename INDX>    
treeindexedD2node<INDX>::treeindexedD2node()
  : left(0), right(0), index(0) 
{
}

template <typename INDX>    
treeindexedD2node<INDX>::treeindexedD2node(INDX const index_)
  : left(0), right(0), index(index_) 
{
}

template <typename INDX>    
treeindexedD2node<INDX>::treeindexedD2node
(
  treeindexedD2node * left_,
  treeindexedD2node * right_,
  INDX index_
)
  : left(left_), right(right_), index(index_) 
{
}


template <typename INDX>    
treeindexedD2node<INDX>::~treeindexedD2node()
{ 
  delete left; 
  delete right; 
  left=0;
  right=0;
}


template <typename INDX>    
void treeindexedD2node<INDX>::swap()
{ 
  treeindexedD2node * tmp=left; 
  right=left; 
  left=tmp; 
}





template <typename INDX>
boolc treeindexedD2node<INDX>::isleaf() const
{ 
  return (left==0)&&(right==0); 
}


template <typename INDX>
boolc treeindexedD2node<INDX>::isleft(INDX index2 ) const
{
  if (left==0) return false;
  if (left->index==index2) return true;
  return false;
}

template <typename INDX>
boolc treeindexedD2node<INDX>::isright(INDX index2) const
{ 
  if (right==0) return false;
  if (right->index==index2) return true;
  return false;
}

template <typename INDX>
boolc treeindexedD2node<INDX>::isleftinternal(INDX index2) const
{ 
  if (left==0) return false;
  if (left->index!=index2) return false;
  if (left->isleaf()) return false;
  return true;
}

template <typename INDX>
boolc treeindexedD2node<INDX>::isrightinternal(INDX index2) const
{ 
  if (right==0) return false;
  if (right->index!=index2) return false;
  if (right->isleaf()) return false;
  return true;
}




template <typename INDX>
treeindexedD2noderep<INDX>::operator stringc () const
{
  string s((stringc)nd);
  if (branch==false)
    s += " 0";
  else
    s += " 1";

  return s;
}

template <typename INDX>
istream & treeindexedD2noderep<INDX>::serializeInverse(istream & istr)
{
  istr >> nd;
  istr >> branch;
  return istr;
}




#endif