grafalgo::SaTreeMap Class Reference

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

#include <SaTreeMap.h>

Inheritance diagram for grafalgo::SaTreeMap:

Collaboration diagram for grafalgo::SaTreeMap:

List of all members.

Public Member Functions
	SaTreeMap (int)
	Constructor for SaTreeMap class.
	~SaTreeMap ()
	Destructor for SaTreeMap class.
void	clear ()
	Reinitialize data structure, creating single node trees.
void	resize (int)
	Resize a SaTreeMap object, discarding old value.
void	expand (int)
	Expand the space available for this ojbect.
void	copyFrom (const SaTreeMap &)
	Copy another object to this one.
int	get (keytyp)
	Get the value for a specified key.
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 string listing the key,value pairs in the map.
Private Member Functions
void	makeSpace (int)
	Allocate and initialize space for SaTreeMap.
void	freeSpace ()
	Free dynamic storage used by SaTreeMap.
Private Attributes
bst	root
	root of search tree
SaBstSet *	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 SaTreeMap.h.

---

Constructor & Destructor Documentation

grafalgo::SaTreeMap::SaTreeMap

(

int

size

)

Constructor for SaTreeMap class.

Parameters:

size	defines the index range for the constructed object.

Definition at line 16 of file SaTreeMap.cpp.

Here is the call graph for this function:

grafalgo::SaTreeMap::~SaTreeMap

(

)

Destructor for SaTreeMap class.

Definition at line 21 of file SaTreeMap.cpp.

Here is the call graph for this function:

---

Member Function Documentation

void grafalgo::SaTreeMap::clear

(

)

[virtual]

Reinitialize data structure, creating single node trees.

Implements grafalgo::Adt.

Definition at line 47 of file SaTreeMap.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

void grafalgo::SaTreeMap::copyFrom

(

const SaTreeMap &

source

)

Copy another object to this one.

Parameters:

source

is object to be copied to this one

Definition at line 74 of file SaTreeMap.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

void grafalgo::SaTreeMap::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 66 of file SaTreeMap.cpp.

Here is the call graph for this function:

void grafalgo::SaTreeMap::freeSpace

(

)

[private]

Free dynamic storage used by SaTreeMap.

Definition at line 42 of file SaTreeMap.cpp.

Here is the caller graph for this function:

int grafalgo::SaTreeMap::get

(

keytyp

key

)

Get the value for a specified key.

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 89 of file SaTreeMap.cpp.

Here is the call graph for this function:

void grafalgo::SaTreeMap::makeSpace

(

int

size

)

[private]

Allocate and initialize space for SaTreeMap.

Parameters:

size	is number of index values to provide space for

Definition at line 26 of file SaTreeMap.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

bool grafalgo::SaTreeMap::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 103 of file SaTreeMap.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

void grafalgo::SaTreeMap::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 120 of file SaTreeMap.cpp.

Here is the call graph for this function:

void grafalgo::SaTreeMap::resize

(

int

size

)

[virtual]

Resize a SaTreeMap object, discarding old value.

Parameters:

size	is the size of the resized object.

Implements grafalgo::Adt.

Definition at line 54 of file SaTreeMap.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

string & grafalgo::SaTreeMap::toString

(

string &

s

)

const [virtual]

Construct string listing the key,value pairs in the map.

Parameters:

s	is a reference to a string in which result is to be returned

Returns:

a reference to s

Implements grafalgo::Adt.

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