1 // (C) Copyright Ben Bear, Herve Bronnimann 2007.
2 // Use, modification and distribution are subject to the
3 // Boost Software License, Version 1.0. (See accompanying file
4 // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
5
6 /*
7 Revision history:
8 Nov 13, 2007: Incorporation of boost-devel comments (Jens Seidel, Ben Bear and myself)
9 Nov 11, 2007: Rewrite of Ben Bear's Gacap
10 */
11
12 #ifndef BOOST_ALGORITHM_COMBINATION_HPP
13 #define BOOST_ALGORITHM_COMBINATION_HPP
14
15 #include <algorithm>
16
17 namespace boost {
18
19 namespace detail {
20
21 template<class BidirectionalIterator>
next_combination(BidirectionalIterator first1,BidirectionalIterator last1,BidirectionalIterator first2,BidirectionalIterator last2)22 bool next_combination(BidirectionalIterator first1,
23 BidirectionalIterator last1,
24 BidirectionalIterator first2,
25 BidirectionalIterator last2)
26 {
27 if ((first1 == last1) || (first2 == last2)) {
28 return false;
29 }
30
31 BidirectionalIterator m1 = last1;
32 BidirectionalIterator m2 = last2; --m2;
33
34 // Find first m1 not less than *m2 (i.e., lower_bound(first1, last1, *m2)).
35 // Actually, this loop stops at one position before that, except perhaps
36 // if m1 == first1 (in which case one must compare *first1 with *m2).
37 while (--m1 != first1 && !(*m1 < *m2)) {
38 }
39
40 // Test if all elements in [first1, last1) not less than *m2.
41 bool result = (m1 == first1) && !(*first1 < *m2);
42
43 if (!result) {
44
45 // Find first first2 greater than *m1 (since *m1 < *m2, we know it
46 // can't pass m2 and there's no need to test m2).
47 while (first2 != m2 && !(*m1 < *first2)) {
48 ++first2;
49 }
50
51 first1 = m1;
52 std::iter_swap (first1, first2);
53 ++first1;
54 ++first2;
55 }
56
57 // Merge [first1, last1) with [first2, last2), given that the rest of the
58 // original ranges are sorted and compare appropriately.
59 if ((first1 != last1) && (first2 != last2)) {
60 for (m1 = last1, m2 = first2; (m1 != first1) && (m2 != last2); ++m2) {
61 std::iter_swap (--m1, m2);
62 }
63
64 std::reverse (first1, m1);
65 std::reverse (first1, last1);
66
67 std::reverse (m2, last2);
68 std::reverse (first2, last2);
69 }
70
71 return !result;
72 }
73
74 template<class BidirectionalIterator, class Compare>
next_combination(BidirectionalIterator first1,BidirectionalIterator last1,BidirectionalIterator first2,BidirectionalIterator last2,Compare comp)75 bool next_combination(BidirectionalIterator first1,
76 BidirectionalIterator last1,
77 BidirectionalIterator first2,
78 BidirectionalIterator last2, Compare comp)
79 {
80 if ((first1 == last1) || (first2 == last2)) {
81 return false;
82 }
83
84 BidirectionalIterator m1 = last1;
85 BidirectionalIterator m2 = last2; --m2;
86
87 while (--m1 != first1 && !comp(*m1, *m2)) {
88 }
89
90 bool result = (m1 == first1) && !comp(*first1, *m2);
91
92 if (!result) {
93
94 while (first2 != m2 && !comp(*m1, *first2)) {
95 ++first2;
96 }
97
98 first1 = m1;
99 std::iter_swap (first1, first2);
100 ++first1;
101 ++first2;
102 }
103
104 if ((first1 != last1) && (first2 != last2)) {
105 for (m1 = last1, m2 = first2; (m1 != first1) && (m2 != last2); ++m2) {
106 std::iter_swap (--m1, m2);
107 }
108
109 std::reverse (first1, m1);
110 std::reverse (first1, last1);
111
112 std::reverse (m2, last2);
113 std::reverse (first2, last2);
114 }
115
116 return !result;
117 }
118
119 } // namespace detail
120
121 /* PROPOSED STANDARD EXTENSIONS:
122 *
123 * template<class BidirectionalIterator>
124 * bool next_partial_permutation(BidirectionalIterator first,
125 * BidirectionalIterator middle,
126 * BidirectionalIterator last);
127 *
128 * template<class BidirectionalIterator, class Compare>
129 * bool next_partial_permutation(BidirectionalIterator first,
130 * BidirectionalIterator middle,
131 * BidirectionalIterator last, Compare comp);
132 */
133
134 template <class BidirectionalIterator>
next_partial_permutation(BidirectionalIterator first,BidirectionalIterator middle,BidirectionalIterator last)135 bool next_partial_permutation(BidirectionalIterator first,
136 BidirectionalIterator middle,
137 BidirectionalIterator last)
138 {
139 reverse (middle, last);
140 return next_permutation(first, last);
141 }
142
143 template<class BidirectionalIterator, class Compare>
next_partial_permutation(BidirectionalIterator first,BidirectionalIterator middle,BidirectionalIterator last,Compare comp)144 bool next_partial_permutation(BidirectionalIterator first,
145 BidirectionalIterator middle,
146 BidirectionalIterator last, Compare comp)
147 {
148 reverse (middle, last);
149 return next_permutation(first, last, comp);
150 }
151
152 /* PROPOSED STANDARD EXTENSIONS:
153 *
154 * template<class BidirectionalIterator>
155 * bool prev_partial_permutation(BidirectionalIterator first,
156 * BidirectionalIterator middle,
157 * BidirectionalIterator last);
158 *
159 * template<class BidirectionalIterator, class Compare>
160 * bool prev_partial_permutation(BidirectionalIterator first,
161 * BidirectionalIterator middle,
162 * BidirectionalIterator last, Compare comp);
163 */
164
165 template<class BidirectionalIterator>
prev_partial_permutation(BidirectionalIterator first,BidirectionalIterator middle,BidirectionalIterator last)166 bool prev_partial_permutation(BidirectionalIterator first,
167 BidirectionalIterator middle,
168 BidirectionalIterator last)
169 {
170 bool result = prev_permutation(first, last);
171 reverse (middle, last);
172 return result;
173 }
174
175
176 template<class BidirectionalIterator, class Compare>
prev_partial_permutation(BidirectionalIterator first,BidirectionalIterator middle,BidirectionalIterator last,Compare comp)177 bool prev_partial_permutation(BidirectionalIterator first,
178 BidirectionalIterator middle,
179 BidirectionalIterator last, Compare comp)
180 {
181 bool result = prev_permutation(first, last);
182 reverse (middle, last);
183 return result;
184 }
185
186 /* PROPOSED STANDARD EXTENSIONS:
187 *
188 * template<class BidirectionalIterator>
189 * bool next_combination(BidirectionalIterator first,
190 * BidirectionalIterator middle,
191 * BidirectionalIterator last);
192 *
193 * template<class BidirectionalIterator, class Compare>
194 * bool next_combination(BidirectionalIterator first,
195 * BidirectionalIterator middle,
196 * BidirectionalIterator last, Compare comp);
197 */
198
199 template<class BidirectionalIterator>
next_combination(BidirectionalIterator first,BidirectionalIterator middle,BidirectionalIterator last)200 bool next_combination(BidirectionalIterator first,
201 BidirectionalIterator middle,
202 BidirectionalIterator last)
203 {
204 return detail::next_combination(first, middle, middle, last);
205 }
206
207 template<class BidirectionalIterator, class Compare>
next_combination(BidirectionalIterator first,BidirectionalIterator middle,BidirectionalIterator last,Compare comp)208 bool next_combination(BidirectionalIterator first,
209 BidirectionalIterator middle,
210 BidirectionalIterator last, Compare comp)
211 {
212 return detail::next_combination(first, middle, middle, last, comp);
213 }
214
215 /* PROPOSED STANDARD EXTENSIONS:
216 *
217 * template<class BidirectionalIterator>
218 * bool prev_combination(BidirectionalIterator first,
219 * BidirectionalIterator middle,
220 * BidirectionalIterator last);
221 *
222 * template<class BidirectionalIterator, class Compare>
223 * bool prev_combination(BidirectionalIterator first,
224 * BidirectionalIterator middle,
225 * BidirectionalIterator last, Compare comp);
226 */
227
228 template<class BidirectionalIterator>
229 inline
prev_combination(BidirectionalIterator first,BidirectionalIterator middle,BidirectionalIterator last)230 bool prev_combination(BidirectionalIterator first,
231 BidirectionalIterator middle,
232 BidirectionalIterator last)
233 {
234 return detail::next_combination(middle, last, first, middle);
235 }
236
237 template<class BidirectionalIterator, class Compare>
238 inline
prev_combination(BidirectionalIterator first,BidirectionalIterator middle,BidirectionalIterator last,Compare comp)239 bool prev_combination(BidirectionalIterator first,
240 BidirectionalIterator middle,
241 BidirectionalIterator last, Compare comp)
242 {
243 return detail::next_combination(middle, last, first, middle, comp);
244 }
245
246 /* PROPOSED STANDARD EXTENSION:
247 *
248 * template<class BidirectionalIterator, class T>
249 * bool next_mapping(BidirectionalIterator first,
250 * BidirectionalIterator last,
251 * T first_value, T last_value);
252 *
253 * template<class BidirectionalIterator, class T, class Incrementor>
254 * bool next_mapping(BidirectionalIterator first,
255 * BidirectionalIterator last,
256 * T first_value, T last_value, Incrementor increment);
257 */
258
259 template <class BidirectionalIterator, class T>
260 bool
next_mapping(BidirectionalIterator first,BidirectionalIterator last,T first_value,T last_value)261 next_mapping(BidirectionalIterator first,
262 BidirectionalIterator last,
263 T first_value, T last_value)
264 {
265 if (last == first ) {
266 return false;
267 }
268 do {
269 if (++(*(--last)) != last_value) {
270 return true;
271 }
272 *last = first_value;
273 } while (last != first);
274 return false;
275 }
276
277 template <class BidirectionalIterator, class T, class Incrementer>
278 bool
next_mapping(BidirectionalIterator first,BidirectionalIterator last,T first_value,T last_value,Incrementer increment)279 next_mapping(BidirectionalIterator first,
280 BidirectionalIterator last,
281 T first_value, T last_value, Incrementer increment)
282 {
283 if (last == first ) {
284 return false;
285 }
286 do {
287 if (incrementer(*(--last)) != last_value) {
288 return true;
289 }
290 *last = first_value;
291 } while (last != first);
292 return false;
293 }
294
295 /* PROPOSED STANDARD EXTENSION:
296 *
297 * template<class BidirectionalIterator, class T>
298 * bool prev_mapping(BidirectionalIterator first,
299 * BidirectionalIterator last,
300 * T first_value, T last_value);
301 *
302 * template<class BidirectionalIterator, class T, class Decrementor>
303 * bool prev_mapping(BidirectionalIterator first,
304 * BidirectionalIterator last,
305 * T first_value, T last_value, Decrementor decrement);
306 */
307
308 template <class BidirectionalIterator, class T>
309 bool
prev_mapping(BidirectionalIterator first,BidirectionalIterator last,T first_value,T last_value)310 prev_mapping(BidirectionalIterator first,
311 BidirectionalIterator last,
312 T first_value, T last_value)
313 {
314 if (last == first) {
315 return false;
316 }
317 --last_value;
318 do {
319 if (*(--last) != first_value) {
320 --(*last);
321 return true;
322 }
323 *last = last_value;
324 } while (last != first);
325 return true;
326 }
327
328 template <class BidirectionalIterator, class T, class Decrementer>
329 bool
prev_mapping(BidirectionalIterator first,BidirectionalIterator last,T first_value,T last_value,Decrementer decrement)330 prev_mapping(BidirectionalIterator first,
331 BidirectionalIterator last,
332 T first_value, T last_value, Decrementer decrement)
333 {
334 if (last == first) {
335 return false;
336 }
337 decrement(last_value);
338 do {
339 if (*(--last) != first_value) {
340 decrement(*last);
341 return true;
342 }
343 *last = last_value;
344 } while (last != first);
345 return true;
346 }
347
348 /* PROPOSED STANDARD EXTENSION:
349 *
350 * template<class BidirectionalIterator, class T>
351 * bool next_combination_counts(BidirectionalIterator first,
352 * BidirectionalIterator last);
353 */
354
355 template <class BidirectionalIterator>
356 bool
next_combination_counts(BidirectionalIterator first,BidirectionalIterator last)357 next_combination_counts(BidirectionalIterator first,
358 BidirectionalIterator last)
359 {
360 BidirectionalIterator current = last;
361 while (current != first && *(--current) == 0) {
362 }
363 if (current == first) {
364 if (first != last && *first != 0)
365 std::iter_swap(--last, first);
366 return false;
367 }
368 --(*current);
369 std::iter_swap(--last, current);
370 ++(*(--current));
371 return true;
372 }
373
374 /* PROPOSED STANDARD EXTENSION:
375 *
376 * template<class BidirectionalIterator>
377 * bool prev_combination_counts(BidirectionalIterator first,
378 * BidirectionalIterator last);
379 */
380
381 template <class BidirectionalIterator>
382 bool
prev_combination_counts(BidirectionalIterator first,BidirectionalIterator last)383 prev_combination_counts(BidirectionalIterator first,
384 BidirectionalIterator last)
385 {
386 if (first == last)
387 return false;
388 BidirectionalIterator current = --last;
389 while (current != first && *(--current) == 0) {
390 }
391 if (current == last || current == first && *current == 0) {
392 if (first != last)
393 std::iter_swap(first, last);
394 return false;
395 }
396 --(*current);
397 ++current;
398 if (0 != *last) {
399 std::iter_swap(current, last);
400 }
401 ++(*current);
402 return true;
403 }
404
405 } // namespace boost
406
407 #endif // BOOST_ALGORITHM_COMBINATION_HPP
408