---

more/gen/nary_tree.h

Go to the documentation of this file.

//  Copyright (C) 2001--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: nary_tree.h,v 1.2 2002/08/24 13:58:38 petter_urkedal Exp $


#ifndef MORE_GEN_NARY_TREE_H
#define MORE_GEN_NARY_TREE_H

#include <iterator>
#include <stdexcept>
#include <algorithm>
#include <more/gen/memory.h>
#include <more/gen/utility.h>


namespace more {
namespace gen {

  using std::swap;

  ///\if bits
  namespace bits {
    struct _nary_tree_node_base : noncopyable
    {
        typedef _nary_tree_node_base self;
        _nary_tree_node_base()
            : m_prev(this), m_next(this), m_parent(0) {}

        self*           prev()          { return m_prev; }
        self const*     prev() const    { return m_prev; }
        self*           next()          { return m_next; }
        self const*     next() const    { return m_next; }

        void unlink()
        {
            m_prev->m_next = m_next;
            m_next->m_prev = m_prev;
            m_parent = 0;
        }

        self* m_prev;
        self* m_next;
        self* m_parent;
    };
  }
  ///\endif

  struct tree_iterator_tag : std::bidirectional_iterator_tag {};

  template<typename T, typename Allocator> class nary_tree;

  ///\if bits
  namespace bits {
    template<typename T> class _nary_tree_node;
    template<typename T> class _nary_tree_iterator;
    template<typename T> class _const_nary_tree_iterator;

    template<typename Node>
      struct _nary_tree_iterator
      {
        private:
          typedef _nary_tree_iterator self;
        public:
          typedef tree_iterator_tag iterator_category;
          typedef typename Node::value_type value_type;
          typedef ptrdiff_t difference_type;
          typedef typename Node::iterator iterator;
          typedef typename Node::const_iterator const_iterator;
          typedef value_type& reference;
          typedef value_type const& const_reference;
          typedef value_type* pointer;

          _nary_tree_iterator() : m_cur(0) {}
          _nary_tree_iterator(_nary_tree_iterator const& it)
              : m_cur(it.m_cur) {}
          _nary_tree_iterator(_nary_tree_node_base* n) : m_cur(n) {}
          _nary_tree_iterator(_nary_tree_node_base const* n) : m_cur(n) {}
          _nary_tree_iterator& operator=(_nary_tree_iterator const& it)
          { m_cur = it.m_cur; return *this; }

          bool operator==(_nary_tree_iterator const& it) const
          { return m_cur == it.m_cur; }
          bool operator!=(_nary_tree_iterator const& it) const
          { return m_cur != it.m_cur; }

          _nary_tree_iterator& operator++()
          { m_cur = m_cur->next(); return *this; }
          _nary_tree_iterator operator++(int)
          { _nary_tree_iterator tmp = *this; ++*this; return tmp; }
          _nary_tree_iterator& operator--()
          { m_cur = m_cur->prev(); return *this; }
          _nary_tree_iterator operator--(int)
          { _nary_tree_iterator tmp = *this; --*this; return tmp; }

          self begin() { return static_cast<Node*>(m_cur)->begin(); }
          self end() { return static_cast<Node*>(m_cur)->end(); }
          bool empty() { return begin() == end(); }

          self parent()
          {
              if (!m_cur->m_parent)
                  throw std::logic_error("_nary_tree_iterator::parent(): "
                                         "Root node has no parent.");
              return static_cast<Node*>(m_cur)->parent();
          }

          reference operator*() { return static_cast<Node*>(m_cur)->value; }
          pointer operator->() { return &static_cast<Node*>(m_cur)->value; }

        private:
          _nary_tree_node_base* m_cur;

          friend class _nary_tree_node<value_type>;
          template<typename U, typename Allocator> friend class nary_tree;
          friend class _const_nary_tree_iterator<Node>;
      };

    template<typename Node>
      struct _const_nary_tree_iterator
      {
          typedef _const_nary_tree_iterator self;
          typedef tree_iterator_tag iterator_category;
          typedef const typename Node::value_type value_type;
          typedef ptrdiff_t difference_type;
          typedef typename Node::iterator iterator;
          typedef typename Node::const_iterator const_iterator;
          typedef value_type& reference;
          typedef value_type const& const_reference;
          typedef value_type* pointer;

          _const_nary_tree_iterator() : m_cur(0) {}
          _const_nary_tree_iterator(_const_nary_tree_iterator const& it)
              : m_cur(it.m_cur) {}
          _const_nary_tree_iterator(_nary_tree_iterator<Node> const& it)
              : m_cur(it.m_cur) {}
          _const_nary_tree_iterator(_nary_tree_node_base* n)
              : m_cur(n) {}
          _const_nary_tree_iterator(_nary_tree_node_base const* n)
              : m_cur(const_cast<_nary_tree_node_base*>(n)) {}
          _const_nary_tree_iterator&
          operator=(_const_nary_tree_iterator const& it)
          { m_cur = it.m_cur; return *this; }

