Hashing.h

Go to the documentation of this file.

/*
 * $Revision: 2299 $
 * 
 * last checkin:
 *   $Author: gutwenger $ 
 *   $Date: 2012-05-07 15:57:08 +0200 (Mon, 07 May 2012) $ 
 ***************************************************************/
 
#ifdef _MSC_VER
#pragma once
#endif

#ifndef OGDF_HASHING_H
#define OGDF_HASHING_H

#include <ogdf/basic/basic.h>
#include <math.h>
#include <limits.h>


namespace ogdf {

class HashingBase;

class HashElementBase {
    friend class HashingBase;

    HashElementBase *m_next; 
    size_t m_hashValue; 

public:
    HashElementBase(size_t hashValue) : m_hashValue(hashValue) { }

    HashElementBase *next() const { return m_next; }

    size_t hashValue() const { return m_hashValue; }

    OGDF_NEW_DELETE
};


class HashingBase {
protected:
    int m_tableSize;     
    int m_hashMask;      
    int m_minTableSize;  
    int m_tableSizeLow;  
    int m_tableSizeHigh; 
    int m_count;         
    HashElementBase **m_table; 

public:
    HashingBase(int minTableSize);

    HashingBase(const HashingBase &H);

    // destruction
    virtual ~HashingBase();

    void resize(int newTableSize);

    void insert(HashElementBase *pElement);

    void del(HashElementBase *pElement);

    void clear();

    HashingBase &operator=(const HashingBase &H);

    int size() const { return m_count; }

    int empty() const { return (m_count==0); }

    HashElementBase *firstListElement(size_t hashValue) const {
        return *(m_table + (hashValue & m_hashMask));
    }

    HashElementBase *firstElement(HashElementBase ***pList) const;

    HashElementBase *nextElement(HashElementBase ***pList,
        HashElementBase *pElement) const;

protected:
    void destroyAll();

    virtual void destroy(HashElementBase *pElement) = 0;

    virtual HashElementBase *copy(HashElementBase *pElement) const = 0;

private:
    void init(int tableSize);

    void copyAll(const HashingBase &H);
};


template<class K, class I, class H> class Hashing;
template<class K, class I, class H> class HashArray;


template<class K, class I>
class HashElement : public HashElementBase
{
    K m_key;  
    I m_info; 

public:
    HashElement(size_t hashValue, const K &key, const I &info) :
        HashElementBase(hashValue), m_key(key), m_info(info) { }

    HashElement<K,I> *next() const {
        return (HashElement<K,I> *)HashElementBase::next();
    }

    const K &key() const { return m_key; }

    const I &info() const { return m_info; }

    I &info() { return m_info; }

    OGDF_NEW_DELETE
};


template<class K, class I, class H> class HashConstIterator;

//--------------------------------------------------------------------
// Hash function classes have to define
// int hash(const E &key)
//
// "const E &" can be replaced by "E"
//--------------------------------------------------------------------

template<class K> class DefHashFunc {
    public: size_t hash(const K &key) const { return size_t(key); }
};

template<> class DefHashFunc<void *> {
    public: size_t hash(const void * &key) const { return size_t(key && 0xffffffff); }
};

template<> class DefHashFunc<double> {
    public: size_t hash(const double &key) const {
        int dummy;
        return size_t(SIZE_MAX*frexp(key,&dummy));
    }
};


template<class K, class I, class H = DefHashFunc<K> >
class Hashing : private HashingBase
{
    friend class HashConstIterator<K,I,H>;
    H m_hashFunc; 

public:
    typedef HashConstIterator<K,I,H> const_iterator;

    explicit Hashing(int minTableSize = 256, const H &hashFunc = H())
        : HashingBase(minTableSize), m_hashFunc(hashFunc) { }

    Hashing(const Hashing<K,I> &h) : HashingBase(h) { }

    // destruction
    ~Hashing() { HashingBase::destroyAll(); }

    int size() const { return HashingBase::size(); }

    bool empty() const { return (HashingBase::size() == 0); }

    bool member(const K &key) const { return (lookup(key) != 0); }

    HashConstIterator<K,I,H> begin() const;

    HashElement<K,I> *lookup(const K &key) const {
        HashElement<K,I> *pElement =
            (HashElement<K,I> *)firstListElement(m_hashFunc.hash(key));
        for (; pElement; pElement = pElement->next())
            if (pElement->key() == key) return pElement;

        return 0;
    }

