forward_tree.hpp

/*
 * forward_tree.hpp
 *
 * Created on: Jul 2, 2016
 * Author: Jan Travnicek
 */

#ifndef __FORWARD_TREE_HPP_
#define __FORWARD_TREE_HPP_

namespace std {

template < class T >
class forward_tree {
	T m_data;

	std::vector < forward_tree > m_children;

public:
	T & getData ( ) {
		return m_data;
	}

	const T & getData ( ) const {
		return m_data;
	}

	std::vector < forward_tree > & getChildren ( ) {
		return m_children;
	}

	const std::vector < forward_tree > & getChildren ( ) const {
		return m_children;
	}

	void nicePrint ( std::ostream & os, const std::string & prefix, const bool last ) const {
		os << prefix;

		std::string nextPrefix ( prefix );

		if ( last ) {
			os << "\\-";
			nextPrefix += "  ";
		} else {
			os << "|-";
			nextPrefix += "| ";
		}

		os << getData ( ) << std::endl;

		for ( unsigned int i = 0; i < m_children.size ( ); ++i ) {
			os << nextPrefix << "|" << std::endl;
			m_children[i].nicePrint ( os, nextPrefix, i == m_children.size ( ) - 1 );
		}
	}

	typedef typename std::vector < forward_tree >::const_iterator const_children_iterator;

	class const_structure_iterator : public std::iterator < std::bidirectional_iterator_tag, T > {
		typename std::vector < forward_tree >::const_iterator node;
		typename std::deque < const forward_tree * > parents;
		unsigned level;

		bool virtual_node;
		bool isEnd;

	public:
		const_structure_iterator ( typename std::vector < forward_tree >::const_iterator n ) : node ( n ), parents ( ), level ( 0 ), virtual_node ( false ), isEnd ( false ) {
		}

		const_structure_iterator ( const const_structure_iterator & other ) : node ( other.node ), parents ( other.parents ), level ( other.level ), virtual_node ( other.virtual_node ) {
		}

		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();
						--level;
						node = typename std::vector < forward_tree >::const_iterator ( parent );
					} else {
						virtual_node = false;
					}
				} else {
					++node;
					virtual_node = false;
					isEnd = true;
				}
			} else {
				typename std::vector < forward_tree >::const_iterator newIter = node->getChildren ( ).begin ( );

				if ( newIter != node->getChildren ( ).end ( ) ) {
					++level;

					parents.push_back ( & * node );
					node = newIter;
				} else {
					virtual_node = true;
				}
			}

			return * this;
		}

		const_structure_iterator operator ++( int ) {
			const_structure_iterator tmp ( * this );

			operator ++( );
			return tmp;
		}

		const_structure_iterator & operator --( ) {
			if ( isEnd ) {
				--node;
				virtual_node = true;
				isEnd = false;
			} else if ( virtual_node ) {
				typename std::vector < forward_tree >::const_iterator newIter = node->getChildren ( ).end ( );

				if ( newIter != node->getChildren ( ).begin ( ) ) {
					++level;

					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();
						--level;
						node = typename std::vector < forward_tree >::const_iterator ( parent );
					} else {
						--node;
						virtual_node = true;
					}
				}
			}

			return * this;
		}

		const_structure_iterator operator --( int ) {
			const_structure_iterator tmp ( * this );

			operator --( );
			return tmp;
		}

		bool operator ==( const const_structure_iterator & other ) {
			return node == other.node && virtual_node == other.virtual_node;
		}

		bool operator !=( const const_structure_iterator & other ) {
			return !( * this == other );
		}

		const T & operator *( ) const {
			return node->getData ( );
		}

		const T * operator ->( ) const {
			return & node->getData ( );
		}

		unsigned getLevel ( ) const {
			return level;
		}

		bool getVirtual ( ) const {
			return virtual_node;
		}

		template < class F >
		friend class forward_tree;
	};

	class const_prefix_iterator : public std::iterator < std::bidirectional_iterator_tag, T > {
		const_structure_iterator node;

	public:
		const_prefix_iterator ( typename std::vector < forward_tree >::const_iterator n ) : node ( n ) {
		}

		const_prefix_iterator ( const const_prefix_iterator & other ) : node ( other.node ) {
		}

		const_prefix_iterator & operator ++( ) {
			while ( ( ++node ).getVirtual ( ) );

			return * this;
		}

		const_prefix_iterator operator ++( int ) {
			const_prefix_iterator tmp ( * this );

			operator ++( );
			return tmp;
		}

		const_prefix_iterator & operator --( ) {
			while ( ( --node ).getVirtual ( ) );

			return * this;
		}

		const_prefix_iterator operator --( int ) {
			const_prefix_iterator tmp ( * this );

			operator --( );
			return tmp;
		}

		bool operator ==( const const_prefix_iterator & other ) {
			return node == other.node;
		}

		bool operator !=( const const_prefix_iterator & other ) {
			return !( * this == other );
		}

		const T & operator *( ) const {
			return * node;
		}

		const T * operator ->( ) const {
			return & node->getData ( );
		}

		unsigned getLevel ( ) const {
			return node.getLevel ( );
		}

		template < class F >
		friend class forward_tree;
	};

	class const_postfix_iterator : public std::iterator < std::bidirectional_iterator_tag, T > {
		const_structure_iterator node;

	public:
		const_postfix_iterator ( typename std::vector < forward_tree >::const_iterator n ) : node ( n ) {
		}

		const_postfix_iterator ( const const_postfix_iterator & other ) : node ( other.node ) {
		}

		const_postfix_iterator & operator ++( ) {
			while ( !( ++node ).getVirtual ( ) && !node.isEnd );

			return * this;
		}

		const_postfix_iterator operator ++( int ) {
			const_postfix_iterator tmp ( * this );

			operator ++( );
			return tmp;
		}

		const_postfix_iterator & operator --( ) {
			while ( !( --node ).getVirtual ( ) );

			return * this;
		}

		const_postfix_iterator operator --( int ) {
			const_postfix_iterator tmp ( * this );

			operator --( );
			return tmp;
		}

		bool operator ==( const const_postfix_iterator & other ) {
			return node == other.node;
		}

		bool operator !=( const const_postfix_iterator & other ) {
			return !( * this == other );
		}

		const T & operator *( ) const {
			return * node;
		}

		const T * operator ->( ) const {
			return & node->getData ( );
		}

		unsigned getLevel ( ) const {
			return node.getLevel ( );
		}

		template < class F >
		friend class forward_tree;
	};

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

