souffle::SparseDisjointSet< SparseDomain > Class Template Reference

#include <UnionFind.h>

Collaboration diagram for souffle::SparseDisjointSet< SparseDomain >:

Public Member Functions
void	clear ()
	Remove all elements from this disjoint set. More...
bool	contains (SparseDomain v1, SparseDomain v2)
SparseDomain	findNode (SparseDomain x)
void	makeNode (SparseDomain val)
bool	nodeExists (const SparseDomain val) const
SparseDisjointSet &	operator= (SparseDisjointSet &&other)=delete
SparseDisjointSet &	operator= (SparseDisjointSet &other)=delete
bool	sameSet (SparseDomain x, SparseDomain y)
std::size_t	size ()
	SparseDisjointSet ()=default
	SparseDisjointSet (SparseDisjointSet &&other)=delete
	SparseDisjointSet (SparseDisjointSet &other)=delete
parent_t	toDense (const SparseDomain in)
	Retrieve dense encoding, adding it in if non-existent. More...
const SparseDomain	toSparse (const parent_t in) const
	For the given dense value, return the associated sparse value Undefined behaviour if dense value not in set. More...
void	unionNodes (SparseDomain x, SparseDomain y)

Private Types
using	DenseMap = RandomInsertPiggyList< SparseDomain >
using	PairStore = std::pair< SparseDomain, parent_t >
using	SparseMap = LambdaBTreeSet< PairStore, std::function< parent_t(PairStore &)>, EqrelMapComparator< PairStore > >

Private Attributes
DenseMap	denseToSparseMap
DisjointSet	ds
SparseMap::operation_hints	last_ins
SparseMap	sparseToDenseMap

Friends
template<typename TupleType >
class	EquivalenceRelation

Detailed Description

template<typename SparseDomain>
class souffle::SparseDisjointSet< SparseDomain >

Definition at line 258 of file UnionFind.h.

Member Typedef Documentation

DenseMap

template<typename SparseDomain >

using souffle::SparseDisjointSet< SparseDomain >::DenseMap = RandomInsertPiggyList<SparseDomain>

private

Definition at line 267 of file UnionFind.h.

PairStore

template<typename SparseDomain >

using souffle::SparseDisjointSet< SparseDomain >::PairStore = std::pair<SparseDomain, parent_t>

private

Definition at line 264 of file UnionFind.h.

SparseMap

template<typename SparseDomain >

using souffle::SparseDisjointSet< SparseDomain >::SparseMap = LambdaBTreeSet<PairStore, std::function<parent_t(PairStore&)>, EqrelMapComparator<PairStore> >

private

Definition at line 266 of file UnionFind.h.

Constructor & Destructor Documentation

SparseDisjointSet() [1/3]

template<typename SparseDomain >

souffle::SparseDisjointSet< SparseDomain >::SparseDisjointSet ( )

default

SparseDisjointSet() [2/3]

template<typename SparseDomain >

souffle::SparseDisjointSet< SparseDomain >::SparseDisjointSet ( SparseDisjointSet< SparseDomain > &  other )

delete

SparseDisjointSet() [3/3]

template<typename SparseDomain >

souffle::SparseDisjointSet< SparseDomain >::SparseDisjointSet ( SparseDisjointSet< SparseDomain > &&  other )

delete

Member Function Documentation

clear()

template<typename SparseDomain >

void souffle::SparseDisjointSet< SparseDomain >::clear ( )

inline

Remove all elements from this disjoint set.

Definition at line 338 of file UnionFind.h.

                                           {
        // dense has the behaviour of creating if not exists.
        toDense(val);
    };

contains()

template<typename SparseDomain >

bool souffle::SparseDisjointSet< SparseDomain >::contains ( SparseDomain  v1, SparseDomain  v2  )

inline

Definition at line 355 of file UnionFind.h.

findNode()

template<typename SparseDomain >

SparseDomain souffle::SparseDisjointSet< SparseDomain >::findNode ( SparseDomain  x )

inline

