kstd/vector: implement insert_range

2 files changed, 362 insertions, 2 deletions

diff --git a/libs/kstd/include/kstd/vector b/libs/kstd/include/kstd/vector
index 2ecb6a8..c714957 100644
--- a/libs/kstd/include/kstd/vector
+++ b/libs/kstd/include/kstd/vector
@@ -147,8 +147,8 @@ namespace kstd
     //!
     //!
     template<typename Range>
-      requires(std::ranges::input_range<Range> && std::ranges::sized_range<Range> &&
-               std::convertible_to<std::ranges::range_reference_t<Range>, ValueType>)
+      requires((std::ranges::forward_range<Range> || std::ranges::sized_range<Range>) &&
+               kstd::bits::container_compatible_range<Range, value_type>)
     constexpr vector(kstd::from_range_t, Range && range, allocator_type const & allocator = allocator_type{})
         : m_allocator{allocator}
         , m_size{std::ranges::size(range)}
@@ -729,6 +729,75 @@ namespace kstd
       return begin() + prefix_size;
     }
 
+    //! Insert the element of a given range into the vector at a given position.
+    //!
+    //! @param range The source range to insert elements from.
+    //! @tparam SourceRange A container compatible range type.
+    template<typename SourceRange>
+      requires requires(allocator_type allocator, pointer destination, SourceRange range) {
+        requires kstd::bits::container_compatible_range<SourceRange, ValueType>;
+        requires std::move_constructible<value_type>;
+        requires std::is_move_assignable_v<value_type>;
+        requires std::swappable<value_type>;
+        std::allocator_traits<allocator_type>::construct(allocator, destination, *std::ranges::begin(range));
+      }
+    // NOLINTNEXTLINE(misc-no-recursion)
+    constexpr auto insert_range(const_iterator position, SourceRange && range) -> iterator
+    {
+      auto prefix_size = std::ranges::distance(begin(), position);
+
+      if (position == end())
+      {
+        append_range(std::forward<SourceRange>(range));
+        return begin() + prefix_size;
+      }
+
+      if constexpr (std::ranges::forward_range<SourceRange> || std::ranges::sized_range<SourceRange>)
+      {
+        auto number_of_elements = static_cast<size_type>(std::ranges::distance(range));
+        if (!number_of_elements)
+        {
+          return begin() + prefix_size;
+        }
+
+        if (capacity() - size() < number_of_elements)
+        {
+          reserve(size() + std::max(size(), number_of_elements));
+        }
+
+        auto insert_position = begin() + prefix_size;
+        auto suffix_size = static_cast<size_type>(std::ranges::distance(insert_position, end()));
+
+        if (number_of_elements >= suffix_size)
+        {
+          uninitialized_move_with_allocator(insert_position, insert_position + number_of_elements, suffix_size);
+          auto result = std::ranges::copy_n(std::ranges::begin(range), suffix_size, insert_position);
+          uninitialized_copy_with_allocator(std::move(result.in), end(), number_of_elements - suffix_size);
+        }
+        else
+        {
+          uninitialized_move_with_allocator(end() - number_of_elements, end(), number_of_elements);
+          std::ranges::move_backward(insert_position, end() - number_of_elements, end());
+          std::ranges::copy_n(std::ranges::begin(range), number_of_elements, insert_position);
+        }
+
+        m_size += number_of_elements;
+        return insert_position;
+      }
+
+      auto range_begin = std::ranges::begin(range);
+      auto range_end = std::ranges::end(range);
+
+      auto remainder = vector{get_allocator()};
+      for (; range_begin != range_end; ++range_begin)
+      {
+        remainder.emplace_back(*static_cast<std::ranges::iterator_t<SourceRange>>(range_begin));
+      }
+      reserve(size() + std::max(size(), remainder.size()));
+
+      return insert_range(begin() + prefix_size, remainder);
+    }
+
     template<typename... Args>
     constexpr auto emplace(const_iterator position, Args &&... args) -> iterator
     {
diff --git a/libs/kstd/tests/src/vector.cpp b/libs/kstd/tests/src/vector.cpp
index a02ebf0..fd44437 100644
--- a/libs/kstd/tests/src/vector.cpp
+++ b/libs/kstd/tests/src/vector.cpp
@@ -620,6 +620,92 @@ SCENARIO("Vector modifiers", "[vector]")
         REQUIRE(v[2] == 2);
       }
     }
