folly/gen/Base-inl.h

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