TPIE

2362a60
Public Member Functions | Static Public Member Functions | List of all members
tpie::disjoint_sets< value_t > Class Template Reference

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...
 

Detailed Description

template<typename value_t = size_type>
class tpie::disjoint_sets< value_t >

Internal memory union find implementation.

The key space is the first n integers (from 0 to n-1). n is given in the constructor.

Template Parameters
value_tThe type of values stored (must be an integer type).

Definition at line 43 of file disjoint_sets.h.

Constructor & Destructor Documentation

template<typename value_t = size_type>
tpie::disjoint_sets< value_t >::disjoint_sets ( size_type  n = 0,
value_t  u = default_unused<value_t>::v(),
tpie::memory_bucket_ref  b = tpie::memory_bucket_ref() 
)
inline

Construct a empty collection of disjoint sets.

Parameters
nThe maximal number of sets to support
uA value you guarentee not to use.

Definition at line 71 of file disjoint_sets.h.

Referenced by tpie::disjoint_sets< value_t >::memory_overhead().

74  : m_elements(n, u, b), m_unused(u), m_size(0) {}

Member Function Documentation

template<typename value_t = size_type>
void tpie::disjoint_sets< value_t >::clear ( )
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().

164  {
165  std::fill(m_elements.begin(), m_elements.end(), m_unused);
166  m_size = 0;
167  }
tpie::array::end
iterator end()
Return an iterator to the end of the array.
Definition: array.h:321
tpie::array::begin
iterator begin()
Return an iterator to the beginning of the array.
Definition: array.h:307
template<typename value_t = size_type>
size_type tpie::disjoint_sets< value_t >::count_sets ( )
inline

Return the number of sets.

Definition at line 157 of file disjoint_sets.h.

157  {
158  return m_size;
159  }
template<typename value_t = size_type>
value_t tpie::disjoint_sets< value_t >::find_set ( value_t  t)
inline

Find the representative of the set contaning a given element.

Parameters
tThe element of which to find the set representative
Returns
The representative.

Definition at line 115 of file disjoint_sets.h.

Referenced by tpie::disjoint_sets< value_t >::union_set().

115  {
116  // If t sits in depth d, we halve the depth of d/2 nodes in the tree,
117  // including t.
118  while (true) {
119  // Set t to point to its grandparent.
120  value_t x = m_elements[m_elements[t]];
121  if (x == t) return t;
122  m_elements[t] = x;
123  t = x;
124  }
125 
126  // The textbook implementation below is faster for some adversarial
127  // inputs, but is cache inefficient on ordinary input.
128 
129  //value_t r = m_elements[t];
130  //if (r == t)
131  // return r;
132  //while (r != m_elements[r])
133  // r = m_elements[r];
134  //while (t != r) {
135  // value_t next = m_elements[t];
136  // m_elements[t] = r;
137  // t = next;
138  //}
139  //return r;
140  }
template<typename value_t = size_type>
bool tpie::disjoint_sets< value_t >::is_set ( value_t  element)
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

Parameters
elementThe key to check

Definition at line 92 of file disjoint_sets.h.

92 {return m_elements[element] != m_unused;}
template<typename value_t = size_type>
value_t tpie::disjoint_sets< value_t >::link ( value_t  a,
value_t  b 
)
inline

Union two sets given by their representatives.

Parameters
aThe representative of one set
bThe representative of the other set
Returns
The representative of the combined set

Definition at line 101 of file disjoint_sets.h.

Referenced by tpie::disjoint_sets< value_t >::union_set().

101  {
102  if (a == b) return a;
103  --m_size;
104  m_elements[b] = a;
105  return a;
106  }
template<typename value_t = size_type>
void tpie::disjoint_sets< value_t >::make_set ( value_t  element)
inline

Make a singleton set.

Parameters
elementThe key of the singleton set to create

Definition at line 83 of file disjoint_sets.h.

83 {m_elements[element] = element; ++m_size;}
template<typename value_t = size_type>
static double tpie::disjoint_sets< value_t >::memory_coefficient ( )
inlinestatic

Return the memory coefficient of the structure.

Allocating a structure with n elements will use at most $ \lfloor \mathrm{memory\_coefficient} \cdot n + \mathrm{memory\_overhead} \rfloor $ bytes. This does not include memory overhead incurred if the structure is allocated using new.

Returns
The memory coefficient of the structure.

Definition at line 53 of file disjoint_sets.h.

References tpie::array< T, Allocator >::memory_coefficient().

53  {
54  return array<value_t>::memory_coefficient();
55  }
tpie::array::memory_coefficient
static double memory_coefficient()
Return the memory coefficient of the structure.
Definition: array.h:393
static memory_size_type tpie::linear_memory_base< disjoint_sets< value_t > >::memory_fits ( memory_size_type  memory)
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.

Parameters
memoryThe number of bytes the structure is allowed to occupy
Returns
The number of elements that will fit in the structure

Definition at line 93 of file util.h.

93  {
94  return static_cast<memory_size_type>(
95  floor((memory - child_t::memory_overhead()) / child_t::memory_coefficient()));
96  }
template<typename value_t = size_type>
static double tpie::disjoint_sets< value_t >::memory_overhead ( )
inlinestatic

Return the memory overhead of the structure.

See also
memory_coefficient()
Returns
The memory overhead.

Definition at line 61 of file disjoint_sets.h.

References tpie::disjoint_sets< value_t >::disjoint_sets(), and tpie::array< T, Allocator >::memory_overhead().

61  {
62  return array<value_t>::memory_overhead() + sizeof(disjoint_sets) - sizeof(array<value_t>);
63  }
tpie::disjoint_sets::disjoint_sets
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.
Definition: disjoint_sets.h:71
tpie::array::memory_overhead
static double memory_overhead()
Return the memory overhead of the structure.
Definition: array.h:400
static memory_size_type tpie::linear_memory_base< disjoint_sets< value_t > >::memory_usage ( memory_size_type  size)
inlinestaticinherited

Return the number of bytes required to create a data structure supporting a given number of elements.

Parameters
sizeThe number of elements to support
Returns
The amount of memory required in bytes

Definition at line 81 of file util.h.

81  {
82  return static_cast<memory_size_type>(
83  floor(static_cast<double>(size) * child_t::memory_coefficient() + child_t::memory_overhead()));
84  }
template<typename value_t = size_type>
void tpie::disjoint_sets< value_t >::resize ( size_t  size)
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().

173  {
174  m_elements.resize(size, m_unused);
175  m_size = 0;
176  }
tpie::array::resize
void resize(size_t size, const T &elm)
Change the size of the array.
Definition: array.h:485
template<typename value_t = size_type>
value_t tpie::disjoint_sets< value_t >::union_set ( value_t  a,
value_t  b 
)
inline

Union the set containing a with the set containing b.

Parameters
aAn element in one set
bAn element in another set (possible)
Returns
The representative of the unioned set

Definition at line 150 of file disjoint_sets.h.

References tpie::disjoint_sets< value_t >::find_set(), and tpie::disjoint_sets< value_t >::link().

150  {
151  return link(find_set(a), find_set(b));
152  }
tpie::disjoint_sets::link
value_t link(value_t a, value_t b)
Union two sets given by their representatives.
Definition: disjoint_sets.h:101
tpie::disjoint_sets::find_set
value_t find_set(value_t t)
Find the representative of the set contaning a given element.
Definition: disjoint_sets.h:115
The documentation for this class was generated from the following file: