ROSE 0.11.145.277
Classes | Typedefs | Functions
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)
 Converts a 64 bit int to base 62.
 
ROSE_DLL_API uint64_t fromBase62String (const std::string &base62)
 Converts a base 62 string 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

MD5 hasher.

Throws exception if libgcrypt is not configured.

Definition at line 433 of file Combinatorics.h.

◆ HasherSha1

SHA1 hasher.

Throws exception if libgcrypt is not configured.

Definition at line 434 of file Combinatorics.h.

◆ HasherSha256

SHA-256 hasher.

Throws exception if libgcrypt is not configured.

Definition at line 435 of file Combinatorics.h.

◆ HasherSha384

SHA-384 hasher.

Throws exception if libgcrypt is not configured.

Definition at line 436 of file Combinatorics.h.

◆ HasherSha512

SHA-512 hasher.

Throws exception if libgcrypt is not configured.

Definition at line 437 of file Combinatorics.h.

◆ HasherCrc32

ISO 3309 hasher.

Throws exception if libgcrypt is not configured.

Definition at line 438 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 78 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);
void reorder(std::vector< T > &values, const std::vector< size_t > &remap)
Reorder the values of one vector according to another.

Definition at line 115 of file Combinatorics.h.

◆ toBase62String()

ROSE_DLL_API std::string Rose::Combinatorics::toBase62String ( uint64_t  )

Converts a 64 bit int to base 62.

The symbols in base 62 are the digits '0' through '9', followed by the upper-case letters 'A' through 'Z', followed by the lower-case letters 'a' through 'z' (62 symbols in total). Note that this order is not the same as Base64 (RFC 4648).

The return value is useful as the non-leading part of a C++ identifier. It cannot serve as the beginning (or complete) identifier because the return value might start with characters that are not valid for the start of a C++ identifier (i.e, the digits '0' through '9').

The return value is not even close to being the most compressed format for an identifier since there are approximately 760 valid characters that can occur at the start and within a C++ identifier. But it does return strings that are almost the most compact for the set of valid ASCII characters.

Referenced by SageInterface::addMangledNameToCache().

◆ fromBase62String()

ROSE_DLL_API uint64_t Rose::Combinatorics::fromBase62String ( const std::string &  base62)

Converts a base 62 string to a 64 bit int.

The symbols in base 62 are the digits '0' through '9', followed by the upper-case letters 'A' through 'Z', followed by the lower-case letters 'a' through 'z' (62 symbols in total).

Base 62 is used to store hashes in a way that can also almost be a C++ identifier, although base 62 can start with the digits '0' through '9' which are not valid first characters for a C++ identifier.

◆ 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 477 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 489 of file Combinatorics.h.