#include <disjoint_set.h>
Classes | |
struct | DisjointSetNode |
struct | SimpleObjHashFunc |
Public Member Functions | |
DisjointSet () | |
OBJECT_TYPE * | FindSet (OBJECT_TYPE *x) |
void | MakeSet (OBJECT_TYPE *x) |
void | Union (OBJECT_TYPE *x, OBJECT_TYPE *y) |
Protected Attributes | |
std::vector< DisjointSetNode > | nodes |
Private Types | |
typedef std::pair< hIterator, bool > | hInsertResult |
typedef std::unordered_map < OBJECT_TYPE *, int > ::iterator | hIterator |
typedef std::pair < ObjectPointer, int > | hPair |
typedef OBJECT_TYPE * | ObjectPointer |
Private Member Functions | |
void | Link (OBJECT_TYPE *x, OBJECT_TYPE *y) |
Private Attributes | |
std::unordered_map < OBJECT_TYPE *, int > | inserted_objects |
Given a set of elements, it is often useful to break them up or partition them into a number of separate, nonoverlapping groups. A disjoint-set data structure is a data structure that keeps track of such a partitioning. See Diskoint-set data structure on Wikipedia for more details.
Definition at line 39 of file disjoint_set.h.
typedef std::pair< hIterator, bool > vcg::DisjointSet< OBJECT_TYPE >::hInsertResult [private] |
Definition at line 62 of file disjoint_set.h.
typedef std::unordered_map< OBJECT_TYPE*, int >::iterator vcg::DisjointSet< OBJECT_TYPE >::hIterator [private] |
Definition at line 60 of file disjoint_set.h.
typedef std::pair< ObjectPointer, int > vcg::DisjointSet< OBJECT_TYPE >::hPair [private] |
Definition at line 53 of file disjoint_set.h.
typedef OBJECT_TYPE* vcg::DisjointSet< OBJECT_TYPE >::ObjectPointer [private] |
Definition at line 52 of file disjoint_set.h.
vcg::DisjointSet< OBJECT_TYPE >::DisjointSet | ( | ) | [inline] |
Default constructor
Definition at line 69 of file disjoint_set.h.
OBJECT_TYPE* vcg::DisjointSet< OBJECT_TYPE >::FindSet | ( | OBJECT_TYPE * | x | ) | [inline] |
Determine which group a particular element is in.
Definition at line 95 of file disjoint_set.h.
void vcg::DisjointSet< OBJECT_TYPE >::Link | ( | OBJECT_TYPE * | x, |
OBJECT_TYPE * | y | ||
) | [inline, private] |
Definition at line 108 of file disjoint_set.h.
void vcg::DisjointSet< OBJECT_TYPE >::MakeSet | ( | OBJECT_TYPE * | x | ) | [inline] |
Makes a group containing only a given element (a singleton).
Definition at line 74 of file disjoint_set.h.
void vcg::DisjointSet< OBJECT_TYPE >::Union | ( | OBJECT_TYPE * | x, |
OBJECT_TYPE * | y | ||
) | [inline] |
Combine or merge two groups into a single group.
Definition at line 85 of file disjoint_set.h.
std::unordered_map< OBJECT_TYPE*, int > vcg::DisjointSet< OBJECT_TYPE >::inserted_objects [private] |
Definition at line 59 of file disjoint_set.h.
std::vector< DisjointSetNode > vcg::DisjointSet< OBJECT_TYPE >::nodes [protected] |
Definition at line 126 of file disjoint_set.h.