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