IteratorImpl.cpp

Go to the documentation of this file.

/* -*- C++ -*- */
#ifndef _TREE_ITERATOR_IMPL_CPP
#define _TREE_ITERATOR_IMPL_CPP

#ifndef _MADARA_NO_KARL_

#include "madara/expression/ExpressionTree.h"
#include "madara/expression/IteratorImpl.h"
#include "madara/expression/ComponentNode.h"
#include "madara/utility/Refcounter.h"

const size_t LQUEUE_SIZE = 40;

// Constructor for ExpressionTreeIteratorImpl that takes a tree
// to iterate over

madara::expression::ExpressionTreeIteratorImpl::ExpressionTreeIteratorImpl (
  const ExpressionTree &tree)
  : tree_ (tree)
{
}

// Destructor

madara::expression::ExpressionTreeIteratorImpl::~ExpressionTreeIteratorImpl (void)
{
}


madara::expression::InOrderIteratorImpl::InOrderIteratorImpl (
  const ExpressionTree &tree, bool end_iter)
  : ExpressionTreeIteratorImpl (tree),
    stack_ ()
{
  // if the caller doesn't want an end iterator, insert the root tree
  // into the queue.
  if (!end_iter && !this->tree_.is_null ())
    {
      stack_.push (const_cast <ExpressionTree &> (tree));

      // start at the smallest element (left-most)
      while (!stack_.top ().left ().is_null ())
        stack_.push (stack_.top ().left ());
    }
}


madara::expression::InOrderIteratorImpl::~InOrderIteratorImpl (void)
{
}

 
madara::expression::ExpressionTree 
madara::expression::InOrderIteratorImpl::operator* (void)
{
  return stack_.top ();
}

 
const madara::expression::ExpressionTree 
madara::expression::InOrderIteratorImpl::operator* (void) const
{
  return stack_.top ();
}

 
void
madara::expression::InOrderIteratorImpl::operator++ (void)
{
  // we know that at this point there is no left () of top ()
  // because we would have already visited it.

  if (!stack_.is_empty ())
    {
      // if we have nodes greater than ourselves
      if (!stack_.top ().right ().is_null ())
        {
          // push the right child node onto the stack
          // and pop the old parent (it's been visited now)
          stack_.push (stack_.pop ().right ());

          // keep pushing until we get to the left most child
          while (!stack_.top ().left ().is_null ())
            stack_.push (stack_.top ().left ());
        }
      else
        stack_.pop ();
    }
}

 
bool 
madara::expression::InOrderIteratorImpl::operator== (
  const ExpressionTreeIteratorImpl &rhs) const
{
  const InOrderIteratorImpl * in_order_rhs = dynamic_cast
    <const InOrderIteratorImpl *> (&rhs);

  // if the rhs was not a level_order iterator then we've already
  // discovered the relation is false.

  if (in_order_rhs)
    {
      // Check if the container we are iterating over has the same
      // root node and that the size of the queues are equal. The
      // latter doesn't truly determine equality. However, this is an
      // easy check for determining most inequalities and it allows us
      // to assume the queue at least has a front node (coupled with
      // the is_empty () function later).

      ExpressionTree &t1 =
        const_cast <ExpressionTree &> (tree_);
      ExpressionTree &t2 =
        const_cast <ExpressionTree &> (in_order_rhs->tree_);

      if (t1.get_root () == t2.get_root () 
          && stack_.size () == in_order_rhs->stack_.size ())
        {
          // Check for both being is_empty (special condition).
          if (stack_.is_empty () && in_order_rhs->stack_.is_empty ())
            return true;

          // check the front's node pointer. If the node pointers are
          // equal, then both iterators are pointing to the same
          // position in the tree.

          if (stack_.top ().get_root () == 
              in_order_rhs->stack_.top ().get_root ())
            return true;
        }
    }

  // either we were trying to compare a non-level order iterator or we
  // were comparing two level order iterators that were obviously at
  // different points in the tree (their queue sizes were different)

  return false;
}

 
bool 
madara::expression::InOrderIteratorImpl::operator!= (
  const ExpressionTreeIteratorImpl &rhs) const
{
  return ! (*this == rhs);
}

 
madara::expression::ExpressionTreeIteratorImpl * 
madara::expression::InOrderIteratorImpl::clone (void)
{
  return new InOrderIteratorImpl (*this);
}


