CBMC
Public Types | Public Member Functions | Protected Types | Protected Attributes | Private Types | Private Attributes | List of all members
union_find< T, hasht > Class Template Referencefinal

#include <union_find.h>

+ Inheritance diagram for union_find< T, hasht >:
+ Collaboration diagram for union_find< T, hasht >:

Public Types

using size_type = typename numbering_typet::size_type
 
using iterator = typename numbering_typet::iterator
 
using const_iterator = typename numbering_typet::const_iterator
 

Public Member Functions

bool make_union (const T &a, const T &b)
 
bool make_union (const_iterator it_a, const_iterator it_b)
 
bool same_set (const T &a, const T &b) const
 
bool same_set (const_iterator it_a, const_iterator it_b) const
 
const T & find (const_iterator it) const
 
const T & find (const T &a)
 
size_type find_number (const_iterator it) const
 
size_type find_number (size_type a) const
 
size_type find_number (const T &a)
 
bool is_root_number (size_type a) const
 
bool is_root (const T &a) const
 
bool is_root (const_iterator it) const
 
size_type number (const T &a)
 
void clear ()
 
void isolate (const_iterator it)
 
void isolate (const T &a)
 
std::optional< number_type > get_number (const T &a) const
 
size_t size () const
 
T & operator[] (size_type t)
 
const T & operator[] (size_type t) const
 
iterator begin ()
 
const_iterator begin () const
 
const_iterator cbegin () const
 
iterator end ()
 
const_iterator end () const
 
const_iterator cend () const
 

Protected Types

using subt = numbering_typet
 

Protected Attributes

unsigned_union_find uuf
 

Private Types

using numbering_typet = numberingt< T, hasht >
 
using number_type = typename numbering_typet::number_type
 

Private Attributes

numbering_typet numbers
 

Detailed Description

template<typename T, typename hasht = std::hash<T>>
class union_find< T, hasht >

Template Parameters
TThe type of values stored.
hashtThe type of hash used for looking up the value numbering.

Definition at line 138 of file union_find.h.

Member Typedef Documentation

◆ const_iterator

template<typename T , typename hasht = std::hash<T>>
using union_find< T, hasht >::const_iterator = typename numbering_typet::const_iterator

Definition at line 152 of file union_find.h.

◆ iterator

template<typename T , typename hasht = std::hash<T>>
using union_find< T, hasht >::iterator = typename numbering_typet::iterator

Definition at line 150 of file union_find.h.

◆ number_type

template<typename T , typename hasht = std::hash<T>>
using union_find< T, hasht >::number_type = typename numbering_typet::number_type
private

Definition at line 144 of file union_find.h.

◆ numbering_typet

template<typename T , typename hasht = std::hash<T>>
using union_find< T, hasht >::numbering_typet = numberingt<T, hasht>
private

Definition at line 140 of file union_find.h.

◆ size_type

template<typename T , typename hasht = std::hash<T>>
using union_find< T, hasht >::size_type = typename numbering_typet::size_type

Definition at line 148 of file union_find.h.

◆ subt

template<typename T , typename hasht = std::hash<T>>
using union_find< T, hasht >::subt = numbering_typet
protected

Definition at line 283 of file union_find.h.

Member Function Documentation

◆ begin() [1/2]

template<typename T , typename hasht = std::hash<T>>
iterator union_find< T, hasht >::begin ( )
inline

Definition at line 273 of file union_find.h.

◆ begin() [2/2]

template<typename T , typename hasht = std::hash<T>>
const_iterator union_find< T, hasht >::begin ( ) const
inline

Definition at line 274 of file union_find.h.

◆ cbegin()

template<typename T , typename hasht = std::hash<T>>
const_iterator union_find< T, hasht >::cbegin ( ) const
inline

Definition at line 275 of file union_find.h.

◆ cend()

template<typename T , typename hasht = std::hash<T>>
const_iterator union_find< T, hasht >::cend ( ) const
inline

Definition at line 279 of file union_find.h.

◆ clear()

template<typename T , typename hasht = std::hash<T>>
void union_find< T, hasht >::clear ( void  )
inline

Definition at line 247 of file union_find.h.

◆ end() [1/2]

template<typename T , typename hasht = std::hash<T>>
iterator union_find< T, hasht >::end ( )
inline

Definition at line 277 of file union_find.h.

◆ end() [2/2]

