Horizon
merge_n.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 // Copyright (c) 2009 Alexander Stepanov and Paul McJones
14 //
15 // Permission to use, copy, modify, distribute and sell this software
16 // and its documentation for any purpose is hereby granted without
17 // fee, provided that the above copyright notice appear in all copies
18 // and that both that copyright notice and this permission notice
19 // appear in supporting documentation. The authors make no
20 // representations about the suitability of this software for any
21 // purpose. It is provided "as is" without express or implied
22 // warranty.
23 //
24 // Algorithms from
25 // Elements of Programming
26 // by Alexander Stepanov and Paul McJones
27 // Addison-Wesley Professional, 2009
28 #ifndef RANGES_V3_ALGORITHM_AUX_MERGE_N_HPP
29 #define RANGES_V3_ALGORITHM_AUX_MERGE_N_HPP
30 
31 #include <tuple>
32 
33 #include <range/v3/range_fwd.hpp>
34 
36 #include <range/v3/algorithm/result_types.hpp>
45 #include <range/v3/utility/static_const.hpp>
46 
47 #include <range/v3/detail/prologue.hpp>
48 
49 namespace ranges
50 {
51  namespace aux
52  {
53  template<typename I0, typename I1, typename O>
54  using merge_n_result = detail::in1_in2_out_result<I0, I1, O>;
55 
56  struct merge_n_fn
57  {
58  template(typename I0, typename I1, typename O, typename C = less,
59  typename P0 = identity, typename P1 = identity)(
60  requires mergeable<I0, I1, O, C, P0, P1>)
61  merge_n_result<I0, I1, O> operator()(I0 begin0,
62  iter_difference_t<I0> n0,
63  I1 begin1,
64  iter_difference_t<I1> n1,
65  O out,
66  C r = C{},
67  P0 p0 = P0{},
68  P1 p1 = P1{}) const
69  {
70  using T = merge_n_result<I0, I1, O>;
71  auto n0orig = n0;
72  auto n1orig = n1;
73  auto b0 = uncounted(begin0);
74  auto b1 = uncounted(begin1);
75  while(true)
76  {
77  if(0 == n0)
78  {
79  auto res = copy_n(b1, n1, out);
80  begin0 = recounted(begin0, b0, n0orig);
81  begin1 = recounted(begin1, res.in, n1orig);
82  return T{begin0, begin1, res.out};
83  }
84  if(0 == n1)
85  {
86  auto res = copy_n(b0, n0, out);
87  begin0 = recounted(begin0, res.in, n0orig);
88  begin1 = recounted(begin1, b1, n1orig);
89  return T{begin0, begin1, res.out};
90  }
91  if(invoke(r, invoke(p1, *b1), invoke(p0, *b0)))
92  {
93  *out = *b1;
94  ++b1;
95  ++out;
96  --n1;
97  }
98  else
99  {
100  *out = *b0;
101  ++b0;
102  ++out;
103  --n0;
104  }
105  }
106  }
107  };
108 
110  } // namespace aux
111 } // namespace ranges
112 
113 #include <range/v3/detail/epilogue.hpp>
114 
115 #endif
RANGES_INLINE_VARIABLE(detail::to_container_fn< detail::from_range< std::vector >>, to_vector) template< template< typename... > class ContT > auto to(RANGES_HIDDEN_DETAIL(detail
For initializing a container of the specified type with the elements of an Range.
Definition: conversion.hpp:399
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: merge_n.hpp:57
Definition: identity.hpp:25