TC::HashTable< KEY_TYPE, MAP_TYPE, HASH_FUNC, KEY_VALUE_COMPARE_FUNC > Class Template Reference
[Base Classes and Functions]

Generic hash table. More...

#include <TCHashTable.h>

Collaboration diagram for TC::HashTable< KEY_TYPE, MAP_TYPE, HASH_FUNC, KEY_VALUE_COMPARE_FUNC >:

Collaboration graph
[legend]

List of all members.

Classes

struct  _Element
 Internal hash table structure which stores the key value and the mapped value of one entry. More...

Public Member Functions

 HashTable (uint32 size, const MAP_TYPE &notFound)
 Construct the hash table with specified hash size.
virtual ~HashTable ()
 Destruct the hash table.
uint32 GetHashSize () const
void SetHashSize (uint32 size)
 Set the size of the hash table.
void Clear ()
 Clear the hash table All added elements get removed.
const MAP_TYPE & GetNotFoundValue () const
 Get the value which is returned when an key is not found.
void SetNotFoundValue (const MAP_TYPE &notFound)
 Set the value which is returned when an key is not found.
void AddKey (const KEY_TYPE &key_value, const MAP_TYPE &map_value)
 Add a new key to the hash table If the key already exits it is replaced.
void RemoveKey (const KEY_TYPE &key_value)
 Remove an existing key from the hash table.
const MAP_TYPE & GetMappedValue (const KEY_TYPE &key_value) const
 Get the mapped value of an element It searches in the table for the key_value and returns the mapped value for this key If the key value is not found it returns the not found value.
const MAP_TYPE & operator[] (const KEY_TYPE &key_value) const
 Get the value because of the key.
void GetAllKeys (std::vector< KEY_TYPE > &keys)
 Get all keys in the hash table.
void GetAllKeysAndValues (std::vector< KEY_TYPE > &keys, std::vector< MAP_TYPE > &values)
 Get all keys in the hash table.
void GetStatistics (uint32 &numEmptyLists, uint32 &maxListLength, double &avgListLength) const
 Return statistic information about the hash table.

Private Member Functions

void GetElementPosition (const KEY_TYPE &key_value, uint32 &p1, sint32 &p2) const
 Get the element which your are searching for This looks a little bit stupied to search for an element by another element To get this working the compare operator needs to be defined in that why tha you only compare the value which you are searching for.
uint32 GetTableEntryPosition (const KEY_TYPE &key_value) const
 Methode calculates out of the identification of the element the hash table position.

Private Attributes

uint32 m_size
 The size of the hash table.
MAP_TYPE m_not_found
 holding the value when a element is not found
std::vector< std::vector
< _Element > > 		m_data
 2-Dimensional array storing the elements

Detailed Description

template<class KEY_TYPE, class MAP_TYPE = sint32, class HASH_FUNC = Hash< KEY_TYPE>, class KEY_VALUE_COMPARE_FUNC = std::equal_to<KEY_TYPE>>
class TC::HashTable< KEY_TYPE, MAP_TYPE, HASH_FUNC, KEY_VALUE_COMPARE_FUNC >

Generic hash table.

Class implements a generic hash table by using a 2-Dimensional array and adding the elements by calculating the first array position because of the modulo of their hash value

The key(KEY_TYPE) which is added to the hash table has to implement the compare equal operator and the Hash template for this type

Elements can be added/removed in the hash table with AddKey or RemoveKey To get then the mapped value for the key use the method GetMappedValue

Author:
Thomas Goessler

Definition at line 145 of file TCHashTable.h.

Constructor & Destructor Documentation

template<class KEY_TYPE , class MAP_TYPE = sint32, class HASH_FUNC = Hash< KEY_TYPE>, class KEY_VALUE_COMPARE_FUNC = std::equal_to<KEY_TYPE>>
TC::HashTable< KEY_TYPE, MAP_TYPE, HASH_FUNC, KEY_VALUE_COMPARE_FUNC >::HashTable ( uint32  size,
const MAP_TYPE &  notFound 
) [inline]

Construct the hash table with specified hash size.

Parameters:
size The size of the hash table int the first direction
notFound The value which should be returned when an searched element is not found in the hash table

Definition at line 165 of file TCHashTable.h.

References TC::HashTable< KEY_TYPE, MAP_TYPE, HASH_FUNC, KEY_VALUE_COMPARE_FUNC >::Clear().

Here is the call graph for this function:

