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, bool deleteSymbols) {
  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
  43   if (deleteSymbols)
  44   {
  45       delete [] symbols;
  46       symbols = 0;
  47   }
  48
  49   to_add = 0;
  50   for(uint i=0;i<max_v;i++)
  51     if(occurrences[i]==0) {
  52       occurrences[i]++;
  53       new_symb[n+to_add]=i;
  54       to_add++;
  55     }
  56   uint new_n = n+to_add;
  57   for(uint i=1;i<=max_v;i++)
  58     occurrences[i] += occurrences[i-1];
  59   uint *oc = new uint[(new_n+1)/W+1];
  60   for(uint i=0;i<(new_n+1)/W+1;i++)
  61     oc[i] = 0;
  62   for(uint i=0;i<=max_v;i++)
  63     bitset(oc,occurrences[i]-1);
  64   bitset(oc,new_n);
  65   occ = bmb->build(oc,new_n+1);
  66   delete [] occurrences;
  67   this->n = new_n;
  68   uint ** _bm=new uint*[height];
  69   for(uint i=0;i<height;i++) {
  70     _bm[i] = new uint[new_n/W+1];
  71     for(uint j=0;j<new_n/W+1;j++)
  72       _bm[i][j]=0;
  73   }
  74   build_level(_bm,new_symb,0,new_n,0);
  75   bitstring = new static_bitsequence*[height];
  76   for(uint i=0;i<height;i++) {
  77         bitstring[i] = bmb->build(_bm[i],new_n);
  78     delete [] _bm[i];
  79   }
  80   delete [] _bm;
  81
  82   if (!deleteSymbols)
  83       for(uint i=0;i<n;i++)
  84           symbols[i] = am->unmap(symbols[i]);
  85
  86 // delete [] new_symb; // already deleted in build_level()!
  87   delete [] oc;
  88 }
  89
  90 static_sequence_wvtree_noptrs::static_sequence_wvtree_noptrs() {
  91 }
  92
  93 static_sequence_wvtree_noptrs::~static_sequence_wvtree_noptrs() {
  94   for(uint i=0;i<height;i++)
  95     delete bitstring[i];
  96   delete [] bitstring;
  97   delete occ;
  98         am->unuse();
  99 }
 100
 101 uint static_sequence_wvtree_noptrs::save(FILE *fp) {
 102   uint wr = WVTREE_NOPTRS_HDR;
 103   wr = fwrite(&wr,sizeof(uint),1,fp);
 104   wr += fwrite(&n,sizeof(uint),1,fp);
 105   wr += fwrite(&max_v,sizeof(uint),1,fp);
 106   wr += fwrite(&height,sizeof(uint),1,fp);
 107   if(wr!=4) return 1;
 108   if(am->save(fp)) return 1;
 109   for(uint i=0;i<height;i++)
 110     if(bitstring[i]->save(fp)) return 1;
 111         if(occ->save(fp)) return 1;
 112   return 0;
 113 }
 114
 115 static_sequence_wvtree_noptrs * static_sequence_wvtree_noptrs::load(FILE *fp) {
 116   uint rd;
 117   if(fread(&rd,sizeof(uint),1,fp)!=1) return NULL;
 118   if(rd!=WVTREE_NOPTRS_HDR) return NULL;
 119   static_sequence_wvtree_noptrs * ret = new static_sequence_wvtree_noptrs();
 120   rd = fread(&ret->n,sizeof(uint),1,fp);
 121   rd += fread(&ret->max_v,sizeof(uint),1,fp);
 122   rd += fread(&ret->height,sizeof(uint),1,fp);
 123   if(rd!=3) {
 124     delete ret;
 125     return NULL;
 126   }
 127   ret->am = alphabet_mapper::load(fp);
 128   if(ret->am==NULL) {
 129     delete ret;
 130     return NULL;
 131   }
 132         ret->am->use();
 133   ret->bitstring = new static_bitsequence*[ret->height];
 134   for(uint i=0;i<ret->height;i++) {
 135     ret->bitstring[i] = static_bitsequence::load(fp);
 136     if(ret->bitstring[i]==NULL){
 137       delete ret;
 138       return NULL;
 139     }
 140   }
 141         ret->occ = static_bitsequence::load(fp);
 142         if(ret->occ==NULL) {
 143                 delete ret;
 144                 return NULL;
 145         }
 146   return ret;
 147 }
 148
 149 uint static_sequence_wvtree_noptrs::access(uint pos) {
 150   uint level=0;
 151   uint ret=0;
 152   uint start=0;
 153   uint end=n-1;
 154   while(level<height) {
 155     assert(pos>=start && pos<=end);
 156     if(bitstring[level]->access(pos)) {
 157       ret=set(ret,level);
 158       pos=bitstring[level]->rank1(pos-1)-bitstring[level]->rank1(start-1);
 159       start=(bitstring[level]->rank1(end)-bitstring[level]->rank1(start-1));
 160       start=end-start+1;
 161       pos+=start;
 162     }
 163     else {
 164       pos=pos-start-(bitstring[level]->rank1(pos)-bitstring[level]->rank1(start-1));
 165       end=end-start-(bitstring[level]->rank1(end)-bitstring[level]->rank1(start-1));
 166       end+=start;
 167       pos+=start;
 168     }
 169     level++;
 170   }
 171   return am->unmap(ret);
 172 }
 173
 174 uint static_sequence_wvtree_noptrs::rank(uint symbol, uint pos) {
 175   symbol = am->map(symbol);
 176   uint level=0;
 177   uint start=0;
 178   uint end=n-1;
 179   uint count=0;
 180   while(level<height) {
 181     if(is_set(symbol,level)) {
 182       pos=bitstring[level]->rank1(pos)-bitstring[level]->rank1(start-1)-1;
 183       count=pos+1;
 184       start=(bitstring[level]->rank1(end)-bitstring[level]->rank1(start-1));
 185       start=end-start+1;
 186       pos+=start;
 187     }
 188     else {
 189       pos=pos-start+bitstring[level]->rank1(start-1)-bitstring[level]->rank1(pos);
 190       count=pos+1;
 191       end=end-start-(bitstring[level]->rank1(end)-bitstring[level]->rank1(start-1));
 192       end+=start;
 193       pos+=start;
 194     }
 195     level++;
 196     if(count==0) return 0;
 197   }
 198   return count;
 199 }
 200
 201 vector<int> static_sequence_wvtree_noptrs::access(uint i, uint j, uint min, uint max)
 202 {
 203     vector<int> resultSet;
 204 //    cout << "height = " << height << endl;
 205     access(resultSet, i, j, am->map(min), am->map(max), 0, 0, 0, n-1);
 206     return resultSet;
 207 }
 208
 209 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)
 210 {
 211     uint symbol = pivot | (1 << (height-l-1));
 212     //std::cout << "At l = " << l << ", [" << i << ", " << j  << "], [" << min << ", " << max << "], [" << start << ", " << end << "], symbol = " << symbol << std::endl;
 213
 214     if (l == height)
 215     {
 216         if (i <= j && pivot >= min && pivot <= max && start <= end)
 217             result.push_back(am->unmap((int)pivot));
 218         return;
 219     }
 220
 221     if (j < i || max < min || end < start)
 222         return;
 223
 224     if (min < symbol)
 225     {
 226         // Recurse left
 227         uint newi = i + bitstring[l]->rank1(start-1) - bitstring[l]->rank1(i-1);
 228         uint newend = end - (bitstring[l]->rank1(end) - bitstring[l]->rank1(start-1));
 229         uint newj = j + bitstring[l]->rank1(start-1) - bitstring[l]->rank1(j) + 1;
 230
 231         uint newmax = max < symbol - 1 ? max : symbol - 1;
 232         if (newj > start)
 233             access(result, newi, newj-1, min, newmax, l+1, pivot, start, newend);
 234     }
 235
 236     if (max >= symbol)
 237     {
 238         // Recurse right
 239         uint newstart = (bitstring[l]->rank1(end)-bitstring[l]->rank1(start-1));
 240         newstart = end - newstart + 1;
 241         uint newi = bitstring[l]->rank1(i-1)-bitstring[l]->rank1(start-1) + newstart;
 242         uint newj = bitstring[l]->rank1(j)-bitstring[l]->rank1(start-1) + newstart;
 243
 244         uint newmin = min > symbol ? min : symbol;
 245         if (newj > newstart)
 246             access(result, newi, newj-1, newmin, max, l+1, symbol, newstart, end);
 247     }
 248 }
 249
 250
 251 vector<int> static_sequence_wvtree_noptrs::accessAll(uint i, uint j)
 252 {
 253     vector<int> resultSet;
 254     if (j < i)
 255         return resultSet;
 256
 257     resultSet.reserve(j-i+1);
 258     accessAll(resultSet, i, j, 0, 0, 0, n-1);
 259     return resultSet;
 260 }
 261
 262 void static_sequence_wvtree_noptrs::accessAll(vector<int> &result, uint i, uint j, uint l, uint pivot, uint start, uint end)
 263 {
 264     uint symbol = pivot | (1 << (height-l-1));
 265 //    std::cout << "At l = " << l << ", [" << i << ", " << j  << "], [" << start << ", " << end << "], symbol = " << symbol << std::endl;
 266
 267     if (l == height)
 268     {
 269         if (i <= j && start <= end)
 270             result.push_back(am->unmap((int)pivot));
 271         return;
 272     }
 273
 274     if (j < i || end < start)
 275         return;
 276
 277     {
 278         // Recurse left
 279         uint newi = i + bitstring[l]->rank1(start-1) - bitstring[l]->rank1(i-1);
 280         uint newend = end - (bitstring[l]->rank1(end) - bitstring[l]->rank1(start-1));
 281         uint newj = j + bitstring[l]->rank1(start-1) - bitstring[l]->rank1(j) + 1;
 282
 283         if (newj > start)
 284             accessAll(result, newi, newj-1, l+1, pivot, start, newend);
 285     }
 286
 287     {
 288         // Recurse right
 289         uint newstart = (bitstring[l]->rank1(end)-bitstring[l]->rank1(start-1));
 290         newstart = end - newstart + 1;
 291         uint newi = bitstring[l]->rank1(i-1)-bitstring[l]->rank1(start-1) + newstart;
 292         uint newj = bitstring[l]->rank1(j)-bitstring[l]->rank1(start-1) + newstart;
 293
 294         if (newj > newstart)
 295             accessAll(result, newi, newj-1, l+1, symbol, newstart, end);
 296     }
 297 }
 298
 299
 300 uint static_sequence_wvtree_noptrs::count(uint i, uint j, uint min, uint max)
 301 {
 302     return count(i, j, am->map(min), am->map(max), 0, 0, 0, n-1);
 303 }
 304
 305 uint static_sequence_wvtree_noptrs::count(uint i, uint j, uint min, uint max, uint l, uint pivot, uint start, uint end)
 306 {
 307     uint symbol = pivot | (1 << (height-l-1));
 308     //std::cout << "At l = " << l << ", [" << i << ", " << j  << "], [" << min << ", " << max << "], [" << start << ", " << end << "], symbol = " << symbol << std::endl;
 309
 310     if (l == height)
 311     {
 312         if (i <= j && pivot >= min && pivot <= max && start <= end)
 313             return 1;
 314         return 0;
 315     }
 316
 317     if (j < i || max < min || end < start)
 318         return 0;
 319
 320     uint result = 0;
 321     if (min < symbol)
 322     {
 323         // Recurse left
 324         uint newi = i + bitstring[l]->rank1(start-1) - bitstring[l]->rank1(i-1);
 325         uint newend = end - (bitstring[l]->rank1(end) - bitstring[l]->rank1(start-1));
 326         uint newj = j + bitstring[l]->rank1(start-1) - bitstring[l]->rank1(j) + 1;
 327
 328         uint newmax = max < symbol - 1 ? max : symbol - 1;
 329         if (newj > start)
 330             result += count(newi, newj-1, min, newmax, l+1, pivot, start, newend);
 331     }
 332
 333     if (max >= symbol)
 334     {
 335         // Recurse right
 336         uint newstart = (bitstring[l]->rank1(end)-bitstring[l]->rank1(start-1));
 337         newstart = end - newstart + 1;
 338         uint newi = bitstring[l]->rank1(i-1)-bitstring[l]->rank1(start-1) + newstart;
 339         uint newj = bitstring[l]->rank1(j)-bitstring[l]->rank1(start-1) + newstart;
 340
 341         uint newmin = min > symbol ? min : symbol;
 342         if (newj > newstart)
 343             result += count(newi, newj-1, newmin, max, l+1, symbol, newstart, end);
 344     }
 345     return result;
 346 }
 347
 348
 349
 350 inline uint get_start(uint symbol, uint mask) {
 351   return symbol&mask;
 352 }
 353
 354 inline uint get_end(uint symbol, uint mask) {
 355   return get_start(symbol,mask)+!mask+1;
 356 }
 357
 358 uint static_sequence_wvtree_noptrs::select(uint symbol, uint j) {
 359   symbol = am->map(symbol);
 360   uint mask = (1<<height)-2;
 361   uint sum=2;
 362   uint level = height-1;
 363   uint pos=j;
 364   while(true) {
 365     uint start = get_start(symbol,mask);
 366     uint end = min(max_v+1,start+sum);
 367     start = (start==0)?0:(occ->select1(start)+1);
 368     end = occ->select1(end+1)-1;
 369     if(is_set(symbol,level)) {
 370       uint ones_start = bitstring[level]->rank1(start-1);
 371       pos = bitstring[level]->select1(ones_start+pos)-start+1;
 372     }
 373     else {
 374       uint ones_start = bitstring[level]->rank1(start-1);
 375       pos = bitstring[level]->select0(start-ones_start+pos)-start+1;
 376     }
 377     mask <<=1;
 378     sum <<=1;
 379     if(level==0) break;
 380     level--;
 381   }
 382   return pos-1;
 383 }
 384
 385 uint static_sequence_wvtree_noptrs::size() {
 386   uint ptrs = sizeof(static_sequence_wvtree_noptrs)+height*sizeof(static_sequence*);
 387   uint bytesBitstrings = 0;
 388   for(uint i=0;i<height;i++)
 389     bytesBitstrings += bitstring[i]->size();
 390   return bytesBitstrings+occ->size()+ptrs;
 391 }
 392
 393 void static_sequence_wvtree_noptrs::build_level(uint **bm, uint *symbols, uint level, uint length, uint offset) {
 394   if(level==height)
 395   {
 396       delete [] symbols;
 397       return;
 398   }
 399   uint cleft=0;
 400   for(uint i=0;i<length;i++)
 401     if(!is_set(symbols[i],level))
 402       cleft++;
 403   uint cright=length-cleft;
 404   uint *left=new uint[cleft], *right=new uint[cright];
 405   cleft=cright=0;
 406   for(uint i=0;i<length;i++)
 407   if(!is_set(symbols[i],level)) {
 408     left[cleft++]=symbols[i];
 409     bitclean(bm[level],offset+i);
 410   }
 411   else {
 412     right[cright++]=symbols[i];
 413     bitset(bm[level],offset+i);
 414   }
 415
 416   delete [] symbols;
 417   symbols = 0;
 418
 419   build_level(bm,left,level+1,cleft,offset);
 420   left = 0; // Gets deleted in recursion.
 421   build_level(bm,right,level+1,cright,offset+cleft);
 422   right = 0; // Gets deleted in recursion.
 423   //delete [] left;
 424   //delete [] right;
 425 }
 426
 427 uint static_sequence_wvtree_noptrs::max_value(uint *symbols, uint n) {
 428   uint max_v = 0;
 429   for(uint i=0;i<n;i++)
 430     max_v = max(symbols[i],max_v);
 431   return max_v;
 432 }
 433
 434 uint static_sequence_wvtree_noptrs::bits(uint val) {
 435   uint ret = 0;
 436   while(val!=0) {
 437     ret++;
 438     val >>= 1;
 439   }
 440   return ret;
 441 }
 442
 443 bool static_sequence_wvtree_noptrs::is_set(uint val, uint ind) {
 444   assert(ind<height);
 445   return (val & (1<<(height-ind-1)))!=0;
 446 }
 447
 448
 449 uint static_sequence_wvtree_noptrs::set(uint val, uint ind) {
 450   assert(ind<=height);
 451   return val | (1<<(height-ind-1));
 452 }