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