folly/experimental/Gen-inl.h

   1 /*
   2  * Copyright 2013 Facebook, Inc.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *   http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 namespace folly { namespace gen {
  18
  19 /**
  20  * IsCompatibleSignature - Trait type for testing whether a given Functor
  21  * matches an expected signature.
  22  *
  23  * Usage:
  24  *   IsCompatibleSignature<FunctorType, bool(int, float)>::value
  25  */
  26 template<class Candidate, class Expected>
  27 class IsCompatibleSignature {
  28   static constexpr bool value = false;
  29 };
  30
  31 template<class Candidate,
  32          class ExpectedReturn,
  33          class... ArgTypes>
  34 class IsCompatibleSignature<Candidate, ExpectedReturn(ArgTypes...)> {
  35   template<class F,
  36            class ActualReturn =
  37              decltype(std::declval<F>()(std::declval<ArgTypes>()...)),
  38            bool good = std::is_same<ExpectedReturn, ActualReturn>::value>
  39   static constexpr bool testArgs(int* p) {
  40     return good;
  41   }
  42
  43   template<class F>
  44   static constexpr bool testArgs(...) {
  45     return false;
  46   }
  47 public:
  48   static constexpr bool value = testArgs<Candidate>(nullptr);
  49 };
  50
  51 /**
  52  * ArgumentReference - For determining ideal argument type to receive a value.
  53  */
  54 template<class T>
  55 struct ArgumentReference :
  56   public std::conditional<std::is_reference<T>::value,
  57                           T, // T& -> T&, T&& -> T&&, const T& -> const T&
  58                           typename std::conditional<
  59                             std::is_const<T>::value,
  60                             T&, // const int -> const int&
  61                             T&& // int -> int&&
  62                           >::type> {};
  63
  64 /**
  65  * FBounded - Helper type for the curiously recurring template pattern, used
  66  * heavily here to enable inlining and obviate virtual functions
  67  */
  68 template<class Self>
  69 struct FBounded {
  70   const Self& self() const {
  71     return *static_cast<const Self*>(this);
  72   }
  73
  74   Self& self() {
  75     return *static_cast<Self*>(this);
  76   }
  77 };
  78
  79 /**
  80  * Operator - Core abstraction of an operation which may be applied to a
  81  * generator. All operators implement a method compose(), which takes a
  82  * generator and produces an output generator.
  83  */
  84 template<class Self>
  85 class Operator : public FBounded<Self> {
  86  public:
  87   /**
  88    * compose() - Must be implemented by child class to compose a new Generator
  89    * out of a given generator. This function left intentionally unimplemented.
  90    */
  91   template<class Source,
  92            class Value,
  93            class ResultGen = void>
  94   ResultGen compose(const GenImpl<Value, Source>& source) const;
  95
  96  protected:
  97   Operator() = default;
  98   Operator(const Operator&) = default;
  99   Operator(Operator&&) = default;
 100 };
 101
 102 /**
 103  * operator|() - For composing two operators without binding it to a
 104  * particular generator.
 105  */
 106 template<class Left,
 107          class Right,
 108          class Composed = detail::Composed<Left, Right>>
 109 Composed operator|(const Operator<Left>& left,
 110                    const Operator<Right>& right) {
 111   return Composed(left.self(), right.self());
 112 }
 113
 114 template<class Left,
 115          class Right,
 116          class Composed = detail::Composed<Left, Right>>
 117 Composed operator|(const Operator<Left>& left,
 118                    Operator<Right>&& right) {
 119   return Composed(left.self(), std::move(right.self()));
 120 }
 121
 122 template<class Left,
 123          class Right,
 124          class Composed = detail::Composed<Left, Right>>
 125 Composed operator|(Operator<Left>&& left,
 126                    const Operator<Right>& right) {
 127   return Composed(std::move(left.self()), right.self());
 128 }
 129
 130 template<class Left,
 131          class Right,
 132          class Composed = detail::Composed<Left, Right>>
 133 Composed operator|(Operator<Left>&& left,
 134                    Operator<Right>&& right) {
 135   return Composed(std::move(left.self()), std::move(right.self()));
 136 }
 137
 138 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) -> bool {
 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   explicit 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   First() { }
1011
1012   template<class Source,
1013            class Value,
1014            class StorageType = typename std::decay<Value>::type>
1015   StorageType compose(const GenImpl<Value, Source>& source) const {
1016     Optional<StorageType> accum;
1017     source | [&](Value v) -> bool {
1018       accum = std::forward<Value>(v);
1019       return false;
1020     };
1021     if (!accum.hasValue()) {
1022       throw EmptySequence();
1023     }
1024     return std::move(accum.value());
1025   }
1026 };
1027
1028
1029 /**
1030  * Any - For determining whether any values are contained in a sequence.
1031  *
1032  * This type is primarily used through the 'any' static value, like:
1033  *
1034  *   bool any20xPrimes = seq(200, 210) | filter(isPrime) | any;
1035  */
1036 class Any : public Operator<Any> {
1037  public:
1038   Any() { }
1039
1040   template<class Source,
1041            class Value>
1042   bool compose(const GenImpl<Value, Source>& source) const {
1043     bool any = false;
1044     source | [&](Value v) -> bool {
1045       any = true;
1046       return false;
1047     };
1048     return any;
1049   }
1050 };
1051
1052 /**
1053  * Reduce - Functional reduce, for recursively combining values from a source
1054  * using a reducer function until there is only one item left. Useful for
1055  * combining values when an empty sequence doesn't make sense.
1056  *
1057  * This type is primarily used through the 'reduce' helper method, like:
1058  *
1059  *   sring longest = from(names)
1060  *                 | reduce([](string&& best, string& current) {
1061  *                     return best.size() >= current.size() ? best : current;
1062  *                   });
1063  */
1064 template<class Reducer>
1065 class Reduce : public Operator<Reduce<Reducer>> {
1066   Reducer reducer_;
1067  public:
1068   explicit Reduce(const Reducer& reducer)
1069     : reducer_(reducer)
1070   {}
1071
1072   template<class Source,
1073            class Value,
1074            class StorageType = typename std::decay<Value>::type>
1075   StorageType compose(const GenImpl<Value, Source>& source) const {
1076     Optional<StorageType> accum;
1077     source | [&](Value v) {
1078       if (accum.hasValue()) {
1079         accum = reducer_(std::move(accum.value()), std::forward<Value>(v));
1080       } else {
1081         accum = std::forward<Value>(v);
1082       }
1083     };
1084     if (!accum.hasValue()) {
1085       throw EmptySequence();
1086     }
1087     return accum.value();
1088   }
1089 };
1090
1091 /**
1092  * Count - for simply counting the items in a collection.
1093  *
1094  * This type is usually used through its singleton, 'count':
1095  *
1096  *   auto shortPrimes = seq(1, 100) | filter(isPrime) | count;
1097  */
1098 class Count : public Operator<Count> {
1099  public:
1100   Count() { }
1101
1102   template<class Source,
1103            class Value>
1104   size_t compose(const GenImpl<Value, Source>& source) const {
1105     return foldl(size_t(0),
1106                  [](size_t accum, Value v) {
1107                    return accum + 1;
1108                  }).compose(source);
1109   }
1110 };
1111
1112 /**
1113  * Sum - For simply summing up all the values from a source.
1114  *
1115  * This type is usually used through its singleton, 'sum':
1116  *
1117  *   auto gaussSum = seq(1, 100) | sum;
1118  */
1119 class Sum : public Operator<Sum> {
1120  public:
1121   Sum() { }
1122
1123   template<class Source,
1124            class Value,
1125            class StorageType = typename std::decay<Value>::type>
1126   StorageType compose(const GenImpl<Value, Source>& source) const {
1127     return foldl(StorageType(0),
1128                  [](StorageType&& accum, Value v) {
1129                    return std::move(accum) + std::forward<Value>(v);
1130                  }).compose(source);
1131   }
1132 };
1133
1134 /**
1135  * Min - For a value which minimizes a key, where the key is determined by a
1136  * given selector, and compared by given comparer.
1137  *
1138  * This type is usually used through the singletone 'min' or through the helper
1139  * functions 'minBy' and 'maxBy'.
1140  *
1141  *   auto oldest = from(people)
1142  *               | minBy([](Person& p) {
1143  *                   return p.dateOfBirth;
1144  *                 });
1145  */
1146 template<class Selector,
1147          class Comparer>
1148 class Min : public Operator<Min<Selector, Comparer>> {
1149   Selector selector_;
1150   Comparer comparer_;
1151  public:
1152   explicit Min(const Selector& selector = Selector(),
1153                const Comparer& comparer = Comparer())
1154     : selector_(selector)
1155     , comparer_(comparer)
1156   {}
1157
1158   template<class Value,
1159            class Source,
1160            class StorageType = typename std::decay<Value>::type,
1161            class Key = typename std::decay<
1162                typename std::result_of<Selector(Value)>::type
1163              >::type>
1164   StorageType compose(const GenImpl<Value, Source>& source) const {
1165     Optional<StorageType> min;
1166     Optional<Key> minKey;
1167     source | [&](Value v) {
1168       Key key = selector_(std::forward<Value>(v));
1169       if (!minKey.hasValue() || comparer_(key, minKey.value())) {
1170         minKey = key;
1171         min = std::forward<Value>(v);
1172       }
1173     };
1174     if (!min.hasValue()) {
1175       throw EmptySequence();
1176     }
1177     return min.value();
1178   }
1179 };
1180
1181 /**
1182  * Append - For collecting values from a source into a given output container
1183  * by appending.
1184  *
1185  * This type is usually used through the helper function 'appendTo', like:
1186  *
1187  *   vector<int64_t> ids;
1188  *   from(results) | map([](Person& p) { return p.id })
1189  *                 | appendTo(ids);
1190  */
1191 template<class Collection>
1192 class Append : public Operator<Append<Collection>> {
1193   Collection* collection_;
1194  public:
1195   explicit Append(Collection* collection)
1196     : collection_(collection)
1197   {}
1198
1199   template<class Value,
1200            class Source>
1201   Collection& compose(const GenImpl<Value, Source>& source) const {
1202     source | [&](Value v) {
1203       collection_->insert(collection_->end(), std::forward<Value>(v));
1204     };
1205     return *collection_;
1206   }
1207 };
1208
1209 /**
1210  * Collect - For collecting values from a source in a collection of the desired
1211  * type.
1212  *
1213  * This type is usually used through the helper function 'as', like:
1214  *
1215  *   std::string upper = from(stringPiece)
1216  *                     | map(&toupper)
1217  *                     | as<std::string>();
1218  */
1219 template<class Collection>
1220 class Collect : public Operator<Collect<Collection>> {
1221  public:
1222   Collect() { }
1223
1224   template<class Value,
1225            class Source,
1226            class StorageType = typename std::decay<Value>::type>
1227   Collection compose(const GenImpl<Value, Source>& source) const {
1228     Collection collection;
1229     source | [&](Value v) {
1230       collection.insert(collection.end(), std::forward<Value>(v));
1231     };
1232     return collection;
1233   }
1234 };
1235
1236
1237 /**
1238  * CollectTemplate - For collecting values from a source in a collection
1239  * constructed using the specified template type. Given the type of values
1240  * produced by the given generator, the collection type will be:
1241  *   Container<Value, Allocator<Value>>
1242  *
1243  * The allocator defaults to std::allocator, so this may be used for the STL
1244  * containers by simply using operators like 'as<set>', 'as<deque>',
1245  * 'as<vector>'. 'as', here is the helper method which is the usual means of
1246  * consturcting this operator.
1247  *
1248  * Example:
1249  *
1250  *   set<string> uniqueNames = from(names) | as<set>();
1251  */
1252 template<template<class, class> class Container,
1253          template<class> class Allocator>
1254 class CollectTemplate : public Operator<CollectTemplate<Container, Allocator>> {
1255  public:
1256   CollectTemplate() { }
1257
1258   template<class Value,
1259            class Source,
1260            class StorageType = typename std::decay<Value>::type,
1261            class Collection = Container<StorageType, Allocator<StorageType>>>
1262   Collection compose(const GenImpl<Value, Source>& source) const {
1263     Collection collection;
1264     source | [&](Value v) {
1265       collection.insert(collection.end(), std::forward<Value>(v));
1266     };
1267     return collection;
1268   }
1269 };
1270
1271 /**
1272  * Concat - For flattening generators of generators.
1273  *
1274  * This type is usually used through the 'concat' static value, like:
1275  *
1276  *   auto edges =
1277  *       from(nodes)
1278  *     | map([](Node& x) {
1279  *           return from(x.neighbors)
1280  *                | map([&](Node& y) {
1281  *                    return Edge(x, y);
1282  *                  });
1283  *         })
1284  *     | concat
1285  *     | as<std::set>();
1286  */
1287 class Concat : public Operator<Concat> {
1288  public:
1289   Concat() { }
1290
1291   template<class Inner,
1292            class Source,
1293            class InnerValue = typename std::decay<Inner>::type::ValueType>
1294   class Generator :
1295       public GenImpl<InnerValue, Generator<Inner, Source, InnerValue>> {
1296     Source source_;
1297    public:
1298     explicit Generator(Source source)
1299       : source_(std::move(source)) {}
1300
1301     template<class Handler>
1302     bool apply(Handler&& handler) const {
1303       return source_.apply([&](Inner inner) -> bool {
1304           return inner.apply(std::forward<Handler>(handler));
1305         });
1306     }
1307
1308     template<class Body>
1309     void foreach(Body&& body) const {
1310       source_.foreach([&](Inner inner) {
1311           inner.foreach(std::forward<Body>(body));
1312         });
1313     }
1314   };
1315
1316   template<class Value,
1317            class Source,
1318            class Gen = Generator<Value, Source>>
1319   Gen compose(GenImpl<Value, Source>&& source) const {
1320     return Gen(std::move(source.self()));
1321   }
1322
1323   template<class Value,
1324            class Source,
1325            class Gen = Generator<Value, Source>>
1326   Gen compose(const GenImpl<Value, Source>& source) const {
1327     return Gen(source.self());
1328   }
1329 };
1330
1331 /**
1332  * RangeConcat - For flattening generators of iterables.
1333  *
1334  * This type is usually used through the 'rconcat' static value, like:
1335  *
1336  *   map<int, vector<int>> adjacency;
1337  *   auto sinks =
1338  *       from(adjacency)
1339  *     | get<1>()
1340  *     | rconcat()
1341  *     | as<std::set>();
1342  */
1343 class RangeConcat : public Operator<RangeConcat> {
1344  public:
1345   RangeConcat() { }
1346
1347   template<class Source,
1348            class Range,
1349            class InnerValue = typename ValueTypeOfRange<Range>::RefType>
1350   class Generator
1351     : public GenImpl<InnerValue, Generator<Source, Range, InnerValue>> {
1352     Source source_;
1353    public:
1354     explicit Generator(Source source)
1355       : source_(std::move(source)) {}
1356
1357     template<class Body>
1358     void foreach(Body&& body) const {
1359       source_.foreach([&](Range range) {
1360           for (auto& value : range) {
1361             body(value);
1362           }
1363         });
1364     }
1365
1366     template<class Handler>
1367     bool apply(Handler&& handler) const {
1368       return source_.apply([&](Range range) -> bool {
1369           for (auto& value : range) {
1370             if (!handler(value)) {
1371               return false;
1372             }
1373           }
1374           return true;
1375         });
1376     }
1377   };
1378
1379   template<class Value,
1380            class Source,
1381            class Gen = Generator<Source, Value>>
1382   Gen compose(GenImpl<Value, Source>&& source) const {
1383     return Gen(std::move(source.self()));
1384   }
1385
1386   template<class Value,
1387            class Source,
1388            class Gen = Generator<Source, Value>>
1389   Gen compose(const GenImpl<Value, Source>& source) const {
1390     return Gen(source.self());
1391   }
1392 };
1393
1394 } //::detail
1395
1396 /**
1397  * VirtualGen<T> - For wrapping template types in simple polymorphic wrapper.
1398  **/
1399 template<class Value>
1400 class VirtualGen : public GenImpl<Value, VirtualGen<Value>> {
1401   class WrapperBase {
1402    public:
1403     virtual ~WrapperBase() {}
1404     virtual bool apply(const std::function<bool(Value)>& handler) const = 0;
1405     virtual void foreach(const std::function<void(Value)>& body) const = 0;
1406     virtual std::unique_ptr<const WrapperBase> clone() const = 0;
1407   };
1408
1409   template<class Wrapped>
1410   class WrapperImpl : public WrapperBase {
1411     Wrapped wrapped_;
1412    public:
1413     explicit WrapperImpl(Wrapped wrapped)
1414      : wrapped_(std::move(wrapped)) {
1415     }
1416
1417     virtual bool apply(const std::function<bool(Value)>& handler) const {
1418       return wrapped_.apply(handler);
1419     }
1420
1421     virtual void foreach(const std::function<void(Value)>& body) const {
1422       wrapped_.foreach(body);
1423     }
1424
1425     virtual std::unique_ptr<const WrapperBase> clone() const {
1426       return std::unique_ptr<const WrapperBase>(new WrapperImpl(wrapped_));
1427     }
1428   };
1429
1430   std::unique_ptr<const WrapperBase> wrapper_;
1431
1432  public:
1433   template<class Self>
1434   /* implicit */ VirtualGen(Self source)
1435    : wrapper_(new WrapperImpl<Self>(std::move(source)))
1436   { }
1437
1438   VirtualGen(VirtualGen&& source)
1439    : wrapper_(std::move(source.wrapper_))
1440   { }
1441
1442   VirtualGen(const VirtualGen& source)
1443    : wrapper_(source.wrapper_->clone())
1444   { }
1445
1446   VirtualGen& operator=(const VirtualGen& source) {
1447     wrapper_.reset(source.wrapper_->clone());
1448     return *this;
1449   }
1450
1451   VirtualGen& operator=(VirtualGen&& source) {
1452     wrapper_= std::move(source.wrapper_);
1453     return *this;
1454   }
1455
1456   bool apply(const std::function<bool(Value)>& handler) const {
1457     return wrapper_->apply(handler);
1458   }
1459
1460   void foreach(const std::function<void(Value)>& body) const {
1461     wrapper_->foreach(body);
1462   }
1463 };
1464
1465 /**
1466  * non-template operators, statically defined to avoid the need for anything but
1467  * the header.
1468  */
1469 static const detail::Sum sum;
1470
1471 static const detail::Count count;
1472
1473 static const detail::First first;
1474
1475 static const detail::Any any;
1476
1477 static const detail::Min<Identity, Less> min;
1478
1479 static const detail::Min<Identity, Greater> max;
1480
1481 static const detail::Order<Identity> order;
1482
1483 static const detail::Map<Move> move;
1484
1485 static const detail::Concat concat;
1486
1487 static const detail::RangeConcat rconcat;
1488
1489 inline detail::Take take(size_t count) {
1490   return detail::Take(count);
1491 }
1492
1493 inline detail::Skip skip(size_t count) {
1494   return detail::Skip(count);
1495 }
1496
1497 }} //folly::gen::detail