    Hashing<K,I> &operator=(const Hashing<K,I> &hashing) {
        HashingBase::operator =(hashing);
        m_hashFunc = hashing.m_hashFunc;
        return *this;
    }

    HashElement<K,I> *insert(const K &key, const I &info) {
        HashElement<K,I> *pElement = lookup(key);

        if (pElement)
            pElement->info() = info;
        else
            HashingBase::insert(pElement =
                OGDF_NEW HashElement<K,I>(m_hashFunc.hash(key),key,info));

        return pElement;
    }

    HashElement<K,I> *insertByNeed(const K &key, const I &info) {
        HashElement<K,I> *pElement = lookup(key);

        if (!pElement)
            HashingBase::insert(pElement = OGDF_NEW HashElement<K,I>(m_hashFunc.hash(key),key,info));

        return pElement;
    }

    HashElement<K,I> *fastInsert(const K &key, const I &info) {
        HashElement<K,I> *pElement = OGDF_NEW HashElement<K,I>(m_hashFunc.hash(key),key,info);
        HashingBase::insert(pElement);
        return pElement;
    }

    void del(const K &key) {
        HashElement<K,I> *pElement = lookup(key);
        if (pElement) {
            HashingBase::del(pElement);
            delete pElement;
        }
    }

    void clear() { HashingBase::clear(); }

protected:
    HashElement<K,I> *firstElement(HashElement<K,I> ***pList) const {
        return (HashElement<K,I> *)(HashingBase::firstElement((HashElementBase ***)pList));
    }

    HashElement<K,I> *nextElement(HashElement<K,I> ***pList,
        HashElement<K,I> *pElement) const
    {
        return (HashElement<K,I> *)(HashingBase::nextElement(
            (HashElementBase ***)pList,pElement));
    }

private:
    virtual void destroy(HashElementBase *pElement) {
        delete (HashElement<K,I> *)(pElement);
    }

    virtual HashElementBase *copy(HashElementBase *pElement) const {
        HashElement<K,I> *pX = (HashElement<K,I> *)(pElement);
        return OGDF_NEW HashElement<K,I>(pX->hashValue(),pX->key(),pX->info());
    }
};


template<class K, class I, class H = DefHashFunc<K> >
class HashConstIterator {
    HashElement<K,I> *m_pElement; 
    HashElement<K,I> **m_pList; 
    const Hashing<K,I,H> *m_pHashing; 

public:
    HashConstIterator() : m_pElement(0), m_pList(0), m_pHashing(0) { }

    HashConstIterator(HashElement<K,I> *pElement, HashElement<K,I> **pList,
        const Hashing<K,I,H> *pHashing) : m_pElement(pElement), m_pList(pList),
        m_pHashing(pHashing) { }

    HashConstIterator(const HashConstIterator<K,I,H> &it) : m_pElement(it.m_pElement),
        m_pList(it.m_pList), m_pHashing(it.m_pHashing) { }

    HashConstIterator &operator=(const HashConstIterator<K,I,H> &it) {
        m_pElement = it.m_pElement;
        m_pList = it.m_pList;
        m_pHashing = it.m_pHashing;
        return *this;
    }

    bool valid() const { return (m_pElement != 0); }

    const K &key() const { return m_pElement->key(); }

    const I &info() const { return m_pElement->info(); }

    friend bool operator==(const HashConstIterator<K,I,H> &it1,
        const HashConstIterator<K,I,H> &it2) { return (it1.m_pElement == it2.m_pElement); }

    friend bool operator!=(const HashConstIterator<K,I,H> &it1,
        const HashConstIterator<K,I,H> &it2) { return (it1.m_pElement != it2.m_pElement); }

    HashConstIterator<K,I,H> &operator++() {
        m_pElement = m_pHashing->nextElement(&m_pList,m_pElement);
        return *this;
    }
};


template<class K, class I, class H>
inline HashConstIterator<K,I,H> Hashing<K,I,H>::begin() const
{
    HashElement<K,I> *pElement, **pList;
    pElement = firstElement(&pList);
    return HashConstIterator<K,I,H>(pElement,pList,this);
}


} // end namespace ogdf

#endif