BLI: improve support for generic algorithms with c++ containers

Some generic algorithms from the standard library like `std::any_of`
did not work with all container and iterator types. To improve the
situation, this patch adds various type members to containers
and iterators.

Custom iterators for Set, Map and IndexRange now have an iterator
category, which soe algorithms require. IndexRange could become
a random access iterator, but adding all the missing methods can
be done when it is necessary.

12 files changed, 197 insertions, 3 deletions

diff --git a/source/blender/blenlib/BLI_array.hh b/source/blender/blenlib/BLI_array.hh
index 284d62fb876..fc8fc615feb 100644
--- a/source/blender/blenlib/BLI_array.hh
+++ b/source/blender/blenlib/BLI_array.hh
@@ -60,6 +60,16 @@ template<
      */
     typename Allocator = GuardedAllocator>
 class Array {
+ public:
+  using value_type = T;
+  using pointer = T *;
+  using const_pointer = const T *;
+  using reference = T &;
+  using const_reference = const T &;
+  using iterator = T *;
+  using const_iterator = const T *;
+  using size_type = int64_t;
+
  private:
   /** The beginning of the array. It might point into the inline buffer. */
   T *data_;
diff --git a/source/blender/blenlib/BLI_index_range.hh b/source/blender/blenlib/BLI_index_range.hh
index 61a8088edea..665f44468db 100644
--- a/source/blender/blenlib/BLI_index_range.hh
+++ b/source/blender/blenlib/BLI_index_range.hh
@@ -82,11 +82,18 @@ class IndexRange {
   }
 
   class Iterator {
+   public:
+    using iterator_category = std::forward_iterator_tag;
+    using value_type = int64_t;
+    using pointer = const int64_t *;
+    using reference = const int64_t &;
+    using difference_type = std::ptrdiff_t;
+
    private:
     int64_t current_;
 
    public:
-    constexpr Iterator(int64_t current) : current_(current)
+    constexpr explicit Iterator(int64_t current) : current_(current)
     {
     }
 
@@ -96,9 +103,21 @@ class IndexRange {
       return *this;
     }
 
-    constexpr bool operator!=(const Iterator &iterator) const
+    constexpr Iterator operator++(int) const
+    {
+      Iterator copied_iterator = *this;
+      ++copied_iterator;
+      return copied_iterator;
+    }
+
+    constexpr friend bool operator!=(const Iterator &a, const Iterator &b)
+    {
+      return a.current_ != b.current_;
+    }
+
+    constexpr friend bool operator==(const Iterator &a, const Iterator &b)
     {
-      return current_ != iterator.current_;
+      return a.current_ == b.current_;
     }
 
     constexpr int64_t operator*() const
diff --git a/source/blender/blenlib/BLI_map.hh b/source/blender/blenlib/BLI_map.hh
index 9480af89107..9fa69853e44 100644
--- a/source/blender/blenlib/BLI_map.hh
+++ b/source/blender/blenlib/BLI_map.hh
@@ -120,6 +120,9 @@ template<
      */
     typename Allocator = GuardedAllocator>
 class Map {
+ public:
+  using size_type = int64_t;
+
  private:
   /**
    * Slots are either empty, occupied or removed. The number of occupied slots can be computed by
@@ -623,6 +626,9 @@ class Map {
    * This uses the "curiously recurring template pattern" (CRTP).
    */
   template<typename SubIterator> struct BaseIterator {
+    using iterator_category = std::forward_iterator_tag;
+    using difference_type = std::ptrdiff_t;
+
     Slot *slots_;
     int64_t total_slots_;
     int64_t current_slot_;
@@ -642,6 +648,13 @@ class Map {
       return *this;
     }
 
+    BaseIterator operator++(int) const
+    {
+      BaseIterator copied_iterator = *this;
+      ++copied_iterator;
+      return copied_iterator;
+    }
+
     friend bool operator!=(const BaseIterator &a, const BaseIterator &b)
     {
       BLI_assert(a.slots_ == b.slots_);
@@ -649,6 +662,11 @@ class Map {
       return a.current_slot_ != b.current_slot_;
     }
 
+    friend bool operator==(const BaseIterator &a, const BaseIterator &b)
+    {
+      return !(a != b);
+    }
+
     SubIterator begin() const
     {
       for (int64_t i = 0; i < total_slots_; i++) {
@@ -672,6 +690,10 @@ class Map {
 
   class KeyIterator final : public BaseIterator<KeyIterator> {
    public:
+    using value_type = Key;
+    using pointer = const Key *;
+    using reference = const Key &;
+
     KeyIterator(const Slot *slots, int64_t total_slots, int64_t current_slot)
         : BaseIterator<KeyIterator>(slots, total_slots, current_slot)
     {
@@ -685,6 +707,10 @@ class Map {
 
   class ValueIterator final : public BaseIterator<ValueIterator> {
    public:
+    using value_type = Value;
+    using pointer = const Value *;
+    using reference = const Value &;
+
     ValueIterator(const Slot *slots, int64_t total_slots, int64_t current_slot)
         : BaseIterator<ValueIterator>(slots, total_slots, current_slot)
     {
@@ -698,6 +724,10 @@ class Map {
 
   class MutableValueIterator final : public BaseIterator<MutableValueIterator> {
    public:
+    using value_type = Value;
+    using pointer = Value *;
+    using reference = Value &;
+
     MutableValueIterator(const Slot *slots, int64_t total_slots, int64_t current_slot)
         : BaseIterator<MutableValueIterator>(slots, total_slots, current_slot)
     {
@@ -726,6 +756,10 @@ class Map {
 
   class ItemIterator final : public BaseIterator<ItemIterator> {
    public:
+    using value_type = Item;
+    using pointer = Item *;
+    using reference = Item &;
+
     ItemIterator(const Slot *slots, int64_t total_slots, int64_t current_slot)
         : BaseIterator<ItemIterator>(slots, total_slots, current_slot)
     {
@@ -740,6 +774,10 @@ class Map {
 
   class MutableItemIterator final : public BaseIterator<MutableItemIterator> {
    public:
+    using value_type = MutableItem;
+    using pointer = MutableItem *;
+    using reference = MutableItem &;
+
     MutableItemIterator(const Slot *slots, int64_t total_slots, int64_t current_slot)
         : BaseIterator<MutableItemIterator>(slots, total_slots, current_slot)
     {
diff --git a/source/blender/blenlib/BLI_multi_value_map.hh b/source/blender/blenlib/BLI_multi_value_map.hh
index 4113085a1e3..98b55067a5c 100644
--- a/source/blender/blenlib/BLI_multi_value_map.hh
+++ b/source/blender/blenlib/BLI_multi_value_map.hh
@@ -38,6 +38,9 @@
 namespace blender {
 
 template<typename Key, typename Value> class MultiValueMap {
+ public:
+  using size_type = int64_t;
+
  private:
   using MapType = Map<Key, Vector<Value>>;
   MapType map_;
diff --git a/source/blender/blenlib/BLI_set.hh b/source/blender/blenlib/BLI_set.hh
index 06b56c3f8e5..fef657b2d8f 100644
--- a/source/blender/blenlib/BLI_set.hh
+++ b/source/blender/blenlib/BLI_set.hh
@@ -119,6 +119,16 @@ template<
      */
     typename Allocator = GuardedAllocator>
 class Set {
+ public:
+  class Iterator;
+  using value_type = Key;
+  using pointer = Key *;
+  using const_pointer = const Key *;
+  using reference = Key &;
+  using const_reference = const Key &;
+  using iterator = Iterator;
+  using size_type = int64_t;
+
  private:
   /**
    * Slots are either empty, occupied or removed. The number of occupied slots can be computed by
@@ -401,6 +411,13 @@ class Set {
    * also change their hash.
    */
   class Iterator {
+   public:
+    using iterator_category = std::forward_iterator_tag;
+    using value_type = Key;
+    using pointer = const Key *;
+    using reference = const Key &;
+    using difference_type = std::ptrdiff_t;
+
    private:
     const Slot *slots_;
     int64_t total_slots_;
@@ -422,17 +439,34 @@ class Set {
       return *this;
     }
 
+    Iterator operator++(int) const
+    {
+      Iterator copied_iterator = *this;
+      ++copied_iterator;
+      return copied_iterator;
+    }
+
     const Key &operator*() const
     {
       return *slots_[current_slot_].key();
     }
 
+    const Key *operator->() const
+    {
+      return slots_[current_slot_].key();
+    }
+
     friend bool operator!=(const Iterator &a, const Iterator &b)
     {
       BLI_assert(a.slots_ == b.slots_);
       BLI_assert(a.total_slots_ == b.total_slots_);
       return a.current_slot_ != b.current_slot_;
     }
+
+    friend bool operator==(const Iterator &a, const Iterator &b)
+    {
+      return !(a != b);
+    }
   };
 
   Iterator begin() const
diff --git a/source/blender/blenlib/BLI_span.hh b/source/blender/blenlib/BLI_span.hh
index fcc6d6f754b..fe511793c46 100644
--- a/source/blender/blenlib/BLI_span.hh
+++ b/source/blender/blenlib/BLI_span.hh
@@ -85,6 +85,15 @@ namespace blender {
  * modified.
  */
 template<typename T> class Span {
+ public:
+  using value_type = T;
+  using pointer = T *;
+  using const_pointer = const T *;
+  using reference = T &;
+  using const_reference = const T &;
+  using iterator = const T *;
+  using size_type = int64_t;
+
  private:
   const T *data_ = nullptr;
   int64_t size_ = 0;
@@ -459,6 +468,15 @@ template<typename T> class Span {
  * MutableSpan.
  */
 template<typename T> class MutableSpan {
+ public:
+  using value_type = T;
+  using pointer = T *;
+  using const_pointer = const T *;
+  using reference = T &;
+  using const_reference = const T &;
+  using iterator = T *;
+  using size_type = int64_t;
+
  private:
   T *data_;
   int64_t size_;
diff --git a/source/blender/blenlib/BLI_stack.hh b/source/blender/blenlib/BLI_stack.hh
index a463ac102f1..19f77078c5b 100644
--- a/source/blender/blenlib/BLI_stack.hh
+++ b/source/blender/blenlib/BLI_stack.hh
@@ -80,6 +80,14 @@ template<
      */
     typename Allocator = GuardedAllocator>
 class Stack {
+ public:
+  using value_type = T;
+  using pointer = T *;
+  using const_pointer = const T *;
+  using reference = T &;
+  using const_reference = const T &;
+  using size_type = int64_t;
+
  private:
   using Chunk = StackChunk<T>;
 
diff --git a/source/blender/blenlib/BLI_vector.hh b/source/blender/blenlib/BLI_vector.hh
index eefacd5d64f..328d623787b 100644
--- a/source/blender/blenlib/BLI_vector.hh
+++ b/source/blender/blenlib/BLI_vector.hh
@@ -76,6 +76,16 @@ template<
      */
     typename Allocator = GuardedAllocator>
 class Vector {
+ public:
+  using value_type = T;
+  using pointer = T *;
+  using const_pointer = const T *;
+  using reference = T &;
+  using const_reference = const T &;
+  using iterator = T *;
+  using const_iterator = const T *;
+  using size_type = int64_t;
+
  private:
   /**
    * Use pointers instead of storing the size explicitly. This reduces the number of instructions
diff --git a/source/blender/blenlib/BLI_vector_set.hh b/source/blender/blenlib/BLI_vector_set.hh
index c9773dc599d..14b38d564cb 100644
--- a/source/blender/blenlib/BLI_vector_set.hh
+++ b/source/blender/blenlib/BLI_vector_set.hh
@@ -100,6 +100,16 @@ template<
      */
     typename Allocator = GuardedAllocator>
 class VectorSet {
+ public:
+  using value_type = Key;
+  using pointer = Key *;
+  using const_pointer = const Key *;
+  using reference = Key &;
+  using const_reference = const Key &;
+  using iterator = Key *;
+  using const_iterator = const Key *;
+  using size_type = int64_t;
+
  private:
   /**
    * Slots are either empty, occupied or removed. The number of occupied slots can be computed by
diff --git a/source/blender/blenlib/tests/BLI_index_range_test.cc b/source/blender/blenlib/tests/BLI_index_range_test.cc
index ddaa067f50e..858dc2ee966 100644
--- a/source/blender/blenlib/tests/BLI_index_range_test.cc
+++ b/source/blender/blenlib/tests/BLI_index_range_test.cc
@@ -147,4 +147,13 @@ TEST(index_range, constexpr_)
   BLI_STATIC_ASSERT(range.size() == 1, "");
   EXPECT_EQ(compiles[0], 1);
 }
+
+TEST(index_range, GenericAlgorithms)
+{
+  IndexRange range{4, 10};
+  EXPECT_TRUE(std::any_of(range.begin(), range.end(), [](int v) { return v == 6; }));
+  EXPECT_FALSE(std::any_of(range.begin(), range.end(), [](int v) { return v == 20; }));
+  EXPECT_EQ(std::count_if(range.begin(), range.end(), [](int v) { return v < 7; }), 3);
+}
+
 }  // namespace blender::tests
diff --git a/source/blender/blenlib/tests/BLI_map_test.cc b/source/blender/blenlib/tests/BLI_map_test.cc
index 70c1887a527..f1ae8fb3921 100644
--- a/source/blender/blenlib/tests/BLI_map_test.cc
+++ b/source/blender/blenlib/tests/BLI_map_test.cc
@@ -587,6 +587,23 @@ TEST(map, EnumKey)
   EXPECT_EQ(map.lookup(TestEnum::B), 10);
 }
 
+TEST(map, GenericAlgorithms)
+{
+  Map<int, int> map;
+  map.add(5, 2);
+  map.add(1, 4);
+  map.add(2, 2);
+  map.add(7, 1);
+  map.add(8, 6);
+  EXPECT_TRUE(std::any_of(map.keys().begin(), map.keys().end(), [](int v) { return v == 1; }));
+  EXPECT_TRUE(std::any_of(map.values().begin(), map.values().end(), [](int v) { return v == 1; }));
+  EXPECT_TRUE(std::any_of(
+      map.items().begin(), map.items().end(), [](auto item) { return item.value == 1; }));
+  EXPECT_EQ(std::count(map.values().begin(), map.values().end(), 2), 2);
+  EXPECT_EQ(std::count(map.values().begin(), map.values().end(), 4), 1);
+  EXPECT_EQ(std::count(map.keys().begin(), map.keys().end(), 7), 1);
+}
+
 /**
  * Set this to 1 to activate the benchmark. It is disabled by default, because it prints a lot.
  */
diff --git a/source/blender/blenlib/tests/BLI_set_test.cc b/source/blender/blenlib/tests/BLI_set_test.cc
index ea4369d6b8f..56f1d57e4ae 100644
--- a/source/blender/blenlib/tests/BLI_set_test.cc
+++ b/source/blender/blenlib/tests/BLI_set_test.cc
@@ -526,6 +526,24 @@ TEST(set, AddExceptions)
   EXPECT_EQ(set.size(), 0);
 }
 
+TEST(set, ForwardIterator)
+{
+  Set<int> set = {5, 2, 6, 4, 1};
+  Set<int>::iterator iter1 = set.begin();
+  int value1 = *iter1;
+  Set<int>::iterator iter2 = iter1++;
+  EXPECT_EQ(*iter1, value1);
+  EXPECT_EQ(*iter2, *(++iter1));
+}
+
+TEST(set, GenericAlgorithms)
+{
+  Set<int> set = {1, 20, 30, 40};
+  EXPECT_FALSE(std::any_of(set.begin(), set.end(), [](int v) { return v == 5; }));
+  EXPECT_TRUE(std::any_of(set.begin(), set.end(), [](int v) { return v == 30; }));
+  EXPECT_EQ(std::count(set.begin(), set.end(), 20), 1);
+}
+
 /**
  * Set this to 1 to activate the benchmark. It is disabled by default, because it prints a lot.
  */