Main Page   Namespace List   Class Hierarchy   Compound List   File List   Namespace Members   Compound Members   File Members  

Hashtable< KEY, VALUE, SIZ > Class Template Reference

Statically sized hash table with contigous vectors of values. More...

#include <hashtable.h>

Collaboration diagram for Hashtable< KEY, VALUE, SIZ >:

Collaboration graph
[legend]
List of all members.

Public Types

typedef std::vector< HashElement > vector_type
 The type of the table, so that it can be changed fairly easily later. More...

typedef HashElement value_type
 To make the Hashtable more similar to STL. More...

typedef HashIterator< typename
vector_type::iterator > 		iterator
 So that users can use an iterator of the private typedef. More...

typedef HashIterator< typename
vector_type::const_iterator > 		const_iterator
 So that users can use an iterator of the private typedef. More...


Public Methods

vector_type & GetAll (const KEY &key)
 Gets all contents of this hashtable in the KEY th table. More...

VALUE * Get (const KEY &key)
 Gets the first value with this key. More...

const VALUE * Get (const KEY &key) const
bool Get (const KEY &key, VALUE &k)
iterator find (const KEY &key)
 Gets an iterator with the first value with the key. More...

const_iterator find (const KEY &key) const
 Gets a const iterator with the first value with the key (for const versions of this class). More...

void Put (const KEY &key, const VALUE &value)
 adds this key/value pair without checking duplicates. More...

iterator insert (value_type valty)
 adds this key/value pair without checking duplicates. More...

void Delete (const KEY &key)
 Deletes the earlierst copy of value in the table with this key (does not delete the memory associated with the pointer). More...

iterator erase (const iterator &iter)
 Erases the item in the requested array. More...

unsigned int size (int vectorname) const
 Returns the size of the specified vector. More...

std::vector< VALUE * > GetAll () const
 Gets all contents of this hashtable. More...

VALUE * Get (const KEY &key) const
 Gets the first value with this key. More...

void Put (const KEY &key, VALUE *value)
 Adds this key/value pair without checking duplicates. More...

void Delete (const KEY &key)
 Deletes the earlierst copy of value in the table with this key (does not delete the memory associated with the pointer). More...


Static Public Methods

template<class Type> int hash (const Type key)
 The generic hash function given an int. More...

int hash (const std::string &key)
 the generic hash function given a string:notes that strings generally are 7 bits per char.FIXME: Should take into account that most stuffage is between 64 and 128 somehow. More...


Private Types

typedef std::pair< KEY, VALUE > HashElement
 A single element in the hash table. More...


Private Methods

void swapiter (iterator iter1, iterator iter2)
iterator SwapIn (vector_type *tbl, HashElement elem)

Static Private Methods

int hash (const int key)
 the hash function that creates a hashval from an int by modding it by SIZ . More...

int hash (const std::string &key)
 the generic hash function given a string:notes that strings generally are 7 bits per char.FIXME: Should take into account that most stuffage is between 64 and 128 somehow. More...


Private Attributes

vector_type table [SIZ]
 Where the actual elements are stored, a statically sized table. More...

std::vector< HashElement > table [SIZ]
 This is an array of vector s of the HashElement structure, which contains a KEY and a VALUE . More...

Key k
VALUE * val

Detailed Description

template<class KEY, class VALUE, int SIZ = 256>
class Hashtable< KEY, VALUE, SIZ >

Statically sized hash table with contigous vectors of values.

Member Typedef Documentation

template<class KEY, class VALUE, int SIZ = 256>
typedef HashIterator<typename vector_type::const_iterator> Hashtable< KEY, VALUE, SIZ >::const_iterator
 

So that users can use an iterator of the private typedef.

template<class KEY, class VALUE, int SIZ = 256>
typedef std::pair<KEY, VALUE> Hashtable< KEY, VALUE, SIZ >::HashElement [private]
 

A single element in the hash table.

template<class KEY, class VALUE, int SIZ = 256>
typedef HashIterator<typename vector_type::iterator> Hashtable< KEY, VALUE, SIZ >::iterator
 

So that users can use an iterator of the private typedef.

template<class KEY, class VALUE, int SIZ = 256>
typedef HashElement Hashtable< KEY, VALUE, SIZ >::value_type
 

To make the Hashtable more similar to STL.

template<class KEY, class VALUE, int SIZ = 256>
typedef std::vector<HashElement> Hashtable< KEY, VALUE, SIZ >::vector_type
 

The type of the table, so that it can be changed fairly easily later.

Member Function Documentation

template<class KEY, class VALUE, int SIZ = 256>
void Hashtable< KEY, VALUE, SIZ >::Delete (  const KEY &    key ) 
 

