CGAL 5.4 - Profiling tools, Hash Map, Union-find, Modifiers
|
#include <CGAL/Union_find.h>
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 | |
typedef unspecified_type | value_type |
values stored in items (equal to T ). | |
typedef unspecified_type | handle |
handle to values. | |
typedef unspecified_type | iterator |
iterator over values. | |
typedef unspecified_type | allocator |
allocator. | |
Creation | |
Union_find () | |
creates an instance P of type Union_find<T,A> and initializes it to the empty partition. | |
Operations | |
allocator | get_allocator () const |
the allocator of the partition. | |
std::size_t | number_of_sets () const |
returns the number of disjoint sets of the partition. | |
std::size_t | size () const |
returns the number of values of the partition. | |
std::size_t | bytes () const |
returns the memory consumed by the partition. | |
std::size_t | size (const_handle h) const |
returns the size of the set containing h . | |
void | clear () |
reinitializes to an empty partition. | |
handle | make_set (const T &x) |
creates a new singleton set containing x and returns a handle to it. | |
handle | push_back (const T &x) |
same as make_set() . | |
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. | |
iterator | end () const |
returns an iterator pointing beyond the last value of the partition. | |
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)
.
h
is a handle in P
. void CGAL::Union_find< T, A >::insert | ( | Forward_iterator | first, |
Forward_iterator | beyond | ||
) |
inserts the range of values referenced by [first,beyond)
.
Forward_iterator | must be a forward iterator with value type T . |
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
.
h1
and h2
are in P
. void CGAL::Union_find< T, A >::unify_sets | ( | handle | h1, |
handle | h2 | ||
) |
unites the sets of partition P
containing h1
and h2
.
h1
and h2
are in P
.