# Details

- Reviewers
huixie90 jdoerfert philnik ldionne - Group Reviewers
Restricted Project - Commits
- rG68264b649461: [libc++][ranges] Implement `ranges::{prev, next}_permutation`.

# Diff Detail

- Repository
- rG LLVM Github Monorepo

### Event Timeline

libcxx/include/CMakeLists.txt | ||
---|---|---|

116 | could you please update the RangeAlgorithms.csv file? | |

libcxx/include/__algorithm/ranges_prev_permutation.h | ||

41–63 | I think this algorithm is complex enough to reuse the classic one. what do you think? | |

56 |
| |

60 |
| |

libcxx/test/support/test_iterators.h | ||

758 ↗ | (On Diff #444987) | take the arguments by const ref, as |

760 ↗ | (On Diff #444987) | why does the |

- Address comments

libcxx/include/__algorithm/ranges_prev_permutation.h | ||
---|---|---|

41–63 | I think it's harder to combine the two than to use separate ones. The algorithms isn't | |

libcxx/test/support/test_iterators.h | ||

758 ↗ | (On Diff #444987) | Weird that this didn't show in the test. Maybe I just missed it. |

760 ↗ | (On Diff #444987) | Because that would increment the counter two times per swap. |

libcxx/include/CMakeLists.txt | ||
---|---|---|

127 | Looks like this line is unsorted (might be what the CI is complaining about). | |

libcxx/include/__algorithm/ranges_prev_permutation.h | ||

41–63 | I'd also prefer reuse, but don't want to block this patch on this. | |

46 | Nit: can you add a blank line before this line? | |

49 | Nit: blank line above. | |

54 | Nit: blank line above. | |

58 | Nit: blank line above. | |

72 | Nit: move? | |

libcxx/include/algorithm | ||

878 | Please also add the definition of the result types to the synopsis. | |

libcxx/test/std/algorithms/alg.sorting/alg.permutation.generators/ranges.next_permutation.pass.cpp | ||

46 | Does the argument have to be forwarded, perhaps? (here and in the other concept above) | |

64 | There's a bunch of references to | |

122 | Question: why is | |

141 |
| |

libcxx/test/std/algorithms/alg.sorting/alg.permutation.generators/ranges.prev_permutation.pass.cpp | ||

92 | Is the output of | |

libcxx/test/support/test_iterators.h | ||

755 ↗ | (On Diff #445453) | Nit: this creates an object with uninitialized variables ( |

758 ↗ | (On Diff #445453) | Would it be possible to just inherit from |

763 ↗ | (On Diff #445453) | (I wish we had something like |

- Address comments

libcxx/test/std/algorithms/alg.sorting/alg.permutation.generators/ranges.next_permutation.pass.cpp | ||
---|---|---|

46 | I don't think so, since | |

122 | The | |

libcxx/test/std/algorithms/alg.sorting/alg.permutation.generators/ranges.prev_permutation.pass.cpp | ||

92 | Yes, the output is deterministic. This test checks the exact output of | |

libcxx/test/support/test_iterators.h | ||

755 ↗ | (On Diff #445453) | These are uninitialized on purpose. Algorithms aren't allowed to read from a default-constructed allocator and the tests always have to provide one. If these are uninitialized for any reason the constexpr tests will fail. That wouldn't be the case if I value-initialized them. |

758 ↗ | (On Diff #445453) | Inheriting wouldn't work with raw pointers. (inheriting was actually my initial design) |

libcxx/include/__algorithm/ranges_prev_permutation.h | ||
---|---|---|

41–63 | I think we should reuse. Teaching | |

libcxx/test/std/algorithms/alg.sorting/alg.permutation.generators/ranges.prev_permutation.pass.cpp | ||

92 | I think this is a clever way to test this. Maybe a little bit too clever to be the only test we have. I'd be OK with this approach if it were also augmented with a small number (e.g. 10 with boundary conditions) of explicit input/output comparisons. Does that sound reasonable? Also, a comment explaining what the testing methodology here would be really helpful. |

libcxx/test/std/algorithms/alg.sorting/alg.permutation.generators/ranges.prev_permutation.pass.cpp | ||
---|---|---|

92 | I refactored this function into several and added comments. However, it adds a lot of complexity and takes a while to run (I had to increase the number of |

- Make
`ranges::{next,prev}_permutation`delegate to the classic algorithm; - modify the classic
`{next,prev}_permutation`and their dependencies to support`_AlgPolicy`; - refactor and comment the test functions that run all possible permutations of a given sequence;
- increase the
`constexpr`evaluation step limit for the new tests and move the`static_assert`back to`main`like in most other tests; - add test cases with expected output;
- add tests for a custom predicate and a custom projection;
- remove the
`SwapCountingIterator`and replace its usages with the existing`adl::Iterator::TrackSwaps`.

Reduce the input size used for the exhaustive permutation checks to avoid

hitting `constexpr` step limit in Clang; remove the Clang command-line option

because it's unrecognized by GCC.

libcxx/test/std/algorithms/alg.sorting/alg.permutation.generators/ranges.prev_permutation.pass.cpp | ||
---|---|---|

88 | Applies in a few places. |

There are still a few tests for these commented out, e.g. in:

libcxx/test/std/algorithms/ranges_robust_against_dangling.pass.cpp

libcxx/test/std/algorithms/ranges_robust_against_proxy_iterators.pass.cpp

libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp

Thanks! I plan to uncomment any remaining ones in a dedicated patch once all the remaining algorithms land.