↵
### Виды генераторов↵
↵
Есть два вида генераторов: обычные и мультигенераторы.↵
↵
1. Первые за один свой запуск выводят ровно один тест. Обычно, чтобы сгенерировать несколько тестов, такой генератор надо запустить несколько раз с разными параметрами командной строки. Такие генераторы выводят тест в стандартный поток вывода (на экран).↵
1. Мультигенераторы за один запуск выводят сразу много тестов. Такие генераторы выводят тесты в файлы (один файл — один тест).↵
↵
### Пример простого обычного генератора на testlib.h↵
↵
Выводит пару чисел от 1 до $n$, где $n$ — переданный параметр запуска генератора.↵
↵
~~~~~↵
#include "testlib.h"↵
#include <iostream>↵
↵
using namespace std;↵
↵
int main(int argc, char* argv[])↵
{↵
registerGen(argc, argv, 1);↵
int n = atoi(argv[1]);↵
cout << rnd.next(1, n) << " ";↵
cout << rnd.next(1, n) << endl;↵
}↵
~~~~~↵
↵
↵
### Зачем testlib.h?↵
↵
При невнимательном взгляде кажется, что testlib.h почти не нужен для написания генератора. На самом деле это неправда. Почти в каждом генераторе нужна возможность получать случайные значения, и есть большое искушение использовать `rand()`. Не делайте этого. Основной принцип написания генератора: *генератор должен выводить один и тот же тест при компиляции любым компилятором на любой платформе, если он запущен одинаковым способом*. При использовании `rand()` или классов C++11 вроде `mt19937/uniform_int_distribution` ваша программа будет выводить разные тесты после компиляции разными компиляторами.↵
↵
Генератор случайных значений в testlib.h гарантирует, что будет сгенерировано одно и то же, независимо от генератора и платформы. Кроме того, в testlib.h есть разные удобности для генерации тестов, например, `rnd.next("[a-z]{1,10}")` вернет случайное слово длины от 1 до 10 из букв от `a` до `z`.↵
↵
### Что есть у testlib.h?↵
↵
Чтобы инициализировать testlib-генератор, первая строка вашего генератора должна иметь вид `registerGen(argc, argv, 1);` (где 1 — это версия используемого генератора случайных чисел). После этого можно будет пользоваться объектом `rnd`, который будет проинициализирован хешем от всех аргументов командной строки. Таким образом, результат вывода `g 100` и `g.exe "100"` будет одинаков, а у `g 100 0` будет отличаться.↵
↵
Объект `rnd` имеет тип `random_t`, то есть вы можете создать и свой генератор, но обычно это не нужно.↵
↵
У объекта `rnd` есть много полезных членов-функций. Вот примеры:↵
↵
|Вызов|Что делает|↵
|-|-|↵
|rnd.next(4)|равновероятное целое случайное число от 0 до 3 включительно|↵
|rnd.next(4, 100)|равновероятное целое случайное число от 4 до 100 включительно|↵
|rnd.next(10.0)|равновероятное вещественное случайное число в полуинтервале [0,10)|↵
|rnd.next("one\|two\|three")|равновероятное случайное одно слово из трех one, two и three|↵
|rnd.next("[1-9][0-9]{99}")|равновероятное случайное 100-значное число в виде строки |↵
|rnd.wnext(4,t)|wnext — это способ получения неравновероятного распределения (со смещенным матожиданием), параметр $t$ обозначает количество вызовов операции "максимум" для аналогичных вызовов next, например rnd.wnext(3, 1) эквивалентен max(rnd.next(3), rnd.next(3)), а rnd.wnext(4, 2) эквивалентен max(rnd.next(4), max(rnd.next(4), rnd.next(4))). Если $t<0$, то $-t$ будет найден минимум. Если $t=0$, то wnext эквивалентен next.|↵
|rnd.any(container)|вернет случайный элемент контейнера container (с произвольным доступом по итератору), например, работает для std::vector и std::string|↵
↵
Кроме того, не надо использовать `std::random_shuffle`, используйте `shuffle` из testlib. Он так же принимает два итератора, но работает, используя `rnd`.↵
↵
#### Пример: генерация неориентированного дерева↵
↵
Ниже основной код генератора неориентированного дерева, который принимает два параметра — количество вершин и степень его *вытянутости*. Например, при $n=10, t=1000$ наверняка будет сгенерирована цепь, а при $n=10, t=-1000$ наверняка будет сгенерирована ромашка (звездочка)
--------------------↵
↵
Generators are helper programs that output test. Most programming task usually has a large input (for example, an array of up to $2 * 10^5$ elements, a tree of up to $10^5$ vertices), so it's not possible to add all the tests manually. In these cases, generators come to the rescue. ↵
↵
If you are writing a generator in C++, it is recommended to use the [testlib.h](https://g...content-available-to-author-only...b.com/MikeMirzayanov/testlib) library.↵
↵
Types of generators↵
-------------------↵
There are two types of generators:↵
↵
1. **Single-test generator:** output exactly one test in a single run. Usually, to generate several tests, one must run the generator several times with different command line parameters. Such generators output the test to the standard output stream (to the screen).↵
2. **Multiple-test generator:** output many tests in a single run. Such generators output tests to files (one file for each test).↵
↵
An example single-test generator with testlib.h↵
-----------------------------------------------↵
The following generator output a pair of integers with each element from $1$ to $n$ — where $n$ is a command line parameter passed to the generator.↵
↵
~~~~~↵
#include "testlib.h"↵
#include <iostream>↵
↵
using namespace std;↵
↵
int main(int argc, char* argv[])↵
{↵
registerGen(argc, argv, 1);↵
int n = atoi(argv[1]);↵
cout << rnd.next(1, n) << " ";↵
cout << rnd.next(1, n) << endl;↵
}↵
~~~~~↵
↵
Why testlib.h?↵
--------------↵
↵
On the surface, it seems that testlib.h is not necessary to write a generator. This is not true. Almost all generators need to generate random values, and it is tempted to use `rand()`. However, this is a bad practice. A basic principle of writing generators is that: a generator must output the same test when compiled by any compiler on any platform if it is run in the same way (using the same command line parameters). When using `rand()` or C++11 classes like `mt19937/uniform_int_distribution`, your program will output different tests when compiled with different compilers.↵
↵
The random value generator in testlib.h ensures that the same value is generated regardless of the (test) generator and platform. Besides, testlib.h has various conveniences for generating tests, for example, `rnd.next("[a-z]{1,10}")` will return a random word of length $1$ to $10$ from letters a to z.↵
↵
_Translator's note: There are more issues with using `rand()` aside from the above one. Refer to [this](https://c...content-available-to-author-only...s.com/profile/neal) blog for a detailed explanation about these issues._↵
↵
Available method↵
----------------↵
↵
To initialize a testlib generator, the first line of your generator must be of the form `registerGen(argc, argv, 1);` (where 1 is the version of the random number generator used). After that, it will be possible to use the `rnd` object, which will be initialized with a hash from all the command line arguments. Thus, the output of `g 100` and `g.exe "100"` will be the same, while `g 100 0` will be different.↵
↵
`rnd` is of type `random_t`. That is, you can create your own generator, but this is not necessary in most of the cases.↵
↵
`rnd` has many useful member functions. Here are some examples:↵
↵
| Call | Return value |↵
|-----------------------------|--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|↵
| rnd.next(4) | An equiprobable random integer from $0$ to $3$ (inclusive) |↵
| rnd.next(4, 100) | An equiprobable random integer from $4$ to $100$ (inclusive) |↵
| rnd.next(10.0) | An equiprobable random real number in the half-interval $[0; 10)$ |↵
| rnd.next("one\|two\|three") | An equiprobable random word out of 'one', 'two' and 'three' |↵
| rnd.next("[1-9][0-9]{99}") | An equiprobable random 100-digit number as a string |↵
| rnd.wnext(4,t) | `wnext` is a method of obtaining an uneven distribution (with a biased expectation), the parameter `t` denotes the number of calls to the maximum operation for similar next calls. For example `rnd.wnext(3, 1)` is equivalent to `max(rnd.next(3), rnd.next(3))`, and `rnd.wnext(4, 2)` is equivalent to `max(rnd.next(4), max(rnd.next(4), rnd.next(4)))`. If t < 0, then -t will find the minimum. If t = 0, then `wnext` is equivalent to `next`. |↵
| rnd.any(container) | A random element of the container `container` (with random access via an iterator), for example, it works for `std::vector` and `std::string` |↵
↵
Also, please do not use `std::random_shuffle`, use the `shuffle` from testlib.h instead. It also takes two iterators, but works using `rnd`.↵
↵
_Translator's note: If my understanding is correct, `rnd.wnext` is defined as follows:_↵
↵
$$wnext(i, t) = \left\{\begin{matrix} next(i) & t = 0 \\ \max(next(i), wnext(i, t-1)) & t > 0 \\ \min(next(i), wnext(i, t+1)) & t < 0 \\ \end{matrix}\right.$$↵
↵
Example: generating an undirected tree↵
--------------------------------------↵
↵
Below is the code of an undirected tree generator that takes two parameters — the number of vertices and the 'elongation' of the tree. For example:↵
↵
- For $n = 10$, $t = 1000$, a path graph (degree of all vertices are at most $2$) is likely to be generated↵
- For $n = 10$, $t = -1000$, a star graph (there's only one non-leaf vertex in the tree) is likely to be generated.↵
↵
~~~~~↵
registerGen(argc, argv, 1);↵
↵
int n = atoi(argv[1]);↵
int t = atoi(argv[2]);↵
↵
vector<int> p(n);↵
↵
/* setup parents for vertices 1..n-1 */↵
for
if (i > 0)↵
p[i] = rnd.wnext(i, t);↵
↵
printf("%d\n", n);↵
↵
/* shuffle vertices 1..n-1 */↵
vector<int> perm(n);↵
for
perm[i] = i;↵
shuffle(perm.begin() + 1, perm.end());↵
↵
/* put edges considering shuffled vertices */↵
vector<pair<int,int> > edges;↵
for (int i = 1; i < n; i++)↵
if (rnd.next(2))↵
edges.push_back(make_pair(perm[i], perm[p[i]]));↵
else↵
edges.push_back(make_pair(perm[p[i]], perm[i]));↵
↵
/* shuffle edges */↵
shuffle(edges.begin(), edges.end());↵
↵
for (int i = 0; i + 1 < n; i++)↵
printf("%d %d\n", edges[i].first + 1, edges[i].second + 1);↵
~~~~~↵
↵
↵
Мультигенератор за одно исполнение может вывести более одного теста. Тесты таким генератором выводятся в файлы. В генераторе на testlib.h достаточно перед выводом теста написать `startTest(test_index)`. Это приведет к переоткрытию (freopen) потока стандартного вывода на файл с именем `test_index`. Обратите внимание, что в системе Polygon в таком случае в скрипте надо писать что-то вроде `multigen a b c > {4-10}` (если предполагается, что запуск мультигенератора вернет тесты 4, 5, 6, 7, 8, 9 и 10).↵
↵
#### На что еще обратить внимание?↵
↵
* Строго следуйте формату теста — пробелы, переводы строк должны быть идеально соблюдены. Тест должен заканчиваться переводом строки. Например, если в тест состоит из единственного числа, то выводите его как `cout << rnd.next(1, n) << endl;` — с переводом строки в конце.↵
* Если выводимый тест может быть довольно большим, то предпочитайте `printf` (а не `cout`) — это улучшит производительность.↵
* Лучше выводите `long long` через `cout`, но если хотите `printf`, то используйте константу I64 (например, `printf(I64, x);`).↵
* Необходимо не забывать о различных случаях неопределенного поведения языка C++. Например, в приведенном выше примере генератора нельзя объединять две команды `cout` в одну, т.к. тогда порядок вызовов функций `rnd.next` не определен.↵
↵
#### Еще примеры↵
↵
Примеры генераторов можно найти в [дистрибутиве](https://github.com/MikeMirzayanov/testlib/releases) или непосредственно в [репозитории](https://githu
------------------------------------↵
A multiple-test generator in one execution can output more than one test. Tests by such a generator are output to files. In the generator on testlib.h it is enough to write `startTest(test_index)` before the test output. This will re-open (`freopen`) the standard output stream to a file named `test_index`. ↵
↵
Please note that if you are working with the Polygon system, in this case, you need to write something like `multigen a b c > {4-10}` in the script (if it is assumed that starting the multiple-test generator will return tests 4, 5, 6, 7, 8, 9, and 10).↵
↵
Other notes about generators↵
----------------------------↵
↵
- Strictly follow the format of the test — spaces and line breaks should be placed correctly. The test should end with a line feed. For example, if the test consists of a single number, then output it as `cout << rnd.next (1, n) << endl;` — with a line feed at the end.↵
- If the test size is large, it is prefered to use `printf` instead of `cout` — this will improve the performance of the generator.↵
- It is better to use `cout` to output `long long`, but if you want `printf`, then use the `I64` constant (for example, `printf(I64, x);`).↵
- Please be awared about various cases of C++ [undefined behavior](https://e...content-available-to-author-only...a.org/wiki/Undefined_behavior). For example, in the first example generator above, if the two `cout` commands are combined into one, the order of the `rnd.next` function calls is not defined.↵
↵
_Translator's note: about the third point, using `lld` constant with `printf` to output `long long` used to be problematic in the past, but is no longer an issue now._↵
↵
Further examples↵
----------------↵
↵
Further examples of generators can be found in the [release notes](https://g...content-available-to-author-only...b.com/MikeMirzayanov/testlib/releases) or directly at [the GitHub repository](https://g...content-available-to-author-only...b.com/MikeMirzayanov/testlib/tree/master/generators).
