XnHash.h

Go to the documentation of this file.

/****************************************************************************
*                                                                           *
*  OpenNI 1.x Alpha                                                         *
*  Copyright (C) 2011 PrimeSense Ltd.                                       *
*                                                                           *
*  This file is part of OpenNI.                                             *
*                                                                           *
*  OpenNI 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 3 of the License, or     *
*  (at your option) any later version.                                      *
*                                                                           *
*  OpenNI 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 OpenNI. If not, see <http://www.gnu.org/licenses/>.           *
*                                                                           *
****************************************************************************/
#ifndef _XN_HASH_H
#define _XN_HASH_H

//---------------------------------------------------------------------------
// Includes
//---------------------------------------------------------------------------
#include "XnList.h"

//---------------------------------------------------------------------------
// Defines
//---------------------------------------------------------------------------
#define XN_HASH_LAST_BIN 256
#define XN_HASH_NUM_BINS (XN_HASH_LAST_BIN + 1)
//---------------------------------------------------------------------------
// Types
//---------------------------------------------------------------------------
typedef XnValue XnKey;

typedef XnUInt8 XnHashValue;

static XnHashValue XnDefaultHashFunction(const XnKey& key)
{
    return (XnSizeT(key) & 0xff);
}

static XnInt32 XnDefaultCompareFunction(const XnKey& key1, const XnKey& key2)
{
    return XnInt32(XnSizeT(key1)-XnSizeT(key2));
}

class XnHash
{
public:
    class ConstIterator
    {
    public:
        friend class XnHash;

        ConstIterator(const ConstIterator& other) :
            m_pHash(other.m_pHash), m_nCurrentBin(other.m_nCurrentBin), m_Iterator(other.m_Iterator) {}

        ConstIterator& operator++()
        {
            ++m_Iterator;

            while (m_Iterator == m_pHash->m_Bins[m_nCurrentBin]->end() &&
                m_Iterator != m_pHash->m_Bins[XN_HASH_LAST_BIN]->end())
            {
                do
                {
                    m_nCurrentBin++;
                } while (m_pHash->m_Bins[m_nCurrentBin] == NULL);
                m_Iterator = m_pHash->m_Bins[m_nCurrentBin]->begin();
            }
            return *this;
        }

        ConstIterator operator++(int)
        {
            XnHash::ConstIterator other(*this);
            ++*this;
            return other;
        }

        ConstIterator& operator--()
        {
            --m_Iterator;

            while (m_Iterator == m_pHash->m_Bins[m_nCurrentBin]->end() &&
                m_Iterator != m_pHash->m_Bins[XN_HASH_LAST_BIN]->end())
            {
                do 
                {
                    if (m_nCurrentBin == 0)
                    {
                        m_nCurrentBin = XN_HASH_LAST_BIN;
                        m_Iterator = m_pHash->m_Bins[XN_HASH_LAST_BIN]->end();
                        return *this;
                    }
                    m_nCurrentBin--;
                } while (m_pHash->m_Bins[m_nCurrentBin] == NULL);
                m_Iterator = m_pHash->m_Bins[m_nCurrentBin]->rbegin();
            }
            return *this;
        }

        ConstIterator operator--(int)
        {
            ConstIterator other(*this);
            --*this;
            return other;
        }

        XnBool operator==(const ConstIterator& other) const
        {
            return m_Iterator == other.m_Iterator;
        }

        XnBool operator!=(const ConstIterator& other) const
        {
            return m_Iterator != other.m_Iterator;
        }

        const XnKey& Key() const
        {
            return ((XnNode*)(*m_Iterator))->Data();
        }

        const XnValue& Value() const
        {
            return ((XnNode*)(*m_Iterator))->Next()->Data();
        }

        XnNode* GetNode()
        {
            return m_Iterator.GetNode();
        }

        const XnNode* GetNode() const
        {
            return m_Iterator.GetNode();
        }

