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