treeindexediter.h

Go to the documentation of this file.

#ifndef TREEINDEXEDD2ITER_H
#define TREEINDEXEDD2ITER_H

#include <treeindexedD2.h>

template< typename T >
class treeindexedD2iter
{
public:

  vector< treeindexedD2node<T> * > path;

  treeindexedD2<T> & tree;

  treeindexedD2iter(treeindexedD2<T> & tree_, boolc setreset=true)
    : tree(tree_) { if (setreset) reset(); }

  void reset();

  void movedown();

  void operator ++ ();

  boolc operator !() const
    { return !path.empty(); }

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


template< typename T >
class treeindexedD2iterleaf : public treeindexedD2iter<T>
{
public:

  treeindexedD2iterleaf
  (
    treeindexedD2<T> & tree_, 
    boolc setreset=true
  )
    : treeindexedD2iter<T>(tree_,setreset) {}

  void operator ++ ();
};

template< typename T >
class treeindexedD2iterinternal : public treeindexedD2iter<T>
{
public:

  treeindexedD2iterinternal
  (
    treeindexedD2<T> & tree_, 
    boolc setreset=true
  );

  void operator ++ ();

  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