NormalizeRotation.h

/*
 * 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 {

/**
 * Computes lexicographically least circular rotation,
 * based on Kellogg S. Booth 1979,
 * modified to working code by Ladislav Vagner
 */
class NormalizeRotation {
public:
	/**
	 * Computes lexicographically least circular rotation,
	 * based on Kellogg S. Booth 1979,
	 * modified to working code by Ladislav Vagner
	 *
	 * \tparam SymbolType the type of symbols in the rotated string.
	 *
	 * \param string the rotated string
	 *
	 * \return the @p string in its least lexicographical rotation
	 */
	template < class SymbolType >
	static string::CyclicString < SymbolType > normalize(const string::CyclicString < SymbolType > & string);
};

template < class SymbolType >
string::CyclicString < SymbolType > NormalizeRotation::normalize(const string::CyclicString < SymbolType > & string) {
	const ext::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 ( size_t 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;

	ext::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__ */