tree_base.hpp

Go to the documentation of this file.

 
#pragma once
 
#include "ptr_vector.hpp"
#include "ptr_array.hpp"
 
namespace ext {
 
template < class Data >
class BaseNode {
    Data * parent;
 
    template < class D, class C >
    friend class NullaryNode;
    template < class D, class C >
    friend class UnaryNode;
    template < class D, class C >
    friend class BinaryNode;
    template < class D, class C >
    friend class TernaryNode;
    template < class D, std::size_t I, class C >
    friend class AnyaryNode;
    template < class D, class C >
    friend class FixedaryNode;
    template < class D, class C >
    friend class VararyNode;
 
    Data * operator ->( ) {
        return static_cast < Data * > ( this );
    }
 
    const Data * operator ->( ) const {
        return static_cast < const Data * > ( this );
    }
 
public:
    BaseNode ( ) : parent ( nullptr ) {
    }
 
    virtual ~BaseNode ( ) noexcept = default;
 
    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, std::size_t arity, class Base = Data >
class AnyaryNode : public Base {
    ext::ptr_array < Data, arity > m_children;
 
    void setParents ( ) {
        for ( Data & child : m_children )
            child->parent = this;
    }
 
public:
    AnyaryNode ( ext::ptr_array < Data, arity > c ) : m_children ( std::move ( c ) ) {
        setParents ( );
    }
 
    ~AnyaryNode ( ) noexcept override = default;
 
    AnyaryNode ( const AnyaryNode & other ) : AnyaryNode ( other.m_children ) {
    }
 
    AnyaryNode ( AnyaryNode && other ) noexcept : AnyaryNode ( std::move ( other.m_children ) ) {
    }
 
    AnyaryNode & operator =( const AnyaryNode & other ) {
        if ( this == & other )
            return * this;
 
        this->m_children = other.m_children;
 
        setParents ( );
 
        return * this;
    }
 
    AnyaryNode & operator =( AnyaryNode && other ) noexcept {
        using std::swap;
 
        swap ( this->m_children, other.m_children );
 
        setParents ( );
 
        return * this;
    }
 
    const ext::ptr_array < Data, arity > & getChildren ( ) & {
        return m_children;
    }
 
    const ext::ptr_array < Data, arity > & getChildren ( ) const & {
        return m_children;
    }
 
    ext::ptr_array < Data, arity > && getChildren ( ) && {
        return std::move ( m_children );
    }
 
    template < size_t N >
    const Data & getChild ( ) const {
        return std::get < N > ( m_children );
    }
 
    template < size_t N >
    Data & getChild ( ) {
        return std::get < N > ( m_children );
    }
 
    void setChildren ( ext::ptr_array < Data, arity > c ) {
        m_children = std::move ( c );
        setParents ( );
    }
 
    template < size_t N >
    void setChild ( const Data & d ) {
        m_children.set ( m_children.cbegin ( ) + N, d );
        std::get < N > ( m_children )->parent = this;
    }
 
    template < size_t N >
    void setChild ( Data && d ) {
        m_children.set ( m_children.cbegin ( ) + N, std::move ( d ) );
        std::get < N > ( m_children )->parent = this;
    }
 
    typename ext::ptr_array < Data, arity >::iterator begin ( ) {
        return m_children.begin ( );
    }
 
    typename ext::ptr_array < Data, arity >::const_iterator begin ( ) const {
        return m_children.begin ( );
    }
 
    typename ext::ptr_array < Data, arity >::iterator end ( ) {
        return m_children.end ( );
    }
 
    typename ext::ptr_array < Data, arity >::const_iterator end ( ) const {
        return m_children.end ( );
    }
 
};
 
template < class Data, class Base = Data >
class NullaryNode : public AnyaryNode < Data, 0, Base > {
public:
    NullaryNode ( ) : AnyaryNode < Data, 0, Base > ( ext::make_ptr_array < Data > ( ) ) {
    }
 
};
 
template < class Data, class Base = Data >
class UnaryNode : public AnyaryNode < Data, 1, Base > {
public:
    UnaryNode ( const Data & c ) : AnyaryNode < Data, 1, Base > ( ext::make_ptr_array ( c ) ) {
    }
 
