folly/gen/Base-inl.h

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