libcds/src/static_sequence/static_sequence_gmr_chunk.cpp

   1
   2 #include "static_sequence_gmr_chunk.h"
   3
   4 static_sequence_gmr_chunk::static_sequence_gmr_chunk(uint * sequence, uint chunk_length, static_bitsequence_builder *bmb, static_permutation_builder *pmb) {
   5   sigma = 0;
   6   for(uint i=0;i<chunk_length;i++) {
   7     sigma = max(sigma,sequence[i]);
   8   }
   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];
  14   assert(pi!=NULL);
  15   for(uint i=0;i<pi_blen*chunk_length/W+1;i++) pi[i] = 0;
  16   uint X_pos = 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]++;
  20
  21   for(uint c=0;c<sigma;c++) {
  22     X_pos++;
  23     for(uint i=0;i<counter[c+1];i++) {
  24       bitset(X_bitmap, X_pos);
  25       X_pos++;
  26     }
  27     counter[c+1]+=counter[c];
  28   }
  29   X_pos++;
  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]]++;
  33   }
  34   this->X = new BitRankW32Int(X_bitmap, X_pos, true,20);
  35   assert(X!=NULL);
  36   this->permutation = createPerm(pi, chunk_length, t);
  37   assert(permutation!=NULL);
  38   this->sigma = sigma;
  39   this->chunk_length = chunk_length;
  40         delete [] counter;
  41 }
  42
  43
  44 static_sequence_gmr_chunk::~static_sequence_gmr_chunk() {
  45         delete X;
  46   delete permutation;
  47 }
  48
  49
  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;
  54   return ret;
  55 }
  56
  57
  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);
  61 }
  62
  63
  64 uint static_sequence_gmr_chunk::crank(uint i, uint j) {
  65   uint ini = X->select0(i+1)-i;
  66   uint ini_o = ini;
  67   uint fin = X->select0(i+2);
  68         if(fin<i+2) return 0;
  69         fin = fin-(i+2);
  70         if(fin<ini) return 0;
  71         if(getelemPerm(permutation,ini) > j) return 0;
  72         if(getelemPerm(permutation,ini) == j) return 1;
  73         if(ini==fin) return 1;
  74   while(ini < fin-1) {
  75                 uint med = (ini+fin)/2;
  76     uint elem = getelemPerm(permutation, med);
  77     if(elem >= j) fin = med;
  78     else ini = med;
  79   }
  80         while(fin>ini_o && getelemPerm(permutation, fin)>j) fin--;
  81   return fin-ini_o+1;
  82 }
  83
  84
  85 uint static_sequence_gmr_chunk::size() {
  86   return sizeof(BitRankW32Int*)+sizeof(perm*)+(X->SpaceRequirementInBits()/8+sizeofPerm(permutation));
  87 }