forward_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 <extensions/iterator.hpp>
 
#include "deque.hpp"
#include "vector.hpp"
#include "tree_base.hpp"
 
namespace ext {
 
template < class T >
class forward_tree {
    T m_data;
 
    ext::vector < forward_tree > m_children;
 
public:
    T & getData ( ) {
        return m_data;
    }
 
    const T & getData ( ) const {
        return m_data;
    }
 
    ext::vector < forward_tree > & getChildren ( ) {
        return m_children;
    }
 
    const ext::vector < forward_tree > & getChildren ( ) const {
        return m_children;
    }
 
    typedef typename ext::vector < forward_tree >::const_iterator const_children_iterator;
 
    typedef typename ext::vector < forward_tree >::iterator children_iterator;
 
    class const_structure_iterator {
        const forward_tree * node;
 
        typename ext::deque < const forward_tree * > parents;
 
        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 forward_tree * n ) : node ( n ), parents ( ), virtual_node ( false ), isEnd ( false ) {
        }
 
        const_structure_iterator & operator ++( ) {
            if ( virtual_node ) {
                ++node;
                if ( parents.size ( ) ) {
                    const forward_tree * parent = parents.back ( );
 
                    if ( std::distance ( & * parent->getChildren ( ).begin ( ), node ) == std::distance ( parent->getChildren ( ).begin ( ), parent->getChildren ( ).end ( ) ) ) { // just a way to detect node == end_of_children
                        parents.pop_back();
                        node = parent;
                    } else {
                        virtual_node = false;
                    }
                } else {
                    virtual_node = false;
                    isEnd = true;
                }
            } else {
                if ( ! node->getChildren ( ).empty ( ) ) {
                    parents.push_back ( node );
                    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 ( ) ) {
                    parents.push_back ( node );
                    node = & * -- node->getChildren ( ).end ( );
                } else {
                    virtual_node = false;
                }
            } else {
                if ( parents.size ( ) ) {
                    const forward_tree * parent = parents.back ( );
 
                    if ( node == & * parent->getChildren ( ).begin ( ) ) {
                        parents.pop_back();
                        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 parents.size ( );
        }
 
        bool getVirtual ( ) const {
            return virtual_node;
        }
 
        template < class F >
        friend class forward_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 forward_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 forward_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 forward_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 forward_tree;
    };
 
// ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 
private:
    template < typename Iterator >
    ext::vector < forward_tree > fromIterator ( Iterator begin, Iterator end ) {
        ext::vector < forward_tree > res;
 
        for ( ; begin != end; ++begin )
            res.push_back ( forward_tree ( * begin, { } ) );
 
        return res;
    }
 
public:
    const_children_iterator insert ( const_children_iterator position, forward_tree < T > && value ) {
        ext::vector < forward_tree > & children = const_cast < ext::vector < forward_tree > & > ( getChildren ( ) );
 
        return children.insert ( position, std::move ( value ) );
    }
 
    const_children_iterator insert ( const_children_iterator position, const forward_tree < T > & value ) {
        return insert ( position, forward_tree < T > ( value ) );
    }
 
    const_children_iterator insert ( const_children_iterator position, const_children_iterator begin, const_children_iterator end ) {
        ext::vector < forward_tree > & children = const_cast < ext::vector < forward_tree > & > ( getChildren ( ) );
 
        return children.insert ( position, begin, end );
    }
 
    template < class Iterator >
    const_children_iterator insert ( const_children_iterator position, Iterator begin, Iterator end ) {
        ext::vector < forward_tree > children = fromIterator ( begin, end );
 
        return insert ( position, children.cbegin ( ), children.cend ( ) );
    }
 
// ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 
    forward_tree ( T && data, ext::vector < forward_tree > && children ) : m_data ( std::move ( data ) ), m_children ( std::move ( children ) ) {
    }
 
    forward_tree ( const T & data, const ext::vector < forward_tree > & subtrees ) : forward_tree ( T ( data ), ext::vector < forward_tree > ( subtrees ) ) {
    }
 
    template < typename ... Types >
    forward_tree ( const T & data, Types ... subtrees ) : forward_tree ( data, ext::vector < forward_tree > { subtrees ... } ) {
    }
 
    template < typename ... Types >
    forward_tree ( T && data, Types ... subtrees ) : forward_tree ( std::move ( data ), ext::vector < forward_tree > { subtrees ... } ) {
    }
 
    template < typename Iterator >
    forward_tree ( const T & data, Iterator begin, Iterator end ) : forward_tree ( data, fromIterator ( begin, end ) ) {
    }
 
    forward_tree ( const T & data, const_children_iterator begin, const_children_iterator end ) : forward_tree ( data, ext::vector < forward_tree > ( begin, end ) ) {
    }
 
// ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 
    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::forward_tree < T > && value ) {
        ext::vector < forward_tree > & children = const_cast < ext::vector < forward_tree > & > ( getChildren ( ) );
 
        children.push_back ( std::move ( value ) );
    }
 
    void push_back ( const ext::forward_tree < T > & value ) {
        push_back ( forward_tree ( value ) );
    }
 
    void push_back ( T && value ) {
        push_back ( forward_tree ( std::move ( value ) ) );
    }
 
    void push_back ( const T & value ) {
        push_back ( T ( value ) );
    }
 
// ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 
    children_iterator erase ( const_children_iterator position ) {
        ext::vector < forward_tree > & children = const_cast < ext::vector < forward_tree > & > ( getChildren ( ) );
 
        return 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 forward_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 ) {
        forward_tree * node = this;
 
        for ( size_t index : indexes ) {
            node = & node->getChildren ( )[index];
        }
 
        return node->getData ( );
    }
 
// ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 
    friend void swap ( forward_tree & first, forward_tree & second ) {
        using std::swap;
 
        swap ( first.m_data, second.m_data );
        swap ( first.m_children, second.m_children );
    }
 
// ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 
    bool operator ==( const forward_tree & other ) const {
        return std::equal ( this->prefix_begin ( ), this->prefix_end ( ), other.prefix_begin ( ), other.prefix_end ( ) );
    }
 
    auto operator <=> ( const forward_tree & other ) const {
        return std::lexicographical_compare_three_way ( this->prefix_begin ( ), this->prefix_end ( ), other.prefix_begin ( ), other.prefix_end ( ) );
    }
 
// ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 
    std::ostream & nicePrint ( std::ostream & os ) const {
        nicePrint ( os, "", true );
        return os;
    }
 
private:
    void nicePrint ( std::ostream & os, std::string prefix, 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 >
std::ostream & operator <<( std::ostream & out, const forward_tree < T > & t ) {
    out << "[";
 
    size_t level = 0;
 
    for ( typename forward_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 */