X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=folly%2Fgen%2FBase-inl.h;h=8869517ef9b5f4c8d80e1ab2a0169c1268e7d6f2;hb=8bfce3ed35f7597ce59278a845e9be6d75609a41;hp=ade7b5d898aa49cfb56b138290ae55eeda9ed0b0;hpb=df324b0aa2b0ecd637dae9acdb15466ec58dee68;p=folly.git diff --git a/folly/gen/Base-inl.h b/folly/gen/Base-inl.h index ade7b5d8..8869517e 100644 --- a/folly/gen/Base-inl.h +++ b/folly/gen/Base-inl.h @@ -1,5 +1,5 @@ /* - * Copyright 2015 Facebook, Inc. + * Copyright 2017 Facebook, Inc. * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. @@ -14,15 +14,18 @@ * limitations under the License. */ -#ifndef FOLLY_GEN_BASE_H +#ifndef FOLLY_GEN_BASE_H_ #error This file may only be included from folly/gen/Base.h #endif +#include + // Ignore shadowing warnings within this file, so includers can use -Wshadow. -#pragma GCC diagnostic push -#pragma GCC diagnostic ignored "-Wshadow" +FOLLY_PUSH_WARNING +FOLLY_GCC_DISABLE_WARNING("-Wshadow") -namespace folly { namespace gen { +namespace folly { +namespace gen { /** * ArgumentReference - For determining ideal argument type to receive a value. @@ -37,6 +40,9 @@ struct ArgumentReference T&& // int -> int&& >::type> {}; +/** + * Group - The output objects from the GroupBy operator + */ template class Group : public GenImpl> { public: @@ -82,6 +88,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 +98,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 +116,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 +140,9 @@ public: } return true; } + + // from takes in a normal stl structure, which are all finite + static constexpr bool infinite = false; }; /** @@ -142,45 +159,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 +206,9 @@ public: } return true; } + + // from takes in a normal stl structure, which are all finite + static constexpr bool infinite = false; }; /** @@ -203,17 +222,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 +241,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 +263,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 +285,82 @@ 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; } + 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 +370,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 +393,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 +409,9 @@ class Empty : public GenImpl> { template void foreach(Body&&) const {} + + // No values, so finite + static constexpr bool infinite = false; }; template @@ -383,6 +419,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 +432,9 @@ class SingleReference : public GenImpl> { void foreach(Body&& body) const { body(*ptr_); } + + // One value, so finite + static constexpr bool infinite = false; }; template @@ -402,6 +442,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 +455,13 @@ class SingleCopy : public GenImpl> { void foreach(Body&& body) const { body(value_); } + + // One value, so finite + static constexpr bool infinite = false; }; /* - * Operators + ***************************** Operators *************************************** */ /** @@ -426,39 +470,37 @@ class SingleCopy : public GenImpl> { * * This type is usually used through the 'map' or 'mapped' helper function: * - * auto squares = seq(1, 10) | map(square) | asVector; + * auto squares = seq(1, 10) | map(square) | as(); */ -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 < + class Value, + class Source, + class Result = typename ArgumentReference< + typename std::result_of::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,22 +510,17 @@ 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_); } }; - /** * Filter - For filtering values from a source sequence by a predicate. * @@ -493,38 +530,46 @@ class Map : public Operator> { * | filter([](const string& str) -> bool { * return !str.empty(); * }); + * + * Note that if no predicate is provided, the values are casted to bool and + * filtered based on that. So if pointers is a vector of pointers, + * + * auto nonNull = from(pointers) | filter(); + * + * 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))) { + // NB: Argument not forwarded to avoid accidental move-construction + if (pred_(value)) { body(std::forward(value)); } }); } - template + template bool apply(Handler&& handler) const { return source_.apply([&](Value value) -> bool { - if (pred_(std::forward(value))) { + // NB: Argument not forwarded to avoid accidental move-construction + if (pred_(value)) { return handler(std::forward(value)); } return true; @@ -534,16 +579,12 @@ 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_); } @@ -556,27 +597,26 @@ class Filter : public Operator> { * * auto best = from(sortedItems) * | until([](Item& item) { return item.score > 100; }) - * | asVector; + * | as(); */ -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 { @@ -591,24 +631,20 @@ 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; }; /** @@ -622,23 +658,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 { @@ -650,23 +687,81 @@ 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_); } }; +/** + * Visit - For calling a function on each item before passing it down the + * pipeline. + * + * This type is usually used through the 'visit' helper function: + * + * auto printedValues = seq(1) | visit(debugPrint); + * // nothing printed yet + * auto results = take(10) | as(); + * // results now populated, 10 values printed + */ +template +class Visit : public Operator> { + Visitor visitor_; + + public: + Visit() = default; + + explicit Visit(Visitor visitor) : visitor_(std::move(visitor)) {} + + template + class Generator : public GenImpl> { + Source source_; + Visitor visitor_; + + public: + explicit Generator(Source source, const Visitor& visitor) + : source_(std::move(source)), visitor_(visitor) {} + + template + void foreach(Body&& body) const { + source_.foreach([&](Value value) { + visitor_(value); // not forwarding to avoid accidental moves + body(std::forward(value)); + }); + } + + template + bool apply(Handler&& handler) const { + return source_.apply([&](Value value) { + visitor_(value); // not forwarding to avoid accidental moves + return handler(std::forward(value)); + }); + } + + static constexpr bool infinite = Source::infinite; + }; + + template > + Gen compose(GenImpl&& source) const { + return Gen(std::move(source.self()), visitor_); + } + + template > + Gen compose(const GenImpl& source) const { + return Gen(source.self(), visitor_); + } +}; + /** * Stride - For producing every Nth value from a source. * @@ -689,34 +784,38 @@ 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 > @@ -734,21 +833,23 @@ 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 < + class Value, + class Source, + class Rand, + class StorageType = typename std::decay::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, @@ -756,53 +857,61 @@ 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 < + class Source, + class Value, + class Gen = Generator> Gen compose(GenImpl&& source) const { return Gen(std::move(source.self()), count_, rng_); } - template> + template < + class Source, + class Value, + class Gen = Generator> Gen compose(const GenImpl& source) const { return Gen(source.self(), count_, rng_); } @@ -819,21 +928,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); @@ -841,42 +949,39 @@ 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_); } @@ -895,30 +1000,27 @@ 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 < + class Value, + class Source, + class StorageType = typename std::decay::type, + class Result = typename std::result_of::type> + class Generator + : public GenImpl> { static_assert(!Source::infinite, "Cannot sort infinite source!"); Source source_; Selector selector_; @@ -934,13 +1036,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(); @@ -950,14 +1051,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 @@ -974,18 +1075,17 @@ 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_); } @@ -1015,11 +1115,12 @@ class GroupBy : public Operator> { explicit GroupBy(Selector selector) : selector_(std::move(selector)) {} - template ::type, - class Key = typename std::result_of::type, - class KeyDecayed = typename std::decay::type> + template < + class Value, + class Source, + class ValueDecayed = typename std::decay::type, + class Key = typename std::result_of::type, + class KeyDecayed = typename std::decay::type> class Generator : public GenImpl< Group&&, @@ -1051,6 +1152,9 @@ class GroupBy : public Operator> { } return true; } + + // Can only be run on and produce finite generators + static constexpr bool infinite = false; }; template > @@ -1073,17 +1177,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"); @@ -1103,18 +1207,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_; @@ -1129,12 +1231,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) { @@ -1144,7 +1244,7 @@ class Distinct : public Operator> { }); } - template + template bool apply(Handler&& handler) const { std::unordered_set keysSeen; return source_.apply([&](Value value) -> bool { @@ -1154,18 +1254,18 @@ 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_); } @@ -1175,16 +1275,17 @@ 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 < + class Source, + class Ret = + decltype(std::declval().compose(std::declval()))> Ret operator()(Source&& source) const { return op_.compose(std::forward(source)); } @@ -1205,42 +1306,43 @@ 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 < + class Value, + class Source, + class StorageType = typename std::decay::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_); @@ -1249,811 +1351,993 @@ 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. + * Window - For overlapping the lifetimes of pipeline values, especially with + * Futures. * - * This type is primarily used through the 'foldl' helper method, like: + * This type is usually used through the 'window' helper function: * - * double movingAverage = from(values) - * | foldl(0.0, [](double avg, double sample) { - * return sample * 0.1 + avg * 0.9; - * }); + * auto responses + * = byLine(STDIN) + * | map(makeRequestFuture) + * | window(1000) + * | map(waitFuture) + * | as(); */ -template -class FoldLeft : public Operator> { - Seed seed_; - Fold fold_; +class Window : public Operator { + size_t windowSize_; + 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; + explicit Window(size_t windowSize) : windowSize_(windowSize) { + if (windowSize_ == 0) { + throw std::invalid_argument("Window size must be non-zero!"); + } } -}; -/** - * 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 < + class Value, + class Source, + class StorageType = typename std::decay::type> + class Generator + : public GenImpl> { + Source source_; + size_t windowSize_; - 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()); - } -}; + public: + explicit Generator(Source source, size_t windowSize) + : source_(std::move(source)), windowSize_(windowSize) {} + template + bool apply(Handler&& handler) const { + std::vector buffer; + buffer.reserve(windowSize_); + size_t readIndex = 0; + bool shouldContinue = source_.apply([&](Value value) -> bool { + if (buffer.size() < windowSize_) { + buffer.push_back(std::forward(value)); + } else { + StorageType& entry = buffer[readIndex++]; + if (readIndex == windowSize_) { + readIndex = 0; + } + if (!handler(std::move(entry))) { + return false; + } + entry = std::forward(value); + } + return true; + }); + if (!shouldContinue) { + return false; + } + if (buffer.size() < windowSize_) { + for (StorageType& entry : buffer) { + if (!handler(std::move(entry))) { + return false; + } + } + } else { + for (size_t i = readIndex;;) { + StorageType& entry = buffer[i++]; + if (!handler(std::move(entry))) { + return false; + } + if (i == windowSize_) { + i = 0; + } + if (i == readIndex) { + break; + } + } + } + return true; + } -/** - * Any - For determining whether any values in a sequence satisfy a predicate. - * - * This type is primarily used through the 'any' static value, like: - * - * bool any20xPrimes = seq(200, 210) | filter(isPrime) | any; - * - * Note that it may also be used like so: - * - * bool any20xPrimes = seq(200, 210) | any(isPrime); - * - */ -class Any : public Operator { - public: - Any() = default; + // Taking n-tuples of an infinite source is still infinite + static constexpr bool infinite = Source::infinite; + }; - template - bool compose(const GenImpl& source) const { - bool any = false; - source | [&](Value v) -> bool { - any = true; - return false; - }; - return any; + template > + Gen compose(GenImpl&& source) const { + return Gen(std::move(source.self()), windowSize_); } - /** - * Convenience function for use like: - * - * bool found = gen | any([](int i) { return i * i > 100; }); - */ - template, - class Composed = Composed> - Composed operator()(Predicate pred) const { - return Composed(Filter(std::move(pred)), Any()); + template > + Gen compose(const GenImpl& source) const { + return Gen(source.self(), windowSize_); } }; /** - * All - For determining whether all values in a sequence satisfy a predicate. - * - * This type is primarily used through the 'any' static value, like: + * Concat - For flattening generators of generators. * - * bool valid = from(input) | all(validate); + * This type is usually used through the 'concat' static value, like: * - * Note: Passing an empty sequence through 'all()' will always return true. + * auto edges = + * from(nodes) + * | map([](Node& x) { + * return from(x.neighbors) + * | map([&](Node& y) { + * return Edge(x, y); + * }); + * }) + * | concat + * | as(); */ -template -class All : public Operator> { - Predicate pred_; +class Concat : public Operator { public: - All() = default; - explicit All(Predicate pred) - : pred_(std::move(pred)) - { } + Concat() = default; - template - bool compose(const GenImpl& source) const { - static_assert(!Source::infinite, "Cannot call 'all' on infinite source"); - bool all = true; - source | [&](Value v) -> bool { - if (!pred_(std::forward(v))) { - all = false; - return false; - } - return true; - }; - return all; + template < + class Inner, + class Source, + class InnerValue = typename std::decay::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()); } }; /** - * 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. + * RangeConcat - For flattening generators of iterables. * - * This type is primarily used through the 'reduce' helper method, like: + * This type is usually used through the 'rconcat' static value, like: * - * sring longest = from(names) - * | reduce([](string&& best, string& current) { - * return best.size() >= current.size() ? best : current; - * }); + * map> adjacency; + * auto sinks = + * from(adjacency) + * | get<1>() + * | rconcat() + * | as(); */ -template -class Reduce : public Operator> { - Reducer reducer_; +class RangeConcat : public Operator { public: - Reduce() = default; - explicit Reduce(Reducer reducer) - : reducer_(std::move(reducer)) - {} + RangeConcat() = default; - 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 < + class Range, + class Source, + class InnerValue = typename ValueTypeOfRange::RefType> + class Generator + : public GenImpl> { + Source source_; + + public: + explicit Generator(Source source) : source_(std::move(source)) {} + + template + void foreach(Body&& body) const { + source_.foreach([&](Range range) { + for (auto& value : range) { + body(value); + } + }); } - return accum.value(); + + template + bool apply(Handler&& handler) const { + return source_.apply([&](Range range) -> bool { + for (auto& value : range) { + if (!handler(value)) { + return false; + } + } + return true; + }); + } + + // 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 > + Gen compose(GenImpl&& source) const { + return Gen(std::move(source.self())); + } + + template > + Gen compose(const GenImpl& source) const { + return Gen(source.self()); } }; /** - * Count - for simply counting the items in a collection. + * 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)'. * - * This type is usually used through its singleton, 'count': + * This type is used through the `guard` helper, like so: * - * auto shortPrimes = seq(1, 100) | filter(isPrime) | count; - */ -class Count : public Operator { + * 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(); + * + * TODO(tjackson): Rename this back to Guard. + **/ +template +class GuardImpl : public Operator> { + ErrorHandler handler_; + public: - Count() = default; + explicit GuardImpl(ErrorHandler handler) : handler_(std::move(handler)) {} - 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 + class Generator : public GenImpl> { + Source source_; + ErrorHandler handler_; + + public: + explicit Generator(Source source, ErrorHandler handler) + : source_(std::move(source)), handler_(std::move(handler)) {} + + 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; + }; + + template > + Gen compose(GenImpl&& source) const { + return Gen(std::move(source.self()), handler_); + } + + template > + Gen compose(const GenImpl& source) const { + return Gen(source.self(), handler_); } }; /** - * Sum - For simply summing up all the values from a source. + * Dereference - For dereferencing a sequence of pointers while filtering out + * null pointers. * - * This type is usually used through its singleton, 'sum': + * This type is usually used through the 'dereference' static value, like: * - * auto gaussSum = seq(1, 100) | sum; + * auto refs = from(ptrs) | dereference; */ -class Sum : public Operator { +class Dereference : public Operator { public: - Sum() : Operator() {} + Dereference() = 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 < + class Value, + class Source, + class Result = decltype(*std::declval())> + class Generator : public GenImpl> { + Source source_; + + public: + explicit Generator(Source source) : source_(std::move(source)) {} + + template + void foreach(Body&& body) const { + source_.foreach([&](Value value) { + if (value) { + return body(*std::forward(value)); + } + }); + } + + template + bool apply(Handler&& handler) const { + return source_.apply([&](Value value) -> bool { + if (value) { + return handler(*std::forward(value)); + } + return true; + }); + } + + // Just passes value though, length unaffected + static constexpr bool infinite = Source::infinite; + }; + + template > + Gen compose(GenImpl&& source) const { + return Gen(std::move(source.self())); + } + + 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. + * Indirect - For producing a sequence of the addresses of the values in the + * input. * - * This type should be used through the 'contains' helper method, like: + * This type is usually used through the 'indirect' static value, like: * - * bool contained = seq(1, 10) | map(square) | contains(49); + * auto ptrs = from(refs) | indirect; */ -template -class Contains : public Operator> { - Needle needle_; +class Indirect : public Operator { public: - explicit Contains(Needle needle) - : needle_(std::move(needle)) - {} + Indirect() = default; - 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)); + template < + class Value, + class Source, + class Result = typename std::remove_reference::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(&std::forward(value)); }); + } + + template + bool apply(Handler&& handler) const { + return source_.apply([&](Value value) -> bool { + return handler(&std::forward(value)); + }); + } + + // Just passes value though, length unaffected + static constexpr bool infinite = Source::infinite; + }; + + template > + Gen compose(GenImpl&& source) const { + return Gen(std::move(source.self())); + } + + template > + Gen compose(const GenImpl& source) const { + return Gen(source.self()); } }; /** - * Min - For a value which minimizes a key, where the key is determined by a - * given selector, and compared by given comparer. + * Cycle - For repeating a sequence forever. * - * This type is usually used through the singletone 'min' or through the helper - * functions 'minBy' and 'maxBy'. + * This type is usually used through the 'cycle' static value, like: * - * auto oldest = from(people) - * | minBy([](Person& p) { - * return p.dateOfBirth; - * }); + * auto tests + * = from(samples) + * | cycle + * | take(100); + * + * or in the finite case: + * + * auto thrice = g | cycle(3); */ -template -class Min : public Operator> { - Selector selector_; - Comparer comparer_; +template +class Cycle : public Operator> { + off_t limit_; // not used if forever == true public: - Min() = default; + Cycle() = default; + + explicit Cycle(off_t limit) : limit_(limit) { + static_assert( + !forever, + "Cycle limit constructor should not be used when forever == true."); + } + + template + class Generator : public GenImpl> { + Source source_; + off_t limit_; - 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); + 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; + } } - }; - if (!min.hasValue()) { - throw EmptySequence(); + return true; } - return min.value(); + + // 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 > + Gen compose(GenImpl&& source) const { + return Gen(std::move(source.self()), limit_); + } + + template > + Gen compose(const GenImpl& source) const { + 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 ***************************************** + */ + /** - * Append - For collecting values from a source into a given output container - * by appending. + * 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 usually used through the helper function 'appendTo', like: + * This type is primarily used through the 'foldl' helper method, like: * - * vector ids; - * from(results) | map([](Person& p) { return p.id }) - * | appendTo(ids); + * double movingAverage = from(values) + * | foldl(0.0, [](double avg, double sample) { + * return sample * 0.1 + avg * 0.9; + * }); */ -template -class Append : public Operator> { - Collection* collection_; +template +class FoldLeft : public Operator> { + Seed seed_; + Fold fold_; + public: - explicit Append(Collection* collection) - : collection_(collection) - {} + FoldLeft() = default; + FoldLeft(Seed seed, Fold fold) + : seed_(std::move(seed)), fold_(std::move(fold)) {} - template - Collection& compose(const GenImpl& source) const { + template + Seed compose(const GenImpl& source) const { + static_assert(!Source::infinite, "Cannot foldl infinite source"); + Seed accum = seed_; source | [&](Value v) { - collection_->insert(collection_->end(), std::forward(v)); + accum = fold_(std::move(accum), std::forward(v)); }; - return *collection_; + return accum; } }; /** - * Collect - For collecting values from a source in a collection of the desired - * type. + * First - For finding the first value in a sequence. * - * This type is usually used through the helper function 'as', like: + * This type is primarily used through the 'first' static value, like: * - * std::string upper = from(stringPiece) - * | map(&toupper) - * | as(); + * int firstThreeDigitPrime = seq(100) | filter(isPrime) | first; */ -template -class Collect : public Operator> { +class First : public Operator { public: - Collect() = default; + First() = default; - template::type> - Collection compose(const GenImpl& source) const { - Collection collection; - source | [&](Value v) { - collection.insert(collection.end(), std::forward(v)); + template < + class Source, + class Value, + class StorageType = typename std::decay::type> + Optional compose(const GenImpl& source) const { + Optional accum; + source | [&](Value v) -> bool { + accum = std::forward(v); + return false; }; - return collection; + return accum; } }; - /** - * 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> + * IsEmpty - a helper class for isEmpty and notEmpty * - * 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. + * 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. * - * Example: * - * set uniqueNames = from(names) | as(); + * 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 Container, - template class Allocator> -class CollectTemplate : public Operator> { +template +class IsEmpty : public Operator> { public: - CollectTemplate() = default; + IsEmpty() = default; - 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 + 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; } }; /** - * Concat - For flattening generators of generators. + * 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 usually used through the 'concat' static value, like: + * This type is primarily used through the 'reduce' helper method, like: * - * auto edges = - * from(nodes) - * | map([](Node& x) { - * return from(x.neighbors) - * | map([&](Node& y) { - * return Edge(x, y); - * }); - * }) - * | concat - * | as(); + * sring longest = from(names) + * | reduce([](string&& best, string& current) { + * return best.size() >= current.size() ? best : current; + * }); */ -class Concat : public Operator { - public: - 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)); - }); - } - - static constexpr bool infinite = Source::infinite; - }; - - template> - Gen compose(GenImpl&& source) const { - return Gen(std::move(source.self())); - } +template +class Reduce : public Operator> { + Reducer reducer_; - template> - Gen compose(const GenImpl& source) const { - return Gen(source.self()); + public: + Reduce() = default; + explicit Reduce(Reducer reducer) : reducer_(std::move(reducer)) {} + + template < + class Source, + class Value, + class StorageType = typename std::decay::type> + Optional compose(const GenImpl& source) const { + static_assert(!Source::infinite, "Cannot reduce infinite source"); + Optional accum; + source | [&](Value v) { + if (auto target = accum.get_pointer()) { + *target = reducer_(std::move(*target), std::forward(v)); + } else { + accum = std::forward(v); + } + }; + return accum; } }; /** - * RangeConcat - For flattening generators of iterables. + * Count - for simply counting the items in a collection. * - * This type is usually used through the 'rconcat' static value, like: + * This type is usually used through its singleton, 'count': * - * map> adjacency; - * auto sinks = - * from(adjacency) - * | get<1>() - * | rconcat() - * | as(); + * auto shortPrimes = seq(1, 100) | filter(isPrime) | count; */ -class RangeConcat : public Operator { +class Count : public Operator { public: - RangeConcat() = default; - - template::RefType> - class Generator - : public GenImpl> { - Source source_; - public: - explicit Generator(Source source) - : source_(std::move(source)) {} - - template - void foreach(Body&& body) const { - source_.foreach([&](Range range) { - for (auto& value : range) { - body(value); - } - }); - } - - template - bool apply(Handler&& handler) const { - return source_.apply([&](Range range) -> bool { - for (auto& value : range) { - if (!handler(value)) { - return false; - } - } - return true; - }); - } - }; - - template> - Gen compose(GenImpl&& source) const { - return Gen(std::move(source.self())); - } + Count() = default; - template> - Gen compose(const GenImpl& source) const { - return Gen(source.self()); + 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); } }; - /** - * 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)'. - * - * This type is used through the `guard` helper, like so: + * Sum - For simply summing up all the values from a source. * - * 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(); + * This type is usually used through its singleton, 'sum': * - * TODO(tjackson): Rename this back to Guard. - **/ -template -class GuardImpl : public Operator> { - ErrorHandler handler_; + * auto gaussSum = seq(1, 100) | sum; + */ +class Sum : public Operator { public: - explicit GuardImpl(ErrorHandler handler) : handler_(std::move(handler)) {} - - template - class Generator : public GenImpl> { - Source source_; - ErrorHandler handler_; - public: - explicit Generator(Source source, - ErrorHandler handler) - : source_(std::move(source)), - handler_(std::move(handler)) {} + Sum() = default; - 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)); - } - }); - } + template < + class Source, + class Value, + class StorageType = typename std::decay::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); + } +}; - static constexpr bool infinite = Source::infinite; - }; +/** + * 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_; - template> - Gen compose(GenImpl&& source) const { - return Gen(std::move(source.self()), handler_); - } + public: + explicit Contains(Needle needle) : needle_(std::move(needle)) {} - template> - Gen compose(const GenImpl& source) const { - return Gen(source.self(), handler_); + template < + class Source, + class Value, + class StorageType = typename std::decay::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)); + }); } }; /** - * Cycle - For repeating a sequence forever. + * 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 'cycle' static value, like: + * This type is usually used through the singletone 'min' or through the helper + * functions 'minBy' and 'maxBy'. * - * auto tests - * = from(samples) - * | cycle - * | take(100); + * auto oldest = from(people) + * | minBy([](Person& p) { + * return p.dateOfBirth; + * }); */ -class Cycle : public Operator { - off_t limit_; // -1 for infinite +template +class Min : public Operator> { + Selector selector_; + Comparer comparer_; + + template + const T& asConst(const T& t) const { + return t; + } + public: - Cycle() - : limit_(-1) { } + Min() = default; - explicit Cycle(off_t limit) - : limit_(limit) { } + explicit Min(Selector selector) : selector_(std::move(selector)) {} - template - class Generator : public GenImpl> { - Source source_; - off_t limit_; // -1 for infinite - public: - explicit Generator(Source source, off_t limit) - : source_(std::move(source)) - , limit_(limit) {} + Min(Selector selector, Comparer comparer) + : selector_(std::move(selector)), comparer_(std::move(comparer)) {} - template - bool apply(Handler&& handler) const { - bool cont; - auto handler2 = [&](Value value) { - cont = handler(std::forward(value)); - return cont; - }; - for (off_t count = 0; count != limit_; ++count) { - cont = false; - source_.apply(handler2); - if (!cont) { - return false; + template < + class Value, + class Source, + class StorageType = typename std::decay::type, + class Key = typename std::decay< + typename std::result_of::type>::type> + Optional 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_(asConst(v)); // so that selector_ cannot mutate v + if (auto lastKey = minKey.get_pointer()) { + if (!comparer_(key, *lastKey)) { + return; } } - return true; - } - - // 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()), limit_); + minKey = std::move(key); + min = std::forward(v); + }; + return min; } +}; - template> - Gen compose(const GenImpl& source) const { - return Gen(source.self(), limit_); - } +/** + * 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_; - /** - * Convenience function for use like: - * - * auto tripled = gen | cycle(3); - */ - Cycle operator()(off_t limit) const { - return Cycle(limit); + public: + explicit Append(Collection* collection) : collection_(collection) {} + + 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_; } }; /** - * Dereference - For dereferencing a sequence of pointers while filtering out - * null pointers. + * Collect - For collecting values from a source in a collection of the desired + * type. * - * This type is usually used through the 'dereference' static value, like: + * This type is usually used through the helper function 'as', like: * - * auto refs = from(ptrs) | dereference; + * std::string upper = from(stringPiece) + * | map(&toupper) + * | as(); */ -class Dereference : public Operator { +template +class Collect : public Operator> { public: - Dereference() = default; - - template())> - class Generator : public GenImpl> { - Source source_; - public: - explicit Generator(Source source) - : source_(std::move(source)) {} - - template - void foreach(Body&& body) const { - source_.foreach([&](Value value) { - if (value) { - return body(*value); - } - }); - } - - template - bool apply(Handler&& handler) const { - return source_.apply([&](Value value) -> bool { - if (value) { - return handler(*value); - } - return true; - }); - } - - // 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())); - } + Collect() = default; - template> - Gen compose(const GenImpl& source) const { - return Gen(source.self()); + template < + class Value, + class Source, + 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; } }; /** - * Indirect - For producing a sequence of the addresses of the values in the - * input. + * 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> * - * This type is usually used through the 'indirect' static value, like: + * 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 + * constructing this operator. * - * auto ptrs = from(refs) | indirect; + * Example: + * + * set uniqueNames = from(names) | as(); */ -class Indirect : public Operator { +template < + template class Container, + template class Allocator> +class CollectTemplate : public Operator> { public: - Indirect() = default; + CollectTemplate() = default; - template ::type*> - class Generator : public GenImpl> { - Source source_; - static_assert(!std::is_rvalue_reference::value, - "Cannot use indirect on an rvalue"); + template < + class Value, + class Source, + class StorageType = typename std::decay::type, + class Collection = Container>> + 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; + } +}; - public: - explicit Generator(Source source) : source_(std::move(source)) {} +/** + * UnwrapOr - For unwrapping folly::Optional values, or providing the given + * fallback value. Usually used through the 'unwrapOr' helper like so: + * + * auto best = from(scores) | max | unwrapOr(-1); + * + * Note that the fallback value needn't match the value in the Optional it is + * unwrapping. If mis-matched types are supported, the common type of the two is + * returned by value. If the types match, a reference (T&& > T& > const T&) is + * returned. + */ +template +class UnwrapOr { + public: + explicit UnwrapOr(T&& value) : value_(std::move(value)) {} + explicit UnwrapOr(const T& value) : value_(value) {} - template - void foreach(Body&& body) const { - source_.foreach([&](Value value) { - return body(&value); - }); - } + T& value() { return value_; } + const T& value() const { return value_; } - template - bool apply(Handler&& handler) const { - return source_.apply([&](Value value) -> bool { - return handler(&value); - }); - } + private: + T value_; +}; - // not actually infinite, since an empty generator will end the cycles. - static constexpr bool infinite = Source::infinite; - }; +template +T&& operator|(Optional&& opt, UnwrapOr&& fallback) { + if (T* p = opt.get_pointer()) { + return std::move(*p); + } + return std::move(fallback.value()); +} - template > - Gen compose(GenImpl&& source) const { - return Gen(std::move(source.self())); +template +T& operator|(Optional& opt, UnwrapOr& fallback) { + if (T* p = opt.get_pointer()) { + return *p; } + return fallback.value(); +} - template > - Gen compose(const GenImpl& source) const { - return Gen(source.self()); +template +const T& operator|(const Optional& opt, const UnwrapOr& fallback) { + if (const T* p = opt.get_pointer()) { + return *p; } -}; + return fallback.value(); +} + +// Mixed type unwrapping always returns values, moving where possible +template < + class T, + class U, + class R = typename std::enable_if< + !std::is_same::value, + typename std::common_type::type>::type> +R operator|(Optional&& opt, UnwrapOr&& fallback) { + if (T* p = opt.get_pointer()) { + return std::move(*p); + } + return std::move(fallback.value()); +} + +template < + class T, + class U, + class R = typename std::enable_if< + !std::is_same::value, + typename std::common_type::type>::type> +R operator|(const Optional& opt, UnwrapOr&& fallback) { + if (const T* p = opt.get_pointer()) { + return *p; + } + return std::move(fallback.value()); +} + +template < + class T, + class U, + class R = typename std::enable_if< + !std::is_same::value, + typename std::common_type::type>::type> +R operator|(Optional&& opt, const UnwrapOr& fallback) { + if (T* p = opt.get_pointer()) { + return std::move(*p); + } + return fallback.value(); +} + +template < + class T, + class U, + class R = typename std::enable_if< + !std::is_same::value, + typename std::common_type::type>::type> +R operator|(const Optional& opt, const UnwrapOr& fallback) { + if (const T* p = opt.get_pointer()) { + return *p; + } + return fallback.value(); +} + +/** + * Unwrap - For unwrapping folly::Optional values in a folly::gen style. Usually + * used through the 'unwrap' instace like so: + * + * auto best = from(scores) | max | unwrap; // may throw + */ +class Unwrap {}; + +template +T&& operator|(Optional&& opt, const Unwrap&) { + return std::move(opt.value()); +} + +template +T& operator|(Optional& opt, const Unwrap&) { + return opt.value(); +} + +template +const T& operator|(const Optional& opt, const Unwrap&) { + return opt.value(); +} -} //::detail +} // namespace detail /** * VirtualGen - For wrapping template types in simple polymorphic wrapper. **/ -template +template class VirtualGen : public GenImpl> { class WrapperBase { public: @@ -2063,23 +2347,22 @@ class VirtualGen : public GenImpl> { virtual std::unique_ptr clone() const = 0; }; - template + template class WrapperImpl : public WrapperBase { Wrapped wrapped_; + public: - explicit WrapperImpl(Wrapped wrapped) - : wrapped_(std::move(wrapped)) { - } + explicit WrapperImpl(Wrapped wrapped) : wrapped_(std::move(wrapped)) {} - virtual bool apply(const std::function& handler) const { + bool apply(const std::function& handler) const override { return wrapped_.apply(handler); } - virtual void foreach(const std::function& body) const { + void foreach(const std::function& body) const override { wrapped_.foreach(body); } - virtual std::unique_ptr clone() const { + std::unique_ptr clone() const override { return std::unique_ptr(new WrapperImpl(wrapped_)); } }; @@ -2094,8 +2377,7 @@ class VirtualGen : public GenImpl> { VirtualGen(VirtualGen&& source) noexcept : wrapper_(std::move(source.wrapper_)) {} - VirtualGen(const VirtualGen& source) - : wrapper_(source.wrapper_->clone()) {} + VirtualGen(const VirtualGen& source) : wrapper_(source.wrapper_->clone()) {} VirtualGen& operator=(const VirtualGen& source) { wrapper_.reset(source.wrapper_->clone()); @@ -2103,7 +2385,7 @@ class VirtualGen : public GenImpl> { } VirtualGen& operator=(VirtualGen&& source) noexcept { - wrapper_= std::move(source.wrapper_); + wrapper_ = std::move(source.wrapper_); return *this; } @@ -2120,68 +2402,64 @@ class VirtualGen : public GenImpl> { * non-template operators, statically defined to avoid the need for anything but * the header. */ -static const detail::Sum sum{}; +constexpr detail::Sum sum{}; -static const detail::Count count{}; +constexpr detail::Count count{}; -static const detail::First first{}; +constexpr detail::First first{}; -/** - * Use directly for detecting any values, or as a function to detect values - * which pass a predicate: - * - * auto nonempty = g | any; - * auto evens = g | any(even); - */ -static const detail::Any any{}; +constexpr detail::IsEmpty isEmpty{}; -static const detail::Min min{}; +constexpr detail::IsEmpty notEmpty{}; -static const detail::Min max{}; +constexpr detail::Min min{}; -static const detail::Order order{}; +constexpr detail::Min max{}; -static const detail::Distinct distinct{}; +constexpr detail::Order order{}; -static const detail::Map move{}; +constexpr detail::Distinct distinct{}; -static const detail::Concat concat{}; +constexpr detail::Map move{}; -static const detail::RangeConcat rconcat{}; +constexpr detail::Concat concat{}; -/** - * Use directly for infinite sequences, or as a function to limit cycle count. - * - * auto forever = g | cycle; - * auto thrice = g | cycle(3); - */ -static const detail::Cycle cycle{}; +constexpr detail::RangeConcat rconcat{}; -static const detail::Dereference dereference{}; +constexpr detail::Cycle cycle{}; -static const detail::Indirect indirect{}; +constexpr detail::Dereference dereference{}; -inline detail::Take take(size_t count) { - return detail::Take(count); -} +constexpr detail::Indirect indirect{}; -inline detail::Stride stride(size_t s) { - return detail::Stride(s); +constexpr detail::Unwrap unwrap{}; + +template +inline detail::Take take(Number count) { + if (count < 0) { + throw std::invalid_argument("Negative value passed to take()"); + } + return detail::Take(static_cast(count)); } -template +inline detail::Stride stride(size_t s) { return detail::Stride(s); } + +template inline detail::Sample sample(size_t count, Random rng = Random()) { return detail::Sample(count, std::move(rng)); } -inline detail::Skip skip(size_t count) { - return detail::Skip(count); -} +inline detail::Skip skip(size_t count) { return detail::Skip(count); } inline detail::Batch batch(size_t batchSize) { return detail::Batch(batchSize); } -}} //folly::gen +inline detail::Window window(size_t windowSize) { + return detail::Window(windowSize); +} + +} // namespace gen +} // namespace folly -#pragma GCC diagnostic pop +FOLLY_POP_WARNING