folly/experimental/Gen-inl.h

   1 /*
   2  * Copyright 2012 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 it returns false. Returns true if the false iff the handler
 160    * returned false.
 161    */
 162   template<class Handler>
 163   bool apply(Handler&& handler) const;
 164
 165   /**
 166    * foreach() - Send all values produced by this generator to given lambda.
 167    */
 168   template<class Body>
 169   void foreach(Body&& body) const {
 170     this->self().apply([&](Value value) {
 171         body(std::forward<Value>(value));
 172         return true;
 173       });
 174   }
 175 };
 176
 177 template<class LeftValue,
 178          class Left,
 179          class RightValue,
 180          class Right,
 181          class Chain = detail::Chain<LeftValue, Left, Right>>
 182 Chain operator+(const GenImpl<LeftValue, Left>& left,
 183                 const GenImpl<RightValue, Right>& right) {
 184   static_assert(
 185     std::is_same<LeftValue, RightValue>::value,
 186     "Generators may ony be combined if Values are the exact same type.");
 187   return Chain(left.self(), right.self());
 188 }
 189
 190 template<class LeftValue,
 191          class Left,
 192          class RightValue,
 193          class Right,
 194          class Chain = detail::Chain<LeftValue, Left, Right>>
 195 Chain operator+(const GenImpl<LeftValue, Left>& left,
 196                 GenImpl<RightValue, Right>&& right) {
 197   static_assert(
 198     std::is_same<LeftValue, RightValue>::value,
 199     "Generators may ony be combined if Values are the exact same type.");
 200   return Chain(left.self(), std::move(right.self()));
 201 }
 202
 203 template<class LeftValue,
 204          class Left,
 205          class RightValue,
 206          class Right,
 207          class Chain = detail::Chain<LeftValue, Left, Right>>
 208 Chain operator+(GenImpl<LeftValue, Left>&& left,
 209                 const GenImpl<RightValue, Right>& right) {
 210   static_assert(
 211     std::is_same<LeftValue, RightValue>::value,
 212     "Generators may ony be combined if Values are the exact same type.");
 213   return Chain(std::move(left.self()), right.self());
 214 }
 215
 216 template<class LeftValue,
 217          class Left,
 218          class RightValue,
 219          class Right,
 220          class Chain = detail::Chain<LeftValue, Left, Right>>
 221 Chain operator+(GenImpl<LeftValue, Left>&& left,
 222                 GenImpl<RightValue, Right>&& right) {
 223   static_assert(
 224     std::is_same<LeftValue, RightValue>::value,
 225     "Generators may ony be combined if Values are the exact same type.");
 226   return Chain(std::move(left.self()), std::move(right.self()));
 227 }
 228
 229 /**
 230  * operator|() which enables foreach-like usage:
 231  *   gen | [](Value v) -> void {...};
 232  */
 233 template<class Value,
 234          class Gen,
 235          class Handler>
 236 typename std::enable_if<
 237   IsCompatibleSignature<Handler, void(Value)>::value>::type
 238 operator|(const GenImpl<Value, Gen>& gen, Handler&& handler) {
 239   gen.self().foreach(std::forward<Handler>(handler));
 240 }
 241
 242 /**
 243  * operator|() which enables foreach-like usage with 'break' support:
 244  *   gen | [](Value v) -> bool { return shouldContinue(); };
 245  */
 246 template<class Value,
 247          class Gen,
 248          class Handler>
 249 typename std::enable_if<
 250   IsCompatibleSignature<Handler, bool(Value)>::value>::type
 251 operator|(const GenImpl<Value, Gen>& gen, Handler&& handler) {
 252   gen.self().apply(std::forward<Handler>(handler));
 253 }
 254
 255 /**
 256  * operator|() for composing generators with operators, similar to boosts' range
 257  * adaptors:
 258  *   gen | map(square) | sum
 259  */
 260 template<class Value,
 261          class Gen,
 262          class Op>
 263 auto operator|(const GenImpl<Value, Gen>& gen, const Operator<Op>& op) ->
 264 decltype(op.self().compose(gen)) {
 265   return op.self().compose(gen.self());
 266 }
 267
 268 template<class Value,
 269          class Gen,
 270          class Op>
 271 auto operator|(GenImpl<Value, Gen>&& gen, const Operator<Op>& op) ->
 272 decltype(op.self().compose(std::move(gen.self()))) {
 273   return op.self().compose(std::move(gen.self()));
 274 }
 275
 276 namespace detail {
 277
 278 /*
 279  * ReferencedSource - Generate values from an STL-like container using
 280  * iterators from .begin() until .end(). Value type defaults to the type of
 281  * *container->begin(). For std::vector<int>, this would be int&. Note that the
 282  * value here is a reference, so the values in the vector will be passed by
 283  * reference to downstream operators.
 284  *
 285  * This type is primarily used through the 'from' helper method, like:
 286  *
 287  *   string& longestName = from(names)
 288  *                       | maxBy([](string& s) { return s.size() });
 289  */
 290 template<class Container,
 291          class Value>
 292 class ReferencedSource :
 293     public GenImpl<Value, ReferencedSource<Container, Value>> {
 294   Container* const container_;
 295 public:
 296   explicit ReferencedSource(Container* container)
 297     : container_(container) {}
 298
 299   template<class Body>
 300   void foreach(Body&& body) const {
 301     for (auto& value : *container_) {
 302       body(std::forward<Value>(value));
 303     }
 304   }
 305
 306   template<class Handler>
 307   bool apply(Handler&& handler) const {
 308     for (auto& value : *container_) {
 309       if (!handler(std::forward<Value>(value))) {
 310         return false;
 311       }
 312     }
 313     return true;
 314   }
 315 };
 316
 317 /**
 318  * CopiedSource - For producing values from eagerly from a sequence of values
 319  * whose storage is owned by this class. Useful for preparing a generator for
 320  * use after a source collection will no longer be available, or for when the
 321  * values are specified literally with an initializer list.
 322  *
 323  * This type is primarily used through the 'fromCopy' function, like:
 324  *
 325  *   auto sourceCopy = fromCopy(makeAVector());
 326  *   auto sum = sourceCopy | sum;
 327  *   auto max = sourceCopy | max;
 328  *
 329  * Though it is also used for the initializer_list specialization of from().
 330  */
 331 template<class StorageType,
 332          class Container>
 333 class CopiedSource :
 334   public GenImpl<const StorageType&,
 335                  CopiedSource<StorageType, Container>> {
 336   static_assert(
 337     !std::is_reference<StorageType>::value, "StorageType must be decayed");
 338  public:
 339   // Generator objects are often copied during normal construction as they are
 340   // encapsulated by downstream generators. It would be bad if this caused
 341   // a copy of the entire container each time, and since we're only exposing a
 342   // const reference to the value, it's safe to share it between multiple
 343   // generators.
 344   static_assert(
 345     !std::is_reference<Container>::value,
 346     "Can't copy into a reference");
 347   const std::shared_ptr<const Container> copy_;
 348 public:
 349   typedef Container ContainerType;
 350
 351   template<class SourceContainer>
 352   explicit CopiedSource(const SourceContainer& container)
 353     : copy_(new Container(begin(container), end(container))) {}
 354
 355   explicit CopiedSource(Container&& container) :
 356     copy_(new Container(std::move(container))) {}
 357
 358   // To enable re-use of cached results.
 359   CopiedSource(const CopiedSource<StorageType, Container>& source)
 360     : copy_(source.copy_) {}
 361
 362   template<class Body>
 363   void foreach(Body&& body) const {
 364     for (const auto& value : *copy_) {
 365       body(value);
 366     }
 367   }
 368
 369   template<class Handler>
 370   bool apply(Handler&& handler) const {
 371     // The collection may be reused by others, we can't allow it to be changed.
 372     for (const auto& value : *copy_) {
 373       if (!handler(value)) {
 374         return false;
 375       }
 376     }
 377     return true;
 378   }
 379 };
 380
 381 /**
 382  * Sequence - For generating values from beginning value, incremented along the
 383  * way with the ++ and += operators. Iteration may continue indefinitely by
 384  * setting the 'endless' template parameter to true. If set to false, iteration
 385  * will stop when value reaches 'end', either inclusively or exclusively,
 386  * depending on the template parameter 'endInclusive'. Value type specified
 387  * explicitly.
 388  *
 389  * This type is primarily used through the 'seq' and 'range' function, like:
 390  *
 391  *   int total = seq(1, 10) | sum;
 392  *   auto indexes = range(0, 10);
 393  */
 394 template<class Value,
 395          bool endless,
 396          bool endInclusive>
 397 class Sequence : public GenImpl<const Value&,
 398                                 Sequence<Value, endless, endInclusive>> {
 399   static_assert(!std::is_reference<Value>::value &&
 400                 !std::is_const<Value>::value, "Value mustn't be const or ref.");
 401   Value bounds_[endless ? 1 : 2];
 402 public:
 403   explicit Sequence(const Value& begin)
 404       : bounds_{begin} {
 405     static_assert(endless, "Must supply 'end'");
 406   }
 407
 408   explicit Sequence(const Value& begin, const Value& end)
 409     : bounds_{begin, end} {}
 410
 411   template<class Handler>
 412   bool apply(Handler&& handler) const {
 413     Value value = bounds_[0];
 414     for (;endless || value < bounds_[1]; ++value) {
 415       const Value& arg = value;
 416       if (!handler(arg)) {
 417         return false;
 418       }
 419     }
 420     if (endInclusive && value == bounds_[1]) {
 421       const Value& arg = value;
 422       if (!handler(arg)) {
 423         return false;
 424       }
 425     }
 426     return true;
 427   }
 428
 429   template<class Body>
 430   void foreach(Body&& body) const {
 431     Value value = bounds_[0];
 432     for (;endless || value < bounds_[1]; ++value) {
 433       const Value& arg = value;
 434       body(arg);
 435     }
 436     if (endInclusive && value == bounds_[1]) {
 437       const Value& arg = value;
 438       body(arg);
 439     }
 440   }
 441 };
 442
 443 /**
 444  * Chain - For concatenating the values produced by two Generators.
 445  *
 446  * This type is primarily used through using '+' to combine generators, like:
 447  *
 448  *   auto nums = seq(1, 10) + seq(20, 30);
 449  *   int total = nums | sum;
 450  */
 451 template<class Value, class First, class Second>
 452 class Chain : public GenImpl<Value,
 453                              Chain<Value, First, Second>> {
 454   const First first_;
 455   const Second second_;
 456 public:
 457   explicit Chain(First first, Second second)
 458       : first_(std::move(first))
 459       , second_(std::move(second)) {}
 460
 461   template<class Handler>
 462   bool apply(Handler&& handler) const {
 463     return first_.apply(std::forward<Handler>(handler))
 464         && second_.apply(std::forward<Handler>(handler));
 465   }
 466
 467   template<class Body>
 468   void foreach(Body&& body) const {
 469     first_.foreach(std::forward<Body>(body));
 470     second_.foreach(std::forward<Body>(body));
 471   }
 472 };
 473
 474 /**
 475  * Yield - For producing values from a user-defined generator by way of a
 476  * 'yield' function.
 477  **/
 478 template<class Value, class Source>
 479 class Yield : public GenImpl<Value, Yield<Value, Source>> {
 480   const Source source_;
 481  public:
 482   explicit Yield(Source source)
 483     : source_(std::move(source)) {
 484   }
 485
 486   template<class Handler>
 487   bool apply(Handler&& handler) const {
 488     struct Break {};
 489     auto body = [&](Value value) {
 490       if (!handler(std::forward<Value>(value))) {
 491         throw Break();
 492       }
 493     };
 494     try {
 495       source_(body);
 496       return true;
 497     } catch (Break&) {
 498       return false;
 499     }
 500   }
 501
 502   template<class Body>
 503   void foreach(Body&& body) const {
 504     source_(std::forward<Body>(body));
 505   }
 506 };
 507
 508
 509 /*
 510  * Operators
 511  */
 512
 513 /**
 514  * Map - For producing a sequence of values by passing each value from a source
 515  * collection through a predicate.
 516  *
 517  * This type is usually used through the 'map' or 'mapped' helper function:
 518  *
 519  *   auto squares = seq(1, 10) | map(square) | asVector;
 520  */
 521 template<class Predicate>
 522 class Map : public Operator<Map<Predicate>> {
 523   const Predicate predicate_;
 524  public:
 525   explicit Map(const Predicate& predicate = Predicate())
 526     : predicate_(predicate)
 527   { }
 528
 529   template<class Value,
 530            class Source,
 531            class Result = typename ArgumentReference<
 532                             typename std::result_of<Predicate(Value)>::type
 533                           >::type>
 534   class Generator :
 535       public GenImpl<Result, Generator<Value, Source, Result>> {
 536     const Source source_;
 537     const Predicate pred_;
 538   public:
 539     explicit Generator(Source source, const Predicate& pred)
 540       : source_(std::move(source)), pred_(pred) {}
 541
 542     template<class Body>
 543     void foreach(Body&& body) const {
 544       source_.foreach([&](Value value) {
 545         body(pred_(std::forward<Value>(value)));
 546       });
 547     }
 548
 549     template<class Handler>
 550     bool apply(Handler&& handler) const {
 551       return source_.apply([&](Value value) {
 552         return handler(pred_(std::forward<Value>(value)));
 553       });
 554     }
 555   };
 556
 557   template<class Source,
 558            class Value,
 559            class Gen = Generator<Value, Source>>
 560   Gen compose(GenImpl<Value, Source>&& source) const {
 561     return Gen(std::move(source.self()), predicate_);
 562   }
 563
 564   template<class Source,
 565            class Value,
 566            class Gen = Generator<Value, Source>>
 567   Gen compose(const GenImpl<Value, Source>& source) const {
 568     return Gen(source.self(), predicate_);
 569   }
 570 };
 571
 572
 573 /**
 574  * Filter - For filtering values from a source sequence by a predicate.
 575  *
 576  * This type is usually used through the 'filter' helper function, like:
 577  *
 578  *   auto nonEmpty = from(strings)
 579  *                 | filter([](const string& str) -> bool {
 580  *                     return !str.empty();
 581  *                   });
 582  */
 583 template<class Predicate>
 584 class Filter : public Operator<Filter<Predicate>> {
 585   const Predicate predicate_;
 586  public:
 587   explicit Filter(const Predicate& predicate)
 588     : predicate_(predicate)
 589   { }
 590
 591   template<class Value,
 592            class Source>
 593   class Generator : public GenImpl<Value, Generator<Value, Source>> {
 594     const Source source_;
 595     const Predicate pred_;
 596   public:
 597     explicit Generator(Source source, const Predicate& pred)
 598       : source_(std::move(source)), pred_(pred) {}
 599
 600     template<class Body>
 601     void foreach(Body&& body) const {
 602       source_.foreach([&](Value value) {
 603         if (pred_(std::forward<Value>(value))) {
 604           body(std::forward<Value>(value));
 605         }
 606       });
 607     }
 608
 609     template<class Handler>
 610     bool apply(Handler&& handler) const {
 611       return source_.apply([&](Value value) -> bool {
 612         if (pred_(std::forward<Value>(value))) {
 613           return handler(std::forward<Value>(value));
 614         }
 615         return true;
 616       });
 617     }
 618   };
 619
 620   template<class Source,
 621            class Value,
 622            class Gen = Generator<Value, Source>>
 623   Gen compose(GenImpl<Value, Source>&& source) const {
 624     return Gen(std::move(source.self()), predicate_);
 625   }
 626
 627   template<class Source,
 628            class Value,
 629            class Gen = Generator<Value, Source>>
 630   Gen compose(const GenImpl<Value, Source>& source) const {
 631     return Gen(source.self(), predicate_);
 632   }
 633 };
 634
 635 /**
 636  * Until - For producing values from a source until a predicate is satisfied.
 637  *
 638  * This type is usually used through the 'until' helper function, like:
 639  *
 640  *   auto best = from(sortedItems)
 641  *             | until([](Item& item) { return item.score > 100; })
 642  *             | asVector;
 643  */
 644 template<class Predicate>
 645 class Until : public Operator<Until<Predicate>> {
 646   const Predicate predicate_;
 647  public:
 648   explicit Until(const Predicate& predicate)
 649     : predicate_(predicate)
 650   { }
 651
 652   template<class Value,
 653            class Source,
 654            class Result = typename std::result_of<Predicate(Value)>::type>
 655   class Generator :
 656       public GenImpl<Result, Generator<Value, Source, Result>> {
 657     const Source source_;
 658     const Predicate pred_;
 659   public:
 660     explicit Generator(Source source, const Predicate& pred)
 661       : source_(std::move(source)), pred_(pred) {}
 662
 663     template<class Handler>
 664     bool apply(Handler&& handler) const {
 665       return source_.apply([&](Value value) -> bool {
 666         return !pred_(std::forward<Value>(value))
 667             && handler(std::forward<Value>(value));
 668       });
 669     }
 670   };
 671
 672   template<class Source,
 673            class Value,
 674            class Gen = Generator<Value, Source>>
 675   Gen compose(GenImpl<Value, Source>&& source) const {
 676     return Gen(std::move(source.self()), predicate_);
 677   }
 678
 679   template<class Source,
 680            class Value,
 681            class Gen = Generator<Value, Source>>
 682   Gen compose(const GenImpl<Value, Source>& source) const {
 683     return Gen(source.self(), predicate_);
 684   }
 685 };
 686
 687 /**
 688  * Take - For producing up to N values from a source.
 689  *
 690  * This type is usually used through the 'take' helper function, like:
 691  *
 692  *   auto best = from(docs)
 693  *             | orderByDescending(scoreDoc)
 694  *             | take(10);
 695  */
 696 class Take : public Operator<Take> {
 697   const size_t count_;
 698 public:
 699   explicit Take(size_t count)
 700     : count_(count) {}
 701
 702   template<class Value,
 703            class Source>
 704   class Generator :
 705       public GenImpl<Value, Generator<Value, Source>> {
 706     const Source source_;
 707     const size_t count_;
 708   public:
 709     explicit Generator(Source source, size_t count)
 710       : source_(std::move(source)) , count_(count) {}
 711
 712     template<class Handler>
 713     bool apply(Handler&& handler) const {
 714       if (count_ == 0) { return false; }
 715       size_t n = count_;
 716       return source_.apply([&](Value value) -> bool {
 717           if (!handler(std::forward<Value>(value))) {
 718             return false;
 719           }
 720           return --n;
 721         });
 722     }
 723   };
 724
 725   template<class Source,
 726            class Value,
 727            class Gen = Generator<Value, Source>>
 728   Gen compose(GenImpl<Value, Source>&& source) const {
 729     return Gen(std::move(source.self()), count_);
 730   }
 731
 732   template<class Source,
 733            class Value,
 734            class Gen = Generator<Value, Source>>
 735   Gen compose(const GenImpl<Value, Source>& source) const {
 736     return Gen(source.self(), count_);
 737   }
 738 };
 739
 740 /**
 741  * Skip - For skipping N items from the beginning of a source generator.
 742  *
 743  * This type is usually used through the 'skip' helper function, like:
 744  *
 745  *   auto page = from(results)
 746  *             | skip(pageSize * startPage)
 747  *             | take(10);
 748  */
 749 class Skip : public Operator<Skip> {
 750   const size_t count_;
 751 public:
 752   explicit Skip(size_t count)
 753     : count_(count) {}
 754
 755   template<class Value,
 756            class Source>
 757   class Generator :
 758       public GenImpl<Value, Generator<Value, Source>> {
 759     const Source source_;
 760     const size_t count_;
 761   public:
 762     explicit Generator(Source source, size_t count)
 763       : source_(std::move(source)) , count_(count) {}
 764
 765     template<class Body>
 766     void foreach(Body&& body) const {
 767       if (count_ == 0) {
 768         source_.foreach(body);
 769         return;
 770       }
 771       size_t n = 0;
 772       source_.foreach([&](Value value) {
 773           if (n < count_) {
 774             ++n;
 775           } else {
 776             body(std::forward<Value>(value));
 777           }
 778         });
 779     }
 780
 781     template<class Handler>
 782     bool apply(Handler&& handler) const {
 783       if (count_ == 0) {
 784         return source_.apply(handler);
 785       }
 786       size_t n = 0;
 787       return source_.apply([&](Value value) -> bool {
 788           if (n < count_) {
 789             ++n;
 790             return true;
 791           }
 792           return handler(std::forward<Value>(value));
 793         });
 794     }
 795   };
 796
 797   template<class Source,
 798            class Value,
 799            class Gen = Generator<Value, Source>>
 800   Gen compose(GenImpl<Value, Source>&& source) const {
 801     return Gen(std::move(source.self()), count_);
 802   }
 803
 804   template<class Source,
 805            class Value,
 806            class Gen = Generator<Value, Source>>
 807   Gen compose(const GenImpl<Value, Source>& source) const {
 808     return Gen(source.self(), count_);
 809   }
 810 };
 811
 812 /**
 813  * Order - For ordering a sequence of values from a source by key.
 814  * The key is extracted by the given selector functor, and this key is then
 815  * compared using the specified comparator.
 816  *
 817  * This type is usually used through the 'order' helper function, like:
 818  *
 819  *   auto closest = from(places)
 820  *                | orderBy([](Place& p) {
 821  *                    return -distance(p.location, here);
 822  *                  })
 823  *                | take(10);
 824  */
 825 template<class Selector, class Comparer>
 826 class Order : public Operator<Order<Selector, Comparer>> {
 827   const Selector selector_;
 828   const Comparer comparer_;
 829  public:
 830   Order(const Selector& selector = Selector(),
 831         const Comparer& comparer = Comparer())
 832     : selector_(selector) , comparer_(comparer) {}
 833
 834   template<class Value,
 835            class Source,
 836            class StorageType = typename std::decay<Value>::type,
 837            class Result = typename std::result_of<Selector(Value)>::type>
 838   class Generator :
 839     public GenImpl<StorageType&&,
 840                    Generator<Value, Source, StorageType, Result>> {
 841     const Source source_;
 842     const Selector selector_;
 843     const Comparer comparer_;
 844
 845     typedef std::vector<StorageType> VectorType;
 846
 847     VectorType asVector() const {
 848       auto comparer = [&](const StorageType& a, const StorageType& b) {
 849         return comparer_(selector_(a), selector_(b));
 850       };
 851       auto vals = source_ | as<VectorType>();
 852       std::sort(vals.begin(), vals.end(), comparer);
 853       return std::move(vals);
 854     }
 855    public:
 856     Generator(Source source,
 857               const Selector& selector,
 858               const Comparer& comparer)
 859       : source_(std::move(source)),
 860         selector_(selector),
 861         comparer_(comparer) {}
 862
 863     VectorType operator|(const Collect<VectorType>&) const {
 864       return asVector();
 865     }
 866
 867     VectorType operator|(const CollectTemplate<std::vector>&) const {
 868       return asVector();
 869     }
 870
 871     template<class Body>
 872     void foreach(Body&& body) const {
 873       for (auto& value : asVector()) {
 874         body(std::move(value));
 875       }
 876     }
 877
 878     template<class Handler>
 879     bool apply(Handler&& handler) const {
 880       auto comparer = [&](const StorageType& a, const StorageType& b) {
 881         // swapped for minHeap
 882         return comparer_(selector_(b), selector_(a));
 883       };
 884       auto heap = source_ | as<VectorType>();
 885       std::make_heap(heap.begin(), heap.end(), comparer);
 886       while (!heap.empty()) {
 887         std::pop_heap(heap.begin(), heap.end(), comparer);
 888         if (!handler(std::move(heap.back()))) {
 889           return false;
 890         }
 891         heap.pop_back();
 892       }
 893       return true;
 894     }
 895   };
 896
 897   template<class Source,
 898            class Value,
 899            class Gen = Generator<Value, Source>>
 900   Gen compose(GenImpl<Value, Source>&& source) const {
 901     return Gen(std::move(source.self()), selector_, comparer_);
 902   }
 903
 904   template<class Source,
 905            class Value,
 906            class Gen = Generator<Value, Source>>
 907   Gen compose(const GenImpl<Value, Source>& source) const {
 908     return Gen(source.self(), selector_, comparer_);
 909   }
 910 };
 911
 912 /**
 913  * Composed - For building up a pipeline of operations to perform, absent any
 914  * particular source generator. Useful for building up custom pipelines.
 915  *
 916  * This type is usually used by just piping two operators together:
 917  *
 918  * auto valuesOf = filter([](Optional<int>& o) { return o.hasValue(); })
 919  *               | map([](Optional<int>& o) -> int& { return o.value(); });
 920  *
 921  *  auto valuesIncluded = from(optionals) | valuesOf | as<vector>();
 922  */
 923 template<class First,
 924          class Second>
 925 class Composed : public Operator<Composed<First, Second>> {
 926   const First first_;
 927   const Second second_;
 928   public:
 929     Composed() {}
 930     Composed(First first, Second second)
 931       : first_(std::move(first))
 932       , second_(std::move(second)) {}
 933
 934   template<class Source,
 935            class Value,
 936            class FirstRet = decltype(std::declval<First>()
 937                                      .compose(std::declval<Source>())),
 938            class SecondRet = decltype(std::declval<Second>()
 939                                       .compose(std::declval<FirstRet>()))>
 940   SecondRet compose(const GenImpl<Value, Source>& source) const {
 941     return second_.compose(first_.compose(source.self()));
 942   }
 943
 944   template<class Source,
 945            class Value,
 946            class FirstRet = decltype(std::declval<First>()
 947                                      .compose(std::declval<Source>())),
 948            class SecondRet = decltype(std::declval<Second>()
 949                                       .compose(std::declval<FirstRet>()))>
 950   SecondRet compose(GenImpl<Value, Source>&& source) const {
 951     return second_.compose(first_.compose(std::move(source.self())));
 952   }
 953 };
 954
 955 /*
 956  * Sinks
 957  */
 958
 959 /**
 960  * FoldLeft - Left-associative functional fold. For producing an aggregate value
 961  * from a seed and a folder function. Useful for custom aggregators on a
 962  * sequence.
 963  *
 964  * This type is primarily used through the 'foldl' helper method, like:
 965  *
 966  *   double movingAverage = from(values)
 967  *                        | foldl(0.0, [](double avg, double sample) {
 968  *                            return sample * 0.1 + avg * 0.9;
 969  *                          });
 970  */
 971 template<class Seed,
 972          class Fold>
 973 class FoldLeft : public Operator<FoldLeft<Seed, Fold>> {
 974   const Seed seed_;
 975   const Fold fold_;
 976  public:
 977   FoldLeft(const Seed& seed, const Fold& fold)
 978     : seed_(seed)
 979     , fold_(fold)
 980   {}
 981
 982   template<class Source,
 983            class Value>
 984   Seed compose(const GenImpl<Value, Source>& source) const {
 985     Seed accum = seed_;
 986     source | [&](Value v) {
 987       accum = fold_(std::move(accum), std::forward<Value>(v));
 988     };
 989     return accum;
 990   }
 991 };
 992
 993 /**
 994  * First - For finding the first value in a sequence.
 995  *
 996  * This type is primarily used through the 'first' static value, like:
 997  *
 998  *   int firstThreeDigitPrime = seq(100) | filter(isPrime) | first;
 999  */
1000 class First : public Operator<First> {
1001  public:
1002   template<class Source,
1003            class Value,
1004            class StorageType = typename std::decay<Value>::type>
1005   StorageType compose(const GenImpl<Value, Source>& source) const {
1006     static_assert(std::is_same<StorageType, int>::value, "wtf");
1007     Optional<StorageType> accum;
1008     source | [&](Value v) -> bool {
1009       accum = std::forward<Value>(v);
1010       return false;
1011     };
1012     if (!accum.hasValue()) {
1013       throw EmptySequence();
1014     }
1015     return std::move(accum.value());
1016   }
1017 };
1018
1019
1020 /**
1021  * Any - For determining whether any values are contained in a sequence.
1022  *
1023  * This type is primarily used through the 'any' static value, like:
1024  *
1025  *   bool any20xPrimes = seq(200, 210) | filter(isPrime) | any;
1026  */
1027 class Any : public Operator<Any> {
1028  public:
1029   template<class Source,
1030            class Value>
1031   bool compose(const GenImpl<Value, Source>& source) const {
1032     bool any = false;
1033     source | [&](Value v) -> bool {
1034       any = true;
1035       return false;
1036     };
1037     return any;
1038   }
1039 };
1040
1041 /**
1042  * Reduce - Functional reduce, for recursively combining values from a source
1043  * using a reducer function until there is only one item left. Useful for
1044  * combining values when an empty sequence doesn't make sense.
1045  *
1046  * This type is primarily used through the 'reduce' helper method, like:
1047  *
1048  *   sring longest = from(names)
1049  *                 | reduce([](string&& best, string& current) {
1050  *                     return best.size() >= current.size() ? best : current;
1051  *                   });
1052  */
1053 template<class Reducer>
1054 class Reduce : public Operator<Reduce<Reducer>> {
1055   const Reducer reducer_;
1056  public:
1057   Reduce(const Reducer& reducer)
1058     : reducer_(reducer)
1059   {}
1060
1061   template<class Source,
1062            class Value,
1063            class StorageType = typename std::decay<Value>::type>
1064   StorageType compose(const GenImpl<Value, Source>& source) const {
1065     Optional<StorageType> accum;
1066     source | [&](Value v) {
1067       if (accum.hasValue()) {
1068         accum = reducer_(std::move(accum.value()), std::forward<Value>(v));
1069       } else {
1070         accum = std::forward<Value>(v);
1071       }
1072     };
1073     if (!accum.hasValue()) {
1074       throw EmptySequence();
1075     }
1076     return accum.value();
1077   }
1078 };
1079
1080 /**
1081  * Count - for simply counting the items in a collection.
1082  *
1083  * This type is usually used through its singleton, 'count':
1084  *
1085  *   auto shortPrimes = seq(1, 100) | filter(isPrime) | count;
1086  */
1087 class Count : public Operator<Count> {
1088  public:
1089   template<class Source,
1090            class Value>
1091   size_t compose(const GenImpl<Value, Source>& source) const {
1092     return foldl(size_t(0),
1093                  [](size_t accum, Value v) {
1094                    return accum + 1;
1095                  }).compose(source);
1096   }
1097 };
1098
1099 /**
1100  * Sum - For simply summing up all the values from a source.
1101  *
1102  * This type is usually used through its singleton, 'sum':
1103  *
1104  *   auto gaussSum = seq(1, 100) | sum;
1105  */
1106 class Sum : public Operator<Sum> {
1107  public:
1108   template<class Source,
1109            class Value,
1110            class StorageType = typename std::decay<Value>::type>
1111   StorageType compose(const GenImpl<Value, Source>& source) const {
1112     return foldl(StorageType(0),
1113                  [](StorageType&& accum, Value v) {
1114                    return std::move(accum) + std::forward<Value>(v);
1115                  }).compose(source);
1116   }
1117 };
1118
1119 /**
1120  * Min - For a value which minimizes a key, where the key is determined by a
1121  * given selector, and compared by given comparer.
1122  *
1123  * This type is usually used through the singletone 'min' or through the helper
1124  * functions 'minBy' and 'maxBy'.
1125  *
1126  *   auto oldest = from(people)
1127  *               | minBy([](Person& p) {
1128  *                   return p.dateOfBirth;
1129  *                 });
1130  */
1131 template<class Selector,
1132          class Comparer>
1133 class Min : public Operator<Min<Selector, Comparer>> {
1134   Selector selector_;
1135   Comparer comparer_;
1136  public:
1137   Min(const Selector& selector = Selector(),
1138       const Comparer& comparer = Comparer())
1139     : selector_(selector)
1140     , comparer_(comparer)
1141   {}
1142
1143   template<class Value,
1144            class Source,
1145            class StorageType = typename std::decay<Value>::type,
1146            class Key = typename std::decay<
1147                typename std::result_of<Selector(Value)>::type
1148              >::type>
1149   StorageType compose(const GenImpl<Value, Source>& source) const {
1150     Optional<StorageType> min;
1151     Optional<Key> minKey;
1152     source | [&](Value v) {
1153       Key key = selector_(std::forward<Value>(v));
1154       if (!minKey.hasValue() || comparer_(key, minKey.value())) {
1155         minKey = key;
1156         min = std::forward<Value>(v);
1157       }
1158     };
1159     if (!min.hasValue()) {
1160       throw EmptySequence();
1161     }
1162     return min.value();
1163   }
1164 };
1165
1166 /**
1167  * Append - For collecting values from a source into a given output container
1168  * by appending.
1169  *
1170  * This type is usually used through the helper function 'appendTo', like:
1171  *
1172  *   vector<int64_t> ids;
1173  *   from(results) | map([](Person& p) { return p.id })
1174  *                 | appendTo(ids);
1175  */
1176 template<class Collection>
1177 class Append : public Operator<Append<Collection>> {
1178   Collection* const collection_;
1179  public:
1180   explicit Append(Collection* collection)
1181     : collection_(collection)
1182   {}
1183
1184   template<class Value,
1185            class Source>
1186   Collection& compose(const GenImpl<Value, Source>& source) const {
1187     source | [&](Value v) {
1188       collection_->insert(collection_->end(), std::forward<Value>(v));
1189     };
1190     return *collection_;
1191   }
1192 };
1193
1194 /**
1195  * Collect - For collecting values from a source in a collection of the desired
1196  * type.
1197  *
1198  * This type is usually used through the helper function 'as', like:
1199  *
1200  *   std::string upper = from(stringPiece)
1201  *                     | map(&toupper)
1202  *                     | as<std::string>();
1203  */
1204 template<class Collection>
1205 class Collect : public Operator<Collect<Collection>> {
1206  public:
1207   template<class Value,
1208            class Source,
1209            class StorageType = typename std::decay<Value>::type>
1210   Collection compose(const GenImpl<Value, Source>& source) const {
1211     Collection collection;
1212     source | [&](Value v) {
1213       collection.insert(collection.end(), std::forward<Value>(v));
1214     };
1215     return collection;
1216   }
1217 };
1218
1219
1220 /**
1221  * CollectTemplate - For collecting values from a source in a collection
1222  * constructed using the specified template type. Given the type of values
1223  * produced by the given generator, the collection type will be:
1224  *   Container<Value, Allocator<Value>>
1225  *
1226  * The allocator defaults to std::allocator, so this may be used for the STL
1227  * containers by simply using operators like 'as<set>', 'as<deque>',
1228  * 'as<vector>'. 'as', here is the helper method which is the usual means of
1229  * consturcting this operator.
1230  *
1231  * Example:
1232  *
1233  *   set<string> uniqueNames = from(names) | as<set>();
1234  */
1235 template<template<class, class> class Container,
1236          template<class> class Allocator>
1237 class CollectTemplate : public Operator<CollectTemplate<Container, Allocator>> {
1238  public:
1239   template<class Value,
1240            class Source,
1241            class StorageType = typename std::decay<Value>::type,
1242            class Collection = Container<StorageType, Allocator<StorageType>>>
1243   Collection compose(const GenImpl<Value, Source>& source) const {
1244     Collection collection;
1245     source | [&](Value v) {
1246       collection.insert(collection.end(), std::forward<Value>(v));
1247     };
1248     return collection;
1249   }
1250 };
1251 /**
1252  * Concat - For flattening generators of generators.
1253  *
1254  * This type is usually used through the 'concat' static value, like:
1255  *
1256  *   auto edges =
1257  *       from(nodes)
1258  *     | map([](Node& x) {
1259  *           return from(x.neighbors)
1260  *                | map([&](Node& y) {
1261  *                    return Edge(x, y);
1262  *                  });
1263  *         })
1264  *     | concat
1265  *     | as<std::set>();
1266  */
1267 class Concat : public Operator<Concat> {
1268 public:
1269   template<class Inner,
1270            class Source,
1271            class InnerValue = typename std::decay<Inner>::type::ValueType>
1272   class Generator :
1273       public GenImpl<InnerValue, Generator<Inner, Source, InnerValue>> {
1274     const Source source_;
1275   public:
1276     explicit Generator(Source source)
1277       : source_(std::move(source)) {}
1278
1279     template<class Handler>
1280     bool apply(Handler&& handler) const {
1281       return source_.apply([&](Inner inner) -> bool {
1282           return inner.apply(std::forward<Handler>(handler));
1283         });
1284     }
1285
1286     template<class Body>
1287     void foreach(Body&& body) const {
1288       source_.foreach([&](Inner inner) {
1289           inner.foreach(std::forward<Body>(body));
1290         });
1291     }
1292   };
1293
1294   template<class Value,
1295            class Source,
1296            class Gen = Generator<Value, Source>>
1297   Gen compose(GenImpl<Value, Source>&& source) const {
1298     return Gen(std::move(source.self()));
1299   }
1300
1301   template<class Value,
1302            class Source,
1303            class Gen = Generator<Value, Source>>
1304   Gen compose(const GenImpl<Value, Source>& source) const {
1305     return Gen(source.self());
1306   }
1307 };
1308
1309 /**
1310  * RangeConcat - For flattening generators of generators.
1311  *
1312  * This type is usually used through the 'rconcat' static value, like:
1313  *
1314  *   map<int, vector<int>> adjacency;
1315  *   auto sinks =
1316  *       from(adjacency)
1317  *     | get<1>()
1318  *     | rconcat()
1319  *     | as<std::set>();
1320  */
1321 class RangeConcat : public Operator<RangeConcat> {
1322 public:
1323   template<class Source,
1324            class Range,
1325            class InnerValue = typename ValueTypeOfRange<Range>::RefType>
1326   class Generator
1327     : public GenImpl<InnerValue, Generator<Source, Range, InnerValue>> {
1328     const Source source_;
1329    public:
1330     explicit Generator(Source source)
1331       : source_(std::move(source)) {}
1332
1333     template<class Body>
1334     void foreach(Body&& body) const {
1335       source_.foreach([&](Range range) {
1336           for (auto& value : range) {
1337             body(value);
1338           }
1339         });
1340     }
1341
1342     template<class Handler>
1343     bool apply(Handler&& handler) const {
1344       return source_.apply([&](Range range) {
1345           for (auto& value : range) {
1346             if (!handler(value)) {
1347               return false;
1348             }
1349           }
1350           return true;
1351         });
1352     }
1353   };
1354
1355   template<class Value,
1356            class Source,
1357            class Gen = Generator<Source, Value>>
1358   Gen compose(GenImpl<Value, Source>&& source) const {
1359     return Gen(std::move(source.self()));
1360   }
1361
1362   template<class Value,
1363            class Source,
1364            class Gen = Generator<Source, Value>>
1365   Gen compose(const GenImpl<Value, Source>& source) const {
1366     return Gen(source.self());
1367   }
1368 };
1369
1370 } //::detail
1371
1372 /**
1373  * Gen<T> - For wrapping template types in simple polymorphic wrapper.
1374  *
1375  * This type is usually used through the 'rconcat' static value, like:
1376  *
1377  *   map<int, vector<int>> adjacency;
1378  *   auto sinks =
1379  *       from(adjacency)
1380  *     | get<1>()
1381  *     | rconcat()
1382  *     | as<std::set>();
1383  **/
1384 template<class Value>
1385 class VirtualGen : public GenImpl<Value, VirtualGen<Value>> {
1386   class WrapperBase {
1387    public:
1388     virtual ~WrapperBase() {}
1389     virtual bool apply(const std::function<bool(Value)>& handler) const = 0;
1390     virtual void foreach(const std::function<void(Value)>& body) const = 0;
1391     virtual std::unique_ptr<const WrapperBase> clone() const = 0;
1392   };
1393
1394   template<class Wrapped>
1395   class WrapperImpl : public WrapperBase {
1396     const Wrapped wrapped_;
1397    public:
1398     explicit WrapperImpl(Wrapped wrapped)
1399      : wrapped_(std::move(wrapped)) {
1400     }
1401
1402     virtual bool apply(const std::function<bool(Value)>& handler) const {
1403       return wrapped_.apply(handler);
1404     }
1405
1406     virtual void foreach(const std::function<void(Value)>& body) const {
1407       wrapped_.foreach(body);
1408     }
1409
1410     virtual std::unique_ptr<const WrapperBase> clone() const {
1411       return std::unique_ptr<const WrapperBase>(new WrapperImpl(wrapped_));
1412     }
1413   };
1414
1415   std::unique_ptr<const WrapperBase> wrapper_;
1416
1417  public:
1418   template<class Self>
1419   /* implicit */ VirtualGen(Self source)
1420    : wrapper_(new WrapperImpl<Self>(std::move(source)))
1421   { }
1422
1423   VirtualGen(VirtualGen&& source)
1424    : wrapper_(std::move(source.wrapper_))
1425   { }
1426
1427   VirtualGen(const VirtualGen& source)
1428    : wrapper_(source.wrapper_->clone())
1429   { }
1430
1431   VirtualGen& operator=(const VirtualGen& source) {
1432     wrapper_.reset(source.wrapper_->clone());
1433     return *this;
1434   }
1435
1436   VirtualGen& operator=(VirtualGen&& source) {
1437     wrapper_= std::move(source.wrapper_);
1438     return *this;
1439   }
1440
1441   bool apply(const std::function<bool(Value)>& handler) const {
1442     return wrapper_->apply(handler);
1443   }
1444
1445   void foreach(const std::function<void(Value)>& body) const {
1446     wrapper_->foreach(body);
1447   }
1448 };
1449
1450 /**
1451  * non-template operators, statically defined to avoid the need for anything but
1452  * the header.
1453  */
1454 static const detail::Sum sum;
1455
1456 static const detail::Count count;
1457
1458 static const detail::First first;
1459
1460 static const detail::Any any;
1461
1462 static const detail::Min<Identity, Less> min;
1463
1464 static const detail::Min<Identity, Greater> max;
1465
1466 static const detail::Order<Identity> order;
1467
1468 static const detail::Map<Move> move;
1469
1470 static const detail::Concat concat;
1471
1472 static const detail::RangeConcat rconcat;
1473
1474 inline detail::Take take(size_t count) {
1475   return detail::Take(count);
1476 }
1477
1478 inline detail::Skip skip(size_t count) {
1479   return detail::Skip(count);
1480 }
1481
1482 }} //folly::gen::detail