tree.hpp

Go to the documentation of this file.

 
/*
 * This file is part of Algorithms library toolkit.
 * Copyright (C) 2017 Jan Travnicek (jan.travnicek@fit.cvut.cz)
 
 * Algorithms library toolkit is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 
 * Algorithms library toolkit is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 
 * You should have received a copy of the GNU General Public License
 * along with Algorithms library toolkit.  If not, see <http://www.gnu.org/licenses/>.
 */
 
#pragma once
 
#include <memory>
#include <string>
#include <compare>
#include <tuple>
 
#include <ext/ostream>
#include <ext/vector>
 
#include <extensions/iterator.hpp>
 
#include <version>
#ifndef __cpp_lib_three_way_comparison
#include <extensions/compare.hpp>
#endif
 
namespace ext {
 
template < class T >
class tree {
    T m_data;
 
    tree * m_parent;
 
    ext::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;
    }
 
    ext::vector < tree > & getChildren ( ) {
        return m_children;
    }
 
    const ext::vector < tree > & getChildren ( ) const {
        return m_children;
    }
 
    typedef typename ext::vector < tree >::const_iterator const_children_iterator;
 
    typedef typename ext::vector < tree >::iterator children_iterator;
 
    class const_structure_iterator {
        const tree * node;
 
        size_t level;
 
        bool virtual_node;
 
        bool isEnd;
 
    public:
        using difference_type = std::ptrdiff_t;
        using value_type = T;
        using pointer = const T*;
        using reference = const T&;
        using iterator_category = std::bidirectional_iterator_tag;
 
        const_structure_iterator ( const tree * n ) : node ( n ), level ( 0 ), virtual_node ( false ), isEnd ( false ) {
        }
 
        const_structure_iterator & operator ++( ) {
            if ( virtual_node ) {
                const tree * parent = node->getParent ( );
                ++node;
 
                if ( parent != nullptr ) {
                    if ( std::distance ( & * parent->getChildren ( ).begin ( ), node ) == std::distance ( parent->getChildren ( ).begin ( ), parent->getChildren ( ).end ( ) ) ) { // just a way to detect node == end_of_children
                        --level;
                        node = parent;
                    } else {
                        virtual_node = false;
                    }
                } else {
                    virtual_node = false;
                    isEnd = true;
                }
            } else {
                if ( ! node->getChildren ( ).empty ( ) ) {
                    ++level;
                    node = & * node->getChildren ( ).begin ( );
                } 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 ) {
                if ( ! node->getChildren ( ).empty ( ) ) {
                    ++level;
 
                    node = & * -- node->getChildren ( ).end ( );
                } else {
                    virtual_node = false;
                }
            } else {
                const tree * parent = node->getParent ( );
 
                if ( parent != nullptr ) {
                    if ( node == & * parent->getChildren ( ).begin ( ) ) {
                        --level;
                        node = 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 ) const {
            return node == other.node && virtual_node == other.virtual_node;
        }
 
        bool operator !=( const const_structure_iterator & other ) const {
            return !( * this == other );
        }
 
        const T & operator *( ) const {
            return node->getData ( );
        }
 
        const T * operator ->( ) const {
            return & node->getData ( );
        }
 
        size_t getLevel ( ) const {
            return level;
        }
 
        bool getVirtual ( ) const {
            return virtual_node;
        }
 
        template < class F >
        friend class tree;
    };
 
    class const_prefix_iterator {
        const_structure_iterator node;
 
    public:
        using difference_type = std::ptrdiff_t;
        using value_type = T;
        using pointer = const T*;
        using reference = const T&;
        using iterator_category = std::bidirectional_iterator_tag;
 
        const_prefix_iterator ( const tree * n ) : node ( n ) {
        }
 
        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 ) const {
            return node == other.node;
        }
 
        bool operator !=( const const_prefix_iterator & other ) const {
            return !( * this == other );
        }
 
        const T & operator *( ) const {
            return * node;
        }
 
        const T * operator ->( ) const {
            return & node->getData ( );
        }
 
        size_t getLevel ( ) const {
            return node.getLevel ( );
        }
 
        template < class F >
        friend class tree;
    };
 
    class const_postfix_iterator {
        const_structure_iterator node;
 
    public:
        using difference_type = std::ptrdiff_t;
        using value_type = T;
        using pointer = const T*;
        using reference = const T&;
        using iterator_category = std::bidirectional_iterator_tag;
 
        const_postfix_iterator ( const tree * n ) : node ( n ) {
        }
 
        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 ) const {
            return node == other.node;
        }
 
        bool operator !=( const const_postfix_iterator & other ) const {
            return !( * this == other );
        }
 
        const T & operator *( ) const {
            return * node;
        }
 
        const T * operator ->( ) const {
            return & node->getData ( );
        }
 
        size_t getLevel ( ) const {
            return node.getLevel ( );
        }
 
        template < class F >
        friend class tree;
    };
 
// ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 
private:
    template < class Iterator >
    ext::vector < tree > fromIterator ( Iterator begin, Iterator end ) {
        ext::vector < tree > res;
 
        for ( ; begin != end; ++begin )
            res.push_back ( tree ( * begin, { } ) );
 
        return res;
    }
 
public:
    const_children_iterator insert ( const_children_iterator position, tree < T > && value ) {
        value.m_parent = this;
        return m_children.insert ( position, std::move ( value ) );
    }
 
    const_children_iterator insert ( const_children_iterator position, const tree < T > & value ) {
        return insert ( position, tree < T > ( value ) );
    }
 
