CGAL 5.1 - Profiling tools, Hash Map, Union-find, Modifiers
CGAL::Union_find< T, A > Class Template Reference

#include <CGAL/Union_find.h>

Definition

template<typename T, typename A>
class CGAL::Union_find< T, A >

An instance P of the data type Union_find<T,A> is a partition of values of type T into disjoint sets. The template parameter A has to be a model of the allocator concept as defined in the C++ standard. It has a default argument CGAL_ALLOCATOR(T).

Implementation

Union_find<T,A> is implemented with union by rank and path compression. The running time for \( m\) set operations on \( n\) elements is \( O(n \alpha(m,n))\) where \( \alpha(m,n)\) is the extremely slow growing inverse of Ackermann's function.

Types

There are also constant versions const_handle and const_iterator.

typedef unspecified_type value_type
 values stored in items (equal to T). More...
 
typedef unspecified_type handle
 handle to values. More...
 
typedef unspecified_type iterator
 iterator over values. More...
 
typedef unspecified_type allocator
 allocator. More...
 

Creation

 Union_find ()
 creates an instance P of type Union_find<T,A> and initializes it to the empty partition. More...
 

Operations

allocator get_allocator () const
 the allocator of the partition. More...
 
std::size_t number_of_sets () const
 returns the number of disjoint sets of the partition. More...
 
std::size_t size () const
 returns the number of values of the partition. More...
 
std::size_t bytes () const
 returns the memory consumed by the partition. More...
 
std::size_t size (const_handle h) const
 returns the size of the set containing h. More...
 
void clear ()
 reinitializes to an empty partition. More...
 
handle make_set (const T &x)
 creates a new singleton set containing x and returns a handle to it. More...
 
handle push_back (const T &x)
 same as make_set(). More...
 
template<class Forward_iterator >
void insert (Forward_iterator first, Forward_iterator beyond)
 inserts the range of values referenced by [first,beyond). More...
 
handle find (handle h) const
 
const_handle find (const_handle p) const
 returns a canonical handle of the set that contains h, i.e., P.same_set(h,h2) iff P.find(h) == P.find(h2). More...
 
void unify_sets (handle h1, handle h2)
 unites the sets of partition P containing h1 and h2. More...
 
bool same_set (const_handle h1, const_handle h2) const
 returns true iff h1 and h2 belong to the same set of P. More...
 
iterator begin () const
 returns an iterator pointing to the first value of the partition. More...
 
iterator end () const
 returns an iterator pointing beyond the last value of the partition. More...
 

Member Typedef Documentation

◆ allocator

template<typename T , typename A >
typedef unspecified_type CGAL::Union_find< T, A >::allocator

allocator.

◆ handle

template<typename T , typename A >
typedef unspecified_type CGAL::Union_find< T, A >::handle

handle to values.

◆ iterator

template<typename T , typename A >
typedef unspecified_type CGAL::Union_find< T, A >::iterator

iterator over values.

◆ value_type

template<typename T , typename A >
typedef unspecified_type CGAL::Union_find< T, A >::value_type

values stored in items (equal to T).

Constructor & Destructor Documentation

◆ Union_find()

template<typename T , typename A >
CGAL::Union_find< T, A >::Union_find ( )

creates an instance P of type Union_find<T,A> and initializes it to the empty partition.

Member Function Documentation

◆ begin()

template<typename T , typename A >
iterator CGAL::Union_find< T, A >::begin ( ) const

returns an iterator pointing to the first value of the partition.

◆ bytes()

template<typename T , typename A >
std::size_t CGAL::Union_find< T, A >::bytes ( ) const

returns the memory consumed by the partition.

◆ clear()

template<typename T , typename A >
void CGAL::Union_find< T, A >::clear ( )

reinitializes to an empty partition.

◆ end()

template<typename T , typename A >
iterator CGAL::Union_find< T, A >::end ( ) const

returns an iterator pointing beyond the last value of the partition.

◆ find() [1/2]

template<typename T , typename A >
const_handle CGAL::Union_find< T, A >::find ( const_handle  p) const

returns a canonical handle of the set that contains h, i.e., P.same_set(h,h2) iff P.find(h) == P.find(h2).

Precondition
h is a handle in P.

◆ find() [2/2]

template<typename T , typename A >
handle CGAL::Union_find< T, A >::find ( handle  h) const

◆ get_allocator()

template<typename T , typename A >
allocator CGAL::Union_find< T, A >::get_allocator ( ) const

the allocator of the partition.

◆ insert()

template<typename T , typename A >
template<class Forward_iterator >
void CGAL::Union_find< T, A >::insert ( Forward_iterator  first,
Forward_iterator  beyond 
)

inserts the range of values referenced by [first,beyond).

Template Parameters
Forward_iteratormust be a forward iterator with value type T.

◆ make_set()

template<typename T , typename A >
handle CGAL::Union_find< T, A >::make_set ( const T &  x)

creates a new singleton set containing x and returns a handle to it.

◆ number_of_sets()

template<typename T , typename A >
std::size_t CGAL::Union_find< T, A >::number_of_sets ( ) const

returns the number of disjoint sets of the partition.

◆ push_back()

template<typename T , typename A >
handle CGAL::Union_find< T, A >::push_back ( const T &  x)

same as make_set().

◆ same_set()

template<typename T , typename A >
bool CGAL::Union_find< T, A >::same_set ( const_handle  h1,
const_handle  h2 
) const

returns true iff h1 and h2 belong to the same set of P.

Precondition
h1 and h2 are in P.

◆ size() [1/2]

template<typename T , typename A >
std::size_t CGAL::Union_find< T, A >::size ( ) const

returns the number of values of the partition.

◆ size() [2/2]

template<typename T , typename A >
std::size_t CGAL::Union_find< T, A >::size ( const_handle  h) const

returns the size of the set containing h.

◆ unify_sets()

template<typename T , typename A >
void CGAL::Union_find< T, A >::unify_sets ( handle  h1,
handle  h2 
)

unites the sets of partition P containing h1 and h2.

Precondition
h1 and h2 are in P.