#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

int DICT_SIZE;
int KEY_LEN;
u_int32_t KEY_MASK;
int NlistSize;
int srcLen;

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

dictCell *dict;
NlistCell *Nlist;
int *List;
unsigned char *src;
int search(unsigned char *sline,int len);
typedef struct {     // Рабочая структура поиска
  dictCell d;        // Запись словаря
  int      offs;     // Смещение ключа в паттерне
  int      current;  // Текущая запись в списке словаря
} searchInfo;
int main() {
  struct stat statbuf;
  indexHeader *header;
  int fdin,fdin1;
//  unsigned char *sline="TTCTCTAGAGCAGACAGATCCGGGTGGAGGTGGTTTTCTTTTGCACTGGATTTTCTCTAGAGCAGAGAGATCCGGGTGGAGGTGGTTTTCTTTTGCACTGGATTTTCTCTAGAGCAGACAGATCCGGGTGGACGTGGTTTTCTTTTGCACTGGATTTTCTCTAGAGCAGACAGATCCGGGTGGAGGTGGTTTTCTTTTGCACTGGATTTTCTCTAGAGCGGACAGATCCAGGTGGGGGTGGTTTTCTTTTGCACTGGATTTTCTCTAGAGCGGACAGATCCGGGTGGGGGTGGTTTTCTTTTGCACTTGATGTTCTCTAG";
  unsigned char *sline="CAGATCCGGGTGGAGGTGGTTTTCTTTTGCACTGGATTTTCTCTAGAGCGGACAGATCCAGGTGGGGGTGGTTTTCTTTTGCACTGGATTTTCTCTAGAGCGGACAGATCCGGGTGGGGGTGGTTTTCTTTTGCACTTGATGTTCTCTAG";
//  unsigned char *sline="GGATGGCTTAATAGTGCCAATAACACAACTGCCTGCCCACTTATTAGGTAACTGAATGTAGGCTCTGTGCCCACATTTCCAGTATAGGCCAGCGGGAGCTGCCCAGTCCTGATGAGATTCTGGATGAGCCCAGGCAGTTTTTAATTTAGAAAATTTACTAAATGGGTTCTTTTCAGTGTGGTTTAGGCCCCACCAAGTAATTGTCTTTGTTGTGCTGTTGTACAACTTCTGTCCTATACAATTAAGCTTTCCTACAGGGATGATAAATTCTTTTCCTTCTCTAGCTATACAGTATTGTCCAATAATTGAGGTTTTTAGGACCCAGAAGTTGCTAACTTGGGCCTTCTGAACTGGAATTATATTAGGAGCTGGATCAGTAGGCACCAACTCTCAGGCTTCCCAAGGCCATCGGTCTCCGATAGTGGTTTCCCCGCATATATAAGATGTAACATTAAGTGAATGAGCTACATTTCCTGCTAATTGGAGAAACAAATTTTTTGTCTTTTTCGGAAGTTCTGGTGCTGGCAGATTCAGCTCCTCATAAAAGGTTTGAAACACTGGTTTGGGAGAGCGCTTGTGGACTTCCCCTCTAACTAAAATGGCAACTTGGGGGTTTAACCCTGTCCCATCGATCCCCAGGGTTACACATTCTCCCTTTTTCCAAGGAGGATCTAGGGGATTGGTAATTATTAGTTCTAGT";
  void *listData;
  char *idxData;
  if ( (fdin = open(DATA_FILE, O_RDONLY)) < 0 ) error("Error opening data file");
  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");
  if ( (fdin1 = open(INDEX_FILE, O_RDONLY)) < 0 ) error("Error opening index file");
  if ( fstat(fdin1, &statbuf) < 0 ) error("fstat1 error");
  if ( (idxData = (char *)mmap(0, statbuf.st_size, PROT_READ, MAP_SHARED, fdin1, 0)) == MAP_FAILED )
    error("index file mmap error");
  header=(indexHeader *)idxData;
  if(header->version!=VERSION) error("Index file version mismatch");
  DICT_SIZE=header->dictSize;
  KEY_LEN=header->keyLen;
  KEY_MASK=DICT_SIZE-1;
  NlistSize=header->NlistSize;
  dict= (dictCell *)(idxData+sizeof(indexHeader));
  Nlist=(NlistCell *)(idxData+sizeof(indexHeader)+sizeof(dictCell)*DICT_SIZE);
  List=(int *)(((char *)Nlist)+sizeof(NlistCell)*header->NlistSize);
  int i;
//  for(i=0;i<15000;i++) {
    search(sline,strlen(sline));
//  }
}
u_int32_t getKey(unsigned char *data) {
  u_int32_t key=0;
  int i;
  for(i=0;i<KEY_LEN;i++) {
    if(data[i]=='N') return LIST_NO_RECORD;
    key=((key<<2) | ((data[i] >> 1)&3));
  }
  return key & KEY_MASK;
}
int si_comparer(const void *a,const void *b) {
  return (*(searchInfo **)a)->d.count - (*(searchInfo **)b)->d.count;
}
#define MAX_KEYS 20
int search(unsigned char *sline,int len) {
  int i=0,k=0;
  searchInfo SI_STAT[MAX_KEYS];
  searchInfo *SI[MAX_KEYS];
  int o=srcLen+1;
  while(i<len-KEY_LEN && k<MAX_KEYS) {  // Сбор информации о ключах и статистики по ним
    if(sline[i]=='N') { i++; continue; } // Быстрый пропуск N
    u_int32_t key=getKey(sline+i);
    if(key==LIST_NO_RECORD) {
      i++; continue;
    }
    if(dict[key].count==0) {
      printf("key %06X (%11.11s): NOT FOUND\n",key,sline+i);
      return -1;
    }
    SI_STAT[k].d.count=dict[key].count;
    SI_STAT[k].d.point=dict[key].point;
    SI_STAT[k].current=0; SI_STAT[k].offs=i;
    SI[k]=&SI_STAT[k];
    if(o>List[dict[key].point]-i) o=List[dict[key].point]-i;
    printf("key %06X (%11.11s): %d o=%d\n",key,sline+i,dict[key].count,o);
    k++;
    i+=KEY_LEN;
  }
  qsort(SI,k,sizeof(searchInfo *),si_comparer);  // Сортировка списков по размеру
  int nli=0,nlm;  // Текущий и максимальный для текущего окна паттерна элемент N-листа
  int oend,endCnt=0;
  while(endCnt<2) {
    oend=o+len;
    while(nli < NlistSize && Nlist[nli].end < o) nli++; // Подгоняем N-лист к текущей позиции
//    if(nli < NlistSize && Nlist[nli].start >= o) {
//      nlm=nli;
//      while(nlm < NlistSize && Nlist[nlm].start < oend) nlm++;
//    }
    int newO=srcLen+1;
    int matchCnt=0,co;
    endCnt=0;
    printf("Search at %d nli %d nlistEnd %d\n",o,nli,Nlist[nli].end);
    for(i=0;i<10 && i<k;i++) { // Для теста обход только 3х листов
      while(SI[i]->current < SI[i]->d.count
            && List[SI[i]->d.point+SI[i]->current]-SI[i]->offs < o)
        SI[i]->current++; // Подгоняем текущий лист к текущей позиции
      if(SI[i]->current >= SI[i]->d.count) { endCnt++; continue; }
      int co=List[SI[i]->d.point+SI[i]->current]-SI[i]->offs;
      if(co==o) matchCnt++;
      else { // Смещение в текущем списке больше текущего, совпадений не найдено
//        printf("not found in %d %d;",i,Nlist[nli].start);
        if(nli>=NlistSize || Nlist[nli].start > co) { // Смещение не покрывается N-листом
          newO=co; // Искать на меньших позициях нет смысла
          break;
        }
      }
      if(newO>co) newO=co; // Ищем минимальную точку поиска на будущее
    }
    if(matchCnt>=4 || matchCnt==k-1) {
      printf("Found match of %d keys at offset %d\n",matchCnt,o);
      printf("%45.45s\n",src+o);
    }
    printf("matchCnt=%d; endCnt=%d; ",matchCnt,endCnt);
    if(o<newO) o=newO;
    else       o=o+len;
  }
}

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