PositionHeapNaive.h

Go to the documentation of this file.

 
#pragma once
 
#include <indexes/stringology/PositionHeap.h>
#include <string/LinearString.h>
#include <exception/CommonException.h>
 
namespace stringology {
 
namespace indexing {
 
class PositionHeapNaive {
public:
    template < class SymbolType >
    static indexes::stringology::PositionHeap < SymbolType > construct ( const string::LinearString < SymbolType > & w );
 
};
 
template < class SymbolType >
indexes::stringology::PositionHeap < SymbolType > PositionHeapNaive::construct ( const string::LinearString < SymbolType > & w ) {
    if ( w.getContent ( ).empty ( ) )
        throw exception::CommonException ( "Position heap can't index empty string" );
 
    ext::trie < SymbolType, unsigned > trie ( 1 );
 
    for ( unsigned i = w.getContent ( ).size ( ) - 1; i > 0; i-- ) {
        unsigned k = i - 1;
        ext::trie < SymbolType, unsigned > * n = & trie;
 
        while ( n->getChildren ( ).count ( w.getContent ( )[k] ) )
            n = & n->getChildren ( ).find ( w.getContent ( )[k++] )->second;
 
        unsigned node = w.getContent ( ).size ( ) - i + 1;
        n = & n->getChildren ( ).insert ( std::make_pair ( w.getContent ( )[k], ext::trie < SymbolType, unsigned > ( node ) ) ).first->second;
    }
 
    return indexes::stringology::PositionHeap < SymbolType > ( std::move ( trie ), string::LinearString < SymbolType > ( w ) );
}
 
} /* namespace indexing */
 
} /* namespace stringology */