This class represents a collection of binary search trees in which nodes have two different keys. More...

#include <DkBstSet.h>

Inheritance diagram for grafalgo::DkBstSet:

Collaboration diagram for grafalgo::DkBstSet:

Public Member Functions
	DkBstSet (int)
	Constructor for DkBstSet class.
	~DkBstSet ()
	Destructor for DkBstSet class.
void	clear ()
	Reinitialize data structure, creating single node trees.
void	resize (int)
	Resize a DkBstSet object, discarding old value.
void	expand (int)
	Expand the space available for this ojbect.
void	copyFrom (const DkBstSet &)
	Copy another object to this one.
keytyp	key1 (index)
	Get the first key of a node.
keytyp	key2 (index)
	Get the value of the second key of a node.
index	first (bst) const
	Return the "first" node in a bst.
index	next (index) const
index	access (keytyp, bst)
	Get the node in a bst with a specified key value.
keytyp	min2 (bst)
	Get the item in a given bst that has the smallest key2 value.
void	setkey (index, keytyp, keytyp)
	Set key values of a node.
void	change2 (keytyp, bst)
	Change the key2 values of all items in a bst.
bst	insert (index, bst)
	Insert a node into a bst.
bst	remove (index, bst)
	Remove a node from a bst.
bst	join (bst, index, bst)
	Join two bsts at a node.
BstPair	split (index, bst)
	Divide a bst at a node.
Static Public Attributes
static const int	MAX2 = Util::BIGINT32-1
	max allowed key2 value
Private Member Functions
virtual void	rotate (index)
	Perform a rotation.
virtual string &	node2string (index, string &) const
	Construct a string representation of a single node.
void	makeSpace (int)
	Allocate and initialize space for DkBstSet.
void	freeSpace ()
	Free dynamic storage used by DkBstSet.
Private Attributes
keytyp *	dmin
keytyp *	dkey

Detailed Description

This class represents a collection of binary search trees in which nodes have two different keys.

The first key is used to order the BST nodes in the usual way.

Definition at line 20 of file DkBstSet.h.

Constructor & Destructor Documentation

grafalgo::DkBstSet::DkBstSet ( int size )

Constructor for DkBstSet class.

Parameters:

size	defines the index range for the constructed object.

Definition at line 22 of file DkBstSet.cpp.

Here is the call graph for this function:

grafalgo::DkBstSet::~DkBstSet ( )

Destructor for DkBstSet class.

Definition at line 27 of file DkBstSet.cpp.

Here is the call graph for this function:

Member Function Documentation

index grafalgo::DkBstSet::access	(	keytyp	k,
		bst	t
	)

Get the node in a bst with a specified key value.

Parameters:

k	is a key value
t	is the root of some bst

Returns:: the node with the largest key1 value that is <=k; if there is no such node, return the node with the smallest key1

Definition at line 132 of file DkBstSet.cpp.

Here is the call graph for this function:

void grafalgo::DkBstSet::change2	(	keytyp	diff,
		bst	s
	)		`[inline]`

Change the key2 values of all items in a bst.

Parameters:

diff	is a key value
s	is a canonical element of some bst (root of the BST); the opertion adds diff to all the key2 values in s

Definition at line 90 of file DkBstSet.h.

void grafalgo::DkBstSet::clear ( ) [virtual]

Reinitialize data structure, creating single node trees.

Reimplemented from grafalgo::BstSet.

Definition at line 51 of file DkBstSet.cpp.

Here is the caller graph for this function:

void grafalgo::DkBstSet::copyFrom ( const DkBstSet & source )

Copy another object to this one.

Parameters:

source is object to be copied to this one

Definition at line 80 of file DkBstSet.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

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

Reimplemented from grafalgo::BstSet.

Definition at line 72 of file DkBstSet.cpp.

Here is the call graph for this function:

index grafalgo::DkBstSet::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 from grafalgo::BstSet.

void grafalgo::DkBstSet::freeSpace ( ) [private]

Free dynamic storage used by DkBstSet.

Reimplemented from grafalgo::BstSet.

