BLI: add reverse iterators, iterator constructor and Vector.insert/prepend

The new reverse iterators behave as the reverse iterators for contains from
the standard library. Have a look at the tests to see how to use them.
Using them will hopefully become easier with ranges in C++20.

A Vector can now be constructed from two iterators, which is very common
in the standard library.

New Vector.insert methods allow adding elements in the middle of a vector.
These methods should not be used often in practice, because they has a linear running time.

New Vector.prepend methods allow adding elements to the beginning of a vector.
These methods are O(n) as well.

6 files changed, 252 insertions, 16 deletions

diff --git a/source/blender/blenlib/BLI_array.hh b/source/blender/blenlib/BLI_array.hh
index 9b307dc6a04..9d09bb3559e 100644
--- a/source/blender/blenlib/BLI_array.hh
+++ b/source/blender/blenlib/BLI_array.hh
@@ -288,7 +288,6 @@ class Array {
   {
     return data_;
   }
-
   const T *end() const
   {
     return data_ + size_;
@@ -298,12 +297,29 @@ class Array {
   {
     return data_;
   }
-
   T *end()
   {
     return data_ + size_;
   }
 
+  std::reverse_iterator<T *> rbegin()
+  {
+    return std::reverse_iterator<T *>(this->end());
+  }
+  std::reverse_iterator<T *> rend()
+  {
+    return std::reverse_iterator<T *>(this->begin());
+  }
+
+  std::reverse_iterator<const T *> rbegin() const
+  {
+    return std::reverse_iterator<T *>(this->end());
+  }
+  std::reverse_iterator<const T *> rend() const
+  {
+    return std::reverse_iterator<T *>(this->begin());
+  }
+
   /**
    * Get an index range containing all valid indices for this array.
    */
diff --git a/source/blender/blenlib/BLI_span.hh b/source/blender/blenlib/BLI_span.hh
index 165814cf23c..5b4d2769f57 100644
--- a/source/blender/blenlib/BLI_span.hh
+++ b/source/blender/blenlib/BLI_span.hh
@@ -213,12 +213,20 @@ template<typename T> class Span {
   {
     return data_;
   }
-
   const T *end() const
   {
     return data_ + size_;
   }
 
+  std::reverse_iterator<const T *> rbegin() const
+  {
+    return std::reverse_iterator<const T *>(this->end());
+  }
+  std::reverse_iterator<const T *> rend() const
+  {
+    return std::reverse_iterator<const T *>(this->begin());
+  }
+
   /**
    * Access an element in the array. This invokes undefined behavior when the index is out of
    * bounds.
@@ -502,12 +510,20 @@ template<typename T> class MutableSpan {
   {
     return data_;
   }
-
   T *end() const
   {
     return data_ + size_;
   }
 
+  std::reverse_iterator<T *> rbegin() const
+  {
+    return std::reverse_iterator<T *>(this->end());
+  }
+  std::reverse_iterator<T *> rend() const
+  {
+    return std::reverse_iterator<T *>(this->begin());
+  }
+
   T &operator[](const int64_t index) const
   {
     BLI_assert(index < this->size());
diff --git a/source/blender/blenlib/BLI_vector.hh b/source/blender/blenlib/BLI_vector.hh
index 48110ef2814..74ce8dd42e7 100644
--- a/source/blender/blenlib/BLI_vector.hh
+++ b/source/blender/blenlib/BLI_vector.hh
@@ -178,17 +178,15 @@ class Vector {
   {
   }
 
-  /**
-   * Create a vector from any container. It must be possible to use the container in a
-   * range-for loop.
-   */
-  template<typename ContainerT> static Vector FromContainer(const ContainerT &container)
-  {
-    Vector vector;
-    for (const auto &value : container) {
-      vector.append(value);
+  template<typename InputIt,
+           /* This constructor should not be called with e.g. Vector(3, 10), because that is
+              expected to produce the vector (10, 10, 10). */
+           typename std::enable_if_t<!std::is_convertible_v<InputIt, int>> * = nullptr>
+  Vector(InputIt first, InputIt last, Allocator allocator = {}) : Vector(std::move(allocator))
+  {
+    for (InputIt current = first; current != last; ++current) {
+      this->append(*current);
     }
-    return vector;
   }
 
   /**
@@ -560,6 +558,78 @@ class Vector {
     UPDATE_VECTOR_SIZE(this);
   }
 
+  template<typename InputIt> void extend(InputIt first, InputIt last)
+  {
+    this->insert(this->end(), first, last);
+  }
+
+  /**
+   * Insert elements into the vector at the specified position. This has a running time of O(n)
+   * where n is the number of values that have to be moved. Undefined behavior is invoked when the
+   * insert position is out of bounds.
+   */
+  void insert(const int64_t insert_index, const T &value)
+  {
+    this->insert(insert_index, Span<T>(&value, 1));
+  }
+  void insert(const int64_t insert_index, T &&value)
+  {
+    this->insert(
+        insert_index, std::make_move_iterator(&value), std::make_move_iterator(&value + 1));
+  }
+  void insert(const int64_t insert_index, Span<T> array)
+  {
+    this->insert(begin_ + insert_index, array.begin(), array.end());
+  }
+  template<typename InputIt> void insert(const T *insert_position, InputIt first, InputIt last)
+  {
+    const int64_t insert_index = insert_position - begin_;
+    this->insert(insert_index, first, last);
+  }
+  template<typename InputIt> void insert(const int64_t insert_index, InputIt first, InputIt last)
+  {
+    BLI_assert(insert_index >= 0);
+    BLI_assert(insert_index <= this->size());
+
+    const int64_t insert_amount = std::distance(first, last);
+    const int64_t old_size = this->size();
+    const int64_t new_size = old_size + insert_amount;
+    const int64_t move_amount = old_size - insert_index;
+
+    this->reserve(new_size);
+    for (int64_t i = 0; i < move_amount; i++) {
+      const int64_t src_index = insert_index + move_amount - i - 1;
+      const int64_t dst_index = new_size - i - 1;
+      new (static_cast<void *>(begin_ + dst_index)) T(std::move(begin_[src_index]));
+      begin_[src_index].~T();
+    }
+
+    std::uninitialized_copy_n(first, insert_amount, begin_ + insert_index);
+    end_ = begin_ + new_size;
+    UPDATE_VECTOR_SIZE(this);
+  }
+
+  /**
+   * Insert values at the beginning of the vector. The has to move all the other elements, so it
+   * has a linear running time.
+   */
+  void prepend(const T &&value)
+  {
+    this->insert(0, value);
+  }
+  void prepend(T &&value)
+  {
+    this->insert(0, std::move(value));
+  }
+  void prepend(Span<T> values)
+  {
+    this->insert(0, values);
+  }
+  template<typename InputIt> void prepend(InputIt first, InputIt last)
+  {
+    this->insert(0, first, last);
+  }
+
   /**
    * Return a reference to the last element in the vector.
    * This invokes undefined behavior when the vector is empty.
@@ -746,6 +816,24 @@ class Vector {
     return end_;
   }
 
+  std::reverse_iterator<T *> rbegin()
+  {
+    return std::reverse_iterator<T *>(this->end());
+  }
+  std::reverse_iterator<T *> rend()
+  {
+    return std::reverse_iterator<T *>(this->begin());
+  }
+
+  std::reverse_iterator<const T *> rbegin() const
+  {
+    return std::reverse_iterator<T *>(this->end());
+  }
+  std::reverse_iterator<const T *> rend() const
+  {
+    return std::reverse_iterator<T *>(this->begin());
+  }
+
   /**
    * Get the current capacity of the vector, i.e. the maximum number of elements the vector can
    * hold, before it has to reallocate.
diff --git a/source/blender/blenlib/tests/BLI_array_test.cc b/source/blender/blenlib/tests/BLI_array_test.cc
index 7348a6f93f3..38ab695d238 100644
--- a/source/blender/blenlib/tests/BLI_array_test.cc
+++ b/source/blender/blenlib/tests/BLI_array_test.cc
@@ -2,6 +2,7 @@
 
 #include "BLI_array.hh"
 #include "BLI_strict_flags.h"
+#include "BLI_vector.hh"
 #include "testing/testing.h"
 
 namespace blender::tests {
@@ -173,4 +174,18 @@ TEST(array, Fill)
   EXPECT_EQ(array[4], 3);
 }
 
+TEST(array, ReverseIterator)
+{
+  Array<int> array = {3, 4, 5, 6};
+  Vector<int> reversed_vec;
+
+  for (auto it = array.rbegin(); it != array.rend(); ++it) {
+    reversed_vec.append(*it);
+    *it += 10;
+  }
+
+  EXPECT_EQ_ARRAY(reversed_vec.data(), Span({6, 5, 4, 3}).data(), 4);
+  EXPECT_EQ_ARRAY(array.data(), Span({13, 14, 15, 16}).data(), 4);
+}
+
 }  // namespace blender::tests
diff --git a/source/blender/blenlib/tests/BLI_span_test.cc b/source/blender/blenlib/tests/BLI_span_test.cc
index 6ad2a5633ad..82d21e53084 100644
--- a/source/blender/blenlib/tests/BLI_span_test.cc
+++ b/source/blender/blenlib/tests/BLI_span_test.cc
@@ -308,4 +308,32 @@ TEST(span, CopyFrom)
   EXPECT_EQ(dst[3], 8);
 }
 
+TEST(span, ReverseIterator)
+{
+  std::array<int, 4> src = {4, 5, 6, 7};
+  Span<int> span = src;
+  Vector<int> reversed_vec;
+
+  for (auto it = span.rbegin(); it != span.rend(); ++it) {
+    reversed_vec.append(*it);
+  }
+  EXPECT_EQ(reversed_vec.size(), 4);
+  EXPECT_EQ_ARRAY(reversed_vec.data(), Span({7, 6, 5, 4}).data(), 4);
+}
+
+TEST(span, MutableReverseIterator)
+{
+  std::array<int, 4> src = {4, 5, 6, 7};
+  MutableSpan<int> span = src;
+  Vector<int> reversed_vec;
+
+  for (auto it = span.rbegin(); it != span.rend(); ++it) {
+    reversed_vec.append(*it);
+    *it += 10;
+  }
+  EXPECT_EQ(reversed_vec.size(), 4);
+  EXPECT_EQ_ARRAY(reversed_vec.data(), Span({7, 6, 5, 4}).data(), 4);
+  EXPECT_EQ_ARRAY(src.data(), Span({14, 15, 16, 17}).data(), 4);
+}
+
 }  // namespace blender::tests
diff --git a/source/blender/blenlib/tests/BLI_vector_test.cc b/source/blender/blenlib/tests/BLI_vector_test.cc
index f72dfc5deb8..792e120d2c0 100644
--- a/source/blender/blenlib/tests/BLI_vector_test.cc
+++ b/source/blender/blenlib/tests/BLI_vector_test.cc
@@ -98,14 +98,14 @@ TEST(vector, ListBaseConstructor)
   delete value3;
 }
 
-TEST(vector, ContainerConstructor)
+TEST(vector, IteratorConstructor)
 {
   std::forward_list<int> list;
   list.push_front(3);
   list.push_front(1);
   list.push_front(5);
 
-  Vector<int> vec = Vector<int>::FromContainer(list);
+  Vector<int> vec = Vector<int>(list.begin(), list.end());
   EXPECT_EQ(vec.size(), 3);
   EXPECT_EQ(vec[0], 5);
   EXPECT_EQ(vec[1], 1);
@@ -279,6 +279,15 @@ TEST(vector, ExtendNonDuplicates)
   EXPECT_EQ(vec.size(), 5);
 }
 
+TEST(vector, ExtendIterator)
+{
+  Vector<int> vec = {3, 4, 5};
+  std::forward_list<int> list = {8, 9};
+  vec.extend(list.begin(), list.end());
+  EXPECT_EQ(vec.size(), 5);
+  EXPECT_EQ_ARRAY(vec.data(), Span({3, 4, 5, 8, 9}).data(), 5);
+}
+
 TEST(vector, Iterator)
 {
   Vector<int> vec({1, 4, 9, 16});
@@ -636,4 +645,68 @@ TEST(vector, Fill)
   EXPECT_EQ(vec[4], 3);
 }
 
+TEST(vector, InsertAtBeginning)
+{
+  Vector<int> vec = {1, 2, 3};
+  vec.insert(0, {6, 7});
+  EXPECT_EQ(vec.size(), 5);
+  EXPECT_EQ_ARRAY(vec.data(), Span({6, 7, 1, 2, 3}).data(), 5);
+}
+
+TEST(vector, InsertAtEnd)
+{
+  Vector<int> vec = {1, 2, 3};
+  vec.insert(3, {6, 7});
+  EXPECT_EQ(vec.size(), 5);
+  EXPECT_EQ_ARRAY(vec.data(), Span({1, 2, 3, 6, 7}).data(), 5);
+}
+
+TEST(vector, InsertInMiddle)
+{
+  Vector<int> vec = {1, 2, 3};
+  vec.insert(1, {6, 7});
+  EXPECT_EQ(vec.size(), 5);
+  EXPECT_EQ_ARRAY(vec.data(), Span({1, 6, 7, 2, 3}).data(), 5);
+}
+
+TEST(vector, InsertAtIterator)
+{
+  Vector<std::string> vec = {"1", "2", "3"};
+  Vector<std::string> other_vec = {"hello", "world"};
+  vec.insert(vec.begin() + 1, other_vec.begin(), other_vec.end());
+  EXPECT_EQ(vec.size(), 5);
+  EXPECT_EQ_ARRAY(vec.data(), Span<std::string>({"1", "hello", "world", "2", "3"}).data(), 5);
+}
+
+TEST(vector, InsertMoveOnlyType)
+{
+  Vector<std::unique_ptr<int>> vec;
+  vec.append(std::make_unique<int>(1));
+  vec.append(std::make_unique<int>(2));
+  vec.insert(1, std::make_unique<int>(30));
+  EXPECT_EQ(vec.size(), 3);
+  EXPECT_EQ(*vec[0], 1);
+  EXPECT_EQ(*vec[1], 30);
+  EXPECT_EQ(*vec[2], 2);
+}
+
+TEST(vector, Prepend)
+{
+  Vector<int> vec = {1, 2, 3};
+  vec.prepend({7, 8});
+  EXPECT_EQ(vec.size(), 5);
+  EXPECT_EQ_ARRAY(vec.data(), Span({7, 8, 1, 2, 3}).data(), 5);
+}
+
+TEST(vector, ReverseIterator)
+{
+  Vector<int> vec = {4, 5, 6, 7};
+  Vector<int> reversed_vec;
+  for (auto it = vec.rbegin(); it != vec.rend(); ++it) {
+    reversed_vec.append(*it);
+  }
+  EXPECT_EQ(reversed_vec.size(), 4);
+  EXPECT_EQ_ARRAY(reversed_vec.data(), Span({7, 6, 5, 4}).data(), 4);
+}
+
 }  // namespace blender::tests