HashMap.h

Go to the documentation of this file.

//! @file HashMap.h
//! @brief Associates key to a single value through an hash table.
//! 
// Associate a key to a single value
//
// KEY: must have zero-parameter and copy constructor,
// operator= and operator!=
// unsigned int Hash(const KEY & Key, int TableSize)
// must be defined
// CONSTRUCTION: with (a) no initializer;
// Copy constructon of CHashMap objects is DISALLOWED
// Deep copy is supported
//
// ******************PUBLIC OPERATIONS*********************
// int Insert(KEY X) --> Insert X
// int Remove(KEY X) --> Remove X
// KEY Find(KEY X) --> Return item that matches X
// int IsFound(KEY X) --> Return 1 if X would be found
// int IsEmpty() --> Return 1 if empty; else return 0
// void Clear() --> Remove all items
// ******************ERRORS********************************
// Predefined exception is propogated if new fails
 
#ifndef __CHASHMAP_H
#define __CHASHMAP_H
 
#include "Hash.h"
 
BEGIN_MOOTOOLS_NAMESPACE
 
 
    #if defined(__WINDOWS__) && (_MSC_VER <= 1500)
        // Const qualifier warning on VS2008 for ARG_KEY
        #pragma warning(push)
        #pragma warning(disable : 4181)
    #endif
 
    //! @class CHashMap
    //! @brief CHashMap is a template class that associates key to a single value through an hash table.
    template<class KEY, class ARG_KEY, class VALUE, typename HashFunctions = CHashMethods<KEY> > // Keep space between > > for Linux C98
    class CHashMap
    {
    public:
        enum KindOfEntry {
            Active, Empty, Deleted 
        };
 
        CHashMap(unsigned int defaultSize = DefaultHashSize);
        CHashMap(const CHashMap& Rhs);
 
        virtual ~CHashMap()
        {
    #ifdef MOOTOOLS_PRIVATE_DEBUG
            if (IsTraceEnabled())
                MOOTOOLS_PRIVATE_TRACE(traceStruct, 1, "HashMap ratio %f\n", ActiveSize/(float)ArraySize);
    #endif
            xDeleteArray(Array, ArraySize);
        }
 
        const CHashMap & operator=(const CHashMap & Rhs);
 
        int Insert2(const ARG_KEY K, const VALUE V); // Same has insert except that value is not a reference (we can pass an int for example)
        int Insert(const ARG_KEY K, const VALUE& V);
        int Remove(const ARG_KEY K, bool enableResize = false); // Return 1 if found, 0 if not. enableResize must be false if removal is done in a GetFirst/GetNext loop
        int Find(const ARG_KEY K, VALUE& V) const; // Return item in table. This return a copy and can be slower than the version below which get a pointer
        int Find(const ARG_KEY K, VALUE *&V) const; // Return item in table
        VALUE *Find(const ARG_KEY K) const; // Return item ptr in table, NULL if not found
        int IsFound(const ARG_KEY K) const; // Return 1 if found
        int IsEmpty() const;
        void Free();
        void Clear();
        unsigned int GetCount() const; // Return the element number
        HashPos GetFirst() const;
        void GetNext(HashPos& pos , KEY& element, VALUE& value) const;
        void GetNext(HashPos& pos, KEY& element, VALUE *& value) const;
        KEY& GetNext(HashPos& pos , VALUE& value) const;
        void GetNext(HashPos& pos , KEY *element, VALUE *value) const; // Return next item in map with corresponding value. This returns a copy and can be slower than the version below which get a pointer
        KEY *GetNext(HashPos& pos , VALUE *&value) const;
        void InitHashTable(unsigned int elementsNumber);
        unsigned int GetHashTableSize() const;
        bool Minimize();
 
        void Merge(const CHashMap& Rhs);
        void Remove(const CHashMap& Rhs);
 
    #ifdef MOOTOOLS_PRIVATE_DEBUG
        bool IsTraceEnabled() const { return traceEnabled; }
        void EnableTrace(bool show) { traceEnabled = show; }
    #endif
 
    private:
 
    #ifdef _DEBUG
        mutable bool checkResize; // Check that we not perform resize in GetFirst/GetNext
    #endif
 
    #ifdef MOOTOOLS_PRIVATE_DEBUG
        unsigned int CheckCount() const; // Return the element number
 
        mutable bool traceEnabled;
        mutable bool checkRehash; // Do not re-rehash
    #endif
 
        HashPos FindActiveElement(HashPos pos) const;
 
        // 05/2018 : Remove HashEntry(const Etype & E, KindOfEntry i = Empty) : Element(E), Info(i) constructor
        // It can be potentially dangerous if Etype is a class, as Element(E) requires a Etype::Etype(const EType& E) constructor which might be missing (in such case, the compile uses Etype::Etype() without warning, probably because HashEntry is a struct)
        // Additionally using this method make hash slower.
        struct HashEntry
        {
            KEY Key; // The key
            VALUE Value;
            KindOfEntry Info; // Active, empty, or deleted
 
            inline HashEntry() : Info(Empty) {}
        };
 
        unsigned int DefaultSize;
        unsigned int ArraySize; // The size of this array
        unsigned int CurrentSize; // The number of non-empty items
        unsigned int ActiveSize; // The number of active items
        HashEntry *Array; // The array of elements
 
        // Some internal routines
        void AllocateArray();
        bool ReHash(bool minimize);
        unsigned int FindPos(const ARG_KEY K) const;
    };
 
    // Friends functions
    template<class KEY, class ARG_KEY, class VALUE, typename HashFunctions> bool IsSameHashMap(const CHashMap<KEY, ARG_KEY, VALUE, HashFunctions> & Rhs1, const CHashMap<KEY, ARG_KEY, VALUE, HashFunctions> & Rhs2);
 
    template<class KEY, class ARG_KEY, class VALUE, typename HashFunctions>
    unsigned int CHashMap<KEY, ARG_KEY, VALUE, HashFunctions>::GetHashTableSize() const
    {
        return ArraySize;
    }
 
    // Allocate the hash table array
    template<class KEY, class ARG_KEY, class VALUE, typename HashFunctions>
    void CHashMap<KEY, ARG_KEY, VALUE, HashFunctions>::AllocateArray()
    {
        Array = xNewArray(HashEntry, ArraySize);
    }
 
    // CHashMap constructor
 
    template<class KEY, class ARG_KEY, class VALUE, typename HashFunctions>
    CHashMap<KEY, ARG_KEY, VALUE, HashFunctions>::CHashMap(unsigned int defaultSize)
    {
    #ifdef MOOTOOLS_PRIVATE_DEBUG
        traceEnabled = false;
        checkRehash = false;
    #endif
 
        Array = NULL;
        ArraySize = 0;
        ActiveSize = CurrentSize = 0;
        InitHashTable(defaultSize);
        
    #ifdef _DEBUG
        checkResize = false;
    #endif
    }
 
 
    template<class KEY, class ARG_KEY, class VALUE, typename HashFunctions>
    CHashMap<KEY, ARG_KEY, VALUE, HashFunctions>::CHashMap(const CHashMap& Rhs)
    {
#ifdef MOOTOOLS_PRIVATE_DEBUG
        traceEnabled = false;
#endif
 
#ifdef _DEBUG
        checkResize = false;
#endif
 
        DefaultSize = Rhs.DefaultSize;
        ArraySize = 0;
        Array = NULL;
        ActiveSize = CurrentSize = 0;
 
        *this = Rhs;
    }
 
    // Set a default starting size
    template<class KEY, class ARG_KEY, class VALUE, typename HashFunctions>
    void CHashMap<KEY, ARG_KEY, VALUE, HashFunctions>::InitHashTable(unsigned int elementsNumber)
    {
        if (Array != NULL) // Already allocated
        {
            elementsNumber = (elementsNumber+1)*2; // 06/19: +1 avoid some rehash when we specify exactly the number of the element of the map
            elementsNumber = NextPrime(elementsNumber);
            elementsNumber = (elementsNumber < MinimalHashSize) ? MinimalHashSize : elementsNumber; // If InitHashTable is called, elementNumber could be the real element number. Don't waste memory with extra space
 
            if (DefaultSize == elementsNumber)
                return;
        }
        else // Constructor only
        {
            if (elementsNumber != DefaultHashSize)
            {
                elementsNumber = NextPrime(elementsNumber);
                elementsNumber = (elementsNumber < MinimalHashSize) ? MinimalHashSize : elementsNumber; // If InitHashTable is called, elementNumber could be the real element number. Don't waste memory with extra space
            }
        }
 
        XASSERT(ActiveSize == 0 && CurrentSize == 0);
        xDeleteArray(Array, ArraySize);
 
        DefaultSize = elementsNumber;
        ArraySize = elementsNumber;
        AllocateArray();
        ActiveSize = CurrentSize = 0;
    }
 
 
    // Set back the hash table to its minimal size
    template<class KEY, class ARG_KEY, class VALUE, typename HashFunctions>
    void CHashMap<KEY, ARG_KEY, VALUE, HashFunctions>::Free()
    {
    #ifdef MOOTOOLS_PRIVATE_DEBUG
        if (IsTraceEnabled())
            MOOTOOLS_PRIVATE_TRACE(traceStruct, 1, "HashMap ratio %f\n", ActiveSize/(float)ArraySize);
    #endif
 
        xDeleteArray(Array, ArraySize);
 
        ArraySize = DefaultSize = DefaultHashSize;
        ActiveSize = CurrentSize = 0;
        AllocateArray();
    }
 
    // Clear the hash table, but keep memory allocated
    template<class KEY, class ARG_KEY, class VALUE, typename HashFunctions>
    void CHashMap<KEY, ARG_KEY, VALUE, HashFunctions>::Clear()
    {
    #ifdef MOOTOOLS_PRIVATE_DEBUG
        if (IsTraceEnabled())
            MOOTOOLS_PRIVATE_TRACE(traceStruct, 1, "HashMap ratio %f\n", ActiveSize/(float)ArraySize);
    #endif
 
        ActiveSize = CurrentSize = 0;
        for (unsigned int i = 0; i < ArraySize; i++)
            Array[i].Info = Empty;
    }
 
    // Return item in hash table that matches X
    template<class KEY, class ARG_KEY, class VALUE, typename HashFunctions>
    int CHashMap<KEY, ARG_KEY, VALUE, HashFunctions>::Find(const ARG_KEY X, VALUE& V) const
    {
        unsigned int CurrentPos = FindPos(X);
        if (Array[CurrentPos].Info == Active)
        {
            V = Array[CurrentPos].Value;
            return true;
        }
 
        return false;
    }
 
    // Return item in hash table that matches X
    template<class KEY, class ARG_KEY, class VALUE, typename HashFunctions>
    int CHashMap<KEY, ARG_KEY, VALUE, HashFunctions>::Find(const ARG_KEY X, VALUE *&V) const
    {
        unsigned int CurrentPos = FindPos(X);
        if (Array[CurrentPos].Info == Active)
        {
            V = &Array[CurrentPos].Value;
            return true;
        }
 
        return false;
    }
 
    // Return item ptr in hash table that matches X, allowing direct modification
    template<class KEY, class ARG_KEY, class VALUE, typename HashFunctions>
    VALUE *CHashMap<KEY, ARG_KEY, VALUE, HashFunctions>::Find(const ARG_KEY X) const
    {
        unsigned int CurrentPos = FindPos(X);
        if (Array[CurrentPos].Info == Active)
            return &Array[CurrentPos].Value;
 
        return NULL;
    }
 
    // Return true if hash could be reduced, false otherwise
    template<class KEY, class ARG_KEY, class VALUE, typename HashFunctions>
    bool CHashMap<KEY, ARG_KEY, VALUE, HashFunctions>::Minimize()
    {
        return ReHash(true); // ReHash does the job only if it is needed
    }
 
    template<class KEY, class ARG_KEY, class VALUE, typename HashFunctions>
    void CHashMap<KEY, ARG_KEY, VALUE, HashFunctions>::Remove(const CHashMap<KEY, ARG_KEY, VALUE, HashFunctions>& hash)
    {
        HashPos pos = hash.GetFirst();
        VALUE *value;
        while (pos != HashEnd)
        {
            KEY *key = hash.GetNext(pos, value);
            Remove(*key);
        }
    }
 
    template<class KEY, class ARG_KEY, class VALUE, typename HashFunctions>
    void CHashMap<KEY, ARG_KEY, VALUE, HashFunctions>::Merge(const CHashMap<KEY, ARG_KEY, VALUE, HashFunctions>& hash)
    {
        HashPos pos = hash.GetFirst();
        VALUE *value;
        while (pos != HashEnd)
        {
            KEY *key = hash.GetNext(pos, value);
            Insert(*key, *value);
        }
    }
 
    // Routine to resolve collisions and locate
    // cell that must contain X if X is found
    // 23/01/14: update FindPos. Cf. CHashTable::FindPos note
    // 10/10/17: minor optimization
    template<class KEY, class ARG_KEY, class VALUE, typename HashFunctions>
    inline unsigned int CHashMap<KEY, ARG_KEY, VALUE, HashFunctions>::FindPos(const ARG_KEY X) const
    {
        unsigned int i = 0; // The number of failed probes
        unsigned int CurrentPos = HashFunctions::HashValue(X) % ArraySize;
        unsigned int DeletedPos = (-1);
 
        while (Array[CurrentPos].Info != Empty)
        {
            if (Array[CurrentPos].Info == Active)
            {
                if (HashFunctions::HashCompare(Array[CurrentPos].Key, X))
                    return CurrentPos;
            }
            else if (DeletedPos == (-1))
            {
                XASSERT(Array[CurrentPos].Info == Deleted);
                DeletedPos = CurrentPos;
            }
 
            CurrentPos += 2*++i - 1; // Compute ith probe
            XASSERT(CurrentPos < ArraySize || ((CurrentPos - ArraySize) < ArraySize));
            if (CurrentPos >= ArraySize) // Implement the mod
                CurrentPos -= ArraySize;
        }
 
        // Return the first deleted entry if we found one
        // If no active element was found
        XASSERT(Array[CurrentPos].Info == Empty);
        return DeletedPos != (-1) ? DeletedPos : CurrentPos;
    }
 
    // Test if X is in the hash table
    template<class KEY, class ARG_KEY, class VALUE, typename HashFunctions>
    int CHashMap<KEY, ARG_KEY, VALUE, HashFunctions>::IsFound(const ARG_KEY X) const
    {
        unsigned int CurrentPos = FindPos(X);
        return (Array[CurrentPos].Info == Active);
    }
 
    // Remove X from hash table
    // Return true if X was removed; false otherwise
 
    template<class KEY, class ARG_KEY, class VALUE, typename HashFunctions>
    int
    CHashMap<KEY, ARG_KEY, VALUE, HashFunctions>::Remove(const ARG_KEY X, bool enableResize)
    {
        unsigned int CurrentPos = FindPos(X);
        if (Array[CurrentPos].Info != Active)
            return 0;
 
        XASSERT(ActiveSize >= 0);
        Array[CurrentPos].Info = Deleted;
        ActiveSize--;
 
        // Should not resize in the GetFirst/GetNext loop
        if (enableResize && (ActiveSize > DefaultHashSize)) // Avoid constant rehash for small bucket. Rehashing is done on insertion / minimize
            ReHash(false);
 
        return 1;
    }
 
    template<class KEY, class ARG_KEY, class VALUE, typename HashFunctions>
    int
    CHashMap<KEY, ARG_KEY, VALUE, HashFunctions>::Insert2(const ARG_KEY X, const VALUE V)
    {
        VALUE tmp = V;
        return Insert(X, tmp);
    }
 
 
    template<class KEY, class ARG_KEY, class VALUE, typename HashFunctions>
    bool CHashMap<KEY, ARG_KEY, VALUE, HashFunctions>::ReHash(bool minimize)
    {
#ifdef _DEBUG
        checkResize = true; // Check we are not in a GetFirst/GetNext loop. Rehashing is not supported when traversing the hash. Remove operation can be performed (which enableResize = false), but insertion is forbidden
#endif
 
        MOOTOOLS_PRIVATE_ASSERT(!checkRehash);
 
        // ReHash can be called for 2 different purposes : removing deleted elements when Insert-Remove occurs or minimize the size of the hash once it has been built
        unsigned int newSize = 0;
        if (minimize)
        {
            newSize = 2*(ActiveSize+1) < MinimalHashSize ? MinimalHashSize : 2*(ActiveSize+1); // +1 avoid some rehash, if NextPrime = 2*ActiveSize+1. Use MinimalHashSize, if we have few elements, don't waste space
            newSize = NextPrime(newSize);
            if (newSize == ArraySize)
            {
                MOOTOOLS_PRIVATE_ASSERT(CurrentSize < ArraySize/2);
                return false;
            }
        }
        else
        {
            if (CurrentSize < ArraySize/2) // Array is large enough. Rehash call with no reason
                return false;
 
            float ratio = (ActiveSize / (float)CurrentSize);
            if (ratio <= 0.65) // Array as t least 50% of empty element and 33% of deleted elements. Insert/Remove sequence called
            {
                newSize = 2*(ActiveSize+1); // This lead to downsize the array
                // newSize is the exact size for containing ActiveSize elements
                // newSize < 0.65*ArraySize and ActiveSize < 0.65*CurrentSize as CurrentSize < 2*ArraySize
                //
                // As we probably insert other element, give space to avoid a new immediate rehash after the next insert, but do not exceed ArraySize to lead to downsize
                newSize = (unsigned int)(newSize/0.65); // Maximum value will be around current ArraySize.
                if (newSize < DefaultHashSize)
                    newSize = DefaultHashSize;
            }
            else // Array is too small
                newSize = ArraySize < 251 ? 4*ArraySize : 2*ArraySize; // Faster grow for small array
 
            newSize = NextPrime(newSize);
            // Must rehash as CurrentSize >= ArraySize/2!
        }
 
        // REHASHING CODE
        // Save old table
        HashEntry *OldArray = Array;
        unsigned int OldArraySize = ArraySize;
 
        ArraySize = newSize;
        ActiveSize = CurrentSize = 0;
        AllocateArray();
 
    #ifdef MOOTOOLS_PRIVATE_DEBUG
        checkRehash = true;
    #endif
 
        // Copy table over
        for (unsigned int i = 0; i < OldArraySize; i++)
        {
            if (OldArray[i].Info == Active)
            {
                Insert(OldArray[i].Key, OldArray[i].Value);
            }
        }
 
    #ifdef MOOTOOLS_PRIVATE_DEBUG
        checkRehash = false;
    #endif
 
        // Recycle OldArray
        xDeleteArray(OldArray, OldArraySize);
 
        return true;
    }
 
    // Insert X into hash table
    // Return false if Xis a duplicate; true otherwise
    // Rehash automatically as needed
    template<class KEY, class ARG_KEY, class VALUE, typename HashFunctions>
    int CHashMap<KEY, ARG_KEY, VALUE, HashFunctions>::Insert(const ARG_KEY X, const VALUE& V)
    {
        unsigned int CurrentPos = FindPos(X);
 
        // Don't insert duplicates
        if (Array[CurrentPos].Info == Active)
        {
            // Update the value because (useful on classes where operator == might return true
            // for 2 differents contents...)
            Array[CurrentPos].Value = V;
            return 0;
        }
        else if (Array[CurrentPos].Info == Empty) // Can be Deleted
            CurrentSize++; // It is the number of non empty item
 
        ActiveSize++;
 
        // 05/2018: Cf note in HashEntry
        // Insert X as active
        Array[CurrentPos].Key = X;
        Array[CurrentPos].Value = V;
        Array[CurrentPos].Info = Active;
 
        if (CurrentSize < ArraySize/2)  // 06/19: Must rehash when CurrentSize = ArraySize/2 (ie when if ArraySize == 21, must rehash with CurrentSize = 10 (not 11!) or ith probe MIGHT fails in FindPos in next insertion
            return 1;
 
#ifdef MOOTOOLS_PRIVATE_DEBUG
        CheckCount();
#endif
 
        ReHash(false);
        return 1;
    }
 
    // Deep copy of the hash table
    template<class KEY, class ARG_KEY, class VALUE, typename HashFunctions>
    const CHashMap<KEY, ARG_KEY, VALUE, HashFunctions> &
    CHashMap<KEY, ARG_KEY, VALUE, HashFunctions>::operator=(const CHashMap<KEY, ARG_KEY, VALUE, HashFunctions> & Rhs)
    {
        if (this != &Rhs)
        {
            if (ArraySize != Rhs.ArraySize)
            {
                xDeleteArray(Array, ArraySize);
                ArraySize = Rhs.ArraySize;
                AllocateArray();
            }
 
            for (unsigned int i = 0; i < ArraySize; i++)
            {
                Array[i].Info = Rhs.Array[i].Info;
                if (Array[i].Info == Active)
                {
                    Array[i].Key = Rhs.Array[i].Key;
                    Array[i].Value = Rhs.Array[i].Value;
                }
            }
 
            DefaultSize = Rhs.DefaultSize;
            CurrentSize = Rhs.CurrentSize;
            ActiveSize = Rhs.ActiveSize;
        }
 
        return *this;
    } 
 
    template<class KEY, class ARG_KEY, class VALUE, typename HashFunctions>
    int CHashMap<KEY, ARG_KEY, VALUE, HashFunctions>::IsEmpty() const
    {
        return (ActiveSize == 0);
    }
 
    // Manu add
    template<class KEY, class ARG_KEY, class VALUE, typename HashFunctions>
    inline unsigned int CHashMap<KEY, ARG_KEY, VALUE, HashFunctions>::GetCount() const
    {
        return ActiveSize;
    }
 
    #ifdef MOOTOOLS_PRIVATE_DEBUG
    template<class KEY, class ARG_KEY, class VALUE, typename HashFunctions>
    unsigned int CHashMap<KEY, ARG_KEY, VALUE, HashFunctions>::CheckCount() const
    {
        if (CurrentSize == 0)
            return 0;
 
        unsigned int size1 = 0;
        unsigned int size2 = 0;
 
        // Copy table over
        for (unsigned int i = 0; i < ArraySize; i++)
        {
            if (Array[i].Info == Active)
                size1++;
            if (Array[i].Info != Empty)
                size2++;
        }
 
        XASSERT(ActiveSize == size1);
        XASSERT(CurrentSize == size2);
 
        return size1;
    }
    #endif
 
    // Find and active element from pos to end of the array
    template<class KEY, class ARG_KEY, class VALUE, typename HashFunctions>
    inline HashPos CHashMap<KEY, ARG_KEY, VALUE, HashFunctions>::FindActiveElement(HashPos pos) const
    {
        for (unsigned int i = pos; i < ArraySize; i++)
        {
            if (Array[i].Info == Active)
                return i;
        }
 
        return HashEnd;
    }
 
    template<class KEY, class ARG_KEY, class VALUE, typename HashFunctions>
    HashPos CHashMap<KEY, ARG_KEY, VALUE, HashFunctions>::GetFirst() const
    {
    #ifdef _DEBUG
        checkResize = false;
    #endif
 
        return FindActiveElement(0);
    }
 
    template<class KEY, class ARG_KEY, class VALUE, typename HashFunctions>
    void CHashMap<KEY, ARG_KEY, VALUE, HashFunctions>::GetNext(HashPos& pos, KEY& key, VALUE& value) const
    {
        XASSERT(pos < ArraySize);
        XASSERT(Array[pos].Info == Active);
        XASSERT(checkResize == false); // We must Rehash during a GetFirst/GetNext operation
 
        // Update the current element and find the next one
        key = Array[pos].Key;
        value = Array[pos].Value;
        pos = FindActiveElement(pos + 1);
    }
 
    template<class KEY, class ARG_KEY, class VALUE, typename HashFunctions>
    void CHashMap<KEY, ARG_KEY, VALUE, HashFunctions>::GetNext(HashPos& pos, KEY& key, VALUE *&value) const
    {
        XASSERT(pos < ArraySize);
        XASSERT(Array[pos].Info == Active);
        XASSERT(checkResize == false); // We must Rehash during a GetFirst/GetNext operation
 
        // Update the current element and find the next one
        key = Array[pos].Key;
        value = &Array[pos].Value;
        pos = FindActiveElement(pos + 1);
    }
 
    template<class KEY, class ARG_KEY, class VALUE, typename HashFunctions>
    void CHashMap<KEY, ARG_KEY, VALUE, HashFunctions>::GetNext(HashPos& pos, KEY *key, VALUE *value) const
    {
        XASSERT(pos < ArraySize);
        XASSERT(Array[pos].Info == Active);
        XASSERT(checkResize == false); // We must Rehash during a GetFirst/GetNext operation
 
        // Update the current element and find the next one
        key = &Array[pos].Key;
        value = &Array[pos].Value;
        pos = FindActiveElement(pos + 1);
    }
 
    template<class KEY, class ARG_KEY, class VALUE, typename HashFunctions>
    KEY *CHashMap<KEY, ARG_KEY, VALUE, HashFunctions>::GetNext(HashPos& pos, VALUE *&value) const
    {
        XASSERT(pos < ArraySize);
        XASSERT(Array[pos].Info == Active);
        XASSERT(checkResize == false); // We must Rehash during a GetFirst/GetNext operation
 
        // Update the current element and find the next one
        HashPos prevpos = pos;
        pos = FindActiveElement(pos + 1);
 
        value = &Array[prevpos].Value;
        return &Array[prevpos].Key;
    }
 
    template<class KEY, class ARG_KEY, class VALUE, typename HashFunctions>
    KEY& CHashMap<KEY, ARG_KEY, VALUE, HashFunctions>::GetNext(HashPos& pos, VALUE& value) const
    {
        XASSERT(pos < ArraySize);
        XASSERT(Array[pos].Info == Active);
        XASSERT(checkResize == false); // We must Rehash during a GetFirst/GetNext operation
 
        // Update the current element and find the next one
        HashPos prevpos = pos;
        pos = FindActiveElement(pos + 1);
 
        value = Array[prevpos].Value;
        return Array[prevpos].Key;
    }
 
    class DLL_TOOLSFUNCTION CIntMap : public CHashMap<int, int, int>
    {
    };
 
    #if defined(__WINDOWS__) && (_MSC_VER <= 1500)
        #pragma warning(pop)
    #endif
 
    template<class KEY, class ARG_KEY, class VALUE, typename HashFunctions>
    bool IsSameHashMap(const CHashMap<KEY, ARG_KEY, VALUE, HashFunctions> & Rhs1, const CHashMap<KEY, ARG_KEY, VALUE, HashFunctions> & Rhs2)
    {
        if (Rhs1.GetCount() != Rhs2.GetCount())
            return false;
 
        KEY *key1;
        VALUE *value1, *value2;
        HashPos pos = Rhs1.GetFirst();
        while (pos != HashEnd)
        {
            key1 = Rhs1.GetNext(pos, value1);
            value2 = Rhs2.Find(*key1);
            if (!value2)
                return false;
 
            if (*value1 != *value2)
                return false;
        }
 
        return true;
    }
END_MOOTOOLS_NAMESPACE
 
#endif // __CHASHMAP_H