Structural Bioinformatics Library
Template C++ / Python API for developping structural bioinformatics applications.
T_Union_find_contains_with_map< T > Class Template Reference

Union-Find data structure where the vertices contains a data. More...

#include <Union_find.hpp>

Public Types

typedef T_Union_find_contains_with_map< T > Self
 
typedef T_Union_find_base< T, T_Union_find_vertex_data_structure_contains< T >, true > Base
 
typedef T_Union_find_vertex_data_structure_contains< T > Vertex
 Representation of a Vertex in the Union-Find data structure. More...
 
typedef Base::Independent_set_iterator Independent_set_iterator
 Iterator type over the independent set of a Union-Find Vertex. More...
 
typedef Base::Leaders_iterator Leaders_iterator
 Iterator type over all the leaders of the Union-Find data structure. More...
 

Accessors

std::size_t get_number_of_vertices (void) const
 Number of vertices in the Union-Find data structure. More...
 
Vertexoperator[] (std::size_t i)
 Access to the ith inserted vertex in the Union-Find data structrure. More...
 
const Vertexoperator[] (std::size_t i) const
 Const access to the ith inserted vertex in the Union-Find data structrure. More...
 
bool is_empty (void) const
 Check that there is no Vertex in the Union-Find data structure. More...
 
Vertexfind_vertex (T data) const
 Return the vertex associated to the given data, or return 0 if not found. More...
 
bool is_leader (const Vertex *v) const
 Check that v is a leader in the Union-Find data structure. More...
 
bool is_leader (T data) const
 Check that v is a leader in the Union-Find data structure. More...
 
bool is_singleton (const Vertex *v) const
 Check that v is in a singleton. More...
 
bool is_singleton (T data) const
 Check that v is in a singleton. More...
 

Modifiers

void reset (void)
 Separate all the vertices in the Union-Find data structure. More...
 
void clear (void)
 Remove all the vertices in the Union-Find data structure. More...
 

Union-Find Operations

Vertexmake_set (T data)
 Create a new independent set with one Vertex initialized with the input data. More...
 
Vertexfind_set (Vertex *u)
 Find the leader of the independent set containing v. More...
 
Vertexfind_set (T data)
 Find the leader of the independent set containing v. More...
 
Vertexunion_sets (Vertex *u, Vertex *v)
 Merge the (possibly different) independent sets containing u and v. More...
 
Vertexunion_sets (T data_1, T data_2)
 Merge the (possibly different) independent sets containing u and v. More...
 

Leaders

std::size_t get_number_of_independent_sets (void) const
 Access to the number of independent sets in the Union-Find data structure. More...
 
std::size_t get_size_of_independent_set (const Vertex *v) const
 Access to the size of an independent set containing a Union-Find Vertex. More...
 
std::size_t get_size_of_independent_set (T data) const
 Access to the size of an independent set containing a Union-Find Vertex. More...
 
Leaders_iterator leaders_begin (void)
 Starts the set of leaders of the Union-Find data structure. More...
 
Leaders_iterator leaders_end (void)
 Ends the set of leaders of the Union-Find data structure. More...
 

Independent Set Iterators

Independent_set_iterator independent_set_begin (Vertex *u) const
 Starts the independent set of vertices containing v. More...
 
Independent_set_iterator independent_set_begin (T data) const
 Starts the independent set of vertices containing v. More...
 
Independent_set_iterator independent_set_end (Vertex *u) const
 Ends the independent set of vertices containing v. More...
 
Independent_set_iterator independent_set_end (T data) const
 Ends the independent set of vertices containing v. More...
 

Rewind

void rewind_to_last_make_set (void)
 Rewind the Union-Find data structure before the last inserted Vertex. More...
 
void rewind_before_make_set (Vertex *v)
 Rewind the Union-Find data structure before v was inserted. More...
 
void rewind_before_make_set (T data)
 Rewind the Union-Find data structure before v was inserted. More...
 
void rewind_to_last_union_sets (void)
 Rewind the Union-Find data structure before the last union of distinct independent sets. More...
 
