Mutable sorters

[Morwenn]

cpp-sort currently gives the middle finger to mutable sorters, which might not be the right reaction to have. It never really mattered because every sorter in the library is immutable. However, we might want to have mutable sorters at some point, for example sorters that can reuse memory instead of allocating new memory whenever they're called. A few design points to take into account:

• Sorter adapters should be able to take sorter instances and use them instead of generating new instances on-the-fly
• Mutable sorters won't convert to function pointers, and sorter_facade wil have to handle that
• A sorter adapter should be made immutable when the adapted sorter is immutable: an std::is_empty check should be enough to guarantee immutability
• If it is not enough, introduce an utility::is_immutable trait which falls back to std::is_empty and can be specialized by users

---

Mutable sorters could allow to pass additional runtime parameters to existing sorter. For example counting_sorter needs one less pass over the collection if the min and max values are known ahead of the sort. They could be passed as follows:

counting_sorter(min, max)(collection);

Such a sorter wouldn't be convertible to a function pointer, but it allows to pass additional runtime parameters to the sorter without having to change the generic sorting interface. Basically: constructor parameters would serve to pass sorter-specific parameters while function-call parameters would serve to pass the generic collection/comparison/projection parameters. Hence mutable sorters are useful.

Another example: one could pass a runtime buffer to merge-sort so that several calls to the algorithm are able to reuse the same memory instead of allocating its own.

---

Usual TODO list:

• Actually store sorters in adapters
• Make sure the instance of a sorter called by a given adapter is always the same
• Make sorter_facade handle mutable sorters
• Make adapters handle mutable sorters when it makes sense
• Handle hybrid_adapter properly
• Add tests
• Update documentation
• Check that examples still work

[Morwenn]

Another problem actually shows up: proper const propagation through sorter adapters and sorter_facade when calling operator(). A first easier step is to handle sorters that carry a state but whose operator() is still const, but the step of actually supporting operator() const seems harder to have without duplicating tons of code.

EDIT: managed to make it with a workaround without duplicating the code. I'm in the process of trying to make the adapters work smoothly with either const or non-const operator() too.

[Morwenn]

Update: while the main design questions are solved, the branch is currently blocked by what appear to be ICE in Clang, no matter what I try. Help wanted to fix the Clang build .___.

[Morwenn]

While mutable sorters are still blocked by the aforementioned issues (ICE and unacceptable compile times), it might be possible to split the features and implement stateful sorters, albeit not allowing them to be modified by the sorting operation. It may solve the compile time issues since we don't have to introduce a double-indirection at every level to handle the const propagation.