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.

3 files changed, 118 insertions, 2 deletions

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