diff options
author | Kenneth Heafield <kenlm@kheafield.com> | 2012-02-28 17:23:55 -0500 |
---|---|---|
committer | Kenneth Heafield <kenlm@kheafield.com> | 2012-02-28 17:23:55 -0500 |
commit | 89238977fc9d8f8d9a6421b0d4f35afc200f08e7 (patch) | |
tree | f60871db033d20faaf406af2736f17631f490b44 /klm/util/sorted_uniform_test.cc | |
parent | 1f0ded1e7f59b13d7512111dd910d0f4b2f82d02 (diff) |
Subject: where's my kenlm update?? From: Chris Dyer <cdyer@cs.cmu.edu>
Diffstat (limited to 'klm/util/sorted_uniform_test.cc')
-rw-r--r-- | klm/util/sorted_uniform_test.cc | 85 |
1 files changed, 48 insertions, 37 deletions
diff --git a/klm/util/sorted_uniform_test.cc b/klm/util/sorted_uniform_test.cc index 4aa4c8aa..d9f6fad1 100644 --- a/klm/util/sorted_uniform_test.cc +++ b/klm/util/sorted_uniform_test.cc @@ -1,12 +1,11 @@ #include "util/sorted_uniform.hh" -#include "util/key_value_packing.hh" - #include <boost/random/mersenne_twister.hpp> #include <boost/random/uniform_int.hpp> #include <boost/random/variate_generator.hpp> #include <boost/scoped_array.hpp> #include <boost/unordered_map.hpp> + #define BOOST_TEST_MODULE SortedUniformTest #include <boost/test/unit_test.hpp> @@ -17,74 +16,86 @@ namespace util { namespace { -template <class Map, class Key, class Value> void Check(const Map &map, const boost::unordered_map<Key, Value> &reference, const Key key) { +template <class KeyT, class ValueT> struct Entry { + typedef KeyT Key; + typedef ValueT Value; + + Key key; + Value value; + + Key GetKey() const { + return key; + } + + Value GetValue() const { + return value; + } + + bool operator<(const Entry<Key,Value> &other) const { + return key < other.key; + } +}; + +template <class KeyT> struct Accessor { + typedef KeyT Key; + template <class Value> Key operator()(const Entry<Key, Value> *entry) const { + return entry->GetKey(); + } +}; + +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) { typename boost::unordered_map<Key, Value>::const_iterator ref = reference.find(key); - typename Map::ConstIterator i = typename Map::ConstIterator(); + typedef const Entry<Key, Value> *It; + // g++ can't tell that require will crash and burn. + It i = NULL; + bool ret = SortedUniformFind<It, Accessor<Key>, Pivot64>(Accessor<Key>(), begin, end, key, i); if (ref == reference.end()) { - BOOST_CHECK(!map.Find(key, i)); + BOOST_CHECK(!ret); } else { - // g++ can't tell that require will crash and burn. - BOOST_REQUIRE(map.Find(key, i)); + BOOST_REQUIRE(ret); BOOST_CHECK_EQUAL(ref->second, i->GetValue()); } } -typedef SortedUniformMap<AlignedPacking<uint64_t, uint32_t> > TestMap; - BOOST_AUTO_TEST_CASE(empty) { - char buf[TestMap::Size(0)]; - TestMap map(buf, TestMap::Size(0)); - map.FinishedInserting(); - TestMap::ConstIterator i; - BOOST_CHECK(!map.Find(42, i)); -} - -BOOST_AUTO_TEST_CASE(one) { - char buf[TestMap::Size(1)]; - TestMap map(buf, sizeof(buf)); - Entry<uint64_t, uint32_t> e; - e.Set(42,2); - map.Insert(e); - map.FinishedInserting(); - TestMap::ConstIterator i = TestMap::ConstIterator(); - BOOST_REQUIRE(map.Find(42, i)); - BOOST_CHECK(i == map.begin()); - BOOST_CHECK(!map.Find(43, i)); - BOOST_CHECK(!map.Find(41, i)); + typedef const Entry<uint64_t, float> T; + const T *i; + bool ret = SortedUniformFind<const T*, Accessor<uint64_t>, Pivot64>(Accessor<uint64_t>(), (const T*)NULL, (const T*)NULL, (uint64_t)10, i); + BOOST_CHECK(!ret); } template <class Key> void RandomTest(Key upper, size_t entries, size_t queries) { typedef unsigned char Value; - typedef SortedUniformMap<AlignedPacking<Key, unsigned char> > Map; - boost::scoped_array<char> buffer(new char[Map::Size(entries)]); - Map map(buffer.get(), entries); boost::mt19937 rng; boost::uniform_int<Key> range_key(0, upper); boost::uniform_int<Value> range_value(0, 255); boost::variate_generator<boost::mt19937&, boost::uniform_int<Key> > gen_key(rng, range_key); boost::variate_generator<boost::mt19937&, boost::uniform_int<unsigned char> > gen_value(rng, range_value); + typedef Entry<Key, Value> Ent; + std::vector<Ent> backing; boost::unordered_map<Key, unsigned char> reference; - Entry<Key, unsigned char> ent; + Ent ent; for (size_t i = 0; i < entries; ++i) { Key key = gen_key(); unsigned char value = gen_value(); if (reference.insert(std::make_pair(key, value)).second) { - ent.Set(key, value); - map.Insert(Entry<Key, unsigned char>(ent)); + ent.key = key; + ent.value = value; + backing.push_back(ent); } } - map.FinishedInserting(); + std::sort(backing.begin(), backing.end()); // Random queries. for (size_t i = 0; i < queries; ++i) { const Key key = gen_key(); - Check<Map, Key, unsigned char>(map, reference, key); + Check<Key, unsigned char>(&*backing.begin(), &*backing.end(), reference, key); } typename boost::unordered_map<Key, unsigned char>::const_iterator it = reference.begin(); for (size_t i = 0; (i < queries) && (it != reference.end()); ++i, ++it) { - Check<Map, Key, unsigned char>(map, reference, it->second); + Check<Key, unsigned char>(&*backing.begin(), &*backing.end(), reference, it->second); } } |