[ceph.git] / ceph / src / boost / libs / algorithm / test / sort_subrange_test.cpp

#include <boost/config.hpp>
#include <boost/algorithm/sort_subrange.hpp>
#include <boost/algorithm/cxx11/is_sorted.hpp>

#define BOOST_TEST_MAIN
#include <boost/test/unit_test.hpp>

#include <vector>
#include <iostream>

#if (__cplusplus >= 201103L) || defined(BOOST_NO_CXX98_RANDOM_SHUFFLE)
#include <random>

std::default_random_engine gen;
template<typename RandomIt>
void do_shuffle(RandomIt first, RandomIt last)
{ std::shuffle(first, last, gen); }
#else
template<typename RandomIt>
void do_shuffle(RandomIt first, RandomIt last)
{ std::random_shuffle(first, last); }
#endif

namespace ba = boost::algorithm;

template <typename Iter>
void check_sequence ( Iter first, Iter last, Iter sf, Iter sl )
{
	if (sf == sl) return;
	for (Iter i = first; i < sf; ++i)
		BOOST_CHECK(*i < *sf);
	BOOST_CHECK(ba::is_sorted(sf, sl));
	for (Iter i = sl; i < last; ++i)
		BOOST_CHECK(*(sl-1) < *i);
}

template <typename Iter, typename Pred>
void check_sequence ( Iter first, Iter last, Iter sf, Iter sl, Pred p )
{
	if (sf == sl) return;
	for (Iter i = first; i < sf; ++i)
		BOOST_CHECK(p(*i, *sf));
	BOOST_CHECK(ba::is_sorted(sf, sl, p));
	for (Iter i = sl; i < last; ++i)
		BOOST_CHECK(p(*(sl-1), *i));

}

// 	for ( int i = 0; i < v.size(); ++i )
// 		std::cout << v[i] << ' ';
// 	std::cout << std::endl;


BOOST_AUTO_TEST_CASE( test_main )
{
	{
	std::vector<int> v;
	for ( int i = 0; i < 10; ++i )
		v.push_back(i);

	const std::vector<int>::iterator b = v.begin();
	ba::sort_subrange(b, v.end(), b + 3, b + 6);
	check_sequence   (b, v.end(), b + 3, b + 6);

	BOOST_CHECK_EQUAL(v[3], 3);
	BOOST_CHECK_EQUAL(v[4], 4);
	BOOST_CHECK_EQUAL(v[5], 5);

//	Mix them up and try again - single element
	do_shuffle(v.begin(), v.end());
	ba::sort_subrange(b, v.end(), b + 7, b + 8);
	check_sequence   (b, v.end(), b + 7, b + 8);

	BOOST_CHECK_EQUAL(v[7], 7);

//	Mix them up and try again - at the end
	do_shuffle(v.begin(), v.end());
	ba::sort_subrange(b, v.end(), b + 7, v.end());
	check_sequence   (b, v.end(), b + 7, v.end());

	BOOST_CHECK_EQUAL(v[7], 7);
	BOOST_CHECK_EQUAL(v[8], 8);
	BOOST_CHECK_EQUAL(v[9], 9);

//	Mix them up and try again - at the beginning
	do_shuffle(v.begin(), v.end());
	ba::sort_subrange(b, v.end(), b, b + 2);
	check_sequence   (b, v.end(), b, b + 2);

	BOOST_CHECK_EQUAL(v[0], 0);
	BOOST_CHECK_EQUAL(v[1], 1);

//	Mix them up and try again - empty subrange
	do_shuffle(v.begin(), v.end());
	ba::sort_subrange(b, v.end(), b, b);
	check_sequence   (b, v.end(), b, b);

//	Mix them up and try again - entire subrange
	do_shuffle(v.begin(), v.end());
	ba::sort_subrange(b, v.end(), b, v.end());
	check_sequence   (b, v.end(), b, v.end());
	}

	{
	std::vector<int> v;
	for ( int i = 0; i < 10; ++i )
		v.push_back(i);

	const std::vector<int>::iterator b = v.begin();
	ba::sort_subrange(b, v.end(), b + 3, b + 6, std::greater<int>());
	check_sequence   (b, v.end(), b + 3, b + 6, std::greater<int>());

	BOOST_CHECK_EQUAL(v[3], 6);
	BOOST_CHECK_EQUAL(v[4], 5);
	BOOST_CHECK_EQUAL(v[5], 4);

//	Mix them up and try again - single element
	do_shuffle(v.begin(), v.end());
	ba::sort_subrange(b, v.end(), b + 7, b + 8, std::greater<int>());
	check_sequence   (b, v.end(), b + 7, b + 8, std::greater<int>());

	BOOST_CHECK_EQUAL(v[7], 2);

//	Mix them up and try again - at the end
	do_shuffle(v.begin(), v.end());
	ba::sort_subrange(b, v.end(), b + 7, v.end(), std::greater<int>());
	check_sequence   (b, v.end(), b + 7, v.end(), std::greater<int>());

	BOOST_CHECK_EQUAL(v[7], 2);
	BOOST_CHECK_EQUAL(v[8], 1);
	BOOST_CHECK_EQUAL(v[9], 0);

//	Mix them up and try again - at the beginning
	do_shuffle(v.begin(), v.end());
	ba::sort_subrange(b, v.end(), b, b + 2, std::greater<int>());
	check_sequence   (b, v.end(), b, b + 2, std::greater<int>());

	BOOST_CHECK_EQUAL(v[0], 9);
	BOOST_CHECK_EQUAL(v[1], 8);

//	Mix them up and try again - empty subrange
	do_shuffle(v.begin(), v.end());
	ba::sort_subrange(b, v.end(), b, b, std::greater<int>());
	check_sequence   (b, v.end(), b, b, std::greater<int>());

//	Mix them up and try again - entire subrange
	do_shuffle(v.begin(), v.end());
	ba::sort_subrange(b, v.end(), b, v.end(), std::greater<int>());
	check_sequence   (b, v.end(), b, v.end(), std::greater<int>());
	}
}
Commit	Line	Data
7c673cae FG	1	#include <boost/config.hpp>
	2	#include <boost/algorithm/sort_subrange.hpp>
	3	#include <boost/algorithm/cxx11/is_sorted.hpp>
	4
	5	#define BOOST_TEST_MAIN
	6	#include <boost/test/unit_test.hpp>
	7
	8	#include <vector>
	9	#include <iostream>
