diff options
Diffstat (limited to 'libs/kstd')
| -rw-r--r-- | libs/kstd/kstd/flat_map.hpp | 84 | ||||
| -rw-r--r-- | libs/kstd/kstd/flat_map.tests.cpp | 310 |
2 files changed, 389 insertions, 5 deletions
diff --git a/libs/kstd/kstd/flat_map.hpp b/libs/kstd/kstd/flat_map.hpp index af269c6a..b9b05366 100644 --- a/libs/kstd/kstd/flat_map.hpp +++ b/libs/kstd/kstd/flat_map.hpp @@ -81,10 +81,13 @@ namespace kstd template<bool IsConst> struct flat_map_iterator { - using iterator_category = std::random_access_iterator_tag; + using iterator_category = std::input_iterator_tag; + using iterator_concept = std::random_access_iterator_tag; using value_type = std::pair<KeyType, MappedType>; using difference_type = std::ptrdiff_t; using reference = std::pair<KeyType const &, std::conditional_t<IsConst, MappedType const, MappedType> &>; + using rvalue_reference = std::pair<std::conditional_t<IsConst, KeyType const &&, KeyType &&>, + std::conditional_t<IsConst, MappedType const &&, MappedType &&>>; struct pointer { @@ -104,7 +107,7 @@ namespace kstd , m_index{it.m_index} {} - [[nodiscard]] constexpr auto operator*() const noexcept -> reference + [[nodiscard]] constexpr auto operator*() const -> reference { if (m_index >= m_containers->keys.size()) { @@ -113,12 +116,12 @@ namespace kstd return {m_containers->keys[m_index], m_containers->values[m_index]}; } - [[nodiscard]] constexpr auto operator->() const noexcept -> pointer + [[nodiscard]] constexpr auto operator->() const -> pointer { return {operator*()}; } - [[nodiscard]] constexpr auto operator[](difference_type offset) const noexcept -> reference + [[nodiscard]] constexpr auto operator[](difference_type offset) const -> reference { return *(*this + offset); } @@ -191,6 +194,24 @@ namespace kstd [[nodiscard]] constexpr auto friend operator<=>(flat_map_iterator const &, flat_map_iterator const &) noexcept = default; + [[nodiscard]] constexpr auto friend iter_move(flat_map_iterator const & it) -> rvalue_reference + { + if (it.m_index >= it.m_containers->keys.size()) + { + os::panic("[kstd::flat_map] Iterator out of range"); + } + + return rvalue_reference{static_cast<rvalue_reference::first_type>(it.m_containers->keys[it.m_index]), + static_cast<rvalue_reference::second_type>(it.m_containers->values[it.m_index])}; + } + + constexpr auto friend iter_swap(flat_map_iterator const & lhs, flat_map_iterator const & rhs) -> void + requires(!IsConst) + { + std::ranges::swap(lhs.m_containers->keys[lhs.m_index], rhs.m_containers->keys[rhs.m_index]); + std::ranges::swap(lhs.m_containers->values[lhs.m_index], rhs.m_containers->values[rhs.m_index]); + } + private: friend struct flat_map; friend flat_map_iterator<!IsConst>; @@ -557,7 +578,8 @@ namespace kstd //! Try to insert a new key-value pair into the map. //! //! @param args Arguments to use for constructing the key-value pair. - //! @return A pair of an iterator to the inserted element and a boolean indicating whether the insertion took place. + //! @return A pair of an iterator to the inserted element and a boolean indicating whether the insertion took + //! place. template<typename... Args> auto emplace(Args &&... args) -> std::pair<iterator, bool> requires std::constructible_from<value_type, Args...> @@ -745,6 +767,58 @@ namespace kstd return find(key) != cend(); } + //! Get an iterator to the first element not less than the given key. + //! + //! @param key The key to look for. + //! @return An iterator to the first element not less than the given key iff. such an element exists, the end + //! iterator otherwise. + [[nodiscard]] constexpr auto lower_bound(key_type const & key) noexcept -> iterator + { + auto found = std::ranges::lower_bound(m_containers.keys, key, m_comparator); + auto offset = static_cast<std::size_t>(std::ranges::distance(m_containers.keys.begin(), found)); + return iterator{m_containers, offset}; + } + + //! Get an iterator to the first element not less than the given key. + //! + //! @param key The key to look for. + //! @return An iterator to the first element not less than the given key iff. such an element exists, the end + //! iterator otherwise. + [[nodiscard]] constexpr auto lower_bound(key_type const & key) const noexcept -> const_iterator + { + auto found = std::ranges::lower_bound(m_containers.keys, key, m_comparator); + auto offset = static_cast<std::size_t>(std::ranges::distance(m_containers.keys.begin(), found)); + return const_iterator{m_containers, offset}; + } + + //! Get an iterator to the first element not less than the given key. + //! + //! @param key The key to look for. + //! @return An iterator to the first element not less than the given key iff. such an element exists, the end + //! iterator otherwise. + template<typename K> + requires requires { typename key_compare::is_transparent; } + [[nodiscard]] constexpr auto lower_bound(K const & key) noexcept -> iterator + { + auto found = std::ranges::lower_bound(m_containers.keys, key, m_comparator); + auto offset = static_cast<std::size_t>(std::ranges::distance(m_containers.keys.begin(), found)); + return iterator{m_containers, offset}; + } + + //! Get an iterator to the first element not less than the given key. + //! + //! @param key The key to look for. + //! @return An iterator to the first element not less than the given key iff. such an element exists, the end + //! iterator otherwise. + template<typename K> + requires requires { typename key_compare::is_transparent; } + [[nodiscard]] constexpr auto lower_bound(K const & key) const noexcept -> const_iterator + { + auto found = std::ranges::lower_bound(m_containers.keys, key, m_comparator); + auto offset = static_cast<std::size_t>(std::ranges::distance(m_containers.keys.begin(), found)); + return const_iterator{m_containers, offset}; + } + //! Get the key comparator of this flat map. //! //! @return The key comparator of this flat map. diff --git a/libs/kstd/kstd/flat_map.tests.cpp b/libs/kstd/kstd/flat_map.tests.cpp index 16b97678..f3384b90 100644 --- a/libs/kstd/kstd/flat_map.tests.cpp +++ b/libs/kstd/kstd/flat_map.tests.cpp @@ -7,6 +7,7 @@ #include <catch2/catch_test_macros.hpp> #include <functional> +#include <string> #include <type_traits> SCENARIO("Flat Map initialization and construction", "[flat_map]") @@ -235,6 +236,215 @@ SCENARIO("Flat Map iterators", "[flat_map]") map.emplace(2, 20); map.emplace(3, 30); + WHEN("getting the begin iterator on a non-const map") + { + auto it = map.begin(); + auto copy = it; + + THEN("it returns an iterator to the first element") + { + REQUIRE(it != map.end()); + REQUIRE((*it).first == 1); + REQUIRE((*it).second == 10); + } + + THEN("its type is flat_map::iterator") + { + STATIC_REQUIRE(std::is_same_v<decltype(it), kstd::flat_map<int, int>::iterator>); + } + + THEN("it can be prefix-incremented to point to the next element") + { + ++it; + REQUIRE(it != map.end()); + REQUIRE((*it).first == 2); + REQUIRE((*it).second == 20); + } + + THEN("it can be postfix-incremented to point to the next element") + { + auto old = it++; + REQUIRE(old == copy); + + REQUIRE(it != map.end()); + REQUIRE((*it).first == 2); + REQUIRE((*it).second == 20); + } + + THEN("it can be addition-incremented") + { + it += 2; + REQUIRE(it != map.end()); + REQUIRE((*it).first == 3); + REQUIRE((*it).second == 30); + } + + THEN("an offset can be added to it") + { + auto new_it = it + 2; + REQUIRE(new_it != map.end()); + REQUIRE((*new_it).first == 3); + REQUIRE((*new_it).second == 30); + } + + THEN("it can be added to an offset") + { + auto new_it = 2 + it; + REQUIRE(new_it != map.end()); + REQUIRE((*new_it).first == 3); + REQUIRE((*new_it).second == 30); + } + + THEN("it can be random access indexed") + { + auto value = it[1]; + REQUIRE(value.first == 2); + REQUIRE(value.second == 20); + } + + THEN("out-of-bounds random access panics") + { + REQUIRE_THROWS_AS(it[3], kstd::tests::os_panic); + } + + THEN("it can be prefix-decremented") + { + --it; + REQUIRE_THROWS_AS(*it, kstd::tests::os_panic); + } + + THEN("it can be postfix-decremented") + { + auto old = it--; + REQUIRE_THROWS_AS(*it, kstd::tests::os_panic); + REQUIRE(old == copy); + } + + THEN("it can be written through") + { + it->second = 100; + REQUIRE(map.at(1) == 100); + } + + THEN("its distance to another iterator can be calculated") + { + auto other = map.begin(); + ++other; + + REQUIRE(other - it == 1); + } + + THEN("it can be compared to another iterator") + { + REQUIRE(it < map.end()); + REQUIRE(it <= map.end()); + REQUIRE(!(it > map.end())); + REQUIRE(!(it >= map.end())); + } + } + + WHEN("getting the begin iterator on a const map") + { + auto const & cmap = map; + auto it = cmap.begin(); + auto copy = it; + + THEN("it returns an iterator to the first element") + { + REQUIRE(it != cmap.end()); + REQUIRE((*it).first == 1); + REQUIRE((*it).second == 10); + } + + THEN("its type is flat_map::const_iterator") + { + STATIC_REQUIRE(std::is_same_v<decltype(it), kstd::flat_map<int, int>::const_iterator>); + } + + THEN("it can be prefix-incremented to point to the next element") + { + ++it; + REQUIRE(it != cmap.end()); + REQUIRE((*it).first == 2); + REQUIRE((*it).second == 20); + } + + THEN("it can be postfix-incremented to point to the next element") + { + auto old = it++; + REQUIRE(old == copy); + + REQUIRE(it != cmap.end()); + REQUIRE((*it).first == 2); + REQUIRE((*it).second == 20); + } + + THEN("it can be addition-incremented") + { + it += 2; + REQUIRE(it != cmap.end()); + REQUIRE((*it).first == 3); + REQUIRE((*it).second == 30); + } + + THEN("an offset can be added to it") + { + auto new_it = it + 2; + REQUIRE(new_it != cmap.end()); + REQUIRE((*new_it).first == 3); + REQUIRE((*new_it).second == 30); + } + + THEN("it can be added to an offset") + { + auto new_it = 2 + it; + REQUIRE(new_it != map.end()); + REQUIRE((*new_it).first == 3); + REQUIRE((*new_it).second == 30); + } + + THEN("it can be random access indexed") + { + auto value = it[1]; + REQUIRE(value.first == 2); + REQUIRE(value.second == 20); + } + + THEN("out-of-bounds random access panics") + { + REQUIRE_THROWS_AS(it[3], kstd::tests::os_panic); + } + + THEN("it can be prefix-decremented") + { + --it; + REQUIRE_THROWS_AS(*it, kstd::tests::os_panic); + } + + THEN("it can be postfix-decremented") + { + auto old = it--; + REQUIRE_THROWS_AS(*it, kstd::tests::os_panic); + REQUIRE(old == copy); + } + + THEN("its distance to another iterator can be calculated") + { + auto other = cmap.begin(); + ++other; + + REQUIRE(other - it == 1); + } + + THEN("it can be compared to another iterator") + { + REQUIRE(it < cmap.end()); + REQUIRE(it <= cmap.end()); + REQUIRE(!(it > cmap.end())); + REQUIRE(!(it >= cmap.end())); + } + } + WHEN("using forward iterators") { THEN("they navigate the elements in the correct forward order") @@ -253,6 +463,7 @@ SCENARIO("Flat Map iterators", "[flat_map]") ++it; REQUIRE(it == map.end()); + REQUIRE_THROWS_AS(*it, kstd::tests::os_panic); } THEN("const forward iterators provide correct access") @@ -271,6 +482,7 @@ SCENARIO("Flat Map iterators", "[flat_map]") ++it; REQUIRE(it == map.cend()); + REQUIRE_THROWS_AS(*it, kstd::tests::os_panic); } THEN("structured bindings evaluate correctly") @@ -305,6 +517,7 @@ SCENARIO("Flat Map iterators", "[flat_map]") ++it; REQUIRE(it == map.rend()); + REQUIRE_THROWS_AS(*it, kstd::tests::os_panic); } THEN("const reverse iterators provide correct access") @@ -323,6 +536,20 @@ SCENARIO("Flat Map iterators", "[flat_map]") ++it; REQUIRE(it == map.crend()); + REQUIRE_THROWS_AS(*it, kstd::tests::os_panic); + } + + THEN("structured bindings evaluate correctly") + { + auto it = map.crbegin(); + + auto [key, value] = *it; + + REQUIRE(key == 3); + REQUIRE(value == 30); + + STATIC_REQUIRE(std::is_same_v<decltype(key), int const &>); + STATIC_REQUIRE(std::is_same_v<decltype(value), int const &>); } } } @@ -412,3 +639,86 @@ SCENARIO("Flat Map heterogeneous element access", "[flat_map]") } } } + +SCENARIO("Flat Map queries", "[flat_map]") +{ + GIVEN("A populated Flat Map") + { + auto map = kstd::flat_map<char, int>{}; + map.emplace('b', 10); + map.emplace('c', 20); + map.emplace('d', 30); + + WHEN("finding the lower bound of a key present in the map") + { + auto it = map.lower_bound('c'); + + THEN("it returns an iterator to the element") + { + REQUIRE(it != map.end()); + REQUIRE((*it).first == 'c'); + REQUIRE((*it).second == 20); + } + } + + WHEN("finding the lower bound of a key larger than any in the map") + { + auto it = map.lower_bound('e'); + + THEN("it returns an iterator to the end of the map") + { + REQUIRE(it == map.end()); + } + } + + WHEN("finding the lower bound of a key smaller than any in the map") + { + auto it = map.lower_bound('a'); + + THEN("it returns an iterator to the beginning of the map") + { + REQUIRE(it == map.begin()); + } + } + } + + GIVEN("A populated Flat Map with a transparent comparator") + { + auto map = kstd::flat_map<std::string, int, std::less<>>{}; + map.emplace("b", 10); + map.emplace("c", 20); + map.emplace("d", 30); + + WHEN("finding the lower bound of a key present in the map") + { + auto it = map.lower_bound("c"); + + THEN("it returns an iterator to the element") + { + REQUIRE(it != map.end()); + REQUIRE((*it).first == "c"); + REQUIRE((*it).second == 20); + } + } + + WHEN("finding the lower bound of a key larger than any in the map") + { + auto it = map.lower_bound("e"); + + THEN("it returns an iterator to the end of the map") + { + REQUIRE(it == map.end()); + } + } + + WHEN("finding the lower bound of a key smaller than any in the map") + { + auto it = map.lower_bound("a"); + + THEN("it returns an iterator to the beginning of the map") + { + REQUIRE(it == map.begin()); + } + } + } +} |