25.random.shuffle.cpp

Go to the documentation of this file.

 
#include <algorithm>    // for random_shuffle
#include <cstring>      // for memset(), size_t
 
#include <rw_alg_test.h>
#include <rw_value.h>   // for UserClass
#include <rw_driver.h>  // for rw_test()
 
 
_RWSTD_NAMESPACE (std) { 
 
// disable explicit instantiation for compilers (like MSVC)
// that can't handle it
#ifndef _RWSTD_NO_EXPLICIT_INSTANTIATION
 
template
void
random_shuffle (RandomAccessIter<assign<base<cpy_ctor> > >, 
                RandomAccessIter<assign<base<cpy_ctor> > >);
 
template
void
random_shuffle (RandomAccessIter<assign<base<cpy_ctor> > >, 
                RandomAccessIter<assign<base<cpy_ctor> > >,
                func<const long>&);
 
#endif // _RWSTD_NO_EXPLICIT_INSTANTIATION
 
}   // namespace std
 
 
// 25.2.11, p3 requires that a RandomNumberGenerator take
// and return a value convertible from and to, respectively,
// iterator::difference_type
 
template <class DifferenceType>
struct Convertible
{
    Convertible (DifferenceType val): val_ (val) { }
    operator DifferenceType () /* non-const */ { return val_; }
 
private:
    const DifferenceType val_;
 
    template <class T>
    Convertible (T);
};
 
// detect assumptions made by the algorithm about the return value
// from RandomGenerator::operator() being anything but convertible
// to the iterator's difference type
template <class DifferenceType, class T>
void operator+ (Convertible<DifferenceType>, T);
 
template <class DifferenceType, class T>
void operator+ (T, Convertible<DifferenceType>);
 
template <class DifferenceType>
struct RandomGenerator
{
    // dummy arguments to prevent the class from being default
    // constructible or construtible by conversion from an int
    RandomGenerator (int, int) {
        ncalls_ = 0;
    }
 
    // non-const in order to detect unwarranted assumptions
    // in the algorithm(s)
    Convertible<DifferenceType>
    operator() (DifferenceType n) /* non-const */ {
 
        ++ncalls_;
 
        gen_ = (gen_ << 7) + gen_ % 128;
 
        // prevent the number from going negative(!)
        if (gen_ < 0)
            gen_ = -gen_;
 
        return gen_ % n;
    }
 
    static std::size_t ncalls_;
 
private:
 
    template <class T>
    void operator() (T) /* non-const */;
 
    static DifferenceType gen_;
};
 
template <class DifferenceType>
std::size_t RandomGenerator<DifferenceType>::ncalls_ = 0;
 
template <class DifferenceType>
DifferenceType RandomGenerator<DifferenceType>::gen_ = 12345;
 
 
int sequence_start;
 
