ApproximateEnhancedCoversComputation.h

#ifndef APPROXIMATE_ENHANCED_COVERS_COMPUTATION_H
#define APPROXIMATE_ENHANCED_COVERS_COMPUTATION_H

#include <alib/set>
#include <string/LinearString.h>

namespace stringology::cover {

struct Element {
	unsigned depth, level;
	Element ( ) = default;
	Element ( unsigned d, unsigned l ) : depth ( d ), level ( l ) { }
};

struct State {
	unsigned				depth;
	ext::vector < Element > elements;
};

class ApproximateEnhancedCoversComputation {
private:
	static unsigned distEnhCov ( State const * q );
	template < class SymbolType >
	static State * constrFirstState ( const string::LinearString < SymbolType > & x, unsigned k );
	template < class SymbolType >
	static State * constrNextState ( const string::LinearString < SymbolType > & x, State const * previousState, unsigned k );
	template < class SymbolType >
	static void updateEnhCov ( State const * state, const string::LinearString < SymbolType > & x, ext::set < string::LinearString < SymbolType > > & enhCovers, unsigned & h );

public:
	template < class SymbolType >
	static ext::set < string::LinearString < SymbolType > > compute ( const string::LinearString < SymbolType > & x, unsigned k );
};

template < class SymbolType >
ext::set < string::LinearString < SymbolType > > ApproximateEnhancedCoversComputation::compute ( const string::LinearString < SymbolType > & x, unsigned k ) {
	ext::set < string::LinearString < SymbolType > > result;
	unsigned h = 0;
	State * previousState = constrFirstState ( x, k );
	State * nextState = nullptr;

	for ( size_t i = 2; i < x.getContent ( ).size ( ); ++i ) {
		nextState = constrNextState ( x, previousState, k );

		if ( nextState->elements.size ( ) < 2 ) {
			delete nextState;
			break;
		}

		delete previousState;
		Element lastElement = nextState->elements[nextState->elements.size ( ) - 1];

		if ( ( lastElement.depth == x.getContent ( ).size ( ) ) && ( lastElement.level == 0 ) && ( nextState->depth > k ) )
			updateEnhCov ( nextState, x, result, h );

		previousState = nextState;
	}

	delete previousState;
	return result;
}

unsigned ApproximateEnhancedCoversComputation::distEnhCov ( State const * q ) {
	unsigned r = 0;
	unsigned m = q->elements[0].depth;

	for ( size_t i = 2; i < q->elements.size ( ); ++i ) {
		if ( q->elements[i].depth - q->elements[i - 1].depth < m )
			r += q->elements[i].depth - q->elements[i - 1].depth;
		else
			r += m;
	}

	return r;
}

template < class SymbolType >
State * ApproximateEnhancedCoversComputation::constrFirstState ( const string::LinearString < SymbolType > & x, unsigned k ) {
	auto * firstState = new State ( );

	firstState->depth = 1;

	for ( size_t i = 0; i < x.getContent ( ).size ( ); ++i ) {
		if ( x.getContent ( )[0] == x.getContent ( )[i] )
			firstState->elements.push_back ( Element ( i + 1, 0 ) );
		else if ( k > 0 )
			firstState->elements.push_back ( Element ( i + 1, 1 ) );
	}

	return firstState;
}

template < class SymbolType >
State * ApproximateEnhancedCoversComputation::constrNextState ( const string::LinearString < SymbolType > & x, State const * previousState, unsigned k ) {
	auto * nextState = new State ( );

	nextState->depth = previousState->depth + 1;

	for ( const auto & element : previousState->elements )
		if ( element.depth < x.getContent ( ).size ( ) ) {
			if ( x.getContent ( )[previousState->depth] == x.getContent ( )[element.depth] )
				nextState->elements.push_back ( Element ( element.depth + 1, element.level ) );
			else if ( element.level < k )
				nextState->elements.push_back ( Element ( element.depth + 1, element.level + 1 ) );
		}

	return nextState;
}

template < class SymbolType >
void ApproximateEnhancedCoversComputation::updateEnhCov ( State const * state, const string::LinearString < SymbolType > & x, ext::set < string::LinearString < SymbolType > > & enhCovers, unsigned & h ) {
	unsigned hNext = distEnhCov ( state );
	string::LinearString u ( ext::vector < SymbolType > ( x.getContent ( ).begin ( ), x.getContent ( ).begin ( ) + state->depth ) );

	if ( hNext > h ) {
		h = hNext;
		enhCovers.clear ( );
	}

	if ( hNext == h )
		enhCovers.insert ( u );
}

} /* namespace stringology::cover */
#endif /* APPROXIMATE_ENHANCED_COVERS_COMPUTATION_H */