    protected:
        ConstIterator(const XnHash* pHash, XnUInt16 nBin, XnList::Iterator listIterator) :
             m_pHash(pHash), m_nCurrentBin(nBin), m_Iterator(listIterator)
             {
                 // Find the first valid
                 while (m_Iterator == m_pHash->m_Bins[m_nCurrentBin]->end() &&
                     m_Iterator != m_pHash->m_Bins[XN_HASH_LAST_BIN]->end())
                 {
                     do
                     {
                         m_nCurrentBin++;
                     } while (m_pHash->m_Bins[m_nCurrentBin] == NULL);
                     m_Iterator = m_pHash->m_Bins[m_nCurrentBin]->begin();
                 }
             }

        ConstIterator(const XnHash* pHash) : 
             m_pHash(pHash), m_nCurrentBin(0), m_Iterator(m_pHash->m_Bins[XN_HASH_LAST_BIN]->end()) {}

        const XnHash* m_pHash;
        XnUInt16 m_nCurrentBin;
        XnList::Iterator m_Iterator;
    };

    class Iterator : public ConstIterator
    {
    public:
        friend class XnHash;

        inline Iterator(const Iterator& other) : ConstIterator(other) {}

        inline Iterator& operator++() 
        { 
            ++(*(ConstIterator*)this);
            return (*this);
        }
        inline Iterator operator++(int) 
        { 
            Iterator result = *this;
            ++*this;
            return (result);
        }
        
        inline Iterator& operator--() 
        { 
            --(*(ConstIterator*)this); 
            return (*this);
        }
        inline Iterator operator--(int)
        { 
            Iterator result = *this;
            --*this;
            return (result);
        }

        XnKey& Key() const { return (XnKey&)ConstIterator::Key(); }

        XnValue& Value() const { return (XnValue&)ConstIterator::Value(); }

    protected:
        Iterator(const XnHash* pHash, XnUInt16 nBin, XnList::Iterator listIterator) :
            ConstIterator(pHash, nBin, listIterator)
        {}

        Iterator(const XnHash* pHash) : ConstIterator(pHash) {}

        Iterator(const ConstIterator& other) : ConstIterator(other) {}
    };

    friend class ConstIterator;

public:
    typedef XnHashValue (*XnHashFunction)(const XnKey& key);
    typedef XnInt32 (*XnCompareFunction)(const XnKey& key1, const XnKey& key2);

    XnHash()
    {
        m_nInitStatus = Init();
    }

    XnHash(const XnHash& other)
    {
        m_nInitStatus = Init();
        if (m_nInitStatus == XN_STATUS_OK)
        {
            m_nMinBin = other.m_nMinBin;
            m_CompareFunction = other.m_CompareFunction;
            m_HashFunction = other.m_HashFunction;
            for (int i = 0; i < XN_HASH_NUM_BINS; i++)
            {
                if (other.m_Bins[i] != NULL)
                {
                    m_Bins[i] = XN_NEW(XnList);
                    if (m_Bins[i] == NULL)
                    {
                        m_nInitStatus = XN_STATUS_ALLOC_FAILED;
                        return;
                    }
                    *(m_Bins[i]) = *(other.m_Bins[i]);
                }
            }
        }
    }

    virtual ~XnHash()
    {
        if (m_Bins != NULL)
        {
            for (int i = 0; i < XN_HASH_NUM_BINS; ++i)
            {
                XN_DELETE(m_Bins[i]);
            }
            XN_DELETE_ARR(m_Bins);
        }
    }

    XnStatus GetInitStatus() const
    {
        return m_nInitStatus;
    }

