tree.hpp

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

#ifndef __TREE_HPP_
#define __TREE_HPP_

namespace std {

template < class Data >
class BaseNode {
	Data * parent;

	template < class D, class CD, class C >
	friend class NularyNode;
	template < class D, class CD, class C >
	friend class UnaryNode;
	template < class D, class CD, class C >
	friend class BinaryNode;
	template < class D, class CD, class C >
	friend class TernaryNode;
	template < class D, int I, class CD, class C >
	friend class AnyaryNode;
	template < class D, class CD, class C >
	friend class FixedaryNode;
	template < class D, class CD, class C >
	friend class VararyNode;

	Data * operator ->( ) {
		return static_cast < Data * > ( this );
	}

	const Data * operator ->( ) const {
		return static_cast < Data * > ( this );
	}

public:
	BaseNode ( ) : parent ( nullptr ) {
	}

	virtual ~BaseNode ( ) noexcept {
	}

	BaseNode ( const BaseNode & ) : parent ( nullptr ) {
	}

	BaseNode ( BaseNode && ) noexcept : parent ( nullptr ) {
	}

	BaseNode & operator =( const BaseNode & ) {
		return * this;
	}

	BaseNode & operator =( BaseNode && ) noexcept {
		return * this;
	}

	Data * getParent ( ) {
		return parent;
	}

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

};

template < class Data, int arity, class ConstData = Data, class Cast = Data >
class AnyaryNode {
	typename TupleBuilder < Data, arity >::type children;

	template < std::size_t ... Indices >
	void setParent ( std::index_sequence < Indices ... > ) {
		( void ) std::initializer_list < void * > { std::get < Indices > ( children )->parent = static_cast < Cast * > ( this ) ... };
	}

public:
	AnyaryNode ( typename TupleBuilder < Data, arity >::type children ) : children ( std::move ( children ) ) {
		setParent ( std::make_index_sequence < arity > ( ) );
	}

	virtual ~AnyaryNode ( ) noexcept {
	}

	AnyaryNode ( const AnyaryNode & other ) : AnyaryNode ( other.children ) {
	}

	AnyaryNode ( AnyaryNode && other ) noexcept : AnyaryNode ( std::move ( other.children ) ) {
	}

	AnyaryNode & operator =( const AnyaryNode & other ) {
		return * this = AnyaryNode ( other );
	}

	AnyaryNode & operator =( AnyaryNode && other ) noexcept {
		std::swap ( this->children, other.children );

		setParent ( std::make_index_sequence < arity > ( ) );

		return * this;
	}

	const typename TupleBuilder < Data, arity >::type & getElements ( ) {
		return children;
	}

	const typename TupleBuilder < ConstData, arity >::type & getElements ( ) const {
		return reinterpret_cast < const typename TupleBuilder < ConstData, arity >::type & > ( children );
	}

	template < int N >
	const ConstData & getElement ( ) const {
		return reinterpret_cast < const ConstData & > ( std::get < N > ( children ) );
	}

	template < int N >
	Data & getElement ( ) {
		return std::get < N > ( children );
	}

	void setElements ( typename TupleBuilder < Data, arity >::type children ) {
		children = std::move ( children );
		setParent ( std::make_index_sequence < arity > ( ) );
	}

	template < int N >
	void setElement ( Data d ) {
		std::get < N > ( children ) = std::move ( d );
		std::get < N > ( children )->parent = static_cast < Cast * > ( this );
	}

};

template < class Data, class ConstData = Data, class Cast = Data >
class NularyNode : public AnyaryNode < Data, 0, ConstData, Cast > {
public:
	NularyNode ( ) : AnyaryNode < Data, 0, ConstData, Cast > ( std::tuple < > ( ) ) {
	}

};

template < class Data, class ConstData = Data, class Cast = Data >
class UnaryNode : public AnyaryNode < Data, 1, ConstData, Cast > {
public:
	UnaryNode ( Data c ) : AnyaryNode < Data, 1, ConstData, Cast > ( std::make_tuple ( std::move ( c ) ) ) {
	}

	Data & getChild ( ) {
		return this->template getElement < 0 > ( );
	}

	const ConstData & getChild ( ) const {
		return this->template getElement < 0 > ( );
	}

	void setChild ( Data c ) {
		this->template setElement < 0 > ( std::move ( c ) );
	}

};

template < class Data, class ConstData = Data, class Cast = Data >
class BinaryNode : public AnyaryNode < Data, 2, ConstData, Cast > {
public:
	BinaryNode ( Data l, Data r ) : AnyaryNode < Data, 2, ConstData, Cast > ( std::make_tuple ( std::move ( l ), std::move ( r ) ) ) {
	}

	Data & getLeft ( ) {
		return this->template getElement < 0 > ( );
	}

	const ConstData & getLeft ( ) const {
		return this->template getElement < 0 > ( );
	}

	void setLeft ( Data l ) {
		this->template setElement < 0 > ( std::move ( l ) );
	}

	Data & getRight ( ) {
		return this->template getElement < 1 > ( );
	}

	const ConstData & getRight ( ) const {
		return this->template getElement < 1 > ( );
	}

	void setRight ( Data r ) {
		this->template setElement < 1 > ( std::move ( r ) );
	}

};

template < class Data, class ConstData = Data, class Cast = Data >
class TernaryNode : public AnyaryNode < Data, 3, ConstData, Cast > {
public:
	TernaryNode ( Data f, Data s, Data t ) : AnyaryNode < Data, 3, ConstData, Cast > ( std::make_tuple ( std::move ( f ), std::move ( s ), std::move ( t ) ) ) {
	}

	Data & getFirst ( ) {
		return this->template getElement < 0 > ( );
	}

	const ConstData & getFirst ( ) const {
		return this->template getElement < 0 > ( );
	}

	void setFirst ( Data f ) {
		this->template setElement < 0 > ( std::move ( f ) );
	}

	Data & getSecond ( ) {
		return this->template getElement < 1 > ( );
	}

	const ConstData & getSecond ( ) const {
		return this->template getElement < 1 > ( );
	}

	void setSecond ( Data s ) {
		this->template setElement < 1 > ( std::move ( s ) );
	}

	Data & getThird ( ) {
		return this->template getElement < 2 > ( );
	}

	const ConstData & getThird ( ) const {
		return this->template getElement < 2 > ( );
	}

	void setThird ( Data t ) {
		this->template setElement < 2 > ( std::move ( t ) );
	}

};

template < class Data, class ConstData = Data, class Cast = Data >
class FixedaryNode {
	std::vector < Data > children;

public:
	template < typename ... Types >
	FixedaryNode ( Types ... data ) {
		Data args[] { std::move ( data ) ... };

		for ( Data & child : args )
			children.push_back ( std::move ( child ) );

		for ( Data & child : children )
			child->parent = static_cast < Cast * > ( this );
	}

	FixedaryNode ( std::vector < Data > c ) : children ( std::move ( c ) ) {
		for ( Data & child : children )
			child->parent = static_cast < Cast * > ( this );
	}

	virtual ~FixedaryNode ( ) noexcept {
	}

	FixedaryNode ( const FixedaryNode & other ) : FixedaryNode ( other.children ) {
	}

	FixedaryNode ( FixedaryNode && other ) noexcept : FixedaryNode ( std::move ( other.children ) ) {
	}

	FixedaryNode & operator =( const FixedaryNode & other ) {
		return * this = FixedaryNode ( other );
	}

	FixedaryNode & operator =( FixedaryNode && other ) noexcept {
		std::swap ( this->children, other.children );

		for ( Data & child : children )
			child->parent = static_cast < Cast * > ( this );

		return * this;
	}

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

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

	void setChildren ( std::vector < Data > c ) {
		if ( c.size ( ) != children.size ( ) )
			throw "Arity != size";

		children = std::move ( c );

		for ( Data & child : children )
			child->parent = static_cast < Cast * > ( this );
	}

	void setChild ( Data d, int index ) {
		if ( children.size ( ) >= index )
			throw "Index out of bounds";

		children[index] = std::move ( d );

		children[index]->parent = static_cast < Cast * > ( this );
	}

};

template < class Data, class ConstData = Data, class Cast = Data >
class VararyNode {
	std::vector < Data > children;

public:
	VararyNode ( ) {
	}

	VararyNode ( std::vector < Data > c ) : children ( std::move ( c ) ) {
		for ( Data & child : children )
			child->parent = static_cast < Cast * > ( this );
	}

	virtual ~VararyNode ( ) noexcept {
	}

	VararyNode ( const VararyNode & other ) : VararyNode ( other.children ) {
	}

	VararyNode ( VararyNode && other ) noexcept : VararyNode ( std::move ( other.children ) ) {
	}

	VararyNode & operator =( const VararyNode & other ) {
		return * this = VararyNode ( other );
	}

	VararyNode & operator =( VararyNode && other ) noexcept {
		std::swap ( this->children, other.children );

		for ( Data & child : children )
			child->parent = static_cast < Cast * > ( this );

		return * this;
	}

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

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

	void setChildren ( std::vector < Data > c ) {
		children = std::move ( c );

		for ( Data & child : children )
			child->parent = static_cast < Cast * > ( this );
	}

	void setChild ( Data d, int index ) {
		children[index] = std::move ( d );

		children[index]->parent = static_cast < Cast * > ( this );
	}

	void setChild ( Data d, typename std::vector < Data >::iterator it ) {
		* it = std::move ( d );

		( * it )->parent = static_cast < Cast * > ( this );
	}

	typename std::vector < Data >::iterator insert ( typename std::vector < Data >::iterator it, Data d ) {
		it = children.insert ( it, std::move ( d ) );

		( * std::prev ( it ) ) -> parent = static_cast < Cast * > ( this );

		return it;
	}

