kstd/vector: add basic insert overloads

2 files changed, 262 insertions, 28 deletions

diff --git a/libs/kstd/include/kstd/vector b/libs/kstd/include/kstd/vector
index 5655854..0d4aac8 100644
--- a/libs/kstd/include/kstd/vector
+++ b/libs/kstd/include/kstd/vector
@@ -259,7 +259,7 @@ namespace kstd
       if (capacity() >= other.size())
       {
         auto const overlap = std::min(m_size, other.m_size);
-        copy_elements(other.begin(), begin(), overlap);
+        std::ranges::copy(other.begin(), other.begin() + overlap, begin());
 
         if (m_size < other.m_size)
         {
@@ -317,7 +317,7 @@ namespace kstd
         if (capacity() >= other.size())
         {
           auto const overlap = std::min(size(), other.size());
-          move_elements(other.begin(), begin(), overlap);
+          std::ranges::move(other.begin(), other.begin() + overlap, begin());
 
           if (size() < other.size())
           {
@@ -590,6 +590,106 @@ namespace kstd
       m_size = 0;
     }
 
+    //! Insert an element at a given position.
+    //!
+    //! @param position The position to insert the element at.
+    //! @param value The value to insert.
+    //! @return An iterator to the inserted element.
+    constexpr auto insert(const_iterator position, value_type const & value) -> iterator
+    {
+      auto prefix_size = std::ranges::distance(begin(), position);
+      auto suffix_size = std::ranges::distance(position, end());
+
+      if (position == end())
+      {
+        push_back(value);
+        return begin() + prefix_size;
+      }
+
+      if (m_capacity == m_size)
+      {
+        auto new_capacity = m_capacity == 0 ? 1 : m_capacity * 2;
+        auto new_data = allocate_n(new_capacity);
+        auto old_size = size();
+        std::allocator_traits<allocator_type>::construct(m_allocator, new_data + prefix_size, value);
+        uninitialized_move_with_allocator(begin(), new_data, prefix_size);
+        uninitialized_move_with_allocator(begin() + prefix_size, new_data + prefix_size + 1, suffix_size);
+        destroy_n(begin(), old_size);
+        deallocate();
+        m_data = new_data;
+        m_capacity = new_capacity;
+        m_size = old_size;
+      }
+      else if (&value >= begin() && &value < end())
+      {
+        auto value_copy = value;
+        auto insert_position = begin() + prefix_size;
+        std::allocator_traits<allocator_type>::construct(m_allocator, end(), std::move(*(end() - 1)));
+        std::ranges::move_backward(insert_position, end() - 1, end());
+        *insert_position = std::move(value_copy);
+      }
+      else
+      {
+        auto insert_position = begin() + prefix_size;
+        std::allocator_traits<allocator_type>::construct(m_allocator, end(), std::move(*(end() - 1)));
+        std::ranges::move_backward(insert_position, end() - 1, end());
+        *insert_position = value;
+      }
+
+      ++m_size;
+      return begin() + prefix_size;
+    }
+
+    //! Insert an element at a given position.
+    //!
+    //! @param position The position to insert the element at.
+    //! @param value The value to insert.
+    //! @return An iterator to the inserted element.
+    constexpr auto insert(const_iterator position, value_type && value) -> iterator
+    {
+      auto prefix_size = std::ranges::distance(begin(), position);
+      auto suffix_size = std::ranges::distance(position, end());
+
+      if (position == end())
+      {
+        push_back(std::move(value));
+        return begin() + prefix_size;
+      }
+
+      if (m_capacity == m_size)
+      {
+        auto new_capacity = m_capacity == 0 ? 1 : m_capacity * 2;
+        auto new_data = allocate_n(new_capacity);
+        auto old_size = size();
+        std::allocator_traits<allocator_type>::construct(m_allocator, new_data + prefix_size, std::move(value));
+        uninitialized_move_with_allocator(begin(), new_data, prefix_size);
+        uninitialized_move_with_allocator(begin() + prefix_size, new_data + prefix_size + 1, suffix_size);
+        destroy_n(begin(), old_size);
+        deallocate();
+        m_data = new_data;
+        m_capacity = new_capacity;
+        m_size = old_size;
+      }
+      else if (&value >= begin() && &value < end())
+      {
+        auto value_copy = std::move(value);
+        auto insert_position = begin() + prefix_size;
+        std::allocator_traits<allocator_type>::construct(m_allocator, end(), std::move(*(end() - 1)));
+        std::ranges::move_backward(insert_position, end() - 1, end());
+        *insert_position = std::move(value_copy);
+      }
+      else
+      {
+        auto insert_position = begin() + prefix_size;
+        std::allocator_traits<allocator_type>::construct(m_allocator, end(), std::move(*(end() - 1)));
+        std::ranges::move_backward(insert_position, end() - 1, end());
+        *insert_position = std::move(value);
+      }
+
+      ++m_size;
+      return begin() + prefix_size;
+    }
+
     //! Append a given element to this vector via copy construction.
     constexpr auto push_back(value_type const & value) -> void
     {
@@ -690,19 +790,6 @@ namespace kstd
       deallocate();
     }
 
-    //! Copy a number of elements from one storage location to another.
-    //!
-    //! @param from The start of the source range.
-    //! @param to The start of the target range.
-    //! @param count The number of element to copy.
-    constexpr auto static copy_elements(const_iterator from, iterator to, size_type count) -> void
-    {
-      for (auto i = 0uz; i < count; ++i)
-      {
-        *to++ = *from++;
-      }
-    }
-
     //! Release the memory of this vector.
     constexpr auto deallocate()
     {
@@ -726,19 +813,6 @@ namespace kstd
       });
     }
 
-    //! Move a number of elements from one storage location to another.
-    //!
-    //! @param from The start of the source range.
-    //! @param to The start of the target range.
-    //! @param count The number of element to copy.
-    constexpr auto static move_elements(iterator from, iterator to, size_t count)
-    {
-      for (auto i = 0uz; i < count; ++i)
-      {
-        *to++ = std::move(*from++);
-      }
-    }
-
     //! Panic the kernel if the given index is out of bounds.
     //!
     //! @param index The index to check.
diff --git a/libs/kstd/tests/src/vector.cpp b/libs/kstd/tests/src/vector.cpp
index d4c5e4f..0735c9a 100644
--- a/libs/kstd/tests/src/vector.cpp
+++ b/libs/kstd/tests/src/vector.cpp
@@ -462,6 +462,19 @@ SCENARIO("Vector modifiers", "[vector]")
         REQUIRE(v[1] == 20);
       }
     }
