Boost logo

Boost-Commit :

From: philgarofalo_at_[hidden]
Date: 2007-12-23 22:53:11


Author: pgarofalo
Date: 2007-12-23 22:53:10 EST (Sun, 23 Dec 2007)
New Revision: 42271
URL: http://svn.boost.org/trac/boost/changeset/42271

Log:
Added typename specifier and scope resolutions detail:: for the iterator_trait references and std:: for string and STL predicate references. Also added max_element_if functions from previous old version of minmax.hpp.
Text files modified:
   sandbox/boost/sequence_algo/combinatorial.hpp | 129 ++++++++++++++++++++++++++++++++-------
   1 files changed, 105 insertions(+), 24 deletions(-)

Modified: sandbox/boost/sequence_algo/combinatorial.hpp
==============================================================================
--- sandbox/boost/sequence_algo/combinatorial.hpp (original)
+++ sandbox/boost/sequence_algo/combinatorial.hpp 2007-12-23 22:53:10 EST (Sun, 23 Dec 2007)
@@ -1,6 +1,6 @@
 // combinatorial.h header file - r-permutation and r-combination algorithms ---//
 
-// Copyright © Philip F. Garofalo 2002. All rights reserved.
+// Copyright © Philip F. Garofalo 2008. All rights reserved.
 // Permission to copy, use, modify, sell and distribute this software
 // is granted provided this copyright notice appears in all copies.
 // This software is provided "as is" without express or implied
@@ -44,15 +44,95 @@
 #include <algorithm> // std::sort(), std::rotate(), etc.
 #include <functional> // less<>(), binary_function
 #include <stdexcept> // out_of_range, invalid_argument
+#include <string>
 #include <boost/utility.hpp> // next()
 #include <algorithm.hpp> // is_sorted()
