Boost logo

Boost-Commit :

From: philgarofalo_at_[hidden]
Date: 2008-01-01 14:15:32


Author: pgarofalo
Date: 2008-01-01 14:15:31 EST (Tue, 01 Jan 2008)
New Revision: 42399
URL: http://svn.boost.org/trac/boost/changeset/42399

Log:
Changed argument name r to middle.
Text files modified:
   sandbox/boost/sequence_algo/combinatorial.hpp | 160 ++++++++++++++++++++--------------------
   1 files changed, 80 insertions(+), 80 deletions(-)

Modified: sandbox/boost/sequence_algo/combinatorial.hpp
==============================================================================
--- sandbox/boost/sequence_algo/combinatorial.hpp (original)
+++ sandbox/boost/sequence_algo/combinatorial.hpp 2008-01-01 14:15:31 EST (Tue, 01 Jan 2008)
@@ -1,4 +1,4 @@
-// combinatorial.hpp header file - r-permutation and r-combination algorithms
+// combinatorial.hpp header file - partial permutation and partial combination algorithms
 
 // Copyright © Philip F. Garofalo 2008. All rights reserved.
 // Permission to copy, use, modify, sell and distribute this software
@@ -32,10 +32,10 @@
 // renamed the function smallest_greater to min_element_greater than
 // and largest_less to max_element_less_than.
 
-// Jun 27 2002 All functions now throw std::out_of_bounds if r (the iterator
+// Jun 27 2002 All functions now throw std::out_of_bounds if middle (the iterator
 // that points into the middle of the sequence) is not within
 // (first, last]. The combination functions throw std::invalid_argument
-// if the selection [first, r) is not in sorted order. [Phil Garofalo]
+// if the selection [first, middle) is not in sorted order. [Phil Garofalo]
 
 // Jul 01 2002 Replaced about two-thirds of the calls to sort with partial_sort.
 // This should result in a more efficient program. Also introduced
@@ -97,7 +97,7 @@
     struct combinatorial_range_error : public std::out_of_range
     {
         combinatorial_range_error(const std::string& func) :
- std::out_of_range(func + ": r is not in range (first, last]")
+ std::out_of_range(func + ": middle is not in range (first, last]")
             { }
     };
 
@@ -106,19 +106,19 @@
     struct combinatorial_sequence_disorder : public std::invalid_argument
     {
         combinatorial_sequence_disorder(const std::string& func) :
- std::invalid_argument(func + ": [first, r) is not in order")
+ std::invalid_argument(func + ": [first, middle) is not in order")
             { }
     };
     
     // next_partial_permutation -----------------------------------------------//
     
- // Arranges the elements in [first, r), from the larger range [first,
- // last) where first < r <= last, such that they represent the next
- // r-permutation of elements in lexicographical (or dictionary) order.
+ // Arranges the elements in [first, middle), from the larger range [first,
+ // last) where first < middle <= last, such that they represent the next
+ // middle-permutation of elements in lexicographical (or dictionary) order.
     // When calling the function for the first time, the elements in
     // [first, last) should be in ascending lexicographical order to start
     // the permutation sequence at its beginning. Typically, when the function
- // is called it arranges the next r-permutation in [first, r) and returns
+ // is called it arranges the next middle-permutation in [first, middle) and returns
     // true. When the last permutation in lexicographical order is passed in,
     // the function std::sorts the entire range, [first, last) into ascending
     // order, restarting the sequence, and returns false.
