0
6
2
1 |
/* -*- C++ -*- |
|
2 |
* |
|
3 |
* This file is a part of LEMON, a generic C++ optimization library |
|
4 |
* |
|
5 |
* Copyright (C) 2003-2008 |
|
6 |
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
|
7 |
* (Egervary Research Group on Combinatorial Optimization, EGRES). |
|
8 |
* |
|
9 |
* Permission to use, modify and distribute this software is granted |
|
10 |
* provided that this copyright notice appears in all copies. For |
|
11 |
* precise terms see the accompanying LICENSE file. |
|
12 |
* |
|
13 |
* This software is provided "AS IS" with no warranty of any kind, |
|
14 |
* express or implied, and with no claim as to its suitability for any |
|
15 |
* purpose. |
|
16 |
* |
|
17 |
*/ |
|
18 |
|
|
19 |
#ifndef LEMON_ERROR_H |
|
20 |
#define LEMON_ERROR_H |
|
21 |
|
|
22 |
/// \ingroup exceptions |
|
23 |
/// \file |
|
24 |
/// \brief Basic exception classes and error handling. |
|
25 |
|
|
26 |
#include <exception> |
|
27 |
#include <string> |
|
28 |
#include <sstream> |
|
29 |
#include <iostream> |
|
30 |
#include <cstdlib> |
|
31 |
#include <memory> |
|
32 |
|
|
33 |
namespace lemon { |
|
34 |
|
|
35 |
/// \addtogroup exceptions |
|
36 |
/// @{ |
|
37 |
|
|
38 |
/// \brief Exception safe wrapper class. |
|
39 |
/// |
|
40 |
/// Exception safe wrapper class to implement the members of exceptions. |
|
41 |
template <typename _Type> |
|
42 |
class ExceptionMember { |
|
43 |
public: |
|
44 |
typedef _Type Type; |
|
45 |
|
|
46 |
ExceptionMember() throw() { |
|
47 |
try { |
|
48 |
ptr.reset(new Type()); |
|
49 |
} catch (...) {} |
|
50 |
} |
|
51 |
|
|
52 |
ExceptionMember(const Type& type) throw() { |
|
53 |
try { |
|
54 |
ptr.reset(new Type()); |
|
55 |
if (ptr.get() == 0) return; |
|
56 |
*ptr = type; |
|
57 |
} catch (...) {} |
|
58 |
} |
|
59 |
|
|
60 |
ExceptionMember(const ExceptionMember& copy) throw() { |
|
61 |
try { |
|
62 |
if (!copy.valid()) return; |
|
63 |
ptr.reset(new Type()); |
|
64 |
if (ptr.get() == 0) return; |
|
65 |
*ptr = copy.get(); |
|
66 |
} catch (...) {} |
|
67 |
} |
|
68 |
|
|
69 |
ExceptionMember& operator=(const ExceptionMember& copy) throw() { |
|
70 |
if (ptr.get() == 0) return; |
|
71 |
try { |
|
72 |
if (!copy.valid()) return; |
|
73 |
*ptr = copy.get(); |
|
74 |
} catch (...) {} |
|
75 |
} |
|
76 |
|
|
77 |
void set(const Type& type) throw() { |
|
78 |
if (ptr.get() == 0) return; |
|
79 |
try { |
|
80 |
*ptr = type; |
|
81 |
} catch (...) {} |
|
82 |
} |
|
83 |
|
|
84 |
const Type& get() const { |
|
85 |
return *ptr; |
|
86 |
} |
|
87 |
|
|
88 |
bool valid() const throw() { |
|
89 |
return ptr.get() != 0; |
|
90 |
} |
|
91 |
|
|
92 |
private: |
|
93 |
std::auto_ptr<_Type> ptr; |
|
94 |
}; |
|
95 |
|
|
96 |
/// Exception-safe convenient "error message" class. |
|
97 |
|
|
98 |
/// Helper class which provides a convenient ostream-like (operator << |
|
99 |
/// based) interface to create a string message. Mostly useful in |
|
100 |
/// exception classes (therefore the name). |
|
101 |
class ErrorMessage { |
|
102 |
protected: |
|
103 |
///\e |
|
104 |
|
|
105 |
///\todo The good solution is boost::shared_ptr... |
|
106 |
/// |
|
107 |
mutable std::auto_ptr<std::ostringstream> buf; |
|
108 |
|
|
109 |
///\e |
|
110 |
bool init() throw() { |
|
111 |
try { |
|
112 |
buf.reset(new std::ostringstream); |
|
113 |
} |
|
114 |
catch(...) { |
|
115 |
buf.reset(); |
|
116 |
} |
|
117 |
return buf.get(); |
|
118 |
} |
|
119 |
|
|
120 |
public: |
|
121 |
|
|
122 |
///\e |
|
123 |
ErrorMessage() throw() { init(); } |
|
124 |
|
|
125 |
ErrorMessage(const ErrorMessage& em) throw() : buf(em.buf) { } |
|
126 |
|
|
127 |
///\e |
|
128 |
ErrorMessage(const char *msg) throw() { |
|
129 |
init(); |
|
130 |
*this << msg; |
|
131 |
} |
|
132 |
|
|
133 |
///\e |
|
134 |
ErrorMessage(const std::string &msg) throw() { |
|
135 |
init(); |
|
136 |
*this << msg; |
|
137 |
} |
|
138 |
|
|
139 |
///\e |
|
140 |
template <typename T> |
|
141 |
ErrorMessage& operator<<(const T &t) throw() { |
|
142 |
if( ! buf.get() ) return *this; |
|
143 |
|
|
144 |
try { |
|
145 |
*buf << t; |
|
146 |
} |
|
147 |
catch(...) { |
|
148 |
buf.reset(); |
|
149 |
} |
|
150 |
return *this; |
|
151 |
} |
|
152 |
|
|
153 |
///\e |
|
154 |
const char* message() throw() { |
|
155 |
if( ! buf.get() ) return 0; |
|
156 |
|
|
157 |
const char* mes = 0; |
|
158 |
try { |
|
159 |
mes = buf->str().c_str(); |
|
160 |
} |
|
161 |
catch(...) {} |
|
162 |
return mes; |
|
163 |
} |
|
164 |
|
|
165 |
}; |
|
166 |
|
|
167 |
/// Generic exception class. |
|
168 |
|
|
169 |
/// Base class for exceptions used in LEMON. |
|
170 |
/// |
|
171 |
class Exception : public std::exception { |
|
172 |
public: |
|
173 |
///\e |
|
174 |
Exception() {} |
|
175 |
///\e |
|
176 |
virtual ~Exception() throw() {} |
|
177 |
///\e |
|
178 |
virtual const char* what() const throw() { |
|
179 |
return "lemon::Exception"; |
|
180 |
} |
|
181 |
}; |
|
182 |
|
|
183 |
/// One of the two main subclasses of \ref Exception. |
|
184 |
|
|
185 |
/// Logic errors represent problems in the internal logic of a program; |
|
186 |
/// in theory, these are preventable, and even detectable before the |
|
187 |
/// program runs (e.g. violations of class invariants). |
|
188 |
/// |
|
189 |
/// A typical example for this is \ref UninitializedParameter. |
|
190 |
class LogicError : public Exception { |
|
191 |
public: |
|
192 |
virtual const char* what() const throw() { |
|
193 |
return "lemon::LogicError"; |
|
194 |
} |
|
195 |
}; |
|
196 |
|
|
197 |
/// \ref Exception for uninitialized parameters. |
|
198 |
|
|
199 |
/// This error represents problems in the initialization |
|
200 |
/// of the parameters of the algorithms. |
|
201 |
class UninitializedParameter : public LogicError { |
|
202 |
public: |
|
203 |
virtual const char* what() const throw() { |
|
204 |
return "lemon::UninitializedParameter"; |
|
205 |
} |
|
206 |
}; |
|
207 |
|
|
208 |
|
|
209 |
/// One of the two main subclasses of \ref Exception. |
|
210 |
|
|
211 |
/// Runtime errors represent problems outside the scope of a program; |
|
212 |
/// they cannot be easily predicted and can generally only be caught |
|
213 |
/// as the program executes. |
|
214 |
class RuntimeError : public Exception { |
|
215 |
public: |
|
216 |
virtual const char* what() const throw() { |
|
217 |
return "lemon::RuntimeError"; |
|
218 |
} |
|
219 |
}; |
|
220 |
|
|
221 |
///\e |
|
222 |
class RangeError : public RuntimeError { |
|
223 |
public: |
|
224 |
virtual const char* what() const throw() { |
|
225 |
return "lemon::RangeError"; |
|
226 |
} |
|
227 |
}; |
|
228 |
|
|
229 |
///\e |
|
230 |
class IoError : public RuntimeError { |
|
231 |
public: |
|
232 |
virtual const char* what() const throw() { |
|
233 |
return "lemon::IoError"; |
|
234 |
} |
|
235 |
}; |
|
236 |
|
|
237 |
///\e |
|
238 |
class DataFormatError : public IoError { |
|
239 |
protected: |
|
240 |
ExceptionMember<std::string> _message; |
|
241 |
ExceptionMember<std::string> _file; |
|
242 |
int _line; |
|
243 |
|
|
244 |
mutable ExceptionMember<std::string> _message_holder; |
|
245 |
public: |
|
246 |
|
|
247 |
DataFormatError(const DataFormatError &dfe) : |
|
248 |
IoError(dfe), _message(dfe._message), _file(dfe._file), |
|
249 |
_line(dfe._line) {} |
|
250 |
|
|
251 |
///\e |
|
252 |
explicit DataFormatError(const char *the_message) |
|
253 |
: _message(the_message), _line(0) {} |
|
254 |
|
|
255 |
///\e |
|
256 |
DataFormatError(const std::string &file_name, int line_num, |
|
257 |
const char *the_message) |
|
258 |
: _message(the_message), _line(line_num) { file(file_name); } |
|
259 |
|
|
260 |
///\e |
|
261 |
void line(int ln) { _line = ln; } |
|
262 |
///\e |
|
263 |
void message(const std::string& msg) { _message.set(msg); } |
|
264 |
///\e |
|
265 |
void file(const std::string &fl) { _file.set(fl); } |
|
266 |
|
|
267 |
///\e |
|
268 |
int line() const { return _line; } |
|
269 |
///\e |
|
270 |
const char* message() const { |
|
271 |
if (_message.valid() && !_message.get().empty()) { |
|
272 |
return _message.get().c_str(); |
|
273 |
} else { |
|
274 |
return 0; |
|
275 |
} |
|
276 |
} |
|
277 |
|
|
278 |
/// \brief Returns the filename. |
|
279 |
/// |
|
280 |
/// Returns \e null if the filename was not specified. |
|
281 |
const char* file() const { |
|
282 |
if (_file.valid() && !_file.get().empty()) { |
|
283 |
return _file.get().c_str(); |
|
284 |
} else { |
|
285 |
return 0; |
|
286 |
} |
|
287 |
} |
|
288 |
|
|
289 |
///\e |
|
290 |
virtual const char* what() const throw() { |
|
291 |
try { |
|
292 |
std::ostringstream ostr; |
|
293 |
ostr << "lemon:DataFormatError" << ": "; |
|
294 |
if (message()) ostr << message(); |
|
295 |
if( file() || line() != 0 ) { |
|
296 |
ostr << " ("; |
|
297 |
if( file() ) ostr << "in file '" << file() << "'"; |
|
298 |
if( file() && line() != 0 ) ostr << " "; |
|
299 |
if( line() != 0 ) ostr << "at line " << line(); |
|
300 |
ostr << ")"; |
|
301 |
} |
|
302 |
_message_holder.set(ostr.str()); |
|
303 |
} |
|
304 |
catch (...) {} |
|
305 |
if( _message_holder.valid()) return _message_holder.get().c_str(); |
|
306 |
return "lemon:DataFormatError"; |
|
307 |
} |
|
308 |
|
|
309 |
virtual ~DataFormatError() throw() {} |
|
310 |
}; |
|
311 |
|
|
312 |
///\e |
|
313 |
class FileOpenError : public IoError { |
|
314 |
protected: |
|
315 |
ExceptionMember<std::string> _file; |
|
316 |
|
|
317 |
mutable ExceptionMember<std::string> _message_holder; |
|
318 |
public: |
|
319 |
|
|
320 |
FileOpenError(const FileOpenError &foe) : |
|
321 |
IoError(foe), _file(foe._file) {} |
|
322 |
|
|
323 |
///\e |
|
324 |
explicit FileOpenError(const std::string& fl) |
|
325 |
: _file(fl) {} |
|
326 |
|
|
327 |
|
|
328 |
///\e |
|
329 |
void file(const std::string &fl) { _file.set(fl); } |
|
330 |
|
|
331 |
/// \brief Returns the filename. |
|
332 |
/// |
|
333 |
/// Returns \e null if the filename was not specified. |
|
334 |
const char* file() const { |
|
335 |
if (_file.valid() && !_file.get().empty()) { |
|
336 |
return _file.get().c_str(); |
|
337 |
} else { |
|
338 |
return 0; |
|
339 |
} |
|
340 |
} |
|
341 |
|
|
342 |
///\e |
|
343 |
virtual const char* what() const throw() { |
|
344 |
try { |
|
345 |
std::ostringstream ostr; |
|
346 |
ostr << "lemon::FileOpenError" << ": "; |
|
347 |
ostr << "Cannot open file - " << file(); |
|
348 |
_message_holder.set(ostr.str()); |
|
349 |
} |
|
350 |
catch (...) {} |
|
351 |
if( _message_holder.valid()) return _message_holder.get().c_str(); |
|
352 |
return "lemon::FileOpenError"; |
|
353 |
} |
|
354 |
virtual ~FileOpenError() throw() {} |
|
355 |
}; |
|
356 |
|
|
357 |
class IoParameterError : public IoError { |
|
358 |
protected: |
|
359 |
ExceptionMember<std::string> _message; |
|
360 |
ExceptionMember<std::string> _file; |
|
361 |
|
|
362 |
mutable ExceptionMember<std::string> _message_holder; |
|
363 |
public: |
|
364 |
|
|
365 |
IoParameterError(const IoParameterError &ile) : |
|
366 |
IoError(ile), _message(ile._message), _file(ile._file) {} |
|
367 |
|
|
368 |
///\e |
|
369 |
explicit IoParameterError(const char *the_message) |
|
370 |
: _message(the_message) {} |
|
371 |
|
|
372 |
///\e |
|
373 |
IoParameterError(const char *file_name, const char *the_message) |
|
374 |
: _message(the_message), _file(file_name) {} |
|
375 |
|
|
376 |
///\e |
|
377 |
void message(const std::string& msg) { _message.set(msg); } |
|
378 |
///\e |
|
379 |
void file(const std::string &fl) { _file.set(fl); } |
|
380 |
|
|
381 |
///\e |
|
382 |
const char* message() const { |
|
383 |
if (_message.valid()) { |
|
384 |
return _message.get().c_str(); |
|
385 |
} else { |
|
386 |
return 0; |
|
387 |
} |
|
388 |
} |
|
389 |
|
|
390 |
/// \brief Returns the filename. |
|
391 |
/// |
|
392 |
/// Returns \c 0 if the filename was not specified. |
|
393 |
const char* file() const { |
|
394 |
if (_file.valid()) { |
|
395 |
return _file.get().c_str(); |
|
396 |
} else { |
|
397 |
return 0; |
|
398 |
} |
|
399 |
} |
|
400 |
|
|
401 |
///\e |
|
402 |
virtual const char* what() const throw() { |
|
403 |
try { |
|
404 |
std::ostringstream ostr; |
|
405 |
if (message()) ostr << message(); |
|
406 |
if (file()) ostr << "(when reading file '" << file() << "')"; |
|
407 |
_message_holder.set(ostr.str()); |
|
408 |
} |
|
409 |
catch (...) {} |
|
410 |
if( _message_holder.valid() ) return _message_holder.get().c_str(); |
|
411 |
return "lemon:IoParameterError"; |
|
412 |
} |
|
413 |
virtual ~IoParameterError() throw() {} |
|
414 |
}; |
|
415 |
|
|
416 |
|
|
417 |
///\e |
|
418 |
class AssertionFailedError : public LogicError { |
|
419 |
protected: |
|
420 |
const char *assertion; |
|
421 |
const char *file; |
|
422 |
int line; |
|
423 |
const char *function; |
|
424 |
const char *message; |
|
425 |
|
|
426 |
mutable ExceptionMember<std::string> _message_holder; |
|
427 |
public: |
|
428 |
///\e |
|
429 |
AssertionFailedError(const char *_file, int _line, const char *func, |
|
430 |
const char *msg, const char *_assertion = 0) : |
|
431 |
assertion(_assertion), file(_file), line(_line), function(func), |
|
432 |
message(msg) {} |
|
433 |
|
|
434 |
///\e |
|
435 |
const char* get_assertion() const { return assertion; } |
|
436 |
///\e |
|
437 |
const char* get_message() const { return message; } |
|
438 |
///\e |
|
439 |
const char* get_file() const { return file; } |
|
440 |
///\e |
|
441 |
const char* get_function() const { return function; } |
|
442 |
///\e |
|
443 |
int get_line() const { return line; } |
|
444 |
|
|
445 |
|
|
446 |
virtual const char* what() const throw() { |
|
447 |
try { |
|
448 |
std::ostringstream ostr; |
|
449 |
ostr << file << ":" << line << ": "; |
|
450 |
if( function ) |
|
451 |
ostr << function << ": "; |
|
452 |
ostr << message; |
|
453 |
if( assertion ) |
|
454 |
ostr << " (assertion '" << assertion << "' failed)"; |
|
455 |
_message_holder.set(ostr.str()); |
|
456 |
return ostr.str().c_str(); |
|
457 |
} |
|
458 |
catch(...) {} |
|
459 |
if( _message_holder.valid() ) return _message_holder.get().c_str(); |
|
460 |
return "lemon::AssertionFailedError"; |
|
461 |
} |
|
462 |
virtual ~AssertionFailedError() throw() {} |
|
463 |
}; |
|
464 |
|
|
465 |
|
|
466 |
/**************** Macros ****************/ |
|
467 |
|
|
468 |
|
|
469 |
template <typename Exception> |
|
470 |
inline void assert_fail(const char *file, int line, |
|
471 |
const char *func, |
|
472 |
Exception exception, |
|
473 |
const char *assertion = 0, |
|
474 |
bool do_abort=true) |
|
475 |
{ |
|
476 |
using namespace std; |
|
477 |
cerr << file << ":" << line << ": "; |
|
478 |
if (func) |
|
479 |
cerr << func << ": "; |
|
480 |
cerr << exception.what(); |
|
481 |
if (assertion) |
|
482 |
cerr << " (assertion '" << assertion << "' failed)"; |
|
483 |
cerr << endl; |
|
484 |
if (do_abort) |
|
485 |
abort(); |
|
486 |
} |
|
487 |
|
|
488 |
template <> |
|
489 |
inline void assert_fail<const char *>(const char *file, int line, |
|
490 |
const char *func, |
|
491 |
const char *message, |
|
492 |
const char *assertion, |
|
493 |
bool do_abort) |
|
494 |
{ |
|
495 |
using namespace std; |
|
496 |
cerr << file << ":" << line << ": "; |
|
497 |
if (func) |
|
498 |
cerr << func << ": "; |
|
499 |
cerr << message; |
|
500 |
if (assertion) |
|
501 |
cerr << " (assertion '" << assertion << "' failed)"; |
|
502 |
cerr << endl; |
|
503 |
if (do_abort) |
|
504 |
abort(); |
|
505 |
} |
|
506 |
|
|
507 |
template <> |
|
508 |
inline void assert_fail<std::string>(const char *file, int line, |
|
509 |
const char *func, |
|
510 |
std::string message, |
|
511 |
const char *assertion, |
|
512 |
bool do_abort) |
|
513 |
{ |
|
514 |
assert_fail(file, line, func, message.c_str(), assertion, do_abort); |
|
515 |
} |
|
516 |
|
|
517 |
template <typename Exception> |
|
518 |
inline void assert_fail_failure(const char *file, int line, const char *func, |
|
519 |
Exception exception, |
|
520 |
const char *assertion = 0, |
|
521 |
bool = true) |
|
522 |
{ |
|
523 |
throw AssertionFailedError(file, line, func, exception.what(), assertion); |
|
524 |
} |
|
525 |
|
|
526 |
template <> |
|
527 |
inline void assert_fail_failure<const char *>(const char *file, int line, |
|
528 |
const char *func, |
|
529 |
const char *message, |
|
530 |
const char *assertion, |
|
531 |
bool) |
|
532 |
{ |
|
533 |
throw AssertionFailedError(file, line, func, message, assertion); |
|
534 |
} |
|
535 |
|
|
536 |
template <> |
|
537 |
inline void assert_fail_failure<std::string>(const char *file, int line, |
|
538 |
const char *func, |
|
539 |
std::string message, |
|
540 |
const char *assertion, |
|
541 |
bool) |
|
542 |
{ |
|
543 |
assert_fail_failure(file, line, func, message.c_str(), assertion, true); |
|
544 |
} |
|
545 |
|
|
546 |
template <typename Exception> |
|
547 |
inline void assert_fail_exception(const char *file, int line, const char *func, |
|
548 |
Exception exception, |
|
549 |
const char *assertion = 0, bool = true) |
|
550 |
{ |
|
551 |
throw exception; |
|
552 |
} |
|
553 |
|
|
554 |
template <> |
|
555 |
inline void assert_fail_exception<const char *>(const char *file, int line, |
|
556 |
const char *func, |
|
557 |
const char *message, |
|
558 |
const char *assertion, |
|
559 |
bool) |
|
560 |
{ |
|
561 |
throw AssertionFailedError(file, line, func, message, assertion); |
|
562 |
} |
|
563 |
|
|
564 |
template <> |
|
565 |
inline void assert_fail_exception<std::string>(const char *file, int line, |
|
566 |
const char *func, |
|
567 |
std::string message, |
|
568 |
const char *assertion, |
|
569 |
bool) |
|
570 |
{ |
|
571 |
assert_fail_exception(file, line, func, message.c_str(), assertion, true); |
|
572 |
} |
|
573 |
|
|
574 |
/// @} |
|
575 |
|
|
576 |
} |
|
577 |
#endif // LEMON_ERROR_H |
|
578 |
|
|
579 |
#undef LEMON_ASSERT |
|
580 |
#undef LEMON_FIXME |
|
581 |
|
|
582 |
#ifdef LEMON_ENABLE_ASSERTS |
|
583 |
# define LEMON_ASSERT_ABORT |
|
584 |
#endif |
|
585 |
|
|
586 |
#ifndef LEMON_ASSERT_DO_ABORT |
|
587 |
# define LEMON_ASSERT_DO_ABORT 1 |
|
588 |
#endif |
|
589 |
|
|
590 |
#ifndef LEMON_ASSERT_HANDLER |
|
591 |
# if defined LEMON_ASSERT_EXCEPTION |
|
592 |
# define LEMON_ASSERT_HANDLER ::lemon::assert_fail_exception |
|
593 |
# elif defined LEMON_ASSERT_FAILURE |
|
594 |
# define LEMON_ASSERT_HANDLER ::lemon::assert_fail_failure |
|
595 |
# elif defined LEMON_ASSERT_ABORT |
|
596 |
# define LEMON_ASSERT_HANDLER ::lemon::assert_fail |
|
597 |
# else |
|
598 |
# define LEMON_DISABLE_ASSERTS |
|
599 |
# endif |
|
600 |
#endif |
|
601 |
|
|
602 |
#ifdef DOXYGEN |
|
603 |
|
|
604 |
/// \brief Macro for assertions with customizable message |
|
605 |
/// |
|
606 |
/// Macro for assertions with customizable message. |
|
607 |
/// |
|
608 |
/// The assertions are disabled in the default behaviour. You can |
|
609 |
/// enable the assertions with the |
|
610 |
/// \code |
|
611 |
/// #define LEMON_ENABLE_ASSERTS |
|
612 |
/// \endcode |
|
613 |
/// Then an assert |
|
614 |
/// provides a log on the standard error about the assertion and aborts |
|
615 |
/// the program if LEMON_ASSERT_DO_ABORT is also defined (otherwise the |
|
616 |
/// program keeps on running). |
|
617 |
/// By defining LEMON_ASSERT_FAILURE or |
|
618 |
/// LEMON_ASSERT_EXCEPTION, you can set other behaviour to the |
|
619 |
/// assertions. In case LEMON_ASSERT_FAILURE is given, LEMON_ASSERT |
|
620 |
/// will always throw an \c AssertionFailedError exception with |
|
621 |
/// the \c msg error message. By using |
|
622 |
/// LEMON_ASSERT_EXCEPTION, one can define an arbitrary exception to be thrown. |
|
623 |
/// |
|
624 |
/// The LEMON_ASSERT macro should be called with the \c exp parameter |
|
625 |
/// which should be an expression convertible to bool. If the given |
|
626 |
/// parameter is false the assertion is raised and one of the assertion |
|
627 |
/// behaviour will be activated. The \c msg should be either a const |
|
628 |
/// char* message or an exception. When the \c msg is an exception the |
|
629 |
/// \ref lemon::Exception::what() "what()" function is called to retrieve and |
|
630 |
/// display the error message. |
|
631 |
/// |
|
632 |
/// \todo We should provide some way to reset to the default behaviour, |
|
633 |
/// shouldn't we? |
|
634 |
/// |
|
635 |
/// \todo This whole 'assert' business should be placed in a separate |
|
636 |
/// include file. The boost assert is not guarded by header sentries |
|
637 |
/// which may help to change the behaviour of the assertions in |
|
638 |
/// the files. |
|
639 |
/// |
|
640 |
/// \todo __PRETTY_FUNCTION__ should be replaced by something |
|
641 |
/// compiler-independent, like BOOST_CURRENT_FUNCTION |
|
642 |
|
|
643 |
# define LEMON_ASSERT(exp, msg) \ |
|
644 |
(static_cast<void> (!!(exp) ? 0 : ( \ |
|
645 |
LEMON_ASSERT_HANDLER(__FILE__, __LINE__, \ |
|
646 |
__PRETTY_FUNCTION__, \ |
|
647 |
msg, #exp, LEMON_ASSERT_DO_ABORT), 0))) |
|
648 |
|
|
649 |
#else |
|
650 |
# if defined LEMON_DISABLE_ASSERTS |
|
651 |
|
|
652 |
# define LEMON_ASSERT(exp, msg) (static_cast<void> (0)) |
|
653 |
|
|
654 |
# else |
|
655 |
# define LEMON_ASSERT(exp, msg) \ |
|
656 |
(static_cast<void> (!!(exp) ? 0 : ( \ |
|
657 |
LEMON_ASSERT_HANDLER(__FILE__, __LINE__, \ |
|
658 |
__PRETTY_FUNCTION__, \ |
|
659 |
msg, #exp, LEMON_ASSERT_DO_ABORT), 0))) |
|
660 |
# endif |
|
661 |
#endif |
|
662 |
|
|
663 |
/** |
|
664 |
* \brief Macro for mark not yet implemented features. |
|
665 |
* |
|
666 |
* \todo Is this the right place for this? It should be used only in |
|
667 |
* modules under development. |
|
668 |
* |
|
669 |
* \todo __PRETTY_FUNCTION__ should be replaced by something |
|
670 |
* compiler-independent, like BOOST_CURRENT_FUNCTION |
|
671 |
*/ |
|
672 |
|
|
673 |
#define LEMON_FIXME(msg) \ |
|
674 |
(LEMON_ASSERT_HANDLER(__FILE__, __LINE__, __PRETTY_FUNCTION__, \ |
|
675 |
"FIXME: " msg)) |
1 |
/* -*- C++ -*- |
|
2 |
* |
|
3 |
* This file is a part of LEMON, a generic C++ optimization library |
|
4 |
* |
|
5 |
* Copyright (C) 2003-2008 |
|
6 |
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
|
7 |
* (Egervary Research Group on Combinatorial Optimization, EGRES). |
|
8 |
* |
|
9 |
* Permission to use, modify and distribute this software is granted |
|
10 |
* provided that this copyright notice appears in all copies. For |
|
11 |
* precise terms see the accompanying LICENSE file. |
|
12 |
* |
|
13 |
* This software is provided "AS IS" with no warranty of any kind, |
|
14 |
* express or implied, and with no claim as to its suitability for any |
|
15 |
* purpose. |
|
16 |
* |
|
17 |
*/ |
|
18 |
|
|
19 |
#include <iostream> |
|
20 |
|
|
21 |
#include <lemon/error.h> |
|
22 |
#include "test_tools.h" |
|
23 |
|
|
24 |
using namespace lemon; |
|
25 |
using std::cout; |
|
26 |
using std::endl; |
|
27 |
|
|
28 |
void faulty_fn() { |
|
29 |
fault("This is a fault message"); |
|
30 |
} |
|
31 |
|
|
32 |
void exception_fn() { |
|
33 |
throw Exception("This is a function throwing exception with some args: ") |
|
34 |
<< 5 << ", " << 18; |
|
35 |
} |
|
36 |
|
|
37 |
void unfinished_fn() { |
|
38 |
LEMON_FIXME("unfinished_fn() is unfinished!"); |
|
39 |
} |
|
40 |
|
|
41 |
|
|
42 |
int main() { |
|
43 |
try { |
|
44 |
faulty_fn(); |
|
45 |
check(false, "A faulty function did not fail."); |
|
46 |
} |
|
47 |
catch(const Exception &e) { |
|
48 |
cout << "Exeption = \"" << e.what() << "\" (Right behaviour)" << endl; |
|
49 |
} |
|
50 |
|
|
51 |
try { |
|
52 |
exception_fn(); |
|
53 |
check(false, "The function did not throw Exception."); |
|
54 |
} |
|
55 |
catch(const Exception &e) { |
|
56 |
cout << "Exeption = \"" << e.what() << "\" (Right behaviour)" << endl; |
|
57 |
} |
|
58 |
|
|
59 |
try { |
|
60 |
unfinished_fn(); |
|
61 |
check(false, "FIXME macro does not work."); |
|
62 |
} |
|
63 |
catch(const Exception &e) { |
|
64 |
cout << "Exeption = \"" << e.what() << "\" (Right behaviour)" << endl; |
|
65 |
} |
|
66 |
|
|
67 |
return 0; |
|
68 |
} |
1 | 1 |
dnl Process this file with autoconf to produce a configure script. |
2 | 2 |
|
3 | 3 |
dnl Version information. |
4 | 4 |
m4_define([lemon_version_major], [0]) |
5 | 5 |
m4_define([lemon_version_minor], [99]) |
6 | 6 |
m4_define([lemon_version_micro], []) |
7 | 7 |
m4_define([lemon_version_nano], []) |
8 | 8 |
m4_define([lemon_version_tag], [hg]) |
9 | 9 |
m4_define([lemon_hg_revision], [m4_normalize(esyscmd([hg id -i]))]) |
10 | 10 |
m4_define([lemon_version], [lemon_version_major().lemon_version_minor()ifelse(lemon_version_micro(), [], [], [.lemon_version_micro()])ifelse(lemon_version_nano(), [], [], [.lemon_version_nano()])ifelse(lemon_version_tag(), [], [], lemon_version_tag(), [hg], [[_]lemon_version_tag()[_]lemon_hg_revision()], [[_]lemon_version_tag()])]) |
11 | 11 |
|
12 | 12 |
AC_PREREQ([2.59]) |
13 | 13 |
AC_INIT([LEMON], [lemon_version()], [etik-ol@cs.elte.hu], [lemon]) |
14 | 14 |
AC_CONFIG_AUX_DIR([build-aux]) |
15 | 15 |
AC_CONFIG_MACRO_DIR([m4]) |
16 |
AM_INIT_AUTOMAKE([-Wall -Werror foreign subdir-objects]) |
|
16 |
AM_INIT_AUTOMAKE([-Wall -Werror foreign subdir-objects nostdinc]) |
|
17 | 17 |
AC_CONFIG_SRCDIR([lemon/list_graph.h]) |
18 | 18 |
AC_CONFIG_HEADERS([config.h lemon/config.h]) |
19 | 19 |
|
20 | 20 |
lx_cmdline_cxxflags_set=${CXXFLAGS+set} |
21 | 21 |
|
22 | 22 |
dnl Checks for programs. |
23 | 23 |
AC_PROG_CXX |
24 | 24 |
AC_PROG_CXXCPP |
25 | 25 |
AC_PROG_INSTALL |
26 | 26 |
AC_DISABLE_SHARED |
27 | 27 |
AC_PROG_LIBTOOL |
28 | 28 |
|
29 | 29 |
AC_CHECK_PROG([doxygen_found],[doxygen],[yes],[no]) |
30 | 30 |
|
31 | 31 |
if test x"$lx_cmdline_cxxflags_set" != x"set" -a "$GXX" = yes; then |
32 | 32 |
CXXFLAGS="$CXXFLAGS -Wall -W -Wall -W -Wunused -Wformat=2 -Wctor-dtor-privacy -Wnon-virtual-dtor -Wno-char-subscripts -Wwrite-strings -Wno-char-subscripts -Wreturn-type -Wcast-qual -Wcast-align -Wsign-promo -Woverloaded-virtual -Woverloaded-virtual -ansi -fno-strict-aliasing -Wold-style-cast -Wno-unknown-pragmas" |
33 | 33 |
fi |
34 | 34 |
|
35 | 35 |
dnl Checks for libraries. |
36 | 36 |
LX_CHECK_GLPK |
37 | 37 |
LX_CHECK_CPLEX |
38 | 38 |
LX_CHECK_SOPLEX |
39 | 39 |
|
40 | 40 |
dnl Disable/enable building the demo programs |
41 | 41 |
AC_ARG_ENABLE([demo], |
42 | 42 |
AS_HELP_STRING([--enable-demo], [build the demo programs]) |
43 | 43 |
AS_HELP_STRING([--disable-demo], [do not build the demo programs @<:@default@:>@]), |
44 | 44 |
[], [enable_demo=no]) |
45 | 45 |
AC_MSG_CHECKING([whether to build the demo programs]) |
46 | 46 |
if test x"$enable_demo" != x"no"; then |
47 | 47 |
AC_MSG_RESULT([yes]) |
48 | 48 |
else |
49 | 49 |
AC_MSG_RESULT([no]) |
50 | 50 |
fi |
51 | 51 |
AM_CONDITIONAL([WANT_DEMO], [test x"$enable_demo" != x"no"]) |
52 | 52 |
|
53 | 53 |
dnl Disable/enable building the binary tools |
54 | 54 |
AC_ARG_ENABLE([tools], |
55 | 55 |
AS_HELP_STRING([--enable-tools], [build additional tools @<:@default@:>@]) |
56 | 56 |
AS_HELP_STRING([--disable-tools], [do not build additional tools]), |
57 | 57 |
[], [enable_tools=yes]) |
58 | 58 |
AC_MSG_CHECKING([whether to build the additional tools]) |
59 | 59 |
if test x"$enable_tools" != x"no"; then |
60 | 60 |
AC_MSG_RESULT([yes]) |
61 | 61 |
else |
62 | 62 |
AC_MSG_RESULT([no]) |
63 | 63 |
fi |
64 | 64 |
AM_CONDITIONAL([WANT_TOOLS], [test x"$enable_tools" != x"no"]) |
65 | 65 |
|
66 | 66 |
dnl Disable/enable building the benchmarks |
67 | 67 |
AC_ARG_ENABLE([benchmark], |
68 | 68 |
AS_HELP_STRING([--enable-benchmark], [build the benchmarks]) |
69 | 69 |
AS_HELP_STRING([--disable-benchmark], [do not build the benchmarks @<:@default@:>@]), |
70 | 70 |
[], [enable_benchmark=no]) |
71 | 71 |
AC_MSG_CHECKING([whether to build the benchmarks]) |
72 | 72 |
if test x"$enable_benchmark" != x"no"; then |
73 | 73 |
AC_MSG_RESULT([yes]) |
74 | 74 |
else |
75 | 75 |
AC_MSG_RESULT([no]) |
76 | 76 |
fi |
77 | 77 |
AM_CONDITIONAL([WANT_BENCHMARK], [test x"$enable_benchmark" != x"no"]) |
78 | 78 |
|
79 | 79 |
dnl Checks for header files. |
80 | 80 |
AC_CHECK_HEADERS(limits.h sys/time.h sys/times.h unistd.h) |
81 | 81 |
|
82 | 82 |
dnl Checks for typedefs, structures, and compiler characteristics. |
83 | 83 |
AC_C_CONST |
84 | 84 |
AC_C_INLINE |
85 | 85 |
AC_TYPE_SIZE_T |
86 | 86 |
AC_HEADER_TIME |
87 | 87 |
AC_STRUCT_TM |
88 | 88 |
|
89 | 89 |
dnl Checks for library functions. |
90 | 90 |
AC_HEADER_STDC |
91 | 91 |
AC_CHECK_FUNCS(gettimeofday times ctime_r) |
92 | 92 |
|
93 | 93 |
AC_CONFIG_FILES([ |
94 | 94 |
Makefile |
95 | 95 |
doc/Doxyfile |
96 | 96 |
lemon/lemon.pc |
97 | 97 |
]) |
98 | 98 |
|
99 | 99 |
AC_OUTPUT |
100 | 100 |
|
101 | 101 |
echo |
102 | 102 |
echo '****************************** SUMMARY ******************************' |
103 | 103 |
echo |
104 | 104 |
echo Package version............... : $PACKAGE-$VERSION |
105 | 105 |
echo |
106 | 106 |
echo C++ compiler.................. : $CXX |
107 | 107 |
echo C++ compiles flags............ : $CXXFLAGS |
108 | 108 |
echo |
109 | 109 |
echo GLPK support.................. : $lx_glpk_found |
110 | 110 |
echo CPLEX support................. : $lx_cplex_found |
111 | 111 |
echo SOPLEX support................ : $lx_soplex_found |
112 | 112 |
echo |
113 | 113 |
echo Build benchmarks.............. : $enable_benchmark |
114 | 114 |
echo Build demo programs........... : $enable_demo |
115 | 115 |
echo Build additional tools........ : $enable_tools |
116 | 116 |
echo |
117 | 117 |
echo The packace will be installed in |
118 | 118 |
echo -n ' ' |
119 | 119 |
echo $prefix. |
120 | 120 |
echo |
121 | 121 |
echo '*********************************************************************' |
122 | 122 |
|
123 | 123 |
echo |
124 | 124 |
echo Configure complete, now type \'make\' and then \'make install\'. |
125 | 125 |
echo |
1 | 1 |
EXTRA_DIST += \ |
2 | 2 |
lemon/Makefile \ |
3 | 3 |
lemon/lemon.pc.in |
4 | 4 |
|
5 | 5 |
pkgconfig_DATA += lemon/lemon.pc |
6 | 6 |
|
7 | 7 |
lib_LTLIBRARIES += lemon/libemon.la |
8 | 8 |
|
9 | 9 |
lemon_libemon_la_SOURCES = \ |
10 | 10 |
lemon/base.cc \ |
11 | 11 |
lemon/random.cc |
12 | 12 |
|
13 | 13 |
|
14 | 14 |
lemon_libemon_la_CXXFLAGS = $(GLPK_CFLAGS) $(CPLEX_CFLAGS) $(SOPLEX_CXXFLAGS) |
15 | 15 |
lemon_libemon_la_LDFLAGS = $(GLPK_LIBS) $(CPLEX_LIBS) $(SOPLEX_LIBS) |
16 | 16 |
|
17 | 17 |
lemon_HEADERS += \ |
18 |
lemon/concept_check.h \ |
|
18 | 19 |
lemon/dim2.h \ |
20 |
lemon/error.h \ |
|
21 |
lemon/list_graph.h \ |
|
19 | 22 |
lemon/maps.h \ |
20 | 23 |
lemon/path.h \ |
21 | 24 |
lemon/random.h \ |
22 |
lemon/list_graph.h \ |
|
23 | 25 |
lemon/tolerance.h |
24 | 26 |
|
25 | 27 |
bits_HEADERS += \ |
26 | 28 |
lemon/bits/alteration_notifier.h \ |
27 | 29 |
lemon/bits/array_map.h \ |
28 | 30 |
lemon/bits/base_extender.h \ |
29 | 31 |
lemon/bits/default_map.h \ |
30 | 32 |
lemon/bits/graph_extender.h \ |
31 | 33 |
lemon/bits/invalid.h \ |
32 | 34 |
lemon/bits/map_extender.h \ |
33 | 35 |
lemon/bits/traits.h \ |
34 | 36 |
lemon/bits/utility.h \ |
35 | 37 |
lemon/bits/vector_map.h |
36 | 38 |
|
37 | 39 |
concept_HEADERS += \ |
38 | 40 |
lemon/concept_check.h \ |
39 | 41 |
lemon/concepts/digraph.h \ |
40 | 42 |
lemon/concepts/graph.h \ |
41 | 43 |
lemon/concepts/maps.h \ |
42 | 44 |
lemon/concepts/path.h \ |
43 | 45 |
lemon/concepts/graph_components.h |
... | ... |
@@ -159,295 +159,328 @@ |
159 | 159 |
|
160 | 160 |
|
161 | 161 |
/// Class for identifying an arc of the digraph |
162 | 162 |
|
163 | 163 |
/// This class identifies an arc of the digraph. It also serves |
164 | 164 |
/// as a base class of the arc iterators, |
165 | 165 |
/// thus they will convert to this type. |
166 | 166 |
class Arc { |
167 | 167 |
public: |
168 | 168 |
/// Default constructor |
169 | 169 |
|
170 | 170 |
/// @warning The default constructor sets the iterator |
171 | 171 |
/// to an undefined value. |
172 | 172 |
Arc() { } |
173 | 173 |
/// Copy constructor. |
174 | 174 |
|
175 | 175 |
/// Copy constructor. |
176 | 176 |
/// |
177 | 177 |
Arc(const Arc&) { } |
178 | 178 |
/// Initialize the iterator to be invalid. |
179 | 179 |
|
180 | 180 |
/// Initialize the iterator to be invalid. |
181 | 181 |
/// |
182 | 182 |
Arc(Invalid) { } |
183 | 183 |
/// Equality operator |
184 | 184 |
|
185 | 185 |
/// Two iterators are equal if and only if they point to the |
186 | 186 |
/// same object or both are invalid. |
187 | 187 |
bool operator==(Arc) const { return true; } |
188 | 188 |
/// Inequality operator |
189 | 189 |
|
190 | 190 |
/// \sa operator==(Arc n) |
191 | 191 |
/// |
192 | 192 |
bool operator!=(Arc) const { return true; } |
193 | 193 |
|
194 | 194 |
/// Artificial ordering operator. |
195 | 195 |
|
196 | 196 |
/// To allow the use of digraph descriptors as key type in std::map or |
197 | 197 |
/// similar associative container we require this. |
198 | 198 |
/// |
199 | 199 |
/// \note This operator only have to define some strict ordering of |
200 | 200 |
/// the items; this order has nothing to do with the iteration |
201 | 201 |
/// ordering of the items. |
202 | 202 |
bool operator<(Arc) const { return false; } |
203 | 203 |
}; |
204 | 204 |
|
205 | 205 |
/// This iterator goes trough the outgoing arcs of a node. |
206 | 206 |
|
207 | 207 |
/// This iterator goes trough the \e outgoing arcs of a certain node |
208 | 208 |
/// of a digraph. |
209 | 209 |
/// Its usage is quite simple, for example you can count the number |
210 | 210 |
/// of outgoing arcs of a node \c n |
211 | 211 |
/// in digraph \c g of type \c Digraph as follows. |
212 | 212 |
///\code |
213 | 213 |
/// int count=0; |
214 | 214 |
/// for (Digraph::OutArcIt e(g, n); e!=INVALID; ++e) ++count; |
215 | 215 |
///\endcode |
216 | 216 |
|
217 | 217 |
class OutArcIt : public Arc { |
218 | 218 |
public: |
219 | 219 |
/// Default constructor |
220 | 220 |
|
221 | 221 |
/// @warning The default constructor sets the iterator |
222 | 222 |
/// to an undefined value. |
223 | 223 |
OutArcIt() { } |
224 | 224 |
/// Copy constructor. |
225 | 225 |
|
226 | 226 |
/// Copy constructor. |
227 | 227 |
/// |
228 | 228 |
OutArcIt(const OutArcIt& e) : Arc(e) { } |
229 | 229 |
/// Initialize the iterator to be invalid. |
230 | 230 |
|
231 | 231 |
/// Initialize the iterator to be invalid. |
232 | 232 |
/// |
233 | 233 |
OutArcIt(Invalid) { } |
234 | 234 |
/// This constructor sets the iterator to the first outgoing arc. |
235 | 235 |
|
236 | 236 |
/// This constructor sets the iterator to the first outgoing arc of |
237 | 237 |
/// the node. |
238 | 238 |
OutArcIt(const Digraph&, const Node&) { } |
239 | 239 |
/// Arc -> OutArcIt conversion |
240 | 240 |
|
241 | 241 |
/// Sets the iterator to the value of the trivial iterator. |
242 | 242 |
/// This feature necessitates that each time we |
243 | 243 |
/// iterate the arc-set, the iteration order is the same. |
244 | 244 |
OutArcIt(const Digraph&, const Arc&) { } |
245 | 245 |
///Next outgoing arc |
246 | 246 |
|
247 | 247 |
/// Assign the iterator to the next |
248 | 248 |
/// outgoing arc of the corresponding node. |
249 | 249 |
OutArcIt& operator++() { return *this; } |
250 | 250 |
}; |
251 | 251 |
|
252 | 252 |
/// This iterator goes trough the incoming arcs of a node. |
253 | 253 |
|
254 | 254 |
/// This iterator goes trough the \e incoming arcs of a certain node |
255 | 255 |
/// of a digraph. |
256 | 256 |
/// Its usage is quite simple, for example you can count the number |
257 | 257 |
/// of outgoing arcs of a node \c n |
258 | 258 |
/// in digraph \c g of type \c Digraph as follows. |
259 | 259 |
///\code |
260 | 260 |
/// int count=0; |
261 | 261 |
/// for(Digraph::InArcIt e(g, n); e!=INVALID; ++e) ++count; |
262 | 262 |
///\endcode |
263 | 263 |
|
264 | 264 |
class InArcIt : public Arc { |
265 | 265 |
public: |
266 | 266 |
/// Default constructor |
267 | 267 |
|
268 | 268 |
/// @warning The default constructor sets the iterator |
269 | 269 |
/// to an undefined value. |
270 | 270 |
InArcIt() { } |
271 | 271 |
/// Copy constructor. |
272 | 272 |
|
273 | 273 |
/// Copy constructor. |
274 | 274 |
/// |
275 | 275 |
InArcIt(const InArcIt& e) : Arc(e) { } |
276 | 276 |
/// Initialize the iterator to be invalid. |
277 | 277 |
|
278 | 278 |
/// Initialize the iterator to be invalid. |
279 | 279 |
/// |
280 | 280 |
InArcIt(Invalid) { } |
281 | 281 |
/// This constructor sets the iterator to first incoming arc. |
282 | 282 |
|
283 | 283 |
/// This constructor set the iterator to the first incoming arc of |
284 | 284 |
/// the node. |
285 | 285 |
InArcIt(const Digraph&, const Node&) { } |
286 | 286 |
/// Arc -> InArcIt conversion |
287 | 287 |
|
288 | 288 |
/// Sets the iterator to the value of the trivial iterator \c e. |
289 | 289 |
/// This feature necessitates that each time we |
290 | 290 |
/// iterate the arc-set, the iteration order is the same. |
291 | 291 |
InArcIt(const Digraph&, const Arc&) { } |
292 | 292 |
/// Next incoming arc |
293 | 293 |
|
294 | 294 |
/// Assign the iterator to the next inarc of the corresponding node. |
295 | 295 |
/// |
296 | 296 |
InArcIt& operator++() { return *this; } |
297 | 297 |
}; |
298 | 298 |
/// This iterator goes through each arc. |
299 | 299 |
|
300 | 300 |
/// This iterator goes through each arc of a digraph. |
301 | 301 |
/// Its usage is quite simple, for example you can count the number |
302 | 302 |
/// of arcs in a digraph \c g of type \c Digraph as follows: |
303 | 303 |
///\code |
304 | 304 |
/// int count=0; |
305 | 305 |
/// for(Digraph::ArcIt e(g); e!=INVALID; ++e) ++count; |
306 | 306 |
///\endcode |
307 | 307 |
class ArcIt : public Arc { |
308 | 308 |
public: |
309 | 309 |
/// Default constructor |
310 | 310 |
|
311 | 311 |
/// @warning The default constructor sets the iterator |
312 | 312 |
/// to an undefined value. |
313 | 313 |
ArcIt() { } |
314 | 314 |
/// Copy constructor. |
315 | 315 |
|
316 | 316 |
/// Copy constructor. |
317 | 317 |
/// |
318 | 318 |
ArcIt(const ArcIt& e) : Arc(e) { } |
319 | 319 |
/// Initialize the iterator to be invalid. |
320 | 320 |
|
321 | 321 |
/// Initialize the iterator to be invalid. |
322 | 322 |
/// |
323 | 323 |
ArcIt(Invalid) { } |
324 | 324 |
/// This constructor sets the iterator to the first arc. |
325 | 325 |
|
326 | 326 |
/// This constructor sets the iterator to the first arc of \c g. |
327 | 327 |
///@param g the digraph |
328 | 328 |
ArcIt(const Digraph& g) { ignore_unused_variable_warning(g); } |
329 | 329 |
/// Arc -> ArcIt conversion |
330 | 330 |
|
331 | 331 |
/// Sets the iterator to the value of the trivial iterator \c e. |
332 | 332 |
/// This feature necessitates that each time we |
333 | 333 |
/// iterate the arc-set, the iteration order is the same. |
334 | 334 |
ArcIt(const Digraph&, const Arc&) { } |
335 | 335 |
///Next arc |
336 | 336 |
|
337 | 337 |
/// Assign the iterator to the next arc. |
338 | 338 |
ArcIt& operator++() { return *this; } |
339 | 339 |
}; |
340 | 340 |
///Gives back the target node of an arc. |
341 | 341 |
|
342 | 342 |
///Gives back the target node of an arc. |
343 | 343 |
/// |
344 | 344 |
Node target(Arc) const { return INVALID; } |
345 | 345 |
///Gives back the source node of an arc. |
346 | 346 |
|
347 | 347 |
///Gives back the source node of an arc. |
348 | 348 |
/// |
349 | 349 |
Node source(Arc) const { return INVALID; } |
350 | 350 |
|
351 |
/// \brief Returns the ID of the node. |
|
352 |
int id(Node) const { return -1; } |
|
353 |
|
|
354 |
/// \brief Returns the ID of the arc. |
|
355 |
int id(Arc) const { return -1; } |
|
356 |
|
|
357 |
/// \brief Returns the node with the given ID. |
|
358 |
/// |
|
359 |
/// \pre The argument should be a valid node ID in the graph. |
|
360 |
Node nodeFromId(int) const { return INVALID; } |
|
361 |
|
|
362 |
/// \brief Returns the arc with the given ID. |
|
363 |
/// |
|
364 |
/// \pre The argument should be a valid arc ID in the graph. |
|
365 |
Arc arcFromId(int) const { return INVALID; } |
|
366 |
|
|
367 |
/// \brief Returns an upper bound on the node IDs. |
|
368 |
int maxNodeId() const { return -1; } |
|
369 |
|
|
370 |
/// \brief Returns an upper bound on the arc IDs. |
|
371 |
int maxArcId() const { return -1; } |
|
372 |
|
|
351 | 373 |
void first(Node&) const {} |
352 | 374 |
void next(Node&) const {} |
353 | 375 |
|
354 | 376 |
void first(Arc&) const {} |
355 | 377 |
void next(Arc&) const {} |
356 | 378 |
|
357 | 379 |
|
358 | 380 |
void firstIn(Arc&, const Node&) const {} |
359 | 381 |
void nextIn(Arc&) const {} |
360 | 382 |
|
361 | 383 |
void firstOut(Arc&, const Node&) const {} |
362 | 384 |
void nextOut(Arc&) const {} |
363 | 385 |
|
386 |
// The second parameter is dummy. |
|
387 |
Node fromId(int, Node) const { return INVALID; } |
|
388 |
// The second parameter is dummy. |
|
389 |
Arc fromId(int, Arc) const { return INVALID; } |
|
390 |
|
|
391 |
// Dummy parameter. |
|
392 |
int maxId(Node) const { return -1; } |
|
393 |
// Dummy parameter. |
|
394 |
int maxId(Arc) const { return -1; } |
|
395 |
|
|
364 | 396 |
/// \brief The base node of the iterator. |
365 | 397 |
/// |
366 | 398 |
/// Gives back the base node of the iterator. |
367 | 399 |
/// It is always the target of the pointed arc. |
368 | 400 |
Node baseNode(const InArcIt&) const { return INVALID; } |
369 | 401 |
|
370 | 402 |
/// \brief The running node of the iterator. |
371 | 403 |
/// |
372 | 404 |
/// Gives back the running node of the iterator. |
373 | 405 |
/// It is always the source of the pointed arc. |
374 | 406 |
Node runningNode(const InArcIt&) const { return INVALID; } |
375 | 407 |
|
376 | 408 |
/// \brief The base node of the iterator. |
377 | 409 |
/// |
378 | 410 |
/// Gives back the base node of the iterator. |
379 | 411 |
/// It is always the source of the pointed arc. |
380 | 412 |
Node baseNode(const OutArcIt&) const { return INVALID; } |
381 | 413 |
|
382 | 414 |
/// \brief The running node of the iterator. |
383 | 415 |
/// |
384 | 416 |
/// Gives back the running node of the iterator. |
385 | 417 |
/// It is always the target of the pointed arc. |
386 | 418 |
Node runningNode(const OutArcIt&) const { return INVALID; } |
387 | 419 |
|
388 | 420 |
/// \brief The opposite node on the given arc. |
389 | 421 |
/// |
390 | 422 |
/// Gives back the opposite node on the given arc. |
391 | 423 |
Node oppositeNode(const Node&, const Arc&) const { return INVALID; } |
392 | 424 |
|
393 | 425 |
/// \brief Read write map of the nodes to type \c T. |
394 | 426 |
/// |
395 | 427 |
/// ReadWrite map of the nodes to type \c T. |
396 | 428 |
/// \sa Reference |
397 | 429 |
template<class T> |
398 | 430 |
class NodeMap : public ReadWriteMap< Node, T > { |
399 | 431 |
public: |
400 | 432 |
|
401 | 433 |
///\e |
402 | 434 |
NodeMap(const Digraph&) { } |
403 | 435 |
///\e |
404 | 436 |
NodeMap(const Digraph&, T) { } |
405 | 437 |
|
406 | 438 |
///Copy constructor |
407 | 439 |
NodeMap(const NodeMap& nm) : ReadWriteMap< Node, T >(nm) { } |
408 | 440 |
///Assignment operator |
409 | 441 |
template <typename CMap> |
410 | 442 |
NodeMap& operator=(const CMap&) { |
411 | 443 |
checkConcept<ReadMap<Node, T>, CMap>(); |
412 | 444 |
return *this; |
413 | 445 |
} |
414 | 446 |
}; |
415 | 447 |
|
416 | 448 |
/// \brief Read write map of the arcs to type \c T. |
417 | 449 |
/// |
418 | 450 |
/// Reference map of the arcs to type \c T. |
419 | 451 |
/// \sa Reference |
420 | 452 |
template<class T> |
421 | 453 |
class ArcMap : public ReadWriteMap<Arc,T> { |
422 | 454 |
public: |
423 | 455 |
|
424 | 456 |
///\e |
425 | 457 |
ArcMap(const Digraph&) { } |
426 | 458 |
///\e |
427 | 459 |
ArcMap(const Digraph&, T) { } |
428 | 460 |
///Copy constructor |
429 | 461 |
ArcMap(const ArcMap& em) : ReadWriteMap<Arc,T>(em) { } |
430 | 462 |
///Assignment operator |
431 | 463 |
template <typename CMap> |
432 | 464 |
ArcMap& operator=(const CMap&) { |
433 | 465 |
checkConcept<ReadMap<Arc, T>, CMap>(); |
434 | 466 |
return *this; |
435 | 467 |
} |
436 | 468 |
}; |
437 | 469 |
|
438 | 470 |
template <typename RDigraph> |
439 | 471 |
struct Constraints { |
440 | 472 |
void constraints() { |
441 | 473 |
checkConcept<IterableDigraphComponent<>, Digraph>(); |
474 |
checkConcept<IDableDigraphComponent<>, Digraph>(); |
|
442 | 475 |
checkConcept<MappableDigraphComponent<>, Digraph>(); |
443 | 476 |
} |
444 | 477 |
}; |
445 | 478 |
|
446 | 479 |
}; |
447 | 480 |
|
448 | 481 |
} //namespace concepts |
449 | 482 |
} //namespace lemon |
450 | 483 |
|
451 | 484 |
|
452 | 485 |
|
453 | 486 |
#endif // LEMON_CONCEPT_DIGRAPH_H |
... | ... |
@@ -435,268 +435,315 @@ |
435 | 435 |
} |
436 | 436 |
/// Arc -> OutArcIt conversion |
437 | 437 |
|
438 | 438 |
/// Sets the iterator to the value of the trivial iterator. |
439 | 439 |
/// This feature necessitates that each time we |
440 | 440 |
/// iterate the arc-set, the iteration order is the same. |
441 | 441 |
OutArcIt(const Graph&, const Arc&) { } |
442 | 442 |
///Next outgoing arc |
443 | 443 |
|
444 | 444 |
/// Assign the iterator to the next |
445 | 445 |
/// outgoing arc of the corresponding node. |
446 | 446 |
OutArcIt& operator++() { return *this; } |
447 | 447 |
}; |
448 | 448 |
|
449 | 449 |
/// This iterator goes trough the incoming directed arcs of a node. |
450 | 450 |
|
451 | 451 |
/// This iterator goes trough the \e incoming arcs of a certain node |
452 | 452 |
/// of a graph. |
453 | 453 |
/// Its usage is quite simple, for example you can count the number |
454 | 454 |
/// of outgoing arcs of a node \c n |
455 | 455 |
/// in graph \c g of type \c Graph as follows. |
456 | 456 |
///\code |
457 | 457 |
/// int count=0; |
458 | 458 |
/// for(Graph::InArcIt e(g, n); e!=INVALID; ++e) ++count; |
459 | 459 |
///\endcode |
460 | 460 |
|
461 | 461 |
class InArcIt : public Arc { |
462 | 462 |
public: |
463 | 463 |
/// Default constructor |
464 | 464 |
|
465 | 465 |
/// @warning The default constructor sets the iterator |
466 | 466 |
/// to an undefined value. |
467 | 467 |
InArcIt() { } |
468 | 468 |
/// Copy constructor. |
469 | 469 |
|
470 | 470 |
/// Copy constructor. |
471 | 471 |
/// |
472 | 472 |
InArcIt(const InArcIt& e) : Arc(e) { } |
473 | 473 |
/// Initialize the iterator to be invalid. |
474 | 474 |
|
475 | 475 |
/// Initialize the iterator to be invalid. |
476 | 476 |
/// |
477 | 477 |
InArcIt(Invalid) { } |
478 | 478 |
/// This constructor sets the iterator to first incoming arc. |
479 | 479 |
|
480 | 480 |
/// This constructor set the iterator to the first incoming arc of |
481 | 481 |
/// the node. |
482 | 482 |
///@param n the node |
483 | 483 |
///@param g the graph |
484 | 484 |
InArcIt(const Graph& g, const Node& n) { |
485 | 485 |
ignore_unused_variable_warning(n); |
486 | 486 |
ignore_unused_variable_warning(g); |
487 | 487 |
} |
488 | 488 |
/// Arc -> InArcIt conversion |
489 | 489 |
|
490 | 490 |
/// Sets the iterator to the value of the trivial iterator \c e. |
491 | 491 |
/// This feature necessitates that each time we |
492 | 492 |
/// iterate the arc-set, the iteration order is the same. |
493 | 493 |
InArcIt(const Graph&, const Arc&) { } |
494 | 494 |
/// Next incoming arc |
495 | 495 |
|
496 | 496 |
/// Assign the iterator to the next inarc of the corresponding node. |
497 | 497 |
/// |
498 | 498 |
InArcIt& operator++() { return *this; } |
499 | 499 |
}; |
500 | 500 |
|
501 | 501 |
/// \brief Read write map of the nodes to type \c T. |
502 | 502 |
/// |
503 | 503 |
/// ReadWrite map of the nodes to type \c T. |
504 | 504 |
/// \sa Reference |
505 | 505 |
template<class T> |
506 | 506 |
class NodeMap : public ReadWriteMap< Node, T > |
507 | 507 |
{ |
508 | 508 |
public: |
509 | 509 |
|
510 | 510 |
///\e |
511 | 511 |
NodeMap(const Graph&) { } |
512 | 512 |
///\e |
513 | 513 |
NodeMap(const Graph&, T) { } |
514 | 514 |
|
515 | 515 |
///Copy constructor |
516 | 516 |
NodeMap(const NodeMap& nm) : ReadWriteMap< Node, T >(nm) { } |
517 | 517 |
///Assignment operator |
518 | 518 |
template <typename CMap> |
519 | 519 |
NodeMap& operator=(const CMap&) { |
520 | 520 |
checkConcept<ReadMap<Node, T>, CMap>(); |
521 | 521 |
return *this; |
522 | 522 |
} |
523 | 523 |
}; |
524 | 524 |
|
525 | 525 |
/// \brief Read write map of the directed arcs to type \c T. |
526 | 526 |
/// |
527 | 527 |
/// Reference map of the directed arcs to type \c T. |
528 | 528 |
/// \sa Reference |
529 | 529 |
template<class T> |
530 | 530 |
class ArcMap : public ReadWriteMap<Arc,T> |
531 | 531 |
{ |
532 | 532 |
public: |
533 | 533 |
|
534 | 534 |
///\e |
535 | 535 |
ArcMap(const Graph&) { } |
536 | 536 |
///\e |
537 | 537 |
ArcMap(const Graph&, T) { } |
538 | 538 |
///Copy constructor |
539 | 539 |
ArcMap(const ArcMap& em) : ReadWriteMap<Arc,T>(em) { } |
540 | 540 |
///Assignment operator |
541 | 541 |
template <typename CMap> |
542 | 542 |
ArcMap& operator=(const CMap&) { |
543 | 543 |
checkConcept<ReadMap<Arc, T>, CMap>(); |
544 | 544 |
return *this; |
545 | 545 |
} |
546 | 546 |
}; |
547 | 547 |
|
548 | 548 |
/// Read write map of the edges to type \c T. |
549 | 549 |
|
550 | 550 |
/// Reference map of the arcs to type \c T. |
551 | 551 |
/// \sa Reference |
552 | 552 |
template<class T> |
553 | 553 |
class EdgeMap : public ReadWriteMap<Edge,T> |
554 | 554 |
{ |
555 | 555 |
public: |
556 | 556 |
|
557 | 557 |
///\e |
558 | 558 |
EdgeMap(const Graph&) { } |
559 | 559 |
///\e |
560 | 560 |
EdgeMap(const Graph&, T) { } |
561 | 561 |
///Copy constructor |
562 | 562 |
EdgeMap(const EdgeMap& em) : ReadWriteMap<Edge,T>(em) {} |
563 | 563 |
///Assignment operator |
564 | 564 |
template <typename CMap> |
565 | 565 |
EdgeMap& operator=(const CMap&) { |
566 | 566 |
checkConcept<ReadMap<Edge, T>, CMap>(); |
567 | 567 |
return *this; |
568 | 568 |
} |
569 | 569 |
}; |
570 | 570 |
|
571 | 571 |
/// \brief Direct the given edge. |
572 | 572 |
/// |
573 | 573 |
/// Direct the given edge. The returned arc source |
574 | 574 |
/// will be the given node. |
575 | 575 |
Arc direct(const Edge&, const Node&) const { |
576 | 576 |
return INVALID; |
577 | 577 |
} |
578 | 578 |
|
579 | 579 |
/// \brief Direct the given edge. |
580 | 580 |
/// |
581 | 581 |
/// Direct the given edge. The returned arc |
582 | 582 |
/// represents the given edge and the direction comes |
583 | 583 |
/// from the bool parameter. The source of the edge and |
584 | 584 |
/// the directed arc is the same when the given bool is true. |
585 | 585 |
Arc direct(const Edge&, bool) const { |
586 | 586 |
return INVALID; |
587 | 587 |
} |
588 | 588 |
|
589 | 589 |
/// \brief Returns true if the arc has default orientation. |
590 | 590 |
/// |
591 | 591 |
/// Returns whether the given directed arc is same orientation as |
592 | 592 |
/// the corresponding edge's default orientation. |
593 | 593 |
bool direction(Arc) const { return true; } |
594 | 594 |
|
595 | 595 |
/// \brief Returns the opposite directed arc. |
596 | 596 |
/// |
597 | 597 |
/// Returns the opposite directed arc. |
598 | 598 |
Arc oppositeArc(Arc) const { return INVALID; } |
599 | 599 |
|
600 | 600 |
/// \brief Opposite node on an arc |
601 | 601 |
/// |
602 | 602 |
/// \return the opposite of the given Node on the given Edge |
603 | 603 |
Node oppositeNode(Node, Edge) const { return INVALID; } |
604 | 604 |
|
605 | 605 |
/// \brief First node of the edge. |
606 | 606 |
/// |
607 | 607 |
/// \return the first node of the given Edge. |
608 | 608 |
/// |
609 | 609 |
/// Naturally edges don't have direction and thus |
610 | 610 |
/// don't have source and target node. But we use these two methods |
611 | 611 |
/// to query the two nodes of the arc. The direction of the arc |
612 | 612 |
/// which arises this way is called the inherent direction of the |
613 | 613 |
/// edge, and is used to define the "default" direction |
614 | 614 |
/// of the directed versions of the arcs. |
615 | 615 |
/// \sa direction |
616 | 616 |
Node u(Edge) const { return INVALID; } |
617 | 617 |
|
618 | 618 |
/// \brief Second node of the edge. |
619 | 619 |
Node v(Edge) const { return INVALID; } |
620 | 620 |
|
621 | 621 |
/// \brief Source node of the directed arc. |
622 | 622 |
Node source(Arc) const { return INVALID; } |
623 | 623 |
|
624 | 624 |
/// \brief Target node of the directed arc. |
625 | 625 |
Node target(Arc) const { return INVALID; } |
626 | 626 |
|
627 |
/// \brief Returns the id of the node. |
|
628 |
int id(Node) const { return -1; } |
|
629 |
|
|
630 |
/// \brief Returns the id of the edge. |
|
631 |
int id(Edge) const { return -1; } |
|
632 |
|
|
633 |
/// \brief Returns the id of the arc. |
|
634 |
int id(Arc) const { return -1; } |
|
635 |
|
|
636 |
/// \brief Returns the node with the given id. |
|
637 |
/// |
|
638 |
/// \pre The argument should be a valid node id in the graph. |
|
639 |
Node nodeFromId(int) const { return INVALID; } |
|
640 |
|
|
641 |
/// \brief Returns the edge with the given id. |
|
642 |
/// |
|
643 |
/// \pre The argument should be a valid edge id in the graph. |
|
644 |
Edge edgeFromId(int) const { return INVALID; } |
|
645 |
|
|
646 |
/// \brief Returns the arc with the given id. |
|
647 |
/// |
|
648 |
/// \pre The argument should be a valid arc id in the graph. |
|
649 |
Arc arcFromId(int) const { return INVALID; } |
|
650 |
|
|
651 |
/// \brief Returns an upper bound on the node IDs. |
|
652 |
int maxNodeId() const { return -1; } |
|
653 |
|
|
654 |
/// \brief Returns an upper bound on the edge IDs. |
|
655 |
int maxEdgeId() const { return -1; } |
|
656 |
|
|
657 |
/// \brief Returns an upper bound on the arc IDs. |
|
658 |
int maxArcId() const { return -1; } |
|
659 |
|
|
627 | 660 |
void first(Node&) const {} |
628 | 661 |
void next(Node&) const {} |
629 | 662 |
|
630 | 663 |
void first(Edge&) const {} |
631 | 664 |
void next(Edge&) const {} |
632 | 665 |
|
633 | 666 |
void first(Arc&) const {} |
634 | 667 |
void next(Arc&) const {} |
635 | 668 |
|
636 | 669 |
void firstOut(Arc&, Node) const {} |
637 | 670 |
void nextOut(Arc&) const {} |
638 | 671 |
|
639 | 672 |
void firstIn(Arc&, Node) const {} |
640 | 673 |
void nextIn(Arc&) const {} |
641 | 674 |
|
642 |
|
|
643 | 675 |
void firstInc(Edge &, bool &, const Node &) const {} |
644 | 676 |
void nextInc(Edge &, bool &) const {} |
645 | 677 |
|
678 |
// The second parameter is dummy. |
|
679 |
Node fromId(int, Node) const { return INVALID; } |
|
680 |
// The second parameter is dummy. |
|
681 |
Edge fromId(int, Edge) const { return INVALID; } |
|
682 |
// The second parameter is dummy. |
|
683 |
Arc fromId(int, Arc) const { return INVALID; } |
|
684 |
|
|
685 |
// Dummy parameter. |
|
686 |
int maxId(Node) const { return -1; } |
|
687 |
// Dummy parameter. |
|
688 |
int maxId(Edge) const { return -1; } |
|
689 |
// Dummy parameter. |
|
690 |
int maxId(Arc) const { return -1; } |
|
691 |
|
|
646 | 692 |
/// \brief Base node of the iterator |
647 | 693 |
/// |
648 | 694 |
/// Returns the base node (the source in this case) of the iterator |
649 | 695 |
Node baseNode(OutArcIt e) const { |
650 | 696 |
return source(e); |
651 | 697 |
} |
652 | 698 |
/// \brief Running node of the iterator |
653 | 699 |
/// |
654 | 700 |
/// Returns the running node (the target in this case) of the |
655 | 701 |
/// iterator |
656 | 702 |
Node runningNode(OutArcIt e) const { |
657 | 703 |
return target(e); |
658 | 704 |
} |
659 | 705 |
|
660 | 706 |
/// \brief Base node of the iterator |
661 | 707 |
/// |
662 | 708 |
/// Returns the base node (the target in this case) of the iterator |
663 | 709 |
Node baseNode(InArcIt e) const { |
664 | 710 |
return target(e); |
665 | 711 |
} |
666 | 712 |
/// \brief Running node of the iterator |
667 | 713 |
/// |
668 | 714 |
/// Returns the running node (the source in this case) of the |
669 | 715 |
/// iterator |
670 | 716 |
Node runningNode(InArcIt e) const { |
671 | 717 |
return source(e); |
672 | 718 |
} |
673 | 719 |
|
674 | 720 |
/// \brief Base node of the iterator |
675 | 721 |
/// |
676 | 722 |
/// Returns the base node of the iterator |
677 | 723 |
Node baseNode(IncArcIt) const { |
678 | 724 |
return INVALID; |
679 | 725 |
} |
680 | 726 |
|
681 | 727 |
/// \brief Running node of the iterator |
682 | 728 |
/// |
683 | 729 |
/// Returns the running node of the iterator |
684 | 730 |
Node runningNode(IncArcIt) const { |
685 | 731 |
return INVALID; |
686 | 732 |
} |
687 | 733 |
|
688 | 734 |
template <typename Graph> |
689 | 735 |
struct Constraints { |
690 | 736 |
void constraints() { |
691 | 737 |
checkConcept<IterableGraphComponent<>, Graph>(); |
738 |
checkConcept<IDableGraphComponent<>, Graph>(); |
|
692 | 739 |
checkConcept<MappableGraphComponent<>, Graph>(); |
693 | 740 |
} |
694 | 741 |
}; |
695 | 742 |
|
696 | 743 |
}; |
697 | 744 |
|
698 | 745 |
} |
699 | 746 |
|
700 | 747 |
} |
701 | 748 |
|
702 | 749 |
#endif |
... | ... |
@@ -65,385 +65,385 @@ |
65 | 65 |
#include <algorithm> |
66 | 66 |
#include <iterator> |
67 | 67 |
#include <vector> |
68 | 68 |
|
69 | 69 |
#include <ctime> |
70 | 70 |
#include <cmath> |
71 | 71 |
|
72 | 72 |
#include <lemon/dim2.h> |
73 | 73 |
///\ingroup misc |
74 | 74 |
///\file |
75 | 75 |
///\brief Mersenne Twister random number generator |
76 | 76 |
|
77 | 77 |
namespace lemon { |
78 | 78 |
|
79 | 79 |
namespace _random_bits { |
80 | 80 |
|
81 | 81 |
template <typename _Word, int _bits = std::numeric_limits<_Word>::digits> |
82 | 82 |
struct RandomTraits {}; |
83 | 83 |
|
84 | 84 |
template <typename _Word> |
85 | 85 |
struct RandomTraits<_Word, 32> { |
86 | 86 |
|
87 | 87 |
typedef _Word Word; |
88 | 88 |
static const int bits = 32; |
89 | 89 |
|
90 | 90 |
static const int length = 624; |
91 | 91 |
static const int shift = 397; |
92 | 92 |
|
93 | 93 |
static const Word mul = 0x6c078965u; |
94 | 94 |
static const Word arrayInit = 0x012BD6AAu; |
95 | 95 |
static const Word arrayMul1 = 0x0019660Du; |
96 | 96 |
static const Word arrayMul2 = 0x5D588B65u; |
97 | 97 |
|
98 | 98 |
static const Word mask = 0x9908B0DFu; |
99 | 99 |
static const Word loMask = (1u << 31) - 1; |
100 | 100 |
static const Word hiMask = ~loMask; |
101 | 101 |
|
102 | 102 |
|
103 | 103 |
static Word tempering(Word rnd) { |
104 | 104 |
rnd ^= (rnd >> 11); |
105 | 105 |
rnd ^= (rnd << 7) & 0x9D2C5680u; |
106 | 106 |
rnd ^= (rnd << 15) & 0xEFC60000u; |
107 | 107 |
rnd ^= (rnd >> 18); |
108 | 108 |
return rnd; |
109 | 109 |
} |
110 | 110 |
|
111 | 111 |
}; |
112 | 112 |
|
113 | 113 |
template <typename _Word> |
114 | 114 |
struct RandomTraits<_Word, 64> { |
115 | 115 |
|
116 | 116 |
typedef _Word Word; |
117 | 117 |
static const int bits = 64; |
118 | 118 |
|
119 | 119 |
static const int length = 312; |
120 | 120 |
static const int shift = 156; |
121 | 121 |
|
122 | 122 |
static const Word mul = Word(0x5851F42Du) << 32 | Word(0x4C957F2Du); |
123 | 123 |
static const Word arrayInit = Word(0x00000000u) << 32 |Word(0x012BD6AAu); |
124 | 124 |
static const Word arrayMul1 = Word(0x369DEA0Fu) << 32 |Word(0x31A53F85u); |
125 | 125 |
static const Word arrayMul2 = Word(0x27BB2EE6u) << 32 |Word(0x87B0B0FDu); |
126 | 126 |
|
127 | 127 |
static const Word mask = Word(0xB5026F5Au) << 32 | Word(0xA96619E9u); |
128 | 128 |
static const Word loMask = (Word(1u) << 31) - 1; |
129 | 129 |
static const Word hiMask = ~loMask; |
130 | 130 |
|
131 | 131 |
static Word tempering(Word rnd) { |
132 | 132 |
rnd ^= (rnd >> 29) & (Word(0x55555555u) << 32 | Word(0x55555555u)); |
133 | 133 |
rnd ^= (rnd << 17) & (Word(0x71D67FFFu) << 32 | Word(0xEDA60000u)); |
134 | 134 |
rnd ^= (rnd << 37) & (Word(0xFFF7EEE0u) << 32 | Word(0x00000000u)); |
135 | 135 |
rnd ^= (rnd >> 43); |
136 | 136 |
return rnd; |
137 | 137 |
} |
138 | 138 |
|
139 | 139 |
}; |
140 | 140 |
|
141 | 141 |
template <typename _Word> |
142 | 142 |
class RandomCore { |
143 | 143 |
public: |
144 | 144 |
|
145 | 145 |
typedef _Word Word; |
146 | 146 |
|
147 | 147 |
private: |
148 | 148 |
|
149 | 149 |
static const int bits = RandomTraits<Word>::bits; |
150 | 150 |
|
151 | 151 |
static const int length = RandomTraits<Word>::length; |
152 | 152 |
static const int shift = RandomTraits<Word>::shift; |
153 | 153 |
|
154 | 154 |
public: |
155 | 155 |
|
156 | 156 |
void initState() { |
157 | 157 |
static const Word seedArray[4] = { |
158 | 158 |
0x12345u, 0x23456u, 0x34567u, 0x45678u |
159 | 159 |
}; |
160 | 160 |
|
161 | 161 |
initState(seedArray, seedArray + 4); |
162 | 162 |
} |
163 | 163 |
|
164 | 164 |
void initState(Word seed) { |
165 | 165 |
|
166 | 166 |
static const Word mul = RandomTraits<Word>::mul; |
167 | 167 |
|
168 | 168 |
current = state; |
169 | 169 |
|
170 | 170 |
Word *curr = state + length - 1; |
171 | 171 |
curr[0] = seed; --curr; |
172 | 172 |
for (int i = 1; i < length; ++i) { |
173 | 173 |
curr[0] = (mul * ( curr[1] ^ (curr[1] >> (bits - 2)) ) + i); |
174 | 174 |
--curr; |
175 | 175 |
} |
176 | 176 |
} |
177 | 177 |
|
178 | 178 |
template <typename Iterator> |
179 | 179 |
void initState(Iterator begin, Iterator end) { |
180 | 180 |
|
181 | 181 |
static const Word init = RandomTraits<Word>::arrayInit; |
182 | 182 |
static const Word mul1 = RandomTraits<Word>::arrayMul1; |
183 | 183 |
static const Word mul2 = RandomTraits<Word>::arrayMul2; |
184 | 184 |
|
185 | 185 |
|
186 | 186 |
Word *curr = state + length - 1; --curr; |
187 | 187 |
Iterator it = begin; int cnt = 0; |
188 | 188 |
int num; |
189 | 189 |
|
190 | 190 |
initState(init); |
191 | 191 |
|
192 | 192 |
num = length > end - begin ? length : end - begin; |
193 | 193 |
while (num--) { |
194 | 194 |
curr[0] = (curr[0] ^ ((curr[1] ^ (curr[1] >> (bits - 2))) * mul1)) |
195 | 195 |
+ *it + cnt; |
196 | 196 |
++it; ++cnt; |
197 | 197 |
if (it == end) { |
198 | 198 |
it = begin; cnt = 0; |
199 | 199 |
} |
200 | 200 |
if (curr == state) { |
201 | 201 |
curr = state + length - 1; curr[0] = state[0]; |
202 | 202 |
} |
203 | 203 |
--curr; |
204 | 204 |
} |
205 | 205 |
|
206 | 206 |
num = length - 1; cnt = length - (curr - state) - 1; |
207 | 207 |
while (num--) { |
208 | 208 |
curr[0] = (curr[0] ^ ((curr[1] ^ (curr[1] >> (bits - 2))) * mul2)) |
209 | 209 |
- cnt; |
210 | 210 |
--curr; ++cnt; |
211 | 211 |
if (curr == state) { |
212 | 212 |
curr = state + length - 1; curr[0] = state[0]; --curr; |
213 | 213 |
cnt = 1; |
214 | 214 |
} |
215 | 215 |
} |
216 | 216 |
|
217 | 217 |
state[length - 1] = Word(1) << (bits - 1); |
218 | 218 |
} |
219 | 219 |
|
220 | 220 |
void copyState(const RandomCore& other) { |
221 | 221 |
std::copy(other.state, other.state + length, state); |
222 | 222 |
current = state + (other.current - other.state); |
223 | 223 |
} |
224 | 224 |
|
225 | 225 |
Word operator()() { |
226 | 226 |
if (current == state) fillState(); |
227 | 227 |
--current; |
228 | 228 |
Word rnd = *current; |
229 | 229 |
return RandomTraits<Word>::tempering(rnd); |
230 | 230 |
} |
231 | 231 |
|
232 | 232 |
private: |
233 | 233 |
|
234 | 234 |
|
235 | 235 |
void fillState() { |
236 | 236 |
static const Word mask[2] = { 0x0ul, RandomTraits<Word>::mask }; |
237 | 237 |
static const Word loMask = RandomTraits<Word>::loMask; |
238 | 238 |
static const Word hiMask = RandomTraits<Word>::hiMask; |
239 | 239 |
|
240 | 240 |
current = state + length; |
241 | 241 |
|
242 | 242 |
register Word *curr = state + length - 1; |
243 | 243 |
register long num; |
244 | 244 |
|
245 | 245 |
num = length - shift; |
246 | 246 |
while (num--) { |
247 | 247 |
curr[0] = (((curr[0] & hiMask) | (curr[-1] & loMask)) >> 1) ^ |
248 | 248 |
curr[- shift] ^ mask[curr[-1] & 1ul]; |
249 | 249 |
--curr; |
250 | 250 |
} |
251 | 251 |
num = shift - 1; |
252 | 252 |
while (num--) { |
253 | 253 |
curr[0] = (((curr[0] & hiMask) | (curr[-1] & loMask)) >> 1) ^ |
254 | 254 |
curr[length - shift] ^ mask[curr[-1] & 1ul]; |
255 | 255 |
--curr; |
256 | 256 |
} |
257 |
|
|
257 |
state[0] = (((state[0] & hiMask) | (curr[length - 1] & loMask)) >> 1) ^ |
|
258 | 258 |
curr[length - shift] ^ mask[curr[length - 1] & 1ul]; |
259 | 259 |
|
260 | 260 |
} |
261 | 261 |
|
262 | 262 |
|
263 | 263 |
Word *current; |
264 | 264 |
Word state[length]; |
265 | 265 |
|
266 | 266 |
}; |
267 | 267 |
|
268 | 268 |
|
269 | 269 |
template <typename Result, |
270 | 270 |
int shift = (std::numeric_limits<Result>::digits + 1) / 2> |
271 | 271 |
struct Masker { |
272 | 272 |
static Result mask(const Result& result) { |
273 | 273 |
return Masker<Result, (shift + 1) / 2>:: |
274 | 274 |
mask(static_cast<Result>(result | (result >> shift))); |
275 | 275 |
} |
276 | 276 |
}; |
277 | 277 |
|
278 | 278 |
template <typename Result> |
279 | 279 |
struct Masker<Result, 1> { |
280 | 280 |
static Result mask(const Result& result) { |
281 | 281 |
return static_cast<Result>(result | (result >> 1)); |
282 | 282 |
} |
283 | 283 |
}; |
284 | 284 |
|
285 | 285 |
template <typename Result, typename Word, |
286 | 286 |
int rest = std::numeric_limits<Result>::digits, int shift = 0, |
287 | 287 |
bool last = rest <= std::numeric_limits<Word>::digits> |
288 | 288 |
struct IntConversion { |
289 | 289 |
static const int bits = std::numeric_limits<Word>::digits; |
290 | 290 |
|
291 | 291 |
static Result convert(RandomCore<Word>& rnd) { |
292 | 292 |
return static_cast<Result>(rnd() >> (bits - rest)) << shift; |
293 | 293 |
} |
294 | 294 |
|
295 | 295 |
}; |
296 | 296 |
|
297 | 297 |
template <typename Result, typename Word, int rest, int shift> |
298 | 298 |
struct IntConversion<Result, Word, rest, shift, false> { |
299 | 299 |
static const int bits = std::numeric_limits<Word>::digits; |
300 | 300 |
|
301 | 301 |
static Result convert(RandomCore<Word>& rnd) { |
302 | 302 |
return (static_cast<Result>(rnd()) << shift) | |
303 | 303 |
IntConversion<Result, Word, rest - bits, shift + bits>::convert(rnd); |
304 | 304 |
} |
305 | 305 |
}; |
306 | 306 |
|
307 | 307 |
|
308 | 308 |
template <typename Result, typename Word, |
309 | 309 |
bool one_word = (std::numeric_limits<Word>::digits < |
310 | 310 |
std::numeric_limits<Result>::digits) > |
311 | 311 |
struct Mapping { |
312 | 312 |
static Result map(RandomCore<Word>& rnd, const Result& bound) { |
313 | 313 |
Word max = Word(bound - 1); |
314 | 314 |
Result mask = Masker<Result>::mask(bound - 1); |
315 | 315 |
Result num; |
316 | 316 |
do { |
317 | 317 |
num = IntConversion<Result, Word>::convert(rnd) & mask; |
318 | 318 |
} while (num > max); |
319 | 319 |
return num; |
320 | 320 |
} |
321 | 321 |
}; |
322 | 322 |
|
323 | 323 |
template <typename Result, typename Word> |
324 | 324 |
struct Mapping<Result, Word, false> { |
325 | 325 |
static Result map(RandomCore<Word>& rnd, const Result& bound) { |
326 | 326 |
Word max = Word(bound - 1); |
327 | 327 |
Word mask = Masker<Word, (std::numeric_limits<Result>::digits + 1) / 2> |
328 | 328 |
::mask(max); |
329 | 329 |
Word num; |
330 | 330 |
do { |
331 | 331 |
num = rnd() & mask; |
332 | 332 |
} while (num > max); |
333 | 333 |
return num; |
334 | 334 |
} |
335 | 335 |
}; |
336 | 336 |
|
337 | 337 |
template <typename Result, int exp, bool pos = (exp >= 0)> |
338 | 338 |
struct ShiftMultiplier { |
339 | 339 |
static const Result multiplier() { |
340 | 340 |
Result res = ShiftMultiplier<Result, exp / 2>::multiplier(); |
341 | 341 |
res *= res; |
342 | 342 |
if ((exp & 1) == 1) res *= static_cast<Result>(2.0); |
343 | 343 |
return res; |
344 | 344 |
} |
345 | 345 |
}; |
346 | 346 |
|
347 | 347 |
template <typename Result, int exp> |
348 | 348 |
struct ShiftMultiplier<Result, exp, false> { |
349 | 349 |
static const Result multiplier() { |
350 | 350 |
Result res = ShiftMultiplier<Result, exp / 2>::multiplier(); |
351 | 351 |
res *= res; |
352 | 352 |
if ((exp & 1) == 1) res *= static_cast<Result>(0.5); |
353 | 353 |
return res; |
354 | 354 |
} |
355 | 355 |
}; |
356 | 356 |
|
357 | 357 |
template <typename Result> |
358 | 358 |
struct ShiftMultiplier<Result, 0, true> { |
359 | 359 |
static const Result multiplier() { |
360 | 360 |
return static_cast<Result>(1.0); |
361 | 361 |
} |
362 | 362 |
}; |
363 | 363 |
|
364 | 364 |
template <typename Result> |
365 | 365 |
struct ShiftMultiplier<Result, -20, true> { |
366 | 366 |
static const Result multiplier() { |
367 | 367 |
return static_cast<Result>(1.0/1048576.0); |
368 | 368 |
} |
369 | 369 |
}; |
370 | 370 |
|
371 | 371 |
template <typename Result> |
372 | 372 |
struct ShiftMultiplier<Result, -32, true> { |
373 | 373 |
static const Result multiplier() { |
374 | 374 |
return static_cast<Result>(1.0/424967296.0); |
375 | 375 |
} |
376 | 376 |
}; |
377 | 377 |
|
378 | 378 |
template <typename Result> |
379 | 379 |
struct ShiftMultiplier<Result, -53, true> { |
380 | 380 |
static const Result multiplier() { |
381 | 381 |
return static_cast<Result>(1.0/9007199254740992.0); |
382 | 382 |
} |
383 | 383 |
}; |
384 | 384 |
|
385 | 385 |
template <typename Result> |
386 | 386 |
struct ShiftMultiplier<Result, -64, true> { |
387 | 387 |
static const Result multiplier() { |
388 | 388 |
return static_cast<Result>(1.0/18446744073709551616.0); |
389 | 389 |
} |
390 | 390 |
}; |
391 | 391 |
|
392 | 392 |
template <typename Result, int exp> |
393 | 393 |
struct Shifting { |
394 | 394 |
static Result shift(const Result& result) { |
395 | 395 |
return result * ShiftMultiplier<Result, exp>::multiplier(); |
396 | 396 |
} |
397 | 397 |
}; |
398 | 398 |
|
399 | 399 |
template <typename Result, typename Word, |
400 | 400 |
int rest = std::numeric_limits<Result>::digits, int shift = 0, |
401 | 401 |
bool last = rest <= std::numeric_limits<Word>::digits> |
402 | 402 |
struct RealConversion{ |
403 | 403 |
static const int bits = std::numeric_limits<Word>::digits; |
404 | 404 |
|
405 | 405 |
static Result convert(RandomCore<Word>& rnd) { |
406 | 406 |
return Shifting<Result, - shift - rest>:: |
407 | 407 |
shift(static_cast<Result>(rnd() >> (bits - rest))); |
408 | 408 |
} |
409 | 409 |
}; |
410 | 410 |
|
411 | 411 |
template <typename Result, typename Word, int rest, int shift> |
412 | 412 |
struct RealConversion<Result, Word, rest, shift, false> { |
413 | 413 |
static const int bits = std::numeric_limits<Word>::digits; |
414 | 414 |
|
415 | 415 |
static Result convert(RandomCore<Word>& rnd) { |
416 | 416 |
return Shifting<Result, - shift - bits>:: |
417 | 417 |
shift(static_cast<Result>(rnd())) + |
418 | 418 |
RealConversion<Result, Word, rest-bits, shift + bits>:: |
419 | 419 |
convert(rnd); |
420 | 420 |
} |
421 | 421 |
}; |
422 | 422 |
|
423 | 423 |
template <typename Result, typename Word> |
424 | 424 |
struct Initializer { |
425 | 425 |
|
426 | 426 |
template <typename Iterator> |
427 | 427 |
static void init(RandomCore<Word>& rnd, Iterator begin, Iterator end) { |
428 | 428 |
std::vector<Word> ws; |
429 | 429 |
for (Iterator it = begin; it != end; ++it) { |
430 | 430 |
ws.push_back(Word(*it)); |
431 | 431 |
} |
432 | 432 |
rnd.initState(ws.begin(), ws.end()); |
433 | 433 |
} |
434 | 434 |
|
435 | 435 |
static void init(RandomCore<Word>& rnd, Result seed) { |
436 | 436 |
rnd.initState(seed); |
437 | 437 |
} |
438 | 438 |
}; |
439 | 439 |
|
440 | 440 |
template <typename Word> |
441 | 441 |
struct BoolConversion { |
442 | 442 |
static bool convert(RandomCore<Word>& rnd) { |
443 | 443 |
return (rnd() & 1) == 1; |
444 | 444 |
} |
445 | 445 |
}; |
446 | 446 |
|
447 | 447 |
template <typename Word> |
448 | 448 |
struct BoolProducer { |
449 | 449 |
Word buffer; |
1 | 1 |
EXTRA_DIST += \ |
2 | 2 |
test/Makefile |
3 | 3 |
|
4 | 4 |
noinst_HEADERS += \ |
5 | 5 |
test/digraph_test.h \ |
6 | 6 |
test/map_test.h \ |
7 | 7 |
test/test_tools.h |
8 | 8 |
|
9 | 9 |
check_PROGRAMS += \ |
10 | 10 |
test/digraph_test \ |
11 | 11 |
test/dim_test \ |
12 | 12 |
test/graph_test \ |
13 |
test/maps_test \ |
|
13 | 14 |
test/random_test \ |
14 | 15 |
test/path_test \ |
15 | 16 |
test/test_tools_fail \ |
16 | 17 |
test/test_tools_pass |
17 | 18 |
|
18 | 19 |
TESTS += $(check_PROGRAMS) |
19 | 20 |
XFAIL_TESTS += test/test_tools_fail$(EXEEXT) |
20 | 21 |
|
21 | 22 |
test_digraph_test_SOURCES = test/digraph_test.cc |
22 | 23 |
test_dim_test_SOURCES = test/dim_test.cc |
24 |
#test_error_test_SOURCES = test/error_test.cc |
|
23 | 25 |
test_graph_test_SOURCES = test/graph_test.cc |
26 |
test_maps_test_SOURCES = test/maps_test.cc |
|
24 | 27 |
test_path_test_SOURCES = test/path_test.cc |
25 | 28 |
test_random_test_SOURCES = test/random_test.cc |
26 | 29 |
test_test_tools_fail_SOURCES = test/test_tools_fail.cc |
27 | 30 |
test_test_tools_pass_SOURCES = test/test_tools_pass.cc |
0 comments (0 inline)