#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/mman.h>
#include <sys/stat.h>
#include <sys/types.h>
#include <unistd.h>
#include <fcntl.h>

#define DATA_FILE "../sequence.dat"
#define INDEX_FILE "sequence.vbsi"
#define KEY_LEN 11
#define DICT_SIZE 4194304
#define KEY_MASK  4194303  /* 4**11 -1 */
#define MAX_LIST_LEN 3000
#define LIST_NO_RECORD 0xFFFFFFFF
#define VERSION 0x01010100

typedef struct {     // Ячейка словаря
  u_int32_t count;   // Количество вхождений ключа
  u_int32_t point;   // Первый элемент в списке или позиция вхождения
} dictCell;
typedef struct {     // Заголовок индексного файла
  int version;       // Версия
  int dictSize;      // Размер словаря
  int NlistSize;     // Размер секции Nlist
  int keyLen;        // Длина ключа
} indexHeader;
void error(const char *);
int Index(dictCell *dict,unsigned char *src,int srcLen,void *,int);

int main() {
  struct stat statbuf;
  indexHeader header;
  int fdin,fdout,srcLen;
  unsigned char *src;
  dictCell *dict;
  void *listData;
  if ( (fdin = open(DATA_FILE, O_RDONLY)) < 0 )
    error("Error opening data file");
  if ( (fdout = open(INDEX_FILE, O_RDWR | O_CREAT | O_TRUNC, S_IRUSR | S_IWUSR | S_IRGRP | S_IROTH)) < 0 )
    error("Error opening index file for writing");
  if ( fstat(fdin, &statbuf) < 0 )
    error("fstat error");
  srcLen=statbuf.st_size;
  if ( (src = mmap(0, srcLen, PROT_READ, MAP_SHARED, fdin, 0)) == MAP_FAILED )
    error("data file mmap error");
  dict=(dictCell *)malloc(sizeof(dictCell)*DICT_SIZE);
  if(dict==NULL) error("Memory allocation error (for dict)");
  memset(dict,0,sizeof(dictCell)*DICT_SIZE);
  int NlistCells=Index(dict,src,srcLen,NULL,0); // Первый проход, подсчет статистики
  int i,listSize=0,keyCnt=0,nIndex=0;
  for(i=0;i<DICT_SIZE;i++) {
    if(dict[i].count > 0 && dict[i].count < MAX_LIST_LEN) {
      dict[i].point=listSize;
      listSize+=dict[i].count;
      keyCnt++;
    } else if(dict[i].count >= MAX_LIST_LEN) {
      nIndex++;
      dict[i].point=LIST_NO_RECORD;
    }
    dict[i].count=0;
  }
  printf("\nNlistCells=%d srcLen=%d listSize=%d keyCnt=%d notIndexedKeys=%d\n",
         NlistCells,srcLen,listSize,keyCnt,nIndex);
  int listDataSize=sizeof(u_int32_t)*listSize+sizeof(dictCell)*NlistCells;
  listData=malloc(listDataSize);
  if(listData==NULL) error("Memory allocation error (for list)");
  Index(dict,src,srcLen,listData,NlistCells);  // Второй проход, индексация
  printf("Index complete. Writing ...\n");
  header.version=VERSION;
  header.dictSize=DICT_SIZE;
  header.keyLen=KEY_LEN;
  header.NlistSize=NlistCells;
  i=write(fdout,&header,sizeof(header));
  i=write(fdout,dict,sizeof(dictCell)*DICT_SIZE);
  i=write(fdout,listData,listDataSize);
  printf("COMPLETE\n");
}
int Index(dictCell *dict,unsigned char *src,int srcLen,void *listData,int NlistCells)
{
  int Npos=-1;
  int keyLen=0;
  int NlistCnt=0;
  dictCell *Nlist=NULL;
  int *List=NULL;
  if(listData!=NULL) {
    Nlist=(dictCell *)listData;
    List=(int *)(((char *)listData)+sizeof(dictCell)*NlistCells);
    NlistCells=0;
  }
  u_int32_t key;
  int i,flg=0;
// Подсчет количества элементов в разбивке по ключам
  for(i=0;i<srcLen;i++) {
    unsigned char ch=src[i];
    if(ch=='N') {  // Есть фиксируемая N-цепочка, считаем
      if(NlistCnt) {
        if(Nlist) Nlist[NlistCells-1].count++;
        NlistCnt++;
        continue;
      }
      if(Npos==0) {  // Предыдущий символ был N, а N-цепочка еще не начата
        if(Nlist) {
          Nlist[NlistCells].count=1;
          Nlist[NlistCells].point=i-1;
        }
        NlistCells++;
        NlistCnt++;
      }
      if(Npos>=0) {  // В ключе уже есть N. Не рассматриваем ключи с >1 N
        keyLen=0; key=0; continue;
      }
      Npos=0; key=(key<<2) & KEY_MASK; // key*=размер_алфавита
    } else {  // Встречен нормальный символ (может нужна проверка ?)
      key=((key<<2) | ((ch >> 1)&3)) & KEY_MASK;
      if(Npos>=0) Npos++;
      if(Npos>=KEY_LEN) Npos=-1;    // N ушел за пределы ключа
      NlistCnt=0;  // Цепочка N закончена, если она была
    }
    if(keyLen<KEY_LEN) {
      keyLen++;
      if(keyLen<KEY_LEN) continue;  // Формирование ключа не закончено
    }
    if(List && dict[key].point!=LIST_NO_RECORD) {
//      if(!flg) {
//        flg++;
//        printf("SaveFirst (%d) to %d+%d\n",i-KEY_LEN+1,dict[key].point,dict[key].count);
//      }
      List[ dict[key].point + dict[key].count ]=i-KEY_LEN+1;
    }
    dict[key].count++;
    if(Npos>=0) {  // В ключе есть N, надо писать другие ключи
     u_int32_t Nmask=~(3 << Npos*2);
     int j;
     for(j=1;j<=3;j++) {
       key|=j << Npos*2;
       if(List && dict[key].point!=LIST_NO_RECORD) {
         List[ dict[key].point + dict[key].count ]=i-KEY_LEN;
       }
       dict[key].count++;
       key&=Nmask;
     }
     ;
    }
  }
//  if(List) printf("List[0]=%d\n",List[0]);
  if(Nlist) {
    for(i=0;i<NlistCells;i++) {
      Nlist[i].count=Nlist[i].point+Nlist[i].count-1;
    }
  }
  return NlistCells;
}

void error(const char *msg) {
  printf("%s\n",msg);
  _exit(1);
}