tree.hpp

	 */
	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
	 */
	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 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 ) const {
		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 ) const {
		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 ) const {
		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 ) const {
		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 ) const {
		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 ) const {
		return compare ( other ) >= 0;
	}

// ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

	/**
	 * \brief
	 * 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_ */