From c1c28d91824242c8fb8d792b63e0072d078b85c8 Mon Sep 17 00:00:00 2001 From: Mike Curtiss Date: Fri, 1 Mar 2013 22:27:56 -0800 Subject: [PATCH] HACK: New Gen operators: zip, interleave Summary: Zip: inspired by python's zip() o Combine a generator with the contents of a container to form a tuple. Note that we combine with a container (and not another generator) because of a fundamental constraint in how control-flow in Generators works. Containers give us 90% of the utility without all the hassle. We could theoretically also add a version of zip where the extra source is generated concurrently in another thread. Interleave: similar to zip, but inspired by Clojure's interleave() o Instead of creating a tuple like zip, just flatten the values. Added some tuple creation/concatenation functions. These are mostly meant as a way to enable zip'ing multiple containers together into an N-tuple. (My variadic-fu was not strong enough to get this working within a single Zip function). Test Plan: Added unit-tests Reviewed By: tjackson@fb.com FB internal diff: D740518 --- folly/experimental/CombineGen-inl.h | 217 ++++++++++++++++++++++++++++ folly/experimental/CombineGen.h | 47 ++++++ folly/experimental/Gen-inl.h | 2 +- folly/experimental/test/GenTest.cpp | 133 ++++++++++++++++- 4 files changed, 397 insertions(+), 2 deletions(-) create mode 100644 folly/experimental/CombineGen-inl.h create mode 100644 folly/experimental/CombineGen.h diff --git a/folly/experimental/CombineGen-inl.h b/folly/experimental/CombineGen-inl.h new file mode 100644 index 00000000..bb3ba6b6 --- /dev/null +++ b/folly/experimental/CombineGen-inl.h @@ -0,0 +1,217 @@ +/* + * Copyright 2013 Facebook, Inc. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef FOLLY_COMBINEGEN_H_ +#error This file may only be included from folly/experimental/CombineGen.h +#endif + +#include +#include +#include +#include + +namespace folly { +namespace gen { +namespace detail { + +/** + * Interleave + * + * Alternate values from a sequence with values from a sequence container. + * Stops once we run out of values from either source. + */ +template +class Interleave : public Operator> { + // see comment about copies in CopiedSource + const std::shared_ptr container_; + public: + explicit Interleave(Container container) + : container_(new Container(std::move(container))) {} + + template + class Generator : public GenImpl> { + Source source_; + const std::shared_ptr container_; + typedef const typename Container::value_type& ConstRefType; + + static_assert(std::is_same::value, + "Only matching types may be interleaved"); + public: + explicit Generator(Source source, + const std::shared_ptr container) + : source_(std::move(source)), + container_(container) { } + + template + bool apply(Handler&& handler) const { + auto iter = container_->begin(); + return source_.apply([&](const Value& value) -> bool { + if (iter == container_->end()) { + return false; + } + if (!handler(value)) { + return false; + } + if (!handler(*iter)) { + return false; + } + iter++; + return true; + }); + } + }; + + template> + Gen compose(GenImpl&& source) const { + return Gen(std::move(source.self()), container_); + } + + template> + Gen compose(const GenImpl& source) const { + return Gen(source.self(), container_); + } +}; + +/** + * Zip + * + * Combine inputs from Source with values from a sequence container by merging + * them into a tuple. + * + */ +template +class Zip : public Operator> { + // see comment about copies in CopiedSource + const std::shared_ptr container_; + public: + explicit Zip(Container container) + : container_(new Container(std::move(container))) {} + + template::type, + typename std::decay::type>> + class Generator : public GenImpl> { + Source source_; + const std::shared_ptr container_; + public: + explicit Generator(Source source, + const std::shared_ptr container) + : source_(std::move(source)), + container_(container) { } + + template + bool apply(Handler&& handler) const { + auto iter = container_->begin(); + return (source_.apply([&](Value1 value) -> bool { + if (iter == container_->end()) { + return false; + } + if (!handler(std::make_tuple(std::forward(value), *iter))) { + return false; + } + ++iter; + return true; + })); + } + }; + + template> + Gen compose(GenImpl&& source) const { + return Gen(std::move(source.self()), container_); + } + + template> + Gen compose(const GenImpl& source) const { + return Gen(source.self(), container_); + } +}; + +template +auto add_to_tuple(std::tuple t1, std::tuple t2) -> +std::tuple { + return std::tuple_cat(std::move(t1), std::move(t2)); +} + +template +auto add_to_tuple(std::tuple t1, Type2&& t2) -> +decltype(std::tuple_cat(std::move(t1), + std::make_tuple(std::forward(t2)))) { + return std::tuple_cat(std::move(t1), + std::make_tuple(std::forward(t2))); +} + +template +auto add_to_tuple(Type1&& t1, std::tuple t2) -> +decltype(std::tuple_cat(std::make_tuple(std::forward(t1)), + std::move(t2))) { + return std::tuple_cat(std::make_tuple(std::forward(t1)), + std::move(t2)); +} + +template +auto add_to_tuple(Type1&& t1, Type2&& t2) -> +decltype(std::make_tuple(std::forward(t1), + std::forward(t2))) { + return std::make_tuple(std::forward(t1), + std::forward(t2)); +} + +// Merges a 2-tuple into a single tuple (get<0> could already be a tuple) +class MergeTuples { + public: + template + auto operator()(Tuple&& value) const -> + decltype(add_to_tuple(std::get<0>(std::forward(value)), + std::get<1>(std::forward(value)))) { + static_assert(std::tuple_size< + typename std::remove_reference::type + >::value == 2, + "Can only merge tuples of size 2"); + return add_to_tuple(std::get<0>(std::forward(value)), + std::get<1>(std::forward(value))); + } +}; + +} // namespace detail + +static const detail::Map tuple_flatten; + +// TODO(mcurtiss): support zip() for N>1 operands. Because of variadic problems, +// this might not be easily possible until gcc4.8 is available. +template::type>> +Zip zip(Source&& source) { + return Zip(std::forward(source)); +} + +} // namespace gen +} // namespace folly diff --git a/folly/experimental/CombineGen.h b/folly/experimental/CombineGen.h new file mode 100644 index 00000000..89585be6 --- /dev/null +++ b/folly/experimental/CombineGen.h @@ -0,0 +1,47 @@ +/* + * Copyright 2013 Facebook, Inc. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef FOLLY_COMBINEGEN_H_ +#define FOLLY_COMBINEGEN_H_ + +#include "folly/experimental/Gen.h" + +namespace folly { +namespace gen { +namespace detail { + +template +class Interleave; + +template +class Zip; + +} // namespace detail + +template::type, + class Interleave = detail::Interleave> +Interleave interleave(Source2&& source2) { + return Interleave(std::forward(source2)); +} + +} // namespace gen +} // namespace folly + +#include "folly/experimental/CombineGen-inl.h" + +#endif /* FOLLY_COMBINEGEN_H_ */ + diff --git a/folly/experimental/Gen-inl.h b/folly/experimental/Gen-inl.h index f916878c..39d63fce 100644 --- a/folly/experimental/Gen-inl.h +++ b/folly/experimental/Gen-inl.h @@ -1828,4 +1828,4 @@ inline detail::Skip skip(size_t count) { return detail::Skip(count); } -}} //folly::gen::detail +}} //folly::gen diff --git a/folly/experimental/test/GenTest.cpp b/folly/experimental/test/GenTest.cpp index 8c7b826f..d732e97e 100644 --- a/folly/experimental/test/GenTest.cpp +++ b/folly/experimental/test/GenTest.cpp @@ -22,8 +22,10 @@ #include #include "folly/experimental/Gen.h" #include "folly/experimental/StringGen.h" +#include "folly/experimental/CombineGen.h" #include "folly/experimental/FileGen.h" #include "folly/experimental/TestUtil.h" +#include "folly/FBString.h" #include "folly/FBVector.h" #include "folly/Format.h" #include "folly/dynamic.h" @@ -38,7 +40,6 @@ using std::vector; using std::string; using std::tuple; using std::make_tuple; -//using std::unordered_map; #define EXPECT_SAME(A, B) \ static_assert(std::is_same::value, "Mismatched: " #A ", " #B) @@ -300,6 +301,136 @@ TEST(Gen, Until) { EXPECT_EQ(31, gen | count); } +auto even = [](int i) -> bool { return i % 2 == 0; }; +auto odd = [](int i) -> bool { return i % 2 == 1; }; + +TEST(CombineGen, Interleave) { + { // large (infinite) base, small container + auto base = seq(1) | filter(odd); + auto toInterleave = seq(1, 6) | filter(even); + auto interleaved = base | interleave(toInterleave | as()); + EXPECT_EQ(interleaved | as(), vector({1, 2, 3, 4, 5, 6})); + } + { // small base, large container + auto base = seq(1) | filter(odd) | take(3); + auto toInterleave = seq(1) | filter(even) | take(50); + auto interleaved = base | interleave(toInterleave | as()); + EXPECT_EQ(interleaved | as(), + vector({1, 2, 3, 4, 5, 6})); + } +} + +TEST(CombineGen, Zip) { + auto base0 = seq(1); + // We rely on std::move(fbvector) emptying the source vector + auto zippee = fbvector{"one", "two", "three"}; + { + auto combined = base0 + | zip(zippee) + | as(); + ASSERT_EQ(combined.size(), 3); + EXPECT_EQ(std::get<0>(combined[0]), 1); + EXPECT_EQ(std::get<1>(combined[0]), "one"); + EXPECT_EQ(std::get<0>(combined[1]), 2); + EXPECT_EQ(std::get<1>(combined[1]), "two"); + EXPECT_EQ(std::get<0>(combined[2]), 3); + EXPECT_EQ(std::get<1>(combined[2]), "three"); + ASSERT_FALSE(zippee.empty()); + EXPECT_FALSE(zippee.front().empty()); // shouldn't have been move'd + } + + { // same as top, but using std::move. + auto combined = base0 + | zip(std::move(zippee)) + | as(); + ASSERT_EQ(combined.size(), 3); + EXPECT_EQ(std::get<0>(combined[0]), 1); + EXPECT_TRUE(zippee.empty()); + } + + { // same as top, but base is truncated + auto baseFinite = seq(1) | take(1); + auto combined = baseFinite + | zip(vector{"one", "two", "three"}) + | as(); + ASSERT_EQ(combined.size(), 1); + EXPECT_EQ(std::get<0>(combined[0]), 1); + EXPECT_EQ(std::get<1>(combined[0]), "one"); + } +} + +TEST(CombineGen, TupleFlatten) { + vector> intStringTupleVec{ + tuple{1, "1"}, + tuple{2, "2"}, + tuple{3, "3"}, + }; + + vector> charTupleVec{ + tuple{'A'}, + tuple{'B'}, + tuple{'C'}, + tuple{'D'}, + }; + + vector doubleVec{ + 1.0, + 4.0, + 9.0, + 16.0, + 25.0, + }; + + auto zipped1 = from(intStringTupleVec) + | zip(charTupleVec) + | assert_type, tuple>>() + | as(); + EXPECT_EQ(std::get<0>(zipped1[0]), std::make_tuple(1, "1")); + EXPECT_EQ(std::get<1>(zipped1[0]), std::make_tuple('A')); + + auto zipped2 = from(zipped1) + | tuple_flatten + | assert_type&&>() + | as(); + ASSERT_EQ(zipped2.size(), 3); + EXPECT_EQ(zipped2[0], std::make_tuple(1, "1", 'A')); + + auto zipped3 = from(charTupleVec) + | zip(intStringTupleVec) + | tuple_flatten + | assert_type&&>() + | as(); + ASSERT_EQ(zipped3.size(), 3); + EXPECT_EQ(zipped3[0], std::make_tuple('A', 1, "1")); + + auto zipped4 = from(intStringTupleVec) + | zip(doubleVec) + | tuple_flatten + | assert_type&&>() + | as(); + ASSERT_EQ(zipped4.size(), 3); + EXPECT_EQ(zipped4[0], std::make_tuple(1, "1", 1.0)); + + auto zipped5 = from(doubleVec) + | zip(doubleVec) + | assert_type>() + | tuple_flatten // essentially a no-op + | assert_type&&>() + | as(); + ASSERT_EQ(zipped5.size(), 5); + EXPECT_EQ(zipped5[0], std::make_tuple(1.0, 1.0)); + + auto zipped6 = from(intStringTupleVec) + | zip(charTupleVec) + | tuple_flatten + | zip(doubleVec) + | tuple_flatten + | assert_type&&>() + | as(); + ASSERT_EQ(zipped6.size(), 3); + EXPECT_EQ(zipped6[0], std::make_tuple(1, "1", 'A', 1.0)); +} + TEST(Gen, Composed) { // Operator, Operator auto valuesOf = -- 2.34.1