kstd/vector: reduce code duplication

1 files changed, 91 insertions, 166 deletions

diff --git a/libs/kstd/kstd/vector b/libs/kstd/kstd/vector
index c714957..736b854 100644
--- a/libs/kstd/kstd/vector
+++ b/libs/kstd/kstd/vector
@@ -551,13 +551,7 @@ namespace kstd
         kstd::os::panic("[kstd:vector] Tried to reserve more space than theoretically possible.");
       }
 
-      auto new_data = allocate_n(new_capacity);
-      auto old_size = size();
-      uninitialized_move_with_allocator(begin(), new_data, size());
-      clear_and_deallocate();
-      m_data = new_data;
-      m_capacity = new_capacity;
-      m_size = old_size;
+      reallocate_exactly(new_capacity);
     }
 
     //! Resize this vector to contain @p new_size elements.
@@ -613,13 +607,7 @@ namespace kstd
         return;
       }
 
-      auto new_data = allocate_n(m_size);
-      auto old_size = size();
-      uninitialized_move_with_allocator(begin(), new_data, old_size);
-      clear_and_deallocate();
-      std::exchange(m_data, new_data);
-      m_capacity = old_size;
-      m_size = old_size;
+      reallocate_exactly(m_size);
     }
 
     //! Clear the contents of this vector.
@@ -636,47 +624,7 @@ namespace kstd
     //! @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;
+      return do_insert(position, value);
     }
 
     //! Insert an element at a given position.
@@ -686,47 +634,7 @@ namespace kstd
     //! @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;
+      return do_insert(position, std::move(value));
     }
 
     //! Insert the element of a given range into the vector at a given position.
@@ -801,39 +709,24 @@ namespace kstd
     template<typename... Args>
     constexpr auto emplace(const_iterator position, Args &&... args) -> iterator
     {
-      auto prefix_size = std::ranges::distance(begin(), position);
-      auto suffix_size = std::ranges::distance(position, end());
-
-      if (position == end())
+      auto prefix_size = std::ranges::distance(cbegin(), position);
+      if (position == cend())
       {
         emplace_back(std::forward<Args>(args)...);
-        return begin() + prefix_size;
       }
-
-      if (m_capacity == m_size)
+      else 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::forward<Args>(args)...);
-        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;
+        reallocate_and_insert(begin() + prefix_size, std::forward<Args>(args)...);
       }
       else
       {
+        auto to_insert = value_type{std::forward<Args>(args)...};
         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_type{std::forward<Args>(args)...};
+        shift_back(insert_position);
+        *insert_position = std::move(to_insert);
+        ++m_size;
       }
 
-      ++m_size;
       return begin() + prefix_size;
     }
 
@@ -884,47 +777,13 @@ namespace kstd
     //! Append a given element to this vector via copy construction.
     constexpr auto push_back(value_type const & value) -> void
     {
-      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 + m_size, value);
-        uninitialized_move_with_allocator(begin(), new_data, size());
-        destroy_n(begin(), size());
-        deallocate();
-        m_data = new_data;
-        m_capacity = new_capacity;
-        m_size = old_size;
-      }
-      else
-      {
-        std::allocator_traits<allocator_type>::construct(m_allocator, data() + size(), value);
-      }
-      ++m_size;
+      emplace_back(value);
     }
 
     //! Append a given element to this vector via move construction.
     constexpr auto push_back(value_type && value) -> void
     {
-      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 + m_size, std::move(value));
-        uninitialized_move_with_allocator(begin(), new_data, size());
-        destroy_n(begin(), size());
-        deallocate();
-        m_data = new_data;
-        m_capacity = new_capacity;
-        m_size = old_size;
-      }
-      else
-      {
-        std::allocator_traits<allocator_type>::construct(m_allocator, data() + size(), std::move(value));
-      }
-      ++m_size;
+      emplace_back(std::move(value));
     }
 
     //! Append a given element to this vector via direct construction.
@@ -933,22 +792,13 @@ namespace kstd
     {
       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 + m_size, std::forward<Args>(args)...);
-        uninitialized_move_with_allocator(begin(), new_data, size());
-        destroy_n(begin(), size());
-        deallocate();
-        m_data = new_data;
-        m_capacity = new_capacity;
-        m_size = old_size;
+        reallocate_and_insert(end(), std::forward<Args>(args)...);
       }
       else
       {
         std::allocator_traits<allocator_type>::construct(m_allocator, data() + size(), std::forward<Args>(args)...);
+        ++m_size;
       }
-      ++m_size;
       return this->back();
     }
 
@@ -1055,6 +905,38 @@ namespace kstd
       }
     }
 
+    //! Insert an element into this vector at the given position.
+    //!
+    //! @param position The position to insert the element at.
+    //! @param value The value to insert.
+    template<typename U>
+    constexpr auto do_insert(const_iterator position, U && value)
+    {
+      auto prefix_size = std::ranges::distance(cbegin(), position);
+      if (position == cend())
+      {
+        push_back(std::forward<U>(value));
+      }
+      else if (m_capacity == m_size)
+      {
+        reallocate_and_insert(begin() + prefix_size, std::forward<U>(value));
+      }
+      else if (&value >= cbegin() && &value < cend())
+      {
+        auto temporary = std::forward<U>(value);
+        shift_back(begin() + prefix_size);
+        *(begin() + prefix_size) = std::move(temporary);
+        ++m_size;
+      }
+      else
+      {
+        shift_back(begin() + prefix_size);
+        *(begin() + prefix_size) = std::forward<U>(value);
+        ++m_size;
+      }
+      return begin() + prefix_size;
+    }
+
     //! Destroy a number of elements in this vector.
     //!
     //! @param first The start of the range of the elements to be destroyed.
@@ -1105,6 +987,49 @@ namespace kstd
       }
     }
 
+    //! Reallocate the storage space to be exactly as large as the given size.
+    constexpr auto reallocate_exactly(size_type new_capacity) -> void
+    {
+      auto new_data = allocate_n(new_capacity);
+      auto old_size = size();
+      uninitialized_move_with_allocator(begin(), new_data, old_size);
+      clear_and_deallocate();
+      m_data = new_data;
+      m_capacity = new_capacity;
+      m_size = old_size;
+    }
+
+    //! Shift all elements, starting the given position, one position back inside the vector.
+    constexpr auto shift_back(iterator starting_at)
+    {
+      std::allocator_traits<allocator_type>::construct(m_allocator, end(), std::move(*(end() - 1)));
+      std::ranges::move_backward(starting_at, end() - 1, end());
+    }
+
+    //! Reallocate the storage of this vector and insert an element at the given position.
+    //!
+    //! @param position The position to insert the element at.
+    //! @param args The constructor arguments for the inserted element.
+    template<typename... Args>
+    constexpr auto reallocate_and_insert(iterator position, Args &&... args)
+    {
+      auto prefix_size = std::ranges::distance(begin(), position);
+      auto suffix_size = std::ranges::distance(position, end());
+      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::forward<Args>(args)...);
+      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 + 1;
+    }
+
     //! The allocator used by this vector.
     [[no_unique_address]] allocator_type m_allocator{};