---

general_tree.hh

/*
*  Name:      general_tree.hh
*  Author:    Rafael Jesus Alcantara Perez
*  Summary:   General tree class
*  Date:      $Date: 2003/04/14 00:18:35 $
*  Revision:  $Revision: 1.1 $
*
*  Copyright (C) 2000-2001  Rafael Jesus Alcantara Perez <rafa@dedalo-ing.com>
*
*  This program 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 program 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.
*/

#ifndef _MPCL_UTIL_COLLECTION_GENERAL_TREE__
#define _MPCL_UTIL_COLLECTION_GENERAL_TREE__

#include <algorithm>
#include <cstddef>
#include <functional>
#include <iterator>
#include <memory>
#include <utility>
#include "../../exceptions.hh"
#include "../../memory/alloc_smart_pointer.hh"
#include "../../memory/smart_pointer.hh"
#include "../general-functions.hh"


namespace mpcl
{

  namespace util
  {

    namespace collection
    {

      template < typename TItem                                               ,
                 template <typename TItemA> class TAllocator = std::allocator >
      class TTreeNode
      {

        public:

          typedef
            memory::TAllocSmartPointer<TTreeNode, TAllocator>
            alloc_smart_pointer;

          typedef
            const TItem&
            const_reference;

          typedef
            TItem*
            pointer;

          typedef
            TItem&
            reference;

          typedef
            TItem
            value_type;

          typedef
            std::size_t
            size_type;


        public:

          TItem   tItem;

          TTreeNode*   ptLeftNode;

          TTreeNode*   ptParentNode;

          alloc_smart_pointer   qtFirstChildNode;

          alloc_smart_pointer   qtRightNode;


        public:

          //
          //  C O N S T R U C T O R S
          //

          static alloc_smart_pointer _copy ( const alloc_smart_pointer& rkqtNODE     ,
                                             TTreeNode*&                rptNODE_HEAP );

          static alloc_smart_pointer _copy ( alloc_smart_pointer&       rqtTARGET_NODE ,
                                             const alloc_smart_pointer& rkqtNODE       ,
                                             TTreeNode*&                rptNODE_HEAP   )
            throw (TConstraintException);

          static alloc_smart_pointer _copySiblings ( const alloc_smart_pointer& rkqtNODE       ,
                                                     const TTreeNode*           pktPARENT_NODE ,
                                                     TTreeNode*&                rptNODE_HEAP   );

          static TTreeNode* _create (const TItem& rktITEM, TTreeNode* ptNODE_HEAP)
          {
            TAllocator<TTreeNode>().construct (ptNODE_HEAP, rktITEM);
            return ptNODE_HEAP;
          }

          static void _link ( alloc_smart_pointer& qtLEFT_NODE  ,
                              alloc_smart_pointer& qtRIGHT_NODE )
          {
            qtRIGHT_NODE->ptParentNode = qtLEFT_NODE->ptParentNode;
            qtRIGHT_NODE->ptLeftNode   = qtLEFT_NODE;
            qtLEFT_NODE->qtRightNode   = qtRIGHT_NODE;
          }

          static void _link ( alloc_smart_pointer& qtLEFT_NODE   ,
                              alloc_smart_pointer& qtMIDDLE_NODE ,
                              alloc_smart_pointer& qtRIGHT_NODE  )
          {
            qtMIDDLE_NODE->ptParentNode = qtLEFT_NODE->ptParentNode;
            qtMIDDLE_NODE->ptLeftNode   = qtLEFT_NODE;
            qtMIDDLE_NODE->qtRightNode  = qtRIGHT_NODE;
            qtLEFT_NODE->qtRightNode    = qtMIDDLE_NODE;
            qtRIGHT_NODE->ptLeftNode    = qtMIDDLE_NODE;
          }

          static void _unlink (TTreeNode* ptTARGET_NODE)
            throw (TConstraintException);


        public:

          //
          //  C O N S T R U C T O R S
          //

          TTreeNode (const TItem& rktITEM) :
            tItem            (rktITEM)     ,
            ptLeftNode       (NULL)        ,
            ptParentNode     (NULL)        ,
            qtFirstChildNode ()            ,
            qtRightNode      ()            {}

          void insert (alloc_smart_pointer& rqtTARGET_NODE)
            throw (TConstraintException);


        public:

          //
          //  S E L E C T O R S
          //

          size_type height (void) const;

