Index: include/llvm/ADT/STLExtras.h =================================================================== --- include/llvm/ADT/STLExtras.h +++ include/llvm/ADT/STLExtras.h @@ -226,39 +226,6 @@ static const bool value = sizeof(test(nullptr)) == sizeof(yes); }; -/// Metafunction to determine if T& or T has a member called rbegin(). -template -struct has_rbegin : has_rbegin_impl::type> { -}; - -// Returns an iterator_range over the given container which iterates in reverse. -// Note that the container must have rbegin()/rend() methods for this to work. -template -auto reverse(ContainerTy &&C, - typename std::enable_if::value>::type * = - nullptr) -> decltype(make_range(C.rbegin(), C.rend())) { - return make_range(C.rbegin(), C.rend()); -} - -// Returns a std::reverse_iterator wrapped around the given iterator. -template -std::reverse_iterator make_reverse_iterator(IteratorTy It) { - return std::reverse_iterator(It); -} - -// Returns an iterator_range over the given container which iterates in reverse. -// Note that the container must have begin()/end() methods which return -// bidirectional iterators for this to work. -template -auto reverse( - ContainerTy &&C, - typename std::enable_if::value>::type * = nullptr) - -> decltype(make_range(llvm::make_reverse_iterator(std::end(C)), - llvm::make_reverse_iterator(std::begin(C)))) { - return make_range(llvm::make_reverse_iterator(std::end(C)), - llvm::make_reverse_iterator(std::begin(C))); -} - /// An iterator adaptor that filters the elements of given inner iterators. /// /// The predicate parameter should be a callable object that accepts the wrapped @@ -311,8 +278,14 @@ // have to be engaged. filter_iterator(WrappedIteratorT End) : BaseT(End) {} + // Used to implement a predicate to check if an object is a filter_iterator. + template + friend struct is_filter_iterator; + struct filter_iterator_tag; + public: using BaseT::operator++; + using BaseT::wrapped; filter_iterator &operator++() { BaseT::operator++(); @@ -323,6 +296,28 @@ template friend iterator_range, PT>> make_filter_range(RT &&, PT); + + /// Move the predicate out of the iterator. This invalidates the iterator. + PredicateT takePredicate() { + assert(Payload && "Cannot find the predicate"); + PredicateT P = std::move(Payload->Pred); + Payload = None; + return std::move(P); + } +}; + +/// Metafunction to determine if T is a filter iterator. +template struct is_filter_iterator { + using yes = char[1]; + using no = char[2]; + + template + static yes &test(Inner *I, typename Inner::filter_iterator_tag * = nullptr); + + template static no &test(...); + +public: + static const bool value = sizeof(test(nullptr)) == sizeof(yes); }; /// Convenience function that takes a range of elements and a predicate, @@ -343,6 +338,58 @@ FilterIteratorT(std::end(std::forward(Range)))); } +/// Metafunction to determine if T& or T has a member called rbegin(). +template +struct has_rbegin : has_rbegin_impl::type> { +}; + +// Returns an iterator_range over the given container which iterates in reverse. +// Note that the container must have rbegin()/rend() methods for this to work. +template +auto reverse(ContainerTy &&C, + typename std::enable_if::value>::type * = + nullptr) -> decltype(make_range(C.rbegin(), C.rend())) { + return make_range(C.rbegin(), C.rend()); +} + +// Returns a std::reverse_iterator wrapped around the given iterator. +template +std::reverse_iterator make_reverse_iterator(IteratorTy It) { + return std::reverse_iterator(It); +} + +// Returns an iterator_range over the given container which iterates in reverse. +// Note that the container must have begin()/end() methods which return +// bidirectional iterators for this to work. +template +auto reverse( + ContainerTy &&C, + typename std::enable_if< + !has_rbegin::value && + !is_filter_iterator::value>::type * = nullptr) + -> decltype(make_range(llvm::make_reverse_iterator(std::end(C)), + llvm::make_reverse_iterator(std::begin(C)))) { + return make_range(llvm::make_reverse_iterator(std::end(C)), + llvm::make_reverse_iterator(std::begin(C))); +} + +// Returns an iterator_range over the given filtered range which iterates in +// reverse. Note that this invalidates the input filtered range. +template +auto reverse( + FilteredRangeT &&R, + typename std::enable_if::value, + void>::type * = nullptr) + -> decltype(make_filter_range( + make_range(llvm::make_reverse_iterator(R.end().wrapped()), + llvm::make_reverse_iterator(R.begin().wrapped())), + R.begin().takePredicate())) { + return make_filter_range( + make_range(llvm::make_reverse_iterator(R.end().wrapped()), + llvm::make_reverse_iterator(R.begin().wrapped())), + R.begin().takePredicate()); +} + // forward declarations required by zip_shortest/zip_first template bool all_of(R &&range, UnaryPredicate P); Index: unittests/ADT/IteratorTest.cpp =================================================================== --- unittests/ADT/IteratorTest.cpp +++ unittests/ADT/IteratorTest.cpp @@ -8,6 +8,7 @@ //===----------------------------------------------------------------------===// #include "llvm/ADT/iterator.h" +#include "llvm/ADT/ArrayRef.h" #include "llvm/ADT/STLExtras.h" #include "llvm/ADT/SmallVector.h" #include "gtest/gtest.h" @@ -196,6 +197,23 @@ EXPECT_EQ((SmallVector{1, 3, 5}), Actual); } +TEST(FilterIteratorTest, ReverseFilterRange) { + auto IsOdd = [](int N) { return N % 2 == 1; }; + int A[] = {0, 1, 2, 3, 4, 5, 6}; + + auto Range = reverse(make_filter_range(A, IsOdd)); + SmallVector Actual(Range.begin(), Range.end()); + EXPECT_EQ((SmallVector{5, 3, 1}), Actual); + + auto Range2 = reverse(reverse(make_filter_range(A, IsOdd))); + SmallVector Actual2(Range2.begin(), Range2.end()); + EXPECT_EQ((SmallVector{1, 3, 5}), Actual2); + + auto Range3 = reverse(make_filter_range(ArrayRef(), IsOdd)); + SmallVector Actual3(Range3.begin(), Range3.end()); + EXPECT_EQ((SmallVector{}), Actual3); +} + TEST(PointerIterator, Basic) { int A[] = {1, 2, 3, 4}; pointer_iterator Begin(std::begin(A)), End(std::end(A));