mi32/mihash.h

Go to the documentation of this file.

#ifndef INC_MI32_MIHASH_H
#define INC_MI32_MIHASH_H

#ifndef  INC_MI32_MILIST_H
   #include <mi32/milist.h>
#endif


template <typename _ITEMTYPE> class MIHASH {
   private:
      #ifndef GENERATING_DOXYGEN_OUTPUT
      typedef MILIST<_ITEMTYPE> HASHBUCKET;
      #endif // GENERATING_DOXYGEN_OUTPUT

   public:

      class ITERATOR;               
      class CONST_ITERATOR;
      friend class CONST_ITERATOR;
      friend class ITERATOR;        

      class CONST_ITERATOR {
      public:
         CONST_ITERATOR (
            ) :
            m_Hash(0),
            m_BucketIndex(0)
            { }

         CONST_ITERATOR (
            const ITERATOR& rhs
            ) : 
            m_Hash(rhs.m_Hash),
            m_BucketIndex(rhs.m_BucketIndex),
            m_Item(rhs.m_Item)
            {}

         const _ITEMTYPE& operator* (
            ) const {
            return (*m_Item);
            }

         const _ITEMTYPE* operator-> (
            ) const {
            return (&**this);
            }

         CONST_ITERATOR& operator++ (
            ) {
            if (m_BucketIndex < m_Hash->m_NumBuckets) {
               ++m_Item;
               while (m_Item == m_Hash->m_BucketList[m_BucketIndex].End()) {
                  ++m_BucketIndex;
                  if (m_BucketIndex == m_Hash->m_NumBuckets) {
                     m_Item = m_Hash->m_BucketList[m_BucketIndex-1].End();
                     }
                  else {
                     m_Item = m_Hash->m_BucketList[m_BucketIndex].Begin();
                     }
                  }
               }
            return (*this);
            }


         bool operator== (          
            const CONST_ITERATOR& rhs
            ) const {
            return (m_Item == rhs.m_Item && m_BucketIndex == rhs.m_BucketIndex);
            }

         bool operator!= (          
            const CONST_ITERATOR& rhs
            ) const {
            return (!(*this == rhs));
            }

      protected:
         const MIHASH<_ITEMTYPE> *const m_Hash;
         UINT32 m_BucketIndex;
         typename HASHBUCKET::ITERATOR m_Item;
         
         CONST_ITERATOR (
            const MIHASH<_ITEMTYPE> *const hash
            ) :
            m_Hash(hash),
            m_BucketIndex(0),
            m_Item(m_Hash->m_BucketList[0].Begin())
            {
            if (m_Item == m_Hash->m_BucketList[0].End()) {
               operator++();
               }
            }

         CONST_ITERATOR (
            const MIHASH<_ITEMTYPE> *const hash,
            int
            ) :
            m_Hash(hash),
            m_BucketIndex(m_Hash->m_NumBuckets),
            m_Item(m_Hash->m_BucketList[0].Begin())
            {}

         CONST_ITERATOR (
            const MIHASH<_ITEMTYPE> *const hash,
            UINT32 BucketIndex,
            typename HASHBUCKET::ITERATOR Item
            ) :
            m_Hash(hash),
            m_BucketIndex(BucketIndex),
            m_Item(Item)
            { }

         friend class MIHASH<_ITEMTYPE>;
         };

      class ITERATOR : public CONST_ITERATOR {
         public:

            ITERATOR (
               ) :
               CONST_ITERATOR()
               {}

            _ITEMTYPE& operator* (
               ) const {
               return (*CONST_ITERATOR::m_Item);
               }

            _ITEMTYPE* operator-> (
               ) const {
               return (&**this);
               }

            ITERATOR& operator++ (
               ) {
               CONST_ITERATOR::operator++();
               return (*this);
               }


            bool operator== (          
               const ITERATOR& rhs
               ) const {
               return (CONST_ITERATOR::m_Item == rhs.m_Item && CONST_ITERATOR::m_BucketIndex == rhs.m_BucketIndex);
               }

            bool operator!= (          
               const ITERATOR& rhs
               ) const {
               return (!(*this == rhs));
               }
         private:
            #ifndef GENERATING_DOXYGEN_OUTPUT
            ITERATOR (
               const MIHASH<_ITEMTYPE> *const hash
               ):
               CONST_ITERATOR(hash)
               { }

            ITERATOR (
               const MIHASH<_ITEMTYPE> *const hash,
               int
               ):
               CONST_ITERATOR(hash,0)
               { }

            ITERATOR (
               const MIHASH<_ITEMTYPE> *const hash,
               UINT32 BucketIndex,
               typename HASHBUCKET::ITERATOR Item
               ) :
               CONST_ITERATOR(hash, BucketIndex, Item)
               { }

            friend class MIHASH<_ITEMTYPE>;
         #endif // GENERATING_DOXYGEN_OUTPUT
         };


      // CONSTRUCTORS / DESTRUCTOR
      
      explicit MIHASH (
         UINT32 NumBuckets = 32        
         ) :
         m_NumBuckets(NumBuckets),
         m_BucketList(new HASHBUCKET[NumBuckets])
         {}
         
      MIHASH (
         const MIHASH& rhs
         ) :
         m_NumBuckets(rhs.m_NumBuckets),
         m_BucketList(new HASHBUCKET[rhs.m_NumBuckets])
         {
         for (UINT32 i = 0;(i < m_NumBuckets);++i) {
            m_BucketList[i] = rhs.m_BucketList[i];
            }
         }

      ~MIHASH (
         ) {
         delete [] m_BucketList;
         }
         
      // METHODS
      
      void Add (
         const _ITEMTYPE& item
         ) {
         UINT32 HashNum = item.GetHashNumber() % m_NumBuckets;
         typename HASHBUCKET::CONST_ITERATOR it;
         for (it = m_BucketList[HashNum].Begin();(it != m_BucketList[HashNum].End());++it) {
            if (*it == item) break;
            }
         if (it == m_BucketList[HashNum].End()) m_BucketList[HashNum].PushBack(item);
         return;
         }
         
      CONST_ITERATOR Begin (
         ) const {
         return (CONST_ITERATOR(this));
         }

      ITERATOR Begin (
         ) {
         return (ITERATOR(this));
         }
         
      void Clear (
         ) {
         for (UINT32 i = 0;(i < m_NumBuckets);++i) {
            m_BucketList[i].Clear();
            }
         return;
         }     
         
      CONST_ITERATOR End (
         ) const {
         return (CONST_ITERATOR(this,0));
         }

      ITERATOR End (
         ) {
         return (ITERATOR(this,0));
         }

      template <typename _CMP> bool Exists (
         const _CMP& item
         ) const {
         return (Find(item) != End());
         }
         
      template <typename _CMP> ITERATOR Find (
         const _CMP& item
         ) {
         UINT32 HashNum = item.GetHashNumber() % m_NumBuckets;
         typename HASHBUCKET::ITERATOR it;
         for (it = m_BucketList[HashNum].Begin();(it != m_BucketList[HashNum].End());++it) {
            if (item == *it) break;    
            }
         ITERATOR retval = (it != m_BucketList[HashNum].End()) ? ITERATOR(this, HashNum, it) : End();
         return (retval);
         }
         
      template <typename _CMP> CONST_ITERATOR Find (
         const _CMP& item
         ) const {
         UINT32 HashNum = item.GetHashNumber() % m_NumBuckets;
         typename HASHBUCKET::ITERATOR it;
         for (it = m_BucketList[HashNum].Begin();(it != m_BucketList[HashNum].End());++it) {
            if (item == *it) break;    
            }
         CONST_ITERATOR retval = (it != m_BucketList[HashNum].End()) ? CONST_ITERATOR(this, HashNum, it) : End();
         return (retval);
         }
         
      void Remove (
         ITERATOR item
         ) {
         if (item != End()) m_BucketList[item.m_BucketIndex].Remove(item.m_Item);
         return;
         }
         
      void Resize (
         INT32 NumBuckets
         ) {
         Clear();
         delete [] m_BucketList;
         m_BucketList = new HASHBUCKET[NumBuckets];
         m_NumBuckets = NumBuckets;
         return;
         }

   private:
      #ifndef GENERATING_DOXYGEN_OUTPUT

      MIHASH& operator= (
         const MIHASH& rhs
         );

      UINT32 m_NumBuckets;
      HASHBUCKET *m_BucketList;
      #endif // GENERATING_DOXYGEN_OUTPUT
      
   };

#endif      // INC_MI32_MIHASH_H

---