void rewind_before_union_sets (Vertex *u, Vertex *v)
 Rewind the Union-Find data structure before u and v were in the same independent set. More...
 
void rewind_before_union_sets (T data_1, T data_2)
 Rewind the Union-Find data structure before u and v were in the same independent set. More...
 

Accessors

bool is_leader (const Vertex *v) const
 Check that v is a leader in the Union-Find data structure. More...
 
bool is_singleton (const Vertex *v) const
 Check that v is in a singleton. More...
 

Union-Find Operations

Vertexfind_vertex (Vertex *v) const
 
Vertexmake_set (Vertex *v)
 Create a new independent set with the input Vertex. More...
 
Vertexconst_find_set (Vertex *v) const
 Const find the leader of the independent set containing v. More...
 
Vertexfind_set (Vertex *v)
 Find the leader of the independent set containing v. More...
 
Vertexunion_sets (Vertex *u, Vertex *v)
 Merge the (possibly different) independent sets containing u and v. More...
 

Algorithms

void quadratic_union (const UnionComparator &comp=UnionComparator())
 Reset the Union-Find data structure and union all the vertices that are in the same independent set related to a given comparator. More...
 
void union_from_edges (InputIterator begin, InputIterator end)
 Reset the union-Find data structure and union all the vertices that are in the same independent set related to the pairs of vertices in between [begin, end). More...
 

Leaders

std::size_t get_size_of_independent_set (const Vertex *v) const
 Access to the size of an independent set containing a Union-Find Vertex. More...
 

Independent Set Iterators

Independent_set_iterator independent_set_begin (Vertex *v) const
 Starts the independent set of vertices containing v. More...
 
Independent_set_iterator independent_set_end (Vertex *v) const
 Ends the independent set of vertices containing v. More...
 

Rewind

void rewind_before_make_set (Vertex *v)
 Rewind the Union-Find data structure before v was inserted. More...
 
void rewind_before_union_sets (Vertex *u, Vertex *v)
 Rewind the Union-Find data structure before u and v were in the same independent set. More...
 

Detailed Description

template<class T>
class SBL::CADS::T_Union_find_contains_with_map< T >

Union-Find data structure where the vertices contains a data.

The data has to be comparable with the less operator

Member Typedef Documentation

◆ Base

◆ Independent_set_iterator

Iterator type over the independent set of a Union-Find Vertex.

◆ Leaders_iterator

Iterator type over all the leaders of the Union-Find data structure.

◆ Self

◆ Vertex

Representation of a Vertex in the Union-Find data structure.

Member Function Documentation

◆ clear()

void clear ( void  )
inline

Remove all the vertices in the Union-Find data structure.

◆ const_find_set()

T_Union_find_base< T, T_Union_find_vertex_data_structure_contains< T > , InternalVertexTag >::Vertex * const_find_set ( Vertex v) const
inlineinherited

Const find the leader of the independent set containing v.

Contrarily to the non const method, there is no path compression.

◆ find_set() [1/3]

T_Union_find_contains_with_map< T >::Vertex * find_set ( data)
inline

Find the leader of the independent set containing v.

◆ find_set() [2/3]

T_Union_find_contains_with_map< T >::Vertex * find_set ( Vertex u)
inline

Find the leader of the independent set containing v.

◆ find_set() [3/3]

T_Union_find_base< T, T_Union_find_vertex_data_structure_contains< T > , InternalVertexTag >::Vertex * find_set ( Vertex v)
inlineinherited

Find the leader of the independent set containing v.

◆ find_vertex() [1/2]

T_Union_find_contains_with_map< T >::Vertex * find_vertex ( data) const
inline

Return the vertex associated to the given data, or return 0 if not found.

◆ find_vertex() [2/2]

T_Union_find_base< T, T_Union_find_vertex_data_structure_contains< T > , InternalVertexTag >::Vertex * find_vertex ( Vertex v) const
inlineinherited

◆ get_number_of_independent_sets()

std::size_t get_number_of_independent_sets ( void  ) const
inline

Access to the number of independent sets in the Union-Find data structure.

