trie.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 <iterator>
#include <string>
#include <compare>
#include <tuple>
 
#include <ext/pair>
#include <ext/map>
#include <ext/ostream>
 
namespace ext {
 
template < class Key, class Value >
class trie {
    Value m_data;
 
    trie * m_parent;
 
    ext::map < Key, trie > m_children;
 
public:
    trie * getParent ( ) {
        return m_parent;
    }
 
    const trie * getParent ( ) const {
        return m_parent;
    }
 
    Value & getData ( ) {
        return m_data;
    }
 
    const Value & getData ( ) const {
        return m_data;
    }
 
    ext::map < Key, trie > & getChildren ( ) {
        return m_children;
    }
 
    const ext::map < Key, trie > & getChildren ( ) const {
        return m_children;
    }
 
    typedef typename ext::map < Key, trie >::iterator children_iterator;
 
    typedef typename ext::map < Key, trie >::const_iterator const_children_iterator;
 
// ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 
    const_children_iterator insert ( Key key, trie < Key, Value > && value ) {
        ext::map < Key, trie > & children = const_cast < ext::map < Key, trie > & > ( getChildren ( ) );
 
        typename ext::map < Key, trie >::iterator iter = children.insert ( std::move ( key ), std::move ( value ) ).first;
        iter->second.m_parent = this;
        return iter;
    }
 
    const_children_iterator insert ( Key key, const trie < Key, Value > & value ) {
        return insert ( std::move ( key ), trie < Key, Value > ( value ) );
    }
 
    void insert ( const_children_iterator begin, const_children_iterator end ) {
        ext::map < Key, trie > & children = const_cast < ext::map < Key, trie > & > ( getChildren ( ) );
 
        for ( ; begin != end; ++begin )
            children.insert ( * begin ).first->second.m_parent = this;
    }
 
// ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 
    trie ( Value && data, ext::map < Key, trie > && children ) : m_data ( std::move ( data ) ), m_parent ( nullptr ), m_children ( std::move ( children ) ) {
        for ( std::pair < const Key, trie > & child : m_children )
            child.second.m_parent = this;
    }
 
    trie ( const Value & data, const ext::map < Key, trie > & subtries ) : trie ( Value ( data ), ext::map < Key, trie > ( subtries ) ) {
    }
 
    template < typename ... Types >
    trie ( const Value & data, Types ... subtries ) : trie ( data, ext::map < Key, trie > { subtries ... } ) {
    }
 
    template < typename ... Types >
    trie ( Value && data, Types ... subtries ) : trie ( std::move ( data ), ext::map < Key, trie > { subtries ... } ) {
    }
 
    trie ( const Value & data, const_children_iterator begin, const_children_iterator end ) : trie ( data, ext::map < Key, trie > ( begin, end ) ) {
    }
 
    ~trie ( ) noexcept = default;
 
    trie ( const trie & other ) : m_data ( other.m_data ), m_parent ( other.m_parent ), m_children ( other.m_children ) {
        for ( std::pair < const Key, trie > & child : m_children )
            child.second.m_parent = this;
    }
 
    trie ( trie && other ) noexcept : m_data ( std::move ( other.m_data ) ), m_parent ( other.m_parent ), m_children ( std::move ( other.m_children ) ) {
        for ( std::pair < const Key, trie > & child : m_children )
            child.second.m_parent = this;
    }
 
    trie & operator =( const trie & node ) {
        * this = trie ( node );
        return * this;
    }
 
    trie & operator =( trie && node ) noexcept {
        m_data = std::move ( node.m_data );
        m_children = std::move ( node.m_children );
 
        for ( std::pair < const Key, trie > & child : m_children )
            child.second.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 ( );
    }
 
// ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 
    children_iterator erase ( const_children_iterator position ) {
        ext::map < Key, trie > & children = const_cast < ext::map < Key, trie > & > ( getChildren ( ) );
 
        return children.erase ( position );
    }
 
// ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 
    template < class ... Indexes >
    const Value & operator ()( Indexes ... indexes ) const {
        return this->operator ()( { static_cast < Key > ( indexes ) ... } );
    }
 
