2 #include "static_sequence_gmr_chunk.h"
4 static_sequence_gmr_chunk::static_sequence_gmr_chunk(uint * sequence, uint chunk_length, static_bitsequence_builder *bmb, static_permutation_builder *pmb) {
6 for(uint i=0;i<chunk_length;i++) {
7 sigma = max(sigma,sequence[i]);
9 uint * X_bitmap = new uint[(1+chunk_length+sigma)/W+1];
10 assert(X_bitmap!=NULL);
11 for(uint i=0;i<(1+sigma+chunk_length)/W+1;i++) X_bitmap[i]=0;
12 uint pi_blen = bits(chunk_length-1);
13 uint * pi = new uint[pi_blen*chunk_length/W+1];
15 for(uint i=0;i<pi_blen*chunk_length/W+1;i++) pi[i] = 0;
17 uint * counter = new uint[sigma+1];
18 for(uint c=0;c<=sigma;c++) counter[c]=0;
19 for(uint i=0;i<chunk_length;i++) counter[sequence[i]+1]++;
21 for(uint c=0;c<sigma;c++) {
23 for(uint i=0;i<counter[c+1];i++) {
24 bitset(X_bitmap, X_pos);
27 counter[c+1]+=counter[c];
30 for(uint i=0;i<chunk_length;i++) {
31 bitput(pi, pi_blen*counter[sequence[i]], pi_blen, (uint)i);
32 counter[sequence[i]]++;
34 this->X = new BitRankW32Int(X_bitmap, X_pos, true,20);
36 this->permutation = createPerm(pi, chunk_length, t);
37 assert(permutation!=NULL);
39 this->chunk_length = chunk_length;
44 static_sequence_gmr_chunk::~static_sequence_gmr_chunk() {
50 uint static_sequence_gmr_chunk::caccess(uint j) {
51 uint invPerm = inversePerm(permutation, j);
52 uint rank_pos = X->select1(invPerm+1);
53 uint ret = rank_pos - X->rank(rank_pos);// - 1;
58 uint static_sequence_gmr_chunk::cselect(uint i, uint j) {
59 uint pos = X->select0(i+1) + j - i -1;
60 return getelemPerm(permutation, pos);
64 uint static_sequence_gmr_chunk::crank(uint i, uint j) {
65 uint ini = X->select0(i+1)-i;
67 uint fin = X->select0(i+2);
71 if(getelemPerm(permutation,ini) > j) return 0;
72 if(getelemPerm(permutation,ini) == j) return 1;
73 if(ini==fin) return 1;
75 uint med = (ini+fin)/2;
76 uint elem = getelemPerm(permutation, med);
77 if(elem >= j) fin = med;
80 while(fin>ini_o && getelemPerm(permutation, fin)>j) fin--;
85 uint static_sequence_gmr_chunk::size() {
86 return sizeof(BitRankW32Int*)+sizeof(perm*)+(X->SpaceRequirementInBits()/8+sizeofPerm(permutation));