b32b8144	10
92f5a8d4	11	#if (__cplusplus >= 201103L) \|\| defined(BOOST_NO_CXX98_RANDOM_SHUFFLE)
b32b8144 FG	12	#include <random>
	13
	14	std::default_random_engine gen;
	15	template<typename RandomIt>
	16	void do_shuffle(RandomIt first, RandomIt last)
	17	{ std::shuffle(first, last, gen); }
	18	#else
	19	template<typename RandomIt>
	20	void do_shuffle(RandomIt first, RandomIt last)
	21	{ std::random_shuffle(first, last); }
	22	#endif
	23
7c673cae FG	24	namespace ba = boost::algorithm;
	25
	26	template <typename Iter>
	27	void check_sequence ( Iter first, Iter last, Iter sf, Iter sl )
	28	{
	29	if (sf == sl) return;
	30	for (Iter i = first; i < sf; ++i)
	31	BOOST_CHECK(i < sf);
	32	BOOST_CHECK(ba::is_sorted(sf, sl));
	33	for (Iter i = sl; i < last; ++i)
	34	BOOST_CHECK((sl-1) < i);
	35	}
	36
	37	template <typename Iter, typename Pred>
	38	void check_sequence ( Iter first, Iter last, Iter sf, Iter sl, Pred p )
	39	{
	40	if (sf == sl) return;
	41	for (Iter i = first; i < sf; ++i)
	42	BOOST_CHECK(p(i, sf));
	43	BOOST_CHECK(ba::is_sorted(sf, sl, p));
	44	for (Iter i = sl; i < last; ++i)
	45	BOOST_CHECK(p((sl-1), i));
	46
	47	}
	48
	49	// for ( int i = 0; i < v.size(); ++i )
	50	// std::cout << v[i] << ' ';
	51	// std::cout << std::endl;
	52
	53
	54	BOOST_AUTO_TEST_CASE( test_main )
	55	{
	56	{
	57	std::vector<int> v;
	58	for ( int i = 0; i < 10; ++i )
	59	v.push_back(i);
92f5a8d4	60
7c673cae FG	61	const std::vector<int>::iterator b = v.begin();
	62	ba::sort_subrange(b, v.end(), b + 3, b + 6);
	63	check_sequence (b, v.end(), b + 3, b + 6);
	64
	65	BOOST_CHECK_EQUAL(v[3], 3);
	66	BOOST_CHECK_EQUAL(v[4], 4);
	67	BOOST_CHECK_EQUAL(v[5], 5);
92f5a8d4	68
7c673cae	69	// Mix them up and try again - single element
b32b8144	70	do_shuffle(v.begin(), v.end());
7c673cae FG	71	ba::sort_subrange(b, v.end(), b + 7, b + 8);
	72	check_sequence (b, v.end(), b + 7, b + 8);
	73
	74	BOOST_CHECK_EQUAL(v[7], 7);
	75
	76	// Mix them up and try again - at the end
b32b8144	77	do_shuffle(v.begin(), v.end());
7c673cae FG	78	ba::sort_subrange(b, v.end(), b + 7, v.end());
	79	check_sequence (b, v.end(), b + 7, v.end());
	80
	81	BOOST_CHECK_EQUAL(v[7], 7);
	82	BOOST_CHECK_EQUAL(v[8], 8);
	83	BOOST_CHECK_EQUAL(v[9], 9);
	84
	85	// Mix them up and try again - at the beginning
b32b8144	86	do_shuffle(v.begin(), v.end());
7c673cae FG	87	ba::sort_subrange(b, v.end(), b, b + 2);
	88	check_sequence (b, v.end(), b, b + 2);
	89
	90	BOOST_CHECK_EQUAL(v[0], 0);
	91	BOOST_CHECK_EQUAL(v[1], 1);
	92
	93	// Mix them up and try again - empty subrange
b32b8144	94	do_shuffle(v.begin(), v.end());
7c673cae FG	95	ba::sort_subrange(b, v.end(), b, b);
	96	check_sequence (b, v.end(), b, b);
	97
	98	// Mix them up and try again - entire subrange
b32b8144	99	do_shuffle(v.begin(), v.end());
7c673cae FG	100	ba::sort_subrange(b, v.end(), b, v.end());
	101	check_sequence (b, v.end(), b, v.end());
	102	}
	103
	104	{
	105	std::vector<int> v;
	106	for ( int i = 0; i < 10; ++i )
	107	v.push_back(i);
92f5a8d4	108
7c673cae FG	109	const std::vector<int>::iterator b = v.begin();
	110	ba::sort_subrange(b, v.end(), b + 3, b + 6, std::greater<int>());
	111	check_sequence (b, v.end(), b + 3, b + 6, std::greater<int>());
	112
	113	BOOST_CHECK_EQUAL(v[3], 6);
	114	BOOST_CHECK_EQUAL(v[4], 5);
	115	BOOST_CHECK_EQUAL(v[5], 4);
	116
	117	// Mix them up and try again - single element
b32b8144	118	do_shuffle(v.begin(), v.end());
7c673cae FG	119	ba::sort_subrange(b, v.end(), b + 7, b + 8, std::greater<int>());
	120	check_sequence (b, v.end(), b + 7, b + 8, std::greater<int>());
	121
	122	BOOST_CHECK_EQUAL(v[7], 2);
	123
	124	// Mix them up and try again - at the end
b32b8144	125	do_shuffle(v.begin(), v.end());
7c673cae FG	126	ba::sort_subrange(b, v.end(), b + 7, v.end(), std::greater<int>());
	127	check_sequence (b, v.end(), b + 7, v.end(), std::greater<int>());
	128
	129	BOOST_CHECK_EQUAL(v[7], 2);
	130	BOOST_CHECK_EQUAL(v[8], 1);
	131	BOOST_CHECK_EQUAL(v[9], 0);
	132
	133	// Mix them up and try again - at the beginning
b32b8144	134	do_shuffle(v.begin(), v.end());
7c673cae FG	135	ba::sort_subrange(b, v.end(), b, b + 2, std::greater<int>());
	136	check_sequence (b, v.end(), b, b + 2, std::greater<int>());
	137
	138	BOOST_CHECK_EQUAL(v[0], 9);
	139	BOOST_CHECK_EQUAL(v[1], 8);
	140
	141	// Mix them up and try again - empty subrange
b32b8144	142	do_shuffle(v.begin(), v.end());
7c673cae FG	143	ba::sort_subrange(b, v.end(), b, b, std::greater<int>());
	144	check_sequence (b, v.end(), b, b, std::greater<int>());
	145
	146	// Mix them up and try again - entire subrange
b32b8144	147	do_shuffle(v.begin(), v.end());
7c673cae FG	148	ba::sort_subrange(b, v.end(), b, v.end(), std::greater<int>());
	149	check_sequence (b, v.end(), b, v.end(), std::greater<int>());
	150	}
	151	}