grafalgo::BstSet Class Reference

Data structure that represents a collection of "sorted sets". More...

#include <BstSet.h>

Inheritance diagram for grafalgo::BstSet:

Collaboration diagram for grafalgo::BstSet:

List of all members.

Classes
struct	BstNode
struct	BstPair
Public Member Functions
	BstSet (int)
	Constructor for BstSet class.
	~BstSet ()
	Destructor for BstSet class.
void	clear ()
	Reinitialize data structure, creating single node trees.
void	resize (int)
	Resize a BstSet object, discarding old value.
void	expand (int)
	Expand the space available for this ojbect.
void	copyFrom (const BstSet &)
	Copy another object to this one.
keytyp	key (index) const
	Get the key of an item.
bst	find (index) const
	Get the root of a bst.
index	first (bst) const
	Return the "first" node in a bst.
index	last (bst) const
	Return the "last" node in a bst.
index	suc (index) const
	Return the successor of a node in a bst.
index	pred (index) const
	Return the predecessor of a node in a bst.
index	access (keytyp, bst &) const
	Get the item with a specified key value.
void	setkey (index, keytyp)
	Set the key of an item.
bool	insert (index, bst &)
	Insert item into a bst.
void	remove (index, bst &)
	Remove an node from a bst.
bst	join (bst, index, bst)
	Form new bst by combining two bsts at a node.
BstSet::BstPair	split (index, bst)
	Divide a bst at a node.
string &	bst2string (bst, string &) const
	Create a string representation of a bst.
string &	toString (string &) const
	Create a string representation of this object.
Protected Member Functions
virtual void	swap (index, index)
	Swap the positions of two nodes in the same tree.
virtual void	rotate (index)
	Perform a rotation in a search tree.
index	sibling (index, index)
	Get the sibling of a tree node.
index	remove (index)
virtual string &	node2string (index, string &) const
	Create a string representation of a node in a bst.
void	makeSpace (int)
	Allocate and initialize space for BstSet.
void	freeSpace ()
	Free dynamic storage used by BstSet.
Protected Attributes
BstNode *	node

---

Detailed Description

Data structure that represents a collection of "sorted sets".

Items in the same set have distinct keys. Sets are represented by binary search trees, with items represented by tree nodes. Items (nodes) are identified by integers 1..n where n is specified when an object is constructed.

Definition at line 26 of file BstSet.h.

---

Constructor & Destructor Documentation

grafalgo::BstSet::BstSet

(

int

size

)

Constructor for BstSet class.

Parameters:

size	defines the index range for the constructed object.

Definition at line 20 of file BstSet.cpp.

Here is the call graph for this function:

grafalgo::BstSet::~BstSet

(

)

Destructor for BstSet class.

Definition at line 25 of file BstSet.cpp.

Here is the call graph for this function:

---

Member Function Documentation

index grafalgo::BstSet::access	(	keytyp	k,
		bst &	t
	)		const

Get the item with a specified key value.

Parameters:

k	is a key value
t	is a reference to the root of some bst; if the operation modifies the root, then s will change

Returns:

the item in s that has key value k, or 0 if there is no such item

Definition at line 127 of file BstSet.cpp.

Here is the caller graph for this function:

string & grafalgo::BstSet::bst2string	(	bst	t,
		string &	s
	)		const

Create a string representation of a bst.

Parameters:

t	is the root of some bst
s	is a string in which the result will be returned

Returns:

a reference to s

Definition at line 331 of file BstSet.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

void grafalgo::BstSet::clear

(

)

[virtual]

Reinitialize data structure, creating single node trees.

Implements grafalgo::Adt.

Reimplemented in grafalgo::BalBstSet, and grafalgo::DkBstSet.

Definition at line 49 of file BstSet.cpp.

Here is the caller graph for this function:

void grafalgo::BstSet::copyFrom

(

const BstSet &

source

)

Copy another object to this one.

Parameters:

source

is object to be copied to this one

Definition at line 78 of file BstSet.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

void grafalgo::BstSet::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.

Reimplemented in grafalgo::BalBstSet, and grafalgo::DkBstSet.

Definition at line 70 of file BstSet.cpp.

Here is the call graph for this function:

bst grafalgo::BstSet::find

(

index

i

)

const

Get the root of a bst.

Parameters:

i	is the index of a node in some bst

Returns:

the root of the bst containing i; this method does not restructure the search tree

Definition at line 115 of file BstSet.cpp.

Here is the caller graph for this function:

index grafalgo::BstSet::first

(

bst

t

)

const

Return the "first" node in a bst.

This operation does not restructure the underlying search tree.

Parameters:

t	is the root of some bst

Returns:

the node with smallest key1 value in s

Reimplemented in grafalgo::DkBstSet.

Definition at line 142 of file BstSet.cpp.

void grafalgo::BstSet::freeSpace

(

)

[protected]

Free dynamic storage used by BstSet.

Reimplemented in grafalgo::BalBstSet, and grafalgo::DkBstSet.

Definition at line 44 of file BstSet.cpp.

Here is the caller graph for this function:

bool grafalgo::BstSet::insert	(	index	i,
		bst &	t
	)

Insert item into a bst.

Parameters:

i	is a singleton bst
t	is a reference to the root of some bst; if the insertion operation changes the root, t will be changed

Returns:

true on success, false on failure

Reimplemented in grafalgo::BalBstSet, and grafalgo::SaBstSet.

Definition at line 193 of file BstSet.cpp.

