libcds/src/static_sequence/static_sequence_gmr.cpp

   1 /* static_sequence_gmr.cpp
   2  * Copyright (C) 2008, Francisco Claude, all rights reserved.
   3  *
   4  * GMR
   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.h>
  23
  24 static_sequence_gmr::static_sequence_gmr(uint * sequence, uint n, uint chunk_length, static_bitsequence_builder * bmb, static_sequence_builder * ssb) {
  25   len = n;
  26         if(len%chunk_length) len+=chunk_length-len%chunk_length;
  27         uint * new_seq = new uint[len];
  28   sigma = 0;
  29         for(uint i=0;i<n;i++){
  30                 new_seq[i] = sequence[i]+1;
  31     sigma = max(sigma,new_seq[i]);
  32         }
  33   sigma++;
  34         for(uint i=n;i<len;i++)
  35                 new_seq[i] = sigma;
  36         if(len!=n) sigma++;
  37   this->chunk_length = chunk_length;
  38   build(new_seq,bmb,ssb);
  39         delete [] new_seq;
  40 }
  41
  42 static_sequence_gmr::static_sequence_gmr() {
  43 }
  44
  45 static_sequence_gmr::~static_sequence_gmr() {
  46   delete B;
  47   for (uint i=0;i<len/chunk_length;i++)
  48     delete chunk[i];
  49   delete [] chunk;
  50 }
  51
  52
  53 void static_sequence_gmr::build(uint * sequence, static_bitsequence_builder * bmb, static_sequence_builder * ssb) {
  54   uint num_chunks = len/chunk_length;
  55   chunk = new static_sequence*[num_chunks];
  56   assert(chunk!=NULL);
  57   for (uint i=0;i<num_chunks;i++) {
  58     chunk[i] = ssb->build(sequence+i*chunk_length, chunk_length);
  59     //cout << "1." << i << endl; cout.flush();
  60     assert(chunk[i]!=NULL);
  61   }
  62   uint * ones = get_ones(sequence);
  63   uint *B_bitmap = new uint[(2+len+(unsigned long long)num_chunks*sigma)/W+1];
  64     assert(B_bitmap!=NULL);
  65   for (uint i=0;i<(2+len+(unsigned long long)num_chunks*sigma)/W+1;i++)
  66     B_bitmap[i] = 0;
  67   uint pos=0;
  68   for (unsigned long long i=0;i<(unsigned long long)num_chunks*sigma;i++) {
  69     for (uint j=0;j<ones[i];j++) {
  70       bitset(B_bitmap, pos);
  71       pos++;
  72     }
  73     pos++;
  74   }
  75   pos++;
  76   //cout << "5  pos=" << pos << endl; cout.flush();
  77   B = bmb->build(B_bitmap, pos);
  78   //cout << "6" << endl; cout.flush();
  79   delete [] B_bitmap;
  80   delete [] ones;
  81 }
  82
  83
  84 uint * static_sequence_gmr::get_ones(uint * sequence) {
  85   uint * ones = new uint[(unsigned long long)(len/chunk_length)*sigma];
  86   assert(ones!=NULL);
  87   for (uint i=0;i<(unsigned long long)(len/chunk_length)*sigma;i++) ones[i] = 0;
  88   for (uint i=0;i<len;i++) {
  89     uint whichChunk = (uint)(((unsigned long long)sequence[i]*len+i)/chunk_length);
  90     ones[whichChunk]++;
  91   }
  92   return ones;
  93 }
  94
  95
  96 uint static_sequence_gmr::rank(uint c, uint j) {
  97   c++;
  98   uint i = j/chunk_length;
  99   uint bp = (c)*(len/chunk_length);
 100   uint rank_pos = B->select0(bp);
 101   uint prev = rank_pos-bp+1;
 102   uint sum = B->rank1(B->select0(bp+i)) - prev;
 103   uint cr = chunk[i]->rank(c,j-i*chunk_length);
 104         /*if(c==0) {
 105                 cout << "c=" << c << " j=" << j << endl;
 106                 cout << "i=" << i << endl;
 107                 cout << "bp=" << bp << endl;
 108                 cout << "rank_pos=" << rank_pos << endl;
 109                 cout << "prev=" << prev << endl;
 110                 cout << "sum=" << sum << endl;
 111                 cout << "cr=" << cr << endl;
 112         }*/
 113   return sum + cr;
 114 }
 115
 116
 117 uint static_sequence_gmr::select(uint c, uint j) {
 118    c++;
 119   uint rank_pos = B->select0(c*(len/chunk_length));
 120   uint prev = B->rank1(rank_pos);
 121   uint sel = prev+j;
 122   uint block = (B->select1(sel));
 123   uint i = block-sel+1;
 124   uint desp = B->rank1(B->select0((i)))-prev;
 125   if (desp+1==0) desp=0;
 126   uint rchunk = i%(len/chunk_length);
 127         /*if(j==90) {
 128                 cout << "------------------------------" << endl;
 129                 cout << "c=" << c << "  j=" << j << endl;
 130                 cout << "chunk_length=" << chunk_length << endl;
 131                 cout << "rank_pos=" << rank_pos << endl;
 132                 cout << "prev=" << prev << endl;
 133                 cout << "sel=" << sel << endl;
 134                 cout << "block=" << block << endl;
 135                 cout << "i=" << i << endl;
 136                 cout << "desp=" << desp << endl;
 137                 cout << "rchunk=" << rchunk << endl;
 138                 cout << "j-desp=" << j-desp << endl;
 139         }*/
 140   return (rchunk*chunk_length)+chunk[rchunk]->select(c, j-desp);
 141 }
 142
 143
 144 uint static_sequence_gmr::access(uint j) {
 145   return chunk[j/chunk_length]->access(j%chunk_length)-1;
 146 }
 147
 148
 149 uint static_sequence_gmr::size() {
 150   uint s = 0;
 151   for (uint i=0;i<len/chunk_length;i++)
 152     s += sizeof(void*)+chunk[i]->size();
 153   return s+B->size()+sizeof(static_sequence_gmr);
 154 }
 155
 156 uint static_sequence_gmr::save(FILE *fp) {
 157   uint wr = GMR_HDR;
 158   wr = fwrite(&wr,sizeof(uint),1,fp);
 159   wr += fwrite(&len,sizeof(uint),1,fp);
 160   wr += fwrite(&sigma,sizeof(uint),1,fp);
 161   wr += fwrite(&chunk_length,sizeof(uint),1,fp);
 162   if(wr!=4) return 1;
 163   if(B->save(fp)) return 1;
 164   for(uint i=0;i<len/chunk_length;i++)
 165     if(chunk[i]->save(fp)) return 1;
 166   return 0;
 167 }
 168
 169 static_sequence_gmr * static_sequence_gmr::load(FILE *fp) {
 170   uint rd;
 171   if(fread(&rd,sizeof(uint),1,fp)!=1) return NULL;
 172   if(rd!=GMR_HDR) return NULL;
 173   static_sequence_gmr * ret = new static_sequence_gmr();
 174   rd = fread(&ret->len,sizeof(uint),1,fp);
 175   rd += fread(&ret->sigma,sizeof(uint),1,fp);
 176   rd += fread(&ret->chunk_length,sizeof(uint),1,fp);
 177   if(rd!=3) {
 178     delete ret;
 179     return NULL;
 180   }
 181   ret->B = static_bitsequence::load(fp);
 182   if(ret->B==NULL) {
 183     delete ret;
 184     return NULL;
 185   }
 186   ret->chunk = new static_sequence*[ret->len/ret->chunk_length];
 187   for(uint i=0;i<ret->len/ret->chunk_length;i++) {
 188     ret->chunk[i] = static_sequence::load(fp);
 189     if(ret->chunk[i]==NULL) {
 190       delete ret;
 191       return NULL;
 192     }
 193   }
 194   return ret;
 195 }