template<class KEY_TYPE , class MAP_TYPE = sint32, class HASH_FUNC = Hash< KEY_TYPE>, class KEY_VALUE_COMPARE_FUNC = std::equal_to<KEY_TYPE>>
virtual TC::HashTable< KEY_TYPE, MAP_TYPE, HASH_FUNC, KEY_VALUE_COMPARE_FUNC >::~HashTable (  )  [inline, virtual]

Destruct the hash table.

Definition at line 173 of file TCHashTable.h.

Member Function Documentation

template<class KEY_TYPE , class MAP_TYPE = sint32, class HASH_FUNC = Hash< KEY_TYPE>, class KEY_VALUE_COMPARE_FUNC = std::equal_to<KEY_TYPE>>
uint32 TC::HashTable< KEY_TYPE, MAP_TYPE, HASH_FUNC, KEY_VALUE_COMPARE_FUNC >::GetHashSize (  )  const [inline]

Returns:
The size of the hash table in the first direction

Definition at line 176 of file TCHashTable.h.

References TC::HashTable< KEY_TYPE, MAP_TYPE, HASH_FUNC, KEY_VALUE_COMPARE_FUNC >::m_size.

template<class KEY_TYPE , class MAP_TYPE = sint32, class HASH_FUNC = Hash< KEY_TYPE>, class KEY_VALUE_COMPARE_FUNC = std::equal_to<KEY_TYPE>>
void TC::HashTable< KEY_TYPE, MAP_TYPE, HASH_FUNC, KEY_VALUE_COMPARE_FUNC >::SetHashSize ( uint32  size  )  [inline]

Set the size of the hash table.

Parameters:
size The size of the hash table int the first direction

Definition at line 182 of file TCHashTable.h.

References TC::HashTable< KEY_TYPE, MAP_TYPE, HASH_FUNC, KEY_VALUE_COMPARE_FUNC >::Clear(), and TC::HashTable< KEY_TYPE, MAP_TYPE, HASH_FUNC, KEY_VALUE_COMPARE_FUNC >::m_size.

Here is the call graph for this function:

template<class KEY_TYPE , class MAP_TYPE = sint32, class HASH_FUNC = Hash< KEY_TYPE>, class KEY_VALUE_COMPARE_FUNC = std::equal_to<KEY_TYPE>>
void TC::HashTable< KEY_TYPE, MAP_TYPE, HASH_FUNC, KEY_VALUE_COMPARE_FUNC >::Clear (  )  [inline]

Clear the hash table All added elements get removed.

Definition at line 192 of file TCHashTable.h.

References TC::HashTable< KEY_TYPE, MAP_TYPE, HASH_FUNC, KEY_VALUE_COMPARE_FUNC >::m_data, and TC::HashTable< KEY_TYPE, MAP_TYPE, HASH_FUNC, KEY_VALUE_COMPARE_FUNC >::m_size.

Referenced by TC::HashTable< KEY_TYPE, MAP_TYPE, HASH_FUNC, KEY_VALUE_COMPARE_FUNC >::HashTable(), and TC::HashTable< KEY_TYPE, MAP_TYPE, HASH_FUNC, KEY_VALUE_COMPARE_FUNC >::SetHashSize().

Here is the caller graph for this function:

template<class KEY_TYPE , class MAP_TYPE = sint32, class HASH_FUNC = Hash< KEY_TYPE>, class KEY_VALUE_COMPARE_FUNC = std::equal_to<KEY_TYPE>>
const MAP_TYPE& TC::HashTable< KEY_TYPE, MAP_TYPE, HASH_FUNC, KEY_VALUE_COMPARE_FUNC >::GetNotFoundValue (  )  const [inline]

Get the value which is returned when an key is not found.

Returns:
The not found value

Definition at line 206 of file TCHashTable.h.

References TC::HashTable< KEY_TYPE, MAP_TYPE, HASH_FUNC, KEY_VALUE_COMPARE_FUNC >::m_not_found.

template<class KEY_TYPE , class MAP_TYPE = sint32, class HASH_FUNC = Hash< KEY_TYPE>, class KEY_VALUE_COMPARE_FUNC = std::equal_to<KEY_TYPE>>
void TC::HashTable< KEY_TYPE, MAP_TYPE, HASH_FUNC, KEY_VALUE_COMPARE_FUNC >::SetNotFoundValue ( const MAP_TYPE &  notFound  )  [inline]

Set the value which is returned when an key is not found.

Parameters:
notFound The new not found value

Definition at line 212 of file TCHashTable.h.

References TC::HashTable< KEY_TYPE, MAP_TYPE, HASH_FUNC, KEY_VALUE_COMPARE_FUNC >::m_not_found.

