Maintains set of (key, value) pairs where key is a 64 bit value and value is a positive 32 bit integer. More...

#include <TreeMap.h>

Inheritance diagram for grafalgo::TreeMap:

Collaboration diagram for grafalgo::TreeMap:

Public Member Functions
	TreeMap (int)
	Constructor for TreeMap class.
	~TreeMap ()
	Destructor for TreeMap class.
void	clear ()
	Reinitialize data structure, creating single node trees.
void	resize (int)
	Resize a TreeMap object, discarding old value.
void	expand (int)
	Expand the space available for this ojbect.
void	copyFrom (const TreeMap &)
	Copy another object to this one.
int	get (keytyp)
	Get an index based on its position in the list.
bool	put (keytyp, uint32_t)
	Put a (key,value) pair into the map.
void	remove (keytyp)
	Remove a (key, value) pair from the table.
string &	toString (string &) const
	Construct a string representation of this object.
Private Member Functions
void	makeSpace (int)
	Allocate and initialize space for TreeMap.
void	freeSpace ()
	Free dynamic storage used by TreeMap.
Private Attributes
bst	root
	root of search tree
BalBstSet *	st
	search tree storing keys
uint32_t *	values
	vector of values
SetPair *	nodes
	in-use and free nodes
Static Private Attributes
static const int	UNDEF_VAL = INT_MIN
	undefined value

Detailed Description

Maintains set of (key, value) pairs where key is a 64 bit value and value is a positive 32 bit integer.

All keys must be distinct.

Main methods get - returns value for given key put - adds a (key,value) pair remove - removes the pair for a given key

The implementation uses a balanced binary search tree.

Definition at line 28 of file TreeMap.h.

Constructor & Destructor Documentation

grafalgo::TreeMap::TreeMap ( int size )

Constructor for TreeMap class.

Parameters:

size	defines the index range for the constructed object.

Definition at line 16 of file TreeMap.cpp.

Here is the call graph for this function:

grafalgo::TreeMap::~TreeMap ( )

Destructor for TreeMap class.

Definition at line 21 of file TreeMap.cpp.

Here is the call graph for this function:

Member Function Documentation

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

Reinitialize data structure, creating single node trees.

Implements grafalgo::Adt.

Definition at line 48 of file TreeMap.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

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

Copy another object to this one.

Parameters:

source is object to be copied to this one

Definition at line 75 of file TreeMap.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

void grafalgo::TreeMap::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 67 of file TreeMap.cpp.

Here is the call graph for this function:

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

Free dynamic storage used by TreeMap.

Definition at line 43 of file TreeMap.cpp.

Here is the caller graph for this function:

int grafalgo::TreeMap::get ( keytyp key )

Get an index based on its position in the list.

Get the value for a specified key.

Parameters:

i	is position of index to be returned; negative values are interpreted relative to the end of the list.

Returns:: the index at the specfied position

Parameters:

key	is the key to be looked up in the table

Returns:: the value stored for the given key, or UNDEF_VAL if there is none.

Definition at line 66 of file Dlist.cpp.

Here is the call graph for this function:

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

Allocate and initialize space for TreeMap.

Parameters:

size	is number of index values to provide space for

Definition at line 26 of file TreeMap.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

bool grafalgo::TreeMap::put	(	keytyp	key,
		uint32_t	val
	)

Put a (key,value) pair into the map.

If there is already a pair defined for the given key value, just update the value

Parameters:

key	is the key part of the pair
val	is the value part of the pair

Returns:: true on success, false on failure.

Definition at line 104 of file TreeMap.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

void grafalgo::TreeMap::remove ( keytyp key )

Remove a (key, value) pair from the table.

Parameters:

key	is the key of the pair to be removed

Definition at line 121 of file TreeMap.cpp.

Here is the call graph for this function:

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

Resize a TreeMap object, discarding old value.

Parameters:

size	is the size of the resized object.

Implements grafalgo::Adt.

Definition at line 55 of file TreeMap.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

string & grafalgo::TreeMap::toString ( string & s ) const [virtual]

Construct a string representation of this object.

Parameters:

s	is a string in which the result is returned

Returns:: a reference to s

Implements grafalgo::Adt.

Definition at line 186 of file DiffHeap.cpp.

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

/Users/jst/src/grafalgo/cpp/include/TreeMap.h
/Users/jst/src/grafalgo/cpp/dataStructures/basic/Dlist.cpp
/Users/jst/src/grafalgo/cpp/dataStructures/heaps/DiffHeap.cpp
/Users/jst/src/grafalgo/cpp/dataStructures/searchTrees/TreeMap.cpp

Public Member Functions

Private Member Functions

Private Attributes

Static Private Attributes

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation