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, class ConstData = Data, class Cast = Data >
class NularyNode {
public:
	NularyNode ( ) {
	}

};

template < class Data, class ConstData = Data, class Cast = Data >
class UnaryNode {
	Data child;

public:
	UnaryNode ( Data c ) : child ( std::move ( c ) ) {
		child->parent = static_cast < Cast * > ( this );
	}

	virtual ~UnaryNode ( ) noexcept {
	}

	UnaryNode ( const UnaryNode & other ) : UnaryNode ( other.child ) {
	}

	UnaryNode ( UnaryNode && other ) noexcept : UnaryNode ( std::move ( other.child ) ) {
	}

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

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

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

		return * this;
	}

	Data & getChild ( ) {
		return child;
	}

	const ConstData & getChild ( ) const {
		return child;
	}

	void setChild ( Data c ) {
		child = std::move ( c );
		child->parent = static_cast < Cast * > ( this );
	}

};

template < class Data, class ConstData = Data, class Cast = Data >
class BinaryNode {
	Data left;
	Data right;

public:
	BinaryNode ( Data l, Data r ) : left ( std::move ( l ) ), right ( std::move ( r ) ) {
		left->parent = static_cast < Cast * > ( this );
		right->parent = static_cast < Cast * > ( this );
	}

	virtual ~BinaryNode ( ) noexcept {
	}

	BinaryNode ( const BinaryNode & other ) : BinaryNode ( other.left, other.right ) {
	}

	BinaryNode ( BinaryNode && other ) noexcept : BinaryNode ( std::move ( other.left ), std::move ( other.right ) ) {
	}

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

	BinaryNode & operator =( BinaryNode && other ) noexcept {
		std::swap ( this->left, other.left );
		std::swap ( this->right, other.right );

		left->parent = static_cast < Cast * > ( this );
		right->parent = static_cast < Cast * > ( this );

		return * this;
	}

	Data & getLeft ( ) {
		return left;
	}

	const ConstData & getLeft ( ) const {
		return left;
	}

	void setLeft ( Data l ) {
		left = std::move ( l );
		left->parent = static_cast < Cast * > ( this );
	}

	Data & getRight ( ) {
		return right;
	}

	const ConstData & getRight ( ) const {
		return right;
	}

	void setRight ( Data r ) {
		right = std::move ( r );
		right->parent = static_cast < Cast * > ( this );
	}

};

template < class Data, class ConstData = Data, class Cast = Data >
class TernaryNode {
	Data first;
	Data second;
	Data third;

public:
	TernaryNode ( Data f, Data s, Data t ) : first ( std::move ( f ) ), second ( std::move ( s ) ), third ( std::move ( t ) ) {
		first->parent = static_cast < Cast * > ( this );
		second->parent = static_cast < Cast * > ( this );
		third->parent = static_cast < Cast * > ( this );
	}

	virtual ~TernaryNode ( ) noexcept {
	}

	TernaryNode ( const TernaryNode & other ) : TernaryNode ( other.first, other.second, other.third ) {
	}

	TernaryNode ( TernaryNode && other ) noexcept : TernaryNode ( std::move ( other.first ), std::move ( other.second ), std::move ( other.third ) ) {
	}

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

	TernaryNode & operator =( TernaryNode && other ) noexcept {
		std::swap ( this->first, other.first );
		std::swap ( this->second, other.second );
		std::swap ( this->third, other.third );

		first->parent = static_cast < Cast * > ( this );
		second->parent = static_cast < Cast * > ( this );
		third->parent = static_cast < Cast * > ( this );

		return * this;
	}

	Data & getFirst ( ) {
		return first;
	}

	const ConstData & getFirst ( ) const {
		return first;
	}

	void setFirst ( Data f ) {
		first = std::move ( f );
		first->parent = static_cast < Cast * > ( this );
	}

	Data & getSecond ( ) {
		return second;
	}

	const ConstData & getSecond ( ) const {
		return second;
	}

	void setSecond ( Data s ) {
		second = std::move ( s );
		second->parent = static_cast < Cast * > ( this );
	}

	Data & getThird ( ) {
		return third;
	}

	const ConstData & getThird ( ) const {
		return third;
	}

	void setThird ( Data t ) {
		third = std::move ( t );
		third->parent = static_cast < Cast * > ( this );
	}

};

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 < Data * > { 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 & getChildren ( ) {
		return children;
	}

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

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

	template < int N >
	void setChildren ( 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 FixedaryNode {
	std::vector < Data > children;

public:
	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 );

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

		return * this;
	}

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

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

		return * this;
	}

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