#include <iostream>
#include <vector>
#include <cstdint>
#include <random>
#include <algorithm>
#include <map>
#include <chrono>
#include <limits>
#include <stdexcept>
//copyright@yakitori2014 AllRightsReserved
//i dont lisence for any one.
//if need to find me and ask me.

typedef std::vector<std::uint8_t> btype;
typedef std::vector<std::pair<std::uint8_t,uint64_t>> rltype;

btype MakeData(std::size_t N = 1024){

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

	btype data;

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

std::pair<std::uint64_t,btype> PermSort(btype& B,bool IsShow=false){
	btype T = B;
	std::uint64_t i=0;
	bool F = false;

	while (std::is_sorted(T.begin(), T.end())==false){
		if (std::next_permutation(T.begin(), T.end()) == false){
			if (F == true){
				std::cout << "パーミテーションに失敗" << std::endl;
				throw std::logic_error("パーテーションに失敗！！");
			}
			F = true;
		}
		i++;
		if(IsShow==true) std::cout << i << '/' << std::numeric_limits<std::uint64_t>::max() << '\r';
	}
	if(IsShow==true) std::cout << std::endl;

	return std::make_pair(i,T);
}

btype PermDeSort(btype RLD, std::uint64_t N){
	auto R = RLD;
	for (std::uint64_t i = 0; i < N; i++){
		std::prev_permutation(R.begin(), R.end());
	}
	return R;
}

rltype RunLengthComp(btype& B){
	std::uint8_t Number = B.front();
	std::uint64_t C = 0;
	rltype ret;

	for (std::size_t i = 0; i < B.size(); i++){
		if (Number == B[i]){
			C++;
		}
		else{
			ret.push_back(std::make_pair(Number, C));
			Number = B[i];
			i--;
			C = 0;

		}
	}
	ret.push_back(std::make_pair(Number, C));

	return ret;
}

btype RunLengthExt(rltype rl){
	std::uint8_t Number = rl.front().first;
	std::uint64_t C = rl.front().second;
	btype ret;
	for (std::size_t i = 0; i < rl.size(); i++){
		Number = rl[i].first;
		C = rl[i].second;
		for (std::uint64_t N = 0; N < C; N++){
			ret.push_back(Number);
		}
	}
	return ret;
}


std::pair<std::uint64_t, rltype> Encode(btype& B, bool IsCheck = false){


	auto A = PermSort(B);
	if (IsCheck == true){
		auto T = B;
		std::sort(T.begin(), T.end());
		if (A.second == T)std::cout << "ソート完了" << std::endl;
		else std::cout << "ソート失敗" << std::endl;
	}
	auto RL = RunLengthComp(A.second);

	return std::make_pair(A.first, RL);
}

btype Decode(std::pair<std::uint64_t, rltype> D){
	auto A = RunLengthExt(D.second);
	auto B = PermDeSort(A, D.first);

	return B;
}
int main(){

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

	auto D = MakeData(11);//ここを16にしてみよう。オーダーはo(N!)だ！！！！！
	auto B = D;

	std::cout <<"オリジナル:"<< std::endl;
	for (auto& o : D) std::cout << static_cast<int>(o) << ',';
	std::cout << std::endl;
	
	

	auto En = Encode(D, true);
	auto De = Decode(En);
	

	std::cout <<"デコード:"<< std::endl;
	for (auto& o : De) std::cout << static_cast<int>(o) << ',';
	std::cout << std::endl;
	for (auto& o : En.second)std::cout << static_cast<int>(o.first) << ':' << o.second << ',';
	std::cout << std::endl;
	std::cout <<"エンコード:"<< std::endl;

	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 << "ソート回数は" << En.first << "回だ！" << std::endl;

	return 0;
}