#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdint>
#include <random>
#include <limits>
#include <functional>
#include <map>
typedef std::vector<std::uint8_t> BType;
typedef std::vector<BType> Block;

//have bug!

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 = 1; 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);
}

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 = 0;
	for (std::size_t i = 0; i < T.size(); i++){
		R.push_back(T[P].first);
		P = T[P].second;
	}

	if(Data.first !=0)
		std::rotate(R.begin(), R.begin() + Data.first-1 , R.end());
	return R;

}

bool MakeHoge(BType D){
	auto BSE = BlockSortEn(D);
	auto BSD = BlockSortDe(BSE);

	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;
	}

	return true;
}

int main(){
	static const std::size_t L = 32;
	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;
	return 0;
}