    XnStatus Set(const XnKey& key, const XnValue& value)
    {
        XnHashValue HashValue = (*m_HashFunction)(key);

        // Check if key already exists
        if (m_Bins[HashValue] != NULL)
        {
            Iterator hiter(this);
            if (Find(key, HashValue, hiter) == XN_STATUS_OK)
            {
                // Replace value
                hiter.Value() = value;
                return XN_STATUS_OK;
            }
        }
        else
        {
            // First time trying to access this bin, create it.
            m_Bins[HashValue] = XN_NEW(XnList);
            if (m_Bins[HashValue] == NULL)
            {
                return XN_STATUS_ALLOC_FAILED;
            }
            if (HashValue < m_nMinBin)
                m_nMinBin = HashValue;
        }

        // Get a new node for the key
        XnNode* pKeyNode = XnNode::Allocate();
        if (pKeyNode == NULL)
        {
            return XN_STATUS_ALLOC_FAILED;
        }
        pKeyNode->Data() = key;

        // Get a new node for the value
        XnNode* pValueNode = XnNode::Allocate();
        if (pValueNode == NULL)
        {
            XnNode::Deallocate(pKeyNode);
            return XN_STATUS_ALLOC_FAILED;
        }
        pValueNode->Data() = value;

        // Concatenate the value node to the key node
        pKeyNode->Next() = pValueNode;
        pValueNode->Next() = NULL;

        // Add the 2 nodes as the value to the key's list
        XnStatus ListStatus = m_Bins[HashValue]->AddLast(XnValue(pKeyNode));
        if (ListStatus != XN_STATUS_OK)
        {
            // Add failed. return the 2 nodes to the pool
            XnNode::Deallocate(pKeyNode);
            XnNode::Deallocate(pValueNode);
            return ListStatus;
        }

        return XN_STATUS_OK;
    }

    XnStatus Get(const XnKey& key, XnValue& value) const
    {
        // Check if key exists
        Iterator hiter(this);
        XnStatus FindStatus = Find(key, hiter);
        if (FindStatus != XN_STATUS_OK)
        {
            // Key doesn't exist!
            return FindStatus;
        }
        value = hiter.Value();

        return XN_STATUS_OK;
    }

    XnStatus Remove(const XnKey& key, XnValue& value)
    {
        // find the entry to which the key belongs
        Iterator hiter(this);

        XnStatus FindStatus = Find(key, hiter);
        if (FindStatus != XN_STATUS_OK)
        {
            // no such entry!
            return FindStatus;
        }

        // Remove by iterator
        value = hiter.Value();
        return Remove(hiter);
    }

    XnStatus Remove(ConstIterator iter, XnKey& key, XnValue& value)
    {
        if (iter == end())
        {
            //  Can't remove invalid node
            return XN_STATUS_ILLEGAL_POSITION;
        }

        // Get value and key, to return to the caller
        value = iter.Value();
        key = iter.Key();

        return Remove(iter);
    }

    virtual XnStatus Remove(ConstIterator iter)
    {
        if (iter == end())
        {
            //  Can't remove invalid node
            return XN_STATUS_ILLEGAL_POSITION;
        }

        XnNode* pNode = iter.GetNode();

        XnNode* pKeyNode = (XnNode*)(pNode->Data());
        XnNode* pValueNode = pKeyNode->Next();

        // Return the nodes to the pool
        XnNode::Deallocate(pKeyNode);
        XnNode::Deallocate(pValueNode);

        pNode->Previous()->Next() = pNode->Next();
        pNode->Next()->Previous() = pNode->Previous();

        XnNode::Deallocate(pNode);

        return XN_STATUS_OK;
    }


    XnStatus Clear()
    {
        while (begin() != end())
            Remove(begin());

        return XN_STATUS_OK;
    }

    XnBool IsEmpty() const
    {
        return (begin() == end());
    }

    XnUInt32 Size() const
    {
        XnUInt32 nSize = 0;
        for (Iterator iter = begin(); iter != end(); ++iter, ++nSize)
            ;

        return nSize;
    }

    XnStatus Find(const XnKey& key, ConstIterator& hiter) const
    {
        return ConstFind(key, hiter);
    }

    XnStatus Find(const XnKey& key, Iterator& hiter)
    {
        XnStatus nRetVal = XN_STATUS_OK;

        ConstIterator& it = hiter;
        nRetVal = ConstFind(key, it);
        XN_IS_STATUS_OK(nRetVal);

        return (XN_STATUS_OK);
    }

    Iterator begin()
    {
        return Iterator(this, m_nMinBin, m_Bins[m_nMinBin]->begin());
    }

    ConstIterator begin() const
    {
        return ConstIterator(this, m_nMinBin, m_Bins[m_nMinBin]->begin());
    }