Definition at line 323 of file UnionFind.h.

                            {

Referenced by souffle::EquivalenceRelation< Arity >::anteriorIt(), souffle::EquivalenceRelation< Arity >::antpostit(), and souffle::EquivalenceRelation< Arity >::upper_bound().

makeNode()

template<typename SparseDomain >

void souffle::SparseDisjointSet< SparseDomain >::makeNode ( SparseDomain  val )

inline

Definition at line 345 of file UnionFind.h.

                                                         {
        return sparseToDenseMap.contains({val, -1});
    };
 

Referenced by souffle::test::TEST().

nodeExists()

template<typename SparseDomain >

bool souffle::SparseDisjointSet< SparseDomain >::nodeExists ( const SparseDomain  val ) const

inline

Definition at line 351 of file UnionFind.h.

Referenced by souffle::EquivalenceRelation< Arity >::getBoundaries().

operator=() [1/2]

template<typename SparseDomain >

SparseDisjointSet& souffle::SparseDisjointSet< SparseDomain >::operator= ( SparseDisjointSet< SparseDomain > &&  other )

delete

operator=() [2/2]

template<typename SparseDomain >

SparseDisjointSet& souffle::SparseDisjointSet< SparseDomain >::operator= ( SparseDisjointSet< SparseDomain > &  other )

delete

sameSet()

template<typename SparseDomain >

bool souffle::SparseDisjointSet< SparseDomain >::sameSet ( SparseDomain  x, SparseDomain  y  )

inline

Definition at line 319 of file UnionFind.h.

                                                           {

Referenced by souffle::EquivalenceRelation< Arity >::anteriorIt().

size()

template<typename SparseDomain >

std::size_t souffle::SparseDisjointSet< SparseDomain >::size ( )

inline

Definition at line 331 of file UnionFind.h.

                 {
        ds.clear();

toDense()

template<typename SparseDomain >

parent_t souffle::SparseDisjointSet< SparseDomain >::toDense ( const SparseDomain  in )

inline

Retrieve dense encoding, adding it in if non-existent.

Parameters

in	the sparse value

Returns

the corresponding dense value

Definition at line 281 of file UnionFind.h.

      :
    SparseDisjointSet() = default;
 
    // copy ctor
    SparseDisjointSet(SparseDisjointSet& other) = delete;

Referenced by souffle::SparseDisjointSet< value_type >::clear().

toSparse()

template<typename SparseDomain >

const SparseDomain souffle::SparseDisjointSet< SparseDomain >::toSparse ( const parent_t  in ) const

inline

For the given dense value, return the associated sparse value Undefined behaviour if dense value not in set.

Parameters

in	the supplied dense value

Returns

the sparse value from the denseToSparseMap

Definition at line 314 of file UnionFind.h.

                                                 {

unionNodes()

template<typename SparseDomain >

void souffle::SparseDisjointSet< SparseDomain >::unionNodes ( SparseDomain  x, SparseDomain  y  )

inline

Definition at line 327 of file UnionFind.h.

                 {

Referenced by souffle::EquivalenceRelation< Arity >::insert().

Friends And Related Function Documentation

EquivalenceRelation

template<typename SparseDomain >

template<typename TupleType >

friend class EquivalenceRelation

friend

Definition at line 262 of file UnionFind.h.

Field Documentation

denseToSparseMap

template<typename SparseDomain >

DenseMap souffle::SparseDisjointSet< SparseDomain >::denseToSparseMap

private

Definition at line 273 of file UnionFind.h.

Referenced by souffle::SparseDisjointSet< value_type >::size().

ds

template<typename SparseDomain >

DisjointSet souffle::SparseDisjointSet< SparseDomain >::ds

private

Definition at line 259 of file UnionFind.h.

Referenced by souffle::EqrelMapComparator< PairStore >::equal(), and souffle::SparseDisjointSet< value_type >::size().

last_ins

template<typename SparseDomain >

SparseMap::operation_hints souffle::SparseDisjointSet< SparseDomain >::last_ins

private

Definition at line 269 of file UnionFind.h.

sparseToDenseMap

template<typename SparseDomain >

SparseMap souffle::SparseDisjointSet< SparseDomain >::sparseToDenseMap

private

Definition at line 271 of file UnionFind.h.

Referenced by souffle::SparseDisjointSet< value_type >::makeNode(), and souffle::SparseDisjointSet< value_type >::size().

---

The documentation for this class was generated from the following file:

• include/souffle/datastructure/UnionFind.h