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 using std::min;
  24 using std::max;
  25 static_sequence_wvtree_noptrs::static_sequence_wvtree_noptrs(uint * symbols, uint n, static_bitsequence_builder * bmb, alphabet_mapper * am, bool deleteSymbols) {
  26   this->n=n;
  27   this->am=am;
  28         am->use();
  29   for(uint i=0;i<n;i++)
  30     symbols[i] = am->map(symbols[i]);
  31   max_v=max_value(symbols,n);
  32   height=bits(max_v);
  33   uint *occurrences=new uint[max_v+1];
  34   for(uint i=0;i<=max_v;i++) occurrences[i]=0;
  35   for(uint i=0;i<n;i++)
  36     occurrences[symbols[i]]++;
  37   uint to_add=0;
  38   for(uint i=0;i<max_v;i++)
  39     if(occurrences[i]==0) to_add++;
  40   uint * new_symb = new uint[n+to_add];
  41   for(uint i=0;i<n;i++)
  42     new_symb[i] = symbols[i];
  43
  44   if (deleteSymbols)
  45   {
  46       delete [] symbols;
  47       symbols = 0;
  48   }
  49
  50   to_add = 0;
  51   for(uint i=0;i<max_v;i++)
  52     if(occurrences[i]==0) {
  53       occurrences[i]++;
  54       new_symb[n+to_add]=i;
  55       to_add++;
  56     }
  57   uint new_n = n+to_add;
  58   for(uint i=1;i<=max_v;i++)
  59     occurrences[i] += occurrences[i-1];
  60   uint *oc = new uint[(new_n+1)/W+1];
  61   for(uint i=0;i<(new_n+1)/W+1;i++)
  62     oc[i] = 0;
  63   for(uint i=0;i<=max_v;i++)
  64     bitset(oc,occurrences[i]-1);
  65   bitset(oc,new_n);
  66   occ = bmb->build(oc,new_n+1);
  67   delete [] occurrences;
  68   this->n = new_n;
  69   uint ** _bm=new uint*[height];
  70   for(uint i=0;i<height;i++) {
  71     _bm[i] = new uint[new_n/W+1];
  72     for(uint j=0;j<new_n/W+1;j++)
  73       _bm[i][j]=0;
  74   }
  75   build_level(_bm,new_symb,0,new_n,0);
  76   bitstring = new static_bitsequence*[height];
  77   for(uint i=0;i<height;i++) {
  78         bitstring[i] = bmb->build(_bm[i],new_n);
  79     delete [] _bm[i];
  80   }
  81   delete [] _bm;
  82
  83   if (!deleteSymbols)
  84       for(uint i=0;i<n;i++)
  85           symbols[i] = am->unmap(symbols[i]);
  86
  87 // delete [] new_symb; // already deleted in build_level()!
  88   delete [] oc;
  89 }
  90
  91 // symbols is an array of elements of "width" bits
  92 static_sequence_wvtree_noptrs::static_sequence_wvtree_noptrs(uint * symbols, uint n, unsigned width, static_bitsequence_builder * bmb, alphabet_mapper * am, bool deleteSymbols) {
  93   this->n=n;
  94   this->am=am;
  95         am->use();
  96   for(uint i=0;i<n;i++)
  97       set_field(symbols, width, i, am->map(get_field(symbols, width, i)));
  98   max_v=max_value(symbols, width, n);
  99   height=bits(max_v);
 100   uint *occurrences=new uint[max_v+1];
 101   for(uint i=0;i<=max_v;i++) occurrences[i]=0;
 102   for(uint i=0;i<n;i++)
 103       occurrences[get_field(symbols, width, i)]++;
 104   uint to_add=0;
 105   for(uint i=0;i<max_v;i++)
 106     if(occurrences[i]==0) to_add++;
 107   uint * new_symb = new uint[((n+to_add)*width)/W + 1];
 108   for(uint i=0;i<n;i++)
 109       set_field(new_symb, width, i, get_field(symbols, width, i));
 110
 111   if (deleteSymbols)
 112   {
 113       delete [] symbols;
 114       symbols = 0;
 115   }
 116
 117   to_add = 0;
 118   for(uint i=0;i<max_v;i++)
 119     if(occurrences[i]==0) {
 120       occurrences[i]++;
 121       set_field(new_symb, width, n+to_add, i);
 122       to_add++;
 123     }
 124   uint new_n = n+to_add;
 125   for(uint i=1;i<=max_v;i++)
 126     occurrences[i] += occurrences[i-1];
 127   uint *oc = new uint[(new_n+1)/W+1];
 128   for(uint i=0;i<(new_n+1)/W+1;i++)
 129     oc[i] = 0;
 130   for(uint i=0;i<=max_v;i++)
 131     bitset(oc,occurrences[i]-1);
 132   bitset(oc,new_n);
 133   occ = bmb->build(oc,new_n+1);
 134   delete [] occurrences;
 135   this->n = new_n;
 136   uint ** _bm=new uint*[height];
 137   for(uint i=0;i<height;i++) {
 138     _bm[i] = new uint[new_n/W+1];
 139     for(uint j=0;j<new_n/W+1;j++)
 140       _bm[i][j]=0;
 141   }
 142   build_level(_bm,new_symb,width,0,new_n,0);
 143   bitstring = new static_bitsequence*[height];
 144   for(uint i=0;i<height;i++) {
 145         bitstring[i] = bmb->build(_bm[i],new_n);
 146     delete [] _bm[i];
 147   }
 148   delete [] _bm;
 149
 150   if (!deleteSymbols)
 151       for(uint i=0;i<n;i++)
 152           set_field(symbols, width, i, am->unmap(get_field(symbols, width, i)));
 153
 154 // delete [] new_symb; // already deleted in build_level()!
 155   delete [] oc;
 156 }
 157
 158 static_sequence_wvtree_noptrs::static_sequence_wvtree_noptrs() {
 159 }
 160
 161 static_sequence_wvtree_noptrs::~static_sequence_wvtree_noptrs() {
 162   for(uint i=0;i<height;i++)
 163     delete bitstring[i];
 164   delete [] bitstring;
 165   delete occ;
 166         am->unuse();
 167 }
 168
 169 uint static_sequence_wvtree_noptrs::save(FILE *fp) {
 170   uint wr = WVTREE_NOPTRS_HDR;
 171   wr = fwrite(&wr,sizeof(uint),1,fp);
 172   wr += fwrite(&n,sizeof(uint),1,fp);
 173   wr += fwrite(&max_v,sizeof(uint),1,fp);
 174   wr += fwrite(&height,sizeof(uint),1,fp);
 175   if(wr!=4) return 1;
 176   if(am->save(fp)) return 1;
 177   for(uint i=0;i<height;i++)
 178     if(bitstring[i]->save(fp)) return 1;
 179         if(occ->save(fp)) return 1;
 180   return 0;
 181 }
 182
 183 static_sequence_wvtree_noptrs * static_sequence_wvtree_noptrs::load(FILE *fp) {
 184   uint rd;
 185   if(fread(&rd,sizeof(uint),1,fp)!=1) return NULL;
 186   if(rd!=WVTREE_NOPTRS_HDR) return NULL;
 187   static_sequence_wvtree_noptrs * ret = new static_sequence_wvtree_noptrs();
 188   rd = fread(&ret->n,sizeof(uint),1,fp);
 189   rd += fread(&ret->max_v,sizeof(uint),1,fp);
 190   rd += fread(&ret->height,sizeof(uint),1,fp);
 191   if(rd!=3) {
 192     delete ret;
 193     return NULL;
 194   }
 195   ret->am = alphabet_mapper::load(fp);
 196   if(ret->am==NULL) {
 197     delete ret;
 198     return NULL;
 199   }
 200         ret->am->use();
 201   ret->bitstring = new static_bitsequence*[ret->height];
 202   for(uint i=0;i<ret->height;i++) {
 203     ret->bitstring[i] = static_bitsequence::load(fp);
 204     if(ret->bitstring[i]==NULL){
 205       delete ret;
 206       return NULL;
 207     }
 208   }
 209         ret->occ = static_bitsequence::load(fp);
 210         if(ret->occ==NULL) {
 211                 delete ret;
 212                 return NULL;
 213         }
 214   return ret;
 215 }
 216
 217 uint static_sequence_wvtree_noptrs::access(uint pos) {
 218   uint level=0;
 219   uint ret=0;
 220   uint start=0;
 221   uint end=n-1;
 222   while(level<height) {
 223     assert(pos>=start && pos<=end);
 224     if(bitstring[level]->access(pos)) {
 225       ret=set(ret,level);
 226       pos=bitstring[level]->rank1(pos-1)-bitstring[level]->rank1(start-1);
 227       start=(bitstring[level]->rank1(end)-bitstring[level]->rank1(start-1));
 228       start=end-start+1;
 229       pos+=start;
 230     }
 231     else {
 232       pos=pos-start-(bitstring[level]->rank1(pos)-bitstring[level]->rank1(start-1));
 233       end=end-start-(bitstring[level]->rank1(end)-bitstring[level]->rank1(start-1));
 234       end+=start;
 235       pos+=start;
 236     }
 237     level++;
 238   }
 239   return am->unmap(ret);
 240 }
 241
 242 uint static_sequence_wvtree_noptrs::rank(uint symbol, uint pos) {
 243   symbol = am->map(symbol);
 244   uint level=0;
 245   uint start=0;
 246   uint end=n-1;
 247   uint count=0;
 248   while(level<height) {
 249     if(is_set(symbol,level)) {
 250       pos=bitstring[level]->rank1(pos)-bitstring[level]->rank1(start-1)-1;
 251       count=pos+1;
 252       start=(bitstring[level]->rank1(end)-bitstring[level]->rank1(start-1));
 253       start=end-start+1;
 254       pos+=start;
 255     }
 256     else {
 257       pos=pos-start+bitstring[level]->rank1(start-1)-bitstring[level]->rank1(pos);
 258       count=pos+1;
 259       end=end-start-(bitstring[level]->rank1(end)-bitstring[level]->rank1(start-1));
 260       end+=start;
 261       pos+=start;
 262     }
 263     level++;
 264     if(count==0) return 0;
 265   }
 266   return count;
 267 }
 268
 269 vector<int> static_sequence_wvtree_noptrs::access(uint i, uint j, uint min, uint max)
 270 {
 271     vector<int> resultSet;
 272 //    cout << "height = " << height << endl;
 273     access(resultSet, i, j, am->map(min), am->map(max), 0, 0, 0, n-1);
 274     return resultSet;
 275 }
 276
 277 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)
 278 {
 279     uint symbol = pivot | (1 << (height-l-1));
 280     //std::cout << "At l = " << l << ", [" << i << ", " << j  << "], [" << min << ", " << max << "], [" << start << ", " << end << "], symbol = " << symbol << std::endl;
 281
 282     if (l == height)
 283     {
 284         if (i <= j && pivot >= min && pivot <= max && start <= end)
 285             result.push_back(am->unmap((int)pivot));
 286         return;
 287     }
 288
 289     if (j < i || max < min || end < start)
 290         return;
 291
 292     if (min < symbol)
 293     {
 294         // Recurse left
 295         uint newi = i + bitstring[l]->rank1(start-1) - bitstring[l]->rank1(i-1);
 296         uint newend = end - (bitstring[l]->rank1(end) - bitstring[l]->rank1(start-1));
 297         uint newj = j + bitstring[l]->rank1(start-1) - bitstring[l]->rank1(j) + 1;
 298
 299         uint newmax = max < symbol - 1 ? max : symbol - 1;
 300         if (newj > start)
 301             access(result, newi, newj-1, min, newmax, l+1, pivot, start, newend);
 302     }
 303
 304     if (max >= symbol)
 305     {
 306         // Recurse right
 307         uint newstart = (bitstring[l]->rank1(end)-bitstring[l]->rank1(start-1));
 308         newstart = end - newstart + 1;
 309         uint newi = bitstring[l]->rank1(i-1)-bitstring[l]->rank1(start-1) + newstart;
 310         uint newj = bitstring[l]->rank1(j)-bitstring[l]->rank1(start-1) + newstart;
 311
 312         uint newmin = min > symbol ? min : symbol;
 313         if (newj > newstart)
 314             access(result, newi, newj-1, newmin, max, l+1, symbol, newstart, end);
 315     }
 316 }
 317
 318
 319 vector<int> static_sequence_wvtree_noptrs::accessAll(uint i, uint j)
 320 {
 321     vector<int> resultSet;
 322     if (j < i)
 323         return resultSet;
 324
 325     resultSet.reserve(j-i+1);
 326     accessAll(resultSet, i, j, 0, 0, 0, n-1);
 327     return resultSet;
 328 }
 329
 330 void static_sequence_wvtree_noptrs::accessAll(vector<int> &result, uint i, uint j, uint l, uint pivot, uint start, uint end)
 331 {
 332     uint symbol = pivot | (1 << (height-l-1));
 333 //    std::cout << "At l = " << l << ", [" << i << ", " << j  << "], [" << start << ", " << end << "], symbol = " << symbol << std::endl;
 334
 335     if (l == height)
 336     {
 337         if (i <= j && start <= end)
 338             result.push_back(am->unmap((int)pivot));
 339         return;
 340     }
 341
 342     if (j < i || end < start)
 343         return;
 344
 345     {
 346         // Recurse left
 347         uint newi = i + bitstring[l]->rank1(start-1) - bitstring[l]->rank1(i-1);
 348         uint newend = end - (bitstring[l]->rank1(end) - bitstring[l]->rank1(start-1));
 349         uint newj = j + bitstring[l]->rank1(start-1) - bitstring[l]->rank1(j) + 1;
 350
 351         if (newj > start)
 352             accessAll(result, newi, newj-1, l+1, pivot, start, newend);
 353     }
 354
 355     {
 356         // Recurse right
 357         uint newstart = (bitstring[l]->rank1(end)-bitstring[l]->rank1(start-1));
 358         newstart = end - newstart + 1;
 359         uint newi = bitstring[l]->rank1(i-1)-bitstring[l]->rank1(start-1) + newstart;
 360         uint newj = bitstring[l]->rank1(j)-bitstring[l]->rank1(start-1) + newstart;
 361
 362         if (newj > newstart)
 363             accessAll(result, newi, newj-1, l+1, symbol, newstart, end);
 364     }
 365 }
 366
 367
 368 uint static_sequence_wvtree_noptrs::count(uint i, uint j, uint min, uint max)
 369 {
 370     return count(i, j, am->map(min), am->map(max), 0, 0, 0, n-1);
 371 }
 372
 373 uint static_sequence_wvtree_noptrs::count(uint i, uint j, uint min, uint max, uint l, uint pivot, uint start, uint end)
 374 {
 375     uint symbol = pivot | (1 << (height-l-1));
 376     //std::cout << "At l = " << l << ", [" << i << ", " << j  << "], [" << min << ", " << max << "], [" << start << ", " << end << "], symbol = " << symbol << std::endl;
 377
 378     if (l == height)
 379     {
 380         if (i <= j && pivot >= min && pivot <= max && start <= end)
 381             return 1;
 382         return 0;
 383     }
 384
 385     if (j < i || max < min || end < start)
 386         return 0;
 387
 388     uint result = 0;
 389     if (min < symbol)
 390     {
 391         // Recurse left
 392         uint newi = i + bitstring[l]->rank1(start-1) - bitstring[l]->rank1(i-1);
 393         uint newend = end - (bitstring[l]->rank1(end) - bitstring[l]->rank1(start-1));
 394         uint newj = j + bitstring[l]->rank1(start-1) - bitstring[l]->rank1(j) + 1;
 395
 396         uint newmax = max < symbol - 1 ? max : symbol - 1;
 397         if (newj > start)
 398             result += count(newi, newj-1, min, newmax, l+1, pivot, start, newend);
 399     }
 400
 401     if (max >= symbol)
 402     {
 403         // Recurse right
 404         uint newstart = (bitstring[l]->rank1(end)-bitstring[l]->rank1(start-1));
 405         newstart = end - newstart + 1;
 406         uint newi = bitstring[l]->rank1(i-1)-bitstring[l]->rank1(start-1) + newstart;
 407         uint newj = bitstring[l]->rank1(j)-bitstring[l]->rank1(start-1) + newstart;
 408
 409         uint newmin = min > symbol ? min : symbol;
 410         if (newj > newstart)
 411             result += count(newi, newj-1, newmin, max, l+1, symbol, newstart, end);
 412     }
 413     return result;
 414 }
 415
 416
 417
 418 inline uint get_start(uint symbol, uint mask) {
 419   return symbol&mask;
 420 }
 421
 422 inline uint get_end(uint symbol, uint mask) {
 423   return get_start(symbol,mask)+!mask+1;
 424 }
 425
 426 uint static_sequence_wvtree_noptrs::select(uint symbol, uint j) {
 427   symbol = am->map(symbol);
 428   uint mask = (1<<height)-2;
 429   uint sum=2;
 430   uint level = height-1;
 431   uint pos=j;
 432   while(true) {
 433     uint start = get_start(symbol,mask);
 434     uint end = min(max_v+1,start+sum);
 435     start = (start==0)?0:(occ->select1(start)+1);
 436     end = occ->select1(end+1)-1;
 437     if(is_set(symbol,level)) {
 438       uint ones_start = bitstring[level]->rank1(start-1);
 439       pos = bitstring[level]->select1(ones_start+pos)-start+1;
 440     }
 441     else {
 442       uint ones_start = bitstring[level]->rank1(start-1);
 443       pos = bitstring[level]->select0(start-ones_start+pos)-start+1;
 444     }
 445     mask <<=1;
 446     sum <<=1;
 447     if(level==0) break;
 448     level--;
 449   }
 450   return pos-1;
 451 }
 452
 453 uint static_sequence_wvtree_noptrs::size() {
 454   uint ptrs = sizeof(static_sequence_wvtree_noptrs)+height*sizeof(static_sequence*);
 455   uint bytesBitstrings = 0;
 456   for(uint i=0;i<height;i++)
 457     bytesBitstrings += bitstring[i]->size();
 458   return bytesBitstrings+occ->size()+ptrs;
 459 }
 460
 461 void static_sequence_wvtree_noptrs::build_level(uint **bm, uint *symbols, uint level, uint length, uint offset) {
 462   if(level==height)
 463   {
 464       delete [] symbols;
 465       return;
 466   }
 467   uint cleft=0;
 468   for(uint i=0;i<length;i++)
 469     if(!is_set(symbols[i],level))
 470       cleft++;
 471   uint cright=length-cleft;
 472   uint *left=new uint[cleft], *right=new uint[cright];
 473   cleft=cright=0;
 474   for(uint i=0;i<length;i++)
 475   if(!is_set(symbols[i],level)) {
 476     left[cleft++]=symbols[i];
 477     bitclean(bm[level],offset+i);
 478   }
 479   else {
 480     right[cright++]=symbols[i];
 481     bitset(bm[level],offset+i);
 482   }
 483
 484   delete [] symbols;
 485   symbols = 0;
 486
 487   build_level(bm,left,level+1,cleft,offset);
 488   left = 0; // Gets deleted in recursion.
 489   build_level(bm,right,level+1,cright,offset+cleft);
 490   right = 0; // Gets deleted in recursion.
 491   //delete [] left;
 492   //delete [] right;
 493 }
 494
 495 // symbols is an array of elements of "width" bits.
 496 void static_sequence_wvtree_noptrs::build_level(uint **bm, uint *symbols, unsigned width, uint level, uint length, uint offset) {
 497     if(level==height)
 498     {
 499         delete [] symbols;
 500         return;
 501     }
 502     uint cleft=0;
 503     for(uint i=0;i<length;i++)
 504         if(!is_set(get_field(symbols, width, i),level))
 505             cleft++;
 506     uint cright=length-cleft;
 507     uint *left=new uint[(cleft*width)/W + 1],
 508         *right=new uint[(cright*width)/W + 1];
 509     cleft=cright=0;
 510     for(uint i=0;i<length;i++)
 511         if(!is_set(get_field(symbols,width,i),level)) {
 512             set_field(left,width,cleft++,get_field(symbols, width,i));
 513             bitclean(bm[level],offset+i);
 514         }
 515         else {
 516             set_field(right,width,cright++,get_field(symbols,width,i));
 517             bitset(bm[level],offset+i);
 518         }
 519
 520     delete [] symbols;
 521     symbols = 0;
 522
 523     build_level(bm,left,width,level+1,cleft,offset);
 524     left = 0; // Gets deleted in recursion.
 525     build_level(bm,right,width,level+1,cright,offset+cleft);
 526     right = 0; // Gets deleted in recursion.
 527     //delete [] left;
 528     //delete [] right;
 529 }
 530
 531 uint static_sequence_wvtree_noptrs::max_value(uint *symbols, uint n) {
 532   uint max_v = 0;
 533   for(uint i=0;i<n;i++)
 534     max_v = max(symbols[i],max_v);
 535   return max_v;
 536 }
 537
 538 uint static_sequence_wvtree_noptrs::max_value(uint *symbols, unsigned width, uint n) {
 539   uint max_v = 0;
 540   for(uint i=0;i<n;i++)
 541       max_v = max(get_field(symbols, width, i),max_v);
 542   return max_v;
 543 }
 544
 545 uint static_sequence_wvtree_noptrs::bits(uint val) {
 546   uint ret = 0;
 547   while(val!=0) {
 548     ret++;
 549     val >>= 1;
 550   }
 551   return ret;
 552 }
 553
 554 bool static_sequence_wvtree_noptrs::is_set(uint val, uint ind) {
 555   assert(ind<height);
 556   return (val & (1<<(height-ind-1)))!=0;
 557 }
 558
 559
 560 uint static_sequence_wvtree_noptrs::set(uint val, uint ind) {
 561   assert(ind<=height);
 562   return val | (1<<(height-ind-1));
 563 }