SubtreeJumpTable.h

Go to the documentation of this file.

 
#pragma once
 
#include <alib/vector>
 
#include <tree/ranked/PrefixRankedTree.h>
#include <tree/ranked/PrefixRankedPattern.h>
#include <tree/ranked/PrefixRankedExtendedPattern.h>
#include <tree/ranked/PrefixRankedNonlinearPattern.h>
#include <tree/ranked/PrefixRankedBarTree.h>
#include <tree/ranked/PrefixRankedBarPattern.h>
#include <tree/ranked/PrefixRankedBarNonlinearPattern.h>
 
namespace tree {
 
namespace properties {
 
class SubtreeJumpTable {
    template < class T >
    static int buildDataPointersBar ( ext::vector < int > & res, const ext::vector < T > & content, const ext::set < T > & bars, int begin );
    template < class T >
    static int buildDataPointersPrefixRanked ( ext::vector < int > & res, const ext::vector < T > & content, int begin );
    template < class T >
    static int buildDataPointersPrefixRankedInternal ( ext::vector < int > & res, const ext::vector < T > & content, int begin );
 
public:
    template < class SymbolType >
    static ext::vector < int > compute ( const tree::PrefixRankedBarTree < SymbolType > & subject );
    template < class SymbolType >
    static ext::vector < int > compute ( const tree::PrefixRankedBarPattern < SymbolType > & pattern );
    template < class SymbolType >
    static ext::vector < int > compute ( const tree::PrefixRankedBarNonlinearPattern < SymbolType > & pattern );
    template < class SymbolType >
    static ext::vector < int > compute ( const tree::PrefixRankedTree < SymbolType > & subject );
    template < class SymbolType >
    static ext::vector < int > compute ( const tree::PrefixRankedPattern < SymbolType > & pattern );
    template < class SymbolType >
    static ext::vector < int > compute ( const tree::PrefixRankedExtendedPattern < SymbolType > & pattern );
    template < class SymbolType >
    static ext::vector < int > compute ( const tree::PrefixRankedNonlinearPattern < SymbolType > & pattern );
 
};
 
template < class SymbolType >
ext::vector < int > SubtreeJumpTable::compute ( const tree::PrefixRankedBarTree < SymbolType > & subject ) {
    ext::vector < int > res;
 
    buildDataPointersBar ( res, subject.getContent ( ), subject.getBars ( ), 0 );
 
    return res;
}
 
template < class SymbolType >
ext::vector < int > SubtreeJumpTable::compute ( const tree::PrefixRankedBarPattern < SymbolType > & pattern ) {
    ext::vector < int > res;
 
    buildDataPointersBar ( res, pattern.getContent ( ), pattern.getBars ( ), 0 );
 
    return res;
}
 
template < class SymbolType >
ext::vector < int > SubtreeJumpTable::compute ( const tree::PrefixRankedBarNonlinearPattern < SymbolType > & pattern ) {
    ext::vector < int > res;
 
    buildDataPointersBar ( res, pattern.getContent ( ), pattern.getBars ( ), 0 );
 
    return res;
}
 
template < class SymbolType >
ext::vector < int > SubtreeJumpTable::compute ( const tree::PrefixRankedTree < SymbolType > & subject ) {
    ext::vector < int > res;
 
    buildDataPointersPrefixRanked ( res, subject.getContent ( ), 0 );
 
    return res;
}
 
template < class SymbolType >
ext::vector < int > SubtreeJumpTable::compute ( const tree::PrefixRankedPattern < SymbolType > & pattern ) {
    ext::vector < int > res;
 
    buildDataPointersPrefixRanked ( res, pattern.getContent ( ), 0 );
 
    return res;
}
 
template < class SymbolType >
ext::vector < int > SubtreeJumpTable::compute ( const tree::PrefixRankedExtendedPattern < SymbolType > & pattern ) {
    ext::vector < int > res;
 
    buildDataPointersPrefixRanked ( res, pattern.getContent ( ), 0 );
 
    return res;
}
 
template < class SymbolType >
ext::vector < int > SubtreeJumpTable::compute ( const tree::PrefixRankedNonlinearPattern < SymbolType > & pattern ) {
    ext::vector < int > res;
 
    buildDataPointersPrefixRanked ( res, pattern.getContent ( ), 0 );
 
    return res;
}
 
template < class T >
int SubtreeJumpTable::buildDataPointersBar ( ext::vector < int > & res, const ext::vector < T > & content, const ext::set < T > & bars, int begin ) {
    res.push_back ( 0 );
    int index = begin + 1;
 
    while ( ! bars.contains ( content [ index ] ) )
        index = buildDataPointersBar ( res, content, bars, index );
 
    index++;
    res [ begin ] = index;
    res.push_back ( begin - 1 );
    return index;
}
 
template < class T >
int SubtreeJumpTable::buildDataPointersPrefixRanked ( ext::vector < int > & res, const ext::vector < T > & content, int begin ) {
    for ( size_t i = 0; i < content.size ( ); i++ )
        res.push_back ( 0 );
 
    return buildDataPointersPrefixRankedInternal ( res, content, begin );
}
 
template < class T >
int SubtreeJumpTable::buildDataPointersPrefixRankedInternal ( ext::vector < int > & res, const ext::vector < T > & content, int begin ) {
    int index = begin + 1;
 
    for ( unsigned i = 0; i < content [ begin ].getRank ( ); i++ )
        index = buildDataPointersPrefixRankedInternal ( res, content, index );
 
    res [ begin ] = index;
    return index;
}
 
} /* namespace properties */
 
} /* namespace tree */