    Iterator end()
    {
        return Iterator(this, XN_HASH_LAST_BIN, m_Bins[XN_HASH_LAST_BIN]->end());
    }

    ConstIterator end() const
    {
        return ConstIterator(this, XN_HASH_LAST_BIN, m_Bins[XN_HASH_LAST_BIN]->end());
    }

    XnStatus SetHashFunction(XnHashFunction hashFunction)
    {
        if (begin() != end())
        {
            return XN_STATUS_IS_NOT_EMPTY;
        }
        m_HashFunction = hashFunction;
        return XN_STATUS_OK;
    }

    XnStatus SetCompareFunction(XnCompareFunction compareFunction)
    {
        if (begin() != end())
        {
            return XN_STATUS_IS_NOT_EMPTY;
        }
        m_CompareFunction = compareFunction;
        return XN_STATUS_OK;
    }

protected:

    XnStatus Init()
    {
        m_Bins = XN_NEW_ARR(XnList*, XN_HASH_NUM_BINS);
        XN_VALIDATE_ALLOC_PTR(m_Bins);

        for (int i = 0; i < XN_HASH_NUM_BINS; i++)
        {
            m_Bins[i] = NULL;
        }

        m_Bins[XN_HASH_LAST_BIN] = XN_NEW(XnList); // We need this for  an end() iterator
        m_nMinBin = XN_HASH_LAST_BIN;

        XN_VALIDATE_ALLOC_PTR(m_Bins[XN_HASH_LAST_BIN]);
        m_CompareFunction = &XnDefaultCompareFunction;
        m_HashFunction = &XnDefaultHashFunction;
        return XN_STATUS_OK;
    }

    XnStatus Find(const XnKey& key, XnHashValue hashValue, ConstIterator& hiter) const
    {
        if (m_Bins[hashValue] != NULL)
        {
            hiter = ConstIterator(this, hashValue, m_Bins[hashValue]->begin());
            for (XnList::ConstIterator iter = m_Bins[hashValue]->begin();
                iter != m_Bins[hashValue]->end(); ++iter, ++hiter)
            {
                if ((*m_CompareFunction)(key, hiter.Key()) == 0)
                    return XN_STATUS_OK;
            }
        }

        return XN_STATUS_NO_MATCH;
    }


    XnList** m_Bins;

    XnUInt16 m_nMinBin;

    /* Status of initialization - could be an error if memory could not be allocated. */
    XnStatus m_nInitStatus;

    XnHashFunction m_HashFunction;
    XnCompareFunction m_CompareFunction;

private:
    XnStatus ConstFind(const XnKey& key, ConstIterator& hiter) const
    {
        XnHashValue HashValue = (*m_HashFunction)(key);
        return Find(key, HashValue, hiter);
    }
};

#define XN_DECLARE_DEFAULT_KEY_MANAGER_DECL(decl, KeyType, ClassName, KeyTranslator)    \
    class decl ClassName                                                                \
    {                                                                                   \
    public:                                                                             \
        inline static XnHashValue Hash(KeyType const& key)                              \
        {                                                                               \
            const XnKey _key = KeyTranslator::GetAsValue(key);                          \
            return XnDefaultHashFunction(_key);                                         \
        }                                                                               \
        inline static XnInt32 Compare(KeyType const& key1, KeyType const& key2)     \
        {                                                                               \
            const XnKey _key1 = KeyTranslator::GetAsValue(key1);                        \
            const XnKey _key2 = KeyTranslator::GetAsValue(key2);                        \
            return XnDefaultCompareFunction(_key1, _key2);                              \
        }                                                                               \
    };

#define XN_DECLARE_DEFAULT_KEY_MANAGER(KeyType, ClassName, KeyTranslator)   \
    XN_DECLARE_DEFAULT_KEY_MANAGER_DECL(, KeyType, ClassName, KeyTranslator)

