From a1107271b093884b8bb4b4dfd911533a46bae61b Mon Sep 17 00:00:00 2001 From: Joe Richey Date: Tue, 14 Jul 2015 13:50:31 -0700 Subject: [PATCH] Actually denote when we have infinite generators Summary: Before we didn't do anything at all with the ::infinite value for our generators, now all the sources operators and sinks are properly notated. The one signifcant change regarding what is allowed concerns 'cycle' which now (when called with no arguments) always produces an infinite generator. This is fine for all but the weirdest of generators fed into cycle. Reviewed By: @ddrcoder Differential Revision: D2240328 --- folly/gen/Base-inl.h | 1920 ++++++++++++++++++----------------- folly/gen/Core-inl.h | 7 + folly/gen/test/BaseTest.cpp | 38 +- 3 files changed, 1031 insertions(+), 934 deletions(-) diff --git a/folly/gen/Base-inl.h b/folly/gen/Base-inl.h index 7a26fede..fe3a78f4 100644 --- a/folly/gen/Base-inl.h +++ b/folly/gen/Base-inl.h @@ -37,6 +37,9 @@ struct ArgumentReference T&& // int -> int&& >::type> {}; +/** + * Group - The output objects from the GroupBy operator + */ template class Group : public GenImpl> { public: @@ -82,6 +85,9 @@ class Group : public GenImpl> { return true; } + // GroupBy only takes in finite generators, so we only have finite groups + static constexpr bool infinite = false; + private: Key key_; mutable VectorType values_; @@ -89,6 +95,12 @@ class Group : public GenImpl> { namespace detail { +// Classes used for the implementation of Sources, Operators, and Sinks + +/* + ******************************* Sources *************************************** + */ + /* * ReferencedSource - Generate values from an STL-like container using * iterators from .begin() until .end(). Value type defaults to the type of @@ -101,23 +113,22 @@ namespace detail { * string& longestName = from(names) * | maxBy([](string& s) { return s.size() }); */ -template -class ReferencedSource : - public GenImpl> { +template +class ReferencedSource + : public GenImpl> { Container* container_; -public: - explicit ReferencedSource(Container* container) - : container_(container) {} - template + public: + explicit ReferencedSource(Container* container) : container_(container) {} + + template void foreach(Body&& body) const { for (auto& value : *container_) { body(std::forward(value)); } } - template + template bool apply(Handler&& handler) const { for (auto& value : *container_) { if (!handler(std::forward(value))) { @@ -126,6 +137,9 @@ public: } return true; } + + // from takes in a normal stl structure, which are all finite + static constexpr bool infinite = false; }; /** @@ -142,45 +156,44 @@ public: * * Though it is also used for the initializer_list specialization of from(). */ -template -class CopiedSource : - public GenImpl> { - static_assert( - !std::is_reference::value, "StorageType must be decayed"); +template +class CopiedSource + : public GenImpl> { + static_assert(!std::is_reference::value, + "StorageType must be decayed"); + public: // Generator objects are often copied during normal construction as they are // encapsulated by downstream generators. It would be bad if this caused // a copy of the entire container each time, and since we're only exposing a // const reference to the value, it's safe to share it between multiple // generators. - static_assert( - !std::is_reference::value, - "Can't copy into a reference"); + static_assert(!std::is_reference::value, + "Can't copy into a reference"); std::shared_ptr copy_; -public: + + public: typedef Container ContainerType; - template + template explicit CopiedSource(const SourceContainer& container) - : copy_(new Container(begin(container), end(container))) {} + : copy_(new Container(begin(container), end(container))) {} - explicit CopiedSource(Container&& container) : - copy_(new Container(std::move(container))) {} + explicit CopiedSource(Container&& container) + : copy_(new Container(std::move(container))) {} // To enable re-use of cached results. CopiedSource(const CopiedSource& source) - : copy_(source.copy_) {} + : copy_(source.copy_) {} - template + template void foreach(Body&& body) const { for (const auto& value : *copy_) { body(value); } } - template + template bool apply(Handler&& handler) const { // The collection may be reused by others, we can't allow it to be changed. for (const auto& value : *copy_) { @@ -190,6 +203,9 @@ public: } return true; } + + // from takes in a normal stl structure, which are all finite + static constexpr bool infinite = false; }; /** @@ -203,17 +219,16 @@ public: * * Reminder: Be careful not to invalidate iterators when using ranges like this. */ -template +template class RangeSource : public GenImpl::reference, RangeSource> { Range range_; + public: RangeSource() = default; - explicit RangeSource(Range range) - : range_(std::move(range)) - {} + explicit RangeSource(Range range) : range_(std::move(range)) {} - template + template bool apply(Handler&& handler) const { for (auto& value : range_) { if (!handler(value)) { @@ -223,12 +238,15 @@ class RangeSource : public GenImpl::reference, return true; } - template + template void foreach(Body&& body) const { for (auto& value : range_) { body(value); } } + + // folly::Range only supports finite ranges + static constexpr bool infinite = false; }; /** @@ -242,17 +260,19 @@ class RangeSource : public GenImpl::reference, * auto indexes = range(0, 10); * auto endless = seq(0); // 0, 1, 2, 3, ... */ -template +template class Sequence : public GenImpl> { static_assert(!std::is_reference::value && - !std::is_const::value, "Value mustn't be const or ref."); + !std::is_const::value, + "Value mustn't be const or ref."); Value start_; SequenceImpl impl_; -public: + + public: explicit Sequence(Value start, SequenceImpl impl) - : start_(std::move(start)), impl_(std::move(impl)) { } + : start_(std::move(start)), impl_(std::move(impl)) {} - template + template bool apply(Handler&& handler) const { for (Value current = start_; impl_.test(current); impl_.step(current)) { if (!handler(current)) { @@ -262,71 +282,83 @@ public: return true; } - template + template void foreach(Body&& body) const { for (Value current = start_; impl_.test(current); impl_.step(current)) { body(current); } } + + // Let the implementation say if we are infinite or not + static constexpr bool infinite = SequenceImpl::infinite; }; /** * Sequence implementations (range, sequence, infinite, with/without step) **/ -template +template class RangeImpl { Value end_; + public: - explicit RangeImpl(Value end) : end_(std::move(end)) { } + 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 = false; }; -template +template class RangeWithStepImpl { Value end_; Distance step_; + public: explicit RangeWithStepImpl(Value end, Distance step) - : end_(std::move(end)), step_(std::move(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_; } + static constexpr bool infinite = false; }; -template +template class SeqImpl { Value end_; + public: - explicit SeqImpl(Value end) : end_(std::move(end)) { } + explicit SeqImpl(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 = false; }; -template +template class SeqWithStepImpl { Value end_; Distance step_; + public: explicit SeqWithStepImpl(Value end, Distance step) - : end_(std::move(end)), step_(std::move(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_; } + static constexpr bool infinite = false; }; -template +template class InfiniteImpl { public: bool test(const Value& current) const { return true; } void step(Value& current) const { ++current; } + static constexpr bool infinite = true; }; /** * GenratorBuilder - Helper for GENERTATOR macro. **/ -template +template struct GeneratorBuilder { - template> + template > Yield operator+(Source&& source) { return Yield(std::forward(source)); } @@ -336,15 +368,14 @@ struct GeneratorBuilder { * Yield - For producing values from a user-defined generator by way of a * 'yield' function. **/ -template +template class Yield : public GenImpl> { Source source_; + public: - explicit Yield(Source source) - : source_(std::move(source)) { - } + explicit Yield(Source source) : source_(std::move(source)) {} - template + template bool apply(Handler&& handler) const { struct Break {}; auto body = [&](Value value) { @@ -360,13 +391,13 @@ class Yield : public GenImpl> { } } - template + template void foreach(Body&& body) const { source_(std::forward(body)); } }; -template +template class Empty : public GenImpl> { public: template @@ -376,6 +407,9 @@ class Empty : public GenImpl> { template void foreach(Body&&) const {} + + // No values, so finite + static constexpr bool infinite = false; }; template @@ -383,6 +417,7 @@ class SingleReference : public GenImpl> { static_assert(!std::is_reference::value, "SingleReference requires non-ref types"); Value* ptr_; + public: explicit SingleReference(Value& ref) : ptr_(&ref) {} @@ -395,6 +430,9 @@ class SingleReference : public GenImpl> { void foreach(Body&& body) const { body(*ptr_); } + + // One value, so finite + static constexpr bool infinite = false; }; template @@ -402,6 +440,7 @@ class SingleCopy : public GenImpl> { static_assert(!std::is_reference::value, "SingleCopy requires non-ref types"); Value value_; + public: explicit SingleCopy(Value value) : value_(std::forward(value)) {} @@ -414,10 +453,13 @@ class SingleCopy : public GenImpl> { void foreach(Body&& body) const { body(value_); } + + // One value, so finite + static constexpr bool infinite = false; }; /* - * Operators + ***************************** Operators *************************************** */ /** @@ -428,37 +470,34 @@ class SingleCopy : public GenImpl> { * * auto squares = seq(1, 10) | map(square) | asVector; */ -template +template class Map : public Operator> { Predicate pred_; + public: Map() = default; - explicit Map(Predicate pred) - : pred_(std::move(pred)) - { } - - template::type - >::type> - class Generator : - public GenImpl> { + explicit Map(Predicate pred) : pred_(std::move(pred)) {} + + template ::type>::type> + class Generator : public GenImpl> { Source source_; Predicate pred_; - public: + + public: explicit Generator(Source source, const Predicate& pred) - : source_(std::move(source)), pred_(pred) {} + : source_(std::move(source)), pred_(pred) {} - template + template void foreach(Body&& body) const { - source_.foreach([&](Value value) { - body(pred_(std::forward(value))); - }); + source_.foreach( + [&](Value value) { body(pred_(std::forward(value))); }); } - template + template bool apply(Handler&& handler) const { return source_.apply([&](Value value) { return handler(pred_(std::forward(value))); @@ -468,16 +507,16 @@ class Map : public Operator> { static constexpr bool infinite = Source::infinite; }; - template> + template > Gen compose(GenImpl&& source) const { return Gen(std::move(source.self()), pred_); } - template> + template > Gen compose(const GenImpl& source) const { return Gen(source.self(), pred_); } @@ -500,25 +539,24 @@ class Map : public Operator> { * * will give a vector of all the pointers != nullptr. */ -template +template class Filter : public Operator> { Predicate pred_; + public: Filter() = default; - explicit Filter(Predicate pred) - : pred_(std::move(pred)) - { } + explicit Filter(Predicate pred) : pred_(std::move(pred)) {} - template + template class Generator : public GenImpl> { Source source_; Predicate pred_; - public: + + public: explicit Generator(Source source, const Predicate& pred) - : source_(std::move(source)), pred_(pred) {} + : source_(std::move(source)), pred_(pred) {} - template + template void foreach(Body&& body) const { source_.foreach([&](Value value) { if (pred_(std::forward(value))) { @@ -527,7 +565,7 @@ class Filter : public Operator> { }); } - template + template bool apply(Handler&& handler) const { return source_.apply([&](Value value) -> bool { if (pred_(std::forward(value))) { @@ -540,16 +578,16 @@ class Filter : public Operator> { static constexpr bool infinite = Source::infinite; }; - template> + template > Gen compose(GenImpl&& source) const { return Gen(std::move(source.self()), pred_); } - template> + template > Gen compose(const GenImpl& source) const { return Gen(source.self(), pred_); } @@ -564,25 +602,24 @@ class Filter : public Operator> { * | until([](Item& item) { return item.score > 100; }) * | asVector; */ -template +template class Until : public Operator> { Predicate pred_; + public: Until() = default; - explicit Until(Predicate pred) - : pred_(std::move(pred)) - {} + explicit Until(Predicate pred) : pred_(std::move(pred)) {} - template + template class Generator : public GenImpl> { Source source_; Predicate pred_; + public: explicit Generator(Source source, const Predicate& pred) - : source_(std::move(source)), pred_(pred) {} + : source_(std::move(source)), pred_(pred) {} - template + template bool apply(Handler&& handler) const { bool cancelled = false; source_.apply([&](Value value) -> bool { @@ -597,24 +634,24 @@ class Until : public Operator> { }); return !cancelled; } + + // Theoretically an 'until' might stop an infinite + static constexpr bool infinite = false; }; - template> + template > Gen compose(GenImpl&& source) const { return Gen(std::move(source.self()), pred_); } - template> + template > Gen compose(const GenImpl& source) const { return Gen(source.self(), pred_); } - - // Theoretically an 'until' might stop an infinite - static constexpr bool infinite = false; }; /** @@ -628,23 +665,24 @@ class Until : public Operator> { */ class Take : public Operator { size_t count_; + public: - explicit Take(size_t count) - : count_(count) {} + explicit Take(size_t count) : count_(count) {} - template - class Generator : - public GenImpl> { + template + class Generator : public GenImpl> { Source source_; size_t count_; - public: + + public: explicit Generator(Source source, size_t count) - : source_(std::move(source)) , count_(count) {} + : source_(std::move(source)), count_(count) {} - template + template bool apply(Handler&& handler) const { - if (count_ == 0) { return false; } + if (count_ == 0) { + return false; + } size_t n = count_; bool cancelled = false; source_.apply([&](Value value) -> bool { @@ -656,18 +694,21 @@ class Take : public Operator { }); return !cancelled; } + + // take will stop an infinite generator + static constexpr bool infinite = false; }; - template> + template > Gen compose(GenImpl&& source) const { return Gen(std::move(source.self()), count_); } - template> + template > Gen compose(const GenImpl& source) const { return Gen(source.self(), count_); } @@ -695,42 +736,50 @@ class Stride : public Operator { class Generator : public GenImpl> { Source source_; size_t stride_; - public: - Generator(Source source, size_t stride) - : source_(std::move(source)), stride_(stride) {} - - template - bool apply(Handler&& handler) const { - size_t distance = stride_; - return source_.apply([&](Value value)->bool { - if (++distance >= stride_) { - if (!handler(std::forward(value))) { - return false; - } - distance = 0; - } - return true; - }); - } - - template - void foreach(Body&& body) const { - size_t distance = stride_; - source_.foreach([&](Value value) { - if (++distance >= stride_) { - body(std::forward(value)); - distance = 0; - } - }); - } + + public: + explicit Generator(Source source, size_t stride) + : source_(std::move(source)), stride_(stride) {} + + template + bool apply(Handler&& handler) const { + size_t distance = stride_; + return source_.apply([&](Value value) -> bool { + if (++distance >= stride_) { + if (!handler(std::forward(value))) { + return false; + } + distance = 0; + } + return true; + }); + } + + template + void foreach(Body&& body) const { + size_t distance = stride_; + source_.foreach([&](Value value) { + if (++distance >= stride_) { + body(std::forward(value)); + distance = 0; + } + }); + } + + // Taking every Nth of an infinite list is still infinte + static constexpr bool infinite = Source::infinite; }; - template > + template > Gen compose(GenImpl&& source) const { return Gen(std::move(source.self()), stride_); } - template > + template > Gen compose(const GenImpl& source) const { return Gen(source.self(), stride_); } @@ -740,21 +789,22 @@ class Stride : public Operator { * Sample - For taking a random sample of N elements from a sequence * (without replacement). */ -template +template class Sample : public Operator> { size_t count_; Random rng_; + public: explicit Sample(size_t count, Random rng) - : count_(count), rng_(std::move(rng)) {} - - template::type> - class Generator : - public GenImpl> { + : count_(count), rng_(std::move(rng)) {} + + template ::type> + class Generator + : public GenImpl> { static_assert(!Source::infinite, "Cannot sample infinite source!"); // It's too easy to bite ourselves if random generator is only 16-bit static_assert(Random::max() >= std::numeric_limits::max() - 1, @@ -762,53 +812,59 @@ class Sample : public Operator> { Source source_; size_t count_; mutable Rand rng_; - public: + + public: explicit Generator(Source source, size_t count, Random rng) - : source_(std::move(source)) , count_(count), rng_(std::move(rng)) {} + : source_(std::move(source)), count_(count), rng_(std::move(rng)) {} - template + template bool apply(Handler&& handler) const { - if (count_ == 0) { return false; } + if (count_ == 0) { + return false; + } std::vector v; v.reserve(count_); // use reservoir sampling to give each source value an equal chance // of appearing in our output. size_t n = 1; source_.foreach([&](Value value) -> void { - if (v.size() < count_) { - v.push_back(std::forward(value)); - } else { - // alternatively, we could create a std::uniform_int_distribution - // instead of using modulus, but benchmarks show this has - // substantial overhead. - size_t index = rng_() % n; - if (index < v.size()) { - v[index] = std::forward(value); - } + if (v.size() < count_) { + v.push_back(std::forward(value)); + } else { + // alternatively, we could create a std::uniform_int_distribution + // instead of using modulus, but benchmarks show this has + // substantial overhead. + size_t index = rng_() % n; + if (index < v.size()) { + v[index] = std::forward(value); } - ++n; - }); + } + ++n; + }); // output is unsorted! - for (auto& val: v) { + for (auto& val : v) { if (!handler(std::move(val))) { return false; } } return true; } + + // Only takes N elements, so finite + static constexpr bool infinite = false; }; - template> + template > Gen compose(GenImpl&& source) const { return Gen(std::move(source.self()), count_, rng_); } - template> + template > Gen compose(const GenImpl& source) const { return Gen(source.self(), count_, rng_); } @@ -825,21 +881,20 @@ class Sample : public Operator> { */ class Skip : public Operator { size_t count_; + public: - explicit Skip(size_t count) - : count_(count) {} + explicit Skip(size_t count) : count_(count) {} - template - class Generator : - public GenImpl> { + template + class Generator : public GenImpl> { Source source_; size_t count_; + public: explicit Generator(Source source, size_t count) - : source_(std::move(source)) , count_(count) {} + : source_(std::move(source)), count_(count) {} - template + template void foreach(Body&& body) const { if (count_ == 0) { source_.foreach(body); @@ -847,42 +902,43 @@ class Skip : public Operator { } size_t n = 0; source_.foreach([&](Value value) { - if (n < count_) { - ++n; - } else { - body(std::forward(value)); - } - }); + if (n < count_) { + ++n; + } else { + body(std::forward(value)); + } + }); } - template + template bool apply(Handler&& handler) const { if (count_ == 0) { return source_.apply(std::forward(handler)); } size_t n = 0; return source_.apply([&](Value value) -> bool { - if (n < count_) { - ++n; - return true; - } - return handler(std::forward(value)); - }); + if (n < count_) { + ++n; + return true; + } + return handler(std::forward(value)); + }); } + // Skipping N items of an infinite source is still infinite static constexpr bool infinite = Source::infinite; }; - template> + template > Gen compose(GenImpl&& source) const { return Gen(std::move(source.self()), count_); } - template> + template > Gen compose(const GenImpl& source) const { return Gen(source.self(), count_); } @@ -901,30 +957,26 @@ class Skip : public Operator { * }) * | take(10); */ -template +template class Order : public Operator> { Selector selector_; Comparer comparer_; + public: Order() = default; - explicit Order(Selector selector) - : selector_(std::move(selector)) - {} - - Order(Selector selector, - Comparer comparer) - : selector_(std::move(selector)) - , comparer_(std::move(comparer)) - {} - - template::type, - class Result = typename std::result_of::type> - class Generator : - public GenImpl> { + explicit Order(Selector selector) : selector_(std::move(selector)) {} + + Order(Selector selector, Comparer comparer) + : selector_(std::move(selector)), comparer_(std::move(comparer)) {} + + template ::type, + class Result = typename std::result_of::type> + class Generator + : public GenImpl> { static_assert(!Source::infinite, "Cannot sort infinite source!"); Source source_; Selector selector_; @@ -940,13 +992,12 @@ class Order : public Operator> { std::sort(vals.begin(), vals.end(), comparer); return std::move(vals); } + public: - Generator(Source source, - Selector selector, - Comparer comparer) - : source_(std::move(source)), - selector_(std::move(selector)), - comparer_(std::move(comparer)) {} + Generator(Source source, Selector selector, Comparer comparer) + : source_(std::move(source)), + selector_(std::move(selector)), + comparer_(std::move(comparer)) {} VectorType operator|(const Collect&) const { return asVector(); @@ -956,14 +1007,14 @@ class Order : public Operator> { return asVector(); } - template + template void foreach(Body&& body) const { for (auto& value : asVector()) { body(std::move(value)); } } - template + template bool apply(Handler&& handler) const { auto comparer = [&](const StorageType& a, const StorageType& b) { // swapped for minHeap @@ -980,18 +1031,21 @@ class Order : public Operator> { } return true; } + + // Can only be run on and produce finite generators + static constexpr bool infinite = false; }; - template> + template > Gen compose(GenImpl&& source) const { return Gen(std::move(source.self()), selector_, comparer_); } - template> + template > Gen compose(const GenImpl& source) const { return Gen(source.self(), selector_, comparer_); } @@ -1057,14 +1111,21 @@ class GroupBy : public Operator> { } return true; } + + // Can only be run on and produce finite generators + static constexpr bool infinite = false; }; - template > + template > Gen compose(GenImpl&& source) const { return Gen(std::move(source.self()), selector_); } - template > + template > Gen compose(const GenImpl& source) const { return Gen(source.self(), selector_); } @@ -1079,17 +1140,17 @@ class GroupBy : public Operator> { * auto c = from(vector) | assert_type() | sum; * */ -template +template class TypeAssertion : public Operator> { public: - template + template const Source& compose(const GenImpl& source) const { static_assert(std::is_same::value, "assert_type() check failed"); return source.self(); } - template + template Source&& compose(GenImpl&& source) const { static_assert(std::is_same::value, "assert_type() check failed"); @@ -1109,18 +1170,16 @@ class TypeAssertion : public Operator> { * }) * | take(10); */ -template +template class Distinct : public Operator> { Selector selector_; + public: Distinct() = default; - explicit Distinct(Selector selector) - : selector_(std::move(selector)) - {} + explicit Distinct(Selector selector) : selector_(std::move(selector)) {} - template + template class Generator : public GenImpl> { Source source_; Selector selector_; @@ -1135,12 +1194,10 @@ class Distinct : public Operator> { typedef typename std::decay::type KeyStorageType; public: - Generator(Source source, - Selector selector) - : source_(std::move(source)), - selector_(std::move(selector)) {} + Generator(Source source, Selector selector) + : source_(std::move(source)), selector_(std::move(selector)) {} - template + template void foreach(Body&& body) const { std::unordered_set keysSeen; source_.foreach([&](Value value) { @@ -1150,7 +1207,7 @@ class Distinct : public Operator> { }); } - template + template bool apply(Handler&& handler) const { std::unordered_set keysSeen; return source_.apply([&](Value value) -> bool { @@ -1160,18 +1217,22 @@ class Distinct : public Operator> { return true; }); } + + // While running distinct on an infinite sequence might produce a + // conceptually finite sequence, it will take infinite time + static constexpr bool infinite = Source::infinite; }; - template> + template > Gen compose(GenImpl&& source) const { return Gen(std::move(source.self()), selector_); } - template> + template > Gen compose(const GenImpl& source) const { return Gen(source.self(), selector_); } @@ -1181,16 +1242,16 @@ class Distinct : public Operator> { * Composer - Helper class for adapting pipelines into functors. Primarily used * for 'mapOp'. */ -template +template class Composer { Operators op_; + public: - explicit Composer(Operators op) - : op_(std::move(op)) {} + explicit Composer(Operators op) : op_(std::move(op)) {} - template() - .compose(std::declval()))> + template ().compose(std::declval()))> Ret operator()(Source&& source) const { return op_.compose(std::forward(source)); } @@ -1211,42 +1272,42 @@ class Composer { */ class Batch : public Operator { size_t batchSize_; + public: - explicit Batch(size_t batchSize) - : batchSize_(batchSize) { + explicit Batch(size_t batchSize) : batchSize_(batchSize) { if (batchSize_ == 0) { throw std::invalid_argument("Batch size must be non-zero!"); } } - template::type, - class VectorType = std::vector> - class Generator : - public GenImpl> { + template ::type, + class VectorType = std::vector> + class Generator + : public GenImpl> { Source source_; size_t batchSize_; - public: + + public: explicit Generator(Source source, size_t batchSize) - : source_(std::move(source)) - , batchSize_(batchSize) {} + : source_(std::move(source)), batchSize_(batchSize) {} - template + template bool apply(Handler&& handler) const { VectorType batch_; batch_.reserve(batchSize_); bool shouldContinue = source_.apply([&](Value value) -> bool { - batch_.push_back(std::forward(value)); - if (batch_.size() == batchSize_) { - bool needMore = handler(batch_); - batch_.clear(); - return needMore; - } - // Always need more if the handler is not called. - return true; - }); + batch_.push_back(std::forward(value)); + if (batch_.size() == batchSize_) { + bool needMore = handler(batch_); + batch_.clear(); + return needMore; + } + // Always need more if the handler is not called. + return true; + }); // Flush everything, if and only if `handler` hasn't returned false. if (shouldContinue && !batch_.empty()) { shouldContinue = handler(batch_); @@ -1255,765 +1316,780 @@ class Batch : public Operator { return shouldContinue; } + // Taking n-tuples of an infinite source is still infinite static constexpr bool infinite = Source::infinite; }; - template> + template > Gen compose(GenImpl&& source) const { return Gen(std::move(source.self()), batchSize_); } - template> + template > Gen compose(const GenImpl& source) const { return Gen(source.self(), batchSize_); } }; -/* - * Sinks - */ /** - * FoldLeft - Left-associative functional fold. For producing an aggregate value - * from a seed and a folder function. Useful for custom aggregators on a - * sequence. + * Concat - For flattening generators of generators. * - * This type is primarily used through the 'foldl' helper method, like: + * This type is usually used through the 'concat' static value, like: * - * double movingAverage = from(values) - * | foldl(0.0, [](double avg, double sample) { - * return sample * 0.1 + avg * 0.9; - * }); + * auto edges = + * from(nodes) + * | map([](Node& x) { + * return from(x.neighbors) + * | map([&](Node& y) { + * return Edge(x, y); + * }); + * }) + * | concat + * | as(); */ -template -class FoldLeft : public Operator> { - Seed seed_; - Fold fold_; +class Concat : public Operator { public: - FoldLeft() = default; - FoldLeft(Seed seed, - Fold fold) - : seed_(std::move(seed)) - , fold_(std::move(fold)) - {} - - template - Seed compose(const GenImpl& source) const { - static_assert(!Source::infinite, "Cannot foldl infinite source"); - Seed accum = seed_; - source | [&](Value v) { - accum = fold_(std::move(accum), std::forward(v)); - }; - return accum; + Concat() = default; + + template ::type::ValueType> + class Generator + : public GenImpl> { + Source source_; + + public: + explicit Generator(Source source) : source_(std::move(source)) {} + + template + bool apply(Handler&& handler) const { + return source_.apply([&](Inner inner) -> bool { + return inner.apply(std::forward(handler)); + }); + } + + template + void foreach(Body&& body) const { + source_.foreach([&](Inner inner) { + inner.foreach(std::forward(body)); + }); + } + + // Resulting concatination is only finite if both Source and Inner are also + // finite. In one sence, if dosn't make sence to call concat when the Inner + // generator is infinite (you could just call first), so we could also just + // static_assert if the inner is infinite. Taking the less restrictive + // approch for now. + static constexpr bool infinite = + Source::infinite || std::decay::type::infinite; + }; + + template > + Gen compose(GenImpl&& source) const { + return Gen(std::move(source.self())); + } + + template > + Gen compose(const GenImpl& source) const { + return Gen(source.self()); } }; /** - * First - For finding the first value in a sequence. + * RangeConcat - For flattening generators of iterables. * - * This type is primarily used through the 'first' static value, like: + * This type is usually used through the 'rconcat' static value, like: * - * int firstThreeDigitPrime = seq(100) | filter(isPrime) | first; + * map> adjacency; + * auto sinks = + * from(adjacency) + * | get<1>() + * | rconcat() + * | as(); */ -class First : public Operator { +class RangeConcat : public Operator { public: - First() = default; - - template::type> - StorageType compose(const GenImpl& source) const { - Optional accum; - source | [&](Value v) -> bool { - accum = std::forward(v); - return false; - }; - if (!accum.hasValue()) { - throw EmptySequence(); - } - return std::move(accum.value()); - } -}; + RangeConcat() = default; -/** - * IsEmpty - a helper class for isEmpty and notEmpty - * - * Essentially returns 'result' if the source is empty. Note that this cannot be - * called on an infinite source, because then there is only one possible return - * value. - */ -template -class IsEmpty : public Operator> { - public: - IsEmpty() = default; + template ::RefType> + class Generator + : public GenImpl> { + Source source_; - template - bool compose(const GenImpl& source) const { - static_assert(!Source::infinite, - "Cannot call 'all', 'any', 'isEmpty', or 'notEmpty' on " - "infinite source. 'all' and 'isEmpty' will either return " - "false or hang. 'any' or 'notEmpty' will either return true " - "or hang."); - bool ans = emptyResult; - source | [&](Value v) -> bool { - ans = !emptyResult; - return false; - }; - return ans; - } -}; + public: + explicit Generator(Source source) : source_(std::move(source)) {} -/** - * Reduce - Functional reduce, for recursively combining values from a source - * using a reducer function until there is only one item left. Useful for - * combining values when an empty sequence doesn't make sense. - * - * This type is primarily used through the 'reduce' helper method, like: - * - * sring longest = from(names) - * | reduce([](string&& best, string& current) { - * return best.size() >= current.size() ? best : current; - * }); - */ -template -class Reduce : public Operator> { - Reducer reducer_; - public: - Reduce() = default; - explicit Reduce(Reducer reducer) - : reducer_(std::move(reducer)) - {} + template + void foreach(Body&& body) const { + source_.foreach([&](Range range) { + for (auto& value : range) { + body(value); + } + }); + } - template::type> - StorageType compose(const GenImpl& source) const { - Optional accum; - source | [&](Value v) { - if (accum.hasValue()) { - accum = reducer_(std::move(accum.value()), std::forward(v)); - } else { - accum = std::forward(v); - } - }; - if (!accum.hasValue()) { - throw EmptySequence(); + template + bool apply(Handler&& handler) const { + return source_.apply([&](Range range) -> bool { + for (auto& value : range) { + if (!handler(value)) { + return false; + } + } + return true; + }); } - return accum.value(); - } -}; -/** - * Count - for simply counting the items in a collection. - * - * This type is usually used through its singleton, 'count': - * - * auto shortPrimes = seq(1, 100) | filter(isPrime) | count; - */ -class Count : public Operator { - public: - Count() = default; + // This is similar to concat, except that the inner iterables all are finite + // so the only thing that matters is that the source is infinite. + static constexpr bool infinite = Source::infinite; + }; - template - size_t compose(const GenImpl& source) const { - static_assert(!Source::infinite, "Cannot count infinite source"); - return foldl(size_t(0), - [](size_t accum, Value v) { - return accum + 1; - }).compose(source); + template > + Gen compose(GenImpl&& source) const { + return Gen(std::move(source.self())); } -}; -/** - * Sum - For simply summing up all the values from a source. - * - * This type is usually used through its singleton, 'sum': - * - * auto gaussSum = seq(1, 100) | sum; - */ -class Sum : public Operator { - public: - Sum() = default; - - template::type> - StorageType compose(const GenImpl& source) const { - static_assert(!Source::infinite, "Cannot sum infinite source"); - return foldl(StorageType(0), - [](StorageType&& accum, Value v) { - return std::move(accum) + std::forward(v); - }).compose(source); + template > + Gen compose(const GenImpl& source) const { + return Gen(source.self()); } }; /** - * Contains - For testing whether a value matching the given value is contained - * in a sequence. - * - * This type should be used through the 'contains' helper method, like: + * GuardImpl - For handling exceptions from downstream computation. Requires the + * type of exception to catch, and handler function to invoke in the event of + * the exception. Note that the handler may: + * 1) return true to continue processing the sequence + * 2) return false to end the sequence immediately + * 3) throw, to pass the exception to the next catch + * The handler must match the signature 'bool(Exception&, Value)'. * - * bool contained = seq(1, 10) | map(square) | contains(49); - */ -template -class Contains : public Operator> { - Needle needle_; - public: - explicit Contains(Needle needle) - : needle_(std::move(needle)) - {} - - template::type> - bool compose(const GenImpl& source) const { - static_assert(!Source::infinite, - "Calling contains on an infinite source might cause " - "an infinite loop."); - return !(source | [this](Value value) { - return !(needle_ == std::forward(value)); - }); - } -}; - -/** - * Min - For a value which minimizes a key, where the key is determined by a - * given selector, and compared by given comparer. + * This type is used through the `guard` helper, like so: * - * This type is usually used through the singletone 'min' or through the helper - * functions 'minBy' and 'maxBy'. + * auto indexes + * = byLine(STDIN_FILENO) + * | guard([](std::runtime_error& e, + * StringPiece sp) { + * LOG(ERROR) << sp << ": " << e.str(); + * return true; // continue processing subsequent lines + * }) + * | eachTo() + * | as(); * - * auto oldest = from(people) - * | minBy([](Person& p) { - * return p.dateOfBirth; - * }); - */ -template -class Min : public Operator> { - Selector selector_; - Comparer comparer_; - public: - Min() = default; - - explicit Min(Selector selector) - : selector_(std::move(selector)) - {} - - Min(Selector selector, - Comparer comparer) - : selector_(std::move(selector)) - , comparer_(std::move(comparer)) - {} - - template::type, - class Key = typename std::decay< - typename std::result_of::type - >::type> - StorageType compose(const GenImpl& source) const { - Optional min; - Optional minKey; - source | [&](Value v) { - Key key = selector_(std::forward(v)); - if (!minKey.hasValue() || comparer_(key, minKey.value())) { - minKey = key; - min = std::forward(v); - } - }; - if (!min.hasValue()) { - throw EmptySequence(); - } - return min.value(); - } -}; + * TODO(tjackson): Rename this back to Guard. + **/ +template +class GuardImpl : public Operator> { + ErrorHandler handler_; -/** - * Append - For collecting values from a source into a given output container - * by appending. - * - * This type is usually used through the helper function 'appendTo', like: - * - * vector ids; - * from(results) | map([](Person& p) { return p.id }) - * | appendTo(ids); - */ -template -class Append : public Operator> { - Collection* collection_; public: - explicit Append(Collection* collection) - : collection_(collection) - {} + explicit GuardImpl(ErrorHandler handler) : handler_(std::move(handler)) {} - template - Collection& compose(const GenImpl& source) const { - source | [&](Value v) { - collection_->insert(collection_->end(), std::forward(v)); - }; - return *collection_; - } -}; + template + class Generator : public GenImpl> { + Source source_; + ErrorHandler handler_; -/** - * Collect - For collecting values from a source in a collection of the desired - * type. - * - * This type is usually used through the helper function 'as', like: - * - * std::string upper = from(stringPiece) - * | map(&toupper) - * | as(); - */ -template -class Collect : public Operator> { - public: - Collect() = default; + public: + explicit Generator(Source source, ErrorHandler handler) + : source_(std::move(source)), handler_(std::move(handler)) {} - template::type> - Collection compose(const GenImpl& source) const { - Collection collection; - source | [&](Value v) { - collection.insert(collection.end(), std::forward(v)); - }; - return collection; - } -}; + template + bool apply(Handler&& handler) const { + return source_.apply([&](Value value) -> bool { + try { + handler(std::forward(value)); + return true; + } catch (Exception& e) { + return handler_(e, std::forward(value)); + } + }); + } + // Just passes value though, length unaffected + static constexpr bool infinite = Source::infinite; + }; -/** - * CollectTemplate - For collecting values from a source in a collection - * constructed using the specified template type. Given the type of values - * produced by the given generator, the collection type will be: - * Container> - * - * The allocator defaults to std::allocator, so this may be used for the STL - * containers by simply using operators like 'as', 'as', - * 'as'. 'as', here is the helper method which is the usual means of - * consturcting this operator. - * - * Example: - * - * set uniqueNames = from(names) | as(); - */ -template class Container, - template class Allocator> -class CollectTemplate : public Operator> { - public: - CollectTemplate() = default; + template > + Gen compose(GenImpl&& source) const { + return Gen(std::move(source.self()), handler_); + } - template::type, - class Collection = Container>> - Collection compose(const GenImpl& source) const { - Collection collection; - source | [&](Value v) { - collection.insert(collection.end(), std::forward(v)); - }; - return collection; + template > + Gen compose(const GenImpl& source) const { + return Gen(source.self(), handler_); } }; /** - * Concat - For flattening generators of generators. + * Dereference - For dereferencing a sequence of pointers while filtering out + * null pointers. * - * This type is usually used through the 'concat' static value, like: + * This type is usually used through the 'dereference' static value, like: * - * auto edges = - * from(nodes) - * | map([](Node& x) { - * return from(x.neighbors) - * | map([&](Node& y) { - * return Edge(x, y); - * }); - * }) - * | concat - * | as(); + * auto refs = from(ptrs) | dereference; */ -class Concat : public Operator { +class Dereference : public Operator { public: - Concat() = default; + Dereference() = default; - template::type::ValueType> - class Generator : - public GenImpl> { + template ())> + class Generator : public GenImpl> { Source source_; + public: - explicit Generator(Source source) - : source_(std::move(source)) {} + explicit Generator(Source source) : source_(std::move(source)) {} - template - bool apply(Handler&& handler) const { - return source_.apply([&](Inner inner) -> bool { - return inner.apply(std::forward(handler)); - }); + template + void foreach(Body&& body) const { + source_.foreach([&](Value value) { + if (value) { + return body(*value); + } + }); } - template - void foreach(Body&& body) const { - source_.foreach([&](Inner inner) { - inner.foreach(std::forward(body)); - }); + template + bool apply(Handler&& handler) const { + return source_.apply([&](Value value) -> bool { + if (value) { + return handler(*value); + } + return true; + }); } + // Just passes value though, length unaffected static constexpr bool infinite = Source::infinite; }; - template> + template > Gen compose(GenImpl&& source) const { return Gen(std::move(source.self())); } - template> + template > Gen compose(const GenImpl& source) const { return Gen(source.self()); } }; /** - * RangeConcat - For flattening generators of iterables. + * Indirect - For producing a sequence of the addresses of the values in the + * input. * - * This type is usually used through the 'rconcat' static value, like: + * This type is usually used through the 'indirect' static value, like: * - * map> adjacency; - * auto sinks = - * from(adjacency) - * | get<1>() - * | rconcat() - * | as(); + * auto ptrs = from(refs) | indirect; */ -class RangeConcat : public Operator { +class Indirect : public Operator { public: - RangeConcat() = default; + Indirect() = default; - template::RefType> - class Generator - : public GenImpl> { + template ::type*> + class Generator : public GenImpl> { Source source_; + static_assert(!std::is_rvalue_reference::value, + "Cannot use indirect on an rvalue"); + public: - explicit Generator(Source source) - : source_(std::move(source)) {} + explicit Generator(Source source) : source_(std::move(source)) {} - template + template void foreach(Body&& body) const { - source_.foreach([&](Range range) { - for (auto& value : range) { - body(value); - } - }); + source_.foreach([&](Value value) { + return body(&value); + }); } - template + template bool apply(Handler&& handler) const { - return source_.apply([&](Range range) -> bool { - for (auto& value : range) { - if (!handler(value)) { - return false; - } - } - return true; - }); + return source_.apply([&](Value value) -> bool { + return handler(&value); + }); } + + // Just passes value though, length unaffected + static constexpr bool infinite = Source::infinite; }; - template> + template > Gen compose(GenImpl&& source) const { return Gen(std::move(source.self())); } - template> + template > Gen compose(const GenImpl& source) const { return Gen(source.self()); } }; - /** - * GuardImpl - For handling exceptions from downstream computation. Requires the - * type of exception to catch, and handler function to invoke in the event of - * the exception. Note that the handler may: - * 1) return true to continue processing the sequence - * 2) return false to end the sequence immediately - * 3) throw, to pass the exception to the next catch - * The handler must match the signature 'bool(Exception&, Value)'. + * Cycle - For repeating a sequence forever. * - * This type is used through the `guard` helper, like so: + * This type is usually used through the 'cycle' static value, like: * - * auto indexes - * = byLine(STDIN_FILENO) - * | guard([](std::runtime_error& e, - * StringPiece sp) { - * LOG(ERROR) << sp << ": " << e.str(); - * return true; // continue processing subsequent lines - * }) - * | eachTo() - * | as(); + * auto tests + * = from(samples) + * | cycle + * | take(100); * - * TODO(tjackson): Rename this back to Guard. - **/ -template -class GuardImpl : public Operator> { - ErrorHandler handler_; + * or in the finite case: + * + * auto thrice = g | cycle(3); + */ +template +class Cycle : public Operator> { + off_t limit_; // not used if forever == true public: - explicit GuardImpl(ErrorHandler handler) : handler_(std::move(handler)) {} + Cycle() = default; + + explicit Cycle(off_t limit) : limit_(limit) { + static_assert( + !forever, + "Cycle limit consturctor should not be used when forever == true."); + } - template + template class Generator : public GenImpl> { Source source_; - ErrorHandler handler_; - public: - explicit Generator(Source source, - ErrorHandler handler) - : source_(std::move(source)), - handler_(std::move(handler)) {} + off_t limit_; + + public: + explicit Generator(Source source, off_t limit) + : source_(std::move(source)), limit_(limit) {} - template + template bool apply(Handler&& handler) const { - return source_.apply([&](Value value) -> bool { - try { - handler(std::forward(value)); - return true; - } catch (Exception& e) { - return handler_(e, std::forward(value)); + bool cont; + auto handler2 = [&](Value value) { + cont = handler(std::forward(value)); + return cont; + }; + // Becomes an infinte loop if forever == true + for (off_t count = 0; (forever || count != limit_); ++count) { + cont = false; + source_.apply(handler2); + if (!cont) { + return false; } - }); + } + return true; } - static constexpr bool infinite = Source::infinite; + // This is the hardest one to infer. If we are simply doing a finite cycle, + // then (gen | cycle(n)) is infinite if and only if gen is infinite. + // However, if we are doing an infinite cycle, (gen | cycle) is infinite + // unless gen is empty. However, we will always mark (gen | cycle) as + // infinite, because patterns such as (gen | cycle | count) can either take + // on exactly one value, or infinite loop. + static constexpr bool infinite = forever || Source::infinite; }; - template> + template > Gen compose(GenImpl&& source) const { - return Gen(std::move(source.self()), handler_); + return Gen(std::move(source.self()), limit_); } - template> + template > Gen compose(const GenImpl& source) const { - return Gen(source.self(), handler_); + return Gen(source.self(), limit_); + } + + /** + * Convenience function for finite cycles used like: + * + * auto tripled = gen | cycle(3); + */ + Cycle operator()(off_t limit) const { return Cycle(limit); } +}; + +/* + ******************************* Sinks ***************************************** + */ + +/** + * FoldLeft - Left-associative functional fold. For producing an aggregate value + * from a seed and a folder function. Useful for custom aggregators on a + * sequence. + * + * This type is primarily used through the 'foldl' helper method, like: + * + * double movingAverage = from(values) + * | foldl(0.0, [](double avg, double sample) { + * return sample * 0.1 + avg * 0.9; + * }); + */ +template +class FoldLeft : public Operator> { + Seed seed_; + Fold fold_; + + public: + FoldLeft() = default; + FoldLeft(Seed seed, Fold fold) + : seed_(std::move(seed)), fold_(std::move(fold)) {} + + template + Seed compose(const GenImpl& source) const { + static_assert(!Source::infinite, "Cannot foldl infinite source"); + Seed accum = seed_; + source | [&](Value v) { + accum = fold_(std::move(accum), std::forward(v)); + }; + return accum; + } +}; + +/** + * First - For finding the first value in a sequence. + * + * This type is primarily used through the 'first' static value, like: + * + * int firstThreeDigitPrime = seq(100) | filter(isPrime) | first; + */ +class First : public Operator { + public: + First() = default; + + template ::type> + StorageType compose(const GenImpl& source) const { + Optional accum; + source | [&](Value v) -> bool { + accum = std::forward(v); + return false; + }; + if (!accum.hasValue()) { + throw EmptySequence(); + } + return std::move(accum.value()); + } +}; + +/** + * IsEmpty - a helper class for isEmpty and notEmpty + * + * Essentially returns 'result' if the source is empty. Note that this cannot be + * called on an infinite source, because then there is only one possible return + * value. + * + * + * Used primarily through 'isEmpty' and 'notEmpty' static values + * + * bool hasPrimes = g | filter(prime) | notEmpty; + * bool lacksEvens = g | filter(even) | isEmpty; + * + * Also used in the implementation of 'any' and 'all' + */ +template +class IsEmpty : public Operator> { + public: + IsEmpty() = default; + + template + bool compose(const GenImpl& source) const { + static_assert(!Source::infinite, + "Cannot call 'all', 'any', 'isEmpty', or 'notEmpty' on " + "infinite source. 'all' and 'isEmpty' will either return " + "false or hang. 'any' or 'notEmpty' will either return true " + "or hang."); + bool ans = emptyResult; + source | [&](Value v) -> bool { + ans = !emptyResult; + return false; + }; + return ans; + } +}; + +/** + * Reduce - Functional reduce, for recursively combining values from a source + * using a reducer function until there is only one item left. Useful for + * combining values when an empty sequence doesn't make sense. + * + * This type is primarily used through the 'reduce' helper method, like: + * + * sring longest = from(names) + * | reduce([](string&& best, string& current) { + * return best.size() >= current.size() ? best : current; + * }); + */ +template +class Reduce : public Operator> { + Reducer reducer_; + + public: + Reduce() = default; + explicit Reduce(Reducer reducer) : reducer_(std::move(reducer)) {} + + template ::type> + StorageType compose(const GenImpl& source) const { + static_assert(!Source::infinite, "Cannot reduce infinite source"); + Optional accum; + source | [&](Value v) { + if (accum.hasValue()) { + accum = reducer_(std::move(accum.value()), std::forward(v)); + } else { + accum = std::forward(v); + } + }; + if (!accum.hasValue()) { + throw EmptySequence(); + } + return accum.value(); + } +}; + +/** + * Count - for simply counting the items in a collection. + * + * This type is usually used through its singleton, 'count': + * + * auto shortPrimes = seq(1, 100) | filter(isPrime) | count; + */ +class Count : public Operator { + public: + Count() = default; + + template + size_t compose(const GenImpl& source) const { + static_assert(!Source::infinite, "Cannot count infinite source"); + return foldl(size_t(0), + [](size_t accum, Value v) { + return accum + 1; + }).compose(source); } }; /** - * Cycle - For repeating a sequence forever. - * - * This type is usually used through the 'cycle' static value, like: - * - * auto tests - * = from(samples) - * | cycle - * | take(100); + * Sum - For simply summing up all the values from a source. * - * or in the finite case: + * This type is usually used through its singleton, 'sum': * - * auto thrice = g | cycle(3); + * auto gaussSum = seq(1, 100) | sum; */ -template -class Cycle : public Operator> { - off_t limit_; // not used if forever == true +class Sum : public Operator { public: - Cycle() = default; - - explicit Cycle(off_t limit) - : limit_(limit) { - static_assert( - !forever, - "Cycle limit consturctor should not be used when forever == true."); - } - - template - class Generator : public GenImpl> { - Source source_; - off_t limit_; - public: - explicit Generator(Source source, off_t limit) - : source_(std::move(source)) - , limit_(limit) {} - - template - bool apply(Handler&& handler) const { - bool cont; - auto handler2 = [&](Value value) { - cont = handler(std::forward(value)); - return cont; - }; - // Becomes an infinte loop if forever == true - for (off_t count = 0; (forever || count != limit_); ++count) { - cont = false; - source_.apply(handler2); - if (!cont) { - return false; - } - } - return true; - } - - // not actually infinite, since an empty generator will end the cycles. - static constexpr bool infinite = Source::infinite; - }; + Sum() = default; - template> - Gen compose(GenImpl&& source) const { - return Gen(std::move(source.self()), limit_); + template ::type> + StorageType compose(const GenImpl& source) const { + static_assert(!Source::infinite, "Cannot sum infinite source"); + return foldl(StorageType(0), + [](StorageType&& accum, Value v) { + return std::move(accum) + std::forward(v); + }).compose(source); } +}; - template> - Gen compose(const GenImpl& source) const { - return Gen(source.self(), limit_); - } +/** + * Contains - For testing whether a value matching the given value is contained + * in a sequence. + * + * This type should be used through the 'contains' helper method, like: + * + * bool contained = seq(1, 10) | map(square) | contains(49); + */ +template +class Contains : public Operator> { + Needle needle_; - /** - * Convenience function for finite cycles used like: - * - * auto tripled = gen | cycle(3); - */ - Cycle operator()(off_t limit) const { - return Cycle(limit); + public: + explicit Contains(Needle needle) : needle_(std::move(needle)) {} + + template ::type> + bool compose(const GenImpl& source) const { + static_assert(!Source::infinite, + "Calling contains on an infinite source might cause " + "an infinite loop."); + return !(source | [this](Value value) { + return !(needle_ == std::forward(value)); + }); } }; /** - * Dereference - For dereferencing a sequence of pointers while filtering out - * null pointers. + * Min - For a value which minimizes a key, where the key is determined by a + * given selector, and compared by given comparer. * - * This type is usually used through the 'dereference' static value, like: + * This type is usually used through the singletone 'min' or through the helper + * functions 'minBy' and 'maxBy'. * - * auto refs = from(ptrs) | dereference; + * auto oldest = from(people) + * | minBy([](Person& p) { + * return p.dateOfBirth; + * }); */ -class Dereference : public Operator { +template +class Min : public Operator> { + Selector selector_; + Comparer comparer_; + public: - Dereference() = default; + Min() = default; - template())> - class Generator : public GenImpl> { - Source source_; - public: - explicit Generator(Source source) - : source_(std::move(source)) {} + explicit Min(Selector selector) : selector_(std::move(selector)) {} - template - void foreach(Body&& body) const { - source_.foreach([&](Value value) { - if (value) { - return body(*value); - } - }); - } + Min(Selector selector, Comparer comparer) + : selector_(std::move(selector)), comparer_(std::move(comparer)) {} - template - bool apply(Handler&& handler) const { - return source_.apply([&](Value value) -> bool { - if (value) { - return handler(*value); - } - return true; - }); + template ::type, + class Key = typename std::decay< + typename std::result_of::type>::type> + StorageType compose(const GenImpl& source) const { + static_assert(!Source::infinite, + "Calling min or max on an infinite source will cause " + "an infinite loop."); + Optional min; + Optional minKey; + source | [&](Value v) { + Key key = selector_(std::forward(v)); + if (!minKey.hasValue() || comparer_(key, minKey.value())) { + minKey = key; + min = std::forward(v); + } + }; + if (!min.hasValue()) { + throw EmptySequence(); } + return min.value(); + } +}; - // not actually infinite, since an empty generator will end the cycles. - static constexpr bool infinite = Source::infinite; - }; +/** + * Append - For collecting values from a source into a given output container + * by appending. + * + * This type is usually used through the helper function 'appendTo', like: + * + * vector ids; + * from(results) | map([](Person& p) { return p.id }) + * | appendTo(ids); + */ +template +class Append : public Operator> { + Collection* collection_; - template> - Gen compose(GenImpl&& source) const { - return Gen(std::move(source.self())); - } + public: + explicit Append(Collection* collection) : collection_(collection) {} - template> - Gen compose(const GenImpl& source) const { - return Gen(source.self()); + template + Collection& compose(const GenImpl& source) const { + static_assert(!Source::infinite, "Cannot appendTo with infinite source"); + source | [&](Value v) { + collection_->insert(collection_->end(), std::forward(v)); + }; + return *collection_; } }; /** - * Indirect - For producing a sequence of the addresses of the values in the - * input. + * Collect - For collecting values from a source in a collection of the desired + * type. * - * This type is usually used through the 'indirect' static value, like: + * This type is usually used through the helper function 'as', like: * - * auto ptrs = from(refs) | indirect; + * std::string upper = from(stringPiece) + * | map(&toupper) + * | as(); */ -class Indirect : public Operator { +template +class Collect : public Operator> { public: - Indirect() = default; + Collect() = default; template ::type*> - class Generator : public GenImpl> { - Source source_; - static_assert(!std::is_rvalue_reference::value, - "Cannot use indirect on an rvalue"); - - public: - explicit Generator(Source source) : source_(std::move(source)) {} - - template - void foreach(Body&& body) const { - source_.foreach([&](Value value) { - return body(&value); - }); - } - - template - bool apply(Handler&& handler) const { - return source_.apply([&](Value value) -> bool { - return handler(&value); - }); - } - - // not actually infinite, since an empty generator will end the cycles. - static constexpr bool infinite = Source::infinite; - }; - - template > - Gen compose(GenImpl&& source) const { - return Gen(std::move(source.self())); + class StorageType = typename std::decay::type> + Collection compose(const GenImpl& source) const { + static_assert(!Source::infinite, + "Cannot convert infinite source to object with as."); + Collection collection; + source | [&](Value v) { + collection.insert(collection.end(), std::forward(v)); + }; + return collection; } +}; - template > - Gen compose(const GenImpl& source) const { - return Gen(source.self()); +/** + * CollectTemplate - For collecting values from a source in a collection + * constructed using the specified template type. Given the type of values + * produced by the given generator, the collection type will be: + * Container> + * + * The allocator defaults to std::allocator, so this may be used for the STL + * containers by simply using operators like 'as', 'as', + * 'as'. 'as', here is the helper method which is the usual means of + * consturcting this operator. + * + * Example: + * + * set uniqueNames = from(names) | as(); + */ +template