/*
* forward_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 __FORWARD_TREE_HPP_
#define __FORWARD_TREE_HPP_
#include <memory>
#include <sstream>
#include <string>
#include "vector.hpp"
#include "deque.hpp"
#include "tree_base.hpp"
#include "iterator.hpp"
#include "compare.hpp"
namespace ext {
/**
* \brief
* Class introducing a forward_tree with interface trying to be close to the interface of standard library containers.
*
* \tparam T the type of values inside nodes of the forward_tree
*/
template < class T >
class forward_tree {
/**
* \brief
* The value in the root node of the forward_tree
*/
T m_data;
/**
* \brief
* Container of children of the root node of the tree.
*
* The children are forward_trees themselves, imitating the notion of a subtree of a tree is itself a tree
*/
ext::vector < forward_tree > m_children;
public:
/**
* \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 < forward_tree > & getChildren ( ) {
return m_children;
}
/**
* \brief
* Getter of children of the root node.
*
* \return children of the root node
*/
const ext::vector < forward_tree > & getChildren ( ) const {
return m_children;
}
/**
* \brief
* The iterator type over children of the node
*/
typedef typename ext::vector < forward_tree >::const_iterator const_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 < forward_tree >::const_iterator node;
/**
* \brief
* List of references to parents so far visited.
*/
typename ext::deque < const forward_tree * > parents;
/**
* \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 < forward_tree >::const_iterator n ) : node ( n ), parents ( ), virtual_node ( false ), isEnd ( false ) {
}
/**
* \brief
* Advance the iterator.
*
* \return the updated iterator
*/
const_structure_iterator & operator ++( ) {
if ( virtual_node ) {
if ( parents.size ( ) ) {
++node;
const forward_tree * parent = parents.back ( );
if ( node == parent->getChildren ( ).end ( ) ) {
parents.pop_back();
node = typename ext::vector < forward_tree >::const_iterator ( parent );
} else {
virtual_node = false;
}
} else {
++node;
virtual_node = false;
isEnd = true;
}
} else {
typename ext::vector < forward_tree >::const_iterator newIter = node->getChildren ( ).begin ( );
if ( newIter != node->getChildren ( ).end ( ) ) {
parents.push_back ( & * node );
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 < forward_tree >::const_iterator newIter = node->getChildren ( ).end ( );
if ( newIter != node->getChildren ( ).begin ( ) ) {
parents.push_back ( & * node );
node = newIter;
--node;
} else {
virtual_node = false;
}
} else {
if ( parents.size ( ) ) {
const forward_tree * parent = parents.back ( );
if ( node == parent->getChildren ( ).begin ( ) ) {
parents.pop_back();
node = typename ext::vector < forward_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.
*
* \brief 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.
*
* \brief 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 parents.size ( );
}
/**
* \brief
* Allows to distinguis 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 forward_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 < forward_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.
*
* \brief 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.
*
* \brief 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 forward_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 < forward_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 forward_tree;
};
// ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
private:
/**
* \brief
* Forward tree vector 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 < forward_tree > fromIterator ( Iterator begin, Iterator end ) {
ext::vector < forward_tree > res;
for ( ; begin != end; ++begin )
res.push_back ( forward_tree ( * begin, { } ) );
return res;
}
public:
/**
* \brief
* Inserts a subtree into a forward_tree.
*
* \param under the node under which to add the subtree
* \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 under, const_children_iterator position, forward_tree < T > && value ) {
ext::vector < forward_tree > & children = const_cast < ext::vector < forward_tree > & > ( under->getChildren ( ) );
return children.insert ( position, std::move ( value ) );
}
/**
* \brief
* Inserts a subtree into a forward_tree.
*
* \param under the node under which to add the subtree
* \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 under, const_children_iterator position, const forward_tree < T > & value ) {
return insert ( under, position, forward_tree < T > ( value ) );
}
/**
* \brief
* Insert helper for insertion specified by position in children and inserted subtrees given by range of iterators.
*
* \param under the node under which to add subtrees
* \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 under, const_children_iterator position, const_children_iterator begin, const_children_iterator end ) {
ext::vector < forward_tree > & children = const_cast < ext::vector < forward_tree > & > ( under->getChildren ( ) );
return children.insert ( position, begin, end );
}
/**
* \brief
* Inserts a subtrees into a forward_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 under the node under which to add the subtree
* \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 under, const_children_iterator position, Iterator begin, Iterator end ) {
ext::vector < forward_tree > children = fromIterator ( begin, end );
return insert ( under, position, children.cbegin ( ), children.cend ( ) );
}
// ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
/**
* \brief
* Constructor of the forward_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
*/
forward_tree ( T && data, ext::vector < forward_tree > && children ) : m_data ( std::move ( data ) ), m_children ( std::move ( children ) ) {
}
/**
* \brief
* Constructor of the forward_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
*/
forward_tree ( const T & data, const ext::vector < forward_tree > & subtrees ) : forward_tree ( T ( data ), ext::vector < forward_tree > ( subtrees ) ) {
}
/**
* \brief
* Constructor of the forward_tree from value to be stored in the root node and pack of children trees.
*
* \param data the value to be stored in the root
* \param subtrees ... pack of subtrees
*/
template < typename ... Types >
forward_tree ( const T & data, Types ... subtrees ) : forward_tree ( data, ext::vector < forward_tree > { subtrees ... } ) {
}
/**
* \brief
* Constructor of the forward_tree from value to be stored in the root node and pack of children trees.
*
* \param data the value to be stored in the root
* \param subtrees ... pack of subtrees
*/
template < typename ... Types >
forward_tree ( T && data, Types ... subtrees ) : forward_tree ( std::move ( data ), ext::vector < forward_tree > { subtrees ... } ) {
}
/**
* \brief
* Constructor of the forward_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 >
forward_tree ( const T & data, Iterator begin, Iterator end ) : forward_tree ( data, fromIterator ( begin, end ) ) {
}
/**
* \brief
* Constructor of the forward_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
*/
forward_tree ( const T & data, const_children_iterator begin, const_children_iterator end ) : forward_tree ( data, ext::vector < forward_tree > ( begin, end ) ) {
}
// ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
/**
* \brief
* Getter of a children iterator to the root of the tree
*
* \return iterator to the root
*/
const_children_iterator root ( ) const {
return typename ext::vector < forward_tree >::const_iterator ( 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 one after the last child
*
* \return iterator one after the last child
*/
const_children_iterator end ( ) const {
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 < forward_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 < forward_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 < forward_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 < forward_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 < forward_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 < forward_tree >::const_iterator ( this + 1 ) );
res.isEnd = true;
return res;
}
// ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
/**
* \brief
* Pushbacks a subtree after last child of a node specified by an interator given by \p under.
*
* \param under the node under which to add the subtree
* \param value a subtree to pushback to child list
*/
void push_back ( const_children_iterator under, ext::forward_tree < T > && value ) {
ext::vector < forward_tree > & children = const_cast < ext::vector < forward_tree > & > ( under->getChildren ( ) );
children.push_back ( std::move ( value ) );
}
/**
* \brief
* Pushbacks a subtree after last child of a node specified by an interator given by \p under.
*
* \param under the node under which to add the subtree
* \param value a subtree to pushback to child list
*/
void push_back ( const_children_iterator under, const ext::forward_tree < T > & value ) {
push_back ( under, forward_tree ( value ) );
}
/**
* \brief
* Pushbacks a nullary node after last child of a node specified by an interator given by \p under.
*
* \param under the node under which to add the subtree
* \param value a value to store in nullary node push-backed to the child list
*/
void push_back ( const_children_iterator under, T && value ) {
push_back ( under, forward_tree ( std::move ( value ) ) );
}
/**
* \brief
* Pushbacks a nullary node after last child of a node specified by an interator given by \p under.
*
* \param under the node under which to add the subtree
* \param value a value to store in nullary node push-backed to the child list
*/
void push_back ( const_children_iterator under, const T & value ) {
push_back ( under, T ( value ) );
}
// ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
/**
* \brief
* Erases a subtree from a tree on given by \p position under a node from \p under
*
* \param under the node under which to perform the erase
* \param position the specification of position in children where to erase the subtree
*/
const_children_iterator erase ( const_children_iterator under, const_children_iterator position ) {
ext::vector < forward_tree > & children = const_cast < ext::vector < forward_tree > & > ( under->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 forward_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 ) {
forward_tree * node = this;
for ( unsigned index : indexes ) {
node = & node->getChildren ( )[index];
}
return node->getData ( );
}
// ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
/**
* \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 ( forward_tree & first, forward_tree & second ) {
using std::swap;
swap ( first.m_data, second.m_data );
swap ( first.m_children, second.m_children );
}
// ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
/**
* \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 forward_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 forward_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 forward_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 forward_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 forward_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 forward_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 forward_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, 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 forward_tree to the output stream.
*
* \param out the output stream
* \param forward_tree the forward_tree to print
*
* \tparam T the type of values inside the forward_tree
*
* \return the output stream from the \p out
*/
template < class T >
std::ostream & operator <<( std::ostream & out, const forward_tree < T > & t ) {
out << "[";
unsigned level = 0;
for ( typename forward_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 forward_tree
*/
template < class T >
struct compare < ext::forward_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::forward_tree < T > & first, const ext::forward_tree < T > & second ) const {
return first.compare ( second );
}
};
/**
* \brief
* Overload of to_string function.
*
* \param value the forward_tree to be converted to string
*
* \tparam T the type of values inside the forward_tree
*
* \return string representation
*/
template < class T >
std::string to_string ( const ext::forward_tree < T > & value ) {
std::stringstream ss;
ss << value;
return ss.str();
}
} /* namespace ext */
#endif /* __FORWARD_TREE_HPP_ */