[Bf-blender-cvs] [cc6c52768a9] master: BLI: add reverse iterators, iterator constructor and Vector.insert/prepend
Jacques Lucke
noreply at git.blender.org
Fri Aug 14 13:17:15 CEST 2020
Commit: cc6c52768a9e6d5c82f35e953a6e53ece76d3a78
Author: Jacques Lucke
Date: Fri Aug 14 13:16:44 2020 +0200
Branches: master
https://developer.blender.org/rBcc6c52768a9e6d5c82f35e953a6e53ece76d3a78
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.
===================================================================
M source/blender/blenlib/BLI_array.hh
M source/blender/blenlib/BLI_span.hh
M source/blender/blenlib/BLI_vector.hh
M source/blender/blenlib/tests/BLI_array_test.cc
M source/blender/blenlib/tests/BLI_span_test.cc
M source/blender/blenlib/tests/BLI_vector_test.cc
===================================================================
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, InsertAtIt
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list