00001 #include "util/sorted_uniform.hh"
00002
00003 #include <boost/random/mersenne_twister.hpp>
00004 #include <boost/random/uniform_int.hpp>
00005 #include <boost/random/variate_generator.hpp>
00006 #include <boost/scoped_array.hpp>
00007 #include <boost/unordered_map.hpp>
00008
00009 #define BOOST_TEST_MODULE SortedUniformTest
00010 #include <boost/test/unit_test.hpp>
00011
00012 #include <algorithm>
00013 #include <limits>
00014 #include <vector>
00015
00016 namespace util {
00017 namespace {
00018
00019 template <class KeyT, class ValueT> struct Entry {
00020 typedef KeyT Key;
00021 typedef ValueT Value;
00022
00023 Key key;
00024 Value value;
00025
00026 Key GetKey() const {
00027 return key;
00028 }
00029
00030 Value GetValue() const {
00031 return value;
00032 }
00033
00034 bool operator<(const Entry<Key,Value> &other) const {
00035 return key < other.key;
00036 }
00037 };
00038
00039 template <class KeyT> struct Accessor {
00040 typedef KeyT Key;
00041 template <class Value> Key operator()(const Entry<Key, Value> *entry) const {
00042 return entry->GetKey();
00043 }
00044 };
00045
00046 template <class Key, class Value> void Check(const Entry<Key, Value> *begin, const Entry<Key, Value> *end, const boost::unordered_map<Key, Value> &reference, const Key key) {
00047 typename boost::unordered_map<Key, Value>::const_iterator ref = reference.find(key);
00048 typedef const Entry<Key, Value> *It;
00049
00050 It i = NULL;
00051 bool ret = SortedUniformFind<It, Accessor<Key>, Pivot64>(Accessor<Key>(), begin, end, key, i);
00052 if (ref == reference.end()) {
00053 BOOST_CHECK(!ret);
00054 } else {
00055 BOOST_REQUIRE(ret);
00056 BOOST_CHECK_EQUAL(ref->second, i->GetValue());
00057 }
00058 }
00059
00060 BOOST_AUTO_TEST_CASE(empty) {
00061 typedef const Entry<uint64_t, float> T;
00062 const T *i;
00063 bool ret = SortedUniformFind<const T*, Accessor<uint64_t>, Pivot64>(Accessor<uint64_t>(), (const T*)NULL, (const T*)NULL, (uint64_t)10, i);
00064 BOOST_CHECK(!ret);
00065 }
00066
00067 template <class Key> void RandomTest(Key upper, size_t entries, size_t queries) {
00068 typedef unsigned char Value;
00069 boost::mt19937 rng;
00070 boost::uniform_int<Key> range_key(0, upper);
00071 boost::uniform_int<Value> range_value(0, 255);
00072 boost::variate_generator<boost::mt19937&, boost::uniform_int<Key> > gen_key(rng, range_key);
00073 boost::variate_generator<boost::mt19937&, boost::uniform_int<unsigned char> > gen_value(rng, range_value);
00074
00075 typedef Entry<Key, Value> Ent;
00076 std::vector<Ent> backing;
00077 boost::unordered_map<Key, unsigned char> reference;
00078 Ent ent;
00079 for (size_t i = 0; i < entries; ++i) {
00080 Key key = gen_key();
00081 unsigned char value = gen_value();
00082 if (reference.insert(std::make_pair(key, value)).second) {
00083 ent.key = key;
00084 ent.value = value;
00085 backing.push_back(ent);
00086 }
00087 }
00088 std::sort(backing.begin(), backing.end());
00089
00090
00091 for (size_t i = 0; i < queries; ++i) {
00092 const Key key = gen_key();
00093 Check<Key, unsigned char>(&*backing.begin(), &*backing.end(), reference, key);
00094 }
00095
00096 typename boost::unordered_map<Key, unsigned char>::const_iterator it = reference.begin();
00097 for (size_t i = 0; (i < queries) && (it != reference.end()); ++i, ++it) {
00098 Check<Key, unsigned char>(&*backing.begin(), &*backing.end(), reference, it->second);
00099 }
00100 }
00101
00102 BOOST_AUTO_TEST_CASE(basic) {
00103 RandomTest<uint8_t>(11, 10, 200);
00104 }
00105
00106 BOOST_AUTO_TEST_CASE(tiny_dense_random) {
00107 RandomTest<uint8_t>(11, 50, 200);
00108 }
00109
00110 BOOST_AUTO_TEST_CASE(small_dense_random) {
00111 RandomTest<uint8_t>(100, 100, 200);
00112 }
00113
00114 BOOST_AUTO_TEST_CASE(small_sparse_random) {
00115 RandomTest<uint8_t>(200, 15, 200);
00116 }
00117
00118 BOOST_AUTO_TEST_CASE(medium_sparse_random) {
00119 RandomTest<uint16_t>(32000, 1000, 2000);
00120 }
00121
00122 BOOST_AUTO_TEST_CASE(sparse_random) {
00123 RandomTest<uint64_t>(std::numeric_limits<uint64_t>::max(), 100000, 2000);
00124 }
00125
00126 }
00127 }