ExactSubtreeRepeatsNaive.h

Go to the documentation of this file.

 
#pragma once
 
#include <alib/map>
#include <alib/vector>
#include <alib/tree>
#include <common/ranked_symbol.hpp>
 
#include "SubtreeJumpTable.h"
 
#include <tree/ranked/RankedTree.h>
#include <tree/ranked/PrefixRankedTree.h>
#include <tree/ranked/PostfixRankedTree.h>
#include <tree/ranked/PrefixRankedBarTree.h>
#include <global/GlobalData.h>
 
namespace tree {
 
namespace properties {
 
class ExactSubtreeRepeatsNaive {
    template < class SymbolType >
    static ext::tree < common::ranked_symbol < unsigned > > repeats ( const ext::tree < common::ranked_symbol < SymbolType > > & node, ext::map < std::pair < common::ranked_symbol < SymbolType >, ext::vector < common::ranked_symbol < unsigned > > >, unsigned > & data, unsigned & minId );
    template < class SymbolType >
    static common::ranked_symbol < unsigned > repeatsPrefixRanked ( const ext::vector < common::ranked_symbol < SymbolType > > & symbols, ext::vector < common::ranked_symbol < unsigned > > & res, ext::map < std::pair < common::ranked_symbol < SymbolType >, ext::vector < common::ranked_symbol < unsigned > > >, unsigned > & data, unsigned & minId, int & index );
    template < class SymbolType >
    static common::ranked_symbol < unsigned > repeatsPostfixRanked ( const ext::vector < common::ranked_symbol < SymbolType > > & symbols, ext::vector < common::ranked_symbol < unsigned > > & res, ext::map < std::pair < common::ranked_symbol < SymbolType >, ext::vector < common::ranked_symbol < unsigned > > >, unsigned > & data, unsigned & minId, int & index );
    template < class SymbolType >
    static common::ranked_symbol < unsigned > repeatsPrefixRankedBar ( const ext::vector < common::ranked_symbol < SymbolType > > & symbols, ext::vector < common::ranked_symbol < unsigned > > & res, ext::map < std::pair < common::ranked_symbol <SymbolType >, ext::vector < common::ranked_symbol < unsigned > > >, unsigned > & data, unsigned & minId, unsigned barId, int & index );
 
public:
    template < class SymbolType >
    static tree::RankedTree < unsigned > repeats ( const tree::RankedTree < SymbolType > & tree );
    template < class SymbolType >
    static tree::PrefixRankedTree < unsigned > repeats ( const tree::PrefixRankedTree < SymbolType > & tree );
    template < class SymbolType >
    static tree::PostfixRankedTree < unsigned > repeats ( const tree::PostfixRankedTree < SymbolType > & tree );
    template < class SymbolType >
    static tree::PrefixRankedBarTree < unsigned > repeats ( const tree::PrefixRankedBarTree < SymbolType > & tree );
 
};
 
template < class SymbolType >
ext::tree < common::ranked_symbol < unsigned > > ExactSubtreeRepeatsNaive::repeats ( const ext::tree < common::ranked_symbol < SymbolType > > & node, ext::map < std::pair < common::ranked_symbol < SymbolType >, ext::vector < common::ranked_symbol < unsigned > > >, unsigned > & data, unsigned & minId ) {
    ext::vector < ext::tree < common::ranked_symbol < unsigned > > > children;
    std::pair < common::ranked_symbol < SymbolType >, ext::vector < common::ranked_symbol < unsigned > > > childRepeatsKey ( node.getData ( ), ext::vector < common::ranked_symbol < unsigned > > ( ) );
 
    for ( const ext::tree < common::ranked_symbol < SymbolType > > & child : node.getChildren() ) {
        children.push_back ( repeats ( child, data, minId ) );
        childRepeatsKey.second.push_back ( children.back ( ).getData ( ) );
    }
 
    unsigned & uniqueRepeatId = data[childRepeatsKey];
 
    if ( uniqueRepeatId == 0 ) uniqueRepeatId = minId++;
 
    return ext::tree < common::ranked_symbol < unsigned > > ( common::ranked_symbol < unsigned > ( uniqueRepeatId, node.getData ( ).getRank ( ) ), std::move ( children ) );
}
 
template < class SymbolType >
tree::RankedTree < unsigned > ExactSubtreeRepeatsNaive::repeats ( const tree::RankedTree < SymbolType > & tree ) {
    unsigned minId = 1;
    ext::map < std::pair < common::ranked_symbol < SymbolType >, ext::vector < common::ranked_symbol < unsigned > > >, unsigned > data;
 
    return tree::RankedTree < unsigned > ( repeats ( tree.getContent ( ), data, minId ) );
}
 
template < class SymbolType >
common::ranked_symbol < unsigned > ExactSubtreeRepeatsNaive::repeatsPrefixRanked ( const ext::vector < common::ranked_symbol < SymbolType > > & symbols, ext::vector < common::ranked_symbol < unsigned > > & res, ext::map < std::pair < common::ranked_symbol < SymbolType >, ext::vector < common::ranked_symbol < unsigned > > >, unsigned > & data, unsigned & minId, int & index ) {
    int begin = index;
    std::pair < common::ranked_symbol < SymbolType >, ext::vector < common::ranked_symbol < unsigned > > > childRepeatsKey ( symbols[begin], ext::vector < common::ranked_symbol < unsigned > > ( ) );
 
    res.push_back ( common::ranked_symbol < unsigned > ( 0, symbols[begin].getRank ( ) ) );
 
    index++;
 
    for ( unsigned i = 0; i < symbols[begin].getRank ( ); ++i )
        childRepeatsKey.second.push_back ( repeatsPrefixRanked ( symbols, res, data, minId, index ) );
 
    unsigned & uniqueRepeatId = data[childRepeatsKey];
 
    if ( uniqueRepeatId == 0 ) uniqueRepeatId = minId++;
 
    res[begin] = common::ranked_symbol < unsigned > ( uniqueRepeatId, symbols[begin].getRank ( ) );
    return res[begin];
}
 
template < class SymbolType >
tree::PrefixRankedTree < unsigned > ExactSubtreeRepeatsNaive::repeats ( const tree::PrefixRankedTree < SymbolType > & tree ) {
    unsigned minId = 1;
    int index = 0;
    ext::vector < common::ranked_symbol < unsigned > > res;
    ext::map < std::pair < common::ranked_symbol < SymbolType >, ext::vector < common::ranked_symbol < unsigned > > >, unsigned > data;
 
    repeatsPrefixRanked ( tree.getContent ( ), res, data, minId, index );
    return tree::PrefixRankedTree < unsigned > ( std::move ( res ) );
}
 
template < class SymbolType >
common::ranked_symbol < unsigned > ExactSubtreeRepeatsNaive::repeatsPostfixRanked ( const ext::vector < common::ranked_symbol < SymbolType > > & symbols, ext::vector < common::ranked_symbol < unsigned > > & res, ext::map < std::pair < common::ranked_symbol < SymbolType >, ext::vector < common::ranked_symbol < unsigned > > >, unsigned > & data, unsigned & minId, int & index ) {
    int begin = index;
 
    std::pair < common::ranked_symbol < SymbolType >, ext::vector < common::ranked_symbol < unsigned > > > childRepeatsKey ( symbols[begin], ext::vector < common::ranked_symbol < unsigned > > ( ) );
    res.insert ( res.begin ( ), common::ranked_symbol < unsigned > ( 0, symbols[begin].getRank ( ) ) );
 
    index--;
 
    for ( unsigned i = symbols.size ( ) - 1; i > symbols.size ( ) - 1 - symbols[begin].getRank ( ); --i )
        childRepeatsKey.second.push_back ( repeatsPostfixRanked ( symbols, res, data, minId, index ) );
 
    unsigned & uniqueRepeatId = data[childRepeatsKey];
 
    if ( uniqueRepeatId == 0 ) uniqueRepeatId = minId++;
 
    unsigned pos_in_res = begin - symbols.size ( ) + res.size ( );
    res[pos_in_res] = common::ranked_symbol < unsigned > ( uniqueRepeatId, symbols[begin].getRank ( ) );
    return res[pos_in_res];
}
 
template < class SymbolType >
tree::PostfixRankedTree < unsigned > ExactSubtreeRepeatsNaive::repeats ( const tree::PostfixRankedTree < SymbolType > & tree ) {
    unsigned minId = 1;
    int index = tree.getContent ( ).size ( ) - 1;
 
    ext::vector < common::ranked_symbol < unsigned > > res;
    ext::map < std::pair < common::ranked_symbol < SymbolType >, ext::vector < common::ranked_symbol < unsigned > > >, unsigned > data;
 
    repeatsPostfixRanked ( tree.getContent ( ), res, data, minId, index );
    return tree::PostfixRankedTree < unsigned > ( std::move ( res ) );
}
 
 
template < class SymbolType >
common::ranked_symbol < unsigned > ExactSubtreeRepeatsNaive::repeatsPrefixRankedBar ( const ext::vector < common::ranked_symbol < SymbolType > > & symbols, ext::vector < common::ranked_symbol < unsigned > > & res, ext::map < std::pair < common::ranked_symbol < SymbolType >, ext::vector < common::ranked_symbol < unsigned > > >, unsigned > & data, unsigned & minId, unsigned barId, int & index ) {
    int begin = index;
    std::pair < common::ranked_symbol < SymbolType >, ext::vector < common::ranked_symbol < unsigned > > > childRepeatsKey ( symbols[begin], ext::vector < common::ranked_symbol < unsigned > > ( ) );
 
    res.push_back ( common::ranked_symbol < unsigned > ( 0, symbols[begin].getRank ( ) ) );
 
    index++;
 
    for ( unsigned i = 0; i < symbols[begin].getRank ( ); ++i )
        childRepeatsKey.second.push_back ( repeatsPrefixRankedBar ( symbols, res, data, minId, barId, index ) );
 
    unsigned & uniqueRepeatId = data[childRepeatsKey];
 
    if ( uniqueRepeatId == 0 ) uniqueRepeatId = minId++;
 
    res[begin] = common::ranked_symbol < unsigned > ( uniqueRepeatId, symbols[begin].getRank ( ) );
    res.push_back ( common::ranked_symbol < unsigned > ( 0, symbols[index].getRank ( ) ) );
    index++;
 
    return res[begin];
}
 
template < class SymbolType >
tree::PrefixRankedBarTree < unsigned > ExactSubtreeRepeatsNaive::repeats ( const tree::PrefixRankedBarTree < SymbolType > & tree ) {
    unsigned barId = 0;
    unsigned minId = barId + 1;
    int index = 0;
    ext::vector < common::ranked_symbol < unsigned > > res;
    ext::map < std::pair < common::ranked_symbol < SymbolType >, ext::vector < common::ranked_symbol < unsigned > > >, unsigned > data;
 
    repeatsPrefixRankedBar ( tree.getContent ( ), res, data, minId, barId, index );
 
    ext::set < common::ranked_symbol < unsigned > > bars;
    for ( const common::ranked_symbol < SymbolType > & bar : tree.getBars ( ) )
        bars.insert ( common::ranked_symbol < unsigned > ( barId, bar.getRank ( ) ) );
 
    return tree::PrefixRankedBarTree < unsigned > ( std::move ( bars ), std::move ( res ) );
}
 
} /* namespace properties */
 
} /* namespace tree */