File ord-vector.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

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 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 Types

using VectorType = std::vector<Key>

using value_type = Key

using size_type = size_t

using iterator = typename VectorType::iterator

using const_iterator = typename VectorType::const_iterator

using const_reference = typename VectorType::const_reference

using reference = typename VectorType::reference

Public Functions

inline OrdVector()

inline explicit OrdVector(const VectorType &vec)

inline explicit OrdVector(const std::set<Key> &set)

template<class T>
inline explicit OrdVector(const T &set)

inline OrdVector(std::initializer_list<Key> list)

OrdVector(const OrdVector &rhs) = default

inline OrdVector(OrdVector &&other) noexcept

inline explicit OrdVector(const Key &key)

template<class InputIterator>
inline explicit OrdVector(InputIterator first, InputIterator last)

inline OrdVector &operator=(const OrdVector &other)

inline OrdVector &operator=(OrdVector &&other) noexcept

virtual ~OrdVector() = default

inline std::pair<iterator, bool> insert(iterator itr, const Key &x)

template<typename ...Args>
inline reference emplace_back(Args&&... args)

inline reference push_back(const Key &t)

inline reference push_back(Key &&t)

inline virtual void reserve(size_t size)

inline virtual void resize(size_t size)

inline virtual iterator erase(const_iterator pos)

inline virtual iterator erase(const_iterator first, const_iterator last)

inline virtual std::pair<iterator, bool> insert(const Key &x)

inline virtual bool insert(const OrdVector &vec)

inline void clear()

inline virtual size_t size() const

inline size_t count(const Key &key) const

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 OrdVector intersection(const OrdVector &rhs) const

inline virtual const_iterator find(const Key &key) const

inline virtual iterator find(const Key &key)

inline virtual const Key &front() const

inline virtual Key &front()

inline virtual const Key &min() const

inline virtual Key &min()

inline virtual const Key &max() const

inline virtual Key &max()

inline virtual const Key &at(const size_t index) const

inline virtual Key &at(const size_t index)

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 bool empty() const

template<typename Fun>
inline void filter_indexes(const Fun &&is_staying)

template<typename Fun>
inline void filter(const Fun &&is_staying)

inline virtual const_reference back() const

inline virtual reference back()

Get reference to the last element in the vector.

Modifying the underlying value in the reference could break sortedness.

inline virtual void pop_back()

inline virtual const_iterator begin() const

inline virtual const_iterator end() const

inline virtual iterator begin()

inline virtual iterator end()

inline virtual const_iterator cbegin() const

inline virtual const_iterator cend() const

inline bool operator==(const OrdVector &rhs) const

inline bool operator<(const OrdVector &rhs) const

inline const std::vector<Key> &to_vector() const

inline bool is_subset_of(const OrdVector &bigger) const

inline bool is_intersection_empty_with(const OrdVector &rhs) const

inline void rename(const std::vector<Key> &renaming)

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.

static inline OrdVector difference(const OrdVector &lhs, const OrdVector &rhs)

static inline bool set_union(const OrdVector &lhs, const OrdVector &rhs, OrdVector &result)

static inline OrdVector set_union(const OrdVector &lhs, const OrdVector &rhs)

static inline OrdVector intersection(const OrdVector &lhs, const OrdVector &rhs)

Private Functions

inline bool is_sorted() const

Private Members

VectorType vec_

Private Static Functions

template<typename T>
static inline std::string to_str(const T &n)

Converts an object to string.

Static method for conversion of an object of any class with the << output operator into a string

Parameters:

n – [in] The object for the conversion.

Returns:

The string representation of the object.

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

namespace std

template<class Key>
struct hash<mata::utils::OrdVector<Key>>

#include <ord-vector.hh>

Public Functions

inline std::size_t operator()(const mata::utils::OrdVector<Key> &vec) const