BLI: improve various C++ data structures

The changes come from the `functions` branch, where I'm using
these structures a lot.

This also includes a new `BLI::Optional<T>` type, which is similar
to `std::Optional<T>` which can be used when Blender starts using
C++17.

8 files changed, 234 insertions, 4 deletions

diff --git a/tests/gtests/blenlib/BLI_array_ref_test.cc b/tests/gtests/blenlib/BLI_array_ref_test.cc
index 4507d9e6e84..538fadc1cf9 100644
--- a/tests/gtests/blenlib/BLI_array_ref_test.cc
+++ b/tests/gtests/blenlib/BLI_array_ref_test.cc
@@ -2,7 +2,8 @@
 #include "BLI_array_ref.h"
 #include "BLI_vector.h"
 
-using BLI::IndexRange;
+using namespace BLI;
+
 using IntVector = BLI::Vector<int>;
 using IntArrayRef = BLI::ArrayRef<int>;
 using MutableIntArrayRef = BLI::MutableArrayRef<int>;
@@ -17,6 +18,15 @@ TEST(array_ref, FromSmallVector)
   EXPECT_EQ(a_ref[2], 3);
 }
 
+TEST(array_ref, AddConstToPointer)
+{
+  int a = 0;
+  std::vector<int *> vec = {&a};
+  ArrayRef<int *> ref = vec;
+  ArrayRef<const int *> const_ref = ref;
+  EXPECT_EQ(const_ref.size(), 1);
+}
+
 TEST(array_ref, IsReferencing)
 {
   int array[] = {3, 5, 8};
@@ -264,3 +274,47 @@ TEST(array_ref, ContainsPtr)
   EXPECT_FALSE(a_ref.contains_ptr(&a[0] - 1));
   EXPECT_FALSE(a_ref.contains_ptr(&other));
 }
+
+TEST(array_ref, FirstIndex)
+{
+  std::array<int, 5> a = {4, 5, 4, 2, 5};
+  IntArrayRef a_ref(a);
+
+  EXPECT_EQ(a_ref.first_index(4), 0);
+  EXPECT_EQ(a_ref.first_index(5), 1);
+  EXPECT_EQ(a_ref.first_index(2), 3);
+}
+
+TEST(array_ref, CastSameSize)
+{
+  int value = 0;
+  std::array<int *, 4> a = {&value, nullptr, nullptr, nullptr};
+  ArrayRef<int *> a_ref = a;
+  ArrayRef<float *> new_a_ref = a_ref.cast<float *>();
+
+  EXPECT_EQ(a_ref.size(), 4);
+  EXPECT_EQ(new_a_ref.size(), 4);
+
+  EXPECT_EQ(a_ref[0], &value);
+  EXPECT_EQ(new_a_ref[0], (float *)&value);
+}
+
+TEST(array_ref, CastSmallerSize)
+{
+  std::array<uint32_t, 4> a = {3, 4, 5, 6};
+  ArrayRef<uint32_t> a_ref = a;
+  ArrayRef<uint16_t> new_a_ref = a_ref.cast<uint16_t>();
+
+  EXPECT_EQ(a_ref.size(), 4);
+  EXPECT_EQ(new_a_ref.size(), 8);
+}
+
+TEST(array_ref, CastLargerSize)
+{
+  std::array<uint16_t, 4> a = {4, 5, 6, 7};
+  ArrayRef<uint16_t> a_ref = a;
+  ArrayRef<uint32_t> new_a_ref = a_ref.cast<uint32_t>();
+
+  EXPECT_EQ(a_ref.size(), 4);
+  EXPECT_EQ(new_a_ref.size(), 2);
+}
diff --git a/tests/gtests/blenlib/BLI_index_range_test.cc b/tests/gtests/blenlib/BLI_index_range_test.cc
index 1944279999d..c5c1f9a875b 100644
--- a/tests/gtests/blenlib/BLI_index_range_test.cc
+++ b/tests/gtests/blenlib/BLI_index_range_test.cc
@@ -119,6 +119,15 @@ TEST(index_range, Slice)
   EXPECT_EQ(slice.last(), 12);
 }
 
