Open
Graph Drawing
Framework

 v.2010.10
 

Hashing.h

Go to the documentation of this file.
00001 /*
00002  * $Revision: 2027 $
00003  * 
00004  * last checkin:
00005  *   $Author: gutwenger $ 
00006  *   $Date: 2010-09-01 11:55:17 +0200 (Wed, 01 Sep 2010) $ 
00007  ***************************************************************/
00008  
00056 #ifdef _MSC_VER
00057 #pragma once
00058 #endif
00059 
00060 #ifndef OGDF_HASHING_H
00061 #define OGDF_HASHING_H
00062 
00063 #include <ogdf/basic/basic.h>
00064 #include <math.h>
00065 #include <limits.h>
00066 
00067 
00068 namespace ogdf {
00069 
00070 class HashingBase;
00071 
00078 class HashElementBase {
00079     friend class HashingBase;
00080 
00081     HashElementBase *m_next; 
00082     size_t m_hashValue; 
00083 
00084 public:
00086     HashElementBase(size_t hashValue) : m_hashValue(hashValue) { }
00087 
00089     HashElementBase *next() const { return m_next; }
00090 
00092     size_t hashValue() const { return m_hashValue; }
00093 
00094     OGDF_NEW_DELETE
00095 };
00096 
00097 
00104 class HashingBase {
00105 protected:
00106     int m_tableSize;     
00107     int m_hashMask;      
00108     int m_minTableSize;  
00109     int m_tableSizeLow;  
00110     int m_tableSizeHigh; 
00111     int m_count;         
00112     HashElementBase **m_table; 
00113 
00114 public:
00116     HashingBase(int minTableSize);
00117 
00119     HashingBase(const HashingBase &H);
00120 
00121     // destruction
00122     virtual ~HashingBase();
00123 
00125     void resize(int newTableSize);
00126 
00128     void insert(HashElementBase *pElement);
00129 
00131     void del(HashElementBase *pElement);
00132 
00134     void clear();
00135 
00137     HashingBase &operator=(const HashingBase &H);
00138 
00140     int size() const { return m_count; }
00141 
00143     int empty() const { return (m_count==0); }
00144 
00150     HashElementBase *firstListElement(size_t hashValue) const {
00151         return *(m_table + (hashValue & m_hashMask));
00152     }
00153 
00162     HashElementBase *firstElement(HashElementBase ***pList) const;
00163 
00173     HashElementBase *nextElement(HashElementBase ***pList,
00174         HashElementBase *pElement) const;
00175 
00176 protected:
00178     void destroyAll();
00179 
00186     virtual void destroy(HashElementBase *pElement) = 0;
00187 
00189     virtual HashElementBase *copy(HashElementBase *pElement) const = 0;
00190 
00191 private:
00193     void init(int tableSize);
00194 
00196     void copyAll(const HashingBase &H);
00197 };
00198 
00199 
00200 template<class K, class I, class H> class Hashing;
00201 template<class K, class I, class H> class HashArray;
00202 
00203 
00211 template<class K, class I>
00212 class HashElement : public HashElementBase
00213 {
00214     K m_key;  
00215     I m_info; 
00216 
00217 public:
00219     HashElement(size_t hashValue, const K &key, const I &info) :
00220         HashElementBase(hashValue), m_key(key), m_info(info) { }
00221 
00223     HashElement<K,I> *next() const {
00224         return (HashElement<K,I> *)HashElementBase::next();
00225     }
00226 
00228     const K &key() const { return m_key; }
00229 
00231     const I &info() const { return m_info; }
00232 
00234     I &info() { return m_info; }
00235 
00236     OGDF_NEW_DELETE
00237 };
00238 
00239 
00240 template<class K, class I, class H> class HashConstIterator;
00241 
00242 //--------------------------------------------------------------------
00243 // Hash function classes have to define
00244 // int hash(const E &key)
00245 //
00246 // "const E &" can be replaced by "E"
00247 //--------------------------------------------------------------------
00248 
00257 template<class K> class DefHashFunc {
00259     public: size_t hash(const K &key) const { return size_t(key); }
00260 };
00261 
00263 template<> class DefHashFunc<void *> {
00264     public: size_t hash(const void * &key) const { return size_t(key && 0xffffffff); }
00265 };
00266 
00268 template<> class DefHashFunc<double> {
00269     public: size_t hash(const double &key) const {
00270         int dummy;
00271         return size_t(SIZE_MAX*frexp(key,&dummy));
00272     }
00273 };
00274 
00275 
00289 template<class K, class I, class H = DefHashFunc<K> >
00290 class Hashing : private HashingBase
00291 {
00292     friend class HashConstIterator<K,I,H>;
00293     H m_hashFunc; 
00294 
00295 public:
00297     typedef HashConstIterator<K,I,H> const_iterator;
00298 
00300     explicit Hashing(int minTableSize = 256, const H &hashFunc = H())
00301         : HashingBase(minTableSize), m_hashFunc(hashFunc) { }
00302 
00304     Hashing(const Hashing<K,I> &h) : HashingBase(h) { }
00305 
00306     // destruction
00307     ~Hashing() { HashingBase::destroyAll(); }
00308 
00310     int size() const { return HashingBase::size(); }
00311 
00313     bool empty() const { return (HashingBase::size() == 0); }
00314 
00316     bool member(const K &key) const { return (lookup(key) != 0); }
00317 
00319     HashConstIterator<K,I,H> begin() const;
00320 
00322     HashElement<K,I> *lookup(const K &key) const {
00323         HashElement<K,I> *pElement =
00324             (HashElement<K,I> *)firstListElement(m_hashFunc.hash(key));
00325         for (; pElement; pElement = pElement->next())
00326             if (pElement->key() == key) return pElement;
00327 
00328         return 0;
00329     }
00330 
00332     Hashing<K,I> &operator=(const Hashing<K,I> &hashing) {
00333         HashingBase::operator =(hashing);
00334         m_hashFunc = hashing.m_hashFunc;
00335         return *this;
00336     }
00337 
00345     HashElement<K,I> *insert(const K &key, const I &info) {
00346         HashElement<K,I> *pElement = lookup(key);
00347 
00348         if (pElement)
00349             pElement->info() = info;
00350         else
00351             HashingBase::insert(pElement =
00352                 OGDF_NEW HashElement<K,I>(m_hashFunc.hash(key),key,info));
00353 
00354         return pElement;
00355     }
00356 
00364     HashElement<K,I> *insertByNeed(const K &key, const I &info) {
00365         HashElement<K,I> *pElement = lookup(key);
00366 
00367         if (!pElement)
00368             HashingBase::insert(pElement = OGDF_NEW HashElement<K,I>(m_hashFunc.hash(key),key,info));
00369 
00370         return pElement;
00371     }
00372 
00379     HashElement<K,I> *fastInsert(const K &key, const I &info) {
00380         HashElement<K,I> *pElement = OGDF_NEW HashElement<K,I>(m_hashFunc.hash(key),key,info);
00381         HashingBase::insert(pElement);
00382         return pElement;
00383     }
00384 
00386     void del(const K &key) {
00387         HashElement<K,I> *pElement = lookup(key);
00388         if (pElement) {
00389             HashingBase::del(pElement);
00390             delete pElement;
00391         }
00392     }
00393 
00395     void clear() { HashingBase::clear(); }
00396 
00397 protected:
00406     HashElement<K,I> *firstElement(HashElement<K,I> ***pList) const {
00407         return (HashElement<K,I> *)(HashingBase::firstElement((HashElementBase ***)pList));
00408     }
00409 
00419     HashElement<K,I> *nextElement(HashElement<K,I> ***pList,
00420         HashElement<K,I> *pElement) const
00421     {
00422         return (HashElement<K,I> *)(HashingBase::nextElement(
00423             (HashElementBase ***)pList,pElement));
00424     }
00425 
00426 private:
00428     virtual void destroy(HashElementBase *pElement) {
00429         delete (HashElement<K,I> *)(pElement);
00430     }
00431 
00433     virtual HashElementBase *copy(HashElementBase *pElement) const {
00434         HashElement<K,I> *pX = (HashElement<K,I> *)(pElement);
00435         return OGDF_NEW HashElement<K,I>(pX->hashValue(),pX->key(),pX->info());
00436     }
00437 };
00438 
00439 
00463 template<class K, class I, class H = DefHashFunc<K> >
00464 class HashConstIterator {
00465     HashElement<K,I> *m_pElement; 
00466     HashElement<K,I> **m_pList; 
00467     const Hashing<K,I,H> *m_pHashing; 
00468 
00469 public:
00471     HashConstIterator() : m_pElement(0), m_pList(0), m_pHashing(0) { }
00472 
00474     HashConstIterator(HashElement<K,I> *pElement, HashElement<K,I> **pList,
00475         const Hashing<K,I,H> *pHashing) : m_pElement(pElement), m_pList(pList),
00476         m_pHashing(pHashing) { }
00477 
00479     HashConstIterator(const HashConstIterator<K,I,H> &it) : m_pElement(it.m_pElement),
00480         m_pList(it.m_pList), m_pHashing(it.m_pHashing) { }
00481 
00483     HashConstIterator &operator=(const HashConstIterator<K,I,H> &it) {
00484         m_pElement = it.m_pElement;
00485         m_pList = it.m_pList;
00486         m_pHashing = it.m_pHashing;
00487         return *this;
00488     }
00489 
00491     bool valid() const { return (m_pElement != 0); }
00492 
00494     const K &key() const { return m_pElement->key(); }
00495 
00497     const I &info() const { return m_pElement->info(); }
00498 
00500     friend bool operator==(const HashConstIterator<K,I,H> &it1,
00501         const HashConstIterator<K,I,H> &it2) { return (it1.m_pElement == it2.m_pElement); }
00502 
00504     friend bool operator!=(const HashConstIterator<K,I,H> &it1,
00505         const HashConstIterator<K,I,H> &it2) { return (it1.m_pElement != it2.m_pElement); }
00506 
00508     HashConstIterator<K,I,H> &operator++() {
00509         m_pElement = m_pHashing->nextElement(&m_pList,m_pElement);
00510         return *this;
00511     }
00512 };
00513 
00514 
00515 template<class K, class I, class H>
00516 inline HashConstIterator<K,I,H> Hashing<K,I,H>::begin() const
00517 {
00518     HashElement<K,I> *pElement, **pList;
00519     pElement = firstElement(&pList);
00520     return HashConstIterator<K,I,H>(pElement,pList,this);
00521 }
00522 
00523 
00524 } // end namespace ogdf
00525 
00526 #endif