1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
|
// -*- C++ -*-
// Copyright (C) 2005, 2006, 2008, 2009, 2010 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library. This library is free
// software; you can redistribute it and/or modify it under the terms
// of the GNU General Public License as published by the Free Software
// Foundation; either version 3, or (at your option) any later
// version.
// This library is distributed in the hope that it will be useful, but
// WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
// General Public License for more details.
// You should have received a copy of the GNU General Public License
// along with this library; see the file COPYING3. If not see
// <http://www.gnu.org/licenses/>.
// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
// Permission to use, copy, modify, sell, and distribute this software
// is hereby granted without fee, provided that the above copyright
// notice appears in all copies, and that both that copyright notice
// and this permission notice appear in supporting documentation. None
// of the above authors, nor IBM Haifa Research Laboratories, make any
// representation about the suitability of this software for any
// purpose. It is provided "as is" without express or implied
// warranty.
/**
* @file rand_regression_test.hpp
* Contains a random-operation test.
*/
#ifndef PB_DS_PQ_RAND_REGRESSION_TEST_HPP
#define PB_DS_PQ_RAND_REGRESSION_TEST_HPP
#include <iostream>
#include <vector>
#include <io/verified_cmd_line_input.hpp>
#include <regression/common_type.hpp>
#include <regression/rand/priority_queue/container_rand_regression_test.h>
namespace __gnu_pbds
{
namespace test
{
namespace detail
{
#ifndef PB_DS_REGRESSION
#error "Must define PB_DS_REGRESSION"
#endif
struct rand_reg_test
{
public:
rand_reg_test(size_t seed, size_t n, size_t m, double tp, double ip,
double dp, double ep, double cp, double mp, bool d)
: m_sd(seed), m_n(n), m_m(m), m_tp(tp), m_ip(ip), m_dp(dp), m_ep(ep),
m_cp(cp), m_mp(mp), m_disp(d)
{ }
template<typename Cntnr>
void
operator()(Cntnr)
{
unsigned long ul = static_cast<unsigned long>(m_sd);
container_rand_regression_test<Cntnr> t(ul, m_n, m_n, m_tp, m_ip, m_dp,
m_ep, m_cp, m_mp, m_disp);
t();
}
private:
const size_t m_sd;
const size_t m_n;
const size_t m_m;
const double m_tp;
const double m_ip;
const double m_dp;
const double m_ep;
const double m_cp;
const double m_mp;
const bool m_disp;
};
void
usage(const std::string& r_name);
void
verify_params(size_t&, size_t&, size_t&,
double&, double&, double&, double&, double&, double&, bool&);
} // namespace detail
template<typename TL>
int
rand_regression_test(size_t iter, size_t keys, const std::string name, TL tl)
{
// Sane defaults.
size_t n = iter;
size_t m = keys;
size_t sd = 0; // 0 = time-determined arbitrary
double tp = 0.2;
double ip = 0.6;
double dp = 0.1;
double ep = 0.2;
double cp = 0.001;
double mp = 1;
bool disp = false; // show progress
try
{
detail::verify_params(sd, n, m, tp, ip, dp, ep, cp, mp, disp);
}
catch(__gnu_pbds::test::illegal_input_error&)
{
detail::usage(name);
return -1;
}
catch(...)
{
return -2;
};
xml_test_rand_regression_formatter* p_fmt = 0;
if (sd == 0)
sd = twister_rand_gen::get_time_determined_seed();
if (disp)
p_fmt = new xml_test_rand_regression_formatter(sd, n, m, tp, ip, dp,
ep, cp, mp);
try
{
detail::rand_reg_test tst(sd, n, m, tp, ip, dp, ep, cp, mp, disp);
__gnu_cxx::typelist::apply(tst, tl);
}
catch(...)
{
std::cerr << "Test failed with seed " << sd << std::endl;
if (disp)
delete p_fmt;
return -1;
}
if (disp)
delete p_fmt;
return 0;
}
namespace detail
{
inline void
usage(const std::string& name)
{
using namespace std;
cerr << "usage: " << name << " <sd> <n> <m> <tp> <ip> <dp> <ep> <cp> <mp> ['t' | 'f']" <<
endl << endl;
cerr << "This test performs basic regression tests on various priority queues."
"For each container, it performs a sequence of operations. At each iteration, it does "
"the following: " << endl;
cerr << "* Performs an operation on the container " << endl;
cerr << "* Performs the same operation on an cntnr object" << endl;
cerr << "* Possibly compares the container to the cntnr object" << endl;
cerr << "* Checks that exceptions (thrown by an allocator) "
"do not violate exception guarantees";
cerr << endl << endl;
cerr << "sd = seed for random-number generator; 0 = "
"time determined value" << endl;
cerr << "n = number of iterations" << endl;
cerr << "m = number of distinct values" << endl;
cerr << "tp = probability that an exception will be actively thrown" << endl;
cerr << "ip = probability that an operation will be insert" << endl;
cerr << "dp = probability that an operation will be modify" << endl;
cerr << "ep = probability that an operation will be erase" << endl;
cerr << "cp = probability that an operation will be clear" << endl;
cerr << "(therefore, 1 - (ip + dp + ep + cp) = probability of any other operation)" << endl;
cerr << "mp = probability that the container will be compared to the cntnr object" << endl;
cerr << "'t' or 'f' determine whether progress will be displayed" << endl;
}
inline void
verify_params(size_t& r_seed, size_t& r_n,
size_t& r_m, double& r_tp, double& r_ip, double& r_dp,
double& r_ep, double& r_cp, double& r_mp, bool& r_d)
{
verify_prob(r_tp);
verify_prob(r_ip);
verify_prob(r_dp);
verify_prob(r_ep);
verify_prob(r_cp);
verify_prob(r_mp);
verify_prob(r_ip + r_dp + r_ep + r_cp);
}
} // namespace detail
} // namespace test
} // namespace __gnu_pbds
#endif
|