template<class KEY_TYPE , class MAP_TYPE = sint32, class HASH_FUNC = Hash< KEY_TYPE>, class KEY_VALUE_COMPARE_FUNC = std::equal_to<KEY_TYPE>>
void TC::HashTable< KEY_TYPE, MAP_TYPE, HASH_FUNC, KEY_VALUE_COMPARE_FUNC >::AddKey ( const KEY_TYPE &  key_value,
const MAP_TYPE &  map_value 
) [inline]

Add a new key to the hash table If the key already exits it is replaced.

Parameters:
key_value The key value to add
map_value The mapped value for the key value

Definition at line 220 of file TCHashTable.h.

References TC::HashTable< KEY_TYPE, MAP_TYPE, HASH_FUNC, KEY_VALUE_COMPARE_FUNC >::GetElementPosition(), TC::HashTable< KEY_TYPE, MAP_TYPE, HASH_FUNC, KEY_VALUE_COMPARE_FUNC >::_Element::key_value, TC::HashTable< KEY_TYPE, MAP_TYPE, HASH_FUNC, KEY_VALUE_COMPARE_FUNC >::m_data, and TC::HashTable< KEY_TYPE, MAP_TYPE, HASH_FUNC, KEY_VALUE_COMPARE_FUNC >::_Element::map_value.

Here is the call graph for this function:

template<class KEY_TYPE , class MAP_TYPE = sint32, class HASH_FUNC = Hash< KEY_TYPE>, class KEY_VALUE_COMPARE_FUNC = std::equal_to<KEY_TYPE>>
void TC::HashTable< KEY_TYPE, MAP_TYPE, HASH_FUNC, KEY_VALUE_COMPARE_FUNC >::RemoveKey ( const KEY_TYPE &  key_value  )  [inline]

Remove an existing key from the hash table.

Parameters:
key_value The key value of the element to remove
Bug fix: use vector's erase() method

Definition at line 246 of file TCHashTable.h.

References TC::HashTable< KEY_TYPE, MAP_TYPE, HASH_FUNC, KEY_VALUE_COMPARE_FUNC >::GetElementPosition(), and TC::HashTable< KEY_TYPE, MAP_TYPE, HASH_FUNC, KEY_VALUE_COMPARE_FUNC >::m_data.

Here is the call graph for this function:

template<class KEY_TYPE , class MAP_TYPE = sint32, class HASH_FUNC = Hash< KEY_TYPE>, class KEY_VALUE_COMPARE_FUNC = std::equal_to<KEY_TYPE>>
const MAP_TYPE& TC::HashTable< KEY_TYPE, MAP_TYPE, HASH_FUNC, KEY_VALUE_COMPARE_FUNC >::GetMappedValue ( const KEY_TYPE &  key_value  )  const [inline]

Get the mapped value of an element It searches in the table for the key_value and returns the mapped value for this key If the key value is not found it returns the not found value.

Parameters:
key_value The key value for which to get the map value

Definition at line 266 of file TCHashTable.h.

References TC::HashTable< KEY_TYPE, MAP_TYPE, HASH_FUNC, KEY_VALUE_COMPARE_FUNC >::GetElementPosition(), TC::HashTable< KEY_TYPE, MAP_TYPE, HASH_FUNC, KEY_VALUE_COMPARE_FUNC >::m_data, and TC::HashTable< KEY_TYPE, MAP_TYPE, HASH_FUNC, KEY_VALUE_COMPARE_FUNC >::m_not_found.

Referenced by TC::HashTable< KEY_TYPE, MAP_TYPE, HASH_FUNC, KEY_VALUE_COMPARE_FUNC >::operator[]().

Here is the call graph for this function:

Here is the caller graph for this function:

template<class KEY_TYPE , class MAP_TYPE = sint32, class HASH_FUNC = Hash< KEY_TYPE>, class KEY_VALUE_COMPARE_FUNC = std::equal_to<KEY_TYPE>>
const MAP_TYPE& TC::HashTable< KEY_TYPE, MAP_TYPE, HASH_FUNC, KEY_VALUE_COMPARE_FUNC >::operator[] ( const KEY_TYPE &  key_value  )  const [inline]

Get the value because of the key.

Definition at line 283 of file TCHashTable.h.

References TC::HashTable< KEY_TYPE, MAP_TYPE, HASH_FUNC, KEY_VALUE_COMPARE_FUNC >::GetMappedValue().

Here is the call graph for this function:

template<class KEY_TYPE , class MAP_TYPE = sint32, class HASH_FUNC = Hash< KEY_TYPE>, class KEY_VALUE_COMPARE_FUNC = std::equal_to<KEY_TYPE>>
void TC::HashTable< KEY_TYPE, MAP_TYPE, HASH_FUNC, KEY_VALUE_COMPARE_FUNC >::GetAllKeys ( std::vector< KEY_TYPE > &  keys  )  [inline]

Get all keys in the hash table.

Definition at line 286 of file TCHashTable.h.

References TC::HashTable< KEY_TYPE, MAP_TYPE, HASH_FUNC, KEY_VALUE_COMPARE_FUNC >::m_data.

template<class KEY_TYPE , class MAP_TYPE = sint32, class HASH_FUNC = Hash< KEY_TYPE>, class KEY_VALUE_COMPARE_FUNC = std::equal_to<KEY_TYPE>>
void TC::HashTable< KEY_TYPE, MAP_TYPE, HASH_FUNC, KEY_VALUE_COMPARE_FUNC >::GetAllKeysAndValues ( std::vector< KEY_TYPE > &  keys,
std::vector< MAP_TYPE > &  values 
) [inline]

Get all keys in the hash table.

Definition at line 298 of file TCHashTable.h.

References TC::HashTable< KEY_TYPE, MAP_TYPE, HASH_FUNC, KEY_VALUE_COMPARE_FUNC >::m_data.

template<class KEY_TYPE , class MAP_TYPE = sint32, class HASH_FUNC = Hash< KEY_TYPE>, class KEY_VALUE_COMPARE_FUNC = std::equal_to<KEY_TYPE>>
void TC::HashTable< KEY_TYPE, MAP_TYPE, HASH_FUNC, KEY_VALUE_COMPARE_FUNC >::GetStatistics ( uint32 &  numEmptyLists,
uint32 &  maxListLength,
double &  avgListLength 
) const [inline]

Return statistic information about the hash table.

Parameters:
numEmptyLists [OUT] Number of empty lists in the hash table.
maxListLength [OUT] Length of the longest list in the hash table.
avgListLength [OUT] Average length of the lists in the hash table.

Definition at line 316 of file TCHashTable.h.

References TC::HashTable< KEY_TYPE, MAP_TYPE, HASH_FUNC, KEY_VALUE_COMPARE_FUNC >::m_data.

template<class KEY_TYPE , class MAP_TYPE = sint32, class HASH_FUNC = Hash< KEY_TYPE>, class KEY_VALUE_COMPARE_FUNC = std::equal_to<KEY_TYPE>>
void TC::HashTable< KEY_TYPE, MAP_TYPE, HASH_FUNC, KEY_VALUE_COMPARE_FUNC >::GetElementPosition ( const KEY_TYPE &  key_value,
uint32 &  p1,
sint32 &  p2 
) const [inline, private]

Get the element which your are searching for This looks a little bit stupied to search for an element by another element To get this working the compare operator needs to be defined in that why tha you only compare the value which you are searching for.

Definition at line 338 of file TCHashTable.h.

References TC::HashTable< KEY_TYPE, MAP_TYPE, HASH_FUNC, KEY_VALUE_COMPARE_FUNC >::GetTableEntryPosition(), and TC::HashTable< KEY_TYPE, MAP_TYPE, HASH_FUNC, KEY_VALUE_COMPARE_FUNC >::m_data.

Referenced by TC::HashTable< KEY_TYPE, MAP_TYPE, HASH_FUNC, KEY_VALUE_COMPARE_FUNC >::AddKey(), TC::HashTable< KEY_TYPE, MAP_TYPE, HASH_FUNC, KEY_VALUE_COMPARE_FUNC >::GetMappedValue(), and TC::HashTable< KEY_TYPE, MAP_TYPE, HASH_FUNC, KEY_VALUE_COMPARE_FUNC >::RemoveKey().

Here is the call graph for this function:

Here is the caller graph for this function:

template<class KEY_TYPE , class MAP_TYPE = sint32, class HASH_FUNC = Hash< KEY_TYPE>, class KEY_VALUE_COMPARE_FUNC = std::equal_to<KEY_TYPE>>
uint32 TC::HashTable< KEY_TYPE, MAP_TYPE, HASH_FUNC, KEY_VALUE_COMPARE_FUNC >::GetTableEntryPosition ( const KEY_TYPE &  key_value  )  const [inline, private]

Methode calculates out of the identification of the element the hash table position.

This is done by a simple modulo with the size of the hash table

