Tree.cpp

Go to the documentation of this file.

// Mint headers
#include "Tree.hpp"

namespace OA {

template <class T> void deque_erase (std::deque<T> d, T elt);

//--------------------------------------------------------------------
Tree::OutEdgesIterator::OutEdgesIterator (const Node&  n)
{
  mQueue = n.outgoing;
  mIter = mQueue->begin();
  OA_ptr<Edge>  e; e = 0;
  if (mIter != mQueue->end()) {
    e = *mIter;
  }
  while ((e.ptrEqual(0)) && (mIter != mQueue->end())) {
    ++mIter;
    e = *mIter;
  }
}
//--------------------------------------------------------------------

//--------------------------------------------------------------------
void
Tree::OutEdgesIterator::operator ++ ()
{
  ++mIter;
  OA_ptr<Edge>  e; e = 0;
  if (mIter != mQueue->end())
    e = *mIter;
  while ((e.ptrEqual(0)) && (mIter != mQueue->end())) {
    ++mIter;
    e = *mIter;
  }
}
//--------------------------------------------------------------------


//--------------------------------------------------------------------
Tree::PreOrderIterator::PreOrderIterator (Tree& t)
{
  if (! t.root_node.ptrEqual(0)) {
    if (t.preorder_needed) {
      // reset all the preoder_next links
      std::set<OA_ptr<Node> >::iterator ni = t.node_set->begin();
      while (ni != t.node_set->end()) {
        OA_ptr<Node>  n = *ni;
        n->next_preorder = 0;
        ++ni;
      }
      t.create_preorder_links(t.root_node);
      t.preorder_needed = false;
    }
  }
  p = t.root_node;
}
//--------------------------------------------------------------------


//--------------------------------------------------------------------
OA_ptr<Tree::Node> 
Tree::create_preorder_links (OA_ptr<Tree::Node>  n)
{
  OA_ptr<Node>  last;

  ChildNodesIterator iter(*n);
  if (!iter.isValid()) {
    n->next_preorder = 0;
    last = n;
  }
  else {
    last = n;
    do {
      last->next_preorder = iter.current();
      last = create_preorder_links(iter.current());
      ++iter;
    } while (iter.isValid());
  }
  return last;
}
//--------------------------------------------------------------------

//--------------------------------------------------------------------
Tree::PostOrderIterator::PostOrderIterator (Tree& t)
{
  if (! t.root_node.ptrEqual(0)) {
    if (t.postorder_needed) {
      // reset all the preoder_next links
      std::set<OA_ptr<Node> >::iterator ni = t.node_set->begin();
      while (ni != t.node_set->end()) {
        OA_ptr<Node>  n = *ni;
        n->next_postorder = NULL;
        n->prev_postorder = NULL;
        ++ni;
      }
      OA_ptr<Node> nullNode;  nullNode = NULL;
      t.create_postorder_links(t.root_node, nullNode);
      t.postorder_needed = false;
      t.rpostorder_needed = false;
    }
  }
  p = t.mPostOrderStart;
}
//--------------------------------------------------------------------


//--------------------------------------------------------------------
OA_ptr<Tree::Node> 
Tree::create_postorder_links (OA_ptr<Tree::Node>  n, OA_ptr<Tree::Node> last)
{
  OA_ptr<Node> retLast = last;

  ChildNodesIterator iter(*n);
  for (; iter.isValid(); ++iter) {
    retLast = create_postorder_links(iter.current(),retLast);
  }
 
  // links for this node
  if (retLast.ptrEqual(NULL)) { // this is the first node in postorder
    mPostOrderStart = n;
  } else {
    retLast->next_postorder = n;
  }
  n->prev_postorder = retLast;
  retLast = n;

  return retLast;
}
//--------------------------------------------------------------------


//--------------------------------------------------------------------
void
Tree::addEdge(OA_ptr<Tree::Edge>  e)
  throw (Tree::DuplicateEdge, Tree::EdgeInUse, Tree::EmptyEdge, Tree::SecondParent, Tree::EmptyEndPoint)
{
  if (e.ptrEqual(0)) {
    throw EmptyEdge();
  }
  if (edge_set->find(e) != edge_set->end()) {
    throw DuplicateEdge(e);
  }
  if (e->in_use) {
    throw EdgeInUse(e);
  }
  if ((e->child_node.ptrEqual(0)) || (e->parent_node.ptrEqual(0))) {
    throw EmptyEndPoint(e);
  }
  if (!e->child_node->incoming.ptrEqual(0)) {
      throw SecondParent(e);
  }

  // insert the nodes if they don't already exist in the graph
  if (node_set->find(e->parent_node) == node_set->end()) {
    addNode(e->parent_node);
  }
  if (node_set->find(e->child_node) == node_set->end()) {
    addNode(e->child_node);
  }

  // insert the edge in the corresponding lists of the two nodes
  e->parent_node->outgoing->push_back(e);
  e->child_node->incoming = e;

  // finally, insert the edge itself in the tree
  e->in_use = true;
  edge_set->insert(e);
  preorder_needed = postorder_needed = rpostorder_needed = true;
}
//--------------------------------------------------------------------


//--------------------------------------------------------------------
void
Tree::addNode(OA_ptr<Tree::Node>  n)
  throw (Tree::DuplicateNode, Tree::NodeInUse, Tree::EmptyNode)
{
  if (n.ptrEqual(0)) {
    throw EmptyNode();
  }
  if (node_set->find(n) != node_set->end()) {
    throw DuplicateNode(n);
  }
  if (n->in_use) {
    throw NodeInUse(n);
  }
  if (root_node.ptrEqual(0)) {
    root_node = n;
  }
  n->in_use = true;
  node_set->insert(n);
  preorder_needed = postorder_needed = rpostorder_needed = true;
}
//--------------------------------------------------------------------


//--------------------------------------------------------------------
void
Tree::add_empty_edge (OA_ptr<Tree::Node> n)
  throw (Tree::EmptyNode)
{
  if (n.ptrEqual(0)) {
    throw EmptyNode();
  }
  OA_ptr<Edge> nullEdge; nullEdge = 0;
  n->outgoing->push_back(nullEdge);
}
//--------------------------------------------------------------------


//--------------------------------------------------------------------
void
Tree::removeEdge (OA_ptr<Tree::Edge>  e)
  throw (Tree::NonexistentEdge, Tree::EmptyEdge)
{
  if (e.ptrEqual(0)) {
    throw EmptyEdge();
  }
  if (edge_set->erase(e) == 0) {
    throw NonexistentEdge(e);
  }
  preorder_needed = postorder_needed = rpostorder_needed = true;
  e->in_use = false;
  deque_erase<OA_ptr<Edge> >(*(e->parent_node->outgoing), e);
  e->child_node->incoming = 0;
}
//--------------------------------------------------------------------


//--------------------------------------------------------------------
void
Tree::removeNode (OA_ptr<Tree::Node>  n)
  throw (Tree::NonexistentNode, Tree::DeletingRootOfNonSingletonTree, Tree::EmptyNode)
{
  if (n.ptrEqual(0)) {
    throw EmptyNode();
  }
  if ((n.ptrEqual(root_node)) && (!edge_set->empty() || (node_set->size() > 1)))
    throw DeletingRootOfNonSingletonTree(n);
  if (node_set->erase(n) == 0)
    throw NonexistentNode(n);
  preorder_needed = postorder_needed = rpostorder_needed = true;
  n->in_use = false;
  if (n == root_node)
    root_node = 0;

  if (! n->incoming.ptrEqual(0)) {
    edge_set->erase(n->incoming);
    deque_erase<OA_ptr<Edge> >(*(n->incoming->parent_node->outgoing), 
                               n->incoming);
  }

  OutEdgesIterator out(*n);
  while (out.isValid()) {
    OA_ptr<Edge>  e = out.current();
    e->child_node->incoming = 0;
    edge_set->erase(e);
    ++out;
  }
}
//--------------------------------------------------------------------------------------------------------------------


//--------------------------------------------------------------------
template <class T>
void
deque_erase (std::deque<T> d, T elt)
{
  typename std::deque<T>::iterator iter = d.begin();
  while (iter != d.end()) {
    T k = *iter;
    if (k == elt) {
      d.erase(iter);
      break;
    }
  }
}
//--------------------------------------------------------------------------------------------------------------------


//--------------------------------------------------------------------------------------------------------------------
/*
OA_ptr<Tree::Node>
Tree::clone (OA_ptr<Tree::Node>  subtree)
{
  OA_ptr<Node>  new_root = subtree->new_copy();
  OutEdgesIterator edge_iter(*subtree);
  while (edge_iter.isValid()) {
    OA_ptr<Edge>  out_edge = edge_iter.current();
    if (! out_edge.ptrEqual(0)) {
      OA_ptr<Node>  new_child = clone(out_edge->sink());
      addEdge(out_edge->new_copy(new_root, new_child));
    }
    else {
      OA_ptr<Edge> nullEdge; nullEdge = 0;
      new_root->outgoing->push_back(nullEdge);
    }
    ++edge_iter;
  }
  return new_root;
}
*/
//--------------------------------------------------------------------------------------------------------------------

} // end of OA namespace

---