    UnaryNode ( Data && c ) : AnyaryNode < Data, 1, Base > ( ext::make_ptr_array ( std::move ( c ) ) ) {
    }
 
    Data & getChild ( ) {
        return this->template getChild < 0 > ( );
    }
 
    const Data & getChild ( ) const {
        return this->template getChild < 0 > ( );
    }
 
    using AnyaryNode < Data, 1, Base >::getChild;
 
    void setChild ( const Data & c ) {
        this->template setChild < 0 > ( c );
    }
 
    void setChild ( Data && c ) {
        this->template setChild < 0 > ( std::move ( c ) );
    }
 
    using AnyaryNode < Data, 1, Base >::setChild;
 
};
 
template < class Data, class Base = Data >
class BinaryNode : public AnyaryNode < Data, 2, Base > {
public:
    BinaryNode ( const Data & l, const Data & r ) : AnyaryNode < Data, 2, Base > ( ext::make_ptr_array ( l, r ) ) {
    }
 
    BinaryNode ( Data && l, Data && r ) : AnyaryNode < Data, 2, Base > ( ext::make_ptr_array ( std::move ( l ), std::move ( r ) ) ) {
    }
 
    Data & getLeft ( ) {
        return this->template getChild < 0 > ( );
    }
 
    const Data & getLeft ( ) const {
        return this->template getChild < 0 > ( );
    }
 
    void setLeft ( const Data & l ) {
        this->template setChild < 0 > ( l );
    }
 
    void setLeft ( Data && l ) {
        this->template setChild < 0 > ( std::move ( l ) );
    }
 
    Data & getRight ( ) {
        return this->template getChild < 1 > ( );
    }
 
    const Data & getRight ( ) const {
        return this->template getChild < 1 > ( );
    }
 
    void setRight ( const Data & r ) {
        this->template setChild < 1 > ( r );
    }
 
    void setRight ( Data && r ) {
        this->template setChild < 1 > ( std::move ( r ) );
    }
 
};
 
template < class Data, class Base = Data >
class TernaryNode : public AnyaryNode < Data, 3, Base > {
public:
    TernaryNode ( const Data & f, const Data & s, const Data & t ) : AnyaryNode < Data, 3, Base > ( ext::make_ptr_array ( f, s, t ) ) {
    }
 
    TernaryNode ( Data && f, Data && s, Data && t ) : AnyaryNode < Data, 3, Base > ( ext::make_ptr_array ( std::move ( f ), std::move ( s ), std::move ( t ) ) ) {
    }
 
    Data & getFirst ( ) {
        return this->template getChild < 0 > ( );
    }
 
    const Data & getFirst ( ) const {
        return this->template getChild < 0 > ( );
    }
 
    void setFirst ( const Data & f ) {
        this->template setChild < 0 > ( f );
    }
 
    void setFirst ( Data && f ) {
        this->template setChild < 0 > ( std::move ( f ) );
    }
 
    Data & getSecond ( ) {
        return this->template getChild < 1 > ( );
    }
 
    const Data & getSecond ( ) const {
        return this->template getChild < 1 > ( );
    }
 
    void setSecond ( const Data & s ) {
        this->template setChild < 1 > ( s );
    }
 
    void setSecond ( Data && s ) {
        this->template setChild < 1 > ( std::move ( s ) );
    }
 
    Data & getThird ( ) {
        return this->template getChild < 2 > ( );
    }
 
    const Data & getThird ( ) const {
        return this->template getChild < 2 > ( );
    }
 
    void setThird ( const Data & t ) {
        this->template setChild < 2 > ( t );
    }
 
    void setThird ( Data && t ) {
        this->template setChild < 2 > ( std::move ( t ) );
    }
 
};
 
template < class Data, class Base = Data >
class FixedaryNode : public Base {
    ext::ptr_vector < Data > m_children;
 
public:
    FixedaryNode ( ext::ptr_vector < Data > c ) : m_children ( std::move ( c ) ) {
        for ( Data & child : m_children )
            child.parent = this;
    }
 
