tgen

Testcase generation for random inputs.

Overview

tgen is a C++ library to help you generate random stuff, useful for testcase generation (such as jngen or testlib). The code is in a single file tgen.h, that should be added to your directory.

#include "tgen.h"

The first thing is to register the generator. That defines the seed for random generation and parses the opts.

tgen uses a global RNG and generator registry; register_gen and subsequent generation are not thread-safe. Use one generator instance per process (or external synchronization) in multi-threaded programs.

There are:

• Base operations
• Math operations
• Geometry operations
• Hacks (adversarial generation)
• Miscellaneous operations

and operations for specific data types:

• Pairs
• Lists
• Permutations
• Strings
• Trees
• Graphs

Selected operations have benchmarks.

Type generators and values

List, string, permutation, pair, and graph generators describe a set of valid values under constraints. Calling gen() on such a generator samples uniformly at random among valid values (where the API documents uniformity). Static helpers such as gen_skewed, get_connected, geometry primitives, and gen_partition_fixed_size_fast are intentionally not uniformly random; see each function's documentation.

Let's see an example with tgen::list:

tgen::list<int> t = tgen::list<int>(/*size=*/10, /*value_left=*/1, /*value_right=*/100);

This will create a list generator representing the set of all lists with 10 values from 1 to 100.

Every generator of type Gen has a method gen(), that returns a Gen::value from the set of valid elements for the current restrictions. For constraint-based generators, gen() is uniformly random over that set. A Gen::value can be fed to std::cout to be printed.

In our example, we can call gen() to generate and print a random list of 10 elements from 1 to 100.

std::cout << t.gen() << std::endl;

The nice thing is that we can add restrictions (specific to each type) to the generator, shrinking the set of valid lists. For example, we can add the restriction that the first and second elements of the list have to be the same.

tgen::list<int>::value inst = t.equal(/*idx_1=*/0, /*idx_2=*/1).gen();

The returned value can also be modified by some deterministic operations (specific to each type).

inst.reverse();

Finally, there can also be random operations.

std::cout << inst.pick() << std::endl;

Combining everything into one line:

std::cout << tgen::list<int>(10, 1, 100)
                 .equal(0, 1)
                 .gen()
                 .reverse()
                 .pick()
          << std::endl;

Complexity notation

Documented time complexities treat associative-container operations as O(log n), as with std::map and std::set. Some implementations use std::unordered_map or std::unordered_set for performance; the stated bounds are unchanged (we do not use O(1) average-case notation for those paths).

Union-find (detail::dsu) find and unite are documented as O(alpha(n)) amortized per operation (inverse Ackermann), not O(1).

Examples

Opts configuration

#include "tgen.h"
 
#include <iostream>
 
int main(int argc, char** argv) {
    tgen::register_gen(argc, argv);
 
    int n_max = tgen::opt<int>("n");
 
    std::cout << tgen::next(1, n_max) << std::endl;
}

Calling this code with ./a.out -n 100 will generate a random number from 1 to 100.

Generation

Random 20 distinct values from 1 to 100.

std::cout <<
    tgen::list<int>(20, 1, 100).all_different().gen() << std::endl;

67 96 80 11 46 52 42 2 93 1 28 3 48 82 90 99 53 98 94 88

Skewed connected graph on 10 vertices and 15 edges.

std::cout << tgen::graph::gen_skewed(10, 15, 100, 2);

0 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
1 3
6 8
7 9
5 7
4 6
2 4

Generated graph

Random palindrome of length 7.

std::cout << tgen::str(7, 'a', 'z').palindrome().gen() << std::endl;

iczpzci

Random 3 runs of 4 equal numbers. Values between runs are different.

std::cout <<
    tgen::list<int>(12, 1, 10)
    .equal_range(0, 3).equal_range(4, 7).equal_range(8, 11)
    .different({0, 4, 8}).gen() << std::endl;

3 3 3 3 2 2 2 2 9 9 9 9

Random DNA sequence of length 8 with no equal adjacent values.

auto s2 = tgen::list<char>(8, {'A','C','G','T'});
for (int i = 1; i < 8; i++) s2.different(i - 1, i);
std::cout << s2.gen() << std::endl;

T C T G T G A C

Random binary sequence of length 10 with 5 1's that starts with 1.

std::cout <<
    tgen::list<int>(10, 0, 1)
    .fix(0, 1)
    .gen_until([](const auto& inst) {
        auto vec = inst.to_std();
        return std::accumulate(vec.begin(), vec.end(), 0) == 5;
    }, 100) << std::endl;

1 0 0 1 0 1 1 0 1 0

Generates a simple polygon given coordinate range.

auto poly = tgen::geometry::random_simple_polygon(200, 0, 2000);
std::cout << tgen::print(poly, '\n') << std::endl;

 * 842 368
 * 847 379
...

Example generated polygon

Random 1-based permutation of size 5 with only one cycle.

std::cout << tgen::permutation(5).cycles({5}).gen().add_1() << std::endl;

2 5 4 1 3

Inverse of a random odd permutation of size 5.

std::cout << tgen::permutation(5)
    .gen_until([](const auto &perm) { return perm.parity() == -1; }, 100)
    .inverse() << std::endl;

4 2 3 1 0

Random prime in [1, 1e18].

std::cout << tgen::math::gen_prime(1, 1e18) << std::endl;

104297037245455381

Largest prime gap that fits in uint64_t.

auto [l, r] = tgen::math::prime_gap_upto(std::numeric_limits<uint64_t>::max());
std::cout << l << " " << r << " " << r - l << std::endl;

6787988999657777798 6787988999657779306 1508

Random partition of 10 into 2 parts in [3, 7].

std::cout << tgen::print(tgen::math::gen_partition_fixed_size(10, 2, 3, 7)) << std::endl;

6 4

Random numbers in [0, 1e30].

std::cout << tgen::str("0 | [1-9][0-9]{0,%d} | 10{%d}", 30 - 1, 30).gen_list(3) << std::endl;

395192209976851520716904879188 507650968099964477977292350849 549612473618635975427061717252

Random perfect matching of K_10.

auto g = tgen::distinct([&]() { return tgen::next(0, 9); });
for (int i = 0; i < 5; ++i)
    std::cout << g.gen() << "," << g.gen() << " ";

9,5 3,1 0,4 7,6 8,2 

All primes in [1, 10], in order.

std::cout << tgen::distinct(tgen::math::gen_prime, 1, 10).gen_all().sort() << std::endl;

2 3 5 7

5 random square numbers in [1, 1e4].

std::cout << tgen::distinct([&]() {
    int x = tgen::next(1, 100);
    return x * x;
}).gen_list(5) << std::endl;

676 1936 484 3481 9604

Some random parenthesis sequences.

std::cout << tgen::distinct(tgen::misc::gen_parenthesis, 6).gen_list(5) << std::endl;

()(()) (())() (()()) ((())) ()()()

All pairs (a, b) in [1, 3] with a <= b.

std::cout << tgen::pair<int>(1, 3).leq().distinct().gen_all().separator('|') << std::endl;

1 3|1 2|3 3|1 1|2 2|2 3