Deletes the earlierst copy of value in the table with this key (does not delete the memory associated with the pointer).

template<class KEY, class VALUE, int SIZ = 256>
void Hashtable< KEY, VALUE, SIZ >::Delete (  const KEY &    key )  [inline]
 

Deletes the earlierst copy of value in the table with this key (does not delete the memory associated with the pointer). 

00220     {
00221         int hashval = hash(key);
00222         typename vector_type::iterator iter = table[hashval].begin(), end = table[hashval].end();
00223 
00224         for(;iter!=end;iter++)
00225             if((*iter).key == key)
00226                 break;
00227         if(iter==end)
00228             return;
00229         else {
00230             table[hashval].erase(iter);
00231         }
00232     }

template<class KEY, class VALUE, int SIZ = 256>
iterator Hashtable< KEY, VALUE, SIZ >::erase (  const iterator &    iter )  [inline]
 

Erases the item in the requested array. 

00234                                           {
00235         iterator ret(iter.key,iter.v,iter.v->erase(iter.i));
00236         ret.findnext();
00237         return ret;
00238     }

template<class KEY, class VALUE, int SIZ = 256>
const_iterator Hashtable< KEY, VALUE, SIZ >::find (  const KEY &    key )  const [inline]
 

Gets a const iterator with the first value with the key (for const versions of this class).

The returned value contains: .first == iterator in the array EX: (*find(...).first).second is VALUE. .second == integer number of the array needed (for calls to end() and begin()) 

00201                                              {
00202         int tablenum=hash(key);
00203         const vector_type *mytyp=&table[tablenum];
00204         return const_iterator (key, mytyp);
00205     }

template<class KEY, class VALUE, int SIZ = 256>
iterator Hashtable< KEY, VALUE, SIZ >::find (  const KEY &    key )  [inline]
 

Gets an iterator with the first value with the key.

The returned value contains: .first == iterator in the array EX: (*find(...).first).second is VALUE. .second == integer number of the array needed (for calls to end() and begin()) 

00191                                   {
00192         int tablenum=hash(key);
00193         vector_type *mytyp=&table[tablenum];
00194         return iterator(key, mytyp);
00195     }

template<class KEY, class VALUE, int SIZ = 256>
VALUE* Hashtable< KEY, VALUE, SIZ >::Get (  const KEY &    key )  const
 

Gets the first value with this key.

template<class KEY, class VALUE, int SIZ = 256>
bool Hashtable< KEY, VALUE, SIZ >::Get (  const KEY &    key,
VALUE &    k
)  [inline]
  

00177                                          {
00178         VALUE * g = Get(key);
00179         if (g) {
00180             k=*g;
00181             return true;
00182         }
00183         return false;
00184     }

template<class KEY, class VALUE, int SIZ = 256>
const VALUE* Hashtable< KEY, VALUE, SIZ >::Get (  const KEY &    key )  const [inline]
  

00165     {
00166         int hashval = hash(key);
00167         typename vector_type::const_iterator iter = table[hashval].find(key);
00168         typename vector_type::const_iterator end = table[hashval].end();
00169         for(;iter!=end;iter++)
00170             if((*iter).first == key)
00171                 break;
00172         if (iter==end)
00173             return NULL;
00174         else
00175             return &(*iter).second;
00176     }

template<class KEY, class VALUE, int SIZ = 256>
VALUE* Hashtable< KEY, VALUE, SIZ >::Get (  const KEY &    key )  [inline]
 

Gets the first value with this key. 

00152     {
00153         int hashval = hash(key);
00154         typename vector_type::iterator iter = table[hashval].begin();
00155         typename vector_type::const_iterator end = table[hashval].end();
00156         for(;;iter++) {
00157             if (iter==end)
00158                 return NULL;
00159             if((*iter).first == key)
00160                 break;
00161         }
00162         return &(*iter).second;
00163     }

template<class KEY, class VALUE, int SIZ = 256>
std::vector<VALUE *> Hashtable< KEY, VALUE, SIZ >::GetAll (    )  const
 

Gets all contents of this hashtable.

template<class KEY, class VALUE, int SIZ = 256>
vector_type& Hashtable< KEY, VALUE, SIZ >::GetAll (  const KEY &    key )  [inline]
 

Gets all contents of this hashtable in the KEY th table.

WARNING: GetAll will return ALL contents of the table in which key lies, and MAY return unexpected VALUE s. This does make GetAll faster than other methods of getting 

00146     {
00147         int hashval = hash(key);
00148         return table[hashval];
00149     }

template<class KEY, class VALUE, int SIZ = 256>
int Hashtable< KEY, VALUE, SIZ >::hash (  const std::string &    key )  [inline, static, private]
 

the generic hash function given a string:notes that strings generally are 7 bits per char.FIXME: Should take into account that most stuffage is between 64 and 128 somehow. 

00088                                           {
00089         unsigned int k = 0;
00090         std::string::iterator start = key.begin();
00091         
00092         for(;start!=key.end(); start++) {
00093             k += (k * 128) + *start;
00094         }
00095         k %= SIZ;
00096         return k;
00097     }

template<class KEY, class VALUE, int SIZ = 256>
int Hashtable< KEY, VALUE, SIZ >::hash (  const int    key )  [inline, static, private]
 

the hash function that creates a hashval from an int by modding it by SIZ . 

00083                                    {
00084       return ((unsigned int)key)%SIZ;
00085     }

template<class KEY, class VALUE, int SIZ = 256>
int Hashtable< KEY, VALUE, SIZ >::hash (  const std::string &    key )  [inline, static]
 

the generic hash function given a string:notes that strings generally are 7 bits per char.FIXME: Should take into account that most stuffage is between 64 and 128 somehow. 

00117                                           {
00118         unsigned int k = 0;
00119         std::string::const_iterator start = key.begin();
00120         
00121         for(;start!=key.end(); start++) {
00122             k += (k * 128) + *start;
00123         }
00124         k %= SIZ;
00125         return k;
00126     }

template<class KEY, class VALUE, int SIZ = 256>
template<class Type>
int Hashtable< KEY, VALUE, SIZ >::hash (  const Type    key )  [inline, static]
 

The generic hash function given an int. 

00039                                                           {
00040       return ((unsigned int)key)%SIZ;
00041     }

template<class KEY, class VALUE, int SIZ = 256>
iterator Hashtable< KEY, VALUE, SIZ >::insert (  value_type    valty )  [inline]
 

adds this key/value pair without checking duplicates. 

00212                                       {
00213         int hashval = hash(valty.first);
00214         vector_type &tab=table[hashval];
00215         tab.push_back (valty);
00216         return iterator(valty.first, &tab, tab.end()-1);//fulliterator (SwapIn(table[hashval],valty), hashval);
00217     }

template<class KEY, class VALUE, int SIZ = 256>
void Hashtable< KEY, VALUE, SIZ >::Put (  const KEY &    key,
VALUE *    value
) 
 

Adds this key/value pair without checking duplicates.

template<class KEY, class VALUE, int SIZ = 256>
void Hashtable< KEY, VALUE, SIZ >::Put (  const KEY &    key,
const VALUE &    value
)  [inline]
 

adds this key/value pair without checking duplicates. 

00207                                                  {
00208         int hashval = hash(key);
00209         table[hashval].push_back(HashElement(key, value));
00210     }

template<class KEY, class VALUE, int SIZ = 256>
unsigned int Hashtable< KEY, VALUE, SIZ >::size (  int    vectorname )  const [inline]
 

Returns the size of the specified vector.

This is usually used to check for the array bounds 

00241                                              {
00242         return table[vectorname].size();
00243     }

template<class KEY, class VALUE, int SIZ = 256>
iterator Hashtable< KEY, VALUE, SIZ >::SwapIn (  vector_type *    tbl,
HashElement    elem
)  [inline, private]
  

00135                                                          {
00136         tbl.push_back(elem);
00137         iterator iter=tbl.back()-1;
00138         return iter;
00139     }

template<class KEY, class VALUE, int SIZ = 256>
void Hashtable< KEY, VALUE, SIZ >::swapiter (  iterator    iter1,
iterator    iter2
)  [inline, private]
  

00130                                                    {
00131         value_type backup=(*iter1);
00132         (*iter1)=(*iter2);
00133         (*iter2)=backup;
00134     }

Member Data Documentation

template<class KEY, class VALUE, int SIZ = 256>
Key Hashtable< KEY, VALUE, SIZ >::k [private]
 

template<class KEY, class VALUE, int SIZ = 256>
std::vector<HashElement> Hashtable< KEY, VALUE, SIZ >::table[SIZ] [private]
 

This is an array of vector s of the HashElement structure, which contains a KEY and a VALUE .

template<class KEY, class VALUE, int SIZ = 256>
vector_type Hashtable< KEY, VALUE, SIZ >::table[SIZ] [private]
 

Where the actual elements are stored, a statically sized table.

template<class KEY, class VALUE, int SIZ = 256>
VALUE* Hashtable< KEY, VALUE, SIZ >::val [private]
 

The documentation for this class was generated from the following files:
Generated on Mon Jul 7 21:13:52 2003 for Ethereal by doxygen1.2.15