Hash.h

//! @file HashTable.h
//! @brief Implements a template hash table
//! 
// Etype: must have zero-parameter and copy constructor,
// operator= and operator!=
// unsigned int Hash( const Etype & Element, int TableSize )
// must be defined
// CONSTRUCTION: with (a) no initializer;
// Copy constructon of CHashTable objects is DISALLOWED
// Deep copy is supported
//
// ******************PUBLIC OPERATIONS*********************
// int Insert( Etype X ) --> Insert X
// int Remove( Etype X ) --> Remove X
// Etype Find( Etype X ) --> Return item that matches X
// int IsFound( Etype X ) --> Return 1 if X would be found
// int IsEmpty( ) --> Return 1 if clear; else return 0
// void Clear( ) --> Remove all items
// ******************ERRORS********************************
// Predefined exception is propogated if new fails
 
#ifndef __CHASHTABLE_H
#define __CHASHTABLE_H
 
BEGIN_MOOTOOLS_NAMESPACE
 
    typedef unsigned int HashPos;
 
    #define HashEnd (unsigned int)(-1)
    #define MinimalHashSize 5 // Must be prime number
    #define DefaultHashSize 23 // Must be prime number
 
    #ifdef MOOTOOLS_PRIVATE_DEBUG
        #define MOOTOOLS_HASH_ADVANCED_DEBUG
 
        #ifdef MOOTOOLS_HASH_ADVANCED_DEBUG
            typedef struct HashStats
            {
                bool checkAllocAboveDefaultSize;
                unsigned int rehash;
                unsigned int insertCollisionCount, rehashCollissionCount;
                unsigned int rehashCollision;
                unsigned int insertCollision;
 
                HashStats()
                {
                    checkAllocAboveDefaultSize = true;
                    rehash = insertCollisionCount = rehashCollissionCount = rehashCollision = insertCollision = 0;
                }
            } HashStats;
 
            typedef enum
            {
                HASH_DBG_INIT = 1,
                HASH_DBG_ALLOC,
                HASH_DBG_BAD_DEFAULT,
            } HASH_DEBUG_INFO;
 
            DLL_TOOLSFUNCTION unsigned int GetDefaultHashSize();
            DLL_TOOLSFUNCTION void DebugCheckHashStats(HASH_DEBUG_INFO info);
            DLL_TOOLSFUNCTION void EnableHashStats(bool enable);
            DLL_TOOLSFUNCTION void ReportHashStats(LPCTSTR txt, unsigned int activeSize, unsigned int currentSize, unsigned int arraySize, HashStats& stats);
 
            #undef DefaultHashSize
            #define DefaultHashSize GetDefaultHashSize()
        #endif
    #endif
 
    // Hash computation
#ifdef _DEBUG
    DLL_TOOLSFUNCTION bool IsPrime(unsigned int N);
