1 /// \file 2 // Range v3 library 3 // 4 // Copyright Eric Niebler 2014-present 5 // 6 // Use, modification and distribution is subject to the 7 // Boost Software License, Version 1.0. (See accompanying 8 // file LICENSE_1_0.txt or copy at 9 // http://www.boost.org/LICENSE_1_0.txt) 10 // 11 // Project home: https://github.com/ericniebler/range-v3 12 // 13 //===----------------------------------------------------------------------===// 14 // 15 // The LLVM Compiler Infrastructure 16 // 17 // This file is dual licensed under the MIT and the University of Illinois Open 18 // Source Licenses. See LICENSE.TXT for details. 19 // 20 //===----------------------------------------------------------------------===// 21 #ifndef RANGES_V3_ALGORITHM_SET_ALGORITHM_HPP 22 #define RANGES_V3_ALGORITHM_SET_ALGORITHM_HPP 23 24 #include <utility> 25 26 #include <range/v3/range_fwd.hpp> 27 28 #include <range/v3/algorithm/copy.hpp> 29 #include <range/v3/algorithm/result_types.hpp> 30 #include <range/v3/functional/comparisons.hpp> 31 #include <range/v3/functional/identity.hpp> 32 #include <range/v3/functional/invoke.hpp> 33 #include <range/v3/iterator/concepts.hpp> 34 #include <range/v3/iterator/traits.hpp> 35 #include <range/v3/range/access.hpp> 36 #include <range/v3/range/concepts.hpp> 37 #include <range/v3/range/dangling.hpp> 38 #include <range/v3/range/traits.hpp> 39 #include <range/v3/utility/static_const.hpp> 40 41 #include <range/v3/detail/prologue.hpp> 42 43 namespace ranges 44 { 45 /// \addtogroup group-algorithms 46 /// @{ 47 RANGES_FUNC_BEGIN(includes) 48 49 /// \brief function template \c includes 50 template(typename I1, 51 typename S1, 52 typename I2, 53 typename S2, 54 typename C = less, 55 typename P1 = identity, 56 typename P2 = identity)( 57 /// \pre 58 requires input_iterator<I1> AND sentinel_for<S1, I1> AND 59 input_iterator<I2> AND sentinel_for<S2, I2> AND 60 indirect_strict_weak_order<C, projected<I1, P1>, projected<I2, P2>>) 61 bool RANGES_FUNC(includes)(I1 begin1, 62 S1 end1, 63 I2 begin2, 64 S2 end2, 65 C pred = C{}, 66 P1 proj1 = P1{}, 67 P2 proj2 = P2{}) // 68 { 69 for(; begin2 != end2; ++begin1) 70 { 71 if(begin1 == end1 || 72 invoke(pred, invoke(proj2, *begin2), invoke(proj1, *begin1))) 73 return false; 74 if(!invoke(pred, invoke(proj1, *begin1), invoke(proj2, *begin2))) 75 ++begin2; 76 } 77 return true; 78 } 79 80 /// \overload 81 template(typename Rng1, 82 typename Rng2, 83 typename C = less, 84 typename P1 = identity, 85 typename P2 = identity)( 86 /// \pre 87 requires input_range<Rng1> AND input_range<Rng2> AND 88 indirect_strict_weak_order<C, 89 projected<iterator_t<Rng1>, P1>, 90 projected<iterator_t<Rng2>, P2>>) 91 bool RANGES_FUNC(includes)( 92 Rng1 && rng1, Rng2 && rng2, C pred = C{}, P1 proj1 = P1{}, P2 proj2 = P2{}) // 93 { 94 return (*this)(begin(rng1), 95 end(rng1), 96 begin(rng2), 97 end(rng2), 98 std::move(pred), 99 std::move(proj1), 100 std::move(proj2)); 101 } 102 103 RANGES_FUNC_END(includes) 104 105 namespace cpp20 106 { 107 using ranges::includes; 108 } 109 110 template<typename I1, typename I2, typename O> 111 using set_union_result = detail::in1_in2_out_result<I1, I2, O>; 112 RANGES_FUNC_BEGIN(set_union)113 RANGES_FUNC_BEGIN(set_union) 114 115 /// \brief function template \c set_union 116 template(typename I1, 117 typename S1, 118 typename I2, 119 typename S2, 120 typename O, 121 typename C = less, 122 typename P1 = identity, 123 typename P2 = identity)( 124 /// \pre 125 requires sentinel_for<S1, I1> AND sentinel_for<S2, I2> AND 126 mergeable<I1, I2, O, C, P1, P2>) 127 set_union_result<I1, I2, O> RANGES_FUNC(set_union)(I1 begin1, 128 S1 end1, 129 I2 begin2, 130 S2 end2, 131 O out, 132 C pred = C{}, 133 P1 proj1 = P1{}, 134 P2 proj2 = P2{}) // 135 { 136 for(; begin1 != end1; ++out) 137 { 138 if(begin2 == end2) 139 { 140 auto tmp = ranges::copy(begin1, end1, out); 141 return {tmp.in, begin2, tmp.out}; 142 } 143 if(invoke(pred, invoke(proj2, *begin2), invoke(proj1, *begin1))) 144 { 145 *out = *begin2; 146 ++begin2; 147 } 148 else 149 { 150 *out = *begin1; 151 if(!invoke(pred, invoke(proj1, *begin1), invoke(proj2, *begin2))) 152 ++begin2; 153 ++begin1; 154 } 155 } 156 auto tmp = ranges::copy(begin2, end2, out); 157 return {begin1, tmp.in, tmp.out}; 158 } 159 160 /// \overload 161 template(typename Rng1, 162 typename Rng2, 163 typename O, 164 typename C = less, 165 typename P1 = identity, 166 typename P2 = identity)( 167 /// \pre 168 requires range<Rng1> AND range<Rng2> AND 169 mergeable<iterator_t<Rng1>, iterator_t<Rng2>, O, C, P1, P2>) 170 set_union_result<borrowed_iterator_t<Rng1>, borrowed_iterator_t<Rng2>, O> // RANGES_FUNC(set_union)171 RANGES_FUNC(set_union)(Rng1 && rng1, 172 Rng2 && rng2, 173 O out, 174 C pred = C{}, 175 P1 proj1 = P1{}, 176 P2 proj2 = P2{}) // 177 { 178 return (*this)(begin(rng1), 179 end(rng1), 180 begin(rng2), 181 end(rng2), 182 std::move(out), 183 std::move(pred), 184 std::move(proj1), 185 std::move(proj2)); 186 } 187 188 RANGES_FUNC_END(set_union) 189 190 namespace cpp20 191 { 192 using ranges::set_union; 193 using ranges::set_union_result; 194 } // namespace cpp20 195 196 RANGES_FUNC_BEGIN(set_intersection) 197 198 /// \brief function template \c set_intersection 199 template(typename I1, 200 typename S1, 201 typename I2, 202 typename S2, 203 typename O, 204 typename C = less, 205 typename P1 = identity, 206 typename P2 = identity)( 207 /// \pre 208 requires sentinel_for<S1, I1> AND sentinel_for<S2, I2> AND 209 mergeable<I1, I2, O, C, P1, P2>) 210 O RANGES_FUNC(set_intersection)(I1 begin1, 211 S1 end1, 212 I2 begin2, 213 S2 end2, 214 O out, 215 C pred = C{}, 216 P1 proj1 = P1{}, 217 P2 proj2 = P2{}) // 218 { 219 while(begin1 != end1 && begin2 != end2) 220 { 221 if(invoke(pred, invoke(proj1, *begin1), invoke(proj2, *begin2))) 222 ++begin1; 223 else 224 { 225 if(!invoke(pred, invoke(proj2, *begin2), invoke(proj1, *begin1))) 226 { 227 *out = *begin1; 228 ++out; 229 ++begin1; 230 } 231 ++begin2; 232 } 233 } 234 return out; 235 } 236 237 /// \overload 238 template(typename Rng1, 239 typename Rng2, 240 typename O, 241 typename C = less, 242 typename P1 = identity, 243 typename P2 = identity)( 244 /// \pre 245 requires range<Rng1> AND range<Rng2> AND 246 mergeable<iterator_t<Rng1>, iterator_t<Rng2>, O, C, P1, P2>) 247 O RANGES_FUNC(set_intersection)(Rng1 && rng1, 248 Rng2 && rng2, 249 O out, 250 C pred = C{}, 251 P1 proj1 = P1{}, 252 P2 proj2 = P2{}) // 253 { 254 return (*this)(begin(rng1), 255 end(rng1), 256 begin(rng2), 257 end(rng2), 258 std::move(out), 259 std::move(pred), 260 std::move(proj1), 261 std::move(proj2)); 262 } 263 264 RANGES_FUNC_END(set_intersection) 265 266 namespace cpp20 267 { 268 using ranges::set_intersection; 269 } 270 271 template<typename I, typename O> 272 using set_difference_result = detail::in1_out_result<I, O>; 273 RANGES_FUNC_BEGIN(set_difference)274 RANGES_FUNC_BEGIN(set_difference) 275 276 /// \brief function template \c set_difference 277 template(typename I1, 278 typename S1, 279 typename I2, 280 typename S2, 281 typename O, 282 typename C = less, 283 typename P1 = identity, 284 typename P2 = identity)( 285 /// \pre 286 requires sentinel_for<S1, I1> AND sentinel_for<S2, I2> AND 287 mergeable<I1, I2, O, C, P1, P2>) 288 set_difference_result<I1, O> RANGES_FUNC(set_difference)(I1 begin1, 289 S1 end1, 290 I2 begin2, 291 S2 end2, 292 O out, 293 C pred = C{}, 294 P1 proj1 = P1{}, 295 P2 proj2 = P2{}) // 296 { 297 while(begin1 != end1) 298 { 299 if(begin2 == end2) 300 { 301 auto tmp = ranges::copy(begin1, end1, out); 302 return {tmp.in, tmp.out}; 303 } 304 if(invoke(pred, invoke(proj1, *begin1), invoke(proj2, *begin2))) 305 { 306 *out = *begin1; 307 ++out; 308 ++begin1; 309 } 310 else 311 { 312 if(!invoke(pred, invoke(proj2, *begin2), invoke(proj1, *begin1))) 313 ++begin1; 314 ++begin2; 315 } 316 } 317 return {begin1, out}; 318 } 319 320 /// \overload 321 template(typename Rng1, 322 typename Rng2, 323 typename O, 324 typename C = less, 325 typename P1 = identity, 326 typename P2 = identity)( 327 /// \pre 328 requires range<Rng1> AND range<Rng2> AND 329 mergeable<iterator_t<Rng1>, iterator_t<Rng2>, O, C, P1, P2>) 330 set_difference_result<borrowed_iterator_t<Rng1>, O> // RANGES_FUNC(set_difference)331 RANGES_FUNC(set_difference)(Rng1 && rng1, 332 Rng2 && rng2, 333 O out, 334 C pred = C{}, 335 P1 proj1 = P1{}, 336 P2 proj2 = P2{}) // 337 { 338 return (*this)(begin(rng1), 339 end(rng1), 340 begin(rng2), 341 end(rng2), 342 std::move(out), 343 std::move(pred), 344 std::move(proj1), 345 std::move(proj2)); 346 } 347 348 RANGES_FUNC_END(set_difference) 349 350 namespace cpp20 351 { 352 using ranges::set_difference; 353 using ranges::set_difference_result; 354 } // namespace cpp20 355 356 template<typename I1, typename I2, typename O> 357 using set_symmetric_difference_result = detail::in1_in2_out_result<I1, I2, O>; 358 RANGES_FUNC_BEGIN(set_symmetric_difference)359 RANGES_FUNC_BEGIN(set_symmetric_difference) 360 361 /// \brief function template \c set_symmetric_difference 362 template(typename I1, 363 typename S1, 364 typename I2, 365 typename S2, 366 typename O, 367 typename C = less, 368 typename P1 = identity, 369 typename P2 = identity)( 370 /// \pre 371 requires sentinel_for<S1, I1> AND sentinel_for<S2, I2> AND 372 mergeable<I1, I2, O, C, P1, P2>) 373 set_symmetric_difference_result<I1, I2, O> // 374 RANGES_FUNC(set_symmetric_difference)(I1 begin1, 375 S1 end1, 376 I2 begin2, 377 S2 end2, 378 O out, 379 C pred = C{}, 380 P1 proj1 = P1{}, 381 P2 proj2 = P2{}) // 382 { 383 while(begin1 != end1) 384 { 385 if(begin2 == end2) 386 { 387 auto tmp = ranges::copy(begin1, end1, out); 388 return {tmp.in, begin2, tmp.out}; 389 } 390 if(invoke(pred, invoke(proj1, *begin1), invoke(proj2, *begin2))) 391 { 392 *out = *begin1; 393 ++out; 394 ++begin1; 395 } 396 else 397 { 398 if(invoke(pred, invoke(proj2, *begin2), invoke(proj1, *begin1))) 399 { 400 *out = *begin2; 401 ++out; 402 } 403 else 404 ++begin1; 405 ++begin2; 406 } 407 } 408 auto tmp = ranges::copy(begin2, end2, out); 409 return {begin1, tmp.in, tmp.out}; 410 } 411 412 /// \overload 413 template(typename Rng1, 414 typename Rng2, 415 typename O, 416 typename C = less, 417 typename P1 = identity, 418 typename P2 = identity)( 419 /// \pre 420 requires range<Rng1> AND range<Rng2> AND 421 mergeable<iterator_t<Rng1>, iterator_t<Rng2>, O, C, P1, P2>) 422 set_symmetric_difference_result<borrowed_iterator_t<Rng1>, 423 borrowed_iterator_t<Rng2>, 424 O> RANGES_FUNC(set_symmetric_difference)425 RANGES_FUNC(set_symmetric_difference)(Rng1 && rng1, 426 Rng2 && rng2, 427 O out, 428 C pred = C{}, 429 P1 proj1 = P1{}, 430 P2 proj2 = P2{}) // 431 { 432 return (*this)(begin(rng1), 433 end(rng1), 434 begin(rng2), 435 end(rng2), 436 std::move(out), 437 std::move(pred), 438 std::move(proj1), 439 std::move(proj2)); 440 } 441 442 RANGES_FUNC_END(set_symmetric_difference) 443 444 namespace cpp20 445 { 446 using ranges::set_symmetric_difference; 447 using ranges::set_symmetric_difference_result; 448 } // namespace cpp20 449 /// @} 450 } // namespace ranges 451 452 #include <range/v3/detail/epilogue.hpp> 453 454 #endif 455