folly/experimental/test/CodingTestUtils.h

   1 /*
   2  * Copyright 2014 Facebook, Inc.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *   http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 #ifndef FOLLY_EXPERIMENTAL_CODING_TEST_UTILS_H
  18 #define FOLLY_EXPERIMENTAL_CODING_TEST_UTILS_H
  19
  20 #include <algorithm>
  21 #include <fstream>
  22 #include <limits>
  23 #include <random>
  24 #include <string>
  25 #include <vector>
  26 #include <unordered_set>
  27 #include <glog/logging.h>
  28 #include <gtest/gtest.h>
  29
  30 namespace folly { namespace compression {
  31
  32 template <class URNG>
  33 std::vector<uint32_t> generateRandomList(size_t n, uint32_t maxId, URNG&& g) {
  34   CHECK_LT(n, 2 * maxId);
  35   std::uniform_int_distribution<> uid(1, maxId);
  36   std::unordered_set<uint32_t> dataset;
  37   while (dataset.size() < n) {
  38     uint32_t value = uid(g);
  39     if (dataset.count(value) == 0) {
  40       dataset.insert(value);
  41     }
  42   }
  43
  44   std::vector<uint32_t> ids(dataset.begin(), dataset.end());
  45   std::sort(ids.begin(), ids.end());
  46   return ids;
  47 }
  48
  49 inline std::vector<uint32_t> generateRandomList(size_t n, uint32_t maxId) {
  50   std::mt19937 gen;
  51   return generateRandomList(n, maxId, gen);
  52 }
  53
  54 inline std::vector<uint32_t> generateSeqList(uint32_t minId, uint32_t maxId,
  55                                              uint32_t step = 1) {
  56   CHECK_LE(minId, maxId);
  57   CHECK_GT(step, 0);
  58   std::vector<uint32_t> ids;
  59   ids.reserve((maxId - minId) / step + 1);
  60   for (uint32_t i = minId; i <= maxId; i += step) {
  61     ids.push_back(i);
  62   }
  63   return ids;
  64 }
  65
  66 inline std::vector<uint32_t> loadList(const std::string& filename) {
  67   std::ifstream fin(filename);
  68   std::vector<uint32_t> result;
  69   uint32_t id;
  70   while (fin >> id) {
  71     result.push_back(id);
  72   }
  73   return result;
  74 }
  75
  76 template <class Reader, class List>
  77 void testNext(const std::vector<uint32_t>& data, const List& list) {
  78   Reader reader(list);
  79   EXPECT_EQ(reader.value(), 0);
  80   for (size_t i = 0; i < data.size(); ++i) {
  81     EXPECT_TRUE(reader.next());
  82     EXPECT_EQ(reader.value(), data[i]);
  83   }
  84   EXPECT_FALSE(reader.next());
  85   EXPECT_EQ(reader.value(), std::numeric_limits<uint32_t>::max());
  86 }
  87
  88 template <class Reader, class List>
  89 void testSkip(const std::vector<uint32_t>& data, const List& list,
  90               size_t skipStep) {
  91   CHECK_GT(skipStep, 0);
  92   Reader reader(list);
  93   EXPECT_EQ(reader.value(), 0);
  94   for (size_t i = skipStep - 1; i < data.size(); i += skipStep) {
  95     EXPECT_TRUE(reader.skip(skipStep));
  96     EXPECT_EQ(reader.value(), data[i]);
  97   }
  98   EXPECT_FALSE(reader.skip(skipStep));
  99   EXPECT_EQ(reader.value(), std::numeric_limits<uint32_t>::max());
 100   EXPECT_FALSE(reader.next());
 101 }
 102
 103 template <class Reader, class List>
 104 void testSkip(const std::vector<uint32_t>& data, const List& list) {
 105   for (size_t skipStep = 1; skipStep < 25; ++skipStep) {
 106     testSkip<Reader, List>(data, list, skipStep);
 107   }
 108   for (size_t skipStep = 25; skipStep <= 500; skipStep += 25) {
 109     testSkip<Reader, List>(data, list, skipStep);
 110   }
 111 }
 112
 113 template <class Reader, class List>
 114 void testSkipTo(const std::vector<uint32_t>& data, const List& list,
 115                 size_t skipToStep) {
 116   CHECK_GT(skipToStep, 0);
 117
 118   Reader reader(list);
 119   EXPECT_EQ(reader.value(), 0);
 120
 121   const uint32_t delta = std::max<uint32_t>(1, data.back() / skipToStep);
 122   uint32_t value = delta;
 123   auto it = data.begin();
 124   while (true) {
 125     it = std::lower_bound(it, data.end(), value);
 126     if (it == data.end()) {
 127       EXPECT_FALSE(reader.skipTo(value));
 128       break;
 129     }
 130     EXPECT_TRUE(reader.skipTo(value));
 131     EXPECT_EQ(reader.value(), *it);
 132     value = reader.value() + delta;
 133   }
 134   EXPECT_EQ(reader.value(), std::numeric_limits<uint32_t>::max());
 135   EXPECT_FALSE(reader.next());
 136 }
 137
 138 template <class Reader, class List>
 139 void testSkipTo(const std::vector<uint32_t>& data, const List& list) {
 140   for (size_t steps = 10; steps < 100; steps += 10) {
 141     testSkipTo<Reader, List>(data, list, steps);
 142   }
 143   for (size_t steps = 100; steps <= 1000; steps += 100) {
 144     testSkipTo<Reader, List>(data, list, steps);
 145   }
 146   testSkipTo<Reader, List>(data, list, std::numeric_limits<size_t>::max());
 147   {
 148     Reader reader(list);
 149     EXPECT_FALSE(reader.skipTo(data.back() + 1));
 150     EXPECT_EQ(reader.value(), std::numeric_limits<uint32_t>::max());
 151     EXPECT_FALSE(reader.next());
 152   }
 153 }
 154
 155 template <class Reader, class List>
 156 void testGoTo(const std::vector<uint32_t>& data, const List& list) {
 157   std::mt19937 gen;
 158   std::vector<size_t> is(data.size());
 159   for (size_t i = 0; i < data.size(); ++i) {
 160     is[i] = i;
 161   }
 162   std::shuffle(is.begin(), is.end(), gen);
 163   if (Reader::EncoderType::forwardQuantum == 0) {
 164     is.resize(std::min<size_t>(is.size(), 100));
 165   }
 166
 167   Reader reader(list);
 168   EXPECT_TRUE(reader.goTo(0));
 169   EXPECT_EQ(reader.value(), 0);
 170   for (auto i : is) {
 171     EXPECT_TRUE(reader.goTo(i + 1));
 172     EXPECT_EQ(reader.value(), data[i]);
 173   }
 174   EXPECT_FALSE(reader.goTo(data.size() + 1));
 175   EXPECT_EQ(reader.value(), std::numeric_limits<uint32_t>::max());
 176 }
 177
 178 template <class Reader, class Encoder>
 179 void testEmpty() {
 180   const typename Encoder::ValueType* const data = nullptr;
 181   auto list = Encoder::encode(data, data);
 182   {
 183     Reader reader(list);
 184     EXPECT_FALSE(reader.next());
 185     EXPECT_EQ(reader.size(), 0);
 186   }
 187   {
 188     Reader reader(list);
 189     EXPECT_FALSE(reader.skip(1));
 190     EXPECT_FALSE(reader.skip(10));
 191   }
 192   {
 193     Reader reader(list);
 194     EXPECT_FALSE(reader.skipTo(1));
 195   }
 196 }
 197
 198 template <class Reader, class Encoder>
 199 void testAll(const std::vector<uint32_t>& data) {
 200   auto list = Encoder::encode(data.begin(), data.end());
 201   testNext<Reader>(data, list);
 202   testSkip<Reader>(data, list);
 203   testSkipTo<Reader>(data, list);
 204   testGoTo<Reader>(data, list);
 205   list.free();
 206 }
 207
 208 template <class Reader, class List>
 209 void bmNext(const List& list, const std::vector<uint32_t>& data,
 210             size_t iters) {
 211   if (data.empty()) {
 212     return;
 213   }
 214   for (size_t i = 0, j; i < iters; ) {
 215     Reader reader(list);
 216     for (j = 0; reader.next(); ++j, ++i) {
 217       const uint32_t value = reader.value();
 218       CHECK_EQ(value, data[j]) << j;
 219     }
 220   }
 221 }
 222
 223 template <class Reader, class List>
 224 void bmSkip(const List& list, const std::vector<uint32_t>& data,
 225             size_t skip, size_t iters) {
 226   if (skip >= data.size()) {
 227     return;
 228   }
 229   for (size_t i = 0, j; i < iters; ) {
 230     Reader reader(list);
 231     for (j = skip - 1; j < data.size(); j += skip, ++i) {
 232       reader.skip(skip);
 233       const uint32_t value = reader.value();
 234       CHECK_EQ(value, data[j]);
 235     }
 236   }
 237 }
 238
 239 template <class Reader, class List>
 240 void bmSkipTo(const List& list, const std::vector<uint32_t>& data,
 241               size_t skip, size_t iters) {
 242   if (skip >= data.size()) {
 243     return;
 244   }
 245   for (size_t i = 0, j; i < iters; ) {
 246     Reader reader(list);
 247     for (j = 0; j < data.size(); j += skip, ++i) {
 248       reader.skipTo(data[j]);
 249       const uint32_t value = reader.value();
 250       CHECK_EQ(value, data[j]);
 251     }
 252   }
 253 }
 254
 255 template <class Reader, class List>
 256 void bmGoTo(const List& list, const std::vector<uint32_t>& data,
 257             const std::vector<size_t>& order, size_t iters) {
 258   CHECK(!data.empty());
 259   CHECK_EQ(data.size(), order.size());
 260
 261   Reader reader(list);
 262   for (size_t i = 0; i < iters; ) {
 263     for (size_t j : order) {
 264       reader.goTo(j + 1);
 265       const uint32_t value = reader.value();
 266       CHECK_EQ(value, data[j]);
 267       ++i;
 268     }
 269   }
 270 }
 271
 272 }}  // namespaces
 273
 274 #endif  // FOLLY_EXPERIMENTAL_CODING_TEST_UTILS_H