    template < typename ... Types >
    FixedaryNode ( Types && ... data ) : FixedaryNode ( ext::ptr_vector < Data > ( { std::forward < Types > ( data ) ... } ) ) {
    }
 
    ~FixedaryNode ( ) noexcept override = default;
 
    FixedaryNode ( const FixedaryNode & other ) : FixedaryNode ( other.m_children ) {
    }
 
    FixedaryNode ( FixedaryNode && other ) noexcept : FixedaryNode ( std::move ( other.m_children ) ) {
    }
 
    FixedaryNode & operator =( const FixedaryNode & other ) {
        if ( this == & other )
            return * this;
 
        this->m_children = other.m_children;
 
        for ( Data & child : m_children )
            child.parent = this;
 
        return * this;
    }
 
    FixedaryNode & operator =( FixedaryNode && other ) noexcept {
        using std::swap;
 
        swap ( this->m_children, other.m_children );
 
        for ( Data & child : m_children )
            child.parent = this;
 
        return * this;
    }
 
    const ext::ptr_vector < Data > & getChildren ( ) & {
        return m_children;
    }
 
    const ext::ptr_vector < Data > & getChildren ( ) const & {
        return m_children;
    }
 
    ext::ptr_vector < Data > && getChildren ( ) && {
        return std::move ( m_children );
    }
 
    void setChildren ( ext::ptr_vector < Data > c ) {
        if ( c.size ( ) != m_children.size ( ) )
            throw "Arity != size";
 
        m_children = std::move ( c );
 
        for ( Data & child : m_children )
            child->parent = this;
    }
 
    Data & getChild ( size_t index ) {
        return m_children [ index ];
    }
 
    const Data & getChild ( size_t index ) const {
        return m_children [ index ];
    }
 
    template < class PositionIterator >
    void setChild ( Data && d, PositionIterator it ) {
        m_children.set ( it, std::move ( d ) )->parent = this;
    }
 
    template < class PositionIterator >
    void setChild ( const Data & d, PositionIterator it ) {
        m_children.set ( it, d )->parent = this;
    }
 
    void setChild ( const Data & d, size_t index ) {
        setChild ( d, m_children.begin ( ) + index );
    }
 
    void setChild ( Data && d, size_t index ) {
        setChild ( std::move ( d ), m_children.begin ( ) + index );
    }
 
    typename ext::ptr_vector < Data >::iterator begin ( ) {
        return m_children.begin ( );
    }
 
    typename ext::ptr_vector < Data >::const_iterator begin ( ) const {
        return m_children.begin ( );
    }
 
    typename ext::ptr_vector < Data >::iterator end ( ) {
        return m_children.end ( );
    }
 
    typename ext::ptr_vector < Data >::const_iterator end ( ) const {
        return m_children.end ( );
    }
 
};
 
template < class Data, class Base = Data >
class VararyNode : public Base {
    ext::ptr_vector < Data > m_children;
 
public:
    VararyNode ( ) = default;
 
    VararyNode ( ext::ptr_vector < Data > c ) : m_children ( std::move ( c ) ) {
        for ( Data & child : m_children )
            child.parent = this;
    }
 
    ~VararyNode ( ) noexcept override = default;
 
    VararyNode ( const VararyNode & other ) : VararyNode ( other.m_children ) {
    }
 
    VararyNode ( VararyNode && other ) noexcept : VararyNode ( std::move ( other.m_children ) ) {
    }
 
    VararyNode & operator =( const VararyNode & other ) {
        if ( this == & other )
            return * this;
 
        this->m_children = other.m_children;
 
        for ( Data & child : m_children )
            child.parent = this;
 
        return * this;
    }
 
    VararyNode & operator =( VararyNode && other ) noexcept {
        using std::swap;
 
        swap ( this->m_children, other.m_children );
 
        for ( Data & child : m_children )
            child.parent = this;
 
        return * this;
    }
 
    const ext::ptr_vector < Data > & getChildren ( ) & {
        return m_children;
    }
 
    const ext::ptr_vector < Data > & getChildren ( ) const & {
        return m_children;
    }
 
    ext::ptr_vector < Data > && getChildren ( ) && {
        return std::move ( m_children );
    }
 
