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