hash.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/lib/abacus/abacusroot.h>
 
namespace abacus {
 
class AbacusGlobal;
 
template<class KeyType,class ItemType> class AbaHash;
 
template <class KeyType, class ItemType>
class  AbaHashItem;
template <class KeyType, class ItemType>
class  AbaHash;
 
template <class KeyType, class ItemType>
std::ostream &operator<< (std::ostream &out, const AbaHashItem<KeyType, ItemType> &rhs);
 
template <class KeyType, class ItemType>
std::ostream &operator<< (std::ostream &out, const AbaHash<KeyType, ItemType> &hash);
 
 
/*
 * \sa AbaHash
 */
template <class KeyType, class ItemType>
class  AbaHashItem :  public AbacusRoot  {
    friend class AbaHash<KeyType, ItemType>;
 
public:
 
 
    AbaHashItem(const KeyType &key, const ItemType &item);
 
 
 
    friend std::ostream &operator<< <> (std::ostream &,
        const AbaHashItem<KeyType, ItemType> &);
 
    AbaHashItem<KeyType, ItemType> *next();
 
    const AbaHashItem<KeyType, ItemType> *next() const;
 
private:
    KeyType                      key_;
    ItemType                     item_;
    AbaHashItem<KeyType, ItemType> *next_;
 
    OGDF_NEW_DELETE
};
 
 
 
template <class KeyType, class ItemType>
class  AbaHash :  public AbacusRoot  {
public:
 
 
    explicit AbaHash(int size);
 
 
    ~AbaHash();
 
 
    friend std::ostream &operator<< <> (std::ostream &out,
        const AbaHash<KeyType, ItemType> &hash);
 
 
    void insert(const KeyType &newKey, const ItemType &newItem);
 
 
    void overWrite(const KeyType &newKey, const ItemType &newItem);
 
 
    const ItemType *find(const KeyType &key) const;
 
 
    ItemType *find(const KeyType &key);
 
 
    bool find(const KeyType &key, const ItemType &item) const;
 
 
 
    ItemType *initializeIteration(const KeyType &key);
 
 
    const ItemType *initializeIteration(const KeyType &key) const;
 
 
    ItemType *next(const KeyType &key);
 
 
    const ItemType *next(const KeyType &key) const;
 
 
    int remove(const KeyType &key);
 
 
    int remove(const KeyType &key, const ItemType &item);
 
    int size() const;
 
    int nCollisions() const;
 
 
    void resize(int newSize);
 
    private:
 
 
    int hf(int key) const;
 
    int hf(unsigned key) const;
 
 
    int hf(const string &str) const;
 
 
 
    AbaHashItem<KeyType, ItemType> **table_;
 
    int size_;
 
    int nCollisions_;
 
 
    mutable AbaHashItem<KeyType, ItemType> *iter_;
 
    AbaHash(const AbaHash &rhs);
    AbaHash &operator=(const AbaHash &rhs);
};
 
}
 
#include <ogdf/lib/abacus/hash.inc>