diff --git a/src/common/aka_iterators.hh b/src/common/aka_iterators.hh index cbd80220c..285ffcf4d 100644 --- a/src/common/aka_iterators.hh +++ b/src/common/aka_iterators.hh @@ -1,452 +1,575 @@ /** * @file aka_iterators.hh * * @author Nicolas Richart * * @date creation: Fri Aug 11 2017 * @date last modification: Mon Jan 29 2018 * * @brief iterator interfaces * * @section LICENSE * * Copyright (©) 2016-2018 EPFL (Ecole Polytechnique Fédérale de Lausanne) * Laboratory (LSMS - Laboratoire de Simulation en Mécanique des Solides) * * Akantu is free software: you can redistribute it and/or modify it under the * terms of the GNU Lesser General Public License as published by the Free * Software Foundation, either version 3 of the License, or (at your option) any * later version. * * Akantu is distributed in the hope that it will be useful, but WITHOUT ANY * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR * A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more * details. * * You should have received a copy of the GNU Lesser General Public License * along with Akantu. If not, see . * */ /* -------------------------------------------------------------------------- */ #include "aka_compatibilty_with_cpp_standard.hh" /* -------------------------------------------------------------------------- */ #include #include /* -------------------------------------------------------------------------- */ #ifndef __AKANTU_AKA_ITERATORS_HH__ #define __AKANTU_AKA_ITERATORS_HH__ namespace akantu { namespace tuple { /* ------------------------------------------------------------------------ */ namespace details { template struct Foreach { template static inline bool not_equal(Tuple && a, Tuple && b) { if (std::get(std::forward(a)) == std::get(std::forward(b))) return false; return Foreach::not_equal(std::forward(a), std::forward(b)); } }; /* ---------------------------------------------------------------------- */ template <> struct Foreach<0> { template static inline bool not_equal(Tuple && a, Tuple && b) { return std::get<0>(std::forward(a)) != std::get<0>(std::forward(b)); } }; template decltype(auto) make_tuple_no_decay(Ts &&... args) { return std::tuple(std::forward(args)...); } template void foreach_impl(F && func, Tuple && tuple, std::index_sequence &&) { (void)std::initializer_list{ (std::forward(func)(std::get(std::forward(tuple))), 0)...}; } template decltype(auto) transform_impl(F && func, Tuple && tuple, std::index_sequence &&) { return make_tuple_no_decay( std::forward(func)(std::get(std::forward(tuple)))...); } } // namespace details /* ------------------------------------------------------------------------ */ template bool are_not_equal(Tuple && a, Tuple && b) { return details::Foreach>::value>:: not_equal(std::forward(a), std::forward(b)); } template void foreach (F && func, Tuple && tuple) { return details::foreach_impl( std::forward(func), std::forward(tuple), std::make_index_sequence< std::tuple_size>::value>{}); } template decltype(auto) transform(F && func, Tuple && tuple) { return details::transform_impl( std::forward(func), std::forward(tuple), std::make_index_sequence< std::tuple_size>::value>{}); } } // namespace tuple /* -------------------------------------------------------------------------- */ namespace iterators { template class ZipIterator { public: using value_type = std::tuple::value_type...>; using difference_type = std::common_type_t< typename std::iterator_traits::difference_type...>; using pointer = std::tuple::pointer...>; using reference = std::tuple::reference...>; using iterator_category = // std::input_iterator_tag; std::common_type_t< typename std::iterator_traits::iterator_category...>; private: using tuple_t = std::tuple; public: explicit ZipIterator(tuple_t iterators) : iterators(std::move(iterators)) {} + template , + std::bidirectional_iterator_tag>::value> * = nullptr> + ZipIterator & operator--() { + tuple::foreach ([](auto && it) { --it; }, iterators); + return *this; + } + + template , + std::bidirectional_iterator_tag>::value> * = nullptr> + ZipIterator operator--(int a) { + auto cpy = *this; + this->operator--(a); + return cpy; + } + // input iterator ++it ZipIterator & operator++() { tuple::foreach ([](auto && it) { ++it; }, iterators); return *this; } // input iterator it++ ZipIterator operator++(int) { auto cpy = *this; - tuple::foreach ([](auto && it) { ++it; }, iterators); + this->operator++(); return cpy; } // input iterator it != other_it bool operator!=(const ZipIterator & other) const { return tuple::are_not_equal(iterators, other.iterators); } // input iterator dereference *it decltype(auto) operator*() { return tuple::transform([](auto && it) -> decltype(auto) { return *it; }, iterators); } + // random iterator it[idx] + template , + std::random_access_iterator_tag>::value> * = nullptr> + decltype(auto) operator[](std::size_t idx) { + return tuple::transform( + [idx](auto && it) -> decltype(auto) { return it[idx]; }, iterators); + } + bool operator==(const ZipIterator & other) const { return not tuple::are_not_equal(iterators, other.iterators); } private: tuple_t iterators; }; } // namespace iterators /* -------------------------------------------------------------------------- */ template decltype(auto) zip_iterator(std::tuple && iterators_tuple) { auto zip = iterators::ZipIterator( std::forward(iterators_tuple)); return zip; } /* -------------------------------------------------------------------------- */ namespace containers { template class ZipContainer { using containers_t = std::tuple; public: explicit ZipContainer(Containers &&... containers) : containers(std::forward(containers)...) {} decltype(auto) begin() const { return zip_iterator( tuple::transform([](auto && c) { return c.begin(); }, std::forward(containers))); } decltype(auto) end() const { return zip_iterator( tuple::transform([](auto && c) { return c.end(); }, std::forward(containers))); } decltype(auto) begin() { return zip_iterator( tuple::transform([](auto && c) { return c.begin(); }, std::forward(containers))); } decltype(auto) end() { return zip_iterator( tuple::transform([](auto && c) { return c.end(); }, std::forward(containers))); } private: containers_t containers; }; template class Range { public: explicit Range(Iterator && it1, Iterator && it2) : iterators(std::forward(it1), std::forward(it2)) {} decltype(auto) begin() const { return std::get<0>(iterators); } decltype(auto) begin() { return std::get<0>(iterators); } decltype(auto) end() const { return std::get<1>(iterators); } decltype(auto) end() { return std::get<1>(iterators); } private: std::tuple iterators; }; } // namespace containers /* -------------------------------------------------------------------------- */ template decltype(auto) zip(Containers &&... conts) { return containers::ZipContainer( std::forward(conts)...); } template decltype(auto) range(Iterator && it1, Iterator && it2) { return containers::Range(std::forward(it1), std::forward(it2)); } /* -------------------------------------------------------------------------- */ /* Arange */ /* -------------------------------------------------------------------------- */ namespace iterators { template class ArangeIterator { public: using value_type = T; using pointer = T *; using reference = T &; using difference_type = size_t; using iterator_category = std::input_iterator_tag; constexpr ArangeIterator(T value, T step) : value(value), step(step) {} constexpr ArangeIterator(const ArangeIterator &) = default; constexpr ArangeIterator & operator++() { value += step; return *this; } constexpr T operator*() const { return value; } constexpr bool operator==(const ArangeIterator & other) const { return (value == other.value) and (step == other.step); } constexpr bool operator!=(const ArangeIterator & other) const { return not operator==(other); } private: T value{0}; const T step{1}; }; } // namespace iterators namespace containers { template class ArangeContainer { public: using iterator = iterators::ArangeIterator; using const_iterator = iterators::ArangeIterator; constexpr ArangeContainer(T start, T stop, T step = 1) : start(start), stop((stop - start) % step == 0 ? stop : start + (1 + (stop - start) / step) * step), step(step) {} explicit constexpr ArangeContainer(T stop) : ArangeContainer(0, stop, 1) {} constexpr T operator[](size_t i) { T val = start + i * step; assert(val < stop && "i is out of range"); return val; } constexpr T size() { return (stop - start) / step; } constexpr iterator begin() { return iterator(start, step); } constexpr iterator end() { return iterator(stop, step); } private: const T start{0}, stop{0}, step{1}; }; } // namespace containers template >::value>> inline decltype(auto) arange(const T & stop) { return containers::ArangeContainer(stop); } template >::value>> inline constexpr decltype(auto) arange(const T1 & start, const T2 & stop) { return containers::ArangeContainer>(start, stop); } template >::value>> inline constexpr decltype(auto) arange(const T1 & start, const T2 & stop, const T3 & step) { return containers::ArangeContainer>( start, stop, step); } /* -------------------------------------------------------------------------- */ template inline constexpr decltype(auto) enumerate(Container && container, size_t start_ = 0) { auto stop = std::forward(container).size(); decltype(stop) start = start_; return zip(arange(start, stop), std::forward(container)); } namespace iterators { template class transform_adaptor_iterator { public: using value_type = decltype(std::declval()( std::declval())); using difference_type = typename iterator_t::difference_type; using pointer = std::decay_t *; using reference = value_type &; using iterator_category = typename iterator_t::iterator_category; transform_adaptor_iterator(iterator_t it, operator_t && op) : it(std::move(it)), op(op) {} transform_adaptor_iterator(const transform_adaptor_iterator &) = default; transform_adaptor_iterator & operator++() { ++it; return *this; } decltype(auto) operator*() const { return op(*it); } bool operator==(const transform_adaptor_iterator & other) const { return (it == other.it); } bool operator!=(const transform_adaptor_iterator & other) const { return not operator==(other); } private: iterator_t it; operator_t op; }; template decltype(auto) make_transform_adaptor_iterator(iterator_t it, operator_t && op) { return transform_adaptor_iterator( it, std::forward(op)); } } // namespace iterators namespace containers { template class TransformIteratorAdaptor { public: using const_iterator = typename std::decay_t::const_iterator; using iterator = typename std::decay_t::iterator; TransformIteratorAdaptor(container_t && cont, operator_t && op) : cont(std::forward(cont)), op(std::forward(op)) {} decltype(auto) begin() const { return iterators::make_transform_adaptor_iterator(cont.begin(), op); } decltype(auto) begin() { return iterators::make_transform_adaptor_iterator(cont.begin(), op); } decltype(auto) end() const { return iterators::make_transform_adaptor_iterator(cont.end(), op); } decltype(auto) end() { return iterators::make_transform_adaptor_iterator(cont.end(), op); } private: container_t cont; operator_t op; }; } // namespace containers template decltype(auto) make_transform_adaptor(container_t && cont, operator_t && op) { return containers::TransformIteratorAdaptor( std::forward(cont), std::forward(op)); } template decltype(auto) make_keys_adaptor(container_t && cont) { return make_transform_adaptor( std::forward(cont), [](auto && pair) -> decltype(pair.first) { return pair.first; }); } template decltype(auto) make_values_adaptor(container_t && cont) { return make_transform_adaptor( std::forward(cont), [](auto && pair) -> decltype(pair.second) { return pair.second; }); } template decltype(auto) make_dereference_adaptor(container_t && cont) { return make_transform_adaptor( std::forward(cont), [](auto && value) -> decltype(*value) { return *value; }); } +/* -------------------------------------------------------------------------- */ +namespace iterators { + template + class RandomAccessFilterIterator { + public: + using value_type = + decltype(std::declval().operator[](0)); + using difference_type = typename filter_iterator_t::difference_type; + using pointer = std::decay_t *; + using reference = value_type &; + using iterator_category = typename filter_iterator_t::iterator_category; + + RandomAccessFilterIterator(filter_iterator_t && filter_it, + container_iterator_t && container_begin) + : filter_it(std::forward(filter_it)), + container_begin(std::forward(container_begin)) {} + + RandomAccessFilterIterator(const RandomAccessFilterIterator &) = default; + + RandomAccessFilterIterator & operator++() { + ++filter_it; + return *this; + } + + decltype(auto) operator*() const { return container_begin[*filter_it]; } + + bool operator==(const RandomAccessFilterIterator & other) const { + return (filter_it == other.filter_it) and + (container_begin == other.container_begin); + } + + bool operator!=(const RandomAccessFilterIterator & other) const { + return not operator==(other); + } + + private: + filter_iterator_t filter_it; + container_iterator_t container_begin; + }; + + template + decltype(auto) + make_random_access_filter_iterator(filter_iterator_t && filter_it, + container_iterator_t && container_begin) { + return RandomAccessFilterIterator( + std::forward(filter_it), + std::forward(container_begin)); + } +} // namespace iterators + +namespace containers { + template class RandomAccessFilterAdaptor { + public: + RandomAccessFilterAdaptor(filter_t && filter, container_t && container) + : filter(std::forward(filter)), + container(std::forward(container)) {} + + decltype(auto) begin() const { + return iterators::make_random_access_filter_iterator(filter.begin(), + container.begin()); + } + decltype(auto) begin() { + return iterators::make_random_access_filter_iterator(filter.begin(), + container.begin()); + } + + decltype(auto) end() const { + return iterators::make_random_access_filter_iterator(filter.end(), + container.begin()); + } + decltype(auto) end() { + return iterators::make_random_access_filter_iterator(filter.end(), + container.begin()); + } + + private: + filter_t filter; + container_t container; + }; +} // namespace containers + +template ::iterator::iterator_category>::value> * = nullptr> +decltype(auto) make_filtered_adaptor(filter_t && filter, container_t && container) { + return containers::RandomAccessFilterAdaptor( + std::forward(filter), std::forward(container)); +} + + + } // namespace akantu namespace std { template struct iterator_traits<::akantu::iterators::ZipIterator> { using iterator_category = forward_iterator_tag; using value_type = typename ::akantu::iterators::ZipIterator::value_type; using difference_type = typename ::akantu::iterators::ZipIterator::difference_type; using pointer = typename ::akantu::iterators::ZipIterator::pointer; using reference = typename ::akantu::iterators::ZipIterator::reference; }; - } // namespace std #endif /* __AKANTU_AKA_ITERATORS_HH__ */ diff --git a/test/test_common/test_iterators.cc b/test/test_common/test_iterators.cc index b07cf52df..d68b00cf8 100644 --- a/test/test_common/test_iterators.cc +++ b/test/test_common/test_iterators.cc @@ -1,300 +1,318 @@ /** * @file test_zip_iterator.cc * * @author Nicolas Richart * * @date creation: Fri Jul 21 2017 * @date last modification: Fri Dec 08 2017 * * @brief test the zip container and iterator * * @section LICENSE * * Copyright (©) 2016-2018 EPFL (Ecole Polytechnique Fédérale de Lausanne) * Laboratory (LSMS - Laboratoire de Simulation en Mécanique des Solides) * * Akantu is free software: you can redistribute it and/or modify it under the * terms of the GNU Lesser General Public License as published by the Free * Software Foundation, either version 3 of the License, or (at your option) any * later version. * * Akantu is distributed in the hope that it will be useful, but WITHOUT ANY * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR * A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more * details. * * You should have received a copy of the GNU Lesser General Public License * along with Akantu. If not, see . * */ /* -------------------------------------------------------------------------- */ #include "aka_iterators.hh" /* -------------------------------------------------------------------------- */ #include #include /* -------------------------------------------------------------------------- */ using namespace akantu; /* -------------------------------------------------------------------------- */ template class A { public: A() = default; A(T a) : a(a){}; A(const A & other) : a(other.a), copy_counter(other.copy_counter + 1), move_counter(other.move_counter) {} A & operator=(const A & other) { if (this != &other) { a = other.a; copy_counter = other.copy_counter + 1; } return *this; } A(A && other) : a(std::move(other.a)), copy_counter(std::move(other.copy_counter)), move_counter(std::move(other.move_counter) + 1) {} A & operator=(A && other) { if (this != &other) { a = std::move(other.a); copy_counter = std::move(other.copy_counter); move_counter = std::move(other.move_counter) + 1; } return *this; } A & operator*=(const T & b) { a *= b; return *this; } T a; size_t copy_counter{0}; size_t move_counter{0}; }; template struct C { struct iterator { using reference = A; using difference_type = void; using iterator_category = std::input_iterator_tag; using value_type = A; using pointer = A *; iterator(T pos) : pos(std::move(pos)) {} A operator*() { return A(pos); } bool operator!=(const iterator & other) const { return pos != other.pos; } bool operator==(const iterator & other) const { return pos == other.pos; } iterator & operator++() { ++pos; return *this; } T pos; }; C(T begin_, T end_) : begin_(std::move(begin_)), end_(std::move(end_)) {} iterator begin() { return iterator(begin_); } iterator end() { return iterator(end_); } T begin_, end_; }; class TestZipFixutre : public ::testing::Test { protected: void SetUp() override { a.reserve(size); b.reserve(size); for (size_t i = 0; i < size; ++i) { a.emplace_back(i); b.emplace_back(i + size); } } template void check(A && a, B && b, size_t pos, size_t nb_copy, size_t nb_move) { EXPECT_EQ(pos, a.a); EXPECT_EQ(nb_copy, a.copy_counter); EXPECT_EQ(nb_move, a.move_counter); EXPECT_FLOAT_EQ(pos + this->size, b.a); EXPECT_EQ(nb_copy, b.copy_counter); EXPECT_EQ(nb_move, b.move_counter); } protected: size_t size{20}; std::vector> a; std::vector> b; }; TEST_F(TestZipFixutre, SimpleTest) { size_t i = 0; for (auto && pair : zip(this->a, this->b)) { this->check(std::get<0>(pair), std::get<1>(pair), i, 0, 0); ++i; } } TEST_F(TestZipFixutre, ConstTest) { size_t i = 0; const auto & ca = this->a; const auto & cb = this->b; for (auto && pair : zip(ca, cb)) { this->check(std::get<0>(pair), std::get<1>(pair), i, 0, 0); EXPECT_EQ(true, std::is_const< std::remove_reference_t(pair))>>::value); EXPECT_EQ(true, std::is_const< std::remove_reference_t(pair))>>::value); ++i; } } TEST_F(TestZipFixutre, MixteTest) { size_t i = 0; const auto & cb = this->b; for (auto && pair : zip(a, cb)) { this->check(std::get<0>(pair), std::get<1>(pair), i, 0, 0); EXPECT_EQ(false, std::is_const< std::remove_reference_t(pair))>>::value); EXPECT_EQ(true, std::is_const< std::remove_reference_t(pair))>>::value); ++i; } } TEST_F(TestZipFixutre, MoveTest) { size_t i = 0; for (auto && pair : zip(C(0, this->size), C(this->size, 2 * this->size))) { this->check(std::get<0>(pair), std::get<1>(pair), i, 0, 1); ++i; } } +TEST_F(TestZipFixutre, RandomAccess) { + auto begin = zip(a, b).begin(); + + auto && val5 = begin[5]; + this->check(std::get<0>(val5), std::get<1>(val5), 5, 0, 0); + + auto && val13 = begin[13]; + this->check(std::get<0>(val13), std::get<1>(val13), 13, 0, 0); +} + /* -------------------------------------------------------------------------- */ TEST(TestArangeIterator, Stop) { size_t ref_i = 0; for (auto i : arange(10)) { EXPECT_EQ(ref_i, i); ++ref_i; } } TEST(TestArangeIterator, StartStop) { size_t ref_i = 1; for (auto i : arange(1, 10)) { EXPECT_EQ(ref_i, i); ++ref_i; } } TEST(TestArangeIterator, StartStopStep) { size_t ref_i = 1; for (auto i : arange(1, 22, 2)) { EXPECT_EQ(ref_i, i); ref_i += 2; } } TEST(TestArangeIterator, StartStopStepZipped) { int ref_i1 = -1, ref_i2 = 1; for (auto && i : zip(arange(-1, -10, -1), arange(1, 18, 2))) { EXPECT_EQ(ref_i1, std::get<0>(i)); EXPECT_EQ(ref_i2, std::get<1>(i)); ref_i1 += -1; ref_i2 += 2; } } /* -------------------------------------------------------------------------- */ TEST(TestTransformAdaptor, Keys) { std::map map{ {"1", 1}, {"2", 2}, {"3", 3}, {"3", 3}, {"4", 4}}; char counter = '1'; for (auto && key : make_keys_adaptor(map)) { EXPECT_EQ(counter, key[0]); ++counter; } } TEST(TestTransformAdaptor, Values) { std::map map{ {"1", 1}, {"2", 2}, {"3", 3}, {"3", 3}, {"4", 4}}; int counter = 1; for (auto && value : make_values_adaptor(map)) { EXPECT_EQ(counter, value); ++counter; } } static int plus1(int value) { return value + 1; } struct Plus { Plus(int a) : a(a) {} int operator()(int b) { return a + b; } private: int a{0}; }; TEST(TestTransformAdaptor, Lambda) { auto && container = arange(10); for (auto && data : zip(container, make_transform_adaptor(container, [](auto && value) { return value + 1; }))) { EXPECT_EQ(std::get<0>(data) + 1, std::get<1>(data)); } } TEST(TestTransformAdaptor, LambdaLambda) { std::map map{ {"1", 1}, {"2", 2}, {"3", 3}, {"3", 3}, {"4", 4}}; int counter = 1; for (auto && data : make_transform_adaptor( make_values_adaptor(map), [](auto && value) { return value + 1; })) { EXPECT_EQ(counter + 1, data); ++counter; } auto && container = arange(10); for (auto && data : zip(container, make_transform_adaptor(container, [](auto && value) { return value + 1; }))) { EXPECT_EQ(std::get<0>(data) + 1, std::get<1>(data)); } } TEST(TestTransformAdaptor, Function) { auto && container = arange(10); for (auto && data : zip(container, make_transform_adaptor(container, plus1))) { EXPECT_EQ(std::get<0>(data) + 1, std::get<1>(data)); } } TEST(TestTransformAdaptor, Functor) { auto && container = arange(10); for (auto && data : zip(container, make_transform_adaptor(container, Plus(1)))) { EXPECT_EQ(std::get<0>(data) + 1, std::get<1>(data)); } } + +TEST(TestFilteredIterator, Simple) { + std::vector values{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; + std::vector filter{0, 2, 4, 10, 8, 6}; + for (auto && data : zip(filter, make_filtered_adaptor(filter, values))) { + EXPECT_EQ(std::get<0>(data), std::get<1>(data)); + } +}