1 // Copyright (c) 2007-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 #if !defined(HPX_PARALLEL_SEGMENTED_ALGORITHM_MINMAX_JAN_24_2016_0800PM) 7 #define HPX_PARALLEL_SEGMENTED_ALGORITHM_MINMAX_JAN_24_2016_0800PM 8 9 #include <hpx/config.hpp> 10 #include <hpx/traits/segmented_iterator_traits.hpp> 11 12 #include <hpx/parallel/algorithms/detail/dispatch.hpp> 13 #include <hpx/parallel/algorithms/minmax.hpp> 14 #include <hpx/parallel/execution_policy.hpp> 15 #include <hpx/parallel/segmented_algorithms/detail/dispatch.hpp> 16 #include <hpx/parallel/util/detail/algorithm_result.hpp> 17 #include <hpx/parallel/util/detail/handle_remote_exceptions.hpp> 18 19 #include <algorithm> 20 #include <exception> 21 #include <iterator> 22 #include <list> 23 #include <type_traits> 24 #include <utility> 25 #include <vector> 26 27 namespace hpx { namespace parallel { inline namespace v1 28 { 29 /////////////////////////////////////////////////////////////////////////// 30 // segmented_minmax 31 namespace detail 32 { 33 /////////////////////////////////////////////////////////////////////// 34 /// \cond NOINTERNAL 35 36 // sequential remote implementation 37 template <typename Algo, typename ExPolicy, typename SegIter, 38 typename F, typename Proj> 39 static typename util::detail::algorithm_result<ExPolicy, SegIter>::type segmented_minormax(Algo && algo,ExPolicy const & policy,SegIter first,SegIter last,F && f,Proj && proj,std::true_type)40 segmented_minormax(Algo && algo, ExPolicy const& policy, 41 SegIter first, SegIter last, F && f, Proj && proj, std::true_type) 42 { 43 typedef hpx::traits::segmented_iterator_traits<SegIter> traits; 44 typedef typename traits::segment_iterator segment_iterator; 45 typedef typename traits::local_iterator local_iterator_type; 46 47 segment_iterator sit = traits::segment(first); 48 segment_iterator send = traits::segment(last); 49 50 std::vector<SegIter> positions; 51 52 if (sit == send) 53 { 54 // all elements are on the same partition 55 local_iterator_type beg = traits::local(first); 56 local_iterator_type end = traits::local(last); 57 if (beg != end) 58 { 59 local_iterator_type out = dispatch( 60 traits::get_id(sit), algo, policy, std::true_type(), 61 beg, end, f, proj); 62 63 positions.push_back(traits::compose(send, out)); 64 } 65 } 66 else { 67 // handle the remaining part of the first partition 68 local_iterator_type beg = traits::local(first); 69 local_iterator_type end = traits::end(sit); 70 71 if (beg != end) 72 { 73 local_iterator_type out = dispatch( 74 traits::get_id(sit), algo, policy, std::true_type(), 75 beg, end, f, proj); 76 77 positions.push_back(traits::compose(sit, out)); 78 } 79 80 // handle all of the full partitions 81 for (++sit; sit != send; ++sit) 82 { 83 beg = traits::begin(sit); 84 end = traits::end(sit); 85 86 if (beg != end) 87 { 88 local_iterator_type out = dispatch( 89 traits::get_id(sit), algo, policy, std::true_type(), 90 beg, end, f, proj); 91 92 positions.push_back(traits::compose(sit, out)); 93 } 94 } 95 96 // handle the beginning of the last partition 97 beg = traits::begin(sit); 98 end = traits::local(last); 99 if (beg != end) 100 { 101 local_iterator_type out = dispatch( 102 traits::get_id(sit), algo, policy, std::true_type(), 103 beg, end, f, proj); 104 105 positions.push_back(traits::compose(sit, out)); 106 } 107 } 108 109 return Algo::sequential_minmax_element_ind( 110 policy, positions.begin(), positions.size(), f, proj); 111 } 112 113 // parallel remote implementation 114 template <typename Algo, typename ExPolicy, typename SegIter, 115 typename F, typename Proj> 116 static typename util::detail::algorithm_result<ExPolicy, SegIter>::type segmented_minormax(Algo && algo,ExPolicy const & policy,SegIter first,SegIter last,F && f,Proj && proj,std::false_type)117 segmented_minormax(Algo && algo, ExPolicy const& policy, 118 SegIter first, SegIter last, F && f, Proj && proj, std::false_type) 119 { 120 typedef hpx::traits::segmented_iterator_traits<SegIter> traits; 121 typedef typename traits::segment_iterator segment_iterator; 122 typedef typename traits::local_iterator local_iterator_type; 123 124 typedef std::integral_constant<bool, 125 !hpx::traits::is_forward_iterator<SegIter>::value 126 > forced_seq; 127 typedef util::detail::algorithm_result<ExPolicy, SegIter> result; 128 129 segment_iterator sit = traits::segment(first); 130 segment_iterator send = traits::segment(last); 131 132 std::vector<future<SegIter> > segments; 133 segments.reserve(std::distance(sit, send)); 134 135 if (sit == send) 136 { 137 // all elements are on the same partition 138 local_iterator_type beg = traits::local(first); 139 local_iterator_type end = traits::local(last); 140 if (beg != end) 141 { 142 segments.push_back( 143 hpx::make_future<SegIter>( 144 dispatch_async(traits::get_id(sit), algo, 145 policy, forced_seq(), beg, end, f, proj), 146 [send](local_iterator_type const& out) 147 -> SegIter 148 { 149 return traits::compose(send, out); 150 })); 151 } 152 } 153 else { 154 // handle the remaining part of the first partition 155 local_iterator_type beg = traits::local(first); 156 local_iterator_type end = traits::end(sit); 157 if (beg != end) 158 { 159 segments.push_back( 160 hpx::make_future<SegIter>( 161 dispatch_async(traits::get_id(sit), algo, 162 policy, forced_seq(), beg, end, f, proj), 163 [sit](local_iterator_type const& out) 164 -> SegIter 165 { 166 return traits::compose(sit, out); 167 })); 168 } 169 170 // handle all of the full partitions 171 for (++sit; sit != send; ++sit) 172 { 173 beg = traits::begin(sit); 174 end = traits::end(sit); 175 if (beg != end) 176 { 177 segments.push_back( 178 hpx::make_future<SegIter>( 179 dispatch_async(traits::get_id(sit), algo, 180 policy, forced_seq(), beg, end, f, proj), 181 [sit](local_iterator_type const& out) 182 -> SegIter 183 { 184 return traits::compose(sit, out); 185 })); 186 } 187 } 188 189 // handle the beginning of the last partition 190 beg = traits::begin(sit); 191 end = traits::local(last); 192 if (beg != end) 193 { 194 segments.push_back( 195 hpx::make_future<SegIter>( 196 dispatch_async(traits::get_id(sit), algo, 197 policy, forced_seq(), beg, end, f, proj), 198 [sit](local_iterator_type const& out) 199 -> SegIter 200 { 201 return traits::compose(sit, out); 202 })); 203 } 204 } 205 206 return result::get( 207 dataflow( 208 [=](std::vector<hpx::future<SegIter> > && r) 209 -> SegIter 210 { 211 // handle any remote exceptions, will throw on error 212 std::list<std::exception_ptr> errors; 213 parallel::util::detail::handle_remote_exceptions< 214 ExPolicy 215 >::call(r, errors); 216 217 std::vector<SegIter> res = 218 hpx::util::unwrap(std::move(r)); 219 return Algo::sequential_minmax_element_ind( 220 policy, res.begin(), res.size(), f, proj); 221 }, 222 std::move(segments))); 223 } 224 225 /////////////////////////////////////////////////////////////////////// 226 // segmented implementation 227 template <typename ExPolicy, typename SegIter, typename F, typename Proj> 228 inline typename util::detail::algorithm_result<ExPolicy, SegIter>::type min_element_(ExPolicy && policy,SegIter first,SegIter last,F && f,Proj && proj,std::true_type)229 min_element_(ExPolicy && policy, SegIter first, SegIter last, F && f, 230 Proj && proj, std::true_type) 231 { 232 typedef parallel::execution::is_sequenced_execution_policy< 233 ExPolicy 234 > is_seq; 235 236 SegIter result = first; 237 if (first == last || ++first == last) 238 { 239 return util::detail::algorithm_result< 240 ExPolicy, SegIter 241 >::get(std::move(result)); 242 } 243 244 typedef hpx::traits::segmented_iterator_traits<SegIter> 245 iterator_traits; 246 247 return segmented_minormax( 248 min_element<typename iterator_traits::local_iterator>(), 249 std::forward<ExPolicy>(policy), first, last, 250 std::forward<F>(f), std::forward<Proj>(proj), is_seq()); 251 } 252 253 template <typename ExPolicy, typename SegIter, typename F, typename Proj> 254 inline typename util::detail::algorithm_result<ExPolicy, SegIter>::type max_element_(ExPolicy && policy,SegIter first,SegIter last,F && f,Proj && proj,std::true_type)255 max_element_(ExPolicy && policy, SegIter first, SegIter last, F && f, 256 Proj && proj, std::true_type) 257 { 258 typedef parallel::execution::is_sequenced_execution_policy< 259 ExPolicy 260 > is_seq; 261 262 SegIter result = first; 263 if (first == last || ++first == last) 264 { 265 return util::detail::algorithm_result< 266 ExPolicy, SegIter 267 >::get(std::move(result)); 268 } 269 270 typedef hpx::traits::segmented_iterator_traits<SegIter> 271 iterator_traits; 272 273 return segmented_minormax( 274 max_element<typename iterator_traits::local_iterator>(), 275 std::forward<ExPolicy>(policy), first, last, 276 std::forward<F>(f), std::forward<Proj>(proj), is_seq()); 277 } 278 279 // forward declare the non-segmented version of those algorithm 280 template <typename ExPolicy, typename FwdIter, typename F, typename Proj> 281 inline typename util::detail::algorithm_result<ExPolicy, FwdIter>::type 282 min_element_(ExPolicy && policy, FwdIter first, FwdIter last, F && f, 283 Proj && proj, std::false_type); 284 285 template <typename ExPolicy, typename FwdIter, typename F, typename Proj> 286 inline typename util::detail::algorithm_result<ExPolicy, FwdIter>::type 287 max_element_(ExPolicy && policy, FwdIter first, FwdIter last, F && f, 288 Proj && proj, std::false_type); 289 290 /// \endcond 291 } 292 293 /////////////////////////////////////////////////////////////////////////// 294 // segmented_minmax 295 namespace detail 296 { 297 /////////////////////////////////////////////////////////////////////// 298 /// \cond NOINTERNAL 299 300 // sequential remote implementation 301 template <typename Algo, typename ExPolicy, typename SegIter, 302 typename F, typename Proj> 303 static typename util::detail::algorithm_result< 304 ExPolicy, std::pair<SegIter, SegIter> 305 >::type segmented_minmax(Algo && algo,ExPolicy const & policy,SegIter first,SegIter last,F && f,Proj && proj,std::true_type)306 segmented_minmax(Algo && algo, ExPolicy const& policy, 307 SegIter first, SegIter last, F && f, Proj && proj, std::true_type) 308 { 309 typedef hpx::traits::segmented_iterator_traits<SegIter> traits; 310 typedef typename traits::segment_iterator segment_iterator; 311 typedef typename traits::local_iterator local_iterator_type; 312 typedef std::pair<SegIter, SegIter> result_type; 313 314 typedef std::pair< 315 local_iterator_type, local_iterator_type 316 > local_iterator_pair_type; 317 318 segment_iterator sit = traits::segment(first); 319 segment_iterator send = traits::segment(last); 320 321 std::vector<result_type> positions; 322 323 if (sit == send) 324 { 325 // all elements are on the same partition 326 local_iterator_type beg = traits::local(first); 327 local_iterator_type end = traits::local(last); 328 if (beg != end) 329 { 330 local_iterator_pair_type out = dispatch( 331 traits::get_id(sit), algo, policy, std::true_type(), 332 beg, end, f, proj); 333 334 positions.push_back(std::make_pair( 335 traits::compose(send, out.first), 336 traits::compose(send, out.second))); 337 } 338 } 339 else { 340 // handle the remaining part of the first partition 341 local_iterator_type beg = traits::local(first); 342 local_iterator_type end = traits::end(sit); 343 344 if (beg != end) 345 { 346 local_iterator_pair_type out = dispatch( 347 traits::get_id(sit), algo, policy, std::true_type(), 348 beg, end, f, proj); 349 350 positions.push_back(std::make_pair( 351 traits::compose(sit, out.first), 352 traits::compose(sit, out.second))); 353 } 354 355 // handle all of the full partitions 356 for (++sit; sit != send; ++sit) 357 { 358 beg = traits::begin(sit); 359 end = traits::end(sit); 360 361 if (beg != end) 362 { 363 local_iterator_pair_type out = dispatch( 364 traits::get_id(sit), algo, policy, std::true_type(), 365 beg, end, f, proj); 366 367 positions.push_back(std::make_pair( 368 traits::compose(sit, out.first), 369 traits::compose(sit, out.second))); 370 } 371 } 372 373 // handle the beginning of the last partition 374 beg = traits::begin(sit); 375 end = traits::local(last); 376 if (beg != end) 377 { 378 local_iterator_pair_type out = dispatch( 379 traits::get_id(sit), algo, policy, std::true_type(), 380 beg, end, f, proj); 381 382 positions.push_back(std::make_pair( 383 traits::compose(sit, out.first), 384 traits::compose(sit, out.second))); 385 } 386 } 387 388 return Algo::sequential_minmax_element_ind( 389 policy, positions.begin(), positions.size(), f, proj); 390 } 391 392 // parallel remote implementation 393 template <typename Algo, typename ExPolicy, typename SegIter, 394 typename F, typename Proj> 395 static typename util::detail::algorithm_result< 396 ExPolicy, std::pair<SegIter, SegIter> 397 >::type segmented_minmax(Algo && algo,ExPolicy const & policy,SegIter first,SegIter last,F && f,Proj && proj,std::false_type)398 segmented_minmax(Algo && algo, ExPolicy const& policy, 399 SegIter first, SegIter last, F && f, Proj && proj, std::false_type) 400 { 401 typedef hpx::traits::segmented_iterator_traits<SegIter> traits; 402 typedef typename traits::segment_iterator segment_iterator; 403 typedef typename traits::local_iterator local_iterator_type; 404 405 typedef std::integral_constant<bool, 406 !hpx::traits::is_forward_iterator<SegIter>::value 407 > forced_seq; 408 typedef std::pair<SegIter, SegIter> result_type; 409 typedef util::detail::algorithm_result<ExPolicy, result_type> result; 410 411 typedef std::pair< 412 local_iterator_type, local_iterator_type 413 > local_iterator_pair_type; 414 415 segment_iterator sit = traits::segment(first); 416 segment_iterator send = traits::segment(last); 417 418 std::vector<future<result_type> > segments; 419 segments.reserve(std::distance(sit, send)); 420 421 if (sit == send) 422 { 423 // all elements are on the same partition 424 local_iterator_type beg = traits::local(first); 425 local_iterator_type end = traits::local(last); 426 if (beg != end) 427 { 428 segments.push_back( 429 hpx::make_future<result_type>( 430 dispatch_async(traits::get_id(sit), algo, 431 policy, forced_seq(), beg, end, f, proj), 432 [send](local_iterator_pair_type out) 433 -> result_type 434 { 435 return std::make_pair( 436 traits::compose(send, out.first), 437 traits::compose(send, out.second)); 438 })); 439 } 440 } 441 else { 442 // handle the remaining part of the first partition 443 local_iterator_type beg = traits::local(first); 444 local_iterator_type end = traits::end(sit); 445 if (beg != end) 446 { 447 segments.push_back( 448 hpx::make_future<result_type>( 449 dispatch_async(traits::get_id(sit), algo, 450 policy, forced_seq(), beg, end, f, proj), 451 [sit](local_iterator_pair_type const& out) 452 -> result_type 453 { 454 return std::make_pair( 455 traits::compose(sit, out.first), 456 traits::compose(sit, out.second)); 457 })); 458 } 459 460 // handle all of the full partitions 461 for (++sit; sit != send; ++sit) 462 { 463 beg = traits::begin(sit); 464 end = traits::end(sit); 465 if (beg != end) 466 { 467 segments.push_back( 468 hpx::make_future<result_type>( 469 dispatch_async(traits::get_id(sit), algo, 470 policy, forced_seq(), beg, end, f, proj), 471 [sit](local_iterator_pair_type const& out) 472 -> result_type 473 { 474 return std::make_pair( 475 traits::compose(sit, out.first), 476 traits::compose(sit, out.second)); 477 })); 478 } 479 } 480 481 // handle the beginning of the last partition 482 beg = traits::begin(sit); 483 end = traits::local(last); 484 if (beg != end) 485 { 486 segments.push_back( 487 hpx::make_future<result_type>( 488 dispatch_async(traits::get_id(sit), algo, 489 policy, forced_seq(), beg, end, f, proj), 490 [sit](local_iterator_pair_type const& out) 491 -> result_type 492 { 493 return std::make_pair( 494 traits::compose(sit, out.first), 495 traits::compose(sit, out.second)); 496 })); 497 } 498 } 499 500 return result::get( 501 dataflow( 502 [=](std::vector<hpx::future<result_type> > && r) 503 -> result_type 504 { 505 // handle any remote exceptions, will throw on error 506 std::list<std::exception_ptr> errors; 507 parallel::util::detail::handle_remote_exceptions< 508 ExPolicy 509 >::call(r, errors); 510 511 std::vector<result_type> res = 512 hpx::util::unwrap(std::move(r)); 513 return Algo::sequential_minmax_element_ind( 514 policy, res.begin(), res.size(), f, proj); 515 }, 516 std::move(segments))); 517 } 518 519 /////////////////////////////////////////////////////////////////////// 520 // segmented implementation 521 template <typename ExPolicy, typename SegIter, typename F, typename Proj> 522 inline typename util::detail::algorithm_result< 523 ExPolicy, std::pair<SegIter, SegIter> 524 >::type minmax_element_(ExPolicy && policy,SegIter first,SegIter last,F && f,Proj && proj,std::true_type)525 minmax_element_(ExPolicy && policy, SegIter first, SegIter last, F && f, 526 Proj && proj, std::true_type) 527 { 528 typedef parallel::execution::is_sequenced_execution_policy< 529 ExPolicy 530 > is_seq; 531 typedef std::pair<SegIter, SegIter> result_type; 532 533 result_type result(first, first); 534 if (first == last || ++first == last) 535 { 536 return util::detail::algorithm_result< 537 ExPolicy, result_type 538 >::get(std::move(result)); 539 } 540 541 typedef hpx::traits::segmented_iterator_traits<SegIter> 542 iterator_traits; 543 544 return segmented_minmax( 545 minmax_element<typename iterator_traits::local_iterator>(), 546 std::forward<ExPolicy>(policy), first, last, 547 std::forward<F>(f), std::forward<Proj>(proj), is_seq()); 548 } 549 550 // forward declare the non-segmented version of this algorithm 551 template <typename ExPolicy, typename FwdIter, typename F, typename Proj> 552 inline typename util::detail::algorithm_result< 553 ExPolicy, std::pair<FwdIter, FwdIter> 554 >::type 555 minmax_element_(ExPolicy && policy, FwdIter first, FwdIter last, F && f, 556 Proj && proj, std::false_type); 557 558 /// \endcond 559 } 560 }}} 561 562 #endif 563