True Axis Physics SDK 1.2.0.1 Beta Documentation
www.trueaxis.com

---

HashTable.h

//---------------------------------------------------------------------------------
// File Name: HashTable.h
// Description: I'm sure any body could write a better hash table if they
//              wanted to.
//
// Copyright (C) 2004 - 2005 True Axis Pty Ltd, Australia. 
// All Rights Reserved.
//
// History:
//      Created File.
//---------------------------------------------------------------------------------

#ifndef TA_HASHTABLE_H
#define TA_HASHTABLE_H

#ifndef TA_TYPES_H
#include "Types.h"
#endif // TA_TYPES_H

#ifndef TA_STRING_H
#include "String.h"
#endif // TA_STRING_H

#ifndef TA_LIST_H
#include "List.h"
#endif // TA_LIST_H

namespace TA
{

template <class Type>
class TACOMMON_CLASS HashTable
{
public:
    class Item
    {
    public:
        Item() { m_pData = 0; }
        ~Item() {}

        Type* GetData() { return m_pData; }
        const Type* GetData() const { return m_pData; }
        void SetData(Type* pData) { m_pData = pData; }

    private:
        friend HashTable;
        Type* m_pData;
        String m_strString;
    };  
/*  // Seem to have trouble getting this to compile
    class Iterator
    {
    public:
        ~Iterator() { Finalise(); }
        void operator ++()
        {
            if (m_nEntry != -1)
            {
                if (m_itList.AtEnd())
                {
                    m_nEntry++;
                    if (m_nEntry < m_nHashSize)
                        m_itList = pHashTable[m_nEntry];
                    else
                        m_nEntry = -1;
                }
                else
                {
                    ++m_itList;
                }
            }
        }
        Item& operator *() { return *m_itList; }
        bool AtEnd() { return m_nEntry == -1; }
    private:
        friend HashTable;
        Iterator() 
        { 
            m_nEntry = -1; 
            m_pHashTable = 0; 
        }
        void Initialise(List<Item>* pHashTable, int nHashSize) 
        {       
            m_nEntry = 0;
            m_pHashTable = pHashTable;
            m_itList = pHashTable[m_nEntry];
            m_nHashSize = nHashSize;
        }
        void Finalise() 
        { 
            m_nEntry = -1; 
            m_pHashTable = 0; 
        }
        int m_nHashSize;
        int m_nEntry;
        List<Item>::Iterator m_itList;
        List<Item>* m_pHashTable;
    };
    */

    HashTable();
    ~HashTable();

    void Initialise(int nHashSize); // nHashSize should be a prime number
    void Finalise();

    Item& CreateItem(const Char* szString);
    Item* GetItemIfExists(const Char* szString);
    void RemoveItem(const Char* szString);

    //---------------------------------------------------------------------------------
    // Traverse the hash table and return a callback for each item.
    //---------------------------------------------------------------------------------
    void Traverse(void (TAC_CALL *pCallBack)(Item& item, void* pCallBackData), void* pCallBackData);

    //---------------------------------------------------------------------------------
    // This is a reasonably chunky iterator
    //---------------------------------------------------------------------------------
    //Iterator GetIterator()


private:

    int m_nHashSize;
    List<Item>* m_pHashTable;

    int CalculateHashValue(const Char * szString);

};

//---------------------------------------------------------------------------------
//---------------------------------------------------------------------------------
template <class Type>
HashTable<Type>::HashTable() 
{
    m_pHashTable = 0;
}

//---------------------------------------------------------------------------------
//---------------------------------------------------------------------------------
template <class Type>
HashTable<Type>::~HashTable()
{
    Finalise();
}

//---------------------------------------------------------------------------------
//---------------------------------------------------------------------------------
template <class Type>
void HashTable<Type>::Initialise(int nHashSize)
{
    m_nHashSize = nHashSize;
    if (m_pHashTable != 0)
    {
        TA_ASSERT(0);
        Finalise();
    }
    TA_MEMORY_MGR_NEW_ARRAY(m_pHashTable, List<Item>, m_nHashSize);
}

//---------------------------------------------------------------------------------
//---------------------------------------------------------------------------------
template <class Type>
void HashTable<Type>::Finalise()
{   
    if (m_pHashTable)
    {       
        TA_MEMORY_MGR_DELETE_ARRAY(m_pHashTable, List<Item>);
        m_pHashTable = 0;
    }
    m_nHashSize = 0;
}

//---------------------------------------------------------------------------------
//---------------------------------------------------------------------------------
template <class Type>
typename HashTable<Type>::Item& HashTable<Type>::CreateItem(const Char* szString)
{
    // todo: use a better searching method
    int nHashValue = CalculateHashValue(szString);  
    List<Item>& list = m_pHashTable[nHashValue];
    for (List<Item>::Iterator it = list.GetIterator(); !it.AtEnd(); ++it)
    {
        Item& item = *it;
        if (item.m_strString == szString)
            return item;
    }
    Item& item = list.Append();
    item.m_strString = szString;
    return item;
}

//---------------------------------------------------------------------------------
//---------------------------------------------------------------------------------
template <class Type>
typename HashTable<Type>::Item* HashTable<Type>::GetItemIfExists(const Char* szString)
{
    // todo: use a better searching method
    int nHashValue = CalculateHashValue(szString);  
    List<Item>& list = m_pHashTable[nHashValue];
    for (List<Item>::Iterator it = list.GetIterator(); !it.AtEnd(); ++it)
    {
        Item& item = *it;
        if (item.m_strString == szString)
            return &item;
    }
    return 0;
}

//---------------------------------------------------------------------------------
//---------------------------------------------------------------------------------
template <class Type>
void HashTable<Type>::RemoveItem(const Char* szString)
{
    int nHashValue = CalculateHashValue(szString);  
    List<Item>& list = m_pHashTable[nHashValue];
    for (List<Item>::Iterator it = list.GetIterator(); !it.AtEnd(); ++it)
    {
        Item& item = *it;
        if (item.m_strString == szString)
        {
            list.Remove(&item);
            return;
        }
    }
}

//---------------------------------------------------------------------------------
//---------------------------------------------------------------------------------
/*template <class Type>
HashTable<Type>::Iterator HashTable<Type>::GetIterator()
{
    Iterator it;
    it.Initialise(m_pHashTable, m_nHashSize);
    return it;
}*/

//---------------------------------------------------------------------------------
//---------------------------------------------------------------------------------
template <class Type>
void HashTable<Type>::Traverse(void (TAC_CALL *pCallBack)(Item& item, void* pCallBackData), void* pCallBackData)
{
    if (!pCallBack)
        return;
    for (int nIndex = 0; nIndex < m_nHashSize; nIndex++)
    {   
        List<Item>& list = m_pHashTable[nIndex];
        for (List<Item>::Iterator it = list.GetIterator(); !it.AtEnd(); ++it)
        {
            Item& item = *it;
            pCallBack(item, pCallBackData);
        }
    }
}

//---------------------------------------------------------------------------------
//---------------------------------------------------------------------------------
template <class Type>
int HashTable<Type>::CalculateHashValue(const Char * szString)
{
    // calculate hash function
    for (int nHashValue = 0; *szString != '\0'; szString++)
        nHashValue = ((nHashValue << 8) + *szString) % m_nHashSize;
    return nHashValue;
}

};

#endif // TA_HASHTABLE_H

---

© Copyright 2004-2006 TRUE AXIS PTY LTD Australia. All rights reserved.