#define XN_DECLARE_HASH_DECL(decl, KeyType, ValueType, ClassName, KeyTranslator, ValueTranslator, KeyManager)   \
    class decl ClassName : public XnHash                                                            \
    {                                                                                               \
    public:                                                                                         \
        class decl ConstIterator : public XnHash::ConstIterator                                     \
        {                                                                                           \
        public:                                                                                     \
            friend class ClassName;                                                                 \
            inline ConstIterator(const ConstIterator& other) : XnHash::ConstIterator(other) {}      \
            inline ConstIterator& operator++()                                                      \
            {                                                                                       \
                ++(*(XnHash::ConstIterator*)this);                                                  \
                return (*this);                                                                     \
            }                                                                                       \
            inline ConstIterator operator++(int)                                                    \
            {                                                                                       \
                ConstIterator result = *this;                                                       \
                ++*this;                                                                            \
                return result;                                                                      \
            }                                                                                       \
            inline ConstIterator& operator--()                                                      \
            {                                                                                       \
                --(*(XnHash::ConstIterator*)this);                                                  \
                return (*this);                                                                     \
            }                                                                                       \
            inline ConstIterator operator--(int)                                                    \
            {                                                                                       \
                ConstIterator result = *this;                                                       \
                --*this;                                                                            \
                return result;                                                                      \
            }                                                                                       \
            inline KeyType const& Key() const                                                       \
            {                                                                                       \
                return KeyTranslator::GetFromValue(XnHash::ConstIterator::Key());                   \
            }                                                                                       \
            inline ValueType const& Value() const                                                   \
            {                                                                                       \
                return ValueTranslator::GetFromValue(XnHash::ConstIterator::Value());               \
            }                                                                                       \
        protected:                                                                                  \
            inline ConstIterator(const XnHash::ConstIterator& other) :                              \
                XnHash::ConstIterator(other) {}                                                     \
        };                                                                                          \
        class decl Iterator : public ConstIterator                                                  \
        {                                                                                           \
        public:                                                                                     \
            friend class ClassName;                                                                 \
            inline Iterator(const Iterator& other) : ConstIterator(other) {}                        \
            inline Iterator& operator++()                                                           \
            {                                                                                       \
                ++(*(ConstIterator*)this);                                                          \
                return (*this);                                                                     \
            }                                                                                       \
            inline Iterator operator++(int)                                                         \
            {                                                                                       \
                Iterator result = *this;                                                            \
                ++*this;                                                                            \
                return result;                                                                      \
            }                                                                                       \
            inline Iterator& operator--()                                                           \
            {                                                                                       \
                --(*(ConstIterator*)this);                                                          \
                return (*this);                                                                     \
            }                                                                                       \
            inline Iterator operator--(int)                                                         \
            {                                                                                       \
                Iterator result = *this;                                                            \
                --*this;                                                                            \
                return result;                                                                      \
            }                                                                                       \
            inline KeyType& Key() const                                                             \
            {                                                                                       \
                return (KeyType&)ConstIterator::Key();                                              \
            }                                                                                       \
            inline ValueType& Value() const                                                         \
            {                                                                                       \
                return (ValueType&)ConstIterator::Value();                                          \
            }                                                                                       \
        protected:                                                                                  \
            inline Iterator(const XnHash::Iterator& other) : ConstIterator(other) {}                \
        };                                                                                          \
    public:                                                                                         \
        ClassName()                                                                                 \
        {                                                                                           \
            SetHashFunction(Hash);                                                                  \
            SetCompareFunction(Compare);                                                            \
        }                                                                                           \
        ClassName(const ClassName& other)                                                           \
        {                                                                                           \
            SetHashFunction(Hash);                                                                  \
            SetCompareFunction(Compare);                                                            \
            *this = other;                                                                          \
        }                                                                                           \
        virtual ~ClassName()                                                                        \
        {                                                                                           \
            while (!IsEmpty())                                                                      \
                Remove(begin());                                                                    \
        }                                                                                           \
        ClassName& operator=(const ClassName& other)                                                \
        {                                                                                           \
            Clear();                                                                                \
            for (ConstIterator it = other.begin(); it != other.end(); it++)                         \
            {                                                                                       \
                m_nInitStatus = Set(it.Key(), it.Value());                                          \
                if (m_nInitStatus != XN_STATUS_OK)                                                  \
                {                                                                                   \
                    return *this;                                                                   \
                }                                                                                   \
            }                                                                                       \
            return *this;                                                                           \
        }                                                                                           \
        XnStatus Set(KeyType const& key, ValueType const& value)                                    \
        {                                                                                           \
            Iterator oldIt = begin();                                                               \
            if (Find(key, oldIt) == XN_STATUS_OK)                                                   \
            {                                                                                       \
                oldIt.Value() = value;                                                              \
            }                                                                                       \
            else                                                                                    \
            {                                                                                       \
                XnKey _key = KeyTranslator::CreateValueCopy(key);                                   \
                XnValue _value = ValueTranslator::CreateValueCopy(value);                           \
                XnStatus nRetVal = XnHash::Set(_key, _value);                                       \
                if (nRetVal != XN_STATUS_OK)                                                        \
                {                                                                                   \
                    KeyTranslator::FreeValue(_key);                                                 \
                    ValueTranslator::FreeValue(_value);                                             \
                    return (nRetVal);                                                               \
                }                                                                                   \
            }                                                                                       \
            return XN_STATUS_OK;                                                                    \
        }                                                                                           \
        XnStatus Get(KeyType const& key, ValueType& value) const                                    \
        {                                                                                           \
            XnKey _key = KeyTranslator::GetAsValue(key);                                            \
            XnValue _value;                                                                         \
            XnStatus nRetVal = XnHash::Get(_key, _value);                                           \
            if (nRetVal != XN_STATUS_OK) return (nRetVal);                                          \
            value = ValueTranslator::GetFromValue(_value);                                          \
            return XN_STATUS_OK;                                                                    \
        }                                                                                           \
        XnStatus Get(KeyType const& key, ValueType*& pValue) const                                  \
        {                                                                                           \
            XnKey _key = KeyTranslator::GetAsValue(key);                                            \
            XnValue _value;                                                                         \
            XnStatus nRetVal = XnHash::Get(_key, _value);                                           \
            if (nRetVal != XN_STATUS_OK) return (nRetVal);                                          \
            pValue = &ValueTranslator::GetFromValue(_value);                                        \
            return XN_STATUS_OK;                                                                    \
        }                                                                                           \
        XnStatus Remove(KeyType const& key)                                                         \
        {                                                                                           \
            ValueType dummy;                                                                        \
            return Remove(key, dummy);                                                              \
        }                                                                                           \
        XnStatus Remove(KeyType const& key, ValueType& value)                                       \
        {                                                                                           \
            ConstIterator it = end();                                                               \
            XnStatus nRetVal = Find(key, it);                                                       \
            if (nRetVal != XN_STATUS_OK) return (nRetVal);                                          \
            value = it.Value();                                                                     \
            return Remove(it);                                                                      \
        }                                                                                           \
        inline XnStatus Remove(ConstIterator iter)                                                  \
        {                                                                                           \
            XnKey key = KeyTranslator::GetAsValue(iter.Key());                                      \
            XnValue value = ValueTranslator::GetAsValue(iter.Value());                              \
            XnStatus nRetVal = XnHash::Remove(iter);                                                \
            if (nRetVal != XN_STATUS_OK) return (nRetVal);                                          \
            KeyTranslator::FreeValue(key);                                                          \
            ValueTranslator::FreeValue(value);                                                      \
            return XN_STATUS_OK;                                                                    \
        }                                                                                           \
        XnStatus Find(KeyType const& key, ConstIterator& hiter) const                               \
        {                                                                                           \
            XnKey _key = KeyTranslator::GetAsValue(key);                                            \
            XnHash::ConstIterator it = XnHash::end();                                               \
            XnStatus nRetVal = XnHash::Find(_key, it);                                              \
            if (nRetVal != XN_STATUS_OK) return (nRetVal);                                          \
            hiter = it;                                                                             \
            return XN_STATUS_OK;                                                                    \
        }                                                                                           \
        XnStatus Find(KeyType const& key, Iterator& hiter)                                          \
        {                                                                                           \
            XnKey _key = KeyTranslator::GetAsValue(key);                                            \
            XnHash::Iterator it = XnHash::end();                                                    \
            XnStatus nRetVal = XnHash::Find(_key, it);                                              \
            if (nRetVal != XN_STATUS_OK) return (nRetVal);                                          \
            hiter = it;                                                                             \
            return XN_STATUS_OK;                                                                    \
        }                                                                                           \
        inline Iterator begin() { return XnHash::begin(); }                                         \
        inline ConstIterator begin() const { return XnHash::begin(); }                              \
        inline Iterator end() { return XnHash::end(); }                                             \
        inline ConstIterator end() const { return XnHash::end(); }                                  \
    protected:                                                                                      \
        virtual XnStatus Remove(XnHash::ConstIterator iter)                                         \
        {                                                                                           \
            return Remove(ConstIterator(iter));                                                     \
        }                                                                                           \
        inline static XnHashValue Hash(const XnKey& key)                                            \
        {                                                                                           \
            KeyType const& _key = KeyTranslator::GetFromValue(key);                                 \
            return KeyManager::Hash(_key);                                                          \
        }                                                                                           \
        inline static XnInt32 Compare(const XnKey& key1, const XnKey& key2)                     \
        {                                                                                           \
            KeyType const _key1 = KeyTranslator::GetFromValue(key1);                                \
            KeyType const _key2 = KeyTranslator::GetFromValue(key2);                                \
            return KeyManager::Compare(_key1, _key2);                                               \
        }                                                                                           \
    };

