Internal memory union find implementation. More...
#include <tpie/disjoint_sets.h>
Inherits tpie::linear_memory_base< disjoint_sets< value_t > >.
Public Member Functions | |
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. More... | |
disjoint_sets (tpie::memory_bucket_ref b) | |
void | make_set (value_t element) |
Make a singleton set. More... | |
bool | is_set (value_t element) |
Check if a given element is a member of any set. More... | |
value_t | link (value_t a, value_t b) |
Union two sets given by their representatives. More... | |
value_t | find_set (value_t t) |
Find the representative of the set contaning a given element. More... | |
value_t | union_set (value_t a, value_t b) |
Union the set containing a with the set containing b. More... | |
size_type | count_sets () |
Return the number of sets. More... | |
void | clear () |
Clears all sets contained in the datastructure. More... | |
void | resize (size_t size) |
Changes the size of the datastructure. More... | |
Static Public Member Functions | |
static double | memory_coefficient () |
Return the memory coefficient of the structure. More... | |
static double | memory_overhead () |
Return the memory overhead of the structure. More... | |
static memory_size_type | memory_usage (memory_size_type size) |
Return the number of bytes required to create a data structure supporting a given number of elements. More... | |
static memory_size_type | memory_fits (memory_size_type memory) |
Return the maximum number of elements that can be contained in in the structure when it is allowed to fill a given number of bytes. More... | |
Internal memory union find implementation.
The key space is the first n integers (from 0 to n-1). n is given in the constructor.
value_t | The type of values stored (must be an integer type). |
Definition at line 43 of file disjoint_sets.h.
|
inline |
Construct a empty collection of disjoint sets.
n | The maximal number of sets to support |
u | A value you guarentee not to use. |
Definition at line 71 of file disjoint_sets.h.
Referenced by tpie::disjoint_sets< value_t >::memory_overhead().
|
inline |
Clears all sets contained in the datastructure.
Definition at line 164 of file disjoint_sets.h.
References tpie::array< T, Allocator >::begin(), and tpie::array< T, Allocator >::end().
|
inline |
Return the number of sets.
Definition at line 157 of file disjoint_sets.h.
|
inline |
Find the representative of the set contaning a given element.
t | The element of which to find the set representative |
Definition at line 115 of file disjoint_sets.h.
Referenced by tpie::disjoint_sets< value_t >::union_set().
|
inline |
Check if a given element is a member of any set.
This is the same as saying if make_set has ever been called with the given key
element | The key to check |
Definition at line 92 of file disjoint_sets.h.
|
inline |
Union two sets given by their representatives.
a | The representative of one set |
b | The representative of the other set |
Definition at line 101 of file disjoint_sets.h.
Referenced by tpie::disjoint_sets< value_t >::union_set().
|
inline |
Make a singleton set.
element | The key of the singleton set to create |
Definition at line 83 of file disjoint_sets.h.
|
inlinestatic |
Return the memory coefficient of the structure.
Allocating a structure with n elements will use at most bytes. This does not include memory overhead incurred if the structure is allocated using new.
Definition at line 53 of file disjoint_sets.h.
References tpie::array< T, Allocator >::memory_coefficient().
|
inlinestaticinherited |
Return the maximum number of elements that can be contained in in the structure when it is allowed to fill a given number of bytes.
memory | The number of bytes the structure is allowed to occupy |
|
inlinestatic |
Return the memory overhead of the structure.
Definition at line 61 of file disjoint_sets.h.
References tpie::disjoint_sets< value_t >::disjoint_sets(), and tpie::array< T, Allocator >::memory_overhead().
|
inlinestaticinherited |
Return the number of bytes required to create a data structure supporting a given number of elements.
size | The number of elements to support |
|
inline |
Changes the size of the datastructure.
All elements are lost.
Definition at line 173 of file disjoint_sets.h.
References tpie::array< T, Allocator >::resize().
|
inline |
Union the set containing a with the set containing b.
a | An element in one set |
b | An element in another set (possible) |
Definition at line 150 of file disjoint_sets.h.
References tpie::disjoint_sets< value_t >::find_set(), and tpie::disjoint_sets< value_t >::link().