Back to home page

Project CMSSW displayed by LXR

 
 

    


File indexing completed on 2021-02-14 14:26:32

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