To implement pawsort::sort function as a drop-in replacement of std::sort().
Details
- Reviewers
jcmcdonald - Maniphest Tasks
- T762: sort() Function Wrappers
- Commits
- rP52c7c3deae3b: sort() Function wrappers - T762
- sort(first iterator, last iterator) tested with array;
- sort to be tested with another type of container (vector);
- sort() to be completed with all other signatures of std::sort().
Diff Detail
- Repository
- rP PawLIB
- Lint
Lint Not Applicable
Event Timeline
Build is green
Building PawLIB on LittleXenial as build 483.
https://jenkins.mousepawmedia.net:8449/job/pawlib_build/483/ for more details.
pawlib-source/include/pawlib/pawsort.hpp | ||
---|---|---|
634 | Should we have a default value of last that will just sort the entire length of the structure? |
- Created tests for pawsort wrapper.
- Implemented pawsort::sort with iterators. Compilation OK. Tests do not
- Saving files to checkout to master.
- Implemented insertion sort and heap sort to work with iterators.
- Merge branch 'pawsort_wrapper2' into pawsort_wrapper
- pawsort::sort(RandomIt, RandomIt) implemented.
- Refactoring.
- pawsort::sort(RandomIt, RandomIt, Compare) implemented.
Build is green
Building PawLIB on LittleXenial as build 484.
https://jenkins.mousepawmedia.net:8449/job/pawlib_build/484/ for more details.
Build is green
Building PawLIB on LittleXenial as build 485.
https://jenkins.mousepawmedia.net:8449/job/pawlib_build/485/ for more details.
I'll need to pull this down and do some more in-depth checking, but I do know we have a couple of edge-case concerns.
- swap() will not always function correctly if the data type is a pointer; those have to be cast to an integer type first, and then cast back afterwards. There may be some other data types with that limitation. We'll have to decide carefully which can be used with which, and offer some overloaded template swap() functions, which you can do like this...
template <typename T> void someFunction(T a, T b);
#include "example.hpp" template <typename T> void someFunction(T, a, T b) { // Implementation here... } void someFunction<int>(int a, int b); // uses above implementation void someFunction<bool>(bool a, bool b); // uses above implementation // The above implementation ONLY uses the listed types. template <typename T> void someFunction(T a, T b) { // Other implementation here... } void someFunction<float>(int a, int b); // uses above implementaton void someFunction<double>(int a, int b); // uses above implementation // The above implementation ONLY uses the listed types. // It is possible to write another generic templated version of the function that accepts everything else.
- There is a profound difference between an iterator and a pointer. I'm a little hesitant to offer pointer-based sorting directly, as it would be prone to undefined behavior (including segfaults) if the user does something weird. @ankush981 and I have been working on implementing iterators for PawLIB, and there are (of course) the std:: iterators. Your iterator-based functions will need to be rewritten to support those...at least std:: iterators for the moment...perhaps via overloaded templates (see above).
- Introduced median of three function to select pivot.
- Checking whether values at the beginning of the container are at the good place.
Build is green
Building PawLIB on LittleXenial as build 486.
https://jenkins.mousepawmedia.net:8449/job/pawlib_build/486/ for more details.
- Using std::iter_swap which improves sorting.
- introsort calling introsort_loop, increased TINY_SIZE.
- Increased Tiny_SIZE to 125.
- Looking for introsort optimization. TINY_SIZE = 100.
Build is green
Building PawLIB on LittleXenial as build 487.
https://jenkins.mousepawmedia.net:8449/job/pawlib_build/487/ for more details.
Build is green
Building PawLIB on LittleXenial as build 488.
https://jenkins.mousepawmedia.net:8449/job/pawlib_build/488/ for more details.
I'm sorry for the delay on this! I've manually landed it with rP52c7c3deae3b: sort() Function wrappers - T762.