          const TTreeNode* parent (void) const
          {
            return ptParentNode;
          }

          size_type size (void) const;

      };  // class TTreeNode

      template < typename TItem                                                 ,
                 template <typename TItemA> class TAllocator = std::allocator   ,
                 typename TNode                              = TTreeNode<TItem> >
      class TGeneralTree;

      template <typename TItem, template <typename TItemA> class TAllocator = std::allocator>
      class TGeneralTreeSideIterator;

      template <typename TItem, template <typename TItemA> class TAllocator = std::allocator>
      class TGeneralTreePreIterator;

      template <typename TItem, template <typename TItemA> class TAllocator>
      class TGeneralTreePreIterator :
        public std::iterator<std::forward_iterator_tag, TItem>
      {

          template < typename TItemB                              ,
                     template <typename TItemC> class TAllocatorB ,
                     typename TNodeB                              >
          friend class TGeneralTree;

          template <typename TItemB, template <typename TItemC> class TAllocatorB>
          friend class TGeneralTreeSideIterator;


        private:

          TTreeNode<TItem, TAllocator>*   ptCurrentNode;


        public:

          typedef
            typename std::iterator<std::forward_iterator_tag, TItem>::difference_type
            difference_type;

          typedef
            typename std::iterator<std::forward_iterator_tag, TItem>::iterator_category
            iterator_category;

          typedef
            typename std::iterator<std::forward_iterator_tag, TItem>::pointer
            pointer;

          typedef
            typename std::iterator<std::forward_iterator_tag, TItem>::reference
            reference;

          typedef
            typename std::iterator<std::forward_iterator_tag, TItem>::value_type
            value_type;


        public:

          //
          //  C O N S T R U C T O R S
          //

          TGeneralTreePreIterator (void)                           :
            std::iterator<std::forward_iterator_tag, TItem> ()     ,
            ptCurrentNode                                   (NULL) {}

          TGeneralTreePreIterator (const TTreeNode<TItem, TAllocator>* pktNODE)                                   :
            std::iterator<std::forward_iterator_tag, TItem> ()                                                    ,
            ptCurrentNode                                   (const_cast<TTreeNode<TItem, TAllocator>*> (pktNODE)) {}

          TGeneralTreePreIterator (const TGeneralTreeSideIterator<TItem, TAllocator>& rktSIDE_ITERATOR) :
            std::iterator<std::forward_iterator_tag, TItem> ()                                          ,
            ptCurrentNode                                   (rktSIDE_ITERATOR.ptCurrentNode)            {}

          TGeneralTreePreIterator& operator ++ (void)
            throw (TConstraintException);

          TGeneralTreePreIterator operator ++ (int)
          {
            TGeneralTreePreIterator   tCopy (*this);

            operator ++();
            return tCopy;
          }

          TGeneralTreePreIterator&
          operator = (const TGeneralTreePreIterator<TItem, TAllocator>& rktPRE_ITERATOR)
          {
            ptCurrentNode = rktPRE_ITERATOR.ptCurrentNode;
            return *this;
          }

          TGeneralTreePreIterator&
          operator = (const TGeneralTreeSideIterator<TItem, TAllocator>& rktSIDE_ITERATOR)
          {
            ptCurrentNode = rktSIDE_ITERATOR.ptCurrentNode;
            return *this;
          }


        public:

          //
          //  S E L E C T O R S
          //

          TGeneralTreePreIterator leftChild (void) const
          {
            if ( !ptCurrentNode )
            {
              throw TConstraintException ("empty node", __FILE__, __LINE__);
            }
            return TGeneralTreePreIterator (ptCurrentNode->qtFirstChildNode.get());
          }

          pointer operator -> (void) const
            throw (TConstraintException)
          {
            if ( !ptCurrentNode )
            {
              throw TConstraintException ("empty node", __FILE__, __LINE__);
            }
            return &(ptCurrentNode->tItem);
          }

          bool operator == (const TGeneralTreePreIterator& rktITERATOR) const
          {
            return ( ptCurrentNode == rktITERATOR.ptCurrentNode );
          }

          bool operator == (const TGeneralTreeSideIterator<TItem, TAllocator>& rktSIDE_ITERATOR) const
          {
            return ( ptCurrentNode == rktSIDE_ITERATOR.ptCurrentNode );
          }

          bool operator != (const TGeneralTreeSideIterator<TItem, TAllocator>& rktSIDE_ITERATOR) const
          {
            return ( ptCurrentNode != rktSIDE_ITERATOR.ptCurrentNode );
          }

          reference operator * (void) const
            throw (TConstraintException)
          {
            if ( !ptCurrentNode )
            {
              throw TConstraintException ("empty node", __FILE__, __LINE__);
            }
            return ptCurrentNode->tItem;
          }

          TGeneralTreePreIterator rightSibling (void) const
          {
            if ( !ptCurrentNode )
            {
              throw TConstraintException ("empty node", __FILE__, __LINE__);
            }
            return TGeneralTreePreIterator (ptCurrentNode->qtRightNode);
          }

      };  // class TGeneralTreePreIterator

