ExactSubtreeRepeats.h

Go to the documentation of this file.

 
#pragma once
 
#include <alib/deque>
#include <alib/map>
#include <queue>
#include <stack>
#include <alib/tree>
#include <alib/tuple>
#include <alib/vector>
#include <common/ranked_symbol.hpp>
 
#include "SubtreeJumpTable.h"
 
#include <global/GlobalData.h>
#include <tree/ranked/PostfixRankedTree.h>
 
namespace tree {
 
namespace properties {
 
class ExactSubtreeRepeats {
 
    class ExactSubtreeRepeatsAux {
 
        template < class SymbolType >
        void buildMu ( const ext::vector < common::ranked_symbol < SymbolType > > & symbols );
 
        template < class SymbolType >
        void buildP ( const ext::vector < common::ranked_symbol < SymbolType > > & symbols );
 
        template < class SymbolType >
        void buildH ( const ext::vector < common::ranked_symbol < SymbolType > > & symbols );
 
        template < class SymbolType >
        void buildFC ( const ext::vector < common::ranked_symbol < SymbolType > > & symbols );
 
    public:
        template < class SymbolType > ExactSubtreeRepeatsAux ( const ext::vector < common::ranked_symbol < SymbolType > > & symbols );
        ext::vector < unsigned > mu;
        ext::vector < unsigned > P;
        ext::vector < unsigned > H;
        ext::vector < bool > FC;
        ext::vector < unsigned > T; 
        ext::vector < unsigned > TL; 
        ext::vector < std::queue < ext::pair < ext::deque < unsigned >, unsigned > > > LA; 
        ext::list < ext::pair < ext::deque < unsigned >, unsigned > > found_repeats; 
        unsigned alphabetSize; 
        unsigned treeSize; 
        unsigned sc; 
    };
 
    template < class SymbolType >
    static ext::vector < common::ranked_symbol < unsigned > > repeatsPostfixRanked ( const ext::vector < common::ranked_symbol < SymbolType > > & symbols );
 
    static void assignLevel ( ext::deque < unsigned > S, unsigned l, ExactSubtreeRepeats::ExactSubtreeRepeatsAux & aux );
 
