1 // Copyright (c) 2007-2017 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 /// \file parallel/algorithms/includes.hpp 7 8 #if !defined(HPX_PARALLEL_ALGORITH_INCLUDES_MAR_10_2015_0737PM) 9 #define HPX_PARALLEL_ALGORITH_INCLUDES_MAR_10_2015_0737PM 10 11 #include <hpx/config.hpp> 12 #include <hpx/traits/is_iterator.hpp> 13 #include <hpx/util/range.hpp> 14 15 #include <hpx/parallel/algorithms/detail/dispatch.hpp> 16 #include <hpx/parallel/algorithms/detail/predicates.hpp> 17 #include <hpx/parallel/execution_policy.hpp> 18 #include <hpx/parallel/util/cancellation_token.hpp> 19 #include <hpx/parallel/util/detail/algorithm_result.hpp> 20 #include <hpx/parallel/util/partitioner.hpp> 21 22 #include <algorithm> 23 #include <cstddef> 24 #include <iterator> 25 #include <type_traits> 26 #include <utility> 27 #include <vector> 28 29 namespace hpx { namespace parallel { inline namespace v1 30 { 31 /////////////////////////////////////////////////////////////////////////// 32 // includes 33 namespace detail 34 { 35 /// \cond NOINTERNAL 36 37 /////////////////////////////////////////////////////////////////////// 38 template <typename FwdIter, typename T, typename F, typename CancelToken> 39 FwdIter lower_bound(FwdIter first, FwdIter last, T const& value, 40 F && f, CancelToken& tok) 41 { 42 typedef typename std::iterator_traits<FwdIter>::difference_type 43 difference_type; 44 45 difference_type count = std::distance(first, last); 46 while (count > 0) 47 { 48 if (tok.was_cancelled()) 49 break; 50 51 difference_type step = count / 2; 52 FwdIter it = detail::next(first, step); 53 54 if (f(*it, value)) 55 { 56 first = ++it; 57 count -= step + 1; 58 } 59 else 60 { 61 count = step; 62 } 63 } 64 return first; 65 } 66 67 template <typename FwdIter, typename T, typename F, typename CancelToken> 68 FwdIter upper_bound(FwdIter first, FwdIter last, T const& value, 69 F && f, CancelToken& tok) 70 { 71 typedef typename std::iterator_traits<FwdIter>::difference_type 72 difference_type; 73 74 difference_type count = std::distance(first, last); 75 while (count > 0) 76 { 77 if (tok.was_cancelled()) 78 break; 79 80 difference_type step = count / 2; 81 FwdIter it = detail::next(first, step); 82 83 if (!f(*it, value)) 84 { 85 first = ++it; 86 count -= step + 1; 87 } 88 else 89 { 90 count = step; 91 } 92 } 93 return first; 94 } 95 96 template <typename FwdIter1, typename FwdIter2, typename F, 97 typename CancelToken> sequential_includes(FwdIter1 first1,FwdIter1 last1,FwdIter2 first2,FwdIter2 last2,F && f,CancelToken & tok)98 bool sequential_includes(FwdIter1 first1, FwdIter1 last1, FwdIter2 first2, 99 FwdIter2 last2, F && f, CancelToken& tok) 100 { 101 while (first2 != last2) 102 { 103 if (tok.was_cancelled()) 104 return false; 105 106 if (first1 == last1 || f(*first2, *first1)) 107 return false; 108 if (!f(*first1, *first2)) 109 ++first2; 110 111 ++first1; 112 } 113 return true; 114 } 115 116 /////////////////////////////////////////////////////////////////////// 117 struct includes : public detail::algorithm<includes, bool> 118 { includeshpx::parallel::v1::detail::includes119 includes() 120 : includes::algorithm("includes") 121 {} 122 123 template <typename ExPolicy, typename InIter1, typename InIter2, 124 typename F> 125 static bool sequentialhpx::parallel::v1::detail::includes126 sequential(ExPolicy, InIter1 first1, InIter1 last1, 127 InIter2 first2, InIter2 last2, F && f) 128 { 129 return std::includes(first1, last1, first2, last2, 130 std::forward<F>(f)); 131 } 132 133 template <typename ExPolicy, typename FwdIter1, typename FwdIter2, 134 typename F> 135 static typename util::detail::algorithm_result<ExPolicy, bool>::type parallelhpx::parallel::v1::detail::includes136 parallel(ExPolicy && policy, FwdIter1 first1, FwdIter1 last1, 137 FwdIter2 first2, FwdIter2 last2, F && f) 138 { 139 if (first1 == last1) 140 { 141 return util::detail::algorithm_result<ExPolicy, bool>::get( 142 false); 143 } 144 145 if (first2 == last2) 146 { 147 return util::detail::algorithm_result<ExPolicy, bool>::get( 148 true); 149 } 150 151 util::cancellation_token<> tok; 152 return util::partitioner<ExPolicy, bool>::call( 153 std::forward<ExPolicy>(policy), 154 first2, std::distance(first2, last2), 155 [first1, last1, first2, last2, tok, 156 HPX_CAPTURE_FORWARD(f) 157 ](FwdIter2 part_begin, std::size_t part_count) mutable 158 -> bool 159 { 160 FwdIter2 part_end = detail::next(part_begin, part_count); 161 if (first2 != part_begin) 162 { 163 part_begin = upper_bound(part_begin, part_end, 164 *part_begin, f, tok); 165 if (tok.was_cancelled()) 166 return false; 167 if (part_begin == part_end) 168 return true; 169 } 170 171 FwdIter1 low = lower_bound(first1, last1, 172 *part_begin, f, tok); 173 if (tok.was_cancelled()) 174 return false; 175 176 if (low == last1 || f(*part_begin, *low)) 177 { 178 tok.cancel(); 179 return false; 180 } 181 182 FwdIter1 high = last1; 183 if (part_end != last2) 184 { 185 high = upper_bound(low, last1, *part_end, f, tok); 186 part_end = upper_bound(part_end, last2, 187 *part_end, f, tok); 188 if (tok.was_cancelled()) 189 return false; 190 } 191 192 if (!sequential_includes(low, high, part_begin, 193 part_end, f, tok)) 194 { 195 tok.cancel(); 196 } 197 return !tok.was_cancelled(); 198 }, 199 [](std::vector<hpx::future<bool> > && results) 200 { 201 return std::all_of( 202 hpx::util::begin(results), hpx::util::end(results), 203 [](hpx::future<bool>& val) 204 { 205 return val.get(); 206 }); 207 }); 208 } 209 }; 210 /// \endcond 211 } 212 213 /// Returns true if every element from the sorted range [first2, last2) is 214 /// found within the sorted range [first1, last1). Also returns true if 215 /// [first2, last2) is empty. The version expects both ranges to be sorted 216 /// with the user supplied binary predicate \a f. 217 /// 218 /// \note At most 2*(N1+N2-1) comparisons, where 219 /// N1 = std::distance(first1, last1) and 220 /// N2 = std::distance(first2, last2). 221 /// 222 /// \tparam ExPolicy The type of the execution policy to use (deduced). 223 /// It describes the manner in which the execution 224 /// of the algorithm may be parallelized and the manner 225 /// in which it executes the assignments. 226 /// \tparam FwdIter1 The type of the source iterators used for the 227 /// first range (deduced). 228 /// This iterator type must meet the requirements of an 229 /// forward iterator. 230 /// \tparam FwdIter2 The type of the source iterators used for the 231 /// second range (deduced). 232 /// This iterator type must meet the requirements of an 233 /// forward iterator. 234 /// \tparam Pred The type of an optional function/function object to use. 235 /// Unlike its sequential form, the parallel 236 /// overload of \a includes requires \a Pred to meet the 237 /// requirements of \a CopyConstructible. This defaults 238 /// to std::less<> 239 /// 240 /// \param policy The execution policy to use for the scheduling of 241 /// the iterations. 242 /// \param first1 Refers to the beginning of the sequence of elements 243 /// of the first range the algorithm will be applied to. 244 /// \param last1 Refers to the end of the sequence of elements of 245 /// the first range the algorithm will be applied to. 246 /// \param first2 Refers to the beginning of the sequence of elements 247 /// of the second range the algorithm will be applied to. 248 /// \param last2 Refers to the end of the sequence of elements of 249 /// the second range the algorithm will be applied to. 250 /// \param op The binary predicate which returns true if the 251 /// elements should be treated as includes. The signature 252 /// of the predicate function should be equivalent to 253 /// the following: 254 /// \code 255 /// bool pred(const Type1 &a, const Type2 &b); 256 /// \endcode \n 257 /// The signature does not need to have const &, but 258 /// the function must not modify the objects passed to 259 /// it. The types \a Type1 and \a Type2 must be such 260 /// that objects of types \a FwdIter1 and \a FwdIter2 can 261 /// be dereferenced and then implicitly converted to 262 /// \a Type1 and \a Type2 respectively 263 /// 264 /// The comparison operations in the parallel \a includes algorithm invoked 265 /// with an execution policy object of type \a sequenced_policy 266 /// execute in sequential order in the calling thread. 267 /// 268 /// The comparison operations in the parallel \a includes algorithm invoked 269 /// with an execution policy object of type \a parallel_policy 270 /// or \a parallel_task_policy are permitted to execute in an unordered 271 /// fashion in unspecified threads, and indeterminately sequenced 272 /// within each thread. 273 /// 274 /// \returns The \a includes algorithm returns a \a hpx::future<bool> if the 275 /// execution policy is of type 276 /// \a sequenced_task_policy or 277 /// \a parallel_task_policy and 278 /// returns \a bool otherwise. 279 /// The \a includes algorithm returns true every element from the 280 /// sorted range [first2, last2) is found within the sorted range 281 /// [first1, last1). Also returns true if [first2, last2) is empty. 282 /// 283 template <typename ExPolicy, typename FwdIter1, typename FwdIter2, 284 typename Pred = detail::less> 285 inline typename std::enable_if< 286 execution::is_execution_policy<ExPolicy>::value, 287 typename util::detail::algorithm_result<ExPolicy, bool>::type 288 >::type includes(ExPolicy && policy,FwdIter1 first1,FwdIter1 last1,FwdIter2 first2,FwdIter2 last2,Pred && op=Pred ())289 includes(ExPolicy&& policy, FwdIter1 first1, FwdIter1 last1, 290 FwdIter2 first2, FwdIter2 last2, Pred && op = Pred()) 291 { 292 #if defined(HPX_HAVE_ALGORITHM_INPUT_ITERATOR_SUPPORT) 293 static_assert( 294 (hpx::traits::is_input_iterator<FwdIter1>::value), 295 "Requires at least input iterator."); 296 static_assert( 297 (hpx::traits::is_input_iterator<FwdIter2>::value), 298 "Requires at least input iterator."); 299 300 typedef std::integral_constant<bool, 301 execution::is_sequenced_execution_policy<ExPolicy>::value || 302 !hpx::traits::is_forward_iterator<FwdIter1>::value || 303 !hpx::traits::is_forward_iterator<FwdIter2>::value 304 > is_seq; 305 #else 306 static_assert( 307 (hpx::traits::is_forward_iterator<FwdIter1>::value), 308 "Requires at least forward iterator."); 309 static_assert( 310 (hpx::traits::is_forward_iterator<FwdIter2>::value), 311 "Requires at least forward iterator."); 312 313 typedef execution::is_sequenced_execution_policy<ExPolicy> is_seq; 314 #endif 315 316 return detail::includes().call( 317 std::forward<ExPolicy>(policy), is_seq(), 318 first1, last1, first2, last2, std::forward<Pred>(op)); 319 } 320 }}} 321 322 #endif 323