1 // Copyright (c) 2014 Grant Mercer 2 // Copyright (c) 2017 Hartmut Kaiser 3 // 4 // Distributed under the Boost Software License, Version 1.0. (See accompanying 5 // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) 6 7 /// \file parallel/algorithms/generate.hpp 8 9 #if !defined(HPX_PARALLEL_DETAIL_GENERATE_JULY_15_2014_0224PM) 10 #define HPX_PARALLEL_DETAIL_GENERATE_JULY_15_2014_0224PM 11 12 #include <hpx/config.hpp> 13 #include <hpx/traits/concepts.hpp> 14 #include <hpx/traits/is_iterator.hpp> 15 #include <hpx/traits/segmented_iterator_traits.hpp> 16 17 #include <hpx/parallel/algorithms/detail/dispatch.hpp> 18 #include <hpx/parallel/algorithms/detail/is_negative.hpp> 19 #include <hpx/parallel/algorithms/for_each.hpp> 20 #include <hpx/parallel/execution_policy.hpp> 21 #include <hpx/parallel/util/detail/algorithm_result.hpp> 22 #include <hpx/parallel/util/projection_identity.hpp> 23 24 #include <algorithm> 25 #include <cstddef> 26 #include <iterator> 27 #include <type_traits> 28 #include <utility> 29 30 namespace hpx { namespace parallel { inline namespace v1 31 { 32 /////////////////////////////////////////////////////////////////////////// 33 // generate 34 namespace detail 35 { 36 /// \cond NOINTERNAL 37 template <typename Iter> 38 struct generate : public detail::algorithm<generate<Iter>, Iter> 39 { generatehpx::parallel::v1::detail::generate40 generate() 41 : generate::algorithm("generate") 42 {} 43 44 template <typename ExPolicy, typename InIter, typename F> 45 static InIter sequentialhpx::parallel::v1::detail::generate46 sequential(ExPolicy, InIter first, InIter last, F && f) 47 { 48 std::generate(first, last, std::forward<F>(f)); 49 return last; 50 } 51 52 template <typename ExPolicy, typename FwdIter, typename F> 53 static typename util::detail::algorithm_result<ExPolicy, FwdIter>::type parallelhpx::parallel::v1::detail::generate54 parallel(ExPolicy && policy, FwdIter first, FwdIter last, F && f) 55 { 56 typedef typename std::iterator_traits<FwdIter>::value_type type; 57 58 return for_each_n<FwdIter>().call( 59 std::forward<ExPolicy>(policy), std::false_type(), 60 first, std::distance(first, last), 61 [HPX_CAPTURE_FORWARD(f)](type& v) mutable 62 { 63 v = f(); 64 }, 65 util::projection_identity()); 66 } 67 }; 68 69 /////////////////////////////////////////////////////////////////////// 70 // non-segmented implementation 71 template <typename ExPolicy, typename FwdIter, typename F> 72 inline typename util::detail::algorithm_result<ExPolicy, FwdIter>::type generate_(ExPolicy && policy,FwdIter first,FwdIter last,F && f,std::false_type)73 generate_(ExPolicy && policy, FwdIter first, FwdIter last, F && f, 74 std::false_type) 75 { 76 typedef parallel::execution::is_sequenced_execution_policy< 77 ExPolicy 78 > is_seq; 79 80 return detail::generate<FwdIter>().call( 81 std::forward<ExPolicy>(policy), is_seq(), 82 first, last, std::forward<F>(f)); 83 } 84 85 /////////////////////////////////////////////////////////////////////// 86 // segmented implementation 87 template <typename ExPolicy, typename FwdIter, typename F> 88 inline typename util::detail::algorithm_result<ExPolicy, FwdIter>::type 89 generate_(ExPolicy && policy, FwdIter first, FwdIter last, F && f, 90 std::true_type); 91 92 /// \endcond 93 } 94 95 /// Assign each element in range [first, last) a value generated by the 96 /// given function object f 97 /// 98 /// \note Complexity: Exactly \a distance(first, last) 99 /// invocations of \a f and assignments. 100 /// 101 /// \tparam ExPolicy The type of the execution policy to use (deduced). 102 /// It describes the manner in which the execution 103 /// of the algorithm may be parallelized and the manner 104 /// in which it executes the assignments. 105 /// \tparam FwdIter The type of the source iterators used (deduced). 106 /// This iterator type must meet the requirements of a 107 /// forward iterator. 108 /// \tparam F The type of the function/function object to use 109 /// (deduced). Unlike its sequential form, the parallel 110 /// overload of \a equal requires \a F to meet the 111 /// requirements of \a CopyConstructible. 112 /// 113 /// \param policy The execution policy to use for the scheduling of 114 /// the iterations. 115 /// \param first Refers to the beginning of the sequence of elements 116 /// the algorithm will be applied to. 117 /// \param last Refers to the end of the sequence of elements the 118 /// algorithm will be applied to. 119 /// \param f generator function that will be called. signature of 120 /// function should be equivalent to the following: 121 /// \code 122 /// Ret fun(); 123 /// \endcode \n 124 /// The type \a Ret must be such that an object of type 125 /// \a FwdIter can be dereferenced and assigned a value 126 /// of type \a Ret. 127 /// 128 /// The assignments in the parallel \a generate algorithm invoked with an 129 /// execution policy object of type \a sequenced_policy 130 /// execute in sequential order in the calling thread. 131 /// 132 /// The assignments in the parallel \a generate algorithm invoked with 133 /// an execution policy object of type \a parallel_policy or 134 /// \a parallel_task_policy are permitted to execute in an unordered 135 /// fashion in unspecified threads, and indeterminately sequenced 136 /// within each thread. 137 /// 138 /// \returns The \a replace_if algorithm returns a \a hpx::future<FwdIter> 139 /// if the execution policy is of type 140 /// \a sequenced_task_policy or 141 /// \a parallel_task_policy 142 /// and returns \a FwdIter otherwise. 143 /// It returns \a last. 144 /// 145 template <typename ExPolicy, typename FwdIter, typename F, 146 HPX_CONCEPT_REQUIRES_( 147 execution::is_execution_policy<ExPolicy>::value && 148 hpx::traits::is_iterator<FwdIter>::value)> 149 typename util::detail::algorithm_result<ExPolicy, FwdIter>::type generate(ExPolicy && policy,FwdIter first,FwdIter last,F && f)150 generate(ExPolicy && policy, FwdIter first, FwdIter last, F && f) 151 { 152 static_assert( 153 (hpx::traits::is_forward_iterator<FwdIter>::value), 154 "Required at least forward iterator."); 155 156 typedef hpx::traits::is_segmented_iterator<FwdIter> is_segmented; 157 158 return detail::generate_( 159 std::forward<ExPolicy>(policy), first, last, 160 std::forward<F>(f), is_segmented()); 161 } 162 163 /////////////////////////////////////////////////////////////////////////// 164 // generate_n 165 namespace detail 166 { 167 /// \cond NOINTERNAL 168 template <typename FwdIter> 169 struct generate_n: public detail::algorithm<generate_n<FwdIter>, FwdIter> 170 { generate_nhpx::parallel::v1::detail::generate_n171 generate_n() 172 : generate_n::algorithm("generate_n") 173 {} 174 175 template <typename ExPolicy, typename InIter, typename F> 176 static FwdIter sequentialhpx::parallel::v1::detail::generate_n177 sequential(ExPolicy, InIter first, std::size_t count, F && f) 178 { 179 return std::generate_n(first, count, f); 180 } 181 182 template <typename ExPolicy, typename F> 183 static typename util::detail::algorithm_result< 184 ExPolicy, FwdIter 185 >::type parallelhpx::parallel::v1::detail::generate_n186 parallel(ExPolicy && policy, FwdIter first, std::size_t count, 187 F && f) 188 { 189 typedef typename std::iterator_traits<FwdIter>::value_type type; 190 191 return 192 for_each_n<FwdIter>().call( 193 std::forward<ExPolicy>(policy), 194 std::false_type(), first, count, 195 [HPX_CAPTURE_FORWARD(f)](type& v) mutable 196 { 197 v = f(); 198 }, 199 util::projection_identity()); 200 } 201 }; 202 /// \endcond 203 } 204 205 /// Assigns each element in range [first, first+count) a value generated by 206 /// the given function object g. 207 /// 208 /// \note Complexity: Exactly \a count invocations of \a f and 209 /// assignments, for count > 0. 210 /// 211 /// \tparam ExPolicy The type of the execution policy to use (deduced). 212 /// It describes the manner in which the execution 213 /// of the algorithm may be parallelized and the manner 214 /// in which it executes the assignments. 215 /// \tparam FwdIter The type of the source iterators used (deduced). 216 /// This iterator type must meet the requirements of an 217 /// forward iterator. 218 /// \tparam F The type of the function/function object to use 219 /// (deduced). Unlike its sequential form, the parallel 220 /// overload of \a equal requires \a F to meet the 221 /// requirements of \a CopyConstructible. 222 /// 223 /// \param policy The execution policy to use for the scheduling of 224 /// the iterations. 225 /// \param first Refers to the beginning of the sequence of elements 226 /// the algorithm will be applied to. 227 /// \param count Refers to the number of elements in the sequence the 228 /// algorithm will be applied to. 229 /// \param f Refers to the generator function object that will be 230 /// called. The signature of the function should be 231 /// equivalent to 232 /// \code 233 /// Ret fun(); 234 /// \endcode \n 235 /// The type \a Ret must be such that an object of type 236 /// \a OutputIt can be dereferenced and assigned a value 237 /// of type \a Ret. 238 /// 239 /// The assignments in the parallel \a generate_n algorithm invoked with an 240 /// execution policy object of type \a sequenced_policy 241 /// execute in sequential order in the calling thread. 242 /// 243 /// The assignments in the parallel \a generate_n algorithm invoked with 244 /// an execution policy object of type \a parallel_policy or 245 /// \a parallel_task_policy are permitted to execute in an unordered 246 /// fashion in unspecified threads, and indeterminately sequenced 247 /// within each thread. 248 /// 249 /// \returns The \a replace_if algorithm returns a \a hpx::future<FwdIter> 250 /// if the execution policy is of type 251 /// \a sequenced_task_policy or 252 /// \a parallel_task_policy 253 /// and returns \a FwdIter otherwise. 254 /// It returns \a last. 255 /// 256 template <typename ExPolicy, typename FwdIter, typename Size, typename F, 257 HPX_CONCEPT_REQUIRES_( 258 execution::is_execution_policy<ExPolicy>::value && 259 hpx::traits::is_iterator<FwdIter>::value)> 260 typename util::detail::algorithm_result<ExPolicy, FwdIter>::type generate_n(ExPolicy && policy,FwdIter first,Size count,F && f)261 generate_n(ExPolicy && policy, FwdIter first, Size count, F && f) 262 { 263 #if defined(HPX_HAVE_ALGORITHM_INPUT_ITERATOR_SUPPORT) 264 static_assert( 265 (hpx::traits::is_output_iterator<FwdIter>::value || 266 hpx::traits::is_forward_iterator<FwdIter>::value), 267 "Required at least output iterator."); 268 269 typedef std::integral_constant<bool, 270 execution::is_sequenced_execution_policy<ExPolicy>::value || 271 !hpx::traits::is_forward_iterator<FwdIter>::value 272 > is_seq; 273 #else 274 static_assert( 275 (hpx::traits::is_forward_iterator<FwdIter>::value), 276 "Required at least forward iterator."); 277 278 typedef execution::is_sequenced_execution_policy<ExPolicy> is_seq; 279 #endif 280 281 if (detail::is_negative(count)) 282 { 283 return util::detail::algorithm_result<ExPolicy, FwdIter>::get( 284 std::move(first)); 285 } 286 287 return detail::generate_n<FwdIter>().call( 288 std::forward<ExPolicy>(policy), is_seq(), 289 first, std::size_t(count), std::forward<F>(f)); 290 } 291 }}} 292 293 #endif 294