Namespace mata::utils

namespace utils

SparseSet.h Implements a class template of a sparse set of unsigned integers.

Non-automata-related structures and algorithms.

In particular, this includes:

  1. Predicates,

  2. Ordered Vectors,

  3. Iterators,

  4. Printers,

  5. Other helper functions.

Author

Sam Griffiths www.computist.xyz https://gist.github.com/sjgriffiths/06732c6076b9db8a7cf4dfe3a7aed43a

Functions

template<class T>
bool are_disjoint(const utils::OrdVector<T> &lhs, const utils::OrdVector<T> &rhs)
template<class Key>
bool is_sorted(const std::vector<Key> &vec)
template<class Container>
void push_back(SynchronizedIterator<typename Container::const_iterator> &i, const Container &container)

In order to make initialisation of the sync.

iterator nicer than inputting v.begin() and v.end() as the two parameters of the method push_back, this function wraps the method push_back, takes the iterator and v and extracts the v.begin() and v.end() from v.

inline std::string replace_all(const std::string &input, const std::string &needle, const std::string &replace)

Replace all occurrences of a substring in a string.

Parameters:

  • input – The input string

  • needle – The substring to be replaced

  • replace – The replacement string

Returns:

A new string with all occurrences of the substring replaced.

template<class T>
bool are_disjoint(const std::set<T> &lhs, const std::set<T> &rhs)

Are two sets disjoint?

template<class T, class Cont>
bool is_in(const T &elem, const Cont &cont)

Is there an element in a container?

template<class T>
inline size_t hash_combine(size_t lhs, const T &rhs)

Combine two hash values.

Values taken from http://www.boost.org/doc/libs/1_64_0/boost/functional/hash/hash.hpp

TODO: fix to be more suitable for 64b

template<typename It>
size_t hash_range(It first, It last)

Hashes a range.

Inspired by http://www.boost.org/doc/libs/1_64_0/boost/functional/hash/hash.hpp

template<class T, class K>
inline bool haskey(const T &cont, const K &key)

checks whether a container with find contains a key

template<template<class, class, class...> class Map, class T1, class T2, class ...Args>
Map<T2, T1> invert_map(const Map<T1, T2> &mp)

inverts a map (should work for std::map and std::unordered_map)

template<class Vector>
inline void reserve_on_insert(Vector &vec, size_t needed_capacity = 0, size_t extension = 32)
template<class Vector, typename Index>
void defragment(Vector &vec, const std::vector<Index> &renaming)
template<class Vector, typename Index>
void rename(Vector &vec, const std::vector<Index> &renaming)
template<class Vector, typename Fun>
void filter_indexes(Vector &vec, const Fun &&is_staying)
template<class Vector, typename Fun>
void filter(Vector &vec, const Fun &&is_staying)
template<class Vector>
inline void sort_and_rmdupl(Vector &vec)
template<class Key>
class OrdVector
#include <ord-vector.hh>

Implementation of a set using ordered vector.

This class implements the interface of a set (the same interface as std::set) using ordered vector as the underlying data structure.

Template Parameters:

Key – Key type: type of the elements contained in the container. Each elements in a set is also its key.

Public Functions

inline OrdVector difference(const OrdVector &rhs) const

Compute set difference as this minus rhs.

Parameters:

rhs – Other vector with symbols to be excluded.

Returns:

this minus rhs.

inline bool contains(const Key &key) const

Check whether key exists in the ordered vector.

inline size_t erase(const Key &k)

Remove k from sorted vector.

This function expects the vector to be sorted.

inline virtual reference back()

Get reference to the last element in the vector.

Modifying the underlying value in the reference could break sortedness.

Public Static Functions

static inline OrdVector with_reserved(const size_t capacity)

Create OrdVector with reserved capacity.

Parameters:

capacity – [in] Capacity of OrdVector to reserve.

Returns:

Newly create OrdVector.

Friends

inline friend std::ostream &operator<<(std::ostream &os, const OrdVector &vec)

Overloaded << operator.

Overloaded << operator for output stream.

See also

to_str()

Parameters:

  • os – [in] The output stream

  • vec – [in] Assignment to the variables

Returns:

Modified output stream

template<typename Number>
class SparseSet
#include <sparse-set.hh>

Implementation of a set of non-negative numbers using sparse-set.

This class implements the interface of a set (similar to std::set) using sparse-set date structure, that is, a pair of vectors dense and sparse (… google it). Importantly

  • Insertion and removal are constant time.

  • Iteration is linear in the number of stored elements.

  • It takes a lot of space, the sparse and dense vectors allocate as many indexes as the maximal stored number.

Template Parameters:

Number – Number type: type of numbers contained in the container.

Public Functions

inline void erase_nocheck(const Number number)

Erase number from the set without checking for its existence.

Parameters:

number – Number to be erased.

Pre:

number exists in the set.

SparseSet() = default

New Mata code.

inline explicit SparseSet(Number domain_size)

Basic constructor where you may reserve a domain size.

inline bool operator[](Number q) const
Returns:

True if predicate for q is set. False otherwise (even if q is out of range of the predicate).

inline Number max()

Maximal Number in set.

Expensive operation as it has to compute the maximal Number in linear time.

template<typename Iterator>
class SynchronizedExistentialIterator : public mata::utils::SynchronizedIterator<Iterator>
#include <synchronized-iterator.hh>

Public Functions

inline virtual bool advance() override

Advances all positions just above current_minimum, that is, to or above next_minimum.

Those at next_minimum are added to currently_synchronized. Since next_minimum becomes the current minimum, new next_minimum must be updated too.

inline virtual const std::vector<Iterator> &get_current() const override

Returns the vector of current still active positions.

Beware, they will be ordered differently from how there were input into the iterator. This is due to swapping of the emptied positions with positions at the end.

inline virtual void push_back(const Iterator &begin, const Iterator &end) override

This is supposed to be called only before an iteration, after constructor of reset.

Calling after advance breaks the iterator. Specifies begin and end of one vector, to initialise before the iteration starts.

template<typename Iterator>
class SynchronizedIterator
#include <synchronized-iterator.hh>

Synchronized iteration.

Subclassed by SynchronizedExistentialIterator< Iterator >, SynchronizedUniversalIterator< Iterator >

Public Functions

inline explicit SynchronizedIterator(const size_t size = 0)
Parameters:

size – Number of elements to reserve up-front for positions and ends.

inline virtual void push_back(const Iterator &begin, const Iterator &end)

This is supposed to be called only before an iteration, after constructor of reset.

Calling after advance breaks the iterator. Specifies begin and end of one vector, to initialise before the iteration starts.

inline void reset(const size_t size = 0)

Empties positions and ends.

Though they should keep the allocated space.

Parameters:

size – Number of elements to reserve up-front for positions and ends.

template<typename Iterator>
class SynchronizedUniversalIterator : public mata::utils::SynchronizedIterator<Iterator>
#include <synchronized-iterator.hh>

Public Functions

inline virtual bool advance()

Advances all positions to the NEXT minimum and returns true (though the next minimum might be the current state if synchronized_at_current_minimum is false), or returns false if positions cannot be synchronized.

If positions are synchronized to start with, then synchronized_at_current_minimum decides whether to stay or advance further. The general of the algorithm is to synchronize everybody with position[0].

inline virtual const std::vector<Iterator> &get_current() const

Returns the vector of current positions.

inline virtual void push_back(const Iterator &begin, const Iterator &end)

This is supposed to be called only before an iteration, after constructor of reset.

Calling after advance breaks the iterator. Specifies begin and end of one vector, to initialise before the iteration starts.

Public Members

bool synchronized_at_current_minimum = false

“minimum” would be the smallest class bounded from below by all positions that appears in all OrdContainers.

Are we sure that all positions at this class? Invariant: it can be true only if all positions are indeed synchronized.

template<class Tuple, size_t N>
struct TuplePrinter
#include <utils.hh>
template<class Tuple>
struct TuplePrinter<Tuple, 1>
#include <utils.hh>
template<typename T, bool track_inverted = true, size_t MAX_MATRIX_SIZE = 50'000'000>
class TwoDimensionalMap
#include <two-dimensional-map.hh>

A two-dimensional map that can be used to store pairs of values and their associated value.

This class can handle both small and large maps efficiently.

The largest matrix of pairs of we are brave enough to allocate is 50’000’000 for 8 Byte values. So ten million cells is close to 100 MB. If the number is larger, then we do not allocate a matrix, but use a vector of unordered maps (vec_map_storage). The unordered_map seems to be about twice slower.

Template Parameters:

  • T – Type of the values stored in the map. Must be an unsigned type.

  • track_inverted – Whether to track inverted indices for the first and second dimensions. To use this feature correctly, the mapping has to be reversible.

  • MAX_MATRIX_SIZE – Maximum size of the matrix before switching to vector of unordered maps.

Public Functions

inline TwoDimensionalMap(const size_t first_dim_size, const size_t second_dim_size)

Constructor for TwoDimensionalMap.

Parameters:

  • first_dim_size – Size of the first dimension.

  • second_dim_size – Size of the second dimension.

inline T get(const T first, const T second) const

Get the value associated with a pair of keys.

Parameters:

  • first – First key.

  • second – Second key.

Returns:

The value associated with the pair, or std::numeric_limits<T>::max() if not found.

inline void insert(const T first, const T second, const T value)

Insert a value associated with a pair of keys.

Parameters:

  • first – First key.

  • second – Second key.

  • value – Value to associate with the pair.

inline T get_first_inverted(const T value) const

Get the first inverted index for a value.

This is only available if track_inverted is true.

inline T get_second_inverted(const T value) const

Get the second inverted index for a value.

This is only available if track_inverted is true.