Class ConcurrentUnionFind

• Defined in File ConcurrentUnionFind.h

Class Documentation

class ConcurrentUnionFind

the union-find of the elements [ 0 , n ) that threads change at once

Public Functions

inline explicit ConcurrentUnionFind(std::size_t n)

n singletons

Pre:

n < 2^31

ConcurrentUnionFind(const ConcurrentUnionFind&) = delete

ConcurrentUnionFind &operator=(const ConcurrentUnionFind&) = delete

inline std::size_t size(void) const

inline std::int32_t find(std::int32_t x)

the root of x, the least element of its set when no union is running

Pre:

x < size()

inline std::int32_t parent(std::int32_t x) const

the parent of x at a moment of the call (x if a root)

Pre:

x < size()

inline void compress(std::int32_t x)

x pointed to its root, unless a union moved x first

Pre:

x < size()

inline bool unite(std::int32_t x, std::int32_t y)

the union of the sets of x and y; false if they were already one

Pre:

x , y < size()

inline bool sameSet(std::int32_t x, std::int32_t y)

whether x and y are in the same set

Pre:

x , y < size()