grafalgo::PathSet Class Reference

Data structure that represents a collection of paths. More...

#include <PathSet.h>

Inheritance diagram for grafalgo::PathSet:

Collaboration diagram for grafalgo::PathSet:

List of all members.

Classes
struct	PathCostPair
struct	PathNode
struct	PathPair
Public Member Functions
	PathSet (int)
	Constructor for PathSet class.
	~PathSet ()
	Destructor for PathSet class.
void	clear ()
	Reinitialize data structure, creating single node trees.
void	resize (int)
	Resize a PathSet object, discarding old value.
void	expand (int)
	Expand the space available for this ojbect.
void	copyFrom (const PathSet &)
	Copy another object to this one.
path	findpath (index)
	Return the canonical element of some path.
index	findtail (path)
	Return the last node in a path.
PathCostPair	findpathcost (path)
	Find the the last node on a path that has minimum cost.
index	findtreeroot (index)
	Find the root of tree represent a path, while not restructuring the tree.
cost	nodeCost (index) const
	Determine the cost of a node without restructuring tree.
void	addpathcost (path, cost)
	Add to the cost of every node in a path.
path	join (path, index, path)
	Join two paths at a node.
PathPair	split (index)
	Divide a path at a node.
string &	path2string (path, string &) const
	Create a string representation of a path.
string &	pathTree2string (path, string &) const
	Create a string representation of the tree representing a path.
string &	toString (string &) const
	Create a string representation of this object.
Protected Member Functions
index	splay (index)
	Perform a splay operation on the binary search tree representing a path.
void	splaystep (index)
	Perform a single splay step.
void	rotate (index)
	Perform a rotation in a search tree representing a path.
void	makeSpace (int)
	Allocate and initialize space for PathSet.
void	freeSpace ()
	Free dynamic storage used by PathSet.
Protected Attributes
PathNode *	pnode
	pnode[u] contains info for node u

---

Detailed Description

Data structure that represents a collection of paths.

Paths are defined on nodes identified by index values. Each path has a "canonical element" which serves to represent the path in method calls. Internally, paths are represented as binary search trees and the roots of the BSTs serve as the canonical elements. Note that the canonical element of a tree may change if method calls restructure the underlying tree.

Definition at line 32 of file PathSet.h.

---

Constructor & Destructor Documentation

grafalgo::PathSet::PathSet

(

int

size

)

Constructor for PathSet class.

Parameters:

size	defines the index range for the constructed object.

Definition at line 21 of file PathSet.cpp.

Here is the call graph for this function:

grafalgo::PathSet::~PathSet

(

)

Destructor for PathSet class.

Definition at line 26 of file PathSet.cpp.

Here is the call graph for this function:

---

Member Function Documentation

void grafalgo::PathSet::addpathcost	(	path	q,
		cost	x
	)

Add to the cost of every node in a path.

Parameters:

q	is the canonical element of some path
x	is the amount to be added to the costs of the nodes in the path

Definition at line 181 of file PathSet.cpp.

Here is the caller graph for this function:

void grafalgo::PathSet::clear

(

)

[virtual]

Reinitialize data structure, creating single node trees.

Implements grafalgo::Adt.

Definition at line 50 of file PathSet.cpp.

Here is the caller graph for this function:

void grafalgo::PathSet::copyFrom

(

const PathSet &

source

)

Copy another object to this one.

Parameters:

source

is object to be copied to this one

Definition at line 79 of file PathSet.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

void grafalgo::PathSet::expand

(

int

size

)

[virtual]

Expand the space available for this ojbect.

Rebuilds old value in new space.

Parameters:

size	is the size of the expanded object.

Implements grafalgo::Adt.

Definition at line 71 of file PathSet.cpp.

Here is the call graph for this function:

path grafalgo::PathSet::findpath

(

index

i

)

Return the canonical element of some path.

Parameters:

i	is a node in some path

Returns:

the node that is the canonical element of the path at the start of the operation; the operation performs a splay at i, so after the operation i is the canonical element.

Definition at line 159 of file PathSet.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

PathSet::PathCostPair grafalgo::PathSet::findpathcost

(

path

q

)

Find the the last node on a path that has minimum cost.