◆ get_number_of_vertices()

std::size_t get_number_of_vertices ( void  ) const
inline

Number of vertices in the Union-Find data structure.

◆ get_size_of_independent_set() [1/3]

std::size_t get_size_of_independent_set ( const Vertex v) const
inlineinherited

Access to the size of an independent set containing a Union-Find Vertex.

◆ get_size_of_independent_set() [2/3]

std::size_t get_size_of_independent_set ( const Vertex v) const
inline

Access to the size of an independent set containing a Union-Find Vertex.

◆ get_size_of_independent_set() [3/3]

std::size_t get_size_of_independent_set ( data) const
inline

Access to the size of an independent set containing a Union-Find Vertex.

◆ independent_set_begin() [1/3]

T_Union_find_contains_with_map< T >::Independent_set_iterator independent_set_begin ( data) const
inline

Starts the independent set of vertices containing v.

Precondition
v is a leader.

◆ independent_set_begin() [2/3]

T_Union_find_contains_with_map< T >::Independent_set_iterator independent_set_begin ( Vertex u) const
inline

Starts the independent set of vertices containing v.

Precondition
v is a leader.

◆ independent_set_begin() [3/3]

T_Union_find_base< T, T_Union_find_vertex_data_structure_contains< T > , InternalVertexTag >::Independent_set_iterator independent_set_begin ( Vertex v) const
inlineinherited

Starts the independent set of vertices containing v.

Precondition
v is a leader.

◆ independent_set_end() [1/3]

T_Union_find_contains_with_map< T >::Independent_set_iterator independent_set_end ( data) const
inline

Ends the independent set of vertices containing v.

Precondition
v is a leader.

◆ independent_set_end() [2/3]

T_Union_find_contains_with_map< T >::Independent_set_iterator independent_set_end ( Vertex u) const
inline

Ends the independent set of vertices containing v.

Precondition
v is a leader.

◆ independent_set_end() [3/3]

T_Union_find_base< T, T_Union_find_vertex_data_structure_contains< T > , InternalVertexTag >::Independent_set_iterator independent_set_end ( Vertex v) const
inlineinherited

Ends the independent set of vertices containing v.

Precondition
v is a leader.

◆ is_empty()

bool is_empty ( void  ) const
inline

Check that there is no Vertex in the Union-Find data structure.

◆ is_leader() [1/3]

bool is_leader ( const Vertex v) const
inlineinherited

Check that v is a leader in the Union-Find data structure.

◆ is_leader() [2/3]

bool is_leader ( const Vertex v) const
inline

Check that v is a leader in the Union-Find data structure.

◆ is_leader() [3/3]

bool is_leader ( data) const
inline

Check that v is a leader in the Union-Find data structure.

◆ is_singleton() [1/3]

bool is_singleton ( const Vertex v) const
inlineinherited

Check that v is in a singleton.

◆ is_singleton() [2/3]

bool is_singleton ( const Vertex v) const
inline

Check that v is in a singleton.

◆ is_singleton() [3/3]

bool is_singleton ( data) const
inline

Check that v is in a singleton.

◆ leaders_begin()

T_Union_find_contains_with_map< T >::Leaders_iterator leaders_begin ( void  )
inline

Starts the set of leaders of the Union-Find data structure.

◆ leaders_end()

T_Union_find_contains_with_map< T >::Leaders_iterator leaders_end ( void  )
inline

Ends the set of leaders of the Union-Find data structure.

◆ make_set() [1/2]

T_Union_find_contains_with_map< T >::Vertex * make_set ( data)
inline

Create a new independent set with one Vertex initialized with the input data.

Precondition
The InternalVertexTag Tag is set to true.
Returns
The new Vertex. Note that if the data already exists, no new vertex is created, and the existing vertex is returned instead.

◆ make_set() [2/2]

T_Union_find_base< T, T_Union_find_vertex_data_structure_contains< T > , InternalVertexTag >::Vertex * make_set ( Vertex v)
inlineinherited

Create a new independent set with the input Vertex.

Returns
The new Vertex.

◆ operator[]() [1/2]

