ExactSubtreeRepeatsFromSubtreeAutomaton.h

Go to the documentation of this file.

 
#pragma once
 
#include <common/ranked_symbol.hpp>
 
#include <tree/ranked/PrefixRankedTree.h>
#include <arbology/exact/ExactSubtreeAutomaton.h>
#include <automaton/determinize/Determinize.h>
 
namespace arbology {
 
namespace properties {
 
class ExactSubtreeRepeatsFromSubtreeAutomaton {
    template < class SymbolType >
    static void repeatsInternal ( const tree::PrefixRankedTree < SymbolType > & originalTree, const automaton::InputDrivenDPDA < common::ranked_symbol < SymbolType >, char, ext::set < unsigned > > & automaton, ext::vector < common::ranked_symbol < unsigned > > & repeats, const ext::set < unsigned > & state, unsigned size, unsigned ac );
 
public:
    template < class SymbolType >
    static tree::PrefixRankedTree < unsigned > repeats ( const tree::PrefixRankedTree < SymbolType > & tree );
 
};
 
template < class SymbolType >
void ExactSubtreeRepeatsFromSubtreeAutomaton::repeatsInternal ( const tree::PrefixRankedTree < SymbolType > & originalTree, const automaton::InputDrivenDPDA < common::ranked_symbol < SymbolType >, char, ext::set < unsigned > > & automaton, ext::vector < common::ranked_symbol < unsigned > > & repeats, const ext::set < unsigned > & state, unsigned size, unsigned ac ) {
    if ( state.empty ( ) )
        return;
 
    if ( ac == 0 )
        for ( unsigned label : state )
            repeats [ label - size ] = common::ranked_symbol < unsigned > ( * state.begin ( ) - size, originalTree.getContent ( ) [ * state.begin ( ) - size ].getRank ( ) );
    else
        for ( const std::pair < const ext::pair < ext::set < unsigned >, common::ranked_symbol < SymbolType > >, ext::set < unsigned > > & transition : automaton.getTransitionsFromState ( state ) )
            repeatsInternal ( originalTree, automaton, repeats, transition.second, size + 1, ac - 1 + transition.first.second.getRank ( ) );
}
 
template < class SymbolType >
tree::PrefixRankedTree < unsigned > ExactSubtreeRepeatsFromSubtreeAutomaton::repeats ( const tree::PrefixRankedTree < SymbolType > & tree ) {
    automaton::InputDrivenNPDA < common::ranked_symbol < SymbolType >, char, unsigned > subtreePushdownAutomaton = arbology::exact::ExactSubtreeAutomaton::construct ( tree );
    automaton::InputDrivenDPDA < common::ranked_symbol < SymbolType >, char, ext::set < unsigned > > deterministicSubtreePushdownAutomaton = automaton::determinize::Determinize::determinize ( subtreePushdownAutomaton );
    ext::vector < common::ranked_symbol < unsigned > > data ( tree.getContent ( ).size ( ), common::ranked_symbol < unsigned > ( 0, 0 ) );
    repeatsInternal ( tree, deterministicSubtreePushdownAutomaton, data, deterministicSubtreePushdownAutomaton.getInitialState ( ), 0, 1 );
    return tree::PrefixRankedTree < unsigned > ( data );
}
 
} /* namespace properties */
 
} /* namespace arbology */