    void setChildren ( ext::ptr_vector < Data > c ) {
        m_children = std::move ( c );
 
        for ( Data & child : m_children )
            child.parent = this;
    }
 
    Data & getChild ( size_t index ) {
        return m_children [ index ];
    }
 
    const Data & getChild ( size_t index ) const {
        return m_children [ index ];
    }
 
    template < class PositionIterator >
    void setChild ( const Data & d, PositionIterator it ) {
        m_children.set ( it, d )->parent = this;
    }
 
    template < class PositionIterator >
    void setChild ( Data && d, PositionIterator it ) {
        m_children.set ( it, std::move ( d ) )->parent = this;
    }
 
    void setChild ( const Data & d, size_t index ) {
        setChild ( d, m_children.begin ( ) + index );
    }
 
    void setChild ( Data && d, size_t index ) {
        setChild ( std::move ( d ), m_children.begin ( ) + index );
    }
 
    typename ext::ptr_vector < Data >::reverse_iterator insert ( typename ext::ptr_vector < Data >::reverse_iterator it, const Data & d ) {
        return insert ( typename ext::ptr_vector < Data >::const_reverse_iterator ( it ), d );
    }
 
    typename ext::ptr_vector < Data >::reverse_iterator insert ( typename ext::ptr_vector < Data >::const_reverse_iterator it, const Data & d ) {
        typename ext::ptr_vector < Data >::reverse_iterator iter = m_children.insert ( it, d );
 
        iter->parent = this;
 
        return iter;
    }
 
    typename ext::ptr_vector < Data >::iterator insert ( typename ext::ptr_vector < Data >::iterator it, const Data & d ) {
        return insert ( typename ext::ptr_vector < Data >::const_iterator ( it ), d );
    }
 
    typename ext::ptr_vector < Data >::iterator insert ( typename ext::ptr_vector < Data >::const_iterator it, const Data & d ) {
        typename ext::ptr_vector < Data >::iterator iter = m_children.insert ( it, d );
 
        iter->parent = this;
 
        return iter;
    }
 
    typename ext::ptr_vector < Data >::reverse_iterator insert ( typename ext::ptr_vector < Data >::reverse_iterator it, Data && d ) {
        return insert ( typename ext::ptr_vector < Data >::const_reverse_iterator ( it ), std::move ( d ) );
    }
 
    typename ext::ptr_vector < Data >::reverse_iterator insert ( typename ext::ptr_vector < Data >::const_reverse_iterator it, Data && d ) {
        typename ext::ptr_vector < Data >::reverse_iterator iter = m_children.insert ( it, std::move ( d ) );
 
        iter->parent = this;
 
        return iter;
    }
 
    typename ext::ptr_vector < Data >::iterator insert ( typename ext::ptr_vector < Data >::iterator it, Data && d ) {
        return insert ( typename ext::ptr_vector < Data >::const_iterator ( it ), std::move ( d ) );
    }
 
    typename ext::ptr_vector < Data >::iterator insert ( typename ext::ptr_vector < Data >::const_iterator it, Data && d ) {
        typename ext::ptr_vector < Data >::iterator iter = m_children.insert ( it, std::move ( d ) );
 
        iter->parent = this;
 
        return iter;
    }
 
    template < class InputIterator >
    typename ext::ptr_vector < Data >::reverse_iterator insert ( typename ext::ptr_vector < Data >::const_reverse_iterator it, InputIterator first, InputIterator last ) {
        size_t size = std::distance ( first, last );
 
        typename ext::ptr_vector < Data >::reverse_iterator iter = m_children.insert ( it, first, last );
 
        for ( size_t i = 0; i < size; ++ i ) {
            ( iter + i )->parent = this;
        }
 
        return iter;
    }
 
    template < class InputIterator >
    typename ext::ptr_vector < Data >::reverse_iterator insert ( typename ext::ptr_vector < Data >::reverse_iterator it, InputIterator first, InputIterator last ) {
        return insert ( typename ext::ptr_vector < Data >::const_reverse_iterator ( it ), first, last );
    }
 
