2 * Copyright 2013 Facebook, Inc.
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
8 * http://www.apache.org/licenses/LICENSE-2.0
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
17 namespace folly { namespace gen {
20 * IsCompatibleSignature - Trait type for testing whether a given Functor
21 * matches an expected signature.
24 * IsCompatibleSignature<FunctorType, bool(int, float)>::value
26 template<class Candidate, class Expected>
27 class IsCompatibleSignature {
28 static constexpr bool value = false;
31 template<class Candidate,
34 class IsCompatibleSignature<Candidate, ExpectedReturn(ArgTypes...)> {
37 decltype(std::declval<F>()(std::declval<ArgTypes>()...)),
38 bool good = std::is_same<ExpectedReturn, ActualReturn>::value>
39 static constexpr bool testArgs(int* p) {
44 static constexpr bool testArgs(...) {
48 static constexpr bool value = testArgs<Candidate>(nullptr);
52 * ArgumentReference - For determining ideal argument type to receive a value.
55 struct ArgumentReference :
56 public std::conditional<std::is_reference<T>::value,
57 T, // T& -> T&, T&& -> T&&, const T& -> const T&
58 typename std::conditional<
59 std::is_const<T>::value,
60 T&, // const int -> const int&
65 * FBounded - Helper type for the curiously recurring template pattern, used
66 * heavily here to enable inlining and obviate virtual functions
70 const Self& self() const {
71 return *static_cast<const Self*>(this);
75 return *static_cast<Self*>(this);
80 * Operator - Core abstraction of an operation which may be applied to a
81 * generator. All operators implement a method compose(), which takes a
82 * generator and produces an output generator.
85 class Operator : public FBounded<Self> {
88 * compose() - Must be implemented by child class to compose a new Generator
89 * out of a given generator. This function left intentionally unimplemented.
91 template<class Source,
93 class ResultGen = void>
94 ResultGen compose(const GenImpl<Value, Source>& source) const;
98 Operator(const Operator&) = default;
99 Operator(Operator&&) = default;
103 * operator|() - For composing two operators without binding it to a
104 * particular generator.
108 class Composed = detail::Composed<Left, Right>>
109 Composed operator|(const Operator<Left>& left,
110 const Operator<Right>& right) {
111 return Composed(left.self(), right.self());
116 class Composed = detail::Composed<Left, Right>>
117 Composed operator|(const Operator<Left>& left,
118 Operator<Right>&& right) {
119 return Composed(left.self(), std::move(right.self()));
124 class Composed = detail::Composed<Left, Right>>
125 Composed operator|(Operator<Left>&& left,
126 const Operator<Right>& right) {
127 return Composed(std::move(left.self()), right.self());
132 class Composed = detail::Composed<Left, Right>>
133 Composed operator|(Operator<Left>&& left,
134 Operator<Right>&& right) {
135 return Composed(std::move(left.self()), std::move(right.self()));
139 * GenImpl - Core abstraction of a generator, an object which produces values by
140 * passing them to a given handler lambda. All generator implementations must
141 * implement apply(). foreach() may also be implemented to special case the
142 * condition where the entire sequence is consumed.
144 template<class Value,
146 class GenImpl : public FBounded<Self> {
148 // To prevent slicing
150 GenImpl(const GenImpl&) = default;
151 GenImpl(GenImpl&&) = default;
154 typedef Value ValueType;
155 typedef typename std::decay<Value>::type StorageType;
158 * apply() - Send all values produced by this generator to given
159 * handler until the handler returns false. Returns false if and only if the
160 * handler returns false. Note: It should return true even if it completes
161 * (without the handler returning false), as 'Chain' uses the return value of
162 * apply to determine if it should process the second object in its chain.
164 template<class Handler>
165 bool apply(Handler&& handler) const;
168 * foreach() - Send all values produced by this generator to given lambda.
171 void foreach(Body&& body) const {
172 this->self().apply([&](Value value) -> bool {
173 static_assert(!infinite, "Cannot call foreach on infinite GenImpl");
174 body(std::forward<Value>(value));
179 // Child classes should override if the sequence generated is *definitely*
180 // infinite. 'infinite' may be false_type for some infinite sequences
181 // (due the the Halting Problem).
182 static constexpr bool infinite = false;
185 template<class LeftValue,
189 class Chain = detail::Chain<LeftValue, Left, Right>>
190 Chain operator+(const GenImpl<LeftValue, Left>& left,
191 const GenImpl<RightValue, Right>& right) {
193 std::is_same<LeftValue, RightValue>::value,
194 "Generators may ony be combined if Values are the exact same type.");
195 return Chain(left.self(), right.self());
198 template<class LeftValue,
202 class Chain = detail::Chain<LeftValue, Left, Right>>
203 Chain operator+(const GenImpl<LeftValue, Left>& left,
204 GenImpl<RightValue, Right>&& right) {
206 std::is_same<LeftValue, RightValue>::value,
207 "Generators may ony be combined if Values are the exact same type.");
208 return Chain(left.self(), std::move(right.self()));
211 template<class LeftValue,
215 class Chain = detail::Chain<LeftValue, Left, Right>>
216 Chain operator+(GenImpl<LeftValue, Left>&& left,
217 const GenImpl<RightValue, Right>& right) {
219 std::is_same<LeftValue, RightValue>::value,
220 "Generators may ony be combined if Values are the exact same type.");
221 return Chain(std::move(left.self()), right.self());
224 template<class LeftValue,
228 class Chain = detail::Chain<LeftValue, Left, Right>>
229 Chain operator+(GenImpl<LeftValue, Left>&& left,
230 GenImpl<RightValue, Right>&& right) {
232 std::is_same<LeftValue, RightValue>::value,
233 "Generators may ony be combined if Values are the exact same type.");
234 return Chain(std::move(left.self()), std::move(right.self()));
238 * operator|() which enables foreach-like usage:
239 * gen | [](Value v) -> void {...};
241 template<class Value,
244 typename std::enable_if<
245 IsCompatibleSignature<Handler, void(Value)>::value>::type
246 operator|(const GenImpl<Value, Gen>& gen, Handler&& handler) {
247 static_assert(!Gen::infinite,
248 "Cannot pull all values from an infinite sequence.");
249 gen.self().foreach(std::forward<Handler>(handler));
253 * operator|() which enables foreach-like usage with 'break' support:
254 * gen | [](Value v) -> bool { return shouldContinue(); };
256 template<class Value,
259 typename std::enable_if<
260 IsCompatibleSignature<Handler, bool(Value)>::value, bool>::type
261 operator|(const GenImpl<Value, Gen>& gen, Handler&& handler) {
262 return gen.self().apply(std::forward<Handler>(handler));
266 * operator|() for composing generators with operators, similar to boosts' range
268 * gen | map(square) | sum
270 template<class Value,
273 auto operator|(const GenImpl<Value, Gen>& gen, const Operator<Op>& op) ->
274 decltype(op.self().compose(gen.self())) {
275 return op.self().compose(gen.self());
278 template<class Value,
281 auto operator|(GenImpl<Value, Gen>&& gen, const Operator<Op>& op) ->
282 decltype(op.self().compose(std::move(gen.self()))) {
283 return op.self().compose(std::move(gen.self()));
289 * ReferencedSource - Generate values from an STL-like container using
290 * iterators from .begin() until .end(). Value type defaults to the type of
291 * *container->begin(). For std::vector<int>, this would be int&. Note that the
292 * value here is a reference, so the values in the vector will be passed by
293 * reference to downstream operators.
295 * This type is primarily used through the 'from' helper method, like:
297 * string& longestName = from(names)
298 * | maxBy([](string& s) { return s.size() });
300 template<class Container,
302 class ReferencedSource :
303 public GenImpl<Value, ReferencedSource<Container, Value>> {
304 Container* container_;
306 explicit ReferencedSource(Container* container)
307 : container_(container) {}
310 void foreach(Body&& body) const {
311 for (auto& value : *container_) {
312 body(std::forward<Value>(value));
316 template<class Handler>
317 bool apply(Handler&& handler) const {
318 for (auto& value : *container_) {
319 if (!handler(std::forward<Value>(value))) {
328 * CopiedSource - For producing values from eagerly from a sequence of values
329 * whose storage is owned by this class. Useful for preparing a generator for
330 * use after a source collection will no longer be available, or for when the
331 * values are specified literally with an initializer list.
333 * This type is primarily used through the 'fromCopy' function, like:
335 * auto sourceCopy = fromCopy(makeAVector());
336 * auto sum = sourceCopy | sum;
337 * auto max = sourceCopy | max;
339 * Though it is also used for the initializer_list specialization of from().
341 template<class StorageType,
344 public GenImpl<const StorageType&,
345 CopiedSource<StorageType, Container>> {
347 !std::is_reference<StorageType>::value, "StorageType must be decayed");
349 // Generator objects are often copied during normal construction as they are
350 // encapsulated by downstream generators. It would be bad if this caused
351 // a copy of the entire container each time, and since we're only exposing a
352 // const reference to the value, it's safe to share it between multiple
355 !std::is_reference<Container>::value,
356 "Can't copy into a reference");
357 std::shared_ptr<const Container> copy_;
359 typedef Container ContainerType;
361 template<class SourceContainer>
362 explicit CopiedSource(const SourceContainer& container)
363 : copy_(new Container(begin(container), end(container))) {}
365 explicit CopiedSource(Container&& container) :
366 copy_(new Container(std::move(container))) {}
368 // To enable re-use of cached results.
369 CopiedSource(const CopiedSource<StorageType, Container>& source)
370 : copy_(source.copy_) {}
373 void foreach(Body&& body) const {
374 for (const auto& value : *copy_) {
379 template<class Handler>
380 bool apply(Handler&& handler) const {
381 // The collection may be reused by others, we can't allow it to be changed.
382 for (const auto& value : *copy_) {
383 if (!handler(value)) {
392 * Sequence - For generating values from beginning value, incremented along the
393 * way with the ++ and += operators. Iteration may continue indefinitely by
394 * setting the 'endless' template parameter to true. If set to false, iteration
395 * will stop when value reaches 'end', either inclusively or exclusively,
396 * depending on the template parameter 'endInclusive'. Value type specified
399 * This type is primarily used through the 'seq' and 'range' function, like:
401 * int total = seq(1, 10) | sum;
402 * auto indexes = range(0, 10);
404 template<class Value,
407 class Sequence : public GenImpl<const Value&,
408 Sequence<Value, endless, endInclusive>> {
409 static_assert(!std::is_reference<Value>::value &&
410 !std::is_const<Value>::value, "Value mustn't be const or ref.");
411 Value bounds_[endless ? 1 : 2];
413 explicit Sequence(Value begin)
414 : bounds_{std::move(begin)} {
415 static_assert(endless, "Must supply 'end'");
418 Sequence(Value begin,
420 : bounds_{std::move(begin), std::move(end)} {}
422 template<class Handler>
423 bool apply(Handler&& handler) const {
424 Value value = bounds_[0];
425 for (;endless || value < bounds_[1]; ++value) {
426 const Value& arg = value;
431 if (endInclusive && value == bounds_[1]) {
432 const Value& arg = value;
441 void foreach(Body&& body) const {
442 Value value = bounds_[0];
443 for (;endless || value < bounds_[1]; ++value) {
444 const Value& arg = value;
447 if (endInclusive && value == bounds_[1]) {
448 const Value& arg = value;
453 static constexpr bool infinite = endless;
457 * Chain - For concatenating the values produced by two Generators.
459 * This type is primarily used through using '+' to combine generators, like:
461 * auto nums = seq(1, 10) + seq(20, 30);
462 * int total = nums | sum;
464 template<class Value, class First, class Second>
465 class Chain : public GenImpl<Value,
466 Chain<Value, First, Second>> {
470 explicit Chain(First first, Second second)
471 : first_(std::move(first))
472 , second_(std::move(second)) {}
474 template<class Handler>
475 bool apply(Handler&& handler) const {
476 return first_.apply(std::forward<Handler>(handler))
477 && second_.apply(std::forward<Handler>(handler));
481 void foreach(Body&& body) const {
482 first_.foreach(std::forward<Body>(body));
483 second_.foreach(std::forward<Body>(body));
486 static constexpr bool infinite = First::infinite || Second::infinite;
490 * GenratorBuilder - Helper for GENERTATOR macro.
492 template<class Value>
493 struct GeneratorBuilder {
494 template<class Source,
495 class Yield = detail::Yield<Value, Source>>
496 Yield operator+(Source&& source) {
497 return Yield(std::forward<Source>(source));
502 * Yield - For producing values from a user-defined generator by way of a
505 template<class Value, class Source>
506 class Yield : public GenImpl<Value, Yield<Value, Source>> {
509 explicit Yield(Source source)
510 : source_(std::move(source)) {
513 template<class Handler>
514 bool apply(Handler&& handler) const {
516 auto body = [&](Value value) {
517 if (!handler(std::forward<Value>(value))) {
530 void foreach(Body&& body) const {
531 source_(std::forward<Body>(body));
541 * Map - For producing a sequence of values by passing each value from a source
542 * collection through a predicate.
544 * This type is usually used through the 'map' or 'mapped' helper function:
546 * auto squares = seq(1, 10) | map(square) | asVector;
548 template<class Predicate>
549 class Map : public Operator<Map<Predicate>> {
554 explicit Map(Predicate pred)
555 : pred_(std::move(pred))
558 template<class Value,
560 class Result = typename ArgumentReference<
561 typename std::result_of<Predicate(Value)>::type
564 public GenImpl<Result, Generator<Value, Source, Result>> {
568 explicit Generator(Source source, const Predicate& pred)
569 : source_(std::move(source)), pred_(pred) {}
572 void foreach(Body&& body) const {
573 source_.foreach([&](Value value) {
574 body(pred_(std::forward<Value>(value)));
578 template<class Handler>
579 bool apply(Handler&& handler) const {
580 return source_.apply([&](Value value) {
581 return handler(pred_(std::forward<Value>(value)));
585 static constexpr bool infinite = Source::infinite;
588 template<class Source,
590 class Gen = Generator<Value, Source>>
591 Gen compose(GenImpl<Value, Source>&& source) const {
592 return Gen(std::move(source.self()), pred_);
595 template<class Source,
597 class Gen = Generator<Value, Source>>
598 Gen compose(const GenImpl<Value, Source>& source) const {
599 return Gen(source.self(), pred_);
605 * Filter - For filtering values from a source sequence by a predicate.
607 * This type is usually used through the 'filter' helper function, like:
609 * auto nonEmpty = from(strings)
610 * | filter([](const string& str) -> bool {
611 * return !str.empty();
614 template<class Predicate>
615 class Filter : public Operator<Filter<Predicate>> {
619 explicit Filter(Predicate pred)
620 : pred_(std::move(pred))
623 template<class Value,
625 class Generator : public GenImpl<Value, Generator<Value, Source>> {
629 explicit Generator(Source source, const Predicate& pred)
630 : source_(std::move(source)), pred_(pred) {}
633 void foreach(Body&& body) const {
634 source_.foreach([&](Value value) {
635 if (pred_(std::forward<Value>(value))) {
636 body(std::forward<Value>(value));
641 template<class Handler>
642 bool apply(Handler&& handler) const {
643 return source_.apply([&](Value value) -> bool {
644 if (pred_(std::forward<Value>(value))) {
645 return handler(std::forward<Value>(value));
651 static constexpr bool infinite = Source::infinite;
654 template<class Source,
656 class Gen = Generator<Value, Source>>
657 Gen compose(GenImpl<Value, Source>&& source) const {
658 return Gen(std::move(source.self()), pred_);
661 template<class Source,
663 class Gen = Generator<Value, Source>>
664 Gen compose(const GenImpl<Value, Source>& source) const {
665 return Gen(source.self(), pred_);
670 * Until - For producing values from a source until a predicate is satisfied.
672 * This type is usually used through the 'until' helper function, like:
674 * auto best = from(sortedItems)
675 * | until([](Item& item) { return item.score > 100; })
678 template<class Predicate>
679 class Until : public Operator<Until<Predicate>> {
683 explicit Until(Predicate pred)
684 : pred_(std::move(pred))
687 template<class Value,
689 class Result = typename std::result_of<Predicate(Value)>::type>
691 public GenImpl<Result, Generator<Value, Source, Result>> {
695 explicit Generator(Source source, const Predicate& pred)
696 : source_(std::move(source)), pred_(pred) {}
698 template<class Handler>
699 bool apply(Handler&& handler) const {
700 return source_.apply([&](Value value) -> bool {
701 return !pred_(std::forward<Value>(value))
702 && handler(std::forward<Value>(value));
707 template<class Source,
709 class Gen = Generator<Value, Source>>
710 Gen compose(GenImpl<Value, Source>&& source) const {
711 return Gen(std::move(source.self()), pred_);
714 template<class Source,
716 class Gen = Generator<Value, Source>>
717 Gen compose(const GenImpl<Value, Source>& source) const {
718 return Gen(source.self(), pred_);
721 // Theoretically an 'until' might stop an infinite
722 static constexpr bool infinite = false;
726 * Take - For producing up to N values from a source.
728 * This type is usually used through the 'take' helper function, like:
730 * auto best = from(docs)
731 * | orderByDescending(scoreDoc)
734 class Take : public Operator<Take> {
737 explicit Take(size_t count)
740 template<class Value,
743 public GenImpl<Value, Generator<Value, Source>> {
747 explicit Generator(Source source, size_t count)
748 : source_(std::move(source)) , count_(count) {}
750 template<class Handler>
751 bool apply(Handler&& handler) const {
752 if (count_ == 0) { return false; }
754 return source_.apply([&](Value value) -> bool {
755 if (!handler(std::forward<Value>(value))) {
763 template<class Source,
765 class Gen = Generator<Value, Source>>
766 Gen compose(GenImpl<Value, Source>&& source) const {
767 return Gen(std::move(source.self()), count_);
770 template<class Source,
772 class Gen = Generator<Value, Source>>
773 Gen compose(const GenImpl<Value, Source>& source) const {
774 return Gen(source.self(), count_);
779 * Sample - For taking a random sample of N elements from a sequence
780 * (without replacement).
782 template<class Random>
783 class Sample : public Operator<Sample<Random>> {
787 explicit Sample(size_t count, Random rng)
788 : count_(count), rng_(std::move(rng)) {}
790 template<class Value,
793 class StorageType = typename std::decay<Value>::type>
795 public GenImpl<StorageType&&,
796 Generator<Value, Source, Rand, StorageType>> {
797 static_assert(!Source::infinite, "Cannot sample infinite source!");
798 // It's too easy to bite ourselves if random generator is only 16-bit
799 static_assert(Random::max() >= std::numeric_limits<int32_t>::max() - 1,
800 "Random number generator must support big values");
805 explicit Generator(Source source, size_t count, Random rng)
806 : source_(std::move(source)) , count_(count), rng_(std::move(rng)) {}
808 template<class Handler>
809 bool apply(Handler&& handler) const {
810 if (count_ == 0) { return false; }
811 std::vector<StorageType> v;
813 // use reservoir sampling to give each source value an equal chance
814 // of appearing in our output.
816 source_.foreach([&](Value value) -> void {
817 if (v.size() < count_) {
818 v.push_back(std::forward<Value>(value));
820 // alternatively, we could create a std::uniform_int_distribution
821 // instead of using modulus, but benchmarks show this has
822 // substantial overhead.
823 size_t index = rng_() % n;
824 if (index < v.size()) {
825 v[index] = std::forward<Value>(value);
831 // output is unsorted!
833 if (!handler(std::move(val))) {
841 template<class Source,
843 class Gen = Generator<Value, Source, Random>>
844 Gen compose(GenImpl<Value, Source>&& source) const {
845 return Gen(std::move(source.self()), count_, rng_);
848 template<class Source,
850 class Gen = Generator<Value, Source, Random>>
851 Gen compose(const GenImpl<Value, Source>& source) const {
852 return Gen(source.self(), count_, rng_);
857 * Skip - For skipping N items from the beginning of a source generator.
859 * This type is usually used through the 'skip' helper function, like:
861 * auto page = from(results)
862 * | skip(pageSize * startPage)
865 class Skip : public Operator<Skip> {
868 explicit Skip(size_t count)
871 template<class Value,
874 public GenImpl<Value, Generator<Value, Source>> {
878 explicit Generator(Source source, size_t count)
879 : source_(std::move(source)) , count_(count) {}
882 void foreach(Body&& body) const {
884 source_.foreach(body);
888 source_.foreach([&](Value value) {
892 body(std::forward<Value>(value));
897 template<class Handler>
898 bool apply(Handler&& handler) const {
900 return source_.apply(handler);
903 return source_.apply([&](Value value) -> bool {
908 return handler(std::forward<Value>(value));
912 static constexpr bool infinite = Source::infinite;
915 template<class Source,
917 class Gen = Generator<Value, Source>>
918 Gen compose(GenImpl<Value, Source>&& source) const {
919 return Gen(std::move(source.self()), count_);
922 template<class Source,
924 class Gen = Generator<Value, Source>>
925 Gen compose(const GenImpl<Value, Source>& source) const {
926 return Gen(source.self(), count_);
931 * Order - For ordering a sequence of values from a source by key.
932 * The key is extracted by the given selector functor, and this key is then
933 * compared using the specified comparator.
935 * This type is usually used through the 'order' helper function, like:
937 * auto closest = from(places)
938 * | orderBy([](Place& p) {
939 * return -distance(p.location, here);
943 template<class Selector, class Comparer>
944 class Order : public Operator<Order<Selector, Comparer>> {
950 explicit Order(Selector selector)
951 : selector_(std::move(selector))
954 Order(Selector selector,
956 : selector_(std::move(selector))
957 , comparer_(std::move(comparer))
960 template<class Value,
962 class StorageType = typename std::decay<Value>::type,
963 class Result = typename std::result_of<Selector(Value)>::type>
965 public GenImpl<StorageType&&,
966 Generator<Value, Source, StorageType, Result>> {
967 static_assert(!Source::infinite, "Cannot sort infinite source!");
972 typedef std::vector<StorageType> VectorType;
974 VectorType asVector() const {
975 auto comparer = [&](const StorageType& a, const StorageType& b) {
976 return comparer_(selector_(a), selector_(b));
978 auto vals = source_ | as<VectorType>();
979 std::sort(vals.begin(), vals.end(), comparer);
980 return std::move(vals);
983 Generator(Source source,
986 : source_(std::move(source)),
987 selector_(std::move(selector)),
988 comparer_(std::move(comparer)) {}
990 VectorType operator|(const Collect<VectorType>&) const {
994 VectorType operator|(const CollectTemplate<std::vector>&) const {
999 void foreach(Body&& body) const {
1000 for (auto& value : asVector()) {
1001 body(std::move(value));
1005 template<class Handler>
1006 bool apply(Handler&& handler) const {
1007 auto comparer = [&](const StorageType& a, const StorageType& b) {
1008 // swapped for minHeap
1009 return comparer_(selector_(b), selector_(a));
1011 auto heap = source_ | as<VectorType>();
1012 std::make_heap(heap.begin(), heap.end(), comparer);
1013 while (!heap.empty()) {
1014 std::pop_heap(heap.begin(), heap.end(), comparer);
1015 if (!handler(std::move(heap.back()))) {
1024 template<class Source,
1026 class Gen = Generator<Value, Source>>
1027 Gen compose(GenImpl<Value, Source>&& source) const {
1028 return Gen(std::move(source.self()), selector_, comparer_);
1031 template<class Source,
1033 class Gen = Generator<Value, Source>>
1034 Gen compose(const GenImpl<Value, Source>& source) const {
1035 return Gen(source.self(), selector_, comparer_);
1040 * Distinct - For filtering duplicates out of a sequence. A selector may be
1041 * provided to generate a key to uniquify for each value.
1043 * This type is usually used through the 'distinct' helper function, like:
1045 * auto closest = from(results)
1046 * | distinctBy([](Item& i) {
1051 template<class Selector>
1052 class Distinct : public Operator<Distinct<Selector>> {
1057 explicit Distinct(Selector selector)
1058 : selector_(std::move(selector))
1061 template<class Value,
1063 class Generator : public GenImpl<Value, Generator<Value, Source>> {
1067 typedef typename std::decay<Value>::type StorageType;
1069 // selector_ cannot be passed an rvalue or it would end up passing the husk
1070 // of a value to the downstream operators.
1071 typedef const StorageType& ParamType;
1073 typedef typename std::result_of<Selector(ParamType)>::type KeyType;
1074 typedef typename std::decay<KeyType>::type KeyStorageType;
1077 Generator(Source source,
1079 : source_(std::move(source)),
1080 selector_(std::move(selector)) {}
1082 template<class Body>
1083 void foreach(Body&& body) const {
1084 std::unordered_set<KeyStorageType> keysSeen;
1085 source_.foreach([&](Value value) {
1086 if (keysSeen.insert(selector_(ParamType(value))).second) {
1087 body(std::forward<Value>(value));
1092 template<class Handler>
1093 bool apply(Handler&& handler) const {
1094 std::unordered_set<KeyStorageType> keysSeen;
1095 return source_.apply([&](Value value) -> bool {
1096 if (keysSeen.insert(selector_(ParamType(value))).second) {
1097 return handler(std::forward<Value>(value));
1104 template<class Source,
1106 class Gen = Generator<Value, Source>>
1107 Gen compose(GenImpl<Value, Source>&& source) const {
1108 return Gen(std::move(source.self()), selector_);
1111 template<class Source,
1113 class Gen = Generator<Value, Source>>
1114 Gen compose(const GenImpl<Value, Source>& source) const {
1115 return Gen(source.self(), selector_);
1120 * Composed - For building up a pipeline of operations to perform, absent any
1121 * particular source generator. Useful for building up custom pipelines.
1123 * This type is usually used by just piping two operators together:
1125 * auto valuesOf = filter([](Optional<int>& o) { return o.hasValue(); })
1126 * | map([](Optional<int>& o) -> int& { return o.value(); });
1128 * auto valuesIncluded = from(optionals) | valuesOf | as<vector>();
1130 template<class First,
1132 class Composed : public Operator<Composed<First, Second>> {
1138 Composed(First first, Second second)
1139 : first_(std::move(first))
1140 , second_(std::move(second)) {}
1142 template<class Source,
1144 class FirstRet = decltype(std::declval<First>()
1145 .compose(std::declval<Source>())),
1146 class SecondRet = decltype(std::declval<Second>()
1147 .compose(std::declval<FirstRet>()))>
1148 SecondRet compose(const GenImpl<Value, Source>& source) const {
1149 return second_.compose(first_.compose(source.self()));
1152 template<class Source,
1154 class FirstRet = decltype(std::declval<First>()
1155 .compose(std::declval<Source>())),
1156 class SecondRet = decltype(std::declval<Second>()
1157 .compose(std::declval<FirstRet>()))>
1158 SecondRet compose(GenImpl<Value, Source>&& source) const {
1159 return second_.compose(first_.compose(std::move(source.self())));
1168 * FoldLeft - Left-associative functional fold. For producing an aggregate value
1169 * from a seed and a folder function. Useful for custom aggregators on a
1172 * This type is primarily used through the 'foldl' helper method, like:
1174 * double movingAverage = from(values)
1175 * | foldl(0.0, [](double avg, double sample) {
1176 * return sample * 0.1 + avg * 0.9;
1179 template<class Seed,
1181 class FoldLeft : public Operator<FoldLeft<Seed, Fold>> {
1188 : seed_(std::move(seed))
1189 , fold_(std::move(fold))
1192 template<class Source,
1194 Seed compose(const GenImpl<Value, Source>& source) const {
1195 static_assert(!Source::infinite, "Cannot foldl infinite source");
1197 source | [&](Value v) {
1198 accum = fold_(std::move(accum), std::forward<Value>(v));
1205 * First - For finding the first value in a sequence.
1207 * This type is primarily used through the 'first' static value, like:
1209 * int firstThreeDigitPrime = seq(100) | filter(isPrime) | first;
1211 class First : public Operator<First> {
1215 template<class Source,
1217 class StorageType = typename std::decay<Value>::type>
1218 StorageType compose(const GenImpl<Value, Source>& source) const {
1219 Optional<StorageType> accum;
1220 source | [&](Value v) -> bool {
1221 accum = std::forward<Value>(v);
1224 if (!accum.hasValue()) {
1225 throw EmptySequence();
1227 return std::move(accum.value());
1233 * Any - For determining whether any values in a sequence satisfy a predicate.
1235 * This type is primarily used through the 'any' static value, like:
1237 * bool any20xPrimes = seq(200, 210) | filter(isPrime) | any;
1239 * Note that it may also be used like so:
1241 * bool any20xPrimes = seq(200, 210) | any(isPrime);
1244 class Any : public Operator<Any> {
1248 template<class Source,
1250 bool compose(const GenImpl<Value, Source>& source) const {
1252 source | [&](Value v) -> bool {
1260 * Convenience function for use like:
1262 * bool found = gen | any([](int i) { return i * i > 100; });
1264 template<class Predicate,
1265 class Filter = Filter<Predicate>,
1266 class Composed = Composed<Filter, Any>>
1267 Composed operator()(Predicate pred) const {
1268 return Composed(Filter(std::move(pred)), Any());
1273 * All - For determining whether all values in a sequence satisfy a predicate.
1275 * This type is primarily used through the 'any' static value, like:
1277 * bool valid = from(input) | all(validate);
1279 * Note: Passing an empty sequence through 'all()' will always return true.
1281 template<class Predicate>
1282 class All : public Operator<All<Predicate>> {
1286 explicit All(Predicate pred)
1287 : pred_(std::move(pred))
1290 template<class Source,
1292 bool compose(const GenImpl<Value, Source>& source) const {
1293 static_assert(!Source::infinite, "Cannot call 'all' on infinite source");
1295 source | [&](Value v) -> bool {
1296 if (!pred_(std::forward<Value>(v))) {
1307 * Reduce - Functional reduce, for recursively combining values from a source
1308 * using a reducer function until there is only one item left. Useful for
1309 * combining values when an empty sequence doesn't make sense.
1311 * This type is primarily used through the 'reduce' helper method, like:
1313 * sring longest = from(names)
1314 * | reduce([](string&& best, string& current) {
1315 * return best.size() >= current.size() ? best : current;
1318 template<class Reducer>
1319 class Reduce : public Operator<Reduce<Reducer>> {
1323 explicit Reduce(Reducer reducer)
1324 : reducer_(std::move(reducer))
1327 template<class Source,
1329 class StorageType = typename std::decay<Value>::type>
1330 StorageType compose(const GenImpl<Value, Source>& source) const {
1331 Optional<StorageType> accum;
1332 source | [&](Value v) {
1333 if (accum.hasValue()) {
1334 accum = reducer_(std::move(accum.value()), std::forward<Value>(v));
1336 accum = std::forward<Value>(v);
1339 if (!accum.hasValue()) {
1340 throw EmptySequence();
1342 return accum.value();
1347 * Count - for simply counting the items in a collection.
1349 * This type is usually used through its singleton, 'count':
1351 * auto shortPrimes = seq(1, 100) | filter(isPrime) | count;
1353 class Count : public Operator<Count> {
1357 template<class Source,
1359 size_t compose(const GenImpl<Value, Source>& source) const {
1360 static_assert(!Source::infinite, "Cannot count infinite source");
1361 return foldl(size_t(0),
1362 [](size_t accum, Value v) {
1369 * Sum - For simply summing up all the values from a source.
1371 * This type is usually used through its singleton, 'sum':
1373 * auto gaussSum = seq(1, 100) | sum;
1375 class Sum : public Operator<Sum> {
1377 Sum() : Operator<Sum>() {}
1379 template<class Source,
1381 class StorageType = typename std::decay<Value>::type>
1382 StorageType compose(const GenImpl<Value, Source>& source) const {
1383 static_assert(!Source::infinite, "Cannot sum infinite source");
1384 return foldl(StorageType(0),
1385 [](StorageType&& accum, Value v) {
1386 return std::move(accum) + std::forward<Value>(v);
1392 * Contains - For testing whether a value matching the given value is contained
1395 * This type should be used through the 'contains' helper method, like:
1397 * bool contained = seq(1, 10) | map(square) | contains(49);
1399 template<class Needle>
1400 class Contains : public Operator<Contains<Needle>> {
1403 explicit Contains(Needle needle)
1404 : needle_(std::move(needle))
1407 template<class Source,
1409 class StorageType = typename std::decay<Value>::type>
1410 bool compose(const GenImpl<Value, Source>& source) const {
1411 static_assert(!Source::infinite,
1412 "Calling contains on an infinite source might cause "
1413 "an infinite loop.");
1414 return !(source | [this](Value value) {
1415 return !(needle_ == std::forward<Value>(value));
1421 * Min - For a value which minimizes a key, where the key is determined by a
1422 * given selector, and compared by given comparer.
1424 * This type is usually used through the singletone 'min' or through the helper
1425 * functions 'minBy' and 'maxBy'.
1427 * auto oldest = from(people)
1428 * | minBy([](Person& p) {
1429 * return p.dateOfBirth;
1432 template<class Selector,
1434 class Min : public Operator<Min<Selector, Comparer>> {
1440 explicit Min(Selector selector)
1441 : selector_(std::move(selector))
1444 Min(Selector selector,
1446 : selector_(std::move(selector))
1447 , comparer_(std::move(comparer))
1450 template<class Value,
1452 class StorageType = typename std::decay<Value>::type,
1453 class Key = typename std::decay<
1454 typename std::result_of<Selector(Value)>::type
1456 StorageType compose(const GenImpl<Value, Source>& source) const {
1457 Optional<StorageType> min;
1458 Optional<Key> minKey;
1459 source | [&](Value v) {
1460 Key key = selector_(std::forward<Value>(v));
1461 if (!minKey.hasValue() || comparer_(key, minKey.value())) {
1463 min = std::forward<Value>(v);
1466 if (!min.hasValue()) {
1467 throw EmptySequence();
1474 * Append - For collecting values from a source into a given output container
1477 * This type is usually used through the helper function 'appendTo', like:
1479 * vector<int64_t> ids;
1480 * from(results) | map([](Person& p) { return p.id })
1483 template<class Collection>
1484 class Append : public Operator<Append<Collection>> {
1485 Collection* collection_;
1487 explicit Append(Collection* collection)
1488 : collection_(collection)
1491 template<class Value,
1493 Collection& compose(const GenImpl<Value, Source>& source) const {
1494 source | [&](Value v) {
1495 collection_->insert(collection_->end(), std::forward<Value>(v));
1497 return *collection_;
1502 * Collect - For collecting values from a source in a collection of the desired
1505 * This type is usually used through the helper function 'as', like:
1507 * std::string upper = from(stringPiece)
1509 * | as<std::string>();
1511 template<class Collection>
1512 class Collect : public Operator<Collect<Collection>> {
1516 template<class Value,
1518 class StorageType = typename std::decay<Value>::type>
1519 Collection compose(const GenImpl<Value, Source>& source) const {
1520 Collection collection;
1521 source | [&](Value v) {
1522 collection.insert(collection.end(), std::forward<Value>(v));
1530 * CollectTemplate - For collecting values from a source in a collection
1531 * constructed using the specified template type. Given the type of values
1532 * produced by the given generator, the collection type will be:
1533 * Container<Value, Allocator<Value>>
1535 * The allocator defaults to std::allocator, so this may be used for the STL
1536 * containers by simply using operators like 'as<set>', 'as<deque>',
1537 * 'as<vector>'. 'as', here is the helper method which is the usual means of
1538 * consturcting this operator.
1542 * set<string> uniqueNames = from(names) | as<set>();
1544 template<template<class, class> class Container,
1545 template<class> class Allocator>
1546 class CollectTemplate : public Operator<CollectTemplate<Container, Allocator>> {
1548 CollectTemplate() { }
1550 template<class Value,
1552 class StorageType = typename std::decay<Value>::type,
1553 class Collection = Container<StorageType, Allocator<StorageType>>>
1554 Collection compose(const GenImpl<Value, Source>& source) const {
1555 Collection collection;
1556 source | [&](Value v) {
1557 collection.insert(collection.end(), std::forward<Value>(v));
1564 * Concat - For flattening generators of generators.
1566 * This type is usually used through the 'concat' static value, like:
1570 * | map([](Node& x) {
1571 * return from(x.neighbors)
1572 * | map([&](Node& y) {
1573 * return Edge(x, y);
1579 class Concat : public Operator<Concat> {
1583 template<class Inner,
1585 class InnerValue = typename std::decay<Inner>::type::ValueType>
1587 public GenImpl<InnerValue, Generator<Inner, Source, InnerValue>> {
1590 explicit Generator(Source source)
1591 : source_(std::move(source)) {}
1593 template<class Handler>
1594 bool apply(Handler&& handler) const {
1595 return source_.apply([&](Inner inner) -> bool {
1596 return inner.apply(std::forward<Handler>(handler));
1600 template<class Body>
1601 void foreach(Body&& body) const {
1602 source_.foreach([&](Inner inner) {
1603 inner.foreach(std::forward<Body>(body));
1607 static constexpr bool infinite = Source::infinite;
1610 template<class Value,
1612 class Gen = Generator<Value, Source>>
1613 Gen compose(GenImpl<Value, Source>&& source) const {
1614 return Gen(std::move(source.self()));
1617 template<class Value,
1619 class Gen = Generator<Value, Source>>
1620 Gen compose(const GenImpl<Value, Source>& source) const {
1621 return Gen(source.self());
1626 * RangeConcat - For flattening generators of iterables.
1628 * This type is usually used through the 'rconcat' static value, like:
1630 * map<int, vector<int>> adjacency;
1637 class RangeConcat : public Operator<RangeConcat> {
1641 template<class Source,
1643 class InnerValue = typename ValueTypeOfRange<Range>::RefType>
1645 : public GenImpl<InnerValue, Generator<Source, Range, InnerValue>> {
1648 explicit Generator(Source source)
1649 : source_(std::move(source)) {}
1651 template<class Body>
1652 void foreach(Body&& body) const {
1653 source_.foreach([&](Range range) {
1654 for (auto& value : range) {
1660 template<class Handler>
1661 bool apply(Handler&& handler) const {
1662 return source_.apply([&](Range range) -> bool {
1663 for (auto& value : range) {
1664 if (!handler(value)) {
1673 template<class Value,
1675 class Gen = Generator<Source, Value>>
1676 Gen compose(GenImpl<Value, Source>&& source) const {
1677 return Gen(std::move(source.self()));
1680 template<class Value,
1682 class Gen = Generator<Source, Value>>
1683 Gen compose(const GenImpl<Value, Source>& source) const {
1684 return Gen(source.self());
1691 * VirtualGen<T> - For wrapping template types in simple polymorphic wrapper.
1693 template<class Value>
1694 class VirtualGen : public GenImpl<Value, VirtualGen<Value>> {
1697 virtual ~WrapperBase() {}
1698 virtual bool apply(const std::function<bool(Value)>& handler) const = 0;
1699 virtual void foreach(const std::function<void(Value)>& body) const = 0;
1700 virtual std::unique_ptr<const WrapperBase> clone() const = 0;
1703 template<class Wrapped>
1704 class WrapperImpl : public WrapperBase {
1707 explicit WrapperImpl(Wrapped wrapped)
1708 : wrapped_(std::move(wrapped)) {
1711 virtual bool apply(const std::function<bool(Value)>& handler) const {
1712 return wrapped_.apply(handler);
1715 virtual void foreach(const std::function<void(Value)>& body) const {
1716 wrapped_.foreach(body);
1719 virtual std::unique_ptr<const WrapperBase> clone() const {
1720 return std::unique_ptr<const WrapperBase>(new WrapperImpl(wrapped_));
1724 std::unique_ptr<const WrapperBase> wrapper_;
1727 template<class Self>
1728 /* implicit */ VirtualGen(Self source)
1729 : wrapper_(new WrapperImpl<Self>(std::move(source)))
1732 VirtualGen(VirtualGen&& source)
1733 : wrapper_(std::move(source.wrapper_))
1736 VirtualGen(const VirtualGen& source)
1737 : wrapper_(source.wrapper_->clone())
1740 VirtualGen& operator=(const VirtualGen& source) {
1741 wrapper_.reset(source.wrapper_->clone());
1745 VirtualGen& operator=(VirtualGen&& source) {
1746 wrapper_= std::move(source.wrapper_);
1750 bool apply(const std::function<bool(Value)>& handler) const {
1751 return wrapper_->apply(handler);
1754 void foreach(const std::function<void(Value)>& body) const {
1755 wrapper_->foreach(body);
1760 * non-template operators, statically defined to avoid the need for anything but
1763 static const detail::Sum sum;
1765 static const detail::Count count;
1767 static const detail::First first;
1769 static const detail::Any any;
1771 static const detail::Min<Identity, Less> min;
1773 static const detail::Min<Identity, Greater> max;
1775 static const detail::Order<Identity> order;
1777 static const detail::Distinct<Identity> distinct;
1779 static const detail::Map<Move> move;
1781 static const detail::Concat concat;
1783 static const detail::RangeConcat rconcat;
1785 inline detail::Take take(size_t count) {
1786 return detail::Take(count);
1789 template<class Random = std::default_random_engine>
1790 inline detail::Sample<Random> sample(size_t count, Random rng = Random()) {
1791 return detail::Sample<Random>(count, std::move(rng));
1794 inline detail::Skip skip(size_t count) {
1795 return detail::Skip(count);
1798 }} //folly::gen::detail