Thrill  0.1
function_stack.hpp
Go to the documentation of this file.
1 /*******************************************************************************
2  * tlx/meta/function_stack.hpp
3  *
4  * A FunctionStack stores a sequence of lambdas or functors which _emit_ items
5  * to the next stage. Each lambda/functor is called with (item, emit) where emit
6  * is the chain of subsequent functors. This "push-down items" method is used by
7  * Thrill to enable expanding of one item to many in FlatMap().
8  *
9  * Given functors f_1, f_2, ... f_n, the FunctionStack calls f_1(x, f_2), for x,
10  * and f_1 calls f_2(y, f_3) for each y it emits.
11  *
12  * Part of tlx - http://panthema.net/tlx
13  *
14  * Copyright (C) 2015 Sebastian Lamm <[email protected]>
15  * Copyright (C) 2015-2017 Timo Bingmann <[email protected]>
16  *
17  * All rights reserved. Published under the Boost Software License, Version 1.0
18  ******************************************************************************/
19 
20 #ifndef TLX_META_FUNCTION_STACK_HEADER
21 #define TLX_META_FUNCTION_STACK_HEADER
22 
24 
25 #include <tuple>
26 
27 namespace tlx {
28 
29 //! \addtogroup tlx_meta
30 //! \{
31 
32 namespace meta_detail {
33 
34 /*!
35  * Base case for the chaining of functors. The last functor receives an input
36  * element, no emitter and should have no return type. It should therefore
37  * store the input parameter externally.
38  *
39  * \param functor Functor that represents the chain end.
40  */
41 template <typename Functor>
42 auto call_stack(const Functor& functor) {
43  // the functor object is captured by non-const copy so that we can use
44  // functors with non-const operator(), i.e. stateful functors (e.g. for
45  // sampling)
46  return [=, functor = functor](const auto& input) mutable -> void {
47  functor(input);
48  };
49 }
50 
51 /*!
52  * Recursive case for the chaining of functors. The given functor receives an
53  * input element, an emitter and should have no return type. The emitter will
54  * be built using the chain of remaining functors.
55  *
56  * \param functor Current functor to be chained.
57  *
58  * \param rest Remaining functors.
59  */
60 template <typename Functor, typename... MoreFunctors>
61 auto call_stack(const Functor& functor, const MoreFunctors& ... rest) {
62  // the functor object is captured by non-const copy so that we can use
63  // functors with non-const operator(), i.e. stateful functors (e.g. for
64  // sampling)
65  return [=, functor = functor](const auto& input) mutable -> void {
66  functor(input, call_stack(rest...));
67  };
68 }
69 
70 } // namespace meta_detail
71 
72 /*!
73  * A FunctionStack is a chain of functor that can be folded to a single functor
74  * (which is usually optimize by the compiler).
75  *
76  * All functors within the chain receive a single input value and a emitter
77  * function. The emitter function is used for chaining functors together by
78  * enabling items to pushed down the sequence. The single exception to this is
79  * the last functor, which receives no emitter, and hence usually stores the
80  * items somehow.
81  *
82  * The FunctionStack basically consists of a tuple that contains functor objects
83  * of varying types.
84  *
85  * \tparam Input_ Input to first functor.
86  *
87  * \tparam Functors Types of the different functor.
88  */
89 template <typename Input_, typename... Functors>
91 {
92 public:
93  using Input = Input_;
94 
95  //! Construct an empty FunctionStack
96  FunctionStack() = default;
97 
98  /*!
99  * Initialize the function stack with a given tuple of functors.
100  *
101  * \param stack Tuple of functor.
102  */
103  explicit FunctionStack(const std::tuple<Functors...>& stack)
104  : stack_(stack) { }
105 
106  /*!
107  * Add a functor function to the end of the stack.
108  *
109  * \tparam Functor Type of the functor.
110  *
111  * \param functor Functor that should be added to the stack.
112  *
113  * \return New stack containing the previous and new functor(s).
114  */
115  template <typename Functor>
116  auto push(const Functor& functor) const {
117  // append to function stack's type the new function.
118  return FunctionStack<Input, Functors..., Functor>(
119  std::tuple_cat(stack_, std::make_tuple(functor)));
120  }
121 
122  /*!
123  * Add a functor to the end of the stack. Alias for push().
124  *
125  * \tparam Functor Type of the functors.
126  *
127  * \param functor functor that should be added to the stack.
128  *
129  * \return New stack containing the previous and new functor(s).
130  */
131  template <typename Functor>
132  auto operator & (const Functor& functor) const { return push(functor); }
133 
134  /*!
135  * Build a single functor by "folding" the stack. Folding means that the
136  * stack is processed from front to back and each emitter is composed using
137  * previous functors.
138  *
139  * \return Single "folded" functor representing the whole stack.
140  */
141  auto fold() const {
142  return fold_stack(make_index_sequence<sizeof ... (Functors)>{ });
143  }
144 
145  //! Is true if the FunctionStack is empty.
146  static constexpr bool empty = (sizeof ... (Functors) == 0);
147 
148  //! Number of functors on the FunctionStack
149  static constexpr size_t size = sizeof ... (Functors);
150 
151 private:
152  //! Tuple of varying type that stores all functor objects functions.
153  std::tuple<Functors...> stack_;
154 
155  /*!
156  * Auxilary function for "folding" the stack. This is needed to send all
157  * functors as parameters to the function that folds them together.
158  *
159  * \return Single "folded" functor representing the stack.
160  */
161  template <size_t... Is>
163  return meta_detail::call_stack(std::get<Is>(stack_) ...);
164  }
165 };
166 
167 //! Function-style construction of a FunctionStack
168 template <typename Input, typename Functor>
169 static inline
170 auto make_function_stack(const Functor& functor) {
171  return FunctionStack<Input, Functor>(std::make_tuple(functor));
172 }
173 
174 //! \}
175 
176 } // namespace tlx
177 
178 #endif // !TLX_META_FUNCTION_STACK_HEADER
179 
180 /******************************************************************************/
auto push(const Functor &functor) const
Add a functor function to the end of the stack.
auto call_stack(const Functor &functor)
Base case for the chaining of functors.
A FunctionStack is a chain of functor that can be folded to a single functor (which is usually optimi...
static auto make_function_stack(const Functor &functor)
Function-style construction of a FunctionStack.
std::tuple< Functors... > stack_
Tuple of varying type that stores all functor objects functions.
auto fold_stack(index_sequence< Is... >) const
Auxilary function for "folding" the stack.
auto fold() const
Build a single functor by "folding" the stack.
FunctionStack(const std::tuple< Functors... > &stack)
Initialize the function stack with a given tuple of functors.