libcds/src/static_sequence/static_sequence_gmr_chunk.cpp

   1 /* static_sequence_gmr_chunk.cpp
   2  * Copyright (C) 2008, Francisco Claude, all rights reserved.
   3  *
   4  * gmr_chunk
   5  *
   6  * This library is free software; you can redistribute it and/or
   7  * modify it under the terms of the GNU Lesser General Public
   8  * License as published by the Free Software Foundation; either
   9  * version 2.1 of the License, or (at your option) any later version.
  10  *
  11  * This library is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14  * Lesser General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU Lesser General Public
  17  * License along with this library; if not, write to the Free Software
  18  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  19  *
  20  */
  21
  22 #include "static_sequence_gmr_chunk.h"
  23 using std::max;
  24
  25 static_sequence_gmr_chunk::static_sequence_gmr_chunk(uint * sequence, uint chunk_length, static_bitsequence_builder *bmb, static_permutation_builder *pmb) {
  26   sigma = 0;
  27   for(uint i=0;i<chunk_length;i++) {
  28     sigma = max(sigma,sequence[i]);
  29   }sigma++;
  30   uint * X_bitmap = new uint[uint_len(1+chunk_length+sigma,1)];
  31   assert(X_bitmap!=NULL);
  32   for(uint i=0;i<uint_len(1+chunk_length+sigma,1);i++) X_bitmap[i]=0;
  33   uint pi_blen = bits(chunk_length-1);
  34   uint * pi = new uint[uint_len(pi_blen,chunk_length)];
  35   assert(pi!=NULL);
  36   for(uint i=0;i<uint_len(pi_blen,chunk_length);i++) pi[i] = 0;
  37   uint X_pos = 0;
  38   uint * counter = new uint[sigma+2];
  39   for(uint c=0;c<=sigma+1;c++) counter[c]=0;
  40   for(uint i=0;i<chunk_length;i++) counter[sequence[i]+1]++;
  41
  42   for(uint c=0;c<sigma;c++) {
  43     X_pos++;
  44     for(uint i=0;i<counter[c+1];i++) {
  45       bitset(X_bitmap, X_pos);
  46       X_pos++;
  47     }
  48     counter[c+1]+=counter[c];
  49   }
  50   X_pos++;
  51   for(uint i=0;i<chunk_length;i++) {
  52     set_field(pi, pi_blen,counter[sequence[i]], i);
  53     counter[sequence[i]]++;
  54   }
  55   //cout << "pi_blen=" << pi_blen << endl;
  56   this->X = bmb->build(X_bitmap,X_pos); //new BitRankW32Int(X_bitmap, X_pos, true,20);
  57   assert(X!=NULL);
  58   delete [] X_bitmap;
  59   //cout << "a" << endl; cout.flush();
  60   this->permutation = pmb->build(pi,chunk_length); //createPerm(pi, chunk_length, t);
  61   //cout << "a" << endl; cout.flush();
  62   assert(permutation!=NULL);
  63   this->sigma = sigma;
  64   this->len = chunk_length;
  65         delete [] counter;
  66 }
  67
  68 static_sequence_gmr_chunk::static_sequence_gmr_chunk() {
  69 }
  70
  71 static_sequence_gmr_chunk::~static_sequence_gmr_chunk() {
  72         delete X;
  73   delete permutation;
  74 }
  75
  76
  77 uint static_sequence_gmr_chunk::access(uint j) {
  78   uint invPerm = permutation->rev_pi(j); //inversePerm(permutation, j);
  79   //cout << "invPerm=" << invPerm << endl;
  80   uint rank_pos = X->select1(invPerm+1);
  81   //cout << "rank_pos=" << rank_pos << endl;
  82   uint ret = rank_pos - X->rank1(rank_pos);// - 1;
  83   //cout << "ret = " << ret << endl;
  84   return ret;
  85 }
  86
  87
  88 uint static_sequence_gmr_chunk::select(uint i, uint j) {
  89   uint pos = X->select0(i+1) + j - i -1;
  90   /*cout << "pos=" << pos << endl;
  91   cout << "pos'=" << X->rank1(X->select0(i+1)+j) << endl;
  92   cout << "perm_pos=" << permutation->pi(pos) << endl;*/
  93   return permutation->pi(pos); //getelemPerm(permutation, pos);
  94 }
  95
  96
  97 uint static_sequence_gmr_chunk::rank(uint i, uint j) {
  98   uint ini = X->select0(i+1)-i;
  99   uint ini_o = ini;
 100   uint fin = X->select0(i+2);
 101         if(fin<i+2) return 0;
 102         fin = fin-(i+2);
 103         if(fin<ini) return 0;
 104         if(permutation->pi(ini) > j) return 0;
 105         if(permutation->pi(ini) == j) return 1;
 106         if(ini==fin) return 1;
 107   while(ini < fin-1) {
 108                 uint med = (ini+fin)/2;
 109     uint elem = permutation->pi(med); //getelemPerm(permutation, med);
 110     if(elem >= j) fin = med;
 111     else ini = med;
 112   }
 113         while(fin>ini_o && permutation->pi(fin)>j) fin--;
 114   return fin-ini_o+1;
 115 }
 116
 117
 118 uint static_sequence_gmr_chunk::size() {
 119   return sizeof(static_sequence_gmr_chunk)+permutation->size()+X->size();
 120 }
 121
 122 uint static_sequence_gmr_chunk::save(FILE *fp) {
 123   uint wr = GMR_CHUNK_HDR;
 124   wr = fwrite(&wr,sizeof(uint),1,fp);
 125   wr += fwrite(&len,sizeof(uint),1,fp);
 126   wr += fwrite(&sigma,sizeof(uint),1,fp);
 127   if(wr!=3) return 1;
 128   if(X->save(fp)) return 1;
 129   if(permutation->save(fp)) return 1;
 130   return 0;
 131 }
 132
 133 static_sequence_gmr_chunk * static_sequence_gmr_chunk::load(FILE *fp) {
 134   uint rd;
 135   if(fread(&rd,sizeof(uint),1,fp)!=1) return NULL;
 136   if(rd!=GMR_CHUNK_HDR) return NULL;
 137   static_sequence_gmr_chunk * ret = new static_sequence_gmr_chunk();
 138   rd = fread(&ret->len,sizeof(uint),1,fp);
 139   rd += fread(&ret->sigma,sizeof(uint),1,fp);
 140   ret->X = static_bitsequence::load(fp);
 141   ret->permutation = static_permutation::load(fp);
 142   if(rd!=2 || ret->X==NULL || ret->permutation==NULL) {
 143                 /*cout << "rd=" << rd << endl;
 144                 cout << "X =" << ret->X << endl;
 145                 cout << "P =" << ret->permutation << endl;*/
 146     delete ret;
 147     return NULL;
 148   }
 149   return ret;
 150 }