	template < class InputIterator >
	typename std::vector < Data >::iterator insert ( typename std::vector < Data >::iterator it, InputIterator first, InputIterator last ) {
		size_t off = it - children.begin ( );
		size_t size = last - first;

		children.insert ( it, first, last );
		it = children.begin ( ) + off;

		 // TODO on g++-4.9 use: it = children->insert( it, first, last );
		typename std::vector < Data >::iterator end = it + size;

		for ( ; it != end; it++ )
			( * it )->parent = static_cast < Cast * > ( this );

		return it;
	}

	void pushBackChild ( Data d ) {
		children.push_back ( std::move ( d ) );
		children[children.size ( ) - 1]->parent = static_cast < Cast * > ( this );
	}

};

template < class Data, class ConstData, class Cast >
class Tree {
public:
	static void setChild ( const UnaryNode < Data, ConstData, Cast > & node, Data child ) {
		const_cast < UnaryNode < Data, ConstData, Cast > & > ( node ).setChild ( std::move ( child ) );
	}

	static void setLeft ( const BinaryNode < Data, ConstData, Cast > & node, Data child ) {
		const_cast < BinaryNode < Data, ConstData, Cast > & > ( node ).setLeft ( std::move ( child ) );
	}

	static void setRight ( const BinaryNode < Data, ConstData, Cast > & node, Data child ) {
		const_cast < BinaryNode < Data, ConstData, Cast > & > ( node ).setRight ( std::move ( child ) );
	}

	static void setFirst ( const TernaryNode < Data, ConstData, Cast > & node, Data child ) {
		const_cast < TernaryNode < Data, ConstData, Cast > & > ( node ).setFirst ( std::move ( child ) );
	}

	static void setSecond ( const TernaryNode < Data, ConstData, Cast > & node, Data child ) {
		const_cast < TernaryNode < Data, ConstData, Cast > & > ( node ).setSecond ( std::move ( child ) );
	}

	static void setThird ( const TernaryNode < Data, ConstData, Cast > & node, Data child ) {
		const_cast < TernaryNode < Data, ConstData, Cast > & > ( node ).setThird ( std::move ( child ) );
	}

	template < int arity >
	static void setChildren ( const AnyaryNode < Data, arity, ConstData, Cast > & node, typename TupleBuilder < Data, arity >::type children ) {
		const_cast < AnyaryNode < Data, arity, ConstData, Cast > & > ( node ).setChildren ( std::move ( children ) );
	}

	template < class N, int arity >
	static void setChild ( const AnyaryNode < Data, arity, ConstData, Cast > & node, Data child ) {
		const_cast < AnyaryNode < Data, arity, ConstData, Cast > & > ( node ).template setChild < N > ( std::move ( child ) );
	}

	static void setChildren ( const FixedaryNode < Data, ConstData, Cast > & node, std::vector < Data > child ) {
		const_cast < FixedaryNode < Data, ConstData, Cast > & > ( node ).setChildren ( std::move ( child ) );
	}

	static void setChild ( const FixedaryNode < Data, ConstData, Cast > & node, Data child, int index ) {
		const_cast < FixedaryNode < Data, ConstData, Cast > & > ( node ).setChild ( std::move ( child ), index );
	}

	static void setChildren ( const VararyNode < Data, ConstData, Cast > & node, std::vector < Data > children ) {
		const_cast < VararyNode < Data, ConstData, Cast > & > ( node ).setChildren ( std::move ( children ) );
	}

	static void setChild ( const VararyNode < Data, ConstData, Cast > & node, Data child, int index ) {
		const_cast < VararyNode < Data, ConstData, Cast > & > ( node ).setChild ( std::move ( child ), index );
	}

	static void setChild ( const VararyNode < Data, ConstData, Cast > & node, Data child, typename std::vector < Data >::iterator it ) {
		const_cast < VararyNode < Data, ConstData, Cast > & > ( node ).setChild ( std::move ( child ), it );
	}

	typename std::vector < Data >::iterator insert ( const VararyNode < Data, ConstData, Cast > & node, typename std::vector < Data >::iterator it, Data child ) {
		const_cast < VararyNode < Data, ConstData, Cast > & > ( node ).insert ( it, std::move ( child ) );
	}

	template < class InputIterator >
	typename std::vector < Data >::iterator insert ( const VararyNode < Data, ConstData, Cast > & node, typename std::vector < Data >::iterator it, InputIterator first, InputIterator last ) {
		const_cast < VararyNode < Data, ConstData, Cast > & > ( node ).insert ( it, first, last );
	}

	static void pushBackChild ( const VararyNode < Data, ConstData, Cast > & node, Data child ) {
		const_cast < VararyNode < Data, ConstData, Cast > & > ( node ).pushBackChild ( std::move ( child ) );
	}

};

} /* namespace std */

#endif /* __TREE_HPP_ */