From 8cd97e5ff78f2ab125cb604c3df3618e8d6c4ec4 Mon Sep 17 00:00:00 2001 From: Hannes Roth Date: Thu, 17 Apr 2014 09:26:56 -0700 Subject: [PATCH] (Folly/Gen) Make ranges and sequences take a stepping functor Summary: The functor allows to create ranges and sequences that advance the iterator by more than 1 per iteration. Test Plan: Unit test. Reviewed By: tjackson@fb.com FB internal diff: D1228065 --- folly/gen/Base-inl.h | 100 ++++++++++++++++++++++-------------- folly/gen/Base.h | 50 ++++++++++++++---- folly/gen/test/BaseTest.cpp | 15 ++++++ 3 files changed, 117 insertions(+), 48 deletions(-) diff --git a/folly/gen/Base-inl.h b/folly/gen/Base-inl.h index 1c2da985..a805b08e 100644 --- a/folly/gen/Base-inl.h +++ b/folly/gen/Base-inl.h @@ -183,47 +183,29 @@ class RangeSource : public GenImpl::reference, /** * Sequence - For generating values from beginning value, incremented along the - * way with the ++ and += operators. Iteration may continue indefinitely by - * setting the 'endless' template parameter to true. If set to false, iteration - * will stop when value reaches 'end', either inclusively or exclusively, - * depending on the template parameter 'endInclusive'. Value type specified - * explicitly. + * way with the ++ and += operators. Iteration may continue indefinitely. + * Value type specified explicitly. * * This type is primarily used through the 'seq' and 'range' function, like: * * int total = seq(1, 10) | sum; * auto indexes = range(0, 10); + * auto endless = seq(0); // 0, 1, 2, 3, ... */ -template -class Sequence : public GenImpl> { +template +class Sequence : public GenImpl> { static_assert(!std::is_reference::value && !std::is_const::value, "Value mustn't be const or ref."); - Value bounds_[endless ? 1 : 2]; + Value start_; + SequenceImpl impl_; public: - explicit Sequence(Value begin) - : bounds_{std::move(begin)} { - static_assert(endless, "Must supply 'end'"); - } - - Sequence(Value begin, - Value end) - : bounds_{std::move(begin), std::move(end)} {} + explicit Sequence(Value start, SequenceImpl impl) + : start_(std::move(start)), impl_(std::move(impl)) { } template bool apply(Handler&& handler) const { - Value value = bounds_[0]; - for (;endless || value < bounds_[1]; ++value) { - const Value& arg = value; - if (!handler(arg)) { - return false; - } - } - if (endInclusive && value == bounds_[1]) { - const Value& arg = value; - if (!handler(arg)) { + for (Value current = start_; impl_.test(current); impl_.step(current)) { + if (!handler(current)) { return false; } } @@ -232,18 +214,60 @@ public: template void foreach(Body&& body) const { - Value value = bounds_[0]; - for (;endless || value < bounds_[1]; ++value) { - const Value& arg = value; - body(arg); - } - if (endInclusive && value == bounds_[1]) { - const Value& arg = value; - body(arg); + for (Value current = start_; impl_.test(current); impl_.step(current)) { + body(current); } } +}; + +/** + * Sequence implementations (range, sequence, infinite, with/without step) + **/ +template +class RangeImpl { + Value end_; + public: + explicit RangeImpl(Value end) : end_(std::move(end)) { } + bool test(const Value& current) const { return current < end_; } + void step(Value& current) const { ++current; } +}; - static constexpr bool infinite = endless; +template +class RangeWithStepImpl { + Value end_; + Distance step_; + public: + explicit RangeWithStepImpl(Value end, Distance step) + : end_(std::move(end)), step_(std::move(step)) { } + bool test(const Value& current) const { return current < end_; } + void step(Value& current) const { current += step_; } +}; + +template +class SeqImpl { + Value end_; + public: + explicit SeqImpl(Value end) : end_(std::move(end)) { } + bool test(const Value& current) const { return current <= end_; } + void step(Value& current) const { ++current; } +}; + +template +class SeqWithStepImpl { + Value end_; + Distance step_; + public: + explicit SeqWithStepImpl(Value end, Distance step) + : end_(std::move(end)), step_(std::move(step)) { } + bool test(const Value& current) const { return current <= end_; } + void step(Value& current) const { current += step_; } +}; + +template +class InfiniteImpl { + public: + bool test(const Value& current) const { return true; } + void step(Value& current) const { ++current; } }; /** diff --git a/folly/gen/Base.h b/folly/gen/Base.h index 06cc0e3c..287d4a6c 100644 --- a/folly/gen/Base.h +++ b/folly/gen/Base.h @@ -256,9 +256,24 @@ template::type>> class CopiedSource; -template +template class Sequence; +template +class RangeImpl; + +template +class RangeWithStepImpl; + +template +class SeqImpl; + +template +class SeqWithStepImpl; + +template +class InfiniteImpl; + template class Yield; @@ -396,21 +411,36 @@ From from(Container&& source) { return From(std::move(source)); } -template> +template, + class Gen = detail::Sequence> Gen range(Value begin, Value end) { - return Gen(begin, end); + return Gen{std::move(begin), Impl{std::move(end)}}; } -template> +template, + class Gen = detail::Sequence> +Gen range(Value begin, Value end, Distance step) { + return Gen{std::move(begin), Impl{std::move(end), std::move(step)}}; +} + +template, + class Gen = detail::Sequence> Gen seq(Value first, Value last) { - return Gen(first, last); + return Gen{std::move(first), Impl{std::move(last)}}; } -template> -Gen seq(Value begin) { - return Gen(begin); +template, + class Gen = detail::Sequence> +Gen seq(Value first, Value last, Distance step) { + return Gen{std::move(first), Impl{std::move(last), std::move(step)}}; +} + +template, + class Gen = detail::Sequence> +Gen seq(Value first) { + return Gen{std::move(first), Impl{}}; } template arr{{1, 2, 3, 4, 5, 6}}; + EXPECT_EQ(9, seq(&arr[0], &arr[5], 2) + | map([](const int *i) { return *i; }) + | sum); +} + TEST(Gen, Range) { // cover the fenceposts of the loop unrolling for (int n = 1; n < 100; ++n) { @@ -193,6 +204,10 @@ TEST(Gen, Range) { } } +TEST(Gen, RangeWithStep) { + EXPECT_EQ(50, range(5, 25, 5) | sum); +} + TEST(Gen, FromIterators) { vector source {2, 3, 5, 7, 11}; auto gen = from(folly::range(source.begin() + 1, source.end() - 1)); -- 2.34.1