tree.hpp

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

#ifndef __TREE_HPP_
#define __TREE_HPP_

#include <memory>
#include <vector>
#include <deque>
#include <string>
#include <sstream>

#include "compare.hpp"
#include "iterator.hpp"
#include "tree_base.hpp"

namespace ext {

template < class T >
class tree {
	T m_data;

	tree * m_parent;
	std::vector < tree > m_children;

public:
	tree * getParent ( ) {
		return m_parent;
	}

	const tree * getParent ( ) const {
		return m_parent;
	}

	T & getData ( ) {
		return m_data;
	}

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

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

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

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

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

	class const_structure_iterator : public std::iterator < std::bidirectional_iterator_tag, T > {
		typename std::vector < tree >::const_iterator node;
		unsigned level;

		bool virtual_node;
		bool isEnd;

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

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

		const_structure_iterator & operator ++( ) {
			if ( virtual_node ) {
				const tree * parent = node->getParent ( );
				++node;

				if ( parent != nullptr ) {
					if ( node == parent->getChildren ( ).end ( ) ) {
						--level;
						node = typename std::vector < tree >::const_iterator ( parent );
					} else {
						virtual_node = false;
					}
				} else {
					virtual_node = false;
					isEnd = true;
				}
			} else {
				typename std::vector < tree >::const_iterator newIter = node->getChildren ( ).begin ( );

				if ( newIter != node->getChildren ( ).end ( ) ) {
					++level;
					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 < 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 std::vector < 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 tree;
	};

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

	public:
		const_prefix_iterator ( typename std::vector < 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 tree;
	};

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

	public:
		const_postfix_iterator ( typename std::vector < 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 tree;
	};

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

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

		typename std::vector < tree >::iterator iter = children.insert ( position, begin, end );

		for ( typename std::vector < tree >::iterator iterCopy = iter; begin != end; ++begin, ++iterCopy )
			iterCopy->m_parent = under_node;

		return iter;
	}

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

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

		return res;
	}

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

		typename std::vector < tree >::iterator iter = children.insert ( position, std::move ( value ) );
		iter->m_parent = const_cast < tree * > ( & * under );
		return iter;
	}

	const_children_iterator insert ( const_children_iterator under, const_children_iterator position, const tree < T > & value ) {
		return insert ( under, position, tree < T > ( value ) );
	}

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

		return insert_helper ( under, position, children.cbegin ( ), 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:
	tree ( T && data, std::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;
	}

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

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

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

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

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

	~tree ( ) noexcept {
	}

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

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

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

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

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

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

	const_children_iterator parent ( ) const {
		return typename std::vector < tree >::const_iterator ( this->getParent ( ) );
	}

	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 < tree >::const_iterator ( this );
	}

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

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

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

	const_postfix_iterator postfix_begin ( ) const {
		const_postfix_iterator res { typename std::vector < 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 < tree >::const_iterator ( this + 1 ) );

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

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

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

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

		res.isEnd = true;
		return res;
	}

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

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

		children.push_back ( std::move ( value ) );
		children.back ( ).m_parent = const_cast < tree * > ( & * under );
	}

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

	void push_back ( const_children_iterator under, T && value ) {
		push_back ( under, 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 < tree > & children = const_cast < std::vector < 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 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 ) {
		tree * node = this;

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

		return node->getData ( );
	}

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

	bool checkStructure ( const tree & node ) const {
		bool sign = true;

		for ( const tree & child : node.getChildren ( ) )
			sign &= child.getParent ( ) == & node && checkStructure ( child );

		return sign;
	}

	bool checkStructure ( ) const {
		return m_parent == nullptr && checkStructure ( * this );
	}

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

	friend void swap ( tree & first, tree & second ) {
		using std::swap;

		swap ( std::move ( first.m_data ), std::move ( second.m_data ) );
		swap ( std::move ( first.m_children ), std::move ( second.m_children ) );
		swap ( std::move ( first.m_parent ), std::move ( second.m_parent ) );
	}

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

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

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

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

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

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

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

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

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

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

};

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

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

};

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