123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151 |
- #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>());
- }
- }
|