madara::expression::PreOrderIteratorImpl::PreOrderIteratorImpl (
  const ExpressionTree &tree, bool end_iter)
  : ExpressionTreeIteratorImpl (tree), 
    stack_ ()
{
  // if the caller doesn't want an end iterator, insert the root tree
  // into the queue.
  if (!end_iter && !this->tree_.is_null ())
    stack_.push (const_cast <ExpressionTree &> (tree));
}


madara::expression::PreOrderIteratorImpl::~PreOrderIteratorImpl (
  void)
{

}

 
madara::expression::ExpressionTree 
madara::expression::PreOrderIteratorImpl::operator* (void)
{
  return stack_.top ();
}

 
const madara::expression::ExpressionTree 
madara::expression::PreOrderIteratorImpl::operator* (void) const
{
  return stack_.top ();
}

 
void
madara::expression::PreOrderIteratorImpl::operator++ (void)
{
  // we know that at this point there is no left () of top ()
  // because we would have already visited it.

  if (!stack_.is_empty ())
    {
      // we need to pop the node off the stack before pushing the
      // children, or else we'll revisit this node later

      ExpressionTree current = stack_.pop ();

      // note the order here: right first, then left. Since this is
      // LIFO, this results in the left child being the first
      // evaluated, which fits into the Pre-order traversal strategy

      if (!current.right ().is_null ())
        stack_.push (current.right ());
      if (!current.left ().is_null ())
        stack_.push (current.left ());
    }
}

 
bool 
madara::expression::PreOrderIteratorImpl::operator== (
  const ExpressionTreeIteratorImpl &rhs) const
{
  const PreOrderIteratorImpl *pre_order_rhs = dynamic_cast
    <const PreOrderIteratorImpl *> (&rhs);

  // if the rhs was not a level_order iterator
  // then we've already discovered the relation is false

  if (pre_order_rhs)
    {
      // check if the container we are iterating over has the same
      // root node and that the size of the queues are equal. The
      // latter doesn't truly determine equality. However, this is an
      // easy check for determining most inequalities and it allows us
      // to assume the queue at least has a front node (coupled with
      // the is_empty () function later).

      ExpressionTree &t1 = const_cast <ExpressionTree &> (tree_);
      ExpressionTree &t2 = const_cast <ExpressionTree &> (
        pre_order_rhs->tree_);

      if (t1.get_root () == t2.get_root () 
          && stack_.size () == pre_order_rhs->stack_.size ())
        {
          // check for both being is_empty (special condition)
          if (stack_.is_empty () && pre_order_rhs->stack_.is_empty ())
            return true;

          // check the front's node pointer. If the node pointers
          // are equal, then both iterators are pointing to the same
          // position in the tree.

          if (stack_.top ().get_root () ==
              pre_order_rhs->stack_.top ().get_root ())
            return true;
        }
    }

  // either we were trying to compare a non-level order iterator or
  // we were comparing two level order iterators that were obviously
  // at different points in the tree (their queue sizes were different)

  return false;
}

 
bool 
madara::expression::PreOrderIteratorImpl::operator!= (
  const ExpressionTreeIteratorImpl &rhs) const
{
  return ! (*this == rhs);
}


 
madara::expression::ExpressionTreeIteratorImpl * 
madara::expression::PreOrderIteratorImpl::clone (void)
{
  return new PreOrderIteratorImpl (*this);
}


