incbwt/bits/vectors.h

   1 #ifndef VECTORS_H
   2 #define VECTORS_H
   3
   4
   5 namespace CSA
   6 {
   7
   8
   9 /*
  10   These functions merge two vectors using marked positions.
  11   The original vectors are deleted.
  12 */
  13
  14 template<class V, class E>
  15 void
  16 handleOne(E& 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
  35 template<class V, class E>
  36 void
  37 handleRun(E& encoder, pair_type& run, pair_type& next, usint limit)
  38 {
  39   if(run.second == 0)
  40   {
  41     run.first = next.first;
  42     run.second = std::min(limit - run.first, next.second);
  43     next.first += run.second;
  44     next.second -= run.second;
  45     return;
  46   }
  47
  48   if(next.first == run.first + run.second)
  49   {
  50     usint cont = std::min(limit - next.first, next.second);
  51     run.second += cont;
  52     next.first += cont;
  53     next.second -= cont;
  54     return;
  55   }
  56
  57   encoder.setRun(run.first, run.second);
  58   run.first = next.first;
  59   run.second = std::min(limit - run.first, next.second);;
  60   next.first += run.second;
  61   next.second -= run.second;
  62 }
  63
  64
  65 template<class V, class E, class I>
  66 V*
  67 mergeVectors(V* first, V* second, usint* positions, usint n, usint size, usint block_size)
  68 {
  69   if((first == 0 && second == 0) || positions == 0) { return 0; }
  70
  71   I* first_iter = 0;
  72   I* second_iter = 0;
  73
  74   pair_type first_run;
  75   bool first_finished;
  76   if(first == 0)
  77   {
  78     first_run = pair_type(size, 0);
  79     first_finished = true;
  80   }
  81   else
  82   {
  83     first_iter = new I(*first);
  84     first_run = first_iter->selectRun(0, size);
  85     first_run.second++;
  86     first_finished = false;
  87   }
  88
  89   usint second_bit;
  90   if(second == 0)
  91   {
  92     second_bit = n;
  93   }
  94   else
  95   {
  96     second_iter = new I(*second);
  97     second_bit = second_iter->select(0);
  98   }
  99
 100   E encoder(block_size);
 101   pair_type run = pair_type(size, 0);
 102   for(usint i = 0; i < n; i++, first_run.first++)
 103   {
 104     while(!first_finished && first_run.first < positions[i])
 105     {
 106       handleRun<V, E>(encoder, run, first_run, positions[i]);
 107       if(first_run.second == 0)
 108       {
 109         if(first_iter->hasNext())
 110         {
 111           first_run = first_iter->selectNextRun(size);
 112           first_run.first += i;
 113           first_run.second++;
 114         }
 115         else
 116         {
 117           first_finished = true;
 118         }
 119       }
 120     }
 121
 122     if(i == second_bit) // positions[i] is one
 123     {
 124       handleOne<V, E>(encoder, run, positions[i]);
 125       second_bit = second_iter->selectNext();
 126     }
 127     else  // positions[i] is zero
 128     {
 129       if(run.second != 0)
 130       {
 131         encoder.setRun(run.first, run.second);
 132         run.second = 0;
 133       }
 134     }
 135   }
 136
 137   while(!first_finished)
 138   {
 139     handleRun<V, E>(encoder, run, first_run, size);
 140     if(first_iter->hasNext())
 141     {
 142       first_run = first_iter->selectNextRun(size);
 143       first_run.first += n;
 144       first_run.second++;
 145     }
 146     else { break; }
 147   }
 148
 149   if(run.second != 0)
 150   {
 151     encoder.setRun(run.first, run.second);
 152   }
 153
 154   delete first_iter; delete second_iter;
 155   delete first; delete second;
 156   return new V(encoder, size);
 157 }
 158
 159
 160 } // namespace CSA
 161
 162
 163 #endif // VECTORS_H