#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdint>
#include <random>
#include <limits>
#include <chrono>
#include <stdexcept>
#include <iterator>
typedef std::vector<std::uint8_t> BType;
typedef std::vector<BType> Block;

template<class T>
class GhostMemory{
	std::size_t N;
	T* P;
public:
	GhostMemory(T* Po = nullptr, std::size_t Num = 0) :N(Num),P(Po){}

	std::size_t Size(){
		return N;
	}
	const T* Pointer(){
		return P;
	}
	T& operator [](const std::size_t Idx){
		if (N <= Idx) throw std::out_of_range("OutOfRange in GhostMemory<T>::operator []");
		return P[Idx];
	}
	const T& operator [](const std::size_t Idx) const{
		if (N <= Idx) throw std::out_of_range("OutOfRange in GhostMemory<T>::operator []");
		return P[Idx];
	}
	bool operator ==(GhostMemory<T>&In){
		if (N != In.N) return false;
		for (std::size_t i = 0; i < N; i++){
			if ((*this)[i] != In[i]) return false;
		}
		return true;
	}
	/**/
	bool operator <(const GhostMemory<T>&In) const{
		if (N < In.N) return true;
		//if (N < In.N) return false;
		for (std::size_t i = 0; i < N; i++){
			if ((*this)[i] != In[i]){
				return (*this)[i]<In[i];
			}
		}
		return false;
	}
	/**/
	bool operator >(const GhostMemory<T>&In) const{
		if (N > In.N) return true;
		//if (N < In.N) return false;
		for (std::size_t i = 0; i < N; i++){
			if ((*this)[i] != In[i]){
				return (*this)[i]>In[i];
			}
		}
		return false;
	}	
	/**/
};

typedef std::vector<GhostMemory<std::uint8_t>> Block2;


BType MakeData(std::size_t N = std::numeric_limits<std::uint16_t>::max()){

	std::random_device RD;
	std::mt19937 mt(RD());
//	std::mt19937 mt(0);
	std::uniform_int_distribution<int> uid(0, 255);

	BType ret;
	for (std::size_t i = 0; i < N; i++){
		ret.push_back(uid(mt));
	}

	return ret;
}

bool Append(Block& B, BType& Data){

	B.push_back(Data);
	
	return true;
}

std::pair<std::size_t,BType> BlockSortEn(BType& Data){
	auto T = Data;
	Block B;
	BType R;
	std::size_t j = 0;
	for (std::size_t i = 0; i < T.size(); i++){
		Append(B, T);
		std::rotate(T.begin(), T.begin()+1, T.end());

	}
	std::sort(B.begin(), B.end());

	for (std::size_t i = 0; i < B.size(); i++){
		R.push_back(B[i][Data.size() - 1]);
		if (B[i] == Data) j = i;
	}

	return std::make_pair(j,R);
}
std::pair<std::size_t,BType> BlockSortEn2(BType& Data){
	auto T = Data;
	Block2 B;
	BType R;
	std::size_t j = 0;

	GhostMemory < std::uint8_t> D;

	auto bi = std::back_inserter(T);
	for (auto o : Data) bi = o;
	//bi = '\0';//debug for ascii char data.for debugger. 

	for (std::size_t i = 0; i < Data.size(); i++){
		GhostMemory<std::uint8_t> GM(static_cast<std::uint8_t*>(&T[i]), Data.size());
		B.push_back(GM);
	}
	D = B[0];
	std::sort(B.begin(), B.end());

	for (std::size_t i = 0; i < B.size(); i++){
		R.push_back(B[i][Data.size() - 1]);
		if (B[i].Pointer() == D.Pointer()) j = i;
	}

	return std::make_pair(j,R);
}
BType BlockSortDe(std::pair<std::size_t, BType>& Data){
	std::vector<std::pair<std::uint8_t,std::size_t>> T;
	BType R;
	for (std::size_t i = 0; i < Data.second.size(); i++){
		T.push_back(std::make_pair(Data.second[i], i));
	}
	std::sort(T.begin(), T.end());
	std::size_t P = Data.first;
	for (std::size_t i = 0; i < T.size(); i++){
		R.push_back(T[P].first);
		P = T[P].second;
	}

	return R;

}

