From 43d53e0668efb3b1c100949183362b931f979932 Mon Sep 17 00:00:00 2001 From: Joe Richey Date: Tue, 14 Jul 2015 13:50:24 -0700 Subject: [PATCH] Changing behavior of 'any' and 'all' sinks, adding in 'isEmpty' and 'notEmpty' sinks Summary: When adding in the 'filter()' default behavior, I considered adding in similar behavior for 'any' and 'all'. However, we had 'any' with no funciton call basically check if anything was present, not testing a predicate. This can create a confusing senario, so I removed this behavior from 'any' and added in the 'isEmpty' and 'notEmpty' sinks. Now the calls 'any()' and 'all()' (called with parens, so old uses won't compile) check for truthy values simlar to 'filter()'. I also added some unit tests and changed 'static const' objects to 'constexpr'. Reviewed By: @ddrcoder Differential Revision: D2234637 --- folly/gen/Base-inl.h | 150 ++++++++++----------------- folly/gen/Base.h | 100 +++++++++++++++--- folly/gen/test/BaseTest.cpp | 36 +++++-- folly/gen/test/ParallelBenchmark.cpp | 4 +- 4 files changed, 173 insertions(+), 117 deletions(-) diff --git a/folly/gen/Base-inl.h b/folly/gen/Base-inl.h index 3827fdf4..7a26fede 100644 --- a/folly/gen/Base-inl.h +++ b/folly/gen/Base-inl.h @@ -1340,78 +1340,32 @@ class First : public Operator { } }; - /** - * 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); + * 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. */ -class Any : public Operator { +template +class IsEmpty : public Operator> { public: - Any() = default; + IsEmpty() = default; template bool compose(const GenImpl& source) const { - bool any = false; + 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 { - any = true; + ans = !emptyResult; return false; }; - return any; - } - - /** - * 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()); - } -}; - -/** - * All - For determining whether all values in a sequence satisfy a predicate. - * - * This type is primarily used through the 'any' static value, like: - * - * bool valid = from(input) | all(validate); - * - * Note: Passing an empty sequence through 'all()' will always return true. - */ -template -class All : public Operator> { - Predicate pred_; - public: - All() = default; - explicit All(Predicate pred) - : pred_(std::move(pred)) - { } - - 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; + return ans; } }; @@ -1486,7 +1440,7 @@ class Count : public Operator { */ class Sum : public Operator { public: - Sum() : Operator() {} + Sum() = default; template> { * = from(samples) * | cycle * | take(100); + * + * or in the finite case: + * + * auto thrice = g | cycle(3); */ -class Cycle : public Operator { - off_t limit_; // -1 for infinite +template +class Cycle : public Operator> { + off_t limit_; // not used if forever == true public: - Cycle() - : limit_(-1) { } + Cycle() = default; explicit Cycle(off_t limit) - : limit_(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_; // -1 for infinite + off_t limit_; public: explicit Generator(Source source, off_t limit) : source_(std::move(source)) @@ -1905,7 +1867,8 @@ class Cycle : public Operator { cont = handler(std::forward(value)); return cont; }; - for (off_t count = 0; count != limit_; ++count) { + // Becomes an infinte loop if forever == true + for (off_t count = 0; (forever || count != limit_); ++count) { cont = false; source_.apply(handler2); if (!cont) { @@ -1934,12 +1897,12 @@ class Cycle : public Operator { } /** - * Convenience function for use like: + * Convenience function for finite cycles used like: * * auto tripled = gen | cycle(3); */ - Cycle operator()(off_t limit) const { - return Cycle(limit); + Cycle operator()(off_t limit) const { + return Cycle(limit); } }; @@ -2126,46 +2089,41 @@ 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: + * Use 'isEmpty' and 'notEmpty' for detecting if there are any values or not. * - * auto nonempty = g | any; - * auto evens = g | any(even); + * bool hasPrimes = g | filter(prime) | notEmpty; + * bool lacksEvens = g | filter(even) | isEmpty; */ -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{}; + +constexpr detail::Cycle cycle{}; -static const detail::Dereference dereference{}; +constexpr detail::Dereference dereference{}; -static const detail::Indirect indirect{}; +constexpr detail::Indirect indirect{}; inline detail::Take take(size_t count) { return detail::Take(count); diff --git a/folly/gen/Base.h b/folly/gen/Base.h index 322b895e..08a901a9 100644 --- a/folly/gen/Base.h +++ b/folly/gen/Base.h @@ -215,6 +215,30 @@ public: } }; +/** + * Class and helper function for negating a boolean Predicate + */ +template +class Negate { + Predicate pred_; + + public: + Negate() = default; + + explicit Negate(Predicate pred) + : pred_(std::move(pred)) + {} + + template + bool operator()(Arg&& arg) const { + return !pred_(std::forward(arg)); + } +}; +template +Negate negate(Predicate pred) { + return Negate(std::move(pred)); +} + template class Cast { public: @@ -346,6 +370,7 @@ class Concat; class RangeConcat; +template class Cycle; class Batch; @@ -363,10 +388,8 @@ class FoldLeft; class First; -class Any; - -template -class All; +template +class IsEmpty; template class Reduce; @@ -620,12 +643,6 @@ Filter filter(Predicate pred = Predicate()) { return Filter(std::move(pred)); } -template> -All all(Predicate pred = Predicate()) { - return All(std::move(pred)); -} - template> Until until(Predicate pred = Predicate()) { @@ -647,9 +664,9 @@ Order orderByDescending(Selector selector = Selector()) { return Order(std::move(selector)); } -template> -GroupBy groupBy(Selector selector = Identity()) { +template > +GroupBy groupBy(Selector selector = Selector()) { return GroupBy(std::move(selector)); } @@ -687,6 +704,63 @@ detail::TypeAssertion assert_type() { /* * Sink Factories */ + +/** + * any() - For determining if any value in a sequence satisfies a predicate. + * + * The following is an example for checking if any computer is broken: + * + * bool schrepIsMad = from(computers) | any(isBroken); + * + * (because everyone knows Schrep hates broken computers). + * + * Note that if no predicate is provided, 'any()' checks if any of the values + * are true when cased to bool. To check if any of the scores are nonZero: + * + * bool somebodyScored = from(scores) | any(); + * + * Note: Passing an empty sequence through 'any()' will always return false. In + * fact, 'any()' is equivilent to the composition of 'filter()' and 'notEmpty'. + * + * from(source) | any(pred) == from(source) | filter(pred) | notEmpty + */ + +template , + class NotEmpty = detail::IsEmpty, + class Composed = detail::Composed> +Composed any(Predicate pred = Predicate()) { + return Composed(Filter(std::move(pred)), NotEmpty()); +} + +/** + * all() - For determining whether all values in a sequence satisfy a predicate. + * + * The following is an example for checking if all members of a team are cool: + * + * bool isAwesomeTeam = from(team) | all(isCool); + * + * Note that if no predicate is provided, 'all()'' checks if all of the values + * are true when cased to bool. + * The following makes sure none of 'pointers' are nullptr: + * + * bool allNonNull = from(pointers) | all(); + * + * Note: Passing an empty sequence through 'all()' will always return true. In + * fact, 'all()' is equivilent to the composition of 'filter()' with the + * reversed predicate and 'isEmpty'. + * + * from(source) | all(pred) == from(source) | filter(negate(pred)) | isEmpty + */ + +template >, + class IsEmpty = detail::IsEmpty, + class Composed = detail::Composed> +Composed all(Predicate pred = Predicate()) { + return Composed(Filter(std::move(negate(pred))), IsEmpty()); +} + template> diff --git a/folly/gen/test/BaseTest.cpp b/folly/gen/test/BaseTest.cpp index c25f40c7..6973def2 100644 --- a/folly/gen/test/BaseTest.cpp +++ b/folly/gen/test/BaseTest.cpp @@ -591,6 +591,18 @@ TEST(Gen, MaxBy) { EXPECT_EQ("eleven", gen | maxBy(&strlen)); } +TEST(Gen, Min) { + auto odds = seq(2,10) | filter([](int i){ return i % 2; }); + + EXPECT_EQ(3, odds | min); +} + +TEST(Gen, Max) { + auto odds = seq(2,10) | filter([](int i){ return i % 2; }); + + EXPECT_EQ(9, odds | max); +} + TEST(Gen, Append) { string expected = "facebook"; string actual = "face"; @@ -730,15 +742,27 @@ TEST(Gen, Get) { EXPECT_EQ(36, from(tuples) | get<2>() | sum); } +TEST(Gen, notEmpty) { + EXPECT_TRUE(seq(0) | notEmpty); + EXPECT_TRUE(seq(0, 1) | notEmpty); + EXPECT_TRUE(just(1) | notEmpty); + EXPECT_FALSE(gen::range(0, 0) | notEmpty); + EXPECT_FALSE(from({1}) | take(0) | notEmpty); + EXPECT_TRUE(seq(1, 3) | cycle | notEmpty); +} + +TEST(Gen, isEmpty) { + EXPECT_FALSE(seq(0) | isEmpty); + EXPECT_FALSE(seq(0, 1) | isEmpty); + EXPECT_FALSE(just(1) | isEmpty); + EXPECT_TRUE(gen::range(0, 0) | isEmpty); + EXPECT_TRUE(from({1}) | take(0) | isEmpty); + EXPECT_FALSE(seq(1, 3) | cycle | isEmpty); +} + TEST(Gen, Any) { - EXPECT_TRUE(seq(0) | any); - EXPECT_TRUE(seq(0, 1) | any); EXPECT_TRUE(seq(0, 10) | any([](int i) { return i == 7; })); EXPECT_FALSE(seq(0, 10) | any([](int i) { return i == 11; })); - - EXPECT_TRUE(from({1}) | any); - EXPECT_FALSE(gen::range(0, 0) | any); - EXPECT_FALSE(from({1}) | take(0) | any); } TEST(Gen, All) { diff --git a/folly/gen/test/ParallelBenchmark.cpp b/folly/gen/test/ParallelBenchmark.cpp index d6dcc25c..61f3c563 100644 --- a/folly/gen/test/ParallelBenchmark.cpp +++ b/folly/gen/test/ParallelBenchmark.cpp @@ -56,10 +56,10 @@ static auto primes = seq(1, 1 << 20) | filter(isPrimeSlow) | as(); static auto isPrime = [](int n) { - return !(from(primes) + return from(primes) | until([&](int d) { return d * d > n; }) | filter([&](int d) { return 0 == n % d; }) - | any); + | isEmpty; }; static auto factors = [](int n) { -- 2.34.1