binary_tree.h

Go to the documentation of this file.

#ifndef _BINARYTREE_H_
#define _BINARYTREE_H_

// includes from STL
#include <list>
#include <queue>
#include <set>

// includes from BOOST
#include <boost/array.hpp>
#include <boost/type_traits.hpp>
#include <boost/utility/enable_if.hpp>

// includes from TIL
#include "globalTraits.h"

namespace til
{

  //---------------------------------------------------------------------------
  
    //------------//
   //  NaryTree  //
  //------------//
  
  template < typename T, std::size_t N >
  class NaryTree
  {
  public: // exceptions -------------------------------------------------------
  
    class TreeRootAlreadyDefined : public std::exception {};
    
  public: // classes ----------------------------------------------------------
  
    class iterator;
    class const_iterator;
  
  private: // classes ---------------------------------------------------------
  
    template < typename X > class iterator_base;
    class Node;
    struct Destructor;

  public: // constructors & destructor ----------------------------------------

    NaryTree() : m_root(), m_size() {}

    ~NaryTree();

  public: // set & get --------------------------------------------------------

    std::size_t size() const { return m_size; }

  public: // functions --------------------------------------------------------

    const_iterator
    root() const;

    iterator 
    root();

    iterator 
    addChild
    (
      Node * parent
    , std::size_t childNumber
    , T value = T()
    );

    iterator
    addChild
    (
      iterator & parent
    , std::size_t childNumber
    , T value = T()
    );

  private: // data ------------------------------------------------------------

    Node * m_root;  
    std::size_t m_size;
  };
  

  //---------------------------------------------------------------------------

    //------------------//
   //  NaryTree::Node  //
  //------------------//
  
  template < typename T, std::size_t N >
  class NaryTree<T,N>::Node
  {
  public: // typedefs ---------------------------------------------------------
  
    typedef T value_type; 
   
  public: // constructors -----------------------------------------------------
  
    Node() :
        m_value()
      , m_branch()
    {
      m_branch.assign(0);
    }
  
    explicit Node(const T & value) :
        m_value(value)
      , m_branch()
    {
      m_branch.assign(0);
    }
    
  public: // set & get --------------------------------------------------------
  
    const T & operator()() const { return m_value; }
    T & operator()() { return m_value; }
  
    const T & get() const { return m_value; }
    T & get() { return m_value; }
  
    Node * child(std::size_t i) const
    {
      assert(i < til::size(m_branch));
      return m_branch[i];
    }
  
    Node * & child(std::size_t i)
    {
      assert(i < til::size(m_branch));
      return m_branch[i];
    }
    
    void operator=(const T & value) { m_value = value; }
  
  private: // data ------------------------------------------------------------
  
    // Index to the current value
    T m_value;
    // pointers to branches
    boost::array<Node*, N> m_branch;  
  };


  //---------------------------------------------------------------------------

    //---------------------------//
   //  NaryTree::iterator_base  //
  //---------------------------//
  
  template < typename T, std::size_t N >
  // NB: It is understood that X is a Node
  template < typename X >
  class NaryTree<T,N>::iterator_base
  {
  public: // typedefs
    typedef iterator_base<X>                Self;
    typedef typename X::value_type          value_type;
    
  public: // constructors & destructor ----------------------------------------
  
    iterator_base() {}
    explicit iterator_base(X * pNode) : m_pNode(pNode) {}
  
  public: // functions --------------------------------------------------------
  
    const value_type & operator*() const { return m_pNode->get(); }
    const value_type * operator->() const { return &(m_pNode->get()); }
  
    operator X*() { return m_pNode; }
    X * node() const { return m_pNode; }
  
  public: // static functions -------------------------------------------------
  
    static std::size_t nchildren() { return N; }
  
  protected: // functions -----------------------------------------------------
  
    X * child(std::size_t i) const { return this->node()->child(i); }
  
  protected: // data ----------------------------------------------------------
  
    X * m_pNode;
  };
  
  //---------------------------------------------------------------------------
  
    //----------------------------//
   //  NaryTree::const_iterator  //
  //----------------------------//
  
  template < typename T, std::size_t N >
  //class NaryTree<T,N>::const_iterator : public iterator_base<const Node>
  class NaryTree<T,N>::const_iterator : public NaryTree<T,N>::template iterator_base<const Node>
  {
  public: // typedefs ---------------------------------------------------------
  
    typedef const_iterator                  Self;
    typedef iterator_base<const Node>       Base;
    typedef typename Base::value_type       value_type;
  
  public: // constructors -----------------------------------------------------
  
    // NB: default constructor set const_iterator to zero
    const_iterator() : Base() {}
    explicit const_iterator(const Node * p) : Base(p) {}
  
  public: // functions --------------------------------------------------------
  
    Self child(std::size_t i) const { return Self(this->Base::child(i)); }
  };
  
  //---------------------------------------------------------------------------
  
    //----------------------//
   //  NaryTree::iterator  //
  //----------------------//
  
  // TODO: get rid of code duplication with const_iterator if possible.
  // TODO: the advertising of parent() and branch() is not cool -- this is more of
  // an internal stuff.
  template < typename T, std::size_t N >
  class NaryTree<T,N>::iterator : public NaryTree<T,N>::template iterator_base<Node>
  {
  public: // typedefs ---------------------------------------------------------
  
    typedef iterator_base<Node>             Base;
    typedef typename Base::value_type       value_type;
    
  public: // constructors -----------------------------------------------------
  
    // NB: default constructor set iterator to zero
    iterator() : Base(), m_parent() {}
    iterator(Node * p) : Base(p) {}
    iterator(Node * p, Node * parent, std::size_t branch) : Base(p), m_parent(parent), m_branch(branch) {}
    //iterator(const iterator &i) : TCollection::iterator(i) {}
  
