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