    const_children_iterator insert ( const_children_iterator position, const_children_iterator begin, const_children_iterator end ) {
        typename ext::vector < tree >::iterator iter = m_children.insert ( position, begin, end );
 
        for ( typename ext::vector < tree >::iterator iterCopy = iter; begin != end; ++begin, ++iterCopy )
            iterCopy->m_parent = this;
 
        return iter;
    }
 
    template < class Iterator >
    const_children_iterator insert ( const_children_iterator position, Iterator begin, Iterator end ) {
        ext::vector < tree > children = fromIterator ( begin, end );
 
        return insert ( position, children.cbegin ( ), children.cend ( ) );
    }
 
// ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 
public:
    tree ( T && data, ext::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 ext::vector < tree > & subtrees ) : tree ( T ( data ), ext::vector < tree > ( subtrees ) ) {
    }
 
    template < typename ... Types >
    tree ( const T & data, Types ... subtrees ) : tree ( data, ext::vector < tree > { subtrees ... } ) {
    }
 
    template < typename ... Types >
    tree ( T && data, Types ... subtrees ) : tree ( std::move ( data ), ext::vector < tree > { subtrees ... } ) {
    }
 
    template < typename Iterator >
    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, ext::vector < tree > ( begin, end ) ) {
    }
 
    ~tree ( ) noexcept = default;
 
    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 ) {
        * this = tree ( node );
        return * this;
    }
 
    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 begin ( ) const {
        return m_children.begin ( );
    }
 
    children_iterator begin ( ) {
        return m_children.begin ( );
    }
 
    const_children_iterator end ( ) const {
        return m_children.end ( );
    }
 
    children_iterator end ( ) {
        return m_children.end ( );
    }
 
// ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 
    const_prefix_iterator prefix_begin ( ) const {
        return const_prefix_iterator ( this );
    }
 
    const_prefix_iterator prefix_end ( ) const {
        const_prefix_iterator res ( this + 1 );
 
        res.node.isEnd = true;
        return res;
    }
 
// ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 
    const_postfix_iterator postfix_begin ( ) const {
        const_postfix_iterator res ( this );
 
        while ( ! res.node.getVirtual ( ) ) ++res.node;
 
        return res;
    }
 
    const_postfix_iterator postfix_end ( ) const {
        const_postfix_iterator res ( this + 1 );
 
        res.node.isEnd = true;
        return res;
    }
 
// ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 
    const_structure_iterator structure_begin ( ) const {
        return const_structure_iterator ( this );
    }
 
    const_structure_iterator structure_end ( ) const {
        const_structure_iterator res ( this + 1 );
 
        res.isEnd = true;
        return res;
    }
 
// ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 
    void push_back ( ext::tree < T > && value ) {
        m_children.push_back ( std::move ( value ) );
        m_children.back ( ).m_parent = this;
    }
 
    void push_back ( const ext::tree < T > & value ) {
        push_back ( tree ( value ) );
    }
 
    void push_back ( T && value ) {
        push_back ( tree ( std::move ( value ) ) );
    }
 
    void push_back ( const T & value ) {
        push_back ( T ( value ) );
    }
 
// ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 
    children_iterator erase ( const_children_iterator position ) {
        return m_children.erase ( position );
    }
 
// ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 
    template < class ... Indexes >
    const T & operator ()( Indexes ... indexes ) const {
        return this->operator ()( { static_cast < size_t > ( indexes ) ... } );
    }
 
    const T & operator ()( std::initializer_list < size_t > indexes ) const {
        const tree * node = this;
 
        for ( size_t index : indexes ) {
            node = & node->getChildren ( )[index];
        }
 
        return node->getData ( );
    }
 
    template < class ... Indexes >
    T & operator ()( Indexes ... indexes ) {
        return this->operator ()( { static_cast < size_t > ( indexes ) ... } );
    }
 
    T & operator ()( std::initializer_list < size_t > indexes ) {
        tree * node = this;
 
        for ( size_t 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 ( first.m_data, second.m_data );
        swap ( first.m_children, second.m_children );
        for ( tree & child : first.m_children )
            child.m_parent = & first;
        for ( tree & child : second.m_children )
            child.m_parent = & second;
    }
 
// ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 
    bool operator ==( const tree & other ) const {
        return std::tie ( this->getData ( ), this->getChildren ( ) ) == std::tie ( other.getData ( ), other.getChildren ( ) );
    }
 
    auto operator <=> ( const tree & other ) const -> decltype ( std::declval < T > ( ) <=> std::declval < T > ( ) ) {
        return std::tie ( this->getData ( ), this->getChildren ( ) ) <=> std::tie ( other.getData ( ), other.getChildren ( ) );
    }
 
// ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 
    ext::ostream & nicePrint ( ext::ostream & os ) const {
        nicePrint ( os, "", true );
        return os;
    }
 
private:
    void nicePrint ( ext::ostream & os, std::string prefix, const bool last ) const {
        os << prefix;
 
        if ( last ) {
            os << "\\-";
            prefix += "  ";
        } else {
            os << "|-";
            prefix += "| ";
        }
 
        os << getData ( ) << std::endl;
 
        for ( size_t i = 0; i < m_children.size ( ); ++i ) {
            os << prefix << "|" << std::endl;
            m_children[i].nicePrint ( os, prefix, i == m_children.size ( ) - 1 );
        }
    }
 
};
 
template < class T >
ext::ostream & operator <<( ext::ostream & out, const tree < T > & t ) {
    out << "[";
 
    size_t 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;
}
 
} /* namespace ext */