HashAssocMap.h

Go to the documentation of this file.

//! @file HashAssocMap.h
//! CHashAssocMap is a template class that associate a key to a severals values
//!
// 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 CHashAssocMap 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 __CHASHEXMAP_H
#define __CHASHEXMAP_H
 
#include "HashMap.h"
 
BEGIN_MOOTOOLS_NAMESPACE
 
    #if defined(__WINDOWS__) && (_MSC_VER <= 1500)
    #pragma warning(push)
    #pragma warning(disable : 4181)
    #endif
 
    //! @class CHashAssocMap
    //! @brief CHashAssocMap is a template class that associate a key to a severals values.
    //! @details CHashAssocMap is an hash table of hash table.
    //! Use of CAssociationMap is more compact and should be used whenever possible.
    template <class KEY, class ARG_KEY, class VALUE>
    class CHashAssocMap : protected CHashMap<KEY, ARG_KEY, CHashTable<VALUE> *>
    {
        public:
            unsigned int GetCount() const; // Return the number of entries
            unsigned int GetAssociationCount() const; // Return the total number of association
            unsigned int GetAssociationCount(const ARG_KEY X) const; // Return the number of association for a given key
 
            void MergeAssociation(const ARG_KEY K, const CHashTable<VALUE>& V);
            int AddAssociation(const ARG_KEY K, const VALUE V);
            int RemoveAssociation(const ARG_KEY K, const VALUE V, bool enableResize = false);   // Return 1 if found, 0 if not. enableResize must be false if removal is done in a GetFirst/GetNext loop
            int RemoveAssociations(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 IsAssociationFound(const ARG_KEY K, VALUE& V);
            int GetFirstAssociationKey(const ARG_KEY X);
            int GetFirstAssociationValue(const ARG_KEY X, VALUE& V);
            // using CHashMap::IsFound;
            CHashTable<VALUE> *GetAssociations(const ARG_KEY X) const;
            HashPos GetFirst() const;
            void GetNext(HashPos& pos, KEY *K, CHashTable<VALUE> *&Associations) const;
            void GetNext(HashPos& pos, KEY& K, CHashTable<VALUE> *&Associations) const;
            void GetNextKey(HashPos& pos, KEY *K) const;
            void GetNextKey(HashPos& pos, KEY& K) const;
            void Clear();
            void Free();
 
            virtual ~CHashAssocMap( );
    };
 
    template <class KEY, class ARG_KEY, class VALUE>
    unsigned int CHashAssocMap<KEY, ARG_KEY, VALUE>::GetCount() const
    {
        return CHashMap<KEY, ARG_KEY, CHashTable<VALUE> *>::GetCount();
    }
 
    template <class KEY, class ARG_KEY, class VALUE>
    HashPos CHashAssocMap<KEY, ARG_KEY, VALUE>::GetFirst() const
    {
        return CHashMap<KEY, ARG_KEY, CHashTable<VALUE> *>::GetFirst();
    }
 
    template <class KEY, class ARG_KEY, class VALUE>
    void CHashAssocMap<KEY, ARG_KEY, VALUE>::GetNext(HashPos& pos, KEY& K, CHashTable<VALUE> *&Associations) const
    {
        CHashMap<KEY, ARG_KEY, CHashTable<VALUE> *>::GetNext(pos, K, Associations);
    }
 
    template <class KEY, class ARG_KEY, class VALUE>
    void CHashAssocMap<KEY, ARG_KEY, VALUE>::GetNext(HashPos& pos, KEY *K, CHashTable<VALUE> *&Associations) const
    {
        CHashMap<KEY, ARG_KEY, CHashTable<VALUE> *>::GetNext(pos, K, Associations);
    }
 
    template <class KEY, class ARG_KEY, class VALUE>
    void CHashAssocMap<KEY, ARG_KEY, VALUE>::GetNextKey(HashPos& pos, KEY& K) const
    {
        CHashTable<VALUE> *values;
        CHashMap<KEY, ARG_KEY, CHashTable<VALUE> *>::GetNext(pos, K, values);
    }
 
    template <class KEY, class ARG_KEY, class VALUE>
    void CHashAssocMap<KEY, ARG_KEY, VALUE>::GetNextKey(HashPos& pos, KEY *K) const
    {
        CHashTable<VALUE> *values;
        CHashMap<KEY, ARG_KEY, CHashTable<VALUE> *>::GetNext(pos, K, values);
    }
 
    template <class KEY, class ARG_KEY, class VALUE>
    void CHashAssocMap<KEY, ARG_KEY, VALUE>::Clear()
    {
        KEY K;
        CHashTable<VALUE> *values = NULL;
 
        HashPos pos = GetFirst();
        while(pos != HashEnd)
        {
            GetNext(pos, K, values);
            xDelete(values);
        }
 
        CHashMap<KEY, ARG_KEY, CHashTable<VALUE> *>::Clear();
    }
 
    template <class KEY, class ARG_KEY, class VALUE>
    void
    CHashAssocMap<KEY, ARG_KEY, VALUE>::Free()
    {
        CHashAssocMap<KEY, ARG_KEY, VALUE>::Clear();
        CHashMap<KEY, ARG_KEY, CHashTable<VALUE> *>::Free();
    }
 
    template <class KEY, class ARG_KEY, class VALUE>
    CHashAssocMap<KEY, ARG_KEY, VALUE>::~CHashAssocMap( )
    {
        Clear();
    }
 
    // 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>
    void CHashAssocMap<KEY, ARG_KEY, VALUE>::MergeAssociation(const ARG_KEY X, const CHashTable<VALUE>& V)
    {
        CHashTable<VALUE> *values;
 
        if (!Find(X, values))
        {
            values = xNew(CHashTable<VALUE>);
            values->Merge(V);
            Insert(X, values);
        }
        else
            values->Merge(V);
    }
 
    // 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>
    int CHashAssocMap<KEY, ARG_KEY, VALUE>::AddAssociation(const ARG_KEY X, const VALUE V)
    {
        CHashTable<VALUE> *values;
 
        if (!this->Find(X, values))
        {
            values = xNew(CHashTable<VALUE>);
            this->Insert(X, values);
        }
 
        return values->Insert(V);
    }
 
    template <class KEY, class ARG_KEY, class VALUE>
    int CHashAssocMap<KEY, ARG_KEY, VALUE>::RemoveAssociations(const ARG_KEY X, bool enableResize)
    {
        CHashTable<VALUE> *values;
 
        if (Find(X, values))
        {
            xDelete(values);
            Remove(X, enableResize);
 
            return 1;
        }
 
        return 0;
    }
 
    // Created 17/10/2001, Never tested
    template <class KEY, class ARG_KEY, class VALUE>
    int CHashAssocMap<KEY, ARG_KEY, VALUE>::IsAssociationFound(const ARG_KEY X, VALUE& V)
    {
        CHashTable<VALUE> *values;
 
        if (Find(X, values) && values->Find(V))
            return 1;
 
        return 0;
    }
 
    template <class KEY, class ARG_KEY, class VALUE>
    int CHashAssocMap<KEY, ARG_KEY, VALUE>::RemoveAssociation(const ARG_KEY X, const VALUE V, bool enableResize)
    {
        CHashTable<VALUE> *values;
 
        if (this->Find(X, values))
        {
            int result = values->Remove(V, enableResize);
 
            // Remove association and key if empty
            if (values->GetCount() == 0)
            {
                xDelete(values);
                this->Remove(X, enableResize);
            }
 
            return result;
        }
 
        return 0;
    }
 
    template <class KEY, class ARG_KEY, class VALUE>
    CHashTable<VALUE> *CHashAssocMap<KEY, ARG_KEY, VALUE>::GetAssociations(const ARG_KEY X ) const
    {
        CHashTable<VALUE> *values;
    
        if (this->Find(X, values))
            return values;
 
        return NULL;
    }
 
    // Get the first value in a association
    template <class KEY, class ARG_KEY, class VALUE>
    int CHashAssocMap<KEY, ARG_KEY, VALUE>::GetFirstAssociationKey(const ARG_KEY X)
    {
        HashPos pos = GetFirst();
        if (pos == HashEnd)
        {
            XASSERT(0);
            return false;
        }
    
        CHashTable<VALUE> *values;
        GetNext(pos, X, values);
 
        return true;
    }
 
    // Get the first value in a association
    template <class KEY, class ARG_KEY, class VALUE>
    int CHashAssocMap<KEY, ARG_KEY, VALUE>::GetFirstAssociationValue(const ARG_KEY X, VALUE& V)
    {
        CHashTable<VALUE> *values;
    
        if (this->Find(X, values))
        {
            HashPos pos;
            pos = values->GetFirst();
            if (pos == HashEnd)
            {
                XASSERT(0);
                return false;
            }
        
            values->GetNext(pos, V);
            return true;
        }
 
        return false;
    }
 
    // Get the first value in a association
    template <class KEY, class ARG_KEY, class VALUE>
    unsigned int CHashAssocMap<KEY, ARG_KEY, VALUE>::GetAssociationCount(const ARG_KEY X) const
    {
        CHashTable<VALUE> *values;
    
        if (Find(X, values))
            return values->GetCount();
 
        return 0;
    }
 
    // Get the first value in a association
    template <class KEY, class ARG_KEY, class VALUE>
    unsigned int CHashAssocMap<KEY, ARG_KEY, VALUE>::GetAssociationCount() const
    {
        KEY X;
        unsigned int count = 0;
 
        CHashTable<VALUE> *assocs;
        HashPos pos = GetFirst();
        while (pos != HashEnd)
        {
            const_cast<CHashAssocMap<KEY, ARG_KEY, VALUE> *>(this)->GetNext(pos, X, assocs);
            count += assocs->GetCount();
        }
 
        return count;
    }
 
    #if defined(__WINDOWS__) && (_MSC_VER <= 1500)
    #pragma warning(pop)
    #endif
 
END_MOOTOOLS_NAMESPACE
 
#endif // __CHASHEXMAP_H