Title
ranges permutation generators discard useful information
Status
new
Section
[alg.permutation.generators]
Submitter
Casey Carter

Created on 2018-11-26.00:00:00, last changed 2018-11-27.00:14:47.

Messages

Date: 2018-11-27.00:14:47

Proposed resolution:

This wording is relative to the post-San Diego working draft.

  1. Modify [algorithm.syn] as follows:

      // [alg.permutation.generators], permutations
      template<class BidirectionalIterator>
        constexpr bool next_permutation(BidirectionalIterator first,
                                        BidirectionalIterator last);
      template<class BidirectionalIterator, class Compare>
        constexpr bool next_permutation(BidirectionalIterator first,
                                        BidirectionalIterator last, Compare comp);
    
      namespace ranges {
        template<class I>
        struct next_permutation_result {
          bool found;
          I in;
        };
    
        template<BidirectionalIterator I, Sentinel<I> S, class Comp = ranges::less<>,
                 class Proj = identity>
          requires Sortable<I, Comp, Proj>
          constexpr boolnext_permutation_result<I>
            next_permutation(I first, S last, Comp comp = {}, Proj proj = {});
        template<BidirectionalRange R, class Comp = ranges::less<>,
                 class Proj = identity>
          requires Sortable<iterator_t<R>, Comp, Proj>
          constexpr boolnext_permutation_result<I>
            next_permutation(R&& r, Comp comp = {}, Proj proj = {});
      }
    
      template<class BidirectionalIterator>
        constexpr bool prev_permutation(BidirectionalIterator first,
                                        BidirectionalIterator last);
      template<class BidirectionalIterator, class Compare>
        constexpr bool prev_permutation(BidirectionalIterator first,
                                        BidirectionalIterator last, Compare comp);
    
      namespace ranges {
        template<class I>
        using prev_permutation_result = next_permutation_result<I>;
    
        template<BidirectionalIterator I, Sentinel<I> S, class Comp = ranges::less<>,
                 class Proj = identity>
          requires Sortable<I, Comp, Proj>
          constexpr boolprev_permutation_result<I>
            prev_permutation(I first, S last, Comp comp = {}, Proj proj = {});
        template<BidirectionalRange R, class Comp = ranges::less<>,
                 class Proj = identity>
          requires Sortable<iterator_t<R>, Comp, Proj>
          constexpr boolprev_permutation_result<I>
            prev_permutation(R&& r, Comp comp = {}, Proj proj = {});
      }
    }
    
  2. Modify [alg.permutation.generators] as follows:

    template<class BidirectionalIterator>
      constexpr bool next_permutation(BidirectionalIterator first,
                                      BidirectionalIterator last);
    template<class BidirectionalIterator, class Compare>
      constexpr bool next_permutation(BidirectionalIterator first,
                                      BidirectionalIterator last, Compare comp);
    
    namespace ranges {
      template<BidirectionalIterator I, Sentinel<I> S, class Comp = ranges::less<>,
               class Proj = identity>
        requires Sortable<I, Comp, Proj>
        constexpr boolnext_permutation_result<I>
          next_permutation(I first, S last, Comp comp = {}, Proj proj = {});
      template<BidirectionalRange R, class Comp = ranges::less<>,
               class Proj = identity>
        requires Sortable<iterator_t<R>, Comp, Proj>
        constexpr boolnext_permutation_result<I>
          next_permutation(R&& r, Comp comp = {}, Proj proj = {});
    }
    
    […]

    4 Returns: Let B be true if and only if a next permutation was found and otherwise false. Returns:

    • B for the overloads in namespace std, or

    • { B, last } for the overloads in namespace ranges.

    5 Complexity: […]

    template<class BidirectionalIterator>
      constexpr bool prev_permutation(BidirectionalIterator first,
                                      BidirectionalIterator last);
    template<class BidirectionalIterator, class Compare>
      constexpr bool prev_permutation(BidirectionalIterator first,
                                      BidirectionalIterator last, Compare comp);
    
    namespace ranges {
      template<BidirectionalIterator I, Sentinel<I> S, class Comp = ranges::less<>,
               class Proj = identity>
        requires Sortable<I, Comp, Proj>
        constexpr boolprev_permutation_result<I>
          prev_permutation(I first, S last, Comp comp = {}, Proj proj = {});
      template<BidirectionalRange R, class Comp = ranges::less<>,
               class Proj = identity>
        requires Sortable<iterator_t<R>, Comp, Proj>
        constexpr boolprev_permutation_result<I>
          prev_permutation(R&& r, Comp comp = {}, Proj proj = {});
    }
    
    […]

    9 Returns: Let B be true if and only if a previous permutation was found and otherwise false. Returns:

    • B for the overloads in namespace std, or

    • { B, last } for the overloads in namespace ranges.

    10 Complexity: […]

Date: 2018-11-26.00:00:00

In the Ranges design, algorithms that necessarily traverse an entire range - consequently discovering the end iterator value - return that iterator value unless the algorithm's sole purpose is to return a derived value, for example, ranges::count. ranges::next_permutation and ranges::prev_permutation necessarily traverse the entirety of their range argument, but are currently specified to discard the end iterator value and return only a bool indicating whether they found a next (respectively previous) permutation or "reset" the range to the first (respectively last) permutation. They should instead return an aggregate composed of both that bool and the end iterator value to be consistent with the other range algorithms.

History
Date User Action Args
2018-11-27 00:14:47adminsetmessages: + msg10231
2018-11-26 00:00:00admincreate