      template <typename TItem, template <typename TItemA> class TAllocator>
      class TGeneralTreeSideIterator :
        public std::iterator<std::forward_iterator_tag, TItem>
      {

          template < typename TItemB                              ,
                     template <typename TItemA> class TAllocatorB ,
                     typename TNodeB                              >
          friend class TGeneralTree;

          template <typename TItemB, template <typename TItemC> class TAllocatorB>
          friend class TGeneralTreePreIterator;


        public:

          typedef
            typename std::iterator<std::forward_iterator_tag, TItem>::difference_type
            difference_type;

          typedef
            typename std::iterator<std::forward_iterator_tag, TItem>::iterator_category
            iterator_category;

          typedef
            typename std::iterator<std::forward_iterator_tag, TItem>::pointer
            pointer;

          typedef
            typename std::iterator<std::forward_iterator_tag, TItem>::reference
            reference;

          typedef
            typename std::iterator<std::forward_iterator_tag, TItem>::value_type
            value_type;


        private:

          TTreeNode<TItem, TAllocator>*   ptCurrentNode;


        public:

          //
          //  C O N S T R U C T O R S
          //

          TGeneralTreeSideIterator (void)                          :
            std::iterator<std::forward_iterator_tag, TItem> ()     ,
            ptCurrentNode                                   (NULL) {}

          TGeneralTreeSideIterator (const TTreeNode<TItem, TAllocator>* pktNODE)                                  :
            std::iterator<std::forward_iterator_tag, TItem> ()                                                    ,
            ptCurrentNode                                   (const_cast<TTreeNode<TItem, TAllocator>*> (pktNODE)) {}

          TGeneralTreeSideIterator (const TGeneralTreePreIterator<TItem, TAllocator>& rktPRE_ITERATOR) :
            std::iterator<std::forward_iterator_tag, TItem> ()                                         ,
            ptCurrentNode                                   (rktPRE_ITERATOR.ptCurrentNode)            {}

          TGeneralTreeSideIterator& operator ++ (void)
            throw (TConstraintException);

          TGeneralTreeSideIterator operator ++ (int)
          {
            TGeneralTreeSideIterator   tCopy (*this);

            operator ++();
            return tCopy;
          }

          TGeneralTreeSideIterator&
          operator = (const TGeneralTreeSideIterator<TItem, TAllocator>& rktSIDE_ITERATOR)
          {
            ptCurrentNode = rktSIDE_ITERATOR.ptCurrentNode;
            return *this;
          }

          TGeneralTreeSideIterator& operator = (const TGeneralTreePreIterator<TItem, TAllocator>& rktPRE_ITERATOR)
          {
            ptCurrentNode = rktPRE_ITERATOR.ptCurrentNode;
            return *this;
          }


        public:

          //
          //  S E L E C T O R S
          //

          TGeneralTreeSideIterator leftChild (void) const
          {
            if ( !ptCurrentNode )
            {
              throw TConstraintException ("empty node", __FILE__, __LINE__);
            }
            return TGeneralTreeSideIterator (ptCurrentNode->qtFirstChildNode.get());
          }

          pointer operator -> (void) const
            throw (TConstraintException)
          {
            if ( !ptCurrentNode )
            {
              throw TConstraintException ("empty node", __FILE__, __LINE__);
            }
            return &(ptCurrentNode->tItem);
          }

          bool operator == (const TGeneralTreeSideIterator& rktITERATOR) const
          {
            return ( ptCurrentNode == rktITERATOR.ptCurrentNode );
          }

          bool operator == (const TGeneralTreePreIterator<TItem, TAllocator>& rktPRE_ITERATOR) const
          {
            return ( ptCurrentNode == rktPRE_ITERATOR.ptCurrentNode );
          }

          bool operator != (const TGeneralTreePreIterator<TItem, TAllocator>& rktPRE_ITERATOR) const
          {
            return ( ptCurrentNode != rktPRE_ITERATOR.ptCurrentNode );
          }

          reference operator * (void) const
            throw (TConstraintException)
          {
            if ( !ptCurrentNode )
            {
              throw TConstraintException ("empty node", __FILE__, __LINE__);
            }
            return ptCurrentNode->tItem;
          }

          TGeneralTreeSideIterator rightSibling (void) const
          {
            if ( !ptCurrentNode )
            {
              throw TConstraintException ("empty node", __FILE__, __LINE__);
            }
            return TGeneralTreeSideIterator (ptCurrentNode->qtRightNode);
          }

      };  // class TGeneralTreeSideIterator

