Merge branch 'fmorgner/interrupt-handling' into develop-BA-FS26

3 files changed, 446 insertions, 1 deletions

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/include/kstd/vector b/libs/kstd/include/kstd/vector
index 0d4aac8..9e41cb6 100644
--- a/libs/kstd/include/kstd/vector
+++ b/libs/kstd/include/kstd/vector
@@ -548,7 +548,6 @@ namespace kstd
       if (new_capacity > max_size())
       {
         kstd::os::panic("[kstd:vector] Tried to reserve more space than theoretically possible.");
-        return;
       }
 
       auto new_data = allocate_n(new_capacity);
@@ -690,6 +689,50 @@ namespace kstd
       return begin() + prefix_size;
     }
 
+    //! Erase an element at a given position.
+    //!
+    //! @note This function will panic if position == end()
+    //!
+    //! @param position An interator pointing to the element to delete
+    //! @return An iterator pointing to the element after the deleted element
+    constexpr auto erase(const_iterator position) -> iterator
+    {
+      if (position == end())
+      {
+        os::panic("[kstd:vector] Attempted to erase end()!");
+      }
+
+      auto prefix_size = std::ranges::distance(cbegin(), position);
+
+      std::ranges::move(begin() + prefix_size + 1, end(), begin() + prefix_size);
+      std::allocator_traits<allocator_type>::destroy(m_allocator, end() - 1);
+      --m_size;
+
+      return begin() + prefix_size;
+    }
+
+    //! Erase a range of elements from this vector.
+    //!
+    //! @param first The start of the range to erase.
+    //! @param last The end of the range to erase.
+    //! @return An iterator pointing to the element after the last deleted element.
+    constexpr auto erase(const_iterator first, const_iterator last) -> iterator
+    {
+      if (first == last)
+      {
+        return begin() + std::ranges::distance(cbegin(), first);
+      }
+
+      auto prefix_size = std::ranges::distance(cbegin(), first);
+      auto element_count = std::ranges::distance(first, last);
+
+      std::ranges::move(begin() + prefix_size + element_count, end(), begin() + prefix_size);
+      destroy_n(end() - element_count, element_count);
+      m_size -= element_count;
+
+      return begin() + prefix_size;
+    }
+
     //! Append a given element to this vector via copy construction.
     constexpr auto push_back(value_type const & value) -> void
     {