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::select(uint c, uint i) {
  67         if(c>=sigma) return (uint)-1;
  68         return bitmaps[c]->select1(i);
  69 }
  70 uint static_sequence_bs::select_next(uint c, uint i) {
  71         if(c>=sigma) return (uint)-1;
  72         return bitmaps[c]->select_next1(i);
  73 }
  74 uint static_sequence_bs::access(uint i) {
  75         for(uint j=0;j<sigma;j++) {
  76                 if(bitmaps[j]->access(i)) return am->unmap(j);
  77         }
  78         return (uint)-1;
  79 }
  80
  81 uint static_sequence_bs::size() {
  82         uint size = sizeof(static_sequence_bs)+am->size();
  83         for(uint i=0;i<sigma;i++)
  84                 size += bitmaps[i]->size();
  85         return size;
  86 }
  87
  88 uint static_sequence_bs::save(FILE * fp) {
  89         uint wr = BS_HDR;
  90         wr = fwrite(&wr,sizeof(uint),1,fp);
  91         wr += fwrite(&len,sizeof(uint),1,fp);
  92         wr += fwrite(&sigma,sizeof(uint),1,fp);
  93         if(wr!=3) return 1;
  94         for(uint i=0;i<sigma;i++)
  95                 if(bitmaps[i]->save(fp)) return 2;
  96         if(am->save(fp)) return 3;
  97         return 0;
  98 }
  99
 100 static_sequence_bs * static_sequence_bs::load(FILE * fp) {
 101         uint rd = 0;
 102         uint type = 0;
 103         rd += fread(&type,sizeof(uint),1,fp);
 104         static_sequence_bs * ret = new static_sequence_bs();
 105         rd += fread(&ret->len,sizeof(uint),1,fp);
 106         rd += fread(&ret->sigma,sizeof(uint),1,fp);
 107         if(rd!=3 || type != BS_HDR) {
 108                 delete ret;
 109                 return NULL;
 110         }
 111         ret->bitmaps = new static_bitsequence*[ret->sigma];
 112         for(uint i=0;i<ret->sigma;i++)
 113                 ret->bitmaps[i] = NULL;
 114         for(uint i=0;i<ret->sigma;i++)
 115                 if((ret->bitmaps[i]=static_bitsequence::load(fp))==NULL) {
 116                         delete ret;
 117                         return NULL;
 118                 }
 119         if((ret->am = alphabet_mapper::load(fp))==NULL) {
 120                 delete ret;
 121                 return NULL;
 122         }
 123         ret->am->use();
 124         return ret;
 125 }
 126