XnHash.h

Go to the documentation of this file.

/*****************************************************************************
*                                                                            *
*  OpenNI 1.0 Alpha                                                          *
*  Copyright (C) 2010 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 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 Iterator;

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
        {
                XnHashValue HashValue = (*m_HashFunction)(key);
                return Find(key, HashValue, hiter);
        }

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

                ConstIterator& it = hiter;
                nRetVal = Find(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;
};

#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