1.13.0 — Swimming Pool

A few days ago I went to the swimming pool for the first time since 2015, which might also be the first time since the very first cpp-sort commits. The library is getting old, and while it might be too late to give it a cute name, it is still time to give it a cute logo.

This release focuses on improving the state of function objects in the library in a somewhat holistic way, notably with the addition of flip and not_fn, but also with smaller changes:

• Many more function objects are now transparent or conditionally transparent.
• Several function objects that except a single parameter now inherit from projection_base, which makes them more easily chainable.
• Some comparator adapters were updated to automatically unwrap upon recognizing specific function objects, allowing to reduce template nesting and instantiations.
• The documentation about function objects and related concepts was improved.

New features

New comparator adapters not_fn and flip. The former is equivalent to the C++17 std::not_fn: it takes a comparator and returns a function object of type not_fn_t<F> whose call operator calls the adapted comparator and returns the negation of its result. The latter is named after the flip function from Haskell's Prelude module: it takes a comparator and returns a function object of type flip_t<F> whose call opearator calls the adapted comparator with its arguments flipped. Here is an example of them being used to reimplement std::upper_bound in terms of std::lower_bound:

template<typename ForwardIt, typename T, typename Compare>
auto upper_bound(ForwardIt first, ForwardIt last, const T& value, Compare comp)
    -> ForwardIt
{
    return std::lower_bound(
        first, last, value,
        cppsort::not_fn(cppsort::flip(comp))
    );
}

The function templates flip and not_fn recognize and unwrap some combinations of flip_t, not_fn_t and other "vocabulary types" in function objects. For example flip(flip(std::less{})) returns an instance of std::less<> instead of flip_t<flip_t<std::less<>>>. The goal is to reduce the nesting of templates as well as the number of templates instantiated by the library — which is especially interesting considering that many of the library's internal functions rely on flip and not_fn.

New sorter: adaptive_shivers_sort, a k-aware natural mergesort described by Vincent Jugé in Adaptive Shivers Sort: An Alternative Sorting Algorithm. It is very similar to tim_sort and actually shares most of its code. Adaptive ShiversSort worst case notably performs 33% fewer comparisons that timsort's worse case.

Bug fixes

• When wrapping a non-comparison sorter that accepts projections (such as spread_sorter), indirect_adapter failed to compile if passed a projection but no comparison (issue #204, thanks to @marc1uk for reporting).

Improvements

• sorting_network_sorter now uses one fewer compare-exchange than previously for 21, 22, 23, 25, 27 and 29 inputs thanks to the latest results of SorterHunter.
• The following function objects from <cpp-sort/utility/functional.h> are now unconditionally transparent and inherit from projection_base:
  • utility::half
  • utility::log
  • utility::sqrt
• The objects returned by as_comparison and as_projection as well as the result of chained projections are now transparent when their parameters are also transparent.
• The objects returned by make_projection_compare, as_comparison and as_projection are now default-constructible when the adapted function objects are default-constructible.
• make_projection_compare now returns the passed comparison directly when the passed projection is std::identity or utility::identity. This change can help to reduce the number of template instantiations in generic code. This is potentially a minor breaking change.
• Silence a -Wunused-but-set-variable false positive in pdq_sorter which fired with some versions of MinGW-w64.

Tooling

Documentation:

• The documentation now uses relative links when linking to its own pages instead of absolute links to the online wiki. This makes the documentation more easily browsable in the GitHub repository interface at any point in time.
• It is also now browsable offline with Gollum (issue #198). A new section of the documentation explains how to do it.
• Update the documentation about comparators, create a dedicated page comparator adapters.
• Add a section explaining what transparent function objects are.

Test suite:

• Rename the test suite directory from testsuite to tests, in accordance with the Pitchfork project layout.
• Upgrade Catch2 to v3-preview4.
• New CMake option CPPSORT_STATIC_TESTS: when ON some tests are turned into static_assert and are reported as success if the program compiles. The option defaults to OFF.
• New wiki section to document the concept of transparent function objects.
• Give the [comparison] tag to more tests, unify similar tags.
• Move every_sorter_* tests from the root of the test suite to the sorters subdirectory.

Miscellaneous:

• The project layout is now fully compatible with the Pitchfork project layout.
• Bump codecov-action to v3.
• The action to deploy the documentation to the wiki was updated to stop relying on the unmaintained SwiftDocOrg/github-wiki-publish-action.

Known bugs

I didn't manage to fix every bug I could find since the previous release, so you might want to check the list of known bugs.