grafalgo::Partition Class Reference

Maintain a partition on positive integers 1..n. More...

#include <Partition.h>

Inheritance diagram for grafalgo::Partition:

Collaboration diagram for grafalgo::Partition:

List of all members.

Classes
struct	pnode
Public Member Functions
	Partition (int=26, int=0)
	Initialize partition so that every element is in separate set.
	~Partition ()
	Destructor for Partition.
void	clear ()
	Inititialize data structure.
void	clear (int)
void	resize (int)
	Resize a Partition object.
void	expand (int)
	Expand the space available for this Partition.
void	copyFrom (const Partition &)
	Copy into list from source.
index	link (index, index)
	Combine two sets.
index	find (index)
	Find and return the canonical element of a set.
string &	toString (string &) const
	Create a string representation of the partition.
Private Member Functions
index	findroot (int) const
	Get the canonical element of a set without restructuring the set.
void	makeSpace (int)
	Allocate and initialize space for list.
void	freeSpace ()
	Free dynamic storage used by list.
Private Attributes
struct grafalgo::Partition::pnode *	node
	vector of nodes

---

Detailed Description

Maintain a partition on positive integers 1..n.

Also known as "disjoint sets" and "union-find".

Definition at line 20 of file Partition.h.

---

Constructor & Destructor Documentation

grafalgo::Partition::Partition	(	int	nn = 26,
		int	noOpt1 = 0
	)

Initialize partition so that every element is in separate set.

Parameters:

nn	defines the index range on which the partition is defined

Definition at line 19 of file Partition.cpp.

Here is the call graph for this function:

grafalgo::Partition::~Partition

(

)

Destructor for Partition.

Definition at line 24 of file Partition.cpp.

Here is the call graph for this function:

---

Member Function Documentation

void grafalgo::Partition::clear

(

)

[virtual]

Inititialize data structure.

Implements grafalgo::Adt.

Definition at line 68 of file Partition.cpp.

Here is the caller graph for this function:

void grafalgo::Partition::copyFrom

(

const Partition &

source

)

Copy into list from source.

Definition at line 73 of file Partition.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

void grafalgo::Partition::expand

(

int

size

)

[virtual]

Expand the space available for this Partition.

Rebuilds old value in new space.

Parameters:

size	is the size of the resized object.

Implements grafalgo::Adt.

Definition at line 59 of file Partition.cpp.

Here is the call graph for this function:

index grafalgo::Partition::find

(

index

x

)

Find and return the canonical element of a set.

Parameters:

x	is an index in some set

Returns:

the canonical element of the set containing x

Definition at line 86 of file Partition.cpp.

Here is the caller graph for this function:

int grafalgo::Partition::findroot

(

int

x

)

const [private]

Get the canonical element of a set without restructuring the set.

Parameters:

x	is an index in some set

Returns:

the canonical element of the set containing x

Definition at line 111 of file Partition.cpp.

Here is the caller graph for this function:

void grafalgo::Partition::freeSpace

(

)

[private]

Free dynamic storage used by list.

Definition at line 41 of file Partition.cpp.

Here is the caller graph for this function:

index grafalgo::Partition::link	(	index	x,
		index	y
	)

Combine two sets.

Parameters:

x	is the canonical element of some set.
y	is the canonical element of another (distinct) set

Returns:

the canonical element of the set obtained by combining the given sets

Definition at line 99 of file Partition.cpp.

Here is the caller graph for this function:

void grafalgo::Partition::makeSpace

(

int

size

)

[private]

Allocate and initialize space for list.

Parameters:

size	is number of index values to provide space for

Definition at line 29 of file Partition.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

void grafalgo::Partition::resize

(

int

size

)

[virtual]

Resize a Partition object.

The old value is discarded.

Parameters:

size	is the size of the resized object.

Implements grafalgo::Adt.

Definition at line 47 of file Partition.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

string & grafalgo::Partition::toString

(

string &

s

)

const [virtual]

Create a string representation of the partition.

Parameters:

s	is a reference to a string in which the partition is returned.

Returns:

a reference to s

Implements grafalgo::Adt.

Definition at line 120 of file Partition.cpp.

Here is the call graph for this function:

---

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

• /Users/jst/src/grafalgo/cpp/include/Partition.h
• /Users/jst/src/grafalgo/cpp/dataStructures/basic/Partition.cpp