1 2 // Copyright 2017 Daniel James. 3 // Distributed under the Boost Software License, Version 1.0. (See accompanying 4 // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) 5 6 // clang-format off 7 #include "../helpers/prefix.hpp" 8 #include <boost/unordered_map.hpp> 9 #include <boost/unordered_set.hpp> 10 #include "../helpers/postfix.hpp" 11 // clang-format on 12 13 #include "../helpers/test.hpp" 14 #include <map> 15 16 // Pretty inefficient, but the test is fast enough. 17 // Might be too slow if we had larger primes? is_prime(std::size_t x)18bool is_prime(std::size_t x) 19 { 20 if (x == 2) { 21 return true; 22 } else if (x == 1 || x % 2 == 0) { 23 return false; 24 } else { 25 // y*y <= x had rounding errors, so instead use y <= (x/y). 26 for (std::size_t y = 3; y <= (x / y); y += 2) { 27 if (x % y == 0) { 28 return false; 29 break; 30 } 31 } 32 33 return true; 34 } 35 } 36 test_next_prime(std::size_t value)37void test_next_prime(std::size_t value) 38 { 39 std::size_t x = boost::unordered::detail::next_prime(value); 40 BOOST_TEST(is_prime(x)); 41 BOOST_TEST(x >= value); 42 } 43 test_prev_prime(std::size_t value)44void test_prev_prime(std::size_t value) 45 { 46 std::size_t x = boost::unordered::detail::prev_prime(value); 47 BOOST_TEST(is_prime(x)); 48 BOOST_TEST(x <= value); 49 if (x > value) { 50 BOOST_LIGHTWEIGHT_TEST_OSTREAM << x << "," << value << std::endl; 51 } 52 } 53 UNORDERED_AUTO_TEST(next_prime_test)54UNORDERED_AUTO_TEST (next_prime_test) { 55 BOOST_TEST(!is_prime(0)); 56 BOOST_TEST(!is_prime(1)); 57 BOOST_TEST(is_prime(2)); 58 BOOST_TEST(is_prime(3)); 59 BOOST_TEST(is_prime(13)); 60 BOOST_TEST(!is_prime(4)); 61 BOOST_TEST(!is_prime(100)); 62 63 BOOST_TEST(boost::unordered::detail::next_prime(0) > 0); 64 65 // test_prev_prime doesn't work for values less than 17. 66 // Which should be okay, unless an allocator has a really tiny 67 // max_size? 68 const std::size_t min_prime = 17; 69 70 // test_next_prime doesn't work for values greater than this, 71 // which might be a problem if you've got terrabytes of memory? 72 // I seriously doubt the container would work well at such sizes 73 // regardless. 74 const std::size_t max_prime = 4294967291ul; 75 76 std::size_t i; 77 78 BOOST_TEST(is_prime(min_prime)); 79 BOOST_TEST(is_prime(max_prime)); 80 81 for (i = 0; i < 10000; ++i) { 82 if (i < min_prime) { 83 BOOST_TEST(boost::unordered::detail::prev_prime(i) == min_prime); 84 } else { 85 test_prev_prime(i); 86 } 87 test_next_prime(i); 88 } 89 90 std::size_t last = i - 1; 91 for (; i > last; last = i, i += i / 5) { 92 if (i > max_prime) { 93 BOOST_TEST(boost::unordered::detail::next_prime(i) == max_prime); 94 } else { 95 test_next_prime(i); 96 } 97 test_prev_prime(i); 98 } 99 } 100 101 RUN_TESTS() 102