Parameters:
key_value The element for which to get the hash table position
Returns:
The hash table position

Definition at line 361 of file TCHashTable.h.

References TC::HashTable< KEY_TYPE, MAP_TYPE, HASH_FUNC, KEY_VALUE_COMPARE_FUNC >::m_size.

Referenced by TC::HashTable< KEY_TYPE, MAP_TYPE, HASH_FUNC, KEY_VALUE_COMPARE_FUNC >::GetElementPosition().

Here is the caller graph for this function:

Member Data Documentation

template<class KEY_TYPE , class MAP_TYPE = sint32, class HASH_FUNC = Hash< KEY_TYPE>, class KEY_VALUE_COMPARE_FUNC = std::equal_to<KEY_TYPE>>
uint32 TC::HashTable< KEY_TYPE, MAP_TYPE, HASH_FUNC, KEY_VALUE_COMPARE_FUNC >::m_size [private]

The size of the hash table.

Definition at line 369 of file TCHashTable.h.

Referenced by TC::HashTable< KEY_TYPE, MAP_TYPE, HASH_FUNC, KEY_VALUE_COMPARE_FUNC >::Clear(), TC::HashTable< KEY_TYPE, MAP_TYPE, HASH_FUNC, KEY_VALUE_COMPARE_FUNC >::GetHashSize(), TC::HashTable< KEY_TYPE, MAP_TYPE, HASH_FUNC, KEY_VALUE_COMPARE_FUNC >::GetTableEntryPosition(), and TC::HashTable< KEY_TYPE, MAP_TYPE, HASH_FUNC, KEY_VALUE_COMPARE_FUNC >::SetHashSize().

template<class KEY_TYPE , class MAP_TYPE = sint32, class HASH_FUNC = Hash< KEY_TYPE>, class KEY_VALUE_COMPARE_FUNC = std::equal_to<KEY_TYPE>>
MAP_TYPE TC::HashTable< KEY_TYPE, MAP_TYPE, HASH_FUNC, KEY_VALUE_COMPARE_FUNC >::m_not_found [private]

holding the value when a element is not found

Definition at line 371 of file TCHashTable.h.

Referenced by TC::HashTable< KEY_TYPE, MAP_TYPE, HASH_FUNC, KEY_VALUE_COMPARE_FUNC >::GetMappedValue(), TC::HashTable< KEY_TYPE, MAP_TYPE, HASH_FUNC, KEY_VALUE_COMPARE_FUNC >::GetNotFoundValue(), and TC::HashTable< KEY_TYPE, MAP_TYPE, HASH_FUNC, KEY_VALUE_COMPARE_FUNC >::SetNotFoundValue().

template<class KEY_TYPE , class MAP_TYPE = sint32, class HASH_FUNC = Hash< KEY_TYPE>, class KEY_VALUE_COMPARE_FUNC = std::equal_to<KEY_TYPE>>
std::vector< std::vector< _Element > > TC::HashTable< KEY_TYPE, MAP_TYPE, HASH_FUNC, KEY_VALUE_COMPARE_FUNC >::m_data [private]

2-Dimensional array storing the elements

Definition at line 373 of file TCHashTable.h.

Referenced by TC::HashTable< KEY_TYPE, MAP_TYPE, HASH_FUNC, KEY_VALUE_COMPARE_FUNC >::AddKey(), TC::HashTable< KEY_TYPE, MAP_TYPE, HASH_FUNC, KEY_VALUE_COMPARE_FUNC >::Clear(), TC::HashTable< KEY_TYPE, MAP_TYPE, HASH_FUNC, KEY_VALUE_COMPARE_FUNC >::GetAllKeys(), TC::HashTable< KEY_TYPE, MAP_TYPE, HASH_FUNC, KEY_VALUE_COMPARE_FUNC >::GetAllKeysAndValues(), TC::HashTable< KEY_TYPE, MAP_TYPE, HASH_FUNC, KEY_VALUE_COMPARE_FUNC >::GetElementPosition(), TC::HashTable< KEY_TYPE, MAP_TYPE, HASH_FUNC, KEY_VALUE_COMPARE_FUNC >::GetMappedValue(), TC::HashTable< KEY_TYPE, MAP_TYPE, HASH_FUNC, KEY_VALUE_COMPARE_FUNC >::GetStatistics(), and TC::HashTable< KEY_TYPE, MAP_TYPE, HASH_FUNC, KEY_VALUE_COMPARE_FUNC >::RemoveKey().

The documentation for this class was generated from the following file:
Copyright (c) Thomas Goessler 2003 - 2008