      template < typename TItem                              ,
                 template <typename TItemA> class TAllocator ,
                 typename TNode                              >
      class TGeneralTree : private virtual TAllocator<TNode>
      {

        public:

          typedef
            typename TNode::alloc_smart_pointer
            QTNode;

          typedef
            memory::TAllocSmartPointer<TGeneralTree, TAllocator>
            QTTree;

          typedef
            TGeneralTreePreIterator<const TItem, TAllocator>
            const_iterator;

          typedef
            TGeneralTreeSideIterator<const TItem, TAllocator>
            const_side_iterator;

          typedef
            TGeneralTreePreIterator<TItem, TAllocator>
            iterator;

          typedef
            TGeneralTreeSideIterator<TItem, TAllocator>
            side_iterator;

          typedef
            typename TNode::size_type
            size_type;

          typedef
            TItem
            value_type;


        private:

          QTNode   qtRootNode;


        private:

          TGeneralTree (const QTNode& rkqtNODE) :
            TAllocator<TNode> ()                ,
            qtRootNode        (rkqtNODE)        {}


        public:

          //
          //  C O N S T R U C T O R S
          //

          TGeneralTree (void)    :
            TAllocator<TNode> () ,
            qtRootNode        () {}

          TGeneralTree (const TItem& rktITEM)                          :
            TAllocator<TNode> ()                                       ,
            qtRootNode        (TNode::_create (rktITEM, allocate (1))) {}

          TGeneralTree (const TGeneralTree& rktGENERAL_TREE) :
            TAllocator<TNode> ()                             ,
            qtRootNode        ()
          {
            TNode*               ptNodeHeap;
            register size_type   zSourceTreeSize = rktGENERAL_TREE.size();

            if ( zSourceTreeSize )
            {
              ptNodeHeap = allocate (zSourceTreeSize);
              qtRootNode = TNode::_copy (rktGENERAL_TREE.qtRootNode, ptNodeHeap);
            }
          }

          virtual ~TGeneralTree (void)
          {
            clear();
          }

          void clear (void)
          {
            qtRootNode = NULL;
          }

          TGeneralTree& copy (const TGeneralTree& rktGENERAL_TREE)
          {
            if ( this != &rktGENERAL_TREE )
            {
              TNode*               ptNodeHeap;
              register size_type   zSourceTreeSize = rktGENERAL_TREE.size();

              if ( !qtRootNode )
              {
                if ( zSourceTreeSize )
                {
                  ptNodeHeap = allocate (zSourceTreeSize);
                  qtRootNode = TNode::_copy (rktGENERAL_TREE.qtRootNode, ptNodeHeap);
                }
              }
              else
              {
                if ( !zSourceTreeSize )
                {
                  qtRootNode = NULL;
                }
                else
                {
                  ptNodeHeap = ( zSourceTreeSize > 1 ) ? allocate (zSourceTreeSize - 1) : NULL;
                  TNode::_copy (qtRootNode, rktGENERAL_TREE.qtRootNode, ptNodeHeap);
                }
              }
            }
            return *this;
          }

          template <typename TIterator>
          TIterator erase (TIterator tPOSITION)
          {
            TIterator   tNEXT_POSITION (tPOSITION);

            ++tNEXT_POSITION;
            TNode::_unlink (tPOSITION.ptCurrentNode);
            return tNEXT_POSITION;
          }

          template <typename TIterator>
          TIterator erase (TIterator tBEGIN, TIterator tEND)
          {
            for (; ( tBEGIN != tEND ) ;)
            {
              //
              //  Post-increments the iterator so, firstly,  it gets the pointer to
              //  the node,  then it increments the  value of the iterator,  and at
              //  last, it unlinks the former node.
              //
              TNode::_unlink ((tBEGIN++).ptCurrentNode);
            }
            return tEND;
          }

