284 lines
11 KiB
C++
284 lines
11 KiB
C++
//////////////////////////////////////////////////////////////////////////////
|
|
//
|
|
// (C) Copyright Ion Gaztanaga 2016-2016.
|
|
// Distributed under the Boost Software License, Version 1.0.
|
|
// (See accompanying file LICENSE_1_0.txt or copy at
|
|
// http://www.boost.org/LICENSE_1_0.txt)
|
|
//
|
|
// See http://www.boost.org/libs/move for documentation.
|
|
//
|
|
//////////////////////////////////////////////////////////////////////////////
|
|
|
|
//#define BOOST_MOVE_ADAPTIVE_SORT_INVARIANTS
|
|
#define BOOST_MOVE_ADAPTIVE_SORT_STATS
|
|
|
|
#include "order_type.hpp"
|
|
|
|
#include <iostream> //std::cout
|
|
#include <boost/config.hpp>
|
|
|
|
#include <boost/move/algo/detail/adaptive_sort_merge.hpp>
|
|
#include <boost/move/core.hpp>
|
|
#include <boost/move/unique_ptr.hpp>
|
|
#include <boost/move/make_unique.hpp>
|
|
|
|
#include <boost/move/detail/type_traits.hpp>
|
|
#include <boost/core/lightweight_test.hpp>
|
|
|
|
#include <cstddef>
|
|
|
|
const std::size_t BlockSize = 7u;
|
|
|
|
#if defined(BOOST_MSVC)
|
|
#pragma warning (disable : 4267)
|
|
#endif
|
|
|
|
|
|
const std::size_t left_merge = 0;
|
|
const std::size_t buf_merge = 1;
|
|
const std::size_t unbuf_merge= 2;
|
|
const std::size_t max_merge = 3;
|
|
|
|
template<class Op>
|
|
void alternating_test(
|
|
const std::size_t NumBlocksA,
|
|
const std::size_t NumBlocksB,
|
|
const std::size_t ExtraA,
|
|
const std::size_t ExtraB,
|
|
Op op)
|
|
{
|
|
using namespace boost::movelib::detail_adaptive;
|
|
|
|
|
|
const std::size_t DataSize = ExtraA + NumBlocksA*BlockSize + NumBlocksB*BlockSize + ExtraB;
|
|
const std::size_t KeySize = NumBlocksA + NumBlocksB + 1;
|
|
const std::size_t HdrSize = BlockSize + KeySize;
|
|
const std::size_t ArraySize = HdrSize + DataSize;
|
|
|
|
boost::movelib::unique_ptr<order_move_type[]> testarray(boost::movelib::make_unique<order_move_type[]>(ArraySize));
|
|
|
|
|
|
for(std::size_t szt_merge = 0; szt_merge != max_merge; ++szt_merge){
|
|
//Order keys
|
|
for (std::size_t szt_i = 0u; szt_i != KeySize; ++szt_i) {
|
|
testarray[szt_i].key = szt_i;
|
|
testarray[szt_i].val = std::size_t(-1);
|
|
}
|
|
|
|
//Order buffer
|
|
for (std::size_t szt_i = 0u; szt_i != BlockSize; ++szt_i) {
|
|
testarray[KeySize+szt_i].key = std::size_t(-1);
|
|
testarray[KeySize+szt_i].val = szt_i;
|
|
}
|
|
|
|
//Block A
|
|
std::size_t szt_k = 0;
|
|
for (std::size_t szt_i = 0u; szt_i != ExtraA; ++szt_i) {
|
|
testarray[HdrSize+szt_k].key = (szt_k/2)*2;
|
|
testarray[HdrSize+szt_k].val = szt_k & 1;
|
|
++szt_k;
|
|
}
|
|
|
|
for (std::size_t szt_b = 0u; szt_b != NumBlocksA; ++szt_b)
|
|
for (std::size_t szt_i = 0u; szt_i != BlockSize; ++szt_i) {
|
|
testarray[HdrSize+szt_k].key = (szt_k/2)*2;
|
|
testarray[HdrSize+szt_k].val = szt_k & 1;
|
|
++szt_k;
|
|
}
|
|
|
|
//Block B
|
|
std::size_t szt_l = 0;
|
|
for (std::size_t szt_b = 0u, szt_t = 0; szt_b != NumBlocksB; ++szt_b)
|
|
for (std::size_t szt_i = 0u; szt_i != BlockSize; ++szt_i, ++szt_t) {
|
|
testarray[HdrSize+szt_k].key = (szt_l/2)*2+1;
|
|
testarray[HdrSize+szt_k].val = szt_l & 1;
|
|
++szt_k;
|
|
++szt_l;
|
|
}
|
|
|
|
for (std::size_t szt_i = 0u; szt_i != ExtraB; ++szt_i) {
|
|
testarray[HdrSize+szt_k].key = (szt_l/2)*2+1;
|
|
testarray[HdrSize+szt_k].val = szt_l & 1;
|
|
++szt_k;
|
|
++szt_l;
|
|
}
|
|
|
|
if(szt_merge == left_merge){
|
|
//Merge Left
|
|
op_merge_blocks_left
|
|
( testarray.get(), order_type_less()
|
|
, testarray.get()+HdrSize, BlockSize, ExtraA, NumBlocksA, NumBlocksB, ExtraB
|
|
, order_type_less(), op );
|
|
BOOST_TEST( is_order_type_ordered(testarray.get()+KeySize, DataSize) );
|
|
BOOST_TEST( is_key(testarray.get(), KeySize) );
|
|
BOOST_TEST(( !boost::move_detail::is_same<Op, boost::movelib::swap_op>::value
|
|
|| is_buffer(testarray.get()+ KeySize+DataSize, BlockSize) ));
|
|
}
|
|
else if(szt_merge == buf_merge){
|
|
//Merge with buf
|
|
op_merge_blocks_with_buf
|
|
( testarray.get(), order_type_less()
|
|
, testarray.get()+HdrSize, BlockSize, ExtraA, NumBlocksA, NumBlocksB, ExtraB
|
|
, order_type_less(), op, testarray.get()+KeySize );
|
|
BOOST_TEST( is_order_type_ordered(testarray.get()+HdrSize, DataSize) );
|
|
BOOST_TEST( is_key(testarray.get(), KeySize) );
|
|
BOOST_TEST(( !boost::move_detail::is_same<Op, boost::movelib::swap_op>::value
|
|
|| is_buffer(testarray.get()+ KeySize, BlockSize) ));
|
|
}
|
|
else if(szt_merge == unbuf_merge){
|
|
//Merge Left
|
|
merge_blocks_bufferless
|
|
( testarray.get(), order_type_less()
|
|
, testarray.get()+HdrSize, BlockSize, ExtraA, NumBlocksA, NumBlocksB, ExtraB
|
|
, order_type_less());
|
|
BOOST_TEST( is_order_type_ordered(testarray.get()+HdrSize, DataSize) );
|
|
BOOST_TEST( is_key(testarray.get(), KeySize) );
|
|
BOOST_TEST(( !boost::move_detail::is_same<Op, boost::movelib::swap_op>::value
|
|
|| is_buffer(testarray.get()+ KeySize, BlockSize) ));
|
|
}
|
|
}
|
|
}
|
|
|
|
int main()
|
|
{
|
|
{
|
|
const std::size_t NumBlocksA = 3u;
|
|
const std::size_t NumBlocksB = 3u;
|
|
const std::size_t ExtraA = BlockSize/2;
|
|
const std::size_t ExtraB = ExtraA;
|
|
alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::move_op());
|
|
alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::swap_op());
|
|
}
|
|
{
|
|
const std::size_t NumBlocksA = 3u;
|
|
const std::size_t NumBlocksB = 3u;
|
|
const std::size_t ExtraA = 0u;
|
|
const std::size_t ExtraB = BlockSize/2;
|
|
alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::move_op());
|
|
alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::swap_op());
|
|
}
|
|
{
|
|
const std::size_t NumBlocksA = 3u;
|
|
const std::size_t NumBlocksB = 3u;
|
|
const std::size_t ExtraA = BlockSize/2;
|
|
const std::size_t ExtraB = 0;
|
|
alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::move_op());
|
|
alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::swap_op());
|
|
}
|
|
{
|
|
const std::size_t NumBlocksA = 3u;
|
|
const std::size_t NumBlocksB = 3u;
|
|
const std::size_t ExtraA = 0;
|
|
const std::size_t ExtraB = 0;
|
|
alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::move_op());
|
|
alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::swap_op());
|
|
}
|
|
{
|
|
const std::size_t NumBlocksA = 6u;
|
|
const std::size_t NumBlocksB = 3u;
|
|
const std::size_t ExtraA = BlockSize/2;
|
|
const std::size_t ExtraB = ExtraA;
|
|
alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::move_op());
|
|
alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::swap_op());
|
|
}
|
|
{
|
|
const std::size_t NumBlocksA = 6u;
|
|
const std::size_t NumBlocksB = 3u;
|
|
const std::size_t ExtraA = BlockSize/2;
|
|
const std::size_t ExtraB = 0;
|
|
alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::move_op());
|
|
alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::swap_op());
|
|
}
|
|
{
|
|
const std::size_t NumBlocksA = 3u;
|
|
const std::size_t NumBlocksB = 5u;
|
|
const std::size_t ExtraA = BlockSize/2;
|
|
const std::size_t ExtraB = ExtraA;
|
|
alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::move_op());
|
|
alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::swap_op());
|
|
}
|
|
{
|
|
const std::size_t NumBlocksA = 3u;
|
|
const std::size_t NumBlocksB = 5u;
|
|
const std::size_t ExtraA = BlockSize/2;
|
|
const std::size_t ExtraB = 0;
|
|
alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::move_op());
|
|
alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::swap_op());
|
|
}
|
|
{
|
|
const std::size_t NumBlocksA = 0u;
|
|
const std::size_t NumBlocksB = 0u;
|
|
const std::size_t ExtraA = 0;
|
|
const std::size_t ExtraB = 0;
|
|
alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::move_op());
|
|
alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::swap_op());
|
|
}
|
|
{
|
|
const std::size_t NumBlocksA = 0u;
|
|
const std::size_t NumBlocksB = 0u;
|
|
const std::size_t ExtraA = BlockSize/2;
|
|
const std::size_t ExtraB = 0;
|
|
alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::move_op());
|
|
alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::swap_op());
|
|
}
|
|
{
|
|
const std::size_t NumBlocksA = 0u;
|
|
const std::size_t NumBlocksB = 0u;
|
|
const std::size_t ExtraA = 0;
|
|
const std::size_t ExtraB = BlockSize/2;
|
|
alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::move_op());
|
|
alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::swap_op());
|
|
}
|
|
//
|
|
{
|
|
const std::size_t NumBlocksA = 0u;
|
|
const std::size_t NumBlocksB = 1u;
|
|
const std::size_t ExtraA = 0;
|
|
const std::size_t ExtraB = 0;
|
|
alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::move_op());
|
|
alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::swap_op());
|
|
}
|
|
{
|
|
const std::size_t NumBlocksA = 1u;
|
|
const std::size_t NumBlocksB = 0u;
|
|
const std::size_t ExtraA = 0;
|
|
const std::size_t ExtraB = 0;
|
|
alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::move_op());
|
|
alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::swap_op());
|
|
}
|
|
{
|
|
const std::size_t NumBlocksA = 1u;
|
|
const std::size_t NumBlocksB = 0u;
|
|
const std::size_t ExtraA = BlockSize/2;
|
|
const std::size_t ExtraB = 0;
|
|
alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::move_op());
|
|
alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::swap_op());
|
|
}
|
|
{
|
|
const std::size_t NumBlocksA = 0u;
|
|
const std::size_t NumBlocksB = 1u;
|
|
const std::size_t ExtraA = BlockSize/2;
|
|
const std::size_t ExtraB = 0;
|
|
alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::move_op());
|
|
alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::swap_op());
|
|
}
|
|
{
|
|
const std::size_t NumBlocksA = 1u;
|
|
const std::size_t NumBlocksB = 0u;
|
|
const std::size_t ExtraA = 0;
|
|
const std::size_t ExtraB = BlockSize/2;
|
|
alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::move_op());
|
|
alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::swap_op());
|
|
}
|
|
{
|
|
const std::size_t NumBlocksA = 0u;
|
|
const std::size_t NumBlocksB = 1u;
|
|
const std::size_t ExtraA = 0;
|
|
const std::size_t ExtraB = BlockSize/2;
|
|
alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::move_op());
|
|
alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::swap_op());
|
|
}
|
|
|
|
return ::boost::report_errors();
|
|
}
|