          bool operator==(_const_nary_tree_iterator const& it) const
          { return m_cur == it.m_cur; }
          bool operator!=(_const_nary_tree_iterator const& it) const
          { return m_cur != it.m_cur; }

          _const_nary_tree_iterator& operator++()
          { m_cur = m_cur->next(); return *this; }
          _const_nary_tree_iterator operator++(int)
          { _const_nary_tree_iterator tmp = *this; ++*this; return tmp; }
          _const_nary_tree_iterator& operator--()
          { m_cur = m_cur->prev(); return *this; }
          _const_nary_tree_iterator operator--(int)
          { _const_nary_tree_iterator tmp = *this; --*this; return tmp; }

          self begin() { return static_cast<Node*>(m_cur)->begin(); }
          self end() { return static_cast<Node*>(m_cur)->end(); }
          bool empty() { return begin() == end(); }

          self parent()
          {
              if (!m_cur->m_parent)
                  throw std::logic_error("_const_nary_tree_iterator::parent(): "
                                         "Root node has no parent.");
              return static_cast<Node*>(m_cur)->parent();
          }

          reference operator*() { return static_cast<Node*>(m_cur)->value; }
          pointer operator->() { return &static_cast<Node*>(m_cur)->value; }

        private:
          _nary_tree_node_base* m_cur;

          friend class _nary_tree_node<value_type>;
          template<typename U, typename Allocator> friend class nary_tree;
      };

    template<typename T>
      struct _nary_tree_node
          : protected _nary_tree_node_base
      {
          typedef _nary_tree_node self;
          typedef _nary_tree_node_base node_base;
          typedef _nary_tree_iterator<self> iterator;
          typedef _const_nary_tree_iterator<self> const_iterator;
          typedef T value_type;
          typedef T& reference;
          typedef T const& const_reference;
          typedef T* pointer;
          typedef ptrdiff_t difference_type;
          typedef size_t size_type;

          _nary_tree_node() { m_inf_child.m_parent = this; }
          _nary_tree_node(const_reference x)
              : value(x) { m_inf_child.m_parent = this;}
          ~_nary_tree_node() { unlink(); }

          self* parent() { return static_cast<self*>(m_parent); }
          self const* parent() const {
              return static_cast<self const*>(m_parent);
          }

          iterator begin() { return inf_child()->next(); }
          iterator end()   { return inf_child(); }
          const_iterator begin() const { return inf_child()->next(); }
          const_iterator end()   const { return inf_child(); }

          iterator insert(iterator it_pos, _nary_tree_node* v);
          _nary_tree_node* erase(iterator it_pos);

        private:
          node_base* inf_child() { return &m_inf_child; }
          node_base const* inf_child() const { return &m_inf_child; }

          _nary_tree_node_base m_inf_child;
          value_type value;

          friend class iterator;
          friend class const_iterator;
          template<typename U, typename Allocator> friend class nary_tree;
      };
  } // bits
  ///\endif

  /** \class nary_tree nary_tree.h more/gen/nary_tree.h
   **
   ** A tree with variable number of branches on each node.  See also
   ** <tt>ntree</tt>. */
  template< typename T, typename Allocator = gen::allocator<T> >
    struct nary_tree
    {
        typedef Allocator allocator_type;
        typedef bits::_nary_tree_node<T> node_type;
      private:
        typedef typename allocator_type::rebind<node_type>::other
                real_allocator_type;
      public:
        typedef typename node_type::iterator iterator;
        typedef typename node_type::const_iterator const_iterator;
        typedef typename node_type::pointer pointer;
        typedef typename node_type::reference reference;
        typedef typename node_type::const_reference const_reference;
        typedef typename node_type::size_type size_type;
        typedef typename node_type::difference_type difference_type;

        nary_tree()
            : m_root(m_alloc.allocate(1))
        {
            m_alloc.construct(m_root);
        }

        nary_tree(nary_tree const& tr)
            : m_root(m_alloc.allocate(1))
        {
            m_alloc.construct(m_root);
            copy_node(tr.m_root, m_root);
        }

        ~nary_tree()
        {
            clear();
            m_alloc.destroy(m_root);
            m_alloc.deallocate(m_root, 1);
        }

        nary_tree&
        operator=(nary_tree const& tr)
        {
            clear();
            copy_node(tr.m_root, m_root);
            return *this;
        }

        struct swapper
        {
            swapper()
                : m_root(m_alloc.allocate(1))
            {
                m_alloc.construct(m_root);
            }
            swapper(nary_tree& t)
                : m_root(m_alloc.allocate(1))
            {
                m_alloc.construct(m_root);
                std::swap(m_root, t.m_root);
            }
            swapper(swapper& sw)
                : m_root(m_alloc.allocate(1))
            {
                m_alloc.construct(m_root);
                std::swap(m_root, sw.m_root);
            }
            swapper& operator=(nary_tree& t)
            {
                std::swap(m_root, t.m_root);
                return *this;
            }
            swapper& operator=(swapper& sw)
            {
                std::swap(m_root, sw.m_root);
                return *this;
            }
            ~swapper()
            {
                nary_tree t(*this);
                m_alloc.destroy(m_root);
                m_alloc.deallocate(m_root, 1);
            }

          private:
            swapper(swapper const&) {}
            swapper& operator=(swapper const&) {}

            node_type* m_root;
            real_allocator_type m_alloc;
            friend class nary_tree;
        };

        nary_tree(swapper& sw)
            : m_root(m_alloc.allocate(1))
        {
            m_alloc.construct(m_root);
            std::swap(m_root, sw.m_root);
        }

        nary_tree& operator=(swapper& sw)
        {
            std::swap(m_root, sw.m_root);
            return *this;
        }

        void set_root(const_reference x)
        {
            m_root->value = x;
        }

        iterator        root() { return iterator(m_root); }
        const_iterator  root() const { return const_iterator(m_root); }

        iterator insert(iterator it_pos, const_reference v)
        {
            node_type* n_new = m_alloc.allocate(1);
            m_alloc.construct(n_new);
            n_new->value = v;
            return static_cast<node_type*>(it_pos.m_cur->m_parent)
                ->insert(it_pos, n_new);
        }

        iterator erase(iterator it_pos)
        {
            node_type* n_old = static_cast<node_type*>(it_pos.m_cur);
            erase(n_old->begin(), n_old->end());
            node_type* n_next = static_cast<node_type*>(n_old->m_next);
            m_alloc.destroy(n_old);
            m_alloc.deallocate(n_old, 1);
            return iterator(n_next);
        }

        void erase(iterator first, iterator last)
        {
            while (first != last)
                first = erase(first);
        }

        void clear() { erase(m_root->begin(), m_root->end()); }

        void swap(nary_tree& x)
        {
            std::swap(m_root, x.m_root);
        }

      private:
        void copy_node(node_type const* src, node_type* dst);

        real_allocator_type m_alloc;
        node_type* m_root;
    };

  template<typename TreeIterator0, typename TreeIterator1>
    bool
    subtree_counted_equal(TreeIterator0 it0, TreeIterator0 it0end,
                          TreeIterator1 it1, TreeIterator1 it1end)
    {
        for (;;) {
            if (it0 == it0end)
                return it1 == it1end;
            if (it1 == it1end)
                return false;
            if (*it0 != *it1)
                return false;
            if (!subtree_counted_equal(it0.begin(), it0.end(),
                                       it1.begin(), it1.end()))
                return false;
            ++it0;
            ++it1;
        }
    }

  template<typename T0, typename T1>
    bool
    operator==(nary_tree<T0> const& t0, nary_tree<T1> const& t1)
    {
        return *t0.root() == *t1.root()
            && subtree_counted_equal(t0.root().begin(), t0.root().end(),
                                     t1.root().begin(), t1.root().end());
    }

  template<typename T, typename Allocator>
    inline void
    nary_tree<T, Allocator>::copy_node(node_type const* src, node_type* dst)
    {
        dst->value = src->value;
        for (typename node_type::const_iterator it = src->begin();
             it != src->end(); ++it) {
            node_type* nd = m_alloc.allocate(1);
            m_alloc.construct(nd);
            copy_node(static_cast<node_type const*>(it.m_cur), nd);
            dst->insert(dst->end(), nd);
        }
    }

  template<typename T, typename Allocator>
    inline void
    swap(nary_tree<T, Allocator>& x, nary_tree<T, Allocator>& y)
    {
        x.swap(y);
    }

  template<typename TreeIterator>
    void
    subtree_dump(TreeIterator it, std::ostream& os,
                 int level = 0, unsigned int cont = 0)
    {
        if (level) {
            for (int i = 0; i < level; ++i)
                os << (cont & (1<<i)? "|  " : "   ");
            os << "|\n";
        }
        for (int i = 0; i < level; ++i)
            os << (cont & (1<<i)? "|  " : "   ");
        os << (level? '+' : '-')
           << (it.empty()? "----" : "--+-") << *it << '\n';
        cont |= 2<<level;
        for (TreeIterator it_sub = it.begin(); it_sub != it.end(); ++it_sub) {
            if (it_sub == --it.end())
                cont &= ~(2<<level);
            subtree_dump(it_sub, os, level+1, cont);
        }
    }

  ///\if bits
  namespace bits {
    template<typename T>
      typename _nary_tree_node<T>::iterator
      _nary_tree_node<T>::insert(iterator it_pos, _nary_tree_node* n_new)
      {
          node_base* n_pos = it_pos.m_cur;
          n_new->m_next = n_pos;
          n_new->m_prev = n_pos->m_prev;
          n_pos->m_prev = n_new;
          n_new->m_prev->m_next = n_new;
          n_new->m_parent = this;
          return iterator(n_new);
      }

    template<typename T>
      _nary_tree_node<T>*
      _nary_tree_node<T>::erase(iterator it_pos)
      {
          self* n_pos = static_cast<self*>(it_pos.m_cur);
          node_base* n_next = n_pos->m_next;
          n_pos->m_prev->m_next = n_next;
          n_next->m_prev = n_pos->m_prev;
          return n_pos;
      }
  } // bits
  ///\endif

}} // more::gen

#endif

---