diff options
Diffstat (limited to 'third_party/immer/test/set/generic.ipp')
| -rw-r--r-- | third_party/immer/test/set/generic.ipp | 459 |
1 files changed, 0 insertions, 459 deletions
diff --git a/third_party/immer/test/set/generic.ipp b/third_party/immer/test/set/generic.ipp deleted file mode 100644 index 8d75373787e2..000000000000 --- a/third_party/immer/test/set/generic.ipp +++ /dev/null @@ -1,459 +0,0 @@ -// -// immer: immutable data structures for C++ -// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente -// -// This software is distributed under the Boost Software License, Version 1.0. -// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt -// - -#ifndef SET_T -#error "define the set template to use in SET_T" -#include <immer/set.hpp> -#define SET_T ::immer::set -#endif - -#include "test/dada.hpp" -#include "test/util.hpp" - -#include <immer/algorithm.hpp> - -#include <catch.hpp> - -#include <random> -#include <unordered_set> - -template <typename T = unsigned> -auto make_generator() -{ - auto engine = std::default_random_engine{42}; - auto dist = std::uniform_int_distribution<T>{}; - return std::bind(dist, engine); -} - -struct conflictor -{ - unsigned v1; - unsigned v2; - - bool operator==(const conflictor& x) const - { - return v1 == x.v1 && v2 == x.v2; - } -}; - -struct hash_conflictor -{ - std::size_t operator()(const conflictor& x) const { return x.v1; } -}; - -auto make_values_with_collisions(unsigned n) -{ - auto gen = make_generator(); - auto vals = std::vector<conflictor>{}; - auto vals_ = std::unordered_set<conflictor, hash_conflictor>{}; - generate_n(back_inserter(vals), n, [&] { - auto newv = conflictor{}; - do { - newv = {unsigned(gen() % (n / 2)), gen()}; - } while (!vals_.insert(newv).second); - return newv; - }); - return vals; -} - -auto make_test_set(unsigned n) -{ - auto s = SET_T<unsigned>{}; - for (auto i = 0u; i < n; ++i) - s = s.insert(i); - return s; -} - -auto make_test_set(const std::vector<conflictor>& vals) -{ - auto s = SET_T<conflictor, hash_conflictor>{}; - for (auto&& v : vals) - s = s.insert(v); - return s; -} - -template <std::size_t BufLen> -struct unaligned_str -{ - std::array<char, BufLen> m_data{}; - - unaligned_str() = default; - unaligned_str(const std::string& in) - { - for (std::size_t i = 0; i < std::min(m_data.size() - 1, in.size()); i++) - m_data[i] = in[i]; - } - unaligned_str(const char* in) - : unaligned_str{std::string{in}} - {} - - std::string str() const { return m_data.data(); } - - bool operator==(unaligned_str other) const - { - return m_data == other.m_data; - } - - bool operator!=(unaligned_str other) const - { - return m_data != other.m_data; - } -}; - -namespace std { -template <size_t BufLen> -struct hash<unaligned_str<BufLen>> -{ - size_t operator()(const unaligned_str<BufLen>& str) const - { - return std::hash<std::string>{}(str.str()); - } -}; -} // namespace std - -template <size_t BufLen> -void check_with_len() -{ - auto v = SET_T<unaligned_str<BufLen>>{}; - - for (int i = 0; i < 1; i++) - v = v.insert(std::to_string(i)); - - CHECK(v.count("0") == 1); -} - -TEST_CASE("insert type with no alignment requirement") -{ - check_with_len<1>(); - check_with_len<9>(); - check_with_len<15>(); - check_with_len<17>(); -} - -TEST_CASE("instantiation") -{ - SECTION("default") - { - auto v = SET_T<unsigned>{}; - CHECK(v.size() == 0u); - } -} - -TEST_CASE("basic insertion") -{ - auto v1 = SET_T<unsigned>{}; - CHECK(v1.count(42) == 0); - - auto v2 = v1.insert(42); - CHECK(v1.count(42) == 0); - CHECK(v2.count(42) == 1); - - auto v3 = v2.insert(42); - CHECK(v1.count(42) == 0); - CHECK(v2.count(42) == 1); - CHECK(v3.count(42) == 1); -} - -TEST_CASE("insert a lot") -{ - constexpr auto N = 666u; - - auto gen = make_generator(); - auto vals = std::vector<unsigned>{}; - generate_n(back_inserter(vals), N, gen); - auto s = SET_T<unsigned>{}; - - for (auto i = 0u; i < N; ++i) { - s = s.insert(vals[i]); - CHECK(s.size() == i + 1); - for (auto j : test_irange(0u, i + 1)) - CHECK(s.count(vals[j]) == 1); - for (auto j : test_irange(i + 1u, N)) - CHECK(s.count(vals[j]) == 0); - } -} - -TEST_CASE("insert conflicts") -{ - constexpr auto N = 666u; - auto vals = make_values_with_collisions(N); - auto s = SET_T<conflictor, hash_conflictor>{}; - for (auto i = 0u; i < N; ++i) { - s = s.insert(vals[i]); - CHECK(s.size() == i + 1); - for (auto j : test_irange(0u, i + 1)) - CHECK(s.count(vals[j]) == 1); - for (auto j : test_irange(i + 1u, N)) - CHECK(s.count(vals[j]) == 0); - } -} - -TEST_CASE("erase a lot") -{ - constexpr auto N = 666u; - auto gen = make_generator(); - auto vals = std::vector<unsigned>{}; - generate_n(back_inserter(vals), N, gen); - - auto s = SET_T<unsigned>{}; - for (auto i = 0u; i < N; ++i) - s = s.insert(vals[i]); - - for (auto i = 0u; i < N; ++i) { - s = s.erase(vals[i]); - CHECK(s.size() == N - i - 1); - for (auto j : test_irange(0u, i + 1)) - CHECK(s.count(vals[j]) == 0); - for (auto j : test_irange(i + 1u, N)) - CHECK(s.count(vals[j]) == 1); - } -} - -TEST_CASE("erase conflicts") -{ - constexpr auto N = 666u; - auto vals = make_values_with_collisions(N); - auto s = SET_T<conflictor, hash_conflictor>{}; - for (auto i = 0u; i < N; ++i) - s = s.insert(vals[i]); - - for (auto i = 0u; i < N; ++i) { - s = s.erase(vals[i]); - CHECK(s.size() == N - i - 1); - for (auto j : test_irange(0u, i + 1)) - CHECK(s.count(vals[j]) == 0); - for (auto j : test_irange(i + 1u, N)) - CHECK(s.count(vals[j]) == 1); - } -} - -TEST_CASE("accumulate") -{ - const auto n = 666u; - auto v = make_test_set(n); - - auto expected_n = [](auto n) { return n * (n - 1) / 2; }; - - SECTION("sum collection") - { - auto sum = immer::accumulate(v, 0u); - CHECK(sum == expected_n(v.size())); - } - - SECTION("sum collisions") - { - auto vals = make_values_with_collisions(n); - auto s = make_test_set(vals); - auto acc = [](unsigned r, conflictor x) { return r + x.v1 + x.v2; }; - auto sum1 = std::accumulate(vals.begin(), vals.end(), 0, acc); - auto sum2 = immer::accumulate(s, 0u, acc); - CHECK(sum1 == sum2); - } -} - -TEST_CASE("find") -{ - const auto n = 666u; - auto v = make_test_set(n); - CHECK(*v.find(0) == 0); - CHECK(*v.find(42) == 42); - CHECK(*v.find(665) == 665); - CHECK(v.find(666) == nullptr); - CHECK(v.find(1234) == nullptr); -} - -TEST_CASE("iterator") -{ - const auto N = 666u; - auto v = make_test_set(N); - - SECTION("empty set") - { - auto s = SET_T<unsigned>{}; - CHECK(s.begin() == s.end()); - } - - SECTION("works with range loop") - { - auto seen = std::unordered_set<unsigned>{}; - for (const auto& x : v) - CHECK(seen.insert(x).second); - CHECK(seen.size() == v.size()); - } - - SECTION("works with standard algorithms") - { - auto s = std::vector<unsigned>(N); - std::iota(s.begin(), s.end(), 0u); - std::equal(v.begin(), v.end(), s.begin(), s.end()); - } - - SECTION("iterator and collisions") - { - auto vals = make_values_with_collisions(N); - auto s = make_test_set(vals); - auto seen = std::unordered_set<conflictor, hash_conflictor>{}; - for (const auto& x : s) - CHECK(seen.insert(x).second); - CHECK(seen.size() == s.size()); - } -} - -struct non_default -{ - unsigned value; - non_default() = delete; - operator unsigned() const { return value; } - -#if IMMER_DEBUG_PRINT - friend std::ostream& operator<<(std::ostream& os, non_default x) - { - os << "ND{" << x.value << "}"; - return os; - } -#endif -}; - -namespace std { - -template <> -struct hash<non_default> -{ - std::size_t operator()(const non_default& x) - { - return std::hash<decltype(x.value)>{}(x.value); - } -}; - -} // namespace std - -TEST_CASE("non default") -{ - const auto n = 666u; - - auto v = SET_T<non_default>{}; - for (auto i = 0u; i < n; ++i) - v = v.insert({i}); - - CHECK(v.size() == n); -} - -TEST_CASE("equals") -{ - const auto n = 666u; - auto v = make_test_set(n); - - CHECK(v == v); - CHECK(v != v.insert(1234)); - CHECK(v == v.erase(1234)); - CHECK(v == v.insert(1234).erase(1234)); - CHECK(v == v.erase(64).insert(64)); - CHECK(v != v.erase(1234).insert(1234)); -} - -TEST_CASE("equals collisions") -{ - const auto n = 666u; - auto vals = make_values_with_collisions(n); - auto v = make_test_set(vals); - - CHECK(v == v); - CHECK(v != v.erase(vals[42])); - CHECK(v == v.erase(vals[42]).insert(vals[42])); - CHECK(v == - v.erase(vals[42]).erase(vals[13]).insert(vals[42]).insert(vals[13])); - CHECK(v == - v.erase(vals[42]).erase(vals[13]).insert(vals[13]).insert(vals[42])); -} - -TEST_CASE("exception safety") -{ - constexpr auto n = 2666u; - - using dadaist_set_t = typename dadaist_wrapper<SET_T<unsigned>>::type; - using dadaist_conflictor_set_t = - typename dadaist_wrapper<SET_T<conflictor, hash_conflictor>>::type; - - SECTION("insert") - { - auto v = dadaist_set_t{}; - auto d = dadaism{}; - for (auto i = 0u; v.size() < n;) { - try { - auto s = d.next(); - v = v.insert({i}); - ++i; - } catch (dada_error) {} - for (auto i : test_irange(0u, i)) - CHECK(v.count({i}) == 1); - } - CHECK(d.happenings > 0); - IMMER_TRACE_E(d.happenings); - } - - SECTION("insert collisions") - { - auto vals = make_values_with_collisions(n); - auto v = dadaist_conflictor_set_t{}; - auto d = dadaism{}; - for (auto i = 0u; v.size() < n;) { - try { - auto s = d.next(); - v = v.insert({vals[i]}); - ++i; - } catch (dada_error) {} - for (auto i : test_irange(0u, i)) - CHECK(v.count({vals[i]}) == 1); - } - CHECK(d.happenings > 0); - IMMER_TRACE_E(d.happenings); - } - - SECTION("erase") - { - auto v = dadaist_set_t{}; - auto d = dadaism{}; - for (auto i = 0u; i < n; ++i) - v = v.insert({i}); - for (auto i = 0u; v.size() > 0;) { - try { - auto s = d.next(); - v = v.erase({i}); - ++i; - } catch (dada_error) {} - for (auto i : test_irange(0u, i)) - CHECK(v.count({i}) == 0); - for (auto i : test_irange(i, n)) - CHECK(v.count({i}) == 1); - } - CHECK(d.happenings > 0); - IMMER_TRACE_E(d.happenings); - } - - SECTION("erase collisisions") - { - auto vals = make_values_with_collisions(n); - auto v = dadaist_conflictor_set_t{}; - auto d = dadaism{}; - for (auto i = 0u; i < n; ++i) - v = v.insert({vals[i]}); - for (auto i = 0u; v.size() > 0;) { - try { - auto s = d.next(); - v = v.erase({vals[i]}); - ++i; - } catch (dada_error) {} - for (auto i : test_irange(0u, i)) - CHECK(v.count({vals[i]}) == 0); - for (auto i : test_irange(i, n)) - CHECK(v.count({vals[i]}) == 1); - } - CHECK(d.happenings > 0); - IMMER_TRACE_E(d.happenings); - } -} |