Horizon
set_algorithm.hpp
Go to the documentation of this file.
1 // 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 
29 #include <range/v3/algorithm/result_types.hpp>
39 #include <range/v3/utility/static_const.hpp>
40 
41 #include <range/v3/detail/prologue.hpp>
42 
43 namespace ranges
44 {
47  RANGES_FUNC_BEGIN(includes)
48 
49 
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  requires input_iterator<I1> AND sentinel_for<S1, I1> AND
58  input_iterator<I2> AND sentinel_for<S2, I2> AND
59  indirect_strict_weak_order<C, projected<I1, P1>, projected<I2, P2>>)
60  constexpr bool RANGES_FUNC(includes)(I1 begin1,
61  S1 end1,
62  I2 begin2,
63  S2 end2,
64  C pred = C{},
65  P1 proj1 = P1{},
66  P2 proj2 = P2{}) //
67  {
68  for(; begin2 != end2; ++begin1)
69  {
70  if(begin1 == end1 ||
71  invoke(pred, invoke(proj2, *begin2), invoke(proj1, *begin1)))
72  return false;
73  if(!invoke(pred, invoke(proj1, *begin1), invoke(proj2, *begin2)))
74  ++begin2;
75  }
76  return true;
77  }
78 
80  template(typename Rng1,
81  typename Rng2,
82  typename C = less,
83  typename P1 = identity,
84  typename P2 = identity)(
85  requires input_range<Rng1> AND input_range<Rng2> AND
87  projected<iterator_t<Rng1>, P1>,
88  projected<iterator_t<Rng2>, P2>>)
89  constexpr bool RANGES_FUNC(includes)(
90  Rng1 && rng1, Rng2 && rng2, C pred = C{}, P1 proj1 = P1{}, P2 proj2 = P2{}) //
91  {
92  return (*this)(begin(rng1),
93  end(rng1),
94  begin(rng2),
95  end(rng2),
96  std::move(pred),
97  std::move(proj1),
98  std::move(proj2));
99  }
100 
101  RANGES_FUNC_END(includes)
102 
103  namespace cpp20
104  {
105  using ranges::includes;
106  }
107 
108  template<typename I1, typename I2, typename O>
109  using set_union_result = detail::in1_in2_out_result<I1, I2, O>;
110 
111  RANGES_FUNC_BEGIN(set_union)
112 
113 
114  template(typename I1,
115  typename S1,
116  typename I2,
117  typename S2,
118  typename O,
119  typename C = less,
120  typename P1 = identity,
121  typename P2 = identity)(
122  requires sentinel_for<S1, I1> AND sentinel_for<S2, I2> AND
123  mergeable<I1, I2, O, C, P1, P2>)
124  constexpr set_union_result<I1, I2, O> RANGES_FUNC(set_union)(I1 begin1,
125  S1 end1,
126  I2 begin2,
127  S2 end2,
128  O out,
129  C pred = C{},
130  P1 proj1 = P1{},
131  P2 proj2 = P2{}) //
132  {
133  for(; begin1 != end1; ++out)
134  {
135  if(begin2 == end2)
136  {
137  auto tmp = ranges::copy(begin1, end1, out);
138  return {tmp.in, begin2, tmp.out};
139  }
140  if(invoke(pred, invoke(proj2, *begin2), invoke(proj1, *begin1)))
141  {
142  *out = *begin2;
143  ++begin2;
144  }
145  else
146  {
147  *out = *begin1;
148  if(!invoke(pred, invoke(proj1, *begin1), invoke(proj2, *begin2)))
149  ++begin2;
150  ++begin1;
151  }
152  }
153  auto tmp = ranges::copy(begin2, end2, out);
154  return {begin1, tmp.in, tmp.out};
155  }
156 
158  template(typename Rng1,
159  typename Rng2,
160  typename O,
161  typename C = less,
162  typename P1 = identity,
163  typename P2 = identity)(
164  requires range<Rng1> AND range<Rng2> AND
165  mergeable<iterator_t<Rng1>, iterator_t<Rng2>, O, C, P1, P2>)
166  constexpr set_union_result<borrowed_iterator_t<Rng1>, borrowed_iterator_t<Rng2>, O> //
167  RANGES_FUNC(set_union)(Rng1 && rng1,
168  Rng2 && rng2,
169  O out,
170  C pred = C{},
171  P1 proj1 = P1{},
172  P2 proj2 = P2{}) //
173  {
174  return (*this)(begin(rng1),
175  end(rng1),
176  begin(rng2),
177  end(rng2),
178  std::move(out),
179  std::move(pred),
180  std::move(proj1),
181  std::move(proj2));
182  }
183 
184  RANGES_FUNC_END(set_union)
185 
186  namespace cpp20
187  {
188  using ranges::set_union;
189  using ranges::set_union_result;
190  } // namespace cpp20
191 
192  RANGES_FUNC_BEGIN(set_intersection)
193 
194 
195  template(typename I1,
196  typename S1,
197  typename I2,
198  typename S2,
199  typename O,
200  typename C = less,
201  typename P1 = identity,
202  typename P2 = identity)(
203  requires sentinel_for<S1, I1> AND sentinel_for<S2, I2> AND
204  mergeable<I1, I2, O, C, P1, P2>)
205  constexpr O RANGES_FUNC(set_intersection)(I1 begin1,
206  S1 end1,
207  I2 begin2,
208  S2 end2,
209  O out,
210  C pred = C{},
211  P1 proj1 = P1{},
212  P2 proj2 = P2{}) //
213  {
214  while(begin1 != end1 && begin2 != end2)
215  {
216  if(invoke(pred, invoke(proj1, *begin1), invoke(proj2, *begin2)))
217  ++begin1;
218  else
219  {
220  if(!invoke(pred, invoke(proj2, *begin2), invoke(proj1, *begin1)))
221  {
222  *out = *begin1;
223  ++out;
224  ++begin1;
225  }
226  ++begin2;
227  }
228  }
229  return out;
230  }
231 
233  template(typename Rng1,
234  typename Rng2,
235  typename O,
236  typename C = less,
237  typename P1 = identity,
238  typename P2 = identity)(
239  requires range<Rng1> AND range<Rng2> AND
240  mergeable<iterator_t<Rng1>, iterator_t<Rng2>, O, C, P1, P2>)
241  constexpr O RANGES_FUNC(set_intersection)(Rng1 && rng1,
242  Rng2 && rng2,
243  O out,
244  C pred = C{},
245  P1 proj1 = P1{},
246  P2 proj2 = P2{}) //
247  {
248  return (*this)(begin(rng1),
249  end(rng1),
250  begin(rng2),
251  end(rng2),
252  std::move(out),
253  std::move(pred),
254  std::move(proj1),
255  std::move(proj2));
256  }
257 
258  RANGES_FUNC_END(set_intersection)
259 
260  namespace cpp20
261  {
262  using ranges::set_intersection;
263  }
264 
265  template<typename I, typename O>
266  using set_difference_result = detail::in1_out_result<I, O>;
267 
268  RANGES_FUNC_BEGIN(set_difference)
269 
270 
271  template(typename I1,
272  typename S1,
273  typename I2,
274  typename S2,
275  typename O,
276  typename C = less,
277  typename P1 = identity,
278  typename P2 = identity)(
279  requires sentinel_for<S1, I1> AND sentinel_for<S2, I2> AND
280  mergeable<I1, I2, O, C, P1, P2>)
281  constexpr set_difference_result<I1, O> RANGES_FUNC(set_difference)(I1 begin1,
282  S1 end1,
283  I2 begin2,
284  S2 end2,
285  O out,
286  C pred = C{},
287  P1 proj1 = P1{},
288  P2 proj2 = P2{}) //
289  {
290  while(begin1 != end1)
291  {
292  if(begin2 == end2)
293  {
294  auto tmp = ranges::copy(begin1, end1, out);
295  return {tmp.in, tmp.out};
296  }
297  if(invoke(pred, invoke(proj1, *begin1), invoke(proj2, *begin2)))
298  {
299  *out = *begin1;
300  ++out;
301  ++begin1;
302  }
303  else
304  {
305  if(!invoke(pred, invoke(proj2, *begin2), invoke(proj1, *begin1)))
306  ++begin1;
307  ++begin2;
308  }
309  }
310  return {begin1, out};
311  }
312 
314  template(typename Rng1,
315  typename Rng2,
316  typename O,
317  typename C = less,
318  typename P1 = identity,
319  typename P2 = identity)(
320  requires range<Rng1> AND range<Rng2> AND
321  mergeable<iterator_t<Rng1>, iterator_t<Rng2>, O, C, P1, P2>)
322  constexpr set_difference_result<borrowed_iterator_t<Rng1>, O> //
323  RANGES_FUNC(set_difference)(Rng1 && rng1,
324  Rng2 && rng2,
325  O out,
326  C pred = C{},
327  P1 proj1 = P1{},
328  P2 proj2 = P2{}) //
329  {
330  return (*this)(begin(rng1),
331  end(rng1),
332  begin(rng2),
333  end(rng2),
334  std::move(out),
335  std::move(pred),
336  std::move(proj1),
337  std::move(proj2));
338  }
339 
340  RANGES_FUNC_END(set_difference)
341 
342  namespace cpp20
343  {
344  using ranges::set_difference;
345  using ranges::set_difference_result;
346  } // namespace cpp20
347 
348  template<typename I1, typename I2, typename O>
349  using set_symmetric_difference_result = detail::in1_in2_out_result<I1, I2, O>;
350 
351  RANGES_FUNC_BEGIN(set_symmetric_difference)
352 
353 
354  template(typename I1,
355  typename S1,
356  typename I2,
357  typename S2,
358  typename O,
359  typename C = less,
360  typename P1 = identity,
361  typename P2 = identity)(
362  requires sentinel_for<S1, I1> AND sentinel_for<S2, I2> AND
363  mergeable<I1, I2, O, C, P1, P2>)
364  constexpr set_symmetric_difference_result<I1, I2, O> //
365  RANGES_FUNC(set_symmetric_difference)(I1 begin1,
366  S1 end1,
367  I2 begin2,
368  S2 end2,
369  O out,
370  C pred = C{},
371  P1 proj1 = P1{},
372  P2 proj2 = P2{}) //
373  {
374  while(begin1 != end1)
375  {
376  if(begin2 == end2)
377  {
378  auto tmp = ranges::copy(begin1, end1, out);
379  return {tmp.in, begin2, tmp.out};
380  }
381  if(invoke(pred, invoke(proj1, *begin1), invoke(proj2, *begin2)))
382  {
383  *out = *begin1;
384  ++out;
385  ++begin1;
386  }
387  else
388  {
389  if(invoke(pred, invoke(proj2, *begin2), invoke(proj1, *begin1)))
390  {
391  *out = *begin2;
392  ++out;
393  }
394  else
395  ++begin1;
396  ++begin2;
397  }
398  }
399  auto tmp = ranges::copy(begin2, end2, out);
400  return {begin1, tmp.in, tmp.out};
401  }
402 
404  template(typename Rng1,
405  typename Rng2,
406  typename O,
407  typename C = less,
408  typename P1 = identity,
409  typename P2 = identity)(
410  requires range<Rng1> AND range<Rng2> AND
411  mergeable<iterator_t<Rng1>, iterator_t<Rng2>, O, C, P1, P2>)
412  constexpr set_symmetric_difference_result<borrowed_iterator_t<Rng1>,
413  borrowed_iterator_t<Rng2>,
414  O>
415  RANGES_FUNC(set_symmetric_difference)(Rng1 && rng1,
416  Rng2 && rng2,
417  O out,
418  C pred = C{},
419  P1 proj1 = P1{},
420  P2 proj2 = P2{}) //
421  {
422  return (*this)(begin(rng1),
423  end(rng1),
424  begin(rng2),
425  end(rng2),
426  std::move(out),
427  std::move(pred),
428  std::move(proj1),
429  std::move(proj2));
430  }
431 
432  RANGES_FUNC_END(set_symmetric_difference)
433 
434  namespace cpp20
435  {
436  using ranges::set_symmetric_difference;
437  using ranges::set_symmetric_difference_result;
438  } // namespace cpp20
440 } // namespace ranges
441 
442 #include <range/v3/detail/epilogue.hpp>
443 
444 #endif
template(typename Rng1, typename Rng2, typename O, typename C=less, typename P1=identity, typename P2=identity)(requires range< Rng1 > AND range< Rng2 > AND mergeable< iterator_t< Rng1 >
This is an overloaded member function, provided for convenience. It differs from the above function o...
CPP_concept sentinel_for
\concept sentinel_for
Definition: concepts.hpp:306
CPP_concept indirect_strict_weak_order
\concept indirect_strict_weak_order
Definition: concepts.hpp:689
decltype(begin(declval(Rng &))) iterator_t
Definition: access.hpp:698
typename Fn::template invoke< Args... > invoke
Evaluate the invocable Fn with the arguments Args.
Definition: meta.hpp:541
bool_<(T::type::value< U::type::value)> less
A Boolean integral constant wrapper around true if T::type::value is less than U::type::value; false,...
Definition: meta.hpp:255
Definition: identity.hpp:25
Definition: comparisons.hpp:50