+TEST(index_range, SliceRange)
+{
+  IndexRange range = IndexRange(5, 15);
+  IndexRange slice = range.slice(IndexRange(3, 5));
+  EXPECT_EQ(slice.size(), 5);
+  EXPECT_EQ(slice.first(), 8);
+  EXPECT_EQ(slice.last(), 12);
+}
+
 TEST(index_range, AsArrayRef)
 {
   IndexRange range = IndexRange(4, 6);
diff --git a/tests/gtests/blenlib/BLI_optional_test.cc b/tests/gtests/blenlib/BLI_optional_test.cc
new file mode 100644
index 00000000000..2e672967680
--- /dev/null
+++ b/tests/gtests/blenlib/BLI_optional_test.cc
@@ -0,0 +1,74 @@
+#include "testing/testing.h"
+#include "BLI_optional.h"
+#include <string>
+
+using namespace BLI;
+
+TEST(optional, DefaultConstructor)
+{
+  Optional<int> a;
+  EXPECT_FALSE(a.has_value());
+}
+
+TEST(optional, ValueConstructor)
+{
+  Optional<int> a(5);
+  EXPECT_TRUE(a.has_value());
+  EXPECT_EQ(a.value(), 5);
+}
+
+TEST(optional, CopyConstructor)
+{
+  Optional<std::string> a("Hello");
+  Optional<std::string> b = a;
+  EXPECT_TRUE(a.has_value());
+  EXPECT_TRUE(b.has_value());
+  b.value()[0] = 'T';
+  EXPECT_EQ(a.value(), "Hello");
+  EXPECT_EQ(b.value(), "Tello");
+}
+
+TEST(optional, Reset)
+{
+  Optional<int> a(4);
+  EXPECT_TRUE(a.has_value());
+  a.reset();
+  EXPECT_FALSE(a.has_value());
+}
+
+TEST(optional, FromNullPointer)
+{
+  Optional<int> a = Optional<int>::FromPointer(nullptr);
+  EXPECT_FALSE(a.has_value());
+}
+
+TEST(optional, FromNonNullPointer)
+{
+  int value = 42;
+  Optional<int> a = Optional<int>::FromPointer(&value);
+  EXPECT_TRUE(a.has_value());
+  EXPECT_EQ(a.value(), 42);
+}
+
+TEST(optional, Extract)
+{
+  Optional<int> a(32);
+  EXPECT_TRUE(a.has_value());
+  EXPECT_EQ(a.extract(), 32);
+  EXPECT_FALSE(a.has_value());
+}
+
+TEST(optional, ArrowOperator)
+{
+  Optional<std::string> value = std::string("Hello");
+  EXPECT_TRUE(value.has_value());
+  EXPECT_EQ(value->size(), 5);
+}
+
+TEST(optional, StarOperator)
+{
+  Optional<std::string> value = std::string("Hello");
+  EXPECT_TRUE(value.has_value());
+  std::string &s = *value;
+  EXPECT_EQ(s.size(), 5);
+}
diff --git a/tests/gtests/blenlib/BLI_stack_cxx_test.cc b/tests/gtests/blenlib/BLI_stack_cxx_test.cc
index 436f1f307b9..272bba05cb8 100644
--- a/tests/gtests/blenlib/BLI_stack_cxx_test.cc
+++ b/tests/gtests/blenlib/BLI_stack_cxx_test.cc
@@ -8,7 +8,7 @@ TEST(stack, DefaultConstructor)
 {
   IntStack stack;
   EXPECT_EQ(stack.size(), 0);
-  EXPECT_TRUE(stack.empty());
+  EXPECT_TRUE(stack.is_empty());
 }
 
 TEST(stack, ArrayRefConstructor)
@@ -19,7 +19,7 @@ TEST(stack, ArrayRefConstructor)
   EXPECT_EQ(stack.pop(), 2);
   EXPECT_EQ(stack.pop(), 7);
   EXPECT_EQ(stack.pop(), 4);
-  EXPECT_TRUE(stack.empty());
+  EXPECT_TRUE(stack.is_empty());
 }
 
 TEST(stack, Push)
@@ -32,6 +32,17 @@ TEST(stack, Push)
   EXPECT_EQ(stack.size(), 2);
 }
 
+TEST(stack, PushMultiple)
+{
+  IntStack stack;
+  EXPECT_EQ(stack.size(), 0);
+  stack.push_multiple({1, 2, 3});
+  EXPECT_EQ(stack.size(), 3);
+  EXPECT_EQ(stack.pop(), 3);
+  EXPECT_EQ(stack.pop(), 2);
+  EXPECT_EQ(stack.pop(), 1);
+}
+
 TEST(stack, Pop)
 {
   IntStack stack;
diff --git a/tests/gtests/blenlib/BLI_string_map_test.cc b/tests/gtests/blenlib/BLI_string_map_test.cc
index cc02a54e0c8..dfe96d63297 100644
--- a/tests/gtests/blenlib/BLI_string_map_test.cc
+++ b/tests/gtests/blenlib/BLI_string_map_test.cc
@@ -43,6 +43,21 @@ TEST(string_map, MoveConstructor)
   EXPECT_EQ(map2.lookup("B")[5], 6);
 }
 
+TEST(string_map, Add)
+{
+  StringMap<int> map;
+  EXPECT_EQ(map.size(), 0);
+
+  map.add("test", 1);
+  EXPECT_EQ(map.lookup("test"), 1);
+
+  map.add("test", 2);
+  EXPECT_EQ(map.lookup("test"), 1);
+
+  map.add("test2", 2);
+  EXPECT_EQ(map.lookup("test2"), 2);
+}
+
 TEST(string_map, AddNew)
 {
   StringMap<int> map;
@@ -128,6 +143,15 @@ TEST(string_map, LookupDefault)
   EXPECT_EQ(map.lookup_default("test", 42), 5);
 }
 
