folly/experimental/Gen.h

   1 /*
   2  * Copyright 2013 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 #pragma once
  18
  19 #include <functional>
  20 #include <memory>
  21 #include <type_traits>
  22 #include <utility>
  23 #include <algorithm>
  24 #include <random>
  25 #include <vector>
  26 #include <unordered_set>
  27
  28 #include "folly/Range.h"
  29 #include "folly/Optional.h"
  30 #include "folly/Conv.h"
  31
  32 /**
  33  * Generator-based Sequence Comprehensions in C++, akin to C#'s LINQ
  34  * @author Tom Jackson <tjackson@fb.com>
  35  *
  36  * This library makes it possible to write declarative comprehensions for
  37  * processing sequences of values efficiently in C++. The operators should be
  38  * familiar to those with experience in functional programming, and the
  39  * performance will be virtually identical to the equivalent, boilerplate C++
  40  * implementations.
  41  *
  42  * Generator objects may be created from either an stl-like container (anything
  43  * supporting begin() and end()), from sequences of values, or from another
  44  * generator (see below). To create a generator that pulls values from a vector,
  45  * for example, one could write:
  46  *
  47  *   vector<string> names { "Jack", "Jill", "Sara", "Tom" };
  48  *   auto gen = from(names);
  49  *
  50  * Generators are composed by building new generators out of old ones through
  51  * the use of operators. These are reminicent of shell pipelines, and afford
  52  * similar composition. Lambda functions are used liberally to describe how to
  53  * handle individual values:
  54  *
  55  *   auto lengths = gen
  56  *                | mapped([](const fbstring& name) { return name.size(); });
  57  *
  58  * Generators are lazy; they don't actually perform any work until they need to.
  59  * As an example, the 'lengths' generator (above) won't actually invoke the
  60  * provided lambda until values are needed:
  61  *
  62  *   auto lengthVector = lengths | as<std::vector>();
  63  *   auto totalLength = lengths | sum;
  64  *
  65  * 'auto' is useful in here because the actual types of the generators objects
  66  * are usually complicated and implementation-sensitive.
  67  *
  68  * If a simpler type is desired (for returning, as an example), VirtualGen<T>
  69  * may be used to wrap the generator in a polymorphic wrapper:
  70  *
  71  *  VirtualGen<float> powersOfE() {
  72  *    return seq(1) | mapped(&expf);
  73  *  }
  74  *
  75  * To learn more about this library, including the use of infinite generators,
  76  * see the examples in the comments, or the docs (coming soon).
  77 */
  78
  79 namespace folly { namespace gen {
  80
  81 template<class Value, class Self>
  82 class GenImpl;
  83
  84 template<class Self>
  85 class Operator;
  86
  87 class EmptySequence : public std::exception {
  88 public:
  89   virtual const char* what() const noexcept {
  90     return "This operation cannot be called on an empty sequence";
  91   }
  92 };
  93
  94 class Less {
  95 public:
  96   template<class First,
  97            class Second>
  98   auto operator()(const First& first, const Second& second) const ->
  99   decltype(first < second) {
 100     return first < second;
 101   }
 102 };
 103
 104 class Greater {
 105 public:
 106   template<class First,
 107            class Second>
 108   auto operator()(const First& first, const Second& second) const ->
 109   decltype(first > second) {
 110     return first > second;
 111   }
 112 };
 113
 114 template<int n>
 115 class Get {
 116 public:
 117   template<class Value>
 118   auto operator()(Value&& value) const ->
 119   decltype(std::get<n>(std::forward<Value>(value))) {
 120     return std::get<n>(std::forward<Value>(value));
 121   }
 122 };
 123
 124 class Move {
 125 public:
 126   template<class Value>
 127   auto operator()(Value&& value) const ->
 128   decltype(std::move(std::forward<Value>(value))) {
 129     return std::move(std::forward<Value>(value));
 130   }
 131 };
 132
 133 class Identity {
 134 public:
 135   template<class Value>
 136   auto operator()(Value&& value) const ->
 137   decltype(std::forward<Value>(value)) {
 138     return std::forward<Value>(value);
 139   }
 140 };
 141
 142 template <class Dest>
 143 class Cast {
 144  public:
 145   template <class Value>
 146   Dest operator()(Value&& value) const {
 147     return Dest(std::forward<Value>(value));
 148   }
 149 };
 150
 151 template <class Dest>
 152 class To {
 153  public:
 154   template <class Value>
 155   Dest operator()(Value&& value) const {
 156     return ::folly::to<Dest>(std::forward<Value>(value));
 157   }
 158 };
 159
 160 namespace detail {
 161
 162 template<class Self>
 163 struct FBounded;
 164
 165 /*
 166  * Type Traits
 167  */
 168 template<class Container>
 169 struct ValueTypeOfRange {
 170  private:
 171   static Container container_;
 172  public:
 173   typedef decltype(*std::begin(container_))
 174     RefType;
 175   typedef typename std::decay<decltype(*std::begin(container_))>::type
 176     StorageType;
 177 };
 178
 179
 180 /*
 181  * Sources
 182  */
 183 template<class Container,
 184          class Value = typename ValueTypeOfRange<Container>::RefType>
 185 class ReferencedSource;
 186
 187 template<class Value,
 188          class Container = std::vector<typename std::decay<Value>::type>>
 189 class CopiedSource;
 190
 191 template<class Value, bool endless = false, bool endInclusive = false>
 192 class Sequence;
 193
 194 template<class Value, class First, class Second>
 195 class Chain;
 196
 197 template<class Value, class Source>
 198 class Yield;
 199
 200 /*
 201  * Operators
 202  */
 203 template<class Predicate>
 204 class Map;
 205
 206 template<class Predicate>
 207 class Filter;
 208
 209 template<class Predicate>
 210 class Until;
 211
 212 class Take;
 213
 214 template<class Rand>
 215 class Sample;
 216
 217 class Skip;
 218
 219 template<class Selector, class Comparer = Less>
 220 class Order;
 221
 222 template<class Selector>
 223 class Distinct;
 224
 225 template<class First, class Second>
 226 class Composed;
 227
 228 /*
 229  * Sinks
 230  */
 231 template<class Seed,
 232          class Fold>
 233 class FoldLeft;
 234
 235 class First;
 236
 237 class Any;
 238
 239 template<class Predicate>
 240 class All;
 241
 242 template<class Reducer>
 243 class Reduce;
 244
 245 class Sum;
 246
 247 template<class Selector,
 248          class Comparer>
 249 class Min;
 250
 251 template<class Container>
 252 class Collect;
 253
 254 template<template<class, class> class Collection = std::vector,
 255          template<class> class Allocator = std::allocator>
 256 class CollectTemplate;
 257
 258 template<class Collection>
 259 class Append;
 260
 261 template<class Value>
 262 struct GeneratorBuilder;
 263
 264 template<class Needle>
 265 class Contains;
 266
 267 }
 268
 269 /**
 270  * Polymorphic wrapper
 271  **/
 272 template<class Value>
 273 class VirtualGen;
 274
 275 /*
 276  * Source Factories
 277  */
 278 template<class Container,
 279          class From = detail::ReferencedSource<const Container>>
 280 From fromConst(const Container& source) {
 281   return From(&source);
 282 }
 283
 284 template<class Container,
 285          class From = detail::ReferencedSource<Container>>
 286 From from(Container& source) {
 287   return From(&source);
 288 }
 289
 290 template<class Container,
 291          class Value =
 292            typename detail::ValueTypeOfRange<Container>::StorageType,
 293          class CopyOf = detail::CopiedSource<Value>>
 294 CopyOf fromCopy(Container&& source) {
 295   return CopyOf(std::forward<Container>(source));
 296 }
 297
 298 template<class Value,
 299          class From = detail::CopiedSource<Value>>
 300 From from(std::initializer_list<Value> source) {
 301   return From(source);
 302 }
 303
 304 template<class Container,
 305          class From = detail::CopiedSource<typename Container::value_type,
 306                                            Container>>
 307 From from(Container&& source) {
 308   return From(std::move(source));
 309 }
 310
 311 template<class Value, class Gen = detail::Sequence<Value, false, false>>
 312 Gen range(Value begin, Value end) {
 313   return Gen(begin, end);
 314 }
 315
 316 template<class Value,
 317          class Gen = detail::Sequence<Value, false, true>>
 318 Gen seq(Value first, Value last) {
 319   return Gen(first, last);
 320 }
 321
 322 template<class Value,
 323          class Gen = detail::Sequence<Value, true>>
 324 Gen seq(Value begin) {
 325   return Gen(begin);
 326 }
 327
 328 template<class Value,
 329          class Source,
 330          class Yield = detail::Yield<Value, Source>>
 331 Yield generator(Source&& source) {
 332   return Yield(std::forward<Source>(source));
 333 }
 334
 335 /*
 336  * Create inline generator, used like:
 337  *
 338  * auto gen = GENERATOR(int) { yield(1); yield(2); };
 339  */
 340 #define GENERATOR(TYPE)                            \
 341   ::folly::gen::detail::GeneratorBuilder<TYPE>() + \
 342    [=](const std::function<void(TYPE)>& yield)
 343
 344 /*
 345  * Operator Factories
 346  */
 347 template<class Predicate,
 348          class Map = detail::Map<Predicate>>
 349 Map mapped(Predicate pred = Predicate()) {
 350   return Map(std::move(pred));
 351 }
 352
 353 template<class Predicate,
 354          class Map = detail::Map<Predicate>>
 355 Map map(Predicate pred = Predicate()) {
 356   return Map(std::move(pred));
 357 }
 358
 359 template<class Predicate,
 360          class Filter = detail::Filter<Predicate>>
 361 Filter filter(Predicate pred = Predicate()) {
 362   return Filter(std::move(pred));
 363 }
 364
 365 template<class Predicate,
 366          class All = detail::All<Predicate>>
 367 All all(Predicate pred = Predicate()) {
 368   return All(std::move(pred));
 369 }
 370
 371 template<class Predicate,
 372          class Until = detail::Until<Predicate>>
 373 Until until(Predicate pred = Predicate()) {
 374   return Until(std::move(pred));
 375 }
 376
 377 template<class Selector,
 378          class Comparer = Less,
 379          class Order = detail::Order<Selector, Comparer>>
 380 Order orderBy(Selector selector = Identity(),
 381               Comparer comparer = Comparer()) {
 382   return Order(std::move(selector),
 383                std::move(comparer));
 384 }
 385
 386 template<class Selector,
 387          class Order = detail::Order<Selector, Greater>>
 388 Order orderByDescending(Selector selector = Identity()) {
 389   return Order(std::move(selector));
 390 }
 391
 392 template<class Selector,
 393          class Distinct = detail::Distinct<Selector>>
 394 Distinct distinctBy(Selector selector = Identity()) {
 395   return Distinct(std::move(selector));
 396 }
 397
 398 template<int n,
 399          class Get = detail::Map<Get<n>>>
 400 Get get() {
 401   return Get();
 402 }
 403
 404 // construct Dest from each value
 405 template <class Dest,
 406           class Cast = detail::Map<Cast<Dest>>>
 407 Cast eachAs() {
 408   return Cast();
 409 }
 410
 411 // call folly::to on each value
 412 template <class Dest,
 413           class To = detail::Map<To<Dest>>>
 414 To eachTo() {
 415   return To();
 416 }
 417
 418 /*
 419  * Sink Factories
 420  */
 421 template<class Seed,
 422          class Fold,
 423          class FoldLeft = detail::FoldLeft<Seed, Fold>>
 424 FoldLeft foldl(Seed seed = Seed(),
 425                Fold fold = Fold()) {
 426   return FoldLeft(std::move(seed),
 427                   std::move(fold));
 428 }
 429
 430 template<class Reducer,
 431          class Reduce = detail::Reduce<Reducer>>
 432 Reduce reduce(Reducer reducer = Reducer()) {
 433   return Reduce(std::move(reducer));
 434 }
 435
 436 template<class Selector = Identity,
 437          class Min = detail::Min<Selector, Less>>
 438 Min minBy(Selector selector = Selector()) {
 439   return Min(std::move(selector));
 440 }
 441
 442 template<class Selector,
 443          class MaxBy = detail::Min<Selector, Greater>>
 444 MaxBy maxBy(Selector selector = Selector()) {
 445   return MaxBy(std::move(selector));
 446 }
 447
 448 template<class Collection,
 449          class Collect = detail::Collect<Collection>>
 450 Collect as() {
 451   return Collect();
 452 }
 453
 454 template<template<class, class> class Container = std::vector,
 455          template<class> class Allocator = std::allocator,
 456          class Collect = detail::CollectTemplate<Container, Allocator>>
 457 Collect as() {
 458   return Collect();
 459 }
 460
 461 template<class Collection,
 462          class Append = detail::Append<Collection>>
 463 Append appendTo(Collection& collection) {
 464   return Append(&collection);
 465 }
 466
 467 template<class Needle,
 468          class Contains = detail::Contains<typename std::decay<Needle>::type>>
 469 Contains contains(Needle&& needle) {
 470   return Contains(std::forward<Needle>(needle));
 471 }
 472
 473 }} // folly::gen
 474
 475 #include "folly/experimental/Gen-inl.h"