    template < class InputIterator >
    typename ext::ptr_vector < Data >::iterator insert ( typename ext::ptr_vector < Data >::const_iterator it, InputIterator first, InputIterator last ) {
        size_t size = std::distance ( first, last );
 
        typename ext::ptr_vector < Data >::iterator iter = m_children.insert ( it, first, last );
 
        for ( size_t i = 0; i < size; ++ i ) {
            ( iter + i )->parent = this;
        }
 
        return iter;
    }
 
    template < class InputIterator >
    typename ext::ptr_vector < Data >::iterator insert ( typename ext::ptr_vector < Data >::iterator it, InputIterator first, InputIterator last ) {
        return insert ( typename ext::ptr_vector < Data >::const_iterator ( it ), first, last );
    }
 
    typename ext::ptr_vector < Data >::reverse_iterator erase ( typename ext::ptr_vector < Data >::reverse_iterator it ) {
        return m_children.erase ( typename ext::ptr_vector < Data >::const_reverse_iterator ( it ) );
    }
 
    typename ext::ptr_vector < Data >::reverse_iterator erase ( typename ext::ptr_vector < Data >::const_reverse_iterator it ) {
        return m_children.erase ( it );
    }
 
    typename ext::ptr_vector < Data >::iterator erase ( typename ext::ptr_vector < Data >::iterator it ) {
        return erase ( typename ext::ptr_vector < Data >::const_iterator ( it ) );
    }
 
    typename ext::ptr_vector < Data >::iterator erase ( typename ext::ptr_vector < Data >::const_iterator it ) {
        return m_children.erase ( it );
    }
 
    typename ext::ptr_vector < Data >::reverse_iterator erase ( typename ext::ptr_vector < Data >::reverse_iterator first, typename ext::ptr_vector < Data >::reverse_iterator last ) {
        return m_children.erase ( typename ext::ptr_vector < Data >::const_reverse_iterator ( first ), typename ext::ptr_vector < Data >::const_reverse_iterator ( last ) );
    }
 
    typename ext::ptr_vector < Data >::reverse_iterator erase ( typename ext::ptr_vector < Data >::const_reverse_iterator first, typename ext::ptr_vector < Data >::const_reverse_iterator last ) {
        return m_children.erase ( first, last );
    }
 
    typename ext::ptr_vector < Data >::iterator erase ( typename ext::ptr_vector < Data >::iterator first, typename ext::ptr_vector < Data >::iterator last ) {
        return m_children.erase ( typename ext::ptr_vector < Data >::const_iterator ( first ), typename ext::ptr_vector < Data >::const_iterator ( last ) );
    }
 
    typename ext::ptr_vector < Data >::iterator erase ( typename ext::ptr_vector < Data >::const_iterator first, typename ext::ptr_vector < Data >::const_iterator last ) {
        return m_children.erase ( first, last );
    }
 
    void clear ( ) {
        m_children.clear ( );
    }
 
    void pushBackChild ( const Data & d ) {
        m_children.push_back ( d );
        m_children [ m_children.size ( ) - 1].parent = this;
    }
 
    void pushBackChild ( Data && d ) {
        m_children.push_back ( std::move ( d ) );
        m_children [ m_children.size ( ) - 1].parent = this;
    }
 
    typename ext::ptr_vector < Data >::iterator begin ( ) {
        return m_children.begin ( );
    }
 
    typename ext::ptr_vector < Data >::const_iterator begin ( ) const {
        return m_children.begin ( );
    }
 
    typename ext::ptr_vector < Data >::reverse_iterator rbegin ( ) {
        return m_children.rbegin ( );
    }
 
    typename ext::ptr_vector < Data >::const_reverse_iterator rbegin ( ) const {
        return m_children.rbegin ( );
    }
 
    typename ext::ptr_vector < Data >::iterator end ( ) {
        return m_children.end ( );
    }
 
    typename ext::ptr_vector < Data >::const_iterator end ( ) const {
        return m_children.end ( );
    }
 
    typename ext::ptr_vector < Data >::reverse_iterator rend ( ) {
        return m_children.rend ( );
    }
 
    typename ext::ptr_vector < Data >::const_reverse_iterator rend ( ) const {
        return m_children.rend ( );
    }
 
};
 
} /* namespace ext */