folly/gen/Base-inl.h

   1 /*
   2  * Copyright 2014 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 // Ignore shadowing warnings within this file, so includers can use -Wshadow.
  22 #pragma GCC diagnostic push
  23 #pragma GCC diagnostic ignored "-Wshadow"
  24
  25 namespace folly { namespace gen {
  26
  27 /**
  28  * ArgumentReference - For determining ideal argument type to receive a value.
  29  */
  30 template <class T>
  31 struct ArgumentReference
  32     : public std::conditional<
  33           std::is_reference<T>::value,
  34           T, // T& -> T&, T&& -> T&&, const T& -> const T&
  35           typename std::conditional<std::is_const<T>::value,
  36                                     T&, // const int -> const int&
  37                                     T&& // int -> int&&
  38                                     >::type> {};
  39
  40 namespace detail {
  41
  42 /*
  43  * ReferencedSource - Generate values from an STL-like container using
  44  * iterators from .begin() until .end(). Value type defaults to the type of
  45  * *container->begin(). For std::vector<int>, this would be int&. Note that the
  46  * value here is a reference, so the values in the vector will be passed by
  47  * reference to downstream operators.
  48  *
  49  * This type is primarily used through the 'from' helper method, like:
  50  *
  51  *   string& longestName = from(names)
  52  *                       | maxBy([](string& s) { return s.size() });
  53  */
  54 template<class Container,
  55          class Value>
  56 class ReferencedSource :
  57     public GenImpl<Value, ReferencedSource<Container, Value>> {
  58   Container* container_;
  59 public:
  60   explicit ReferencedSource(Container* container)
  61     : container_(container) {}
  62
  63   template<class Body>
  64   void foreach(Body&& body) const {
  65     for (auto& value : *container_) {
  66       body(std::forward<Value>(value));
  67     }
  68   }
  69
  70   template<class Handler>
  71   bool apply(Handler&& handler) const {
  72     for (auto& value : *container_) {
  73       if (!handler(std::forward<Value>(value))) {
  74         return false;
  75       }
  76     }
  77     return true;
  78   }
  79 };
  80
  81 /**
  82  * CopiedSource - For producing values from eagerly from a sequence of values
  83  * whose storage is owned by this class. Useful for preparing a generator for
  84  * use after a source collection will no longer be available, or for when the
  85  * values are specified literally with an initializer list.
  86  *
  87  * This type is primarily used through the 'fromCopy' function, like:
  88  *
  89  *   auto sourceCopy = fromCopy(makeAVector());
  90  *   auto sum = sourceCopy | sum;
  91  *   auto max = sourceCopy | max;
  92  *
  93  * Though it is also used for the initializer_list specialization of from().
  94  */
  95 template<class StorageType,
  96          class Container>
  97 class CopiedSource :
  98   public GenImpl<const StorageType&,
  99                  CopiedSource<StorageType, Container>> {
 100   static_assert(
 101     !std::is_reference<StorageType>::value, "StorageType must be decayed");
 102  public:
 103   // Generator objects are often copied during normal construction as they are
 104   // encapsulated by downstream generators. It would be bad if this caused
 105   // a copy of the entire container each time, and since we're only exposing a
 106   // const reference to the value, it's safe to share it between multiple
 107   // generators.
 108   static_assert(
 109     !std::is_reference<Container>::value,
 110     "Can't copy into a reference");
 111   std::shared_ptr<const Container> copy_;
 112 public:
 113   typedef Container ContainerType;
 114
 115   template<class SourceContainer>
 116   explicit CopiedSource(const SourceContainer& container)
 117     : copy_(new Container(begin(container), end(container))) {}
 118
 119   explicit CopiedSource(Container&& container) :
 120     copy_(new Container(std::move(container))) {}
 121
 122   // To enable re-use of cached results.
 123   CopiedSource(const CopiedSource<StorageType, Container>& source)
 124     : copy_(source.copy_) {}
 125
 126   template<class Body>
 127   void foreach(Body&& body) const {
 128     for (const auto& value : *copy_) {
 129       body(value);
 130     }
 131   }
 132
 133   template<class Handler>
 134   bool apply(Handler&& handler) const {
 135     // The collection may be reused by others, we can't allow it to be changed.
 136     for (const auto& value : *copy_) {
 137       if (!handler(value)) {
 138         return false;
 139       }
 140     }
 141     return true;
 142   }
 143 };
 144
 145 /**
 146  * RangeSource - For producing values from a folly::Range. Useful for referring
 147  * to a slice of some container.
 148  *
 149  * This type is primarily used through the 'from' function, like:
 150  *
 151  *   auto rangeSource = from(folly::range(v.begin(), v.end()));
 152  *   auto sum = rangeSource | sum;
 153  *
 154  * Reminder: Be careful not to invalidate iterators when using ranges like this.
 155  */
 156 template<class Iterator>
 157 class RangeSource : public GenImpl<typename Range<Iterator>::reference,
 158                                    RangeSource<Iterator>> {
 159   Range<Iterator> range_;
 160  public:
 161   RangeSource() {}
 162   explicit RangeSource(Range<Iterator> range)
 163     : range_(std::move(range))
 164   {}
 165
 166   template<class Handler>
 167   bool apply(Handler&& handler) const {
 168     for (auto& value : range_) {
 169       if (!handler(value)) {
 170         return false;
 171       }
 172     }
 173     return true;
 174   }
 175
 176   template<class Body>
 177   void foreach(Body&& body) const {
 178     for (auto& value : range_) {
 179       body(value);
 180     }
 181   }
 182 };
 183
 184 /**
 185  * Sequence - For generating values from beginning value, incremented along the
 186  * way with the ++ and += operators. Iteration may continue indefinitely.
 187  * Value type specified explicitly.
 188  *
 189  * This type is primarily used through the 'seq' and 'range' function, like:
 190  *
 191  *   int total = seq(1, 10) | sum;
 192  *   auto indexes = range(0, 10);
 193  *   auto endless = seq(0); // 0, 1, 2, 3, ...
 194  */
 195 template<class Value, class SequenceImpl>
 196 class Sequence : public GenImpl<const Value&, Sequence<Value, SequenceImpl>> {
 197   static_assert(!std::is_reference<Value>::value &&
 198                 !std::is_const<Value>::value, "Value mustn't be const or ref.");
 199   Value start_;
 200   SequenceImpl impl_;
 201 public:
 202   explicit Sequence(Value start, SequenceImpl impl)
 203       : start_(std::move(start)), impl_(std::move(impl)) { }
 204
 205   template<class Handler>
 206   bool apply(Handler&& handler) const {
 207     for (Value current = start_; impl_.test(current); impl_.step(current)) {
 208       if (!handler(current)) {
 209         return false;
 210       }
 211     }
 212     return true;
 213   }
 214
 215   template<class Body>
 216   void foreach(Body&& body) const {
 217     for (Value current = start_; impl_.test(current); impl_.step(current)) {
 218       body(current);
 219     }
 220   }
 221 };
 222
 223 /**
 224  * Sequence implementations (range, sequence, infinite, with/without step)
 225  **/
 226 template<class Value>
 227 class RangeImpl {
 228   Value end_;
 229  public:
 230   explicit RangeImpl(Value end) : end_(std::move(end)) { }
 231   bool test(const Value& current) const { return current < end_; }
 232   void step(Value& current) const { ++current; }
 233 };
 234
 235 template<class Value, class Distance>
 236 class RangeWithStepImpl {
 237   Value end_;
 238   Distance step_;
 239  public:
 240   explicit RangeWithStepImpl(Value end, Distance step)
 241     : end_(std::move(end)), step_(std::move(step)) { }
 242   bool test(const Value& current) const { return current < end_; }
 243   void step(Value& current) const { current += step_; }
 244 };
 245
 246 template<class Value>
 247 class SeqImpl {
 248   Value end_;
 249  public:
 250   explicit SeqImpl(Value end) : end_(std::move(end)) { }
 251   bool test(const Value& current) const { return current <= end_; }
 252   void step(Value& current) const { ++current; }
 253 };
 254
 255 template<class Value, class Distance>
 256 class SeqWithStepImpl {
 257   Value end_;
 258   Distance step_;
 259  public:
 260   explicit SeqWithStepImpl(Value end, Distance step)
 261     : end_(std::move(end)), step_(std::move(step)) { }
 262   bool test(const Value& current) const { return current <= end_; }
 263   void step(Value& current) const { current += step_; }
 264 };
 265
 266 template<class Value>
 267 class InfiniteImpl {
 268  public:
 269   bool test(const Value& current) const { return true; }
 270   void step(Value& current) const { ++current; }
 271 };
 272
 273 /**
 274  * GenratorBuilder - Helper for GENERTATOR macro.
 275  **/
 276 template<class Value>
 277 struct GeneratorBuilder {
 278   template<class Source,
 279            class Yield = detail::Yield<Value, Source>>
 280   Yield operator+(Source&& source) {
 281     return Yield(std::forward<Source>(source));
 282   }
 283 };
 284
 285 /**
 286  * Yield - For producing values from a user-defined generator by way of a
 287  * 'yield' function.
 288  **/
 289 template<class Value, class Source>
 290 class Yield : public GenImpl<Value, Yield<Value, Source>> {
 291   Source source_;
 292  public:
 293   explicit Yield(Source source)
 294     : source_(std::move(source)) {
 295   }
 296
 297   template<class Handler>
 298   bool apply(Handler&& handler) const {
 299     struct Break {};
 300     auto body = [&](Value value) {
 301       if (!handler(std::forward<Value>(value))) {
 302         throw Break();
 303       }
 304     };
 305     try {
 306       source_(body);
 307       return true;
 308     } catch (Break&) {
 309       return false;
 310     }
 311   }
 312
 313   template<class Body>
 314   void foreach(Body&& body) const {
 315     source_(std::forward<Body>(body));
 316   }
 317 };
 318
 319 template<class Value>
 320 class Empty : public GenImpl<Value, Empty<Value>> {
 321  public:
 322   template <class Handler>
 323   bool apply(Handler&&) const {
 324     return true;
 325   }
 326
 327   template <class Body>
 328   void foreach(Body&&) const {}
 329 };
 330
 331 template<class Value>
 332 class Just : public GenImpl<const Value&, Just<Value>> {
 333   static_assert(!std::is_reference<Value>::value,
 334                 "Just requires non-ref types");
 335   const Value value_;
 336  public:
 337   Just(Value value) : value_(std::forward<Value>(value)) {}
 338
 339   template <class Handler>
 340   bool apply(Handler&& handler) const {
 341     return handler(value_);
 342   }
 343
 344   template <class Body>
 345   void foreach(Body&& body) const {
 346     body(value_);
 347   }
 348 };
 349
 350 /*
 351  * Operators
 352  */
 353
 354 /**
 355  * Map - For producing a sequence of values by passing each value from a source
 356  * collection through a predicate.
 357  *
 358  * This type is usually used through the 'map' or 'mapped' helper function:
 359  *
 360  *   auto squares = seq(1, 10) | map(square) | asVector;
 361  */
 362 template<class Predicate>
 363 class Map : public Operator<Map<Predicate>> {
 364   Predicate pred_;
 365  public:
 366   Map() {}
 367
 368   explicit Map(Predicate pred)
 369     : pred_(std::move(pred))
 370   { }
 371
 372   template<class Value,
 373            class Source,
 374            class Result = typename ArgumentReference<
 375                             typename std::result_of<Predicate(Value)>::type
 376                           >::type>
 377   class Generator :
 378       public GenImpl<Result, Generator<Value, Source, Result>> {
 379     Source source_;
 380     Predicate pred_;
 381   public:
 382     explicit Generator(Source source, const Predicate& pred)
 383       : source_(std::move(source)), pred_(pred) {}
 384
 385     template<class Body>
 386     void foreach(Body&& body) const {
 387       source_.foreach([&](Value value) {
 388         body(pred_(std::forward<Value>(value)));
 389       });
 390     }
 391
 392     template<class Handler>
 393     bool apply(Handler&& handler) const {
 394       return source_.apply([&](Value value) {
 395         return handler(pred_(std::forward<Value>(value)));
 396       });
 397     }
 398
 399     static constexpr bool infinite = Source::infinite;
 400   };
 401
 402   template<class Source,
 403            class Value,
 404            class Gen = Generator<Value, Source>>
 405   Gen compose(GenImpl<Value, Source>&& source) const {
 406     return Gen(std::move(source.self()), pred_);
 407   }
 408
 409   template<class Source,
 410            class Value,
 411            class Gen = Generator<Value, Source>>
 412   Gen compose(const GenImpl<Value, Source>& source) const {
 413     return Gen(source.self(), pred_);
 414   }
 415 };
 416
 417
 418 /**
 419  * Filter - For filtering values from a source sequence by a predicate.
 420  *
 421  * This type is usually used through the 'filter' helper function, like:
 422  *
 423  *   auto nonEmpty = from(strings)
 424  *                 | filter([](const string& str) -> bool {
 425  *                     return !str.empty();
 426  *                   });
 427  */
 428 template<class Predicate>
 429 class Filter : public Operator<Filter<Predicate>> {
 430   Predicate pred_;
 431  public:
 432   Filter() {}
 433   explicit Filter(Predicate pred)
 434     : pred_(std::move(pred))
 435   { }
 436
 437   template<class Value,
 438            class Source>
 439   class Generator : public GenImpl<Value, Generator<Value, Source>> {
 440     Source source_;
 441     Predicate pred_;
 442   public:
 443     explicit Generator(Source source, const Predicate& pred)
 444       : source_(std::move(source)), pred_(pred) {}
 445
 446     template<class Body>
 447     void foreach(Body&& body) const {
 448       source_.foreach([&](Value value) {
 449         if (pred_(std::forward<Value>(value))) {
 450           body(std::forward<Value>(value));
 451         }
 452       });
 453     }
 454
 455     template<class Handler>
 456     bool apply(Handler&& handler) const {
 457       return source_.apply([&](Value value) -> bool {
 458         if (pred_(std::forward<Value>(value))) {
 459           return handler(std::forward<Value>(value));
 460         }
 461         return true;
 462       });
 463     }
 464
 465     static constexpr bool infinite = Source::infinite;
 466   };
 467
 468   template<class Source,
 469            class Value,
 470            class Gen = Generator<Value, Source>>
 471   Gen compose(GenImpl<Value, Source>&& source) const {
 472     return Gen(std::move(source.self()), pred_);
 473   }
 474
 475   template<class Source,
 476            class Value,
 477            class Gen = Generator<Value, Source>>
 478   Gen compose(const GenImpl<Value, Source>& source) const {
 479     return Gen(source.self(), pred_);
 480   }
 481 };
 482
 483 /**
 484  * Until - For producing values from a source until a predicate is satisfied.
 485  *
 486  * This type is usually used through the 'until' helper function, like:
 487  *
 488  *   auto best = from(sortedItems)
 489  *             | until([](Item& item) { return item.score > 100; })
 490  *             | asVector;
 491  */
 492 template<class Predicate>
 493 class Until : public Operator<Until<Predicate>> {
 494   Predicate pred_;
 495  public:
 496   Until() {}
 497   explicit Until(Predicate pred)
 498     : pred_(std::move(pred))
 499   {}
 500
 501   template<class Value,
 502            class Source>
 503   class Generator : public GenImpl<Value, Generator<Value, Source>> {
 504     Source source_;
 505     Predicate pred_;
 506    public:
 507     explicit Generator(Source source, const Predicate& pred)
 508       : source_(std::move(source)), pred_(pred) {}
 509
 510     template<class Handler>
 511     bool apply(Handler&& handler) const {
 512       bool cancelled = false;
 513       source_.apply([&](Value value) -> bool {
 514         if (pred_(value)) { // un-forwarded to disable move
 515           return false;
 516         }
 517         if (!handler(std::forward<Value>(value))) {
 518           cancelled = true;
 519           return false;
 520         }
 521         return true;
 522       });
 523       return !cancelled;
 524     }
 525   };
 526
 527   template<class Source,
 528            class Value,
 529            class Gen = Generator<Value, Source>>
 530   Gen compose(GenImpl<Value, Source>&& source) const {
 531     return Gen(std::move(source.self()), pred_);
 532   }
 533
 534   template<class Source,
 535            class Value,
 536            class Gen = Generator<Value, Source>>
 537   Gen compose(const GenImpl<Value, Source>& source) const {
 538     return Gen(source.self(), pred_);
 539   }
 540
 541   // Theoretically an 'until' might stop an infinite
 542   static constexpr bool infinite = false;
 543 };
 544
 545 /**
 546  * Take - For producing up to N values from a source.
 547  *
 548  * This type is usually used through the 'take' helper function, like:
 549  *
 550  *   auto best = from(docs)
 551  *             | orderByDescending(scoreDoc)
 552  *             | take(10);
 553  */
 554 class Take : public Operator<Take> {
 555   size_t count_;
 556  public:
 557   explicit Take(size_t count)
 558     : count_(count) {}
 559
 560   template<class Value,
 561            class Source>
 562   class Generator :
 563       public GenImpl<Value, Generator<Value, Source>> {
 564     Source source_;
 565     size_t count_;
 566   public:
 567     explicit Generator(Source source, size_t count)
 568       : source_(std::move(source)) , count_(count) {}
 569
 570     template<class Handler>
 571     bool apply(Handler&& handler) const {
 572       if (count_ == 0) { return false; }
 573       size_t n = count_;
 574       bool cancelled = false;
 575       source_.apply([&](Value value) -> bool {
 576         if (!handler(std::forward<Value>(value))) {
 577           cancelled = true;
 578           return false;
 579         }
 580         return --n;
 581       });
 582       return !cancelled;
 583     }
 584   };
 585
 586   template<class Source,
 587            class Value,
 588            class Gen = Generator<Value, Source>>
 589   Gen compose(GenImpl<Value, Source>&& source) const {
 590     return Gen(std::move(source.self()), count_);
 591   }
 592
 593   template<class Source,
 594            class Value,
 595            class Gen = Generator<Value, Source>>
 596   Gen compose(const GenImpl<Value, Source>& source) const {
 597     return Gen(source.self(), count_);
 598   }
 599 };
 600
 601 /**
 602  * Sample - For taking a random sample of N elements from a sequence
 603  * (without replacement).
 604  */
 605 template<class Random>
 606 class Sample : public Operator<Sample<Random>> {
 607   size_t count_;
 608   Random rng_;
 609  public:
 610   explicit Sample(size_t count, Random rng)
 611     : count_(count), rng_(std::move(rng)) {}
 612
 613   template<class Value,
 614            class Source,
 615            class Rand,
 616            class StorageType = typename std::decay<Value>::type>
 617   class Generator :
 618           public GenImpl<StorageType&&,
 619                          Generator<Value, Source, Rand, StorageType>> {
 620     static_assert(!Source::infinite, "Cannot sample infinite source!");
 621     // It's too easy to bite ourselves if random generator is only 16-bit
 622     static_assert(Random::max() >= std::numeric_limits<int32_t>::max() - 1,
 623                   "Random number generator must support big values");
 624     Source source_;
 625     size_t count_;
 626     mutable Rand rng_;
 627   public:
 628     explicit Generator(Source source, size_t count, Random rng)
 629       : source_(std::move(source)) , count_(count), rng_(std::move(rng)) {}
 630
 631     template<class Handler>
 632     bool apply(Handler&& handler) const {
 633       if (count_ == 0) { return false; }
 634       std::vector<StorageType> v;
 635       v.reserve(count_);
 636       // use reservoir sampling to give each source value an equal chance
 637       // of appearing in our output.
 638       size_t n = 1;
 639       source_.foreach([&](Value value) -> void {
 640           if (v.size() < count_) {
 641             v.push_back(std::forward<Value>(value));
 642           } else {
 643             // alternatively, we could create a std::uniform_int_distribution
 644             // instead of using modulus, but benchmarks show this has
 645             // substantial overhead.
 646             size_t index = rng_() % n;
 647             if (index < v.size()) {
 648               v[index] = std::forward<Value>(value);
 649             }
 650           }
 651           ++n;
 652         });
 653
 654       // output is unsorted!
 655       for (auto& val: v) {
 656         if (!handler(std::move(val))) {
 657           return false;
 658         }
 659       }
 660       return true;
 661     }
 662   };
 663
 664   template<class Source,
 665            class Value,
 666            class Gen = Generator<Value, Source, Random>>
 667   Gen compose(GenImpl<Value, Source>&& source) const {
 668     return Gen(std::move(source.self()), count_, rng_);
 669   }
 670
 671   template<class Source,
 672            class Value,
 673            class Gen = Generator<Value, Source, Random>>
 674   Gen compose(const GenImpl<Value, Source>& source) const {
 675     return Gen(source.self(), count_, rng_);
 676   }
 677 };
 678
 679 /**
 680  * Skip - For skipping N items from the beginning of a source generator.
 681  *
 682  * This type is usually used through the 'skip' helper function, like:
 683  *
 684  *   auto page = from(results)
 685  *             | skip(pageSize * startPage)
 686  *             | take(10);
 687  */
 688 class Skip : public Operator<Skip> {
 689   size_t count_;
 690  public:
 691   explicit Skip(size_t count)
 692     : count_(count) {}
 693
 694   template<class Value,
 695            class Source>
 696   class Generator :
 697       public GenImpl<Value, Generator<Value, Source>> {
 698     Source source_;
 699     size_t count_;
 700    public:
 701     explicit Generator(Source source, size_t count)
 702       : source_(std::move(source)) , count_(count) {}
 703
 704     template<class Body>
 705     void foreach(Body&& body) const {
 706       if (count_ == 0) {
 707         source_.foreach(body);
 708         return;
 709       }
 710       size_t n = 0;
 711       source_.foreach([&](Value value) {
 712           if (n < count_) {
 713             ++n;
 714           } else {
 715             body(std::forward<Value>(value));
 716           }
 717         });
 718     }
 719
 720     template<class Handler>
 721     bool apply(Handler&& handler) const {
 722       if (count_ == 0) {
 723         return source_.apply(std::forward<Handler>(handler));
 724       }
 725       size_t n = 0;
 726       return source_.apply([&](Value value) -> bool {
 727           if (n < count_) {
 728             ++n;
 729             return true;
 730           }
 731           return handler(std::forward<Value>(value));
 732         });
 733     }
 734
 735     static constexpr bool infinite = Source::infinite;
 736   };
 737
 738   template<class Source,
 739            class Value,
 740            class Gen = Generator<Value, Source>>
 741   Gen compose(GenImpl<Value, Source>&& source) const {
 742     return Gen(std::move(source.self()), count_);
 743   }
 744
 745   template<class Source,
 746            class Value,
 747            class Gen = Generator<Value, Source>>
 748   Gen compose(const GenImpl<Value, Source>& source) const {
 749     return Gen(source.self(), count_);
 750   }
 751 };
 752
 753 /**
 754  * Order - For ordering a sequence of values from a source by key.
 755  * The key is extracted by the given selector functor, and this key is then
 756  * compared using the specified comparator.
 757  *
 758  * This type is usually used through the 'order' helper function, like:
 759  *
 760  *   auto closest = from(places)
 761  *                | orderBy([](Place& p) {
 762  *                    return -distance(p.location, here);
 763  *                  })
 764  *                | take(10);
 765  */
 766 template<class Selector, class Comparer>
 767 class Order : public Operator<Order<Selector, Comparer>> {
 768   Selector selector_;
 769   Comparer comparer_;
 770  public:
 771   Order() {}
 772
 773   explicit Order(Selector selector)
 774     : selector_(std::move(selector))
 775   {}
 776
 777   Order(Selector selector,
 778         Comparer comparer)
 779     : selector_(std::move(selector))
 780     , comparer_(std::move(comparer))
 781   {}
 782
 783   template<class Value,
 784            class Source,
 785            class StorageType = typename std::decay<Value>::type,
 786            class Result = typename std::result_of<Selector(Value)>::type>
 787   class Generator :
 788     public GenImpl<StorageType&&,
 789                    Generator<Value, Source, StorageType, Result>> {
 790     static_assert(!Source::infinite, "Cannot sort infinite source!");
 791     Source source_;
 792     Selector selector_;
 793     Comparer comparer_;
 794
 795     typedef std::vector<StorageType> VectorType;
 796
 797     VectorType asVector() const {
 798       auto comparer = [&](const StorageType& a, const StorageType& b) {
 799         return comparer_(selector_(a), selector_(b));
 800       };
 801       auto vals = source_ | as<VectorType>();
 802       std::sort(vals.begin(), vals.end(), comparer);
 803       return std::move(vals);
 804     }
 805    public:
 806     Generator(Source source,
 807               Selector selector,
 808               Comparer comparer)
 809       : source_(std::move(source)),
 810         selector_(std::move(selector)),
 811         comparer_(std::move(comparer)) {}
 812
 813     VectorType operator|(const Collect<VectorType>&) const {
 814       return asVector();
 815     }
 816
 817     VectorType operator|(const CollectTemplate<std::vector>&) const {
 818       return asVector();
 819     }
 820
 821     template<class Body>
 822     void foreach(Body&& body) const {
 823       for (auto& value : asVector()) {
 824         body(std::move(value));
 825       }
 826     }
 827
 828     template<class Handler>
 829     bool apply(Handler&& handler) const {
 830       auto comparer = [&](const StorageType& a, const StorageType& b) {
 831         // swapped for minHeap
 832         return comparer_(selector_(b), selector_(a));
 833       };
 834       auto heap = source_ | as<VectorType>();
 835       std::make_heap(heap.begin(), heap.end(), comparer);
 836       while (!heap.empty()) {
 837         std::pop_heap(heap.begin(), heap.end(), comparer);
 838         if (!handler(std::move(heap.back()))) {
 839           return false;
 840         }
 841         heap.pop_back();
 842       }
 843       return true;
 844     }
 845   };
 846
 847   template<class Source,
 848            class Value,
 849            class Gen = Generator<Value, Source>>
 850   Gen compose(GenImpl<Value, Source>&& source) const {
 851     return Gen(std::move(source.self()), selector_, comparer_);
 852   }
 853
 854   template<class Source,
 855            class Value,
 856            class Gen = Generator<Value, Source>>
 857   Gen compose(const GenImpl<Value, Source>& source) const {
 858     return Gen(source.self(), selector_, comparer_);
 859   }
 860 };
 861
 862 /*
 863  * TypeAssertion - For verifying the exact type of the value produced by a
 864  * generator. Useful for testing and debugging, and acts as a no-op at runtime.
 865  * Pass-through at runtime. Used through the 'assert_type<>()' factory method
 866  * like so:
 867  *
 868  *   auto c =  from(vector) | assert_type<int&>() | sum;
 869  *
 870  */
 871 template<class Expected>
 872 class TypeAssertion : public Operator<TypeAssertion<Expected>> {
 873  public:
 874   template<class Source, class Value>
 875   const Source& compose(const GenImpl<Value, Source>& source) const {
 876     static_assert(std::is_same<Expected, Value>::value,
 877                   "assert_type() check failed");
 878     return source.self();
 879   }
 880
 881   template<class Source, class Value>
 882   Source&& compose(GenImpl<Value, Source>&& source) const {
 883     static_assert(std::is_same<Expected, Value>::value,
 884                   "assert_type() check failed");
 885     return std::move(source.self());
 886   }
 887 };
 888
 889 /**
 890  * Distinct - For filtering duplicates out of a sequence. A selector may be
 891  * provided to generate a key to uniquify for each value.
 892  *
 893  * This type is usually used through the 'distinct' helper function, like:
 894  *
 895  *   auto closest = from(results)
 896  *                | distinctBy([](Item& i) {
 897  *                    return i.target;
 898  *                  })
 899  *                | take(10);
 900  */
 901 template<class Selector>
 902 class Distinct : public Operator<Distinct<Selector>> {
 903   Selector selector_;
 904  public:
 905   Distinct() {}
 906
 907   explicit Distinct(Selector selector)
 908     : selector_(std::move(selector))
 909   {}
 910
 911   template<class Value,
 912            class Source>
 913   class Generator : public GenImpl<Value, Generator<Value, Source>> {
 914     Source source_;
 915     Selector selector_;
 916
 917     typedef typename std::decay<Value>::type StorageType;
 918
 919     // selector_ cannot be passed an rvalue or it would end up passing the husk
 920     // of a value to the downstream operators.
 921     typedef const StorageType& ParamType;
 922
 923     typedef typename std::result_of<Selector(ParamType)>::type KeyType;
 924     typedef typename std::decay<KeyType>::type KeyStorageType;
 925
 926    public:
 927     Generator(Source source,
 928               Selector selector)
 929       : source_(std::move(source)),
 930         selector_(std::move(selector)) {}
 931
 932     template<class Body>
 933     void foreach(Body&& body) const {
 934       std::unordered_set<KeyStorageType> keysSeen;
 935       source_.foreach([&](Value value) {
 936         if (keysSeen.insert(selector_(ParamType(value))).second) {
 937           body(std::forward<Value>(value));
 938         }
 939       });
 940     }
 941
 942     template<class Handler>
 943     bool apply(Handler&& handler) const {
 944       std::unordered_set<KeyStorageType> keysSeen;
 945       return source_.apply([&](Value value) -> bool {
 946         if (keysSeen.insert(selector_(ParamType(value))).second) {
 947           return handler(std::forward<Value>(value));
 948         }
 949         return true;
 950       });
 951     }
 952   };
 953
 954   template<class Source,
 955            class Value,
 956            class Gen = Generator<Value, Source>>
 957   Gen compose(GenImpl<Value, Source>&& source) const {
 958     return Gen(std::move(source.self()), selector_);
 959   }
 960
 961   template<class Source,
 962            class Value,
 963            class Gen = Generator<Value, Source>>
 964   Gen compose(const GenImpl<Value, Source>& source) const {
 965     return Gen(source.self(), selector_);
 966   }
 967 };
 968
 969 /**
 970  * Composer - Helper class for adapting pipelines into functors. Primarily used
 971  * for 'mapOp'.
 972  */
 973 template<class Operators>
 974 class Composer {
 975   Operators op_;
 976  public:
 977   explicit Composer(Operators op)
 978     : op_(std::move(op)) {}
 979
 980   template<class Source,
 981            class Ret = decltype(std::declval<Operators>()
 982                                   .compose(std::declval<Source>()))>
 983   Ret operator()(Source&& source) const {
 984     return op_.compose(std::forward<Source>(source));
 985   }
 986 };
 987
 988 /**
 989  * Batch - For producing fixed-size batches of each value from a source.
 990  *
 991  * This type is usually used through the 'batch' helper function:
 992  *
 993  *   auto batchSums
 994  *     = seq(1, 10)
 995  *     | batch(3)
 996  *     | map([](const std::vector<int>& batch) {
 997  *         return from(batch) | sum;
 998  *       })
 999  *     | as<vector>();
1000  */
1001 class Batch : public Operator<Batch> {
1002   size_t batchSize_;
1003  public:
1004   explicit Batch(size_t batchSize)
1005     : batchSize_(batchSize) {
1006     if (batchSize_ == 0) {
1007       throw std::invalid_argument("Batch size must be non-zero!");
1008     }
1009   }
1010
1011   template<class Value,
1012            class Source,
1013            class StorageType = typename std::decay<Value>::type,
1014            class VectorType = std::vector<StorageType>>
1015   class Generator :
1016       public GenImpl<VectorType&,
1017                      Generator<Value, Source, StorageType, VectorType>> {
1018     Source source_;
1019     size_t batchSize_;
1020   public:
1021     explicit Generator(Source source, size_t batchSize)
1022       : source_(std::move(source))
1023       , batchSize_(batchSize) {}
1024
1025     template<class Handler>
1026     bool apply(Handler&& handler) const {
1027       VectorType batch_;
1028       batch_.reserve(batchSize_);
1029       bool shouldContinue = source_.apply([&](Value value) -> bool {
1030           batch_.push_back(std::forward<Value>(value));
1031           if (batch_.size() == batchSize_) {
1032             bool needMore = handler(batch_);
1033             batch_.clear();
1034             return needMore;
1035           }
1036           // Always need more if the handler is not called.
1037           return true;
1038         });
1039       // Flush everything, if and only if `handler` hasn't returned false.
1040       if (shouldContinue && !batch_.empty()) {
1041         shouldContinue = handler(batch_);
1042         batch_.clear();
1043       }
1044       return shouldContinue;
1045     }
1046
1047     static constexpr bool infinite = Source::infinite;
1048   };
1049
1050   template<class Source,
1051            class Value,
1052            class Gen = Generator<Value, Source>>
1053   Gen compose(GenImpl<Value, Source>&& source) const {
1054     return Gen(std::move(source.self()), batchSize_);
1055   }
1056
1057   template<class Source,
1058            class Value,
1059            class Gen = Generator<Value, Source>>
1060   Gen compose(const GenImpl<Value, Source>& source) const {
1061     return Gen(source.self(), batchSize_);
1062   }
1063 };
1064 /*
1065  * Sinks
1066  */
1067
1068 /**
1069  * FoldLeft - Left-associative functional fold. For producing an aggregate value
1070  * from a seed and a folder function. Useful for custom aggregators on a
1071  * sequence.
1072  *
1073  * This type is primarily used through the 'foldl' helper method, like:
1074  *
1075  *   double movingAverage = from(values)
1076  *                        | foldl(0.0, [](double avg, double sample) {
1077  *                            return sample * 0.1 + avg * 0.9;
1078  *                          });
1079  */
1080 template<class Seed,
1081          class Fold>
1082 class FoldLeft : public Operator<FoldLeft<Seed, Fold>> {
1083   Seed seed_;
1084   Fold fold_;
1085  public:
1086   FoldLeft() {}
1087   FoldLeft(Seed seed,
1088            Fold fold)
1089     : seed_(std::move(seed))
1090     , fold_(std::move(fold))
1091   {}
1092
1093   template<class Source,
1094            class Value>
1095   Seed compose(const GenImpl<Value, Source>& source) const {
1096     static_assert(!Source::infinite, "Cannot foldl infinite source");
1097     Seed accum = seed_;
1098     source | [&](Value v) {
1099       accum = fold_(std::move(accum), std::forward<Value>(v));
1100     };
1101     return accum;
1102   }
1103 };
1104
1105 /**
1106  * First - For finding the first value in a sequence.
1107  *
1108  * This type is primarily used through the 'first' static value, like:
1109  *
1110  *   int firstThreeDigitPrime = seq(100) | filter(isPrime) | first;
1111  */
1112 class First : public Operator<First> {
1113  public:
1114   First() { }
1115
1116   template<class Source,
1117            class Value,
1118            class StorageType = typename std::decay<Value>::type>
1119   StorageType compose(const GenImpl<Value, Source>& source) const {
1120     Optional<StorageType> accum;
1121     source | [&](Value v) -> bool {
1122       accum = std::forward<Value>(v);
1123       return false;
1124     };
1125     if (!accum.hasValue()) {
1126       throw EmptySequence();
1127     }
1128     return std::move(accum.value());
1129   }
1130 };
1131
1132
1133 /**
1134  * Any - For determining whether any values in a sequence satisfy a predicate.
1135  *
1136  * This type is primarily used through the 'any' static value, like:
1137  *
1138  *   bool any20xPrimes = seq(200, 210) | filter(isPrime) | any;
1139  *
1140  * Note that it may also be used like so:
1141  *
1142  *   bool any20xPrimes = seq(200, 210) | any(isPrime);
1143  *
1144  */
1145 class Any : public Operator<Any> {
1146  public:
1147   Any() { }
1148
1149   template<class Source,
1150            class Value>
1151   bool compose(const GenImpl<Value, Source>& source) const {
1152     bool any = false;
1153     source | [&](Value v) -> bool {
1154       any = true;
1155       return false;
1156     };
1157     return any;
1158   }
1159
1160   /**
1161    * Convenience function for use like:
1162    *
1163    *  bool found = gen | any([](int i) { return i * i > 100; });
1164    */
1165   template<class Predicate,
1166            class Filter = Filter<Predicate>,
1167            class Composed = Composed<Filter, Any>>
1168   Composed operator()(Predicate pred) const {
1169     return Composed(Filter(std::move(pred)), Any());
1170   }
1171 };
1172
1173 /**
1174  * All - For determining whether all values in a sequence satisfy a predicate.
1175  *
1176  * This type is primarily used through the 'any' static value, like:
1177  *
1178  *   bool valid = from(input) | all(validate);
1179  *
1180  * Note: Passing an empty sequence through 'all()' will always return true.
1181  */
1182 template<class Predicate>
1183 class All : public Operator<All<Predicate>> {
1184   Predicate pred_;
1185  public:
1186   All() {}
1187   explicit All(Predicate pred)
1188     : pred_(std::move(pred))
1189   { }
1190
1191   template<class Source,
1192            class Value>
1193   bool compose(const GenImpl<Value, Source>& source) const {
1194     static_assert(!Source::infinite, "Cannot call 'all' on infinite source");
1195     bool all = true;
1196     source | [&](Value v) -> bool {
1197       if (!pred_(std::forward<Value>(v))) {
1198         all = false;
1199         return false;
1200       }
1201       return true;
1202     };
1203     return all;
1204   }
1205 };
1206
1207 /**
1208  * Reduce - Functional reduce, for recursively combining values from a source
1209  * using a reducer function until there is only one item left. Useful for
1210  * combining values when an empty sequence doesn't make sense.
1211  *
1212  * This type is primarily used through the 'reduce' helper method, like:
1213  *
1214  *   sring longest = from(names)
1215  *                 | reduce([](string&& best, string& current) {
1216  *                     return best.size() >= current.size() ? best : current;
1217  *                   });
1218  */
1219 template<class Reducer>
1220 class Reduce : public Operator<Reduce<Reducer>> {
1221   Reducer reducer_;
1222  public:
1223   Reduce() {}
1224   explicit Reduce(Reducer reducer)
1225     : reducer_(std::move(reducer))
1226   {}
1227
1228   template<class Source,
1229            class Value,
1230            class StorageType = typename std::decay<Value>::type>
1231   StorageType compose(const GenImpl<Value, Source>& source) const {
1232     Optional<StorageType> accum;
1233     source | [&](Value v) {
1234       if (accum.hasValue()) {
1235         accum = reducer_(std::move(accum.value()), std::forward<Value>(v));
1236       } else {
1237         accum = std::forward<Value>(v);
1238       }
1239     };
1240     if (!accum.hasValue()) {
1241       throw EmptySequence();
1242     }
1243     return accum.value();
1244   }
1245 };
1246
1247 /**
1248  * Count - for simply counting the items in a collection.
1249  *
1250  * This type is usually used through its singleton, 'count':
1251  *
1252  *   auto shortPrimes = seq(1, 100) | filter(isPrime) | count;
1253  */
1254 class Count : public Operator<Count> {
1255  public:
1256   Count() { }
1257
1258   template<class Source,
1259            class Value>
1260   size_t compose(const GenImpl<Value, Source>& source) const {
1261     static_assert(!Source::infinite, "Cannot count infinite source");
1262     return foldl(size_t(0),
1263                  [](size_t accum, Value v) {
1264                    return accum + 1;
1265                  }).compose(source);
1266   }
1267 };
1268
1269 /**
1270  * Sum - For simply summing up all the values from a source.
1271  *
1272  * This type is usually used through its singleton, 'sum':
1273  *
1274  *   auto gaussSum = seq(1, 100) | sum;
1275  */
1276 class Sum : public Operator<Sum> {
1277  public:
1278   Sum() : Operator<Sum>() {}
1279
1280   template<class Source,
1281            class Value,
1282            class StorageType = typename std::decay<Value>::type>
1283   StorageType compose(const GenImpl<Value, Source>& source) const {
1284     static_assert(!Source::infinite, "Cannot sum infinite source");
1285     return foldl(StorageType(0),
1286                  [](StorageType&& accum, Value v) {
1287                    return std::move(accum) + std::forward<Value>(v);
1288                  }).compose(source);
1289   }
1290 };
1291
1292 /**
1293  * Contains - For testing whether a value matching the given value is contained
1294  * in a sequence.
1295  *
1296  * This type should be used through the 'contains' helper method, like:
1297  *
1298  *   bool contained = seq(1, 10) | map(square) | contains(49);
1299  */
1300 template<class Needle>
1301 class Contains : public Operator<Contains<Needle>> {
1302   Needle needle_;
1303  public:
1304   explicit Contains(Needle needle)
1305     : needle_(std::move(needle))
1306   {}
1307
1308   template<class Source,
1309            class Value,
1310            class StorageType = typename std::decay<Value>::type>
1311   bool compose(const GenImpl<Value, Source>& source) const {
1312     static_assert(!Source::infinite,
1313                   "Calling contains on an infinite source might cause "
1314                   "an infinite loop.");
1315     return !(source | [this](Value value) {
1316         return !(needle_ == std::forward<Value>(value));
1317       });
1318   }
1319 };
1320
1321 /**
1322  * Min - For a value which minimizes a key, where the key is determined by a
1323  * given selector, and compared by given comparer.
1324  *
1325  * This type is usually used through the singletone 'min' or through the helper
1326  * functions 'minBy' and 'maxBy'.
1327  *
1328  *   auto oldest = from(people)
1329  *               | minBy([](Person& p) {
1330  *                   return p.dateOfBirth;
1331  *                 });
1332  */
1333 template<class Selector,
1334          class Comparer>
1335 class Min : public Operator<Min<Selector, Comparer>> {
1336   Selector selector_;
1337   Comparer comparer_;
1338  public:
1339   Min() {}
1340
1341   explicit Min(Selector selector)
1342     : selector_(std::move(selector))
1343   {}
1344
1345   Min(Selector selector,
1346         Comparer comparer)
1347     : selector_(std::move(selector))
1348     , comparer_(std::move(comparer))
1349   {}
1350
1351   template<class Value,
1352            class Source,
1353            class StorageType = typename std::decay<Value>::type,
1354            class Key = typename std::decay<
1355                typename std::result_of<Selector(Value)>::type
1356              >::type>
1357   StorageType compose(const GenImpl<Value, Source>& source) const {
1358     Optional<StorageType> min;
1359     Optional<Key> minKey;
1360     source | [&](Value v) {
1361       Key key = selector_(std::forward<Value>(v));
1362       if (!minKey.hasValue() || comparer_(key, minKey.value())) {
1363         minKey = key;
1364         min = std::forward<Value>(v);
1365       }
1366     };
1367     if (!min.hasValue()) {
1368       throw EmptySequence();
1369     }
1370     return min.value();
1371   }
1372 };
1373
1374 /**
1375  * Append - For collecting values from a source into a given output container
1376  * by appending.
1377  *
1378  * This type is usually used through the helper function 'appendTo', like:
1379  *
1380  *   vector<int64_t> ids;
1381  *   from(results) | map([](Person& p) { return p.id })
1382  *                 | appendTo(ids);
1383  */
1384 template<class Collection>
1385 class Append : public Operator<Append<Collection>> {
1386   Collection* collection_;
1387  public:
1388   explicit Append(Collection* collection)
1389     : collection_(collection)
1390   {}
1391
1392   template<class Value,
1393            class Source>
1394   Collection& compose(const GenImpl<Value, Source>& source) const {
1395     source | [&](Value v) {
1396       collection_->insert(collection_->end(), std::forward<Value>(v));
1397     };
1398     return *collection_;
1399   }
1400 };
1401
1402 /**
1403  * Collect - For collecting values from a source in a collection of the desired
1404  * type.
1405  *
1406  * This type is usually used through the helper function 'as', like:
1407  *
1408  *   std::string upper = from(stringPiece)
1409  *                     | map(&toupper)
1410  *                     | as<std::string>();
1411  */
1412 template<class Collection>
1413 class Collect : public Operator<Collect<Collection>> {
1414  public:
1415   Collect() { }
1416
1417   template<class Value,
1418            class Source,
1419            class StorageType = typename std::decay<Value>::type>
1420   Collection compose(const GenImpl<Value, Source>& source) const {
1421     Collection collection;
1422     source | [&](Value v) {
1423       collection.insert(collection.end(), std::forward<Value>(v));
1424     };
1425     return collection;
1426   }
1427 };
1428
1429
1430 /**
1431  * CollectTemplate - For collecting values from a source in a collection
1432  * constructed using the specified template type. Given the type of values
1433  * produced by the given generator, the collection type will be:
1434  *   Container<Value, Allocator<Value>>
1435  *
1436  * The allocator defaults to std::allocator, so this may be used for the STL
1437  * containers by simply using operators like 'as<set>', 'as<deque>',
1438  * 'as<vector>'. 'as', here is the helper method which is the usual means of
1439  * consturcting this operator.
1440  *
1441  * Example:
1442  *
1443  *   set<string> uniqueNames = from(names) | as<set>();
1444  */
1445 template<template<class, class> class Container,
1446          template<class> class Allocator>
1447 class CollectTemplate : public Operator<CollectTemplate<Container, Allocator>> {
1448  public:
1449   CollectTemplate() { }
1450
1451   template<class Value,
1452            class Source,
1453            class StorageType = typename std::decay<Value>::type,
1454            class Collection = Container<StorageType, Allocator<StorageType>>>
1455   Collection compose(const GenImpl<Value, Source>& source) const {
1456     Collection collection;
1457     source | [&](Value v) {
1458       collection.insert(collection.end(), std::forward<Value>(v));
1459     };
1460     return collection;
1461   }
1462 };
1463
1464 /**
1465  * Concat - For flattening generators of generators.
1466  *
1467  * This type is usually used through the 'concat' static value, like:
1468  *
1469  *   auto edges =
1470  *       from(nodes)
1471  *     | map([](Node& x) {
1472  *           return from(x.neighbors)
1473  *                | map([&](Node& y) {
1474  *                    return Edge(x, y);
1475  *                  });
1476  *         })
1477  *     | concat
1478  *     | as<std::set>();
1479  */
1480 class Concat : public Operator<Concat> {
1481  public:
1482   Concat() { }
1483
1484   template<class Inner,
1485            class Source,
1486            class InnerValue = typename std::decay<Inner>::type::ValueType>
1487   class Generator :
1488       public GenImpl<InnerValue, Generator<Inner, Source, InnerValue>> {
1489     Source source_;
1490    public:
1491     explicit Generator(Source source)
1492       : source_(std::move(source)) {}
1493
1494     template<class Handler>
1495     bool apply(Handler&& handler) const {
1496       return source_.apply([&](Inner inner) -> bool {
1497           return inner.apply(std::forward<Handler>(handler));
1498         });
1499     }
1500
1501     template<class Body>
1502     void foreach(Body&& body) const {
1503       source_.foreach([&](Inner inner) {
1504           inner.foreach(std::forward<Body>(body));
1505         });
1506     }
1507
1508     static constexpr bool infinite = Source::infinite;
1509   };
1510
1511   template<class Value,
1512            class Source,
1513            class Gen = Generator<Value, Source>>
1514   Gen compose(GenImpl<Value, Source>&& source) const {
1515     return Gen(std::move(source.self()));
1516   }
1517
1518   template<class Value,
1519            class Source,
1520            class Gen = Generator<Value, Source>>
1521   Gen compose(const GenImpl<Value, Source>& source) const {
1522     return Gen(source.self());
1523   }
1524 };
1525
1526 /**
1527  * RangeConcat - For flattening generators of iterables.
1528  *
1529  * This type is usually used through the 'rconcat' static value, like:
1530  *
1531  *   map<int, vector<int>> adjacency;
1532  *   auto sinks =
1533  *       from(adjacency)
1534  *     | get<1>()
1535  *     | rconcat()
1536  *     | as<std::set>();
1537  */
1538 class RangeConcat : public Operator<RangeConcat> {
1539  public:
1540   RangeConcat() { }
1541
1542   template<class Range,
1543            class Source,
1544            class InnerValue = typename ValueTypeOfRange<Range>::RefType>
1545   class Generator
1546     : public GenImpl<InnerValue, Generator<Range, Source, InnerValue>> {
1547     Source source_;
1548    public:
1549     explicit Generator(Source source)
1550       : source_(std::move(source)) {}
1551
1552     template<class Body>
1553     void foreach(Body&& body) const {
1554       source_.foreach([&](Range range) {
1555           for (auto& value : range) {
1556             body(value);
1557           }
1558         });
1559     }
1560
1561     template<class Handler>
1562     bool apply(Handler&& handler) const {
1563       return source_.apply([&](Range range) -> bool {
1564           for (auto& value : range) {
1565             if (!handler(value)) {
1566               return false;
1567             }
1568           }
1569           return true;
1570         });
1571     }
1572   };
1573
1574   template<class Value,
1575            class Source,
1576            class Gen = Generator<Value, Source>>
1577   Gen compose(GenImpl<Value, Source>&& source) const {
1578     return Gen(std::move(source.self()));
1579   }
1580
1581   template<class Value,
1582            class Source,
1583            class Gen = Generator<Value, Source>>
1584   Gen compose(const GenImpl<Value, Source>& source) const {
1585     return Gen(source.self());
1586   }
1587 };
1588
1589
1590 /**
1591  * GuardImpl - For handling exceptions from downstream computation. Requires the
1592  * type of exception to catch, and handler function to invoke in the event of
1593  * the exception. Note that the handler may:
1594  *   1) return true to continue processing the sequence
1595  *   2) return false to end the sequence immediately
1596  *   3) throw, to pass the exception to the next catch
1597  * The handler must match the signature 'bool(Exception&, Value)'.
1598  *
1599  * This type is used through the `guard` helper, like so:
1600  *
1601  *  auto indexes
1602  *    = byLine(STDIN_FILENO)
1603  *    | guard<std::runtime_error>([](std::runtime_error& e,
1604  *                                   StringPiece sp) {
1605  *        LOG(ERROR) << sp << ": " << e.str();
1606  *        return true; // continue processing subsequent lines
1607  *      })
1608  *    | eachTo<int>()
1609  *    | as<vector>();
1610  *
1611  *  TODO(tjackson): Rename this back to Guard.
1612  **/
1613 template<class Exception,
1614          class ErrorHandler>
1615 class GuardImpl : public Operator<GuardImpl<Exception, ErrorHandler>> {
1616   ErrorHandler handler_;
1617  public:
1618   GuardImpl(ErrorHandler handler)
1619     : handler_(std::move(handler)) {}
1620
1621   template<class Value,
1622            class Source>
1623   class Generator : public GenImpl<Value, Generator<Value, Source>> {
1624     Source source_;
1625     ErrorHandler handler_;
1626   public:
1627     explicit Generator(Source source,
1628                        ErrorHandler handler)
1629       : source_(std::move(source)),
1630         handler_(std::move(handler)) {}
1631
1632     template<class Handler>
1633     bool apply(Handler&& handler) const {
1634       return source_.apply([&](Value value) -> bool {
1635         try {
1636           handler(std::forward<Value>(value));
1637           return true;
1638         } catch (Exception& e) {
1639           return handler_(e, std::forward<Value>(value));
1640         }
1641       });
1642     }
1643
1644     static constexpr bool infinite = Source::infinite;
1645   };
1646
1647   template<class Value,
1648            class Source,
1649            class Gen = Generator<Value, Source>>
1650   Gen compose(GenImpl<Value, Source>&& source) const {
1651     return Gen(std::move(source.self()), handler_);
1652   }
1653
1654   template<class Value,
1655            class Source,
1656            class Gen = Generator<Value, Source>>
1657   Gen compose(const GenImpl<Value, Source>& source) const {
1658     return Gen(source.self(), handler_);
1659   }
1660 };
1661
1662 /**
1663  * Cycle - For repeating a sequence forever.
1664  *
1665  * This type is usually used through the 'cycle' static value, like:
1666  *
1667  *   auto tests
1668  *     = from(samples)
1669  *     | cycle
1670  *     | take(100);
1671  */
1672 class Cycle : public Operator<Cycle> {
1673   off_t limit_; // -1 for infinite
1674  public:
1675   Cycle()
1676     : limit_(-1) { }
1677
1678   explicit Cycle(off_t limit)
1679     : limit_(limit) { }
1680
1681   template<class Value,
1682            class Source>
1683   class Generator : public GenImpl<Value, Generator<Value, Source>> {
1684     Source source_;
1685     off_t limit_; // -1 for infinite
1686   public:
1687     explicit Generator(Source source, off_t limit)
1688       : source_(std::move(source))
1689       , limit_(limit) {}
1690
1691     template<class Handler>
1692     bool apply(Handler&& handler) const {
1693       bool cont;
1694       auto handler2 = [&](Value value) {
1695         cont = handler(std::forward<Value>(value));
1696         return cont;
1697       };
1698       for (off_t count = 0; count != limit_; ++count) {
1699         cont = false;
1700         source_.apply(handler2);
1701         if (!cont) {
1702           return false;
1703         }
1704       }
1705       return true;
1706     }
1707
1708     // not actually infinite, since an empty generator will end the cycles.
1709     static constexpr bool infinite = Source::infinite;
1710   };
1711
1712   template<class Source,
1713            class Value,
1714            class Gen = Generator<Value, Source>>
1715   Gen compose(GenImpl<Value, Source>&& source) const {
1716     return Gen(std::move(source.self()), limit_);
1717   }
1718
1719   template<class Source,
1720            class Value,
1721            class Gen = Generator<Value, Source>>
1722   Gen compose(const GenImpl<Value, Source>& source) const {
1723     return Gen(source.self(), limit_);
1724   }
1725
1726   /**
1727    * Convenience function for use like:
1728    *
1729    *  auto tripled = gen | cycle(3);
1730    */
1731   Cycle operator()(off_t limit) const {
1732     return Cycle(limit);
1733   }
1734 };
1735
1736 /**
1737  * Dereference - For dereferencing a sequence of pointers while filtering out
1738  * null pointers.
1739  *
1740  * This type is usually used through the 'dereference' static value, like:
1741  *
1742  *   auto refs = from(ptrs) | dereference;
1743  */
1744 class Dereference : public Operator<Dereference> {
1745  public:
1746   Dereference() {}
1747
1748   template<class Value,
1749            class Source,
1750            class Result = decltype(*std::declval<Value>())>
1751   class Generator : public GenImpl<Result, Generator<Value, Source, Result>> {
1752     Source source_;
1753   public:
1754     explicit Generator(Source source)
1755       : source_(std::move(source)) {}
1756
1757     template<class Body>
1758     void foreach(Body&& body) const {
1759       source_.foreach([&](Value value) {
1760         if (value) {
1761           return body(*value);
1762         }
1763       });
1764     }
1765
1766     template<class Handler>
1767     bool apply(Handler&& handler) const {
1768       return source_.apply([&](Value value) -> bool {
1769         if (value) {
1770           return handler(*value);
1771         }
1772         return true;
1773       });
1774     }
1775
1776     // not actually infinite, since an empty generator will end the cycles.
1777     static constexpr bool infinite = Source::infinite;
1778   };
1779
1780   template<class Source,
1781            class Value,
1782            class Gen = Generator<Value, Source>>
1783   Gen compose(GenImpl<Value, Source>&& source) const {
1784     return Gen(std::move(source.self()));
1785   }
1786
1787   template<class Source,
1788            class Value,
1789            class Gen = Generator<Value, Source>>
1790   Gen compose(const GenImpl<Value, Source>& source) const {
1791     return Gen(source.self());
1792   }
1793 };
1794
1795 } //::detail
1796
1797 /**
1798  * VirtualGen<T> - For wrapping template types in simple polymorphic wrapper.
1799  **/
1800 template<class Value>
1801 class VirtualGen : public GenImpl<Value, VirtualGen<Value>> {
1802   class WrapperBase {
1803    public:
1804     virtual ~WrapperBase() {}
1805     virtual bool apply(const std::function<bool(Value)>& handler) const = 0;
1806     virtual void foreach(const std::function<void(Value)>& body) const = 0;
1807     virtual std::unique_ptr<const WrapperBase> clone() const = 0;
1808   };
1809
1810   template<class Wrapped>
1811   class WrapperImpl : public WrapperBase {
1812     Wrapped wrapped_;
1813    public:
1814     explicit WrapperImpl(Wrapped wrapped)
1815      : wrapped_(std::move(wrapped)) {
1816     }
1817
1818     virtual bool apply(const std::function<bool(Value)>& handler) const {
1819       return wrapped_.apply(handler);
1820     }
1821
1822     virtual void foreach(const std::function<void(Value)>& body) const {
1823       wrapped_.foreach(body);
1824     }
1825
1826     virtual std::unique_ptr<const WrapperBase> clone() const {
1827       return std::unique_ptr<const WrapperBase>(new WrapperImpl(wrapped_));
1828     }
1829   };
1830
1831   std::unique_ptr<const WrapperBase> wrapper_;
1832
1833  public:
1834   template<class Self>
1835   /* implicit */ VirtualGen(Self source)
1836    : wrapper_(new WrapperImpl<Self>(std::move(source)))
1837   { }
1838
1839   VirtualGen(VirtualGen&& source)
1840    : wrapper_(std::move(source.wrapper_))
1841   { }
1842
1843   VirtualGen(const VirtualGen& source)
1844    : wrapper_(source.wrapper_->clone())
1845   { }
1846
1847   VirtualGen& operator=(const VirtualGen& source) {
1848     wrapper_.reset(source.wrapper_->clone());
1849     return *this;
1850   }
1851
1852   VirtualGen& operator=(VirtualGen&& source) {
1853     wrapper_= std::move(source.wrapper_);
1854     return *this;
1855   }
1856
1857   bool apply(const std::function<bool(Value)>& handler) const {
1858     return wrapper_->apply(handler);
1859   }
1860
1861   void foreach(const std::function<void(Value)>& body) const {
1862     wrapper_->foreach(body);
1863   }
1864 };
1865
1866 /**
1867  * non-template operators, statically defined to avoid the need for anything but
1868  * the header.
1869  */
1870 static const detail::Sum sum;
1871
1872 static const detail::Count count;
1873
1874 static const detail::First first;
1875
1876 /**
1877  * Use directly for detecting any values, or as a function to detect values
1878  * which pass a predicate:
1879  *
1880  *  auto nonempty = g | any;
1881  *  auto evens = g | any(even);
1882  */
1883 static const detail::Any any;
1884
1885 static const detail::Min<Identity, Less> min;
1886
1887 static const detail::Min<Identity, Greater> max;
1888
1889 static const detail::Order<Identity> order;
1890
1891 static const detail::Distinct<Identity> distinct;
1892
1893 static const detail::Map<Move> move;
1894
1895 static const detail::Concat concat;
1896
1897 static const detail::RangeConcat rconcat;
1898
1899 /**
1900  * Use directly for infinite sequences, or as a function to limit cycle count.
1901  *
1902  *  auto forever = g | cycle;
1903  *  auto thrice = g | cycle(3);
1904  */
1905 static const detail::Cycle cycle;
1906
1907 static const detail::Dereference dereference;
1908
1909 inline detail::Take take(size_t count) {
1910   return detail::Take(count);
1911 }
1912
1913 template<class Random = std::default_random_engine>
1914 inline detail::Sample<Random> sample(size_t count, Random rng = Random()) {
1915   return detail::Sample<Random>(count, std::move(rng));
1916 }
1917
1918 inline detail::Skip skip(size_t count) {
1919   return detail::Skip(count);
1920 }
1921
1922 inline detail::Batch batch(size_t batchSize) {
1923   return detail::Batch(batchSize);
1924 }
1925
1926 }} //folly::gen
1927
1928 #pragma GCC diagnostic pop