#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdint>
#include <random>
#include <limits>
#include <functional>
#include <map>
#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==(const 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();
}