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   RLEVector::Iterator* first_iter = 0;
  68   RLEVector::Iterator* second_iter = 0;
  69
  70   pair_type first_run;
  71   bool first_finished;
  72   if(first == 0)
  73   {
  74     first_run = pair_type(size, 0);
  75     first_finished = true;
  76   }
  77   else
  78   {
  79     first_iter = new RLEVector::Iterator(*first);
  80     first_run = first_iter->selectRun(0, size);
  81     first_run.second++;
  82     first_finished = false;
  83   }
  84
  85   usint second_bit;
  86   if(second == 0)
  87   {
  88     second_bit = n;
  89   }
  90   else
  91   {
  92     second_iter = new RLEVector::Iterator(*second);
  93     second_bit = second_iter->select(0);
  94   }
  95
  96   RLEEncoder encoder(block_size);
  97   pair_type run = pair_type(size, 0);
  98   for(usint i = 0; i < n; i++, first_run.first++)
  99   {
 100     while(!first_finished && first_run.first < positions[i])
 101     {
 102       handleRun(encoder, run, first_run, positions[i]);
 103       if(first_run.second == 0)
 104       {
 105         if(first_iter->hasNext())
 106         {
 107           first_run = first_iter->selectNextRun(size);
 108           first_run.first += i;
 109           first_run.second++;
 110         }
 111         else
 112         {
 113           first_finished = true;
 114         }
 115       }
 116     }
 117
 118     if(i == second_bit) // positions[i] is one
 119     {
 120       handleOne(encoder, run, positions[i]);
 121       second_bit = second_iter->selectNext();
 122     }
 123     else  // positions[i] is zero
 124     {
 125       if(run.second != 0)
 126       {
 127         encoder.setRun(run.first, run.second);
 128         run.second = 0;
 129       }
 130     }
 131   }
 132
 133   while(!first_finished)
 134   {
 135     handleRun(encoder, run, first_run, size);
 136     if(first_iter->hasNext())
 137     {
 138       first_run = first_iter->selectNextRun(size);
 139       first_run.first += n;
 140       first_run.second++;
 141     }
 142     else { break; }
 143   }
 144
 145   if(run.second != 0)
 146   {
 147     encoder.setRun(run.first, run.second);
 148   }
 149
 150   delete first_iter; delete second_iter;
 151   delete first; delete second;
 152   return new RLEVector(encoder, size);
 153 }
 154
 155 //--------------------------------------------------------------------------
 156
 157 DeltaVector*
 158 mergeVectors(DeltaVector* first, DeltaVector* second, usint* positions, usint n, usint size, usint block_size)
 159 {
 160   if((first == 0 && second == 0) || positions == 0) { return 0; }
 161
 162   DeltaVector::Iterator* first_iter = 0;
 163   DeltaVector::Iterator* second_iter = 0;
 164
 165   usint first_bit;
 166   bool first_finished;
 167   if(first == 0)
 168   {
 169     first_bit = 0;
 170     first_finished = true;
 171   }
 172   else
 173   {
 174     first_iter = new DeltaVector::Iterator(*first);
 175     first_bit = first_iter->select(0);
 176     first_finished = false;
 177   }
 178
 179   usint second_bit;
 180   if(second == 0)
 181   {
 182     second_bit = n;
 183   }
 184   else
 185   {
 186     second_iter = new DeltaVector::Iterator(*second);
 187     second_bit = second_iter->select(0);
 188   }
 189
 190   DeltaEncoder encoder(block_size);
 191   for(usint i = 0; i < n; i++, first_bit++)
 192   {
 193     while(!first_finished && first_bit < positions[i])
 194     {
 195       encoder.setBit(first_bit);
 196       if(first_iter->hasNext())
 197       {
 198         first_bit = first_iter->selectNext() + i;
 199       }
 200       else
 201       {
 202         first_finished = true;
 203       }
 204     }
 205
 206     if(i == second_bit) // positions[i] is one
 207     {
 208       encoder.setBit(positions[i]);
 209       second_bit = second_iter->selectNext();
 210     }
 211   }
 212
 213   while(!first_finished)
 214   {
 215     encoder.setBit(first_bit);
 216     if(!first_iter->hasNext()) { break; }
 217     first_bit = first_iter->selectNext() + n;
 218   }
 219
 220   delete first_iter; delete second_iter;
 221   delete first; delete second;
 222   return new DeltaVector(encoder, size);
 223 }
 224
 225
 226 } // namespace CSA