tree.hpp

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

#ifndef __TREE_HPP_
#define __TREE_HPP_

namespace std {

template < class T >
struct AnyArity {
	bool operator ()( const T &, unsigned ) const {
		return true;
	}

};

template < class T, class ArityChecker = AnyArity < T > >
class tree {

	ArityChecker arityChecker;

	struct tree_node {
		T data;

		tree_node * parent;
		std::vector < tree_node > children;

		tree_node ( const T & data, const std::vector < tree_node > & children ) : data ( data ), parent ( nullptr ), children ( children ) {
			for ( tree_node & child : this->children )
				child.parent = this;
		}

		tree_node ( T && data, std::vector < tree_node > && children ) : data ( std::move ( data ) ), parent ( nullptr ), children ( std::move ( children ) ) {
			for ( tree_node & child : this->children )
				child.parent = this;
		}

		~tree_node ( ) noexcept {
		}

		tree_node ( const tree_node & node ) : data ( node.data ), parent ( node.parent ), children ( node.children ) {
			for ( tree_node & child : children )
				child.parent = this;
		}

		tree_node ( tree_node && node ) noexcept : data ( std::move ( node.data ) ), parent ( node.parent ), children ( std::move ( node.children ) ) {
			for ( tree_node & child : children )
				child.parent = this;
		}

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

		tree_node & operator =( tree_node && node ) noexcept {
			data = std::move ( node.data );
			children = std::move ( node.children );

			for ( tree_node & child : children )
				child.parent = this;

			return * this;
		}

		tree_node * getParent ( ) {
			return parent;
		}

		const tree_node * getParent ( ) const {
			return parent;
		}

		T & getData ( ) {
			return data;
		}

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

		std::vector < tree_node > & getChildren ( ) {
			return children;
		}

		const std::vector < tree_node > & getChildren ( ) const {
			return children;
		}

	};

	tree_node root;

	std::vector < tree_node > fromTree ( const std::vector < tree < T, ArityChecker > > & input ) {
		std::vector < tree_node > res;

		for ( const tree < T, ArityChecker > & subtree : input )
			res.push_back ( subtree.root );

		return res;
	}

public:
	class const_children_iterator : public std::iterator < std::bidirectional_iterator_tag, T > {
		typename std::vector < tree_node >::const_iterator node;

	public:
		const_children_iterator ( typename std::vector < tree_node >::const_iterator node ) : node ( node ) {
		}

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

		const_children_iterator & operator ++( ) {
			++node;
			return * this;
		}

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

			operator ++( );
			return tmp;
		}

		const_children_iterator & operator --( ) {
			--node;
			return * this;
		}

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

			operator --( );
			return tmp;
		}

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

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

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

		size_t operator -( const const_children_iterator other ) const {
			return node - other.node;
		}

		const_children_iterator begin ( ) const {
			return node->getChildren ( ).begin ( );
		}

		const_children_iterator end ( ) const {
			return node->getChildren ( ).end ( );
		}

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

	private:
		const tree_node & getTreeNode ( ) const {
			return * node;
		}

		typename std::vector < tree_node >::const_iterator getUnderlyingIterator ( ) const {
			return node;
		}