          void insert (QTTree& rqtGENERAL_TREE)
            throw (TConstraintException)
          {
            if ( !qtRootNode || !rqtGENERAL_TREE )
            {
              throw TConstraintException ("empty tree", __FILE__, __LINE__);
            }
            qtRootNode->insert (rqtGENERAL_TREE->qtRootNode);
          }

          void insert (const TItem& rktITEM)
            throw (TConstraintException)
          {
            if ( !qtRootNode )
            {
              throw TConstraintException ("empty tree", __FILE__, __LINE__);
            }
            else
            {
              QTNode   qtNewNode (TNode::_create (rktITEM, allocate (1)));

              qtRootNode->insert (qtNewNode);
            }
          }

          template <class TIterator>
          void insert ( TIterator tPOSITION       ,
                        QTTree&   rqtGENERAL_TREE )
            throw (TConstraintException)
          {
            if ( !qtRootNode || !rqtGENERAL_TREE )
            {
              throw TConstraintException ("empty tree", __FILE__, __LINE__);
            }
            if ( !tPOSITION.ptCurrentNode )
            {
              throw TConstraintException ("null iterator", __FILE__, __LINE__);
            }
            tPOSITION.ptCurrentNode->insert (rqtGENERAL_TREE->qtRootNode);
          }

          template <class TIterator>
          void insert ( TIterator    tPOSITION ,
                        const TItem& rktITEM   )
            throw (TConstraintException)
          {
            if ( !qtRootNode )
            {
              throw TConstraintException ("empty tree", __FILE__, __LINE__);
            }
            else if ( !tPOSITION.ptCurrentNode )
            {
              throw TConstraintException ("null iterator", __FILE__, __LINE__);
            }
            else
            {
              QTNode   qtNewNode (TNode::_create (rktITEM, allocate (1)));

              tPOSITION.ptCurrentNode->insert (qtNewNode);
            }
          }

          TGeneralTree&
          operator = (const TGeneralTree& rktGENERAL_TREE)
          {
            return copy (rktGENERAL_TREE);
          }

          void setRoot (const TItem& rktITEM)
          {
            if ( !qtRootNode )
            {
              qtRootNode = TNode::_create (rktITEM, allocate (1));
            }
            else
            {
              qtRootNode->tItem = rktITEM;
            }
          }


        public:

          //
          //  S E L E C T O R S
          //

          iterator begin (void)
          {
            return iterator (qtRootNode.get());
          }

          const_iterator begin (void) const
          {
            return const_iterator (qtRootNode.get());
          }

          side_iterator beginChild (void)
            throw (TConstraintException)
          {
            if ( !qtRootNode )
            {
              throw TConstraintException ("empty tree", __FILE__, __LINE__);
            }
            return side_iterator (qtRootNode->qtFirstChildNode.get());
          }

          const_side_iterator beginChild (void) const
            throw (TConstraintException)
          {
            if ( !qtRootNode )
            {
              throw TConstraintException ("empty tree", __FILE__, __LINE__);
            }
            return const_side_iterator (qtRootNode->qtFirstChildNode);
          }

          bool empty (void) const
          {
            return ( !qtRootNode );
          }

          iterator end (void)
          {
            return iterator();
          }

          const_iterator end (void) const
          {
            return const_iterator();
          }

          side_iterator endChild (void)
          {
            return side_iterator();
          }

          const_side_iterator endChild (void) const
          {
            return const_side_iterator();
          }

          const TItem& getRoot (void) const
            throw (TConstraintException)
          {
            if ( !qtRootNode )
            {
              throw TConstraintException ("empty tree", __FILE__, __LINE__);
            }
            return qtRootNode->tItem;
          }

          TItem& getRoot (void)
            throw (TConstraintException)
          {
            if ( !qtRootNode )
            {
              throw TConstraintException ("empty tree", __FILE__, __LINE__);
            }
            return qtRootNode->tItem;
          }

          size_type height (void) const
          {
            return ( qtRootNode.isNull() ) ? 0 : qtRootNode->height();
          }

          TGeneralTree leftChild (void) const
          {
            if ( !qtRootNode )
            {
              throw TConstraintException ("empty tree", __FILE__, __LINE__);
            }
            return TGeneralTree (qtRootNode->qtFirstChildNode);
          }

