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. |
25 | FOLLY_PUSH_WARNING |
26 | FOLLY_GNU_DISABLE_WARNING("-Wshadow" ) |
27 | |
28 | namespace folly { |
29 | namespace gen { |
30 | |
31 | /** |
32 | * ArgumentReference - For determining ideal argument type to receive a value. |
33 | */ |
34 | template <class T> |
35 | struct 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 | */ |
47 | template <class Key, class Value> |
48 | class 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 | |
108 | namespace 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 | */ |
128 | template <class Container, class Value> |
129 | class 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 | */ |
171 | template <class StorageType, class Container> |
172 | class 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 | */ |
236 | template <class Iterator> |
237 | class 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 | */ |
278 | template <class Value, class SequenceImpl> |
279 | class 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 | **/ |
314 | template <class Value> |
315 | class 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 | |
329 | template <class Value, class Distance> |
330 | class 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 | |
346 | template <class Value> |
347 | class 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 | |
361 | template <class Value, class Distance> |
362 | class 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 | |
378 | template <class Value> |
379 | class 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 | **/ |
393 | template <class Value> |
394 | struct 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 | **/ |
405 | template <class Value, class Source> |
406 | class 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 | |
434 | template <class Value> |
435 | class 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 | |
449 | template <class Value> |
450 | class 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 | |
473 | template <class Value> |
474 | class 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 | */ |
509 | template <class Predicate> |
510 | class 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 | */ |
575 | template <class Predicate> |
576 | class 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 | */ |
636 | template <class Predicate> |
637 | class 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 | */ |
693 | class 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 | */ |
751 | template <class Visitor> |
752 | class 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 | */ |
807 | class 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 | */ |
870 | template <class Random> |
871 | class 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 | */ |
964 | class 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 | */ |
1038 | template <class Selector, class Comparer> |
1039 | class 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 | */ |
1144 | template <class Selector> |
1145 | class 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 | */ |
1220 | template <class Selector> |
1221 | class 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 | */ |
1316 | template <class Expected> |
1317 | class 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 | */ |
1346 | template <class Selector> |
1347 | class 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 | */ |
1414 | template <class Operators> |
1415 | class 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 | */ |
1443 | class 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 | */ |
1518 | class 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 | */ |
1618 | class 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 | */ |
1678 | class 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 | **/ |
1753 | template <class Exception, class ErrorHandler> |
1754 | class 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 | */ |
1804 | class 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 | */ |
1860 | class 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 | */ |
1919 | template <bool forever> |
1920 | class 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 | */ |
2003 | template <class Seed, class Fold> |
2004 | class 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 | */ |
2031 | class 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 | */ |
2064 | template <bool emptyResult> |
2065 | class 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 | */ |
2098 | template <class Reducer> |
2099 | class 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 | */ |
2131 | class 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 | */ |
2151 | class 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 | */ |
2178 | template <class Needle> |
2179 | class 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 | */ |
2212 | template <class Selector, class Comparer> |
2213 | class 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 | */ |
2266 | template <class Collection> |
2267 | class 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 | */ |
2293 | template <class Collection> |
2294 | class 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 | */ |
2328 | template < |
2329 | template <class, class> class Container, |
2330 | template <class> class Allocator> |
2331 | class 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 | */ |
2362 | template <class T> |
2363 | class 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 | |
2379 | template <class T> |
2380 | T&& 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 | |
2387 | template <class T> |
2388 | T& operator|(Optional<T>& opt, UnwrapOr<T>& fallback) { |
2389 | if (T* p = opt.get_pointer()) { |
2390 | return *p; |
2391 | } |
2392 | return fallback.value(); |
2393 | } |
2394 | |
2395 | template <class T> |
2396 | const 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 |
2404 | template < |
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> |
2410 | R 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 | |
2417 | template < |
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> |
2423 | R 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 | |
2430 | template < |
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> |
2436 | R 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 | |
2443 | template < |
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> |
2449 | R 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 | */ |
2462 | class Unwrap {}; |
2463 | |
2464 | template <class T> |
2465 | T&& operator|(Optional<T>&& opt, const Unwrap&) { |
2466 | return std::move(opt.value()); |
2467 | } |
2468 | |
2469 | template <class T> |
2470 | T& operator|(Optional<T>& opt, const Unwrap&) { |
2471 | return opt.value(); |
2472 | } |
2473 | |
2474 | template <class T> |
2475 | const 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 | **/ |
2484 | template <class Value> |
2485 | class 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 | */ |
2549 | constexpr detail::Sum sum{}; |
2550 | |
2551 | constexpr detail::Count count{}; |
2552 | |
2553 | constexpr detail::First first{}; |
2554 | |
2555 | constexpr detail::IsEmpty<true> isEmpty{}; |
2556 | |
2557 | constexpr detail::IsEmpty<false> notEmpty{}; |
2558 | |
2559 | constexpr detail::Min<Identity, Less> min{}; |
2560 | |
2561 | constexpr detail::Min<Identity, Greater> max{}; |
2562 | |
2563 | constexpr detail::Order<Identity> order{}; |
2564 | |
2565 | constexpr detail::Distinct<Identity> distinct{}; |
2566 | |
2567 | constexpr detail::Map<Move> move{}; |
2568 | |
2569 | constexpr detail::Concat concat{}; |
2570 | |
2571 | constexpr detail::RangeConcat rconcat{}; |
2572 | |
2573 | constexpr detail::Cycle<true> cycle{}; |
2574 | |
2575 | constexpr detail::Dereference dereference{}; |
2576 | |
2577 | constexpr detail::Indirect indirect{}; |
2578 | |
2579 | constexpr detail::Unwrap unwrap{}; |
2580 | |
2581 | template <class Number> |
2582 | inline 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 | |
2589 | inline detail::Stride stride(size_t s) { |
2590 | return detail::Stride(s); |
2591 | } |
2592 | |
2593 | template <class Random = std::default_random_engine> |
2594 | inline detail::Sample<Random> sample(size_t count, Random rng = Random()) { |
2595 | return detail::Sample<Random>(count, std::move(rng)); |
2596 | } |
2597 | |
2598 | inline detail::Skip skip(size_t count) { |
2599 | return detail::Skip(count); |
2600 | } |
2601 | |
2602 | inline detail::Batch batch(size_t batchSize) { |
2603 | return detail::Batch(batchSize); |
2604 | } |
2605 | |
2606 | inline detail::Window window(size_t windowSize) { |
2607 | return detail::Window(windowSize); |
2608 | } |
2609 | |
2610 | } // namespace gen |
2611 | } // namespace folly |
2612 | |
2613 | FOLLY_POP_WARNING |
2614 | |