#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;

/*!
\brief 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.
*/
template <typename INDX>
class treeindexedD2
{
public:

  /** As nodes are created this index increases and assigns 
      indexes to the new nodes. */
  INDX nodecounter;
  /** As regions are created this index increases and assignes
      indexes to the new regions. */
  INDX regioncounter;

  /** The top node. */
  treeindexedD2node<INDX> * root;
  /** Current node. */
  treeindexedD2node<INDX> * current;

  /** Build the initial tree with root and two leafs. */
  void construct();
  /** Set the counters with a value 1. Build
      the root node and two leafs. */
  treeindexedD2();
  /** Memory cleanup. */
  ~treeindexedD2(); 

  /** Set current to top of tree. */
  inline void reset(); 
  /** Is iteration possible? */
  inline boolc operator ! () const; 
  /** Access the current node. */
  inline treeindexedD2node<INDX> * operator()(); 

  /** Move the current node left. */
  void moveleft();
  /** Move the current node right. */
  void moveright();
  /** Move along a path. For example move(0*1+1*2+0*4,3) is 
      move left, right, left.  */
  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);
  
  /** Assuming the current node is an internal node
     ( has two leafs), add a new node left. */ 
  void addleft();
  /** At the current node add a new node right. It is assumed
      that the current node has two leafs. */
  void addright();

  /** Serialize this object by writing it out as a string. */
  operator stringc () const;
  /** Inverse of string serialization.
      O(n^2) complexity because the tree is unordered. */
  istream & serializeInverse(istream & istr);

  /** Set found to false before use as this is recursive.
      The root node must be inserted before use. */
  void insert
  (
    bool & found,
    treeindexedD2node<INDX> & curr,
    treeindexedD2noderep<INDX> const & ndrep
  );
  /** The first node inserted into the tree. */
  void addroot(treeindexedD2noderep<INDX> const & ndrep);
};

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

/*!
\brief Binary tree node with each node having an index.
 
Nodes and leafs indexed independently from each other.
 A zero index value is used for writing out the tree when
 there is no node on that branch.

The client can use the index as a pointer to the real data
 structure.  The tree manages the nodes assuming
 that they were created with new.

There are deliberately no virtual functions. If a very
 (Designed for a large number of treeindexedD2node's. 
 The cost is that leafs do not use left or right
 and nodes may or may not using index depending on the 
 application.
*/
template <typename INDX>
class treeindexedD2node
{
public:

  /** The left branch. */
  treeindexedD2node * left;
  /** The right branch. */
  treeindexedD2node * right;
  /** The index to either whats in a node or whats in a leaf. */
  INDX index;

  /** Is this a leaf node? */
  boolc isleaf() const;
  /** Is the node left? */
  boolc isleft(INDX index2 ) const;
  /** Is the node right? */
  boolc isright(INDX index2) const;
  /** Is left an internal node? */
  boolc isleftinternal(INDX index2) const;
  /** Is right an internal node? */
  boolc isrightinternal(INDX index2) const;

  /** Unconstructed, classed as a leaf. */
  treeindexedD2node();
  /** Construct a leaf. */
  treeindexedD2node(INDX const index_);
  /** Construct a node. */
  treeindexedD2node
  (
    treeindexedD2node * left_,
    treeindexedD2node * right_,
    INDX index_
  );
  /** Memory cleanup if left and right are not zero. */
  ~treeindexedD2node();

  /** Set the left and right pointers to zero recursively 
      down the tree. */
  void unlink();
  /** Serialize this object by writing it out as a string. */
  operator stringc () const;
  /** Write the tree out as a linear list of nodes, where
      each node refers to a previous node. For uniques then
      parents branch that points to this node is needed. */
  void printrecursive
  (
    string & s, 
    INDX const parentindex, 
    boolc branch
  ) const;
  /** Swap left and right. */
  void swap();
  /** How many nodes are in the tree? */
  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:

  /** index, left and right and parent indexes.*/
  point4<INDX> nd;
  /** Left is false, right is true. */
  bool branch;

  /** Serialize this object by writing it out as a string. */
  operator stringc () const;

  /** Inverse of string serialization. */
  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>
  /** Print the tree as a tree in text.  This lets the tree
      be easily visualized for small trees. */
//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