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     Optional<StorageType> accum;
1015     source | [&](Value v) -> bool {
1016       accum = std::forward<Value>(v);
1017       return false;
1018     };
1019     if (!accum.hasValue()) {
1020       throw EmptySequence();
1021     }
1022     return std::move(accum.value());
1023   }
1024 };
1025
1026
1027 /**
1028  * Any - For determining whether any values are contained in a sequence.
1029  *
1030  * This type is primarily used through the 'any' static value, like:
1031  *
1032  *   bool any20xPrimes = seq(200, 210) | filter(isPrime) | any;
1033  */
1034 class Any : public Operator<Any> {
1035  public:
1036   template<class Source,
1037            class Value>
1038   bool compose(const GenImpl<Value, Source>& source) const {
1039     bool any = false;
1040     source | [&](Value v) -> bool {
1041       any = true;
1042       return false;
1043     };
1044     return any;
1045   }
1046 };
1047
1048 /**
1049  * Reduce - Functional reduce, for recursively combining values from a source
1050  * using a reducer function until there is only one item left. Useful for
1051  * combining values when an empty sequence doesn't make sense.
1052  *
1053  * This type is primarily used through the 'reduce' helper method, like:
1054  *
1055  *   sring longest = from(names)
1056  *                 | reduce([](string&& best, string& current) {
1057  *                     return best.size() >= current.size() ? best : current;
1058  *                   });
1059  */
1060 template<class Reducer>
1061 class Reduce : public Operator<Reduce<Reducer>> {
1062   Reducer reducer_;
1063  public:
1064   Reduce(const Reducer& reducer)
1065     : reducer_(reducer)
1066   {}
1067
1068   template<class Source,
1069            class Value,
1070            class StorageType = typename std::decay<Value>::type>
1071   StorageType compose(const GenImpl<Value, Source>& source) const {
1072     Optional<StorageType> accum;
1073     source | [&](Value v) {
1074       if (accum.hasValue()) {
1075         accum = reducer_(std::move(accum.value()), std::forward<Value>(v));
1076       } else {
1077         accum = std::forward<Value>(v);
1078       }
1079     };
1080     if (!accum.hasValue()) {
1081       throw EmptySequence();
1082     }
1083     return accum.value();
1084   }
1085 };
1086
1087 /**
1088  * Count - for simply counting the items in a collection.
1089  *
1090  * This type is usually used through its singleton, 'count':
1091  *
1092  *   auto shortPrimes = seq(1, 100) | filter(isPrime) | count;
1093  */
1094 class Count : public Operator<Count> {
1095  public:
1096   template<class Source,
1097            class Value>
1098   size_t compose(const GenImpl<Value, Source>& source) const {
1099     return foldl(size_t(0),
1100                  [](size_t accum, Value v) {
1101                    return accum + 1;
1102                  }).compose(source);
1103   }
1104 };
1105
1106 /**
1107  * Sum - For simply summing up all the values from a source.
1108  *
1109  * This type is usually used through its singleton, 'sum':
1110  *
1111  *   auto gaussSum = seq(1, 100) | sum;
1112  */
1113 class Sum : public Operator<Sum> {
1114  public:
1115   template<class Source,
1116            class Value,
1117            class StorageType = typename std::decay<Value>::type>
1118   StorageType compose(const GenImpl<Value, Source>& source) const {
1119     return foldl(StorageType(0),
1120                  [](StorageType&& accum, Value v) {
1121                    return std::move(accum) + std::forward<Value>(v);
1122                  }).compose(source);
1123   }
1124 };
1125
1126 /**
1127  * Min - For a value which minimizes a key, where the key is determined by a
1128  * given selector, and compared by given comparer.
1129  *
1130  * This type is usually used through the singletone 'min' or through the helper
1131  * functions 'minBy' and 'maxBy'.
1132  *
1133  *   auto oldest = from(people)
1134  *               | minBy([](Person& p) {
1135  *                   return p.dateOfBirth;
1136  *                 });
1137  */
1138 template<class Selector,
1139          class Comparer>
1140 class Min : public Operator<Min<Selector, Comparer>> {
1141   Selector selector_;
1142   Comparer comparer_;
1143  public:
1144   Min(const Selector& selector = Selector(),
1145       const Comparer& comparer = Comparer())
1146     : selector_(selector)
1147     , comparer_(comparer)
1148   {}
1149
1150   template<class Value,
1151            class Source,
1152            class StorageType = typename std::decay<Value>::type,
1153            class Key = typename std::decay<
1154                typename std::result_of<Selector(Value)>::type
1155              >::type>
1156   StorageType compose(const GenImpl<Value, Source>& source) const {
1157     Optional<StorageType> min;
1158     Optional<Key> minKey;
1159     source | [&](Value v) {
1160       Key key = selector_(std::forward<Value>(v));
1161       if (!minKey.hasValue() || comparer_(key, minKey.value())) {
1162         minKey = key;
1163         min = std::forward<Value>(v);
1164       }
1165     };
1166     if (!min.hasValue()) {
1167       throw EmptySequence();
1168     }
1169     return min.value();
1170   }
1171 };
1172
1173 /**
1174  * Append - For collecting values from a source into a given output container
1175  * by appending.
1176  *
1177  * This type is usually used through the helper function 'appendTo', like:
1178  *
1179  *   vector<int64_t> ids;
1180  *   from(results) | map([](Person& p) { return p.id })
1181  *                 | appendTo(ids);
1182  */
1183 template<class Collection>
1184 class Append : public Operator<Append<Collection>> {
1185   Collection* collection_;
1186  public:
1187   explicit Append(Collection* collection)
1188     : collection_(collection)
1189   {}
1190
1191   template<class Value,
1192            class Source>
1193   Collection& compose(const GenImpl<Value, Source>& source) const {
1194     source | [&](Value v) {
1195       collection_->insert(collection_->end(), std::forward<Value>(v));
1196     };
1197     return *collection_;
1198   }
1199 };
1200
1201 /**
1202  * Collect - For collecting values from a source in a collection of the desired
1203  * type.
1204  *
1205  * This type is usually used through the helper function 'as', like:
1206  *
1207  *   std::string upper = from(stringPiece)
1208  *                     | map(&toupper)
1209  *                     | as<std::string>();
1210  */
1211 template<class Collection>
1212 class Collect : public Operator<Collect<Collection>> {
1213  public:
1214   template<class Value,
1215            class Source,
1216            class StorageType = typename std::decay<Value>::type>
1217   Collection compose(const GenImpl<Value, Source>& source) const {
1218     Collection collection;
1219     source | [&](Value v) {
1220       collection.insert(collection.end(), std::forward<Value>(v));
1221     };
1222     return collection;
1223   }
1224 };
1225
1226
1227 /**
1228  * CollectTemplate - For collecting values from a source in a collection
1229  * constructed using the specified template type. Given the type of values
1230  * produced by the given generator, the collection type will be:
1231  *   Container<Value, Allocator<Value>>
1232  *
1233  * The allocator defaults to std::allocator, so this may be used for the STL
1234  * containers by simply using operators like 'as<set>', 'as<deque>',
1235  * 'as<vector>'. 'as', here is the helper method which is the usual means of
1236  * consturcting this operator.
1237  *
1238  * Example:
1239  *
1240  *   set<string> uniqueNames = from(names) | as<set>();
1241  */
1242 template<template<class, class> class Container,
1243          template<class> class Allocator>
1244 class CollectTemplate : public Operator<CollectTemplate<Container, Allocator>> {
1245  public:
1246   template<class Value,
1247            class Source,
1248            class StorageType = typename std::decay<Value>::type,
1249            class Collection = Container<StorageType, Allocator<StorageType>>>
1250   Collection compose(const GenImpl<Value, Source>& source) const {
1251     Collection collection;
1252     source | [&](Value v) {
1253       collection.insert(collection.end(), std::forward<Value>(v));
1254     };
1255     return collection;
1256   }
1257 };
1258 /**
1259  * Concat - For flattening generators of generators.
1260  *
1261  * This type is usually used through the 'concat' static value, like:
1262  *
1263  *   auto edges =
1264  *       from(nodes)
1265  *     | map([](Node& x) {
1266  *           return from(x.neighbors)
1267  *                | map([&](Node& y) {
1268  *                    return Edge(x, y);
1269  *                  });
1270  *         })
1271  *     | concat
1272  *     | as<std::set>();
1273  */
1274 class Concat : public Operator<Concat> {
1275 public:
1276   template<class Inner,
1277            class Source,
1278            class InnerValue = typename std::decay<Inner>::type::ValueType>
1279   class Generator :
1280       public GenImpl<InnerValue, Generator<Inner, Source, InnerValue>> {
1281     Source source_;
1282   public:
1283     explicit Generator(Source source)
1284       : source_(std::move(source)) {}
1285
1286     template<class Handler>
1287     bool apply(Handler&& handler) const {
1288       return source_.apply([&](Inner inner) -> bool {
1289           return inner.apply(std::forward<Handler>(handler));
1290         });
1291     }
1292
1293     template<class Body>
1294     void foreach(Body&& body) const {
1295       source_.foreach([&](Inner inner) {
1296           inner.foreach(std::forward<Body>(body));
1297         });
1298     }
1299   };
1300
1301   template<class Value,
1302            class Source,
1303            class Gen = Generator<Value, Source>>
1304   Gen compose(GenImpl<Value, Source>&& source) const {
1305     return Gen(std::move(source.self()));
1306   }
1307
1308   template<class Value,
1309            class Source,
1310            class Gen = Generator<Value, Source>>
1311   Gen compose(const GenImpl<Value, Source>& source) const {
1312     return Gen(source.self());
1313   }
1314 };
1315
1316 /**
1317  * RangeConcat - For flattening generators of iterables.
1318  *
1319  * This type is usually used through the 'rconcat' static value, like:
1320  *
1321  *   map<int, vector<int>> adjacency;
1322  *   auto sinks =
1323  *       from(adjacency)
1324  *     | get<1>()
1325  *     | rconcat()
1326  *     | as<std::set>();
1327  */
1328 class RangeConcat : public Operator<RangeConcat> {
1329 public:
1330   template<class Source,
1331            class Range,
1332            class InnerValue = typename ValueTypeOfRange<Range>::RefType>
1333   class Generator
1334     : public GenImpl<InnerValue, Generator<Source, Range, InnerValue>> {
1335     Source source_;
1336    public:
1337     explicit Generator(Source source)
1338       : source_(std::move(source)) {}
1339
1340     template<class Body>
1341     void foreach(Body&& body) const {
1342       source_.foreach([&](Range range) {
1343           for (auto& value : range) {
1344             body(value);
1345           }
1346         });
1347     }
1348
1349     template<class Handler>
1350     bool apply(Handler&& handler) const {
1351       return source_.apply([&](Range range) {
1352           for (auto& value : range) {
1353             if (!handler(value)) {
1354               return false;
1355             }
1356           }
1357           return true;
1358         });
1359     }
1360   };
1361
1362   template<class Value,
1363            class Source,
1364            class Gen = Generator<Source, Value>>
1365   Gen compose(GenImpl<Value, Source>&& source) const {
1366     return Gen(std::move(source.self()));
1367   }
1368
1369   template<class Value,
1370            class Source,
1371            class Gen = Generator<Source, Value>>
1372   Gen compose(const GenImpl<Value, Source>& source) const {
1373     return Gen(source.self());
1374   }
1375 };
1376
1377 } //::detail
1378
1379 /**
1380  * VirtualGen<T> - For wrapping template types in simple polymorphic wrapper.
1381  **/
1382 template<class Value>
1383 class VirtualGen : public GenImpl<Value, VirtualGen<Value>> {
1384   class WrapperBase {
1385    public:
1386     virtual ~WrapperBase() {}
1387     virtual bool apply(const std::function<bool(Value)>& handler) const = 0;
1388     virtual void foreach(const std::function<void(Value)>& body) const = 0;
1389     virtual std::unique_ptr<const WrapperBase> clone() const = 0;
1390   };
1391
1392   template<class Wrapped>
1393   class WrapperImpl : public WrapperBase {
1394     Wrapped wrapped_;
1395    public:
1396     explicit WrapperImpl(Wrapped wrapped)
1397      : wrapped_(std::move(wrapped)) {
1398     }
1399
1400     virtual bool apply(const std::function<bool(Value)>& handler) const {
1401       return wrapped_.apply(handler);
1402     }
1403
1404     virtual void foreach(const std::function<void(Value)>& body) const {
1405       wrapped_.foreach(body);
1406     }
1407
1408     virtual std::unique_ptr<const WrapperBase> clone() const {
1409       return std::unique_ptr<const WrapperBase>(new WrapperImpl(wrapped_));
1410     }
1411   };
1412
1413   std::unique_ptr<const WrapperBase> wrapper_;
1414
1415  public:
1416   template<class Self>
1417   /* implicit */ VirtualGen(Self source)
1418    : wrapper_(new WrapperImpl<Self>(std::move(source)))
1419   { }
1420
1421   VirtualGen(VirtualGen&& source)
1422    : wrapper_(std::move(source.wrapper_))
1423   { }
1424
1425   VirtualGen(const VirtualGen& source)
1426    : wrapper_(source.wrapper_->clone())
1427   { }
1428
1429   VirtualGen& operator=(const VirtualGen& source) {
1430     wrapper_.reset(source.wrapper_->clone());
1431     return *this;
1432   }
1433
1434   VirtualGen& operator=(VirtualGen&& source) {
1435     wrapper_= std::move(source.wrapper_);
1436     return *this;
1437   }
1438
1439   bool apply(const std::function<bool(Value)>& handler) const {
1440     return wrapper_->apply(handler);
1441   }
1442
1443   void foreach(const std::function<void(Value)>& body) const {
1444     wrapper_->foreach(body);
1445   }
1446 };
1447
1448 /**
1449  * non-template operators, statically defined to avoid the need for anything but
1450  * the header.
1451  */
1452 static const detail::Sum sum;
1453
1454 static const detail::Count count;
1455
1456 static const detail::First first;
1457
1458 static const detail::Any any;
1459
1460 static const detail::Min<Identity, Less> min;
1461
1462 static const detail::Min<Identity, Greater> max;
1463
1464 static const detail::Order<Identity> order;
1465
1466 static const detail::Map<Move> move;
1467
1468 static const detail::Concat concat;
1469
1470 static const detail::RangeConcat rconcat;
1471
1472 inline detail::Take take(size_t count) {
1473   return detail::Take(count);
1474 }
1475
1476 inline detail::Skip skip(size_t count) {
1477   return detail::Skip(count);
1478 }
1479
1480 }} //folly::gen::detail