1 //////////////////////////////////////////////////////////////////////////////
2 //
3 // (C) Copyright Ion Gaztanaga 2017-2017.
4 // Distributed under the Boost Software License, Version 1.0.
5 // (See accompanying file LICENSE_1_0.txt or copy at
6 // http://www.boost.org/LICENSE_1_0.txt)
7 //
8 // See http://www.boost.org/libs/move for documentation.
9 //
10 //////////////////////////////////////////////////////////////////////////////
11 #ifndef BOOST_MOVE_SET_DIFFERENCE_HPP
12 #define BOOST_MOVE_SET_DIFFERENCE_HPP
13
14 #include <boost/move/algo/move.hpp>
15 #include <boost/move/iterator.hpp>
16 #include <boost/move/utility_core.hpp>
17
18 namespace boost {
19
20 namespace move_detail{
21
22 template<class InputIt, class OutputIt>
copy(InputIt first,InputIt last,OutputIt result)23 OutputIt copy(InputIt first, InputIt last, OutputIt result)
24 {
25 while (first != last) {
26 *result++ = *first;
27 ++result;
28 ++first;
29 }
30 return result;
31 }
32
33 } //namespace move_detail{
34
35 namespace movelib {
36
37 //Moves the elements from the sorted range [first1, last1) which are not found in the sorted
38 //range [first2, last2) to the range beginning at result.
39 //The resulting range is also sorted. Equivalent elements are treated individually,
40 //that is, if some element is found m times in [first1, last1) and n times in [first2, last2),
41 //it will be moved to result exactly max(m-n, 0) times.
42 //The resulting range cannot overlap with either of the input ranges.
43 template<class InputIt1, class InputIt2,
44 class OutputIt, class Compare>
set_difference(InputIt1 first1,InputIt1 last1,InputIt2 first2,InputIt2 last2,OutputIt result,Compare comp)45 OutputIt set_difference
46 (InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt result, Compare comp)
47 {
48 while (first1 != last1) {
49 if (first2 == last2)
50 return boost::move_detail::copy(first1, last1, result);
51
52 if (comp(*first1, *first2)) {
53 *result = *first1;
54 ++result;
55 ++first1;
56 }
57 else {
58 if (!comp(*first2, *first1)) {
59 ++first1;
60 }
61 ++first2;
62 }
63 }
64 return result;
65 }
66
67 //Moves the elements from the sorted range [first1, last1) which are not found in the sorted
68 //range [first2, last2) to the range beginning at first1 (in place operation in range1).
69 //The resulting range is also sorted. Equivalent elements are treated individually,
70 //that is, if some element is found m times in [first1, last1) and n times in [first2, last2),
71 //it will be moved to result exactly max(m-n, 0) times.
72 template<class InputOutputIt1, class InputIt2, class Compare>
inplace_set_difference(InputOutputIt1 first1,InputOutputIt1 last1,InputIt2 first2,InputIt2 last2,Compare comp)73 InputOutputIt1 inplace_set_difference
74 (InputOutputIt1 first1, InputOutputIt1 last1, InputIt2 first2, InputIt2 last2, Compare comp )
75 {
76 while (first1 != last1) {
77 //Skip copying from range 1 if no element has to be skipped
78 if (first2 == last2){
79 return last1;
80 }
81 else if (comp(*first1, *first2)){
82 ++first1;
83 }
84 else{
85 if (!comp(*first2, *first1)) {
86 InputOutputIt1 result = first1;
87 //An element from range 1 must be skipped, no longer an inplace operation
88 return boost::movelib::set_difference
89 ( boost::make_move_iterator(++first1)
90 , boost::make_move_iterator(last1)
91 , ++first2, last2, result, comp);
92 }
93 ++first2;
94 }
95 }
96 return first1;
97 }
98
99 //Moves the elements from the sorted range [first1, last1) which are not found in the sorted
100 //range [first2, last2) to the range beginning at first1.
101 //The resulting range is also sorted. Equivalent elements from range 1 are moved past to end
102 //of the result,
103 //that is, if some element is found m times in [first1, last1) and n times in [first2, last2),
104 //it will be moved to result exactly max(m-n, 0) times.
105 //The resulting range cannot overlap with either of the input ranges.
106 template<class ForwardIt1, class InputIt2,
107 class OutputIt, class Compare>
set_unique_difference(ForwardIt1 first1,ForwardIt1 last1,InputIt2 first2,InputIt2 last2,OutputIt result,Compare comp)108 OutputIt set_unique_difference
109 (ForwardIt1 first1, ForwardIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt result, Compare comp)
110 {
111 while (first1 != last1) {
112 if (first2 == last2){
113 //unique_copy-like sequence with forward iterators but don't write i
114 //to result before comparing as moving *i could alter the value in i.
115 ForwardIt1 i = first1;
116 while (++first1 != last1) {
117 if (comp(*i, *first1)) {
118 *result = *i;
119 ++result;
120 i = first1;
121 }
122 }
123 *result = *i;
124 ++result;
125 break;
126 }
127
128 if (comp(*first1, *first2)) {
129 //Skip equivalent elements in range1 but don't write i
130 //to result before comparing as moving *i could alter the value in i.
131 ForwardIt1 i = first1;
132 while (++first1 != last1) {
133 if (comp(*i, *first1)) {
134 break;
135 }
136 }
137 *result = *i;
138 ++result;
139 }
140 else {
141 if (comp(*first2, *first1)) {
142 ++first2;
143 }
144 else{
145 ++first1;
146 }
147 }
148 }
149 return result;
150 }
151
152 //Moves the elements from the sorted range [first1, last1) which are not found in the sorted
153 //range [first2, last2) to the range beginning at first1 (in place operation in range1).
154 //The resulting range is also sorted. Equivalent elements are treated individually,
155 //that is, if some element is found m times in [first1, last1) and n times in [first2, last2),
156 //it will be moved to result exactly max(m-n, 0) times.
157 template<class ForwardOutputIt1, class ForwardIt2, class Compare>
inplace_set_unique_difference(ForwardOutputIt1 first1,ForwardOutputIt1 last1,ForwardIt2 first2,ForwardIt2 last2,Compare comp)158 ForwardOutputIt1 inplace_set_unique_difference
159 (ForwardOutputIt1 first1, ForwardOutputIt1 last1, ForwardIt2 first2, ForwardIt2 last2, Compare comp )
160 {
161 while (first1 != last1) {
162 //Skip copying from range 1 if no element has to be skipped
163 if (first2 == last2){
164 //unique-like algorithm for the remaining range 1
165 ForwardOutputIt1 result = first1;
166 while (++first1 != last1) {
167 if (comp(*result, *first1) && ++result != first1) {
168 *result = boost::move(*first1);
169 }
170 }
171 return ++result;
172 }
173 else if (comp(*first2, *first1)) {
174 ++first2;
175 }
176 else if (comp(*first1, *first2)){
177 //skip any adjacent equivalent element in range 1
178 ForwardOutputIt1 result = first1;
179 if (++first1 != last1 && !comp(*result, *first1)) {
180 //Some elements from range 1 must be skipped, no longer an inplace operation
181 while (++first1 != last1 && !comp(*result, *first1)){}
182 return boost::movelib::set_unique_difference
183 ( boost::make_move_iterator(first1)
184 , boost::make_move_iterator(last1)
185 , first2, last2, ++result, comp);
186 }
187 }
188 else{
189 ForwardOutputIt1 result = first1;
190 //Some elements from range 1 must be skipped, no longer an inplace operation
191 while (++first1 != last1 && !comp(*result, *first1)){}
192 //An element from range 1 must be skipped, no longer an inplace operation
193 return boost::movelib::set_unique_difference
194 ( boost::make_move_iterator(first1)
195 , boost::make_move_iterator(last1)
196 , first2, last2, result, comp);
197 }
198 }
199 return first1;
200 }
201
202
203
204 } //namespace movelib {
205 } //namespace boost {
206
207 #endif //#define BOOST_MOVE_SET_DIFFERENCE_HPP
208