Parameters:

q	is the canonical element of some path

Returns:

a pair containing the last node on the path that has minimum cost and its cost

Definition at line 188 of file PathSet.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

path grafalgo::PathSet::findtail

(

path

q

)

Return the last node in a path.

Parameters:

q	is the canonical element of some path

Returns:

the last node in the path containing q

Definition at line 170 of file PathSet.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

path grafalgo::PathSet::findtreeroot

(

index

i

)

Find the root of tree represent a path, while not restructuring the tree.

This is used mainly for constructing a string representation of a path.

Parameters:

i	is a node in some path

Returns:

the root of the search tree containing i

Definition at line 207 of file PathSet.cpp.

Here is the caller graph for this function:

void grafalgo::PathSet::freeSpace

(

)

[protected]

Free dynamic storage used by PathSet.

Definition at line 45 of file PathSet.cpp.

Here is the caller graph for this function:

path grafalgo::PathSet::join	(	path	r,
		index	i,
		path	q
	)

Join two paths at a node.

Parameters:

r	is the canonical element of some path
i	is an isolated node (equivalently, it is in a length 1 path)
q	is the canonical element of some path

Returns:

the new path formed by combining r,i and q (so r is the first part of the resultant path, then i, then q); this new path replaces the original paths

Definition at line 220 of file PathSet.cpp.

Here is the caller graph for this function:

void grafalgo::PathSet::makeSpace

(

int

size

)

[protected]

Allocate and initialize space for PathSet.

Parameters:

size	is number of index values to provide space for

Definition at line 31 of file PathSet.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

cost grafalgo::PathSet::nodeCost

(

index

i

)

const

Determine the cost of a node without restructuring tree.

This method is used mainly to construct a string representation of a path.

Parameters:

i	is a node in some path

Returns:

the cost of node i

Definition at line 276 of file PathSet.cpp.

Here is the caller graph for this function:

string & grafalgo::PathSet::path2string	(	path	q,
		string &	s
	)		const

Create a string representation of a path.

Parameters:

q	is the canonical element of some path
s	is a string in which the result is returned

Returns:

a referece to s

Definition at line 288 of file PathSet.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

string & grafalgo::PathSet::pathTree2string	(	path	q,
		string &	s
	)		const

Create a string representation of the tree representing a path.

Parameters:

q	is the canonical element of some path
s	is a string in which the result is returned

Returns:

a referece to s

Definition at line 304 of file PathSet.cpp.

Here is the call graph for this function:

void grafalgo::PathSet::resize

(

int

size

)

[virtual]

Resize a PathSet object, discarding old value.

Parameters:

size	is the size of the resized object.

Implements grafalgo::Adt.

Definition at line 59 of file PathSet.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

void grafalgo::PathSet::rotate

(

index

x

)

[protected]

Perform a rotation in a search tree representing a path.

Parameters:

x	is a node in some path; the operation performs a rotation at the parent of x, moving x up into its parent's position.

Definition at line 117 of file PathSet.cpp.

Here is the caller graph for this function:

index grafalgo::PathSet::splay

(

index

x

)

[protected]

Perform a splay operation on the binary search tree representing a path.

Parameters:

x	is a node in some path; the operation does a splay operation that moves x to the root of the search tree that represents the path containing x

Definition at line 94 of file PathSet.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

void grafalgo::PathSet::splaystep

(

index

x

)

[protected]

Perform a single splay step.

Parameters:

x	is a node in some path

Definition at line 102 of file PathSet.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

PathSet::PathPair grafalgo::PathSet::split

(

index

i

)

Divide a path at a node.

Parameters:

i	is a node in some path; the operation splits the path into three parts, the original portion of the path that precedes i, i itself, and the portion of the original path that follows i

Returns:

the a pair consisting of the two new path segments

Definition at line 248 of file PathSet.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

string & grafalgo::PathSet::toString

(

string &

s

)

const [virtual]

Create a string representation of this object.

Parameters:

s	is a string in which the result is returned

Returns:

a referece to s

Implements grafalgo::Adt.

Definition at line 322 of file PathSet.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/PathSet.h
• /Users/jst/src/grafalgo/cpp/dataStructures/advanced/PathSet.cpp