Sequence generators

Defines a set of sequences, subject to restrictions. More...

Classes
struct	tgen::sequence< T >
	Sequence generator. More...

Functions
	tgen::sequence< T >::sequence (int size, T value_l, T value_r)
	Creates sequence generator define by size and range of values.
	tgen::sequence< T >::sequence (int size, std::set< T > values)
	Creates sequence generator define by value set.
sequence &	tgen::sequence< T >::set (int idx, T value)
	Restricts generator s.t. value at index is fixed.
sequence &	tgen::sequence< T >::equal (int idx_1, int idx_2)
	Restricts generator s.t. values at two indices are the same.
sequence &	tgen::sequence< T >::equal_range (int left, int right)
	Restricts generator s.t. all values at index range are the same.
sequence &	tgen::sequence< T >::distinct (std::set< int > indices)
	Restricts generator s.t. all values at index set are distinct.
sequence &	tgen::sequence< T >::different (int idx_1, int idx_2)
	Restricts generator s.t. values at two indices are different.
sequence &	tgen::sequence< T >::distinct ()
	Restricts generator s.t. all values are distinct.
instance	tgen::sequence< T >::gen () const
	Generates a random instance from the set of valid sequences.
template<typename T, typename Gen, typename Pred>
instance	tgen::sequence< T >::gen_until (Pred predicate, int max_tries) const
	Generates a random instance from the set of valid sequences until a condition is met.

Detailed Description

Defines a set of sequences, subject to restrictions.

A uniformly random tgen::sequence::instance (see Sequence instances) from this set of sequences (that satisfies the restrictions) can be generated with tgen::sequence::gen.

Function Documentation

different()

template<typename T>

sequence & tgen::sequence< T >::different ( int idx_1, int idx_2 )

inline

Restricts generator s.t. values at two indices are different.

Parameters

idx_1	First index.
idx_2	Second index.

Equivalent to tgen::sequence::distinct({idx_1, idx_2}).

Examples

// Sequences of 10 ints from 1 to 5 with the first and last values different.
auto seq_gen = tgen::sequence<int>(10, 1, 5).different(0, 9);

Definition at line 707 of file tgen.h.

distinct() [1/2]

template<typename T>

sequence & tgen::sequence< T >::distinct ( )

inline

Restricts generator s.t. all values are distinct.

Equivalent to tgen::sequence::distinct({0, 1, ... size-1}).

Note

If you add this restriction, do not add another tgen::sequence::distinct restriction! Generation might fail otherwise.

Examples

// Sequences of 5 distinct ints from 1 to 5.
auto seq_gen = tgen::sequence<int>(5, 1, 5).distinct();

Definition at line 713 of file tgen.h.

distinct() [2/2]

template<typename T>

sequence & tgen::sequence< T >::distinct ( std::set< int > indices )

inline

Restricts generator s.t. all values at index set are distinct.

Parameters

indices

Index set.

Note

Generation might fail if restrictions are considered to be too complex! The restrictions are considered too complex if the following condition does not hold. Consider the graph defined with vertices as the tgen::sequence::distinct sets added, and there is an edge between two vertices if they share an index. Note that you need to consider indices (directed or indirectly) connected by equality constraints as being the same. This resulting graph must be a acyclic. Moreover, for every tree in this graph, all of its indices with a tgen::sequence::set operation must be covered by a single distinct constraint set.

Examples

// Sequences of 10 ints from 1 to 5 with the first half distinct.
auto seq_gen = tgen::sequence<int>(10, 1, 5).distinct({0, 1, 2, 3, 4});

Definition at line 700 of file tgen.h.

equal()

template<typename T>

sequence & tgen::sequence< T >::equal ( int idx_1, int idx_2 )

inline

Restricts generator s.t. values at two indices are the same.

Parameters

idx_1	First index.
idx_2	Second index.

Examples

// Sequences of 10 ints from 1 to 5 that start and end with the same value.
auto seq_gen = tgen::sequence<int>(10, 1, 5).equal(0, 9);

Definition at line 676 of file tgen.h.

equal_range()

template<typename T>

sequence & tgen::sequence< T >::equal_range ( int left, int right )

inline

Restricts generator s.t. all values at index range are the same.

Parameters

left	Left endpoint of index range.
right	Right endpoint of index range.

Examples

// Sequences of 10 ints from 1 to 5 with the first half all equal.
auto seq_gen = tgen::sequence<int>(10, 1, 5).equal_range(0, 4);

Definition at line 689 of file tgen.h.

gen()

template<typename T>

instance tgen::sequence< T >::gen ( ) const

inline

Generates a random instance from the set of valid sequences.

Returns

A uniformly random instance from the set of valid sequences, given the added constraints.

Exceptions

std::runtime_error

if there is no valid sequence satisfying all added constraints, or if the added constraints are considered to be too complex (see tgen::sequence::distinct).

Complexity

O(n log n).

Examples

// Generates and prints a random sequence of 5 ints from 1 to 5.
auto inst = tgen::sequence<int>(5, 1, 5).gen();
std::cout << inst << std::endl;

Definition at line 828 of file tgen.h.

gen_until()

template<typename T, typename Gen, typename Pred>

instance gen_until	(	Pred	predicate,
		int	max_tries ) const

Generates a random instance from the set of valid sequences until a condition is met.

Template Parameters

Gen	Automatically set to tgen::sequence<T>.
Pred	Type of predicate, deduced automatically.

Parameters

predicate	Condition to be checked. Should be a function that takes in a tgen::sequence::instance, and returns a bool.
max_tries	The maximum number of times the function will try to generate a valid instance satisfying predicate.

If predicate has probabiliyy p of returning true, then the tgen::sequence::instance will be found with probability 1 - (1-p)^max_tries.

Returns

An instance found by repeatedly choosing a uniformly random valid sequence and checking if it satisfies predicate.

Exceptions

std::runtime_error

if no valid instance satisfying predicate is found after max_tries tries.

Complexity

O((1/p) n log n) expected, O(max_tries * n log n) worst case.

Examples

// Prints a sequence of 10 distinct ints from 1 to 10 such that the first element is larger than the last.
std::cout <<
    tgen::sequence<int>(10, 1, 10)
        .distinct()
        .gen_until([](const auto &seq) { return seq[0] < seq[9]; }, 100)
  << std::endl;

sequence() [1/2]

template<typename T>

tgen::sequence< T >::sequence ( int size, std::set< T > values )

inline

Creates sequence generator define by value set.

Parameters

size	Size of the sequence.
values	Value set.

Defines a generator of sequences of length size with values in values.

Examples

// Sequences of 10 ints that are either 3, 6, or 9.
auto seq_gen = tgen::sequence<int>(10, std::set<int>({3, 6, 9}));

Definition at line 638 of file tgen.h.

sequence() [2/2]

template<typename T>

tgen::sequence< T >::sequence ( int size, T value_l, T value_r )

inline

Creates sequence generator define by size and range of values.

Parameters

size	Size of the sequence.
value_l	Left endpoint of value range.
value_r	Right endpoint of value range.

Defines a generator of sequences of length size with values in [value_l, value_r].

Examples

// Sequences of 10 ints from 1 to 100.
auto seq_gen = tgen::sequence<int>(10, 1, 100);

Definition at line 629 of file tgen.h.

set()

template<typename T>

sequence & tgen::sequence< T >::set ( int idx, T value )

inline

Restricts generator s.t. value at index is fixed.

Parameters

idx	Index.
value	Value.

Exceptions

std::runtime_error

if value is not in the value range/set.

Examples

// Sequences of 10 ints from 1 to 5 that start with 1.
auto seq_gen = tgen::sequence<int>(10, 1, 5).set(0, 1);

Definition at line 651 of file tgen.h.