---

more/gen/ntree.h

Go to the documentation of this file.

//  Copyright (C) 2002  Petter Urkedal
//
//  This file is free software; 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.
//
//  This file 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 General Public License
//  along with this program; if not, write to the Free Software
//  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
//
//  As a special exception, you may use this file as part of a free
//  software library without restriction.  Specifically, if other files
//  instantiate templates or use macros or inline functions from this
//  file, or you compile this file and link it with other files to
//  produce an executable, this file does not by itself cause the
//  resulting executable to be covered by the GNU General Public
//  License.  This exception does not however invalidate any other
//  reasons why the executable file might be covered by the GNU General
//  Public License.
//
//  $Id: ntree.h,v 1.3 2002/08/24 13:58:38 petter_urkedal Exp $


#ifndef MORE_GEN_NTREE_H
#define MORE_GEN_NTREE_H

#include <more/gen/memory.h>
#include <list>


namespace more {
namespace gen {

  /** \class ntree ntree.h more/gen/ntree.h
   ** An general tree.  This is a alternative to the nary_tree, and
   ** this should work better with mutating algorithms. */
  template< typename T,
            template<typename X, typename A>
                class BranchContainer = std::list,
            typename Allocator = gen::allocator<T> >
  struct ntree
  {
      typedef Allocator allocator_type;
      typedef typename allocator_type::value_type value_type;
      typedef typename allocator_type::reference reference;
      typedef typename allocator_type::const_reference const_reference;
      typedef typename allocator_type::pointer pointer;
      typedef typename allocator_type::size_type size_type;

    private:
      typedef typename allocator_type::rebind<ntree>::other
              ntree_allocator_type;
      typedef BranchContainer<ntree, ntree_allocator_type> internal_branch_cont;
    public:

    private:
      class swapper;

      struct node
      {
          typedef typename internal_branch_cont::iterator
                  iterator;
          typedef typename internal_branch_cont::const_iterator
                  const_iterator;

        public:
          node()
              : m_stem_node(0) {}

        private:
          explicit node(node* stem)
              : m_stem_node(stem) {}

          node(node* stem, value_type const& x)
              : m_stem_node(stem),
                m_value(x) {}

        public:
          node(node const& x)
              : m_branches(x.m_branches),
                m_stem_node(0),
                m_value(x.m_value)
          {
              for (iterator it = m_branches.begin();
                   it != m_branches.end(); ++it)
                  it->m_node->m_stem_node = this;
          }

        public:
          iterator begin() { return m_branches.begin(); }
          iterator end() { return m_branches.end(); }

          const_iterator begin() const
          { return m_branches.begin(); }

          const_iterator end() const
          { return m_branches.end(); }

          bool empty() const { return m_branches.empty(); }

          iterator
          insert(iterator it, const_reference x)
          {
              ntree t(x);
              iterator it_ins = m_branches.insert(it, t);
              it_ins->m_stem_node = this;
              return it_ins;
          }

          iterator
          erase(iterator it)
          {
              return m_branches.erase(it);
          }

          iterator
          erase(iterator it, iterator it_end)
          {
              return m_branches.erase(it);
          }

          void
          clear()
          {
              m_branches.clear();
          }

          void
          push_front(const_reference x)
          {
              ntree t(x);
              m_branches.push_front(t);
              m_branches.front().m_node->m_stem_node = this;
          }

          void
          push_back(const_reference x)
          {
              ntree t(x);
              m_branches.push_back(t);
              m_branches.back().m_node->m_stem_node = this;
          }

          ntree& front() { return m_branches.front(); }
          ntree& back() { return m_branches.back(); }

        private:
          internal_branch_cont m_branches;
          node* m_stem_node;
          value_type m_value;
          ntree* m_owner;  // handled by ntree

          friend class ntree;
          friend class swapper;
      };

      typedef typename allocator_type::rebind<node>::other
              node_allocator_type;

    public:
      typedef node branch_container;
      typedef typename branch_container::iterator branch_iterator;
      typedef typename branch_container::const_iterator branch_const_iterator;

      /** Construct a tree with a default constructed root node
       ** only. */
      ntree()
          : m_node(s_alloc.allocate(1))
      {
          s_alloc.construct(m_node);
          m_node->m_owner = this;
      }

      /** Construct a tree with only a root node of value \a x. */
      explicit ntree(const_reference x)
          : m_node(s_alloc.allocate(1))
      {
          s_alloc.construct(m_node);
          m_node->m_value = x;
          m_node->m_owner = this;
      }

