diff options
author | Jacques Lucke <jacques@blender.org> | 2020-08-14 14:16:44 +0300 |
---|---|---|
committer | Jacques Lucke <jacques@blender.org> | 2020-08-14 14:16:44 +0300 |
commit | cc6c52768a9e6d5c82f35e953a6e53ece76d3a78 (patch) | |
tree | 2318e47733e2c63eda60011b22797bad22022cbd /source/blender/blenlib | |
parent | 2d653364086d62cc9b503724c962cc466ad3e4b4 (diff) |
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.
Diffstat (limited to 'source/blender/blenlib')
-rw-r--r-- | source/blender/blenlib/BLI_array.hh | 20 | ||||
-rw-r--r-- | source/blender/blenlib/BLI_span.hh | 20 | ||||
-rw-r--r-- | source/blender/blenlib/BLI_vector.hh | 108 | ||||
-rw-r--r-- | source/blender/blenlib/tests/BLI_array_test.cc | 15 | ||||
-rw-r--r-- | source/blender/blenlib/tests/BLI_span_test.cc | 28 | ||||
-rw-r--r-- | source/blender/blenlib/tests/BLI_vector_test.cc | 77 |
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 |