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