          size_type max_size (void) const
          {
            return size_type (-1);
          }

          TGeneralTree rightSibling (void) const
          {
            if ( !qtRootNode )
            {
              throw TConstraintException ("empty tree", __FILE__, __LINE__);
            }
            return TGeneralTree (qtRootNode->qtRightNode);
          }

          size_type size (void) const
          {
            register size_type   zSize = 0;

            if ( !qtRootNode.isNull() )
            {
              zSize = qtRootNode->size();
            }
            return zSize;
          }

          void swap (TGeneralTree& rtTREE)
          {
            std::swap<QTNode> (qtRootNode, rtTREE.qtRootNode);
          }

      };  // class TGeneralTree


      //
      //  C O N S T R U C T O R S
      //

      template <typename TItem, template <typename TItemA> class TAllocator>
      inline typename TTreeNode<TItem, TAllocator>::alloc_smart_pointer TTreeNode<TItem, TAllocator>::
      _copy (const alloc_smart_pointer& rkqtNODE, TTreeNode*& rptNODE_HEAP)
      {

        alloc_smart_pointer   qtNewNode;

        if ( rkqtNODE.get() )
        {
          //
          //  Takes the space for the node from the heap, and the construct the new
          //  instance on it. Finally, it copies the child nodes.
          //
          qtNewNode = rptNODE_HEAP;
          TAllocator<TTreeNode>().construct (rptNODE_HEAP++, rkqtNODE->tItem);
          qtNewNode->qtFirstChildNode =
            _copySiblings (rkqtNODE->qtFirstChildNode, qtNewNode.get(), rptNODE_HEAP);
        }
        return qtNewNode;

      }  // TTreeNode::_copy()

      template <typename TItem, template <typename TItemA> class TAllocator>
      inline typename TTreeNode<TItem, TAllocator>::alloc_smart_pointer TTreeNode<TItem, TAllocator>::
      _copy ( alloc_smart_pointer&       rqtTARGET_NODE ,
              const alloc_smart_pointer& rkqtNODE       ,
              TTreeNode*&                rptNODE_HEAP   )
        throw (TConstraintException)
      {

        if ( !rqtTARGET_NODE )
        {
          throw TConstraintException ("target node is null", __FILE__, __LINE__);
        }
        if ( !rkqtNODE.isNull() )
        {
          TTreeNode*   ptChildNode = rqtTARGET_NODE->qtFirstChildNode.get();

          //
          //  Detaches target node children from the parent node.
          //
          while ( ptChildNode )
          {
            ptChildNode->ptParentNode = NULL;
            ptChildNode               = ptChildNode->qtRightNode.get();
          }

          //
          //  Makes a copy of the source nodes.
          //
          rqtTARGET_NODE->tItem            = rkqtNODE->tItem;
          rqtTARGET_NODE->qtFirstChildNode =
            _copySiblings (rkqtNODE->qtFirstChildNode, rqtTARGET_NODE.get(), rptNODE_HEAP);
        }
        return rqtTARGET_NODE;

      }  // TTreeNode::_copy()

      template <typename TItem, template <typename TItemA> class TAllocator>
      inline typename TTreeNode<TItem, TAllocator>::alloc_smart_pointer TTreeNode<TItem, TAllocator>::
      _copySiblings ( const alloc_smart_pointer& rkqtNODE       ,
                      const TTreeNode*           pktPARENT_NODE ,
                      TTreeNode*&                rptNODE_HEAP   )
      {

        alloc_smart_pointer   qtFirstNode;

        if ( !rkqtNODE.isNull() )
        {
          alloc_smart_pointer   qtNewNode;
          alloc_smart_pointer   qtOldNode;
          alloc_smart_pointer   qtSourceNode (rkqtNODE);

          //
          //  Copies the first node of source sibling nodes.
          //
          qtFirstNode               = _copy (qtSourceNode, rptNODE_HEAP);
          qtFirstNode->ptParentNode = const_cast<TTreeNode*> (pktPARENT_NODE);
          qtSourceNode              = qtSourceNode->qtRightNode;

          //
          //  Copies rest of source siblings nodes.
          //
          for (qtOldNode = qtFirstNode; ( !qtSourceNode.isNull() ) ;)
          {
            //
            //  Creates  a new node and  attaches  to the parent node,  then it
            //  connects left and right newly created nodes.
            //
            qtNewNode               = _copy (qtSourceNode, rptNODE_HEAP);
            qtNewNode->ptParentNode = const_cast<TTreeNode*> (pktPARENT_NODE);
            qtNewNode->ptLeftNode   = qtOldNode.get();
            qtOldNode->qtRightNode  = qtNewNode;
            qtOldNode               = qtNewNode;
            qtSourceNode            = qtSourceNode->qtRightNode;
          }
        }
        return qtFirstNode;

      }  // TTreeNode::_copySiblings()

