tools/bwt/dcs-bwt/src/difference_cover-inl.h

   1 // Copyright 2007 Google Inc.
   2
   3 // This program is free software; you can redistribute it and/or
   4 // modify it under the terms of the GNU General Public License
   5 // as published by the Free Software Foundation; either version 2
   6 // of the License, or (at your option) any later version.
   7
   8 // This program is distributed in the hope that it will be useful,
   9 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  10 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  11 // GNU General Public License for more details.
  12
  13 // You should have received a copy of the GNU General Public License
  14 // along with this program; if not, write to the Free Software
  15 // Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
  16
  17 #ifndef DCSBWT_DIFFERENCE_COVER_INL_H__
  18 #define DCSBWT_DIFFERENCE_COVER_INL_H__
  19
  20 #include "difference_cover.h"
  21
  22 #include <cassert>     // for assert
  23
  24 #include <algorithm>   // for transform
  25 #include <functional>  // for bind2nd, plus
  26
  27 namespace dcsbwt {
  28
  29 //------------------
  30 // DifferenceCover
  31 //------------------
  32
  33 inline bool DifferenceCover::Contains(unsigned int i) const {
  34   assert(i < period());
  35   return Rank(i) < size() && Select(Rank(i)) == i;
  36 }
  37 inline unsigned int DifferenceCover::Rank(unsigned int i) const {
  38   assert(i < period());
  39   return ranks_[i];
  40 }
  41 inline unsigned int DifferenceCover::Select(unsigned int j) const {
  42   assert(j < size());
  43   return cover_[j];
  44 }
  45 inline unsigned int DifferenceCover::Coverer(unsigned int diff) const {
  46   assert(diff < period());
  47   return coverers_[diff];
  48 }
  49
  50 //-------------------------
  51 // DifferenceCoverSample
  52 //-------------------------
  53
  54 // constructor
  55 template <typename Integer>
  56 DifferenceCoverSample<Integer>::DifferenceCoverSample(
  57     unsigned int period, Integer range )
  58     : dc_(period), period_(period), range_(range)
  59 {
  60   // Check that range >= period
  61   // We cannot convert range into unsigned int since its value
  62   // could legally exceed UINT_MAX. It is also possible that
  63   // the value of period exceeds the maximum value of Integer,
  64   // but then period > max(Integer) >= range, which violates
  65   // the condition. Thus one of the following tests fails if
  66   // and only if period > range.
  67   assert(static_cast<unsigned int>(static_cast<Integer>(period)) == period);
  68   assert(range >= static_cast<Integer>(period));
  69   ComputeSize();
  70 }
  71
  72 template <typename Integer>
  73 void DifferenceCoverSample<Integer>::ComputeSize() {
  74   Integer n_div_p = dc_.DivideByPeriod(range_);
  75   unsigned int n_mod_p = dc_.ModuloPeriod(range_);
  76   size_ = static_cast<Integer>(dc_.size()) * n_div_p
  77       + static_cast<Integer>(dc_.Rank(n_mod_p));
  78 }
  79
  80 template <typename Integer>
  81 inline bool DifferenceCoverSample<Integer>::Contains(Integer i) const {
  82   return 0 <= i && i < range() && dc_.Contains(dc_.ModuloPeriod(i));
  83 }
  84
  85 template <typename Integer>
  86 inline Integer DifferenceCoverSample<Integer>::Shift(
  87     unsigned int i, unsigned int j) const
  88 {
  89   unsigned int diff_mod_p = dc_.ModuloPeriod(j-i);
  90   return dc_.ModuloPeriod(dc_.Coverer(diff_mod_p) - i);
  91 }
  92
  93 // Fill the output range with the elements of Dn
  94 // Dn order 1 (see header)
  95 template <typename Integer>
  96 template <typename OutputIterator>
  97 OutputIterator DifferenceCoverSample<Integer>::Fill(
  98     OutputIterator out_iter) const
  99 {
 100   Integer start_of_period = 0;
 101   Integer num_elements_written = 0;
 102   // Write copies of the difference cover, each shifted by one
 103   // period length from the previous one.
 104   // Note that the test in while is equivalent to
 105   // start_of_period + period() <= range(), but the latter could
 106   // overflow, since Integer is not guaranteed to be able to represent
 107   // a value larger than range().
 108   while (start_of_period <= range() - period()) {
 109     out_iter = std::transform(dc_.begin(), dc_.end(), out_iter,
 110                    std::bind2nd(std::plus<Integer>(), start_of_period));
 111     start_of_period += period();
 112     num_elements_written += dc_.size();
 113   }
 114   // Now there might not be room for a full copy of the difference
 115   // cover anymore, so write the last copy one element at a time.
 116   DifferenceCover::iterator dc_iter = dc_.begin();
 117   while ((dc_iter != dc_.end()) &&
 118          (start_of_period < range() - static_cast<Integer>(*dc_iter)) ) {
 119     *out_iter++ = start_of_period + *dc_iter++;
 120     ++num_elements_written;
 121   }
 122   assert(size() == num_elements_written);
 123   return out_iter;
 124 }
 125
 126 // Rank
 127 // Dn order 1 (see header)
 128 template <typename Integer>
 129 inline Integer DifferenceCoverSample<Integer>::Rank(Integer i) const {
 130   assert(Contains(i));
 131   Integer i_div_p = dc_.DivideByPeriod(i);
 132   unsigned int i_mod_p = dc_.ModuloPeriod(i);
 133   Integer num_elements_in_earlier_periods = period_size() * i_div_p;
 134   Integer num_earlier_elements_in_this_period = dc_.Rank(i_mod_p);
 135   return num_elements_in_earlier_periods + num_earlier_elements_in_this_period;
 136 }
 137
 138 // period_distance
 139 // Dn order 1 (see header)
 140 template <typename Integer>
 141 inline Integer DifferenceCoverSample<Integer>::PeriodInterval() const {
 142   return dc_.size();
 143 }
 144
 145 }  // namespace dcsbwt
 146
 147 #endif  // DCSBWT_DIFFERENCE_COVER_INL_H__