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 vector<int> static_sequence_wvtree_noptrs::access(uint i, uint j, uint min, uint max)
 192 {
 193     vector<int> resultSet;
 194 //    cout << "height = " << height << endl;
 195     access(resultSet, i, j, am->map(min), am->map(max), 0, 0, 0, n-1);
 196     return resultSet;
 197 }
 198
 199 void static_sequence_wvtree_noptrs::access(vector<int> &result, uint i, uint j, uint min, uint max, uint l, uint pivot, uint start, uint end)
 200 {
 201     uint symbol = pivot | (1 << (height-l-1));
 202     //std::cout << "At l = " << l << ", [" << i << ", " << j  << "], [" << min << ", " << max << "], [" << start << ", " << end << "], symbol = " << symbol << std::endl;
 203
 204     if (l == height)
 205     {
 206         if (i <= j && pivot >= min && pivot <= max && start <= end)
 207             result.push_back(am->unmap((int)pivot));
 208         return;
 209     }
 210
 211     if (j < i || max < min || end < start)
 212         return;
 213
 214     if (min < symbol)
 215     {
 216         // Recurse left
 217         uint newi = i + bitstring[l]->rank1(start-1) - bitstring[l]->rank1(i-1);
 218         uint newend = end - (bitstring[l]->rank1(end) - bitstring[l]->rank1(start-1));
 219         uint newj = j + bitstring[l]->rank1(start-1) - bitstring[l]->rank1(j) + 1;
 220
 221         uint newmax = max < symbol - 1 ? max : symbol - 1;
 222         if (newj > start)
 223             access(result, newi, newj-1, min, newmax, l+1, pivot, start, newend);
 224     }
 225
 226     if (max >= symbol)
 227     {
 228         // Recurse right
 229         uint newstart = (bitstring[l]->rank1(end)-bitstring[l]->rank1(start-1));
 230         newstart = end - newstart + 1;
 231         uint newi = bitstring[l]->rank1(i-1)-bitstring[l]->rank1(start-1) + newstart;
 232         uint newj = bitstring[l]->rank1(j)-bitstring[l]->rank1(start-1) + newstart;
 233
 234         uint newmin = min > symbol ? min : symbol;
 235         if (newj > newstart)
 236             access(result, newi, newj-1, newmin, max, l+1, symbol, newstart, end);
 237     }
 238 }
 239
 240
 241 vector<int> static_sequence_wvtree_noptrs::accessAll(uint i, uint j)
 242 {
 243     vector<int> resultSet;
 244     if (j > i)
 245         return resultSet;
 246
 247     resultSet.reserve(j-i+1);
 248     accessAll(resultSet, i, j, 0, 0, 0, n-1);
 249     return resultSet;
 250 }
 251
 252 void static_sequence_wvtree_noptrs::accessAll(vector<int> &result, uint i, uint j, uint l, uint pivot, uint start, uint end)
 253 {
 254     uint symbol = pivot | (1 << (height-l-1));
 255 //    std::cout << "At l = " << l << ", [" << i << ", " << j  << "], [" << start << ", " << end << "], symbol = " << symbol << std::endl;
 256
 257     if (l == height)
 258     {
 259         if (i <= j && start <= end)
 260             result.push_back(am->unmap((int)pivot));
 261         return;
 262     }
 263
 264     if (j < i || end < start)
 265         return;
 266
 267     {
 268         // Recurse left
 269         uint newi = i + bitstring[l]->rank1(start-1) - bitstring[l]->rank1(i-1);
 270         uint newend = end - (bitstring[l]->rank1(end) - bitstring[l]->rank1(start-1));
 271         uint newj = j + bitstring[l]->rank1(start-1) - bitstring[l]->rank1(j) + 1;
 272
 273         if (newj > start)
 274             accessAll(result, newi, newj-1, l+1, pivot, start, newend);
 275     }
 276
 277     {
 278         // Recurse right
 279         uint newstart = (bitstring[l]->rank1(end)-bitstring[l]->rank1(start-1));
 280         newstart = end - newstart + 1;
 281         uint newi = bitstring[l]->rank1(i-1)-bitstring[l]->rank1(start-1) + newstart;
 282         uint newj = bitstring[l]->rank1(j)-bitstring[l]->rank1(start-1) + newstart;
 283
 284         if (newj > newstart)
 285             accessAll(result, newi, newj-1, l+1, symbol, newstart, end);
 286     }
 287 }
 288
 289
 290 uint static_sequence_wvtree_noptrs::count(uint i, uint j, uint min, uint max)
 291 {
 292     return count(i, j, am->map(min), am->map(max), 0, 0, 0, n-1);
 293 }
 294
 295 uint static_sequence_wvtree_noptrs::count(uint i, uint j, uint min, uint max, uint l, uint pivot, uint start, uint end)
 296 {
 297     uint symbol = pivot | (1 << (height-l-1));
 298     //std::cout << "At l = " << l << ", [" << i << ", " << j  << "], [" << min << ", " << max << "], [" << start << ", " << end << "], symbol = " << symbol << std::endl;
 299
 300     if (l == height)
 301     {
 302         if (i <= j && pivot >= min && pivot <= max && start <= end)
 303             return 1;
 304         return 0;
 305     }
 306
 307     if (j < i || max < min || end < start)
 308         return 0;
 309
 310     uint result = 0;
 311     if (min < symbol)
 312     {
 313         // Recurse left
 314         uint newi = i + bitstring[l]->rank1(start-1) - bitstring[l]->rank1(i-1);
 315         uint newend = end - (bitstring[l]->rank1(end) - bitstring[l]->rank1(start-1));
 316         uint newj = j + bitstring[l]->rank1(start-1) - bitstring[l]->rank1(j) + 1;
 317
 318         uint newmax = max < symbol - 1 ? max : symbol - 1;
 319         if (newj > start)
 320             result += count(newi, newj-1, min, newmax, l+1, pivot, start, newend);
 321     }
 322
 323     if (max >= symbol)
 324     {
 325         // Recurse right
 326         uint newstart = (bitstring[l]->rank1(end)-bitstring[l]->rank1(start-1));
 327         newstart = end - newstart + 1;
 328         uint newi = bitstring[l]->rank1(i-1)-bitstring[l]->rank1(start-1) + newstart;
 329         uint newj = bitstring[l]->rank1(j)-bitstring[l]->rank1(start-1) + newstart;
 330
 331         uint newmin = min > symbol ? min : symbol;
 332         if (newj > newstart)
 333             result += count(newi, newj-1, newmin, max, l+1, symbol, newstart, end);
 334     }
 335     return result;
 336 }
 337
 338
 339
 340 inline uint get_start(uint symbol, uint mask) {
 341   return symbol&mask;
 342 }
 343
 344 inline uint get_end(uint symbol, uint mask) {
 345   return get_start(symbol,mask)+!mask+1;
 346 }
 347
 348 uint static_sequence_wvtree_noptrs::select(uint symbol, uint j) {
 349   symbol = am->map(symbol);
 350   uint mask = (1<<height)-2;
 351   uint sum=2;
 352   uint level = height-1;
 353   uint pos=j;
 354   while(true) {
 355     uint start = get_start(symbol,mask);
 356     uint end = min(max_v+1,start+sum);
 357     start = (start==0)?0:(occ->select1(start)+1);
 358     end = occ->select1(end+1)-1;
 359     if(is_set(symbol,level)) {
 360       uint ones_start = bitstring[level]->rank1(start-1);
 361       pos = bitstring[level]->select1(ones_start+pos)-start+1;
 362     }
 363     else {
 364       uint ones_start = bitstring[level]->rank1(start-1);
 365       pos = bitstring[level]->select0(start-ones_start+pos)-start+1;
 366     }
 367     mask <<=1;
 368     sum <<=1;
 369     if(level==0) break;
 370     level--;
 371   }
 372   return pos-1;
 373 }
 374
 375 uint static_sequence_wvtree_noptrs::size() {
 376   uint ptrs = sizeof(static_sequence_wvtree_noptrs)+height*sizeof(static_sequence*);
 377   uint bytesBitstrings = 0;
 378   for(uint i=0;i<height;i++)
 379     bytesBitstrings += bitstring[i]->size();
 380   return bytesBitstrings+occ->size()+ptrs;
 381 }
 382
 383 void static_sequence_wvtree_noptrs::build_level(uint **bm, uint *symbols, uint level, uint length, uint offset) {
 384   if(level==height) return;
 385   uint cleft=0;
 386   for(uint i=0;i<length;i++)
 387     if(!is_set(symbols[i],level))
 388       cleft++;
 389   uint cright=length-cleft;
 390   uint *left=new uint[cleft], *right=new uint[cright];
 391   cleft=cright=0;
 392   for(uint i=0;i<length;i++)
 393   if(!is_set(symbols[i],level)) {
 394     left[cleft++]=symbols[i];
 395     bitclean(bm[level],offset+i);
 396   }
 397   else {
 398     right[cright++]=symbols[i];
 399     bitset(bm[level],offset+i);
 400   }
 401   build_level(bm,left,level+1,cleft,offset);
 402   build_level(bm,right,level+1,cright,offset+cleft);
 403   delete [] left;
 404   delete [] right;
 405 }
 406
 407 uint static_sequence_wvtree_noptrs::max_value(uint *symbols, uint n) {
 408   uint max_v = 0;
 409   for(uint i=0;i<n;i++)
 410     max_v = max(symbols[i],max_v);
 411   return max_v;
 412 }
 413
 414 uint static_sequence_wvtree_noptrs::bits(uint val) {
 415   uint ret = 0;
 416   while(val!=0) {
 417     ret++;
 418     val >>= 1;
 419   }
 420   return ret;
 421 }
 422
 423 bool static_sequence_wvtree_noptrs::is_set(uint val, uint ind) {
 424   assert(ind<height);
 425   return (val & (1<<(height-ind-1)))!=0;
 426 }
 427
 428
 429 uint static_sequence_wvtree_noptrs::set(uint val, uint ind) {
 430   assert(ind<=height);
 431   return val | (1<<(height-ind-1));
 432 }