      template <typename TItem, template <typename TItemA> class TAllocator>
      inline void TTreeNode<TItem, TAllocator>::_unlink (TTreeNode* ptTARGET_NODE)
        throw (TConstraintException)
      {

        if ( !ptTARGET_NODE )
        {
          throw TConstraintException ("node is null", __FILE__, __LINE__);
        }
        if ( ptTARGET_NODE->ptParentNode )
        {
          alloc_smart_pointer   qtTargetNode;

          //
          //  Unlinks  from parent node. There is no need to  unlink  from  sibling
          //  nodes because if there is no parent, then there are no sibling nodes.
          //
          if ( ptTARGET_NODE->ptLeftNode )
          {
            //
            //  This is not the first sibling node.
            //
            //  Warning:  Cause  node  ptTARGET_NODE  is  holded  by  (possibly) an
            //            unique  smart-pointer,  (left node  smart-pointer to  its
            //            right sibling  node)  it must  point  to  another  smart-
            //            pointer instance pointing to the former node.
            //
            qtTargetNode = ptTARGET_NODE->ptLeftNode->qtRightNode;
            if ( !ptTARGET_NODE->qtRightNode )
            {
              //
              //  This is the last node.
              //
              ptTARGET_NODE->ptLeftNode->qtRightNode = NULL;
            }
            else
            {
              //
              //  This is an inner node.
              //
              ptTARGET_NODE->qtRightNode->ptLeftNode = ptTARGET_NODE->ptLeftNode;
              ptTARGET_NODE->ptLeftNode->qtRightNode = ptTARGET_NODE->qtRightNode;
            }
          }
          else
          {
            //
            //  Node ptTARGET_NODE is the first sibling node.
            //
            //  Warning:  Cause  node   ptTARGET_NODE  is   holded by (possibly) an
            //            unique smart-pointer,  (parent node  smart-pointer to its
            //            first child node) it must point  to another smart-pointer
            //            instance pointing to the former node.
            //
            qtTargetNode = ptTARGET_NODE->ptParentNode->qtFirstChildNode;
            if ( !ptTARGET_NODE->qtRightNode )
            {
              //
              //  This is the unique child node,  so it removes the pointer to this
              //  node.   If  there   is  no   other   smart-pointer   pointing  to
              //  ptTARGET_NODE, then it may  automatically destroyed before we can
              //  finish all operations over it.
              //
              ptTARGET_NODE->ptParentNode->qtFirstChildNode = NULL;
            }
            else
            {
              //
              //  There are sibling nodes,  so it  re-connects the parent node with
              //  its right node.
              //
              ptTARGET_NODE->qtRightNode->ptLeftNode        = NULL;
              ptTARGET_NODE->ptParentNode->qtFirstChildNode = ptTARGET_NODE->qtRightNode;
              ptTARGET_NODE->qtRightNode                    = NULL;
            }
          }
          //
          //  Erases pointer to parent node.
          //
          ptTARGET_NODE->ptParentNode = NULL;
        }

      }  // TTreeNode::_unlink()

      template <typename TItem, template <typename TItemA> class TAllocator>
      inline void TTreeNode<TItem, TAllocator>::
      insert (alloc_smart_pointer& rqtTARGET_NODE)
        throw (TConstraintException)
      {

        if ( !rqtTARGET_NODE )
        {
          throw TConstraintException ("empty node", __FILE__, __LINE__);
        }
        if ( !qtFirstChildNode )
        {
          //
          //  There is no child nodes.
          //
          qtFirstChildNode           = rqtTARGET_NODE;
          rqtTARGET_NODE->ptLeftNode = NULL;
        }
        else
        {
          alloc_smart_pointer   qtNode (qtFirstChildNode);

          //
          //  Iterates through the nodes to the last one.
          //
          while ( !qtNode->qtRightNode.isNull() )
          {
            qtNode = qtNode->qtRightNode;
          }
          qtNode->qtRightNode        = rqtTARGET_NODE;
          rqtTARGET_NODE->ptLeftNode = qtNode.get();
        }

        //
        //  Isolates  the  new node as the only node at last,  and  then makes this
        //  instance to 'adopt' that node.
        //
        rqtTARGET_NODE->qtRightNode  = NULL;
        rqtTARGET_NODE->ptParentNode = this;

      }  // TTreeNode::insert()

