blocksort

#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#include <algorithm>

int bs_enc(int len, char* input, int* index, char** bwt);
int bs_dec(int index, char* bwt, int len, char** output);

class CompEnc{
public:
  CompEnc(int len_) : len(len_){}
  bool operator()(const char* a, const char* b){
    int ret = memcmp((void*)a, (void*)b, len);
    return (ret < 0) ? true : false;
  }
private:
  int len;
};

class CompDec{
public:
  bool operator()(char* a, char*b){
    return (*a < *b);
  }
};

int main(int argc, char *argv[]){
  if (argc < 2)
    return 1;

  char* input = argv[1];
  size_t len = strlen(input);
  if (len <= 0)
    return 1;

  printf("input = %s\n", input);

  int index;
  char* bwt = (char*)malloc(len);
  if (bs_enc(len, input, &index, &bwt))
    return 1;

  printf("BWT : \"%.*s\": %d\n", len, bwt, index);  

  char* output = (char*)malloc(len);
  if (bs_dec(index, bwt, len, &output))
    return 1;

  printf("output : %.*s\n", len, output); 

  if(memcmp(input, output, len)){
    printf("F \n%.*s\n%.*s\n", len, input, len, output);
  } else {
    printf("T \n");
  }
  free(bwt);
  free(output);
  return 0;
}

int bs_enc(int len, char* input, int* index, char** bwt){
  char* cm = (char*)malloc(len*2-1);
  char** bs = (char**)malloc(len*sizeof(char**));
  if (!cm || !bs) return 1;

  memcpy(cm, input, len);
  memcpy(cm+len, input, len-1);
  for (int i = 0; i < len; i++){	
    *(bs+i) = cm+i;
  }

  CompEnc cmpenc(len);
  std::stable_sort(bs, bs+len, cmpenc);

  char* pp = *bwt;
  for (int i = 0; i < len; i++){
    char* p = *(bs+i);
    *(pp+i) = *(p+len-1);
  }
  for (int i = 0; i < len; i++){
    char* p = *(bs+i);
    if (!memcmp(p, input, len)){
      *index = i;
      break;
    }
  }
  free(cm);
  free(bs);
  return 0;
}

int bs_dec(int index, char* bwt, int len, char** output){
  char** bwt2 = (char**)malloc(sizeof(char**)*len);
  if (! bwt2) return 1;

  for (int i = 0; i < len; i++){
    *(bwt2+i) = bwt+i;
  }
  std::stable_sort(bwt2, bwt2+len, CompDec());
  int ii = index;
  char* po = *output;
  for (int i= 0; i < len; i++){
    char** p = bwt2+ii;
    *(po+i) = **p;
    ii = *p-bwt;
  }
  free(bwt2);
  return 0;
}