+
+    WHEN("inserting an element")
+    {
+      auto it = v.insert(v.cbegin(), 42);
+
+      THEN("the size and capacity increase and the element is inserted")
+      {
+        REQUIRE(v.size() == 1);
+        REQUIRE(v.capacity() >= 1);
+        REQUIRE(v[0] == 42);
+        REQUIRE(it == v.begin());
+      }
+    }
   }
 
   GIVEN("A populated vector")
@@ -538,6 +551,104 @@ SCENARIO("Vector modifiers", "[vector]")
         REQUIRE(v.capacity() == initial_capacity);
       }
     }
+
+    WHEN("inserting at the beginning")
+    {
+      auto it = v.insert(v.cbegin(), 5);
+
+      THEN("the element is inserted at the front")
+      {
+        REQUIRE(v.size() == 4);
+        REQUIRE(v[0] == 5);
+        REQUIRE(v[1] == 10);
+        REQUIRE(v[2] == 20);
+        REQUIRE(v[3] == 30);
+        REQUIRE(it == v.begin());
+      }
+    }
+
+    WHEN("inserting in the middle")
+    {
+      auto it = v.insert(v.cbegin() + 1, 15);
+
+      THEN("the element is inserted in the middle")
+      {
+        REQUIRE(v.size() == 4);
+        REQUIRE(v[0] == 10);
+        REQUIRE(v[1] == 15);
+        REQUIRE(v[2] == 20);
+        REQUIRE(v[3] == 30);
+        REQUIRE(it == v.begin() + 1);
+      }
+    }
+
+    WHEN("inserting at the end")
+    {
+      auto it = v.insert(v.cend(), 40);
+
+      THEN("the element is inserted at the back")
+      {
+        REQUIRE(v.size() == 4);
+        REQUIRE(v[0] == 10);
+        REQUIRE(v[1] == 20);
+        REQUIRE(v[2] == 30);
+        REQUIRE(v[3] == 40);
+        REQUIRE(it == v.begin() + 3);
+      }
+    }
+
+    WHEN("inserting when capacity is sufficient")
+    {
+      v.reserve(10);
+      auto const capacity = v.capacity();
+
+      auto it = v.insert(v.cbegin() + 1, 15);
+
+      THEN("the element is added without reallocation")
+      {
+        REQUIRE(v.size() == 4);
+        REQUIRE(v.capacity() == capacity);
+        REQUIRE(v[0] == 10);
+        REQUIRE(v[1] == 15);
+        REQUIRE(v[2] == 20);
+        REQUIRE(v[3] == 30);
+        REQUIRE(it == v.begin() + 1);
+      }
+    }
+
+    WHEN("inserting a reference to an existing element with reallocation")
+    {
+      v.shrink_to_fit();
+      REQUIRE(v.capacity() == v.size());
+      auto it = v.insert(v.cbegin() + 1, v[2]);
+
+      THEN("the element is correctly copied and inserted")
+      {
+        REQUIRE(v.size() == 4);
+        REQUIRE(v[0] == 10);
+        REQUIRE(v[1] == 30);
+        REQUIRE(v[2] == 20);
+        REQUIRE(v[3] == 30);
+        REQUIRE(it == v.begin() + 1);
+      }
+    }
+
+    WHEN("inserting a reference to an existing element without reallocation")
+    {
+      v.reserve(10);
+      REQUIRE(v.capacity() > v.size());
+      auto it = v.insert(v.cbegin() + 1, v[2]);
+
+      THEN("the element is correctly copied and inserted")
+      {
+        REQUIRE(v.size() == 4);
+        REQUIRE(v[0] == 10);
+        REQUIRE(v[1] == 30);
+        REQUIRE(v[2] == 20);
+        REQUIRE(v[3] == 30);
+        REQUIRE(it == v.begin() + 1);
+      }
+    }
   }
 }
 
