daily pastebin goal
31%
SHARE
TWEET

testlib.h, modified to work on LibreOJ

cyand1317 Jul 27th, 2017 396 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2.  * It is strictly recommended to include "testlib.h" before any other include
  3.  * in your code. In this case testlib overrides compiler specific "random()".
  4.  *
  5.  * If you can't compile your code and compiler outputs something about
  6.  * ambiguous call of "random_shuffle", "rand" or "srand" it means that
  7.  * you shouldn't use them. Use "shuffle", and "rnd.next()" instead of them
  8.  * because these calls produce stable result for any C++ compiler. Read
  9.  * sample generator sources for clarification.
  10.  *
  11.  * Please read the documentation for class "random_t" and use "rnd" instance in
  12.  * generators. Probably, these sample calls will be usefull for you:
  13.  *              rnd.next(); rnd.next(100); rnd.next(1, 2);
  14.  *              rnd.next(3.14); rnd.next("[a-z]{1,100}").
  15.  *
  16.  * Also read about wnext() to generate off-center random distribution.
  17.  *
  18.  * See http://code.google.com/p/testlib/ to get latest version or bug tracker.
  19.  */
  20.  
  21. #ifndef _TESTLIB_H_
  22. #define _TESTLIB_H_
  23.  
  24. /*
  25.  * Copyright (c) 2005-2017
  26.  */
  27.  
  28. #define VERSION "0.9.12"
  29.  
  30. /*
  31.  * Mike Mirzayanov
  32.  *
  33.  * This material is provided "as is", with absolutely no warranty expressed
  34.  * or implied. Any use is at your own risk.
  35.  *
  36.  * Permission to use or copy this software for any purpose is hereby granted
  37.  * without fee, provided the above notices are retained on all copies.
  38.  * Permission to modify the code and to distribute modified code is granted,
  39.  * provided the above notices are retained, and a notice that the code was
  40.  * modified is included with the above copyright notice.
  41.  *
  42.  */
  43.  
  44. /* NOTE: This file contains testlib library for C++.
  45.  *
  46.  *   Check, using testlib running format:
  47.  *     check.exe <Input_File> <Output_File> <Answer_File> [<Result_File> [-appes]],
  48.  *   If result file is specified it will contain results.
  49.  *
  50.  *   Validator, using testlib running format:                                          
  51.  *     validator.exe < input.txt,
  52.  *   It will return non-zero exit code and writes message to standard output.
  53.  *
  54.  *   Generator, using testlib running format:                                          
  55.  *     gen.exe [parameter-1] [parameter-2] [... paramerter-n]
  56.  *   You can write generated test(s) into standard output or into the file(s).
  57.  *
  58.  *   Interactor, using testlib running format:                                          
  59.  *     interactor.exe <Input_File> <Output_File> [<Answer_File> [<Result_File> [-appes]]],
  60.  *   Reads test from inf (mapped to args[1]), writes result to tout (mapped to argv[2],
  61.  *   can be judged by checker later), reads program output from ouf (mapped to stdin),
  62.  *   writes output to program via stdout (use cout, printf, etc).
  63.  */
  64.  
  65. const char* latestFeatures[] = {
  66.                           "Introduced space-separated read functions: readWords/readTokens, multilines read functions: readStrings/readLines",
  67.                           "Introduced space-separated read functions: readInts/readIntegers/readLongs/readUnsignedLongs/readDoubles/readReals/readStrictDoubles/readStrictReals",
  68.                           "Introduced split/tokenize functions to separate string by given char",
  69.                           "Introduced InStream::readUnsignedLong and InStream::readLong with unsigned long long paramerters",
  70.                           "Supported --testOverviewLogFileName for validator: bounds hits + features",
  71.                           "Fixed UB (sequence points) in random_t",
  72.                           "POINTS_EXIT_CODE returned back to 7 (instead of 0)",
  73.                           "Removed disable buffers for interactive problems, because it works unexpectedly in wine",
  74.                           "InStream over string: constructor of InStream from base InStream to inherit policies and std::string",
  75.                           "Added expectedButFound quit function, examples: expectedButFound(_wa, 10, 20), expectedButFound(_fail, ja, pa, \"[n=%d,m=%d]\", n, m)",
  76.                           "Fixed incorrect interval parsing in patterns",
  77.                           "Use registerGen(argc, argv, 1) to develop new generator, use registerGen(argc, argv, 0) to compile old generators (originally created for testlib under 0.8.7)",
  78.                           "Introduced disableFinalizeGuard() to switch off finalization checkings",
  79.                           "Use join() functions to format a range of items as a single string (separated by spaces or other separators)",
  80.                           "Use -DENABLE_UNEXPECTED_EOF to enable special exit code (by default, 8) in case of unexpected eof. It is good idea to use it in interactors",
  81.                           "Use -DUSE_RND_AS_BEFORE_087 to compile in compatibility mode with random behavior of versions before 0.8.7",
  82.                           "Fixed bug with nan in stringToDouble",
  83.                           "Fixed issue around overloads for size_t on x64",  
  84.                           "Added attribute 'points' to the XML output in case of result=_points",  
  85.                           "Exit codes can be customized via macros, e.g. -DPE_EXIT_CODE=14",  
  86.                           "Introduced InStream function readWordTo/readTokenTo/readStringTo/readLineTo for faster reading",  
  87.                           "Introduced global functions: format(), englishEnding(), upperCase(), lowerCase(), compress()",  
  88.                           "Manual buffer in InStreams, some IO speed improvements",  
  89.                           "Introduced quitif(bool, const char* pattern, ...) which delegates to quitf() in case of first argument is true",  
  90.                           "Introduced guard against missed quitf() in checker or readEof() in validators",  
  91.                           "Supported readStrictReal/readStrictDouble - to use in validators to check strictly float numbers",  
  92.                           "Supported registerInteraction(argc, argv)",  
  93.                           "Print checker message to the stderr instead of stdout",  
  94.                           "Supported TResult _points to output calculated score, use quitp(...) functions",  
  95.                           "Fixed to be compilable on Mac",  
  96.                           "PC_BASE_EXIT_CODE=50 in case of defined TESTSYS",
  97.                           "Fixed issues 19-21, added __attribute__ format printf",  
  98.                           "Some bug fixes",  
  99.                           "ouf.readInt(1, 100) and similar calls return WA",  
  100.                           "Modified random_t to avoid integer overflow",  
  101.                           "Truncated checker output [patch by Stepan Gatilov]",  
  102.                           "Renamed class random -> class random_t",  
  103.                           "Supported name parameter for read-and-validation methods, like readInt(1, 2, \"n\")",  
  104.                           "Fixed bug in readDouble()",  
  105.                           "Improved ensuref(), fixed nextLine to work in case of EOF, added startTest()",  
  106.                           "Supported \"partially correct\", example: quitf(_pc(13), \"result=%d\", result)",  
  107.                           "Added shuffle(begin, end), use it instead of random_shuffle(begin, end)",  
  108.                           "Added readLine(const string& ptrn), fixed the logic of readLine() in the validation mode",  
  109.                           "Package extended with samples of generators and validators",  
  110.                           "Written the documentation for classes and public methods in testlib.h",
  111.                           "Implemented random routine to support generators, use registerGen() to switch it on",
  112.                           "Implemented strict mode to validate tests, use registerValidation() to switch it on",
  113.                           "Now ncmp.cpp and wcmp.cpp are return WA if answer is suffix or prefix of the output",
  114.                           "Added InStream::readLong() and removed InStream::readLongint()",
  115.                           "Now no footer added to each report by default (use directive FOOTER to switch on)",
  116.                           "Now every checker has a name, use setName(const char* format, ...) to set it",
  117.                           "Now it is compatible with TTS (by Kittens Computing)",
  118.                           "Added \'ensure(condition, message = \"\")\' feature, it works like assert()",
  119.                           "Fixed compatibility with MS C++ 7.1",
  120.                           "Added footer with exit code information",
  121.                           "Added compatibility with EJUDGE (compile with EJUDGE directive)"
  122.                          };
  123.  
  124. #ifdef _MSC_VER
  125. #define _CRT_SECURE_NO_DEPRECATE
  126. #define _CRT_SECURE_NO_WARNINGS
  127. #define _CRT_NO_VA_START_VALIDATION
  128. #endif
  129.  
  130. /* Overrides random() for Borland C++. */
  131. #define random __random_deprecated
  132. #include <stdlib.h>
  133. #include <cstdlib>
  134. #include <climits>
  135. #include <algorithm>
  136. #undef random
  137.  
  138. #include <cstdio>
  139. #include <cctype>
  140. #include <string>
  141. #include <vector>
  142. #include <map>
  143. #include <set>
  144. #include <cmath>
  145. #include <sstream>
  146. #include <fstream>
  147. #include <cstring>
  148. #include <limits>
  149. #include <stdarg.h>
  150. #include <fcntl.h>
  151.  
  152. #if ( _WIN32 || __WIN32__ || _WIN64 || __WIN64__ )
  153. #   if !defined(_MSC_VER) || _MSC_VER>1400
  154. #       define NOMINMAX 1
  155. #       include <windows.h>
  156. #   else
  157. #       define WORD unsigned short
  158. #       include <unistd.h>
  159. #   endif
  160. #   include <io.h>
  161. #   define ON_WINDOWS
  162. #else
  163. #   define WORD unsigned short
  164. #endif
  165.  
  166. #ifndef LLONG_MIN
  167. #define LLONG_MIN   (-9223372036854775807LL - 1)
  168. #endif
  169.  
  170. #ifndef ULLONG_MAX
  171. #define ULLONG_MAX   (18446744073709551615)
  172. #endif
  173.  
  174. #define LF ((char)10)
  175. #define CR ((char)13)
  176. #define TAB ((char)9)
  177. #define SPACE ((char)' ')
  178. #define EOFC (255)
  179.  
  180. #ifndef OK_EXIT_CODE
  181. #   define OK_EXIT_CODE 0
  182. #endif
  183.  
  184. #ifndef WA_EXIT_CODE
  185. #   ifdef EJUDGE
  186. #       define WA_EXIT_CODE 5
  187. #   else
  188. #       define WA_EXIT_CODE 1
  189. #   endif
  190. #endif
  191.  
  192. #ifndef PE_EXIT_CODE
  193. #   ifdef EJUDGE
  194. #       define PE_EXIT_CODE 4
  195. #   else
  196. #       define PE_EXIT_CODE 2
  197. #   endif
  198. #endif
  199.  
  200. #ifndef FAIL_EXIT_CODE
  201. #   ifdef EJUDGE
  202. #       define FAIL_EXIT_CODE 6
  203. #   else
  204. #       define FAIL_EXIT_CODE 3
  205. #   endif
  206. #endif
  207.  
  208. #ifndef DIRT_EXIT_CODE
  209. #   ifdef EJUDGE
  210. #       define DIRT_EXIT_CODE 6
  211. #   else
  212. #       define DIRT_EXIT_CODE 4
  213. #   endif
  214. #endif
  215.  
  216. #ifndef POINTS_EXIT_CODE
  217. #   define POINTS_EXIT_CODE 7
  218. #endif
  219.  
  220. #ifndef UNEXPECTED_EOF_EXIT_CODE
  221. #   define UNEXPECTED_EOF_EXIT_CODE 8
  222. #endif
  223.  
  224. #ifndef PC_BASE_EXIT_CODE
  225. #   ifdef TESTSYS
  226. #       define PC_BASE_EXIT_CODE 50
  227. #   else
  228. #       define PC_BASE_EXIT_CODE 0
  229. #   endif
  230. #endif
  231.  
  232. #ifdef __GNUC__
  233. #    define __TESTLIB_STATIC_ASSERT(condition) typedef void* __testlib_static_assert_type[(condition) ? 1 : -1] __attribute__((unused))
  234. #else
  235. #    define __TESTLIB_STATIC_ASSERT(condition) typedef void* __testlib_static_assert_type[(condition) ? 1 : -1]
  236. #endif
  237.  
  238. #ifdef ON_WINDOWS
  239. #define I64 "%I64d"
  240. #define U64 "%I64u"
  241. #else
  242. #define I64 "%lld"
  243. #define U64 "%llu"
  244. #endif
  245.  
  246. #ifdef _MSC_VER
  247. #   define NORETURN __declspec(noreturn)
  248. #elif defined __GNUC__
  249. #   define NORETURN __attribute__ ((noreturn))
  250. #else
  251. #   define NORETURN
  252. #endif
  253.                    
  254. static char __testlib_format_buffer[16777216];
  255. static int __testlib_format_buffer_usage_count = 0;
  256.  
  257. #define FMT_TO_RESULT(fmt, cstr, result)  std::string result;                              \
  258.             if (__testlib_format_buffer_usage_count != 0)                                  \
  259.                 __testlib_fail("FMT_TO_RESULT::__testlib_format_buffer_usage_count != 0"); \
  260.             __testlib_format_buffer_usage_count++;                                         \
  261.             va_list ap;                                                                    \
  262.             va_start(ap, fmt);                                                             \
  263.             std::vsprintf(__testlib_format_buffer, cstr, ap);                              \
  264.             va_end(ap);                                                                    \
  265.             result = std::string(__testlib_format_buffer);                                 \
  266.             __testlib_format_buffer_usage_count--;                                         \
  267.  
  268. const long long __TESTLIB_LONGLONG_MAX = 9223372036854775807LL;
  269.  
  270. NORETURN static void __testlib_fail(const std::string& message);
  271.  
  272. template<typename T>
  273. static inline T __testlib_abs(const T& x)
  274. {
  275.     return x > 0 ? x : -x;
  276. }
  277.  
  278. template<typename T>
  279. static inline T __testlib_min(const T& a, const T& b)
  280. {
  281.     return a < b ? a : b;
  282. }
  283.  
  284. template<typename T>
  285. static inline T __testlib_max(const T& a, const T& b)
  286. {
  287.     return a > b ? a : b;
  288. }
  289.  
  290. static bool __testlib_prelimIsNaN(double r)
  291. {
  292.     volatile double ra = r;
  293. #ifndef __BORLANDC__
  294.     return ((ra != ra) == true) && ((ra == ra) == false) && ((1.0 > ra) == false) && ((1.0 < ra) == false);
  295. #else
  296.     return std::_isnan(ra);
  297. #endif
  298. }
  299.  
  300. static std::string removeDoubleTrailingZeroes(std::string value)
  301. {
  302.     while (!value.empty() && value[value.length() - 1] == '0' && value.find('.') != std::string::npos)
  303.         value = value.substr(0, value.length() - 1);
  304.     return value + '0';
  305. }
  306.  
  307. #ifdef __GNUC__
  308. __attribute__ ((format (printf, 1, 2)))
  309. #endif
  310. std::string format(const char* fmt, ...)
  311. {
  312.     FMT_TO_RESULT(fmt, fmt, result);
  313.     return result;
  314. }
  315.  
  316. std::string format(const std::string& fmt, ...)
  317. {
  318.     FMT_TO_RESULT(fmt, fmt.c_str(), result);
  319.     return result;
  320. }
  321.  
  322. static std::string __testlib_part(const std::string& s);
  323.  
  324. static bool __testlib_isNaN(double r)
  325. {
  326.     __TESTLIB_STATIC_ASSERT(sizeof(double) == sizeof(long long));
  327.     volatile double ra = r;
  328.     long long llr1, llr2;
  329.     std::memcpy((void*)&llr1, (void*)&ra, sizeof(double));
  330.     ra = -ra;
  331.     std::memcpy((void*)&llr2, (void*)&ra, sizeof(double));
  332.     long long llnan = 0xFFF8000000000000;
  333.     return __testlib_prelimIsNaN(r) || llnan == llr1 || llnan == llr2;
  334. }
  335.  
  336. static double __testlib_nan()
  337. {
  338.     __TESTLIB_STATIC_ASSERT(sizeof(double) == sizeof(long long));
  339. #ifndef NAN
  340.     long long llnan = 0xFFF8000000000000;
  341.     double nan;
  342.     std::memcpy(&nan, &llnan, sizeof(double));
  343.     return nan;
  344. #else
  345.     return NAN;
  346. #endif
  347. }
  348.  
  349. static bool __testlib_isInfinite(double r)
  350. {
  351.     volatile double ra = r;
  352.     return (ra > 1E300 || ra < -1E300);
  353. }
  354.  
  355. #ifdef __GNUC__
  356. __attribute__((const))
  357. #endif
  358. inline bool doubleCompare(double expected, double result, double MAX_DOUBLE_ERROR)
  359. {
  360.         if (__testlib_isNaN(expected))
  361.         {
  362.             return __testlib_isNaN(result);
  363.         }
  364.         else
  365.             if (__testlib_isInfinite(expected))
  366.             {
  367.                 if (expected > 0)
  368.                 {
  369.                     return result > 0 && __testlib_isInfinite(result);
  370.                 }
  371.                 else
  372.                 {
  373.                     return result < 0 && __testlib_isInfinite(result);
  374.                 }
  375.             }
  376.             else
  377.                 if (__testlib_isNaN(result) || __testlib_isInfinite(result))
  378.                 {
  379.                     return false;
  380.                 }
  381.                 else
  382.                 if (__testlib_abs(result - expected) <= MAX_DOUBLE_ERROR + 1E-15)
  383.                 {
  384.                     return true;
  385.                 }
  386.                 else
  387.                 {
  388.                     double minv = __testlib_min(expected * (1.0 - MAX_DOUBLE_ERROR),
  389.                                  expected * (1.0 + MAX_DOUBLE_ERROR));
  390.                     double maxv = __testlib_max(expected * (1.0 - MAX_DOUBLE_ERROR),
  391.                                   expected * (1.0 + MAX_DOUBLE_ERROR));
  392.                     return result + 1E-15 >= minv && result <= maxv + 1E-15;
  393.                 }
  394. }
  395.  
  396. #ifdef __GNUC__
  397. __attribute__((const))
  398. #endif
  399. inline double doubleDelta(double expected, double result)
  400. {
  401.     double absolute = __testlib_abs(result - expected);
  402.    
  403.     if (__testlib_abs(expected) > 1E-9)
  404.     {
  405.         double relative = __testlib_abs(absolute / expected);
  406.         return __testlib_min(absolute, relative);
  407.     }
  408.     else
  409.         return absolute;
  410. }
  411.  
  412. #ifndef _fileno
  413. #define _fileno(_stream)  ((_stream)->_file)
  414. #endif
  415.  
  416. #ifndef O_BINARY
  417. static void __testlib_set_binary(
  418. #ifdef __GNUC__
  419.     __attribute__((unused))
  420. #endif
  421.     std::FILE* file
  422. )
  423. #else
  424. static void __testlib_set_binary(std::FILE* file)
  425. #endif
  426. {
  427. #ifdef O_BINARY
  428.     if (NULL != file)
  429.     {
  430. #ifndef __BORLANDC__
  431.         _setmode(_fileno(file), O_BINARY);
  432. #else
  433.         setmode(fileno(file), O_BINARY);
  434. #endif
  435.     }
  436. #endif
  437. }
  438.  
  439. /*
  440.  * Very simple regex-like pattern.
  441.  * It used for two purposes: validation and generation.
  442.  *
  443.  * For example, pattern("[a-z]{1,5}").next(rnd) will return
  444.  * random string from lowercase latin letters with length
  445.  * from 1 to 5. It is easier to call rnd.next("[a-z]{1,5}")
  446.  * for the same effect.
  447.  *
  448.  * Another samples:
  449.  * "mike|john" will generate (match) "mike" or "john";
  450.  * "-?[1-9][0-9]{0,3}" will generate (match) non-zero integers from -9999 to 9999;
  451.  * "id-([ac]|b{2})" will generate (match) "id-a", "id-bb", "id-c";
  452.  * "[^0-9]*" will match sequences (empty or non-empty) without digits, you can't
  453.  * use it for generations.
  454.  *
  455.  * You can't use pattern for generation if it contains meta-symbol '*'. Also it
  456.  * is not recommended to use it for char-sets with meta-symbol '^' like [^a-z].
  457.  *
  458.  * For matching very simple greedy algorithm is used. For example, pattern
  459.  * "[0-9]?1" will not match "1", because of greedy nature of matching.
  460.  * Alternations (meta-symbols "|") are processed with brute-force algorithm, so
  461.  * do not use many alternations in one expression.
  462.  *
  463.  * If you want to use one expression many times it is better to compile it into
  464.  * a single pattern like "pattern p("[a-z]+")". Later you can use
  465.  * "p.matches(std::string s)" or "p.next(random_t& rd)" to check matching or generate
  466.  * new string by pattern.
  467.  *
  468.  * Simpler way to read token and check it for pattern matching is "inf.readToken("[a-z]+")".
  469.  */
  470. class random_t;
  471.  
  472. class pattern
  473. {
  474. public:
  475.     /* Create pattern instance by string. */
  476.     pattern(std::string s);
  477.     /* Generate new string by pattern and given random_t. */
  478.     std::string next(random_t& rnd) const;
  479.     /* Checks if given string match the pattern. */
  480.     bool matches(const std::string& s) const;
  481.     /* Returns source string of the pattern. */
  482.     std::string src() const;
  483. private:
  484.     bool matches(const std::string& s, size_t pos) const;
  485.  
  486.     std::string s;
  487.     std::vector<pattern> children;
  488.     std::vector<char> chars;
  489.     int from;
  490.     int to;
  491. };
  492.  
  493. /*
  494.  * Use random_t instances to generate random values. It is preffered
  495.  * way to use randoms instead of rand() function or self-written
  496.  * randoms.
  497.  *
  498.  * Testlib defines global variable "rnd" of random_t class.
  499.  * Use registerGen(argc, argv, 1) to setup random_t seed be command
  500.  * line (to use latest random generator version).
  501.  *
  502.  * Random generates uniformly distributed values if another strategy is
  503.  * not specified explicitly.
  504.  */
  505. class random_t
  506. {
  507. private:
  508.     unsigned long long seed;
  509.     static const unsigned long long multiplier;
  510.     static const unsigned long long addend;
  511.     static const unsigned long long mask;
  512.     static const int lim;
  513.  
  514.     long long nextBits(int bits)
  515.     {
  516.         if (bits <= 48)
  517.         {
  518.             seed = (seed * multiplier + addend) & mask;
  519.             return (long long)(seed >> (48 - bits));
  520.         }
  521.         else
  522.         {
  523.             if (bits > 63)
  524.                 __testlib_fail("random_t::nextBits(int bits): n must be less than 64");
  525.  
  526.             int lowerBitCount = (random_t::version == 0 ? 31 : 32);
  527.            
  528.             long long left = (nextBits(31) << 32);
  529.             long long right = nextBits(lowerBitCount);
  530.            
  531.             return left ^ right;
  532.         }
  533.     }
  534.  
  535. public:
  536.     static int version;
  537.  
  538.     /* New random_t with fixed seed. */
  539.     random_t()
  540.         : seed(3905348978240129619LL)
  541.     {
  542.     }
  543.  
  544.     /* Sets seed by command line. */
  545.     void setSeed(int argc, char* argv[])
  546.     {
  547.         random_t p;
  548.  
  549.         seed = 3905348978240129619LL;
  550.         for (int i = 1; i < argc; i++)
  551.         {
  552.             std::size_t le = std::strlen(argv[i]);
  553.             for (std::size_t j = 0; j < le; j++)
  554.                 seed = seed * multiplier + (unsigned int)(argv[i][j]) + addend;
  555.             seed += multiplier / addend;
  556.         }
  557.  
  558.         seed = seed & mask;
  559.     }
  560.  
  561.     /* Sets seed by given value. */
  562.     void setSeed(long long _seed)
  563.     {
  564.         _seed = (_seed ^ multiplier) & mask;
  565.         seed = _seed;
  566.     }
  567.  
  568. #ifndef __BORLANDC__
  569.     /* Random string value by given pattern (see pattern documentation). */
  570.     std::string next(const std::string& ptrn)
  571.     {
  572.         pattern p(ptrn);
  573.         return p.next(*this);
  574.     }
  575. #else
  576.     /* Random string value by given pattern (see pattern documentation). */
  577.     std::string next(std::string ptrn)
  578.     {
  579.         pattern p(ptrn);
  580.         return p.next(*this);
  581.     }
  582. #endif
  583.  
  584.     /* Random value in range [0, n-1]. */
  585.     int next(int n)
  586.     {
  587.         if (n <= 0)
  588.             __testlib_fail("random_t::next(int n): n must be positive");
  589.  
  590.         if ((n & -n) == n)  // n is a power of 2
  591.             return (int)((n * (long long)nextBits(31)) >> 31);
  592.  
  593.         const long long limit = INT_MAX / n * n;
  594.        
  595.         long long bits;
  596.         do {
  597.             bits = nextBits(31);
  598.         } while (bits >= limit);
  599.  
  600.         return int(bits % n);
  601.     }
  602.  
  603.     /* Random value in range [0, n-1]. */
  604.     unsigned int next(unsigned int n)
  605.     {
  606.         if (n >= INT_MAX)
  607.             __testlib_fail("random_t::next(unsigned int n): n must be less INT_MAX");
  608.         return (unsigned int)next(int(n));
  609.     }
  610.  
  611.     /* Random value in range [0, n-1]. */
  612.     long long next(long long n)
  613.     {
  614.         if (n <= 0)
  615.             __testlib_fail("random_t::next(long long n): n must be positive");
  616.  
  617.         const long long limit = __TESTLIB_LONGLONG_MAX / n * n;
  618.        
  619.         long long bits;
  620.         do {
  621.             bits = nextBits(63);
  622.         } while (bits >= limit);
  623.  
  624.         return bits % n;
  625.     }
  626.  
  627.     /* Random value in range [0, n-1]. */
  628.     unsigned long long next(unsigned long long n)
  629.     {
  630.         if (n >= (unsigned long long)(__TESTLIB_LONGLONG_MAX))
  631.             __testlib_fail("random_t::next(unsigned long long n): n must be less LONGLONG_MAX");
  632.         return (unsigned long long)next((long long)(n));
  633.     }
  634.  
  635.     /* Random value in range [0, n-1]. */
  636.     long next(long n)
  637.     {
  638.         return (long)next((long long)(n));
  639.     }
  640.  
  641.     /* Random value in range [0, n-1]. */
  642.     unsigned long next(unsigned long n)
  643.     {
  644.         if (n >= (unsigned long)(LONG_MAX))
  645.             __testlib_fail("random_t::next(unsigned long n): n must be less LONG_MAX");
  646.         return (unsigned long)next((unsigned long long)(n));
  647.     }
  648.  
  649.     /* Returns random value in range [from,to]. */
  650.     int next(int from, int to)
  651.     {
  652.         return int(next((long long)to - from + 1) + from);
  653.     }
  654.  
  655.     /* Returns random value in range [from,to]. */
  656.     unsigned int next(unsigned int from, unsigned int to)
  657.     {
  658.         return (unsigned int)(next((long long)to - from + 1) + from);
  659.     }
  660.  
  661.     /* Returns random value in range [from,to]. */
  662.     long long next(long long from, long long to)
  663.     {
  664.         return next(to - from + 1) + from;
  665.     }
  666.  
  667.     /* Returns random value in range [from,to]. */
  668.     unsigned long long next(unsigned long long from, unsigned long long to)
  669.     {
  670.         if (from > to)
  671.             __testlib_fail("random_t::next(unsigned long long from, unsigned long long to): from can't not exceed to");
  672.         return next(to - from + 1) + from;
  673.     }
  674.  
  675.     /* Returns random value in range [from,to]. */
  676.     long next(long from, long to)
  677.     {
  678.         return next(to - from + 1) + from;
  679.     }
  680.  
  681.     /* Returns random value in range [from,to]. */
  682.     unsigned long next(unsigned long from, unsigned long to)
  683.     {
  684.         if (from > to)
  685.             __testlib_fail("random_t::next(unsigned long from, unsigned long to): from can't not exceed to");
  686.         return next(to - from + 1) + from;
  687.     }
  688.  
  689.     /* Random double value in range [0, 1). */
  690.     double next()
  691.     {
  692.         long long left = ((long long)(nextBits(26)) << 27);
  693.         long long right = nextBits(27);
  694.         return (double)(left + right) / (double)(1LL << 53);
  695.     }
  696.  
  697.     /* Random double value in range [0, n). */
  698.     double next(double n)
  699.     {
  700.         return n * next();
  701.     }
  702.  
  703.     /* Random double value in range [from, to). */
  704.     double next(double from, double to)
  705.     {
  706.         if (from > to)
  707.             __testlib_fail("random_t::next(double from, double to): from can't not exceed to");
  708.         return next(to - from) + from;
  709.     }
  710.  
  711.     /* Returns random element from container. */
  712.     template <typename Container>
  713.     typename Container::value_type any(const Container& c)
  714.     {
  715.         size_t size = c.size();
  716.         if (size <= 0)
  717.             __testlib_fail("random_t::any(const Container& c): c.size() must be positive");
  718.         return *(c.begin() + next(size));
  719.     }
  720.  
  721.     /* Returns random element from iterator range. */
  722.     template <typename Iter>
  723.     typename Iter::value_type any(const Iter& begin, const Iter& end)
  724.     {
  725.         int size = int(end - begin);
  726.         if (size <= 0)
  727.             __testlib_fail("random_t::any(const Iter& begin, const Iter& end): range must have positive length");
  728.         return *(begin + next(size));
  729.     }
  730.  
  731.     /* Random string value by given pattern (see pattern documentation). */
  732. #ifdef __GNUC__
  733.     __attribute__ ((format (printf, 2, 3)))
  734. #endif
  735.     std::string next(const char* format, ...)
  736.     {
  737.         FMT_TO_RESULT(format, format, ptrn);
  738.         return next(ptrn);
  739.     }
  740.  
  741.     /*
  742.      * Weighted next. If type == 0 than it is usual "next()".
  743.      *
  744.      * If type = 1, than it returns "max(next(), next())"
  745.      * (the number of "max" functions equals to "type").
  746.      *
  747.      * If type < 0, than "max" function replaces with "min".
  748.      */
  749.     int wnext(int n, int type)
  750.     {
  751.         if (n <= 0)
  752.             __testlib_fail("random_t::wnext(int n, int type): n must be positive");
  753.        
  754.         if (abs(type) < random_t::lim)
  755.         {
  756.             int result = next(n);
  757.  
  758.             for (int i = 0; i < +type; i++)
  759.                 result = __testlib_max(result, next(n));
  760.            
  761.             for (int i = 0; i < -type; i++)
  762.                 result = __testlib_min(result, next(n));
  763.  
  764.             return result;
  765.         }
  766.         else
  767.         {
  768.             double p;
  769.            
  770.             if (type > 0)
  771.                 p = std::pow(next() + 0.0, 1.0 / (type + 1));
  772.             else
  773.                 p = 1 - std::pow(next() + 0.0, 1.0 / (-type + 1));
  774.  
  775.             return int(n * p);
  776.         }
  777.     }
  778.    
  779.     /* See wnext(int, int). It uses the same algorithms. */
  780.     long long wnext(long long n, int type)
  781.     {
  782.         if (n <= 0)
  783.             __testlib_fail("random_t::wnext(long long n, int type): n must be positive");
  784.        
  785.         if (abs(type) < random_t::lim)
  786.         {
  787.             long long result = next(n);
  788.  
  789.             for (int i = 0; i < +type; i++)
  790.                 result = __testlib_max(result, next(n));
  791.            
  792.             for (int i = 0; i < -type; i++)
  793.                 result = __testlib_min(result, next(n));
  794.  
  795.             return result;
  796.         }
  797.         else
  798.         {
  799.             double p;
  800.            
  801.             if (type > 0)
  802.                 p = std::pow(next() + 0.0, 1.0 / (type + 1));
  803.             else
  804.                 p = std::pow(next() + 0.0, - type + 1);
  805.  
  806.             return __testlib_min(__testlib_max((long long)(double(n) * p), 0LL), n - 1LL);
  807.         }
  808.     }
  809.    
  810.     /* See wnext(int, int). It uses the same algorithms. */
  811.     double wnext(int type)
  812.     {
  813.         if (abs(type) < random_t::lim)
  814.         {
  815.             double result = next();
  816.  
  817.             for (int i = 0; i < +type; i++)
  818.                 result = __testlib_max(result, next());
  819.            
  820.             for (int i = 0; i < -type; i++)
  821.                 result = __testlib_min(result, next());
  822.  
  823.             return result;
  824.         }
  825.         else
  826.         {
  827.             double p;
  828.            
  829.             if (type > 0)
  830.                 p = std::pow(next() + 0.0, 1.0 / (type + 1));
  831.             else
  832.                 p = std::pow(next() + 0.0, - type + 1);
  833.  
  834.             return p;
  835.         }
  836.     }
  837.    
  838.     /* See wnext(int, int). It uses the same algorithms. */
  839.     double wnext(double n, int type)
  840.     {
  841.         if (n <= 0)
  842.             __testlib_fail("random_t::wnext(double n, int type): n must be positive");
  843.  
  844.         if (abs(type) < random_t::lim)
  845.         {
  846.             double result = next();
  847.  
  848.             for (int i = 0; i < +type; i++)
  849.                 result = __testlib_max(result, next());
  850.            
  851.             for (int i = 0; i < -type; i++)
  852.                 result = __testlib_min(result, next());
  853.  
  854.             return n * result;
  855.         }
  856.         else
  857.         {
  858.             double p;
  859.            
  860.             if (type > 0)
  861.                 p = std::pow(next() + 0.0, 1.0 / (type + 1));
  862.             else
  863.                 p = std::pow(next() + 0.0, - type + 1);
  864.  
  865.             return n * p;
  866.         }
  867.     }
  868.  
  869.     /* See wnext(int, int). It uses the same algorithms. */
  870.     unsigned int wnext(unsigned int n, int type)
  871.     {
  872.         if (n >= INT_MAX)
  873.             __testlib_fail("random_t::wnext(unsigned int n, int type): n must be less INT_MAX");
  874.         return (unsigned int)wnext(int(n), type);
  875.     }
  876.    
  877.     /* See wnext(int, int). It uses the same algorithms. */
  878.     unsigned long long wnext(unsigned long long n, int type)
  879.     {
  880.         if (n >= (unsigned long long)(__TESTLIB_LONGLONG_MAX))
  881.             __testlib_fail("random_t::wnext(unsigned long long n, int type): n must be less LONGLONG_MAX");
  882.  
  883.         return (unsigned long long)wnext((long long)(n), type);
  884.     }
  885.  
  886.     /* See wnext(int, int). It uses the same algorithms. */
  887.     long wnext(long n, int type)
  888.     {
  889.         return (long)wnext((long long)(n), type);
  890.     }
  891.    
  892.     /* See wnext(int, int). It uses the same algorithms. */
  893.     unsigned long wnext(unsigned long n, int type)
  894.     {
  895.         if (n >= (unsigned long)(LONG_MAX))
  896.             __testlib_fail("random_t::wnext(unsigned long n, int type): n must be less LONG_MAX");
  897.  
  898.         return (unsigned long)wnext((unsigned long long)(n), type);
  899.     }
  900.  
  901.     /* Returns weighted random value in range [from, to]. */
  902.     int wnext(int from, int to, int type)
  903.     {
  904.         if (from > to)
  905.             __testlib_fail("random_t::wnext(int from, int to, int type): from can't not exceed to");
  906.         return wnext(to - from + 1, type) + from;
  907.     }
  908.    
  909.     /* Returns weighted random value in range [from, to]. */
  910.     int wnext(unsigned int from, unsigned int to, int type)
  911.     {
  912.         if (from > to)
  913.             __testlib_fail("random_t::wnext(unsigned int from, unsigned int to, int type): from can't not exceed to");
  914.         return int(wnext(to - from + 1, type) + from);
  915.     }
  916.    
  917.     /* Returns weighted random value in range [from, to]. */
  918.     long long wnext(long long from, long long to, int type)
  919.     {
  920.         if (from > to)
  921.             __testlib_fail("random_t::wnext(long long from, long long to, int type): from can't not exceed to");
  922.         return wnext(to - from + 1, type) + from;
  923.     }
  924.    
  925.     /* Returns weighted random value in range [from, to]. */
  926.     unsigned long long wnext(unsigned long long from, unsigned long long to, int type)
  927.     {
  928.         if (from > to)
  929.             __testlib_fail("random_t::wnext(unsigned long long from, unsigned long long to, int type): from can't not exceed to");
  930.         return wnext(to - from + 1, type) + from;
  931.     }
  932.    
  933.     /* Returns weighted random value in range [from, to]. */
  934.     long wnext(long from, long to, int type)
  935.     {
  936.         if (from > to)
  937.             __testlib_fail("random_t::wnext(long from, long to, int type): from can't not exceed to");
  938.         return wnext(to - from + 1, type) + from;
  939.     }
  940.    
  941.     /* Returns weighted random value in range [from, to]. */
  942.     unsigned long wnext(unsigned long from, unsigned long to, int type)
  943.     {
  944.         if (from > to)
  945.             __testlib_fail("random_t::wnext(unsigned long from, unsigned long to, int type): from can't not exceed to");
  946.         return wnext(to - from + 1, type) + from;
  947.     }
  948.    
  949.     /* Returns weighted random double value in range [from, to). */
  950.     double wnext(double from, double to, int type)
  951.     {
  952.         if (from > to)
  953.             __testlib_fail("random_t::wnext(double from, double to, int type): from can't not exceed to");
  954.         return wnext(to - from, type) + from;
  955.     }
  956.  
  957.     /* Returns weighted random element from container. */
  958.     template <typename Container>
  959.     typename Container::value_type wany(const Container& c, int type)
  960.     {
  961.         size_t size = c.size();
  962.         if (size <= 0)
  963.             __testlib_fail("random_t::wany(const Container& c, int type): c.size() must be positive");
  964.         return *(c.begin() + wnext(size, type));
  965.     }
  966.  
  967.     /* Returns weighted random element from iterator range. */
  968.     template <typename Iter>
  969.     typename Iter::value_type wany(const Iter& begin, const Iter& end, int type)
  970.     {
  971.         int size = int(end - begin);
  972.         if (size <= 0)
  973.             __testlib_fail("random_t::any(const Iter& begin, const Iter& end, int type): range must have positive length");
  974.         return *(begin + wnext(size, type));
  975.     }
  976. };
  977.  
  978. const int random_t::lim = 25;
  979. const unsigned long long random_t::multiplier = 0x5DEECE66DLL;
  980. const unsigned long long random_t::addend = 0xBLL;
  981. const unsigned long long random_t::mask = (1LL << 48) - 1;
  982. int random_t::version = -1;
  983.  
  984. /* Pattern implementation */
  985. bool pattern::matches(const std::string& s) const
  986. {
  987.     return matches(s, 0);
  988. }
  989.  
  990. static bool __pattern_isSlash(const std::string& s, size_t pos)
  991. {
  992.     return s[pos] == '\\';
  993. }
  994.  
  995. #ifdef __GNUC__
  996. __attribute__((pure))
  997. #endif
  998. static bool __pattern_isCommandChar(const std::string& s, size_t pos, char value)
  999. {
  1000.     if (pos >= s.length())
  1001.         return false;
  1002.  
  1003.     int slashes = 0;
  1004.  
  1005.     int before = int(pos) - 1;
  1006.     while (before >= 0 && s[before] == '\\')
  1007.         before--, slashes++;
  1008.  
  1009.     return slashes % 2 == 0 && s[pos] == value;
  1010. }
  1011.  
  1012. static char __pattern_getChar(const std::string& s, size_t& pos)
  1013. {
  1014.     if (__pattern_isSlash(s, pos))
  1015.         pos += 2;
  1016.     else
  1017.         pos++;
  1018.  
  1019.     return s[pos - 1];
  1020. }
  1021.  
  1022. #ifdef __GNUC__
  1023. __attribute__((pure))
  1024. #endif
  1025. static int __pattern_greedyMatch(const std::string& s, size_t pos, const std::vector<char> chars)
  1026. {
  1027.     int result = 0;
  1028.  
  1029.     while (pos < s.length())
  1030.     {
  1031.         char c = s[pos++];
  1032.         if (!std::binary_search(chars.begin(), chars.end(), c))
  1033.             break;
  1034.         else
  1035.             result++;
  1036.     }
  1037.  
  1038.     return result;
  1039. }
  1040.  
  1041. std::string pattern::src() const
  1042. {
  1043.     return s;
  1044. }
  1045.  
  1046. bool pattern::matches(const std::string& s, size_t pos) const
  1047. {
  1048.     std::string result;
  1049.  
  1050.     if (to > 0)
  1051.     {
  1052.         int size = __pattern_greedyMatch(s, pos, chars);
  1053.         if (size < from)
  1054.             return false;
  1055.         if (size > to)
  1056.             size = to;
  1057.         pos += size;
  1058.     }
  1059.  
  1060.     if (children.size() > 0)
  1061.     {
  1062.         for (size_t child = 0; child < children.size(); child++)
  1063.             if (children[child].matches(s, pos))
  1064.                 return true;
  1065.         return false;
  1066.     }
  1067.     else
  1068.         return pos == s.length();
  1069. }
  1070.  
  1071. std::string pattern::next(random_t& rnd) const
  1072. {
  1073.     std::string result;
  1074.     result.reserve(20);
  1075.  
  1076.     if (to == INT_MAX)
  1077.         __testlib_fail("pattern::next(random_t& rnd): can't process character '*' for generation");
  1078.  
  1079.     if (to > 0)
  1080.     {
  1081.         int count = rnd.next(to - from + 1) + from;
  1082.         for (int i = 0; i < count; i++)
  1083.             result += chars[rnd.next(int(chars.size()))];
  1084.     }
  1085.  
  1086.     if (children.size() > 0)
  1087.     {
  1088.         int child = rnd.next(int(children.size()));
  1089.         result += children[child].next(rnd);
  1090.     }
  1091.  
  1092.     return result;
  1093. }
  1094.  
  1095. static void __pattern_scanCounts(const std::string& s, size_t& pos, int& from, int& to)
  1096. {
  1097.     if (pos >= s.length())
  1098.     {
  1099.         from = to = 1;
  1100.         return;
  1101.     }
  1102.        
  1103.     if (__pattern_isCommandChar(s, pos, '{'))
  1104.     {
  1105.         std::vector<std::string> parts;
  1106.         std::string part;
  1107.  
  1108.         pos++;
  1109.  
  1110.         while (pos < s.length() && !__pattern_isCommandChar(s, pos, '}'))
  1111.         {
  1112.             if (__pattern_isCommandChar(s, pos, ','))
  1113.                 parts.push_back(part), part = "", pos++;
  1114.             else
  1115.                 part += __pattern_getChar(s, pos);
  1116.         }
  1117.  
  1118.         if (part != "")
  1119.             parts.push_back(part);
  1120.  
  1121.         if (!__pattern_isCommandChar(s, pos, '}'))
  1122.             __testlib_fail("pattern: Illegal pattern (or part) \"" + s + "\"");
  1123.  
  1124.         pos++;
  1125.  
  1126.         if (parts.size() < 1 || parts.size() > 2)
  1127.             __testlib_fail("pattern: Illegal pattern (or part) \"" + s + "\"");
  1128.  
  1129.         std::vector<int> numbers;
  1130.  
  1131.         for (size_t i = 0; i < parts.size(); i++)
  1132.         {
  1133.             if (parts[i].length() == 0)
  1134.                 __testlib_fail("pattern: Illegal pattern (or part) \"" + s + "\"");
  1135.             int number;
  1136.             if (std::sscanf(parts[i].c_str(), "%d", &number) != 1)
  1137.                 __testlib_fail("pattern: Illegal pattern (or part) \"" + s + "\"");
  1138.             numbers.push_back(number);
  1139.         }
  1140.  
  1141.         if (numbers.size() == 1)
  1142.             from = to = numbers[0];
  1143.         else
  1144.             from = numbers[0], to = numbers[1];
  1145.  
  1146.         if (from > to)
  1147.             __testlib_fail("pattern: Illegal pattern (or part) \"" + s + "\"");
  1148.     }
  1149.     else
  1150.     {
  1151.         if (__pattern_isCommandChar(s, pos, '?'))
  1152.         {
  1153.             from = 0, to = 1, pos++;
  1154.             return;
  1155.         }
  1156.  
  1157.         if (__pattern_isCommandChar(s, pos, '*'))
  1158.         {
  1159.             from = 0, to = INT_MAX, pos++;
  1160.             return;
  1161.         }
  1162.  
  1163.         if (__pattern_isCommandChar(s, pos, '+'))
  1164.         {
  1165.             from = 1, to = INT_MAX, pos++;
  1166.             return;
  1167.         }
  1168.        
  1169.         from = to = 1;
  1170.     }
  1171. }
  1172.  
  1173. static std::vector<char> __pattern_scanCharSet(const std::string& s, size_t& pos)
  1174. {
  1175.     if (pos >= s.length())
  1176.         __testlib_fail("pattern: Illegal pattern (or part) \"" + s + "\"");
  1177.  
  1178.     std::vector<char> result;
  1179.  
  1180.     if (__pattern_isCommandChar(s, pos, '['))
  1181.     {
  1182.         pos++;
  1183.         bool negative = __pattern_isCommandChar(s, pos, '^');
  1184.  
  1185.         char prev = 0;
  1186.  
  1187.         while (pos < s.length() && !__pattern_isCommandChar(s, pos, ']'))
  1188.         {
  1189.             if (__pattern_isCommandChar(s, pos, '-') && prev != 0)
  1190.             {
  1191.                 pos++;
  1192.  
  1193.                 if (pos + 1 == s.length() || __pattern_isCommandChar(s, pos, ']'))
  1194.                 {
  1195.                     result.push_back(prev);
  1196.                     prev = '-';
  1197.                     continue;
  1198.                 }
  1199.  
  1200.                 char next = __pattern_getChar(s, pos);
  1201.                 if (prev > next)
  1202.                     __testlib_fail("pattern: Illegal pattern (or part) \"" + s + "\"");
  1203.  
  1204.                 for (char c = prev; c != next; c++)
  1205.                     result.push_back(c);
  1206.                 result.push_back(next);
  1207.  
  1208.                 prev = 0;
  1209.             }
  1210.             else
  1211.             {
  1212.                 if (prev != 0)
  1213.                     result.push_back(prev);
  1214.                 prev = __pattern_getChar(s, pos);
  1215.             }
  1216.         }
  1217.  
  1218.         if (prev != 0)
  1219.             result.push_back(prev);
  1220.  
  1221.         if (!__pattern_isCommandChar(s, pos, ']'))
  1222.             __testlib_fail("pattern: Illegal pattern (or part) \"" + s + "\"");
  1223.  
  1224.         pos++;
  1225.  
  1226.         if (negative)
  1227.         {
  1228.             std::sort(result.begin(), result.end());
  1229.             std::vector<char> actuals;
  1230.             for (int code = 0; code < 255; code++)
  1231.             {
  1232.                 char c = char(code);
  1233.                 if (!std::binary_search(result.begin(), result.end(), c))
  1234.                     actuals.push_back(c);
  1235.             }
  1236.             result = actuals;
  1237.         }
  1238.  
  1239.         std::sort(result.begin(), result.end());
  1240.     }
  1241.     else
  1242.         result.push_back(__pattern_getChar(s, pos));
  1243.  
  1244.     return result;
  1245. }
  1246.  
  1247. pattern::pattern(std::string s): s(s), from(0), to(0)
  1248. {
  1249.     std::string t;
  1250.     for (size_t i = 0; i < s.length(); i++)
  1251.         if (!__pattern_isCommandChar(s, i, ' '))
  1252.             t += s[i];
  1253.     s = t;
  1254.  
  1255.     int opened = 0;
  1256.     int firstClose = -1;
  1257.     std::vector<int> seps;
  1258.  
  1259.     for (size_t i = 0; i < s.length(); i++)
  1260.     {
  1261.         if (__pattern_isCommandChar(s, i, '('))
  1262.         {
  1263.             opened++;
  1264.             continue;
  1265.         }
  1266.  
  1267.         if (__pattern_isCommandChar(s, i, ')'))
  1268.         {
  1269.             opened--;
  1270.             if (opened == 0 && firstClose == -1)
  1271.                 firstClose = int(i);
  1272.             continue;
  1273.         }
  1274.        
  1275.         if (opened < 0)
  1276.             __testlib_fail("pattern: Illegal pattern (or part) \"" + s + "\"");
  1277.  
  1278.         if (__pattern_isCommandChar(s, i, '|') && opened == 0)
  1279.             seps.push_back(int(i));
  1280.     }
  1281.  
  1282.     if (opened != 0)
  1283.         __testlib_fail("pattern: Illegal pattern (or part) \"" + s + "\"");
  1284.  
  1285.     if (seps.size() == 0 && firstClose + 1 == (int)s.length()
  1286.             && __pattern_isCommandChar(s, 0, '(') && __pattern_isCommandChar(s, s.length() - 1, ')'))
  1287.     {
  1288.         children.push_back(pattern(s.substr(1, s.length() - 2)));
  1289.     }
  1290.     else
  1291.     {
  1292.         if (seps.size() > 0)
  1293.         {
  1294.             seps.push_back(int(s.length()));
  1295.             int last = 0;
  1296.  
  1297.             for (size_t i = 0; i < seps.size(); i++)
  1298.             {
  1299.                 children.push_back(pattern(s.substr(last, seps[i] - last)));
  1300.                 last = seps[i] + 1;
  1301.             }
  1302.         }
  1303.         else
  1304.         {
  1305.             size_t pos = 0;
  1306.             chars = __pattern_scanCharSet(s, pos);
  1307.             __pattern_scanCounts(s, pos, from, to);
  1308.             if (pos < s.length())
  1309.                 children.push_back(pattern(s.substr(pos)));
  1310.         }
  1311.     }
  1312. }
  1313. /* End of pattern implementation */
  1314.  
  1315. template <typename C>
  1316. inline bool isEof(C c)
  1317. {
  1318.     return c == EOFC;
  1319. }
  1320.  
  1321. template <typename C>
  1322. inline bool isEoln(C c)
  1323. {
  1324.     return (c == LF || c == CR);
  1325. }
  1326.  
  1327. template<typename C>
  1328. inline bool isBlanks(C c)
  1329. {
  1330.     return (c == LF || c == CR || c == SPACE || c == TAB);
  1331. }
  1332.  
  1333. enum TMode
  1334. {
  1335.     _input, _output, _answer
  1336. };
  1337.  
  1338. /* Outcomes 6-15 are reserved for future use. */
  1339. enum TResult
  1340. {
  1341.     _ok = 0,
  1342.     _wa = 1,
  1343.     _pe = 2,
  1344.     _fail = 3,
  1345.     _dirt = 4,
  1346.     _points = 5,
  1347.     _unexpected_eof = 8,
  1348.     _partially = 16
  1349. };
  1350.  
  1351. enum TTestlibMode
  1352. {
  1353.     _unknown, _checker, _validator, _generator, _interactor
  1354. };
  1355.  
  1356. #define _pc(exitCode) (TResult(_partially + (exitCode)))
  1357.  
  1358. /* Outcomes 6-15 are reserved for future use. */
  1359. const std::string outcomes[] = {
  1360.     "accepted",
  1361.     "wrong-answer",
  1362.     "presentation-error",
  1363.     "fail",
  1364.     "fail",
  1365. #ifndef PCMS2
  1366.     "points",
  1367. #else
  1368.     "relative-scoring",
  1369. #endif
  1370.     "reserved",
  1371.     "reserved",
  1372.     "unexpected-eof",
  1373.     "reserved",
  1374.     "reserved",
  1375.     "reserved",
  1376.     "reserved",
  1377.     "reserved",
  1378.     "reserved",
  1379.     "reserved",
  1380.     "partially-correct"
  1381. };
  1382.  
  1383. class InputStreamReader
  1384. {
  1385. public:
  1386.     virtual int curChar() = 0;    
  1387.     virtual int nextChar() = 0;    
  1388.     virtual void skipChar() = 0;
  1389.     virtual void unreadChar(int c) = 0;
  1390.     virtual std::string getName() = 0;
  1391.     virtual bool eof() = 0;
  1392.     virtual void close() = 0;
  1393.     virtual ~InputStreamReader() = 0;
  1394. };
  1395.  
  1396. InputStreamReader::~InputStreamReader()
  1397. {
  1398.     // No operations.
  1399. }
  1400.  
  1401. class StringInputStreamReader: public InputStreamReader
  1402. {
  1403. private:
  1404.     std::string s;
  1405.     size_t pos;
  1406.  
  1407. public:
  1408.     StringInputStreamReader(const std::string& content): s(content), pos(0)
  1409.     {
  1410.         // No operations.
  1411.     }
  1412.  
  1413.     int curChar()
  1414.     {
  1415.         if (pos >= s.length())
  1416.             return EOFC;
  1417.         else
  1418.             return s[pos];
  1419.     }
  1420.  
  1421.     int nextChar()
  1422.     {
  1423.         if (pos >= s.length())
  1424.         {
  1425.             pos++;
  1426.             return EOFC;
  1427.         }
  1428.         else
  1429.             return s[pos++];
  1430.     }
  1431.  
  1432.     void skipChar()
  1433.     {
  1434.         pos++;
  1435.     }
  1436.  
  1437.     void unreadChar(int c)
  1438.     {  
  1439.         if (pos == 0)
  1440.             __testlib_fail("FileFileInputStreamReader::unreadChar(int): pos == 0.");
  1441.         pos--;
  1442.         if (pos < s.length())
  1443.             s[pos] = char(c);
  1444.     }
  1445.  
  1446.     std::string getName()
  1447.     {
  1448.         return __testlib_part(s);
  1449.     }
  1450.  
  1451.     bool eof()
  1452.     {
  1453.         return pos >= s.length();
  1454.     }
  1455.  
  1456.     void close()
  1457.     {
  1458.         // No operations.
  1459.     }
  1460. };
  1461.  
  1462. class FileInputStreamReader: public InputStreamReader
  1463. {
  1464. private:
  1465.     std::FILE* file;
  1466.     std::string name;
  1467.  
  1468.     inline int postprocessGetc(int getcResult)
  1469.     {
  1470.         if (getcResult != EOF)
  1471.             return getcResult;
  1472.         else
  1473.             return EOFC;
  1474.     }
  1475.  
  1476. public:
  1477.     FileInputStreamReader(std::FILE* file, const std::string& name): file(file), name(name)
  1478.     {
  1479.         // No operations.
  1480.     }
  1481.  
  1482.     int curChar()
  1483.     {
  1484.         if (feof(file))
  1485.             return EOFC;
  1486.         else
  1487.         {
  1488.             int c = getc(file);
  1489.             ungetc(c, file);
  1490.             return postprocessGetc(c);
  1491.         }
  1492.     }
  1493.  
  1494.     int nextChar()
  1495.     {
  1496.         if (feof(file))
  1497.             return EOFC;
  1498.         else
  1499.             return postprocessGetc(getc(file));
  1500.     }
  1501.  
  1502.     void skipChar()
  1503.     {
  1504.         getc(file);
  1505.     }
  1506.  
  1507.     void unreadChar(int c)
  1508.     {  
  1509.         ungetc(c, file);
  1510.     }
  1511.  
  1512.     std::string getName()
  1513.     {
  1514.         return name;
  1515.     }
  1516.  
  1517.     bool eof()
  1518.     {
  1519.         if (NULL == file || feof(file))
  1520.             return true;
  1521.         else
  1522.         {
  1523.             int c = nextChar();
  1524.             if (c == EOFC || (c == EOF && feof(file)))
  1525.                 return true;
  1526.             unreadChar(c);
  1527.             return false;
  1528.         }
  1529.     }
  1530.  
  1531.     void close()
  1532.     {
  1533.         if (NULL != file)
  1534.         {
  1535.             fclose(file);
  1536.             file = NULL;
  1537.         }
  1538.     }
  1539. };
  1540.  
  1541. class BufferedFileInputStreamReader: public InputStreamReader
  1542. {
  1543. private:
  1544.     static const size_t BUFFER_SIZE;
  1545.     static const size_t MAX_UNREAD_COUNT;
  1546.    
  1547.     std::FILE* file;
  1548.     char* buffer;
  1549.     bool* isEof;
  1550.     int bufferPos;
  1551.     size_t bufferSize;
  1552.  
  1553.     std::string name;
  1554.  
  1555.     bool refill()
  1556.     {
  1557.         if (NULL == file)
  1558.             __testlib_fail("BufferedFileInputStreamReader: file == NULL (" + getName() + ")");
  1559.  
  1560.         if (bufferPos >= int(bufferSize))
  1561.         {
  1562.             size_t readSize = fread(
  1563.                 buffer + MAX_UNREAD_COUNT,
  1564.                 1,
  1565.                 BUFFER_SIZE - MAX_UNREAD_COUNT,
  1566.                 file
  1567.             );
  1568.  
  1569.             if (readSize < BUFFER_SIZE - MAX_UNREAD_COUNT
  1570.                     && ferror(file))
  1571.                 __testlib_fail("BufferedFileInputStreamReader: unable to read (" + getName() + ")");
  1572.  
  1573.             bufferSize = MAX_UNREAD_COUNT + readSize;
  1574.             bufferPos = int(MAX_UNREAD_COUNT);
  1575.             std::memset(isEof + MAX_UNREAD_COUNT, 0, sizeof(isEof[0]) * readSize);
  1576.  
  1577.             return readSize > 0;
  1578.         }
  1579.         else
  1580.             return true;
  1581.     }
  1582.  
  1583. public:
  1584.     BufferedFileInputStreamReader(std::FILE* file, const std::string& name): file(file), name(name)
  1585.     {
  1586.         buffer = new char[BUFFER_SIZE];
  1587.         isEof = new bool[BUFFER_SIZE];
  1588.         bufferSize = MAX_UNREAD_COUNT;
  1589.         bufferPos = int(MAX_UNREAD_COUNT);
  1590.     }
  1591.  
  1592.     ~BufferedFileInputStreamReader()
  1593.     {
  1594.         if (NULL != buffer)
  1595.         {
  1596.             delete[] buffer;
  1597.             buffer = NULL;
  1598.         }
  1599.         if (NULL != isEof)
  1600.         {
  1601.             delete[] isEof;
  1602.             isEof = NULL;
  1603.         }
  1604.     }
  1605.  
  1606.     int curChar()
  1607.     {
  1608.         if (!refill())
  1609.             return EOFC;
  1610.  
  1611.         return isEof[bufferPos] ? EOFC : buffer[bufferPos];
  1612.     }
  1613.  
  1614.     int nextChar()
  1615.     {
  1616.         if (!refill())
  1617.             return EOFC;
  1618.  
  1619.         return isEof[bufferPos] ? EOFC : buffer[bufferPos++];
  1620.     }
  1621.  
  1622.     void skipChar()
  1623.     {
  1624.         bufferPos++;
  1625.     }
  1626.  
  1627.     void unreadChar(int c)
  1628.     {  
  1629.         bufferPos--;
  1630.         if (bufferPos < 0)
  1631.             __testlib_fail("BufferedFileInputStreamReader::unreadChar(int): bufferPos < 0");
  1632.         isEof[bufferPos] = (c == EOFC);
  1633.         buffer[bufferPos] = char(c);
  1634.     }
  1635.  
  1636.     std::string getName()
  1637.     {
  1638.         return name;
  1639.     }
  1640.    
  1641.     bool eof()
  1642.     {
  1643.         return !refill() || EOFC == curChar();
  1644.     }
  1645.  
  1646.     void close()
  1647.     {
  1648.         if (NULL != file)
  1649.         {
  1650.             fclose(file);
  1651.             file = NULL;
  1652.         }
  1653.     }
  1654. };
  1655.  
  1656. const size_t BufferedFileInputStreamReader::BUFFER_SIZE = 2000000;
  1657. const size_t BufferedFileInputStreamReader::MAX_UNREAD_COUNT = BufferedFileInputStreamReader::BUFFER_SIZE / 2;
  1658.  
  1659. /*
  1660.  * Streams to be used for reading data in checkers or validators.
  1661.  * Each read*() method moves pointer to the next character after the
  1662.  * read value.
  1663.  */
  1664. struct InStream
  1665. {
  1666.     /* Do not use them. */
  1667.     InStream();
  1668.     ~InStream();
  1669.  
  1670.     /* Wrap std::string with InStream. */
  1671.     InStream(const InStream& baseStream, std::string content);
  1672.  
  1673.     InputStreamReader* reader;
  1674.  
  1675.     std::string name;
  1676.     TMode mode;
  1677.     bool opened;
  1678.     bool stdfile;
  1679.     bool strict;
  1680.  
  1681.     int wordReserveSize;
  1682.     std::string _tmpReadToken;
  1683.  
  1684.     int readManyIteration;
  1685.  
  1686.     void init(std::string fileName, TMode mode);
  1687.     void init(std::FILE* f, TMode mode);
  1688.  
  1689.     /* Moves stream pointer to the first non-white-space character or EOF. */
  1690.     void skipBlanks();
  1691.    
  1692.     /* Returns current character in the stream. Doesn't remove it from stream. */
  1693.     char curChar();
  1694.     /* Moves stream pointer one character forward. */
  1695.     void skipChar();
  1696.     /* Returns current character and moves pointer one character forward. */
  1697.     char nextChar();
  1698.    
  1699.     /* Returns current character and moves pointer one character forward. */
  1700.     char readChar();
  1701.     /* As "readChar()" but ensures that the result is equal to given parameter. */
  1702.     char readChar(char c);
  1703.     /* As "readChar()" but ensures that the result is equal to the space (code=32). */
  1704.     char readSpace();
  1705.     /* Puts back the character into the stream. */
  1706.     void unreadChar(char c);
  1707.  
  1708.     /* Reopens stream, you should not use it. */
  1709.     void reset(std::FILE* file = NULL);
  1710.     /* Checks that current position is EOF. If not it doesn't move stream pointer. */
  1711.     bool eof();
  1712.     /* Moves pointer to the first non-white-space character and calls "eof()". */
  1713.     bool seekEof();
  1714.  
  1715.     /*
  1716.      * Checks that current position contains EOLN.
  1717.      * If not it doesn't move stream pointer.
  1718.      * In strict mode expects "#13#10" for windows or "#10" for other platforms.
  1719.      */
  1720.     bool eoln();
  1721.     /* Moves pointer to the first non-space and non-tab character and calls "eoln()". */
  1722.     bool seekEoln();
  1723.  
  1724.     /* Moves stream pointer to the first character of the next line (if exists). */
  1725.     void nextLine();
  1726.  
  1727.     /*
  1728.      * Reads new token. Ignores white-spaces into the non-strict mode
  1729.      * (strict mode is used in validators usually).
  1730.      */
  1731.     std::string readWord();
  1732.     /* The same as "readWord()", it is preffered to use "readToken()". */
  1733.     std::string readToken();
  1734.     /* The same as "readWord()", but ensures that token matches to given pattern. */
  1735.     std::string readWord(const std::string& ptrn, const std::string& variableName = "");
  1736.     std::string readWord(const pattern& p, const std::string& variableName = "");
  1737.     std::vector<std::string> readWords(int size, const std::string& ptrn, const std::string& variablesName = "", int indexBase = 1);
  1738.     std::vector<std::string> readWords(int size, const pattern& p, const std::string& variablesName = "", int indexBase = 1);
  1739.     /* The same as "readToken()", but ensures that token matches to given pattern. */
  1740.     std::string readToken(const std::string& ptrn, const std::string& variableName = "");
  1741.     std::string readToken(const pattern& p, const std::string& variableName = "");
  1742.     std::vector<std::string> readTokens(int size, const std::string& ptrn, const std::string& variablesName = "", int indexBase = 1);
  1743.     std::vector<std::string> readTokens(int size, const pattern& p, const std::string& variablesName = "", int indexBase = 1);
  1744.  
  1745.     void readWordTo(std::string& result);
  1746.     void readWordTo(std::string& result, const pattern& p, const std::string& variableName = "");
  1747.     void readWordTo(std::string& result, const std::string& ptrn, const std::string& variableName = "");
  1748.  
  1749.     void readTokenTo(std::string& result);
  1750.     void readTokenTo(std::string& result, const pattern& p, const std::string& variableName = "");
  1751.     void readTokenTo(std::string& result, const std::string& ptrn, const std::string& variableName = "");
  1752.  
  1753.     /*
  1754.      * Reads new long long value. Ignores white-spaces into the non-strict mode
  1755.      * (strict mode is used in validators usually).
  1756.      */
  1757.     long long readLong();
  1758.     unsigned long long readUnsignedLong();
  1759.     /*
  1760.      * Reads new int. Ignores white-spaces into the non-strict mode
  1761.      * (strict mode is used in validators usually).
  1762.      */
  1763.     int readInteger();
  1764.     /*
  1765.      * Reads new int. Ignores white-spaces into the non-strict mode
  1766.      * (strict mode is used in validators usually).
  1767.      */
  1768.     int readInt();
  1769.  
  1770.     /* As "readLong()" but ensures that value in the range [minv,maxv]. */
  1771.     long long readLong(long long minv, long long maxv, const std::string& variableName = "");
  1772.     /* Reads space-separated sequence of long longs. */
  1773.     std::vector<long long> readLongs(int size, long long minv, long long maxv, const std::string& variablesName = "", int indexBase = 1);
  1774.  
  1775.     unsigned long long readUnsignedLong(unsigned long long minv, unsigned long long maxv, const std::string& variableName = "");
  1776.     std::vector<unsigned long long> readUnsignedLongs(int size, unsigned long long minv, unsigned long long maxv, const std::string& variablesName = "", int indexBase = 1);
  1777.     unsigned long long readLong(unsigned long long minv, unsigned long long maxv, const std::string& variableName = "");
  1778.     std::vector<unsigned long long> readLongs(int size, unsigned long long minv, unsigned long long maxv, const std::string& variablesName = "", int indexBase = 1);
  1779.  
  1780.     /* As "readInteger()" but ensures that value in the range [minv,maxv]. */
  1781.     int readInteger(int minv, int maxv, const std::string& variableName = "");
  1782.     /* As "readInt()" but ensures that value in the range [minv,maxv]. */
  1783.     int readInt(int minv, int maxv, const std::string& variableName = "");
  1784.     /* Reads space-separated sequence of integers. */
  1785.     std::vector<int> readIntegers(int size, int minv, int maxv, const std::string& variablesName = "", int indexBase = 1);
  1786.     /* Reads space-separated sequence of integers. */
  1787.     std::vector<int> readInts(int size, int minv, int maxv, const std::string& variablesName = "", int indexBase = 1);
  1788.  
  1789.     /*
  1790.      * Reads new double. Ignores white-spaces into the non-strict mode
  1791.      * (strict mode is used in validators usually).
  1792.      */
  1793.     double readReal();
  1794.     /*
  1795.      * Reads new double. Ignores white-spaces into the non-strict mode
  1796.      * (strict mode is used in validators usually).
  1797.      */
  1798.     double readDouble();
  1799.    
  1800.     /* As "readReal()" but ensures that value in the range [minv,maxv]. */
  1801.     double readReal(double minv, double maxv, const std::string& variableName = "");
  1802.     std::vector<double> readReals(int size, double minv, double maxv, const std::string& variablesName = "", int indexBase = 1);
  1803.     /* As "readDouble()" but ensures that value in the range [minv,maxv]. */
  1804.     double readDouble(double minv, double maxv, const std::string& variableName = "");
  1805.     std::vector<double> readDoubles(int size, double minv, double maxv, const std::string& variablesName = "", int indexBase = 1);
  1806.    
  1807.     /*
  1808.      * As "readReal()" but ensures that value in the range [minv,maxv] and
  1809.      * number of digit after the decimal point is in range [minAfterPointDigitCount,maxAfterPointDigitCount]
  1810.      * and number is in the form "[-]digit(s)[.digit(s)]".
  1811.      */
  1812.     double readStrictReal(double minv, double maxv,
  1813.             int minAfterPointDigitCount, int maxAfterPointDigitCount,
  1814.             const std::string& variableName = "");
  1815.     std::vector<double> readStrictReals(int size, double minv, double maxv,
  1816.             int minAfterPointDigitCount, int maxAfterPointDigitCount,
  1817.             const std::string& variablesName = "", int indexBase = 1);
  1818.  
  1819.     /*
  1820.      * As "readDouble()" but ensures that value in the range [minv,maxv] and
  1821.      * number of digit after the decimal point is in range [minAfterPointDigitCount,maxAfterPointDigitCount]
  1822.      * and number is in the form "[-]digit(s)[.digit(s)]".
  1823.      */
  1824.     double readStrictDouble(double minv, double maxv,
  1825.             int minAfterPointDigitCount, int maxAfterPointDigitCount,
  1826.             const std::string& variableName = "");
  1827.     std::vector<double> readStrictDoubles(int size, double minv, double maxv,
  1828.             int minAfterPointDigitCount, int maxAfterPointDigitCount,
  1829.             const std::string& variablesName = "", int indexBase = 1);
  1830.    
  1831.     /* As readLine(). */
  1832.     std::string readString();
  1833.     /* Read many lines. */
  1834.     std::vector<std::string> readStrings(int size, int indexBase = 1);
  1835.     /* See readLine(). */
  1836.     void readStringTo(std::string& result);
  1837.     /* The same as "readLine()/readString()", but ensures that line matches to the given pattern. */
  1838.     std::string readString(const pattern& p, const std::string& variableName = "");
  1839.     /* The same as "readLine()/readString()", but ensures that line matches to the given pattern. */
  1840.     std::string readString(const std::string& ptrn, const std::string& variableName = "");
  1841.     /* Read many lines. */
  1842.     std::vector<std::string> readStrings(int size, const pattern& p, const std::string& variableName = "", int indexBase = 1);
  1843.     /* Read many lines. */
  1844.     std::vector<std::string> readStrings(int size, const std::string& ptrn, const std::string& variableName = "", int indexBase = 1);
  1845.     /* The same as "readLine()/readString()", but ensures that line matches to the given pattern. */
  1846.     void readStringTo(std::string& result, const pattern& p, const std::string& variableName = "");
  1847.     /* The same as "readLine()/readString()", but ensures that line matches to the given pattern. */
  1848.     void readStringTo(std::string& result, const std::string& ptrn, const std::string& variableName = "");
  1849.  
  1850.     /*
  1851.      * Reads line from the current position to EOLN or EOF. Moves stream pointer to
  1852.      * the first character of the new line (if possible).
  1853.      */
  1854.     std::string readLine();
  1855.     /* Read many lines. */
  1856.     std::vector<std::string> readLines(int size, int indexBase = 1);
  1857.     /* See readLine(). */
  1858.     void readLineTo(std::string& result);
  1859.     /* The same as "readLine()", but ensures that line matches to the given pattern. */
  1860.     std::string readLine(const pattern& p, const std::string& variableName = "");
  1861.     /* The same as "readLine()", but ensures that line matches to the given pattern. */
  1862.     std::string readLine(const std::string& ptrn, const std::string& variableName = "");
  1863.     /* Read many lines. */
  1864.     std::vector<std::string> readLines(int size, const pattern& p, const std::string& variableName = "", int indexBase = 1);
  1865.     /* Read many lines. */
  1866.     std::vector<std::string> readLines(int size, const std::string& ptrn, const std::string& variableName = "", int indexBase = 1);
  1867.     /* The same as "readLine()", but ensures that line matches to the given pattern. */
  1868.     void readLineTo(std::string& result, const pattern& p, const std::string& variableName = "");
  1869.     /* The same as "readLine()", but ensures that line matches to the given pattern. */
  1870.     void readLineTo(std::string& result, const std::string& ptrn, const std::string& variableName = "");
  1871.  
  1872.     /* Reads EOLN or fails. Use it in validators. Calls "eoln()" method internally. */
  1873.     void readEoln();
  1874.     /* Reads EOF or fails. Use it in validators. Calls "eof()" method internally. */
  1875.     void readEof();
  1876.  
  1877.     /*
  1878.      * Quit-functions aborts program with <result> and <message>:
  1879.      * input/answer streams replace any result to FAIL.
  1880.      */
  1881.     NORETURN void quit(TResult result, const char* msg);
  1882.     /*
  1883.      * Quit-functions aborts program with <result> and <message>:
  1884.      * input/answer streams replace any result to FAIL.
  1885.      */
  1886.     NORETURN void quitf(TResult result, const char* msg, ...);
  1887.     /*
  1888.      * Quit-functions aborts program with <result> and <message>:
  1889.      * input/answer streams replace any result to FAIL.
  1890.      */
  1891.     NORETURN void quits(TResult result, std::string msg);
  1892.  
  1893.     void close();
  1894.  
  1895.     const static int NO_INDEX = INT_MAX;
  1896.  
  1897.     const static WORD LightGray = 0x07;    
  1898.     const static WORD LightRed = 0x0c;    
  1899.     const static WORD LightCyan = 0x0b;    
  1900.     const static WORD LightGreen = 0x0a;    
  1901.     const static WORD LightYellow = 0x0e;    
  1902.  
  1903.     static void textColor(WORD color);
  1904.     static void quitscr(WORD color, const char* msg);
  1905.     static void quitscrS(WORD color, std::string msg);
  1906.     void xmlSafeWrite(std::FILE * file, const char* msg);
  1907.  
  1908. private:
  1909.     InStream(const InStream&);
  1910.     InStream& operator =(const InStream&);
  1911. };
  1912.  
  1913. InStream inf;
  1914. InStream ouf;
  1915. InStream ans;
  1916. bool appesMode;
  1917. std::string resultName;
  1918. std::string checkerName = "untitled checker";
  1919. random_t rnd;
  1920. TTestlibMode testlibMode = _unknown;
  1921. double __testlib_points = std::numeric_limits<float>::infinity();
  1922.  
  1923. struct ValidatorBoundsHit
  1924. {
  1925.     static const double EPS;
  1926.     bool minHit;
  1927.     bool maxHit;
  1928.  
  1929.     ValidatorBoundsHit(bool minHit = false, bool maxHit = false): minHit(minHit), maxHit(maxHit)
  1930.     {
  1931.     };
  1932.  
  1933.     ValidatorBoundsHit merge(const ValidatorBoundsHit& validatorBoundsHit)
  1934.     {
  1935.         return ValidatorBoundsHit(
  1936.             __testlib_max(minHit, validatorBoundsHit.minHit),
  1937.             __testlib_max(maxHit, validatorBoundsHit.maxHit)
  1938.         );
  1939.     }
  1940. };
  1941.  
  1942. const double ValidatorBoundsHit::EPS = 1E-12;
  1943.  
  1944. class Validator
  1945. {
  1946. private:
  1947.     std::string _testset;
  1948.     std::string _group;
  1949.     std::string _testOverviewLogFileName;
  1950.     std::map<std::string, ValidatorBoundsHit> _boundsHitByVariableName;
  1951.     std::set<std::string> _features;
  1952.     std::set<std::string> _hitFeatures;
  1953.  
  1954.     bool isVariableNameBoundsAnalyzable(const std::string& variableName)
  1955.     {
  1956.         for (size_t i = 0; i < variableName.length(); i++)
  1957.             if ((variableName[i] >= '0' && variableName[i] <= '9') || variableName[i] < ' ')
  1958.                 return false;
  1959.         return true;
  1960.     }
  1961.  
  1962.     bool isFeatureNameAnalyzable(const std::string& featureName)
  1963.     {
  1964.         for (size_t i = 0; i < featureName.length(); i++)
  1965.             if (featureName[i] < ' ')
  1966.                 return false;
  1967.         return true;
  1968.     }
  1969. public:
  1970.     Validator(): _testset("tests"), _group()
  1971.     {
  1972.     }
  1973.  
  1974.     std::string testset() const
  1975.     {
  1976.         return _testset;
  1977.     }
  1978.    
  1979.     std::string group() const
  1980.     {
  1981.         return _group;
  1982.     }
  1983.  
  1984.     std::string testOverviewLogFileName() const
  1985.     {
  1986.         return _testOverviewLogFileName;
  1987.     }
  1988.    
  1989.     void setTestset(const char* const testset)
  1990.     {
  1991.         _testset = testset;
  1992.     }
  1993.  
  1994.     void setGroup(const char* const group)
  1995.     {
  1996.         _group = group;
  1997.     }
  1998.  
  1999.     void setTestOverviewLogFileName(const char* const testOverviewLogFileName)
  2000.     {
  2001.         _testOverviewLogFileName = testOverviewLogFileName;
  2002.     }
  2003.  
  2004.     void addBoundsHit(const std::string& variableName, ValidatorBoundsHit boundsHit)
  2005.     {
  2006.         if (isVariableNameBoundsAnalyzable(variableName))
  2007.         {
  2008.             _boundsHitByVariableName[variableName]
  2009.                 = boundsHit.merge(_boundsHitByVariableName[variableName]);
  2010.         }
  2011.     }
  2012.  
  2013.     std::string getBoundsHitLog()
  2014.     {
  2015.         std::string result;
  2016.         for (std::map<std::string, ValidatorBoundsHit>::iterator i = _boundsHitByVariableName.begin();
  2017.             i != _boundsHitByVariableName.end();
  2018.             i++)
  2019.         {
  2020.             result += "\"" + i->first + "\":";
  2021.             if (i->second.minHit)
  2022.                 result += " min-value-hit";
  2023.             if (i->second.maxHit)
  2024.                 result += " max-value-hit";
  2025.             result += "\n";
  2026.         }
  2027.         return result;
  2028.     }
  2029.  
  2030.     std::string getFeaturesLog()
  2031.     {
  2032.         std::string result;
  2033.         for (std::set<std::string>::iterator i = _features.begin();
  2034.             i != _features.end();
  2035.             i++)
  2036.         {
  2037.             result += "feature \"" + *i + "\":";
  2038.             if (_hitFeatures.count(*i))
  2039.                 result += " hit";
  2040.             result += "\n";
  2041.         }
  2042.         return result;
  2043.     }
  2044.  
  2045.     void writeTestOverviewLog()
  2046.     {
  2047.         if (!_testOverviewLogFileName.empty())
  2048.         {
  2049.             std::string fileName(_testOverviewLogFileName);
  2050.             _testOverviewLogFileName = "";
  2051.             FILE* testOverviewLogFile = fopen(fileName.c_str(), "w");
  2052.             if (NULL == testOverviewLogFile)
  2053.                 __testlib_fail("Validator::writeTestOverviewLog: can't test overview log to (" + fileName + ")");
  2054.             fprintf(testOverviewLogFile, "%s%s", getBoundsHitLog().c_str(), getFeaturesLog().c_str());
  2055.             if (fclose(testOverviewLogFile))
  2056.                 __testlib_fail("Validator::writeTestOverviewLog: can't close test overview log file (" + fileName + ")");
  2057.         }
  2058.     }
  2059.  
  2060.     void addFeature(const std::string& feature)
  2061.     {
  2062.         if (_features.count(feature))
  2063.             __testlib_fail("Feature " + feature + " registered twice.");
  2064.         if (!isFeatureNameAnalyzable(feature))
  2065.             __testlib_fail("Feature name '" + feature + "' contains restricted characters.");
  2066.  
  2067.         _features.insert(feature);
  2068.     }
  2069.  
  2070.     void feature(const std::string& feature)
  2071.     {
  2072.         if (!isFeatureNameAnalyzable(feature))
  2073.             __testlib_fail("Feature name '" + feature + "' contains restricted characters.");
  2074.  
  2075.         if (!_features.count(feature))
  2076.             __testlib_fail("Feature " + feature + " didn't registered via addFeature(feature).");
  2077.  
  2078.         _hitFeatures.insert(feature);
  2079.     }
  2080. } validator;
  2081.  
  2082. struct TestlibFinalizeGuard
  2083. {
  2084.     static bool alive;
  2085.     int quitCount, readEofCount;
  2086.  
  2087.     TestlibFinalizeGuard() : quitCount(0), readEofCount(0)
  2088.     {
  2089.         // No operations.
  2090.     }
  2091.  
  2092.     ~TestlibFinalizeGuard()
  2093.     {
  2094.         bool _alive = alive;
  2095.         alive = false;
  2096.  
  2097.         if (_alive)
  2098.         {
  2099.             if (testlibMode == _checker && quitCount == 0)
  2100.                 __testlib_fail("Checker must end with quit or quitf call.");
  2101.  
  2102.             if (testlibMode == _validator && readEofCount == 0 && quitCount == 0)
  2103.                 __testlib_fail("Validator must end with readEof call.");
  2104.         }
  2105.  
  2106.         validator.writeTestOverviewLog();
  2107.     }
  2108. };
  2109.  
  2110. bool TestlibFinalizeGuard::alive = true;
  2111. TestlibFinalizeGuard testlibFinalizeGuard;
  2112.  
  2113. /*
  2114.  * Call it to disable checks on finalization.
  2115.  */
  2116. void disableFinalizeGuard()
  2117. {
  2118.     TestlibFinalizeGuard::alive = false;
  2119. }
  2120.  
  2121. /* Interactor streams.
  2122.  */
  2123. std::fstream tout;
  2124.  
  2125. /* implementation
  2126.  */
  2127.  
  2128. template <typename T>
  2129. static std::string vtos(const T& t)
  2130. {
  2131.     std::string s;
  2132.     std::stringstream ss;
  2133.     ss << t;
  2134.     ss >> s;
  2135.     return s;
  2136. }
  2137.  
  2138. template <typename T>
  2139. static std::string toString(const T& t)
  2140. {
  2141.     return vtos(t);
  2142. }
  2143.  
  2144. InStream::InStream()
  2145. {
  2146.     reader = NULL;
  2147.     name = "";
  2148.     mode = _input;
  2149.     strict = false;
  2150.     stdfile = false;
  2151.     wordReserveSize = 4;
  2152.     readManyIteration = NO_INDEX;
  2153. }
  2154.  
  2155. InStream::InStream(const InStream& baseStream, std::string content)
  2156. {
  2157.     reader = new StringInputStreamReader(content);
  2158.     opened = true;
  2159.     strict = baseStream.strict;
  2160.     mode = baseStream.mode;
  2161.     name = "based on " + baseStream.name;
  2162.     readManyIteration = NO_INDEX;
  2163. }
  2164.  
  2165. InStream::~InStream()
  2166. {
  2167.     if (NULL != reader)
  2168.     {
  2169.         reader->close();
  2170.         delete reader;
  2171.         reader = NULL;
  2172.     }
  2173. }
  2174.  
  2175. #ifdef __GNUC__
  2176. __attribute__((const))
  2177. #endif
  2178. int resultExitCode(TResult r)
  2179. {
  2180.     if (r == _ok)
  2181.         return OK_EXIT_CODE;
  2182.     if (r == _wa)
  2183.         return WA_EXIT_CODE;
  2184.     if (r == _pe)
  2185.         return PE_EXIT_CODE;
  2186.     if (r == _fail)
  2187.         return FAIL_EXIT_CODE;
  2188.     if (r == _dirt)
  2189.         return DIRT_EXIT_CODE;
  2190.     if (r == _points)
  2191.         return POINTS_EXIT_CODE;
  2192.     if (r == _unexpected_eof)
  2193. #ifdef ENABLE_UNEXPECTED_EOF
  2194.         return UNEXPECTED_EOF_EXIT_CODE;
  2195. #else
  2196.         return PE_EXIT_CODE;
  2197. #endif
  2198.     if (r >= _partially)
  2199.         return PC_BASE_EXIT_CODE + (r - _partially);
  2200.     return FAIL_EXIT_CODE;
  2201. }
  2202.  
  2203. void InStream::textColor(
  2204. #if !(defined(ON_WINDOWS) && (!defined(_MSC_VER) || _MSC_VER>1400)) && defined(__GNUC__)
  2205.     __attribute__((unused))
  2206. #endif
  2207.     WORD color
  2208. )
  2209. {
  2210. #if defined(ON_WINDOWS) && (!defined(_MSC_VER) || _MSC_VER>1400)
  2211.     HANDLE handle = GetStdHandle(STD_OUTPUT_HANDLE);
  2212.     SetConsoleTextAttribute(handle, color);
  2213. #endif
  2214. #if !defined(ON_WINDOWS) && defined(__CNUC__)
  2215.     if (isatty(2))
  2216.     {
  2217.         switch (color)
  2218.         {
  2219.         case LightRed:
  2220.             fprintf(stderr, "\033[1;31m");
  2221.             break;
  2222.         case LightCyan:
  2223.             fprintf(stderr, "\033[1;36m");
  2224.             break;
  2225.         case LightGreen:
  2226.             fprintf(stderr, "\033[1;32m");
  2227.             break;
  2228.         case LightYellow:
  2229.             fprintf(stderr, "\033[1;33m");
  2230.             break;
  2231.         case LightGray:
  2232.         default:
  2233.             fprintf(stderr, "\033[0m");
  2234.         }
  2235.     }
  2236. #endif
  2237. }
  2238.  
  2239. NORETURN void halt(int exitCode)
  2240. {
  2241. #ifdef FOOTER
  2242.     InStream::textColor(InStream::LightGray);
  2243.     std::fprintf(stderr, "Checker: \"%s\"\n", checkerName.c_str());
  2244.     std::fprintf(stderr, "Exit code: %d\n", exitCode);
  2245.     InStream::textColor(InStream::LightGray);
  2246. #endif
  2247.     std::exit(exitCode);
  2248. }
  2249.  
  2250. static bool __testlib_shouldCheckDirt(TResult result)
  2251. {
  2252.     return result == _ok || result == _points || result >= _partially;
  2253. }
  2254.  
  2255. NORETURN void InStream::quit(TResult result, const char* msg)
  2256. {
  2257.     if (TestlibFinalizeGuard::alive)
  2258.         testlibFinalizeGuard.quitCount++;
  2259.  
  2260. #ifndef ENABLE_UNEXPECTED_EOF
  2261.     if (result == _unexpected_eof)
  2262.         result = _pe;
  2263. #endif
  2264.  
  2265.     if (mode != _output && result != _fail)
  2266.         quits(_fail, std::string(msg) + " (" + name + ")");
  2267.  
  2268.     std::FILE * resultFile;
  2269.     std::string errorName;
  2270.    
  2271.     if (__testlib_shouldCheckDirt(result))
  2272.     {
  2273.         if (testlibMode != _interactor && !ouf.seekEof())
  2274.             quit(_dirt, "Extra information in the output file");
  2275.     }
  2276.  
  2277.     int pctype = result - _partially;
  2278.     bool isPartial = false;
  2279.  
  2280.     switch (result)
  2281.     {
  2282.     case _ok:
  2283.         errorName = "Accepted | ";
  2284.         quitscrS(LightGreen, errorName);
  2285.         break;
  2286.     case _wa:
  2287.         errorName = "Wrong Answer | ";
  2288.         quitscrS(LightRed, errorName);
  2289.         break;
  2290.     case _pe:
  2291.         errorName = "Presentation Error | ";
  2292.         quitscrS(LightRed, errorName);
  2293.         break;
  2294.     case _fail:
  2295.         errorName = "Failed | ";
  2296.         quitscrS(LightRed, errorName);
  2297.         break;
  2298.     case _dirt:
  2299.         errorName = "Presentation Error | ";
  2300.         quitscrS(LightCyan, errorName);
  2301.         result = _pe;
  2302.         break;
  2303.     case _points:
  2304.         errorName = "Partial ";
  2305.         quitscrS(LightYellow, errorName);
  2306.         break;
  2307.     case _unexpected_eof:
  2308.         errorName = "Unexpected EOF | ";
  2309.         quitscrS(LightCyan, errorName);
  2310.         break;
  2311.     default:
  2312.         if (result >= _partially)
  2313.         {
  2314.             errorName = format("partially correct (%d) ", pctype);
  2315.             isPartial = true;
  2316.             quitscrS(LightYellow, errorName);
  2317.         }
  2318.         else
  2319.             quit(_fail, "What is the code ??? ");
  2320.     }
  2321.  
  2322.     if (resultName != "")
  2323.     {
  2324.         resultFile = std::fopen(resultName.c_str(), "w");
  2325.         if (resultFile == NULL)
  2326.             quit(_fail, "Can not write to the result file");
  2327.         if (appesMode)
  2328.         {
  2329.             std::fprintf(resultFile, "<?xml version=\"1.0\" encoding=\"windows-1251\"?>");
  2330.             if (isPartial)
  2331.                 std::fprintf(resultFile, "<result outcome = \"%s\" pctype = \"%d\">", outcomes[(int)_partially].c_str(), pctype);
  2332.             else
  2333.             {
  2334.                 if (result != _points)
  2335.                     std::fprintf(resultFile, "<result outcome = \"%s\">", outcomes[(int)result].c_str());
  2336.                 else
  2337.                 {
  2338.                     if (__testlib_points == std::numeric_limits<float>::infinity())
  2339.                         quit(_fail, "Expected points, but infinity found");
  2340.                     std::string stringPoints = removeDoubleTrailingZeroes(format("%.10f", __testlib_points));
  2341.                     std::fprintf(resultFile, "<result outcome = \"%s\" points = \"%s\">", outcomes[(int)result].c_str(), stringPoints.c_str());
  2342.                 }
  2343.             }
  2344.             xmlSafeWrite(resultFile, msg);
  2345.             std::fprintf(resultFile, "</result>\n");
  2346.         }
  2347.         else
  2348.              std::fprintf(resultFile, "%s", msg);
  2349.         if (NULL == resultFile || fclose(resultFile) != 0)
  2350.             quit(_fail, "Can not write to the result file");
  2351.     }
  2352.  
  2353.     quitscr(LightGray, msg);
  2354.     std::fprintf(stderr, "\n");
  2355.  
  2356.     if (result != _points)
  2357.         std::fprintf(stdout, "%d\n", result == _ok ? 100 : 0);
  2358.     else
  2359.     {
  2360.         if (__testlib_points == std::numeric_limits<float>::infinity())
  2361.             quit(_fail, "Expected points, but infinity found");
  2362.         std::string stringPoints = removeDoubleTrailingZeroes(format("%.10f", __testlib_points));
  2363.         std::fprintf(stdout, "%s\n", stringPoints.c_str());
  2364.     }
  2365.  
  2366.     inf.close();
  2367.     ouf.close();
  2368.     ans.close();
  2369.     if (tout.is_open())
  2370.         tout.close();
  2371.  
  2372.     textColor(LightGray);
  2373.  
  2374.     if (resultName != "")
  2375.         std::fprintf(stderr, "See file to check exit message\n");
  2376.  
  2377.     halt(resultExitCode(result));
  2378. }
  2379.  
  2380. #ifdef __GNUC__
  2381.     __attribute__ ((format (printf, 3, 4)))
  2382. #endif
  2383. NORETURN void InStream::quitf(TResult result, const char* msg, ...)
  2384. {
  2385.     FMT_TO_RESULT(msg, msg, message);
  2386.     InStream::quit(result, message.c_str());
  2387. }
  2388.  
  2389. NORETURN void InStream::quits(TResult result, std::string msg)
  2390. {
  2391.     InStream::quit(result, msg.c_str());
  2392. }
  2393.  
  2394. void InStream::xmlSafeWrite(std::FILE * file, const char* msg)
  2395. {
  2396.     size_t lmsg = strlen(msg);
  2397.     for (size_t i = 0; i < lmsg; i++)
  2398.     {
  2399.         if (msg[i] == '&')
  2400.         {
  2401.             std::fprintf(file, "%s", "&amp;");
  2402.             continue;
  2403.         }
  2404.         if (msg[i] == '<')
  2405.         {
  2406.             std::fprintf(file, "%s", "&lt;");
  2407.             continue;
  2408.         }
  2409.         if (msg[i] == '>')
  2410.         {
  2411.             std::fprintf(file, "%s", "&gt;");
  2412.             continue;
  2413.         }
  2414.         if (msg[i] == '"')
  2415.         {
  2416.             std::fprintf(file, "%s", "&quot;");
  2417.             continue;
  2418.         }
  2419.         if (0 <= msg[i] && msg[i] <= 31)
  2420.         {
  2421.             std::fprintf(file, "%c", '.');
  2422.             continue;
  2423.         }
  2424.         std::fprintf(file, "%c", msg[i]);
  2425.     }
  2426. }
  2427.  
  2428. void InStream::quitscrS(WORD color, std::string msg)
  2429. {
  2430.     quitscr(color, msg.c_str());
  2431. }
  2432.  
  2433. void InStream::quitscr(WORD color, const char* msg)
  2434. {
  2435.     if (resultName == "")
  2436.     {
  2437.         textColor(color);
  2438.         std::fprintf(stderr, "%s", msg);
  2439.         textColor(LightGray);
  2440.     }
  2441. }
  2442.  
  2443. void InStream::reset(std::FILE* file)
  2444. {
  2445.     if (opened && stdfile)
  2446.         quit(_fail, "Can't reset standard handle");
  2447.  
  2448.     if (opened)
  2449.         close();
  2450.  
  2451.     if (!stdfile)
  2452.         if (NULL == (file = std::fopen(name.c_str(), "rb")))
  2453.         {
  2454.             if (mode == _output)
  2455.                 quits(_pe, std::string("Output file not found: \"") + name + "\"");
  2456.            
  2457.             if (mode == _answer)
  2458.                 quits(_fail, std::string("Answer file not found: \"") + name + "\"");
  2459.         }
  2460.  
  2461.     if (NULL != file)
  2462.     {
  2463.         opened = true;
  2464.  
  2465.         __testlib_set_binary(file);
  2466.  
  2467.         if (stdfile)
  2468.             reader = new FileInputStreamReader(file, name);
  2469.         else
  2470.             reader = new BufferedFileInputStreamReader(file, name);
  2471.     }
  2472.     else
  2473.     {
  2474.         opened = false;
  2475.         reader = NULL;
  2476.     }
  2477. }
  2478.  
  2479. void InStream::init(std::string fileName, TMode mode)
  2480. {
  2481.     opened = false;
  2482.     name = fileName;
  2483.     stdfile = false;
  2484.     this->mode = mode;
  2485.    
  2486.     reset();
  2487. }
  2488.  
  2489. void InStream::init(std::FILE* f, TMode mode)
  2490. {
  2491.     opened = false;
  2492.    
  2493.     name = "untitled";
  2494.    
  2495.     if (f == stdin)
  2496.         name = "stdin", stdfile = true;
  2497.    
  2498.     if (f == stdout)
  2499.         name = "stdout", stdfile = true;
  2500.    
  2501.     if (f == stderr)
  2502.         name = "stderr", stdfile = true;
  2503.  
  2504.     this->mode = mode;
  2505.  
  2506.     reset(f);
  2507. }
  2508.  
  2509. char InStream::curChar()
  2510. {
  2511.     return char(reader->curChar());
  2512. }
  2513.  
  2514. char InStream::nextChar()
  2515. {
  2516.     return char(reader->nextChar());
  2517. }
  2518.  
  2519. char InStream::readChar()
  2520. {
  2521.     return nextChar();
  2522. }
  2523.  
  2524. char InStream::readChar(char c)
  2525. {
  2526.     char found = readChar();
  2527.     if (c != found)
  2528.     {
  2529.         if (!isEoln(found))
  2530.             quit(_pe, ("Unexpected character '" + std::string(1, found) + "', but '" + std::string(1, c) + "' expected").c_str());
  2531.         else
  2532.             quit(_pe, ("Unexpected character " + ("#" + vtos(int(found))) + ", but '" + std::string(1, c) + "' expected").c_str());
  2533.     }
  2534.     return found;
  2535. }
  2536.  
  2537. char InStream::readSpace()
  2538. {
  2539.     return readChar(' ');
  2540. }
  2541.  
  2542. void InStream::unreadChar(char c)
  2543. {
  2544.     reader->unreadChar(c);
  2545. }
  2546.  
  2547. void InStream::skipChar()
  2548. {
  2549.     reader->skipChar();
  2550. }
  2551.  
  2552. void InStream::skipBlanks()
  2553. {
  2554.     while (isBlanks(reader->curChar()))
  2555.         reader->skipChar();
  2556. }
  2557.  
  2558. std::string InStream::readWord()
  2559. {
  2560.     readWordTo(_tmpReadToken);
  2561.     return _tmpReadToken;
  2562. }
  2563.  
  2564. void InStream::readWordTo(std::string& result)
  2565. {
  2566.     if (!strict)
  2567.         skipBlanks();
  2568.  
  2569.     int cur = reader->nextChar();
  2570.  
  2571.     if (cur == EOFC)
  2572.         quit(_unexpected_eof, "Unexpected end of file - token expected");
  2573.  
  2574.     if (isBlanks(cur))
  2575.         quit(_pe, "Unexpected white-space - token expected");
  2576.  
  2577.     result.clear();
  2578.  
  2579.     while (!(isBlanks(cur) || cur == EOFC))
  2580.     {
  2581.         result += char(cur);
  2582.         cur = reader->nextChar();
  2583.     }
  2584.  
  2585.     reader->unreadChar(cur);
  2586.  
  2587.     if (result.length() == 0)
  2588.         quit(_unexpected_eof, "Unexpected end of file or white-space - token expected");
  2589. }
  2590.  
  2591. std::string InStream::readToken()
  2592. {
  2593.     return readWord();
  2594. }
  2595.  
  2596. void InStream::readTokenTo(std::string& result)
  2597. {
  2598.     readWordTo(result);
  2599. }
  2600.  
  2601. static std::string __testlib_part(const std::string& s)
  2602. {
  2603.     if (s.length() <= 64)
  2604.         return s;
  2605.     else
  2606.         return s.substr(0, 30) + "..." + s.substr(s.length() - 31, 31);
  2607. }
  2608.  
  2609. #define __testlib_readMany(readMany, readOne, typeName, space)                  \
  2610.     if (size < 0)                                                               \
  2611.         quit(_fail, #readMany ": size should be non-negative.");                \
  2612.     if (size > 100000000)                                                       \
  2613.         quit(_fail, #readMany ": size should be at most 100000000.");           \
  2614.                                                                                 \
  2615.     std::vector<typeName> result(size);                                         \
  2616.     readManyIteration = indexBase;                                              \
  2617.                                                                                 \
  2618.     for (int i = 0; i < size; i++)                                              \
  2619.     {                                                                           \
  2620.         result[i] = readOne;                                                    \
  2621.         readManyIteration++;                                                    \
  2622.         if (space && i + 1 < size)                                              \
  2623.             readSpace();                                                        \
  2624.     }                                                                           \
  2625.                                                                                 \
  2626.     readManyIteration = NO_INDEX;                                               \
  2627.     return result;                                                              \
  2628.  
  2629. std::string InStream::readWord(const pattern& p, const std::string& variableName)
  2630. {
  2631.     readWordTo(_tmpReadToken);
  2632.     if (!p.matches(_tmpReadToken))
  2633.     {
  2634.         if (readManyIteration == NO_INDEX)
  2635.         {
  2636.             if (variableName.empty())
  2637.                 quit(_wa, ("Token \"" + __testlib_part(_tmpReadToken) + "\" doesn't correspond to pattern \"" + p.src() + "\"").c_str());
  2638.             else
  2639.                 quit(_wa, ("Token parameter [name=" + variableName + "] equals to \"" + __testlib_part(_tmpReadToken) + "\", doesn't correspond to pattern \"" + p.src() + "\"").c_str());
  2640.         }
  2641.         else
  2642.         {
  2643.             if (variableName.empty())
  2644.                 quit(_wa, ("Token element [index=" + vtos(readManyIteration) + "] equals to \"" + __testlib_part(_tmpReadToken) + "\" doesn't correspond to pattern \"" + p.src() + "\"").c_str());
  2645.             else
  2646.                 quit(_wa, ("Token element " + variableName + "[" + vtos(readManyIteration) + "] equals to \"" + __testlib_part(_tmpReadToken) + "\", doesn't correspond to pattern \"" + p.src() + "\"").c_str());
  2647.         }
  2648.     }
  2649.     return _tmpReadToken;
  2650. }
  2651.  
  2652. std::vector<std::string> InStream::readWords(int size, const pattern& p, const std::string& variablesName, int indexBase)
  2653. {
  2654.     __testlib_readMany(readWords, readWord(p, variablesName), std::string, true);
  2655. }
  2656.  
  2657. std::string InStream::readWord(const std::string& ptrn, const std::string& variableName)
  2658. {
  2659.     return readWord(pattern(ptrn), variableName);
  2660. }
  2661.  
  2662. std::vector<std::string> InStream::readWords(int size, const std::string& ptrn, const std::string& variablesName, int indexBase)
  2663. {
  2664.     pattern p(ptrn);
  2665.     __testlib_readMany(readWords, readWord(p, variablesName), std::string, true);
  2666. }
  2667.  
  2668. std::string InStream::readToken(const pattern& p, const std::string& variableName)
  2669. {
  2670.     return readWord(p, variableName);
  2671. }
  2672.  
  2673. std::vector<std::string> InStream::readTokens(int size, const pattern& p, const std::string& variablesName, int indexBase)
  2674. {
  2675.     __testlib_readMany(readTokens, readToken(p, variablesName), std::string, true);
  2676. }
  2677.  
  2678. std::string InStream::readToken(const std::string& ptrn, const std::string& variableName)
  2679. {
  2680.     return readWord(ptrn, variableName);
  2681. }
  2682.  
  2683. std::vector<std::string> InStream::readTokens(int size, const std::string& ptrn, const std::string& variablesName, int indexBase)
  2684. {
  2685.     pattern p(ptrn);
  2686.     __testlib_readMany(readTokens, readWord(p, variablesName), std::string, true);
  2687. }
  2688.  
  2689. void InStream::readWordTo(std::string& result, const pattern& p, const std::string& variableName)
  2690. {
  2691.     readWordTo(result);
  2692.     if (!p.matches(result))
  2693.     {
  2694.         if (variableName.empty())
  2695.             quit(_wa, ("Token \"" + __testlib_part(result) + "\" doesn't correspond to pattern \"" + p.src() + "\"").c_str());
  2696.         else
  2697.             quit(_wa, ("Token parameter [name=" + variableName + "] equals to \"" + __testlib_part(result) + "\", doesn't correspond to pattern \"" + p.src() + "\"").c_str());
  2698.     }
  2699. }
  2700.  
  2701. void InStream::readWordTo(std::string& result, const std::string& ptrn, const std::string& variableName)
  2702. {
  2703.     return readWordTo(result, pattern(ptrn), variableName);
  2704. }
  2705.  
  2706. void InStream::readTokenTo(std::string& result, const pattern& p, const std::string& variableName)
  2707. {
  2708.     return readWordTo(result, p, variableName);
  2709. }
  2710.  
  2711. void InStream::readTokenTo(std::string& result, const std::string& ptrn, const std::string& variableName)
  2712. {
  2713.     return readWordTo(result, ptrn, variableName);
  2714. }
  2715.  
  2716. #ifdef __GNUC__
  2717. __attribute__((pure))
  2718. #endif
  2719. static inline bool equals(long long integer, const char* s)
  2720. {
  2721.     if (integer == LLONG_MIN)
  2722.         return strcmp(s, "-9223372036854775808") == 0;
  2723.  
  2724.     if (integer == 0LL)
  2725.         return strcmp(s, "0") == 0;
  2726.  
  2727.     size_t length = strlen(s);
  2728.  
  2729.     if (length == 0)
  2730.         return false;
  2731.  
  2732.     if (integer < 0 && s[0] != '-')
  2733.         return false;
  2734.  
  2735.     if (integer < 0)
  2736.         s++, length--, integer = -integer;
  2737.  
  2738.     if (length == 0)
  2739.         return false;
  2740.  
  2741.     while (integer > 0)
  2742.     {
  2743.         int digit = int(integer % 10);
  2744.  
  2745.         if (s[length - 1] != '0' + digit)
  2746.             return false;
  2747.  
  2748.         length--;
  2749.         integer /= 10;
  2750.     }
  2751.  
  2752.     return length == 0;
  2753. }
  2754.  
  2755. #ifdef __GNUC__
  2756. __attribute__((pure))
  2757. #endif
  2758. static inline bool equals(unsigned long long integer, const char* s)
  2759. {
  2760.     if (integer == ULLONG_MAX)
  2761.         return strcmp(s, "18446744073709551615") == 0;
  2762.  
  2763.     if (integer == 0ULL)
  2764.         return strcmp(s, "0") == 0;
  2765.  
  2766.     size_t length = strlen(s);
  2767.  
  2768.     if (length == 0)
  2769.         return false;
  2770.  
  2771.     while (integer > 0)
  2772.     {
  2773.         int digit = int(integer % 10);
  2774.  
  2775.         if (s[length - 1] != '0' + digit)
  2776.             return false;
  2777.  
  2778.         length--;
  2779.         integer /= 10;
  2780.     }
  2781.  
  2782.     return length == 0;
  2783. }
  2784.  
  2785. static inline double stringToDouble(InStream& in, const char* buffer)
  2786. {
  2787.     double retval;
  2788.  
  2789.     size_t length = strlen(buffer);
  2790.  
  2791.     int minusCount = 0;
  2792.     int plusCount = 0;
  2793.     int decimalPointCount = 0;
  2794.     int digitCount = 0;
  2795.     int eCount = 0;
  2796.  
  2797.     for (size_t i = 0; i < length; i++)
  2798.     {
  2799.         if (('0' <= buffer[i] && buffer[i] <= '9') || buffer[i] == '.'
  2800.                 || buffer[i] == 'e' || buffer[i] == 'E'
  2801.                 || buffer[i] == '-' || buffer[i] == '+')
  2802.         {
  2803.             if ('0' <= buffer[i] && buffer[i] <= '9')
  2804.                 digitCount++;
  2805.             if (buffer[i] == 'e' || buffer[i] == 'E')
  2806.                 eCount++;
  2807.             if (buffer[i] == '-')
  2808.                 minusCount++;
  2809.             if (buffer[i] == '+')
  2810.                 plusCount++;
  2811.             if (buffer[i] == '.')
  2812.                 decimalPointCount++;
  2813.         }
  2814.         else
  2815.             in.quit(_pe, ("Expected double, but \"" + __testlib_part(buffer) + "\" found").c_str());
  2816.     }
  2817.  
  2818.     // If for sure is not a number in standard notation or in e-notation.
  2819.     if (digitCount == 0 || minusCount > 2 || plusCount > 2 || decimalPointCount > 1 || eCount > 1)
  2820.         in.quit(_pe, ("Expected double, but \"" + __testlib_part(buffer) + "\" found").c_str());
  2821.  
  2822.     char* suffix = new char[length + 1];
  2823.     int scanned = std::sscanf(buffer, "%lf%s", &retval, suffix);
  2824.     bool empty = strlen(suffix) == 0;
  2825.     delete[] suffix;
  2826.  
  2827.     if (scanned == 1 || (scanned == 2 && empty))
  2828.     {
  2829.         if (__testlib_isNaN(retval))
  2830.             in.quit(_pe, ("Expected double, but \"" + __testlib_part(buffer) + "\" found").c_str());
  2831.         return retval;
  2832.     }
  2833.     else
  2834.         in.quit(_pe, ("Expected double, but \"" + __testlib_part(buffer) + "\" found").c_str());
  2835. }
  2836.  
  2837. static inline double stringToStrictDouble(InStream& in, const char* buffer, int minAfterPointDigitCount, int maxAfterPointDigitCount)
  2838. {
  2839.     if (minAfterPointDigitCount < 0)
  2840.         in.quit(_fail, "stringToStrictDouble: minAfterPointDigitCount should be non-negative.");
  2841.    
  2842.     if (minAfterPointDigitCount > maxAfterPointDigitCount)
  2843.         in.quit(_fail, "stringToStrictDouble: minAfterPointDigitCount should be less or equal to maxAfterPointDigitCount.");
  2844.  
  2845.     double retval;
  2846.  
  2847.     size_t length = strlen(buffer);
  2848.  
  2849.     if (length == 0 || length > 1000)
  2850.         in.quit(_pe, ("Expected strict double, but \"" + __testlib_part(buffer) + "\" found").c_str());
  2851.  
  2852.     if (buffer[0] != '-' && (buffer[0] < '0' || buffer[0] > '9'))
  2853.         in.quit(_pe, ("Expected strict double, but \"" + __testlib_part(buffer) + "\" found").c_str());
  2854.  
  2855.     int pointPos = -1;
  2856.     for (size_t i = 1; i + 1 < length; i++)
  2857.     {
  2858.         if (buffer[i] == '.')
  2859.         {
  2860.             if (pointPos > -1)
  2861.                 in.quit(_pe, ("Expected strict double, but \"" + __testlib_part(buffer) + "\" found").c_str());
  2862.             pointPos = int(i);
  2863.         }
  2864.         if (buffer[i] != '.' && (buffer[i] < '0' || buffer[i] > '9'))
  2865.             in.quit(_pe, ("Expected strict double, but \"" + __testlib_part(buffer) + "\" found").c_str());
  2866.     }
  2867.  
  2868.     if (buffer[length - 1] < '0' || buffer[length - 1] > '9')
  2869.         in.quit(_pe, ("Expected strict double, but \"" + __testlib_part(buffer) + "\" found").c_str());
  2870.  
  2871.     int afterDigitsCount = (pointPos == -1 ? 0 : int(length) - pointPos - 1);
  2872.     if (afterDigitsCount < minAfterPointDigitCount || afterDigitsCount > maxAfterPointDigitCount)
  2873.         in.quit(_pe, ("Expected strict double with number of digits after point in range ["
  2874.             + vtos(minAfterPointDigitCount)
  2875.             + ","
  2876.             + vtos(maxAfterPointDigitCount)
  2877.             + "], but \"" + __testlib_part(buffer) + "\" found").c_str()
  2878.         );
  2879.  
  2880.     int firstDigitPos = -1;
  2881.     for (size_t i = 0; i < length; i++)
  2882.         if (buffer[i] >= '0' && buffer[i] <= '9')
  2883.         {
  2884.             firstDigitPos = int(i);
  2885.             break;
  2886.         }
  2887.  
  2888.     if (firstDigitPos > 1 || firstDigitPos == -1)
  2889.         in.quit(_pe, ("Expected strict double, but \"" + __testlib_part(buffer) + "\" found").c_str());
  2890.  
  2891.     if (buffer[firstDigitPos] == '0' && firstDigitPos + 1 < int(length)
  2892.             && buffer[firstDigitPos + 1] >= '0' && buffer[firstDigitPos + 1] <= '9')
  2893.         in.quit(_pe, ("Expected strict double, but \"" + __testlib_part(buffer) + "\" found").c_str());
  2894.  
  2895.     char* suffix = new char[length + 1];
  2896.     int scanned = std::sscanf(buffer, "%lf%s", &retval, suffix);
  2897.     bool empty = strlen(suffix) == 0;
  2898.     delete[] suffix;
  2899.  
  2900.     if (scanned == 1 || (scanned == 2 && empty))
  2901.     {
  2902.         if (__testlib_isNaN(retval) || __testlib_isInfinite(retval))
  2903.             in.quit(_pe, ("Expected double, but \"" + __testlib_part(buffer) + "\" found").c_str());
  2904.         return retval;
  2905.     }
  2906.     else
  2907.         in.quit(_pe, ("Expected double, but \"" + __testlib_part(buffer) + "\" found").c_str());
  2908. }
  2909.  
  2910. static inline long long stringToLongLong(InStream& in, const char* buffer)
  2911. {
  2912.     if (strcmp(buffer, "-9223372036854775808") == 0)
  2913.         return LLONG_MIN;
  2914.  
  2915.     bool minus = false;
  2916.     size_t length = strlen(buffer);
  2917.    
  2918.     if (length > 1 && buffer[0] == '-')
  2919.         minus = true;
  2920.  
  2921.     if (length > 20)
  2922.         in.quit(_pe, ("Expected integer, but \"" + __testlib_part(buffer) + "\" found").c_str());
  2923.  
  2924.     long long retval = 0LL;
  2925.  
  2926.     int zeroes = 0;
  2927.     int processingZeroes = true;
  2928.    
  2929.     for (int i = (minus ? 1 : 0); i < int(length); i++)
  2930.     {
  2931.         if (buffer[i] == '0' && processingZeroes)
  2932.             zeroes++;
  2933.         else
  2934.             processingZeroes = false;
  2935.  
  2936.         if (buffer[i] < '0' || buffer[i] > '9')
  2937.             in.quit(_pe, ("Expected integer, but \"" + __testlib_part(buffer) + "\" found").c_str());
  2938.         retval = retval * 10 + (buffer[i] - '0');
  2939.     }
  2940.  
  2941.     if (retval < 0)
  2942.         in.quit(_pe, ("Expected integer, but \"" + __testlib_part(buffer) + "\" found").c_str());
  2943.    
  2944.     if ((zeroes > 0 && (retval != 0 || minus)) || zeroes > 1)
  2945.         in.quit(_pe, ("Expected integer, but \"" + __testlib_part(buffer) + "\" found").c_str());
  2946.  
  2947.     retval = (minus ? -retval : +retval);
  2948.  
  2949.     if (length < 19)
  2950.         return retval;
  2951.  
  2952.     if (equals(retval, buffer))
  2953.         return retval;
  2954.     else
  2955.         in.quit(_pe, ("Expected int64, but \"" + __testlib_part(buffer) + "\" found").c_str());
  2956. }
  2957.  
  2958. static inline unsigned long long stringToUnsignedLongLong(InStream& in, const char* buffer)
  2959. {
  2960.     size_t length = strlen(buffer);
  2961.  
  2962.     if (length > 20)
  2963.         in.quit(_pe, ("Expected unsigned integer, but \"" + __testlib_part(buffer) + "\" found").c_str());
  2964.     if (length > 1 && buffer[0] == '0')
  2965.         in.quit(_pe, ("Expected unsigned integer, but \"" + __testlib_part(buffer) + "\" found").c_str());
  2966.  
  2967.     unsigned long long retval = 0LL;
  2968.     for (int i = 0; i < int(length); i++)
  2969.     {
  2970.         if (buffer[i] < '0' || buffer[i] > '9')
  2971.             in.quit(_pe, ("Expected unsigned integer, but \"" + __testlib_part(buffer) + "\" found").c_str());
  2972.         retval = retval * 10 + (buffer[i] - '0');
  2973.     }
  2974.  
  2975.     if (length < 19)
  2976.         return retval;
  2977.  
  2978.     if (length == 20 && strcmp(buffer, "18446744073709551615") == 1)
  2979.         in.quit(_pe, ("Expected unsigned int64, but \"" + __testlib_part(buffer) + "\" found").c_str());
  2980.  
  2981.     if (equals(retval, buffer))
  2982.         return retval;
  2983.     else
  2984.         in.quit(_pe, ("Expected unsigned int64, but \"" + __testlib_part(buffer) + "\" found").c_str());
  2985. }
  2986.  
  2987. int InStream::readInteger()
  2988. {
  2989.     if (!strict && seekEof())
  2990.         quit(_unexpected_eof, "Unexpected end of file - int32 expected");
  2991.  
  2992.     readWordTo(_tmpReadToken);
  2993.    
  2994.     long long value = stringToLongLong(*this, _tmpReadToken.c_str());
  2995.     if (value < INT_MIN || value > INT_MAX)
  2996.         quit(_pe, ("Expected int32, but \"" + __testlib_part(_tmpReadToken) + "\" found").c_str());
  2997.    
  2998.     return int(value);
  2999. }
  3000.  
  3001. long long InStream::readLong()
  3002. {
  3003.     if (!strict && seekEof())
  3004.         quit(_unexpected_eof, "Unexpected end of file - int64 expected");
  3005.  
  3006.     readWordTo(_tmpReadToken);
  3007.  
  3008.     return stringToLongLong(*this, _tmpReadToken.c_str());
  3009. }
  3010.  
  3011. unsigned long long InStream::readUnsignedLong()
  3012. {
  3013.     if (!strict && seekEof())
  3014.         quit(_unexpected_eof, "Unexpected end of file - int64 expected");
  3015.  
  3016.     readWordTo(_tmpReadToken);
  3017.  
  3018.     return stringToUnsignedLongLong(*this, _tmpReadToken.c_str());
  3019. }
  3020.  
  3021. long long InStream::readLong(long long minv, long long maxv, const std::string& variableName)
  3022. {
  3023.     long long result = readLong();
  3024.  
  3025.     if (result < minv || result > maxv)
  3026.     {
  3027.         if (readManyIteration == NO_INDEX)
  3028.         {
  3029.             if (variableName.empty())
  3030.                 quit(_wa, ("Integer " + vtos(result) + " violates the range [" + vtos(minv) + ", " + vtos(maxv) + "]").c_str());
  3031.             else
  3032.                 quit(_wa, ("Integer parameter [name=" + std::string(variableName) + "] equals to " + vtos(result) + ", violates the range [" + vtos(minv) + ", " + vtos(maxv) + "]").c_str());
  3033.         }
  3034.         else
  3035.         {
  3036.             if (variableName.empty())
  3037.                 quit(_wa, ("Integer element [index=" + vtos(readManyIteration) + "] equals to " + vtos(result) + ", violates the range [" + vtos(minv) + ", " + vtos(maxv) + "]").c_str());
  3038.             else
  3039.                 quit(_wa, ("Integer element " + std::string(variableName) + "[" + vtos(readManyIteration) + "] equals to " + vtos(result) + ", violates the range [" + vtos(minv) + ", " + vtos(maxv) + "]").c_str());
  3040.         }
  3041.     }
  3042.  
  3043.     if (strict && !variableName.empty())
  3044.         validator.addBoundsHit(variableName, ValidatorBoundsHit(minv == result, maxv == result));
  3045.  
  3046.     return result;
  3047. }
  3048.  
  3049. std::vector<long long> InStream::readLongs(int size, long long minv, long long maxv, const std::string& variablesName, int indexBase)
  3050. {
  3051.     __testlib_readMany(readLongs, readLong(minv, maxv, variablesName), long long, true)
  3052. }
  3053.  
  3054. unsigned long long InStream::readUnsignedLong(unsigned long long minv, unsigned long long maxv, const std::string& variableName)
  3055. {
  3056.     unsigned long long result = readUnsignedLong();
  3057.  
  3058.     if (result < minv || result > maxv)
  3059.     {
  3060.         if (readManyIteration == NO_INDEX)
  3061.         {
  3062.             if (variableName.empty())
  3063.                 quit(_wa, ("Unsigned integer " + vtos(result) + " violates the range [" + vtos(minv) + ", " + vtos(maxv) + "]").c_str());
  3064.             else
  3065.                 quit(_wa, ("Unsigned integer parameter [name=" + std::string(variableName) + "] equals to " + vtos(result) + ", violates the range [" + vtos(minv) + ", " + vtos(maxv) + "]").c_str());
  3066.         }
  3067.         else
  3068.         {
  3069.             if (variableName.empty())
  3070.                 quit(_wa, ("Unsigned integer element [index=" + vtos(readManyIteration) + "] equals to " + vtos(result) + ", violates the range [" + vtos(minv) + ", " + vtos(maxv) + "]").c_str());
  3071.             else
  3072.                 quit(_wa, ("Unsigned integer element " + std::string(variableName) + "[" + vtos(readManyIteration) + "] equals to " + vtos(result) + ", violates the range [" + vtos(minv) + ", " + vtos(maxv) + "]").c_str());
  3073.         }
  3074.     }
  3075.  
  3076.     if (strict && !variableName.empty())
  3077.         validator.addBoundsHit(variableName, ValidatorBoundsHit(minv == result, maxv == result));
  3078.  
  3079.     return result;
  3080. }
  3081.  
  3082. std::vector<unsigned long long> InStream::readUnsignedLongs(int size, unsigned long long minv, unsigned long long maxv, const std::string& variablesName, int indexBase)
  3083. {
  3084.     __testlib_readMany(readUnsignedLongs, readUnsignedLong(minv, maxv, variablesName), unsigned long long, true)
  3085. }
  3086.  
  3087. unsigned long long InStream::readLong(unsigned long long minv, unsigned long long maxv, const std::string& variableName)
  3088. {
  3089.     return readUnsignedLong(minv, maxv, variableName);
  3090. }
  3091.  
  3092. int InStream::readInt()
  3093. {
  3094.     return readInteger();
  3095. }
  3096.  
  3097. int InStream::readInt(int minv, int maxv, const std::string& variableName)
  3098. {
  3099.     int result = readInt();
  3100.  
  3101.     if (result < minv || result > maxv)
  3102.     {
  3103.         if (readManyIteration == NO_INDEX)
  3104.         {
  3105.             if (variableName.empty())
  3106.                 quit(_wa, ("Integer " + vtos(result) + " violates the range [" + vtos(minv) + ", " + vtos(maxv) + "]").c_str());
  3107.             else
  3108.                 quit(_wa, ("Integer parameter [name=" + std::string(variableName) + "] equals to " + vtos(result) + ", violates the range [" + vtos(minv) + ", " + vtos(maxv) + "]").c_str());
  3109.         }
  3110.         else
  3111.         {
  3112.             if (variableName.empty())
  3113.                 quit(_wa, ("Integer element [index=" + vtos(readManyIteration) + "] equals to " + vtos(result) + ", violates the range [" + vtos(minv) + ", " + vtos(maxv) + "]").c_str());
  3114.             else
  3115.                 quit(_wa, ("Integer element " + std::string(variableName) + "[" + vtos(readManyIteration) + "] equals to " + vtos(result) + ", violates the range [" + vtos(minv) + ", " + vtos(maxv) + "]").c_str());
  3116.         }
  3117.     }
  3118.  
  3119.     if (strict && !variableName.empty())
  3120.         validator.addBoundsHit(variableName, ValidatorBoundsHit(minv == result, maxv == result));
  3121.  
  3122.     return result;
  3123. }
  3124.  
  3125. int InStream::readInteger(int minv, int maxv, const std::string& variableName)
  3126. {
  3127.     return readInt(minv, maxv, variableName);
  3128. }
  3129.  
  3130. std::vector<int> InStream::readInts(int size, int minv, int maxv, const std::string& variablesName, int indexBase)
  3131. {
  3132.     __testlib_readMany(readInts, readInt(minv, maxv, variablesName), int, true)
  3133. }
  3134.  
  3135. std::vector<int> InStream::readIntegers(int size, int minv, int maxv, const std::string& variablesName, int indexBase)
  3136. {
  3137.     __testlib_readMany(readIntegers, readInt(minv, maxv, variablesName), int, true)
  3138. }
  3139.  
  3140. double InStream::readReal()
  3141. {
  3142.     if (!strict && seekEof())
  3143.         quit(_unexpected_eof, "Unexpected end of file - double expected");
  3144.  
  3145.     return stringToDouble(*this, readWord().c_str());
  3146. }
  3147.  
  3148. double InStream::readDouble()
  3149. {
  3150.     return readReal();
  3151. }
  3152.  
  3153. double InStream::readReal(double minv, double maxv, const std::string& variableName)
  3154. {
  3155.     double result = readReal();
  3156.  
  3157.     if (result < minv || result > maxv)
  3158.     {
  3159.         if (readManyIteration == NO_INDEX)
  3160.         {
  3161.             if (variableName.empty())
  3162.                 quit(_wa, ("Double " + vtos(result) + " violates the range [" + vtos(minv) + ", " + vtos(maxv) + "]").c_str());
  3163.             else
  3164.                 quit(_wa, ("Double parameter [name=" + std::string(variableName) + "] equals to " + vtos(result) + ", violates the range [" + vtos(minv) + ", " + vtos(maxv) + "]").c_str());
  3165.         }
  3166.         else
  3167.         {
  3168.             if (variableName.empty())
  3169.                 quit(_wa, ("Double element [index=" + vtos(readManyIteration) + "] equals to " + vtos(result) + ", violates the range [" + vtos(minv) + ", " + vtos(maxv) + "]").c_str());
  3170.             else
  3171.                 quit(_wa, ("Double element " + std::string(variableName) + "[" + vtos(readManyIteration) + "] equals to " + vtos(result) + ", violates the range [" + vtos(minv) + ", " + vtos(maxv) + "]").c_str());
  3172.         }
  3173.     }
  3174.  
  3175.     if (strict && !variableName.empty())
  3176.         validator.addBoundsHit(variableName, ValidatorBoundsHit(
  3177.             doubleDelta(minv, result) < ValidatorBoundsHit::EPS,
  3178.             doubleDelta(maxv, result) < ValidatorBoundsHit::EPS
  3179.         ));
  3180.  
  3181.     return result;
  3182. }
  3183.  
  3184. std::vector<double> InStream::readReals(int size, double minv, double maxv, const std::string& variablesName, int indexBase)
  3185. {
  3186.     __testlib_readMany(readReals, readReal(minv, maxv, variablesName), double, true)
  3187. }
  3188.  
  3189. double InStream::readDouble(double minv, double maxv, const std::string& variableName)
  3190. {
  3191.     return readReal(minv, maxv, variableName);
  3192. }                                          
  3193.  
  3194. std::vector<double> InStream::readDoubles(int size, double minv, double maxv, const std::string& variablesName, int indexBase)
  3195. {
  3196.     __testlib_readMany(readDoubles, readDouble(minv, maxv, variablesName), double, true)
  3197. }
  3198.  
  3199. double InStream::readStrictReal(double minv, double maxv,
  3200.         int minAfterPointDigitCount, int maxAfterPointDigitCount,
  3201.         const std::string& variableName)
  3202. {
  3203.     if (!strict && seekEof())
  3204.         quit(_unexpected_eof, "Unexpected end of file - strict double expected");
  3205.  
  3206.     double result = stringToStrictDouble(*this, readWord().c_str(),
  3207.             minAfterPointDigitCount, maxAfterPointDigitCount);
  3208.  
  3209.     if (result < minv || result > maxv)
  3210.     {
  3211.         if (readManyIteration == NO_INDEX)
  3212.         {
  3213.             if (variableName.empty())
  3214.                 quit(_wa, ("Strict double " + vtos(result) + " violates the range [" + vtos(minv) + ", " + vtos(maxv) + "]").c_str());
  3215.             else
  3216.                 quit(_wa, ("Strict double parameter [name=" + std::string(variableName) + "] equals to " + vtos(result) + ", violates the range [" + vtos(minv) + ", " + vtos(maxv) + "]").c_str());
  3217.         }
  3218.         else
  3219.         {
  3220.             if (variableName.empty())
  3221.                 quit(_wa, ("Strict double element [index=" + vtos(readManyIteration) + "] equals to " + vtos(result) + ", violates the range [" + vtos(minv) + ", " + vtos(maxv) + "]").c_str());
  3222.             else
  3223.                 quit(_wa, ("Strict double element " + std::string(variableName) + "[" + vtos(readManyIteration) + "] equals to " + vtos(result) + ", violates the range [" + vtos(minv) + ", " + vtos(maxv) + "]").c_str());
  3224.         }
  3225.     }
  3226.  
  3227.     if (strict && !variableName.empty())
  3228.         validator.addBoundsHit(variableName, ValidatorBoundsHit(
  3229.             doubleDelta(minv, result) < ValidatorBoundsHit::EPS,
  3230.             doubleDelta(maxv, result) < ValidatorBoundsHit::EPS
  3231.         ));
  3232.  
  3233.     return result;
  3234. }
  3235.  
  3236. std::vector<double> InStream::readStrictReals(int size, double minv, double maxv,
  3237.         int minAfterPointDigitCount, int maxAfterPointDigitCount,
  3238.         const std::string& variablesName, int indexBase)
  3239. {
  3240.     __testlib_readMany(readStrictReals, readStrictReal(minv, maxv, minAfterPointDigitCount, maxAfterPointDigitCount, variablesName), double, true)
  3241. }
  3242.  
  3243. double InStream::readStrictDouble(double minv, double maxv,
  3244.         int minAfterPointDigitCount, int maxAfterPointDigitCount,
  3245.         const std::string& variableName)
  3246. {
  3247.     return readStrictReal(minv, maxv,
  3248.             minAfterPointDigitCount, maxAfterPointDigitCount,
  3249.             variableName);
  3250. }
  3251.  
  3252. std::vector<double> InStream::readStrictDoubles(int size, double minv, double maxv,
  3253.         int minAfterPointDigitCount, int maxAfterPointDigitCount,
  3254.         const std::string& variablesName, int indexBase)
  3255. {
  3256.     __testlib_readMany(readStrictDoubles, readStrictDouble(minv, maxv, minAfterPointDigitCount, maxAfterPointDigitCount, variablesName), double, true)
  3257. }
  3258.  
  3259. bool InStream::eof()
  3260. {
  3261.     if (!strict && NULL == reader)
  3262.         return true;
  3263.  
  3264.     return reader->eof();
  3265. }
  3266.  
  3267. bool InStream::seekEof()
  3268. {
  3269.     if (!strict && NULL == reader)
  3270.         return true;
  3271.     skipBlanks();
  3272.     return eof();
  3273. }
  3274.  
  3275. bool InStream::eoln()
  3276. {
  3277.     if (!strict && NULL == reader)
  3278.         return true;
  3279.  
  3280.     int c = reader->nextChar();
  3281.  
  3282.     if (!strict)
  3283.     {
  3284.         if (c == EOFC)
  3285.             return true;
  3286.  
  3287.         if (c == CR)
  3288.         {
  3289.             c = reader->nextChar();
  3290.  
  3291.             if (c != LF)
  3292.             {
  3293.                 reader->unreadChar(c);
  3294.                 reader->unreadChar(CR);
  3295.                 return false;
  3296.             }
  3297.             else
  3298.                 return true;
  3299.         }
  3300.        
  3301.         if (c == LF)
  3302.             return true;
  3303.  
  3304.         reader->unreadChar(c);
  3305.         return false;
  3306.     }
  3307.     else
  3308.     {
  3309.         bool returnCr = false;
  3310.  
  3311. #ifdef ON_WINDOWS
  3312.         if (c != CR)
  3313.         {
  3314.             reader->unreadChar(c);
  3315.             return false;
  3316.         }
  3317.         else
  3318.         {
  3319.             if (!returnCr)
  3320.                 returnCr = true;
  3321.             c = reader->nextChar();
  3322.         }
  3323. #endif        
  3324.         if (c != LF)
  3325.         {
  3326.             reader->unreadChar(c);
  3327.             if (returnCr)
  3328.                 reader->unreadChar(CR);
  3329.             return false;
  3330.         }
  3331.  
  3332.         return true;
  3333.     }
  3334. }
  3335.  
  3336. void InStream::readEoln()
  3337. {
  3338.     if (!eoln())
  3339.         quit(_pe, "Expected EOLN");
  3340. }
  3341.  
  3342. void InStream::readEof()
  3343. {
  3344.     if (!eof())
  3345.         quit(_pe, "Expected EOF");
  3346.  
  3347.     if (TestlibFinalizeGuard::alive && this == &inf)
  3348.         testlibFinalizeGuard.readEofCount++;
  3349. }
  3350.  
  3351. bool InStream::seekEoln()
  3352. {
  3353.     if (!strict && NULL == reader)
  3354.         return true;
  3355.    
  3356.     int cur;
  3357.     do
  3358.     {
  3359.         cur = reader->nextChar();
  3360.     }
  3361.     while (cur == SPACE || cur == TAB);
  3362.  
  3363.     reader->unreadChar(cur);
  3364.     return eoln();
  3365. }
  3366.  
  3367. void InStream::nextLine()
  3368. {
  3369.     readLine();
  3370. }
  3371.  
  3372. void InStream::readStringTo(std::string& result)
  3373. {
  3374.     if (NULL == reader)
  3375.         quit(_pe, "Expected line");
  3376.  
  3377.     result.clear();
  3378.     int cur;
  3379.  
  3380.     for (;;)
  3381.     {
  3382.         cur = reader->curChar();
  3383.  
  3384.         if (isEoln(cur))
  3385.             break;
  3386.  
  3387.         if (cur == EOFC)
  3388.             break;
  3389.  
  3390.         result += char(reader->nextChar());
  3391.     }
  3392.  
  3393.     if (strict)
  3394.         readEoln();
  3395.     else
  3396.         eoln();
  3397. }
  3398.  
  3399. std::string InStream::readString()
  3400. {
  3401.     readStringTo(_tmpReadToken);
  3402.     return _tmpReadToken;
  3403. }
  3404.  
  3405. std::vector<std::string> InStream::readStrings(int size, int indexBase)
  3406. {
  3407.     __testlib_readMany(readStrings, readString(), std::string, false)
  3408. }
  3409.  
  3410. void InStream::readStringTo(std::string& result, const pattern& p, const std::string& variableName)
  3411. {
  3412.     readStringTo(result);
  3413.     if (!p.matches(result))
  3414.     {
  3415.         if (readManyIteration == NO_INDEX)
  3416.         {
  3417.             if (variableName.empty())
  3418.                 quit(_wa, ("Line \"" + __testlib_part(result) + "\" doesn't correspond to pattern \"" + p.src() + "\"").c_str());
  3419.             else
  3420.                 quit(_wa, ("Line [name=" + variableName + "] equals to \"" + __testlib_part(result) + "\", doesn't correspond to pattern \"" + p.src() + "\"").c_str());
  3421.         }
  3422.         else
  3423.         {
  3424.             if (variableName.empty())
  3425.                 quit(_wa, ("Line element [index=" + vtos(readManyIteration) + "] equals to \"" + __testlib_part(result) + "\" doesn't correspond to pattern \"" + p.src() + "\"").c_str());
  3426.             else
  3427.                 quit(_wa, ("Line element " + std::string(variableName) + "[" + vtos(readManyIteration) + "] equals to \"" + __testlib_part(result) + "\", doesn't correspond to pattern \"" + p.src() + "\"").c_str());
  3428.         }
  3429.     }
  3430. }
  3431.  
  3432. void InStream::readStringTo(std::string& result, const std::string& ptrn, const std::string& variableName)
  3433. {
  3434.     readStringTo(result, pattern(ptrn), variableName);
  3435. }
  3436.  
  3437. std::string InStream::readString(const pattern& p, const std::string& variableName)
  3438. {
  3439.     readStringTo(_tmpReadToken, p, variableName);
  3440.     return _tmpReadToken;
  3441. }
  3442.  
  3443. std::vector<std::string> InStream::readStrings(int size, const pattern& p, const std::string& variablesName, int indexBase)
  3444. {
  3445.     __testlib_readMany(readStrings, readString(p, variablesName), std::string, false)
  3446. }
  3447.  
  3448. std::string InStream::readString(const std::string& ptrn, const std::string& variableName)
  3449. {
  3450.     readStringTo(_tmpReadToken, ptrn, variableName);
  3451.     return _tmpReadToken;
  3452. }
  3453.  
  3454. std::vector<std::string> InStream::readStrings(int size, const std::string& ptrn, const std::string& variablesName, int indexBase)
  3455. {
  3456.     pattern p(ptrn);
  3457.     __testlib_readMany(readStrings, readString(p, variablesName), std::string, false)
  3458. }
  3459.  
  3460. void InStream::readLineTo(std::string& result)
  3461. {
  3462.     readStringTo(result);
  3463. }
  3464.  
  3465. std::string InStream::readLine()
  3466. {
  3467.     return readString();
  3468. }
  3469.  
  3470. std::vector<std::string> InStream::readLines(int size, int indexBase)
  3471. {
  3472.     __testlib_readMany(readLines, readString(), std::string, false)
  3473. }
  3474.  
  3475. void InStream::readLineTo(std::string& result, const pattern& p, const std::string& variableName)
  3476. {
  3477.     readStringTo(result, p, variableName);
  3478. }
  3479.  
  3480. void InStream::readLineTo(std::string& result, const std::string& ptrn, const std::string& variableName)
  3481. {
  3482.     readStringTo(result, ptrn, variableName);
  3483. }
  3484.  
  3485. std::string InStream::readLine(const pattern& p, const std::string& variableName)
  3486. {
  3487.     return readString(p, variableName);
  3488. }
  3489.  
  3490. std::vector<std::string> InStream::readLines(int size, const pattern& p, const std::string& variablesName, int indexBase)
  3491. {
  3492.     __testlib_readMany(readLines, readString(p, variablesName), std::string, false)
  3493. }
  3494.  
  3495. std::string InStream::readLine(const std::string& ptrn, const std::string& variableName)
  3496. {
  3497.     return readString(ptrn, variableName);
  3498. }
  3499.  
  3500. std::vector<std::string> InStream::readLines(int size, const std::string& ptrn, const std::string& variablesName, int indexBase)
  3501. {
  3502.     pattern p(ptrn);
  3503.     __testlib_readMany(readLines, readString(p, variablesName), std::string, false)
  3504. }
  3505.  
  3506. void InStream::close()
  3507. {
  3508.     if (NULL != reader)
  3509.     {
  3510.         reader->close();
  3511.         delete reader;
  3512.         reader = NULL;
  3513.     }
  3514.    
  3515.     opened = false;
  3516. }
  3517.  
  3518. NORETURN void quit(TResult result, const std::string& msg)
  3519. {
  3520.     ouf.quit(result, msg.c_str());
  3521. }
  3522.  
  3523. NORETURN void quit(TResult result, const char* msg)
  3524. {
  3525.     ouf.quit(result, msg);
  3526. }
  3527.  
  3528. NORETURN void __testlib_quitp(double points, const char* message)
  3529. {
  3530.     __testlib_points = points;
  3531.     std::string stringPoints = removeDoubleTrailingZeroes(format("%.10f", points));
  3532.  
  3533.     std::string quitMessage;
  3534.     if (NULL == message || 0 == strlen(message))
  3535.         quitMessage = stringPoints;
  3536.     else
  3537.         quitMessage = stringPoints + " | " + message;
  3538.  
  3539.     quit(_points, quitMessage.c_str());
  3540. }
  3541.  
  3542. NORETURN void __testlib_quitp(int points, const char* message)
  3543. {
  3544.     __testlib_points = points;
  3545.     std::string stringPoints = format("%d", points);
  3546.  
  3547.     std::string quitMessage;
  3548.     if (NULL == message || 0 == strlen(message))
  3549.         quitMessage = stringPoints;
  3550.     else
  3551.         quitMessage = stringPoints + " | " + message;
  3552.  
  3553.     quit(_points, quitMessage.c_str());
  3554. }
  3555.  
  3556. NORETURN void quitp(float points, const std::string& message = "")
  3557. {
  3558.     __testlib_quitp(double(points), message.c_str());
  3559. }
  3560.  
  3561. NORETURN void quitp(double points, const std::string& message = "")
  3562. {
  3563.     __testlib_quitp(points, message.c_str());
  3564. }
  3565.  
  3566. NORETURN void quitp(long double points, const std::string& message = "")
  3567. {
  3568.     __testlib_quitp(double(points), message.c_str());
  3569. }
  3570.  
  3571. NORETURN void quitp(int points, const std::string& message = "")
  3572. {
  3573.     __testlib_quitp(points, message.c_str());
  3574. }
  3575.  
  3576. template<typename F>
  3577. #ifdef __GNUC__
  3578. __attribute__ ((format (printf, 2, 3)))
  3579. #endif
  3580. NORETURN void quitp(F points, const char* format, ...)
  3581. {
  3582.     FMT_TO_RESULT(format, format, message);
  3583.     quitp(points, message);
  3584. }
  3585.  
  3586. #ifdef __GNUC__
  3587. __attribute__ ((format (printf, 2, 3)))
  3588. #endif
  3589. NORETURN void quitf(TResult result, const char* format, ...)
  3590. {
  3591.     FMT_TO_RESULT(format, format, message);
  3592.     quit(result, message);
  3593. }
  3594.  
  3595. #ifdef __GNUC__
  3596. __attribute__ ((format (printf, 3, 4)))
  3597. #endif
  3598. void quitif(bool condition, TResult result, const char* format, ...)
  3599. {
  3600.     if (condition)
  3601.     {
  3602.         FMT_TO_RESULT(format, format, message);
  3603.         quit(result, message);
  3604.     }
  3605. }
  3606.  
  3607. NORETURN void __testlib_help()
  3608. {
  3609.     InStream::textColor(InStream::LightCyan);
  3610.     std::fprintf(stderr, "TESTLIB %s, http://code.google.com/p/testlib/ ", VERSION);
  3611.     std::fprintf(stderr, "by Mike Mirzayanov, copyright(c) 2005-2017\n");
  3612.     std::fprintf(stderr, "Checker name: \"%s\"\n", checkerName.c_str());
  3613.     InStream::textColor(InStream::LightGray);
  3614.  
  3615.     std::fprintf(stderr, "\n");
  3616.     std::fprintf(stderr, "Latest features: \n");
  3617.     for (size_t i = 0; i < sizeof(latestFeatures) / sizeof(char*); i++)
  3618.     {
  3619.         std::fprintf(stderr, "*) %s\n", latestFeatures[i]);
  3620.     }
  3621.     std::fprintf(stderr, "\n");
  3622.  
  3623.     std::fprintf(stderr, "Program must be run with the following arguments: \n");
  3624.     std::fprintf(stderr, "    <input-file> <output-file> <answer-file> [<report-file> [<-appes>]]\n\n");
  3625.  
  3626.     std::exit(FAIL_EXIT_CODE);
  3627. }
  3628.  
  3629. static void __testlib_ensuresPreconditions()
  3630. {
  3631.     // testlib assumes: sizeof(int) = 4.
  3632.     __TESTLIB_STATIC_ASSERT(sizeof(int) == 4);
  3633.  
  3634.     // testlib assumes: INT_MAX == 2147483647.
  3635.     __TESTLIB_STATIC_ASSERT(INT_MAX == 2147483647);
  3636.  
  3637.     // testlib assumes: sizeof(long long) = 8.
  3638.     __TESTLIB_STATIC_ASSERT(sizeof(long long) == 8);
  3639.  
  3640.     // testlib assumes: sizeof(double) = 8.
  3641.     __TESTLIB_STATIC_ASSERT(sizeof(double) == 8);
  3642.  
  3643.     // testlib assumes: no -ffast-math.
  3644.     if (!__testlib_isNaN(+__testlib_nan()))
  3645.         quit(_fail, "Function __testlib_isNaN is not working correctly: possible reason is '-ffast-math'");
  3646.     if (!__testlib_isNaN(-__testlib_nan()))
  3647.         quit(_fail, "Function __testlib_isNaN is not working correctly: possible reason is '-ffast-math'");
  3648. }
  3649.  
  3650. void registerGen(int argc, char* argv[], int randomGeneratorVersion)
  3651. {
  3652.     if (randomGeneratorVersion < 0 || randomGeneratorVersion > 1)
  3653.         quitf(_fail, "Random generator version is expected to be 0 or 1.");
  3654.     random_t::version = randomGeneratorVersion;
  3655.  
  3656.     __testlib_ensuresPreconditions();
  3657.  
  3658.     testlibMode = _generator;
  3659.     __testlib_set_binary(stdin);
  3660.     rnd.setSeed(argc, argv);
  3661. }
  3662.  
  3663. #ifdef USE_RND_AS_BEFORE_087
  3664. void registerGen(int argc, char* argv[])
  3665. {
  3666.     registerGen(argc, argv, 0);
  3667. }
  3668. #else
  3669. #ifdef __GNUC__
  3670.     __attribute__ ((deprecated("Use registerGen(argc, argv, 0) or registerGen(argc, argv, 1)."
  3671.             " The third parameter stands for the random generator version."
  3672.             " If you are trying to compile old generator use macro -DUSE_RND_AS_BEFORE_087 or registerGen(argc, argv, 0)."
  3673.             " Version 1 has been released on Spring, 2013. Use it to write new generators.")))
  3674. #endif
  3675. #ifdef _MSC_VER
  3676.     __declspec(deprecated("Use registerGen(argc, argv, 0) or registerGen(argc, argv, 1)."
  3677.             " The third parameter stands for the random generator version."
  3678.             " If you are trying to compile old generator use macro -DUSE_RND_AS_BEFORE_087 or registerGen(argc, argv, 0)."
  3679.             " Version 1 has been released on Spring, 2013. Use it to write new generators."))
  3680. #endif
  3681. void registerGen(int argc, char* argv[])
  3682. {
  3683.     std::fprintf(stderr, "Use registerGen(argc, argv, 0) or registerGen(argc, argv, 1)."
  3684.             " The third parameter stands for the random generator version."
  3685.             " If you are trying to compile old generator use macro -DUSE_RND_AS_BEFORE_087 or registerGen(argc, argv, 0)."
  3686.             " Version 1 has been released on Spring, 2013. Use it to write new generators.\n\n");
  3687.     registerGen(argc, argv, 0);
  3688. }
  3689. #endif
  3690.  
  3691. void registerInteraction(int argc, char* argv[])
  3692. {
  3693.     __testlib_ensuresPreconditions();
  3694.  
  3695.     testlibMode = _interactor;
  3696.     __testlib_set_binary(stdin);
  3697.  
  3698.     if (argc > 1 && !strcmp("--help", argv[1]))
  3699.         __testlib_help();
  3700.    
  3701.     if (argc < 3 || argc > 6)
  3702.     {
  3703.         quit(_fail, std::string("Program must be run with the following arguments: ") +
  3704.             std::string("<input-file> <output-file> [<answer-file> [<report-file> [<-appes>]]]") +
  3705.             "\nUse \"--help\" to get help information");
  3706.     }
  3707.  
  3708.     if (argc <= 4)
  3709.     {
  3710.         resultName = "";
  3711.         appesMode = false;
  3712.     }
  3713.  
  3714.     if (argc == 5)
  3715.     {
  3716.         resultName = argv[4];
  3717.         appesMode = false;
  3718.     }
  3719.  
  3720.     if (argc == 6)
  3721.     {
  3722.         if (strcmp("-APPES", argv[5]) && strcmp("-appes", argv[5]))
  3723.         {
  3724.             quit(_fail, std::string("Program must be run with the following arguments: ") +
  3725.                         "<input-file> <output-file> <answer-file> [<report-file> [<-appes>]]");
  3726.         }
  3727.         else
  3728.         {
  3729.             resultName = argv[4];
  3730.             appesMode = true;
  3731.         }
  3732.     }
  3733.  
  3734.     inf.init(argv[1], _input);
  3735.  
  3736.     tout.open(argv[2], std::ios_base::out);
  3737.     if (tout.fail() || !tout.is_open())
  3738.         quit(_fail, std::string("Can not write to the test-output-file '") + argv[2] + std::string("'"));
  3739.  
  3740.     ouf.init(stdin, _output);
  3741.    
  3742.     if (argc >= 4)
  3743.         ans.init(argv[3], _answer);
  3744.     else
  3745.         ans.name = "unopened answer stream";
  3746. }
  3747.  
  3748. void registerValidation()
  3749. {
  3750.     __testlib_ensuresPreconditions();
  3751.  
  3752.     testlibMode = _validator;
  3753.     __testlib_set_binary(stdin);
  3754.  
  3755.     inf.init(stdin, _input);
  3756.     inf.strict = true;
  3757. }
  3758.  
  3759. void registerValidation(int argc, char* argv[])
  3760. {
  3761.     registerValidation();
  3762.  
  3763.     for (int i = 1; i < argc; i++)
  3764.     {
  3765.         if (!strcmp("--testset", argv[i]))
  3766.         {
  3767.             if (i + 1 < argc && strlen(argv[i + 1]) > 0)
  3768.                 validator.setTestset(argv[++i]);
  3769.             else
  3770.                 quit(_fail, std::string("Validator must be run with the following arguments: ") +
  3771.                         "[--testset testset] [--group group] [--testOverviewLogFileName fileName]");
  3772.         }
  3773.         if (!strcmp("--group", argv[i]))
  3774.         {
  3775.             if (i + 1 < argc)
  3776.                 validator.setGroup(argv[++i]);
  3777.             else
  3778.                 quit(_fail, std::string("Validator must be run with the following arguments: ") +
  3779.                         "[--testset testset] [--group group] [--testOverviewLogFileName fileName]");
  3780.         }
  3781.         if (!strcmp("--testOverviewLogFileName", argv[i]))
  3782.         {
  3783.             if (i + 1 < argc)
  3784.                 validator.setTestOverviewLogFileName(argv[++i]);
  3785.             else
  3786.                 quit(_fail, std::string("Validator must be run with the following arguments: ") +
  3787.                         "[--testset testset] [--group group] [--testOverviewLogFileName fileName]");
  3788.         }
  3789.     }        
  3790. }
  3791.  
  3792. void addFeature(const std::string& feature)
  3793. {
  3794.     if (testlibMode != _validator)
  3795.         quit(_fail, "Features are supported in validators only.");
  3796.     validator.addFeature(feature);    
  3797. }
  3798.  
  3799. void feature(const std::string& feature)
  3800. {
  3801.     if (testlibMode != _validator)
  3802.         quit(_fail, "Features are supported in validators only.");
  3803.     validator.feature(feature);    
  3804. }
  3805.  
  3806. void registerTestlibCmd(int argc, char* argv[])
  3807. {
  3808.     __testlib_ensuresPreconditions();
  3809.  
  3810.     testlibMode = _checker;
  3811.     __testlib_set_binary(stdin);
  3812.  
  3813.     /*if (argc > 1 && !strcmp("--help", argv[1]))
  3814.         __testlib_help();
  3815.  
  3816.     if (argc < 4 || argc > 6)
  3817.     {
  3818.         quit(_fail, std::string("Program must be run with the following arguments: ") +
  3819.             std::string("<input-file> <output-file> <answer-file> [<report-file> [<-appes>]]") +
  3820.             "\nUse \"--help\" to get help information");
  3821.     }
  3822.  
  3823.     if (argc == 4)
  3824.     {
  3825.         resultName = "";
  3826.         appesMode = false;
  3827.     }
  3828.  
  3829.     if (argc == 5)
  3830.     {
  3831.         resultName = argv[4];
  3832.         appesMode = false;
  3833.     }
  3834.  
  3835.     if (argc == 6)
  3836.     {
  3837.         if (strcmp("-APPES", argv[5]) && strcmp("-appes", argv[5]))
  3838.         {
  3839.             quit(_fail, std::string("Program must be run with the following arguments: ") +
  3840.                         "<input-file> <output-file> <answer-file> [<report-file> [<-appes>]]");
  3841.         }
  3842.         else
  3843.         {
  3844.             resultName = argv[4];
  3845.             appesMode = true;
  3846.         }
  3847.     }*/
  3848.  
  3849.     resultName = "";
  3850.     appesMode = false;
  3851.  
  3852.     //inf.init(argv[1], _input);
  3853.     //ouf.init(argv[2], _output);
  3854.     //ans.init(argv[3], _answer);
  3855.     inf.init("input", _input);
  3856.     ouf.init("user_out", _output);
  3857.     ans.init("answer", _answer);
  3858. }
  3859.  
  3860. void registerTestlib(int argc, ...)
  3861. {
  3862.     if (argc  < 3 || argc > 5)
  3863.         quit(_fail, std::string("Program must be run with the following arguments: ") +
  3864.             "<input-file> <output-file> <answer-file> [<report-file> [<-appes>]]");
  3865.  
  3866.     char** argv = new char*[argc + 1];
  3867.    
  3868.     va_list ap;
  3869.     va_start(ap, argc);
  3870.     argv[0] = NULL;
  3871.     for (int i = 0; i < argc; i++)
  3872.     {
  3873.         argv[i + 1] = va_arg(ap, char*);
  3874.     }
  3875.     va_end(ap);
  3876.  
  3877.     registerTestlibCmd(argc + 1, argv);
  3878.     delete[] argv;
  3879. }
  3880.  
  3881. static inline void __testlib_ensure(bool cond, const std::string& msg)
  3882. {
  3883.     if (!cond)
  3884.         quit(_fail, msg.c_str());
  3885. }
  3886.  
  3887. static inline void __testlib_ensure(bool cond, const char* msg)
  3888. {
  3889.     if (!cond)
  3890.         quit(_fail, msg);
  3891. }
  3892.  
  3893. #define ensure(cond) __testlib_ensure(cond, "Condition failed: \"" #cond "\"")
  3894.  
  3895. #ifdef __GNUC__
  3896. __attribute__ ((format (printf, 2, 3)))
  3897. #endif
  3898. inline void ensuref(bool cond, const char* format, ...)
  3899. {
  3900.     if (!cond)
  3901.     {
  3902.         FMT_TO_RESULT(format, format, message);
  3903.         __testlib_ensure(cond, message);
  3904.     }
  3905. }
  3906.  
  3907. NORETURN static void __testlib_fail(const std::string& message)
  3908. {
  3909.     quitf(_fail, "%s", message.c_str());
  3910. }
  3911.  
  3912. #ifdef __GNUC__
  3913. __attribute__ ((format (printf, 1, 2)))
  3914. #endif
  3915. void setName(const char* format, ...)
  3916. {
  3917.     FMT_TO_RESULT(format, format, name);
  3918.     checkerName = name;
  3919. }
  3920.  
  3921. /*
  3922.  * Do not use random_shuffle, because it will produce different result
  3923.  * for different C++ compilers.
  3924.  *
  3925.  * This implementation uses testlib random_t to produce random numbers, so
  3926.  * it is stable.
  3927.  */
  3928. template<typename _RandomAccessIter>
  3929. void shuffle(_RandomAccessIter __first, _RandomAccessIter __last)
  3930. {
  3931.     if (__first == __last) return;
  3932.     for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
  3933.         std::iter_swap(__i, __first + rnd.next(int(__i - __first) + 1));
  3934. }
  3935.  
  3936.  
  3937. template<typename _RandomAccessIter>
  3938. #ifdef __GNUC__
  3939. __attribute__ ((error("Don't use random_shuffle(), use shuffle() instead")))
  3940. #endif
  3941. void random_shuffle(_RandomAccessIter , _RandomAccessIter )
  3942. {
  3943.     quitf(_fail, "Don't use random_shuffle(), use shuffle() instead");
  3944. }
  3945.  
  3946. #ifdef __GLIBC__
  3947. #  define RAND_THROW_STATEMENT throw()
  3948. #else
  3949. #  define RAND_THROW_STATEMENT
  3950. #endif
  3951.  
  3952. #ifdef __GNUC__
  3953. __attribute__ ((error("Don't use rand(), use rnd.next() instead")))
  3954. #endif
  3955. #ifdef _MSC_VER
  3956. #   pragma warning( disable : 4273 )
  3957. #endif
  3958. int rand() RAND_THROW_STATEMENT
  3959. {
  3960.     quitf(_fail, "Don't use rand(), use rnd.next() instead");
  3961.    
  3962.     /* This line never runs. */
  3963.     //throw "Don't use rand(), use rnd.next() instead";
  3964. }
  3965.  
  3966. #ifdef __GNUC__
  3967. __attribute__ ((error("Don't use srand(), you should use "
  3968.         "'registerGen(argc, argv, 1);' to initialize generator seed "
  3969.         "by hash code of the command line params. The third parameter "
  3970.         "is randomGeneratorVersion (currently the latest is 1).")))
  3971. #endif
  3972. #ifdef _MSC_VER
  3973. #   pragma warning( disable : 4273 )
  3974. #endif
  3975. void srand(unsigned int seed) RAND_THROW_STATEMENT
  3976. {
  3977.     quitf(_fail, "Don't use srand(), you should use "
  3978.         "'registerGen(argc, argv, 1);' to initialize generator seed "
  3979.         "by hash code of the command line params. The third parameter "
  3980.         "is randomGeneratorVersion (currently the latest is 1) [ignored seed=%d].", seed);
  3981. }
  3982.  
  3983. void startTest(int test)
  3984. {
  3985.     const std::string testFileName = vtos(test);
  3986.     if (NULL == freopen(testFileName.c_str(), "wt", stdout))
  3987.         __testlib_fail("Unable to write file '" + testFileName + "'");
  3988. }
  3989.  
  3990. inline std::string upperCase(std::string s)
  3991. {
  3992.     for (size_t i = 0; i < s.length(); i++)
  3993.         if ('a' <= s[i] && s[i] <= 'z')
  3994.             s[i] = char(s[i] - 'a' + 'A');
  3995.     return s;
  3996. }
  3997.  
  3998. inline std::string lowerCase(std::string s)
  3999. {
  4000.     for (size_t i = 0; i < s.length(); i++)
  4001.         if ('A' <= s[i] && s[i] <= 'Z')
  4002.             s[i] = char(s[i] - 'A' + 'a');
  4003.     return s;
  4004. }
  4005.  
  4006. inline std::string compress(const std::string& s)
  4007. {
  4008.     return __testlib_part(s);
  4009. }
  4010.  
  4011. inline std::string englishEnding(int x)
  4012. {
  4013.     x %= 100;
  4014.     if (x / 10 == 1)
  4015.         return "th";
  4016.     if (x % 10 == 1)
  4017.         return "st";
  4018.     if (x % 10 == 2)
  4019.         return "nd";
  4020.     if (x % 10 == 3)
  4021.         return "rd";
  4022.     return "th";
  4023. }
  4024.  
  4025. inline std::string trim(const std::string& s)
  4026. {
  4027.     if (s.empty())
  4028.         return s;
  4029.  
  4030.     int left = 0;
  4031.     while (left < int(s.length()) && isBlanks(s[left]))
  4032.         left++;
  4033.     if (left >= int(s.length()))
  4034.         return "";
  4035.  
  4036.     int right = int(s.length()) - 1;
  4037.     while (right >= 0 && isBlanks(s[right]))
  4038.         right--;
  4039.     if (right < 0)
  4040.         return "";
  4041.  
  4042.     return s.substr(left, right - left + 1);
  4043. }
  4044.  
  4045. template <typename _ForwardIterator, typename _Separator>
  4046. std::string join(_ForwardIterator first, _ForwardIterator last, _Separator separator)
  4047. {
  4048.     std::stringstream ss;
  4049.     bool repeated = false;
  4050.     for (_ForwardIterator i = first; i != last; i++)
  4051.     {
  4052.         if (repeated)
  4053.             ss << separator;
  4054.         else
  4055.             repeated = true;
  4056.         ss << *i;
  4057.     }
  4058.     return ss.str();
  4059. }
  4060.  
  4061. template <typename _ForwardIterator>
  4062. std::string join(_ForwardIterator first, _ForwardIterator last)
  4063. {
  4064.     return join(first, last, ' ');
  4065. }
  4066.  
  4067. template <typename _Collection, typename _Separator>
  4068. std::string join(const _Collection& collection, _Separator separator)
  4069. {
  4070.     return join(collection.begin(), collection.end(), separator);
  4071. }
  4072.  
  4073. template <typename _Collection>
  4074. std::string join(const _Collection& collection)
  4075. {
  4076.     return join(collection, ' ');
  4077. }
  4078.  
  4079. /**
  4080.  * Splits string s by character separator returning exactly k+1 items,
  4081.  * where k is the number of separator occurences.
  4082.  */
  4083. std::vector<std::string> split(const std::string& s, char separator)
  4084. {
  4085.     std::vector<std::string> result;
  4086.     std::string item;
  4087.     for (size_t i = 0; i < s.length(); i++)
  4088.         if (s[i] == separator)
  4089.         {
  4090.             result.push_back(item);
  4091.             item = "";
  4092.         }
  4093.         else
  4094.             item += s[i];
  4095.     result.push_back(item);
  4096.     return result;
  4097. }
  4098.  
  4099. /**
  4100.  * Splits string s by character separators returning exactly k+1 items,
  4101.  * where k is the number of separator occurences.
  4102.  */
  4103. std::vector<std::string> split(const std::string& s, const std::string& separators)
  4104. {
  4105.     if (separators.empty())
  4106.         return std::vector<std::string>(1, s);
  4107.  
  4108.     std::vector<bool> isSeparator(256);
  4109.     for (size_t i = 0; i < separators.size(); i++)
  4110.         isSeparator[(unsigned char)(separators[i])] = true;
  4111.  
  4112.     std::vector<std::string> result;
  4113.     std::string item;
  4114.     for (size_t i = 0; i < s.length(); i++)
  4115.         if (isSeparator[(unsigned char)(s[i])])
  4116.         {
  4117.             result.push_back(item);
  4118.             item = "";
  4119.         }
  4120.         else
  4121.             item += s[i];
  4122.     result.push_back(item);
  4123.     return result;
  4124. }
  4125.  
  4126. /**
  4127.  * Splits string s by character separator returning non-empty items.
  4128.  */
  4129. std::vector<std::string> tokenize(const std::string& s, char separator)
  4130. {
  4131.     std::vector<std::string> result;
  4132.     std::string item;
  4133.     for (size_t i = 0; i < s.length(); i++)
  4134.         if (s[i] == separator)
  4135.         {
  4136.             if (!item.empty())
  4137.                 result.push_back(item);
  4138.             item = "";
  4139.         }
  4140.         else
  4141.             item += s[i];
  4142.     if (!item.empty())
  4143.         result.push_back(item);
  4144.     return result;
  4145. }
  4146.  
  4147. /**
  4148.  * Splits string s by character separators returning non-empty items.
  4149.  */
  4150. std::vector<std::string> tokenize(const std::string& s, const std::string& separators)
  4151. {
  4152.     if (separators.empty())
  4153.         return std::vector<std::string>(1, s);
  4154.  
  4155.     std::vector<bool> isSeparator(256);
  4156.     for (size_t i = 0; i < separators.size(); i++)
  4157.         isSeparator[(unsigned char)(separators[i])] = true;
  4158.  
  4159.     std::vector<std::string> result;
  4160.     std::string item;
  4161.     for (size_t i = 0; i < s.length(); i++)
  4162.         if (isSeparator[(unsigned char)(s[i])])
  4163.         {
  4164.             if (!item.empty())
  4165.                 result.push_back(item);
  4166.             item = "";
  4167.         }
  4168.         else
  4169.             item += s[i];
  4170.    
  4171.     if (!item.empty())
  4172.         result.push_back(item);
  4173.  
  4174.     return result;
  4175. }
  4176.  
  4177. NORETURN void __testlib_expectedButFound(TResult result, std::string expected, std::string found, const char* prepend)
  4178. {
  4179.     std::string message;
  4180.     if (strlen(prepend) != 0)
  4181.         message = format("%s: expected '%s', but found '%s'",
  4182.             compress(prepend).c_str(), compress(expected).c_str(), compress(found).c_str());
  4183.     else
  4184.         message = format("expected '%s', but found '%s'",
  4185.             compress(expected).c_str(), compress(found).c_str());
  4186.     quit(result, message);
  4187. }
  4188.  
  4189. NORETURN void __testlib_expectedButFound(TResult result, double expected, double found, const char* prepend)
  4190. {
  4191.     std::string expectedString = removeDoubleTrailingZeroes(format("%.12f", expected));
  4192.     std::string foundString = removeDoubleTrailingZeroes(format("%.12f", found));
  4193.     __testlib_expectedButFound(result, expectedString, foundString, prepend);
  4194. }
  4195.  
  4196. template <typename T>
  4197. #ifdef __GNUC__
  4198. __attribute__ ((format (printf, 4, 5)))
  4199. #endif
  4200. NORETURN void expectedButFound(TResult result, T expected, T found, const char* prependFormat = "", ...)
  4201. {
  4202.     FMT_TO_RESULT(prependFormat, prependFormat, prepend);
  4203.     std::string expectedString = vtos(expected);
  4204.     std::string foundString = vtos(found);
  4205.     __testlib_expectedButFound(result, expectedString, foundString, prepend.c_str());
  4206. }
  4207.  
  4208. template <>
  4209. #ifdef __GNUC__
  4210. __attribute__ ((format (printf, 4, 5)))
  4211. #endif
  4212. NORETURN void expectedButFound<std::string>(TResult result, std::string expected, std::string found, const char* prependFormat, ...)
  4213. {
  4214.     FMT_TO_RESULT(prependFormat, prependFormat, prepend);
  4215.     __testlib_expectedButFound(result, expected, found, prepend.c_str());
  4216. }
  4217.  
  4218. template <>
  4219. #ifdef __GNUC__
  4220. __attribute__ ((format (printf, 4, 5)))
  4221. #endif
  4222. NORETURN void expectedButFound<double>(TResult result, double expected, double found, const char* prependFormat, ...)
  4223. {
  4224.     FMT_TO_RESULT(prependFormat, prependFormat, prepend);
  4225.     std::string expectedString = removeDoubleTrailingZeroes(format("%.12f", expected));
  4226.     std::string foundString = removeDoubleTrailingZeroes(format("%.12f", found));
  4227.     __testlib_expectedButFound(result, expectedString, foundString, prepend.c_str());
  4228. }
  4229.  
  4230. template <>
  4231. #ifdef __GNUC__
  4232. __attribute__ ((format (printf, 4, 5)))
  4233. #endif
  4234. NORETURN void expectedButFound<const char*>(TResult result, const char* expected, const char* found, const char* prependFormat, ...)
  4235. {
  4236.     FMT_TO_RESULT(prependFormat, prependFormat, prepend);
  4237.     __testlib_expectedButFound(result, std::string(expected), std::string(found), prepend.c_str());
  4238. }
  4239.  
  4240. template <>
  4241. #ifdef __GNUC__
  4242. __attribute__ ((format (printf, 4, 5)))
  4243. #endif
  4244. NORETURN void expectedButFound<float>(TResult result, float expected, float found, const char* prependFormat, ...)
  4245. {
  4246.     FMT_TO_RESULT(prependFormat, prependFormat, prepend);
  4247.     __testlib_expectedButFound(result, double(expected), double(found), prepend.c_str());
  4248. }
  4249.  
  4250. template <>
  4251. #ifdef __GNUC__
  4252. __attribute__ ((format (printf, 4, 5)))
  4253. #endif
  4254. NORETURN void expectedButFound<long double>(TResult result, long double expected, long double found, const char* prependFormat, ...)
  4255. {
  4256.     FMT_TO_RESULT(prependFormat, prependFormat, prepend);
  4257.     __testlib_expectedButFound(result, double(expected), double(found), prepend.c_str());
  4258. }
  4259.  
  4260. #endif
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top