NormalizeRotation.cpp

/*
 * NormalizeRotation.cpp
 *
 *  Created on: 9. 2. 2014
 *      Author: Radomir Polach
 */

#include "NormalizeRotation.h"

#include <string/CyclicString.h>

namespace string {

namespace simplify {

string::String NormalizeRotation::normalize(const string::String& string) {
	return getInstance().dispatch(string.getData());
}

string::CyclicString NormalizeRotation::normalize(const string::CyclicString& string) {
	/**
	 * Lexicographically least circular substrings
	 * Kellogg S. Booth
	 * 1979
	 */
	const std::vector<alphabet::Symbol>& data = string.getContent();
	int* f = new int[data.size() + 1]; /** Knuth–Morris–Pratt like array */
	int k = 0; /** Least circular string shift value */
	int i;
	f[0] = -1;
	for (unsigned j = 1; j < 2 * data.size(); ++j) {
		/** condition adjusted by Radomir Polach, >= is not correct */
		if (j - k > data.size()) break; 
		i = f[j - k - 1];
		while (data[j % data.size()] != data[(k + i + 1) % data.size()] && i != -1) {
			if (data[j % data.size()] < data[(k + i + 1) % data.size()]) k = j - i - 1;
			i = f[i];
		}
		if (data[j % data.size()] != data[(k + i + 1) % data.size()] && i == -1) {
			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<alphabet::Symbol> rotated;
	for (unsigned l = k; l < data.size() + k; ++l) {
		rotated.push_back(data[l % data.size()]);
	}

	return string::CyclicString { string.getAlphabet(), rotated };
}

auto NormalizeRotationCyclicString = NormalizeRotation::RegistratorWrapper<string::CyclicString, string::CyclicString>(NormalizeRotation::getInstance(), NormalizeRotation::normalize);

} /* namespace simplify */

} /* namespace string */