Newer
Older
/*
* NormalizeRotation.h
*
* Created on: 9. 2. 2014
* Author: Jan Travnicek
*/
#ifndef _NORMALIZE_ROTATION_H__
#define _NORMALIZE_ROTATION_H__
#include <string/CyclicString.h>
namespace string {
namespace simplify {
class NormalizeRotation : public alib::SingleDispatch<NormalizeRotation, string::String, const string::StringBase &> {
public:
/**
* Performs conversion.
* @return left regular grammar equivalent to source automaton.
*/
static string::String normalize(const string::String& string);
template < class SymbolType >
static string::CyclicString < SymbolType > normalize(const string::CyclicString < SymbolType > & string);
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
template < class SymbolType >
string::CyclicString < SymbolType > NormalizeRotation::normalize(const string::CyclicString < SymbolType > & string) {
/**
* Lexicographically least circular substrings,
* based on
* Kellogg S. Booth
* 1979,
* modified to working code by Ladislav Vagner
*/
const std::vector < SymbolType > & data = string.getContent ( );
int * f = new int [ 2 * data.size ( ) ]; /** Knuth–Morris–Pratt like array */
int k = 0; /** Least circular string shift value */
f [ 0 ] = -1;
for ( unsigned j = 1; j < 2 * data.size ( ); ++j ) {
int i = f [ j - k - 1 ];
while ( i != -1 && data [ j % data.size ( ) ] != data [ ( k + i + 1 ) % data.size ( ) ] ) {
if ( data [ j % data.size ( ) ] < data [ ( k + i + 1 ) % data.size ( ) ] ) k = j - i - 1;
i = f [ i ];
}
if ( i == -1 && data [ j % data.size ( ) ] != data [ k % data.size ( ) ] ) {
if ( data [ j % data.size ( ) ] < data [ ( k + i + 1 ) % data.size ( ) ] ) k = j;
f [ j - k ] = -1;
} else f [ j - k ] = i + 1;
}
delete [] f;
if(k == 0)
return string;
std::vector < SymbolType > rotated;
for ( unsigned l = k % data.size ( ); l < data.size() + k % data.size ( ); ++l ) {
rotated.push_back ( data [ l % data.size ( ) ] );
}
return string::CyclicString < > { string.getAlphabet ( ), rotated };
}
} /* namespace simplify */
} /* namespace string */
#endif /* _NORMALIZE_ROTATION_H__ */