To implement pawsort::sort function as a drop-in replacement of std::sort().
Details
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
Diff Detail
- Repository
- rP PawLIB
- Lint
Lint Not Applicable
Event Timeline
Comment Actions
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? | |
Comment Actions
- 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.
Comment Actions
Build is green
Building PawLIB on LittleXenial as build 484.
https://jenkins.mousepawmedia.net:8449/job/pawlib_build/484/ for more details.
Comment Actions
Build is green
Building PawLIB on LittleXenial as build 485.
https://jenkins.mousepawmedia.net:8449/job/pawlib_build/485/ for more details.
Comment Actions
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...
NOTE: Below was just done off of memory, so some of the finer points of syntax might be wrong. Check iochannel.hpp and iochannel.cpp for a whole slew of examples of this at work!
example.hpp
template <typename T> void someFunction(T a, T b);
example.cpp
#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).
Comment Actions
- Introduced median of three function to select pivot.
- Checking whether values at the beginning of the container are at the good place.
Comment Actions
Build is green
Building PawLIB on LittleXenial as build 486.
https://jenkins.mousepawmedia.net:8449/job/pawlib_build/486/ for more details.
Comment Actions
- 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.
Comment Actions
Build is green
Building PawLIB on LittleXenial as build 487.
https://jenkins.mousepawmedia.net:8449/job/pawlib_build/487/ for more details.
Comment Actions
Build is green
Building PawLIB on LittleXenial as build 488.
https://jenkins.mousepawmedia.net:8449/job/pawlib_build/488/ for more details.
Comment Actions
I'm sorry for the delay on this! I've manually landed it with rP52c7c3deae3b: sort() Function wrappers - T762.