      template <typename TItem, template <typename TItemA> class TAllocator>
      inline TGeneralTreePreIterator<TItem, TAllocator>& TGeneralTreePreIterator<TItem, TAllocator>::
      operator ++ (void)
        throw (TConstraintException)
      {

        if ( !ptCurrentNode )
        {
          throw TConstraintException ("iterator past the end", __FILE__, __LINE__);
        }
        if ( !ptCurrentNode->qtFirstChildNode.isNull() )
        {
          //
          //  The node has at least one child, so take the that node.
          //
          ptCurrentNode = ptCurrentNode->qtFirstChildNode.get();
        }
        else
        {
          //
          //  Node has no child nodes.
          //
          if ( !ptCurrentNode->qtRightNode.isNull() )
          {
            //
            //  The node has at least one sibling node.
            //
            ptCurrentNode = ptCurrentNode->qtRightNode.get();
          }
          else
          {
            //
            //  The Node has no  sibling nodes,  so the searches  for the first
            //  parent node with sibling nodes.
            //
            while ( ptCurrentNode && !ptCurrentNode->qtRightNode )
            {
              ptCurrentNode = ptCurrentNode->ptParentNode;
            }
            if ( ptCurrentNode )
            {
              //
              //  There  has been found a node with  right sibling node,  so it
              //  points to this one.
              //
              ptCurrentNode = ptCurrentNode->qtRightNode.get();
            }
          }
        }
        return *this;

      }  // TGeneralTreePreIterator::operator ++()

      template <typename TItem, template <typename TItemA> class TAllocator>
      inline TGeneralTreeSideIterator<TItem, TAllocator>& TGeneralTreeSideIterator<TItem, TAllocator>::
      operator ++ (void)
        throw (TConstraintException)
      {

        if ( !ptCurrentNode )
        {
          throw TConstraintException ("empty node", __FILE__, __LINE__);
        }
        if ( !ptCurrentNode->qtRightNode )
        {
          //
          //  Node is empty.
          //
          ptCurrentNode = NULL;
        }
        else
        {
          //
          //  The node has at least one sibling node.
          //
          ptCurrentNode = ptCurrentNode->qtRightNode.get();
        }
        return *this;

      }  // TGeneralTreeSideIterator::operator ++()


      //
      //  S E L E C T O R S
      //

      template <typename TItem, template <typename TItemA> class TAllocator>
      inline typename TTreeNode<TItem, TAllocator>::size_type TTreeNode<TItem, TAllocator>::
      height (void) const
      {

        alloc_smart_pointer   qtNode  = qtFirstChildNode;
        size_type             zHeight = 0;

        //
        //  Computes the maximum height.
        //
        while ( qtNode.get() )
        {
          zHeight = std::max<size_type> (zHeight, qtNode->height());
          qtNode  = qtNode->qtRightNode;
        }
        return (1 + zHeight);

      }  // TTreeNode::height()

      template <typename TItem, template <typename TItemA> class TAllocator>
      inline typename TTreeNode<TItem, TAllocator>::size_type TTreeNode<TItem, TAllocator>::
      size (void) const
      {

        alloc_smart_pointer   qtNode = qtFirstChildNode;
        register size_type    zSize  = 1;

        while ( !qtNode.isNull() )
        {
          zSize  += qtNode->size();
          qtNode  = qtNode->qtRightNode;
        }
        return zSize;

      }  // TTreeNode::size()

    }  // namespace collection

  }  // namespace util

}  // namespace mpcl


namespace std
{

  using mpcl::util::collection::TGeneralTree;

  template < typename TItem                              ,
             template <typename TItemA> class TAllocator ,
             typename TNode                              >
  inline void swap ( TGeneralTree<TItem, TAllocator, TNode>& rtTREE1 , 
                     TGeneralTree<TItem, TAllocator, TNode>& rtTREE2 )
  {
    rtTREE1.swap (rtTREE2);
  }

}  // namespace std


#endif  // not _MPCL_UTIL_COLLECTION_GENERAL_TREE__

---