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