bool MakeHoge(BType D){

	auto Start = std::chrono::high_resolution_clock::now();

	auto BSE = BlockSortEn2(D);
	auto BSD = BlockSortDe(BSE);

	auto End = std::chrono::high_resolution_clock::now();

	auto E = std::chrono::duration_cast<std::chrono::milliseconds>(End - Start);

	std::cout << "経過時間は" << E.count() << "msでした。"<<std::endl;
	
	std::cout << "オリジナル" << std::endl;
	for (auto& o : D) std::cout << static_cast<int>(o) << ',';
	std::cout << std::endl;
	std::cout << "復号化" << std::endl;
	for (auto& o : BSD) std::cout << static_cast<int>(o) << ',';
	std::cout << std::endl;
	std::cout << "符号化@" <<BSE.first<< std::endl;
	for (auto& o : BSE.second) std::cout << static_cast<int>(o) << ',';
	std::cout << std::endl;

	if (D == BSD){
		std::cout << "データ完全一致！" << std::endl;
	}
	else{
		std::cout << "データ完全一致しませんでした！" << std::endl;
	}

	//std::cout << "経過時間は" << E.count() << "msでした。"<<std::endl;


	return true;
}

bool GMemTest(){
	std::uint8_t S1[] = "1234567";
	std::uint8_t S3[] = "2234567";
	std::uint8_t S2[] = "123456";
	GhostMemory<std::uint8_t> G1(S1, sizeof(S1));
	GhostMemory<std::uint8_t> G2(S2, sizeof(S2));
	GhostMemory<std::uint8_t> G3(S3, sizeof(S3));

	std::vector<int> V1{ 1, 2, 3 };
	std::vector<int> V2{ 1, 2 };
	/**/
	if (V1 > V2){
		std::cout << "std::vector is Large is Greater"<<std::endl;
	}
	else{
		std::cout << "std::vector is Small is Greater"<<std::endl;
	}

	if (G1 == G1){
		std::cout << "GhostMemory::oeprator = is Work;"<<std::endl;
	}
	else{
		std::cout << "GhostMemory::oeprator = is Not Work;"<<std::endl;
	}
	if (G1 > G1){
		std::cout << "GhostMemory::oeprator > is not Work@;"<<std::endl;
	}
	else{
		std::cout << "GhostMemory::oeprator > is  Work@;"<<std::endl;
	}
	if (G1 < G1){
		std::cout << "GhostMemory::oeprator < is not Work@;"<<std::endl;
	}
	else{
		std::cout << "GhostMemory::oeprator < is Work@;"<<std::endl;
	}
	if (G1 > G2){
		std::cout << "GhostMemory::oeprator > is Work;"<<std::endl;
	}
	else{
		std::cout << "GhostMemory::oeprator > is Not Work;"<<std::endl;
	}
	if (G1 < G2){
		std::cout << "GhostMemory::oeprator < is not Work;"<<std::endl;
	}
	else{
		std::cout << "GhostMemory::oeprator < is Work;"<<std::endl;
	}
	if (G1 > G3){
		std::cout << "GhostMemory::oeprator > is Not Work@2;"<<std::endl;
	}
	else{
		std::cout << "GhostMemory::oeprator > is Work@2;"<<std::endl;
	}
	if (G1 < G3){
		std::cout << "GhostMemory::oeprator < is Work@2;"<<std::endl;
	}
	else{
		std::cout << "GhostMemory::oeprator < is Not Work@2;"<<std::endl;
	}
	/**/
	return true;
}


int main(){
	static const std::size_t L = 1024*6;
	auto D = MakeData(L);
	BType A{ 'A', 'B', 'B', 'A', 'C' };	//サンプルA
	BType B{ 'a','e','a','d','a','c','a','b' };//サンプルB
	/* */
	MakeHoge(A);
	std::cout << std::endl;
	MakeHoge(B);
	std::cout << std::endl;
	MakeHoge(D);
	std::cout << std::endl;
	/* * /

	GMemTest();
	/* */

	return 0;
}