    const Value & operator ()( std::initializer_list < Key > indexes ) const {
        const trie * node = this;
 
        for ( Key index : indexes ) {
            node = & node->getChildren ( ).find ( index )->second;
        }
 
        return node->getData ( );
    }
 
    template < class ... Indexes >
    Value & operator ()( Indexes ... indexes ) {
        return this->operator ()( { static_cast < Key > ( indexes ) ... } );
    }
 
    Value & operator ()( std::initializer_list < Key > indexes ) {
        trie * node = this;
 
        for ( Key index : indexes ) {
            node = & node->getChildren ( ).find ( index )->second;
        }
 
        return node->getData ( );
    }
 
// ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 
    bool checkStructure ( const trie & node ) const {
        bool sign = true;
 
        for ( const std::pair < const Key, trie > & child : node.getChildren ( ) )
            sign &= child.second.getParent ( ) == & node && checkStructure ( child.second );
 
        return sign;
    }
 
    bool checkStructure ( ) const {
        return m_parent == nullptr && checkStructure ( * this );
    }
 
// ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 
    friend void swap ( trie & first, trie & second ) {
        swap ( first.m_data, second.m_data );
        swap ( first.m_children, second.m_children );
        for ( trie & child : first.m_children )
            child.m_parent = & first;
        for ( trie & child : second.m_children )
            child.m_parent = & second;
    }
 
// ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 
    bool operator ==( const trie & other ) const {
        return std::tie ( this->getData ( ), this->getChildren ( ) ) == std::tie ( other.getData ( ), other.getChildren ( ) );
    }
 
    auto operator <=> ( const trie & other ) const -> std::common_comparison_category_t < decltype ( std::declval < Key > ( ) <=> std::declval < Key > ( ) ), decltype ( std::declval < Value > ( ) <=> std::declval < Value > ( ) ) > {
        return std::tie ( this->getData ( ), this->getChildren ( ) ) <=> std::tie ( other.getData ( ), other.getChildren ( ) );
    }
 
// ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 
    ext::ostream & nicePrint ( ext::ostream & os ) const {
        os << "\\-";
        std::string prefix ( "  " );
 
        os << getData ( ) << std::endl;
 
        size_t i = 0;
        for ( const std::pair < const Key, trie < Key, Value > > & subdata : getChildren ( ) ) {
            os << prefix << "|" << std::endl;
            nicePrint ( os, subdata, prefix, i == m_children.size ( ) - 1 );
            ++i;
        }
        return os;
    }
 
private:
    static void nicePrint ( ext::ostream & os, const std::pair < const Key, trie < Key, Value > > & data, std::string prefix, const bool last ) {
        os << prefix;
 
        if ( last ) {
            os << "\\-";
            prefix += "  ";
        } else {
            os << "|-";
            prefix += "| ";
        }
 
        os << data.first << ":" << data.second.getData ( ) << std::endl;
 
        size_t i = 0;
        for ( const std::pair < const Key, trie < Key, Value > > & subdata : data.second ) {
            os << prefix << "|" << std::endl;
            nicePrint ( os, subdata, prefix, i == data.second.m_children.size ( ) - 1 );
            ++i;
        }
    }
 
};
 
template < class Key, class Value >
ext::ostream & operator <<( ext::ostream & out, const trie < Key, Value > & t ) {
    out << "[";
 
    out << t.getData ( ) << ";";
 
    for ( typename ext::map < Key, trie < Key, Value > >::const_iterator iter = t.getChildren ( ).begin ( ); iter != t.getChildren ( ).end ( ); ++ iter) {
        if ( iter != t.getChildren ( ).begin ( ) ) {
            out << ",";
        }
 
        out << iter->first << ":" << iter->second;
    }
 
    out << "]";
    return out;
}
 
} /* namespace ext */