folly/experimental/Gen-inl.h

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