boost/libs/range/test/algorithm_test/random_shuffle.cpp

//  Copyright Neil Groves 2009. Use, modification and
//  distribution is subject to 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)
//
//
// For more information, see http://www.boost.org/libs/range/
//
#include <boost/range/algorithm/random_shuffle.hpp>

#include <boost/test/test_tools.hpp>
#include <boost/test/unit_test.hpp>

#include <boost/assign.hpp>
#include "../test_function/counted_function.hpp"
#include <algorithm>
#include <functional>
#include <list>
#include <numeric>
#include <deque>
#include <vector>

namespace boost
{
    namespace
    {
        template<class Int>
        class counted_generator
            : private range_test_function::counted_function
        {
        public:
            typedef Int result_type;
            typedef Int argument_type;

            using range_test_function::counted_function::invocation_count;

            result_type operator()(argument_type modulo_value)
            {
                invoked();
                return static_cast<result_type>(std::rand() % modulo_value);
            }
        };

        template<class Container>
        bool test_shuffle_result(
            const Container& old_cont,
            const Container& new_cont
            )
        {
            typedef BOOST_DEDUCED_TYPENAME range_iterator<const Container>::type iterator_t;

            // The size must remain equal
            BOOST_CHECK_EQUAL( old_cont.size(), new_cont.size() );
            if (old_cont.size() != new_cont.size())
                return false;

            if (new_cont.size() < 2)
            {
                BOOST_CHECK_EQUAL_COLLECTIONS(
                    old_cont.begin(), old_cont.end(),
                    new_cont.begin(), new_cont.end()
                    );

                return std::equal(old_cont.begin(), old_cont.end(),
                                  new_cont.begin());
            }

            // Elements must only be moved around. This is tested by
            // ensuring the count of each element remains the
            // same.
            bool failed = false;
            iterator_t last = old_cont.end();
            for (iterator_t it = old_cont.begin(); !failed && (it != last); ++it)
            {
                const std::size_t old_count
                    = std::count(old_cont.begin(), old_cont.end(), *it);

                const std::size_t new_count
                    = std::count(new_cont.begin(), new_cont.end(), *it);

                BOOST_CHECK_EQUAL( old_count, new_count );

                failed = (old_count != new_count);
            }

            return !failed;
        }

        template<class Container>
        void test_random_shuffle_nogen_impl(Container& cont)
        {
            typedef BOOST_DEDUCED_TYPENAME range_iterator<Container>::type
                                                iterator_t BOOST_RANGE_UNUSED;

            const int MAX_RETRIES = 10000;

            bool shuffled = false;
            for (int attempt = 0; !shuffled && (attempt < MAX_RETRIES); ++attempt)
            {
                Container test(cont);
                boost::random_shuffle(test);
                bool ok = test_shuffle_result(cont, test);
                if (!ok)
                    break;

                // Since the counts are equal, then if they are 
                // not equal the contents must have been shuffled
                if (cont.size() == test.size()
                &&  !std::equal(cont.begin(), cont.end(), test.begin()))
                {
                    shuffled = true;
                }
                
                // Verify that the shuffle can be performed on a
                // temporary range
                Container test2(cont);
                boost::random_shuffle(boost::make_iterator_range(test2));
                ok = test_shuffle_result(cont, test2);
                if (!ok)
                    break;
            }
        }

        template<class RandomGenerator, class Container>
        void test_random_shuffle_gen_impl(Container& cont)
        {
            RandomGenerator gen;
            Container old_cont(cont);
            boost::random_shuffle(cont, gen);
            test_shuffle_result(cont, old_cont);
            if (cont.size() > 2)
            {
                BOOST_CHECK( gen.invocation_count() > 0 );
            }
            
            // Test that random shuffle works when 
            // passed a temporary range
            RandomGenerator gen2;
            Container cont2(old_cont);
            boost::random_shuffle(boost::make_iterator_range(cont2), gen2);
            test_shuffle_result(cont2, old_cont);
            if (cont2.size() > 2)
            {
                BOOST_CHECK( gen2.invocation_count() > 0 );
            }
        }

        template<class Container>
        void test_random_shuffle_impl(Container& cont)
        {
            Container old_cont(cont);
            boost::random_shuffle(cont);
            test_shuffle_result(cont, old_cont);
        }

        template<class Container>
        void test_random_shuffle_impl()
        {
            using namespace boost::assign;

            typedef counted_generator<
                BOOST_DEDUCED_TYPENAME range_difference<Container>::type > generator_t;

            Container cont;
            test_random_shuffle_nogen_impl(cont);
            test_random_shuffle_gen_impl<generator_t>(cont);

            cont.clear();
            cont += 1;
            test_random_shuffle_nogen_impl(cont);
            test_random_shuffle_gen_impl<generator_t>(cont);

            cont.clear();
            cont += 1,2,3,4,5,6,7,8,9;
            test_random_shuffle_nogen_impl(cont);
            test_random_shuffle_gen_impl<generator_t>(cont);
        }

        void test_random_shuffle()
        {
            test_random_shuffle_impl< std::vector<int> >();
            test_random_shuffle_impl< std::deque<int> >();
        }
    }
}


boost::unit_test::test_suite*
init_unit_test_suite(int argc, char* argv[])
{
    boost::unit_test::test_suite* test
        = BOOST_TEST_SUITE( "RangeTestSuite.algorithm.random_shuffle" );

    test->add( BOOST_TEST_CASE( &boost::test_random_shuffle ) );

    return test;
}