  public: // functions --------------------------------------------------------
  
    //operator Node* () { return &**this; }
  
    iterator child(std::size_t i) const
    {
      // NB: no need to assert here, as it is done in Node
      return iterator(this->node()->child(i), this->node(), 0);
    }
  
    std::size_t branch() const { return m_branch; }
  
    Node * parent() const { return m_parent; }
  
    value_type & operator*() { return this->m_pNode->get(); }
    value_type * operator->() { return &(this->m_pNode->get()); }
  
  private: // data ------------------------------------------------------------
  
    // The private information of the non-const iterator contains information
    // necessary in case of a new allocation, i.e. its relation with its parent.
  
    // Pointer on the parent  
    Node * m_parent;
    // Branch number on which we lie.
    std::size_t m_branch;
  };
  
  template < typename T, std::size_t N >
  inline
  std::size_t
  size(const NaryTree<T,N> & ntree) { return ntree.size(); }
  

  //---------------------------------------------------------------------------

    //-----------------------------//
   //  inline methods and structs //
  //-----------------------------//

  template < typename T, std::size_t N >
  struct NaryTree<T, N>::Destructor
  {
    void operator()(iterator i) const { delete &*i; }
  };

  template < typename T, std::size_t N >
  inline typename NaryTree<T, N>::const_iterator
  NaryTree<T, N>::root() const
  { return const_iterator(m_root); }

  template < typename T, std::size_t N >
  inline typename NaryTree<T, N>::iterator
  NaryTree<T, N>::root()
  { return iterator(m_root, 0, 0); }

  template < typename T, std::size_t N >
  inline typename NaryTree<T, N>::iterator
  NaryTree<T, N>::addChild
  (
    iterator & parent
  , std::size_t childNumber
  , T value
  )
  { return this->addChild(parent.node(), childNumber, value); }


  //---------------------------------------------------------------------------
  
    //------------------------//
   //  functors and helpers  //
  //------------------------//


  
  namespace treeFunctors
  {
    // a dummy functor to test tree traversals.
    template < typename TTreeIterator >
    class Count
    {
    public: // constructors & destructor
      Count() : m_count() {}
      
    public: // functions
      static bool leftFirst() { return true; }
      static bool left() { return true; }
      static bool right() { return true; }
  
      void operator()(const TTreeIterator &) { ++m_count; }
      std::size_t operator()() { return m_count; }
  
    private:
      std::size_t m_count;
    };
  }

  
  //---------------------------------------------------------------------------
  
  template < typename TTreeIterator, typename TTreeFunctor >
  void pre_order_scan(TTreeIterator iTree, TTreeFunctor & f)
  {
    f(iTree);
    for (std::size_t i=0; i < iTree.nchildren(); ++i)
    {
      if (&*(iTree.child(i))) pre_order_scan(iTree.child(i), f);
    }
  }
  
  //---------------------------------------------------------------------------

  template < typename TTreeIterator, typename TTreeFunctor >
  void post_order_scan(TTreeIterator iTree, const TTreeFunctor & f)
  {
    for (std::size_t i=0; i < iTree.nchildren(); ++i)
    {
      if (&*(iTree.child(i))) post_order_scan(iTree.child(i), f);
    }
    f(iTree);
  }
  
  //---------------------------------------------------------------------------

  template < typename TTreeIterator, typename TTreeFunctor >
  void
  in_order_scan(TTreeIterator iTree, const TTreeFunctor & f)
  {  
    while (iTree)
    {
      if (&*(iTree.child(0))) in_order_scan(iTree->child(0));
      f(iTree);
      iTree = iTree.child(1);
    }
  }
  
  //---------------------------------------------------------------------------

  namespace detail
  {
    template < typename TTreeIterator, typename TBFFunctor >
    void breadth_first(std::queue<TTreeIterator> q, const TBFFunctor & f)
    {
      std::queue<TTreeIterator> newQ;
      while (!q.empty())
      {
        f(q.front());
        for (std::size_t i = 0; i < q.front().nchildren(); ++i)
        {
          if (q.front().child(i)) newQ.push(q.front().child(i));
        }
        q.pop();
      }
      if (!newQ.empty())
      {
        // warn functor that we are about to go to the next level  
        f.nextLevel();
        // iterate
        breadth_first(newQ, f);
      }
    }
  } // namespace detail
  
  //---------------------------------------------------------------------------

  template < typename TTreeIterator, typename TBFFunctor >
  void breadth_first(TTreeIterator iTree, const TBFFunctor & f)
  {
    // Do nothing if nothing to be done.
    if (!&*iTree) return;
    // Here, we simply construct a queue containing a single element, and call
    // the appropriate version of breadth_first.
    std::queue<TTreeIterator> q;
    q.push(iTree);
    detail::breadth_first(q, f);
  }
  
  //---------------------------------------------------------------------------

  namespace detail
  {
    struct Print
    {
      static void nextLevel() { std::cout << std::endl; }
  
      template < typename TIterator >
      void operator()(const TIterator & i) const
      {
        if (&*i)
        {
          std::cout << *i << " , ";
        }
        else 
        {
          std::cout << " [X] , ";
        }      
      }
    };
  } // namespace detail
  
  //---------------------------------------------------------------------------

  template < typename T, std::size_t N >
  void print(const NaryTree<T,N> & tree)
  {
    breadth_first(tree.root(), detail::Print());
  }

  //---------------------------------------------------------------------------

} // namespace til

// package include
#include "binary_tree.tpp"

#endif //_BINARYTREE_H_