#endif
 
    DLL_TOOLSFUNCTION unsigned int NextPrime(unsigned int N);
 
    // std lib hash method
    inline unsigned int HashBuffer(const char *values, longuint count)
    {
        const unsigned int _FNV_offset_basis = 2166136261U;
        const unsigned int _FNV_prime = 16777619U;
 
        unsigned int _Val = _FNV_offset_basis;
 
        longuint i = count;
        while (i--)
        {   // fold in another byte
            _Val ^= (unsigned int)values[i];
            _Val *= _FNV_prime;
        }
 
        return (_Val);
    }
 
    inline unsigned int HashBuffer(const wchar_t *values, longuint count)
    {
        const unsigned int _FNV_offset_basis = 2166136261U;
        const unsigned int _FNV_prime = 16777619U;
 
        unsigned int _Val = _FNV_offset_basis;
 
        longuint i = count;
        while (i--)
        {   // fold in another byte
            _Val ^= (unsigned int)values[i];
            _Val *= _FNV_prime;
        }
 
        return (_Val);
    }
 
    template<class TYPE> inline longuint Hash64DefaultType(TYPE key)
    {
        key = (~key) + (key << 21); // key = (key << 21) - key - 1;
        key = key ^ (key >> 24);
        key = (key + (key << 3)) + (key << 8); // key * 265
        key = key ^ (key >> 14);
        key = (key + (key << 2)) + (key << 4); // key * 21
        key = key ^ (key >> 28);
        key = key + (key << 31);
        return (longuint)key;
    }
 
    template<class TYPE> inline unsigned int HashDefaultType(TYPE key)
    {
        key = (~key) + (key << 18);
        key = key ^ (key >> 31);
        key = key * 21;
        key = key ^ (key >> 11);
        key = key + (key << 6);
        key = key ^ (key >> 22);
        return (unsigned int)(key);
    }
 
    template<class TYPE> inline unsigned int HashMixValue(TYPE value)
    {
        value += ~(value << 15);
        value ^= (value >> 10);
        value += (value << 3);
        value ^= (value >> 6);
        value += ~(value << 11);
        value ^= (value >> 16);
        return value;
    }
 
    template<class TYPE> class CHashMethods
    {
    public:
        static inline bool HashCompare(const TYPE& a, const TYPE& b);
        static inline unsigned int HashValue(const TYPE& a);
    };
 
    template <class TYPE> class CHashMethods<TYPE *>
    {
    public:
        static inline bool HashCompare(const TYPE *a, const TYPE *b)
        {
            return a == b;
        }
 
        static inline unsigned int HashValue(const TYPE *ptr)
        {
            return HashDefaultType((longuint)(ptr));
        }
    };
 
    template <> class CHashMethods<unsigned int>
    {
    public:
        static inline bool HashCompare(unsigned int a, unsigned int b)
        {
            return a == b;
        }
 
        static inline unsigned int HashValue(unsigned int value)
        {
            return value << 4;
        }
    };
 
    template <> class CHashMethods<int> : public CHashMethods<unsigned int> {};
    template <> class CHashMethods<unsigned char> : public CHashMethods<unsigned int> {};
    template <> class CHashMethods<char > : public CHashMethods<unsigned int> {};
    template <> class CHashMethods<wchar_t > : public CHashMethods<unsigned int> {};
 
#if defined(__LINUX__) && (__WORDSIZE != 32)
    template <> class CHashMethods<unsigned long long>
    {
    public:
        static inline bool HashCompare(unsigned long long a, unsigned long long b)
        {
            return a == b;
        }
 
        // cf. Integer Hash Function. Thomas Wang, Jan 1997 - last update Mar 2007 Version 3.1
        // https://gist.github.com/badboy/6267743 
        static inline unsigned int HashValue(unsigned long long key)
        {
            return HashDefaultType(key);
        }
    };
 
    template <> class CHashMethods<long long>
    {
    public:
        static inline bool HashCompare(long long a, long long b)
        {
            return a == b;
        }
 
        // cf. Integer Hash Function. Thomas Wang, Jan 1997 - last update Mar 2007 Version 3.1
        // https://gist.github.com/badboy/6267743 
        static inline unsigned int HashValue(long long key)
        {
            return HashDefaultType(key);
        }
    };
#endif
 
    template <> class CHashMethods<longuint>
    {
    public:
        static inline bool HashCompare(longuint a, longuint b)
        {
            return a == b;
        }
 
        // cf. Integer Hash Function. Thomas Wang, Jan 1997 - last update Mar 2007 Version 3.1
        // https://gist.github.com/badboy/6267743 
        static inline unsigned int HashValue(longuint key)
        {
            return HashDefaultType(key);
        }
    };
 
    template <> class CHashMethods<longint>
    {
    public:
        static inline bool HashCompare(longint a, longint b)
        {
            return a == b;
        }
 
        static inline unsigned int HashValue(longint key)
        {
            return HashDefaultType(key);
        }
    };
 
#ifdef __WINDOWS__
    template <> class CHashMethods<unsigned long>
    {
    public:
        static inline bool HashCompare(unsigned long a, unsigned long b)
        {
            return a == b;
        }
 
        static inline unsigned int HashValue(unsigned long value)
        {
            return value << 4;
        }
    };
#endif
 
    template <> class CHashMethods<float>
    {
    public:
        static inline bool HashCompare(float a, float b)
        {
            return a == b;
        }
 
        static inline unsigned int HashValue(float value)
        {
            // On IEEE-float machines, minus zero and zero have different bit patterns
            // but should compare as equal.  We must ensure that they have the same
            // hash value, which is most reliably done this way:
            if (value == 0.0f)
                return 0;
 
            return *((unsigned int *)&value);
        }
    };
 
    template <> class CHashMethods<double>
    {
    public:
        static inline bool HashCompare(double a, double b)
        {
            return a == b;
        }
 
        static inline unsigned int HashValue(double value)
        {
            // On IEEE-float machines, minus zero and zero have different bit patterns
            // but should compare as equal.  We must ensure that they have the same
            // hash value, which is most reliably done this way:
            if (value == 0.0)
                return 0;
 
            return *((unsigned int *)&value);
        }
    };
 
    template <> class CHashMethods<CXStringW>
    {
    public:
        static inline unsigned int HashValue(const CXStringW &Key)
        {
            return HashBuffer(Key, Key.GetLength());
        }
 
        static inline bool HashCompare(const CXStringW& a, const CXStringW& b)
        {
            return a == b;
        }
    };
 
    template <> class CHashMethods<CXStringA>
    {
    public:
        static inline unsigned int HashValue(const CXStringA &Key)
        {
            return HashBuffer(Key, Key.GetLength());
        }
 
        static inline bool HashCompare(const CXStringA& a, const CXStringA& b)
        {
            return a == b;
        }
    };
 
    //! @class CHashTable
    //! @brief CHashTable is a template class that implements an hash table.
    //! @details CHashMethods must be provided to compare entries and generate hash value for the template EType
    template<class Etype, typename HashFunctions = CHashMethods<Etype> > class CHashTable   // Keep space between > > for Linux C98
    {
        public:
 
        enum KindOfEntry {
            Active, Empty, Deleted
        };
 
        CHashTable(unsigned int defaultSize = DefaultHashSize);
        CHashTable(const CHashTable& Rhs);
        virtual ~CHashTable();
 
        const CHashTable & operator=(const CHashTable & Rhs);
        unsigned int CopyTo(CXArray<Etype>& dstArray) const;
        unsigned int InitFrom(const CXArray<Etype>& dstArray, bool clear = true);
 
        void InitHashTable(unsigned int elementsNumber);
        unsigned int GetHashTableSize() const;
        bool Minimize();
 
        bool Compare(const CHashTable& Rhs) const; // return true if same
        void Merge(const CHashTable& Rhs);
        void Remove(const CHashTable& Rhs);
        int Insert(const Etype & X);
        void InsertAndReplace(const Etype & X);
        int Remove(const Etype & X, bool enableResize = false); // Return 1 if found, 0 if not. enableResize must be false if removal is done in a GetFirst/GetNext loop
        int FindAndUpdate(Etype & X); // Return item in table
        int IsFound(const Etype & X) 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, Etype& element) const;  // Get the next element. This return a copy and can be slower than GetNextPtr(HashPos& pos) which return a pointer on the element.
//      void GetNext(HashPos& pos, Etype *&element) const; // Get the next element pointer
        Etype& GetNext(HashPos& pos) const; // Return the next element. This return a copy and can be slower than GetNextPtr(HashPos& pos) which returns a pointer on the element.
        Etype *GetNextPtr(HashPos& pos) const; // Return a pointer on the next element.
 
    private:
        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
        {
            Etype Element; // The item
            unsigned char Info; // Active, empty, or deleted
            HashEntry() : Info(CHashTable<Etype, HashFunctions>::Empty) {}
        };
 
        unsigned int DefaultSize;
        unsigned int ArraySize; // The size of this array
        unsigned int CurrentSize; // The number of non-empty items (Active or Deleted)
        unsigned int ActiveSize; // The number of active items (hash Active items)
        HashEntry *Array; // The array of elements
 
        // Some internal routines
        void AllocateArray();
        bool ReHash(bool minimize);
        unsigned int FindPos(const Etype & X) const;
 
#ifdef _DEBUG
        mutable bool checkResize; // Check that we not perform resize in GetFirst/GetNext
#endif
 
#ifdef MOOTOOLS_HASH_ADVANCED_DEBUG
        mutable HashStats stats;
        unsigned int CheckCount() const; // Return the element number
