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, value_t u=default_unused< value_t >::v())
	Construct a empty collection of disjoint sets. More...

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

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 stream_size_type	memory_usage (stream_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_t The 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,
		value_t	u = `default_unused<value_t>::v()`
	)

inline

Construct a empty collection of disjoint sets.

Parameters

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

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

Member Function Documentation

template<typename value_t = size_type>

size_type tpie::disjoint_sets< value_t >::count_sets ( )

inline

Return the number of sets.

Definition at line 152 of file disjoint_sets.h.

                                   {
         return m_size;
     }

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

t	The element of which to find the set representative

Returns: The representative.

Definition at line 110 of file disjoint_sets.h.

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

                                        {
         // If t sits in depth d, we halve the depth of d/2 nodes in the tree,
         // including t.
         while (true) {
             // Set t to point to its grandparent.
             value_t x = m_elements[m_elements[t]];
             if (x == t) return t;
             m_elements[t] = x;
             t = x;
         }
 
         // The textbook implementation below is faster for some adversarial
         // inputs, but is cache inefficient on ordinary input.
 
         //value_t r = m_elements[t];
         //if (r == t)
         //  return r;
         //while (r != m_elements[r])
         //  r = m_elements[r];
         //while (t != r) {
         //  value_t next = m_elements[t];
         //  m_elements[t] = r;
         //  t = next;
         //}
         //return r;
     }

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

element The key to check

Definition at line 87 of file disjoint_sets.h.

87 {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

a	The representative of one set
b	The representative of the other set

Returns: The representative of the combined set

Definition at line 96 of file disjoint_sets.h.

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

                                               {
         if (a == b) return a;
         --m_size;
         m_elements[b] = a;
         return a;
     }

template<typename value_t = size_type>

void tpie::disjoint_sets< value_t >::make_set ( value_t element )

inline

Make a singleton set.

Parameters

element The key of the singleton set to create

Definition at line 78 of file disjoint_sets.h.

78 {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().

                                        {
         return array<value_t>::memory_coefficient();
     }

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

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

                                                                         {
         return static_cast<memory_size_type>(
             floor((memory - child_t::memory_overhead()) / child_t::memory_coefficient()));
     }

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

                                     {
         return array<value_t>::memory_overhead() + sizeof(disjoint_sets) - sizeof(array<value_t>);
     }

static stream_size_type tpie::linear_memory_base< disjoint_sets< value_t > >::memory_usage ( stream_size_type size )

inlinestaticinherited

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

Parameters

size	The number of elements to support

Returns: The amount of memory required in bytes

Definition at line 81 of file util.h.

                                                                        {
         return static_cast<stream_size_type>(
             floor(static_cast<double>(size) * child_t::memory_coefficient() + child_t::memory_overhead()));
     }

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

a	An element in one set
b	An element in another set (possible)

Returns: The representative of the unioned set

Definition at line 145 of file disjoint_sets.h.

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

                                                    {
         return link(find_set(a), find_set(b));
     }

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

disjoint_sets.h

TPIE

Public Member Functions

Static Public Member Functions

Detailed Description

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

Constructor & Destructor Documentation

Member Function Documentation

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