libcds/src/static_sequence/static_sequence_bs.cpp

   1
   2 #include <static_sequence_bs.h>
   3
   4 static_sequence_bs::static_sequence_bs(uint * seq, uint n, alphabet_mapper * am, static_bitsequence_builder * bmb) {
   5         sigma = 0;
   6         len = n;
   7         this->am = am;
   8         am->use();
   9         for(uint i=0;i<n;i++) sigma=max(sigma,am->map(seq[i]));
  10         sigma++;
  11         uint * occ = new uint[sigma+1];
  12         for(uint i=0;i<=sigma;i++) occ[i] = 0;
  13         for(uint i=0;i<n;i++) occ[am->map(seq[i])+1]++;
  14         for(uint i=1;i<sigma;i++) occ[i] += occ[i-1];
  15         uint * pos = new uint[n];
  16         for(uint i=0;i<n;i++) pos[i] = 0;
  17         for(uint i=0;i<n;i++) pos[occ[am->map(seq[i])]++]=i;
  18         bitmaps = new static_bitsequence*[sigma];
  19         uint * bm = new uint[uint_len(n,1)];
  20         uint pp=0;
  21         for(uint i=0;i<sigma;i++) {
  22                 for(uint j=0;j<uint_len(n,1);j++) bm[j]=0;
  23                 while(pp<occ[i]) {
  24                         bitset(bm,pos[pp]);
  25                         pp++;
  26                 }
  27                 bitmaps[i] = bmb->build(bm,len);
  28         }
  29         delete [] bm;
  30         delete [] occ;
  31         delete [] pos;
  32 }
  33
  34 static_sequence_bs::static_sequence_bs() {
  35         len = 0;
  36         sigma = 0;
  37         bitmaps = NULL;
  38         am = NULL;
  39 }
  40
  41 static_sequence_bs::~static_sequence_bs() {
  42         if(bitmaps!=NULL) {
  43                 for(uint i=0;i<sigma;i++) {
  44                         if(bitmaps[i]!=NULL) delete bitmaps[i];
  45                 }
  46                 delete [] bitmaps;
  47         }
  48         if(am!=NULL) am->unuse();
  49 }
  50
  51 uint static_sequence_bs::rank(uint c, uint i) {
  52         if(am->map(c)>=sigma) return (uint)-1;
  53         return bitmaps[am->map(c)]->rank1(i);
  54 }
  55
  56 uint static_sequence_bs::select(uint c, uint i) {
  57         if(am->map(c)>=sigma) return (uint)-1;
  58         return bitmaps[am->map(c)]->select1(i);
  59 }
  60
  61 uint static_sequence_bs::select_next(uint c, uint i) {
  62         if(am->map(c)>=sigma) return (uint)-1;
  63         return bitmaps[am->map(c)]->select_next1(i);
  64 }
  65
  66 uint static_sequence_bs::access(uint i) {
  67         for(uint j=0;j<sigma;j++) {
  68                 if(bitmaps[j]->access(i)) return am->unmap(j);
  69         }
  70         return (uint)-1;
  71 }
  72
  73 uint static_sequence_bs::size() {
  74         uint size = sizeof(static_sequence_bs)+am->size();
  75         for(uint i=0;i<sigma;i++)
  76                 size += bitmaps[i]->size();
  77         return size;
  78 }
  79
  80 uint static_sequence_bs::save(FILE * fp) {
  81         uint wr = BS_HDR;
  82         wr = fwrite(&wr,sizeof(uint),1,fp);
  83         wr += fwrite(&len,sizeof(uint),1,fp);
  84         wr += fwrite(&sigma,sizeof(uint),1,fp);
  85         if(wr!=3) return 1;
  86         for(uint i=0;i<sigma;i++)
  87                 if(bitmaps[i]->save(fp)) return 2;
  88         if(am->save(fp)) return 3;
  89         return 0;
  90 }
  91
  92 static_sequence_bs * static_sequence_bs::load(FILE * fp) {
  93         uint rd = 0;
  94         uint type = 0;
  95         rd += fread(&type,sizeof(uint),1,fp);
  96         static_sequence_bs * ret = new static_sequence_bs();
  97         rd += fread(&ret->len,sizeof(uint),1,fp);
  98         rd += fread(&ret->sigma,sizeof(uint),1,fp);
  99         if(rd!=3 || type != BS_HDR) {
 100                 delete ret;
 101                 return NULL;
 102         }
 103         ret->bitmaps = new static_bitsequence*[ret->sigma];
 104         for(uint i=0;i<ret->sigma;i++)
 105                 ret->bitmaps[i] = NULL;
 106         for(uint i=0;i<ret->sigma;i++)
 107                 if((ret->bitmaps[i]=static_bitsequence::load(fp))==NULL) {
 108                         delete ret;
 109                         return NULL;
 110                 }
 111         if((ret->am = alphabet_mapper::load(fp))==NULL) {
 112                 delete ret;
 113                 return NULL;
 114         }
 115         ret->am->use();
 116         return ret;
 117 }
 118