-
Notifications
You must be signed in to change notification settings - Fork 1
/
util.h
269 lines (239 loc) · 7.53 KB
/
util.h
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
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
#ifndef UTIL_INCLUDED
#define UTIL_INCLUDED
#include <numeric>
#include <vector>
#include <map>
#include <string>
#include <sstream>
#include <algorithm>
#include <functional>
#include <cassert>
#include <mutex>
#include <sys/stat.h>
/* uncomment to enable NaN checks */
#define NAN_DEBUG
/* Errors, warnings, assertions.
Fail(...) and Require(...) are quieter versions of Abort(...) and Assert(...)
that do not print a stack trace or throw an exception,
but merely call exit().
Test(...) does not exit or throw an exception,
just prints a warning and returns false if the assertion fails.
*/
void Abort(const char* error, ...);
void Warn(const char* warning, ...);
void Fail(const char* error, ...);
#define Test(assertion,...) ((assertion) ? true : (Warn(__VA_ARGS__), false))
#define Assert(assertion,...) do { if (!(assertion)) Abort("Assertion Failed: " __VA_ARGS__); } while (0)
#define Require(assertion,...) do { if (!(assertion)) Fail(__VA_ARGS__); } while (0)
/* singular or plural? */
std::string plural (long n, const char* singular);
std::string plural (long n, const char* singular, const char* plural);
/* stringify */
#define STRINGIFY(x) #x
#define TOSTRING(x) STRINGIFY(x)
/* join */
template<class Container>
std::string join (const Container& c, const char* sep = " ") {
std::string j;
for (const auto& s : c) {
if (!j.empty())
j += sep;
j += s;
}
return j;
}
/* to_string_join */
template<class Container>
std::string to_string_join (const Container& c, const char* sep = " ") {
std::ostringstream j;
int n = 0;
for (const auto& s : c) {
if (n++ > 0)
j << sep;
j << s;
}
return j.str();
}
/* vec_to_string */
template<class Container>
std::string vec_to_string (const Container& c, const char* sep = " ") {
return std::string("(") + to_string_join(c,sep) + ")";
}
/* to_string_join for a vector of vectors */
template<class Container>
std::string vec2_to_string (const Container& c) {
std::ostringstream j;
int n = 0;
j << "{";
for (const auto& row : c) {
if (n++ > 0)
j << " ";
j << vec_to_string(row);
}
j << "}";
return j.str();
}
/* to_string_join for a vector of vectors of vectors */
template<class Container>
std::string vec3_to_string (const Container& c) {
std::ostringstream j;
int n = 0;
j << "[";
for (const auto& row : c) {
if (n++ > 0)
j << " ";
j << vec2_to_string(row);
}
j << "]";
return j.str();
}
/* to_string_join for a vector of vectors of vectors of vectors */
template<class Container>
std::string vec4_to_string (const Container& c) {
std::ostringstream j;
int n = 0;
j << "<";
for (const auto& row : c) {
if (n++ > 0)
j << " ";
j << vec3_to_string(row);
}
j << ">";
return j.str();
}
/* transform_vector */
template<class S,class Container>
std::vector<S> transform_container (const Container& v, S (op) (typename Container::value_type const&)) {
std::vector<S> result;
std::transform (v.begin(), v.end(), back_inserter(result), op);
return result;
}
template<class S,class Container>
std::vector<S> transform_container (const Container& v, S (op) (typename Container::value_type)) {
std::vector<S> result;
std::transform (v.begin(), v.end(), back_inserter(result), op);
return result;
}
/* split */
std::vector<std::string> split (const std::string& s, const char* splitChars = " \t\n");
std::vector<std::string> splitToChars (const std::string& s);
/* toupper */
std::string toupper (const std::string& s);
/* escaping a string
http://stackoverflow.com/questions/2417588/escaping-a-c-string
*/
void write_escaped (std::string const& s, std::ostream& out);
std::string escaped_str (std::string const& s);
/* random_double */
template<class Generator>
double random_double (Generator& generator) {
return generator() / (((double) std::numeric_limits<typename Generator::result_type>::max()) + 1);
}
/* extract_keys */
template<typename TK, typename TV>
std::vector<TK> extract_keys(std::map<TK, TV> const& input_map) {
std::vector<TK> retval;
for (auto const& element : input_map) {
retval.push_back(element.first);
}
return retval;
}
/* extract_values */
template<typename TK, typename TV>
std::vector<TV> extract_values(std::map<TK, TV> const& input_map) {
std::vector<TV> retval;
for (auto const& element : input_map) {
retval.push_back(element.second);
}
return retval;
}
/* random_element */
template<class Iterator,class Generator>
Iterator random_element (Iterator begin, Iterator end, Generator generator)
{
const size_t n = std::distance(begin, end);
std::uniform_int_distribution<int> distribution (0, n - 1);
const size_t k = distribution (generator);
std::advance(begin, k);
return begin;
}
template<class Container,class Generator>
typename Container::const_reference random_element (const Container& container, Generator generator)
{
return *(random_element (container.begin(), container.end(), generator));
}
template<class Container,class Generator>
typename Container::reference random_element (Container& container, Generator generator)
{
return *(random_element (container.begin(), container.end(), generator));
}
/* random_index */
template<class T,class Generator>
size_t random_index (const std::vector<T>& weights, Generator& generator) {
T norm = 0;
for (const T& w : weights) {
Assert (w >= 0, "Negative weights in random_index");
norm += w;
}
Assert (norm > 0, "Zero weights in random_index");
T variate = random_double(generator) * norm;
for (size_t n = 0; n < weights.size(); ++n)
if ((variate -= weights[n]) <= 0)
return n;
return weights.size();
}
/* random_key */
template<class T,class Generator>
const T& random_key (const std::map<T,double>& weight, Generator& generator) {
double norm = 0;
for (const auto& kv : weight) {
Assert (kv.second >= 0, "Negative weights in random_key");
norm += kv.second;
}
Assert (norm > 0, "Zero weights in random_key");
T variate = random_double(generator) * norm;
for (const auto& kv : weight)
if ((variate -= kv.second) <= 0)
return kv.first;
Abort ("random_key failed");
return *(weight.begin()).first;
}
/* random_key_log */
template<class T,class Generator>
const T& random_key_log (const std::map<T,double>& logWeight, Generator& generator) {
double norm = 0, logmax = -std::numeric_limits<double>::infinity();
for (const auto& kv : logWeight)
logmax = max (logmax, kv.second);
for (const auto& kv : logWeight)
norm += exp (kv.second - logmax);
Assert (norm > 0, "Zero weights in random_key_log");
double variate = random_double(generator) * norm;
for (const auto& kv : logWeight)
if ((variate -= exp (kv.second - logmax)) <= 0)
return kv.first;
Abort ("random_key_log failed");
const auto& iter = logWeight.begin();
return (*iter).first;
}
/* index sort
http://stackoverflow.com/questions/10580982/c-sort-keeping-track-of-indices
*/
template <typename S, typename T>
void sortIndices (std::vector<S>& indices, std::vector<T> const& values) {
std::sort(
begin(indices), end(indices),
[&](S a, S b) { return values[a] < values[b]; }
);
}
template <typename T>
std::vector<size_t> orderedIndices (std::vector<T> const& values) {
std::vector<size_t> indices(values.size());
std::iota(begin(indices), end(indices), static_cast<size_t>(0));
sortIndices (indices, values);
return indices;
}
// normalize
void normalize (std::vector<double>&, double tolerance = -1); // tolerance<0 => no error reporting
// safelog(x)
inline double safelog (double x) { return x > 0 ? log(x) : 0; }
#endif /* UTIL_INCLUDED */