int sequence_generator ()
{
    return sequence_start++;
}
 
 
// exercises 25.2.11 -- std::random_shuffle()
template <class T, class Iterator, class RandomNumberGenerator>
void test_random_shuffle (const int                    line,
                          const std::size_t            N,
                          const Iterator              &it, 
                          const RandomNumberGenerator*,
                          const T*,
                          bool                         rnd_gen)
{
    const char* const itname  = type_name (it, (T*)0);
    const char* const fname   = "random_shuffle";
    const char* const funname = rnd_gen ? "random_generator" : "";
 
    rw_info (0, 0, 0,
             "std::%s (%s, %2$s%{?}, %s%{;})",
             fname, itname, rnd_gen, funname);
 
    // generate a sequential value for each default-constructed T
    // starting with 0 (i.e., T::val_ will be 0 for the first T)
    sequence_start = 0;
    T::gen_        = sequence_generator;
 
    T    *buf      = new T [N + 1];
    char *missing  = new char [N + 1];
 
    for (std::size_t i = 0; i < N; ++i) {
 
        // create a pair of safe iterator to pass to random_shuffle
        // in order to test that the function doesn't write past
        // the end of the sequence [first, last)
        const Iterator first = make_iter (buf,     buf, buf + i, it);
        const Iterator last  = make_iter (buf + i, buf, buf + i, it);
 
        /* non-const */ RandomNumberGenerator rnd (0, 0);   // dummy args
 
        // exercise 25.2.11 - std::random_shuffle<>()
        std::size_t n_op_assign = T::n_total_op_assign_;
 
        // shuffle buffer elements
        if (rnd_gen)
            std::random_shuffle (first, last, rnd);
        else
            std::random_shuffle (first, last);
 
        n_op_assign = T::n_total_op_assign_ - n_op_assign;
 
        // verify 25.2.11, p1
        // iterate over elements of the missing array clearing those
        // at the index given by T::val_ to true to verify that the
        // algorithm didn't drop any elements
        std::size_t j;
        std::memset (missing, 1, N);
        for (j = 0; j != i; ++j) {
            const std::size_t inx = std::size_t (buf [j].data_.val_);
            if (inx < N)
                missing [inx] = 0;
        }
 
        // find the first missing element (if any)
        const char* const first_missing = (char*)std::memchr (missing, 1, i);
 
        bool success = 0 == first_missing;
 
        rw_assert (success, 0, line,
                   "%zu. std::%s<%s%{?}, %s%{;}>(): can't find element "
                   "with value %td: got \"%{X=*.*}\"",
                   i, fname, itname, rnd_gen, funname,
                   first_missing - missing,
                   int (sizeof (*buf)), int (i), -1, buf);
 
 
        // verify 25.2.11, p2, complexity:
        // exactly K = ((last - first) - 1) swaps
        // i.e., K * 2 assignments (at 2 assignment per swap
        // plus one copy construction)
        success = n_op_assign == 2 * (i ? i - 1 : i);
        rw_assert (success, 0, line,
                   "%zu. std::%s<%s%{?}, %s%{;}>(): complexity: "
                   "expected %zu swaps, got %zu",
                   i, fname, itname, rnd_gen, funname, 
                   2 * i, n_op_assign);
    }
 
    delete[] buf;
    delete[] missing;
}
 
 
void test_random_shuffle (const int line)
{
#ifndef _RWSTD_NO_EXT_PORTABLE_RANDOM_SEQUENCE
 
    rw_info (0, 0, 0,
             "verify that the randomly shuffled sequence "
             "matches the expected result, this "
             "depends on the implementation of the random "
             "number generator used by random_shuffle()");
    
    int array[] = {
        0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
        0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,
        0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17,
        0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f,
        0x20, 0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27,
        0x28, 0x29, 0x2a, 0x2b, 0x2c, 0x2d, 0x2e, 0x2f,
        0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37,
        0x38, 0x39, 0x3a, 0x3b, 0x3c, 0x3d, 0x3e, 0x3f,
        0x40, 0x41, 0x42, 0x43, 0x44, 0x45, 0x46, 0x47,
        0x48, 0x49, 0x4a, 0x4b, 0x4c, 0x4d, 0x4e, 0x4f,
        0x50, 0x51, 0x52, 0x53, 0x54, 0x55, 0x56, 0x57,
        0x58, 0x59, 0x5a, 0x5b, 0x5c, 0x5d, 0x5e, 0x5f,
        0x60, 0x61, 0x62, 0x63, 0x64, 0x65, 0x66, 0x67,
        0x68, 0x69, 0x6a, 0x6b, 0x6c, 0x6d, 0x6e, 0x6f,
        0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77,
        0x78, 0x79, 0x7a, 0x7b, 0x7c, 0x7d, 0x7e, 0x7f,
        0x80, 0x81, 0x82, 0x83, 0x84, 0x85, 0x86, 0x87,
        0x88, 0x89, 0x8a, 0x8b, 0x8c, 0x8d, 0x8e, 0x8f,
        0x90, 0x91, 0x92, 0x93, 0x94, 0x95, 0x96, 0x97,
        0x98, 0x99, 0x9a, 0x9b, 0x9c, 0x9d, 0x9e, 0x9f,
        0xa0, 0xa1, 0xa2, 0xa3, 0xa4, 0xa5, 0xa6, 0xa7,
        0xa8, 0xa9, 0xaa, 0xab, 0xac, 0xad, 0xae, 0xaf,
        0xb0, 0xb1, 0xb2, 0xb3, 0xb4, 0xb5, 0xb6, 0xb7,
        0xb8, 0xb9, 0xba, 0xbb, 0xbc, 0xbd, 0xbe, 0xbf,
        0xc0, 0xc1, 0xc2, 0xc3, 0xc4, 0xc5, 0xc6, 0xc7,
        0xc8, 0xc9, 0xca, 0xcb, 0xcc, 0xcd, 0xce, 0xcf,
        0xd0, 0xd1, 0xd2, 0xd3, 0xd4, 0xd5, 0xd6, 0xd7,
        0xd8, 0xd9, 0xda, 0xdb, 0xdc, 0xdd, 0xde, 0xdf,
        0xe0, 0xe1, 0xe2, 0xe3, 0xe4, 0xe5, 0xe6, 0xe7,
        0xe8, 0xe9, 0xea, 0xeb, 0xec, 0xed, 0xee, 0xef,
        0xf0, 0xf1, 0xf2, 0xf3, 0xf4, 0xf5, 0xf6, 0xf7,
        0xf8, 0xf9, 0xfa, 0xfb, 0xfc, 0xfd, 0xfe, 0xff
    };
 
    std::random_shuffle (array, array + sizeof array / sizeof *array);
 
    const int result[] = {
        0xdc, 0x98, 0x6c, 0xcc, 0x1c, 0xb1, 0x2f, 0x13,
        0xa4, 0x8b, 0x96, 0x87, 0x95, 0xd8, 0x5e, 0xd5,
        0xb6, 0xee, 0xc3, 0x07, 0x68, 0xe4, 0x4e, 0xc0,
        0xb7, 0x40, 0x15, 0x55, 0x31, 0x5f, 0xaf, 0xce,
        0x01, 0x51, 0x09, 0x4f, 0x0b, 0x80, 0x28, 0x0f,
        0xec, 0x43, 0x8a, 0x14, 0x90, 0x9a, 0x7b, 0x3e,
        0x81, 0x1e, 0xab, 0xff, 0xed, 0xf6, 0xca, 0x0c,
        0x6a, 0x9c, 0x91, 0x60, 0x27, 0xb2, 0x04, 0xd3,
        0x72, 0xd7, 0x08, 0x8c, 0x8e, 0x1b, 0x35, 0x49,
        0xba, 0x7a, 0xfd, 0x53, 0x22, 0xaa, 0xf5, 0x93,
        0xf2, 0x63, 0x05, 0xb4, 0x33, 0x9b, 0xea, 0xc8,
        0xc5, 0x39, 0xfc, 0x5d, 0x56, 0x50, 0xe2, 0xf4,
        0xc1, 0xa9, 0x76, 0x99, 0xe7, 0xd0, 0xc6, 0x83,
        0x11, 0x77, 0x70, 0xa6, 0x46, 0x38, 0x1d, 0x74,
        0x6b, 0xdf, 0x30, 0xcf, 0xd1, 0x29, 0x7f, 0x4b,
        0xe8, 0x1f, 0xc4, 0xa1, 0x75, 0xae, 0x3f, 0xf1,
        0xad, 0x42, 0x2d, 0xfe, 0x62, 0x61, 0x6d, 0x3d,
        0xa7, 0x0a, 0x6e, 0xde, 0x16, 0x36, 0xd2, 0xcb,
        0x5c, 0xc2, 0x7c, 0xd6, 0x37, 0xa0, 0x20, 0xb5,
        0xf3, 0xac, 0x71, 0x64, 0x26, 0x66, 0x88, 0x23,
        0x52, 0xdb, 0x2e, 0x10, 0x84, 0x0e, 0x6f, 0x89,
        0xb3, 0x86, 0xe5, 0xe6, 0x25, 0x78, 0xd4, 0x2a,
        0xa8, 0x5b, 0xc9, 0x44, 0x24, 0x17, 0x1a, 0xf0,
        0x69, 0x7e, 0xbf, 0x8d, 0x5a, 0x82, 0x9e, 0xf9,
        0xc7, 0xf7, 0x4c, 0x92, 0x9d, 0x34, 0x02, 0x45,
        0x59, 0xe1, 0x48, 0x7d, 0xb9, 0x94, 0x41, 0x47,
        0x54, 0x00, 0x3c, 0x65, 0xf8, 0xb8, 0xcd, 0x0d,
        0xe9, 0x9f, 0x8f, 0x79, 0x3a, 0xda, 0x4a, 0x97,
        0xef, 0xa2, 0x21, 0x58, 0x67, 0x32, 0xb0, 0x3b,
        0xe0, 0x85, 0x19, 0x12, 0x2c, 0xbc, 0x4d, 0xe3,
        0x2b, 0x03, 0xbe, 0xfb, 0xbd, 0x57, 0xeb, 0x06,
        0xfa, 0xbb, 0xdd, 0xa5, 0xa3, 0x73, 0x18, 0xd9
    };
 
    for (std::size_t i = 0; i != sizeof array / sizeof *array; ++i) {
        if (!rw_assert (array [i] == result [i], 0, line, 
                        "randomly shuffled sequence failed to match "
                        "the expected result (data portability failure) "
                        "%d != %d at %zu",
                        array [i], result [i], i + 1))
            break;
    }
 
#else
    rw_note (0, 0, 0,
             "_RWSTD_NO_EXT_PORTABLE_RANDOM_SEQUENCE is defined, "
             "no random_test available");
#endif   // _RWSTD_NO_EXT_PORTABLE_RANDOM_SEQUENCE
}
 
 
/* extern */ int rw_opt_nloops = 1024;          // --nloops=#
/* extern */ int rw_opt_no_random;              // --no-random
/* extern */ int rw_opt_no_random_generator;    // --no-random_generator
/* extern */ int rw_opt_no_rand_test;           // --no-rand_test
 
 
static int run_test (int, char*[])
{
    const std::size_t N = std::size_t (rw_opt_nloops);
 
    typedef RandomAccessIter<UserClass>::difference_type DiffT;
    typedef RandomGenerator<DiffT>               RandGenT;
 
    if (rw_opt_no_random) {
        rw_note (0, __FILE__, __LINE__, "std::random test disabled");
    }
    else {
        rw_info (0, 0, 0,
                 "template <class %s> "
                 "std::random_shuffle (%1$s, %1$s)",
                 "RandomAccessIterator");
 
        test_random_shuffle (__LINE__, N, RandomAccessIter<UserClass>(),
                             (RandGenT*)0, (UserClass*)0, false);
    }
 
    if (rw_opt_no_rand_test) {
        rw_note (0, __FILE__, __LINE__, "random algorithm test disabled");
    }
    else {
        test_random_shuffle (__LINE__);
    }
 
    if (rw_opt_no_random_generator) {
        rw_note (0, __FILE__, __LINE__,  
                 "std::random with random_generator test disabled");
    }
    else {
        rw_info (0, 0, 0,
                 "template <class %s, class %s> "
                 "std::random_shuffle (%1$s, %1$s, %2$s)",
                 "RandomAccessIterator", "RandomNumberGenerator");
 
        test_random_shuffle (__LINE__, N, RandomAccessIter<UserClass>(),
                             (RandGenT*)0, (UserClass*)0, true);
    }
 
    return 0;
}
 
 
int main (int argc, char *argv[])
{
    return rw_test (argc, argv, __FILE__,
                    "lib.alg.random_shuffle",
                    0 /* no comment */, run_test,
                    "|-nloops#0 "   // must be non-negative
                    "|-no-random# "
                    "|-no-random_generator# "
                    "|-no-rand_test", 
                    &rw_opt_nloops,
                    &rw_opt_no_random,
                    &rw_opt_no_random_generator,
                    &rw_opt_no_rand_test);
}