Author: sebor
Date: Wed Jan 25 18:59:04 2006
New Revision: 372412
URL: http://svn.apache.org/viewcvs?rev=372412&view=rev
Log:
2006-01-25 Martin Sebor <[EMAIL PROTECTED]>
* 25.random.shuffle.cpp: Corrected subtle logic errors and simplified.
Modified:
incubator/stdcxx/trunk/tests/algorithms/25.random.shuffle.cpp
Modified: incubator/stdcxx/trunk/tests/algorithms/25.random.shuffle.cpp
URL:
http://svn.apache.org/viewcvs/incubator/stdcxx/trunk/tests/algorithms/25.random.shuffle.cpp?rev=372412&r1=372411&r2=372412&view=diff
==============================================================================
--- incubator/stdcxx/trunk/tests/algorithms/25.random.shuffle.cpp (original)
+++ incubator/stdcxx/trunk/tests/algorithms/25.random.shuffle.cpp Wed Jan 25
18:59:04 2006
@@ -107,6 +107,10 @@
gen_ = (gen_ << 7) + gen_ % 128;
+ // prevent the number from going negative(!)
+ if (gen_ < 0)
+ gen_ = -gen_;
+
return gen_ % n;
}
@@ -168,28 +172,25 @@
fname, itname, rnd_gen, funname);
// generate a sequential value for each default-constructed T
- // starying with 0 (i.e., T::val_ will be 0 for the first T)
+ // starting with 0 (i.e., T::val_ will be 0 for the first T)
sequence_start = 0;
- T::gen_ = sequence_generator;
+ T::gen_ = sequence_generator;
- T *buf = new T [N];
- bool *found = new bool [N];
+ T *buf = new T [N + 1];
+ char *missing = new char [N + 1];
for (std::size_t i = 0; i < N; ++i) {
- // reset found array to false
- std::memset (found, 0, N * sizeof *found);
-
// 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 + 1, it);
- const Iterator last = make_iter (buf + i + 1, buf, buf + i + 1, it);
+ 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 last_n_op_assign = T::n_total_op_assign_;
+ std::size_t n_op_assign = T::n_total_op_assign_;
// shuffle buffer elements
if (rnd_gen)
@@ -197,45 +198,47 @@
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 found array setting those
- // at the index given by T::val_ to true to verify that
- // random_shuffle() didn't drop any elements
+ // 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;
- for (j = 0; j != i + 1; ++j)
- found [(buf + j)->val_ - 1] = true;
-
- // iterate over elements of the found array once again,
- // this time to verify that no elements of the buf array
- // are missing
- bool success = true;
- for (j = 0; j != i + 1; ++j) {
- success = found [j];
- if (!success)
- break;
+ std::memset (missing, 1, N);
+ for (j = 0; j != i; ++j) {
+ const std::size_t inx = std::size_t (buf [j].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 %zu",
- i, fname, itname, rnd_gen, funname, j);
+ "%zu. std::%s<%s%{?}, %s%{;}>(): can't find element "
+ "with value %td: got \"%{X=*.*}\"",
+ i, fname, itname, rnd_gen, funname,
+ first_missing - missing,
+ int (i), -1, buf);
- if (!success)
- break;
- // verify 25.2.11, p2
- // exactly (i + 1) - 1 swaps * 2 assigns per swap = 2 * i assignments
- success = T::n_total_op_assign_ - last_n_op_assign == 2 * i;
+ // 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: %zu != %zu",
+ "%zu. std::%s<%s%{?}, %s%{;}>(): complexity: "
+ "expected %zu swaps, got %zu",
i, fname, itname, rnd_gen, funname,
- T::n_total_op_assign_ - last_n_op_assign, 2 * i);
-
- if (!success)
- break;
+ 2 * i, n_op_assign);
}
delete[] buf;
- delete[] found;
+ delete[] missing;
}
/**************************************************************************/
