CMappedTree.hpp

/* This file is part of sUtil, a random collection of utilities.

sUtil is free software; you can redistribute it and/or
modify it under the terms of the GNU Lesser General Public
License as published by the Free Software Foundation; either
version 3 of the License, or (at your option) any later version.

Alternatively, you can redistribute it and/or
modify it under the terms of the GNU General Public License as
published by the Free Software Foundation; either version 2 of
the License, or (at your option) any later version.

sUtil is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU Lesser General Public
License and a copy of the GNU General Public License along with
sUtil. If not, see <http://www.gnu.org/licenses/>.
 */
/* \file CMappedTree.hpp
 *
 *  Created on: Dec 27, 2010
 *
 *  Copyright (C) 2010, Samir Menon <smenon@stanford.edu>
 */

#ifndef CMAPPEDTREE_HPP_
#define CMAPPEDTREE_HPP_

#include <sutil/CMappedList.hpp>

#ifdef DEBUG
#include <iostream>
#endif

namespace sutil
{
  template <typename TIdx, typename TNode>
  class CMappedTree : public sutil::CMappedList<TIdx,TNode>
  {
  protected:
    TNode* root_node_;

    bool has_been_init_;

    virtual bool deepCopy(const CMappedTree<TIdx,TNode>* arg_mt);

  public:
    struct SMTNodeBase;

    CMappedTree();
    virtual ~CMappedTree();

    virtual CMappedTree<TIdx,TNode>& operator = (const CMappedTree<TIdx,TNode>& arg_rhs)
    {
      CMappedTree<TIdx,TNode>::deepCopy(&arg_rhs);
      return *this;
    }

    virtual TNode* create(const TIdx& arg_idx, const TNode & arg_node2add,
        const bool arg_is_root_);

    virtual TNode* create(const TIdx& arg_idx, const bool arg_is_root_);

    virtual TNode* insert(const TIdx& arg_idx, TNode *arg_node2add,
        const bool arg_is_root_);

    virtual bool linkNodes();

    virtual const TNode* getRootNodeConst() const
    { return static_cast<const TNode*>(root_node_); }

    virtual TNode* getRootNode()
    { return root_node_; }

    virtual bool isAncestor(const TIdx& arg_idx_child,
        const TIdx& arg_idx_ancestor)  const;

    virtual bool isAncestor(const TNode* arg_node_child,
        const TNode* arg_node_ancestor)  const;

    virtual bool isDescendant(const TIdx& arg_idx_parent,
        const TIdx& arg_idx_descendant)  const;

    virtual bool isDescendant(const TNode* arg_node_parent,
        const TNode* arg_node_descendant)  const;
  }; //End of template class


  template <typename TIdx, typename TNode>
  struct CMappedTree<TIdx,TNode>::SMTNodeBase
  {
  public:
    TIdx name_;
    TIdx parent_name_;
    TNode* parent_addr_;
    std::vector<TNode*> child_addrs_;

    SMTNodeBase()
    {
      name_ = "";
      parent_name_ = "";
      parent_addr_ = NULL;
      child_addrs_.clear();
    }
  };

  /***************************************************************
   *******************************Function Definitions*************
   ****************************************************************
   */

  template <typename TIdx, typename TNode>
  CMappedTree<TIdx,TNode>::CMappedTree()
  {
    root_node_ = NULL;
    has_been_init_ = false;
  }

  template <typename TIdx, typename TNode>
  CMappedTree<TIdx,TNode>::~CMappedTree()
  {}

  template <typename TIdx, typename TNode>
  bool CMappedTree<TIdx,TNode>::
  deepCopy(const CMappedTree<TIdx,TNode>* const arg_mt)
  {//Deep copy.
    bool flag;
    flag = sutil::CMappedList<TIdx,TNode>::
        deepCopy(arg_mt);
    if(true == flag)
    {
      this->root_node_ = CMappedList<TIdx,TNode>::at(arg_mt->getRootNodeConst()->name_);
      this->has_been_init_ = arg_mt->has_been_init_;
      return true;
    }
    else
    { return false; }
  }

  template <typename TIdx, typename TNode>
  TNode* CMappedTree<TIdx,TNode>::create(
      const TIdx& arg_idx, const TNode & arg_node2add,
      const bool arg_is_root_)
      {
    if((arg_is_root_)&&(NULL!=root_node_))
    {
#ifdef DEBUG
      std::cerr<<"\nCMappedTree::create() : Error. Tried to insert a root node when one already exists.";
#endif
      return NULL;
    }

    //Add the node.
    TNode* tLnk =
        sutil::CMappedList<TIdx,TNode>::create(arg_idx,arg_node2add);

    if((arg_is_root_) && (root_node_==NULL))
    { root_node_ = tLnk;  }

    return tLnk;
      }

