#include <static_sequence_bs.h>
-
+using std::max;
static_sequence_bs::static_sequence_bs(uint * seq, uint n, alphabet_mapper * am, static_bitsequence_builder * bmb) {
sigma = 0;
len = n;
this->am = am;
am->use();
for(uint i=0;i<n;i++) sigma=max(sigma,am->map(seq[i]));
- bitmaps = new static_bitsequence*[++sigma];
- uint ** bm = new uint*[sigma];
+ sigma++;
+ uint * occ = new uint[sigma+1];
+ for(uint i=0;i<=sigma;i++) occ[i] = 0;
+ for(uint i=0;i<n;i++) occ[am->map(seq[i])+1]++;
+ for(uint i=1;i<sigma;i++) occ[i] += occ[i-1];
+ uint * pos = new uint[n];
+ for(uint i=0;i<n;i++) pos[i] = 0;
+ for(uint i=0;i<n;i++) pos[occ[am->map(seq[i])]++]=i;
+ bitmaps = new static_bitsequence*[sigma];
+ uint * bm = new uint[uint_len(n,1)];
+ uint pp=0;
for(uint i=0;i<sigma;i++) {
- bm[i] = new uint[uint_len(len,1)];
- for(uint j=0;j<uint_len(len,1);j++)
- bm[i][j] = 0;
+ for(uint j=0;j<uint_len(n,1);j++) bm[j]=0;
+ while(pp<occ[i]) {
+ bitset(bm,pos[pp]);
+ pp++;
+ }
+ bitmaps[i] = bmb->build(bm,len);
}
- for(uint i=0;i<n;i++)
- bitset(bm[am->map(seq[i])],i);
- for(uint i=0;i<sigma;i++)
- bitmaps[i] = bmb->build(bm[i],len);
- for(uint i=0;i<sigma;i++)
- delete [] bm[i];
delete [] bm;
+ delete [] occ;
+ delete [] pos;
}
static_sequence_bs::static_sequence_bs() {
if(am->map(c)>=sigma) return (uint)-1;
return bitmaps[am->map(c)]->rank1(i);
}
-
+/*
uint static_sequence_bs::select(uint c, uint i) {
if(am->map(c)>=sigma) return (uint)-1;
return bitmaps[am->map(c)]->select1(i);
if(am->map(c)>=sigma) return (uint)-1;
return bitmaps[am->map(c)]->select_next1(i);
}
-
+*/
+uint static_sequence_bs::select(uint c, uint i) {
+ if(c>=sigma) return (uint)-1;
+ return bitmaps[c]->select1(i);
+}
+uint static_sequence_bs::select_next(uint c, uint i) {
+ if(c>=sigma) return (uint)-1;
+ return bitmaps[c]->select_next1(i);
+}
uint static_sequence_bs::access(uint i) {
for(uint j=0;j<sigma;j++) {
if(bitmaps[j]->access(i)) return am->unmap(j);