Rose::Combinatorics Namespace Reference

Description

Combinatoric functions.

Classes
class	Hasher
	Hash interface. More...
class	HasherFnv
	Fowler-Noll-Vo hashing using the Hasher interface. More...
class	HasherGcrypt
	Hasher for any libgcrypt hash algorithm. More...
class	HasherSha256Builtin
	Built-in SHA-256 hasher. More...

Typedefs
typedef HasherGcrypt< 0 >	HasherMd5
	MD5 hasher.
typedef HasherGcrypt< 0 >	HasherSha1
	SHA1 hasher.
typedef HasherGcrypt< 0 >	HasherSha256
	SHA-256 hasher.
typedef HasherGcrypt< 0 >	HasherSha384
	SHA-384 hasher.
typedef HasherGcrypt< 0 >	HasherSha512
	SHA-512 hasher.
typedef HasherGcrypt< 0 >	HasherCrc32
	ISO 3309 hasher.

Functions
ROSE_DLL_API bool	flip_coin ()
	Simulate flipping a coin.
template<typename T >
void	shuffle (std::vector< T > &vector, size_t nitems=UNLIMITED, size_t limit=UNLIMITED)
	Shuffle the values of a vector.
template<class T >
void	reorder (std::vector< T > &values, const std::vector< size_t > &remap)
	Reorder the values of one vector according to another.
ROSE_DLL_API std::string	toBase62String (uint64_t num)
	Converts a 64 bit in to base 62 (All letters and numbers).
ROSE_DLL_API uint64_t	fromBase62String (const std::string &base62)
	Converts a base-62 (All letters and numbers) number to a 64 bit int.
template<class T , class U >
std::vector< std::pair< T, U > >	zip (const std::vector< T > &first, const std::vector< U > &second)
	Convert two vectors to a vector of pairs.
template<class T , class U >
std::pair< std::vector< T >, std::vector< U > >	unzip (const std::vector< std::pair< T, U > > &pairs)
	Convert a vector of pairs to a pair of vectors.

Typedef Documentation

HasherMd5

typedef HasherGcrypt<0> Rose::Combinatorics::HasherMd5

MD5 hasher.

Throws exception if libgcrypt is not configured.

Definition at line 447 of file Combinatorics.h.

HasherSha1

typedef HasherGcrypt<0> Rose::Combinatorics::HasherSha1

SHA1 hasher.

Throws exception if libgcrypt is not configured.

Definition at line 448 of file Combinatorics.h.

HasherSha256

typedef HasherGcrypt<0> Rose::Combinatorics::HasherSha256

SHA-256 hasher.

Throws exception if libgcrypt is not configured.

Definition at line 449 of file Combinatorics.h.

HasherSha384

typedef HasherGcrypt<0> Rose::Combinatorics::HasherSha384

SHA-384 hasher.

Throws exception if libgcrypt is not configured.

Definition at line 450 of file Combinatorics.h.

HasherSha512

typedef HasherGcrypt<0> Rose::Combinatorics::HasherSha512

SHA-512 hasher.

Throws exception if libgcrypt is not configured.

Definition at line 451 of file Combinatorics.h.

HasherCrc32

typedef HasherGcrypt<0> Rose::Combinatorics::HasherCrc32

ISO 3309 hasher.

Throws exception if libgcrypt is not configured.

Definition at line 452 of file Combinatorics.h.

Function Documentation

flip_coin()

ROSE_DLL_API bool Rose::Combinatorics::flip_coin

(

)

Simulate flipping a coin.

Randomly returns true or false with equal probability.

shuffle()

template<typename T >

void Rose::Combinatorics::shuffle	(	std::vector< T > &	vector,
		size_t	nitems = UNLIMITED,
		size_t	limit = UNLIMITED
	)

Shuffle the values of a vector.

This algorithm randomly shuffles the items in the vector by swapping values at indexes zero through limit with values at randomly selected indexes zero through nitems. The defaults for nitems and limit are the size of the input vector.

Definition at line 77 of file Combinatorics.h.

References Sawyer::fastRandomIndex().

reorder()

template<class T >

void Rose::Combinatorics::reorder	(	std::vector< T > &	values,
		const std::vector< size_t > &	remap
	)

Reorder the values of one vector according to another.

The second vector says how the first vector is rearranged. The argument values are the values to be reordered, and the argument remap says how to reorder them. Both arguments must be the same length, n. The remap argument contains all the integer indices from 0 (inclusive) to n (exclusive). If the values in their original order are named "old" and the values in their new desired order are named "new", then new[i] = old[remap[i]].

This function is useful when sorting parallel arrays. Say we have three parallel arrays named a, b, and c and we want to sort them all so array a is in ascending order according to its natural less-than operator. We could do that as follows:

std::vector<ValueA> a = { ... };
std::vector<ValueB> b = { ... };
std::vector<ValueC> c = { ... };
 
std::vector<size_t> remap(a.size());
std::iota(remap.begin(), remap.end(), 0);
std::sort(remap.begin(), remap.end(), [&a](const size_t i, const size_t j) {
    return a[i] < a[j];
});
 
reorder(a, remap);
reorder(b, remap);
reorder(c, remap);

Definition at line 115 of file Combinatorics.h.

toBase62String()

ROSE_DLL_API std::string Rose::Combinatorics::toBase62String

(

uint64_t

num

)

Converts a 64 bit in to base 62 (All letters and numbers).

This is the most compressed format that can be used for a C++ identifier.
(Although C++ identifiers can not start with a digit, so to use it for one you need to prepend a letter or "_")

Referenced by SageInterface::addMangledNameToCache().

fromBase62String()

ROSE_DLL_API uint64_t Rose::Combinatorics::fromBase62String

(

const std::string &

base62

)

Converts a base-62 (All letters and numbers) number to a 64 bit int.

Base-62 is used to store hashes in the most efficient was that can also be a C++ identifier. Converting back to a uint64 is not generally required, but here's a function to do so.

zip()

template<class T , class U >

std::vector< std::pair< T, U > > Rose::Combinatorics::zip	(	const std::vector< T > &	first,
		const std::vector< U > &	second
	)

Convert two vectors to a vector of pairs.

If the two input vectors are not the same length, then the length of the result is the length of the shorter input vector.

Definition at line 491 of file Combinatorics.h.

unzip()

template<class T , class U >

std::pair< std::vector< T >, std::vector< U > > Rose::Combinatorics::unzip

(

const std::vector< std::pair< T, U > > &

pairs

)

Convert a vector of pairs to a pair of vectors.

Definition at line 503 of file Combinatorics.h.