  template <typename TIdx, typename TNode>
  TNode* CMappedTree<TIdx,TNode>::create(
      const TIdx& arg_idx, const bool arg_is_root_)
      {
    if((arg_is_root_)&&(NULL!=root_node_))
    {
#ifdef DEBUG
      std::cerr<<"\nCMappedTree::create() : Error. Tried to insert a root node when one already exists.";
#endif
      return NULL;
    }

    //Add the node.
    TNode* tLnk = sutil::CMappedList<TIdx,TNode>::create(arg_idx);

    if((arg_is_root_) && (NULL==root_node_))
    { root_node_ = tLnk;  }

    return tLnk;
      }

  template <typename TIdx, typename TNode>
  TNode* CMappedTree<TIdx,TNode>::insert(
      const TIdx& arg_idx, TNode *arg_node2add,
      const bool arg_is_root_)
  {
    if((arg_is_root_)&&(NULL!=root_node_))
    {
#ifdef DEBUG
      std::cerr<<"\nCMappedTree::create() : Error. Tried to insert a root node when one already exists.";
#endif
      return NULL;
    }

    //Add the node.
    TNode* tLnk = sutil::CMappedList<TIdx,TNode>::create(arg_idx,arg_node2add);

    if((arg_is_root_) && (root_node_==NULL))
    { root_node_ = tLnk;  }

    return tLnk;
  }


  template <typename TIdx, typename TNode>
  bool CMappedTree<TIdx,TNode>::linkNodes()
  {
    if(NULL == getRootNodeConst())
    { return false; }

    //Clear previous links (if any)
    typename CMappedList<TIdx,TNode>::iterator it,ite;
    for(it = CMappedList<TIdx,TNode>::begin(),
        ite = CMappedList<TIdx,TNode>::end();
        it != ite; ++it)
    {
      TNode& tmp_node = *it;
      tmp_node.parent_addr_ = NULL;
      tmp_node.child_addrs_.clear();
    }

    //Form the new links
    for(it = CMappedList<TIdx,TNode>::begin(),
        ite = CMappedList<TIdx,TNode>::end();
        it != ite; ++it)
    {
      TNode& tmp_node = *it;
      //Iterate over all nodes and connect them to their
      //parents
      if(&tmp_node == root_node_)
      {//No parents
        has_been_init_ = true;
        continue;
      }
      else
      {
        tmp_node.parent_addr_ =
            sutil::CMappedList<TIdx,TNode>::at(tmp_node.parent_name_);
        if(tmp_node.parent_addr_ == NULL)
        {//No parent -- Ignore this node
#ifdef DEBUG
          std::cerr<<"\nCMappedTree::linkNodes(): Warning.";
          std::cerr<<"Orphan node found: "<<tmp_node.name_<<". Ignoring.";
#endif
          continue;
        }
        tmp_node.parent_addr_->child_addrs_.push_back(&tmp_node);

#ifdef DEBUG
        std::cerr<<"\n\tAdding child "<<tmp_node.name_
            <<" to (parent) "<<tmp_node.parent_addr_->name_;
        std::cerr<<std::flush;
#endif
      }
    }//End of while loop
    return has_been_init_;
  }


  template <typename TIdx, typename TNode>
  bool CMappedTree<TIdx,TNode>::isAncestor(const TIdx& arg_idx_child,
      const TIdx& arg_idx_ancestor) const
  { return isAncestor(this->at_const(arg_idx_child), this->at_const(arg_idx_child));  }

  template <typename TIdx, typename TNode>
    bool CMappedTree<TIdx,TNode>::isAncestor(const TNode* arg_node_child,
      const TNode* arg_node_ancestor)  const
  {
    const TNode *child = arg_node_child;
    if( NULL == child || NULL == arg_node_ancestor)
    { return false; }

    while(NULL != child)
    {
      if(arg_node_ancestor == child)
      { return true; }
      child = child->parent_addr_;
    }
    return false;
  }

  template <typename TIdx, typename TNode>
  bool CMappedTree<TIdx,TNode>::isDescendant(const TIdx& arg_idx_parent,
      const TIdx& arg_idx_descendant) const
  { return isDescendant(this->at_const(arg_idx_parent), this->at_const(arg_idx_descendant)); }

  template <typename TIdx, typename TNode>
  bool CMappedTree<TIdx,TNode>::isDescendant(const TNode* arg_node_parent,
      const TNode* arg_node_descendant)  const
  {
    const TNode *parent = arg_node_parent;
    if( NULL == parent || NULL == arg_node_descendant)
    { return false; }

    if(NULL != parent)
    {
      if(arg_node_descendant == parent)
      { return true; }

      typename std::vector<TNode*>::const_iterator it,ite;
      for(it = parent->child_addrs_.begin(), ite = parent->child_addrs_.end(); it!=ite; ++it)
      {
        if(isDescendant(*it, arg_node_descendant))
        { return true;  }
      }
    }
    return false;
  }

}//End of namespace sutil

#endif /*CMAPPEDTREE_HPP_*/