2 * Copyright 2015 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 #ifndef FOLLY_GEN_BASE_H
18 #error This file may only be included from folly/gen/Base.h
21 // Ignore shadowing warnings within this file, so includers can use -Wshadow.
22 #pragma GCC diagnostic push
23 #pragma GCC diagnostic ignored "-Wshadow"
25 namespace folly { namespace gen {
28 * ArgumentReference - For determining ideal argument type to receive a value.
31 struct ArgumentReference
32 : public std::conditional<
33 std::is_reference<T>::value,
34 T, // T& -> T&, T&& -> T&&, const T& -> const T&
35 typename std::conditional<std::is_const<T>::value,
36 T&, // const int -> const int&
43 * ReferencedSource - Generate values from an STL-like container using
44 * iterators from .begin() until .end(). Value type defaults to the type of
45 * *container->begin(). For std::vector<int>, this would be int&. Note that the
46 * value here is a reference, so the values in the vector will be passed by
47 * reference to downstream operators.
49 * This type is primarily used through the 'from' helper method, like:
51 * string& longestName = from(names)
52 * | maxBy([](string& s) { return s.size() });
54 template<class Container,
56 class ReferencedSource :
57 public GenImpl<Value, ReferencedSource<Container, Value>> {
58 Container* container_;
60 explicit ReferencedSource(Container* container)
61 : container_(container) {}
64 void foreach(Body&& body) const {
65 for (auto& value : *container_) {
66 body(std::forward<Value>(value));
70 template<class Handler>
71 bool apply(Handler&& handler) const {
72 for (auto& value : *container_) {
73 if (!handler(std::forward<Value>(value))) {
82 * CopiedSource - For producing values from eagerly from a sequence of values
83 * whose storage is owned by this class. Useful for preparing a generator for
84 * use after a source collection will no longer be available, or for when the
85 * values are specified literally with an initializer list.
87 * This type is primarily used through the 'fromCopy' function, like:
89 * auto sourceCopy = fromCopy(makeAVector());
90 * auto sum = sourceCopy | sum;
91 * auto max = sourceCopy | max;
93 * Though it is also used for the initializer_list specialization of from().
95 template<class StorageType,
98 public GenImpl<const StorageType&,
99 CopiedSource<StorageType, Container>> {
101 !std::is_reference<StorageType>::value, "StorageType must be decayed");
103 // Generator objects are often copied during normal construction as they are
104 // encapsulated by downstream generators. It would be bad if this caused
105 // a copy of the entire container each time, and since we're only exposing a
106 // const reference to the value, it's safe to share it between multiple
109 !std::is_reference<Container>::value,
110 "Can't copy into a reference");
111 std::shared_ptr<const Container> copy_;
113 typedef Container ContainerType;
115 template<class SourceContainer>
116 explicit CopiedSource(const SourceContainer& container)
117 : copy_(new Container(begin(container), end(container))) {}
119 explicit CopiedSource(Container&& container) :
120 copy_(new Container(std::move(container))) {}
122 // To enable re-use of cached results.
123 CopiedSource(const CopiedSource<StorageType, Container>& source)
124 : copy_(source.copy_) {}
127 void foreach(Body&& body) const {
128 for (const auto& value : *copy_) {
133 template<class Handler>
134 bool apply(Handler&& handler) const {
135 // The collection may be reused by others, we can't allow it to be changed.
136 for (const auto& value : *copy_) {
137 if (!handler(value)) {
146 * RangeSource - For producing values from a folly::Range. Useful for referring
147 * to a slice of some container.
149 * This type is primarily used through the 'from' function, like:
151 * auto rangeSource = from(folly::range(v.begin(), v.end()));
152 * auto sum = rangeSource | sum;
154 * Reminder: Be careful not to invalidate iterators when using ranges like this.
156 template<class Iterator>
157 class RangeSource : public GenImpl<typename Range<Iterator>::reference,
158 RangeSource<Iterator>> {
159 Range<Iterator> range_;
161 RangeSource() = default;
162 explicit RangeSource(Range<Iterator> range)
163 : range_(std::move(range))
166 template<class Handler>
167 bool apply(Handler&& handler) const {
168 for (auto& value : range_) {
169 if (!handler(value)) {
177 void foreach(Body&& body) const {
178 for (auto& value : range_) {
185 * Sequence - For generating values from beginning value, incremented along the
186 * way with the ++ and += operators. Iteration may continue indefinitely.
187 * Value type specified explicitly.
189 * This type is primarily used through the 'seq' and 'range' function, like:
191 * int total = seq(1, 10) | sum;
192 * auto indexes = range(0, 10);
193 * auto endless = seq(0); // 0, 1, 2, 3, ...
195 template<class Value, class SequenceImpl>
196 class Sequence : public GenImpl<const Value&, Sequence<Value, SequenceImpl>> {
197 static_assert(!std::is_reference<Value>::value &&
198 !std::is_const<Value>::value, "Value mustn't be const or ref.");
202 explicit Sequence(Value start, SequenceImpl impl)
203 : start_(std::move(start)), impl_(std::move(impl)) { }
205 template<class Handler>
206 bool apply(Handler&& handler) const {
207 for (Value current = start_; impl_.test(current); impl_.step(current)) {
208 if (!handler(current)) {
216 void foreach(Body&& body) const {
217 for (Value current = start_; impl_.test(current); impl_.step(current)) {
224 * Sequence implementations (range, sequence, infinite, with/without step)
226 template<class Value>
230 explicit RangeImpl(Value end) : end_(std::move(end)) { }
231 bool test(const Value& current) const { return current < end_; }
232 void step(Value& current) const { ++current; }
235 template<class Value, class Distance>
236 class RangeWithStepImpl {
240 explicit RangeWithStepImpl(Value end, Distance step)
241 : end_(std::move(end)), step_(std::move(step)) { }
242 bool test(const Value& current) const { return current < end_; }
243 void step(Value& current) const { current += step_; }
246 template<class Value>
250 explicit SeqImpl(Value end) : end_(std::move(end)) { }
251 bool test(const Value& current) const { return current <= end_; }
252 void step(Value& current) const { ++current; }
255 template<class Value, class Distance>
256 class SeqWithStepImpl {
260 explicit SeqWithStepImpl(Value end, Distance step)
261 : end_(std::move(end)), step_(std::move(step)) { }
262 bool test(const Value& current) const { return current <= end_; }
263 void step(Value& current) const { current += step_; }
266 template<class Value>
269 bool test(const Value& current) const { return true; }
270 void step(Value& current) const { ++current; }
274 * GenratorBuilder - Helper for GENERTATOR macro.
276 template<class Value>
277 struct GeneratorBuilder {
278 template<class Source,
279 class Yield = detail::Yield<Value, Source>>
280 Yield operator+(Source&& source) {
281 return Yield(std::forward<Source>(source));
286 * Yield - For producing values from a user-defined generator by way of a
289 template<class Value, class Source>
290 class Yield : public GenImpl<Value, Yield<Value, Source>> {
293 explicit Yield(Source source)
294 : source_(std::move(source)) {
297 template<class Handler>
298 bool apply(Handler&& handler) const {
300 auto body = [&](Value value) {
301 if (!handler(std::forward<Value>(value))) {
314 void foreach(Body&& body) const {
315 source_(std::forward<Body>(body));
319 template<class Value>
320 class Empty : public GenImpl<Value, Empty<Value>> {
322 template <class Handler>
323 bool apply(Handler&&) const {
327 template <class Body>
328 void foreach(Body&&) const {}
331 template <class Value>
332 class SingleReference : public GenImpl<Value&, SingleReference<Value>> {
333 static_assert(!std::is_reference<Value>::value,
334 "SingleReference requires non-ref types");
337 explicit SingleReference(Value& ref) : ptr_(&ref) {}
339 template <class Handler>
340 bool apply(Handler&& handler) const {
341 return handler(*ptr_);
344 template <class Body>
345 void foreach(Body&& body) const {
350 template <class Value>
351 class SingleCopy : public GenImpl<const Value&, SingleCopy<Value>> {
352 static_assert(!std::is_reference<Value>::value,
353 "SingleCopy requires non-ref types");
356 explicit SingleCopy(Value value) : value_(std::forward<Value>(value)) {}
358 template <class Handler>
359 bool apply(Handler&& handler) const {
360 return handler(value_);
363 template <class Body>
364 void foreach(Body&& body) const {
374 * Map - For producing a sequence of values by passing each value from a source
375 * collection through a predicate.
377 * This type is usually used through the 'map' or 'mapped' helper function:
379 * auto squares = seq(1, 10) | map(square) | asVector;
381 template<class Predicate>
382 class Map : public Operator<Map<Predicate>> {
387 explicit Map(Predicate pred)
388 : pred_(std::move(pred))
391 template<class Value,
393 class Result = typename ArgumentReference<
394 typename std::result_of<Predicate(Value)>::type
397 public GenImpl<Result, Generator<Value, Source, Result>> {
401 explicit Generator(Source source, const Predicate& pred)
402 : source_(std::move(source)), pred_(pred) {}
405 void foreach(Body&& body) const {
406 source_.foreach([&](Value value) {
407 body(pred_(std::forward<Value>(value)));
411 template<class Handler>
412 bool apply(Handler&& handler) const {
413 return source_.apply([&](Value value) {
414 return handler(pred_(std::forward<Value>(value)));
418 static constexpr bool infinite = Source::infinite;
421 template<class Source,
423 class Gen = Generator<Value, Source>>
424 Gen compose(GenImpl<Value, Source>&& source) const {
425 return Gen(std::move(source.self()), pred_);
428 template<class Source,
430 class Gen = Generator<Value, Source>>
431 Gen compose(const GenImpl<Value, Source>& source) const {
432 return Gen(source.self(), pred_);
438 * Filter - For filtering values from a source sequence by a predicate.
440 * This type is usually used through the 'filter' helper function, like:
442 * auto nonEmpty = from(strings)
443 * | filter([](const string& str) -> bool {
444 * return !str.empty();
447 template<class Predicate>
448 class Filter : public Operator<Filter<Predicate>> {
452 explicit Filter(Predicate pred)
453 : pred_(std::move(pred))
456 template<class Value,
458 class Generator : public GenImpl<Value, Generator<Value, Source>> {
462 explicit Generator(Source source, const Predicate& pred)
463 : source_(std::move(source)), pred_(pred) {}
466 void foreach(Body&& body) const {
467 source_.foreach([&](Value value) {
468 if (pred_(std::forward<Value>(value))) {
469 body(std::forward<Value>(value));
474 template<class Handler>
475 bool apply(Handler&& handler) const {
476 return source_.apply([&](Value value) -> bool {
477 if (pred_(std::forward<Value>(value))) {
478 return handler(std::forward<Value>(value));
484 static constexpr bool infinite = Source::infinite;
487 template<class Source,
489 class Gen = Generator<Value, Source>>
490 Gen compose(GenImpl<Value, Source>&& source) const {
491 return Gen(std::move(source.self()), pred_);
494 template<class Source,
496 class Gen = Generator<Value, Source>>
497 Gen compose(const GenImpl<Value, Source>& source) const {
498 return Gen(source.self(), pred_);
503 * Until - For producing values from a source until a predicate is satisfied.
505 * This type is usually used through the 'until' helper function, like:
507 * auto best = from(sortedItems)
508 * | until([](Item& item) { return item.score > 100; })
511 template<class Predicate>
512 class Until : public Operator<Until<Predicate>> {
516 explicit Until(Predicate pred)
517 : pred_(std::move(pred))
520 template<class Value,
522 class Generator : public GenImpl<Value, Generator<Value, Source>> {
526 explicit Generator(Source source, const Predicate& pred)
527 : source_(std::move(source)), pred_(pred) {}
529 template<class Handler>
530 bool apply(Handler&& handler) const {
531 bool cancelled = false;
532 source_.apply([&](Value value) -> bool {
533 if (pred_(value)) { // un-forwarded to disable move
536 if (!handler(std::forward<Value>(value))) {
546 template<class Source,
548 class Gen = Generator<Value, Source>>
549 Gen compose(GenImpl<Value, Source>&& source) const {
550 return Gen(std::move(source.self()), pred_);
553 template<class Source,
555 class Gen = Generator<Value, Source>>
556 Gen compose(const GenImpl<Value, Source>& source) const {
557 return Gen(source.self(), pred_);
560 // Theoretically an 'until' might stop an infinite
561 static constexpr bool infinite = false;
565 * Take - For producing up to N values from a source.
567 * This type is usually used through the 'take' helper function, like:
569 * auto best = from(docs)
570 * | orderByDescending(scoreDoc)
573 class Take : public Operator<Take> {
576 explicit Take(size_t count)
579 template<class Value,
582 public GenImpl<Value, Generator<Value, Source>> {
586 explicit Generator(Source source, size_t count)
587 : source_(std::move(source)) , count_(count) {}
589 template<class Handler>
590 bool apply(Handler&& handler) const {
591 if (count_ == 0) { return false; }
593 bool cancelled = false;
594 source_.apply([&](Value value) -> bool {
595 if (!handler(std::forward<Value>(value))) {
605 template<class Source,
607 class Gen = Generator<Value, Source>>
608 Gen compose(GenImpl<Value, Source>&& source) const {
609 return Gen(std::move(source.self()), count_);
612 template<class Source,
614 class Gen = Generator<Value, Source>>
615 Gen compose(const GenImpl<Value, Source>& source) const {
616 return Gen(source.self(), count_);
621 * Stride - For producing every Nth value from a source.
623 * This type is usually used through the 'stride' helper function, like:
625 * auto half = from(samples)
628 class Stride : public Operator<Stride> {
632 explicit Stride(size_t stride) : stride_(stride) {
634 throw std::invalid_argument("stride must not be 0");
638 template <class Value, class Source>
639 class Generator : public GenImpl<Value, Generator<Value, Source>> {
643 Generator(Source source, size_t stride)
644 : source_(std::move(source)), stride_(stride) {}
646 template <class Handler>
647 bool apply(Handler&& handler) const {
648 size_t distance = stride_;
649 return source_.apply([&](Value value)->bool {
650 if (++distance >= stride_) {
651 if (!handler(std::forward<Value>(value))) {
660 template <class Body>
661 void foreach(Body&& body) const {
662 size_t distance = stride_;
663 source_.foreach([&](Value value) {
664 if (++distance >= stride_) {
665 body(std::forward<Value>(value));
672 template <class Source, class Value, class Gen = Generator<Value, Source>>
673 Gen compose(GenImpl<Value, Source>&& source) const {
674 return Gen(std::move(source.self()), stride_);
677 template <class Source, class Value, class Gen = Generator<Value, Source>>
678 Gen compose(const GenImpl<Value, Source>& source) const {
679 return Gen(source.self(), stride_);
684 * Sample - For taking a random sample of N elements from a sequence
685 * (without replacement).
687 template<class Random>
688 class Sample : public Operator<Sample<Random>> {
692 explicit Sample(size_t count, Random rng)
693 : count_(count), rng_(std::move(rng)) {}
695 template<class Value,
698 class StorageType = typename std::decay<Value>::type>
700 public GenImpl<StorageType&&,
701 Generator<Value, Source, Rand, StorageType>> {
702 static_assert(!Source::infinite, "Cannot sample infinite source!");
703 // It's too easy to bite ourselves if random generator is only 16-bit
704 static_assert(Random::max() >= std::numeric_limits<int32_t>::max() - 1,
705 "Random number generator must support big values");
710 explicit Generator(Source source, size_t count, Random rng)
711 : source_(std::move(source)) , count_(count), rng_(std::move(rng)) {}
713 template<class Handler>
714 bool apply(Handler&& handler) const {
715 if (count_ == 0) { return false; }
716 std::vector<StorageType> v;
718 // use reservoir sampling to give each source value an equal chance
719 // of appearing in our output.
721 source_.foreach([&](Value value) -> void {
722 if (v.size() < count_) {
723 v.push_back(std::forward<Value>(value));
725 // alternatively, we could create a std::uniform_int_distribution
726 // instead of using modulus, but benchmarks show this has
727 // substantial overhead.
728 size_t index = rng_() % n;
729 if (index < v.size()) {
730 v[index] = std::forward<Value>(value);
736 // output is unsorted!
738 if (!handler(std::move(val))) {
746 template<class Source,
748 class Gen = Generator<Value, Source, Random>>
749 Gen compose(GenImpl<Value, Source>&& source) const {
750 return Gen(std::move(source.self()), count_, rng_);
753 template<class Source,
755 class Gen = Generator<Value, Source, Random>>
756 Gen compose(const GenImpl<Value, Source>& source) const {
757 return Gen(source.self(), count_, rng_);
762 * Skip - For skipping N items from the beginning of a source generator.
764 * This type is usually used through the 'skip' helper function, like:
766 * auto page = from(results)
767 * | skip(pageSize * startPage)
770 class Skip : public Operator<Skip> {
773 explicit Skip(size_t count)
776 template<class Value,
779 public GenImpl<Value, Generator<Value, Source>> {
783 explicit Generator(Source source, size_t count)
784 : source_(std::move(source)) , count_(count) {}
787 void foreach(Body&& body) const {
789 source_.foreach(body);
793 source_.foreach([&](Value value) {
797 body(std::forward<Value>(value));
802 template<class Handler>
803 bool apply(Handler&& handler) const {
805 return source_.apply(std::forward<Handler>(handler));
808 return source_.apply([&](Value value) -> bool {
813 return handler(std::forward<Value>(value));
817 static constexpr bool infinite = Source::infinite;
820 template<class Source,
822 class Gen = Generator<Value, Source>>
823 Gen compose(GenImpl<Value, Source>&& source) const {
824 return Gen(std::move(source.self()), count_);
827 template<class Source,
829 class Gen = Generator<Value, Source>>
830 Gen compose(const GenImpl<Value, Source>& source) const {
831 return Gen(source.self(), count_);
836 * Order - For ordering a sequence of values from a source by key.
837 * The key is extracted by the given selector functor, and this key is then
838 * compared using the specified comparator.
840 * This type is usually used through the 'order' helper function, like:
842 * auto closest = from(places)
843 * | orderBy([](Place& p) {
844 * return -distance(p.location, here);
848 template<class Selector, class Comparer>
849 class Order : public Operator<Order<Selector, Comparer>> {
855 explicit Order(Selector selector)
856 : selector_(std::move(selector))
859 Order(Selector selector,
861 : selector_(std::move(selector))
862 , comparer_(std::move(comparer))
865 template<class Value,
867 class StorageType = typename std::decay<Value>::type,
868 class Result = typename std::result_of<Selector(Value)>::type>
870 public GenImpl<StorageType&&,
871 Generator<Value, Source, StorageType, Result>> {
872 static_assert(!Source::infinite, "Cannot sort infinite source!");
877 typedef std::vector<StorageType> VectorType;
879 VectorType asVector() const {
880 auto comparer = [&](const StorageType& a, const StorageType& b) {
881 return comparer_(selector_(a), selector_(b));
883 auto vals = source_ | as<VectorType>();
884 std::sort(vals.begin(), vals.end(), comparer);
885 return std::move(vals);
888 Generator(Source source,
891 : source_(std::move(source)),
892 selector_(std::move(selector)),
893 comparer_(std::move(comparer)) {}
895 VectorType operator|(const Collect<VectorType>&) const {
899 VectorType operator|(const CollectTemplate<std::vector>&) const {
904 void foreach(Body&& body) const {
905 for (auto& value : asVector()) {
906 body(std::move(value));
910 template<class Handler>
911 bool apply(Handler&& handler) const {
912 auto comparer = [&](const StorageType& a, const StorageType& b) {
913 // swapped for minHeap
914 return comparer_(selector_(b), selector_(a));
916 auto heap = source_ | as<VectorType>();
917 std::make_heap(heap.begin(), heap.end(), comparer);
918 while (!heap.empty()) {
919 std::pop_heap(heap.begin(), heap.end(), comparer);
920 if (!handler(std::move(heap.back()))) {
929 template<class Source,
931 class Gen = Generator<Value, Source>>
932 Gen compose(GenImpl<Value, Source>&& source) const {
933 return Gen(std::move(source.self()), selector_, comparer_);
936 template<class Source,
938 class Gen = Generator<Value, Source>>
939 Gen compose(const GenImpl<Value, Source>& source) const {
940 return Gen(source.self(), selector_, comparer_);
945 * TypeAssertion - For verifying the exact type of the value produced by a
946 * generator. Useful for testing and debugging, and acts as a no-op at runtime.
947 * Pass-through at runtime. Used through the 'assert_type<>()' factory method
950 * auto c = from(vector) | assert_type<int&>() | sum;
953 template<class Expected>
954 class TypeAssertion : public Operator<TypeAssertion<Expected>> {
956 template<class Source, class Value>
957 const Source& compose(const GenImpl<Value, Source>& source) const {
958 static_assert(std::is_same<Expected, Value>::value,
959 "assert_type() check failed");
960 return source.self();
963 template<class Source, class Value>
964 Source&& compose(GenImpl<Value, Source>&& source) const {
965 static_assert(std::is_same<Expected, Value>::value,
966 "assert_type() check failed");
967 return std::move(source.self());
972 * Distinct - For filtering duplicates out of a sequence. A selector may be
973 * provided to generate a key to uniquify for each value.
975 * This type is usually used through the 'distinct' helper function, like:
977 * auto closest = from(results)
978 * | distinctBy([](Item& i) {
983 template<class Selector>
984 class Distinct : public Operator<Distinct<Selector>> {
987 Distinct() = default;
989 explicit Distinct(Selector selector)
990 : selector_(std::move(selector))
993 template<class Value,
995 class Generator : public GenImpl<Value, Generator<Value, Source>> {
999 typedef typename std::decay<Value>::type StorageType;
1001 // selector_ cannot be passed an rvalue or it would end up passing the husk
1002 // of a value to the downstream operators.
1003 typedef const StorageType& ParamType;
1005 typedef typename std::result_of<Selector(ParamType)>::type KeyType;
1006 typedef typename std::decay<KeyType>::type KeyStorageType;
1009 Generator(Source source,
1011 : source_(std::move(source)),
1012 selector_(std::move(selector)) {}
1014 template<class Body>
1015 void foreach(Body&& body) const {
1016 std::unordered_set<KeyStorageType> keysSeen;
1017 source_.foreach([&](Value value) {
1018 if (keysSeen.insert(selector_(ParamType(value))).second) {
1019 body(std::forward<Value>(value));
1024 template<class Handler>
1025 bool apply(Handler&& handler) const {
1026 std::unordered_set<KeyStorageType> keysSeen;
1027 return source_.apply([&](Value value) -> bool {
1028 if (keysSeen.insert(selector_(ParamType(value))).second) {
1029 return handler(std::forward<Value>(value));
1036 template<class Source,
1038 class Gen = Generator<Value, Source>>
1039 Gen compose(GenImpl<Value, Source>&& source) const {
1040 return Gen(std::move(source.self()), selector_);
1043 template<class Source,
1045 class Gen = Generator<Value, Source>>
1046 Gen compose(const GenImpl<Value, Source>& source) const {
1047 return Gen(source.self(), selector_);
1052 * Composer - Helper class for adapting pipelines into functors. Primarily used
1055 template<class Operators>
1059 explicit Composer(Operators op)
1060 : op_(std::move(op)) {}
1062 template<class Source,
1063 class Ret = decltype(std::declval<Operators>()
1064 .compose(std::declval<Source>()))>
1065 Ret operator()(Source&& source) const {
1066 return op_.compose(std::forward<Source>(source));
1071 * Batch - For producing fixed-size batches of each value from a source.
1073 * This type is usually used through the 'batch' helper function:
1078 * | map([](const std::vector<int>& batch) {
1079 * return from(batch) | sum;
1083 class Batch : public Operator<Batch> {
1086 explicit Batch(size_t batchSize)
1087 : batchSize_(batchSize) {
1088 if (batchSize_ == 0) {
1089 throw std::invalid_argument("Batch size must be non-zero!");
1093 template<class Value,
1095 class StorageType = typename std::decay<Value>::type,
1096 class VectorType = std::vector<StorageType>>
1098 public GenImpl<VectorType&,
1099 Generator<Value, Source, StorageType, VectorType>> {
1103 explicit Generator(Source source, size_t batchSize)
1104 : source_(std::move(source))
1105 , batchSize_(batchSize) {}
1107 template<class Handler>
1108 bool apply(Handler&& handler) const {
1110 batch_.reserve(batchSize_);
1111 bool shouldContinue = source_.apply([&](Value value) -> bool {
1112 batch_.push_back(std::forward<Value>(value));
1113 if (batch_.size() == batchSize_) {
1114 bool needMore = handler(batch_);
1118 // Always need more if the handler is not called.
1121 // Flush everything, if and only if `handler` hasn't returned false.
1122 if (shouldContinue && !batch_.empty()) {
1123 shouldContinue = handler(batch_);
1126 return shouldContinue;
1129 static constexpr bool infinite = Source::infinite;
1132 template<class Source,
1134 class Gen = Generator<Value, Source>>
1135 Gen compose(GenImpl<Value, Source>&& source) const {
1136 return Gen(std::move(source.self()), batchSize_);
1139 template<class Source,
1141 class Gen = Generator<Value, Source>>
1142 Gen compose(const GenImpl<Value, Source>& source) const {
1143 return Gen(source.self(), batchSize_);
1151 * FoldLeft - Left-associative functional fold. For producing an aggregate value
1152 * from a seed and a folder function. Useful for custom aggregators on a
1155 * This type is primarily used through the 'foldl' helper method, like:
1157 * double movingAverage = from(values)
1158 * | foldl(0.0, [](double avg, double sample) {
1159 * return sample * 0.1 + avg * 0.9;
1162 template<class Seed,
1164 class FoldLeft : public Operator<FoldLeft<Seed, Fold>> {
1168 FoldLeft() = default;
1171 : seed_(std::move(seed))
1172 , fold_(std::move(fold))
1175 template<class Source,
1177 Seed compose(const GenImpl<Value, Source>& source) const {
1178 static_assert(!Source::infinite, "Cannot foldl infinite source");
1180 source | [&](Value v) {
1181 accum = fold_(std::move(accum), std::forward<Value>(v));
1188 * First - For finding the first value in a sequence.
1190 * This type is primarily used through the 'first' static value, like:
1192 * int firstThreeDigitPrime = seq(100) | filter(isPrime) | first;
1194 class First : public Operator<First> {
1198 template<class Source,
1200 class StorageType = typename std::decay<Value>::type>
1201 StorageType compose(const GenImpl<Value, Source>& source) const {
1202 Optional<StorageType> accum;
1203 source | [&](Value v) -> bool {
1204 accum = std::forward<Value>(v);
1207 if (!accum.hasValue()) {
1208 throw EmptySequence();
1210 return std::move(accum.value());
1216 * Any - For determining whether any values in a sequence satisfy a predicate.
1218 * This type is primarily used through the 'any' static value, like:
1220 * bool any20xPrimes = seq(200, 210) | filter(isPrime) | any;
1222 * Note that it may also be used like so:
1224 * bool any20xPrimes = seq(200, 210) | any(isPrime);
1227 class Any : public Operator<Any> {
1231 template<class Source,
1233 bool compose(const GenImpl<Value, Source>& source) const {
1235 source | [&](Value v) -> bool {
1243 * Convenience function for use like:
1245 * bool found = gen | any([](int i) { return i * i > 100; });
1247 template<class Predicate,
1248 class Filter = Filter<Predicate>,
1249 class Composed = Composed<Filter, Any>>
1250 Composed operator()(Predicate pred) const {
1251 return Composed(Filter(std::move(pred)), Any());
1256 * All - For determining whether all values in a sequence satisfy a predicate.
1258 * This type is primarily used through the 'any' static value, like:
1260 * bool valid = from(input) | all(validate);
1262 * Note: Passing an empty sequence through 'all()' will always return true.
1264 template<class Predicate>
1265 class All : public Operator<All<Predicate>> {
1269 explicit All(Predicate pred)
1270 : pred_(std::move(pred))
1273 template<class Source,
1275 bool compose(const GenImpl<Value, Source>& source) const {
1276 static_assert(!Source::infinite, "Cannot call 'all' on infinite source");
1278 source | [&](Value v) -> bool {
1279 if (!pred_(std::forward<Value>(v))) {
1290 * Reduce - Functional reduce, for recursively combining values from a source
1291 * using a reducer function until there is only one item left. Useful for
1292 * combining values when an empty sequence doesn't make sense.
1294 * This type is primarily used through the 'reduce' helper method, like:
1296 * sring longest = from(names)
1297 * | reduce([](string&& best, string& current) {
1298 * return best.size() >= current.size() ? best : current;
1301 template<class Reducer>
1302 class Reduce : public Operator<Reduce<Reducer>> {
1306 explicit Reduce(Reducer reducer)
1307 : reducer_(std::move(reducer))
1310 template<class Source,
1312 class StorageType = typename std::decay<Value>::type>
1313 StorageType compose(const GenImpl<Value, Source>& source) const {
1314 Optional<StorageType> accum;
1315 source | [&](Value v) {
1316 if (accum.hasValue()) {
1317 accum = reducer_(std::move(accum.value()), std::forward<Value>(v));
1319 accum = std::forward<Value>(v);
1322 if (!accum.hasValue()) {
1323 throw EmptySequence();
1325 return accum.value();
1330 * Count - for simply counting the items in a collection.
1332 * This type is usually used through its singleton, 'count':
1334 * auto shortPrimes = seq(1, 100) | filter(isPrime) | count;
1336 class Count : public Operator<Count> {
1340 template<class Source,
1342 size_t compose(const GenImpl<Value, Source>& source) const {
1343 static_assert(!Source::infinite, "Cannot count infinite source");
1344 return foldl(size_t(0),
1345 [](size_t accum, Value v) {
1352 * Sum - For simply summing up all the values from a source.
1354 * This type is usually used through its singleton, 'sum':
1356 * auto gaussSum = seq(1, 100) | sum;
1358 class Sum : public Operator<Sum> {
1360 Sum() : Operator<Sum>() {}
1362 template<class Source,
1364 class StorageType = typename std::decay<Value>::type>
1365 StorageType compose(const GenImpl<Value, Source>& source) const {
1366 static_assert(!Source::infinite, "Cannot sum infinite source");
1367 return foldl(StorageType(0),
1368 [](StorageType&& accum, Value v) {
1369 return std::move(accum) + std::forward<Value>(v);
1375 * Contains - For testing whether a value matching the given value is contained
1378 * This type should be used through the 'contains' helper method, like:
1380 * bool contained = seq(1, 10) | map(square) | contains(49);
1382 template<class Needle>
1383 class Contains : public Operator<Contains<Needle>> {
1386 explicit Contains(Needle needle)
1387 : needle_(std::move(needle))
1390 template<class Source,
1392 class StorageType = typename std::decay<Value>::type>
1393 bool compose(const GenImpl<Value, Source>& source) const {
1394 static_assert(!Source::infinite,
1395 "Calling contains on an infinite source might cause "
1396 "an infinite loop.");
1397 return !(source | [this](Value value) {
1398 return !(needle_ == std::forward<Value>(value));
1404 * Min - For a value which minimizes a key, where the key is determined by a
1405 * given selector, and compared by given comparer.
1407 * This type is usually used through the singletone 'min' or through the helper
1408 * functions 'minBy' and 'maxBy'.
1410 * auto oldest = from(people)
1411 * | minBy([](Person& p) {
1412 * return p.dateOfBirth;
1415 template<class Selector,
1417 class Min : public Operator<Min<Selector, Comparer>> {
1423 explicit Min(Selector selector)
1424 : selector_(std::move(selector))
1427 Min(Selector selector,
1429 : selector_(std::move(selector))
1430 , comparer_(std::move(comparer))
1433 template<class Value,
1435 class StorageType = typename std::decay<Value>::type,
1436 class Key = typename std::decay<
1437 typename std::result_of<Selector(Value)>::type
1439 StorageType compose(const GenImpl<Value, Source>& source) const {
1440 Optional<StorageType> min;
1441 Optional<Key> minKey;
1442 source | [&](Value v) {
1443 Key key = selector_(std::forward<Value>(v));
1444 if (!minKey.hasValue() || comparer_(key, minKey.value())) {
1446 min = std::forward<Value>(v);
1449 if (!min.hasValue()) {
1450 throw EmptySequence();
1457 * Append - For collecting values from a source into a given output container
1460 * This type is usually used through the helper function 'appendTo', like:
1462 * vector<int64_t> ids;
1463 * from(results) | map([](Person& p) { return p.id })
1466 template<class Collection>
1467 class Append : public Operator<Append<Collection>> {
1468 Collection* collection_;
1470 explicit Append(Collection* collection)
1471 : collection_(collection)
1474 template<class Value,
1476 Collection& compose(const GenImpl<Value, Source>& source) const {
1477 source | [&](Value v) {
1478 collection_->insert(collection_->end(), std::forward<Value>(v));
1480 return *collection_;
1485 * Collect - For collecting values from a source in a collection of the desired
1488 * This type is usually used through the helper function 'as', like:
1490 * std::string upper = from(stringPiece)
1492 * | as<std::string>();
1494 template<class Collection>
1495 class Collect : public Operator<Collect<Collection>> {
1497 Collect() = default;
1499 template<class Value,
1501 class StorageType = typename std::decay<Value>::type>
1502 Collection compose(const GenImpl<Value, Source>& source) const {
1503 Collection collection;
1504 source | [&](Value v) {
1505 collection.insert(collection.end(), std::forward<Value>(v));
1513 * CollectTemplate - For collecting values from a source in a collection
1514 * constructed using the specified template type. Given the type of values
1515 * produced by the given generator, the collection type will be:
1516 * Container<Value, Allocator<Value>>
1518 * The allocator defaults to std::allocator, so this may be used for the STL
1519 * containers by simply using operators like 'as<set>', 'as<deque>',
1520 * 'as<vector>'. 'as', here is the helper method which is the usual means of
1521 * consturcting this operator.
1525 * set<string> uniqueNames = from(names) | as<set>();
1527 template<template<class, class> class Container,
1528 template<class> class Allocator>
1529 class CollectTemplate : public Operator<CollectTemplate<Container, Allocator>> {
1531 CollectTemplate() = default;
1533 template<class Value,
1535 class StorageType = typename std::decay<Value>::type,
1536 class Collection = Container<StorageType, Allocator<StorageType>>>
1537 Collection compose(const GenImpl<Value, Source>& source) const {
1538 Collection collection;
1539 source | [&](Value v) {
1540 collection.insert(collection.end(), std::forward<Value>(v));
1547 * Concat - For flattening generators of generators.
1549 * This type is usually used through the 'concat' static value, like:
1553 * | map([](Node& x) {
1554 * return from(x.neighbors)
1555 * | map([&](Node& y) {
1556 * return Edge(x, y);
1562 class Concat : public Operator<Concat> {
1566 template<class Inner,
1568 class InnerValue = typename std::decay<Inner>::type::ValueType>
1570 public GenImpl<InnerValue, Generator<Inner, Source, InnerValue>> {
1573 explicit Generator(Source source)
1574 : source_(std::move(source)) {}
1576 template<class Handler>
1577 bool apply(Handler&& handler) const {
1578 return source_.apply([&](Inner inner) -> bool {
1579 return inner.apply(std::forward<Handler>(handler));
1583 template<class Body>
1584 void foreach(Body&& body) const {
1585 source_.foreach([&](Inner inner) {
1586 inner.foreach(std::forward<Body>(body));
1590 static constexpr bool infinite = Source::infinite;
1593 template<class Value,
1595 class Gen = Generator<Value, Source>>
1596 Gen compose(GenImpl<Value, Source>&& source) const {
1597 return Gen(std::move(source.self()));
1600 template<class Value,
1602 class Gen = Generator<Value, Source>>
1603 Gen compose(const GenImpl<Value, Source>& source) const {
1604 return Gen(source.self());
1609 * RangeConcat - For flattening generators of iterables.
1611 * This type is usually used through the 'rconcat' static value, like:
1613 * map<int, vector<int>> adjacency;
1620 class RangeConcat : public Operator<RangeConcat> {
1622 RangeConcat() = default;
1624 template<class Range,
1626 class InnerValue = typename ValueTypeOfRange<Range>::RefType>
1628 : public GenImpl<InnerValue, Generator<Range, Source, InnerValue>> {
1631 explicit Generator(Source source)
1632 : source_(std::move(source)) {}
1634 template<class Body>
1635 void foreach(Body&& body) const {
1636 source_.foreach([&](Range range) {
1637 for (auto& value : range) {
1643 template<class Handler>
1644 bool apply(Handler&& handler) const {
1645 return source_.apply([&](Range range) -> bool {
1646 for (auto& value : range) {
1647 if (!handler(value)) {
1656 template<class Value,
1658 class Gen = Generator<Value, Source>>
1659 Gen compose(GenImpl<Value, Source>&& source) const {
1660 return Gen(std::move(source.self()));
1663 template<class Value,
1665 class Gen = Generator<Value, Source>>
1666 Gen compose(const GenImpl<Value, Source>& source) const {
1667 return Gen(source.self());
1673 * GuardImpl - For handling exceptions from downstream computation. Requires the
1674 * type of exception to catch, and handler function to invoke in the event of
1675 * the exception. Note that the handler may:
1676 * 1) return true to continue processing the sequence
1677 * 2) return false to end the sequence immediately
1678 * 3) throw, to pass the exception to the next catch
1679 * The handler must match the signature 'bool(Exception&, Value)'.
1681 * This type is used through the `guard` helper, like so:
1684 * = byLine(STDIN_FILENO)
1685 * | guard<std::runtime_error>([](std::runtime_error& e,
1687 * LOG(ERROR) << sp << ": " << e.str();
1688 * return true; // continue processing subsequent lines
1693 * TODO(tjackson): Rename this back to Guard.
1695 template<class Exception,
1697 class GuardImpl : public Operator<GuardImpl<Exception, ErrorHandler>> {
1698 ErrorHandler handler_;
1700 explicit GuardImpl(ErrorHandler handler) : handler_(std::move(handler)) {}
1702 template<class Value,
1704 class Generator : public GenImpl<Value, Generator<Value, Source>> {
1706 ErrorHandler handler_;
1708 explicit Generator(Source source,
1709 ErrorHandler handler)
1710 : source_(std::move(source)),
1711 handler_(std::move(handler)) {}
1713 template<class Handler>
1714 bool apply(Handler&& handler) const {
1715 return source_.apply([&](Value value) -> bool {
1717 handler(std::forward<Value>(value));
1719 } catch (Exception& e) {
1720 return handler_(e, std::forward<Value>(value));
1725 static constexpr bool infinite = Source::infinite;
1728 template<class Value,
1730 class Gen = Generator<Value, Source>>
1731 Gen compose(GenImpl<Value, Source>&& source) const {
1732 return Gen(std::move(source.self()), handler_);
1735 template<class Value,
1737 class Gen = Generator<Value, Source>>
1738 Gen compose(const GenImpl<Value, Source>& source) const {
1739 return Gen(source.self(), handler_);
1744 * Cycle - For repeating a sequence forever.
1746 * This type is usually used through the 'cycle' static value, like:
1753 class Cycle : public Operator<Cycle> {
1754 off_t limit_; // -1 for infinite
1759 explicit Cycle(off_t limit)
1762 template<class Value,
1764 class Generator : public GenImpl<Value, Generator<Value, Source>> {
1766 off_t limit_; // -1 for infinite
1768 explicit Generator(Source source, off_t limit)
1769 : source_(std::move(source))
1772 template<class Handler>
1773 bool apply(Handler&& handler) const {
1775 auto handler2 = [&](Value value) {
1776 cont = handler(std::forward<Value>(value));
1779 for (off_t count = 0; count != limit_; ++count) {
1781 source_.apply(handler2);
1789 // not actually infinite, since an empty generator will end the cycles.
1790 static constexpr bool infinite = Source::infinite;
1793 template<class Source,
1795 class Gen = Generator<Value, Source>>
1796 Gen compose(GenImpl<Value, Source>&& source) const {
1797 return Gen(std::move(source.self()), limit_);
1800 template<class Source,
1802 class Gen = Generator<Value, Source>>
1803 Gen compose(const GenImpl<Value, Source>& source) const {
1804 return Gen(source.self(), limit_);
1808 * Convenience function for use like:
1810 * auto tripled = gen | cycle(3);
1812 Cycle operator()(off_t limit) const {
1813 return Cycle(limit);
1818 * Dereference - For dereferencing a sequence of pointers while filtering out
1821 * This type is usually used through the 'dereference' static value, like:
1823 * auto refs = from(ptrs) | dereference;
1825 class Dereference : public Operator<Dereference> {
1827 Dereference() = default;
1829 template<class Value,
1831 class Result = decltype(*std::declval<Value>())>
1832 class Generator : public GenImpl<Result, Generator<Value, Source, Result>> {
1835 explicit Generator(Source source)
1836 : source_(std::move(source)) {}
1838 template<class Body>
1839 void foreach(Body&& body) const {
1840 source_.foreach([&](Value value) {
1842 return body(*value);
1847 template<class Handler>
1848 bool apply(Handler&& handler) const {
1849 return source_.apply([&](Value value) -> bool {
1851 return handler(*value);
1857 // not actually infinite, since an empty generator will end the cycles.
1858 static constexpr bool infinite = Source::infinite;
1861 template<class Source,
1863 class Gen = Generator<Value, Source>>
1864 Gen compose(GenImpl<Value, Source>&& source) const {
1865 return Gen(std::move(source.self()));
1868 template<class Source,
1870 class Gen = Generator<Value, Source>>
1871 Gen compose(const GenImpl<Value, Source>& source) const {
1872 return Gen(source.self());
1877 * Indirect - For producing a sequence of the addresses of the values in the
1880 * This type is usually used through the 'indirect' static value, like:
1882 * auto ptrs = from(refs) | indirect;
1884 class Indirect : public Operator<Indirect> {
1886 Indirect() = default;
1888 template <class Value,
1890 class Result = typename std::remove_reference<Value>::type*>
1891 class Generator : public GenImpl<Result, Generator<Value, Source, Result>> {
1893 static_assert(!std::is_rvalue_reference<Value>::value,
1894 "Cannot use indirect on an rvalue");
1897 explicit Generator(Source source) : source_(std::move(source)) {}
1899 template <class Body>
1900 void foreach (Body&& body) const {
1901 source_.foreach([&](Value value) {
1902 return body(&value);
1906 template <class Handler>
1907 bool apply(Handler&& handler) const {
1908 return source_.apply([&](Value value) -> bool {
1909 return handler(&value);
1913 // not actually infinite, since an empty generator will end the cycles.
1914 static constexpr bool infinite = Source::infinite;
1917 template <class Source, class Value, class Gen = Generator<Value, Source>>
1918 Gen compose(GenImpl<Value, Source>&& source) const {
1919 return Gen(std::move(source.self()));
1922 template <class Source, class Value, class Gen = Generator<Value, Source>>
1923 Gen compose(const GenImpl<Value, Source>& source) const {
1924 return Gen(source.self());
1931 * VirtualGen<T> - For wrapping template types in simple polymorphic wrapper.
1933 template<class Value>
1934 class VirtualGen : public GenImpl<Value, VirtualGen<Value>> {
1937 virtual ~WrapperBase() noexcept {}
1938 virtual bool apply(const std::function<bool(Value)>& handler) const = 0;
1939 virtual void foreach(const std::function<void(Value)>& body) const = 0;
1940 virtual std::unique_ptr<const WrapperBase> clone() const = 0;
1943 template<class Wrapped>
1944 class WrapperImpl : public WrapperBase {
1947 explicit WrapperImpl(Wrapped wrapped)
1948 : wrapped_(std::move(wrapped)) {
1951 virtual bool apply(const std::function<bool(Value)>& handler) const {
1952 return wrapped_.apply(handler);
1955 virtual void foreach(const std::function<void(Value)>& body) const {
1956 wrapped_.foreach(body);
1959 virtual std::unique_ptr<const WrapperBase> clone() const {
1960 return std::unique_ptr<const WrapperBase>(new WrapperImpl(wrapped_));
1964 std::unique_ptr<const WrapperBase> wrapper_;
1967 template <class Self>
1968 /* implicit */ VirtualGen(Self source)
1969 : wrapper_(new WrapperImpl<Self>(std::move(source))) {}
1971 VirtualGen(VirtualGen&& source) noexcept
1972 : wrapper_(std::move(source.wrapper_)) {}
1974 VirtualGen(const VirtualGen& source)
1975 : wrapper_(source.wrapper_->clone()) {}
1977 VirtualGen& operator=(const VirtualGen& source) {
1978 wrapper_.reset(source.wrapper_->clone());
1982 VirtualGen& operator=(VirtualGen&& source) noexcept {
1983 wrapper_= std::move(source.wrapper_);
1987 bool apply(const std::function<bool(Value)>& handler) const {
1988 return wrapper_->apply(handler);
1991 void foreach(const std::function<void(Value)>& body) const {
1992 wrapper_->foreach(body);
1997 * non-template operators, statically defined to avoid the need for anything but
2000 static const detail::Sum sum{};
2002 static const detail::Count count{};
2004 static const detail::First first{};
2007 * Use directly for detecting any values, or as a function to detect values
2008 * which pass a predicate:
2010 * auto nonempty = g | any;
2011 * auto evens = g | any(even);
2013 static const detail::Any any{};
2015 static const detail::Min<Identity, Less> min{};
2017 static const detail::Min<Identity, Greater> max{};
2019 static const detail::Order<Identity> order{};
2021 static const detail::Distinct<Identity> distinct{};
2023 static const detail::Map<Move> move{};
2025 static const detail::Concat concat{};
2027 static const detail::RangeConcat rconcat{};
2030 * Use directly for infinite sequences, or as a function to limit cycle count.
2032 * auto forever = g | cycle;
2033 * auto thrice = g | cycle(3);
2035 static const detail::Cycle cycle{};
2037 static const detail::Dereference dereference{};
2039 static const detail::Indirect indirect{};
2041 inline detail::Take take(size_t count) {
2042 return detail::Take(count);
2045 inline detail::Stride stride(size_t s) {
2046 return detail::Stride(s);
2049 template<class Random = std::default_random_engine>
2050 inline detail::Sample<Random> sample(size_t count, Random rng = Random()) {
2051 return detail::Sample<Random>(count, std::move(rng));
2054 inline detail::Skip skip(size_t count) {
2055 return detail::Skip(count);
2058 inline detail::Batch batch(size_t batchSize) {
2059 return detail::Batch(batchSize);
2064 #pragma GCC diagnostic pop