TCHashTable.h

Go to the documentation of this file.

//*******************************************************************************
//
// *******   ***   ***               *
//    *     *     *                  *
//    *    *      *                *****
//    *    *       ***  *   *   **   *    **    ***
//    *    *          *  * *   *     *   ****  * * *
//    *     *         *   *      *   * * *     * * *
//    *      ***   ***    *     **   **   **   *   *
//                        *
//*******************************************************************************
// see http://sourceforge.net/projects/tcsystem/ for details.
// Copyright (C) 2003 - 2008 Thomas Goessler. All Rights Reserved. 
//*******************************************************************************
//
// TCSystem is the legal property of its developers.
// Please refer to the COPYRIGHT file distributed with this source distribution.
// 
// This library is free software; you can redistribute it and/or             
// modify it under the terms of the GNU Lesser General Public                
// License as published by the Free Software Foundation; either              
// version 2.1 of the License, or (at your option) any later version.        
//                                                                           
// This library is distributed in the hope that it will be useful,           
// but WITHOUT ANY WARRANTY; without even the implied warranty of            
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU         
// Lesser General Public License for more details.                           
//                                                                           
// You should have received a copy of the GNU Lesser General Public          
// License along with this library; if not, write to the Free Software       
// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA.
//*******************************************************************************
//  $Id: TCHashTable.h 801 2008-01-23 19:46:25Z the_____tiger $
//*******************************************************************************

#ifndef TC_HASHTABLE_H
#define TC_HASHTABLE_H

#include "TCTypes.h"

#include <vector>
#include <string>
#include <functional>

namespace TC
{
   template <class KEY_TYPE> struct Hash { };

   template<> struct Hash<sint8>
   {
       uint32 operator() (sint8 val) const { return val; }
   };
   template<> struct Hash<uint8>
   {
       uint32 operator() (uint8 val) const { return val; }
   };
   template<> struct Hash<sint16>
   {
       uint32 operator() (sint16 val) const { return val; }
   };
   template<> struct Hash<uint16>
   {
       uint32 operator() (uint16 val) const { return val; }
   };
   template<> struct Hash<sint32>
   {
       uint32 operator() (sint32 val) const { return val; }
   };
   template<> struct Hash<uint32>
   {
       uint32 operator() (uint32 val) const { return val; }
   };

   template<> struct Hash<char*>
   {
       uint32 operator() (const char* text) const
       {
           const char *s = text;
           uint32 h=0;
           uint32 c;
           while((c=*s++) != '\0')
           {
               h = ((h << 5) + h) ^ c;
           }
           return h;
       }
   };

   template<> struct Hash<std::string>
   {
       uint32 operator() (const std::string& text) const
       {
           const char *s = text.c_str();
           uint32 h=0;
           uint32 c;
           while((c=*s++) != '\0')
           {
               h = ((h << 5) + h) ^ c;
           }
           return h;
       }
   };

   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 HashTable
   {
   private:
       struct _Element
       {
           KEY_TYPE key_value;
           MAP_TYPE map_value;
       };

   public:
       HashTable(uint32 size, const MAP_TYPE& notFound)
           :m_size(size),
            m_not_found(notFound)
       {
           Clear();
       }

       virtual ~HashTable() {}

       inline uint32 GetHashSize() const { return m_size; }

       inline void SetHashSize(uint32 size)
       {
           m_size = size;
           Clear();
       }

       inline void Clear()
       {
           m_data.clear();
           m_data.reserve(m_size);
           for (uint32 i=0; i<m_size; i++)
           {
               m_data.push_back(std::vector< _Element >());
           }
       }

       inline const MAP_TYPE& GetNotFoundValue() const { return m_not_found; }

       inline void SetNotFoundValue(const MAP_TYPE& notFound) { m_not_found = notFound; }

       void AddKey(const KEY_TYPE &key_value, const MAP_TYPE& map_value)
       {
           uint32 p1;
           sint32 p2;
           GetElementPosition(key_value, p1, p2);

           _Element elem;
           elem.key_value = key_value;
           elem.map_value = map_value;
           if (p2 == -1)
           {
               m_data[p1].push_back(elem);
           }
           else
           {
               m_data[p1][p2] = elem;
           }
       }

       void RemoveKey(const KEY_TYPE &key_value)
       {
           uint32 p1;
           sint32 p2;
           GetElementPosition(key_value, p1, p2);


           if (p2 != -1)
           {
               m_data[p1].erase(m_data[p1].begin() + p2);
           }
       }

       const MAP_TYPE& GetMappedValue(const KEY_TYPE& key_value) const
       {
           uint32 p1;
           sint32 p2;
           GetElementPosition(key_value, p1, p2);

           if (p2 == -1)
           {
               return m_not_found;
           }
           else
           {
               return m_data[p1][p2].map_value;
           }
       }

       const MAP_TYPE& operator[](const KEY_TYPE& key_value) const { return GetMappedValue(key_value);}

       void GetAllKeys(std::vector< KEY_TYPE >& keys)
       {
           for (uint32 i=0; i<m_data.size(); i++)
           {
               for (uint32 j=0; j<m_data[i].size(); j++)
               {
                   keys.push_back(m_data[i][j].key_value);
               }
           }
       }

       void GetAllKeysAndValues(std::vector< KEY_TYPE >& keys, std::vector< MAP_TYPE >& values)
       {
           for (uint32 i=0; i<m_data.size(); i++)
           {
               for (uint32 j=0; j<m_data[i].size(); j++)
               {
                   keys.push_back(m_data[i][j].key_value);
                   values.push_back(m_data[i][j].map_value);
               }
           }
       }

       void GetStatistics(uint32& numEmptyLists, uint32& maxListLength, double& avgListLength) const
       {
           numEmptyLists = 0;
           maxListLength = 0;
           avgListLength = 0;
           for (uint32 i = 0; i < m_data.size(); i++)
           {
               uint32 thisListLength = m_data[i].size();
               if (thisListLength == 0) numEmptyLists++;
               if (maxListLength < thisListLength) maxListLength = thisListLength;
               avgListLength += thisListLength;
           }
           avgListLength /= m_data.size();
       }

   private:
       void GetElementPosition(const KEY_TYPE &key_value, uint32 &p1, sint32 &p2) const
       {
           KEY_VALUE_COMPARE_FUNC compare;
           p1 = GetTableEntryPosition(key_value);
           p2 = -1;
           for (uint32 i=0; i<m_data[p1].size(); i++)
           {
               if (compare(m_data[p1][i].key_value, key_value))
               {
                   p2 = i;
                   break;
               }
           }
       }

       uint32 GetTableEntryPosition(const KEY_TYPE &key_value) const
       {
           HASH_FUNC func;
           return (func(key_value) % m_size);
       }

   private:
       uint32 m_size;
       MAP_TYPE m_not_found;
       std::vector< std::vector< _Element > > m_data;
   };

} // namespace TC

#endif // TC_HASHTABLE_H