Definition at line 46 of file DkBstSet.cpp.

Here is the caller graph for this function:

index grafalgo::DkBstSet::insert	(	index	i,
		bst	t
	)

Insert a node into a bst.

Parameters:

i	is a singleton node
t	is the root of some bst

Returns:: the new bst that results from adding i to t

Definition at line 155 of file DkBstSet.cpp.

Here is the call graph for this function:

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

Join two bsts at a node.

Parameters:

t1	is the root of some bst
t2	is the root of some bst
i	is a singleton node with key larger than that of any node in t1, and smaller than that of any node in t2

Returns:: the new bst formed by combining t1, i and t2

Reimplemented from grafalgo::BstSet.

Definition at line 236 of file DkBstSet.cpp.

keytyp grafalgo::DkBstSet::key1 ( index i ) [inline]

Get the first key of a node.

Parameters:

i	is a node in a BST

Returns:: the value of the first key of i

Definition at line 71 of file DkBstSet.h.

keytyp grafalgo::DkBstSet::key2 ( index i )

Get the value of the second key of a node.

Parameters:

i	is a node in a search tree

Returns:: the value of the second key at i

Definition at line 95 of file DkBstSet.cpp.

Here is the call graph for this function:

void grafalgo::DkBstSet::makeSpace ( int size ) [private]

Allocate and initialize space for DkBstSet.

Parameters:

size	is number of index values to provide space for

Reimplemented from grafalgo::BstSet.

Definition at line 32 of file DkBstSet.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

keytyp grafalgo::DkBstSet::min2 ( bst s ) [inline]

Get the item in a given bst that has the smallest key2 value.

Parameters:

s	is a canonical element of some bst (root of the BST)

Returns:: the smallest key2 value for any element in the bst

Definition at line 80 of file DkBstSet.h.

string & grafalgo::DkBstSet::node2string	(	index	i,
		string &	s
	)		const `[private, virtual]`

Construct a string representation of a single node.

Parameters:

i	is a node in some bst
t	is a string in which the result is returned

Returns:: a reference to t

Reimplemented from grafalgo::BstSet.

Definition at line 267 of file DkBstSet.cpp.

index grafalgo::DkBstSet::remove	(	index	i,
		bst	t
	)

Remove a node from a bst.

Parameters:

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

Returns:: the root of the new bst that results from removing i from t

Definition at line 190 of file DkBstSet.cpp.

Here is the call graph for this function:

void grafalgo::DkBstSet::resize ( int size ) [virtual]

Resize a DkBstSet object, discarding old value.

Parameters:

size	is the size of the resized object.

Reimplemented from grafalgo::BstSet.

Definition at line 59 of file DkBstSet.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

void grafalgo::DkBstSet::rotate ( index x ) [private, virtual]

Perform a rotation.

Parameters:

x	is a node in a bst (node in a search tree); the operation does a rotation at the parent of x, moving x up into its parent's place

Reimplemented from grafalgo::BstSet.

Definition at line 105 of file DkBstSet.cpp.

Here is the caller graph for this function:

void grafalgo::DkBstSet::setkey	(	index	i,
		keytyp	k1,
		keytyp	k2
	)		`[inline]`

Set key values of a node.

Parameters:

i	is an isolated node (that is, it's a single node BST)

Definition at line 61 of file DkBstSet.h.

Here is the caller graph for this function:

BstSet::BstPair grafalgo::DkBstSet::split	(	index	i,
		bst	t
	)

Divide a bst at a node.

Parameters:

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

Returns:: the pair of bst [t1,t2] obtained by dividing s into three parts, t1,i and t2, where the keys of the nodes in t1 are smaller than the key of i and keys of nodes in t2 are larger than the key of i

Reimplemented from grafalgo::SaBstSet.

Definition at line 254 of file DkBstSet.cpp.

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

/Users/jst/src/grafalgo/cpp/include/DkBstSet.h
/Users/jst/src/grafalgo/cpp/dataStructures/searchTrees/DkBstSet.cpp

Public Member Functions

Static Public Attributes

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation