File sparse-set.hh

namespace mata

Main namespace including structs and algorithms for all automata.

In particular, this includes:

  1. Alphabets,

  2. Formula graphs and nodes,

  3. Mintermization,

  4. Closed sets.

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

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 Types

using iterator = typename std::vector<Number>::const_iterator
using const_iterator = typename std::vector<Number>::const_iterator

Public Functions

inline iterator begin()
inline const_iterator begin() const
inline iterator end()
inline const_iterator end() const
inline size_t size() const
inline size_t domain_size() const
inline bool empty() const
inline void clear()
inline void reserve(size_t u)
inline bool contains(const Number val) const
inline void insert(const Number val)
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.

inline void erase(const Number val)
SparseSet() = default

New Mata code.

inline explicit SparseSet(Number domain_size)

Basic constructor where you may reserve a domain size.

inline SparseSet(std::initializer_list<Number> list)
template<class InputIterator>
inline explicit SparseSet(InputIterator first, InputIterator last)
template<class T>
inline explicit SparseSet(T &container)
inline explicit SparseSet(const BoolVector &bv)
SparseSet(const SparseSet<Number> &rhs) = default
inline SparseSet(SparseSet<Number> &&other) noexcept
SparseSet<Number> &operator=(const SparseSet<Number> &rhs) = default
inline SparseSet<Number> &operator=(SparseSet<Number> &&other) noexcept
bool operator==(const SparseSet<Number>&) const = default
inline bool consistent()
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).

template<class InputIterator>
inline void insert(InputIterator first, InputIterator last)
template<Iterable T>
inline void insert(const T &set)
inline void insert(const std::initializer_list<Number> &list)
template<class InputIterator>
inline void erase(InputIterator first, InputIterator last)
template<Iterable T>
inline void erase(const T &set)
inline void erase(const std::initializer_list<Number> &list)
template<class T>
inline bool intersects_with(const T &set) const
inline void complement(Number new_domain_size)
template<typename F>
inline void filter(F &&is_staying)
inline void sort()
template<typename F>
inline void rename(F &&renaming)
inline Number max()

Maximal Number in set.

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

inline void truncate()

Private Members

std::vector<Number> dense = {}
std::vector<Number> sparse = {}
size_t size_ = 0

Number of elements which are in the set (current size).

size_t domain_size_ = 0

Over-approximation of Number in sparse set. It represents the Numbers which were in the set throughout the life of the set until now.

truncate() will update the domain size to the current maximal Number + 1. Constructor can preallocate the sparse set and set domain size to the requested value. The structures are preallocated to at least domain_size_ size (can be more when maximal Number is removed).

Friends

inline friend bool are_disjoint(const SparseSet &A, const SparseSet &B)