    template < class SymbolType >
    static void partition ( ext::deque < unsigned > S, unsigned l, int ac, const ext::vector < common::ranked_symbol < SymbolType > > & symbols, ExactSubtreeRepeats::ExactSubtreeRepeatsAux & aux );
 
public:
    template < class SymbolType >
    static tree::PostfixRankedTree < unsigned > repeats ( const tree::PostfixRankedTree < SymbolType > & tree );
};
 
template < class SymbolType >
ExactSubtreeRepeats::ExactSubtreeRepeatsAux::ExactSubtreeRepeatsAux ( const ext::vector < common::ranked_symbol < SymbolType > > & symbols ) {
 
    sc = 0;
    this->treeSize = symbols.size ( );
    buildMu ( symbols );
    buildP ( symbols );
    buildH ( symbols );
    buildFC ( symbols );
    this->T = ext::vector < unsigned > ( symbols.size ( ) );
    this->TL = ext::vector < unsigned > ( symbols.size ( ) );
    this->LA = ext::vector < std::queue < ext::pair < ext::deque < unsigned >, unsigned > > > ( this->H.back ( ) + 1 );
 
    if ( common::GlobalData::verbose ) {
        common::Streams::log << "Alphabet size set to " << alphabetSize << std::endl;
        common::Streams::log << "Tree size set to     " << this->treeSize << std::endl;
        common::Streams::log << "Auxiliary structures computed ! " << std::endl;
    }
}
 
template < class SymbolType >
void ExactSubtreeRepeats::ExactSubtreeRepeatsAux::buildMu ( const ext::vector < common::ranked_symbol < SymbolType > > & symbols ) {
     // Build mapping mu_map((Symb, Rank) -> Number) and construct array mu from it
    ext::map < ext::pair < SymbolType, size_t >, unsigned > mu_map;
    this->alphabetSize = 0;
 
    for ( auto it = symbols.begin ( ); it != symbols.end ( ); it++ ) {
        auto search = mu_map.find ( ext::make_pair ( it->getSymbol ( ), it->getRank ( ) ) );
 
        if ( search == mu_map.end ( ) ) {
            mu_map.insert ( std::make_pair ( ext::make_pair ( it->getSymbol ( ), it->getRank ( ) ), this->alphabetSize ) );
            mu.push_back ( this->alphabetSize );
            this->alphabetSize += 1;
        } else {
            mu.push_back ( search->second );
        }
    }
 
     // Test mu_map
    if ( common::GlobalData::verbose ) {
        for ( auto it = mu_map.begin ( ); it != mu_map.end ( ); it++ )
            common::Streams::log << "map: " << it->first << " -> " << it->second << std::endl;
 
        common::Streams::log << "mu : ";
 
        for ( auto it : mu )
            common::Streams::log << it << " ";
 
        common::Streams::log << std::endl;
    }
}
 
template < class SymbolType >
void ExactSubtreeRepeats::ExactSubtreeRepeatsAux::buildP ( const ext::vector < common::ranked_symbol < SymbolType > > & symbols ) {
     // Build parent array
    P = ext::vector < unsigned > ( this->treeSize - 1 );
    std::stack < unsigned > RP;
 
    for ( unsigned i = 0; i < symbols.size ( ); ++i ) {
        for ( unsigned j = 0; j < symbols[i].getRank ( ); ++j ) {
            P[RP.top ( )] = i;
            RP.pop ( );
        }
 
        RP.push ( i );
    }
 
     // Test parents
    if ( common::GlobalData::verbose ) {
        common::Streams::log << " P : ";
 
        for ( unsigned parent : P )
            common::Streams::log << parent << " ";
 
        common::Streams::log << std::endl;
    }
}
 
template < class SymbolType >
void ExactSubtreeRepeats::ExactSubtreeRepeatsAux::buildH ( const ext::vector < common::ranked_symbol < SymbolType > > & symbols ) {
     // Build height array
    H = ext::vector < unsigned > ( this->treeSize );
    std::stack < unsigned > RH;
 
    for ( unsigned i = 0; i < symbols.size ( ); ++i ) {
        if ( symbols[i].getRank ( ) == 0 ) {
            RH.push ( 0 );
            H[i] = 0;
        } else {
            unsigned r = 0;
 
            for ( unsigned j = 0; j < symbols[i].getRank ( ); ++j ) {
                unsigned p = RH.top ( );
 
                if ( p > r )
                    r = p;
 
                RH.pop ( );
            }
 
            H[i] = r + 1;
            RH.push ( r + 1 );
        }
    }
 
     // Test heights
    if ( common::GlobalData::verbose ) {
        common::Streams::log << " H : ";
 
        for ( unsigned height : H )
            common::Streams::log << height << " ";
 
        common::Streams::log << std::endl;
    }
}
 
template < class SymbolType >
void ExactSubtreeRepeats::ExactSubtreeRepeatsAux::buildFC ( const ext::vector < common::ranked_symbol < SymbolType > > & symbols ) {
     // Build First child array
    FC = ext::vector < bool > ( this->treeSize - 1 );
    std::stack < unsigned > RFC;
 
    for ( unsigned i = 0; i < symbols.size ( ); ++i ) {
        if ( symbols[i].getRank ( ) == 0 ) {
            RFC.push ( i );
        } else {
            for ( unsigned j = 0; j < symbols[i].getRank ( ) - 1; ++j ) {
                unsigned r = RFC.top ( );
                RFC.pop ( );
                FC[r] = false;
            }
 
            unsigned r = RFC.top ( );
            RFC.pop ( );
            FC[r] = true;
            RFC.push ( i );
        }
    }
 
     // Test First child
    if ( common::GlobalData::verbose ) {
        common::Streams::log << "FC : ";
 
        for ( bool firstChild : FC )
            common::Streams::log << firstChild << " ";
 
        common::Streams::log << std::endl;
    }
}
 
template < class SymbolType >
void ExactSubtreeRepeats::partition ( ext::deque < unsigned > S, unsigned l, int ac, const ext::vector < common::ranked_symbol < SymbolType > > & symbols, ExactSubtreeRepeats::ExactSubtreeRepeatsAux & aux ) {
 
    std::queue < unsigned > Q1;
    std::queue < unsigned > Q2;
    std::queue < ext::tuple < ext::deque < unsigned >, unsigned, int > > Q3;
 
    ext::vector < bool > Bn ( symbols.size ( ) );
    ext::vector < bool > Bs ( aux.alphabetSize );
    ext::vector < ext::tuple < ext::deque < unsigned >, unsigned, int > > En ( symbols.size ( ) );
    ext::vector < ext::tuple < ext::deque < unsigned >, unsigned, int > > Es ( aux.alphabetSize );
 
    while ( !S.empty ( ) ) {
        unsigned i = S.front ( );
        S.pop_front ( );
        unsigned r = i + l;
 
        if ( aux.T[r] != 0 ) {
            std::get < 0 > ( En[aux.T[r]] ).push_back ( i );
 
            if ( ! Bn [ aux.T [ r ] ] ) {
                Bn[aux.T[r]] = true;
                std::get < 1 > ( En[aux.T[r]] ) = l + aux.TL[r];
                std::get < 2 > ( En[aux.T[r]] ) = ac - 1;
                Q1.push ( aux.T[r] );
            }
        } else {
            unsigned v = aux.mu[r];
            std::get < 0 > ( Es[v] ).push_back ( i );
 
            if ( ! Bs [ v ] ) {
                Bs[v] = true;
                std::get < 1 > ( Es[v] ) = l + 1;
                std::get < 2 > ( Es[v] ) = ac + symbols[r].getRank ( ) - 1;
                Q2.push ( v );
            }
        }
    }
 
    while ( !Q1.empty ( ) ) {
        unsigned k = Q1.front ( );
        Q1.pop ( );
        Q3.push ( std::move ( En[k] ) );
 
        /* The next two lines can be safely removed (Partition(), lines 23-24 in the paper)
         * The variables are local and won't be used in the function again.
         * Leaving them here to show every step of the algorithm.
         */
        /* En[k] = ext::tuple < ext::deque < unsigned >, unsigned, int > ( );
         * Bn[k] = false;
         */
    }
 
    while ( !Q2.empty ( ) ) {
        unsigned k = Q2.front ( );
        Q2.pop ( );
        Q3.push ( std::move ( Es[k] ) );
 
        /* The next two lines can be safely removed (Partition(), lines 28-29 in the paper)
         * The variables are local and won't be used in the function again.
         * Leaving them here to show every step of the algorithm.
         */
        /* Es[k] = ext::tuple < ext::deque < unsigned >, unsigned, int > ( );
         * Bs[k] = false;
         */
    }
 
    while ( !Q3.empty ( ) ) {
        ext::tie ( S, l, ac ) = std::move ( Q3.front ( ) );
        Q3.pop ( );
 
        if ( ac == 0 ) {
            if ( common::GlobalData::verbose )
                common::Streams::log << " ! Repeat : " << S << " " << l << std::endl;
 
            aux.found_repeats.push_back ( ext::make_pair ( S, l ) );
            aux.sc += 1;
 
            for ( unsigned j : S ) {
                aux.T[j] = aux.sc;
                aux.TL[j] = l;
            }
 
            ExactSubtreeRepeats::assignLevel ( std::move ( S ), l, aux );
        } else {
            ExactSubtreeRepeats::partition ( std::move ( S ), l, ac, symbols, aux );
        }
    }
}
 
template < class SymbolType >
ext::vector < common::ranked_symbol < unsigned > > ExactSubtreeRepeats::repeatsPostfixRanked ( const ext::vector < common::ranked_symbol < SymbolType > > & symbols ) {
 
    ExactSubtreeRepeats::ExactSubtreeRepeatsAux aux = ExactSubtreeRepeats::ExactSubtreeRepeatsAux ( symbols );
 
    ext::vector < ext::deque < unsigned > > As ( aux.alphabetSize );
    ext::vector < bool > Bs ( aux.alphabetSize );
    ext::vector < unsigned > Cs ( aux.alphabetSize );
    std::queue < unsigned > Q5;
 
    for ( unsigned i = 0; i < aux.treeSize; ++i ) {
        if ( symbols[i].getRank ( ) == 0 ) {
            unsigned k = aux.mu[i];
 
            if ( ! Bs[k] ) {
                Bs[k] = true;
                Q5.push ( k );
            }
 
            As[k].push_back ( i );
 
            if ( Cs[k] == 0 ) {
                aux.sc += 1;
                Cs[k] = aux.sc;
            }
 
            aux.T[i] = Cs[k];
            aux.TL[i] = 1;
        } else {
            aux.T[i] = 0;
            aux.TL[i] = 0;
        }
    }
 
     // Check As contents
    if ( common::GlobalData::verbose ) {
        common::Streams::log << "One node repeats (As): ";
 
        for ( unsigned i = 0; i < As.size ( ); ++i )
            if ( !As[i].empty ( ) )
                common::Streams::log << i << ":" << As[i] << " ";
 
        common::Streams::log << std::endl;
    }
 
    while ( !Q5.empty ( ) ) {
        unsigned k = Q5.front ( );
        Q5.pop ( );
        Bs[k] = false;
 
        if ( common::GlobalData::verbose )
            common::Streams::log << " ! Repeat : " << As[k] << " " << 1 << std::endl;
 
        aux.found_repeats.push_back ( ext::make_pair ( As[k], 1 ) );
        ExactSubtreeRepeats::assignLevel ( std::move ( As[k] ), 1, aux );
    }
 
    for ( unsigned i = 1; i <= aux.H.back ( ); i++ )
        while ( !aux.LA[i].empty ( ) ) {
            ExactSubtreeRepeats::partition ( std::move ( aux.LA[i].front ( ).first ), aux.LA[i].front ( ).second, 0, symbols, aux );
            aux.LA[i].pop ( );
        }
 
    /* Prepare result :
     * we have collected the triplets (ac part of the triplet from the paper is always 0, so implementation reduces it to pairs) at this point and
     * need to build a postfix representation of a tree from them.
     * S-repeats IDs will be used as node-labels for the root (index_from_S + l)
     * of each subtree.
     */
    ext::vector < unsigned > post_repeats ( aux.treeSize );
 
    unsigned curr_repeat = 0;
 
    for ( const auto & repeat : aux.found_repeats ) {
        for ( unsigned s : repeat.first )
            post_repeats[s + repeat.second - 1] = curr_repeat;
 
        ++ curr_repeat;
    }
 
    if ( common::GlobalData::verbose ) {
        common::Streams::log << "Repeat postfix string : ";
 
        for ( unsigned post_repeat : post_repeats )
            common::Streams::log << post_repeat << " ";
 
        common::Streams::log << std::endl;
    }
 
    ext::vector < common::ranked_symbol < unsigned > > res;
 
    for ( unsigned i = 0; i < aux.treeSize; i++ )
        res.push_back ( common::ranked_symbol < unsigned > ( post_repeats[i], symbols[i].getRank ( ) ) );
 
    return res;
}
 
template < class SymbolType >
tree::PostfixRankedTree < unsigned > ExactSubtreeRepeats::repeats ( const tree::PostfixRankedTree < SymbolType > & tree ) {
    ext::vector < common::ranked_symbol < unsigned > > res = repeatsPostfixRanked ( tree.getContent ( ) );
 
    return tree::PostfixRankedTree < unsigned > ( std::move ( res ) );
}
 
} /* namespace properties */
 
} /* namespace tree */