diff options
| -rw-r--r-- | gfx/gl/instanceVertices.h | 23 | ||||
| -rw-r--r-- | test/test-instancing.cpp | 30 |
2 files changed, 53 insertions, 0 deletions
diff --git a/gfx/gl/instanceVertices.h b/gfx/gl/instanceVertices.h index d9d9123..ad1716d 100644 --- a/gfx/gl/instanceVertices.h +++ b/gfx/gl/instanceVertices.h @@ -124,6 +124,13 @@ public: return base::size(); } + template<typename Pred> + glContainer<T>::iterator + partition(Pred pred) + { + return partition(base::begin(), base::end(), pred); + } + protected: friend InstanceProxy; @@ -152,6 +159,22 @@ protected: return base::data()[index[pindex]]; } + template<typename Pred> + glContainer<T>::iterator + partition(glContainer<T>::iterator first, glContainer<T>::iterator last, Pred pred) + { + while (first < last) { + first = std::find_if_not(first, last, pred); + last = --std::find_if(std::make_reverse_iterator(last), std::make_reverse_iterator(first), pred).base(); + if (first < last) { + std::iter_swap(first, last); + std::iter_swap(std::find(index.begin(), index.end(), first - base::begin()), + std::find(index.begin(), index.end(), last - base::begin())); + } + } + return first; + } + // Index into buffer given to nth proxy std::vector<size_t> index; // List of free spaces in index diff --git a/test/test-instancing.cpp b/test/test-instancing.cpp index c1860a4..37f32c8 100644 --- a/test/test-instancing.cpp +++ b/test/test-instancing.cpp @@ -174,4 +174,34 @@ BOOST_DATA_TEST_CASE(shuffle_random, boost::unit_test::data::xrange(0, 10), x) } } +BOOST_AUTO_TEST_CASE(partition_by, *boost::unit_test::timeout(1)) +{ + std::mt19937 gen(std::random_device {}()); + std::uniform_int_distribution<int> dist(0, 100000); + static constexpr auto N = 1000; + reserve(N); + std::vector<decltype(acquire(0))> instances; + instances.reserve(N); + // At least one of each + instances.push_back(acquire(1)); + instances.push_back(acquire(3)); + while (instances.size() < N) { + instances.push_back(acquire(dist(gen))); + } + const std::vector<int> values(instances.begin(), instances.end()); + BOOST_REQUIRE_EQUAL(size(), N); + + const auto pred = [](auto x) { + return (x % 3) == 0; + }; + auto matchedEnd = partition(pred); + // The underlying data is partitioned... + BOOST_REQUIRE(std::is_partitioned(mkcspan().cbegin(), mkcspan().cend(), pred)); + // The external view of the data is unchanged... + BOOST_CHECK_EQUAL_COLLECTIONS(values.cbegin(), values.cend(), instances.cbegin(), instances.cend()); + // The partition point is right... + BOOST_CHECK(!pred(*matchedEnd)); + BOOST_CHECK(pred(*--matchedEnd)); +} + BOOST_AUTO_TEST_SUITE_END() |