@@ -709,6 +820,55 @@ SCENARIO("Vector modifier move semantics", "[vector]")
       }
     }
   }
+
+  GIVEN("A populated vector of move trackers")
+  {
+    auto v = kstd::vector<kstd::tests::move_tracker>{};
+    v.reserve(10);
+    v.emplace_back(10);
+    v.emplace_back(20);
+    v.emplace_back(30);
+
+    WHEN("inserting an element in the middle with sufficient capacity")
+    {
+      auto const tracker = kstd::tests::move_tracker{15};
+      v.insert(v.cbegin() + 1, tracker);
+
+      THEN("the shifted elements are move-assigned and the new element is copy-assigned")
+      {
+        REQUIRE(v.size() == 4);
+        REQUIRE(v[0].value == 10);
+        REQUIRE_FALSE(v[0].was_moved);
+        REQUIRE(v[1].value == 15);
+        REQUIRE(v[1].was_copied);
+        REQUIRE_FALSE(v[1].was_moved);
+        REQUIRE(v[2].value == 20);
+        REQUIRE(v[2].was_moved);
+        REQUIRE(v[3].value == 30);
+        REQUIRE(v[3].was_moved);
+      }
+    }
+
+    WHEN("inserting an rvalue element in the middle with sufficient capacity")
+    {
+      auto tracker = kstd::tests::move_tracker{15};
+      v.insert(v.cbegin() + 1, std::move(tracker));
+
+      THEN("the shifted elements are move-assigned and the new element is move-assigned")
+      {
+        REQUIRE(v.size() == 4);
+        REQUIRE(v[0].value == 10);
+        REQUIRE_FALSE(v[0].was_moved);
+        REQUIRE(v[1].value == 15);
+        REQUIRE_FALSE(v[1].was_copied);
+        REQUIRE(v[1].was_moved);
+        REQUIRE(v[2].value == 20);
+        REQUIRE(v[2].was_moved);
+        REQUIRE(v[3].value == 30);
+        REQUIRE(v[3].was_moved);
+      }
+    }
+  }
 }
 
 SCENARIO("Vector advanced construction", "[vector]")