disjointFamily Class Template Reference
[Set families]

Efficient implementation of the disjoint set union process. More...

#include <disjointFamily.h>

Inheritance diagram for disjointFamily:

Public Member Functions
	disjointFamily (TItem _n, goblinController &_CT) throw ()
	~disjointFamily () throw ()
void	Init () throw ()
unsigned long	Size () const throw ()
unsigned long	Allocated () const throw ()
char *	Display () const throw ()
void	Bud (TItem v) throw (ERRange)
void	Merge (TItem u, TItem v) throw (ERRange)
TItem	Find (TItem v) const throw (ERRange)

---

Detailed Description

template<class TItem>
class disjointFamily< TItem >

Efficient implementation of the disjoint set union process.

---

Constructor & Destructor Documentation

disjointFamily (  TItem  _n, goblinController &  _CT )  throw ()

~disjointFamily (   )  throw ()

---

Member Function Documentation

unsigned long Allocated (   )  const throw ()

Reimplemented from managedObject.

void Bud (  TItem  v  )  throw (ERRange)

Start a single element set. Parameters: v  An index ranged [0,1,..,n-1] After this operation, it is Find(v)==v.

char * Display (   )  const throw () [virtual]

Unconditional display of data objects. Reimplemented from managedObject.

TItem Find (  TItem  v  )  const throw (ERRange)

Retrieve the set containing a given element. Parameters: v  An index ranged [0,1,..,n-1] Returns: An index ranged [0,1,..,n-1] or UNDEFINED This returns the index of an arbitrary but fixed element in the same set as v, the so-called canonical element in this set. Only when sets are merged, the canonical element changes. In order to check if two elements x,y are in the same set, it is sufficient to evaluate Find(x)==Find(y) and Find(u)!=UNDEFINED. If the context parameter methDSU is set, Find() does not only lookup the canonical element, but also performs some path compression to reduce the future lookup times.

void Init (   )  throw ()

Initialize the disjoint node set structure. After this operation, it is Find(v)==UNDEFINED for every element v.

void Merge (  TItem  u, TItem  v )  throw (ERRange)

Merge two disjoint sets represented by arbitrary elements. Parameters: u  An index ranged [0,1,..,n-1] v  An index ranged [0,1,..,n-1] After this operation, it is Find(u)==Find(v).

unsigned long Size (   )  const throw () [virtual]

Implements goblinRootObject.