#define XN_DECLARE_HASH(KeyType, ValueType, ClassName, KeyTranslator, ValueTranslator, KeyManager)  \
    XN_DECLARE_HASH_DECL(, KeyType, ValueType, ClassName, KeyTranslator, ValueTranslator, KeyManager)

#define _XN_DEFAULT_KEY_MANAGER_NAME(ClassName) _##ClassName##Manager

#define XN_DECLARE_DEFAULT_MANAGER_HASH_DECL(decl, KeyType, ValueType, ClassName, KeyTranslator, ValueTranslator)   \
    XN_DECLARE_DEFAULT_KEY_MANAGER_DECL(decl, KeyType, _XN_DEFAULT_KEY_MANAGER_NAME(ClassName), KeyTranslator)      \
    XN_DECLARE_HASH_DECL(decl, KeyType, ValueType, ClassName, KeyTranslator, ValueTranslator, _XN_DEFAULT_KEY_MANAGER_NAME(ClassName))

#define XN_DECLARE_DEFAULT_MANAGER_HASH(decl, KeyType, ValueType, ClassName, KeyTranslator, ValueTranslator)    \
    XN_DECLARE_DEFAULT_MANAGER_HASH_DECL(, KeyType, ValueType, ClassName, KeyTranslator, ValueTranslator)

#define _XN_DEFAULT_KEY_TRANSLATOR(ClassName)   _##ClassName##KeyTranslator
#define _XN_DEFAULT_VALUE_TRANSLATOR(ClassName) _##ClassName##ValueTranslator

#define XN_DECLARE_DEFAULT_HASH_DECL(decl, KeyType, ValueType, ClassName)                                           \
    XN_DECLARE_DEFAULT_VALUE_TRANSLATOR_DECL(decl, KeyType, _XN_DEFAULT_KEY_TRANSLATOR(ClassName))                  \
    XN_DECLARE_DEFAULT_VALUE_TRANSLATOR_DECL(decl, ValueType, _XN_DEFAULT_VALUE_TRANSLATOR(ClassName))              \
    XN_DECLARE_DEFAULT_MANAGER_HASH_DECL(decl, KeyType, ValueType, ClassName, _XN_DEFAULT_KEY_TRANSLATOR(ClassName), _XN_DEFAULT_VALUE_TRANSLATOR(ClassName))

#define XN_DECLARE_DEFAULT_HASH(KeyType, ValueType, ClassName)      \
    XN_DECLARE_DEFAULT_HASH_DECL(, KeyType, ValueType, ClassName)

#endif // _XN_HASH_H