libcds/src/static_sequence/static_sequence_wvtree_noptrs.cpp

   1 /* static_sequence_wvtree_noptrs.cpp
   2  * Copyright (C) 2008, Francisco Claude, all rights reserved.
   3  *
   4  * static_sequence_wvtree_noptrs definition
   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_wvtree_noptrs.h>
  23
  24 static_sequence_wvtree_noptrs::static_sequence_wvtree_noptrs(uint * symbols, uint n, static_bitsequence_builder * bmb, alphabet_mapper * am) {
  25   this->n=n;
  26   this->am=am;
  27         am->use();
  28   for(uint i=0;i<n;i++)
  29     symbols[i] = am->map(symbols[i]);
  30   max_v=max_value(symbols,n);
  31   height=bits(max_v);
  32   uint *occurrences=new uint[max_v+1];
  33   for(uint i=0;i<=max_v;i++) occurrences[i]=0;
  34   for(uint i=0;i<n;i++)
  35     occurrences[symbols[i]]++;
  36   uint to_add=0;
  37   for(uint i=0;i<max_v;i++)
  38     if(occurrences[i]==0) to_add++;
  39   uint * new_symb = new uint[n+to_add];
  40   for(uint i=0;i<n;i++)
  41     new_symb[i] = symbols[i];
  42   to_add = 0;
  43   for(uint i=0;i<max_v;i++)
  44     if(occurrences[i]==0) {
  45       occurrences[i]++;
  46       new_symb[n+to_add]=i;
  47       to_add++;
  48     }
  49   uint new_n = n+to_add;
  50   for(uint i=1;i<=max_v;i++)
  51     occurrences[i] += occurrences[i-1];
  52   uint *oc = new uint[(new_n+1)/W+1];
  53   for(uint i=0;i<(new_n+1)/W+1;i++)
  54     oc[i] = 0;
  55   for(uint i=0;i<=max_v;i++)
  56     bitset(oc,occurrences[i]-1);
  57   bitset(oc,new_n);
  58   occ = bmb->build(oc,new_n+1);
  59   delete [] occurrences;
  60   this->n = new_n;
  61   uint ** _bm=new uint*[height];
  62   for(uint i=0;i<height;i++) {
  63     _bm[i] = new uint[new_n/W+1];
  64     for(uint j=0;j<new_n/W+1;j++)
  65       _bm[i][j]=0;
  66   }
  67   build_level(_bm,new_symb,0,new_n,0);
  68   bitstring = new static_bitsequence*[height];
  69   for(uint i=0;i<height;i++) {
  70         bitstring[i] = bmb->build(_bm[i],new_n);
  71     delete [] _bm[i];
  72   }
  73   delete [] _bm;
  74   for(uint i=0;i<n;i++)
  75     symbols[i] = am->unmap(symbols[i]);
  76         delete [] new_symb;
  77         delete [] oc;
  78 }
  79
  80 static_sequence_wvtree_noptrs::static_sequence_wvtree_noptrs() {
  81 }
  82
  83 static_sequence_wvtree_noptrs::~static_sequence_wvtree_noptrs() {
  84   for(uint i=0;i<height;i++)
  85     delete bitstring[i];
  86   delete [] bitstring;
  87   delete occ;
  88         am->unuse();
  89 }
  90
  91 uint static_sequence_wvtree_noptrs::save(FILE *fp) {
  92   uint wr = WVTREE_NOPTRS_HDR;
  93   wr = fwrite(&wr,sizeof(uint),1,fp);
  94   wr += fwrite(&n,sizeof(uint),1,fp);
  95   wr += fwrite(&max_v,sizeof(uint),1,fp);
  96   wr += fwrite(&height,sizeof(uint),1,fp);
  97   if(wr!=4) return 1;
  98   if(am->save(fp)) return 1;
  99   for(uint i=0;i<height;i++)
 100     if(bitstring[i]->save(fp)) return 1;
 101         if(occ->save(fp)) return 1;
 102   return 0;
 103 }
 104
 105 static_sequence_wvtree_noptrs * static_sequence_wvtree_noptrs::load(FILE *fp) {
 106   uint rd;
 107   if(fread(&rd,sizeof(uint),1,fp)!=1) return NULL;
 108   if(rd!=WVTREE_NOPTRS_HDR) return NULL;
 109   static_sequence_wvtree_noptrs * ret = new static_sequence_wvtree_noptrs();
 110   rd = fread(&ret->n,sizeof(uint),1,fp);
 111   rd += fread(&ret->max_v,sizeof(uint),1,fp);
 112   rd += fread(&ret->height,sizeof(uint),1,fp);
 113   if(rd!=3) {
 114     delete ret;
 115     return NULL;
 116   }
 117   ret->am = alphabet_mapper::load(fp);
 118   if(ret->am==NULL) {
 119     delete ret;
 120     return NULL;
 121   }
 122         ret->am->use();
 123   ret->bitstring = new static_bitsequence*[ret->height];
 124   for(uint i=0;i<ret->height;i++) {
 125     ret->bitstring[i] = static_bitsequence::load(fp);
 126     if(ret->bitstring[i]==NULL){
 127       delete ret;
 128       return NULL;
 129     }
 130   }
 131         ret->occ = static_bitsequence::load(fp);
 132         if(ret->occ==NULL) {
 133                 delete ret;
 134                 return NULL;
 135         }
 136   return ret;
 137 }
 138
 139 uint static_sequence_wvtree_noptrs::access(uint pos) {
 140   uint level=0;
 141   uint ret=0;
 142   uint start=0;
 143   uint end=n-1;
 144   while(level<height) {
 145     assert(pos>=start && pos<=end);
 146     if(bitstring[level]->access(pos)) {
 147       ret=set(ret,level);
 148       pos=bitstring[level]->rank1(pos-1)-bitstring[level]->rank1(start-1);
 149       start=(bitstring[level]->rank1(end)-bitstring[level]->rank1(start-1));
 150       start=end-start+1;
 151       pos+=start;
 152     }
 153     else {
 154       pos=pos-start-(bitstring[level]->rank1(pos)-bitstring[level]->rank1(start-1));
 155       end=end-start-(bitstring[level]->rank1(end)-bitstring[level]->rank1(start-1));
 156       end+=start;
 157       pos+=start;
 158     }
 159     level++;
 160   }
 161   return am->unmap(ret);
 162 }
 163
 164 uint static_sequence_wvtree_noptrs::rank(uint symbol, uint pos) {
 165   symbol = am->map(symbol);
 166   uint level=0;
 167   uint start=0;
 168   uint end=n-1;
 169   uint count=0;
 170   while(level<height) {
 171     if(is_set(symbol,level)) {
 172       pos=bitstring[level]->rank1(pos)-bitstring[level]->rank1(start-1)-1;
 173       count=pos+1;
 174       start=(bitstring[level]->rank1(end)-bitstring[level]->rank1(start-1));
 175       start=end-start+1;
 176       pos+=start;
 177     }
 178     else {
 179       pos=pos-start+bitstring[level]->rank1(start-1)-bitstring[level]->rank1(pos);
 180       count=pos+1;
 181       end=end-start-(bitstring[level]->rank1(end)-bitstring[level]->rank1(start-1));
 182       end+=start;
 183       pos+=start;
 184     }
 185     level++;
 186     if(count==0) return 0;
 187   }
 188   return count;
 189 }
 190
 191 inline uint get_start(uint symbol, uint mask) {
 192   return symbol&mask;
 193 }
 194
 195 inline uint get_end(uint symbol, uint mask) {
 196   return get_start(symbol,mask)+!mask+1;
 197 }
 198
 199 uint static_sequence_wvtree_noptrs::select(uint symbol, uint j) {
 200   symbol = am->map(symbol);
 201   uint mask = (1<<height)-2;
 202   uint sum=2;
 203   uint level = height-1;
 204   uint pos=j;
 205   while(true) {
 206     uint start = get_start(symbol,mask);
 207     uint end = min(max_v+1,start+sum);
 208     start = (start==0)?0:(occ->select1(start)+1);
 209     end = occ->select1(end+1)-1;
 210     if(is_set(symbol,level)) {
 211       uint ones_start = bitstring[level]->rank1(start-1);
 212       pos = bitstring[level]->select1(ones_start+pos)-start+1;
 213     }
 214     else {
 215       uint ones_start = bitstring[level]->rank1(start-1);
 216       pos = bitstring[level]->select0(start-ones_start+pos)-start+1;
 217     }
 218     mask <<=1;
 219     sum <<=1;
 220     if(level==0) break;
 221     level--;
 222   }
 223   return pos-1;
 224 }
 225
 226 uint static_sequence_wvtree_noptrs::size() {
 227   uint ptrs = sizeof(static_sequence_wvtree_noptrs)+height*sizeof(static_sequence*);
 228   uint bytesBitstrings = 0;
 229   for(uint i=0;i<height;i++)
 230     bytesBitstrings += bitstring[i]->size();
 231   return bytesBitstrings+occ->size()+ptrs;
 232 }
 233
 234 void static_sequence_wvtree_noptrs::build_level(uint **bm, uint *symbols, uint level, uint length, uint offset) {
 235   if(level==height) return;
 236   uint cleft=0;
 237   for(uint i=0;i<length;i++)
 238     if(!is_set(symbols[i],level))
 239       cleft++;
 240   uint cright=length-cleft;
 241   uint *left=new uint[cleft], *right=new uint[cright];
 242   cleft=cright=0;
 243   for(uint i=0;i<length;i++)
 244   if(!is_set(symbols[i],level)) {
 245     left[cleft++]=symbols[i];
 246     bitclean(bm[level],offset+i);
 247   }
 248   else {
 249     right[cright++]=symbols[i];
 250     bitset(bm[level],offset+i);
 251   }
 252   build_level(bm,left,level+1,cleft,offset);
 253   build_level(bm,right,level+1,cright,offset+cleft);
 254   delete [] left;
 255   delete [] right;
 256 }
 257
 258 uint static_sequence_wvtree_noptrs::max_value(uint *symbols, uint n) {
 259   uint max_v = 0;
 260   for(uint i=0;i<n;i++)
 261     max_v = max(symbols[i],max_v);
 262   return max_v;
 263 }
 264
 265 uint static_sequence_wvtree_noptrs::bits(uint val) {
 266   uint ret = 0;
 267   while(val!=0) {
 268     ret++;
 269     val >>= 1;
 270   }
 271   return ret;
 272 }
 273
 274 bool static_sequence_wvtree_noptrs::is_set(uint val, uint ind) {
 275   assert(ind<height);
 276   return (val & (1<<(height-ind-1)))!=0;
 277 }
 278
 279
 280 uint static_sequence_wvtree_noptrs::set(uint val, uint ind) {
 281   assert(ind<=height);
 282   return val | (1<<(height-ind-1));
 283 }