19 #ifndef __TPIE_DISJOINT_SETS__
20 #define __TPIE_DISJOINT_SETS__
42 template <
typename value_t=
size_type>
74 : m_elements(n, u, b), m_unused(u), m_size(0) {}
83 inline void make_set(value_t element) {m_elements[element] = element; ++m_size;}
92 inline bool is_set(value_t element) {
return m_elements[element] != m_unused;}
101 inline value_t
link(value_t a, value_t b) {
102 if (a == b)
return a;
120 value_t x = m_elements[m_elements[t]];
121 if (x == t)
return t;
165 std::fill(m_elements.
begin(), m_elements.
end(), m_unused);
174 m_elements.
resize(size, m_unused);
180 #endif //__TPIE_DISJOINT_SETS__
value_t link(value_t a, value_t b)
Union two sets given by their representatives.
disjoint_sets(size_type n=0, value_t u=default_unused< value_t >::v(), tpie::memory_bucket_ref b=tpie::memory_bucket_ref())
Construct a empty collection of disjoint sets.
value_t find_set(value_t t)
Find the representative of the set contaning a given element.
value_t union_set(value_t a, value_t b)
Union the set containing a with the set containing b.
Base class of data structures with linear memory usage.
void resize(size_t size)
Changes the size of the datastructure.
bool is_set(value_t element)
Check if a given element is a member of any set.
static double memory_coefficient()
Return the memory coefficient of the structure.
Generic internal array with known memory requirements.
size_type count_sets()
Return the number of sets.
Class storring a reference to a memory bucket.
Miscellaneous utility functions.
static double memory_overhead()
Return the memory overhead of the structure.
static double memory_coefficient()
Return the memory coefficient of the structure.
void resize(size_t size, const T &elm)
Change the size of the array.
Internal memory union find implementation.
static double memory_overhead()
Return the memory overhead of the structure.
void clear()
Clears all sets contained in the datastructure.
iterator end()
Return an iterator to the end of the array.
iterator begin()
Return an iterator to the beginning of the array.
void make_set(value_t element)
Make a singleton set.
Default special unused values for standard types.