tools/bwt/dcs-bwt/test/difference_cover_test.cc

   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 #include "../src/difference_cover-inl.h"
  18 #include "../src/difference_cover.h"
  19 #include "../src/inttypes.h"
  20 #include "../src/ternary_partition.h"  // for random numbers
  21
  22 #include <cstdio>
  23 #include <vector>
  24 #include <cassert>
  25 #include <iostream>
  26
  27 namespace {
  28
  29 using dcsbwt::DifferenceCover;
  30 using dcsbwt::DifferenceCoverSample;
  31 using dcsbwt::ternary_partition::RandomNumberGenerator;
  32
  33 const int kMaxPeriod = 1024;  // includes all precomputed covers and
  34                               // two covers computed by Colbourn-Ling
  35
  36 void TestCoverConstruction() {
  37   for (int32 period = 1; period <= kMaxPeriod; period *= 2) {
  38     DifferenceCover dc(period);
  39     assert(dc.period() == period);
  40     assert(dc.size() <= period);
  41     assert(DifferenceCover::CoverSizeForPeriod(period) == dc.size());
  42     assert(DifferenceCover::SizeInBytesForPeriod(period) > period);
  43   }
  44   std::cout << "TestCoverConstruction passed" << std::endl;
  45 }
  46
  47
  48 void TestCoverDivision() {
  49   for (int32 period = 1; period <= kMaxPeriod; period *= 2) {
  50     DifferenceCover dc(period);
  51     for (int32 dividend = 0; dividend < period; ++dividend) {
  52       assert(dc.DivideByPeriod(dividend) == 0);
  53       assert(dc.ModuloPeriod(dividend) == dividend);
  54     }
  55     int32 dividend = 0;
  56     for (int32 quotient = 0; quotient < period; ++quotient) {
  57       dividend += period - 1;
  58       int32 remainder = period - quotient - 1;
  59       assert(dc.DivideByPeriod(dividend) == quotient);
  60       assert(dc.ModuloPeriod(dividend) == remainder);
  61     }
  62     // Division should work even for values larger than MAX_UINT.
  63     int64 large_value = 1489245697U;  // random large number
  64     large_value *= (large_value-4);
  65     assert(dc.DivideByPeriod(large_value) * static_cast<int64>(period) +
  66               dc.ModuloPeriod(large_value) == large_value);
  67     // ModuloPeriod should work even for negative values.
  68     int x = -1;
  69     assert(dc.ModuloPeriod(x) == period-1);
  70   }
  71   std::cout << "TestCoverDivision passed" << std::endl;
  72 }
  73
  74
  75 void TestCoverRankSelect() {
  76   for (int32 period = 1; period <= kMaxPeriod; period *= 2) {
  77     DifferenceCover dc(period);
  78     int32 i = 0;
  79     for (; i < period; ++i) {
  80       // continue up to and including the last cover element
  81       if (dc.Rank(i) == dc.size()) break;
  82       assert(dc.Rank(i) < dc.size());
  83       assert(dc.Select(dc.Rank(i)) >= i);
  84     }
  85     for (; i < period; ++i) {
  86       // after the last cover element
  87       assert(dc.Rank(i) == dc.size());
  88     }
  89     for (int32 j = 0; j < dc.size(); ++j) {
  90       assert(dc.Select(j) < period);
  91       assert(dc.Rank(dc.Select(j)) == j);
  92       assert(dc.Contains(dc.Select(j)));
  93     }
  94   }
  95   std::cout << "TestCoverRankSelect passed" << std::endl;
  96 }
  97
  98
  99 void TestCoverContainer() {
 100   for (int32 period = 1; period <= kMaxPeriod; period *= 2) {
 101     DifferenceCover dc(period);
 102     std::vector<int32> cover(dc.begin(), dc.end());
 103     assert(cover.size() == dc.size());
 104     std::vector<int32>::iterator it = cover.begin();
 105     for (int32 i = 0; i < period; ++i) {
 106       if (it != cover.end() && *it == i) {
 107         assert(dc.Contains(i));
 108         ++it;
 109       } else {
 110         assert(!dc.Contains(i));
 111       }
 112     }
 113   }
 114   std::cout << "TestCoverContainer passed" << std::endl;
 115 }
 116
 117
 118 void TestCoverCoverage() {
 119   for (int32 period = 1; period <= kMaxPeriod; period *= 2) {
 120     DifferenceCover dc(period);
 121     for (int32 diff = 0; diff < period; ++diff) {
 122       int32 k = dc.Coverer(diff);
 123       assert(k < period);
 124       assert(dc.Contains(k));
 125       int32 k_plus_diff = dc.ModuloPeriod(k + diff);
 126       assert(dc.Contains(k_plus_diff));
 127     }
 128   }
 129   std::cout << "TestCoverCoverage passed" << std::endl;
 130 }
 131
 132
 133 static struct PeriodRangePair{
 134   int32 period;
 135   int32 range;
 136 } period_range_pairs[20] = {
 137   {    1,   1 },
 138   {    1,   2 },
 139   {    1,   7 },
 140   {    2,   2 },
 141   {    2,   3 },
 142   {    2,   4 },
 143   {    2,   7 },
 144   {   64,  64 },
 145   {   64,  65 },
 146   {   64,  96 },
 147   {   64,  127 },
 148   {   64,  128 },
 149   {   64,  129 },
 150   {   64,  917 },
 151   { 1024, 1024 },
 152   { 1024, 1025 },
 153   { 1024, 2047 },
 154   { 1024, 2048 },
 155   { 1024, 2049 },
 156   { 1024, 5847 }
 157 };
 158
 159 void TestSampleConstruction() {
 160   for (int32 i = 0; i < 20; ++i) {
 161     int32 period = period_range_pairs[i].period;
 162     int32 range = period_range_pairs[i].range;
 163     DifferenceCoverSample<int32> dcs(period, range);
 164     assert(dcs.period() == period);
 165     assert(dcs.range() == range);
 166     assert(dcs.size() <= range);
 167     assert(dcs.period_size() <= period);
 168   }
 169   std::cout << "TestSampleConstruction passed" << std::endl;
 170 }
 171
 172
 173 void TestSampleFill() {
 174   for (int32 i = 0; i < 20; ++i) {
 175     int32 period = period_range_pairs[i].period;
 176     int32 range = period_range_pairs[i].range;
 177     DifferenceCoverSample<int32> dcs(period, range);
 178     std::vector<int32> sample;
 179     dcs.Fill(std::back_inserter(sample));
 180     assert(sample.size() == dcs.size());
 181     std::vector<int32>::iterator it = sample.begin();
 182     int32 sample_count = 0;
 183     bool death_test_done = false;     // do just one death test
 184     for (int32 i = 0; i < range; ++i) {
 185       if (it != sample.end() && *it == i) {
 186         assert(dcs.Contains(i));
 187         assert(dcs.Rank(i) == sample_count);
 188         if (i < range - period) {
 189           assert(dcs.Rank(i+period) - dcs.Rank(i) == dcs.PeriodInterval());
 190         }
 191         ++it;
 192         ++sample_count;
 193       } else {
 194         assert(!dcs.Contains(i));
 195       }
 196     }
 197   }
 198   std::cout << "TestSampleFill passed" << std::endl;
 199 }
 200
 201
 202 void TestSampleShift() {
 203   for (int32 i = 0; i < 20; ++i) {
 204     int32 period = period_range_pairs[i].period;
 205     int32 range = period_range_pairs[i].range;
 206     DifferenceCoverSample<int32> dcs(period, range);
 207     RandomNumberGenerator rng;
 208     for (int32 n = 20000; n; --n) {
 209       int32 i = rng.Uniform(range);
 210       int32 j = rng.Uniform(range);
 211       int32 shift = dcs.Shift(i,j);
 212       assert(shift >= 0);
 213       assert(shift < period);
 214       if (i < range - shift) {
 215         assert(dcs.Contains(i + shift));
 216       }
 217       if (j < range - shift) {
 218         assert(dcs.Contains(j + shift));
 219       }
 220     }
 221   }
 222   std::cout << "TestSampleShift passed" << std::endl;
 223 }
 224
 225 }  // unnamed namespace
 226
 227 int main(int argc, char **argv) {
 228
 229   TestCoverConstruction();
 230   TestCoverDivision();
 231   TestCoverRankSelect();
 232   TestCoverContainer();
 233   TestCoverCoverage();
 234   TestSampleConstruction();
 235   TestSampleFill();
 236   TestSampleShift();
 237
 238   return 0;
 239 }