incbwt/bits/vectors.cpp

   1 #include <algorithm>
   2 #include <cstdlib>
   3 #include <ctime>
   4 #include <fstream>
   5 #include <iostream>
   6
   7 #include "vectors.h"
   8 #include "../misc/utils.h"
   9
  10
  11 namespace CSA
  12 {
  13
  14
  15 inline void
  16 handleOne(RLEEncoder& encoder, pair_type& run, usint position)
  17 {
  18   if(run.second == 0)
  19   {
  20     run.first = position;
  21     run.second = 1;
  22     return;
  23   }
  24   if(position == run.first + run.second)
  25   {
  26     run.second++;
  27     return;
  28   }
  29   encoder.setRun(run.first, run.second);
  30   run.first = position;
  31   run.second = 1;
  32 }
  33
  34 inline void
  35 handleRun(RLEEncoder& encoder, pair_type& run, pair_type& next, usint limit)
  36 {
  37   if(run.second == 0)
  38   {
  39     run.first = next.first;
  40     run.second = std::min(limit - run.first, next.second);
  41     next.first += run.second;
  42     next.second -= run.second;
  43     return;
  44   }
  45
  46   if(next.first == run.first + run.second)
  47   {
  48     usint cont = std::min(limit - next.first, next.second);
  49     run.second += cont;
  50     next.first += cont;
  51     next.second -= cont;
  52     return;
  53   }
  54
  55   encoder.setRun(run.first, run.second);
  56   run.first = next.first;
  57   run.second = std::min(limit - run.first, next.second);;
  58   next.first += run.second;
  59   next.second -= run.second;
  60 }
  61
  62 RLEVector*
  63 mergeVectors(RLEVector* first, RLEVector* second, usint* positions, usint n, usint size, usint block_size)
  64 {
  65   if((first == 0 && second == 0) || positions == 0) { return 0; }
  66
  67   pair_type first_run;
  68   bool first_finished;
  69   if(first == 0)
  70   {
  71     first_run = pair_type(size, 0);
  72     first_finished = true;
  73   }
  74   else
  75   {
  76     first_run = first->selectRun(0, size);
  77     first_run.second++;
  78     first_finished = false;
  79   }
  80
  81   usint second_bit;
  82   if(second == 0)
  83   {
  84     second_bit = n;
  85   }
  86   else
  87   {
  88     second_bit = second->select(0);
  89   }
  90
  91   RLEEncoder encoder(block_size);
  92   pair_type run = pair_type(size, 0);
  93   for(usint i = 0; i < n; i++, first_run.first++)
  94   {
  95     while(!first_finished && first_run.first < positions[i])
  96     {
  97       handleRun(encoder, run, first_run, positions[i]);
  98       if(first_run.second == 0)
  99       {
 100         if(first->hasNext())
 101         {
 102           first_run = first->selectNextRun(size);
 103           first_run.first += i;
 104           first_run.second++;
 105         }
 106         else
 107         {
 108           first_finished = true;
 109         }
 110       }
 111     }
 112
 113     if(i == second_bit) // positions[i] is one
 114     {
 115       handleOne(encoder, run, positions[i]);
 116       second_bit = second->selectNext();
 117     }
 118     else  // positions[i] is zero
 119     {
 120       if(run.second != 0)
 121       {
 122         encoder.setRun(run.first, run.second);
 123         run.second = 0;
 124       }
 125     }
 126   }
 127
 128   while(!first_finished)
 129   {
 130     handleRun(encoder, run, first_run, size);
 131     if(first->hasNext())
 132     {
 133       first_run = first->selectNextRun(size);
 134       first_run.first += n;
 135       first_run.second++;
 136     }
 137     else { break; }
 138   }
 139
 140   if(run.second != 0)
 141   {
 142     encoder.setRun(run.first, run.second);
 143   }
 144
 145   delete first; delete second;
 146   return new RLEVector(encoder, size);
 147 }
 148
 149 //--------------------------------------------------------------------------
 150
 151 DeltaVector*
 152 mergeVectors(DeltaVector* first, DeltaVector* second, usint* positions, usint n, usint size, usint block_size)
 153 {
 154   if((first == 0 && second == 0) || positions == 0) { return 0; }
 155
 156   usint first_bit;
 157   bool first_finished;
 158   if(first == 0)
 159   {
 160     first_bit = 0;
 161     first_finished = true;
 162   }
 163   else
 164   {
 165     first_bit = first->select(0);
 166     first_finished = false;
 167   }
 168
 169   usint second_bit;
 170   if(second == 0)
 171   {
 172     second_bit = n;
 173   }
 174   else
 175   {
 176     second_bit = second->select(0);
 177   }
 178
 179   DeltaEncoder encoder(block_size);
 180   for(usint i = 0; i < n; i++, first_bit++)
 181   {
 182     while(!first_finished && first_bit < positions[i])
 183     {
 184       encoder.setBit(first_bit);
 185       if(first->hasNext())
 186       {
 187         first_bit = first->selectNext() + i;
 188       }
 189       else
 190       {
 191         first_finished = true;
 192       }
 193     }
 194
 195     if(i == second_bit) // positions[i] is one
 196     {
 197       encoder.setBit(positions[i]);
 198       second_bit = second->selectNext();
 199     }
 200   }
 201
 202   while(!first_finished)
 203   {
 204     encoder.setBit(first_bit);
 205     if(!first->hasNext()) { break; }
 206     first_bit = first->selectNext() + n;
 207   }
 208
 209   delete first; delete second;
 210   return new DeltaVector(encoder, size);
 211 }
 212
 213
 214 } // namespace CSA