1 // Copyright (c) 2014-2016 Hartmut Kaiser 2 // 3 // Distributed under the Boost Software License, Version 1.0. (See accompanying 4 // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) 5 6 // make inspect happy: hpxinspect:nominmax 7 8 /// \file parallel/container_algorithms/minmax.hpp 9 10 #if !defined(HPX_PARALLEL_CONTAINER_ALGORITHMS_MINMAX_JAN_25_2016_1218PM) 11 #define HPX_PARALLEL_CONTAINER_ALGORITHMS_MINMAX_JAN_25_2016_1218PM 12 13 #include <hpx/config.hpp> 14 #include <hpx/traits/concepts.hpp> 15 #include <hpx/traits/is_range.hpp> 16 #include <hpx/util/range.hpp> 17 #include <hpx/util/tagged_pair.hpp> 18 19 #include <hpx/parallel/algorithms/minmax.hpp> 20 #include <hpx/parallel/traits/projected.hpp> 21 #include <hpx/parallel/traits/projected_range.hpp> 22 23 #include <type_traits> 24 #include <utility> 25 26 namespace hpx { namespace parallel { inline namespace v1 27 { 28 /// Finds the smallest element in the range [first, last) using the given 29 /// comparison function \a f. 30 /// 31 /// \note Complexity: Exactly \a max(N-1, 0) comparisons, where 32 /// N = std::distance(first, last). 33 /// 34 /// \tparam ExPolicy The type of the execution policy to use (deduced). 35 /// It describes the manner in which the execution 36 /// of the algorithm may be parallelized and the manner 37 /// in which it executes the assignments. 38 /// \tparam Rng The type of the source range used (deduced). 39 /// The iterators extracted from this range type must 40 /// meet the requirements of an forward iterator. 41 /// \tparam F The type of the function/function object to use 42 /// (deduced). Unlike its sequential form, the parallel 43 /// overload of \a min_element requires \a F to meet the 44 /// requirements of \a CopyConstructible. 45 /// \tparam Proj The type of an optional projection function. This 46 /// defaults to \a util::projection_identity 47 /// 48 /// \param policy The execution policy to use for the scheduling of 49 /// the iterations. 50 /// \param rng Refers to the sequence of elements the algorithm 51 /// will be applied to. 52 /// \param f The binary predicate which returns true if the 53 /// the left argument is less than the right element. 54 /// The signature 55 /// of the predicate function should be equivalent to 56 /// the following: 57 /// \code 58 /// bool pred(const Type1 &a, const Type1 &b); 59 /// \endcode \n 60 /// The signature does not need to have const &, but 61 /// the function must not modify the objects passed to 62 /// it. The type \a Type1 must be such that objects of 63 /// type \a FwdIter can be dereferenced and then 64 /// implicitly converted to \a Type1. 65 /// \param proj Specifies the function (or function object) which 66 /// will be invoked for each of the elements as a 67 /// projection operation before the actual predicate 68 /// \a is invoked. 69 /// 70 /// The comparisons in the parallel \a min_element algorithm invoked with 71 /// an execution policy object of type \a sequenced_policy 72 /// execute in sequential order in the calling thread. 73 /// 74 /// The comparisons in the parallel \a min_element algorithm invoked with 75 /// an execution policy object of type \a parallel_policy or 76 /// \a parallel_task_policy are permitted to execute in an unordered 77 /// fashion in unspecified threads, and indeterminately sequenced 78 /// within each thread. 79 /// 80 /// \returns The \a min_element algorithm returns a \a hpx::future<FwdIter> 81 /// if the execution policy is of type 82 /// \a sequenced_task_policy or 83 /// \a parallel_task_policy 84 /// and returns \a FwdIter otherwise. 85 /// The \a min_element algorithm returns the iterator to the 86 /// smallest element in the range [first, last). If several 87 /// elements in the range are equivalent to the smallest element, 88 /// returns the iterator to the first such element. Returns last 89 /// if the range is empty. 90 /// 91 template <typename ExPolicy, typename Rng, 92 typename Proj = util::projection_identity, 93 typename F = detail::less, 94 HPX_CONCEPT_REQUIRES_( 95 execution::is_execution_policy<ExPolicy>::value && 96 hpx::traits::is_range<Rng>::value && 97 traits::is_projected_range<Proj, Rng>::value && 98 traits::is_indirect_callable< 99 ExPolicy, F, 100 traits::projected_range<Proj, Rng>, 101 traits::projected_range<Proj, Rng> 102 >::value)> 103 typename util::detail::algorithm_result< 104 ExPolicy, typename hpx::traits::range_traits<Rng>::iterator_type 105 >::type min_element(ExPolicy && policy,Rng && rng,F && f=F (),Proj && proj=Proj ())106 min_element(ExPolicy && policy, Rng && rng, F && f = F(), 107 Proj && proj = Proj()) 108 { 109 return min_element(std::forward<ExPolicy>(policy), 110 hpx::util::begin(rng), hpx::util::end(rng), 111 std::forward<F>(f), std::forward<Proj>(proj)); 112 } 113 114 /// Finds the greatest element in the range [first, last) using the given 115 /// comparison function \a f. 116 /// 117 /// \note Complexity: Exactly \a max(N-1, 0) comparisons, where 118 /// N = std::distance(first, last). 119 /// 120 /// \tparam ExPolicy The type of the execution policy to use (deduced). 121 /// It describes the manner in which the execution 122 /// of the algorithm may be parallelized and the manner 123 /// in which it executes the assignments. 124 /// \tparam Rng The type of the source range used (deduced). 125 /// The iterators extracted from this range type must 126 /// meet the requirements of an forward iterator. 127 /// \tparam F The type of the function/function object to use 128 /// (deduced). Unlike its sequential form, the parallel 129 /// overload of \a max_element requires \a F to meet the 130 /// requirements of \a CopyConstructible. 131 /// \tparam Proj The type of an optional projection function. This 132 /// defaults to \a util::projection_identity 133 /// 134 /// \param policy The execution policy to use for the scheduling of 135 /// the iterations. 136 /// \param rng Refers to the sequence of elements the algorithm 137 /// will be applied to. 138 /// \param f The binary predicate which returns true if the 139 /// This argument is optional and defaults to std::less. 140 /// the left argument is less than the right element. 141 /// The signature 142 /// of the predicate function should be equivalent to 143 /// the following: 144 /// \code 145 /// bool pred(const Type1 &a, const Type1 &b); 146 /// \endcode \n 147 /// The signature does not need to have const &, but 148 /// the function must not modify the objects passed to 149 /// it. The type \a Type1 must be such that objects of 150 /// type \a FwdIter can be dereferenced and then 151 /// implicitly converted to \a Type1. 152 /// \param proj Specifies the function (or function object) which 153 /// will be invoked for each of the elements as a 154 /// projection operation before the actual predicate 155 /// \a is invoked. 156 /// 157 /// The comparisons in the parallel \a max_element algorithm invoked with 158 /// an execution policy object of type \a sequenced_policy 159 /// execute in sequential order in the calling thread. 160 /// 161 /// The comparisons in the parallel \a max_element algorithm invoked with 162 /// an execution policy object of type \a parallel_policy or 163 /// \a parallel_task_policy are permitted to execute in an unordered 164 /// fashion in unspecified threads, and indeterminately sequenced 165 /// within each thread. 166 /// 167 /// \returns The \a max_element algorithm returns a \a hpx::future<FwdIter> 168 /// if the execution policy is of type 169 /// \a sequenced_task_policy or 170 /// \a parallel_task_policy 171 /// and returns \a FwdIter otherwise. 172 /// The \a max_element algorithm returns the iterator to the 173 /// smallest element in the range [first, last). If several 174 /// elements in the range are equivalent to the smallest element, 175 /// returns the iterator to the first such element. Returns last 176 /// if the range is empty. 177 /// 178 template <typename ExPolicy, typename Rng, 179 typename Proj = util::projection_identity, 180 typename F = detail::less, 181 HPX_CONCEPT_REQUIRES_( 182 execution::is_execution_policy<ExPolicy>::value && 183 hpx::traits::is_range<Rng>::value && 184 traits::is_projected_range<Proj, Rng>::value && 185 traits::is_indirect_callable< 186 ExPolicy, F, 187 traits::projected_range<Proj, Rng>, 188 traits::projected_range<Proj, Rng> 189 >::value)> 190 typename util::detail::algorithm_result< 191 ExPolicy, typename hpx::traits::range_traits<Rng>::iterator_type 192 >::type max_element(ExPolicy && policy,Rng && rng,F && f=F (),Proj && proj=Proj ())193 max_element(ExPolicy && policy, Rng && rng, F && f = F(), 194 Proj && proj = Proj()) 195 { 196 return max_element(std::forward<ExPolicy>(policy), 197 hpx::util::begin(rng), hpx::util::end(rng), 198 std::forward<F>(f), std::forward<Proj>(proj)); 199 } 200 201 /// Finds the greatest element in the range [first, last) using the given 202 /// comparison function \a f. 203 /// 204 /// \note Complexity: At most \a max(floor(3/2*(N-1)), 0) applications of 205 /// the predicate, where N = std::distance(first, last). 206 /// 207 /// \tparam ExPolicy The type of the execution policy to use (deduced). 208 /// It describes the manner in which the execution 209 /// of the algorithm may be parallelized and the manner 210 /// in which it executes the assignments. 211 /// \tparam Rng The type of the source range used (deduced). 212 /// The iterators extracted from this range type must 213 /// meet the requirements of an forward iterator. 214 /// \tparam F The type of the function/function object to use 215 /// (deduced). Unlike its sequential form, the parallel 216 /// overload of \a minmax_element requires \a F to meet the 217 /// requirements of \a CopyConstructible. 218 /// \tparam Proj The type of an optional projection function. This 219 /// defaults to \a util::projection_identity 220 /// 221 /// \param policy The execution policy to use for the scheduling of 222 /// the iterations. 223 /// \param rng Refers to the sequence of elements the algorithm 224 /// will be applied to. 225 /// \param f The binary predicate which returns true if the 226 /// the left argument is less than the right element. 227 /// This argument is optional and defaults to std::less. 228 /// The signature 229 /// of the predicate function should be equivalent to 230 /// the following: 231 /// \code 232 /// bool pred(const Type1 &a, const Type1 &b); 233 /// \endcode \n 234 /// The signature does not need to have const &, but 235 /// the function must not modify the objects passed to 236 /// it. The type \a Type1 must be such that objects of 237 /// type \a FwdIter can be dereferenced and then 238 /// implicitly converted to \a Type1. 239 /// \param proj Specifies the function (or function object) which 240 /// will be invoked for each of the elements as a 241 /// projection operation before the actual predicate 242 /// \a is invoked. 243 /// 244 /// The comparisons in the parallel \a minmax_element algorithm invoked with 245 /// an execution policy object of type \a sequenced_policy 246 /// execute in sequential order in the calling thread. 247 /// 248 /// The comparisons in the parallel \a minmax_element algorithm invoked with 249 /// an execution policy object of type \a parallel_policy or 250 /// \a parallel_task_policy are permitted to execute in an unordered 251 /// fashion in unspecified threads, and indeterminately sequenced 252 /// within each thread. 253 /// 254 /// \returns The \a minmax_element algorithm returns a 255 /// \a hpx::future<tagged_pair<tag::min(FwdIter), tag::max(FwdIter)> > 256 /// if the execution policy is of type 257 /// \a sequenced_task_policy or 258 /// \a parallel_task_policy 259 /// and returns \a tagged_pair<tag::min(FwdIter), tag::max(FwdIter)> 260 /// otherwise. 261 /// The \a minmax_element algorithm returns a pair consisting of 262 /// an iterator to the smallest element as the first element and 263 /// an iterator to the greatest element as the second. Returns 264 /// std::make_pair(first, first) if the range is empty. If 265 /// several elements are equivalent to the smallest element, the 266 /// iterator to the first such element is returned. If several 267 /// elements are equivalent to the largest element, the iterator 268 /// to the last such element is returned. 269 /// 270 271 #if defined(HPX_MSVC) 272 #pragma push_macro("min") 273 #pragma push_macro("max") 274 #undef min 275 #undef max 276 #endif 277 278 template <typename ExPolicy, typename Rng, 279 typename Proj = util::projection_identity, 280 typename F = detail::less, 281 HPX_CONCEPT_REQUIRES_( 282 execution::is_execution_policy<ExPolicy>::value && 283 hpx::traits::is_range<Rng>::value && 284 traits::is_projected_range<Proj, Rng>::value && 285 traits::is_indirect_callable< 286 ExPolicy, F, 287 traits::projected_range<Proj, Rng>, 288 traits::projected_range<Proj, Rng> 289 >::value)> 290 typename util::detail::algorithm_result< 291 ExPolicy, 292 hpx::util::tagged_pair< 293 tag::min(typename hpx::traits::range_traits<Rng>::iterator_type), 294 tag::max(typename hpx::traits::range_traits<Rng>::iterator_type)> 295 >::type minmax_element(ExPolicy && policy,Rng && rng,F && f=F (),Proj && proj=Proj ())296 minmax_element(ExPolicy && policy, Rng && rng, F && f = F(), 297 Proj && proj = Proj()) 298 { 299 return minmax_element(std::forward<ExPolicy>(policy), 300 hpx::util::begin(rng), hpx::util::end(rng), 301 std::forward<F>(f), std::forward<Proj>(proj)); 302 } 303 304 #if defined(HPX_MSVC) 305 #pragma pop_macro("min") 306 #pragma pop_macro("max") 307 #endif 308 }}} 309 310 #endif 311