T_Union_find_contains_with_map< T >::Vertex * operator[] ( std::size_t  i)
inline

Access to the ith inserted vertex in the Union-Find data structrure.

Precondition
i < get_number_of_vertices().

◆ operator[]() [2/2]

const T_Union_find_contains_with_map< T >::Vertex * operator[] ( std::size_t  i) const
inline

Const access to the ith inserted vertex in the Union-Find data structrure.

Precondition
i < get_number_of_vertices().

◆ quadratic_union()

void quadratic_union ( const UnionComparator &  comp = UnionComparator())
inlineinherited

Reset the Union-Find data structure and union all the vertices that are in the same independent set related to a given comparator.

Template Parameters
UnionComparatorBinary functor checking that two vertices are in the same independent set

◆ reset()

void reset ( void  )
inline

Separate all the vertices in the Union-Find data structure.

◆ rewind_before_make_set() [1/3]

void rewind_before_make_set ( data)
inline

Rewind the Union-Find data structure before v was inserted.

It does a rewind_to_last_make_set() until v is removed from the union-Find structure. Note that v is not valid anymore after this operation.

◆ rewind_before_make_set() [2/3]

void rewind_before_make_set ( Vertex v)
inlineinherited

Rewind the Union-Find data structure before v was inserted.

It does a rewind_to_last_make_set() until v is removed from the union-Find structure. Note that v is not valid anymore after this operation.

◆ rewind_before_make_set() [3/3]

void rewind_before_make_set ( Vertex v)
inline

Rewind the Union-Find data structure before v was inserted.

It does a rewind_to_last_make_set() until v is removed from the union-Find structure. Note that v is not valid anymore after this operation.

◆ rewind_before_union_sets() [1/3]

void rewind_before_union_sets ( data_1,
data_2 
)
inline

Rewind the Union-Find data structure before u and v were in the same independent set.

It does a rewind_to_last_union_sets() until u and v are not in the same independent set.

◆ rewind_before_union_sets() [2/3]

void rewind_before_union_sets ( Vertex u,
Vertex v 
)
inlineinherited

Rewind the Union-Find data structure before u and v were in the same independent set.

It does a rewind_to_last_union_sets() until u and v are not in the same independent set.

◆ rewind_before_union_sets() [3/3]

void rewind_before_union_sets ( Vertex u,
Vertex v 
)
inline

Rewind the Union-Find data structure before u and v were in the same independent set.

It does a rewind_to_last_union_sets() until u and v are not in the same independent set.

◆ rewind_to_last_make_set()

void rewind_to_last_make_set ( void  )
inline

Rewind the Union-Find data structure before the last inserted Vertex.

It pops the stack until an insertion is found, and undo all operations encountered.

◆ rewind_to_last_union_sets()

void rewind_to_last_union_sets ( void  )
inline

Rewind the Union-Find data structure before the last union of distinct independent sets.

It pops the stack until an union is found, and undo all operations encountered.

◆ union_from_edges()

void union_from_edges ( InputIterator  begin,
InputIterator  end 
)
inlineinherited

Reset the union-Find data structure and union all the vertices that are in the same independent set related to the pairs of vertices in between [begin, end).

Template Parameters
InputIteratorIterator over a set of pairs of vertices.

◆ union_sets() [1/3]

T_Union_find_contains_with_map< T >::Vertex * union_sets ( data_1,
data_2 
)
inline

Merge the (possibly different) independent sets containing u and v.

Returns
The leader of the independent set containing u and v.

◆ union_sets() [2/3]

T_Union_find_base< T, T_Union_find_vertex_data_structure_contains< T > , InternalVertexTag >::Vertex * union_sets ( Vertex u,
Vertex v 
)
inlineinherited

Merge the (possibly different) independent sets containing u and v.

Returns
The leader of the independent set containing u and v.

◆ union_sets() [3/3]

T_Union_find_contains_with_map< T >::Vertex * union_sets ( Vertex u,
Vertex v 
)
inline

Merge the (possibly different) independent sets containing u and v.

Returns
The leader of the independent set containing u and v.