		template < class F, class G >
		friend class tree;
	};

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

		bool virtual_node;
		bool isEnd;

	public:
		const_structure_iterator ( typename std::vector < tree_node >::const_iterator node ) : node ( node ), 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_node * parent = node->getParent ( );

				if ( parent != nullptr ) {
					++node;

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

				if ( newIter != node->getChildren ( ).begin ( ) ) {
					++level;
					node = newIter;
					--node;
				} else {
					virtual_node = false;
				}
			} else {
				const tree_node * parent = node->getParent ( );

				if ( parent != nullptr ) {
					if ( node == parent->getChildren ( ).begin ( ) ) {
						--level;
						node = typename std::vector < tree_node >::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 ( );
		}

		unsigned getLevel ( ) const {
			return level;
		}

		bool getVirtual ( ) const {
			return virtual_node;
		}

	private:
		const tree_node & getTreeNode ( ) const {
			return * node;
		}

		typename std::vector < tree_node >::const_iterator getUnderlyingIterator ( ) const {
			return node;
		}

		template < class F, class G >
		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_node >::const_iterator node ) : node ( node ) {
		}

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

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

	private:
		const tree_node & getTreeNode ( ) const {
			return node.getTreeNode ( );
		}

		typename std::vector < tree_node >::const_iterator getUnderlyingIterator ( ) const {
			return node.getUnderlyingIterator;
		}

		template < class F, class G >
		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_node >::const_iterator node ) : node ( node ) {
		}

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

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

	private:
		const tree_node & getTreeNode ( ) const {
			return node.getTreeNode ( );
		}

		typename std::vector < tree_node >::const_iterator getUnderlyingIterator ( ) const {
			return node.getUnderlyingIterator ( );
		}

		template < class F, class G >
		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_node * under_node = const_cast < tree_node * > ( & under.getTreeNode ( ) );
		std::vector < tree_node > & children = const_cast < std::vector < tree_node > & > ( under_node->getChildren ( ) );

		size_t insertedSize = end - begin;

		if ( !arityChecker ( * under, children.size ( ) + insertedSize ) )
			throw std::length_error ( "Invalid number of children" );

		std::vector < tree_node > inserted;

		for ( const_children_iterator beginCopy = begin; beginCopy != end; ++beginCopy )
			inserted.push_back ( beginCopy.getTreeNode ( ) );

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

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

		typename std::vector < tree_node >::const_iterator citer = iter;
		return citer;
	}

public:
	const_children_iterator insert ( const_children_iterator under, const_children_iterator position, const tree < T, ArityChecker > & value ) {
		std::vector < tree_node > & children = const_cast < std::vector < tree_node > & > ( under.getTreeNode ( ).getChildren ( ) );

		typename std::vector < tree_node >::iterator iter = children.insert ( position.getUnderlyingIterator ( ), value.root );
		iter->parent = const_cast < tree_node * > ( & under.getTreeNode ( ) );
		typename std::vector < tree_node >::const_iterator res = iter;
		return res;
	}

	const_children_iterator insert ( const_children_iterator under, const_children_iterator position, tree < T, ArityChecker > && value ) {
		std::vector < tree_node > & children = const_cast < std::vector < tree_node > & > ( under.getTreeNode ( ).getChildren ( ) );

		typename std::vector < tree_node >::iterator iter = children.insert ( position.getUnderlyingIterator ( ), std::move ( value.root ) );
		iter->parent = const_cast < tree_node * > ( & under.getTreeNode ( ) );
		typename std::vector < tree_node >::const_iterator res = iter;
		return res;
	}

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

		for ( ; begin != end; ++begin )
			children.push_back ( tree_node ( * begin, { } ) );

		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 ( const T & data, const std::vector < tree < T, ArityChecker > > & subtrees, ArityChecker arityChecker = ArityChecker ( ) ) : arityChecker ( arityChecker ), root ( data, fromTree ( subtrees ) ) {
		if ( !arityChecker ( data, subtrees.size ( ) ) )
			throw std::length_error ( "Invalid number of children" );
	}

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

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

	template < typename Iterator, typename std::enable_if < std::is_iterator < Iterator >::value >::type >
	tree ( const T & data, Iterator begin, Iterator end ) : root ( data, { } ) {
		std::vector < tree_node > children;

		for ( ; begin != end; ++begin )
			children.push_back ( tree_node ( * begin, { } ) );

		insert_helper ( begin ( ), begin ( ).end ( ), children.cbegin ( ), children.cend ( ) );
	}

	tree ( const T & data, const_children_iterator begin, const_children_iterator end ) : root ( data, { } ) {
		insert_helper ( begin ( ), begin ( ).end ( ), begin, end );
	}

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

	const_children_iterator begin ( ) const {
		return typename std::vector < tree_node >::const_iterator ( & root );
	}

	const_children_iterator end ( ) const {
		return typename std::vector < tree_node >::const_iterator ( & root + 1 );
	}

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

	const_prefix_iterator prefix_begin ( ) const {
		return typename std::vector < tree_node >::const_iterator ( & root );
	}

	const_prefix_iterator prefix_end ( ) const {
		const_prefix_iterator res ( typename std::vector < tree_node >::const_iterator ( & root + 1 ) );

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

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

	const_postfix_iterator postfix_begin ( ) const {
		const_postfix_iterator res { typename std::vector < tree_node >::const_iterator ( & root ) };

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

		return res;
	}

	const_postfix_iterator postfix_end ( ) const {
		const_postfix_iterator res ( typename std::vector < tree_node >::const_iterator ( & root + 1 ) );

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

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

	const_structure_iterator structure_begin ( ) const {
		return typename std::vector < tree_node >::const_iterator ( & root );
	}

	const_structure_iterator structure_end ( ) const {
		const_structure_iterator res ( typename std::vector < tree_node >::const_iterator ( & root + 1 ) );

		res.isEnd = true;
		return res;
	}

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

	void push_back ( const_children_iterator under, const T & value ) {
		std::vector < tree_node > & children = const_cast < std::vector < tree_node > & > ( under.getTreeNode ( ).getChildren ( ) );

		if ( !arityChecker ( * under, children.size ( ) + 1 ) )
			throw std::length_error ( "Invalid number of children" );

		children.push_back ( tree_node ( value, { } ) );
		std::prev ( children.end ( ) )->parent = const_cast < tree_node * > ( & under.getTreeNode ( ) );
	}

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

		if ( !arityChecker ( * under, children.size ( ) + 1 ) )
			throw std::length_error ( "Invalid number of children" );

		children.push_back ( tree_node ( std::move ( value ), { } ) );
		std::prev ( children.end ( ) )->parent = const_cast < tree_node * > ( & under.getTreeNode ( ) );
	}

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

	const_children_iterator erase ( const_children_iterator under, const_children_iterator position ) {
		std::vector < tree_node > & children = const_cast < std::vector < tree_node > & > ( under.getTreeNode ( ).getChildren ( ) );

		if ( !arityChecker ( * under, children.size ( ) - 1 ) )
			throw std::length_error ( "Invalid number of children" );

		typename std::vector < tree_node >::iterator iter = children.erase ( position.getUnderlyingIterator ( ) );
		typename std::vector < tree_node >::const_iterator res = iter;
		return res;
	}

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

	template < class ... Indexes >
	const T & operator ()( Indexes ... indexes ) const {
		const tree_node * node = & root;

		( void ) std::initializer_list < int > { ( node = & node->getChildren ( )[indexes], 0 ) ... };

		return node->getData ( );
	}

private:
	class SubscriptAccess {
		tree_node * node;
		const ArityChecker & arityChecker;

	public:
		SubscriptAccess ( tree_node * node, const ArityChecker & arityChecker ) : node ( node ), arityChecker ( arityChecker ) {
		}

		SubscriptAccess ( const SubscriptAccess & ) = delete;
		SubscriptAccess ( SubscriptAccess && ) = delete;

		SubscriptAccess & operator =( const SubscriptAccess & ) = delete;
		SubscriptAccess & operator =( SubscriptAccess && ) = delete;

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

		SubscriptAccess & operator =( const T & data ) {
			if ( !arityChecker ( data, node->getChildren ( ).size ( ) ) )
				throw std::length_error ( "Invalid number of children" );

			node->getData ( ) = data;

			return * this;
		}

		SubscriptAccess & operator =( const tree < T, ArityChecker > & data ) {
			* node = data.root;

			return * this;
		}

		friend void swap ( SubscriptAccess && first, SubscriptAccess && second ) {
			tree_node tmp = std::move ( * first.node );

			* first.node = std::move ( * second.node );
			* second.node = std::move ( tmp );
		}

	};

public:
	template < class ... Indexes >
	SubscriptAccess operator ()( Indexes ... indexes ) {
		tree_node * node = & root;

		( void ) std::initializer_list < int > { ( node = & node->getChildren ( )[indexes], 0 ) ... };

		return { node, arityChecker };
	}

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

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

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

		return sign;
	}

	bool checkStructure ( ) const {
		return root.parent == nullptr && checkStructure ( root );
	}

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

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

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

	int compare ( const 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 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;
	}

};

template < class T, class ... Ts >
std::ostream & operator <<( std::ostream & out, const tree < T, Ts ... > & t ) {
	out << "[";

	unsigned level = 0;

	for ( typename tree < T, Ts ... >::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, class ... Ts >
struct compare < tree < T, Ts ... > > {
	int operator ()( const tree < T, Ts ... > & first, const tree < T, Ts ... > & second ) const {
		return first.compare ( second );
	}

};

} /* namespace std */

#endif /* __TREE_HPP_ */