@@ -126,16 +126,16 @@
     template<class RandomAccessIterator>
         bool
         next_partial_permutation(RandomAccessIterator first,
- RandomAccessIterator r, RandomAccessIterator last)
+ RandomAccessIterator middle, RandomAccessIterator last)
     {
         typedef typename detail::iterator_traits<RandomAccessIterator>::value_type T;
 
         if (last - first < 2)
             return false;
- if (!(first < r && r <= last))
+ if (!(first < middle && middle <= last))
             throw combinatorial_range_error("next_partial_permutation");
         
- RandomAccessIterator i = r - 1;
+ RandomAccessIterator i = middle - 1;
         while(true)
         {
             // find smallest element greater than *i after index i.
@@ -145,7 +145,7 @@
             if (k == last) // Didn't find it.
                 if (i == first)
                 {
- std::partial_sort(first, r, last);
+ std::partial_sort(first, middle, last);
                     return false; // we're done--end of permutations
                 }
                 else
@@ -153,7 +153,7 @@
             else
             {
                 std::swap(*i, *k);
- std::partial_sort(i + 1, r, last); // O(n lg n), heapsort
+ std::partial_sort(i + 1, middle, last); // O(n lg n), heapsort
                 return true;
             } // else
         } // while
@@ -167,16 +167,16 @@
     template<class RandomAccessIterator, class Compare>
         bool
         next_partial_permutation(RandomAccessIterator first,
- RandomAccessIterator r, RandomAccessIterator last, Compare comp)
+ RandomAccessIterator middle, RandomAccessIterator last, Compare comp)
     {
         typedef typename detail::iterator_traits<RandomAccessIterator>::value_type T;
      
         if (last - first < 2)
             return false;
- if (!(first < r && r <= last))
+ if (!(first < middle && middle <= last))
             throw combinatorial_range_error("next_partial_permutation");
         
- RandomAccessIterator i = r - 1;
+ RandomAccessIterator i = middle - 1;
         while(true)
         {
             // find smallest element greater than *i after index i.
@@ -187,7 +187,7 @@
             if (k == last) // Didn't find it.
                 if (i == first)
                 {
- std::partial_sort(first, r, last, comp);
+ std::partial_sort(first, middle, last, comp);
                     return false; // we're done--end of permutations
                 }
                 else
@@ -195,7 +195,7 @@
             else
             {
                 std::swap(*i, *k);
- std::partial_sort(i + 1, r, last, comp); // O(n lg n), heapsort
+ std::partial_sort(i + 1, middle, last, comp); // O(n lg n), heapsort
                 return true;
             } // else
         } // while
@@ -203,13 +203,13 @@
     
     // prev_partial_permutation -----------------------------------------------//
     
- // Arranges the elements in [first, r), from the larger range [first,
- // last) where first < r <= last, such that they represent the previous
- // r-permutation of elements in lexicographical order. When calling
+ // Arranges the elements in [first, middle), from the larger range [first,
+ // last) where first < middle <= last, such that they represent the previous
+ // middle-permutation of elements in lexicographical order. When calling
     // the function for the first time, the elements in [first, last) should
     // be in descending lexicographical order to start a new series at the
     // end. Typically, when the function is called it arranges the previous
- // r-permutation in [first, r) and returns true. When the first permutation
+ // middle-permutation in [first, middle) and returns true. When the first permutation
     // in lexicographical order is passed in, the function std::sorts the entire
     // range, [first, last) into descending order, restarting the sequence
     // at the end, and returns false.
@@ -217,16 +217,16 @@
     template<class RandomAccessIterator>
         bool
         prev_partial_permutation(RandomAccessIterator first,
- RandomAccessIterator r, RandomAccessIterator last)
+ RandomAccessIterator middle, RandomAccessIterator last)
     {
         typedef typename detail::iterator_traits<RandomAccessIterator>::value_type T;
 
         if (last - first < 2)
             return false;
- if (!(first < r && r <= last))
+ if (!(first < middle && middle <= last))
             throw combinatorial_range_error("prev_partial_permutation");
         
- RandomAccessIterator i = r - 1;
+ RandomAccessIterator i = middle - 1;
         while(true)
         {
             // find the largest element less than *i after index i.
@@ -236,7 +236,7 @@
             if (k == last) // Didn't find it.
                 if (i == first)
                 {
- std::partial_sort(first, r, last,
+ std::partial_sort(first, middle, last,
                         reverse_args(std::less<T>()));
                     return false; // we're done--end of permutations
                 }
@@ -245,7 +245,7 @@
             else
             {
                 std::swap(*i, *k);
- std::partial_sort(i+1, r, last,
+ std::partial_sort(i+1, middle, last,
                     reverse_args(std::less<T>())); // O(n lg n), heapsort
                 return true;
             } // else
@@ -260,16 +260,16 @@
     template<class RandomAccessIterator, class Compare>
         bool
         prev_partial_permutation(RandomAccessIterator first,
- RandomAccessIterator r, RandomAccessIterator last, Compare comp)
+ RandomAccessIterator middle, RandomAccessIterator last, Compare comp)
     {
         typedef typename detail::iterator_traits<RandomAccessIterator>::value_type T;
 
         if (last - first < 2)
             return false;
- if (!(first < r && r <= last))
+ if (!(first < middle && middle <= last))
             throw combinatorial_range_error("prev_partial_permutation");
         
- RandomAccessIterator i = r - 1;
+ RandomAccessIterator i = middle - 1;
         while(true)
         {
             // find the largest element less than *i after index i.
@@ -279,7 +279,7 @@
             if (k == last) // Didn't find it.
                 if (i == first)
                 {
- std::partial_sort(first, r, last,
+ std::partial_sort(first, middle, last,
                         reverse_args(comp));
                     return false; // we're done--end of permutations
                 }
@@ -288,7 +288,7 @@
             else
             {
                 std::swap(*i, *k);
- std::partial_sort(i + 1, r, last,
+ std::partial_sort(i + 1, middle, last,
                     reverse_args(comp)); // O(n lg n), heapsort
                 return true;
             } // else
@@ -298,12 +298,12 @@
     
     // next_partial_combination -----------------------------------------------//
     
- // Arranges the elements in [first, r), from the larger range [first,
- // last) where first < r <= last, such that they represent the next
- // r-combination of elements in lexicographical order. The elements
- // in [first, r) must be in ascending lexicographical order.
+ // Arranges the elements in [first, middle), from the larger range [first,
+ // last) where first < middle <= last, such that they represent the next
+ // middle-combination of elements in lexicographical order. The elements
+ // in [first, middle) must be in ascending lexicographical order.
     // When the function is called and a next combination exists,
- // it arranges the next r-combination in [first, r) and returns true.
+ // it arranges the next middle-combination in [first, middle) and returns true.
     // If the next combination does not exist, the function std::sorts the
     // entire range, [first, last) into ascending order, restarting the
     // sequence, and returns false.
@@ -311,27 +311,27 @@
     template<class RandomAccessIterator>
         bool
         next_partial_combination(RandomAccessIterator first,
- RandomAccessIterator r, RandomAccessIterator last)
+ RandomAccessIterator middle, RandomAccessIterator last)
     {
         typedef typename detail::iterator_traits<RandomAccessIterator>::value_type T;
 
         if (last - first < 2)
             return false;
- if (!(first < r && r <= last))
+ if (!(first < middle && middle <= last))
             throw combinatorial_range_error("next_partial_combination");
- if (!is_sorted(first, r))
+ if (!is_sorted(first, middle))
             throw combinatorial_sequence_disorder("next_partial_combination");
         
- RandomAccessIterator i = r - 1;
+ RandomAccessIterator i = middle - 1;
         while(true)
         {
- // find smallest element greater than *i after r - 1.
+ // find smallest element greater than *i after middle - 1.
             RandomAccessIterator j =
- min_element_if(r, last, std::bind1st(std::less<T>(), *i));
+ min_element_if(middle, last, std::bind1st(std::less<T>(), *i));
             if (j == last)
                 if (i == first)
                 {
- std::partial_sort(first, r, last);
+ std::partial_sort(first, middle, last);
                     return false;
                 }
                 else
@@ -339,10 +339,10 @@
             else
             {
                 std::swap(*i, *j);
- for(++i; i < r; ++i)
+ for(++i; i < middle; ++i)
                 {
- // find smallest element greater than *(i - 1) after r - 1.
- j = min_element_if(r, last,
+ // find smallest element greater than *(i - 1) after middle - 1.
+ j = min_element_if(middle, last,
                         std::bind1st(std::less<T>(), *(i - 1)));
                     if (j != last)
                         std::swap(*i,* j);
@@ -360,28 +360,28 @@
     template<class RandomAccessIterator, class Compare>
         bool
         next_partial_combination(RandomAccessIterator first,
- RandomAccessIterator r, RandomAccessIterator last, Compare comp)
+ RandomAccessIterator middle, RandomAccessIterator last, Compare comp)
     {
         typedef typename detail::iterator_traits<RandomAccessIterator>::value_type T;
 
         if (last - first < 2)
             return false;
- if (!(first < r && r <= last))
+ if (!(first < middle && middle <= last))
             throw combinatorial_range_error("next_partial_combination");
- if (!is_sorted(first, r, comp))
+ if (!is_sorted(first, middle, comp))
             throw combinatorial_sequence_disorder("next_partial_combination");
         
- RandomAccessIterator i = r - 1;
+ RandomAccessIterator i = middle - 1;
         while(true)
         {
- // find smallest element greater than *i after r - 1.
+ // find smallest element greater than *i after middle - 1.
             RandomAccessIterator j =
- min_element_if(r, last, comp,
+ min_element_if(middle, last, comp,
                 std::bind2nd(reverse_args(comp), *i));
             if (j == last)
                 if (i == first)
                 {
- std::partial_sort(first, r, last, comp);
+ std::partial_sort(first, middle, last, comp);
                     return false;
                 }
                 else
@@ -389,10 +389,10 @@
             else
             {
                 std::swap(*i, *j);
- for(++i; i < r; ++i)
+ for(++i; i < middle; ++i)
                 {
- // find smallest element greater than *(i - 1) after r - 1.
- j = min_element_if(r, last, comp,
+ // find smallest element greater than *(i - 1) after middle - 1.
+ j = min_element_if(middle, last, comp,
                         std::bind2nd(reverse_args(comp), *(i - 1)));
                     if (j != last)
                         std::swap(*i, *j);
@@ -405,39 +405,39 @@
     
     // prev_partial_combination -----------------------------------------------//
     
- // Arranges the elements in [first, r), from the larger range [first,
- // last) where first < r <= last, such that they represent the
- // previous r-combination of elements in lexicographical order.
- // The elements in [first, r) must be in ascending lexicographical
+ // Arranges the elements in [first, middle), from the larger range [first,
+ // last) where first < middle <= last, such that they represent the
+ // previous middle-combination of elements in lexicographical order.
+ // The elements in [first, middle) must be in ascending lexicographical
     // order. When the function is called and a prior combination exists,
- // it arranges the previous r-combination in [first, r) and returns
+ // it arranges the previous middle-combination in [first, middle) and returns
     // true. If the prior combination does not exist, the function
- // arranges the sequence [first, last) into the last r-combination,
+ // arranges the sequence [first, last) into the last middle-combination,
     // thus restarting the sequence at the end, and returns false.
     
     template<class RandomAccessIterator>
         bool
         prev_partial_combination(RandomAccessIterator first,
- RandomAccessIterator r, RandomAccessIterator last)
+ RandomAccessIterator middle, RandomAccessIterator last)
     {
         if (last - first < 2)
             return false;
- if (!(first < r && r <= last))
+ if (!(first < middle && middle <= last))
             throw combinatorial_range_error("prev_partial_combination");
- if (!is_sorted(first, r))
+ if (!is_sorted(first, middle))
             throw combinatorial_sequence_disorder("prev_partial_combination");
 
- std::sort(r, last);
- for (RandomAccessIterator i = last - 1; i >= r; --i)
- for (RandomAccessIterator j = first; j < r; ++j)
+ std::sort(middle, last);
+ for (RandomAccessIterator i = last - 1; i >= middle; --i)
+ for (RandomAccessIterator j = first; j < middle; ++j)
                 if (*i < *j)
                 {
                     std::swap(*j, *i);
                     std::sort(++j, last); // O(n lg n)
- std::rotate(j, j + (last - r), last); // 2*[n/2]+[m/2]+[(n-m)/2] exchanges
+ std::rotate(j, j + (last - middle), last); // 2*[n/2]+[m/2]+[(n-m)/2] exchanges
                     return true;
                 } // if
- std::rotate(first, first + (last - r), last);
+ std::rotate(first, first + (last - middle), last);
         return false;
     } // prev_partial_combination
     
@@ -449,26 +449,26 @@
     template<class RandomAccessIterator, class Compare>
         bool
         prev_partial_combination(RandomAccessIterator first,
- RandomAccessIterator r, RandomAccessIterator last, Compare comp)
+ RandomAccessIterator middle, RandomAccessIterator last, Compare comp)
     {
         if (last - first < 2)
             return false;
- if (!(first < r && r <= last))
+ if (!(first < middle && middle <= last))
             throw combinatorial_range_error("prev_partial_combination");
- if (!is_sorted(first, r, comp))
+ if (!is_sorted(first, middle, comp))
             throw combinatorial_sequence_disorder("prev_partial_combination");
 
- std::sort(r, last, comp);
- for (RandomAccessIterator i = last - 1; i >= r; i--)
- for (RandomAccessIterator j = first; j < r; j++)
+ std::sort(middle, last, comp);
+ for (RandomAccessIterator i = last - 1; i >= middle; i--)
+ for (RandomAccessIterator j = first; j < middle; j++)
                 if (comp(*i, *j))
                 {
                     std::swap(*j, *i);
                     std::sort(++j, last, comp); // O(n lg n)
- std::rotate(j, last - (r - j), last); // 2*[n/2]+[m/2]+[(n-m)/2] exchanges
+ std::rotate(j, last - (middle - j), last); // 2*[n/2]+[m/2]+[(n-m)/2] exchanges
                     return true;
                 } // if
- std::rotate(first, first + (last - r), last);
+ std::rotate(first, first + (last - middle), last);
         return false;
     } // prev_partial_combination
     


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