private:
	const_children_iterator insert_helper ( const_children_iterator under, const_children_iterator position, const_children_iterator begin, const_children_iterator end ) {
		forward_tree * under_node = const_cast < forward_tree * > ( & * under );
		std::vector < forward_tree > & children = const_cast < std::vector < forward_tree > & > ( under_node->getChildren ( ) );

		return children.insert ( position, begin, end );
	}

	template < typename Iterator >
	std::vector < forward_tree > fromIterator ( Iterator begin, Iterator end ) {
		std::vector < forward_tree > res;

		for ( ; begin != end; ++begin )
			res.push_back ( forward_tree ( * begin, { } ) );

		return res;
	}

public:
	const_children_iterator insert ( const_children_iterator under, const_children_iterator position, forward_tree < T > && value ) {
		std::vector < forward_tree > & children = const_cast < std::vector < forward_tree > & > ( under->getChildren ( ) );

		return children.insert ( position, std::move ( value ) );
	}

	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 ) );
	}

	template < class Iterator >
	const_children_iterator insert ( const_children_iterator under, const_children_iterator position, Iterator begin, Iterator end ) {
		std::vector < forward_tree > children = fromIterator ( begin, end );

		return insert_helper ( under, position, children.begin ( ), children.cend ( ) );
	}

	const_children_iterator insert ( const_children_iterator under, const_children_iterator position, const_children_iterator begin, const_children_iterator end ) {
		return insert_helper ( under, position, begin, end );
	}

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

public:
	forward_tree ( T && data, std::vector < forward_tree > && children ) : m_data ( std::move ( data ) ), m_children ( std::move ( children ) ) {
	}

	forward_tree ( const T & data, const std::vector < forward_tree > & subtrees ) : forward_tree ( T ( data ), std::vector < forward_tree > ( subtrees ) ) {
	}

	template < typename ... Types >
	forward_tree ( const T & data, Types ... subtrees ) : forward_tree ( data, std::vector < forward_tree > { subtrees ... } ) {
	}

	template < typename ... Types >
	forward_tree ( T && data, Types ... subtrees ) : forward_tree ( std::move ( data ), std::vector < forward_tree > { subtrees ... } ) {
	}

	template < typename Iterator, typename std::enable_if < std::is_iterator < Iterator >::value >::type >
	forward_tree ( const T & data, Iterator begin, Iterator end ) : forward_tree ( data, fromIterator ( begin, end ) ) {
	}

	forward_tree ( const T & data, const_children_iterator begin, const_children_iterator end ) : forward_tree ( data, std::vector < forward_tree > ( begin, end ) ) {
	}

	~forward_tree ( ) noexcept {
	}

	forward_tree ( const forward_tree & other ) : m_data ( other.m_data ), m_children ( other.m_children ) {
	}

	forward_tree ( forward_tree && other ) noexcept : m_data ( std::move ( other.m_data ) ), m_children ( std::move ( other.m_children ) ) {
	}

	forward_tree & operator =( const forward_tree & node ) {
		return this->operator =( forward_tree ( node ) );
	}

	forward_tree & operator =( forward_tree && node ) noexcept {
		m_data = std::move ( node.m_data );
		m_children = std::move ( node.m_children );

		return * this;
	}

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

	const_children_iterator root ( ) const {
		return typename std::vector < forward_tree >::const_iterator ( this );
	}

	const_children_iterator begin ( ) const {
		return m_children.begin ( );
	}

	const_children_iterator end ( ) const {
		return m_children.end ( );
	}

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

	const_prefix_iterator prefix_begin ( ) const {
		return typename std::vector < forward_tree >::const_iterator ( this );
	}

	const_prefix_iterator prefix_end ( ) const {
		const_prefix_iterator res ( typename std::vector < forward_tree >::const_iterator ( this + 1 ) );

		res.node.isEnd = true;
		return res;
	}

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

	const_postfix_iterator postfix_begin ( ) const {
		const_postfix_iterator res { typename std::vector < forward_tree >::const_iterator ( this ) };

		while ( ! res.node.getVirtual ( ) ) ++res.node;

		return res;
	}

	const_postfix_iterator postfix_end ( ) const {
		const_postfix_iterator res ( typename std::vector < forward_tree >::const_iterator ( this + 1 ) );

		res.node.isEnd = true;
		return res;
	}

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

	const_structure_iterator structure_begin ( ) const {
		return typename std::vector < forward_tree >::const_iterator ( this );
	}

	const_structure_iterator structure_end ( ) const {
		const_structure_iterator res ( typename std::vector < forward_tree >::const_iterator ( this + 1 ) );

		res.isEnd = true;
		return res;
	}

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

	void push_back ( const_children_iterator under, std::forward_tree < T > && value ) {
		std::vector < forward_tree > & children = const_cast < std::vector < forward_tree > & > ( under->getChildren ( ) );

		children.push_back ( std::move ( value ) );
	}

	void push_back ( const_children_iterator under, const std::forward_tree < T > & value ) {
		push_back ( under, forward_tree ( value ) );
	}

	void push_back ( const_children_iterator under, T && value ) {
		push_back ( under, forward_tree ( std::move ( value ) ) );
	}

	void push_back ( const_children_iterator under, const T & value ) {
		push_back ( under, T ( value ) );
	}

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

	const_children_iterator erase ( const_children_iterator under, const_children_iterator position ) {
		std::vector < forward_tree > & children = const_cast < std::vector < forward_tree > & > ( under->getChildren ( ) );

		return children.erase ( position );
	}

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

	template < class ... Indexes >
	const T & operator ()( Indexes ... indexes ) const {
		return this->operator ()( { ( unsigned ) indexes ... } );
	}

	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 ( );
	}

	template < class ... Indexes >
	T & operator ()( Indexes ... indexes ) {
		return this->operator ()( { ( unsigned ) indexes ... } );
	}

	T & operator ()( std::initializer_list < unsigned > indexes ) {
		forward_tree * node = this;

		for ( unsigned index : indexes ) {
			node = & node->getChildren ( )[index];
		}

		return node->getData ( );
	}

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

	friend void swap ( forward_tree & first, forward_tree & second ) {
		swap ( std::move ( first.m_data ), std::move ( second.m_data ) );
		swap ( std::move ( first.m_children ), std::move ( second.m_children ) );
	}

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

	int compare ( const forward_tree & other ) const {
		std::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;
	}

	bool operator ==( const forward_tree & other ) {
		return compare ( other ) == 0;
	}

	bool operator !=( const forward_tree & other ) {
		return compare ( other ) != 0;
	}

	bool operator <( const forward_tree & other ) {
		return compare ( other ) < 0;
	}

	bool operator <=( const forward_tree & other ) {
		return compare ( other ) <= 0;
	}

	bool operator >( const forward_tree & other ) {
		return compare ( other ) > 0;
	}

	bool operator >=( const forward_tree & other ) {
		return compare ( other ) >= 0;
	}

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

	std::ostream & nicePrint ( std::ostream & os ) const {
		nicePrint ( os, "", true );
		return os;
	}

};

template < class T, class ... Ts >
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;
}

template < class T >
struct compare < forward_tree < T > > {
	int operator ()( const forward_tree < T > & first, const forward_tree < T > & second ) const {
		return first.compare ( second );
	}

};

} /* namespace std */

#endif /* __FORWARD_TREE_HPP_ */