folly/gen/Base-inl.h

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