1.1.0

This is the last proper C++03 release before moving to C++11: from now on development will mostly target the 2.x version. That said the 1.x branch won't go totally unmaintained either: bugs will still be fixed and new features can still be backported if they are easy enough to implement in C++03.

Projections support

gfx::timsort now supports projections. Originally introduced in the Adobe Source Libraries (ASL), then later picked up by Eric Niebler's for range-v3 before making it all the way to the Ranges TS and C++20, projections are transformations that algorithms apply before examining the values of elements; in timsort a projection is applied to each element to be compared prior to a comparison.

Consider that you've got a collection of strings and want to sort it by string size instead of string contents. You could use a projection as follows:

#include <string>
#include <vector>
#include <gfx/timsort.hpp>

size_t len(const std::string& str) {
    return str.size();
}

// Sort a vector of strings by length
std::vector<std::string> vec;
// ... fill vec ...
gfx::timsort(vec.begin(), vec.end(), std::less<size_t>(), &len);

In C++20 projections (but also comparisons) can be pretty much anything satisfying the std::invocable concept, which means all function-like objects and even pointer to members. The support in gfx::timsort is a bit rougher and projections can only be instances of types callable with parentheses.

Miscellaneous changes

The following changes were also applied to the project:

• Assertions with an assert(xx && yy); pattern were split into assert(xx); assert(yy); to provide more precise diagnostics when something fails.
• When running the testsuite in debug mode through CMake, the flag -Og is now passed to GCC instead of -O0. It was always the intended behaviour but didn't work because of a case bug.
• Some useless files and configuration were removed from the project in an attempt to clean it a bit.

1.0.0

Hi everyone, this release marks a change of maintainers since Goro Fuji (gfx) couldn't take care of the project anymore. I didn't want to let this project go unmaintained so I offered to take care of it.

The interface of the algorithm remains the same as it was and still works with C++98 and newer C++ standards. However the tooling changed significantly, here is a brief list of overarching changes, which will be described with more detail later:

• The project now has numbered releases following semantic versioning, this is logically version 1.0.0.
• The project layout was changed to conform to the Pitchfork Layout.
• The project now has first-class CMake support.
• The test suite has been revamped.

Bug fixes

The following bugs were fixed:

• Fixed support for move-only types.
• Fixed iterator pointing one element before the beginning of the collection in mergeHi: this sometimes caused issues with std::deque or the MSVC STL debug iterators (issue #30).

Improvements to timsort

The following improvements were made to the code of timsort:

• The algorithm now performs fewer comparisons overall (thanks @mitchblank, #24 #26).
• Some copies/moves to the temporary buffer are now faster (thanks @mitchblank for the ideas in #25).
• mergeLo and mergeHi are faster and don't allocate extra memory anymore when one of the runs contains only one element.
• Move semantics support is properly recognized for more compilers.
• Fixed warning -Winline with GCC.
• Fixed warning C4244 with MSVC.
• Fixed warnings about dead code.

The following changes also affect timsort.hpp:

• The macro GFX_TIMSORT_USE_STD_MOVE can be defined to 0 or 1 to disable or enable move semantics support in gfx::timsort. If this macro is not set, we try to enable move semantics when we detect compiler support.
• The logs are enabled only when the macro GFX_TIMSORT_ENABLE_LOG is defined.
• The assertions are enabled only when the macro GFX_TIMSORT_ENABLE_ASSERT is defined (they previously always fired).
• Everything except the gfx::timsort function was placed in a pseudo-private gfx::detail:: namespace.

Tooling

The tooling was significantly changed prior to this release. One of the main changes was to remove the old project's Makefile and to introduce CMake support instead:

• The new CMakeLists.txt exports the INTERFACE target gfx::timsort.
• The tests can be built with -DBUILD_TESTING=ON and run as CTest tests.
• The benchmarks can be built with -DBUILD_BENCHMARKS=ON.
• The tests can be run through with Valgrind with -DGFX_TIMSORT_USE_VALGRIND=ON.
• The tests can be run with sanitizers with -DGFX_TIMSORT_SANITIZE=<comma-separated-list-of-sanitizers>.
• Both C++98 and C++11 tests are run with the appropriate standard.

The tests were partly rewritten:

• They now use Catch2 instead of Boost.Test.
• They were separated in two files: cxx_98_tests.cpp and cxx_11_tests.cpp which should be compiled with C++98 and C++11 respectively.
• The tests for move-only types where updated to detect more problematic scenarios like self-moves.

The continuous integration was also revised:

• It is now based on CMake & CTest instead of make.
• Tests are now run on Linux (with GCC and Clang), OSX (with AppleClang) and Windows (with MSVC and MinGW-w64).
• Some tests are run with either Valgrind, ASAN or UBSAN.

Other miscellaneous changes:

• The examples don't rely on Boost anymore.
• The benchmark in examples/ was moved to benchmarks/.

Original project

This release marks the last commit from the original project before a change of tooling and architecture. After this release, the raw Makefile support will be replaced with CMake support, Boost.Test with Catch2, and the project structure will change a bit.

The algorithm interface itself will remain stable through the new releases: C++ code using gfx::timsort should continue to work.