1/*
2 * Copyright 2014-present Facebook, Inc.
3 *
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
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
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.
15 */
16
17#ifndef FOLLY_GEN_BASE_H_
18#error This file may only be included from folly/gen/Base.h
19#endif
20
21#include <folly/Portability.h>
22#include <folly/functional/Invoke.h>
23
24// Ignore shadowing warnings within this file, so includers can use -Wshadow.
25FOLLY_PUSH_WARNING
26FOLLY_GNU_DISABLE_WARNING("-Wshadow")
27
28namespace folly {
29namespace gen {
30
31/**
32 * ArgumentReference - For determining ideal argument type to receive a value.
33 */
34template <class T>
35struct ArgumentReference : public std::conditional<
36 std::is_reference<T>::value,
37 T, // T& -> T&, T&& -> T&&, const T& -> const T&
38 typename std::conditional<
39 std::is_const<T>::value,
40 T&, // const int -> const int&
41 T&& // int -> int&&
42 >::type> {};
43
44/**
45 * Group - The output objects from the GroupBy operator
46 */
47template <class Key, class Value>
48class Group : public GenImpl<Value&&, Group<Key, Value>> {
49 public:
50 static_assert(
51 !std::is_reference<Key>::value && !std::is_reference<Value>::value,
52 "Key and Value must be decayed types");
53
54 typedef std::vector<Value> VectorType;
55 typedef Key KeyType;
56 typedef Value ValueType;
57
58 Group(Key key, VectorType values)
59 : key_(std::move(key)), values_(std::move(values)) {}
60
61 const Key& key() const {
62 return key_;
63 }
64
65 size_t size() const {
66 return values_.size();
67 }
68 const VectorType& values() const {
69 return values_;
70 }
71 VectorType& values() {
72 return values_;
73 }
74
75 VectorType operator|(const detail::Collect<VectorType>&) const {
76 return values();
77 }
78
79 VectorType operator|(const detail::CollectTemplate<std::vector>&) const {
80 return values();
81 }
82
83 template <class Body>
84 void foreach(Body&& body) const {
85 for (auto& value : values_) {
86 body(std::move(value));
87 }
88 }
89
90 template <class Handler>
91 bool apply(Handler&& handler) const {
92 for (auto& value : values_) {
93 if (!handler(std::move(value))) {
94 return false;
95 }
96 }
97 return true;
98 }
99
100 // GroupBy only takes in finite generators, so we only have finite groups
101 static constexpr bool infinite = false;
102
103 private:
104 Key key_;
105 mutable VectorType values_;
106};
107
108namespace detail {
109
110// Classes used for the implementation of Sources, Operators, and Sinks
111
112/*
113 ******************************* Sources ***************************************
114 */
115
116/*
117 * ReferencedSource - Generate values from an STL-like container using
118 * iterators from .begin() until .end(). Value type defaults to the type of
119 * *container->begin(). For std::vector<int>, this would be int&. Note that the
120 * value here is a reference, so the values in the vector will be passed by
121 * reference to downstream operators.
122 *
123 * This type is primarily used through the 'from' helper method, like:
124 *
125 * string& longestName = from(names)
126 * | maxBy([](string& s) { return s.size() });
127 */
128template <class Container, class Value>
129class ReferencedSource
130 : public GenImpl<Value, ReferencedSource<Container, Value>> {
131 Container* container_;
132
133 public:
134 explicit ReferencedSource(Container* container) : container_(container) {}
135
136 template <class Body>
137 void foreach(Body&& body) const {
138 for (auto& value : *container_) {
139 body(std::forward<Value>(value));
140 }
141 }
142
143 template <class Handler>
144 bool apply(Handler&& handler) const {
145 for (auto& value : *container_) {
146 if (!handler(std::forward<Value>(value))) {
147 return false;
148 }
149 }
150 return true;
151 }
152
153 // from takes in a normal stl structure, which are all finite
154 static constexpr bool infinite = false;
155};
156
157/**
158 * CopiedSource - For producing values from eagerly from a sequence of values
159 * whose storage is owned by this class. Useful for preparing a generator for
160 * use after a source collection will no longer be available, or for when the
161 * values are specified literally with an initializer list.
162 *
163 * This type is primarily used through the 'fromCopy' function, like:
164 *
165 * auto sourceCopy = fromCopy(makeAVector());
166 * auto sum = sourceCopy | sum;
167 * auto max = sourceCopy | max;
168 *
169 * Though it is also used for the initializer_list specialization of from().
170 */
171template <class StorageType, class Container>
172class CopiedSource
173 : public GenImpl<const StorageType&, CopiedSource<StorageType, Container>> {
174 static_assert(
175 !std::is_reference<StorageType>::value,
176 "StorageType must be decayed");
177
178 public:
179 // Generator objects are often copied during normal construction as they are
180 // encapsulated by downstream generators. It would be bad if this caused
181 // a copy of the entire container each time, and since we're only exposing a
182 // const reference to the value, it's safe to share it between multiple
183 // generators.
184 static_assert(
185 !std::is_reference<Container>::value,
186 "Can't copy into a reference");
187 std::shared_ptr<const Container> copy_;
188
189 public:
190 typedef Container ContainerType;
191
192 template <class SourceContainer>
193 explicit CopiedSource(const SourceContainer& container)
194 : copy_(new Container(begin(container), end(container))) {}
195
196 explicit CopiedSource(Container&& container)
197 : copy_(new Container(std::move(container))) {}
198
199 // To enable re-use of cached results.
200 CopiedSource(const CopiedSource<StorageType, Container>& source)
201 : copy_(source.copy_) {}
202
203 template <class Body>
204 void foreach(Body&& body) const {
205 for (const auto& value : *copy_) {
206 body(value);
207 }
208 }
209
210 template <class Handler>
211 bool apply(Handler&& handler) const {
212 // The collection may be reused by others, we can't allow it to be changed.
213 for (const auto& value : *copy_) {
214 if (!handler(value)) {
215 return false;
216 }
217 }
218 return true;
219 }
220
221 // from takes in a normal stl structure, which are all finite
222 static constexpr bool infinite = false;
223};
224
225/**
226 * RangeSource - For producing values from a folly::Range. Useful for referring
227 * to a slice of some container.
228 *
229 * This type is primarily used through the 'from' function, like:
230 *
231 * auto rangeSource = from(folly::range(v.begin(), v.end()));
232 * auto sum = rangeSource | sum;
233 *
234 * Reminder: Be careful not to invalidate iterators when using ranges like this.
235 */
236template <class Iterator>
237class RangeSource : public GenImpl<
238 typename Range<Iterator>::reference,
239 RangeSource<Iterator>> {
240 Range<Iterator> range_;
241
242 public:
243 RangeSource() = default;
244 explicit RangeSource(Range<Iterator> range) : range_(std::move(range)) {}
245
246 template <class Handler>
247 bool apply(Handler&& handler) const {
248 for (auto& value : range_) {
249 if (!handler(value)) {
250 return false;
251 }
252 }
253 return true;
254 }
255
256 template <class Body>
257 void foreach(Body&& body) const {
258 for (auto& value : range_) {
259 body(value);
260 }
261 }
262
263 // folly::Range only supports finite ranges
264 static constexpr bool infinite = false;
265};
266
267/**
268 * Sequence - For generating values from beginning value, incremented along the
269 * way with the ++ and += operators. Iteration may continue indefinitely.
270 * Value type specified explicitly.
271 *
272 * This type is primarily used through the 'seq' and 'range' function, like:
273 *
274 * int total = seq(1, 10) | sum;
275 * auto indexes = range(0, 10);
276 * auto endless = seq(0); // 0, 1, 2, 3, ...
277 */
278template <class Value, class SequenceImpl>
279class Sequence : public GenImpl<const Value&, Sequence<Value, SequenceImpl>> {
280 static_assert(
281 !std::is_reference<Value>::value && !std::is_const<Value>::value,
282 "Value mustn't be const or ref.");
283 Value start_;
284 SequenceImpl impl_;
285
286 public:
287 explicit Sequence(Value start, SequenceImpl impl)
288 : start_(std::move(start)), impl_(std::move(impl)) {}
289
290 template <class Handler>
291 bool apply(Handler&& handler) const {
292 for (Value current = start_; impl_.test(current); impl_.step(current)) {
293 if (!handler(current)) {
294 return false;
295 }
296 }
297 return true;
298 }
299
300 template <class Body>
301 void foreach(Body&& body) const {
302 for (Value current = start_; impl_.test(current); impl_.step(current)) {
303 body(current);
304 }
305 }
306
307 // Let the implementation say if we are infinite or not
308 static constexpr bool infinite = SequenceImpl::infinite;
309};
310
311/**
312 * Sequence implementations (range, sequence, infinite, with/without step)
313 **/
314template <class Value>
315class RangeImpl {
316 Value end_;
317
318 public:
319 explicit RangeImpl(Value end) : end_(std::move(end)) {}
320 bool test(const Value& current) const {
321 return current < end_;
322 }
323 void step(Value& current) const {
324 ++current;
325 }
326 static constexpr bool infinite = false;
327};
328
329template <class Value, class Distance>
330class RangeWithStepImpl {
331 Value end_;
332 Distance step_;
333
334 public:
335 explicit RangeWithStepImpl(Value end, Distance step)
336 : end_(std::move(end)), step_(std::move(step)) {}
337 bool test(const Value& current) const {
338 return current < end_;
339 }
340 void step(Value& current) const {
341 current += step_;
342 }
343 static constexpr bool infinite = false;
344};
345
346template <class Value>
347class SeqImpl {
348 Value end_;
349
350 public:
351 explicit SeqImpl(Value end) : end_(std::move(end)) {}
352 bool test(const Value& current) const {
353 return current <= end_;
354 }
355 void step(Value& current) const {
356 ++current;
357 }
358 static constexpr bool infinite = false;
359};
360
361template <class Value, class Distance>
362class SeqWithStepImpl {
363 Value end_;
364 Distance step_;
365
366 public:
367 explicit SeqWithStepImpl(Value end, Distance step)
368 : end_(std::move(end)), step_(std::move(step)) {}
369 bool test(const Value& current) const {
370 return current <= end_;
371 }
372 void step(Value& current) const {
373 current += step_;
374 }
375 static constexpr bool infinite = false;
376};
377
378template <class Value>
379class InfiniteImpl {
380 public:
381 bool test(const Value& /* current */) const {
382 return true;
383 }
384 void step(Value& current) const {
385 ++current;
386 }
387 static constexpr bool infinite = true;
388};
389
390/**
391 * GenratorBuilder - Helper for GENERTATOR macro.
392 **/
393template <class Value>
394struct GeneratorBuilder {
395 template <class Source, class Yield = detail::Yield<Value, Source>>
396 Yield operator+(Source&& source) {
397 return Yield(std::forward<Source>(source));
398 }
399};
400
401/**
402 * Yield - For producing values from a user-defined generator by way of a
403 * 'yield' function.
404 **/
405template <class Value, class Source>
406class Yield : public GenImpl<Value, Yield<Value, Source>> {
407 Source source_;
408
409 public:
410 explicit Yield(Source source) : source_(std::move(source)) {}
411
412 template <class Handler>
413 bool apply(Handler&& handler) const {
414 struct Break {};
415 auto body = [&](Value value) {
416 if (!handler(std::forward<Value>(value))) {
417 throw Break();
418 }
419 };
420 try {
421 source_(body);
422 return true;
423 } catch (Break&) {
424 return false;
425 }
426 }
427
428 template <class Body>
429 void foreach(Body&& body) const {
430 source_(std::forward<Body>(body));
431 }
432};
433
434template <class Value>
435class Empty : public GenImpl<Value, Empty<Value>> {
436 public:
437 template <class Handler>
438 bool apply(Handler&&) const {
439 return true;
440 }
441
442 template <class Body>
443 void foreach(Body&&) const {}
444
445 // No values, so finite
446 static constexpr bool infinite = false;
447};
448
449template <class Value>
450class SingleReference : public GenImpl<Value&, SingleReference<Value>> {
451 static_assert(
452 !std::is_reference<Value>::value,
453 "SingleReference requires non-ref types");
454 Value* ptr_;
455
456 public:
457 explicit SingleReference(Value& ref) : ptr_(&ref) {}
458
459 template <class Handler>
460 bool apply(Handler&& handler) const {
461 return handler(*ptr_);
462 }
463
464 template <class Body>
465 void foreach(Body&& body) const {
466 body(*ptr_);
467 }
468
469 // One value, so finite
470 static constexpr bool infinite = false;
471};
472
473template <class Value>
474class SingleCopy : public GenImpl<const Value&, SingleCopy<Value>> {
475 static_assert(
476 !std::is_reference<Value>::value,
477 "SingleCopy requires non-ref types");
478 Value value_;
479
480 public:
481 explicit SingleCopy(Value value) : value_(std::forward<Value>(value)) {}
482
483 template <class Handler>
484 bool apply(Handler&& handler) const {
485 return handler(value_);
486 }
487
488 template <class Body>
489 void foreach(Body&& body) const {
490 body(value_);
491 }
492
493 // One value, so finite
494 static constexpr bool infinite = false;
495};
496
497/*
498 ***************************** Operators ***************************************
499 */
500
501/**
502 * Map - For producing a sequence of values by passing each value from a source
503 * collection through a predicate.
504 *
505 * This type is usually used through the 'map' or 'mapped' helper function:
506 *
507 * auto squares = seq(1, 10) | map(square) | as<std::vector>();
508 */
509template <class Predicate>
510class Map : public Operator<Map<Predicate>> {
511 Predicate pred_;
512
513 public:
514 Map() = default;
515
516 explicit Map(Predicate pred) : pred_(std::move(pred)) {}
517
518 template <
519 class Value,
520 class Source,
521 class Result =
522 typename ArgumentReference<invoke_result_t<Predicate, Value>>::type>
523 class Generator : public GenImpl<Result, Generator<Value, Source, Result>> {
524 Source source_;
525 Predicate pred_;
526
527 public:
528 explicit Generator(Source source, const Predicate& pred)
529 : source_(std::move(source)), pred_(pred) {}
530
531 template <class Body>
532 void foreach(Body&& body) const {
533 source_.foreach(
534 [&](Value value) { body(pred_(std::forward<Value>(value))); });
535 }
536
537 template <class Handler>
538 bool apply(Handler&& handler) const {
539 return source_.apply([&](Value value) {
540 return handler(pred_(std::forward<Value>(value)));
541 });
542 }
543
544 static constexpr bool infinite = Source::infinite;
545 };
546
547 template <class Source, class Value, class Gen = Generator<Value, Source>>
548 Gen compose(GenImpl<Value, Source>&& source) const {
549 return Gen(std::move(source.self()), pred_);
550 }
551
552 template <class Source, class Value, class Gen = Generator<Value, Source>>
553 Gen compose(const GenImpl<Value, Source>& source) const {
554 return Gen(source.self(), pred_);
555 }
556};
557
558/**
559 * Filter - For filtering values from a source sequence by a predicate.
560 *
561 * This type is usually used through the 'filter' helper function, like:
562 *
563 * auto nonEmpty = from(strings)
564 * | filter([](const string& str) -> bool {
565 * return !str.empty();
566 * });
567 *
568 * Note that if no predicate is provided, the values are casted to bool and
569 * filtered based on that. So if pointers is a vector of pointers,
570 *
571 * auto nonNull = from(pointers) | filter();
572 *
573 * will give a vector of all the pointers != nullptr.
574 */
575template <class Predicate>
576class Filter : public Operator<Filter<Predicate>> {
577 Predicate pred_;
578
579 public:
580 Filter() = default;
581 explicit Filter(Predicate pred) : pred_(std::move(pred)) {}
582
583 template <class Value, class Source>
584 class Generator : public GenImpl<Value, Generator<Value, Source>> {
585 Source source_;
586 Predicate pred_;
587
588 public:
589 explicit Generator(Source source, const Predicate& pred)
590 : source_(std::move(source)), pred_(pred) {}
591
592 template <class Body>
593 void foreach(Body&& body) const {
594 source_.foreach([&](Value value) {
595 // NB: Argument not forwarded to avoid accidental move-construction
596 if (pred_(value)) {
597 body(std::forward<Value>(value));
598 }
599 });
600 }
601
602 template <class Handler>
603 bool apply(Handler&& handler) const {
604 return source_.apply([&](Value value) -> bool {
605 // NB: Argument not forwarded to avoid accidental move-construction
606 if (pred_(value)) {
607 return handler(std::forward<Value>(value));
608 }
609 return true;
610 });
611 }
612
613 static constexpr bool infinite = Source::infinite;
614 };
615
616 template <class Source, class Value, class Gen = Generator<Value, Source>>
617 Gen compose(GenImpl<Value, Source>&& source) const {
618 return Gen(std::move(source.self()), pred_);
619 }
620
621 template <class Source, class Value, class Gen = Generator<Value, Source>>
622 Gen compose(const GenImpl<Value, Source>& source) const {
623 return Gen(source.self(), pred_);
624 }
625};
626
627/**
628 * Until - For producing values from a source until a predicate is satisfied.
629 *
630 * This type is usually used through the 'until' helper function, like:
631 *
632 * auto best = from(sortedItems)
633 * | until([](Item& item) { return item.score > 100; })
634 * | as<std::vector>();
635 */
636template <class Predicate>
637class Until : public Operator<Until<Predicate>> {
638 Predicate pred_;
639
640 public:
641 Until() = default;
642 explicit Until(Predicate pred) : pred_(std::move(pred)) {}
643
644 template <class Value, class Source>
645 class Generator : public GenImpl<Value, Generator<Value, Source>> {
646 Source source_;
647 Predicate pred_;
648
649 public:
650 explicit Generator(Source source, const Predicate& pred)
651 : source_(std::move(source)), pred_(pred) {}
652
653 template <class Handler>
654 bool apply(Handler&& handler) const {
655 bool cancelled = false;
656 source_.apply([&](Value value) -> bool {
657 if (pred_(value)) { // un-forwarded to disable move
658 return false;
659 }
660 if (!handler(std::forward<Value>(value))) {
661 cancelled = true;
662 return false;
663 }
664 return true;
665 });
666 return !cancelled;
667 }
668
669 // Theoretically an 'until' might stop an infinite
670 static constexpr bool infinite = false;
671 };
672
673 template <class Source, class Value, class Gen = Generator<Value, Source>>
674 Gen compose(GenImpl<Value, Source>&& source) const {
675 return Gen(std::move(source.self()), pred_);
676 }
677
678 template <class Source, class Value, class Gen = Generator<Value, Source>>
679 Gen compose(const GenImpl<Value, Source>& source) const {
680 return Gen(source.self(), pred_);
681 }
682};
683
684/**
685 * Take - For producing up to N values from a source.
686 *
687 * This type is usually used through the 'take' helper function, like:
688 *
689 * auto best = from(docs)
690 * | orderByDescending(scoreDoc)
691 * | take(10);
692 */
693class Take : public Operator<Take> {
694 size_t count_;
695
696 public:
697 explicit Take(size_t count) : count_(count) {}
698
699 template <class Value, class Source>
700 class Generator : public GenImpl<Value, Generator<Value, Source>> {
701 Source source_;
702 size_t count_;
703
704 public:
705 explicit Generator(Source source, size_t count)
706 : source_(std::move(source)), count_(count) {}
707
708 template <class Handler>
709 bool apply(Handler&& handler) const {
710 if (count_ == 0) {
711 return false;
712 }
713 size_t n = count_;
714 bool cancelled = false;
715 source_.apply([&](Value value) -> bool {
716 if (!handler(std::forward<Value>(value))) {
717 cancelled = true;
718 return false;
719 }
720 return --n;
721 });
722 return !cancelled;
723 }
724
725 // take will stop an infinite generator
726 static constexpr bool infinite = false;
727 };
728
729 template <class Source, class Value, class Gen = Generator<Value, Source>>
730 Gen compose(GenImpl<Value, Source>&& source) const {
731 return Gen(std::move(source.self()), count_);
732 }
733
734 template <class Source, class Value, class Gen = Generator<Value, Source>>
735 Gen compose(const GenImpl<Value, Source>& source) const {
736 return Gen(source.self(), count_);
737 }
738};
739
740/**
741 * Visit - For calling a function on each item before passing it down the
742 * pipeline.
743 *
744 * This type is usually used through the 'visit' helper function:
745 *
746 * auto printedValues = seq(1) | visit(debugPrint);
747 * // nothing printed yet
748 * auto results = take(10) | as<std::vector>();
749 * // results now populated, 10 values printed
750 */
751template <class Visitor>
752class Visit : public Operator<Visit<Visitor>> {
753 Visitor visitor_;
754
755 public:
756 Visit() = default;
757
758 explicit Visit(Visitor visitor) : visitor_(std::move(visitor)) {}
759
760 template <class Value, class Source>
761 class Generator : public GenImpl<Value, Generator<Value, Source>> {
762 Source source_;
763 Visitor visitor_;
764
765 public:
766 explicit Generator(Source source, const Visitor& visitor)
767 : source_(std::move(source)), visitor_(visitor) {}
768
769 template <class Body>
770 void foreach(Body&& body) const {
771 source_.foreach([&](Value value) {
772 visitor_(value); // not forwarding to avoid accidental moves
773 body(std::forward<Value>(value));
774 });
775 }
776
777 template <class Handler>
778 bool apply(Handler&& handler) const {
779 return source_.apply([&](Value value) {
780 visitor_(value); // not forwarding to avoid accidental moves
781 return handler(std::forward<Value>(value));
782 });
783 }
784
785 static constexpr bool infinite = Source::infinite;
786 };
787
788 template <class Source, class Value, class Gen = Generator<Value, Source>>
789 Gen compose(GenImpl<Value, Source>&& source) const {
790 return Gen(std::move(source.self()), visitor_);
791 }
792
793 template <class Source, class Value, class Gen = Generator<Value, Source>>
794 Gen compose(const GenImpl<Value, Source>& source) const {
795 return Gen(source.self(), visitor_);
796 }
797};
798
799/**
800 * Stride - For producing every Nth value from a source.
801 *
802 * This type is usually used through the 'stride' helper function, like:
803 *
804 * auto half = from(samples)
805 * | stride(2);
806 */
807class Stride : public Operator<Stride> {
808 size_t stride_;
809
810 public:
811 explicit Stride(size_t stride) : stride_(stride) {
812 if (stride == 0) {
813 throw std::invalid_argument("stride must not be 0");
814 }
815 }
816
817 template <class Value, class Source>
818 class Generator : public GenImpl<Value, Generator<Value, Source>> {
819 Source source_;
820 size_t stride_;
821
822 public:
823 explicit Generator(Source source, size_t stride)
824 : source_(std::move(source)), stride_(stride) {}
825
826 template <class Handler>
827 bool apply(Handler&& handler) const {
828 size_t distance = stride_;
829 return source_.apply([&](Value value) -> bool {
830 if (++distance >= stride_) {
831 if (!handler(std::forward<Value>(value))) {
832 return false;
833 }
834 distance = 0;
835 }
836 return true;
837 });
838 }
839
840 template <class Body>
841 void foreach(Body&& body) const {
842 size_t distance = stride_;
843 source_.foreach([&](Value value) {
844 if (++distance >= stride_) {
845 body(std::forward<Value>(value));
846 distance = 0;
847 }
848 });
849 }
850
851 // Taking every Nth of an infinite list is still infinte
852 static constexpr bool infinite = Source::infinite;
853 };
854
855 template <class Source, class Value, class Gen = Generator<Value, Source>>
856 Gen compose(GenImpl<Value, Source>&& source) const {
857 return Gen(std::move(source.self()), stride_);
858 }
859
860 template <class Source, class Value, class Gen = Generator<Value, Source>>
861 Gen compose(const GenImpl<Value, Source>& source) const {
862 return Gen(source.self(), stride_);
863 }
864};
865
866/**
867 * Sample - For taking a random sample of N elements from a sequence
868 * (without replacement).
869 */
870template <class Random>
871class Sample : public Operator<Sample<Random>> {
872 size_t count_;
873 Random rng_;
874
875 public:
876 explicit Sample(size_t count, Random rng)
877 : count_(count), rng_(std::move(rng)) {}
878
879 template <
880 class Value,
881 class Source,
882 class Rand,
883 class StorageType = typename std::decay<Value>::type>
884 class Generator : public GenImpl<
885 StorageType&&,
886 Generator<Value, Source, Rand, StorageType>> {
887 static_assert(!Source::infinite, "Cannot sample infinite source!");
888 // It's too easy to bite ourselves if random generator is only 16-bit
889 static_assert(
890 Random::max() >= std::numeric_limits<int32_t>::max() - 1,
891 "Random number generator must support big values");
892 Source source_;
893 size_t count_;
894 mutable Rand rng_;
895
896 public:
897 explicit Generator(Source source, size_t count, Random rng)
898 : source_(std::move(source)), count_(count), rng_(std::move(rng)) {}
899
900 template <class Handler>
901 bool apply(Handler&& handler) const {
902 if (count_ == 0) {
903 return false;
904 }
905 std::vector<StorageType> v;
906 v.reserve(count_);
907 // use reservoir sampling to give each source value an equal chance
908 // of appearing in our output.
909 size_t n = 1;
910 source_.foreach([&](Value value) -> void {
911 if (v.size() < count_) {
912 v.push_back(std::forward<Value>(value));
913 } else {
914 // alternatively, we could create a std::uniform_int_distribution
915 // instead of using modulus, but benchmarks show this has
916 // substantial overhead.
917 size_t index = rng_() % n;
918 if (index < v.size()) {
919 v[index] = std::forward<Value>(value);
920 }
921 }
922 ++n;
923 });
924
925 // output is unsorted!
926 for (auto& val : v) {
927 if (!handler(std::move(val))) {
928 return false;
929 }
930 }
931 return true;
932 }
933
934 // Only takes N elements, so finite
935 static constexpr bool infinite = false;
936 };
937
938 template <
939 class Source,
940 class Value,
941 class Gen = Generator<Value, Source, Random>>
942 Gen compose(GenImpl<Value, Source>&& source) const {
943 return Gen(std::move(source.self()), count_, rng_);
944 }
945
946 template <
947 class Source,
948 class Value,
949 class Gen = Generator<Value, Source, Random>>
950 Gen compose(const GenImpl<Value, Source>& source) const {
951 return Gen(source.self(), count_, rng_);
952 }
953};
954
955/**
956 * Skip - For skipping N items from the beginning of a source generator.
957 *
958 * This type is usually used through the 'skip' helper function, like:
959 *
960 * auto page = from(results)
961 * | skip(pageSize * startPage)
962 * | take(10);
963 */
964class Skip : public Operator<Skip> {
965 size_t count_;
966
967 public:
968 explicit Skip(size_t count) : count_(count) {}
969
970 template <class Value, class Source>
971 class Generator : public GenImpl<Value, Generator<Value, Source>> {
972 Source source_;
973 size_t count_;
974
975 public:
976 explicit Generator(Source source, size_t count)
977 : source_(std::move(source)), count_(count) {}
978
979 template <class Body>
980 void foreach(Body&& body) const {
981 if (count_ == 0) {
982 source_.foreach(body);
983 return;
984 }
985 size_t n = 0;
986 source_.foreach([&](Value value) {
987 if (n < count_) {
988 ++n;
989 } else {
990 body(std::forward<Value>(value));
991 }
992 });
993 }
994
995 template <class Handler>
996 bool apply(Handler&& handler) const {
997 if (count_ == 0) {
998 return source_.apply(std::forward<Handler>(handler));
999 }
1000 size_t n = 0;
1001 return source_.apply([&](Value value) -> bool {
1002 if (n < count_) {
1003 ++n;
1004 return true;
1005 }
1006 return handler(std::forward<Value>(value));
1007 });
1008 }
1009
1010 // Skipping N items of an infinite source is still infinite
1011 static constexpr bool infinite = Source::infinite;
1012 };
1013
1014 template <class Source, class Value, class Gen = Generator<Value, Source>>
1015 Gen compose(GenImpl<Value, Source>&& source) const {
1016 return Gen(std::move(source.self()), count_);
1017 }
1018
1019 template <class Source, class Value, class Gen = Generator<Value, Source>>
1020 Gen compose(const GenImpl<Value, Source>& source) const {
1021 return Gen(source.self(), count_);
1022 }
1023};
1024
1025/**
1026 * Order - For ordering a sequence of values from a source by key.
1027 * The key is extracted by the given selector functor, and this key is then
1028 * compared using the specified comparator.
1029 *
1030 * This type is usually used through the 'order' helper function, like:
1031 *
1032 * auto closest = from(places)
1033 * | orderBy([](Place& p) {
1034 * return -distance(p.location, here);
1035 * })
1036 * | take(10);
1037 */
1038template <class Selector, class Comparer>
1039class Order : public Operator<Order<Selector, Comparer>> {
1040 Selector selector_;
1041 Comparer comparer_;
1042
1043 public:
1044 Order() = default;
1045
1046 explicit Order(Selector selector) : selector_(std::move(selector)) {}
1047
1048 Order(Selector selector, Comparer comparer)
1049 : selector_(std::move(selector)), comparer_(std::move(comparer)) {}
1050
1051 template <
1052 class Value,
1053 class Source,
1054 class StorageType = typename std::decay<Value>::type,
1055 class Result = invoke_result_t<Selector, Value>>
1056 class Generator : public GenImpl<
1057 StorageType&&,
1058 Generator<Value, Source, StorageType, Result>> {
1059 static_assert(!Source::infinite, "Cannot sort infinite source!");
1060 Source source_;
1061 Selector selector_;
1062 Comparer comparer_;
1063
1064 typedef std::vector<StorageType> VectorType;
1065
1066 VectorType asVector() const {
1067 auto comparer = [&](const StorageType& a, const StorageType& b) {
1068 return comparer_(selector_(a), selector_(b));
1069 };
1070 auto vals = source_ | as<VectorType>();
1071 std::sort(vals.begin(), vals.end(), comparer);
1072 return std::move(vals);
1073 }
1074
1075 public:
1076 Generator(Source source, Selector selector, Comparer comparer)
1077 : source_(std::move(source)),
1078 selector_(std::move(selector)),
1079 comparer_(std::move(comparer)) {}
1080
1081 VectorType operator|(const Collect<VectorType>&) const {
1082 return asVector();
1083 }
1084
1085 VectorType operator|(const CollectTemplate<std::vector>&) const {
1086 return asVector();
1087 }
1088
1089 template <class Body>
1090 void foreach(Body&& body) const {
1091 for (auto& value : asVector()) {
1092 body(std::move(value));
1093 }
1094 }
1095
1096 template <class Handler>
1097 bool apply(Handler&& handler) const {
1098 auto comparer = [&](const StorageType& a, const StorageType& b) {
1099 // swapped for minHeap
1100 return comparer_(selector_(b), selector_(a));
1101 };
1102 auto heap = source_ | as<VectorType>();
1103 std::make_heap(heap.begin(), heap.end(), comparer);
1104 while (!heap.empty()) {
1105 std::pop_heap(heap.begin(), heap.end(), comparer);
1106 if (!handler(std::move(heap.back()))) {
1107 return false;
1108 }
1109 heap.pop_back();
1110 }
1111 return true;
1112 }
1113
1114 // Can only be run on and produce finite generators
1115 static constexpr bool infinite = false;
1116 };
1117
1118 template <class Source, class Value, class Gen = Generator<Value, Source>>
1119 Gen compose(GenImpl<Value, Source>&& source) const {
1120 return Gen(std::move(source.self()), selector_, comparer_);
1121 }
1122
1123 template <class Source, class Value, class Gen = Generator<Value, Source>>
1124 Gen compose(const GenImpl<Value, Source>& source) const {
1125 return Gen(source.self(), selector_, comparer_);
1126 }
1127};
1128
1129/**
1130 * GroupBy - Group values by a given key selector, producing a sequence of
1131 * groups.
1132 *
1133 * This type is usually used through the 'groupBy' helper function, like:
1134 *
1135 * auto bests
1136 * = from(places)
1137 * | groupBy([](const Place& p) {
1138 * return p.city;
1139 * })
1140 * | [](Group<std::string, Place>&& g) {
1141 * cout << g.key() << ": " << (g | first).description;
1142 * };
1143 */
1144template <class Selector>
1145class GroupBy : public Operator<GroupBy<Selector>> {
1146 Selector selector_;
1147
1148 public:
1149 GroupBy() {}
1150
1151 explicit GroupBy(Selector selector) : selector_(std::move(selector)) {}
1152
1153 template <
1154 class Value,
1155 class Source,
1156 class ValueDecayed = typename std::decay<Value>::type,
1157 class Key = invoke_result_t<Selector, Value>,
1158 class KeyDecayed = typename std::decay<Key>::type>
1159 class Generator
1160 : public GenImpl<
1161 Group<KeyDecayed, ValueDecayed>&&,
1162 Generator<Value, Source, ValueDecayed, Key, KeyDecayed>> {
1163 static_assert(!Source::infinite, "Cannot group infinite source!");
1164 Source source_;
1165 Selector selector_;
1166
1167 public:
1168 Generator(Source source, Selector selector)
1169 : source_(std::move(source)), selector_(std::move(selector)) {}
1170
1171 typedef Group<KeyDecayed, ValueDecayed> GroupType;
1172
1173 template <class Handler>
1174 bool apply(Handler&& handler) const {
1175 std::unordered_map<KeyDecayed, typename GroupType::VectorType> groups;
1176 source_ | [&](Value value) {
1177 const Value& cv = value;
1178 auto& group = groups[selector_(cv)];
1179 group.push_back(std::forward<Value>(value));
1180 };
1181 for (auto& kg : groups) {
1182 GroupType group(kg.first, std::move(kg.second));
1183 if (!handler(std::move(group))) {
1184 return false;
1185 }
1186 kg.second.clear();
1187 }
1188 return true;
1189 }
1190
1191 // Can only be run on and produce finite generators
1192 static constexpr bool infinite = false;
1193 };
1194
1195 template <class Source, class Value, class Gen = Generator<Value, Source>>
1196 Gen compose(GenImpl<Value, Source>&& source) const {
1197 return Gen(std::move(source.self()), selector_);
1198 }
1199
1200 template <class Source, class Value, class Gen = Generator<Value, Source>>
1201 Gen compose(const GenImpl<Value, Source>& source) const {
1202 return Gen(source.self(), selector_);
1203 }
1204};
1205
1206/**
1207 * GroupByAdjacent - Group adjacent values by a given key selector, producing a
1208 * sequence of groups. This differs from GroupBy in that only contiguous sets
1209 * of values with the same key are considered part of the same group. Unlike
1210 * GroupBy, this can be used on infinite sequences.
1211 *
1212 * This type is usually used through the 'groupByAdjacent' helper function:
1213 *
1214 * auto tens
1215 * = seq(0)
1216 * | groupByAdjacent([](int i){ return (i / 10) % 2; })
1217 *
1218 * This example results in a list like [ 0:[0-9], 1:[10-19], 0:[20-29], ... ]
1219 */
1220template <class Selector>
1221class GroupByAdjacent : public Operator<GroupByAdjacent<Selector>> {
1222 Selector selector_;
1223
1224 public:
1225 GroupByAdjacent() {}
1226
1227 explicit GroupByAdjacent(Selector selector)
1228 : selector_(std::move(selector)) {}
1229
1230 template <
1231 class Value,
1232 class Source,
1233 class ValueDecayed = typename std::decay<Value>::type,
1234 class Key = invoke_result_t<Selector, Value>,
1235 class KeyDecayed = typename std::decay<Key>::type>
1236 class Generator
1237 : public GenImpl<
1238 Group<KeyDecayed, ValueDecayed>&&,
1239 Generator<Value, Source, ValueDecayed, Key, KeyDecayed>> {
1240 Source source_;
1241 Selector selector_;
1242
1243 public:
1244 Generator(Source source, Selector selector)
1245 : source_(std::move(source)), selector_(std::move(selector)) {}
1246
1247 typedef Group<KeyDecayed, ValueDecayed> GroupType;
1248
1249 template <class Handler>
1250 bool apply(Handler&& handler) const {
1251 Optional<KeyDecayed> key = none;
1252 typename GroupType::VectorType values;
1253
1254 bool result = source_.apply([&](Value value) mutable {
1255 KeyDecayed newKey = selector_(value);
1256
1257 // start the first group
1258 if (!key.hasValue()) {
1259 key.emplace(newKey);
1260 }
1261
1262 if (key == newKey) {
1263 // grow the current group
1264 values.push_back(value);
1265 } else {
1266 // flush the current group
1267 GroupType group(key.value(), std::move(values));
1268 if (!handler(std::move(group))) {
1269 return false;
1270 }
1271
1272 // start a new group
1273 key.emplace(newKey);
1274 values.clear();
1275 values.push_back(value);
1276 }
1277 return true;
1278 });
1279
1280 if (!result) {
1281 return false;
1282 }
1283
1284 if (!key.hasValue()) {
1285 return true;
1286 }
1287
1288 // flush the final group
1289 GroupType group(key.value(), std::move(values));
1290 return handler(std::move(group));
1291 }
1292
1293 static constexpr bool infinite = Source::infinite;
1294 };
1295
1296 template <class Source, class Value, class Gen = Generator<Value, Source>>
1297 Gen compose(GenImpl<Value, Source>&& source) const {
1298 return Gen(std::move(source.self()), selector_);
1299 }
1300
1301 template <class Source, class Value, class Gen = Generator<Value, Source>>
1302 Gen compose(const GenImpl<Value, Source>& source) const {
1303 return Gen(source.self(), selector_);
1304 }
1305};
1306
1307/*
1308 * TypeAssertion - For verifying the exact type of the value produced by a
1309 * generator. Useful for testing and debugging, and acts as a no-op at runtime.
1310 * Pass-through at runtime. Used through the 'assert_type<>()' factory method
1311 * like so:
1312 *
1313 * auto c = from(vector) | assert_type<int&>() | sum;
1314 *
1315 */
1316template <class Expected>
1317class TypeAssertion : public Operator<TypeAssertion<Expected>> {
1318 public:
1319 template <class Source, class Value>
1320 const Source& compose(const GenImpl<Value, Source>& source) const {
1321 static_assert(
1322 std::is_same<Expected, Value>::value, "assert_type() check failed");
1323 return source.self();
1324 }
1325
1326 template <class Source, class Value>
1327 Source&& compose(GenImpl<Value, Source>&& source) const {
1328 static_assert(
1329 std::is_same<Expected, Value>::value, "assert_type() check failed");
1330 return std::move(source.self());
1331 }
1332};
1333
1334/**
1335 * Distinct - For filtering duplicates out of a sequence. A selector may be
1336 * provided to generate a key to uniquify for each value.
1337 *
1338 * This type is usually used through the 'distinct' helper function, like:
1339 *
1340 * auto closest = from(results)
1341 * | distinctBy([](Item& i) {
1342 * return i.target;
1343 * })
1344 * | take(10);
1345 */
1346template <class Selector>
1347class Distinct : public Operator<Distinct<Selector>> {
1348 Selector selector_;
1349
1350 public:
1351 Distinct() = default;
1352
1353 explicit Distinct(Selector selector) : selector_(std::move(selector)) {}
1354
1355 template <class Value, class Source>
1356 class Generator : public GenImpl<Value, Generator<Value, Source>> {
1357 Source source_;
1358 Selector selector_;
1359
1360 typedef typename std::decay<Value>::type StorageType;
1361
1362 // selector_ cannot be passed an rvalue or it would end up passing the husk
1363 // of a value to the downstream operators.
1364 typedef const StorageType& ParamType;
1365
1366 typedef invoke_result_t<Selector, ParamType> KeyType;
1367 typedef typename std::decay<KeyType>::type KeyStorageType;
1368
1369 public:
1370 Generator(Source source, Selector selector)
1371 : source_(std::move(source)), selector_(std::move(selector)) {}
1372
1373 template <class Body>
1374 void foreach(Body&& body) const {
1375 std::unordered_set<KeyStorageType> keysSeen;
1376 source_.foreach([&](Value value) {
1377 if (keysSeen.insert(selector_(ParamType(value))).second) {
1378 body(std::forward<Value>(value));
1379 }
1380 });
1381 }
1382
1383 template <class Handler>
1384 bool apply(Handler&& handler) const {
1385 std::unordered_set<KeyStorageType> keysSeen;
1386 return source_.apply([&](Value value) -> bool {
1387 if (keysSeen.insert(selector_(ParamType(value))).second) {
1388 return handler(std::forward<Value>(value));
1389 }
1390 return true;
1391 });
1392 }
1393
1394 // While running distinct on an infinite sequence might produce a
1395 // conceptually finite sequence, it will take infinite time
1396 static constexpr bool infinite = Source::infinite;
1397 };
1398
1399 template <class Source, class Value, class Gen = Generator<Value, Source>>
1400 Gen compose(GenImpl<Value, Source>&& source) const {
1401 return Gen(std::move(source.self()), selector_);
1402 }
1403
1404 template <class Source, class Value, class Gen = Generator<Value, Source>>
1405 Gen compose(const GenImpl<Value, Source>& source) const {
1406 return Gen(source.self(), selector_);
1407 }
1408};
1409
1410/**
1411 * Composer - Helper class for adapting pipelines into functors. Primarily used
1412 * for 'mapOp'.
1413 */
1414template <class Operators>
1415class Composer {
1416 Operators op_;
1417
1418 public:
1419 explicit Composer(Operators op) : op_(std::move(op)) {}
1420
1421 template <
1422 class Source,
1423 class Ret =
1424 decltype(std::declval<Operators>().compose(std::declval<Source>()))>
1425 Ret operator()(Source&& source) const {
1426 return op_.compose(std::forward<Source>(source));
1427 }
1428};
1429
1430/**
1431 * Batch - For producing fixed-size batches of each value from a source.
1432 *
1433 * This type is usually used through the 'batch' helper function:
1434 *
1435 * auto batchSums
1436 * = seq(1, 10)
1437 * | batch(3)
1438 * | map([](const std::vector<int>& batch) {
1439 * return from(batch) | sum;
1440 * })
1441 * | as<vector>();
1442 */
1443class Batch : public Operator<Batch> {
1444 size_t batchSize_;
1445
1446 public:
1447 explicit Batch(size_t batchSize) : batchSize_(batchSize) {
1448 if (batchSize_ == 0) {
1449 throw std::invalid_argument("Batch size must be non-zero!");
1450 }
1451 }
1452
1453 template <
1454 class Value,
1455 class Source,
1456 class StorageType = typename std::decay<Value>::type,
1457 class VectorType = std::vector<StorageType>>
1458 class Generator : public GenImpl<
1459 VectorType&,
1460 Generator<Value, Source, StorageType, VectorType>> {
1461 Source source_;
1462 size_t batchSize_;
1463
1464 public:
1465 explicit Generator(Source source, size_t batchSize)
1466 : source_(std::move(source)), batchSize_(batchSize) {}
1467
1468 template <class Handler>
1469 bool apply(Handler&& handler) const {
1470 VectorType batch_;
1471 batch_.reserve(batchSize_);
1472 bool shouldContinue = source_.apply([&](Value value) -> bool {
1473 batch_.push_back(std::forward<Value>(value));
1474 if (batch_.size() == batchSize_) {
1475 bool needMore = handler(batch_);
1476 batch_.clear();
1477 return needMore;
1478 }
1479 // Always need more if the handler is not called.
1480 return true;
1481 });
1482 // Flush everything, if and only if `handler` hasn't returned false.
1483 if (shouldContinue && !batch_.empty()) {
1484 shouldContinue = handler(batch_);
1485 batch_.clear();
1486 }
1487 return shouldContinue;
1488 }
1489
1490 // Taking n-tuples of an infinite source is still infinite
1491 static constexpr bool infinite = Source::infinite;
1492 };
1493
1494 template <class Source, class Value, class Gen = Generator<Value, Source>>
1495 Gen compose(GenImpl<Value, Source>&& source) const {
1496 return Gen(std::move(source.self()), batchSize_);
1497 }
1498
1499 template <class Source, class Value, class Gen = Generator<Value, Source>>
1500 Gen compose(const GenImpl<Value, Source>& source) const {
1501 return Gen(source.self(), batchSize_);
1502 }
1503};
1504
1505/**
1506 * Window - For overlapping the lifetimes of pipeline values, especially with
1507 * Futures.
1508 *
1509 * This type is usually used through the 'window' helper function:
1510 *
1511 * auto responses
1512 * = byLine(STDIN)
1513 * | map(makeRequestFuture)
1514 * | window(1000)
1515 * | map(waitFuture)
1516 * | as<vector>();
1517 */
1518class Window : public Operator<Window> {
1519 size_t windowSize_;
1520
1521 public:
1522 explicit Window(size_t windowSize) : windowSize_(windowSize) {
1523 if (windowSize_ == 0) {
1524 throw std::invalid_argument("Window size must be non-zero!");
1525 }
1526 }
1527
1528 template <
1529 class Value,
1530 class Source,
1531 class StorageType = typename std::decay<Value>::type>
1532 class Generator
1533 : public GenImpl<StorageType&&, Generator<Value, Source, StorageType>> {
1534 Source source_;
1535 size_t windowSize_;
1536
1537 public:
1538 explicit Generator(Source source, size_t windowSize)
1539 : source_(std::move(source)), windowSize_(windowSize) {}
1540
1541 template <class Handler>
1542 bool apply(Handler&& handler) const {
1543 std::vector<StorageType> buffer;
1544 buffer.reserve(windowSize_);
1545 size_t readIndex = 0;
1546 bool shouldContinue = source_.apply([&](Value value) -> bool {
1547 if (buffer.size() < windowSize_) {
1548 buffer.push_back(std::forward<Value>(value));
1549 } else {
1550 StorageType& entry = buffer[readIndex++];
1551 if (readIndex == windowSize_) {
1552 readIndex = 0;
1553 }
1554 if (!handler(std::move(entry))) {
1555 return false;
1556 }
1557 entry = std::forward<Value>(value);
1558 }
1559 return true;
1560 });
1561 if (!shouldContinue) {
1562 return false;
1563 }
1564 if (buffer.size() < windowSize_) {
1565 for (StorageType& entry : buffer) {
1566 if (!handler(std::move(entry))) {
1567 return false;
1568 }
1569 }
1570 } else {
1571 for (size_t i = readIndex;;) {
1572 StorageType& entry = buffer[i++];
1573 if (!handler(std::move(entry))) {
1574 return false;
1575 }
1576 if (i == windowSize_) {
1577 i = 0;
1578 }
1579 if (i == readIndex) {
1580 break;
1581 }
1582 }
1583 }
1584 return true;
1585 }
1586
1587 // Taking n-tuples of an infinite source is still infinite
1588 static constexpr bool infinite = Source::infinite;
1589 };
1590
1591 template <class Source, class Value, class Gen = Generator<Value, Source>>
1592 Gen compose(GenImpl<Value, Source>&& source) const {
1593 return Gen(std::move(source.self()), windowSize_);
1594 }
1595
1596 template <class Source, class Value, class Gen = Generator<Value, Source>>
1597 Gen compose(const GenImpl<Value, Source>& source) const {
1598 return Gen(source.self(), windowSize_);
1599 }
1600};
1601
1602/**
1603 * Concat - For flattening generators of generators.
1604 *
1605 * This type is usually used through the 'concat' static value, like:
1606 *
1607 * auto edges =
1608 * from(nodes)
1609 * | map([](Node& x) {
1610 * return from(x.neighbors)
1611 * | map([&](Node& y) {
1612 * return Edge(x, y);
1613 * });
1614 * })
1615 * | concat
1616 * | as<std::set>();
1617 */
1618class Concat : public Operator<Concat> {
1619 public:
1620 Concat() = default;
1621
1622 template <
1623 class Inner,
1624 class Source,
1625 class InnerValue = typename std::decay<Inner>::type::ValueType>
1626 class Generator
1627 : public GenImpl<InnerValue, Generator<Inner, Source, InnerValue>> {
1628 Source source_;
1629
1630 public:
1631 explicit Generator(Source source) : source_(std::move(source)) {}
1632
1633 template <class Handler>
1634 bool apply(Handler&& handler) const {
1635 return source_.apply([&](Inner inner) -> bool {
1636 return inner.apply(std::forward<Handler>(handler));
1637 });
1638 }
1639
1640 template <class Body>
1641 void foreach(Body&& body) const {
1642 source_.foreach(
1643 [&](Inner inner) { inner.foreach(std::forward<Body>(body)); });
1644 }
1645
1646 // Resulting concatenation is only finite if both Source and Inner are also
1647 // finite. In one sence, if dosn't make sence to call concat when the Inner
1648 // generator is infinite (you could just call first), so we could also just
1649 // static_assert if the inner is infinite. Taking the less restrictive
1650 // approch for now.
1651 static constexpr bool infinite =
1652 Source::infinite || std::decay<Inner>::type::infinite;
1653 };
1654
1655 template <class Value, class Source, class Gen = Generator<Value, Source>>
1656 Gen compose(GenImpl<Value, Source>&& source) const {
1657 return Gen(std::move(source.self()));
1658 }
1659
1660 template <class Value, class Source, class Gen = Generator<Value, Source>>
1661 Gen compose(const GenImpl<Value, Source>& source) const {
1662 return Gen(source.self());
1663 }
1664};
1665
1666/**
1667 * RangeConcat - For flattening generators of iterables.
1668 *
1669 * This type is usually used through the 'rconcat' static value, like:
1670 *
1671 * map<int, vector<int>> adjacency;
1672 * auto sinks =
1673 * from(adjacency)
1674 * | get<1>()
1675 * | rconcat()
1676 * | as<std::set>();
1677 */
1678class RangeConcat : public Operator<RangeConcat> {
1679 public:
1680 RangeConcat() = default;
1681
1682 template <
1683 class Range,
1684 class Source,
1685 class InnerValue = typename ValueTypeOfRange<Range>::RefType>
1686 class Generator
1687 : public GenImpl<InnerValue, Generator<Range, Source, InnerValue>> {
1688 Source source_;
1689
1690 public:
1691 explicit Generator(Source source) : source_(std::move(source)) {}
1692
1693 template <class Body>
1694 void foreach(Body&& body) const {
1695 source_.foreach([&](Range range) {
1696 for (auto& value : range) {
1697 body(value);
1698 }
1699 });
1700 }
1701
1702 template <class Handler>
1703 bool apply(Handler&& handler) const {
1704 return source_.apply([&](Range range) -> bool {
1705 for (auto& value : range) {
1706 if (!handler(value)) {
1707 return false;
1708 }
1709 }
1710 return true;
1711 });
1712 }
1713
1714 // This is similar to concat, except that the inner iterables all are finite
1715 // so the only thing that matters is that the source is infinite.
1716 static constexpr bool infinite = Source::infinite;
1717 };
1718
1719 template <class Value, class Source, class Gen = Generator<Value, Source>>
1720 Gen compose(GenImpl<Value, Source>&& source) const {
1721 return Gen(std::move(source.self()));
1722 }
1723
1724 template <class Value, class Source, class Gen = Generator<Value, Source>>
1725 Gen compose(const GenImpl<Value, Source>& source) const {
1726 return Gen(source.self());
1727 }
1728};
1729
1730/**
1731 * GuardImpl - For handling exceptions from downstream computation. Requires the
1732 * type of exception to catch, and handler function to invoke in the event of
1733 * the exception. Note that the handler may:
1734 * 1) return true to continue processing the sequence
1735 * 2) return false to end the sequence immediately
1736 * 3) throw, to pass the exception to the next catch
1737 * The handler must match the signature 'bool(Exception&, Value)'.
1738 *
1739 * This type is used through the `guard` helper, like so:
1740 *
1741 * auto indexes
1742 * = byLine(STDIN_FILENO)
1743 * | guard<std::runtime_error>([](std::runtime_error& e,
1744 * StringPiece sp) {
1745 * LOG(ERROR) << sp << ": " << e.str();
1746 * return true; // continue processing subsequent lines
1747 * })
1748 * | eachTo<int>()
1749 * | as<vector>();
1750 *
1751 * TODO(tjackson): Rename this back to Guard.
1752 **/
1753template <class Exception, class ErrorHandler>
1754class GuardImpl : public Operator<GuardImpl<Exception, ErrorHandler>> {
1755 ErrorHandler handler_;
1756
1757 public:
1758 explicit GuardImpl(ErrorHandler handler) : handler_(std::move(handler)) {}
1759
1760 template <class Value, class Source>
1761 class Generator : public GenImpl<Value, Generator<Value, Source>> {
1762 Source source_;
1763 ErrorHandler handler_;
1764
1765 public:
1766 explicit Generator(Source source, ErrorHandler handler)
1767 : source_(std::move(source)), handler_(std::move(handler)) {}
1768
1769 template <class Handler>
1770 bool apply(Handler&& handler) const {
1771 return source_.apply([&](Value value) -> bool {
1772 try {
1773 handler(std::forward<Value>(value));
1774 return true;
1775 } catch (Exception& e) {
1776 return handler_(e, std::forward<Value>(value));
1777 }
1778 });
1779 }
1780
1781 // Just passes value though, length unaffected
1782 static constexpr bool infinite = Source::infinite;
1783 };
1784
1785 template <class Value, class Source, class Gen = Generator<Value, Source>>
1786 Gen compose(GenImpl<Value, Source>&& source) const {
1787 return Gen(std::move(source.self()), handler_);
1788 }
1789
1790 template <class Value, class Source, class Gen = Generator<Value, Source>>
1791 Gen compose(const GenImpl<Value, Source>& source) const {
1792 return Gen(source.self(), handler_);
1793 }
1794};
1795
1796/**
1797 * Dereference - For dereferencing a sequence of pointers while filtering out
1798 * null pointers.
1799 *
1800 * This type is usually used through the 'dereference' static value, like:
1801 *
1802 * auto refs = from(ptrs) | dereference;
1803 */
1804class Dereference : public Operator<Dereference> {
1805 public:
1806 Dereference() = default;
1807
1808 template <
1809 class Value,
1810 class Source,
1811 class Result = decltype(*std::declval<Value>())>
1812 class Generator : public GenImpl<Result, Generator<Value, Source, Result>> {
1813 Source source_;
1814
1815 public:
1816 explicit Generator(Source source) : source_(std::move(source)) {}
1817
1818 template <class Body>
1819 void foreach(Body&& body) const {
1820 source_.foreach([&](Value value) {
1821 if (value) {
1822 return body(*std::forward<Value>(value));
1823 }
1824 });
1825 }
1826
1827 template <class Handler>
1828 bool apply(Handler&& handler) const {
1829 return source_.apply([&](Value value) -> bool {
1830 if (value) {
1831 return handler(*std::forward<Value>(value));
1832 }
1833 return true;
1834 });
1835 }
1836
1837 // Just passes value though, length unaffected
1838 static constexpr bool infinite = Source::infinite;
1839 };
1840
1841 template <class Source, class Value, class Gen = Generator<Value, Source>>
1842 Gen compose(GenImpl<Value, Source>&& source) const {
1843 return Gen(std::move(source.self()));
1844 }
1845
1846 template <class Source, class Value, class Gen = Generator<Value, Source>>
1847 Gen compose(const GenImpl<Value, Source>& source) const {
1848 return Gen(source.self());
1849 }
1850};
1851
1852/**
1853 * Indirect - For producing a sequence of the addresses of the values in the
1854 * input.
1855 *
1856 * This type is usually used through the 'indirect' static value, like:
1857 *
1858 * auto ptrs = from(refs) | indirect;
1859 */
1860class Indirect : public Operator<Indirect> {
1861 public:
1862 Indirect() = default;
1863
1864 template <
1865 class Value,
1866 class Source,
1867 class Result = typename std::remove_reference<Value>::type*>
1868 class Generator : public GenImpl<Result, Generator<Value, Source, Result>> {
1869 Source source_;
1870 static_assert(
1871 !std::is_rvalue_reference<Value>::value,
1872 "Cannot use indirect on an rvalue");
1873
1874 public:
1875 explicit Generator(Source source) : source_(std::move(source)) {}
1876
1877 template <class Body>
1878 void foreach(Body&& body) const {
1879 source_.foreach(
1880 [&](Value value) { return body(&std::forward<Value>(value)); });
1881 }
1882
1883 template <class Handler>
1884 bool apply(Handler&& handler) const {
1885 return source_.apply([&](Value value) -> bool {
1886 return handler(&std::forward<Value>(value));
1887 });
1888 }
1889
1890 // Just passes value though, length unaffected
1891 static constexpr bool infinite = Source::infinite;
1892 };
1893
1894 template <class Source, class Value, class Gen = Generator<Value, Source>>
1895 Gen compose(GenImpl<Value, Source>&& source) const {
1896 return Gen(std::move(source.self()));
1897 }
1898
1899 template <class Source, class Value, class Gen = Generator<Value, Source>>
1900 Gen compose(const GenImpl<Value, Source>& source) const {
1901 return Gen(source.self());
1902 }
1903};
1904
1905/**
1906 * Cycle - For repeating a sequence forever.
1907 *
1908 * This type is usually used through the 'cycle' static value, like:
1909 *
1910 * auto tests
1911 * = from(samples)
1912 * | cycle
1913 * | take(100);
1914 *
1915 * or in the finite case:
1916 *
1917 * auto thrice = g | cycle(3);
1918 */
1919template <bool forever>
1920class Cycle : public Operator<Cycle<forever>> {
1921 off_t limit_; // not used if forever == true
1922 public:
1923 Cycle() = default;
1924
1925 explicit Cycle(off_t limit) : limit_(limit) {
1926 static_assert(
1927 !forever,
1928 "Cycle limit constructor should not be used when forever == true.");
1929 }
1930
1931 template <class Value, class Source>
1932 class Generator : public GenImpl<Value, Generator<Value, Source>> {
1933 Source source_;
1934 off_t limit_;
1935
1936 public:
1937 explicit Generator(Source source, off_t limit)
1938 : source_(std::move(source)), limit_(limit) {}
1939
1940 template <class Handler>
1941 bool apply(Handler&& handler) const {
1942 bool cont;
1943 auto handler2 = [&](Value value) {
1944 cont = handler(std::forward<Value>(value));
1945 return cont;
1946 };
1947 // Becomes an infinte loop if forever == true
1948 for (off_t count = 0; (forever || count != limit_); ++count) {
1949 cont = false;
1950 source_.apply(handler2);
1951 if (!cont) {
1952 return false;
1953 }
1954 }
1955 return true;
1956 }
1957
1958 // This is the hardest one to infer. If we are simply doing a finite cycle,
1959 // then (gen | cycle(n)) is infinite if and only if gen is infinite.
1960 // However, if we are doing an infinite cycle, (gen | cycle) is infinite
1961 // unless gen is empty. However, we will always mark (gen | cycle) as
1962 // infinite, because patterns such as (gen | cycle | count) can either take
1963 // on exactly one value, or infinite loop.
1964 static constexpr bool infinite = forever || Source::infinite;
1965 };
1966
1967 template <class Source, class Value, class Gen = Generator<Value, Source>>
1968 Gen compose(GenImpl<Value, Source>&& source) const {
1969 return Gen(std::move(source.self()), limit_);
1970 }
1971
1972 template <class Source, class Value, class Gen = Generator<Value, Source>>
1973 Gen compose(const GenImpl<Value, Source>& source) const {
1974 return Gen(source.self(), limit_);
1975 }
1976
1977 /**
1978 * Convenience function for finite cycles used like:
1979 *
1980 * auto tripled = gen | cycle(3);
1981 */
1982 Cycle<false> operator()(off_t limit) const {
1983 return Cycle<false>(limit);
1984 }
1985};
1986
1987/*
1988 ******************************* Sinks *****************************************
1989 */
1990
1991/**
1992 * FoldLeft - Left-associative functional fold. For producing an aggregate value
1993 * from a seed and a folder function. Useful for custom aggregators on a
1994 * sequence.
1995 *
1996 * This type is primarily used through the 'foldl' helper method, like:
1997 *
1998 * double movingAverage = from(values)
1999 * | foldl(0.0, [](double avg, double sample) {
2000 * return sample * 0.1 + avg * 0.9;
2001 * });
2002 */
2003template <class Seed, class Fold>
2004class FoldLeft : public Operator<FoldLeft<Seed, Fold>> {
2005 Seed seed_;
2006 Fold fold_;
2007
2008 public:
2009 FoldLeft() = default;
2010 FoldLeft(Seed seed, Fold fold)
2011 : seed_(std::move(seed)), fold_(std::move(fold)) {}
2012
2013 template <class Source, class Value>
2014 Seed compose(const GenImpl<Value, Source>& source) const {
2015 static_assert(!Source::infinite, "Cannot foldl infinite source");
2016 Seed accum = seed_;
2017 source | [&](Value v) {
2018 accum = fold_(std::move(accum), std::forward<Value>(v));
2019 };
2020 return accum;
2021 }
2022};
2023
2024/**
2025 * First - For finding the first value in a sequence.
2026 *
2027 * This type is primarily used through the 'first' static value, like:
2028 *
2029 * int firstThreeDigitPrime = seq(100) | filter(isPrime) | first;
2030 */
2031class First : public Operator<First> {
2032 public:
2033 First() = default;
2034
2035 template <
2036 class Source,
2037 class Value,
2038 class StorageType = typename std::decay<Value>::type>
2039 Optional<StorageType> compose(const GenImpl<Value, Source>& source) const {
2040 Optional<StorageType> accum;
2041 source | [&](Value v) -> bool {
2042 accum = std::forward<Value>(v);
2043 return false;
2044 };
2045 return accum;
2046 }
2047};
2048
2049/**
2050 * IsEmpty - a helper class for isEmpty and notEmpty
2051 *
2052 * Essentially returns 'result' if the source is empty. Note that this cannot be
2053 * called on an infinite source, because then there is only one possible return
2054 * value.
2055 *
2056 *
2057 * Used primarily through 'isEmpty' and 'notEmpty' static values
2058 *
2059 * bool hasPrimes = g | filter(prime) | notEmpty;
2060 * bool lacksEvens = g | filter(even) | isEmpty;
2061 *
2062 * Also used in the implementation of 'any' and 'all'
2063 */
2064template <bool emptyResult>
2065class IsEmpty : public Operator<IsEmpty<emptyResult>> {
2066 public:
2067 IsEmpty() = default;
2068
2069 template <class Source, class Value>
2070 bool compose(const GenImpl<Value, Source>& source) const {
2071 static_assert(
2072 !Source::infinite,
2073 "Cannot call 'all', 'any', 'isEmpty', or 'notEmpty' on "
2074 "infinite source. 'all' and 'isEmpty' will either return "
2075 "false or hang. 'any' or 'notEmpty' will either return true "
2076 "or hang.");
2077 bool ans = emptyResult;
2078 source | [&](Value /* v */) -> bool {
2079 ans = !emptyResult;
2080 return false;
2081 };
2082 return ans;
2083 }
2084};
2085
2086/**
2087 * Reduce - Functional reduce, for recursively combining values from a source
2088 * using a reducer function until there is only one item left. Useful for
2089 * combining values when an empty sequence doesn't make sense.
2090 *
2091 * This type is primarily used through the 'reduce' helper method, like:
2092 *
2093 * sring longest = from(names)
2094 * | reduce([](string&& best, string& current) {
2095 * return best.size() >= current.size() ? best : current;
2096 * });
2097 */
2098template <class Reducer>
2099class Reduce : public Operator<Reduce<Reducer>> {
2100 Reducer reducer_;
2101
2102 public:
2103 Reduce() = default;
2104 explicit Reduce(Reducer reducer) : reducer_(std::move(reducer)) {}
2105
2106 template <
2107 class Source,
2108 class Value,
2109 class StorageType = typename std::decay<Value>::type>
2110 Optional<StorageType> compose(const GenImpl<Value, Source>& source) const {
2111 static_assert(!Source::infinite, "Cannot reduce infinite source");
2112 Optional<StorageType> accum;
2113 source | [&](Value v) {
2114 if (auto target = accum.get_pointer()) {
2115 *target = reducer_(std::move(*target), std::forward<Value>(v));
2116 } else {
2117 accum = std::forward<Value>(v);
2118 }
2119 };
2120 return accum;
2121 }
2122};
2123
2124/**
2125 * Count - for simply counting the items in a collection.
2126 *
2127 * This type is usually used through its singleton, 'count':
2128 *
2129 * auto shortPrimes = seq(1, 100) | filter(isPrime) | count;
2130 */
2131class Count : public Operator<Count> {
2132 public:
2133 Count() = default;
2134
2135 template <class Source, class Value>
2136 size_t compose(const GenImpl<Value, Source>& source) const {
2137 static_assert(!Source::infinite, "Cannot count infinite source");
2138 return foldl(
2139 size_t(0), [](size_t accum, Value /* v */) { return accum + 1; })
2140 .compose(source);
2141 }
2142};
2143
2144/**
2145 * Sum - For simply summing up all the values from a source.
2146 *
2147 * This type is usually used through its singleton, 'sum':
2148 *
2149 * auto gaussSum = seq(1, 100) | sum;
2150 */
2151class Sum : public Operator<Sum> {
2152 public:
2153 Sum() = default;
2154
2155 template <
2156 class Source,
2157 class Value,
2158 class StorageType = typename std::decay<Value>::type>
2159 StorageType compose(const GenImpl<Value, Source>& source) const {
2160 static_assert(!Source::infinite, "Cannot sum infinite source");
2161 return foldl(
2162 StorageType(0),
2163 [](StorageType&& accum, Value v) {
2164 return std::move(accum) + std::forward<Value>(v);
2165 })
2166 .compose(source);
2167 }
2168};
2169
2170/**
2171 * Contains - For testing whether a value matching the given value is contained
2172 * in a sequence.
2173 *
2174 * This type should be used through the 'contains' helper method, like:
2175 *
2176 * bool contained = seq(1, 10) | map(square) | contains(49);
2177 */
2178template <class Needle>
2179class Contains : public Operator<Contains<Needle>> {
2180 Needle needle_;
2181
2182 public:
2183 explicit Contains(Needle needle) : needle_(std::move(needle)) {}
2184
2185 template <
2186 class Source,
2187 class Value,
2188 class StorageType = typename std::decay<Value>::type>
2189 bool compose(const GenImpl<Value, Source>& source) const {
2190 static_assert(
2191 !Source::infinite,
2192 "Calling contains on an infinite source might cause "
2193 "an infinite loop.");
2194 return !(source | [this](Value value) {
2195 return !(needle_ == std::forward<Value>(value));
2196 });
2197 }
2198};
2199
2200/**
2201 * Min - For a value which minimizes a key, where the key is determined by a
2202 * given selector, and compared by given comparer.
2203 *
2204 * This type is usually used through the singletone 'min' or through the helper
2205 * functions 'minBy' and 'maxBy'.
2206 *
2207 * auto oldest = from(people)
2208 * | minBy([](Person& p) {
2209 * return p.dateOfBirth;
2210 * });
2211 */
2212template <class Selector, class Comparer>
2213class Min : public Operator<Min<Selector, Comparer>> {
2214 Selector selector_;
2215 Comparer comparer_;
2216
2217 template <typename T>
2218 const T& asConst(const T& t) const {
2219 return t;
2220 }
2221
2222 public:
2223 Min() = default;
2224
2225 explicit Min(Selector selector) : selector_(std::move(selector)) {}
2226
2227 Min(Selector selector, Comparer comparer)
2228 : selector_(std::move(selector)), comparer_(std::move(comparer)) {}
2229
2230 template <
2231 class Value,
2232 class Source,
2233 class StorageType = typename std::decay<Value>::type,
2234 class Key = typename std::decay<invoke_result_t<Selector, Value>>::type>
2235 Optional<StorageType> compose(const GenImpl<Value, Source>& source) const {
2236 static_assert(
2237 !Source::infinite,
2238 "Calling min or max on an infinite source will cause "
2239 "an infinite loop.");
2240 Optional<StorageType> min;
2241 Optional<Key> minKey;
2242 source | [&](Value v) {
2243 Key key = selector_(asConst(v)); // so that selector_ cannot mutate v
2244 if (auto lastKey = minKey.get_pointer()) {
2245 if (!comparer_(key, *lastKey)) {
2246 return;
2247 }
2248 }
2249 minKey = std::move(key);
2250 min = std::forward<Value>(v);
2251 };
2252 return min;
2253 }
2254};
2255
2256/**
2257 * Append - For collecting values from a source into a given output container
2258 * by appending.
2259 *
2260 * This type is usually used through the helper function 'appendTo', like:
2261 *
2262 * vector<int64_t> ids;
2263 * from(results) | map([](Person& p) { return p.id })
2264 * | appendTo(ids);
2265 */
2266template <class Collection>
2267class Append : public Operator<Append<Collection>> {
2268 Collection* collection_;
2269
2270 public:
2271 explicit Append(Collection* collection) : collection_(collection) {}
2272
2273 template <class Value, class Source>
2274 Collection& compose(const GenImpl<Value, Source>& source) const {
2275 static_assert(!Source::infinite, "Cannot appendTo with infinite source");
2276 source | [&](Value v) {
2277 collection_->insert(collection_->end(), std::forward<Value>(v));
2278 };
2279 return *collection_;
2280 }
2281};
2282
2283/**
2284 * Collect - For collecting values from a source in a collection of the desired
2285 * type.
2286 *
2287 * This type is usually used through the helper function 'as', like:
2288 *
2289 * std::string upper = from(stringPiece)
2290 * | map(&toupper)
2291 * | as<std::string>();
2292 */
2293template <class Collection>
2294class Collect : public Operator<Collect<Collection>> {
2295 public:
2296 Collect() = default;
2297
2298 template <
2299 class Value,
2300 class Source,
2301 class StorageType = typename std::decay<Value>::type>
2302 Collection compose(const GenImpl<Value, Source>& source) const {
2303 static_assert(
2304 !Source::infinite, "Cannot convert infinite source to object with as.");
2305 Collection collection;
2306 source | [&](Value v) {
2307 collection.insert(collection.end(), std::forward<Value>(v));
2308 };
2309 return collection;
2310 }
2311};
2312
2313/**
2314 * CollectTemplate - For collecting values from a source in a collection
2315 * constructed using the specified template type. Given the type of values
2316 * produced by the given generator, the collection type will be:
2317 * Container<Value, Allocator<Value>>
2318 *
2319 * The allocator defaults to std::allocator, so this may be used for the STL
2320 * containers by simply using operators like 'as<set>', 'as<deque>',
2321 * 'as<vector>'. 'as', here is the helper method which is the usual means of
2322 * constructing this operator.
2323 *
2324 * Example:
2325 *
2326 * set<string> uniqueNames = from(names) | as<set>();
2327 */
2328template <
2329 template <class, class> class Container,
2330 template <class> class Allocator>
2331class CollectTemplate : public Operator<CollectTemplate<Container, Allocator>> {
2332 public:
2333 CollectTemplate() = default;
2334
2335 template <
2336 class Value,
2337 class Source,
2338 class StorageType = typename std::decay<Value>::type,
2339 class Collection = Container<StorageType, Allocator<StorageType>>>
2340 Collection compose(const GenImpl<Value, Source>& source) const {
2341 static_assert(
2342 !Source::infinite, "Cannot convert infinite source to object with as.");
2343 Collection collection;
2344 source | [&](Value v) {
2345 collection.insert(collection.end(), std::forward<Value>(v));
2346 };
2347 return collection;
2348 }
2349};
2350
2351/**
2352 * UnwrapOr - For unwrapping folly::Optional values, or providing the given
2353 * fallback value. Usually used through the 'unwrapOr' helper like so:
2354 *
2355 * auto best = from(scores) | max | unwrapOr(-1);
2356 *
2357 * Note that the fallback value needn't match the value in the Optional it is
2358 * unwrapping. If mis-matched types are supported, the common type of the two is
2359 * returned by value. If the types match, a reference (T&& > T& > const T&) is
2360 * returned.
2361 */
2362template <class T>
2363class UnwrapOr {
2364 public:
2365 explicit UnwrapOr(T&& value) : value_(std::move(value)) {}
2366 explicit UnwrapOr(const T& value) : value_(value) {}
2367
2368 T& value() {
2369 return value_;
2370 }
2371 const T& value() const {
2372 return value_;
2373 }
2374
2375 private:
2376 T value_;
2377};
2378
2379template <class T>
2380T&& operator|(Optional<T>&& opt, UnwrapOr<T>&& fallback) {
2381 if (T* p = opt.get_pointer()) {
2382 return std::move(*p);
2383 }
2384 return std::move(fallback.value());
2385}
2386
2387template <class T>
2388T& operator|(Optional<T>& opt, UnwrapOr<T>& fallback) {
2389 if (T* p = opt.get_pointer()) {
2390 return *p;
2391 }
2392 return fallback.value();
2393}
2394
2395template <class T>
2396const T& operator|(const Optional<T>& opt, const UnwrapOr<T>& fallback) {
2397 if (const T* p = opt.get_pointer()) {
2398 return *p;
2399 }
2400 return fallback.value();
2401}
2402
2403// Mixed type unwrapping always returns values, moving where possible
2404template <
2405 class T,
2406 class U,
2407 class R = typename std::enable_if<
2408 !std::is_same<T, U>::value,
2409 typename std::common_type<T, U>::type>::type>
2410R operator|(Optional<T>&& opt, UnwrapOr<U>&& fallback) {
2411 if (T* p = opt.get_pointer()) {
2412 return std::move(*p);
2413 }
2414 return std::move(fallback.value());
2415}
2416
2417template <
2418 class T,
2419 class U,
2420 class R = typename std::enable_if<
2421 !std::is_same<T, U>::value,
2422 typename std::common_type<T, U>::type>::type>
2423R operator|(const Optional<T>& opt, UnwrapOr<U>&& fallback) {
2424 if (const T* p = opt.get_pointer()) {
2425 return *p;
2426 }
2427 return std::move(fallback.value());
2428}
2429
2430template <
2431 class T,
2432 class U,
2433 class R = typename std::enable_if<
2434 !std::is_same<T, U>::value,
2435 typename std::common_type<T, U>::type>::type>
2436R operator|(Optional<T>&& opt, const UnwrapOr<U>& fallback) {
2437 if (T* p = opt.get_pointer()) {
2438 return std::move(*p);
2439 }
2440 return fallback.value();
2441}
2442
2443template <
2444 class T,
2445 class U,
2446 class R = typename std::enable_if<
2447 !std::is_same<T, U>::value,
2448 typename std::common_type<T, U>::type>::type>
2449R operator|(const Optional<T>& opt, const UnwrapOr<U>& fallback) {
2450 if (const T* p = opt.get_pointer()) {
2451 return *p;
2452 }
2453 return fallback.value();
2454}
2455
2456/**
2457 * Unwrap - For unwrapping folly::Optional values in a folly::gen style. Usually
2458 * used through the 'unwrap' instace like so:
2459 *
2460 * auto best = from(scores) | max | unwrap; // may throw
2461 */
2462class Unwrap {};
2463
2464template <class T>
2465T&& operator|(Optional<T>&& opt, const Unwrap&) {
2466 return std::move(opt.value());
2467}
2468
2469template <class T>
2470T& operator|(Optional<T>& opt, const Unwrap&) {
2471 return opt.value();
2472}
2473
2474template <class T>
2475const T& operator|(const Optional<T>& opt, const Unwrap&) {
2476 return opt.value();
2477}
2478
2479} // namespace detail
2480
2481/**
2482 * VirtualGen<T> - For wrapping template types in simple polymorphic wrapper.
2483 **/
2484template <class Value>
2485class VirtualGen : public GenImpl<Value, VirtualGen<Value>> {
2486 class WrapperBase {
2487 public:
2488 virtual ~WrapperBase() noexcept {}
2489 virtual bool apply(const std::function<bool(Value)>& handler) const = 0;
2490 virtual void foreach(const std::function<void(Value)>& body) const = 0;
2491 virtual std::unique_ptr<const WrapperBase> clone() const = 0;
2492 };
2493
2494 template <class Wrapped>
2495 class WrapperImpl : public WrapperBase {
2496 Wrapped wrapped_;
2497
2498 public:
2499 explicit WrapperImpl(Wrapped wrapped) : wrapped_(std::move(wrapped)) {}
2500
2501 bool apply(const std::function<bool(Value)>& handler) const override {
2502 return wrapped_.apply(handler);
2503 }
2504
2505 void foreach(const std::function<void(Value)>& body) const override {
2506 wrapped_.foreach(body);
2507 }
2508
2509 std::unique_ptr<const WrapperBase> clone() const override {
2510 return std::unique_ptr<const WrapperBase>(new WrapperImpl(wrapped_));
2511 }
2512 };
2513
2514 std::unique_ptr<const WrapperBase> wrapper_;
2515
2516 public:
2517 template <class Self>
2518 /* implicit */ VirtualGen(Self source)
2519 : wrapper_(new WrapperImpl<Self>(std::move(source))) {}
2520
2521 VirtualGen(VirtualGen&& source) noexcept
2522 : wrapper_(std::move(source.wrapper_)) {}
2523
2524 VirtualGen(const VirtualGen& source) : wrapper_(source.wrapper_->clone()) {}
2525
2526 VirtualGen& operator=(const VirtualGen& source) {
2527 wrapper_.reset(source.wrapper_->clone());
2528 return *this;
2529 }
2530
2531 VirtualGen& operator=(VirtualGen&& source) noexcept {
2532 wrapper_ = std::move(source.wrapper_);
2533 return *this;
2534 }
2535
2536 bool apply(const std::function<bool(Value)>& handler) const {
2537 return wrapper_->apply(handler);
2538 }
2539
2540 void foreach(const std::function<void(Value)>& body) const {
2541 wrapper_->foreach(body);
2542 }
2543};
2544
2545/**
2546 * non-template operators, statically defined to avoid the need for anything but
2547 * the header.
2548 */
2549constexpr detail::Sum sum{};
2550
2551constexpr detail::Count count{};
2552
2553constexpr detail::First first{};
2554
2555constexpr detail::IsEmpty<true> isEmpty{};
2556
2557constexpr detail::IsEmpty<false> notEmpty{};
2558
2559constexpr detail::Min<Identity, Less> min{};
2560
2561constexpr detail::Min<Identity, Greater> max{};
2562
2563constexpr detail::Order<Identity> order{};
2564
2565constexpr detail::Distinct<Identity> distinct{};
2566
2567constexpr detail::Map<Move> move{};
2568
2569constexpr detail::Concat concat{};
2570
2571constexpr detail::RangeConcat rconcat{};
2572
2573constexpr detail::Cycle<true> cycle{};
2574
2575constexpr detail::Dereference dereference{};
2576
2577constexpr detail::Indirect indirect{};
2578
2579constexpr detail::Unwrap unwrap{};
2580
2581template <class Number>
2582inline detail::Take take(Number count) {
2583 if (count < 0) {
2584 throw std::invalid_argument("Negative value passed to take()");
2585 }
2586 return detail::Take(static_cast<size_t>(count));
2587}
2588
2589inline detail::Stride stride(size_t s) {
2590 return detail::Stride(s);
2591}
2592
2593template <class Random = std::default_random_engine>
2594inline detail::Sample<Random> sample(size_t count, Random rng = Random()) {
2595 return detail::Sample<Random>(count, std::move(rng));
2596}
2597
2598inline detail::Skip skip(size_t count) {
2599 return detail::Skip(count);
2600}
2601
2602inline detail::Batch batch(size_t batchSize) {
2603 return detail::Batch(batchSize);
2604}
2605
2606inline detail::Window window(size_t windowSize) {
2607 return detail::Window(windowSize);
2608}
2609
2610} // namespace gen
2611} // namespace folly
2612
2613FOLLY_POP_WARNING
2614