mgctclassmap.inl

《3D游戏引擎设计》的源码

// Magic Software, Inc.
// http://www.magic-software.com
// Copyright (c) 2000, All Rights Reserved
//
// Source code from Magic Software is supplied under the terms of a license
// agreement and may not be copied or disclosed except in accordance with the
// terms of that agreement.  The various license agreements may be found at
// the Magic Software web site.  This file is subject to the license
//
// FREE SOURCE CODE
// http://www.magic-software.com/License/free.pdf

//----------------------------------------------------------------------------
template <class TKEY, class TVALUE>
MgcTClassMap<TKEY,TVALUE>::MgcTClassMap (unsigned int uiTableSize)
{
    assert( uiTableSize > 0 );

    m_uiTableSize = uiTableSize;
    m_uiQuantity = 0;
    m_uiIndex = 0;
    m_pkItem = 0;
    m_apkTable = new HashItem*[m_uiTableSize];
    memset(m_apkTable,0,m_uiTableSize*sizeof(HashItem*));
}
//----------------------------------------------------------------------------
template <class TKEY, class TVALUE>
MgcTClassMap<TKEY,TVALUE>::~MgcTClassMap ()
{
    RemoveAll();
    delete[] m_apkTable;
}
//----------------------------------------------------------------------------
template <class TKEY, class TVALUE>
unsigned int MgcTClassMap<TKEY,TVALUE>::GetQuantity () const
{
    return m_uiQuantity;
}
//----------------------------------------------------------------------------
template <class TKEY, class TVALUE>
bool MgcTClassMap<TKEY,TVALUE>::IsEmpty () const
{
    return m_uiQuantity == 0;
}
//----------------------------------------------------------------------------
template <class TKEY, class TVALUE>
bool MgcTClassMap<TKEY,TVALUE>::SetAt (const TKEY& rtKey,
    const TVALUE& rtValue)
{
    // find hash table entry for given key
    unsigned int uiIndex = HashFunction(rtKey);
    HashItem* pkItem = m_apkTable[uiIndex];

    // search for item in list associated with key
    while ( pkItem )
    {
        if ( rtKey == pkItem->m_tKey )
        {
            // item already in hash table
            return false;
        }
        pkItem = pkItem->m_pkNext;
    }

    // add item to beginning of list
    pkItem = new HashItem;
    pkItem->m_tKey = rtKey;
    pkItem->m_tValue = rtValue;
    pkItem->m_pkNext = m_apkTable[uiIndex];
    m_apkTable[uiIndex] = pkItem;
    m_uiQuantity++;

    return true;
}
//----------------------------------------------------------------------------
template <class TKEY, class TVALUE>
bool MgcTClassMap<TKEY,TVALUE>::GetAt (const TKEY& rtKey,
    TVALUE& rtValue) const
{
    // find hash table entry for given key
    unsigned int uiIndex = HashFunction(rtKey);
    HashItem* pkItem = m_apkTable[uiIndex];

    // search for item in list associated with key
    while ( pkItem )
    {
        if ( rtKey == pkItem->m_tKey )
        {
            // item is in hash table
            rtValue = pkItem->m_tValue;
            return true;
        }
        pkItem = pkItem->m_pkNext;
    }

    return false;
}
//----------------------------------------------------------------------------
template <class TKEY, class TVALUE>
bool MgcTClassMap<TKEY,TVALUE>::RemoveAt (const TKEY& rtKey)
{
    // find hash table entry for given key
    unsigned int uiIndex = HashFunction(rtKey);
    HashItem* pkItem = m_apkTable[uiIndex];

    if ( !pkItem )
    {
        return false;
    }
    else if ( rtKey == pkItem->m_tKey )
    {
        // item is at front of list, strip it off
        HashItem* pkSave = pkItem;
        m_apkTable[uiIndex] = pkItem->m_pkNext;
        delete pkSave;
        m_uiQuantity--;
        return true;
    }
    else
    {
        // search for item in list
        HashItem* pkPrev = pkItem;
        HashItem* pkCurr = pkItem->m_pkNext;
        while ( pkCurr && rtKey != pkCurr->m_tKey )
        {
            pkPrev = pkCurr;
            pkCurr = pkCurr->m_pkNext;
        }
        if ( pkCurr )
        {
            // found the item
            pkPrev->m_pkNext = pkCurr->m_pkNext;
            delete pkCurr;
            m_uiQuantity--;
            return true;
        }
    }

    return false;
}
//----------------------------------------------------------------------------
template <class TKEY, class TVALUE>
void MgcTClassMap<TKEY,TVALUE>::RemoveAll ()
{
    if ( m_uiQuantity > 0 )
    {
        for (unsigned int uiIndex = 0; uiIndex < m_uiTableSize; uiIndex++)
        {
            while ( m_apkTable[uiIndex] )
            {
                HashItem* pkSave = m_apkTable[uiIndex];
                m_apkTable[uiIndex] = m_apkTable[uiIndex]->m_pkNext;
                delete pkSave;
                if ( --m_uiQuantity == 0 )
                    return;
            }
        }
    }
}
//----------------------------------------------------------------------------
template <class TKEY, class TVALUE>
bool MgcTClassMap<TKEY,TVALUE>::GetFirst (TKEY& rtKey, TVALUE& rtValue)
{
    if ( m_uiQuantity > 0 )
    {
        for (m_uiIndex = 0; m_uiIndex < m_uiTableSize; m_uiIndex++)
        {
            if ( m_apkTable[m_uiIndex] )
            {
                m_pkItem = m_apkTable[m_uiIndex];
                rtKey = m_pkItem->m_tKey;
                rtValue = m_pkItem->m_tValue;
                return true;
            }
        }
    }

    return false;
}
//----------------------------------------------------------------------------
template <class TKEY, class TVALUE>
bool MgcTClassMap<TKEY,TVALUE>::GetNext (TKEY& rtKey, TVALUE& rtValue)
{
    if ( m_uiQuantity > 0 )
    {
        m_pkItem = m_pkItem->m_pkNext;
        if ( m_pkItem )
        {
            rtKey = m_pkItem->m_tKey;
            rtValue = m_pkItem->m_tValue;
            return true;
        }
        
        for (m_uiIndex++; m_uiIndex < m_uiTableSize; m_uiIndex++)
        {
            if ( m_apkTable[m_uiIndex] )
            {
                m_pkItem = m_apkTable[m_uiIndex];
                rtKey = m_pkItem->m_tKey;
                rtValue = m_pkItem->m_tValue;
                return true;
            }
        }
    }

    return false;
}
//----------------------------------------------------------------------------
template <class TKEY, class TVALUE>
unsigned int MgcTClassMap<TKEY,TVALUE>::HashFunction (const TKEY& rtKey) const
{
    static double s_dHashMultiplier = 0.5*(sqrt(5.0)-1.0);

    unsigned int uiKey = (unsigned int)rtKey;
    double dFraction = fmod(s_dHashMultiplier*uiKey,1.0);
    return (unsigned int)floor(m_uiTableSize*dFraction);
}
//----------------------------------------------------------------------------