Skip to content

Tests with move only types #10

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
gfx merged 2 commits into from
Oct 17, 2015
Merged

Tests with move only types #10

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
2 commits
Select commit Hold shift + click to select a range
16b5c35
Make timsort work with move-only types.
Morwenn Oct 9, 2015
d937471
add tests on move only types for #9
gfx Oct 17, 2015
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
82 changes: 81 additions & 1 deletion test/test.cpp
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -195,7 +195,7 @@ BOOST_AUTO_TEST_CASE( shuffle1023 ) {
}

BOOST_AUTO_TEST_CASE( shuffle1024 ) {
const int size = 1024; // even number of elements
const int size = 1024; // should be even number of elements

std::vector<int> a;
for(int i = 0; i < size; ++i) {
Expand Down Expand Up @@ -539,3 +539,83 @@ BOOST_AUTO_TEST_CASE( issue2_duplication ) {
BOOST_CHECK_EQUAL(a[1001].first, expected[1001].first);
BOOST_CHECK_EQUAL(a[1001].second, expected[1001].second);
}

#if ENABLE_STD_MOVE && __cplusplus >= 201103L
template<typename T>
struct move_only
{
// Constructors

move_only() = delete;
move_only(const move_only&) = delete;

move_only(const T& value):
can_read(true),
value(value)
{}

move_only(move_only&& other):
can_read(true),
value(std::move(other.value))
{
if (not exchange(other.can_read, false))
{
std::cerr << "illegal read from a moved-from value\n";
assert(false);
}
}

// Assignment operators

move_only& operator=(const move_only&) = delete;

auto operator=(move_only&& other)
-> move_only&
{
if (&other != this)
{
if (not exchange(other.can_read, false))
{
std::cerr << "illegal read from a moved-from value\n";
assert(false);
}
can_read = true;
value = std::move(other.value);
}
return *this;
}

// A C++11 backport of std::exchange()

template <typename U> U exchange(U& obj, U&& new_val) {
U old_val = std::move(obj);
obj = std::forward<U>(new_val);
return old_val;
}

// Whether the value can be read
bool can_read;
// Actual value
T value;
};

BOOST_AUTO_TEST_CASE( shuffle10k_for_move_only_types ) {
const int size = 1024 * 10; // should be even number of elements

std::vector<move_only<int>> a;
for(int i = 0; i < size; ++i) {
a.push_back((i+1) * 10);
}

for(int n = 0; n < 100; ++n) {
std::random_shuffle(a.begin(), a.end());

timsort(a.begin(), a.end(), [](const move_only<int>& x, const move_only<int>& y) { return x.value < y.value; });

for(int i = 0; i < size; ++i) {
BOOST_CHECK_EQUAL( a[i].value, (i+1) * 10 );
}
}
}

#endif // if std::move available
64 changes: 35 additions & 29 deletions timsort.hpp
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -44,8 +44,12 @@

#if ENABLE_STD_MOVE && __cplusplus >= 201103L
#define GFX_TIMSORT_MOVE(x) std::move(x)
#define GFX_TIMSORT_MOVE_RANGE(in1, in2, out) std::move((in1), (in2), (out))
#define GFX_TIMSORT_MOVE_BACKWARD(in1, in2, out) std::move_backward((in1), (in2), (out))
#else
#define GFX_TIMSORT_MOVE(x) (x)
#define GFX_TIMSORT_MOVE_RANGE(in1, in2, out) std::copy((in1), (in2), (out))
#define GFX_TIMSORT_MOVE_BACKWARD(in1, in2, out) std::copy_backward((in1), (in2), (out))
#endif

namespace gfx {
Expand Down Expand Up @@ -412,14 +416,14 @@ class TimSort {
iter_t cursor2 = base2;
iter_t dest = base1;

*(dest++) = *(cursor2++);
*(dest++) = GFX_TIMSORT_MOVE(*(cursor2++));
if(--len2 == 0) {
std::copy(cursor1, cursor1 + len1, dest);
GFX_TIMSORT_MOVE_RANGE(cursor1, cursor1 + len1, dest);
return;
}
if(len1 == 1) {
std::copy(cursor2, cursor2 + len2, dest);
*(dest + len2) = *cursor1;
GFX_TIMSORT_MOVE_RANGE(cursor2, cursor2 + len2, dest);
*(dest + len2) = GFX_TIMSORT_MOVE(*cursor1);
return;
}

Expand All @@ -435,7 +439,7 @@ class TimSort {
assert( len1 > 1 && len2 > 0 );

if(comp_.lt(*cursor2, *cursor1)) {
*(dest++) = *(cursor2++);
*(dest++) = GFX_TIMSORT_MOVE(*(cursor2++));
++count2;
count1 = 0;
if(--len2 == 0) {
Expand All @@ -444,7 +448,7 @@ class TimSort {
}
}
else {
*(dest++) = *(cursor1++);
*(dest++) = GFX_TIMSORT_MOVE(*(cursor1++));
++count1;
count2 = 0;
if(--len1 == 1) {
Expand All @@ -462,7 +466,7 @@ class TimSort {

count1 = gallopRight(*cursor2, cursor1, len1, 0);
if(count1 != 0) {
std::copy_backward(cursor1, cursor1 + count1, dest + count1);
GFX_TIMSORT_MOVE_BACKWARD(cursor1, cursor1 + count1, dest + count1);
dest += count1;
cursor1 += count1;
len1 -= count1;
Expand All @@ -472,15 +476,15 @@ class TimSort {
break;
}
}
*(dest++) = *(cursor2++);
*(dest++) = GFX_TIMSORT_MOVE(*(cursor2++));
if(--len2 == 0) {
break_outer = true;
break;
}

count2 = gallopLeft(*cursor1, cursor2, len2, 0);
if(count2 != 0) {
std::copy(cursor2, cursor2 + count2, dest);
GFX_TIMSORT_MOVE_RANGE(cursor2, cursor2 + count2, dest);
dest += count2;
cursor2 += count2;
len2 -= count2;
Expand All @@ -489,7 +493,7 @@ class TimSort {
break;
}
}
*(dest++) = *(cursor1++);
*(dest++) = GFX_TIMSORT_MOVE(*(cursor1++));
if(--len1 == 1) {
break_outer = true;
break;
Expand All @@ -511,14 +515,14 @@ class TimSort {

if(len1 == 1) {
assert( len2 > 0 );
std::copy(cursor2, cursor2 + len2, dest);
*(dest + len2) = *cursor1;
GFX_TIMSORT_MOVE_RANGE(cursor2, cursor2 + len2, dest);
*(dest + len2) = GFX_TIMSORT_MOVE(*cursor1);
}
else {
assert( len1 != 0 && "Comparision function violates its general contract");
assert( len1 != 0 && "Comparison function violates its general contract" );
assert( len2 == 0 );
assert( len1 > 1 );
std::copy(cursor1, cursor1 + len1, dest);
GFX_TIMSORT_MOVE_RANGE(cursor1, cursor1 + len1, dest);
}
}

Expand All @@ -531,16 +535,16 @@ class TimSort {
tmp_iter_t cursor2 = tmp_.begin() + (len2 - 1);
iter_t dest = base2 + (len2 - 1);

*(dest--) = *(cursor1--);
*(dest--) = GFX_TIMSORT_MOVE(*(cursor1--));
if(--len1 == 0) {
std::copy(tmp_.begin(), tmp_.begin() + len2, dest - (len2 - 1));
GFX_TIMSORT_MOVE_RANGE(tmp_.begin(), tmp_.begin() + len2, dest - (len2 - 1));
return;
}
if(len2 == 1) {
dest -= len1;
cursor1 -= len1;
std::copy_backward(cursor1 + 1, cursor1 + (1 + len1), dest + (1 + len1));
*dest = *cursor2;
GFX_TIMSORT_MOVE_BACKWARD(cursor1 + 1, cursor1 + (1 + len1), dest + (1 + len1));
*dest = GFX_TIMSORT_MOVE(*cursor2);
return;
}

Expand All @@ -556,7 +560,7 @@ class TimSort {
assert( len1 > 0 && len2 > 1 );

if(comp_.lt(*cursor2, *cursor1)) {
*(dest--) = *(cursor1--);
*(dest--) = GFX_TIMSORT_MOVE(*(cursor1--));
++count1;
count2 = 0;
if(--len1 == 0) {
Expand All @@ -565,7 +569,7 @@ class TimSort {
}
}
else {
*(dest--) = *(cursor2--);
*(dest--) = GFX_TIMSORT_MOVE(*(cursor2--));
++count2;
count1 = 0;
if(--len2 == 1) {
Expand All @@ -586,14 +590,14 @@ class TimSort {
dest -= count1;
cursor1 -= count1;
len1 -= count1;
std::copy_backward(cursor1 + 1, cursor1 + (1 + count1), dest + (1 + count1));
GFX_TIMSORT_MOVE_BACKWARD(cursor1 + 1, cursor1 + (1 + count1), dest + (1 + count1));

if(len1 == 0) {
break_outer = true;
break;
}
}
*(dest--) = *(cursor2--);
*(dest--) = GFX_TIMSORT_MOVE(*(cursor2--));
if(--len2 == 1) {
break_outer = true;
break;
Expand All @@ -604,13 +608,13 @@ class TimSort {
dest -= count2;
cursor2 -= count2;
len2 -= count2;
std::copy(cursor2 + 1, cursor2 + (1 + count2), dest + 1);
GFX_TIMSORT_MOVE_RANGE(cursor2 + 1, cursor2 + (1 + count2), dest + 1);
if(len2 <= 1) {
break_outer = true;
break;
}
}
*(dest--) = *(cursor1--);
*(dest--) = GFX_TIMSORT_MOVE(*(cursor1--));
if(--len1 == 0) {
break_outer = true;
break;
Expand All @@ -634,21 +638,21 @@ class TimSort {
assert( len1 > 0 );
dest -= len1;
cursor1 -= len1;
std::copy_backward(cursor1 + 1, cursor1 + (1 + len1), dest + (1 + len1));
*dest = *cursor2;
GFX_TIMSORT_MOVE_BACKWARD(cursor1 + 1, cursor1 + (1 + len1), dest + (1 + len1));
*dest = GFX_TIMSORT_MOVE(*cursor2);
}
else {
assert( len2 != 0 && "Comparision function violates its general contract");
assert( len2 != 0 && "Comparison function violates its general contract" );
assert( len1 == 0 );
assert( len2 > 1 );
std::copy(tmp_.begin(), tmp_.begin() + len2, dest - (len2 - 1));
GFX_TIMSORT_MOVE_RANGE(tmp_.begin(), tmp_.begin() + len2, dest - (len2 - 1));
}
}

void copy_to_tmp(iter_t const begin, diff_t const len) {
tmp_.clear();
tmp_.reserve(len);
std::copy(begin, begin + len, std::back_inserter(tmp_));
GFX_TIMSORT_MOVE_RANGE(begin, begin + len, std::back_inserter(tmp_));
}

// the only interface is the friend timsort() function
Expand All @@ -671,5 +675,7 @@ inline void timsort(RandomAccessIterator const first, RandomAccessIterator const

#undef GFX_TIMSORT_LOG
#undef GFX_TIMSORT_MOVE
#undef GFX_TIMSORT_MOVE_RANGE
#undef GFX_TIMSORT_MOVE_BACKWARD
#endif // GFX_TIMSORT_HPP