tgen::str

String generator. More...

Inheritance diagram for tgen::str:

Classes
struct	instance
	String instance. More...

Public Member Functions
	str (int size, char value_l='a', char value_r='z')
	Creates string generator define by size and range of characters.
	str (int size, std::set< char > chars)
	Creates string generator define by character set.
template<typename... Args>
	str (const std::string &regex, Args &&...args)
	Creates string generator define by regex.
str &	fix (int idx, char character)
	Restricts generator s.t. character at index is fixed.
str &	equal (int idx_1, int idx_2)
	Restricts generator s.t. values at two indices are the same.
str &	equal_range (int left, int right)
	Restricts generator s.t. all values at index range are the same.
str &	palindrome (int left, int right)
	Restricts generator s.t. range is a palindrome.
str &	palindrome ()
	Restricts generator s.t. string is a palindrome.
str &	distinct (std::set< int > indices)
	Restricts generator s.t. all characters in index set are distinct.
str &	different (int idx_1, int idx_2)
	Restricts generator s.t. characters at two indices are different.
str &	distinct ()
	Restricts generator s.t. all characters are distinct.
instance	gen () const
	Generates a random instance from the set of valid strings.
Public Member Functions inherited from tgen::gen_base< str >
auto	gen_list (int size, Args &&...args) const
	Generates a list of several generation calls.
auto	gen_until (Pred predicate, int max_tries, Args &&...args) const
	Generates a random instance from the valid set until a condition is met.
auto	unique (Args &&...args) const
	Creates unique generator for current generator.

Static Public Member Functions
static instance	abacaba (int n)
	Returns the prefix of the infinite word "abacabad...".
static std::pair< instance, instance >	unsigned_polynomial_hash_hack ()
	Returns two strings that force polynomial hash collision for power-of-two mod.
static std::pair< instance, instance >	polynomial_hash_hack (int alphabet_size, int base, int mod)
	Returns two strings that force polynomial hash collision given base and mod.
static std::pair< instance, instance >	polynomial_hash_hack (int alphabet_size, std::vector< int > bases, std::vector< int > mods)
	Returns two strings that force polynomial hash collision given bases and mods.

Detailed Description

String generator.

Defines a set of strings, subject to restrictions.

A uniformly random tgen::str::instance from this set of strings (that satisfies the restrictions) can be generated with tgen::str::gen.

Definition at line 3055 of file tgen.h.

Constructor & Destructor Documentation

str() [1/3]

tgen::str::str ( int size, char value_l = 'a', char value_r = 'z' )

inline

Creates string generator define by size and range of characters.

Parameters

size	Size of the string.
value_l	Left endpoint of character range.
value_r	Right endpoint of character range.

Defines a generator of strings of length size with characters in [value_l, value_r].

Examples

// Strings of lowercase letters of size 10.
auto str_gen = tgen::str(10, 'a', 'z');

Definition at line 3062 of file tgen.h.

str() [2/3]

tgen::str::str ( int size, std::set< char > chars )

inline

Creates string generator define by character set.

Parameters

size	Size of the string.
chars	Character set.

Defines a generator of strings of length size with characters in chars.

Examples

// Strings size 10 with characters that are either 'a', 'e', or 'i'.
auto seq_gen = tgen::str(10, {'a', 'e', 'i'});

Definition at line 3067 of file tgen.h.

str() [3/3]

template<typename... Args>

tgen::str::str ( const std::string & regex, Args &&... args )

inline

Creates string generator define by regex.

Parameters

regex	Regex.
args	Arguments for the regex.

Defines a generator of strings generated by regex (see Strings), with the given args.

Examples

// Numbers from from 0 up to 10^30.
auto leq1e30 = tgen::str("0 | [1-9][0-9]{0,%d} | 10{%d}", 30-1, 30);

Definition at line 3070 of file tgen.h.

Member Function Documentation

abacaba()

instance tgen::str::abacaba ( int n )

inlinestatic

Returns the prefix of the infinite word "abacabad...".

Parameters

n	Length of the prefix.

Returns

A tgen::str::instance with the prefix of length n of "abacabad...".

Complexity

O(n).

Examples

// Prints "abacaba".
std::cout << tgen::str::abacaba(7) << std::endl;

Definition at line 3229 of file tgen.h.

different()

str & tgen::str::different ( int idx_1, int idx_2 )

inline

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

Parameters

idx_1	First index.
idx_2	Second index.

Exceptions

std::runtime_error

if the generator was created from a regex (restrictions cannot be added for regex).

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

Examples

// Strings of 10 lowercase letters with the first and last characters different.
auto str_gen = tgen::str(10, 'a', 'z').different(0, 9);

Definition at line 3123 of file tgen.h.

distinct() [1/2]

str & tgen::str::distinct ( )

inline

Restricts generator s.t. all characters are distinct.

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

Note

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

Exceptions

std::runtime_error

if the generator was created from a regex (restrictions cannot be added for regex).

Examples

// Strings consisting of 10 distinct lowercase letters.
auto s = tgen::str(10, 'a', 'z').distinct();

Definition at line 3130 of file tgen.h.

distinct() [2/2]

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

inline

Restricts generator s.t. all characters in 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::str::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 restrictions 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::str::set operation must be covered by a single distinct restriction set.

Exceptions

std::runtime_error

if the generator was created from regex (restrictions cannot be added for regex).

Examples

// Strings of 10 lowercase letters with first 3 characters distinct.
auto str_gen = tgen::str(10, 'a', 'z').distinct({0, 1, 2});

Definition at line 3116 of file tgen.h.

equal()

str & tgen::str::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.

Exceptions

std::runtime_error

if the generator was created from a regex (restrictions cannot be added for regex).

Examples

// Strings of 7 lowercase letters that start and end with the same character.
auto str_gen = tgen::str(7, '0', '9').equal(0, 6);

Definition at line 3085 of file tgen.h.

equal_range()

str & tgen::str::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 (inclusive).
right	Right endpoint of index range (inclusive).

Exceptions

std::runtime_error

if the generator was created from a regex (restrictions cannot be added for regex).

Examples

// Strings of 10 lowercase letters with a run of 4 equal characters at the start.
auto str_gen = tgen::str(10, 'a', 'z').equal_range(0, 3);

Definition at line 3092 of file tgen.h.

fix()

str & tgen::str::fix ( int idx, char character )

inline

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

Parameters

idx	Index.
character	Character.

Exceptions

std::runtime_error

if the generator was created from a regex (restrictions cannot be added for regex).

Examples

// Strings of 5 lowercase letters starting with 'x'.
auto str_gen = tgen::str(5, 'a', 'z').fix(0, 'x');

Definition at line 3078 of file tgen.h.

gen()

instance tgen::str::gen ( ) const

inline

Generates a random instance from the set of valid strings.

Returns

A uniformly random tgen::str::instance satisfying the restrictions, or (for regex generators) a random match according to the regex semantics described in Strings.

Note

For regex, the generation is only guaranteed to be uniform if there is a unique way to generate each string generated by the regex (see Strings).

Exceptions

std::runtime_error

if there is no valid string satisfying all restrictions.

Complexity

If created from restrictions: O(n log n).

If created from regex: expected linear.

Examples

// Prints a random number from 0 to 10^3.
std::cout << tgen::str("0 | [1-9][0-9]{0,%d} | 10{%d}", 3-1, 3).gen() << std::endl;

Definition at line 3214 of file tgen.h.

palindrome() [1/2]

str & tgen::str::palindrome ( )

inline

Restricts generator s.t. string is a palindrome.

Exceptions

std::runtime_error

if the generator was created from a regex (restrictions cannot be added for regex).

Examples

// Palindromes of 10 lowercase letters.
auto str_gen = tgen::str(10, 'a', 'z').palindrome();

Definition at line 3109 of file tgen.h.

palindrome() [2/2]

str & tgen::str::palindrome ( int left, int right )

inline

Restricts generator s.t. range is a palindrome.

Parameters

left	Left endpoint of the index range (inclusive).
right	Right endpoint of the index range (inclusive).

Exceptions

std::runtime_error

if the generator was created from a regex (restrictions cannot be added for regex).

Examples

// Strings of 10 lowercase letters that are the concatenation of two length 5 palindromes.
auto str_gen = tgen::str(10, 'a', 'z').palindrome(0, 4).palindrome(5, 9);

Definition at line 3099 of file tgen.h.

polynomial_hash_hack() [1/2]

std::pair< instance, instance > tgen::str::polynomial_hash_hack ( int alphabet_size, int base, int mod )

inlinestatic

Returns two strings that force polynomial hash collision given base and mod.

Parameters

alphabet_size	Alphabet size.
base	Base.
mod	Mod.

Precondition

0 < base < mod

Computes two strings that have the same polynomial hash for given base and mod.
Characters are in [a, a + alphabet_size).

Returns

A std::pair<instance, instance> with the colided strings.

Reference:

• On the mathematics behind rolling hashes and anti-hash tests: Composition-attack: Multiple hashes

Complexity

O(sqrt(mod) log mod).

Examples

// Prints polynomial hash hack.
std::cout << tgen::print(tgen::str::polynomial_hash_hack(2, 31, 1e9+7), '\n') << std::endl;

Definition at line 3261 of file tgen.h.

polynomial_hash_hack() [2/2]

std::pair< instance, instance > tgen::str::polynomial_hash_hack ( int alphabet_size, std::vector< int > bases, std::vector< int > mods )

inlinestatic

Returns two strings that force polynomial hash collision given bases and mods.

Parameters

alphabet_size	Alphabet size.
bases	Bases.
mods	Mods.

Precondition

|bases| = |mods|.
0 < bases[i] < mods[i].

Computes two strings that have the same polynomial hash for given bases and mods, up to 2 (base, mod) pairs.
Characters are in [a, a + alphabet_size).

Returns

A std::pair<instance, instance> with the colided strings.

Reference:

• On the mathematics behind rolling hashes and anti-hash tests: Composition-attack: Multiple hashes

Complexity

O(sqrt(mod) log^2 mod), with mod = max(mods).

Examples

// Prints polynomial hash hack for double hash.
std::cout << tgen::print(tgen::str::polynomial_hash_hack(2, {31, 33}, {1000000007, 1000000009}), '\n') << std::endl;

Definition at line 3278 of file tgen.h.

unsigned_polynomial_hash_hack()

std::pair< instance, instance > tgen::str::unsigned_polynomial_hash_hack ( )

inlinestatic

Returns two strings that force polynomial hash collision for power-of-two mod.

Computes two strings that have the same polynomial hash for any base and power-of-two mod (up to 2^64).
Characters are in [a, b].

Returns

A std::pair<instance, instance> with the colided strings.

Reference:

• On the mathematics behind rolling hashes and anti-hash tests: Thue–Morse sequence: Hashing with unsigned overflow (p = 2^64, q arbitrary).

Complexity

O(1).

Examples

// Prints unsined polynomial hash hack.
std::cout << tgen::print(tgen::str::unsigned_polynomial_hash_hack()) << std::endl;

Definition at line 3247 of file tgen.h.

---

The documentation for this struct was generated from the following files:

• /home/runner/work/tgen/tgen/single_include/tgen.h
• str.dox