2 * Copyright 2017 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 #include <folly/Portability.h>
23 // Ignore shadowing warnings within this file, so includers can use -Wshadow.
25 FOLLY_GCC_DISABLE_WARNING("-Wshadow")
31 * ArgumentReference - For determining ideal argument type to receive a value.
34 struct ArgumentReference
35 : public std::conditional<
36 std::is_reference<T>::value,
37 T, // T& -> T&, T&& -> T&&, const T& -> const T&
38 typename std::conditional<std::is_const<T>::value,
39 T&, // const int -> const int&
44 * Group - The output objects from the GroupBy operator
46 template <class Key, class Value>
47 class Group : public GenImpl<Value&&, Group<Key, Value>> {
49 static_assert(!std::is_reference<Key>::value &&
50 !std::is_reference<Value>::value,
51 "Key and Value must be decayed types");
53 typedef std::vector<Value> VectorType;
55 typedef Value ValueType;
57 Group(Key key, VectorType values)
58 : key_(std::move(key)), values_(std::move(values)) {}
60 const Key& key() const { return key_; }
62 size_t size() const { return values_.size(); }
63 const VectorType& values() const { return values_; }
64 VectorType& values() { return values_; }
66 VectorType operator|(const detail::Collect<VectorType>&) const {
70 VectorType operator|(const detail::CollectTemplate<std::vector>&) const {
75 void foreach(Body&& body) const {
76 for (auto& value : values_) {
77 body(std::move(value));
81 template <class Handler>
82 bool apply(Handler&& handler) const {
83 for (auto& value : values_) {
84 if (!handler(std::move(value))) {
91 // GroupBy only takes in finite generators, so we only have finite groups
92 static constexpr bool infinite = false;
96 mutable VectorType values_;
101 // Classes used for the implementation of Sources, Operators, and Sinks
104 ******************************* Sources ***************************************
108 * ReferencedSource - Generate values from an STL-like container using
109 * iterators from .begin() until .end(). Value type defaults to the type of
110 * *container->begin(). For std::vector<int>, this would be int&. Note that the
111 * value here is a reference, so the values in the vector will be passed by
112 * reference to downstream operators.
114 * This type is primarily used through the 'from' helper method, like:
116 * string& longestName = from(names)
117 * | maxBy([](string& s) { return s.size() });
119 template <class Container, class Value>
120 class ReferencedSource
121 : public GenImpl<Value, ReferencedSource<Container, Value>> {
122 Container* container_;
125 explicit ReferencedSource(Container* container) : container_(container) {}
127 template <class Body>
128 void foreach(Body&& body) const {
129 for (auto& value : *container_) {
130 body(std::forward<Value>(value));
134 template <class Handler>
135 bool apply(Handler&& handler) const {
136 for (auto& value : *container_) {
137 if (!handler(std::forward<Value>(value))) {
144 // from takes in a normal stl structure, which are all finite
145 static constexpr bool infinite = false;
149 * CopiedSource - For producing values from eagerly from a sequence of values
150 * whose storage is owned by this class. Useful for preparing a generator for
151 * use after a source collection will no longer be available, or for when the
152 * values are specified literally with an initializer list.
154 * This type is primarily used through the 'fromCopy' function, like:
156 * auto sourceCopy = fromCopy(makeAVector());
157 * auto sum = sourceCopy | sum;
158 * auto max = sourceCopy | max;
160 * Though it is also used for the initializer_list specialization of from().
162 template <class StorageType, class Container>
164 : public GenImpl<const StorageType&, CopiedSource<StorageType, Container>> {
165 static_assert(!std::is_reference<StorageType>::value,
166 "StorageType must be decayed");
169 // Generator objects are often copied during normal construction as they are
170 // encapsulated by downstream generators. It would be bad if this caused
171 // a copy of the entire container each time, and since we're only exposing a
172 // const reference to the value, it's safe to share it between multiple
174 static_assert(!std::is_reference<Container>::value,
175 "Can't copy into a reference");
176 std::shared_ptr<const Container> copy_;
179 typedef Container ContainerType;
181 template <class SourceContainer>
182 explicit CopiedSource(const SourceContainer& container)
183 : copy_(new Container(begin(container), end(container))) {}
185 explicit CopiedSource(Container&& container)
186 : copy_(new Container(std::move(container))) {}
188 // To enable re-use of cached results.
189 CopiedSource(const CopiedSource<StorageType, Container>& source)
190 : copy_(source.copy_) {}
192 template <class Body>
193 void foreach(Body&& body) const {
194 for (const auto& value : *copy_) {
199 template <class Handler>
200 bool apply(Handler&& handler) const {
201 // The collection may be reused by others, we can't allow it to be changed.
202 for (const auto& value : *copy_) {
203 if (!handler(value)) {
210 // from takes in a normal stl structure, which are all finite
211 static constexpr bool infinite = false;
215 * RangeSource - For producing values from a folly::Range. Useful for referring
216 * to a slice of some container.
218 * This type is primarily used through the 'from' function, like:
220 * auto rangeSource = from(folly::range(v.begin(), v.end()));
221 * auto sum = rangeSource | sum;
223 * Reminder: Be careful not to invalidate iterators when using ranges like this.
225 template <class Iterator>
226 class RangeSource : public GenImpl<typename Range<Iterator>::reference,
227 RangeSource<Iterator>> {
228 Range<Iterator> range_;
231 RangeSource() = default;
232 explicit RangeSource(Range<Iterator> range) : range_(std::move(range)) {}
234 template <class Handler>
235 bool apply(Handler&& handler) const {
236 for (auto& value : range_) {
237 if (!handler(value)) {
244 template <class Body>
245 void foreach(Body&& body) const {
246 for (auto& value : range_) {
251 // folly::Range only supports finite ranges
252 static constexpr bool infinite = false;
256 * Sequence - For generating values from beginning value, incremented along the
257 * way with the ++ and += operators. Iteration may continue indefinitely.
258 * Value type specified explicitly.
260 * This type is primarily used through the 'seq' and 'range' function, like:
262 * int total = seq(1, 10) | sum;
263 * auto indexes = range(0, 10);
264 * auto endless = seq(0); // 0, 1, 2, 3, ...
266 template <class Value, class SequenceImpl>
267 class Sequence : public GenImpl<const Value&, Sequence<Value, SequenceImpl>> {
268 static_assert(!std::is_reference<Value>::value &&
269 !std::is_const<Value>::value,
270 "Value mustn't be const or ref.");
275 explicit Sequence(Value start, SequenceImpl impl)
276 : start_(std::move(start)), impl_(std::move(impl)) {}
278 template <class Handler>
279 bool apply(Handler&& handler) const {
280 for (Value current = start_; impl_.test(current); impl_.step(current)) {
281 if (!handler(current)) {
288 template <class Body>
289 void foreach(Body&& body) const {
290 for (Value current = start_; impl_.test(current); impl_.step(current)) {
295 // Let the implementation say if we are infinite or not
296 static constexpr bool infinite = SequenceImpl::infinite;
300 * Sequence implementations (range, sequence, infinite, with/without step)
302 template <class Value>
307 explicit RangeImpl(Value end) : end_(std::move(end)) {}
308 bool test(const Value& current) const { return current < end_; }
309 void step(Value& current) const { ++current; }
310 static constexpr bool infinite = false;
313 template <class Value, class Distance>
314 class RangeWithStepImpl {
319 explicit RangeWithStepImpl(Value end, Distance step)
320 : end_(std::move(end)), step_(std::move(step)) {}
321 bool test(const Value& current) const { return current < end_; }
322 void step(Value& current) const { current += step_; }
323 static constexpr bool infinite = false;
326 template <class Value>
331 explicit SeqImpl(Value end) : end_(std::move(end)) {}
332 bool test(const Value& current) const { return current <= end_; }
333 void step(Value& current) const { ++current; }
334 static constexpr bool infinite = false;
337 template <class Value, class Distance>
338 class SeqWithStepImpl {
343 explicit SeqWithStepImpl(Value end, Distance step)
344 : end_(std::move(end)), step_(std::move(step)) {}
345 bool test(const Value& current) const { return current <= end_; }
346 void step(Value& current) const { current += step_; }
347 static constexpr bool infinite = false;
350 template <class Value>
353 bool test(const Value& /* current */) const { return true; }
354 void step(Value& current) const { ++current; }
355 static constexpr bool infinite = true;
359 * GenratorBuilder - Helper for GENERTATOR macro.
361 template <class Value>
362 struct GeneratorBuilder {
363 template <class Source, class Yield = detail::Yield<Value, Source>>
364 Yield operator+(Source&& source) {
365 return Yield(std::forward<Source>(source));
370 * Yield - For producing values from a user-defined generator by way of a
373 template <class Value, class Source>
374 class Yield : public GenImpl<Value, Yield<Value, Source>> {
378 explicit Yield(Source source) : source_(std::move(source)) {}
380 template <class Handler>
381 bool apply(Handler&& handler) const {
383 auto body = [&](Value value) {
384 if (!handler(std::forward<Value>(value))) {
396 template <class Body>
397 void foreach(Body&& body) const {
398 source_(std::forward<Body>(body));
402 template <class Value>
403 class Empty : public GenImpl<Value, Empty<Value>> {
405 template <class Handler>
406 bool apply(Handler&&) const {
410 template <class Body>
411 void foreach(Body&&) const {}
413 // No values, so finite
414 static constexpr bool infinite = false;
417 template <class Value>
418 class SingleReference : public GenImpl<Value&, SingleReference<Value>> {
419 static_assert(!std::is_reference<Value>::value,
420 "SingleReference requires non-ref types");
424 explicit SingleReference(Value& ref) : ptr_(&ref) {}
426 template <class Handler>
427 bool apply(Handler&& handler) const {
428 return handler(*ptr_);
431 template <class Body>
432 void foreach(Body&& body) const {
436 // One value, so finite
437 static constexpr bool infinite = false;
440 template <class Value>
441 class SingleCopy : public GenImpl<const Value&, SingleCopy<Value>> {
442 static_assert(!std::is_reference<Value>::value,
443 "SingleCopy requires non-ref types");
447 explicit SingleCopy(Value value) : value_(std::forward<Value>(value)) {}
449 template <class Handler>
450 bool apply(Handler&& handler) const {
451 return handler(value_);
454 template <class Body>
455 void foreach(Body&& body) const {
459 // One value, so finite
460 static constexpr bool infinite = false;
464 ***************************** Operators ***************************************
468 * Map - For producing a sequence of values by passing each value from a source
469 * collection through a predicate.
471 * This type is usually used through the 'map' or 'mapped' helper function:
473 * auto squares = seq(1, 10) | map(square) | as<std::vector>();
475 template <class Predicate>
476 class Map : public Operator<Map<Predicate>> {
482 explicit Map(Predicate pred) : pred_(std::move(pred)) {}
487 class Result = typename ArgumentReference<
488 typename std::result_of<Predicate(Value)>::type>::type>
489 class Generator : public GenImpl<Result, Generator<Value, Source, Result>> {
494 explicit Generator(Source source, const Predicate& pred)
495 : source_(std::move(source)), pred_(pred) {}
497 template <class Body>
498 void foreach(Body&& body) const {
500 [&](Value value) { body(pred_(std::forward<Value>(value))); });
503 template <class Handler>
504 bool apply(Handler&& handler) const {
505 return source_.apply([&](Value value) {
506 return handler(pred_(std::forward<Value>(value)));
510 static constexpr bool infinite = Source::infinite;
513 template <class Source, class Value, class Gen = Generator<Value, Source>>
514 Gen compose(GenImpl<Value, Source>&& source) const {
515 return Gen(std::move(source.self()), pred_);
518 template <class Source, class Value, class Gen = Generator<Value, Source>>
519 Gen compose(const GenImpl<Value, Source>& source) const {
520 return Gen(source.self(), pred_);
525 * Filter - For filtering values from a source sequence by a predicate.
527 * This type is usually used through the 'filter' helper function, like:
529 * auto nonEmpty = from(strings)
530 * | filter([](const string& str) -> bool {
531 * return !str.empty();
534 * Note that if no predicate is provided, the values are casted to bool and
535 * filtered based on that. So if pointers is a vector of pointers,
537 * auto nonNull = from(pointers) | filter();
539 * will give a vector of all the pointers != nullptr.
541 template <class Predicate>
542 class Filter : public Operator<Filter<Predicate>> {
547 explicit Filter(Predicate pred) : pred_(std::move(pred)) {}
549 template <class Value, class Source>
550 class Generator : public GenImpl<Value, Generator<Value, Source>> {
555 explicit Generator(Source source, const Predicate& pred)
556 : source_(std::move(source)), pred_(pred) {}
558 template <class Body>
559 void foreach(Body&& body) const {
560 source_.foreach([&](Value value) {
561 // NB: Argument not forwarded to avoid accidental move-construction
563 body(std::forward<Value>(value));
568 template <class Handler>
569 bool apply(Handler&& handler) const {
570 return source_.apply([&](Value value) -> bool {
571 // NB: Argument not forwarded to avoid accidental move-construction
573 return handler(std::forward<Value>(value));
579 static constexpr bool infinite = Source::infinite;
582 template <class Source, class Value, class Gen = Generator<Value, Source>>
583 Gen compose(GenImpl<Value, Source>&& source) const {
584 return Gen(std::move(source.self()), pred_);
587 template <class Source, class Value, class Gen = Generator<Value, Source>>
588 Gen compose(const GenImpl<Value, Source>& source) const {
589 return Gen(source.self(), pred_);
594 * Until - For producing values from a source until a predicate is satisfied.
596 * This type is usually used through the 'until' helper function, like:
598 * auto best = from(sortedItems)
599 * | until([](Item& item) { return item.score > 100; })
600 * | as<std::vector>();
602 template <class Predicate>
603 class Until : public Operator<Until<Predicate>> {
608 explicit Until(Predicate pred) : pred_(std::move(pred)) {}
610 template <class Value, class Source>
611 class Generator : public GenImpl<Value, Generator<Value, Source>> {
616 explicit Generator(Source source, const Predicate& pred)
617 : source_(std::move(source)), pred_(pred) {}
619 template <class Handler>
620 bool apply(Handler&& handler) const {
621 bool cancelled = false;
622 source_.apply([&](Value value) -> bool {
623 if (pred_(value)) { // un-forwarded to disable move
626 if (!handler(std::forward<Value>(value))) {
635 // Theoretically an 'until' might stop an infinite
636 static constexpr bool infinite = false;
639 template <class Source, class Value, class Gen = Generator<Value, Source>>
640 Gen compose(GenImpl<Value, Source>&& source) const {
641 return Gen(std::move(source.self()), pred_);
644 template <class Source, class Value, class Gen = Generator<Value, Source>>
645 Gen compose(const GenImpl<Value, Source>& source) const {
646 return Gen(source.self(), pred_);
651 * Take - For producing up to N values from a source.
653 * This type is usually used through the 'take' helper function, like:
655 * auto best = from(docs)
656 * | orderByDescending(scoreDoc)
659 class Take : public Operator<Take> {
663 explicit Take(size_t count) : count_(count) {}
665 template <class Value, class Source>
666 class Generator : public GenImpl<Value, Generator<Value, Source>> {
671 explicit Generator(Source source, size_t count)
672 : source_(std::move(source)), count_(count) {}
674 template <class Handler>
675 bool apply(Handler&& handler) const {
680 bool cancelled = false;
681 source_.apply([&](Value value) -> bool {
682 if (!handler(std::forward<Value>(value))) {
691 // take will stop an infinite generator
692 static constexpr bool infinite = false;
695 template <class Source, class Value, class Gen = Generator<Value, Source>>
696 Gen compose(GenImpl<Value, Source>&& source) const {
697 return Gen(std::move(source.self()), count_);
700 template <class Source, class Value, class Gen = Generator<Value, Source>>
701 Gen compose(const GenImpl<Value, Source>& source) const {
702 return Gen(source.self(), count_);
707 * Visit - For calling a function on each item before passing it down the
710 * This type is usually used through the 'visit' helper function:
712 * auto printedValues = seq(1) | visit(debugPrint);
713 * // nothing printed yet
714 * auto results = take(10) | as<std::vector>();
715 * // results now populated, 10 values printed
717 template <class Visitor>
718 class Visit : public Operator<Visit<Visitor>> {
724 explicit Visit(Visitor visitor) : visitor_(std::move(visitor)) {}
726 template <class Value, class Source>
727 class Generator : public GenImpl<Value, Generator<Value, Source>> {
732 explicit Generator(Source source, const Visitor& visitor)
733 : source_(std::move(source)), visitor_(visitor) {}
735 template <class Body>
736 void foreach(Body&& body) const {
737 source_.foreach([&](Value value) {
738 visitor_(value); // not forwarding to avoid accidental moves
739 body(std::forward<Value>(value));
743 template <class Handler>
744 bool apply(Handler&& handler) const {
745 return source_.apply([&](Value value) {
746 visitor_(value); // not forwarding to avoid accidental moves
747 return handler(std::forward<Value>(value));
751 static constexpr bool infinite = Source::infinite;
754 template <class Source, class Value, class Gen = Generator<Value, Source>>
755 Gen compose(GenImpl<Value, Source>&& source) const {
756 return Gen(std::move(source.self()), visitor_);
759 template <class Source, class Value, class Gen = Generator<Value, Source>>
760 Gen compose(const GenImpl<Value, Source>& source) const {
761 return Gen(source.self(), visitor_);
766 * Stride - For producing every Nth value from a source.
768 * This type is usually used through the 'stride' helper function, like:
770 * auto half = from(samples)
773 class Stride : public Operator<Stride> {
777 explicit Stride(size_t stride) : stride_(stride) {
779 throw std::invalid_argument("stride must not be 0");
783 template <class Value, class Source>
784 class Generator : public GenImpl<Value, Generator<Value, Source>> {
789 explicit Generator(Source source, size_t stride)
790 : source_(std::move(source)), stride_(stride) {}
792 template <class Handler>
793 bool apply(Handler&& handler) const {
794 size_t distance = stride_;
795 return source_.apply([&](Value value) -> bool {
796 if (++distance >= stride_) {
797 if (!handler(std::forward<Value>(value))) {
806 template <class Body>
807 void foreach(Body&& body) const {
808 size_t distance = stride_;
809 source_.foreach([&](Value value) {
810 if (++distance >= stride_) {
811 body(std::forward<Value>(value));
817 // Taking every Nth of an infinite list is still infinte
818 static constexpr bool infinite = Source::infinite;
821 template <class Source, class Value, class Gen = Generator<Value, Source>>
822 Gen compose(GenImpl<Value, Source>&& source) const {
823 return Gen(std::move(source.self()), stride_);
826 template <class Source, class Value, class Gen = Generator<Value, Source>>
827 Gen compose(const GenImpl<Value, Source>& source) const {
828 return Gen(source.self(), stride_);
833 * Sample - For taking a random sample of N elements from a sequence
834 * (without replacement).
836 template <class Random>
837 class Sample : public Operator<Sample<Random>> {
842 explicit Sample(size_t count, Random rng)
843 : count_(count), rng_(std::move(rng)) {}
849 class StorageType = typename std::decay<Value>::type>
851 : public GenImpl<StorageType&&,
852 Generator<Value, Source, Rand, StorageType>> {
853 static_assert(!Source::infinite, "Cannot sample infinite source!");
854 // It's too easy to bite ourselves if random generator is only 16-bit
855 static_assert(Random::max() >= std::numeric_limits<int32_t>::max() - 1,
856 "Random number generator must support big values");
862 explicit Generator(Source source, size_t count, Random rng)
863 : source_(std::move(source)), count_(count), rng_(std::move(rng)) {}
865 template <class Handler>
866 bool apply(Handler&& handler) const {
870 std::vector<StorageType> v;
872 // use reservoir sampling to give each source value an equal chance
873 // of appearing in our output.
875 source_.foreach([&](Value value) -> void {
876 if (v.size() < count_) {
877 v.push_back(std::forward<Value>(value));
879 // alternatively, we could create a std::uniform_int_distribution
880 // instead of using modulus, but benchmarks show this has
881 // substantial overhead.
882 size_t index = rng_() % n;
883 if (index < v.size()) {
884 v[index] = std::forward<Value>(value);
890 // output is unsorted!
891 for (auto& val : v) {
892 if (!handler(std::move(val))) {
899 // Only takes N elements, so finite
900 static constexpr bool infinite = false;
906 class Gen = Generator<Value, Source, Random>>
907 Gen compose(GenImpl<Value, Source>&& source) const {
908 return Gen(std::move(source.self()), count_, rng_);
914 class Gen = Generator<Value, Source, Random>>
915 Gen compose(const GenImpl<Value, Source>& source) const {
916 return Gen(source.self(), count_, rng_);
921 * Skip - For skipping N items from the beginning of a source generator.
923 * This type is usually used through the 'skip' helper function, like:
925 * auto page = from(results)
926 * | skip(pageSize * startPage)
929 class Skip : public Operator<Skip> {
933 explicit Skip(size_t count) : count_(count) {}
935 template <class Value, class Source>
936 class Generator : public GenImpl<Value, Generator<Value, Source>> {
941 explicit Generator(Source source, size_t count)
942 : source_(std::move(source)), count_(count) {}
944 template <class Body>
945 void foreach(Body&& body) const {
947 source_.foreach(body);
951 source_.foreach([&](Value value) {
955 body(std::forward<Value>(value));
960 template <class Handler>
961 bool apply(Handler&& handler) const {
963 return source_.apply(std::forward<Handler>(handler));
966 return source_.apply([&](Value value) -> bool {
971 return handler(std::forward<Value>(value));
975 // Skipping N items of an infinite source is still infinite
976 static constexpr bool infinite = Source::infinite;
979 template <class Source, class Value, class Gen = Generator<Value, Source>>
980 Gen compose(GenImpl<Value, Source>&& source) const {
981 return Gen(std::move(source.self()), count_);
984 template <class Source, class Value, class Gen = Generator<Value, Source>>
985 Gen compose(const GenImpl<Value, Source>& source) const {
986 return Gen(source.self(), count_);
991 * Order - For ordering a sequence of values from a source by key.
992 * The key is extracted by the given selector functor, and this key is then
993 * compared using the specified comparator.
995 * This type is usually used through the 'order' helper function, like:
997 * auto closest = from(places)
998 * | orderBy([](Place& p) {
999 * return -distance(p.location, here);
1003 template <class Selector, class Comparer>
1004 class Order : public Operator<Order<Selector, Comparer>> {
1011 explicit Order(Selector selector) : selector_(std::move(selector)) {}
1013 Order(Selector selector, Comparer comparer)
1014 : selector_(std::move(selector)), comparer_(std::move(comparer)) {}
1019 class StorageType = typename std::decay<Value>::type,
1020 class Result = typename std::result_of<Selector(Value)>::type>
1022 : public GenImpl<StorageType&&,
1023 Generator<Value, Source, StorageType, Result>> {
1024 static_assert(!Source::infinite, "Cannot sort infinite source!");
1029 typedef std::vector<StorageType> VectorType;
1031 VectorType asVector() const {
1032 auto comparer = [&](const StorageType& a, const StorageType& b) {
1033 return comparer_(selector_(a), selector_(b));
1035 auto vals = source_ | as<VectorType>();
1036 std::sort(vals.begin(), vals.end(), comparer);
1037 return std::move(vals);
1041 Generator(Source source, Selector selector, Comparer comparer)
1042 : source_(std::move(source)),
1043 selector_(std::move(selector)),
1044 comparer_(std::move(comparer)) {}
1046 VectorType operator|(const Collect<VectorType>&) const {
1050 VectorType operator|(const CollectTemplate<std::vector>&) const {
1054 template <class Body>
1055 void foreach(Body&& body) const {
1056 for (auto& value : asVector()) {
1057 body(std::move(value));
1061 template <class Handler>
1062 bool apply(Handler&& handler) const {
1063 auto comparer = [&](const StorageType& a, const StorageType& b) {
1064 // swapped for minHeap
1065 return comparer_(selector_(b), selector_(a));
1067 auto heap = source_ | as<VectorType>();
1068 std::make_heap(heap.begin(), heap.end(), comparer);
1069 while (!heap.empty()) {
1070 std::pop_heap(heap.begin(), heap.end(), comparer);
1071 if (!handler(std::move(heap.back()))) {
1079 // Can only be run on and produce finite generators
1080 static constexpr bool infinite = false;
1083 template <class Source, class Value, class Gen = Generator<Value, Source>>
1084 Gen compose(GenImpl<Value, Source>&& source) const {
1085 return Gen(std::move(source.self()), selector_, comparer_);
1088 template <class Source, class Value, class Gen = Generator<Value, Source>>
1089 Gen compose(const GenImpl<Value, Source>& source) const {
1090 return Gen(source.self(), selector_, comparer_);
1095 * GroupBy - Group values by a given key selector, producing a sequence of
1098 * This type is usually used through the 'groupBy' helper function, like:
1102 * | groupBy([](const Place& p) {
1105 * | [](Group<std::string, Place>&& g) {
1106 * cout << g.key() << ": " << (g | first).description;
1109 template <class Selector>
1110 class GroupBy : public Operator<GroupBy<Selector>> {
1116 explicit GroupBy(Selector selector) : selector_(std::move(selector)) {}
1121 class ValueDecayed = typename std::decay<Value>::type,
1122 class Key = typename std::result_of<Selector(Value)>::type,
1123 class KeyDecayed = typename std::decay<Key>::type>
1126 Group<KeyDecayed, ValueDecayed>&&,
1127 Generator<Value, Source, ValueDecayed, Key, KeyDecayed>> {
1128 static_assert(!Source::infinite, "Cannot group infinite source!");
1133 Generator(Source source, Selector selector)
1134 : source_(std::move(source)), selector_(std::move(selector)) {}
1136 typedef Group<KeyDecayed, ValueDecayed> GroupType;
1138 template <class Handler>
1139 bool apply(Handler&& handler) const {
1140 std::unordered_map<KeyDecayed, typename GroupType::VectorType> groups;
1141 source_ | [&](Value value) {
1142 const Value& cv = value;
1143 auto& group = groups[selector_(cv)];
1144 group.push_back(std::forward<Value>(value));
1146 for (auto& kg : groups) {
1147 GroupType group(kg.first, std::move(kg.second));
1148 if (!handler(std::move(group))) {
1156 // Can only be run on and produce finite generators
1157 static constexpr bool infinite = false;
1160 template <class Source, class Value, class Gen = Generator<Value, Source>>
1161 Gen compose(GenImpl<Value, Source>&& source) const {
1162 return Gen(std::move(source.self()), selector_);
1165 template <class Source, class Value, class Gen = Generator<Value, Source>>
1166 Gen compose(const GenImpl<Value, Source>& source) const {
1167 return Gen(source.self(), selector_);
1172 * TypeAssertion - For verifying the exact type of the value produced by a
1173 * generator. Useful for testing and debugging, and acts as a no-op at runtime.
1174 * Pass-through at runtime. Used through the 'assert_type<>()' factory method
1177 * auto c = from(vector) | assert_type<int&>() | sum;
1180 template <class Expected>
1181 class TypeAssertion : public Operator<TypeAssertion<Expected>> {
1183 template <class Source, class Value>
1184 const Source& compose(const GenImpl<Value, Source>& source) const {
1185 static_assert(std::is_same<Expected, Value>::value,
1186 "assert_type() check failed");
1187 return source.self();
1190 template <class Source, class Value>
1191 Source&& compose(GenImpl<Value, Source>&& source) const {
1192 static_assert(std::is_same<Expected, Value>::value,
1193 "assert_type() check failed");
1194 return std::move(source.self());
1199 * Distinct - For filtering duplicates out of a sequence. A selector may be
1200 * provided to generate a key to uniquify for each value.
1202 * This type is usually used through the 'distinct' helper function, like:
1204 * auto closest = from(results)
1205 * | distinctBy([](Item& i) {
1210 template <class Selector>
1211 class Distinct : public Operator<Distinct<Selector>> {
1215 Distinct() = default;
1217 explicit Distinct(Selector selector) : selector_(std::move(selector)) {}
1219 template <class Value, class Source>
1220 class Generator : public GenImpl<Value, Generator<Value, Source>> {
1224 typedef typename std::decay<Value>::type StorageType;
1226 // selector_ cannot be passed an rvalue or it would end up passing the husk
1227 // of a value to the downstream operators.
1228 typedef const StorageType& ParamType;
1230 typedef typename std::result_of<Selector(ParamType)>::type KeyType;
1231 typedef typename std::decay<KeyType>::type KeyStorageType;
1234 Generator(Source source, Selector selector)
1235 : source_(std::move(source)), selector_(std::move(selector)) {}
1237 template <class Body>
1238 void foreach(Body&& body) const {
1239 std::unordered_set<KeyStorageType> keysSeen;
1240 source_.foreach([&](Value value) {
1241 if (keysSeen.insert(selector_(ParamType(value))).second) {
1242 body(std::forward<Value>(value));
1247 template <class Handler>
1248 bool apply(Handler&& handler) const {
1249 std::unordered_set<KeyStorageType> keysSeen;
1250 return source_.apply([&](Value value) -> bool {
1251 if (keysSeen.insert(selector_(ParamType(value))).second) {
1252 return handler(std::forward<Value>(value));
1258 // While running distinct on an infinite sequence might produce a
1259 // conceptually finite sequence, it will take infinite time
1260 static constexpr bool infinite = Source::infinite;
1263 template <class Source, class Value, class Gen = Generator<Value, Source>>
1264 Gen compose(GenImpl<Value, Source>&& source) const {
1265 return Gen(std::move(source.self()), selector_);
1268 template <class Source, class Value, class Gen = Generator<Value, Source>>
1269 Gen compose(const GenImpl<Value, Source>& source) const {
1270 return Gen(source.self(), selector_);
1275 * Composer - Helper class for adapting pipelines into functors. Primarily used
1278 template <class Operators>
1283 explicit Composer(Operators op) : op_(std::move(op)) {}
1288 decltype(std::declval<Operators>().compose(std::declval<Source>()))>
1289 Ret operator()(Source&& source) const {
1290 return op_.compose(std::forward<Source>(source));
1295 * Batch - For producing fixed-size batches of each value from a source.
1297 * This type is usually used through the 'batch' helper function:
1302 * | map([](const std::vector<int>& batch) {
1303 * return from(batch) | sum;
1307 class Batch : public Operator<Batch> {
1311 explicit Batch(size_t batchSize) : batchSize_(batchSize) {
1312 if (batchSize_ == 0) {
1313 throw std::invalid_argument("Batch size must be non-zero!");
1320 class StorageType = typename std::decay<Value>::type,
1321 class VectorType = std::vector<StorageType>>
1323 : public GenImpl<VectorType&,
1324 Generator<Value, Source, StorageType, VectorType>> {
1329 explicit Generator(Source source, size_t batchSize)
1330 : source_(std::move(source)), batchSize_(batchSize) {}
1332 template <class Handler>
1333 bool apply(Handler&& handler) const {
1335 batch_.reserve(batchSize_);
1336 bool shouldContinue = source_.apply([&](Value value) -> bool {
1337 batch_.push_back(std::forward<Value>(value));
1338 if (batch_.size() == batchSize_) {
1339 bool needMore = handler(batch_);
1343 // Always need more if the handler is not called.
1346 // Flush everything, if and only if `handler` hasn't returned false.
1347 if (shouldContinue && !batch_.empty()) {
1348 shouldContinue = handler(batch_);
1351 return shouldContinue;
1354 // Taking n-tuples of an infinite source is still infinite
1355 static constexpr bool infinite = Source::infinite;
1358 template <class Source, class Value, class Gen = Generator<Value, Source>>
1359 Gen compose(GenImpl<Value, Source>&& source) const {
1360 return Gen(std::move(source.self()), batchSize_);
1363 template <class Source, class Value, class Gen = Generator<Value, Source>>
1364 Gen compose(const GenImpl<Value, Source>& source) const {
1365 return Gen(source.self(), batchSize_);
1370 * Window - For overlapping the lifetimes of pipeline values, especially with
1373 * This type is usually used through the 'window' helper function:
1377 * | map(makeRequestFuture)
1382 class Window : public Operator<Window> {
1386 explicit Window(size_t windowSize) : windowSize_(windowSize) {
1387 if (windowSize_ == 0) {
1388 throw std::invalid_argument("Window size must be non-zero!");
1395 class StorageType = typename std::decay<Value>::type>
1397 : public GenImpl<StorageType&&, Generator<Value, Source, StorageType>> {
1402 explicit Generator(Source source, size_t windowSize)
1403 : source_(std::move(source)), windowSize_(windowSize) {}
1405 template <class Handler>
1406 bool apply(Handler&& handler) const {
1407 std::vector<StorageType> buffer;
1408 buffer.reserve(windowSize_);
1409 size_t readIndex = 0;
1410 bool shouldContinue = source_.apply([&](Value value) -> bool {
1411 if (buffer.size() < windowSize_) {
1412 buffer.push_back(std::forward<Value>(value));
1414 StorageType& entry = buffer[readIndex++];
1415 if (readIndex == windowSize_) {
1418 if (!handler(std::move(entry))) {
1421 entry = std::forward<Value>(value);
1425 if (!shouldContinue) {
1428 if (buffer.size() < windowSize_) {
1429 for (StorageType& entry : buffer) {
1430 if (!handler(std::move(entry))) {
1435 for (size_t i = readIndex;;) {
1436 StorageType& entry = buffer[i++];
1437 if (!handler(std::move(entry))) {
1440 if (i == windowSize_) {
1443 if (i == readIndex) {
1451 // Taking n-tuples of an infinite source is still infinite
1452 static constexpr bool infinite = Source::infinite;
1455 template <class Source, class Value, class Gen = Generator<Value, Source>>
1456 Gen compose(GenImpl<Value, Source>&& source) const {
1457 return Gen(std::move(source.self()), windowSize_);
1460 template <class Source, class Value, class Gen = Generator<Value, Source>>
1461 Gen compose(const GenImpl<Value, Source>& source) const {
1462 return Gen(source.self(), windowSize_);
1467 * Concat - For flattening generators of generators.
1469 * This type is usually used through the 'concat' static value, like:
1473 * | map([](Node& x) {
1474 * return from(x.neighbors)
1475 * | map([&](Node& y) {
1476 * return Edge(x, y);
1482 class Concat : public Operator<Concat> {
1489 class InnerValue = typename std::decay<Inner>::type::ValueType>
1491 : public GenImpl<InnerValue, Generator<Inner, Source, InnerValue>> {
1495 explicit Generator(Source source) : source_(std::move(source)) {}
1497 template <class Handler>
1498 bool apply(Handler&& handler) const {
1499 return source_.apply([&](Inner inner) -> bool {
1500 return inner.apply(std::forward<Handler>(handler));
1504 template <class Body>
1505 void foreach(Body&& body) const {
1506 source_.foreach([&](Inner inner) {
1507 inner.foreach(std::forward<Body>(body));
1511 // Resulting concatination is only finite if both Source and Inner are also
1512 // finite. In one sence, if dosn't make sence to call concat when the Inner
1513 // generator is infinite (you could just call first), so we could also just
1514 // static_assert if the inner is infinite. Taking the less restrictive
1516 static constexpr bool infinite =
1517 Source::infinite || std::decay<Inner>::type::infinite;
1520 template <class Value, class Source, class Gen = Generator<Value, Source>>
1521 Gen compose(GenImpl<Value, Source>&& source) const {
1522 return Gen(std::move(source.self()));
1525 template <class Value, class Source, class Gen = Generator<Value, Source>>
1526 Gen compose(const GenImpl<Value, Source>& source) const {
1527 return Gen(source.self());
1532 * RangeConcat - For flattening generators of iterables.
1534 * This type is usually used through the 'rconcat' static value, like:
1536 * map<int, vector<int>> adjacency;
1543 class RangeConcat : public Operator<RangeConcat> {
1545 RangeConcat() = default;
1550 class InnerValue = typename ValueTypeOfRange<Range>::RefType>
1552 : public GenImpl<InnerValue, Generator<Range, Source, InnerValue>> {
1556 explicit Generator(Source source) : source_(std::move(source)) {}
1558 template <class Body>
1559 void foreach(Body&& body) const {
1560 source_.foreach([&](Range range) {
1561 for (auto& value : range) {
1567 template <class Handler>
1568 bool apply(Handler&& handler) const {
1569 return source_.apply([&](Range range) -> bool {
1570 for (auto& value : range) {
1571 if (!handler(value)) {
1579 // This is similar to concat, except that the inner iterables all are finite
1580 // so the only thing that matters is that the source is infinite.
1581 static constexpr bool infinite = Source::infinite;
1584 template <class Value, class Source, class Gen = Generator<Value, Source>>
1585 Gen compose(GenImpl<Value, Source>&& source) const {
1586 return Gen(std::move(source.self()));
1589 template <class Value, class Source, class Gen = Generator<Value, Source>>
1590 Gen compose(const GenImpl<Value, Source>& source) const {
1591 return Gen(source.self());
1596 * GuardImpl - For handling exceptions from downstream computation. Requires the
1597 * type of exception to catch, and handler function to invoke in the event of
1598 * the exception. Note that the handler may:
1599 * 1) return true to continue processing the sequence
1600 * 2) return false to end the sequence immediately
1601 * 3) throw, to pass the exception to the next catch
1602 * The handler must match the signature 'bool(Exception&, Value)'.
1604 * This type is used through the `guard` helper, like so:
1607 * = byLine(STDIN_FILENO)
1608 * | guard<std::runtime_error>([](std::runtime_error& e,
1610 * LOG(ERROR) << sp << ": " << e.str();
1611 * return true; // continue processing subsequent lines
1616 * TODO(tjackson): Rename this back to Guard.
1618 template <class Exception, class ErrorHandler>
1619 class GuardImpl : public Operator<GuardImpl<Exception, ErrorHandler>> {
1620 ErrorHandler handler_;
1623 explicit GuardImpl(ErrorHandler handler) : handler_(std::move(handler)) {}
1625 template <class Value, class Source>
1626 class Generator : public GenImpl<Value, Generator<Value, Source>> {
1628 ErrorHandler handler_;
1631 explicit Generator(Source source, ErrorHandler handler)
1632 : source_(std::move(source)), handler_(std::move(handler)) {}
1634 template <class Handler>
1635 bool apply(Handler&& handler) const {
1636 return source_.apply([&](Value value) -> bool {
1638 handler(std::forward<Value>(value));
1640 } catch (Exception& e) {
1641 return handler_(e, std::forward<Value>(value));
1646 // Just passes value though, length unaffected
1647 static constexpr bool infinite = Source::infinite;
1650 template <class Value, class Source, class Gen = Generator<Value, Source>>
1651 Gen compose(GenImpl<Value, Source>&& source) const {
1652 return Gen(std::move(source.self()), handler_);
1655 template <class Value, class Source, class Gen = Generator<Value, Source>>
1656 Gen compose(const GenImpl<Value, Source>& source) const {
1657 return Gen(source.self(), handler_);
1662 * Dereference - For dereferencing a sequence of pointers while filtering out
1665 * This type is usually used through the 'dereference' static value, like:
1667 * auto refs = from(ptrs) | dereference;
1669 class Dereference : public Operator<Dereference> {
1671 Dereference() = default;
1676 class Result = decltype(*std::declval<Value>())>
1677 class Generator : public GenImpl<Result, Generator<Value, Source, Result>> {
1681 explicit Generator(Source source) : source_(std::move(source)) {}
1683 template <class Body>
1684 void foreach(Body&& body) const {
1685 source_.foreach([&](Value value) {
1687 return body(*std::forward<Value>(value));
1692 template <class Handler>
1693 bool apply(Handler&& handler) const {
1694 return source_.apply([&](Value value) -> bool {
1696 return handler(*std::forward<Value>(value));
1702 // Just passes value though, length unaffected
1703 static constexpr bool infinite = Source::infinite;
1706 template <class Source, class Value, class Gen = Generator<Value, Source>>
1707 Gen compose(GenImpl<Value, Source>&& source) const {
1708 return Gen(std::move(source.self()));
1711 template <class Source, class Value, class Gen = Generator<Value, Source>>
1712 Gen compose(const GenImpl<Value, Source>& source) const {
1713 return Gen(source.self());
1718 * Indirect - For producing a sequence of the addresses of the values in the
1721 * This type is usually used through the 'indirect' static value, like:
1723 * auto ptrs = from(refs) | indirect;
1725 class Indirect : public Operator<Indirect> {
1727 Indirect() = default;
1732 class Result = typename std::remove_reference<Value>::type*>
1733 class Generator : public GenImpl<Result, Generator<Value, Source, Result>> {
1735 static_assert(!std::is_rvalue_reference<Value>::value,
1736 "Cannot use indirect on an rvalue");
1739 explicit Generator(Source source) : source_(std::move(source)) {}
1741 template <class Body>
1742 void foreach(Body&& body) const {
1743 source_.foreach([&](Value value) {
1744 return body(&std::forward<Value>(value));
1748 template <class Handler>
1749 bool apply(Handler&& handler) const {
1750 return source_.apply([&](Value value) -> bool {
1751 return handler(&std::forward<Value>(value));
1755 // Just passes value though, length unaffected
1756 static constexpr bool infinite = Source::infinite;
1759 template <class Source, class Value, class Gen = Generator<Value, Source>>
1760 Gen compose(GenImpl<Value, Source>&& source) const {
1761 return Gen(std::move(source.self()));
1764 template <class Source, class Value, class Gen = Generator<Value, Source>>
1765 Gen compose(const GenImpl<Value, Source>& source) const {
1766 return Gen(source.self());
1771 * Cycle - For repeating a sequence forever.
1773 * This type is usually used through the 'cycle' static value, like:
1780 * or in the finite case:
1782 * auto thrice = g | cycle(3);
1784 template <bool forever>
1785 class Cycle : public Operator<Cycle<forever>> {
1786 off_t limit_; // not used if forever == true
1790 explicit Cycle(off_t limit) : limit_(limit) {
1793 "Cycle limit constructor should not be used when forever == true.");
1796 template <class Value, class Source>
1797 class Generator : public GenImpl<Value, Generator<Value, Source>> {
1802 explicit Generator(Source source, off_t limit)
1803 : source_(std::move(source)), limit_(limit) {}
1805 template <class Handler>
1806 bool apply(Handler&& handler) const {
1808 auto handler2 = [&](Value value) {
1809 cont = handler(std::forward<Value>(value));
1812 // Becomes an infinte loop if forever == true
1813 for (off_t count = 0; (forever || count != limit_); ++count) {
1815 source_.apply(handler2);
1823 // This is the hardest one to infer. If we are simply doing a finite cycle,
1824 // then (gen | cycle(n)) is infinite if and only if gen is infinite.
1825 // However, if we are doing an infinite cycle, (gen | cycle) is infinite
1826 // unless gen is empty. However, we will always mark (gen | cycle) as
1827 // infinite, because patterns such as (gen | cycle | count) can either take
1828 // on exactly one value, or infinite loop.
1829 static constexpr bool infinite = forever || Source::infinite;
1832 template <class Source, class Value, class Gen = Generator<Value, Source>>
1833 Gen compose(GenImpl<Value, Source>&& source) const {
1834 return Gen(std::move(source.self()), limit_);
1837 template <class Source, class Value, class Gen = Generator<Value, Source>>
1838 Gen compose(const GenImpl<Value, Source>& source) const {
1839 return Gen(source.self(), limit_);
1843 * Convenience function for finite cycles used like:
1845 * auto tripled = gen | cycle(3);
1847 Cycle<false> operator()(off_t limit) const { return Cycle<false>(limit); }
1851 ******************************* Sinks *****************************************
1855 * FoldLeft - Left-associative functional fold. For producing an aggregate value
1856 * from a seed and a folder function. Useful for custom aggregators on a
1859 * This type is primarily used through the 'foldl' helper method, like:
1861 * double movingAverage = from(values)
1862 * | foldl(0.0, [](double avg, double sample) {
1863 * return sample * 0.1 + avg * 0.9;
1866 template <class Seed, class Fold>
1867 class FoldLeft : public Operator<FoldLeft<Seed, Fold>> {
1872 FoldLeft() = default;
1873 FoldLeft(Seed seed, Fold fold)
1874 : seed_(std::move(seed)), fold_(std::move(fold)) {}
1876 template <class Source, class Value>
1877 Seed compose(const GenImpl<Value, Source>& source) const {
1878 static_assert(!Source::infinite, "Cannot foldl infinite source");
1880 source | [&](Value v) {
1881 accum = fold_(std::move(accum), std::forward<Value>(v));
1888 * First - For finding the first value in a sequence.
1890 * This type is primarily used through the 'first' static value, like:
1892 * int firstThreeDigitPrime = seq(100) | filter(isPrime) | first;
1894 class First : public Operator<First> {
1901 class StorageType = typename std::decay<Value>::type>
1902 Optional<StorageType> compose(const GenImpl<Value, Source>& source) const {
1903 Optional<StorageType> accum;
1904 source | [&](Value v) -> bool {
1905 accum = std::forward<Value>(v);
1913 * IsEmpty - a helper class for isEmpty and notEmpty
1915 * Essentially returns 'result' if the source is empty. Note that this cannot be
1916 * called on an infinite source, because then there is only one possible return
1920 * Used primarily through 'isEmpty' and 'notEmpty' static values
1922 * bool hasPrimes = g | filter(prime) | notEmpty;
1923 * bool lacksEvens = g | filter(even) | isEmpty;
1925 * Also used in the implementation of 'any' and 'all'
1927 template <bool emptyResult>
1928 class IsEmpty : public Operator<IsEmpty<emptyResult>> {
1930 IsEmpty() = default;
1932 template <class Source, class Value>
1933 bool compose(const GenImpl<Value, Source>& source) const {
1934 static_assert(!Source::infinite,
1935 "Cannot call 'all', 'any', 'isEmpty', or 'notEmpty' on "
1936 "infinite source. 'all' and 'isEmpty' will either return "
1937 "false or hang. 'any' or 'notEmpty' will either return true "
1939 bool ans = emptyResult;
1941 [&](Value /* v */) -> bool {
1950 * Reduce - Functional reduce, for recursively combining values from a source
1951 * using a reducer function until there is only one item left. Useful for
1952 * combining values when an empty sequence doesn't make sense.
1954 * This type is primarily used through the 'reduce' helper method, like:
1956 * sring longest = from(names)
1957 * | reduce([](string&& best, string& current) {
1958 * return best.size() >= current.size() ? best : current;
1961 template <class Reducer>
1962 class Reduce : public Operator<Reduce<Reducer>> {
1967 explicit Reduce(Reducer reducer) : reducer_(std::move(reducer)) {}
1972 class StorageType = typename std::decay<Value>::type>
1973 Optional<StorageType> compose(const GenImpl<Value, Source>& source) const {
1974 static_assert(!Source::infinite, "Cannot reduce infinite source");
1975 Optional<StorageType> accum;
1976 source | [&](Value v) {
1977 if (auto target = accum.get_pointer()) {
1978 *target = reducer_(std::move(*target), std::forward<Value>(v));
1980 accum = std::forward<Value>(v);
1988 * Count - for simply counting the items in a collection.
1990 * This type is usually used through its singleton, 'count':
1992 * auto shortPrimes = seq(1, 100) | filter(isPrime) | count;
1994 class Count : public Operator<Count> {
1998 template <class Source, class Value>
1999 size_t compose(const GenImpl<Value, Source>& source) const {
2000 static_assert(!Source::infinite, "Cannot count infinite source");
2001 return foldl(size_t(0),
2002 [](size_t accum, Value /* v */) { return accum + 1; })
2008 * Sum - For simply summing up all the values from a source.
2010 * This type is usually used through its singleton, 'sum':
2012 * auto gaussSum = seq(1, 100) | sum;
2014 class Sum : public Operator<Sum> {
2021 class StorageType = typename std::decay<Value>::type>
2022 StorageType compose(const GenImpl<Value, Source>& source) const {
2023 static_assert(!Source::infinite, "Cannot sum infinite source");
2024 return foldl(StorageType(0),
2025 [](StorageType&& accum, Value v) {
2026 return std::move(accum) + std::forward<Value>(v);
2032 * Contains - For testing whether a value matching the given value is contained
2035 * This type should be used through the 'contains' helper method, like:
2037 * bool contained = seq(1, 10) | map(square) | contains(49);
2039 template <class Needle>
2040 class Contains : public Operator<Contains<Needle>> {
2044 explicit Contains(Needle needle) : needle_(std::move(needle)) {}
2049 class StorageType = typename std::decay<Value>::type>
2050 bool compose(const GenImpl<Value, Source>& source) const {
2051 static_assert(!Source::infinite,
2052 "Calling contains on an infinite source might cause "
2053 "an infinite loop.");
2054 return !(source | [this](Value value) {
2055 return !(needle_ == std::forward<Value>(value));
2061 * Min - For a value which minimizes a key, where the key is determined by a
2062 * given selector, and compared by given comparer.
2064 * This type is usually used through the singletone 'min' or through the helper
2065 * functions 'minBy' and 'maxBy'.
2067 * auto oldest = from(people)
2068 * | minBy([](Person& p) {
2069 * return p.dateOfBirth;
2072 template <class Selector, class Comparer>
2073 class Min : public Operator<Min<Selector, Comparer>> {
2077 template <typename T>
2078 const T& asConst(const T& t) const {
2085 explicit Min(Selector selector) : selector_(std::move(selector)) {}
2087 Min(Selector selector, Comparer comparer)
2088 : selector_(std::move(selector)), comparer_(std::move(comparer)) {}
2093 class StorageType = typename std::decay<Value>::type,
2094 class Key = typename std::decay<
2095 typename std::result_of<Selector(Value)>::type>::type>
2096 Optional<StorageType> compose(const GenImpl<Value, Source>& source) const {
2097 static_assert(!Source::infinite,
2098 "Calling min or max on an infinite source will cause "
2099 "an infinite loop.");
2100 Optional<StorageType> min;
2101 Optional<Key> minKey;
2102 source | [&](Value v) {
2103 Key key = selector_(asConst(v)); // so that selector_ cannot mutate v
2104 if (auto lastKey = minKey.get_pointer()) {
2105 if (!comparer_(key, *lastKey)) {
2109 minKey = std::move(key);
2110 min = std::forward<Value>(v);
2117 * Append - For collecting values from a source into a given output container
2120 * This type is usually used through the helper function 'appendTo', like:
2122 * vector<int64_t> ids;
2123 * from(results) | map([](Person& p) { return p.id })
2126 template <class Collection>
2127 class Append : public Operator<Append<Collection>> {
2128 Collection* collection_;
2131 explicit Append(Collection* collection) : collection_(collection) {}
2133 template <class Value, class Source>
2134 Collection& compose(const GenImpl<Value, Source>& source) const {
2135 static_assert(!Source::infinite, "Cannot appendTo with infinite source");
2136 source | [&](Value v) {
2137 collection_->insert(collection_->end(), std::forward<Value>(v));
2139 return *collection_;
2144 * Collect - For collecting values from a source in a collection of the desired
2147 * This type is usually used through the helper function 'as', like:
2149 * std::string upper = from(stringPiece)
2151 * | as<std::string>();
2153 template <class Collection>
2154 class Collect : public Operator<Collect<Collection>> {
2156 Collect() = default;
2161 class StorageType = typename std::decay<Value>::type>
2162 Collection compose(const GenImpl<Value, Source>& source) const {
2163 static_assert(!Source::infinite,
2164 "Cannot convert infinite source to object with as.");
2165 Collection collection;
2166 source | [&](Value v) {
2167 collection.insert(collection.end(), std::forward<Value>(v));
2174 * CollectTemplate - For collecting values from a source in a collection
2175 * constructed using the specified template type. Given the type of values
2176 * produced by the given generator, the collection type will be:
2177 * Container<Value, Allocator<Value>>
2179 * The allocator defaults to std::allocator, so this may be used for the STL
2180 * containers by simply using operators like 'as<set>', 'as<deque>',
2181 * 'as<vector>'. 'as', here is the helper method which is the usual means of
2182 * constructing this operator.
2186 * set<string> uniqueNames = from(names) | as<set>();
2189 template <class, class> class Container,
2190 template <class> class Allocator>
2191 class CollectTemplate : public Operator<CollectTemplate<Container, Allocator>> {
2193 CollectTemplate() = default;
2198 class StorageType = typename std::decay<Value>::type,
2199 class Collection = Container<StorageType, Allocator<StorageType>>>
2200 Collection compose(const GenImpl<Value, Source>& source) const {
2201 static_assert(!Source::infinite,
2202 "Cannot convert infinite source to object with as.");
2203 Collection collection;
2204 source | [&](Value v) {
2205 collection.insert(collection.end(), std::forward<Value>(v));
2212 * UnwrapOr - For unwrapping folly::Optional values, or providing the given
2213 * fallback value. Usually used through the 'unwrapOr' helper like so:
2215 * auto best = from(scores) | max | unwrapOr(-1);
2217 * Note that the fallback value needn't match the value in the Optional it is
2218 * unwrapping. If mis-matched types are supported, the common type of the two is
2219 * returned by value. If the types match, a reference (T&& > T& > const T&) is
2225 explicit UnwrapOr(T&& value) : value_(std::move(value)) {}
2226 explicit UnwrapOr(const T& value) : value_(value) {}
2228 T& value() { return value_; }
2229 const T& value() const { return value_; }
2236 T&& operator|(Optional<T>&& opt, UnwrapOr<T>&& fallback) {
2237 if (T* p = opt.get_pointer()) {
2238 return std::move(*p);
2240 return std::move(fallback.value());
2244 T& operator|(Optional<T>& opt, UnwrapOr<T>& fallback) {
2245 if (T* p = opt.get_pointer()) {
2248 return fallback.value();
2252 const T& operator|(const Optional<T>& opt, const UnwrapOr<T>& fallback) {
2253 if (const T* p = opt.get_pointer()) {
2256 return fallback.value();
2259 // Mixed type unwrapping always returns values, moving where possible
2263 class R = typename std::enable_if<
2264 !std::is_same<T, U>::value,
2265 typename std::common_type<T, U>::type>::type>
2266 R operator|(Optional<T>&& opt, UnwrapOr<U>&& fallback) {
2267 if (T* p = opt.get_pointer()) {
2268 return std::move(*p);
2270 return std::move(fallback.value());
2276 class R = typename std::enable_if<
2277 !std::is_same<T, U>::value,
2278 typename std::common_type<T, U>::type>::type>
2279 R operator|(const Optional<T>& opt, UnwrapOr<U>&& fallback) {
2280 if (const T* p = opt.get_pointer()) {
2283 return std::move(fallback.value());
2289 class R = typename std::enable_if<
2290 !std::is_same<T, U>::value,
2291 typename std::common_type<T, U>::type>::type>
2292 R operator|(Optional<T>&& opt, const UnwrapOr<U>& fallback) {
2293 if (T* p = opt.get_pointer()) {
2294 return std::move(*p);
2296 return fallback.value();
2302 class R = typename std::enable_if<
2303 !std::is_same<T, U>::value,
2304 typename std::common_type<T, U>::type>::type>
2305 R operator|(const Optional<T>& opt, const UnwrapOr<U>& fallback) {
2306 if (const T* p = opt.get_pointer()) {
2309 return fallback.value();
2313 * Unwrap - For unwrapping folly::Optional values in a folly::gen style. Usually
2314 * used through the 'unwrap' instace like so:
2316 * auto best = from(scores) | max | unwrap; // may throw
2321 T&& operator|(Optional<T>&& opt, const Unwrap&) {
2322 return std::move(opt.value());
2326 T& operator|(Optional<T>& opt, const Unwrap&) {
2331 const T& operator|(const Optional<T>& opt, const Unwrap&) {
2335 } // namespace detail
2338 * VirtualGen<T> - For wrapping template types in simple polymorphic wrapper.
2340 template <class Value>
2341 class VirtualGen : public GenImpl<Value, VirtualGen<Value>> {
2344 virtual ~WrapperBase() noexcept {}
2345 virtual bool apply(const std::function<bool(Value)>& handler) const = 0;
2346 virtual void foreach(const std::function<void(Value)>& body) const = 0;
2347 virtual std::unique_ptr<const WrapperBase> clone() const = 0;
2350 template <class Wrapped>
2351 class WrapperImpl : public WrapperBase {
2355 explicit WrapperImpl(Wrapped wrapped) : wrapped_(std::move(wrapped)) {}
2357 bool apply(const std::function<bool(Value)>& handler) const override {
2358 return wrapped_.apply(handler);
2361 void foreach(const std::function<void(Value)>& body) const override {
2362 wrapped_.foreach(body);
2365 std::unique_ptr<const WrapperBase> clone() const override {
2366 return std::unique_ptr<const WrapperBase>(new WrapperImpl(wrapped_));
2370 std::unique_ptr<const WrapperBase> wrapper_;
2373 template <class Self>
2374 /* implicit */ VirtualGen(Self source)
2375 : wrapper_(new WrapperImpl<Self>(std::move(source))) {}
2377 VirtualGen(VirtualGen&& source) noexcept
2378 : wrapper_(std::move(source.wrapper_)) {}
2380 VirtualGen(const VirtualGen& source) : wrapper_(source.wrapper_->clone()) {}
2382 VirtualGen& operator=(const VirtualGen& source) {
2383 wrapper_.reset(source.wrapper_->clone());
2387 VirtualGen& operator=(VirtualGen&& source) noexcept {
2388 wrapper_ = std::move(source.wrapper_);
2392 bool apply(const std::function<bool(Value)>& handler) const {
2393 return wrapper_->apply(handler);
2396 void foreach(const std::function<void(Value)>& body) const {
2397 wrapper_->foreach(body);
2402 * non-template operators, statically defined to avoid the need for anything but
2405 constexpr detail::Sum sum{};
2407 constexpr detail::Count count{};
2409 constexpr detail::First first{};
2411 constexpr detail::IsEmpty<true> isEmpty{};
2413 constexpr detail::IsEmpty<false> notEmpty{};
2415 constexpr detail::Min<Identity, Less> min{};
2417 constexpr detail::Min<Identity, Greater> max{};
2419 constexpr detail::Order<Identity> order{};
2421 constexpr detail::Distinct<Identity> distinct{};
2423 constexpr detail::Map<Move> move{};
2425 constexpr detail::Concat concat{};
2427 constexpr detail::RangeConcat rconcat{};
2429 constexpr detail::Cycle<true> cycle{};
2431 constexpr detail::Dereference dereference{};
2433 constexpr detail::Indirect indirect{};
2435 constexpr detail::Unwrap unwrap{};
2437 template <class Number>
2438 inline detail::Take take(Number count) {
2440 throw std::invalid_argument("Negative value passed to take()");
2442 return detail::Take(static_cast<size_t>(count));
2445 inline detail::Stride stride(size_t s) { return detail::Stride(s); }
2447 template <class Random = std::default_random_engine>
2448 inline detail::Sample<Random> sample(size_t count, Random rng = Random()) {
2449 return detail::Sample<Random>(count, std::move(rng));
2452 inline detail::Skip skip(size_t count) { return detail::Skip(count); }
2454 inline detail::Batch batch(size_t batchSize) {
2455 return detail::Batch(batchSize);
2458 inline detail::Window window(size_t windowSize) {
2459 return detail::Window(windowSize);
2463 } // namespace folly