Thea
Public Member Functions | List of all members
UnionFind< T > Class Template Reference

Union-find data structure. More...

#include <UnionFind.hpp>

Public Member Functions

intx find (intx p) const
 Return the ID of the representative element of the set corresponding to the object with ID p. More...
 
intx getObjectId (T const &obj) const
 Get the ID of an object, or a negative value if it is not present in the data structure. More...
 
void merge (intx x, intx y)
 Replace sets containing x and y with their union. More...
 
intx numSets () const
 Get the number of disjoint sets. More...
 
bool sameSet (intx x, intx y) const
 Are objects x and y in the same set? More...
 
intx sizeOfSet (intx p) const
 Get the size of the set containing object p. More...
 
 UnionFind (intx n)
 Create a union-find data structure for n objects, which will be assumed to have sequential IDs from 0 to n - 1. More...
 
template<typename InputIterator >
 UnionFind (InputIterator begin, InputIterator end)
 Create a union-find data structure for objects in the range [begin, end). More...
 
 ~UnionFind ()
 Destructor. More...
 

Detailed Description

template<typename T = intx>
class Thea::UnionFind< T >

Union-find data structure.

Original code by Kartik Kukreja, https://github.com/kartikkukreja/ . The data structure will save a copy of each object to support getObjectId(), so T should be easily copyable (a small/POD class, or a pointer).

Definition at line 28 of file UnionFind.hpp.

Constructor & Destructor Documentation

UnionFind ( intx  n)

Create a union-find data structure for n objects, which will be assumed to have sequential IDs from 0 to n - 1.

If you use this constructor, note that getObjectId() will return the expected results (operating as an identity function) only if T = intx. Else, avoid calling getObjectId().

Definition at line 36 of file UnionFind.hpp.

UnionFind ( InputIterator  begin,
InputIterator  end 
)

Create a union-find data structure for objects in the range [begin, end).

The objects will be assigned sequential IDs 0, 1, 2, ..., n - 1 in the same order as the input. Note that the data structure will save a copy of each object to support getObjectId(), so T should be easily copyable (a small/POD class, or a pointer).

Definition at line 47 of file UnionFind.hpp.

~UnionFind ( )

Destructor.

Definition at line 58 of file UnionFind.hpp.

Member Function Documentation

intx find ( intx  p) const

Return the ID of the representative element of the set corresponding to the object with ID p.

Definition at line 76 of file UnionFind.hpp.

intx getObjectId ( T const &  obj) const

Get the ID of an object, or a negative value if it is not present in the data structure.

Note that if you used the UnionFind(intx) constructor, this function will give the expected results (operating as an identity function) only if T = intx.

Definition at line 69 of file UnionFind.hpp.

void merge ( intx  x,
intx  y 
)

Replace sets containing x and y with their union.

Definition at line 94 of file UnionFind.hpp.

intx numSets ( ) const

Get the number of disjoint sets.

Definition at line 124 of file UnionFind.hpp.

bool sameSet ( intx  x,
intx  y 
) const

Are objects x and y in the same set?

Definition at line 118 of file UnionFind.hpp.

intx sizeOfSet ( intx  p) const

Get the size of the set containing object p.

Definition at line 130 of file UnionFind.hpp.


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