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 /**
1345  * Any - For determining whether any values in a sequence satisfy a predicate.
1346  *
1347  * This type is primarily used through the 'any' static value, like:
1348  *
1349  *   bool any20xPrimes = seq(200, 210) | filter(isPrime) | any;
1350  *
1351  * Note that it may also be used like so:
1352  *
1353  *   bool any20xPrimes = seq(200, 210) | any(isPrime);
1354  *
1355  */
1356 class Any : public Operator<Any> {
1357  public:
1358   Any() = default;
1359
1360   template<class Source,
1361            class Value>
1362   bool compose(const GenImpl<Value, Source>& source) const {
1363     bool any = false;
1364     source | [&](Value v) -> bool {
1365       any = true;
1366       return false;
1367     };
1368     return any;
1369   }
1370
1371   /**
1372    * Convenience function for use like:
1373    *
1374    *  bool found = gen | any([](int i) { return i * i > 100; });
1375    */
1376   template<class Predicate,
1377            class Filter = Filter<Predicate>,
1378            class Composed = Composed<Filter, Any>>
1379   Composed operator()(Predicate pred) const {
1380     return Composed(Filter(std::move(pred)), Any());
1381   }
1382 };
1383
1384 /**
1385  * All - For determining whether all values in a sequence satisfy a predicate.
1386  *
1387  * This type is primarily used through the 'any' static value, like:
1388  *
1389  *   bool valid = from(input) | all(validate);
1390  *
1391  * Note: Passing an empty sequence through 'all()' will always return true.
1392  */
1393 template<class Predicate>
1394 class All : public Operator<All<Predicate>> {
1395   Predicate pred_;
1396  public:
1397   All() = default;
1398   explicit All(Predicate pred)
1399     : pred_(std::move(pred))
1400   { }
1401
1402   template<class Source,
1403            class Value>
1404   bool compose(const GenImpl<Value, Source>& source) const {
1405     static_assert(!Source::infinite, "Cannot call 'all' on infinite source");
1406     bool all = true;
1407     source | [&](Value v) -> bool {
1408       if (!pred_(std::forward<Value>(v))) {
1409         all = false;
1410         return false;
1411       }
1412       return true;
1413     };
1414     return all;
1415   }
1416 };
1417
1418 /**
1419  * Reduce - Functional reduce, for recursively combining values from a source
1420  * using a reducer function until there is only one item left. Useful for
1421  * combining values when an empty sequence doesn't make sense.
1422  *
1423  * This type is primarily used through the 'reduce' helper method, like:
1424  *
1425  *   sring longest = from(names)
1426  *                 | reduce([](string&& best, string& current) {
1427  *                     return best.size() >= current.size() ? best : current;
1428  *                   });
1429  */
1430 template<class Reducer>
1431 class Reduce : public Operator<Reduce<Reducer>> {
1432   Reducer reducer_;
1433  public:
1434   Reduce() = default;
1435   explicit Reduce(Reducer reducer)
1436     : reducer_(std::move(reducer))
1437   {}
1438
1439   template<class Source,
1440            class Value,
1441            class StorageType = typename std::decay<Value>::type>
1442   StorageType compose(const GenImpl<Value, Source>& source) const {
1443     Optional<StorageType> accum;
1444     source | [&](Value v) {
1445       if (accum.hasValue()) {
1446         accum = reducer_(std::move(accum.value()), std::forward<Value>(v));
1447       } else {
1448         accum = std::forward<Value>(v);
1449       }
1450     };
1451     if (!accum.hasValue()) {
1452       throw EmptySequence();
1453     }
1454     return accum.value();
1455   }
1456 };
1457
1458 /**
1459  * Count - for simply counting the items in a collection.
1460  *
1461  * This type is usually used through its singleton, 'count':
1462  *
1463  *   auto shortPrimes = seq(1, 100) | filter(isPrime) | count;
1464  */
1465 class Count : public Operator<Count> {
1466  public:
1467   Count() = default;
1468
1469   template<class Source,
1470            class Value>
1471   size_t compose(const GenImpl<Value, Source>& source) const {
1472     static_assert(!Source::infinite, "Cannot count infinite source");
1473     return foldl(size_t(0),
1474                  [](size_t accum, Value v) {
1475                    return accum + 1;
1476                  }).compose(source);
1477   }
1478 };
1479
1480 /**
1481  * Sum - For simply summing up all the values from a source.
1482  *
1483  * This type is usually used through its singleton, 'sum':
1484  *
1485  *   auto gaussSum = seq(1, 100) | sum;
1486  */
1487 class Sum : public Operator<Sum> {
1488  public:
1489   Sum() : Operator<Sum>() {}
1490
1491   template<class Source,
1492            class Value,
1493            class StorageType = typename std::decay<Value>::type>
1494   StorageType compose(const GenImpl<Value, Source>& source) const {
1495     static_assert(!Source::infinite, "Cannot sum infinite source");
1496     return foldl(StorageType(0),
1497                  [](StorageType&& accum, Value v) {
1498                    return std::move(accum) + std::forward<Value>(v);
1499                  }).compose(source);
1500   }
1501 };
1502
1503 /**
1504  * Contains - For testing whether a value matching the given value is contained
1505  * in a sequence.
1506  *
1507  * This type should be used through the 'contains' helper method, like:
1508  *
1509  *   bool contained = seq(1, 10) | map(square) | contains(49);
1510  */
1511 template<class Needle>
1512 class Contains : public Operator<Contains<Needle>> {
1513   Needle needle_;
1514  public:
1515   explicit Contains(Needle needle)
1516     : needle_(std::move(needle))
1517   {}
1518
1519   template<class Source,
1520            class Value,
1521            class StorageType = typename std::decay<Value>::type>
1522   bool compose(const GenImpl<Value, Source>& source) const {
1523     static_assert(!Source::infinite,
1524                   "Calling contains on an infinite source might cause "
1525                   "an infinite loop.");
1526     return !(source | [this](Value value) {
1527         return !(needle_ == std::forward<Value>(value));
1528       });
1529   }
1530 };
1531
1532 /**
1533  * Min - For a value which minimizes a key, where the key is determined by a
1534  * given selector, and compared by given comparer.
1535  *
1536  * This type is usually used through the singletone 'min' or through the helper
1537  * functions 'minBy' and 'maxBy'.
1538  *
1539  *   auto oldest = from(people)
1540  *               | minBy([](Person& p) {
1541  *                   return p.dateOfBirth;
1542  *                 });
1543  */
1544 template<class Selector,
1545          class Comparer>
1546 class Min : public Operator<Min<Selector, Comparer>> {
1547   Selector selector_;
1548   Comparer comparer_;
1549  public:
1550   Min() = default;
1551
1552   explicit Min(Selector selector)
1553     : selector_(std::move(selector))
1554   {}
1555
1556   Min(Selector selector,
1557         Comparer comparer)
1558     : selector_(std::move(selector))
1559     , comparer_(std::move(comparer))
1560   {}
1561
1562   template<class Value,
1563            class Source,
1564            class StorageType = typename std::decay<Value>::type,
1565            class Key = typename std::decay<
1566                typename std::result_of<Selector(Value)>::type
1567              >::type>
1568   StorageType compose(const GenImpl<Value, Source>& source) const {
1569     Optional<StorageType> min;
1570     Optional<Key> minKey;
1571     source | [&](Value v) {
1572       Key key = selector_(std::forward<Value>(v));
1573       if (!minKey.hasValue() || comparer_(key, minKey.value())) {
1574         minKey = key;
1575         min = std::forward<Value>(v);
1576       }
1577     };
1578     if (!min.hasValue()) {
1579       throw EmptySequence();
1580     }
1581     return min.value();
1582   }
1583 };
1584
1585 /**
1586  * Append - For collecting values from a source into a given output container
1587  * by appending.
1588  *
1589  * This type is usually used through the helper function 'appendTo', like:
1590  *
1591  *   vector<int64_t> ids;
1592  *   from(results) | map([](Person& p) { return p.id })
1593  *                 | appendTo(ids);
1594  */
1595 template<class Collection>
1596 class Append : public Operator<Append<Collection>> {
1597   Collection* collection_;
1598  public:
1599   explicit Append(Collection* collection)
1600     : collection_(collection)
1601   {}
1602
1603   template<class Value,
1604            class Source>
1605   Collection& compose(const GenImpl<Value, Source>& source) const {
1606     source | [&](Value v) {
1607       collection_->insert(collection_->end(), std::forward<Value>(v));
1608     };
1609     return *collection_;
1610   }
1611 };
1612
1613 /**
1614  * Collect - For collecting values from a source in a collection of the desired
1615  * type.
1616  *
1617  * This type is usually used through the helper function 'as', like:
1618  *
1619  *   std::string upper = from(stringPiece)
1620  *                     | map(&toupper)
1621  *                     | as<std::string>();
1622  */
1623 template<class Collection>
1624 class Collect : public Operator<Collect<Collection>> {
1625  public:
1626   Collect() = default;
1627
1628   template<class Value,
1629            class Source,
1630            class StorageType = typename std::decay<Value>::type>
1631   Collection compose(const GenImpl<Value, Source>& source) const {
1632     Collection collection;
1633     source | [&](Value v) {
1634       collection.insert(collection.end(), std::forward<Value>(v));
1635     };
1636     return collection;
1637   }
1638 };
1639
1640
1641 /**
1642  * CollectTemplate - For collecting values from a source in a collection
1643  * constructed using the specified template type. Given the type of values
1644  * produced by the given generator, the collection type will be:
1645  *   Container<Value, Allocator<Value>>
1646  *
1647  * The allocator defaults to std::allocator, so this may be used for the STL
1648  * containers by simply using operators like 'as<set>', 'as<deque>',
1649  * 'as<vector>'. 'as', here is the helper method which is the usual means of
1650  * consturcting this operator.
1651  *
1652  * Example:
1653  *
1654  *   set<string> uniqueNames = from(names) | as<set>();
1655  */
1656 template<template<class, class> class Container,
1657          template<class> class Allocator>
1658 class CollectTemplate : public Operator<CollectTemplate<Container, Allocator>> {
1659  public:
1660   CollectTemplate() = default;
1661
1662   template<class Value,
1663            class Source,
1664            class StorageType = typename std::decay<Value>::type,
1665            class Collection = Container<StorageType, Allocator<StorageType>>>
1666   Collection compose(const GenImpl<Value, Source>& source) const {
1667     Collection collection;
1668     source | [&](Value v) {
1669       collection.insert(collection.end(), std::forward<Value>(v));
1670     };
1671     return collection;
1672   }
1673 };
1674
1675 /**
1676  * Concat - For flattening generators of generators.
1677  *
1678  * This type is usually used through the 'concat' static value, like:
1679  *
1680  *   auto edges =
1681  *       from(nodes)
1682  *     | map([](Node& x) {
1683  *           return from(x.neighbors)
1684  *                | map([&](Node& y) {
1685  *                    return Edge(x, y);
1686  *                  });
1687  *         })
1688  *     | concat
1689  *     | as<std::set>();
1690  */
1691 class Concat : public Operator<Concat> {
1692  public:
1693   Concat() = default;
1694
1695   template<class Inner,
1696            class Source,
1697            class InnerValue = typename std::decay<Inner>::type::ValueType>
1698   class Generator :
1699       public GenImpl<InnerValue, Generator<Inner, Source, InnerValue>> {
1700     Source source_;
1701    public:
1702     explicit Generator(Source source)
1703       : source_(std::move(source)) {}
1704
1705     template<class Handler>
1706     bool apply(Handler&& handler) const {
1707       return source_.apply([&](Inner inner) -> bool {
1708           return inner.apply(std::forward<Handler>(handler));
1709         });
1710     }
1711
1712     template<class Body>
1713     void foreach(Body&& body) const {
1714       source_.foreach([&](Inner inner) {
1715           inner.foreach(std::forward<Body>(body));
1716         });
1717     }
1718
1719     static constexpr bool infinite = Source::infinite;
1720   };
1721
1722   template<class Value,
1723            class Source,
1724            class Gen = Generator<Value, Source>>
1725   Gen compose(GenImpl<Value, Source>&& source) const {
1726     return Gen(std::move(source.self()));
1727   }
1728
1729   template<class Value,
1730            class Source,
1731            class Gen = Generator<Value, Source>>
1732   Gen compose(const GenImpl<Value, Source>& source) const {
1733     return Gen(source.self());
1734   }
1735 };
1736
1737 /**
1738  * RangeConcat - For flattening generators of iterables.
1739  *
1740  * This type is usually used through the 'rconcat' static value, like:
1741  *
1742  *   map<int, vector<int>> adjacency;
1743  *   auto sinks =
1744  *       from(adjacency)
1745  *     | get<1>()
1746  *     | rconcat()
1747  *     | as<std::set>();
1748  */
1749 class RangeConcat : public Operator<RangeConcat> {
1750  public:
1751   RangeConcat() = default;
1752
1753   template<class Range,
1754            class Source,
1755            class InnerValue = typename ValueTypeOfRange<Range>::RefType>
1756   class Generator
1757     : public GenImpl<InnerValue, Generator<Range, Source, InnerValue>> {
1758     Source source_;
1759    public:
1760     explicit Generator(Source source)
1761       : source_(std::move(source)) {}
1762
1763     template<class Body>
1764     void foreach(Body&& body) const {
1765       source_.foreach([&](Range range) {
1766           for (auto& value : range) {
1767             body(value);
1768           }
1769         });
1770     }
1771
1772     template<class Handler>
1773     bool apply(Handler&& handler) const {
1774       return source_.apply([&](Range range) -> bool {
1775           for (auto& value : range) {
1776             if (!handler(value)) {
1777               return false;
1778             }
1779           }
1780           return true;
1781         });
1782     }
1783   };
1784
1785   template<class Value,
1786            class Source,
1787            class Gen = Generator<Value, Source>>
1788   Gen compose(GenImpl<Value, Source>&& source) const {
1789     return Gen(std::move(source.self()));
1790   }
1791
1792   template<class Value,
1793            class Source,
1794            class Gen = Generator<Value, Source>>
1795   Gen compose(const GenImpl<Value, Source>& source) const {
1796     return Gen(source.self());
1797   }
1798 };
1799
1800
1801 /**
1802  * GuardImpl - For handling exceptions from downstream computation. Requires the
1803  * type of exception to catch, and handler function to invoke in the event of
1804  * the exception. Note that the handler may:
1805  *   1) return true to continue processing the sequence
1806  *   2) return false to end the sequence immediately
1807  *   3) throw, to pass the exception to the next catch
1808  * The handler must match the signature 'bool(Exception&, Value)'.
1809  *
1810  * This type is used through the `guard` helper, like so:
1811  *
1812  *  auto indexes
1813  *    = byLine(STDIN_FILENO)
1814  *    | guard<std::runtime_error>([](std::runtime_error& e,
1815  *                                   StringPiece sp) {
1816  *        LOG(ERROR) << sp << ": " << e.str();
1817  *        return true; // continue processing subsequent lines
1818  *      })
1819  *    | eachTo<int>()
1820  *    | as<vector>();
1821  *
1822  *  TODO(tjackson): Rename this back to Guard.
1823  **/
1824 template<class Exception,
1825          class ErrorHandler>
1826 class GuardImpl : public Operator<GuardImpl<Exception, ErrorHandler>> {
1827   ErrorHandler handler_;
1828  public:
1829   explicit GuardImpl(ErrorHandler handler) : handler_(std::move(handler)) {}
1830
1831   template<class Value,
1832            class Source>
1833   class Generator : public GenImpl<Value, Generator<Value, Source>> {
1834     Source source_;
1835     ErrorHandler handler_;
1836   public:
1837     explicit Generator(Source source,
1838                        ErrorHandler handler)
1839       : source_(std::move(source)),
1840         handler_(std::move(handler)) {}
1841
1842     template<class Handler>
1843     bool apply(Handler&& handler) const {
1844       return source_.apply([&](Value value) -> bool {
1845         try {
1846           handler(std::forward<Value>(value));
1847           return true;
1848         } catch (Exception& e) {
1849           return handler_(e, std::forward<Value>(value));
1850         }
1851       });
1852     }
1853
1854     static constexpr bool infinite = Source::infinite;
1855   };
1856
1857   template<class Value,
1858            class Source,
1859            class Gen = Generator<Value, Source>>
1860   Gen compose(GenImpl<Value, Source>&& source) const {
1861     return Gen(std::move(source.self()), handler_);
1862   }
1863
1864   template<class Value,
1865            class Source,
1866            class Gen = Generator<Value, Source>>
1867   Gen compose(const GenImpl<Value, Source>& source) const {
1868     return Gen(source.self(), handler_);
1869   }
1870 };
1871
1872 /**
1873  * Cycle - For repeating a sequence forever.
1874  *
1875  * This type is usually used through the 'cycle' static value, like:
1876  *
1877  *   auto tests
1878  *     = from(samples)
1879  *     | cycle
1880  *     | take(100);
1881  */
1882 class Cycle : public Operator<Cycle> {
1883   off_t limit_; // -1 for infinite
1884  public:
1885   Cycle()
1886     : limit_(-1) { }
1887
1888   explicit Cycle(off_t limit)
1889     : limit_(limit) { }
1890
1891   template<class Value,
1892            class Source>
1893   class Generator : public GenImpl<Value, Generator<Value, Source>> {
1894     Source source_;
1895     off_t limit_; // -1 for infinite
1896   public:
1897     explicit Generator(Source source, off_t limit)
1898       : source_(std::move(source))
1899       , limit_(limit) {}
1900
1901     template<class Handler>
1902     bool apply(Handler&& handler) const {
1903       bool cont;
1904       auto handler2 = [&](Value value) {
1905         cont = handler(std::forward<Value>(value));
1906         return cont;
1907       };
1908       for (off_t count = 0; count != limit_; ++count) {
1909         cont = false;
1910         source_.apply(handler2);
1911         if (!cont) {
1912           return false;
1913         }
1914       }
1915       return true;
1916     }
1917
1918     // not actually infinite, since an empty generator will end the cycles.
1919     static constexpr bool infinite = Source::infinite;
1920   };
1921
1922   template<class Source,
1923            class Value,
1924            class Gen = Generator<Value, Source>>
1925   Gen compose(GenImpl<Value, Source>&& source) const {
1926     return Gen(std::move(source.self()), limit_);
1927   }
1928
1929   template<class Source,
1930            class Value,
1931            class Gen = Generator<Value, Source>>
1932   Gen compose(const GenImpl<Value, Source>& source) const {
1933     return Gen(source.self(), limit_);
1934   }
1935
1936   /**
1937    * Convenience function for use like:
1938    *
1939    *  auto tripled = gen | cycle(3);
1940    */
1941   Cycle operator()(off_t limit) const {
1942     return Cycle(limit);
1943   }
1944 };
1945
1946 /**
1947  * Dereference - For dereferencing a sequence of pointers while filtering out
1948  * null pointers.
1949  *
1950  * This type is usually used through the 'dereference' static value, like:
1951  *
1952  *   auto refs = from(ptrs) | dereference;
1953  */
1954 class Dereference : public Operator<Dereference> {
1955  public:
1956   Dereference() = default;
1957
1958   template<class Value,
1959            class Source,
1960            class Result = decltype(*std::declval<Value>())>
1961   class Generator : public GenImpl<Result, Generator<Value, Source, Result>> {
1962     Source source_;
1963   public:
1964     explicit Generator(Source source)
1965       : source_(std::move(source)) {}
1966
1967     template<class Body>
1968     void foreach(Body&& body) const {
1969       source_.foreach([&](Value value) {
1970         if (value) {
1971           return body(*value);
1972         }
1973       });
1974     }
1975
1976     template<class Handler>
1977     bool apply(Handler&& handler) const {
1978       return source_.apply([&](Value value) -> bool {
1979         if (value) {
1980           return handler(*value);
1981         }
1982         return true;
1983       });
1984     }
1985
1986     // not actually infinite, since an empty generator will end the cycles.
1987     static constexpr bool infinite = Source::infinite;
1988   };
1989
1990   template<class Source,
1991            class Value,
1992            class Gen = Generator<Value, Source>>
1993   Gen compose(GenImpl<Value, Source>&& source) const {
1994     return Gen(std::move(source.self()));
1995   }
1996
1997   template<class Source,
1998            class Value,
1999            class Gen = Generator<Value, Source>>
2000   Gen compose(const GenImpl<Value, Source>& source) const {
2001     return Gen(source.self());
2002   }
2003 };
2004
2005 /**
2006  * Indirect - For producing a sequence of the addresses of the values in the
2007  * input.
2008  *
2009  * This type is usually used through the 'indirect' static value, like:
2010  *
2011  *   auto ptrs = from(refs) | indirect;
2012  */
2013 class Indirect : public Operator<Indirect> {
2014  public:
2015   Indirect() = default;
2016
2017   template <class Value,
2018             class Source,
2019             class Result = typename std::remove_reference<Value>::type*>
2020   class Generator : public GenImpl<Result, Generator<Value, Source, Result>> {
2021     Source source_;
2022     static_assert(!std::is_rvalue_reference<Value>::value,
2023                   "Cannot use indirect on an rvalue");
2024
2025    public:
2026     explicit Generator(Source source) : source_(std::move(source)) {}
2027
2028     template <class Body>
2029     void foreach(Body&& body) const {
2030       source_.foreach([&](Value value) {
2031         return body(&value);
2032       });
2033     }
2034
2035     template <class Handler>
2036     bool apply(Handler&& handler) const {
2037       return source_.apply([&](Value value) -> bool {
2038         return handler(&value);
2039       });
2040     }
2041
2042     // not actually infinite, since an empty generator will end the cycles.
2043     static constexpr bool infinite = Source::infinite;
2044   };
2045
2046   template <class Source, class Value, class Gen = Generator<Value, Source>>
2047   Gen compose(GenImpl<Value, Source>&& source) const {
2048     return Gen(std::move(source.self()));
2049   }
2050
2051   template <class Source, class Value, class Gen = Generator<Value, Source>>
2052   Gen compose(const GenImpl<Value, Source>& source) const {
2053     return Gen(source.self());
2054   }
2055 };
2056
2057 } //::detail
2058
2059 /**
2060  * VirtualGen<T> - For wrapping template types in simple polymorphic wrapper.
2061  **/
2062 template<class Value>
2063 class VirtualGen : public GenImpl<Value, VirtualGen<Value>> {
2064   class WrapperBase {
2065    public:
2066     virtual ~WrapperBase() noexcept {}
2067     virtual bool apply(const std::function<bool(Value)>& handler) const = 0;
2068     virtual void foreach(const std::function<void(Value)>& body) const = 0;
2069     virtual std::unique_ptr<const WrapperBase> clone() const = 0;
2070   };
2071
2072   template<class Wrapped>
2073   class WrapperImpl : public WrapperBase {
2074     Wrapped wrapped_;
2075    public:
2076     explicit WrapperImpl(Wrapped wrapped)
2077      : wrapped_(std::move(wrapped)) {
2078     }
2079
2080     virtual bool apply(const std::function<bool(Value)>& handler) const {
2081       return wrapped_.apply(handler);
2082     }
2083
2084     virtual void foreach(const std::function<void(Value)>& body) const {
2085       wrapped_.foreach(body);
2086     }
2087
2088     virtual std::unique_ptr<const WrapperBase> clone() const {
2089       return std::unique_ptr<const WrapperBase>(new WrapperImpl(wrapped_));
2090     }
2091   };
2092
2093   std::unique_ptr<const WrapperBase> wrapper_;
2094
2095  public:
2096   template <class Self>
2097   /* implicit */ VirtualGen(Self source)
2098       : wrapper_(new WrapperImpl<Self>(std::move(source))) {}
2099
2100   VirtualGen(VirtualGen&& source) noexcept
2101       : wrapper_(std::move(source.wrapper_)) {}
2102
2103   VirtualGen(const VirtualGen& source)
2104       : wrapper_(source.wrapper_->clone()) {}
2105
2106   VirtualGen& operator=(const VirtualGen& source) {
2107     wrapper_.reset(source.wrapper_->clone());
2108     return *this;
2109   }
2110
2111   VirtualGen& operator=(VirtualGen&& source) noexcept {
2112     wrapper_= std::move(source.wrapper_);
2113     return *this;
2114   }
2115
2116   bool apply(const std::function<bool(Value)>& handler) const {
2117     return wrapper_->apply(handler);
2118   }
2119
2120   void foreach(const std::function<void(Value)>& body) const {
2121     wrapper_->foreach(body);
2122   }
2123 };
2124
2125 /**
2126  * non-template operators, statically defined to avoid the need for anything but
2127  * the header.
2128  */
2129 static const detail::Sum sum{};
2130
2131 static const detail::Count count{};
2132
2133 static const detail::First first{};
2134
2135 /**
2136  * Use directly for detecting any values, or as a function to detect values
2137  * which pass a predicate:
2138  *
2139  *  auto nonempty = g | any;
2140  *  auto evens = g | any(even);
2141  */
2142 static const detail::Any any{};
2143
2144 static const detail::Min<Identity, Less> min{};
2145
2146 static const detail::Min<Identity, Greater> max{};
2147
2148 static const detail::Order<Identity> order{};
2149
2150 static const detail::Distinct<Identity> distinct{};
2151
2152 static const detail::Map<Move> move{};
2153
2154 static const detail::Concat concat{};
2155
2156 static const detail::RangeConcat rconcat{};
2157
2158 /**
2159  * Use directly for infinite sequences, or as a function to limit cycle count.
2160  *
2161  *  auto forever = g | cycle;
2162  *  auto thrice = g | cycle(3);
2163  */
2164 static const detail::Cycle cycle{};
2165
2166 static const detail::Dereference dereference{};
2167
2168 static const detail::Indirect indirect{};
2169
2170 inline detail::Take take(size_t count) {
2171   return detail::Take(count);
2172 }
2173
2174 inline detail::Stride stride(size_t s) {
2175   return detail::Stride(s);
2176 }
2177
2178 template<class Random = std::default_random_engine>
2179 inline detail::Sample<Random> sample(size_t count, Random rng = Random()) {
2180   return detail::Sample<Random>(count, std::move(rng));
2181 }
2182
2183 inline detail::Skip skip(size_t count) {
2184   return detail::Skip(count);
2185 }
2186
2187 inline detail::Batch batch(size_t batchSize) {
2188   return detail::Batch(batchSize);
2189 }
2190
2191 }} //folly::gen
2192
2193 #pragma GCC diagnostic pop