madara::expression::PostOrderIteratorImpl::PostOrderIteratorImpl (
  const ExpressionTree &tree, bool end_iter)
  : ExpressionTreeIteratorImpl (tree), 
    stack_ ()
{
  // if the caller doesn't want an end iterator, insert the root tree
  // into the queue.
  if (!end_iter && !this->tree_.is_null ())
    {
      ExpressionTree current = const_cast <ExpressionTree &> (tree);
      stack_.push (current);

      // the commented code does not work on unary operator nodes with 
      // no left child, but a right child - or at least, there is a 
      // certain depth that this will not go down

      while (!current.is_null ())
        {
          if (!current.right ().is_null ())
            stack_.push (current.right ());
          if (!current.left ().is_null ())
            {
              // if there was a left, then update current
              // this is the case for all non-negations
              stack_.push (current.left ());
              current = current.left ();
            }
          else
            // if there was not a left, then current = current->right_
            // this handles cases of unary nodes, like negations
            current = current.right ();
        }
    }
}


madara::expression::PostOrderIteratorImpl::~PostOrderIteratorImpl (
  void)
{
}

 
madara::expression::ExpressionTree 
madara::expression::PostOrderIteratorImpl::operator* (void)
{
  return stack_.top ();
}

 
const madara::expression::ExpressionTree 
madara::expression::PostOrderIteratorImpl::operator* (void) const
{
  return stack_.top ();
}

 
void
madara::expression::PostOrderIteratorImpl::operator++ (void)
{
  // we know that at this point there is no left () of top ()
  // because we would have already visited it.

  if (!stack_.is_empty ())
    {
      // we need to pop the node off the stack before pushing the
      // children, or else we'll revisit this node later

      ExpressionTree current = stack_.pop ();

      // This is where stuff gets a little confusing.

      if (!stack_.is_empty () 
          && stack_.top ().left ().get_root () != current.get_root ()
          && stack_.top ().right ().get_root () != current.get_root () )

        {
          current = stack_.top ();

          while (!current.is_null ())
            {
              if (!current.right ().is_null ())
                stack_.push (current.right ());
              if (!current.left ().is_null ())
                {
                  // if there was a left, then update current
                  // this is the case for all non-negations
                  stack_.push (current.left ());
                  current = current.left ();
                }
              else
                {
                  // if there was not a left, then current = current->right_
                  // this handles cases of unary nodes, like negations
                  current = current.right ();
                }
            }
        }
    }
}

 
bool 
madara::expression::PostOrderIteratorImpl::operator== (
  const ExpressionTreeIteratorImpl &rhs) const
{
  const PostOrderIteratorImpl * post_order_rhs = dynamic_cast
    <const PostOrderIteratorImpl *> (&rhs);

  // if the rhs was not a level_order iterator
  // then we've already discovered the relation is false

  if (post_order_rhs)
    {
      // check if the container we are iterating over has the same
      // root node and that the size of the queues are equal. The
      // latter doesn't truly determine equality. However, this is an
      // easy check for determining most inequalities and it allows us
      // to assume the queue at least has a front node (coupled with
      // the is_empty () function later).

      ExpressionTree &t1 = const_cast <ExpressionTree &> (tree_);
      ExpressionTree &t2 = const_cast <ExpressionTree &> (
        post_order_rhs->tree_);

      if (t1.get_root () == t2.get_root () 
          && stack_.size () == post_order_rhs->stack_.size ())
        {
          // check for both being is_empty (special condition)
          if (stack_.is_empty () && post_order_rhs->stack_.is_empty ())
            return true;

          // check the front's node pointer. If the node pointers are
          // equal, then both iterators are pointing to the same
          // position in the tree.

          if (stack_.top ().get_root () ==
              post_order_rhs->stack_.top ().get_root ())
            return true;
        }
    }

  // either we were trying to compare a non-level order iterator or
  // we were comparing two level order iterators that were obviously
  // at different points in the tree (their queue sizes were different)

  return false;
}

 
bool 
madara::expression::PostOrderIteratorImpl::operator!= (
  const ExpressionTreeIteratorImpl &rhs) const
{
  return ! (*this == rhs);
}

 
madara::expression::ExpressionTreeIteratorImpl * 
madara::expression::PostOrderIteratorImpl::clone (void)
{
  return new PostOrderIteratorImpl (*this);
}


