/*
* tree.hpp
*
* This file is part of Algorithms library toolkit.
* Copyright (C) 2017 Jan Travnicek (jan.travnicek@fit.cvut.cz)
* Algorithms library toolkit 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 3 of the License, or
* (at your option) any later version.
* Algorithms library toolkit 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 Algorithms library toolkit. If not, see <http://www.gnu.org/licenses/>.
*
* Created on: Jul 2, 2016
* Author: Jan Travnicek
*/
#ifndef __TREE_HPP_
#define __TREE_HPP_
#include <memory>
#include <sstream>
#include <string>
#include "vector.hpp"
#include "compare.hpp"
#include "iterator.hpp"
#include "tree_base.hpp"
namespace ext {
/**
* \brief
* Class introducing a tree with interface trying to be close to the interface of standard library containers.
*
* The tree is a hierarchical structure of nodes with parent child relationship, where the children are ordered and indexed by integers.
*
* \tparam T the type of values inside nodes of the tree
*/
template < class T >
class tree {
/**
* \brief
* The value in the root node of the tree
*/
T m_data;
/**
* \brief
* Pointer to the parent of the node. Null pointer for root of a tree.
*/
tree * m_parent;
/**
* \brief
* Container of children of the root node of the tree.
*
* The children are trees themselves, hence the subtree of a tree is itself a tree.
*/
ext::vector < tree > m_children;
public:
/**
* \brief
* Getter of the parent node. Null if the node is root.
*
* \return pointer to the parent node
*/
tree * getParent ( ) {
return m_parent;
}
/**
* \brief
* Getter of the parent node. Null if the node is root.
*
* \return pointer to the parent node
*/
const tree * getParent ( ) const {
return m_parent;
}
/**
* \brief
* Getter of the value in the root node.
*
* \return the value in the root node
*/
T & getData ( ) {
return m_data;
}
/**
* \brief
* Getter of the value in the root node.
*
* \return the value in the root node
*/
const T & getData ( ) const {
return m_data;
}
/**
* \brief
* Getter of children of the root node.
*
* \return children of the root node
*/
ext::vector < tree > & getChildren ( ) {
return m_children;
}
/**
* \brief
* Getter of children of the root node.
*
* \return children of the root node
*/
const ext::vector < tree > & getChildren ( ) const {
return m_children;
}
/**
* \brief
* The iterator type over children of the node
*/
typedef typename ext::vector < tree >::const_iterator const_children_iterator;
/**
* \brief
* The iterator type over children of the node
*/
typedef typename ext::vector < tree >::iterator children_iterator;
/**
* \brief
* The iterator type over structure of the tree representing nodes and node_ends
*
* The iterator performs a top to bottom, left to right or depth first travrsal stopping at each node twice. Once as it enters it the first time and second time when it leaves it (on the way to its parent).
*/
class const_structure_iterator : public std::iterator < std::bidirectional_iterator_tag, T > {
/**
* \brief
* The underlying iterator within some list of children.
*/
typename ext::vector < tree >::const_iterator node;
/**
* \brief
* The depth of the current pointed to node.
*/
unsigned level;
/**
* \brief
* True if the iterator is pointing to a tree node in the first visit, false in the second (leaving case).
*/
bool virtual_node;
/**
* \brief
* True if the iterator is one position after the last valid iterator value.
*/
bool isEnd;
public:
/**
* \brief
* Constructor of the iterator based on the iterator to child list
*
* \param n the iterator to child list
*/
const_structure_iterator ( typename ext::vector < tree >::const_iterator n ) : node ( n ), level ( 0 ), virtual_node ( false ), isEnd ( false ) {
}
/**
* \brief
* Advance the iterator.
*
* \return the updated iterator
*/
const_structure_iterator & operator ++( ) {
if ( virtual_node ) {
const tree * parent = node->getParent ( );
++node;
if ( parent != nullptr ) {
if ( node == parent->getChildren ( ).end ( ) ) {
--level;
node = typename ext::vector < tree >::const_iterator ( parent );
} else {
virtual_node = false;
}
} else {
virtual_node = false;
isEnd = true;
}
} else {
typename ext::vector < tree >::const_iterator newIter = node->getChildren ( ).begin ( );
if ( newIter != node->getChildren ( ).end ( ) ) {
++level;
node = newIter;
} else {
virtual_node = true;
}
}
return * this;
}
/**
* \brief
* Advance the iterator.
*
* \return the original iterator
*/
const_structure_iterator operator ++( int ) {
const_structure_iterator tmp ( * this );
operator ++( );
return tmp;
}
/**
* \brief
* Retract the iterator.
*
* \return the updated iterator
*/
const_structure_iterator & operator --( ) {
if ( isEnd ) {
--node;
virtual_node = true;
isEnd = false;
} else if ( virtual_node ) {
typename ext::vector < tree >::const_iterator newIter = node->getChildren ( ).end ( );
if ( newIter != node->getChildren ( ).begin ( ) ) {
++level;
node = newIter;
--node;
} else {
virtual_node = false;
}
} else {
const tree * parent = node->getParent ( );
if ( parent != nullptr ) {
if ( node == parent->getChildren ( ).begin ( ) ) {
--level;
node = typename ext::vector < tree >::const_iterator ( parent );
} else {
--node;
virtual_node = true;
}
}
}
return * this;
}
/**
* \brief
* Retract the iterator.
*
* \return the original iterator
*/
const_structure_iterator operator --( int ) {
const_structure_iterator tmp ( * this );
operator --( );
return tmp;
}
/**
* \brief
* Compare the iterators for equality.
*
* \param other the other instance
*
* \return true if the two iterators are the same, false othervise
*/
bool operator ==( const const_structure_iterator & other ) {
return node == other.node && virtual_node == other.virtual_node;
}
/**
* \brief
* Compare the iterators for nonequality.
*
* \param other the other instance
*
* \return true if the two iterators are not the same, false othervise
*/
bool operator !=( const const_structure_iterator & other ) {
return !( * this == other );
}
/**
* \brief
* Dereference the iterator by accessing the pointed node value.
*
* \return the value of node pointed to
*/
const T & operator *( ) const {
return node->getData ( );
}
/**
* \brief
* Dereference the iterator by accessing the pointed node value.
*
* \return the value of node pointed to
*/
const T * operator ->( ) const {
return & node->getData ( );
}
/**
* \brief
* Retrieves what is the depth of node the iterator is pointing to.
*
* \return the depth of node pointed to
*/
unsigned getLevel ( ) const {
return level;
}
/**
* \brief
* Allows to distinguish entry or leave visit of a pointed to node.
*
* \return true if the iterator is pointing to a tree node in the first visit, false in the second (leaving case).
*/
bool getVirtual ( ) const {
return virtual_node;
}
template < class F >
friend class tree;
};
/**
* \brief
* The iterator type over structure of the tree following preorder traversal.
*
* The prefix iterator is constructed as a wrapper over structure iterator, it selects only non-virtual nodes.
*/
class const_prefix_iterator : public std::iterator < std::bidirectional_iterator_tag, T > {
/**
* \brief
* The underlying structure iterator.
*/
const_structure_iterator node;
public:
/**
* \brief
* Constructor of the iterator based on the iterator to child list
*
* \param n the iterator to child list
*/
const_prefix_iterator ( typename ext::vector < tree >::const_iterator n ) : node ( n ) {
}
/**
* \brief
* Advance the iterator.
*
* \return the updated iterator
*/
const_prefix_iterator & operator ++( ) {
while ( ( ++node ).getVirtual ( ) );
return * this;
}
/**
* \brief
* Advance the iterator.
*
* \return the original iterator
*/
const_prefix_iterator operator ++( int ) {
const_prefix_iterator tmp ( * this );
operator ++( );
return tmp;
}
/**
* \brief
* Retract the iterator.
*
* \return the updated iterator
*/
const_prefix_iterator & operator --( ) {
while ( ( --node ).getVirtual ( ) );
return * this;
}
/**
* \brief
* Retract the iterator.
*
* \return the original iterator
*/
const_prefix_iterator operator --( int ) {
const_prefix_iterator tmp ( * this );
operator --( );
return tmp;
}
/**
* \brief
* Compare the iterators for equality.
*
* \param other the other instance
*
* \return true if the two iterators are the same, false othervise
*/
bool operator ==( const const_prefix_iterator & other ) {
return node == other.node;
}
/**
* \brief
* Compare the iterators for nonequality.
*
* \param other the other instance
*
* \return true if the two iterators are not the same, false othervise
*/
bool operator !=( const const_prefix_iterator & other ) {
return !( * this == other );
}
/**
* \brief
* Dereference the iterator by accessing the pointed node value.
*
* \return the value of node pointed to
*/
const T & operator *( ) const {
return * node;
}
/**
* \brief
* Dereference the iterator by accessing the pointed node value.
*
* \return the value of node pointed to
*/
const T * operator ->( ) const {
return & node->getData ( );
}
/**
* \brief
* Retrieves what is the depth of node the iterator is pointing to.
*
* \return the depth of node pointed to
*/
unsigned getLevel ( ) const {
return node.getLevel ( );
}
template < class F >
friend class tree;
};
/**
* \brief
* The iterator type over structure of the tree following postorder traversal
*
* The prefix iterator is constructed as a wrapper over structure iterator, it selects only virtual nodes.
*/
class const_postfix_iterator : public std::iterator < std::bidirectional_iterator_tag, T > {
/**
* \brief
* The underlying structure iterator.
*/
const_structure_iterator node;
public:
/**
* \brief
* Constructor of the iterator based on the iterator to child list
*
* \param n the iterator to child list
*/
const_postfix_iterator ( typename ext::vector < tree >::const_iterator n ) : node ( n ) {
}
/**
* \brief
* Advances the iterator.
*
* \return the updated iterator
*/
const_postfix_iterator & operator ++( ) {
while ( !( ++node ).getVirtual ( ) && !node.isEnd );
return * this;
}
/**
* \brief
* Advances the iterator.
*
* \return the original iterator
*/
const_postfix_iterator operator ++( int ) {
const_postfix_iterator tmp ( * this );
operator ++( );
return tmp;
}
/**
* \brief
* Retract the iterator.
*
* \return the updated iterator
*/
const_postfix_iterator & operator --( ) {
while ( !( --node ).getVirtual ( ) );
return * this;
}
/**
* \brief
* Retract the iterator.
*
* \return the original iterator
*/
const_postfix_iterator operator --( int ) {
const_postfix_iterator tmp ( * this );
operator --( );
return tmp;
}
/**
* \brief
* Compare the iterators for equality.
*
* \brief other the other instance
*
* \return true if the two iterators are the same, false othervise
*/
bool operator ==( const const_postfix_iterator & other ) {
return node == other.node;
}
/**
* \brief
* Compare the iterators for nonequality.
*
* \brief other the other instance
*
* \return true if the two iterators are not the same, false othervise
*/
bool operator !=( const const_postfix_iterator & other ) {
return !( * this == other );
}
/**
* \brief
* Dereference the iterator by accessing the pointed node value.
*
* \return the value of node pointed to
*/
const T & operator *( ) const {
return * node;
}
/**
* \brief
* Dereference the iterator by accessing the pointed node value.
*
* \return the value of node pointed to
*/
const T * operator ->( ) const {
return & node->getData ( );
}
/**
* \brief
* Retrieves what is the depth of node the iterator is pointing to.
*
* \return the depth of node pointed to
*/
unsigned getLevel ( ) const {
return node.getLevel ( );
}
template < class F >
friend class tree;
};
// ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
private:
/**
* \brief
* vector of trees construction helper. Trees are nullary nodes having value given by values in the range begin to end.
*
* \tparam Iterator the type of iterators forming the range
*
* \param begin the start of the range of values
* \param end the end of the range of values
*
* \return vector of unary nodes constructed from the begin and end range
*/
template < typename Iterator >
ext::vector < tree > fromIterator ( Iterator begin, Iterator end ) {
ext::vector < tree > res;
for ( ; begin != end; ++begin )
res.push_back ( tree ( * begin, { } ) );
return res;
}
public:
/**
* \brief
* Inserts a subtree into a tree.
*
* \param position the specification of position in children of the node where to add subtrees
* \param value a subtree to insert
*
* \return updated position iterator pointing to the first node inserted
*/
const_children_iterator insert ( const_children_iterator position, tree < T > && value ) {
ext::vector < tree > & children = const_cast < ext::vector < tree > & > ( getChildren ( ) );
typename ext::vector < tree >::iterator iter = children.insert ( position, std::move ( value ) );
iter->m_parent = this;
return iter;
}
/**
* \brief
* Inserts a subtree into a tree.
*
* \param position the specification of position in children of the node where to add subtrees
* \param value a subtree to insert
*
* \return updated position iterator pointing to the first node inserted
*/
const_children_iterator insert ( const_children_iterator position, const tree < T > & value ) {
return insert ( position, tree < T > ( value ) );
}
/**
* \brief
* Insert helper for insertion specified by position in children and inserted subtrees given by range of iterators.
*
* \param position the specification of position in children of the node where to add subtrees
* \param begin the start of the range of subtrees
* \param end the end of the range of subtrees
*
* \return updated position iterator pointing to the first node inserted
*/
const_children_iterator insert ( const_children_iterator position, const_children_iterator begin, const_children_iterator end ) {
ext::vector < tree > & children = const_cast < ext::vector < tree > & > ( getChildren ( ) );
typename ext::vector < tree >::iterator iter = children.insert ( position, begin, end );
for ( typename ext::vector < tree >::iterator iterCopy = iter; begin != end; ++begin, ++iterCopy )
iterCopy->m_parent = this;
return iter;
}
/**
* \brief
* Inserts a subtrees into a tree. The subtrees are nullary nodes having value given by values in the range begin to end.
*
* \tparam Iterator the type of iterators forming the range
*
* \param position the specification of position in children of the node where to add subtrees
* \param begin the start of the range of values
* \param end the end of the range of values
*
* \return updated position iterator pointing to the first node inserted
*/
template < class Iterator >
const_children_iterator insert ( const_children_iterator position, Iterator begin, Iterator end ) {
ext::vector < tree > children = fromIterator ( begin, end );
return insert ( position, children.cbegin ( ), children.cend ( ) );
}
// ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
public:
/**
* \brief
* Constructor of the tree from value to be stored in the root node and children trees.
*
* \param data the value to be stored in the root
* \param children list of subtrees
*/
tree ( T && data, ext::vector < tree > && children ) : m_data ( std::move ( data ) ), m_parent ( nullptr ), m_children ( std::move ( children ) ) {
for ( tree & child : m_children )
child.m_parent = this;
}
/**
* \brief
* Constructor of the tree from value to be stored in the root node and children trees.
*
* \param data the value to be stored in the root
* \param children list of subtrees
*/
tree ( const T & data, const ext::vector < tree > & subtrees ) : tree ( T ( data ), ext::vector < tree > ( subtrees ) ) {
}
/**
* \brief
* Constructor of the tree from value to be stored in the root node and pack of children trees.
*
* \tparam Types ... pack of types convertible to tree
*
* \param data the value to be stored in the root
* \param subtrees ... pack of subtrees
*/
template < typename ... Types >
tree ( const T & data, Types ... subtrees ) : tree ( data, ext::vector < tree > { subtrees ... } ) {
}
/**
* \brief
* Constructor of the tree from value to be stored in the root node and pack of children trees.
*
* \tparam Types ... pack of types convertible to tree
*
* \param data the value to be stored in the root
* \param subtrees ... pack of subtrees
*/
template < typename ... Types >
tree ( T && data, Types ... subtrees ) : tree ( std::move ( data ), ext::vector < tree > { subtrees ... } ) {
}
/**
* \brief
* Constructor of the tree from value to be stored in the root node and range of values to construct nullary nodes from range of values.
*
* \param data the value to be stored in the root
* \param begin the iterator to the begining of values range
* \param end the iterator to the end of values range
*/
template < typename Iterator, typename std::enable_if < ext::is_iterator < Iterator >::value >::type >
tree ( const T & data, Iterator begin, Iterator end ) : tree ( data, fromIterator ( begin, end ) ) {
}
/**
* \brief
* Constructor of the tree from value to be stored in the root node and range of subtrees.
*
* \param data the value to be stored in the root
* \param begin the iterator to the begining of subtree range
* \param end the iterator to the end of subtree range
*/
tree ( const T & data, const_children_iterator begin, const_children_iterator end ) : tree ( data, ext::vector < tree > ( begin, end ) ) {
}
/**
* \brief
* Dectructor of the tree
*/
~tree ( ) noexcept {
}
/**
* \brief
* Copy constructor of the tree.
*
* \param other the other instace of the tree
*/
tree ( const tree & other ) : m_data ( other.m_data ), m_parent ( other.m_parent ), m_children ( other.m_children ) {
for ( tree & child : m_children )
child.m_parent = this;
}
/**
* \brief
* Move constructor of the tree.
*
* \param other the other instace of the tree
*/
tree ( tree && other ) noexcept : m_data ( std::move ( other.m_data ) ), m_parent ( other.m_parent ), m_children ( std::move ( other.m_children ) ) {
for ( tree & child : m_children )
child.m_parent = this;
}
/**
* \brief
* Copy operator of assignment of the tree.
*
* \param other the other instace of the tree
*
* \return the assigned to instance
*/
tree & operator =( const tree & node ) {
return this->operator =( tree ( node ) );
}
/**
* \brief
* Move operator of assignment of the tree.
*
* \param other the other instace of the tree
*
* \return the assigned to instance
*/
tree & operator =( tree && node ) noexcept {
m_data = std::move ( node.m_data );
m_children = std::move ( node.m_children );
for ( tree & child : m_children )
child.m_parent = this;
return * this;
}
// ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
/**
* \brief
* Getter of a children iterator to the begining of children
*
* \return iterator to the first child
*/
const_children_iterator begin ( ) const {
return m_children.begin ( );
}
/**
* \brief
* Getter of a children iterator to the begining of children
*
* \return iterator to the first child
*/
children_iterator begin ( ) {
return m_children.begin ( );
}
/**
* \brief
* Getter of a children iterator one after the last child
*
* \return iterator one after the last child
*/
const_children_iterator end ( ) const {
return m_children.end ( );
}
/**
* \brief
* Getter of a children iterator one after the last child
*
* \return iterator one after the last child
*/
children_iterator end ( ) {
return m_children.end ( );
}
// ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
/**
* \brief
* Getter of the prefix iterator to the root node
*
* \return prefix iterator to the root
*/
const_prefix_iterator prefix_begin ( ) const {
return typename ext::vector < tree >::const_iterator ( this );
}
/**
* \brief
* Getter of the prefix iterator one after the last node in the prefix traversal
*
* \return prefix iterator one after the last node in the prefix traversal
*/
const_prefix_iterator prefix_end ( ) const {
const_prefix_iterator res ( typename ext::vector < tree >::const_iterator ( this + 1 ) );
res.node.isEnd = true;
return res;
}
// ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
/**
* \brief
* Getter of the postfix iterator to the first node in the postfix traversal
*
* \return prefix iterator to the first node in the postfix traversal
*/
const_postfix_iterator postfix_begin ( ) const {
const_postfix_iterator res { typename ext::vector < tree >::const_iterator ( this ) };
while ( ! res.node.getVirtual ( ) ) ++res.node;
return res;
}
/**
* \brief
* Getter of the postfix iterator one after the last node in the postfix traversal
*
* \return prefix iterator one after the last node in the postfix traversal
*/
const_postfix_iterator postfix_end ( ) const {
const_postfix_iterator res ( typename ext::vector < tree >::const_iterator ( this + 1 ) );
res.node.isEnd = true;
return res;
}
// ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
/**
* \brief
* Getter of the structure iterator to the first node in the traversal
*
* \return prefix iterator to the first node in the traversal
*/
const_structure_iterator structure_begin ( ) const {
return typename ext::vector < tree >::const_iterator ( this );
}
/**
* \brief
* Getter of the structure iterator to one after the last node in the traversal
*
* \return prefix iterator to one after the last node in the traversal
*/
const_structure_iterator structure_end ( ) const {
const_structure_iterator res ( typename ext::vector < tree >::const_iterator ( this + 1 ) );
res.isEnd = true;
return res;
}
// ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
/**
* \brief
* Pushbacks a subtree after last child of a tree.
*
* \param value a subtree to pushback to child list
*/
void push_back ( ext::tree < T > && value ) {
ext::vector < tree > & children = const_cast < ext::vector < tree > & > ( getChildren ( ) );
children.push_back ( std::move ( value ) );
children.back ( ).m_parent = this;
}
/**
* \brief
* Pushbacks a subtree after last child of a tree.
*
* \param value a subtree to pushback to child list
*/
void push_back ( const ext::tree < T > & value ) {
push_back ( tree ( value ) );
}
/**
* \brief
* Pushbacks a nullary node after last child of a tree.
*
* \param value a value to store in nullary node push-backed to the child list
*/
void push_back ( T && value ) {
push_back ( tree ( std::move ( value ) ) );
}
/**
* \brief
* Pushbacks a nullary node after last child of a tree.
*
* \param value a value to store in nullary node push-backed to the child list
*/
void push_back ( const T & value ) {
push_back ( T ( value ) );
}
// ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
/**
* \brief
* Erases a subtree from a tree on given by \p position
*
* \param position the specification of position in children where to erase the subtree
*/
const_children_iterator erase ( const_children_iterator position ) {
ext::vector < tree > & children = const_cast < ext::vector < tree > & > ( getChildren ( ) );
return children.erase ( position );
}
// ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
/**
* \brief
* Access value given indexes of chindren allong the selection path
*
* \tparam Indexes ... types of child indexes
*
* \param indexes actual values of child indexes
*
* \return the value in the selected node
*/
template < class ... Indexes >
const T & operator ()( Indexes ... indexes ) const {
return this->operator ()( { ( unsigned ) indexes ... } );
}
/**
* \brief
* Access value given indexes of chindren allong the selection path
*
* \param indexes actual values of child indexes
*
* \return the value in the selected node
*/
const T & operator ()( std::initializer_list < unsigned > indexes ) const {
const tree * node = this;
for ( unsigned index : indexes ) {
node = & node->getChildren ( )[index];
}
return node->getData ( );
}
/**
* \brief
* Access value given indexes of chindren allong the selection path
*
* \tparam Indexes ... types of child indexes
*
* \param indexes actual values of child indexes
*
* \return the value in the selected node
*/
template < class ... Indexes >
T & operator ()( Indexes ... indexes ) {
return this->operator ()( { ( unsigned ) indexes ... } );
}
/**
* \brief
* Access value given indexes of chindren allong the selection path
*
* \param indexes actual values of child indexes
*
* \return the value in the selected node
*/
T & operator ()( std::initializer_list < unsigned > indexes ) {
tree * node = this;
for ( unsigned index : indexes ) {
node = & node->getChildren ( )[index];
}
return node->getData ( );
}
// ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
/**
* \brief
* Helper method to traverse the tree and check all parent references are set correctly.
*
* \param node the node to test
*
* \return true if the parent child relationship of nodes is sound
*/
bool checkStructure ( const tree & node ) const {
bool sign = true;
for ( const tree & child : node.getChildren ( ) )
sign &= child.getParent ( ) == & node && checkStructure ( child );
return sign;
}
/**
* \brief
* Helper method to traverse the tree and check all parent references are set correctly. Starts at root node and recursively tests all its child nodes.
*
* \param node the node to test
*
* \return true if the parent child relationship of nodes is sound
*/
bool checkStructure ( ) const {
return m_parent == nullptr && checkStructure ( * this );
}
// ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
/**
* \brief
* Swap method of two forward trees
*
* \param first the first forward tree to swap
* \param second the second forward tree to swap
*/
friend void swap ( tree & first, tree & second ) {
using std::swap;
swap ( first.m_data, second.m_data );
swap ( first.m_children, second.m_children );
swap ( first.m_parent, second.m_parent );
}
// ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
/**
* \brief
* Three-way comparison method of forward trees.
*
* \param other the other instance to compare against
*
* \return negative if this instance is smaller than \p other instance
* zero if this is equal to \p other instance
* positive if this instance is bigger than \p other instance
*/
int compare ( const tree & other ) const {
static ext::compare < typename std::decay < T >::type > comp;
auto iterF = this->prefix_begin ( );
auto iterS = other.prefix_begin ( );
for ( ; iterF != this->prefix_end ( ) || iterS != other.prefix_end ( ); ++iterF, ++iterS ) {
int res = comp ( * iterF, * iterS );
if ( res != 0 ) return res;
}
if ( iterF != this->prefix_end ( ) ) return -1;
if ( iterS != other.prefix_end ( ) ) return 1;
return 0;
}
/**
* \brief
* Equality comparison operator.
*
* \param other the other instance to compare with
*
* \return true if this instance is equal to other instance, false othervise
*/
bool operator ==( const tree & other ) {
return compare ( other ) == 0;
}
/**
* \brief
* Non-equality comparison operator.
*
* \param other the other instance to compare with
*
* \return true if this instance is not equal to other instance, false othervise
*/
bool operator !=( const tree & other ) {
return compare ( other ) != 0;
}
/**
* \brief
* Less comparison operator.
*
* \param other the other instance to compare with
*
* \return true if this instance is smaller than other instance, false othervise
*/
bool operator <( const tree & other ) {
return compare ( other ) < 0;
}
/**
* \brief
* Less or equal comparison operator.
*
* \param other the other instance to compare with
*
* \return true if this instance is smaller or equal than other instance, false othervise
*/
bool operator <=( const tree & other ) {
return compare ( other ) <= 0;
}
/**
* \brief
* Greater comparison operator.
*
* \param other the other instance to compare with
*
* \return true if this instance is greater than other instance, false othervise
*/
bool operator >( const tree & other ) {
return compare ( other ) > 0;
}
/**
* \brief
* Greater or equal comparison operator.
*
* \param other the other instance to compare with
*
* \return true if this instance is greater or equal than other instance, false othervise
*/
bool operator >=( const tree & other ) {
return compare ( other ) >= 0;
}
// ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
/**
* \brief
* Internal method of printing a tree into a stream
*
* The tree is printed hierarchically.
*
* Example tree a ( b ( c ), b ( c ) ) would be printed like
*
* \-a
* |
* |-b
* | |
* | \-c
* |
* \-b
* |
* \-c
*
* \param os the stream to print to
*
* \return the changed output stream
*/
std::ostream & nicePrint ( std::ostream & os ) const {
nicePrint ( os, "", true );
return os;
}
private:
/**
* \brief
* Internal method of printing a tree into a stream
*
* The tree is printed hierarchically.
*
* Example tree a ( b ( c ), b ( c ) ) would be printed like
*
* \-a
* |
* |-b
* | |
* | \-c
* |
* \-b
* |
* \-c
*
* \param os the stream to print to
* \param prefix the auxiliary parameter representing string of paths in the print
* \param last flag indicating this tree is the last subtree of its parent
*/
void nicePrint ( std::ostream & os, std::string prefix, const bool last ) const {
os << prefix;
if ( last ) {
os << "\\-";
prefix += " ";
} else {
os << "|-";
prefix += "| ";
}
os << getData ( ) << std::endl;
for ( unsigned int i = 0; i < m_children.size ( ); ++i ) {
os << prefix << "|" << std::endl;
m_children[i].nicePrint ( os, prefix, i == m_children.size ( ) - 1 );
}
}
};
/**
* \brief
* Operator to print the tree to the output stream.
*
* \param out the output stream
* \param tree the tree to print
*
* \tparam T the type of values inside the tree
*
* \return the output stream from the \p out
*/
template < class T >
std::ostream & operator <<( std::ostream & out, const tree < T > & t ) {
out << "[";
unsigned level = 0;
for ( typename tree < T >::const_prefix_iterator iter = t.prefix_begin ( ); iter != t.prefix_end ( ); ) {
while ( iter.getLevel ( ) > level ) {
out << "[";
++level;
}
out << level << * iter;
++iter;
bool printComma = iter.getLevel ( ) == level;
while ( iter.getLevel ( ) < level ) {
out << "]";
--level;
printComma = true;
}
if ( printComma && ( level != 0 ) )
out << ",";
}
out << "]";
return out;
}
/**
* \brief
* Specialisation of the compare structure implementing the three-way comparison.
*
* \tparam T the type of values inside the tree
*/
template < class T >
struct compare < ext::tree < T > > {
/**
* \brief
* Implementation of the three-way comparison.
*
* \param first the left operand of the comparison
* \param second the right operand of the comparison
*
* \return negative value of left < right, positive value if left > right, zero if left == right
*/
int operator ()( const ext::tree < T > & first, const ext::tree < T > & second ) const {
return first.compare ( second );
}
};
/**
* \brief
* Overload of to_string function.
*
* \param value the tree to be converted to string
*
* \tparam T the type of values inside the tree
*
* \return string representation
*/
template < class T >
std::string to_string ( const ext::tree < T > & value ) {
std::stringstream ss;
ss << value;
return ss.str();
}
} /* namespace ext */
#endif /* __TREE_HPP_ */