Data structure that assigns small integer identifiers to large keys. More...

#include <IdMap.h>

Inheritance diagram for grafalgo::IdMap:

Collaboration diagram for grafalgo::IdMap:

Public Member Functions
	IdMap (int)
	Constructor for IdMap, allocates space and initializes table.
	~IdMap ()
	Destructor for IdMap.
void	clear ()
	Remove all elements from map.
void	resize (int)
	Resize a IdMap object.
void	expand (int)
	Expand the space available for this IdMap.
void	copyFrom (const IdMap &)
	Copy into this from source.
int	firstId () const
	Get the first assigned identifier, in some arbitrary order.
int	nextId (int) const
	Get the next assigned identifier, in some arbitrary order.
int	size () const
	The size of the mapping.
int	getId (uint64_t) const
	Get the id for a given key.
uint64_t	getKey (int) const
	Get the key that was mapped to the given identifier.
int	addPair (uint64_t)
	Add a new key->id pair.
int	addPair (uint64_t, int)
	Add a new key->id pair.
void	dropPair (uint64_t)
	Remove a pair from the mapping.
bool	validKey (uint64_t) const
	Determine if a given key has been mapped to an identfier.
bool	validId (int) const
	Determine if a given identifier has been assigned to a key.
string &	toString (string &) const
	Create a string representation of the IdMap.
Private Member Functions
void	makeSpace (int)
	Allocate and initialize space for list.
void	freeSpace ()
	Free dynamic storage used by list.
Private Attributes
HashTbl *	ht
SetPair *	ids
Static Private Attributes
static const int	MAXID = (1 << 20)-1
	largest possible identifier

Detailed Description

Data structure that assigns small integer identifiers to large keys.

This is useful in contexts where the "natural identifiers" in an application can vary over a large range, but the number of distinct identifiers that are in use at one time is relatively small. This data structure can be used to map the "natural identfiers" into integers in a restricted range 1..max, where max is specified when the data structure is initialized.

Definition at line 27 of file IdMap.h.

Constructor & Destructor Documentation

grafalgo::IdMap::IdMap ( int n1 )

Constructor for IdMap, allocates space and initializes table.

N1 is the limit on the range of values; it must be less than 2^20.

Definition at line 16 of file IdMap.cpp.

Here is the call graph for this function:

grafalgo::IdMap::~IdMap ( )

Destructor for IdMap.

Definition at line 19 of file IdMap.cpp.

Here is the call graph for this function:

Member Function Documentation

int grafalgo::IdMap::addPair ( uint64_t key )

Add a new key->id pair.

Parameters:

key	is the key for which an id is required

Returns:: the new id or 0 if the key is already mapped or the operation fails

Definition at line 82 of file IdMap.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

int grafalgo::IdMap::addPair	(	uint64_t	key,
		int	id
	)

Add a new key->id pair.

Parameters:

key	is the key for which an id is required
id	is the requested id that the key is to be mapped to

Returns:: the new id or 0 if the key is already mapped or the id is already in use or the operation fails

Definition at line 95 of file IdMap.cpp.

Here is the call graph for this function:

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

Remove all elements from map.

Implements grafalgo::Adt.

Definition at line 64 of file IdMap.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

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

Copy into this from source.

Definition at line 69 of file IdMap.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

void grafalgo::IdMap::dropPair ( uint64_t key )

Remove a pair from the mapping.

This operation removes a (key,id) pair from the mapping.

Parameters:

key	is the key whose id is to be released

Definition at line 105 of file IdMap.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

void grafalgo::IdMap::expand ( int size ) [virtual]

Expand the space available for this IdMap.

Rebuilds old value in new space.

Parameters:

size	is the size of the resized object.

Implements grafalgo::Adt.

Definition at line 57 of file IdMap.cpp.

Here is the call graph for this function:

int grafalgo::IdMap::firstId ( ) const [inline]

Get the first assigned identifier, in some arbitrary order.

Returns:: number of the first identfier

Definition at line 68 of file IdMap.h.

Here is the call graph for this function:

Here is the caller graph for this function:

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

Free dynamic storage used by list.

Definition at line 39 of file IdMap.cpp.

Here is the caller graph for this function:

int grafalgo::IdMap::getId ( uint64_t key ) const [inline]

Get the id for a given key.

Parameters:

key	is the key for which the id is required

Returns:: the corresponding id or 0 if the key is not mapped or the operation fails

Definition at line 98 of file IdMap.h.

Here is the call graph for this function:

uint64_t grafalgo::IdMap::getKey ( int id ) const [inline]

Get the key that was mapped to the given identifier.

Parameters:

id	is the identifier whose key is to be returned

Returns:: the key that maps to id, or 0 if there is none

Definition at line 104 of file IdMap.h.

Here is the call graph for this function:

Here is the caller graph for this function:

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

Allocate and initialize space for list.

Parameters:

size	is number of index values to provide space for

Definition at line 24 of file IdMap.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

int grafalgo::IdMap::nextId ( int id ) const [inline]

Get the next assigned identifier, in some arbitrary order.

Parameters:

id	is an identifer in the set

Returns:: number of the next identfier

Definition at line 74 of file IdMap.h.

Here is the call graph for this function:

Here is the caller graph for this function:

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

Resize a IdMap object.

The old value is discarded.

Parameters:

size	is the size of the resized object.

Implements grafalgo::Adt.

Definition at line 45 of file IdMap.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

int grafalgo::IdMap::size ( ) const [inline]

The size of the mapping.

Returns:: the number of mapped identifiers.

Definition at line 91 of file IdMap.h.

Here is the call graph for this function:

Here is the caller graph for this function:

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

Create a string representation of the IdMap.

Parameters:

s	is the string in which the result is returned.

Implements grafalgo::Adt.

Definition at line 113 of file IdMap.cpp.

Here is the call graph for this function:

bool grafalgo::IdMap::validId ( int id ) const [inline]

Determine if a given identifier has been assigned to a key.

Parameters:

id	is the identifier to be checked

Returns:: true if the key has been mapped, else false

Definition at line 86 of file IdMap.h.

Here is the call graph for this function:

Here is the caller graph for this function:

bool grafalgo::IdMap::validKey ( uint64_t key ) const [inline]

Determine if a given key has been mapped to an identfier.

Parameters:

key	is the key to be checked

Returns:: true if the key has been mapped, else false

Definition at line 80 of file IdMap.h.

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/IdMap.h
/Users/jst/src/grafalgo/cpp/dataStructures/hash/IdMap.cpp

Public Member Functions

Private Member Functions

Private Attributes

Static Private Attributes

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation