PFProducer/src/combination.hpp

0001 //  (C) Copyright Ben Bear, Herve Bronnimann 2007.
0002 //  Use, modification and distribution are subject to the
0003 //  Boost Software License, Version 1.0. (See accompanying file
0004 //  LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
0005
0006 /*
0007  Revision history:
0008 Nov 13, 2007:  Incorporation of boost-devel comments (Jens Seidel, Ben Bear and myself)
0009 Nov 11, 2007:  Rewrite of Ben Bear's Gacap
0010 Dec 27, 2018:  Removed code not used, changed namespace to notboost since this was never incorporated in boost by cdj
0011 */
0012
0013 #ifndef NOTBOOST_ALGORITHM_COMBINATION_HPP
0014 #define NOTBOOST_ALGORITHM_COMBINATION_HPP
0015
0016 #include <algorithm>
0017
0018 namespace notboost {
0019
0020   namespace detail {
0021
0022     template <class BidirectionalIterator>
0023     bool next_combination(BidirectionalIterator first1,
0024                           BidirectionalIterator last1,
0025                           BidirectionalIterator first2,
0026                           BidirectionalIterator last2) {
0027       if ((first1 == last1) || (first2 == last2)) {
0028         return false;
0029       }
0030
0031       BidirectionalIterator m1 = last1;
0032       BidirectionalIterator m2 = last2;
0033       --m2;
0034
0035       // Find first m1 not less than *m2 (i.e., lower_bound(first1, last1, *m2)).
0036       // Actually, this loop stops at one position before that, except perhaps
0037       // if m1 == first1 (in which case one must compare *first1 with *m2).
0038       while (--m1 != first1 && !(*m1 < *m2)) {
0039       }
0040
0041       // Test if all elements in [first1, last1) not less than *m2.
0042       bool result = (m1 == first1) && !(*first1 < *m2);
0043
0044       if (!result) {
0045         // Find first first2 greater than *m1 (since *m1 < *m2, we know it
0046         // can't pass m2 and there's no need to test m2).
0047         while (first2 != m2 && !(*m1 < *first2)) {
0048           ++first2;
0049         }
0050
0051         first1 = m1;
0052         std::iter_swap(first1, first2);
0053         ++first1;
0054         ++first2;
0055       }
0056
0057       // Merge [first1, last1) with [first2, last2), given that the rest of the
0058       // original ranges are sorted and compare appropriately.
0059       if ((first1 != last1) && (first2 != last2)) {
0060         for (m1 = last1, m2 = first2; (m1 != first1) && (m2 != last2); ++m2) {
0061           std::iter_swap(--m1, m2);
0062         }
0063
0064         std::reverse(first1, m1);
0065         std::reverse(first1, last1);
0066
0067         std::reverse(m2, last2);
0068         std::reverse(first2, last2);
0069       }
0070
0071       return !result;
0072     }
0073
0074   }  // namespace detail
0075
0076   /* PROPOSED STANDARD EXTENSIONS:
0077  *
0078  * template<class BidirectionalIterator>
0079  *   bool next_combination(BidirectionalIterator first,
0080  *                         BidirectionalIterator middle,
0081  *                         BidirectionalIterator last);
0082  *
0083  */
0084
0085   template <class BidirectionalIterator>
0086   bool next_combination(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last) {
0087     return detail::next_combination(first, middle, middle, last);
0088   }
0089
0090 }  // namespace notboost
0091
0092 #endif  // NOTBOOST_ALGORITHM_COMBINATION_HPP