madara::expression::LevelOrderExpressionTreeIteratorImpl::LevelOrderExpressionTreeIteratorImpl (
  const ExpressionTree &tree, bool end_iter)
  : ExpressionTreeIteratorImpl (tree), 
    queue_ (LQUEUE_SIZE)
{
  // if the caller doesn't want an end iterator, insert the root tree
  // into the queue.
  if (!end_iter && !this->tree_.is_null ())
    queue_.enqueue (const_cast <ExpressionTree &> (tree));
}


madara::expression::LevelOrderExpressionTreeIteratorImpl::~LevelOrderExpressionTreeIteratorImpl (
  void)
{
}

 
madara::expression::ExpressionTree 
madara::expression::LevelOrderExpressionTreeIteratorImpl::operator* (
  void)
{
  return queue_.front ();
}

 
const madara::expression::ExpressionTree 
madara::expression::LevelOrderExpressionTreeIteratorImpl::operator* (
  void) const
{
  return queue_.front ();
}

 
void
madara::expression::LevelOrderExpressionTreeIteratorImpl::operator++ (
  void) 
{
  if (!queue_.is_empty ())
    {
      // If the queue is not empty, dequeue an element
      ExpressionTree root = queue_.dequeue ();

      if (!root.is_null ())
        {
          // If the element wasn't null, enqueue its children
          if (!root.left ().is_null ())
            queue_.enqueue (root.left ());
          if (!root.right ().is_null ())
            queue_.enqueue (root.right ());
        }
    }
}

 
bool 
madara::expression::LevelOrderExpressionTreeIteratorImpl::operator== (
  const ExpressionTreeIteratorImpl &rhs) const
{
  const LevelOrderExpressionTreeIteratorImpl * level_order_rhs =
    dynamic_cast<const LevelOrderExpressionTreeIteratorImpl *> (&rhs);

  // if the rhs was not a level_order iterator then we've already
  // discovered the relation is false.

  if (level_order_rhs)
    {
      // check if the container we are iterating over has the same
      // root node and that the size of the queues are equal. The
      // latter doesn't truly determine equality. However, this is an
      // easy check for determining most inequalities and it allows us
      // to assume the queue at least has a front node (coupled with
      // the is_empty () function later).

      ExpressionTree &t1 = const_cast <ExpressionTree &> (tree_);
      ExpressionTree &t2 = const_cast <ExpressionTree &> (
        level_order_rhs->tree_);

      if (t1.get_root () == t2.get_root () 
          && queue_.size () == level_order_rhs->queue_.size ())
        {
          // check for both being is_empty (special condition)
          if (queue_.is_empty () && level_order_rhs->queue_.is_empty ())
            return true;

          // check the front's node pointer. If the node pointers
          // are equal, then both iterators are pointing to the same
          // position in the tree.

          if (queue_.front ().get_root () ==
              level_order_rhs->queue_.front ().get_root ())
            return true;
        }
    }

  // either we were trying to compare a non-level order iterator or we
  // were comparing two level order iterators that were obviously at
  // different points in the tree (their queue sizes were different)

  return false;
}

 
bool 
madara::expression::LevelOrderExpressionTreeIteratorImpl::operator!= (
  const ExpressionTreeIteratorImpl &rhs) const
{
  return !(*this == rhs);
}

 
madara::expression::ExpressionTreeIteratorImpl * 
madara::expression::LevelOrderExpressionTreeIteratorImpl::clone (
  void)
{
  return new LevelOrderExpressionTreeIteratorImpl (*this);
}

#endif // _MADARA_NO_KARL_

#endif /* _TREE_ITERATOR_IMPL_CPP */