+
+    WHEN("inserting a range at the beginning")
+    {
+      auto const arr = std::array<int, 3>{1, 2, 3};
+      auto it = v.insert_range(v.begin(), arr);
+
+      THEN("the size increases")
+      {
+        REQUIRE(v.size() == 3);
+      }
+
+      THEN("the capacity increases")
+      {
+        REQUIRE(v.capacity() >= 3);
+      }
+
+      THEN("the elements are inserted")
+      {
+        REQUIRE(v[0] == 1);
+        REQUIRE(v[1] == 2);
+        REQUIRE(v[2] == 3);
+      }
+
+      THEN("the returned iterator points to the beginning of the inserted range")
+      {
+        REQUIRE(it == v.begin());
+      }
+    }
+
+    WHEN("inserting a range at the end")
+    {
+      auto const arr = std::array<int, 3>{1, 2, 3};
+      auto it = v.insert_range(v.end(), arr);
+
+      THEN("the size increases")
+      {
+        REQUIRE(v.size() == 3);
+      }
+
+      THEN("the capacity increases")
+      {
+        REQUIRE(v.capacity() >= 3);
+      }
+
+      THEN("the elements are inserted")
+      {
+        REQUIRE(v[0] == 1);
+        REQUIRE(v[1] == 2);
+        REQUIRE(v[2] == 3);
+      }
+
+      THEN("the returned iterator points to the beginning of the inserted range")
+      {
+        REQUIRE(it == v.begin());
+      }
+    }
+
+    WHEN("inserting from an input range without sufficient capacity")
+    {
+      auto const arr = std::array<int, 3>{1, 2, 3};
+      auto const first = kstd::tests::test_input_iterator{arr.data(), arr.size()};
+      auto const last = kstd::tests::test_input_iterator{};
+      auto it = v.insert_range(v.begin(), std::ranges::subrange{first, last});
+
+      THEN("the size increases")
+      {
+        REQUIRE(v.size() == 3);
+      }
+
+      THEN("the capacity increases")
+      {
+        REQUIRE(v.capacity() >= 3);
+      }
+
+      THEN("the elements are inserted")
+      {
+        REQUIRE(v[0] == 1);
+        REQUIRE(v[1] == 2);
+        REQUIRE(v[2] == 3);
+      }
+
+      THEN("the returned iterator points to the beginning of the inserted range")
+      {
+        REQUIRE(it == v.begin());
+      }
+    }
   }
 
   GIVEN("A populated vector")
@@ -1000,6 +1086,211 @@ SCENARIO("Vector modifiers", "[vector]")
         REQUIRE(v[0] == 10);
       }
     }