-#include <minmax.hpp> // min/max_element_if()
+#include <minmax.hpp> // formerly contained min/max_element_if()
+
+/* PROPOSED STANDARD EXTENSIONS:
+ *
+ * min_element_if(first, last, predicate)
+ * Effect: returns the smallest element of the subsequence of [first,last)
+ * satisfying the predicate (or last if none)
+ *
+ * min_element_if(first, last, comp, predicate)
+ * Effect: returns the smallest element, for the order comp, of the subsequence
+ * of [first,last) satisfying the predicate (or last if none)
+ *
+ * max_element_if(first, last, predicate)
+ * Effect: returns the largest element of the subsequence of [first,last)
+ * satisfying the predicate (or last if none)
+ *
+ * max_element_if(first, last, comp, predicate)
+ * Effect: returns the largest element, for the order comp, of the subsequence
+ * of [first,last) satisfying the predicate (or last if none)
+ */
+
+ template <class ForwardIter, class UnaryPredicate>
+ ForwardIter
+ min_element_if(ForwardIter first, ForwardIter last, UnaryPredicate cond)
+ {
+ while (first != last && !cond(*first))
+ ++first;
+ if (first == last) return last;
+ ForwardIter min_result = first;
+ while (++first != last)
+ if (cond(*first) && *first < *min_result)
+ min_result = first;
+ return min_result;
+ } // min_element_if
+
+ template <class ForwardIter, class BinaryPredicate, class UnaryPredicate>
+ ForwardIter
+ min_element_if(ForwardIter first, ForwardIter last,
+ BinaryPredicate comp, UnaryPredicate cond)
+ {
+ while (first != last && !cond(*first))
+ ++first;
+ if (first == last) return last;
+ ForwardIter min_result = first;
+ while (++first != last)
+ if (cond(*first) && comp(*first, *min_result))
+ min_result = first;
+ return min_result;
+ } // min_element_if
+
+ template <class ForwardIter, class UnaryPredicate>
+ ForwardIter
+ max_element_if(ForwardIter first, ForwardIter last, UnaryPredicate cond)
+ {
+ while (first != last && !cond(*first))
+ ++first;
+ if (first == last) return last;
+ ForwardIter max_result = first;
+ while (++first != last)
+ if (cond(*first) && *max_result < *first)
+ max_result = first;
+ return max_result;
+ } // max_element_if
+
+ template <class ForwardIter, class BinaryPredicate, class UnaryPredicate>
+ ForwardIter
+ max_element_if(ForwardIter first, ForwardIter last,
+ BinaryPredicate comp, UnaryPredicate cond)
+ {
+ while (first != last && !cond(*first))
+ ++first;
+ if (first == last) return last;
+ ForwardIter max_result = first;
+ while (++first != last)
+ if (cond(*first) && comp(*max_result, *first))
+ max_result = first;
+ return max_result;
+ } // max_element_if
+
 
 namespace boost {
 
     // Binary predicate argument reverser
     
- #define BINFUNC std::binary_function<Predicate::first_argument_type, Predicate::second_argument_type, bool>
+ #define BINFUNC std::binary_function<typename Predicate::first_argument_type,\
+ typename Predicate::second_argument_type, bool>
 
     template <class Predicate>
     class binary_reverse : public BINFUNC
@@ -61,8 +141,9 @@
         const Predicate pred;
     public:
         binary_reverse(const Predicate& x) : pred(x) {}
- BINFUNC::result_type operator()(const BINFUNC::first_argument_type& x,
- const BINFUNC::second_argument_type& y) const
+ typename BINFUNC::result_type operator()(
+ const typename BINFUNC::first_argument_type& x,
+ const typename BINFUNC::second_argument_type& y) const
         {
             return pred(y, x);
         }
@@ -81,7 +162,7 @@
 
     struct combinatorial_range_error : public std::out_of_range
     {
- combinatorial_range_error(const string& func) :
+ combinatorial_range_error(const std::string& func) :
             std::out_of_range(func + ": r is not in range (first, last]")
             { }
     };
@@ -90,7 +171,7 @@
 
     struct combinatorial_sequence_disorder : public std::invalid_argument
     {
- combinatorial_sequence_disorder(const string& func) :
+ combinatorial_sequence_disorder(const std::string& func) :
             std::invalid_argument(func + ": [first, r) is not in order")
             { }
     };
@@ -113,7 +194,7 @@
         next_r_permutation(RandomAccessIterator first, RandomAccessIterator r,
             RandomAccessIterator last)
     {
- typedef typename iterator_traits<RandomAccessIterator>::value_type T;
+ typedef typename detail::iterator_traits<RandomAccessIterator>::value_type T;
 
         if (last - first < 2)
             return false;
@@ -125,7 +206,7 @@
         {
             // find smallest element greater than *i after index i.
             RandomAccessIterator k =
- min_element_if(i + 1, last, bind1st(less<T>(), *i));
+ min_element_if(i + 1, last, std::bind1st(std::less<T>(), *i));
 
             if (k == last) // Didn't find it.
                 if (i == first)
@@ -154,7 +235,7 @@
         next_r_permutation(RandomAccessIterator first, RandomAccessIterator r,
             RandomAccessIterator last, Compare comp)
     {
- typedef typename iterator_traits<RandomAccessIterator>::value_type T;
+ typedef typename detail::iterator_traits<RandomAccessIterator>::value_type T;
      
         if (last - first < 2)
             return false;
@@ -166,7 +247,7 @@
         {
             // find smallest element greater than *i after index i.
             RandomAccessIterator k =
- min_element_if(i + 1, last, comp, bind2nd(reverse_args(comp), *i));
+ min_element_if(i + 1, last, /*comp,*/ std::bind2nd(reverse_args(comp), *i));
 
             if (k == last) // Didn't find it.
                 if (i == first)
@@ -203,7 +284,7 @@
         prev_r_permutation(RandomAccessIterator first, RandomAccessIterator r,
             RandomAccessIterator last)
     {
- typedef typename iterator_traits<RandomAccessIterator>::value_type T;
+ typedef typename detail::iterator_traits<RandomAccessIterator>::value_type T;
 
         if (last - first < 2)
             return false;
@@ -215,12 +296,12 @@
         {
             // find the largest element less than *i after index i.
             RandomAccessIterator k =
- max_element_if(i + 1, last, bind2nd(less<T>(), *i));
+ max_element_if(i + 1, last, std::bind2nd(std::less<T>(), *i));
             
             if (k == last) // Didn't find it.
                 if (i == first)
                 {
- std::partial_sort(first, r, last, reverse_args(less<T>()));
+ std::partial_sort(first, r, last, reverse_args(std::less<T>()));
                     return false; // we're done--end of permutations
                 }
                 else
@@ -228,7 +309,7 @@
             else
             {
                 std::swap(*i,* k);
- std::partial_sort(i+1, r, last, reverse_args(less<T>())); // O(n lg n), heapsort
+ std::partial_sort(i+1, r, last, reverse_args(std::less<T>())); // O(n lg n), heapsort
                 return true;
             } // else
         } // while
@@ -244,7 +325,7 @@
         prev_r_permutation(RandomAccessIterator first, RandomAccessIterator r,
             RandomAccessIterator last, Compare comp)
     {
- typedef typename iterator_traits<RandomAccessIterator>::value_type T;
+ typedef typename detail::iterator_traits<RandomAccessIterator>::value_type T;
 
         if (last - first < 2)
             return false;
@@ -256,7 +337,7 @@
         {
             // find the largest element less than *i after index i.
             RandomAccessIterator k =
- max_element_if(i + 1, last, comp, bind2nd(comp, *i));
+ max_element_if(i + 1, last, /*comp,*/ std::bind2nd(comp, *i));
             
             if (k == last) // Didn't find it.
                 if (i == first)
@@ -293,7 +374,7 @@
         next_r_combination(RandomAccessIterator first, RandomAccessIterator r,
             RandomAccessIterator last)
     {
- typedef typename iterator_traits<RandomAccessIterator>::value_type T;
+ typedef typename detail::iterator_traits<RandomAccessIterator>::value_type T;
 
         if (last - first < 2)
             return false;
@@ -307,7 +388,7 @@
         {
             // find smallest element greater than *i after r - 1.
             RandomAccessIterator j =
- min_element_if(r, last, bind1st(less<T>(), *i));
+ min_element_if(r, last, std::bind1st(std::less<T>(), *i));
             if (j == last)
                 if (i == first)
                 {
@@ -322,7 +403,7 @@
                 for(++i; i < r; i++)
                 {
                     // find smallest element greater than *(i - 1) after r - 1.
- j = min_element_if(r, last, bind1st(less<T>(), *(i - 1)));
+ j = min_element_if(r, last, std::bind1st(std::less<T>(), *(i - 1)));
                     if (j != last)
                         std::swap(*i,* j);
                 } // for
@@ -341,7 +422,7 @@
         next_r_combination(RandomAccessIterator first, RandomAccessIterator r,
             RandomAccessIterator last, Compare comp)
     {
- typedef typename iterator_traits<RandomAccessIterator>::value_type T;
+ typedef typename detail::iterator_traits<RandomAccessIterator>::value_type T;
 
         if (last - first < 2)
             return false;
@@ -355,7 +436,7 @@
         {
             // find smallest element greater than *i after r - 1.
             RandomAccessIterator j =
- min_element_if(r, last, comp, bind2nd(reverse_args(comp), *i));
+ min_element_if(r, last, /*comp,*/ std::bind2nd(reverse_args(comp), *i));
             if (j == last)
                 if (i == first)
                 {
@@ -370,8 +451,8 @@
                 for(++i; i < r; ++i)
                 {
                     // find smallest element greater than *(i - 1) after r - 1.
- j = min_element_if(r, last, comp,
- bind2nd(reverse_args(comp), *(i - 1)));
+ j = min_element_if(r, last, /*comp,*/
+ std::bind2nd(reverse_args(comp), *(i - 1)));
                     if (j != last)
                         std::swap(*i, *j);
                 } // for


Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk