Page MenuHomePhabricator

sort() Function wrappers - T762
ClosedPublic

Authored by lulu731 on Sep 20 2018, 1:35 PM.

Details

Summary

To implement pawsort::sort function as a drop-in replacement of std::sort().

Test Plan
  • 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.

Restricted Application completed remote builds in Restricted Buildable.Sep 20 2018, 1:36 PM
jcmcdonald added inline comments.
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?

lulu731 marked an inline comment as done.
  • 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.
Restricted Application completed remote builds in Restricted Buildable.Sep 25 2018, 12:58 PM

Build is green

Building PawLIB on LittleXenial as build 484.

https://jenkins.mousepawmedia.net:8449/job/pawlib_build/484/ for more details.

  • Fixed swap by using XORswapping.
  • Looked for other optimizations without success.

Build is green

Building PawLIB on LittleXenial as build 485.

https://jenkins.mousepawmedia.net:8449/job/pawlib_build/485/ for more details.

Restricted Application completed remote builds in Restricted Buildable.Sep 26 2018, 7:17 AM

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.

  1. 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.
  1. 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.
Restricted Application completed remote builds in Restricted Buildable.Sep 28 2018, 1:51 PM

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.
Restricted Application completed remote builds in Restricted Buildable.Oct 3 2018, 7:10 AM

Build is green

Building PawLIB on LittleXenial as build 487.

https://jenkins.mousepawmedia.net:8449/job/pawlib_build/487/ for more details.

  • Insertion sort implemented as pair insertion sort.

    Updating D244: sort() Function wrappers - T762 Implementing insertion sort as a pair insertion sort improves algo.
Restricted Application completed remote builds in Restricted Buildable.Oct 6 2018, 5:46 AM

Build is green

Building PawLIB on LittleXenial as build 488.

https://jenkins.mousepawmedia.net:8449/job/pawlib_build/488/ for more details.

This revision was not accepted when it landed; it landed in state Needs Review.Nov 28 2019, 11:09 AM
Closed by commit rP52c7c3deae3b: sort() Function wrappers - T762 (authored by lulu731, committed by jcmcdonald). · Explain Why
This revision was automatically updated to reflect the committed changes.

I'm sorry for the delay on this! I've manually landed it with rP52c7c3deae3b: sort() Function wrappers - T762.