+
+    WHEN("inserting an empty range")
+    {
+      auto initial_size = v.size();
+      auto it = v.insert_range(v.begin(), std::views::empty<int>);
+
+      THEN("the size does not change")
+      {
+        REQUIRE(v.size() == initial_size);
+      }
+
+      THEN("the capacity does not change")
+      {
+        REQUIRE(v.capacity() == initial_capacity);
+      }
+
+      THEN("the content is unchanged")
+      {
+        REQUIRE(v[0] == 10);
+        REQUIRE(v[1] == 20);
+        REQUIRE(v[2] == 30);
+      }
+
+      THEN("the returned iterator points to the position of insertion")
+      {
+        REQUIRE(it == v.begin());
+      }
+    }
+
+    WHEN("inserting a range at the beginning")
+    {
+      auto initial_size = v.size();
+      auto const arr = std::array<int, 3>{1, 2, 3};
+      auto it = v.insert_range(v.begin(), arr);
+
+      THEN("the size increases")
+      {
+        REQUIRE(v.size() == initial_size + 3);
+      }
+
+      THEN("the capacity increases")
+      {
+        REQUIRE(v.capacity() >= initial_size + 3);
+      }
+
+      THEN("the elements are inserted")
+      {
+        REQUIRE(v[0] == 1);
+        REQUIRE(v[1] == 2);
+        REQUIRE(v[2] == 3);
+        REQUIRE(v[3] == 10);
+        REQUIRE(v[4] == 20);
+        REQUIRE(v[5] == 30);
+      }
+
+      THEN("the returned iterator points to the beginning of the inserted range")
+      {
+        REQUIRE(it == v.begin());
+      }
+    }
+
+    WHEN("inserting a range at the end")
+    {
+      auto initial_size = v.size();
+      auto const arr = std::array<int, 3>{1, 2, 3};
+      auto it = v.insert_range(v.end(), arr);
+
+      THEN("the size increases")
+      {
+        REQUIRE(v.size() == initial_size + 3);
+      }
+
+      THEN("the capacity increases")
+      {
+        REQUIRE(v.capacity() >= initial_size + 3);
+      }
+
+      THEN("the elements are inserted")
+      {
+        REQUIRE(v[0] == 10);
+        REQUIRE(v[1] == 20);
+        REQUIRE(v[2] == 30);
+        REQUIRE(v[3] == 1);
+        REQUIRE(v[4] == 2);
+        REQUIRE(v[5] == 3);
+      }
+
+      THEN("the returned iterator points to the beginning of the inserted range")
+      {
+        REQUIRE(it == v.begin() + initial_size);
+      }
+    }
+
+    WHEN("inserting a range that causes reallocation")
+    {
+      auto initial_size = v.size();
+      auto const arr = std::array<int, 3>{1, 2, 3};
+      auto it = v.insert_range(v.begin() + 1, arr);
+
+      THEN("the size increases")
+      {
+        REQUIRE(v.size() == initial_size + 3);
+      }
+
+      THEN("the capacity increases")
+      {
+        REQUIRE(v.capacity() >= initial_size + 3);
+      }
+
+      THEN("the elements are inserted")
+      {
+        REQUIRE(v[0] == 10);
+        REQUIRE(v[1] == 1);
+        REQUIRE(v[2] == 2);
+        REQUIRE(v[3] == 3);
+        REQUIRE(v[4] == 20);
+        REQUIRE(v[5] == 30);
+      }
+
+      THEN("the returned iterator points to the beginning of the inserted range")
+      {
+        REQUIRE(it == v.begin() + 1);
+      }
+    }
+
+    WHEN("inserting fewer elements than the suffix without reallocation")
+    {
+      v.reserve(10);
+      auto const capacity = v.capacity();
+      auto const arr = std::array<int, 1>{1};
+      auto it = v.insert_range(v.begin() + 1, arr);
+
+      THEN("the elements are correctly placed")
+      {
+        REQUIRE(v.size() == 4);
+        REQUIRE(v[0] == 10);
+        REQUIRE(v[1] == 1);
+        REQUIRE(v[2] == 20);
+        REQUIRE(v[3] == 30);
+      }
+
+      THEN("no reallocation occurs")
+      {
+        REQUIRE(v.capacity() == capacity);
+      }
+
+      THEN("the returned iterator points to the inserted element")
+      {
+        REQUIRE(it == v.begin() + 1);
+      }
+    }
+
+    WHEN("inserting fewer elements than the suffix without sufficient capacity")
+    {
+      v.shrink_to_fit();
+      auto const arr = std::array<int, 1>{1};
+      auto it = v.insert_range(v.begin() + 1, arr);
+
+      THEN("the elements are correctly placed")
+      {
+        REQUIRE(v.size() == 4);
+        REQUIRE(v[0] == 10);
+        REQUIRE(v[1] == 1);
+        REQUIRE(v[2] == 20);
+        REQUIRE(v[3] == 30);
+      }
+
+      THEN("the returned iterator points to the inserted element")
+      {
+        REQUIRE(it == v.begin() + 1);
+      }
+    }
+
+    WHEN("inserting from an input range without sufficient capacity")
+    {
+      auto const arr = std::array<int, 3>{1, 2, 3};
+      auto const first = kstd::tests::test_input_iterator{arr.data(), arr.size()};
+      auto const last = kstd::tests::test_input_iterator{};
+      auto it = v.insert_range(v.begin(), std::ranges::subrange{first, last});
+
+      THEN("the size increases")
+      {
+        REQUIRE(v.size() == 6);
+      }
+
+      THEN("the capacity increases")
+      {
+        REQUIRE(v.capacity() >= 6);
+      }
+
+      THEN("the elements are inserted")
+      {
+        REQUIRE(v[0] == 1);
+        REQUIRE(v[1] == 2);
+        REQUIRE(v[2] == 3);
+        REQUIRE(v[3] == 10);
+        REQUIRE(v[4] == 20);
+        REQUIRE(v[5] == 30);
+      }
+
+      THEN("the returned iterator points to the beginning of the inserted range")
+      {
+        REQUIRE(it == v.begin());
+      }
+    }
   }
 }