#ifndef TREEINDEXEDD2ITER_H
#define TREEINDEXEDD2ITER_H

#include <treeindexedD2.h>

/*!
\brief Iterate over the nodes of the tree.
\par Example 1
\verbatim
  cout << "Iterating over every node." << endl;
  treeindexedD2iter<uint> i1(t1,false);
  for ( i1.reset(); !i1; ++i1)
    cout << i1()->index << " ";
\endverbatim

\par Example 2
\verbatim
  cout << "Iterating over every node." << endl;
  for ( treeindexedD2iter<uint> i1(t1); !i1; ++i1)
    cout << i1()->index << " ";
\endverbatim
*/
template< typename T >
class treeindexedD2iter
{
public:

  /** List of nodes defining the current path. The last
      node is the current node. */
  vector< treeindexedD2node<T> * > path;

  /** The tree this iterator is iterating over. */
  treeindexedD2<T> & tree;

  /** Pass in the tree. */
  treeindexedD2iter(treeindexedD2<T> & tree_, boolc setreset=true)
    : tree(tree_) { if (setreset) reset(); }

  /** Reset the iterator. */
  void reset();

  /** From the current node as defined by path, fall 
      down left first, then right. The path is changed. */
  void movedown();

  /** Move to the next node in the tree. */
  void operator ++ ();

  /** Is the iterator valid? */
  boolc operator !() const
    { return !path.empty(); }

  /** Get the current node. */
  treeindexedD2node<T> * operator () () const
    { assert(path.size()>0); return path[path.size()-1]; }
};


/*!
\brief Iterate over the leaves.

\par Example
\verbatim
  cout << "Iterating over the leaves." << endl;
  for ( treeindexedD2iterleaf<uint> i3(t1); !i3; ++i3 )
    cout << i3()->index << " ";  
\endverbatim
*/
template< typename T >
class treeindexedD2iterleaf : public treeindexedD2iter<T>
{
public:

  /** Pass in the tree. */
  treeindexedD2iterleaf
  (
    treeindexedD2<T> & tree_, 
    boolc setreset=true
  )
    : treeindexedD2iter<T>(tree_,setreset) {}

  /** Move to the next leaf. */
  void operator ++ ();
};

/*!
\brief Iterate over the internal nodes (not leaves).
*/
template< typename T >
class treeindexedD2iterinternal : public treeindexedD2iter<T>
{
public:

  /** Pass in the tree. */
  treeindexedD2iterinternal
  (
    treeindexedD2<T> & tree_, 
    boolc setreset=true
  );

  /** Move to the next internal node. */
  void operator ++ ();

  /** Reset the iterator. */
  void reset();
};


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

template <typename T>
void treeindexedD2iterinternal<T>::reset()
{
  treeindexedD2iter<T>::reset();

  // Warning, deliberate duplicate code - same as in constructor treeindexedD2iterinternal(...).

  if (! treeindexedD2iter<T>::operator !())
    return;

  if (treeindexedD2iter<T>::operator()()->isleaf())
    treeindexedD2iterinternal<T>::operator++();
}

template <typename T>
treeindexedD2iterinternal<T>::treeindexedD2iterinternal
(
  treeindexedD2<T> & tree_, 
  boolc setreset
)
  : treeindexedD2iter<T>(tree_,setreset) 
{
  if (setreset==false)
    return;

  // Warning, deliberate duplicate code - same as in reset().

  if (! treeindexedD2iter<T>::operator !())
    return;

  if (treeindexedD2iter<T>::operator()()->isleaf())
    treeindexedD2iterinternal<T>::operator++();
}

template <typename T>
void treeindexedD2iterinternal<T>::operator ++ ()
{
  treeindexedD2iter<T>::operator ++ ();

  while (treeindexedD2iter<T>::operator ! ()) 
  {
    if (! treeindexedD2iter<T>::operator ()()->isleaf())
      return;

    treeindexedD2iter<T>::operator ++ ();
  }
}

template <typename T>
void treeindexedD2iterleaf<T>::operator ++ ()
{
  treeindexedD2iter<T>::operator ++ ();

  while (treeindexedD2iter<T>::operator ! ()) 
  {
    if (treeindexedD2iter<T>::operator ()()->isleaf())
      return;

    treeindexedD2iter<T>::operator ++ ();
  }
}


template <typename T>
void treeindexedD2iter<T>::operator ++ ()
{
  uint sz = path.size();
  if (sz<=1)
  {
    if (sz==0)
      return;

    path.pop_back();
    return;
  }

  --sz;
  treeindexedD2node<T> * current = path[sz];
  path.pop_back();

  treeindexedD2node<T> * parent = path[sz-1];

  if (current->isleaf())
  {
    if (parent->left==current)
    {
      if (parent->right!=0)
      {
        path.push_back(parent->right);
        movedown();
        return;
      }

      return;
    }

    if (parent->right==current)
      return;

    assert(false);
  }

  // The node is not a leaf therefore it is internal.
  // Therefore moving up.

  // Is it a left branch?
  if (parent->left==current)
  {
    if (parent->right!=0)
    {
      path.push_back(parent->right);
      movedown();
      return;
    }

    return;
  }

  if (parent->right==current)
    return;

  assert(false);
}

template <typename T>
void treeindexedD2iter<T>::reset()
{
  path.clear();
  treeindexedD2node<T> * current = tree.root;
  if (current==0)
    return;

  path.push_back(current);
  movedown();
}

template <typename T>
void treeindexedD2iter<T>::movedown()
{
  assert(path.size()>0);

  treeindexedD2node<T> * current = path[path.size()-1];
  assert(current!=0);

  for ( ; current!=0; )
  {
    if (current->left!=0)
    {
      current = current->left;
      path.push_back(current);
      continue;
    }

    if (current->right!=0)
    {
      current = current->right;
      path.push_back(current);
      continue;
    }

    current=0;
  }

}
  


#endif