src/test/mruset_tests.cpp

   1 #include <boost/test/unit_test.hpp>
   2
   3 using namespace std;
   4
   5 #include "mruset.h"
   6 #include "util.h"
   7
   8 #define NUM_TESTS 16
   9 #define MAX_SIZE 100
  10
  11 class mrutester
  12 {
  13 private:
  14     mruset<int> mru;
  15     std::set<int> set;
  16
  17 public:
  18     mrutester() { mru.max_size(MAX_SIZE); }
  19     int size() const { return set.size(); }
  20
  21     void insert(int n)
  22     {
  23         mru.insert(n);
  24         set.insert(n);
  25         BOOST_CHECK(mru == set);
  26     }
  27 };
  28
  29 BOOST_AUTO_TEST_SUITE(mruset_tests)
  30
  31 // Test that an mruset behaves like a set, as long as no more than MAX_SIZE elements are in it
  32 BOOST_AUTO_TEST_CASE(mruset_like_set)
  33 {
  34
  35     for (int nTest=0; nTest<NUM_TESTS; nTest++)
  36     {
  37         mrutester tester;
  38         while (tester.size() < MAX_SIZE)
  39             tester.insert(GetRandInt(2 * MAX_SIZE));
  40     }
  41
  42 }
  43
  44 // Test that an mruset's size never exceeds its max_size
  45 BOOST_AUTO_TEST_CASE(mruset_limited_size)
  46 {
  47     for (int nTest=0; nTest<NUM_TESTS; nTest++)
  48     {
  49         mruset<int> mru(MAX_SIZE);
  50         for (int nAction=0; nAction<3*MAX_SIZE; nAction++)
  51         {
  52             int n = GetRandInt(2 * MAX_SIZE);
  53             mru.insert(n);
  54             BOOST_CHECK(mru.size() <= MAX_SIZE);
  55         }
  56     }
  57 }
  58
  59 // 16-bit permutation function
  60 int static permute(int n)
  61 {
  62     // hexadecimals of pi; verified to be linearly independent
  63     static const int table[16] = {0x243F, 0x6A88, 0x85A3, 0x08D3, 0x1319, 0x8A2E, 0x0370, 0x7344,
  64                                   0xA409, 0x3822, 0x299F, 0x31D0, 0x082E, 0xFA98, 0xEC4E, 0x6C89};
  65
  66     int ret = 0;
  67     for (int bit=0; bit<16; bit++)
  68          if (n & (1<<bit))
  69              ret ^= table[bit];
  70
  71     return ret;
  72 }
  73
  74 // Test that an mruset acts like a moving window, if no duplicate elements are added
  75 BOOST_AUTO_TEST_CASE(mruset_window)
  76 {
  77     mruset<int> mru(MAX_SIZE);
  78     for (int n=0; n<10*MAX_SIZE; n++)
  79     {
  80         mru.insert(permute(n));
  81
  82         set<int> tester;
  83         for (int m=max(0,n-MAX_SIZE+1); m<=n; m++)
  84             tester.insert(permute(m));
  85
  86         BOOST_CHECK(mru == tester);
  87     }
  88 }
  89
  90 BOOST_AUTO_TEST_SUITE_END()