template<typename T , typename hasht = std::hash<T>>
const_iterator union_find< T, hasht >::end ( ) const
inline

Definition at line 278 of file union_find.h.

◆ find() [1/2]

template<typename T , typename hasht = std::hash<T>>
const T& union_find< T, hasht >::find ( const T &  a)
inline

Definition at line 196 of file union_find.h.

◆ find() [2/2]

template<typename T , typename hasht = std::hash<T>>
const T& union_find< T, hasht >::find ( const_iterator  it) const
inline

Definition at line 191 of file union_find.h.

◆ find_number() [1/3]

template<typename T , typename hasht = std::hash<T>>
size_type union_find< T, hasht >::find_number ( const T &  a)
inline

Definition at line 211 of file union_find.h.

◆ find_number() [2/3]

template<typename T , typename hasht = std::hash<T>>
size_type union_find< T, hasht >::find_number ( const_iterator  it) const
inline

Definition at line 201 of file union_find.h.

◆ find_number() [3/3]

template<typename T , typename hasht = std::hash<T>>
size_type union_find< T, hasht >::find_number ( size_type  a) const
inline

Definition at line 206 of file union_find.h.

◆ get_number()

template<typename T , typename hasht = std::hash<T>>
std::optional<number_type> union_find< T, hasht >::get_number ( const T &  a) const
inline

Definition at line 263 of file union_find.h.

◆ is_root() [1/2]

template<typename T , typename hasht = std::hash<T>>
bool union_find< T, hasht >::is_root ( const T &  a) const
inline

Definition at line 221 of file union_find.h.

◆ is_root() [2/2]

template<typename T , typename hasht = std::hash<T>>
bool union_find< T, hasht >::is_root ( const_iterator  it) const
inline

Definition at line 230 of file union_find.h.

◆ is_root_number()

template<typename T , typename hasht = std::hash<T>>
bool union_find< T, hasht >::is_root_number ( size_type  a) const
inline

Definition at line 216 of file union_find.h.

◆ isolate() [1/2]

template<typename T , typename hasht = std::hash<T>>
void union_find< T, hasht >::isolate ( const T &  a)
inline

Definition at line 258 of file union_find.h.

◆ isolate() [2/2]

template<typename T , typename hasht = std::hash<T>>
void union_find< T, hasht >::isolate ( const_iterator  it)
inline

Definition at line 253 of file union_find.h.

◆ make_union() [1/2]

template<typename T , typename hasht = std::hash<T>>
bool union_find< T, hasht >::make_union ( const T &  a,
const T &  b 
)
inline

Definition at line 155 of file union_find.h.

◆ make_union() [2/2]

template<typename T , typename hasht = std::hash<T>>
bool union_find< T, hasht >::make_union ( const_iterator  it_a,
const_iterator  it_b 
)
inline

Definition at line 164 of file union_find.h.

◆ number()

template<typename T , typename hasht = std::hash<T>>
size_type union_find< T, hasht >::number ( const T &  a)
inline

Definition at line 235 of file union_find.h.

◆ operator[]() [1/2]

template<typename T , typename hasht = std::hash<T>>
T& union_find< T, hasht >::operator[] ( size_type  t)
inline

Definition at line 270 of file union_find.h.

◆ operator[]() [2/2]

template<typename T , typename hasht = std::hash<T>>
const T& union_find< T, hasht >::operator[] ( size_type  t) const
inline

Definition at line 271 of file union_find.h.

◆ same_set() [1/2]

template<typename T , typename hasht = std::hash<T>>
bool union_find< T, hasht >::same_set ( const T &  a,
const T &  b 
) const
inline

Definition at line 173 of file union_find.h.

◆ same_set() [2/2]

template<typename T , typename hasht = std::hash<T>>
bool union_find< T, hasht >::same_set ( const_iterator  it_a,
const_iterator  it_b 
) const
inline

Definition at line 186 of file union_find.h.

◆ size()

template<typename T , typename hasht = std::hash<T>>
size_t union_find< T, hasht >::size ( ) const
inline

Definition at line 268 of file union_find.h.

Member Data Documentation

◆ numbers

template<typename T , typename hasht = std::hash<T>>
numbering_typet union_find< T, hasht >::numbers
private

Definition at line 141 of file union_find.h.

◆ uuf

template<typename T , typename hasht = std::hash<T>>
unsigned_union_find union_find< T, hasht >::uuf
protected

Definition at line 282 of file union_find.h.

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