+TEST(string_map, TryLookup)
+{
+  StringMap<int> map;
+  map.add_new("test", 4);
+  EXPECT_TRUE(map.try_lookup("test").has_value());
+  EXPECT_FALSE(map.try_lookup("value").has_value());
+  EXPECT_EQ(map.try_lookup("test").value(), 4);
+}
+
 TEST(string_map, FindKeyForValue)
 {
   StringMap<int> map;
@@ -179,7 +203,7 @@ TEST(string_map, ForeachKeyValuePair)
   Vector<std::string> keys;
   Vector<int> values;
 
-  map.foreach_key_value_pair([&keys, &values](StringRefNull key, int value) {
+  map.foreach_item([&keys, &values](StringRefNull key, int value) {
     keys.append(key);
     values.append(value);
   });
diff --git a/tests/gtests/blenlib/BLI_string_ref_test.cc b/tests/gtests/blenlib/BLI_string_ref_test.cc
index 5605e10ac86..38a970455c0 100644
--- a/tests/gtests/blenlib/BLI_string_ref_test.cc
+++ b/tests/gtests/blenlib/BLI_string_ref_test.cc
@@ -228,3 +228,12 @@ TEST(string_ref, DropPrefix)
   EXPECT_EQ(ref2.size(), 1);
   EXPECT_EQ(ref2, "t");
 }
+
+TEST(string_ref, Substr)
+{
+  StringRef ref("hello world");
+  EXPECT_EQ(ref.substr(0, 5), "hello");
+  EXPECT_EQ(ref.substr(4, 0), "");
+  EXPECT_EQ(ref.substr(3, 4), "lo w");
+  EXPECT_EQ(ref.substr(6, 5), "world");
+}
diff --git a/tests/gtests/blenlib/BLI_vector_test.cc b/tests/gtests/blenlib/BLI_vector_test.cc
index f258e50a60c..6cf67fb2488 100644
--- a/tests/gtests/blenlib/BLI_vector_test.cc
+++ b/tests/gtests/blenlib/BLI_vector_test.cc
@@ -216,6 +216,38 @@ TEST(vector, Append)
   EXPECT_EQ(vec[2], 7);
 }
 
+TEST(vector, AppendAndGetIndex)
+{
+  IntVector vec;
+  EXPECT_EQ(vec.append_and_get_index(10), 0);
+  EXPECT_EQ(vec.append_and_get_index(10), 1);
+  EXPECT_EQ(vec.append_and_get_index(10), 2);
+  vec.append(10);
+  EXPECT_EQ(vec.append_and_get_index(10), 4);
+}
+
+TEST(vector, AppendNonDuplicates)
+{
+  IntVector vec;
+  vec.append_non_duplicates(4);
+  EXPECT_EQ(vec.size(), 1);
+  vec.append_non_duplicates(5);
+  EXPECT_EQ(vec.size(), 2);
+  vec.append_non_duplicates(4);
+  EXPECT_EQ(vec.size(), 2);
+}
+
+TEST(vector, ExtendNonDuplicates)
+{
+  IntVector vec;
+  vec.extend_non_duplicates({1, 2});
+  EXPECT_EQ(vec.size(), 2);
+  vec.extend_non_duplicates({3, 4});
+  EXPECT_EQ(vec.size(), 4);
+  vec.extend_non_duplicates({0, 1, 2, 3});
+  EXPECT_EQ(vec.size(), 5);
+}
+
 TEST(vector, Fill)
 {
   IntVector vec(5);
@@ -339,6 +371,22 @@ TEST(vector, RemoveReorder)
   EXPECT_TRUE(vec.empty());
 }
 
+TEST(vector, RemoveFirstOccurrenceAndReorder)
+{
+  IntVector vec = {4, 5, 6, 7};
+  vec.remove_first_occurrence_and_reorder(5);
+  EXPECT_EQ(vec[0], 4);
+  EXPECT_EQ(vec[1], 7);
+  EXPECT_EQ(vec[2], 6);
+  vec.remove_first_occurrence_and_reorder(6);
+  EXPECT_EQ(vec[0], 4);
+  EXPECT_EQ(vec[1], 7);
+  vec.remove_first_occurrence_and_reorder(4);
+  EXPECT_EQ(vec[0], 7);
+  vec.remove_first_occurrence_and_reorder(7);
+  EXPECT_EQ(vec.size(), 0);
+}
+
 TEST(vector, AllEqual_False)
 {
   IntVector a = {1, 2, 3};
diff --git a/tests/gtests/blenlib/CMakeLists.txt b/tests/gtests/blenlib/CMakeLists.txt
index c6b23615a5a..1a104fcb746 100644
--- a/tests/gtests/blenlib/CMakeLists.txt
+++ b/tests/gtests/blenlib/CMakeLists.txt
@@ -59,6 +59,7 @@ BLENDER_TEST(BLI_math_base "bf_blenlib")
 BLENDER_TEST(BLI_math_color "bf_blenlib")
 BLENDER_TEST(BLI_math_geom "bf_blenlib")
 BLENDER_TEST(BLI_memiter "bf_blenlib")
+BLENDER_TEST(BLI_optional "bf_blenlib")
 BLENDER_TEST(BLI_path_util "${BLI_path_util_extra_libs}")
 BLENDER_TEST(BLI_polyfill_2d "bf_blenlib")
 BLENDER_TEST(BLI_set "bf_blenlib")