aboutsummaryrefslogtreecommitdiff
path: root/libs
diff options
context:
space:
mode:
Diffstat (limited to 'libs')
-rw-r--r--libs/kstd/CMakeLists.txt1
-rw-r--r--libs/kstd/include/kstd/bits/flat_map.hpp82
-rw-r--r--libs/kstd/include/kstd/flat_map320
-rw-r--r--libs/kstd/tests/src/flat_map.cpp288
4 files changed, 691 insertions, 0 deletions
diff --git a/libs/kstd/CMakeLists.txt b/libs/kstd/CMakeLists.txt
index 06543ab..ff3c8cc 100644
--- a/libs/kstd/CMakeLists.txt
+++ b/libs/kstd/CMakeLists.txt
@@ -44,6 +44,7 @@ endif()
if(NOT CMAKE_CROSSCOMPILING)
add_executable("kstd_tests"
+ "tests/src/flat_map.cpp"
"tests/src/vector.cpp"
"tests/src/os_panic.cpp"
)
diff --git a/libs/kstd/include/kstd/bits/flat_map.hpp b/libs/kstd/include/kstd/bits/flat_map.hpp
new file mode 100644
index 0000000..903841e
--- /dev/null
+++ b/libs/kstd/include/kstd/bits/flat_map.hpp
@@ -0,0 +1,82 @@
+#ifndef KSTD_BITS_FLAT_MAP_HPP
+#define KSTD_BITS_FLAT_MAP_HPP
+
+#include <cstddef>
+#include <iterator>
+#include <utility>
+
+namespace kstd::bits
+{
+
+ template<typename KeyType, typename MappedType, typename KeyIterator, typename MappedIterator>
+ struct flat_map_iterator
+ {
+ using iterator_category = std::random_access_iterator_tag;
+ using value_type = std::pair<KeyType, MappedType>;
+ using difference_type = std::ptrdiff_t;
+ using reference = std::pair<KeyType const &, MappedType &>;
+ using pointer = void;
+
+ constexpr flat_map_iterator(KeyIterator key_iterator, MappedIterator mapped_iterator)
+ : m_key_iterator{key_iterator}
+ , m_mapped_iterator{mapped_iterator}
+ {}
+
+ [[nodiscard]] auto key_iterator() const noexcept -> KeyIterator
+ {
+ return m_key_iterator;
+ }
+
+ [[nodiscard]] constexpr auto operator*() const noexcept -> reference
+ {
+ return {*m_key_iterator, *m_mapped_iterator};
+ }
+
+ constexpr auto operator++() noexcept -> flat_map_iterator &
+ {
+ ++m_key_iterator;
+ ++m_mapped_iterator;
+ return *this;
+ }
+
+ constexpr auto operator++(int) noexcept -> flat_map_iterator
+ {
+ auto copy = *this;
+ ++(*this);
+ return copy;
+ }
+
+ constexpr auto operator--() noexcept -> flat_map_iterator &
+ {
+ --m_key_iterator;
+ --m_mapped_iterator;
+ return *this;
+ }
+
+ constexpr auto operator--(int) noexcept -> flat_map_iterator
+ {
+ auto copy = *this;
+ --(*this);
+ return copy;
+ }
+
+ [[nodiscard]] constexpr auto operator+(difference_type offset) const noexcept -> flat_map_iterator
+ {
+ return {m_key_iterator + offset, m_mapped_iterator + offset};
+ }
+
+ [[nodiscard]] constexpr auto operator-(flat_map_iterator const & other) const noexcept -> difference_type
+ {
+ return m_key_iterator - other.m_key_iterator;
+ }
+
+ [[nodiscard]] constexpr auto operator<=>(flat_map_iterator const & other) const noexcept = default;
+
+ private:
+ KeyIterator m_key_iterator{};
+ MappedIterator m_mapped_iterator{};
+ };
+
+} // namespace kstd::bits
+
+#endif \ No newline at end of file
diff --git a/libs/kstd/include/kstd/flat_map b/libs/kstd/include/kstd/flat_map
new file mode 100644
index 0000000..6ffbbcf
--- /dev/null
+++ b/libs/kstd/include/kstd/flat_map
@@ -0,0 +1,320 @@
+#ifndef KSTD_FLAT_MAP_HPP
+#define KSTD_FLAT_MAP_HPP
+
+#include <kstd/bits/flat_map.hpp>
+#include <kstd/os/error.hpp>
+#include <kstd/vector>
+
+#include <algorithm>
+#include <concepts>
+#include <cstddef>
+#include <functional>
+#include <iterator>
+#include <utility>
+
+namespace kstd
+{
+
+ template<typename KeyType, typename MappedType, typename KeyCompare = std::less<KeyType>,
+ typename KeyContainerType = kstd::vector<KeyType>, typename MappedContainerType = kstd::vector<MappedType>>
+ struct flat_map
+ {
+ using key_container_type = KeyContainerType;
+ using mapped_container_type = MappedContainerType;
+ using key_type = KeyType;
+ using mapped_type = MappedType;
+ using value_type = std::pair<key_type, mapped_type>;
+ using key_compare = KeyCompare;
+ using reference = std::pair<key_type const &, mapped_type &>;
+ using const_reference = std::pair<key_type const &, mapped_type const &>;
+ using size_type = std::size_t;
+ using difference_type = std::ptrdiff_t;
+ using iterator = bits::flat_map_iterator<KeyType, MappedType, typename key_container_type::iterator,
+ typename mapped_container_type::iterator>;
+ using const_iterator =
+ bits::flat_map_iterator<KeyType, MappedType const, typename key_container_type::const_iterator,
+ typename mapped_container_type::const_iterator>;
+ using reverse_iterator = std::reverse_iterator<iterator>;
+ using const_reverse_iterator = std::reverse_iterator<const_iterator>;
+ using containers = struct
+ {
+ key_container_type keys;
+ mapped_container_type values;
+ };
+
+ //! Compare two object of type value_type.
+ struct value_compare
+ {
+ constexpr auto operator()(const_reference lhs, const_reference rhs) const -> bool
+ {
+ return lhs.first < rhs.first;
+ }
+ };
+
+ //! Construct an empty flat map.
+ constexpr flat_map()
+ : flat_map{key_compare{}}
+ {}
+
+ //! Construct an empty flat map using the given custom comparator.
+ //!
+ //! @param comparator The comparator to use for comparing keys.
+ constexpr explicit flat_map(key_compare const & comparator)
+ : m_containers{}
+ , m_comparator{comparator}
+ {}
+
+ //! Get a reference to the mapped value associated with the given key.
+ //!
+ //! @warning This function will panic if the key is not found.
+ //! @param key The key to look up.
+ //! @return A reference to the mapped value.
+ [[nodiscard]] constexpr auto at(key_type const & key) -> mapped_type &
+ {
+ auto found = std::ranges::lower_bound(m_containers.keys, key, m_comparator);
+ if (found != m_containers.keys.cend() && !m_comparator(key, *found) && !m_comparator(*found, key))
+ {
+ auto offset = std::distance(m_containers.keys.begin(), found);
+ return *(m_containers.values.begin() + offset);
+ }
+ os::panic("[kstd::flat_map] Key not found");
+ }
+
+ //! Get a reference to the mapped value associated with the given key.
+ //!
+ //! @warning This function will panic if the key is not found.
+ //! @param key The key to look up.
+ //! @return A const reference to the mapped value.
+ [[nodiscard]] constexpr auto at(key_type const & key) const -> mapped_type const &
+ {
+ auto found = std::ranges::lower_bound(m_containers.keys, key, m_comparator);
+ if (found != m_containers.keys.cend() && !m_comparator(key, *found) && !m_comparator(*found, key))
+ {
+ auto offset = std::distance(m_containers.keys.cbegin(), found);
+ return *(m_containers.values.cbegin() + offset);
+ }
+ os::panic("[kstd::flat_map] Key not found");
+ }
+
+ //! Get a reference to the mapped value associated with the given key.
+ //!
+ //! @note This overload only participates in overload resolution if the key compare type is transparent.
+ //! @warning This function will panic if the key is not found.
+ //! @param x The key to look up.
+ //! @return A reference to the mapped value.
+ template<typename K>
+ requires requires(K const & k, key_type const & l) { typename key_compare::is_transparent; }
+ [[nodiscard]] constexpr auto at(K const & x) -> mapped_type &
+ {
+ auto found = find(x);
+ if (found != end())
+ {
+ auto offset = std::distance(m_containers.keys.begin(), found.key_iterator());
+ return *(m_containers.values.begin() + offset);
+ }
+ os::panic("[kstd::flat_map] Key not found");
+ }
+
+ //! Get a reference to the mapped value associated with the given key.
+ //! @note This overload only participates in overload resolution if the key compare type is transparent.
+ //! @warning This function will panic if the key is not found.
+ //! @param x The key to look up.
+ //! @return A const reference to the mapped value.
+ template<typename K>
+ requires requires(K const & k, key_type const & l) { typename key_compare::is_transparent; }
+ [[nodiscard]] auto at(K const & x) const -> mapped_type const &
+ {
+ auto found = find(x);
+ if (found != end())
+ {
+ auto offset = std::distance(m_containers.keys.cbegin(), found.key_iterator());
+ return *(m_containers.values.cbegin() + offset);
+ }
+ os::panic("[kstd::flat_map] Key not found");
+ }
+
+ //! Get an iterator to the first element.
+ [[nodiscard]] auto begin() noexcept -> iterator
+ {
+ return iterator{m_containers.keys.begin(), m_containers.values.begin()};
+ }
+
+ //! Get an iterator to the first element.
+ [[nodiscard]] auto begin() const noexcept -> const_iterator
+ {
+ return const_iterator{m_containers.keys.cbegin(), m_containers.values.cbegin()};
+ }
+
+ //! Get an iterator to the first element.
+ [[nodiscard]] auto cbegin() const noexcept -> const_iterator
+ {
+ return const_iterator{m_containers.keys.cbegin(), m_containers.values.cbegin()};
+ }
+
+ //! Get an iterator to the element past the last element.
+ [[nodiscard]] auto end() noexcept -> iterator
+ {
+ return iterator{m_containers.keys.end(), m_containers.values.end()};
+ }
+
+ //! Get an iterator to the element past the last element.
+ [[nodiscard]] auto end() const noexcept -> const_iterator
+ {
+ return const_iterator{m_containers.keys.cend(), m_containers.values.cend()};
+ }
+
+ //! Get an iterator to the element past the last element.
+ [[nodiscard]] auto cend() const noexcept -> const_iterator
+ {
+ return const_iterator{m_containers.keys.cend(), m_containers.values.cend()};
+ }
+
+ //! Get an iterator to the first element.
+ [[nodiscard]] auto rbegin() noexcept -> reverse_iterator
+ {
+ return reverse_iterator{end()};
+ }
+
+ //! Get an iterator to the first element.
+ [[nodiscard]] auto rbegin() const noexcept -> const_reverse_iterator
+ {
+ return const_reverse_iterator{cend()};
+ }
+
+ //! Get an iterator to the first element.
+ [[nodiscard]] auto crbegin() const noexcept -> const_reverse_iterator
+ {
+ return const_reverse_iterator{cend()};
+ }
+
+ //! Get an iterator to the element past the last element.
+ [[nodiscard]] auto rend() noexcept -> reverse_iterator
+ {
+ return reverse_iterator{begin()};
+ }
+
+ //! Get an iterator to the element past the last element.
+ [[nodiscard]] auto rend() const noexcept -> const_reverse_iterator
+ {
+ return const_reverse_iterator{cbegin()};
+ }
+
+ //! Get an iterator to the element past the last element.
+ [[nodiscard]] auto crend() const noexcept -> const_reverse_iterator
+ {
+ return const_reverse_iterator{cbegin()};
+ }
+
+ //! 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.
+ template<typename... Args>
+ auto emplace(Args &&... args) -> std::pair<iterator, bool>
+ requires std::constructible_from<value_type, Args...>
+ {
+ auto value = value_type{std::forward<Args>(args)...};
+ auto found = std::ranges::lower_bound(m_containers.keys, value.first, m_comparator);
+
+ if (found != m_containers.keys.cend() && !m_comparator(value.first, *found) && !m_comparator(*found, value.first))
+ {
+ auto offset = std::distance(m_containers.keys.begin(), found);
+ return {
+ iterator{m_containers.keys.begin() + offset, m_containers.values.begin() + offset},
+ false
+ };
+ }
+
+ auto offset = std::distance(m_containers.keys.begin(), found);
+ auto key_iterator = m_containers.keys.begin() + offset;
+ auto mapped_iterator = m_containers.values.begin() + offset;
+
+ auto inserted_key = m_containers.keys.insert(key_iterator, std::move(value.first));
+ auto inserted_mapped = m_containers.values.insert(mapped_iterator, std::move(value.second));
+
+ return {
+ iterator{inserted_key, inserted_mapped},
+ true
+ };
+ }
+
+ //! Find an element with an equivalent key.
+ //!
+ //! @param key The key to look up.
+ //! @return An iterator to the element with the equivalent key, or end() if no such element is found.
+ [[nodiscard]] auto find(key_type const & key) noexcept -> iterator
+ {
+ auto found = std::ranges::lower_bound(m_containers.keys, key, m_comparator);
+ if (found != m_containers.keys.cend() && !m_comparator(key, *found) && !m_comparator(*found, key))
+ {
+ auto offset = std::distance(m_containers.keys.begin(), found);
+ return iterator{m_containers.keys.begin() + offset, m_containers.values.begin() + offset};
+ }
+ return end();
+ }
+
+ //! Find an element with an equivalent key.
+ //!
+ //! @param key The key to look up.
+ //! @return An iterator to the element with the equivalent key, or end() if no such element is found.
+ [[nodiscard]] auto find(key_type const & key) const noexcept -> const_iterator
+ {
+ auto found = std::ranges::lower_bound(m_containers.keys, key, m_comparator);
+ if (found != m_containers.keys.cend() && !m_comparator(key, *found) && !m_comparator(*found, key))
+ {
+ auto offset = std::distance(m_containers.keys.cbegin(), found);
+ return const_iterator{m_containers.keys.cbegin() + offset, m_containers.values.cbegin() + offset};
+ }
+ return cend();
+ }
+
+ //! Find an element with an equivalent key.
+ //! @note This overload only participates in overload resolution if the key compare type is transparent.
+ //! @param x The key to look up.
+ //! @return An iterator to the element with the equivalent key, or end() if no such element is found.
+ template<typename K>
+ requires requires(K const & k, key_type const & l) { typename key_compare::is_transparent; }
+ [[nodiscard]] auto find(K const & x) noexcept -> iterator
+ {
+ auto found = std::ranges::lower_bound(m_containers.keys, x, m_comparator);
+ if (found != m_containers.keys.cend() && !m_comparator(x, *found) && !m_comparator(*found, x))
+ {
+ auto offset = std::distance(m_containers.keys.begin(), found);
+ return iterator{m_containers.keys.begin() + offset, m_containers.values.begin() + offset};
+ }
+ return end();
+ }
+
+ //! Find an element with an equivalent key.
+ //! @note This overload only participates in overload resolution if the key compare type is transparent.
+ //! @param x The key to look up.
+ //! @return An iterator to the element with the equivalent key, or end() if no such element is found.
+ template<typename K>
+ requires requires(K const & k, key_type const & l) { typename key_compare::is_transparent; }
+ [[nodiscard]] auto find(K const & x) const noexcept -> const_iterator
+ {
+ auto found = std::ranges::lower_bound(m_containers.keys, x, m_comparator);
+ if (found != m_containers.keys.cend() && !m_comparator(x, *found) && !m_comparator(*found, x))
+ {
+ auto offset = std::distance(m_containers.keys.cbegin(), found);
+ return const_iterator{m_containers.keys.cbegin() + offset, m_containers.values.cbegin() + offset};
+ }
+ return cend();
+ }
+
+ //! Check if the map contains the given key.
+ //!
+ //! @param key The key to check.
+ //! @return true iff. the key is found, false otherwise.
+ [[nodiscard]] constexpr auto contains(key_type const & key) const noexcept -> bool
+ {
+ return find(key) != cend();
+ }
+
+ private:
+ containers m_containers;
+ key_compare m_comparator;
+ };
+} // namespace kstd
+
+#endif \ No newline at end of file
diff --git a/libs/kstd/tests/src/flat_map.cpp b/libs/kstd/tests/src/flat_map.cpp
new file mode 100644
index 0000000..cde136a
--- /dev/null
+++ b/libs/kstd/tests/src/flat_map.cpp
@@ -0,0 +1,288 @@
+#include <kstd/flat_map>
+#include <kstd/tests/os_panic.hpp>
+
+#include <catch2/catch_test_macros.hpp>
+
+#include <functional>
+
+SCENARIO("Flat Map initialization and construction", "[flat_map]")
+{
+ GIVEN("An empty context")
+ {
+ WHEN("constructing by default")
+ {
+ auto map = kstd::flat_map<int, int>{};
+
+ THEN("the Flat Map does not contain elements")
+ {
+ REQUIRE_FALSE(map.contains(1));
+ }
+ }
+ }
+}
+
+SCENARIO("Flat Map modifiers", "[flat_map]")
+{
+ GIVEN("An empty Flat Map")
+ {
+ auto map = kstd::flat_map<int, int>{};
+
+ WHEN("emplacing a new element")
+ {
+ auto [it, inserted] = map.emplace(1, 100);
+
+ THEN("the map contains the new element")
+ {
+ REQUIRE(inserted);
+ REQUIRE(map.contains(1));
+ }
+ }
+
+ WHEN("emplacing an existing element")
+ {
+ map.emplace(1, 100);
+ auto [it, inserted] = map.emplace(1, 200);
+
+ THEN("the map does not insert the duplicate")
+ {
+ REQUIRE_FALSE(inserted);
+ REQUIRE(map.contains(1));
+ }
+ }
+ }
+}
+
+SCENARIO("Flat Map element access", "[flat_map]")
+{
+ GIVEN("A populated Flat Map")
+ {
+ auto map = kstd::flat_map<int, int>{};
+ map.emplace(1, 10);
+ map.emplace(2, 20);
+ map.emplace(3, 30);
+
+ WHEN("accessing an existing element with at()")
+ {
+ auto & val = map.at(2);
+
+ THEN("it returns a reference to the mapped value")
+ {
+ REQUIRE(val == 20);
+ }
+
+ THEN("the mapped value can be modified")
+ {
+ val = 200;
+ REQUIRE(map.at(2) == 200);
+ }
+ }
+
+ WHEN("accessing a non-existent element with at()")
+ {
+ THEN("it panics")
+ {
+ REQUIRE_THROWS_AS(map.at(4), kstd::tests::os_panic);
+ }
+ }
+ }
+
+ GIVEN("A const populated Flat Map")
+ {
+ auto map_builder = kstd::flat_map<int, int>{};
+ map_builder.emplace(1, 10);
+ map_builder.emplace(2, 20);
+ auto const map = map_builder;
+
+ WHEN("accessing an existing element with const at()")
+ {
+ auto const & val = map.at(2);
+
+ THEN("it returns a const reference to the mapped value")
+ {
+ REQUIRE(val == 20);
+ }
+ }
+
+ WHEN("accessing a non-existent element with const at()")
+ {
+ THEN("it panics")
+ {
+ REQUIRE_THROWS_AS(map.at(4), kstd::tests::os_panic);
+ }
+ }
+ }
+}
+
+SCENARIO("Flat Map iterators", "[flat_map]")
+{
+ GIVEN("A populated Flat Map")
+ {
+ auto map = kstd::flat_map<int, int>{};
+ map.emplace(1, 10);
+ map.emplace(2, 20);
+ map.emplace(3, 30);
+
+ WHEN("using forward iterators")
+ {
+ THEN("they navigate the elements in the correct forward order")
+ {
+ auto it = map.begin();
+ REQUIRE(it != map.end());
+ REQUIRE((*it).first == 1);
+
+ ++it;
+ REQUIRE(it != map.end());
+ REQUIRE((*it).first == 2);
+
+ ++it;
+ REQUIRE(it != map.end());
+ REQUIRE((*it).first == 3);
+
+ ++it;
+ REQUIRE(it == map.end());
+ }
+
+ THEN("const forward iterators provide correct access")
+ {
+ auto it = map.cbegin();
+ REQUIRE(it != map.cend());
+ REQUIRE((*it).first == 1);
+
+ ++it;
+ REQUIRE(it != map.cend());
+ REQUIRE((*it).first == 2);
+
+ ++it;
+ REQUIRE(it != map.cend());
+ REQUIRE((*it).first == 3);
+
+ ++it;
+ REQUIRE(it == map.cend());
+ }
+ }
+
+ WHEN("using reverse iterators")
+ {
+ THEN("they navigate the elements in the correct reverse order")
+ {
+ auto it = map.rbegin();
+ REQUIRE(it != map.rend());
+ REQUIRE((*it).first == 3);
+
+ ++it;
+ REQUIRE(it != map.rend());
+ REQUIRE((*it).first == 2);
+
+ ++it;
+ REQUIRE(it != map.rend());
+ REQUIRE((*it).first == 1);
+
+ ++it;
+ REQUIRE(it == map.rend());
+ }
+
+ THEN("const reverse iterators provide correct access")
+ {
+ auto it = map.crbegin();
+ REQUIRE(it != map.crend());
+ REQUIRE((*it).first == 3);
+
+ ++it;
+ REQUIRE(it != map.crend());
+ REQUIRE((*it).first == 2);
+
+ ++it;
+ REQUIRE(it != map.crend());
+ REQUIRE((*it).first == 1);
+
+ ++it;
+ REQUIRE(it == map.crend());
+ }
+ }
+ }
+
+ GIVEN("an empty Flat Map")
+ {
+ auto map = kstd::flat_map<int, int>{};
+
+ WHEN("getting iterators")
+ {
+ THEN("begin() equals end() and cbegin() equals cend()")
+ {
+ REQUIRE(map.begin() == map.end());
+ REQUIRE(map.cbegin() == map.cend());
+ }
+
+ THEN("rbegin() equals rend() and crbegin() equals crend()")
+ {
+ REQUIRE(map.rbegin() == map.rend());
+ REQUIRE(map.crbegin() == map.crend());
+ }
+ }
+ }
+}
+
+SCENARIO("Flat Map heterogeneous element access", "[flat_map]")
+{
+ GIVEN("A populated Flat Map with a transparent comparator")
+ {
+ auto map = kstd::flat_map<int, int, std::less<void>>{};
+ map.emplace(1, 10);
+ map.emplace(2, 20);
+ map.emplace(3, 30);
+
+ WHEN("accessing an existing element with a different key type via at()")
+ {
+ long const key = 2L;
+ auto & val = map.at(key);
+
+ THEN("it returns a reference to the mapped value")
+ {
+ REQUIRE(val == 20);
+ }
+
+ THEN("the mapped value can be modified")
+ {
+ val = 200;
+ REQUIRE(map.at(2L) == 200);
+ }
+ }
+
+ WHEN("accessing a non-existent element with a different key type via at()")
+ {
+ long const key = 4L;
+ THEN("it panics")
+ {
+ REQUIRE_THROWS_AS(map.at(key), kstd::tests::os_panic);
+ }
+ }
+ }
+
+ GIVEN("A const populated Flat Map with a transparent comparator")
+ {
+ auto map_builder = kstd::flat_map<int, int, std::less<void>>{};
+ map_builder.emplace(1, 10);
+ map_builder.emplace(2, 20);
+ auto const map = map_builder;
+
+ WHEN("accessing an existing element with a different key type via const at()")
+ {
+ long const key = 2L;
+ auto const & val = map.at(key);
+
+ THEN("it returns a const reference to the mapped value")
+ {
+ REQUIRE(val == 20);
+ }
+ }
+
+ WHEN("accessing a non-existent element with a different key type via const at()")
+ {
+ long const key = 4L;
+ THEN("it panics")
+ {
+ REQUIRE_THROWS_AS(map.at(key), kstd::tests::os_panic);
+ }
+ }
+ }
+}
generated by cgit v1.2.3 (git 2.25.1) at 2026-04-17 07:52:19 +0000