bst grafalgo::BstSet::join	(	bst	t1,
		index	i,
		bst	t2
	)

Form new bst by combining two bsts at a node.

Parameters:

t1	is the root of some bst
t2	is the root of some bst
i	is a singleton item with key value larger than those of the items in t1 and smaller than those of the items in t2

Returns:

new bst formed by merging t1, i and t2

Reimplemented in grafalgo::BalBstSet, and grafalgo::DkBstSet.

Definition at line 281 of file BstSet.cpp.

Here is the caller graph for this function:

keytyp grafalgo::BstSet::key

(

index

i

)

const [inline]

Get the key of an item.

Parameters:

i	is the index of an item in a bst

Returns:

the key of i

Definition at line 81 of file BstSet.h.

Here is the caller graph for this function:

index grafalgo::BstSet::last

(

bst

t

)

const

Return the "last" node in a bst.

This operation does not restructure the underlying search tree.

Parameters:

t	is the root of some bst

Returns:

the node with smallest key1 value in s

Definition at line 152 of file BstSet.cpp.

void grafalgo::BstSet::makeSpace

(

int

size

)

[protected]

Allocate and initialize space for BstSet.

Parameters:

size	is number of index values to provide space for

Reimplemented in grafalgo::BalBstSet, and grafalgo::DkBstSet.

Definition at line 30 of file BstSet.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

string & grafalgo::BstSet::node2string	(	index	i,
		string &	s
	)		const [protected, virtual]

Create a string representation of a node in a bst.

Parameters:

i	is a node in some bst
s	is a string in which the result will be returned

Returns:

a reference to s

Reimplemented in grafalgo::BalBstSet, and grafalgo::DkBstSet.

Definition at line 315 of file BstSet.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

index grafalgo::BstSet::pred

(

index

i

)

const

Return the predecessor of a node in a bst.

This operation does not restructure the underlying search tree.

Parameters:

i	is a node in some bst

Returns:

the node with largest key1 value in the bst

Definition at line 177 of file BstSet.cpp.

void grafalgo::BstSet::remove	(	index	i,
		bst &	t
	)

Remove an node from a bst.

Parameters:

i	is a node in some bst
t	is a reference to the root of some bst; if the operation changes the root, t will be changed

Reimplemented in grafalgo::BalBstSet, and grafalgo::SaBstSet.

Definition at line 253 of file BstSet.cpp.

Here is the call graph for this function:

void grafalgo::BstSet::resize

(

int

size

)

[virtual]

Resize a BstSet object, discarding old value.

Parameters:

size	is the size of the resized object.

Implements grafalgo::Adt.

Reimplemented in grafalgo::BalBstSet, and grafalgo::DkBstSet.

Definition at line 58 of file BstSet.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

void grafalgo::BstSet::rotate

(

index

x

)

[protected, virtual]

Perform a rotation in a search tree.

Parameters:

x	is a node in some search tree; this method does a rotation at the parent of x, moving x up into it's parent's position

Reimplemented in grafalgo::DkBstSet.

Definition at line 92 of file BstSet.cpp.

Here is the caller graph for this function:

void grafalgo::BstSet::setkey	(	index	i,
		keytyp	k
	)		[inline]

Set the key of an item.

Parameters:

i	is a singleton item
k	is the new key value to be assigned to i

Definition at line 87 of file BstSet.h.

Here is the caller graph for this function:

index grafalgo::BstSet::sibling	(	index	x,
		index	px
	)		[inline, protected]

Get the sibling of a tree node.

Parameters:

x	is an item in a set (node in a BST)
px	is the parent of x in its tree

Returns:

the "other child" of px, or 0 if there is none

Definition at line 97 of file BstSet.h.

Here is the caller graph for this function:

BstSet::BstPair grafalgo::BstSet::split	(	index	i,
		bst	s
	)

Divide a bst at a node.

Parameters:

i	is a node in some bst
s	is the root of the bst containing i

Returns:

the pair of bsts [t1,t2] that results from splitting s into three parts; t1 (containing ityems with keys smaller than that of i), i itself, and t2 (contining items with keys larger than that of i)

Reimplemented in grafalgo::BalBstSet, grafalgo::DkBstSet, and grafalgo::SaBstSet.

Definition at line 297 of file BstSet.cpp.

Here is the call graph for this function:

index grafalgo::BstSet::suc

(

index

i

)

const

Return the successor of a node in a bst.

This operation does not restructure the underlying search tree.

Parameters:

i	is a node in some bst

Returns:

the node with largest key1 value in the bst

Definition at line 162 of file BstSet.cpp.

void grafalgo::BstSet::swap	(	index	i,
		index	j
	)		[protected, virtual]

Swap the positions of two nodes in the same tree.

Parameters:

i	is a node in a search tree
j	is another node in the same tree, which is not the parent of i; this is a helper method for the remove method; it exchanges the positions of the nodes in the tree

Reimplemented in grafalgo::BalBstSet.

Definition at line 216 of file BstSet.cpp.

Here is the caller graph for this function:

string & grafalgo::BstSet::toString

(

string &

s

)

const [virtual]

Create a string representation of this object.

Omits singleton trees.

Parameters:

s	is a string in which the result will be returned

Returns:

a reference to s

Implements grafalgo::Adt.

Definition at line 346 of file BstSet.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/BstSet.h
• /Users/jst/src/grafalgo/cpp/dataStructures/searchTrees/BstSet.cpp