#endif
    };
 
    // Friends functions
    template<class Etype, typename HashFunctions> bool IsSameHash(const CHashTable<Etype, HashFunctions> & Rhs1, const CHashTable<Etype, HashFunctions> & Rhs2);
 
    // Define function here to allow CHashTable without specialisation
    // Allocate the hash table array
    template<class Etype, typename HashFunctions> void CHashTable<Etype, HashFunctions>::AllocateArray()
    {
    #ifdef MOOTOOLS_HASH_ADVANCED_DEBUG
        DebugCheckHashStats(HASH_DBG_ALLOC);
        if (ArraySize > DefaultSize && stats.checkAllocAboveDefaultSize)
        {
            stats.checkAllocAboveDefaultSize = false;
            DebugCheckHashStats(HASH_DBG_BAD_DEFAULT);
        }
    #endif
 
        Array = xNewArray(HashEntry, ArraySize);
    }
 
    // CHashTable constructor
    template<class Etype, typename HashFunctions>
    CHashTable<Etype, HashFunctions>::CHashTable(unsigned int defaultSize)
    {
        Array = NULL;
        ArraySize = 0;
        ActiveSize = CurrentSize = 0;
        InitHashTable(defaultSize);
 
    #ifdef _DEBUG
        checkResize = false;
    #endif
 
    #ifdef MOOTOOLS_HASH_ADVANCED_DEBUG
        DebugCheckHashStats(HASH_DBG_INIT);
    #endif
 
    }
 
    template<class Etype, typename HashFunctions>
    CHashTable<Etype, HashFunctions>::CHashTable(const CHashTable& Rhs)
    {
        Array = NULL;
        ArraySize = 0;
        ActiveSize = CurrentSize = 0;
 
#ifdef _DEBUG
        checkResize = false;
#endif
 
#ifdef MOOTOOLS_HASH_ADVANCED_DEBUG
    DebugCheckHashStats(HASH_DBG_INIT);
#endif
 
        *this = Rhs;
    }
 
    // CHashTable constructor
    template<class Etype, typename HashFunctions>
    CHashTable<Etype, HashFunctions>::~CHashTable()
    {
        xDeleteArray(Array, ArraySize);
 
    #ifdef MOOTOOLS_HASH_ADVANCED_DEBUG
        Array = NULL; // Check that array is not accessed after deletion
        ReportHashStats(_T("CHashTable::~CHashTable"), ActiveSize, CurrentSize, ArraySize, stats);
    #endif
    }
    template<class Etype, typename HashFunctions>
    void CHashTable<Etype, 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
        {
            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;
    }
 
    template<class Etype, typename HashFunctions>
    unsigned int CHashTable<Etype, HashFunctions>::GetHashTableSize() const
    {
        return ArraySize;
    }
 
    template<class Etype, typename HashFunctions> void CHashTable<Etype, HashFunctions>::Free()
    {
    #ifdef MOOTOOLS_HASH_ADVANCED_DEBUG
        ReportHashStats(_T("CHashTable::Free"), ActiveSize, CurrentSize, ArraySize, stats);
    #endif
 
        xDeleteArray(Array, ArraySize);
 
        ArraySize = DefaultSize = DefaultHashSize;
        ActiveSize = CurrentSize = 0;
        AllocateArray();
    }
 
    // Clear the hash table
    template<class Etype, typename HashFunctions> void CHashTable<Etype, HashFunctions>::Clear()
    {
    #ifdef MOOTOOLS_HASH_ADVANCED_DEBUG
        ReportHashStats(_T("CHashTable::Clear"), ActiveSize, CurrentSize, ArraySize, stats);
    #endif
 
        if (ActiveSize == 0 && CurrentSize == 0)
            return;
 
        ActiveSize = CurrentSize = 0;
        for (unsigned int i = 0; i < ArraySize; i++)
            Array[i].Info = Empty;
    }
 
    // Find an element and update it. If HashCompare is complete and the element inserted is the same than the X we provide
    // In such case, IsFound is faster and should be used
    template<class Etype, typename HashFunctions> int CHashTable<Etype, HashFunctions>::FindAndUpdate(Etype& X)
    {
        unsigned int CurrentPos = FindPos(X);
 
        if (Array[CurrentPos].Info == Active)
        {
            X = Array[CurrentPos].Element;
            return true;
        }
 
        return false;
    }
 
    // Return true if hash could be reduced, false otherwise
    template<class Etype, typename HashFunctions> bool CHashTable<Etype, HashFunctions>::Minimize()
    {
    #ifdef MOOTOOLS_HASH_ADVANCED_DEBUG
            ReportHashStats(_T("CHashTable::Minimize"),  ActiveSize, CurrentSize, ArraySize, stats);
    #endif
 
        return ReHash(true); // ReHash does the job only if it is needed
    }
 
    // Routine to resolve collisions and locate
    // cell that must contain X if X is found
    // Note:
    // 04/07/2013 changes: the hash could returns a deleted element, to reuse it
    // As the caller checks if the element is active this have no incidence.
    //
    // Before the hash calls HashCompare for every element, even deleted
    // 10/10/17: minor optimization
    template<class Etype, typename HashFunctions>
    inline unsigned int CHashTable<Etype, HashFunctions>::FindPos(const Etype & 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].Element, 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;
        }
 
    #ifdef MOOTOOLS_HASH_ADVANCED_DEBUG
        if (i > stats.insertCollisionCount)
            stats.insertCollisionCount = i;
        if (i > stats.rehashCollissionCount)
            stats.rehashCollissionCount = i;
    #endif
 
        // 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 Etype, typename HashFunctions> int CHashTable<Etype, HashFunctions>::IsFound(const Etype & 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 Etype, typename HashFunctions> int CHashTable<Etype, HashFunctions>::Remove(const Etype & X, bool enableResize)
    {
        unsigned int CurrentPos = FindPos(X);
        if (Array[CurrentPos].Info != Active)
            return 0;
 
        XASSERT(ActiveSize >= 0);
        Array[CurrentPos].Info = Deleted; // Do not tag as empty, otherwise this makes holes in findpos
        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 Etype, typename HashFunctions> void CHashTable<Etype, HashFunctions>::Remove(const CHashTable<Etype, HashFunctions>& hash)
    {
        HashPos pos = hash.GetFirst();
 
        while (pos != HashEnd)
        {
            const Etype& value = hash.GetNext(pos);
            Remove(value);
        }
    }
 
    template<class Etype, typename HashFunctions> bool CHashTable<Etype, HashFunctions>::Compare(const CHashTable<Etype, HashFunctions>& hash) const
    {
        if (GetCount() != hash.GetCount())
            return false;
 
        HashPos pos = hash.GetFirst();
        const Etype* value;
        while (pos != HashEnd)
        {
            value = hash.GetNextPtr(pos);
            if (!IsFound(*value))
                return false;
        }
 
        return true;
    }
 
    template<class Etype, typename HashFunctions> void CHashTable<Etype, HashFunctions>::Merge(const CHashTable<Etype, HashFunctions>& hash)
    {
        HashPos pos = hash.GetFirst();
        Etype *value;
 
        while (pos != HashEnd)
        {
            value = hash.GetNextPtr(pos);
            Insert(*value);
        }
    }
 
    // Insert X into hash table
    // Update X if it exists, which make sense only when a class defined an operator == which might return true
    // for 2 differents contents...
 
    template<class Etype, typename HashFunctions> void CHashTable<Etype, HashFunctions>::InsertAndReplace(const Etype & X)
    {
        unsigned int CurrentPos = FindPos(X);
 
        if (Array[CurrentPos].Info == Active)
        {
            Array[CurrentPos].Element = X;
            return;
        }
 
        // Does not exists, insert it...
        Insert(X);
        return;
    }
 
    // 06/2019: modify rehash method to make it automatically compute the size
    //
    // 01/07/2013: use 6*ActiveSize instead 2*ArraySize
    //  note 2*ActiveSize is an array that as the minimal free space (see condition above)
    //  2*2*ActiveSize is a correct size, which 2 time more space than needed
    //  6*ActiveSize leaves enough space to avoid constant rehash, when adding and removing entries many times
    //  6*ActiveSize < 2*ArraySize avoids to allocate array too big (when hash is used to only adds entries)
    //
    //  The hash array size should be sized accordingly to the real size element number
    //  not the currentSize element number which is made of active and deleted values
    //  The ReHash methods removes deleted entries...
    //  The previous forms generates very large array for the pairs array in Polygon Cruncher
    //  as it spends its time to add and removes pairs.
    template<class Etype, typename HashFunctions> bool CHashTable<Etype, 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
 
        // 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_HASH_ADVANCED_DEBUG
        stats.rehashCollissionCount = 0;
    #endif
 
        // Copy table over
        for (unsigned int i = 0; i < OldArraySize; i++)
        {
            if (OldArray[i].Info == Active)
            {
                Insert(OldArray[i].Element);
            }
        }
 
    #ifdef MOOTOOLS_HASH_ADVANCED_DEBUG
        stats.rehash++;
 
        if (stats.rehashCollissionCount  > stats.rehashCollision)
            stats.rehashCollision = stats.rehashCollissionCount;
    #endif
 
        // Recycle OldArray
        xDeleteArray(OldArray, OldArraySize);
        
        return true;
    }
 
    template<class Etype, typename HashFunctions> int CHashTable<Etype, HashFunctions>::Insert(const Etype & X)
    {
    #ifdef MOOTOOLS_HASH_ADVANCED_DEBUG
        stats.insertCollisionCount = 0;
    #endif
 
        unsigned int CurrentPos = FindPos(X);
 
        // Don't insert duplicates
        if (Array[CurrentPos].Info == Active)
            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].Element = X;
        Array[CurrentPos].Info = Active;
 
    #ifdef MOOTOOLS_HASH_ADVANCED_DEBUG
        if (stats.insertCollisionCount  > stats.insertCollision)
            stats.insertCollision = stats.insertCollisionCount;
    #endif
 
        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_HASH_ADVANCED_DEBUG
        CheckCount();
    #endif
 
        ReHash(false);
        return 1;
    }
 
    // Copy of the hash table to an array
    template<class Etype, typename HashFunctions>
    unsigned int CHashTable<Etype, HashFunctions>::CopyTo(CXArray<Etype>& dstArray) const
    {
        dstArray.SetSize(GetCount());
 
        unsigned int i = 0;
        HashPos pos = GetFirst();
        while (pos != HashEnd)
            dstArray[i++] = GetNext(pos);
 
        XASSERT(i == GetCount());
        return i;
    }
 
    template<class Etype, typename HashFunctions>
    inline unsigned int CHashTable<Etype, HashFunctions>::InitFrom(const CXArray<Etype>& dstArray, bool clear)
    {
        if (clear)
            Clear();
 
        unsigned int i, size = dstArray.GetSize();
        for (i=0;i<size; i++)
            Insert(dstArray[i]);
 
        return GetCount();;
    }
 
    // Deep copy of the hash table
    template<class Etype, typename HashFunctions> const CHashTable<Etype, HashFunctions> &CHashTable<Etype, HashFunctions>::operator=(const CHashTable<Etype, 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].Element = Rhs.Array[i].Element;
            }
 
            DefaultSize = Rhs.DefaultSize;
            CurrentSize = Rhs.CurrentSize;
            ActiveSize = Rhs.ActiveSize;
        }
 
        return *this;
    } 
 
    template<class Etype, typename HashFunctions> int CHashTable<Etype, HashFunctions>::IsEmpty() const
    {
        return (ActiveSize == 0);
    }
 
    // Manu add
    template<class Etype, typename HashFunctions>
    inline unsigned int CHashTable<Etype, HashFunctions>::GetCount() const
    {
        return ActiveSize;
    }
 
    #ifdef MOOTOOLS_HASH_ADVANCED_DEBUG
    template<class Etype, typename HashFunctions> unsigned int CHashTable<Etype, 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 Etype, typename HashFunctions> HashPos CHashTable<Etype, HashFunctions>::FindActiveElement(HashPos pos) const
    {
        for (unsigned int i = pos; i < ArraySize; i++)
        {
            if (Array[i].Info == Active)
                return i;
        }
 
        return HashEnd;
    }
 
    template<class Etype, typename HashFunctions> HashPos CHashTable<Etype, HashFunctions>::GetFirst() const
    {
    #ifdef _DEBUG
        checkResize = false;
    #endif
 
        return FindActiveElement(0);
    }
 
    template<class Etype, typename HashFunctions> void CHashTable<Etype, HashFunctions>::GetNext(HashPos& pos, Etype& element) 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
        element = Array[pos].Element;
        pos = FindActiveElement(pos + 1);
    }
 
    //template<class Etype, typename HashFunctions> void CHashTable<Etype, HashFunctions>::GetNext(HashPos& pos, Etype *&element) 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
    //  element = &Array[pos].Element;
    //  pos = FindActiveElement(pos + 1);
    //}
 
    template<class Etype, typename HashFunctions> Etype& CHashTable<Etype, HashFunctions>::GetNext(HashPos& pos) 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);
 
        return Array[prevpos].Element;
    }
 
    template<class Etype, typename HashFunctions> Etype *CHashTable<Etype, HashFunctions>::GetNextPtr(HashPos& pos) 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);
 
        return &Array[prevpos].Element;
    }
    
    template<class Etype, typename HashFunctions>
    bool IsSameHash(const CHashTable<Etype, HashFunctions> & Rhs1, const CHashTable<Etype, HashFunctions> & Rhs2)
    {
        if (Rhs1.GetCount() != Rhs2.GetCount())
            return false;
 
        Etype *key;
        HashPos pos = Rhs1.GetFirst();
        while (pos != HashEnd)
        {
            key = Rhs1.GetNextPtr(pos);
            if (!Rhs2.IsFound(*key))
                return false;
        }
 
        return true;
    }
 
    END_MOOTOOLS_NAMESPACE
 
#endif // __CHASHTABLE_H