      /** Construct a deep copy of \a t. */
      ntree(ntree const& t)
          : m_node(s_alloc.allocate(1))
      {
          s_alloc.construct(m_node, *t.m_node);
          m_node->m_owner = this;
      }

      /** Assign a deep copy of \a t. */
      ntree& operator=(ntree const& t)
      {
          s_alloc.destroy(m_node);
          s_alloc.construct(m_node, *t.m_node);
          m_node->m_owner = this;
          return *this;
      }

      /** Destruct. */
      ~ntree()
      {
          s_alloc.destroy(m_node);
          s_alloc.deallocate(m_node, 1);
      }

      /** A class which can be used to move all nodes of a tree to
       ** another tree without copying.  This class can be used as a
       ** return type in place of \c ntree itself to avoid redundant
       ** copying.  */
      struct swapper
      {
          swapper()
              : m_node(s_alloc.allocate(1))
          {
              s_alloc.construct(m_node);
              m_node->m_owner = 0;
          }

          /** Take the nodes of \a t and replace them with none. */
          swapper(ntree& t)
              : m_node(s_alloc.allocate(1))
          {
              s_alloc.construct(m_node);
              m_node->m_owner = &t;
              std::swap(m_node, t.m_node);
              m_node->m_owner = 0;
          }

          /** Swap the nodes with those of \a t. */
          swapper& operator=(swapper& t)
          {
              m_node->m_owner = &t;
              std::swap(m_node, t.m_node);
              m_node->m_owner = 0;
              return *this;
          }

          /** Destroy the nodes. */
          ~swapper()
          {
              s_alloc.destroy(m_node);
          }

          friend class ntree;

        private:
          mutable node* m_node;
      };

      /** Take the nodes of \a sw and replace them with none. */
      ntree(swapper const& sw)
          : m_node(s_alloc.allocate(1))
      {
          s_alloc.construct(m_node);
          m_node->m_owner = 0;
          std::swap(m_node, sw.m_node);
          m_node->m_owner = this;
      }

      /** Swap nodes with \a sw. */
      ntree& operator=(swapper const& sw)
      {
          m_node->m_owner = 0;
          std::swap(m_node, sw.m_node);
          m_node->m_owner = this;
          return *this;
      }

      /** Return true if this tree's top node is the root of the whole
       ** tree. */
      bool is_root() const { return m_node->m_stem_node == 0; }

      /** Return the tree of which this is a subtree.
       ** \pre The top node is not the root. */
      ntree& stem()
      {
#  ifndef MORE_NDEBUG
          if (is_root())
              throw std::logic_error("more::gen::ntree: "
                                     "Requested stem of the root.");
#  endif
          return *m_node->m_stem_node->m_owner;
      }

      /** Return the tree of which this is a subtree.
       ** \pre The top node is not the root. */
      ntree const& stem() const
      {
#  ifndef MORE_NDEBUG
          if (is_root())
              throw std::logic_error("more::gen::ntree: "
                                     "Requested stem of the root.");
#  endif
          return *m_node->m_stem_node->m_owner;
      }

      /** Return a container of the immediate branches.  The container
       ** has \c begin() and \c end() methods.  */
      branch_container const& branches() const { return *m_node; }
      /** Return a container of the immediate branches.  The container
       ** has \c begin() and \c end() methods. */
      branch_container& branches() { return *m_node; }

      /** Return the value of the topmost node. */
      reference value() { return m_node->m_value; }
      /** Return the value of the topmost node. */
      const_reference value() const { return m_node->m_value; }

      /** Return the result of a deep comparison with \c rhs. */
      bool operator==(ntree const& rhs) const
      {
          return m_node->m_value == rhs.m_node->m_value
              && m_node->m_branches == m_node->m_branches;
      }

      /** Clear all branches and set the root value to a default
       ** constructed instance of \c value_type. */
      void clear()
      {
          m_node->m_branches.clear();
          m_node->m_value = value_type();
      }

    private:
      node* m_node;

      static node_allocator_type s_alloc;
  };

  template< typename T,
            template<typename X, typename A>
                class BranchContainer = std::list,
            typename Allocator = gen::allocator<T> >
  typename ntree<T, BranchContainer, Allocator>::node_allocator_type
      ntree<T, BranchContainer, Allocator>::s_alloc;


}}

#endif

---