Standard Portable Library: spl/collection/Hashtable.h Source File

00001 /*
00002  *   This file is part of the Standard Portable Library (SPL).
00003  *
00004  *   SPL is free software: you can redistribute it and/or modify
00005  *   it under the terms of the GNU General Public License as published by
00006  *   the Free Software Foundation, either version 3 of the License, or
00007  *   (at your option) any later version.
00008  *
00009  *   SPL is distributed in the hope that it will be useful,
00010  *   but WITHOUT ANY WARRANTY; without even the implied warranty of
00011  *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00012  *   GNU General Public License for more details.
00013  *
00014  *   You should have received a copy of the GNU General Public License
00015  *   along with SPL.  If not, see <http://www.gnu.org/licenses/>.
00016  */
00017 #ifndef _thashtable_h
00018 #define _thashtable_h
00019 
00020 #include <spl/types.h>
00021 #include <spl/Debug.h>
00022 
00023 #ifdef _WINDOWS
00024 #include <spl/configwin32.h>
00025 #else
00026 #include <spl/autoconf/config.h>
00027 #endif
00028 
00029 #include <spl/Compare.h>
00030 #include <spl/Exception.h>
00031 #include <spl/collection/IEnumerable.h>
00032 #include <spl/IIterator.h>
00033 #include <spl/collection/List.h>
00034 #include <spl/math/Math.h>
00035 #include <spl/Memory.h>
00036 #include <spl/RefCountPtr.h>
00037 #include <spl/String.h>
00038 #include <spl/collection/Vector.h>
00039 
00045 /* For resizing the hashtable */
00046 extern const int __hashtableSizes[];
00047 
00052 template<typename K, typename T>
00053 class Hashtable : public IEnumerable<T>
00054 {
00055 private:
00056         class _Kthashitem : public IMemoryValidate
00057         {
00058         public:
00059                 K key;
00060                 T data;
00061 
00062                 _Kthashitem() : key(), data() {}
00063                 _Kthashitem(const _Kthashitem& item) : key(item.key), data(item.data) {}
00064                 ~_Kthashitem() {}
00065 
00066         #if defined(DEBUG)
00067                 virtual void CheckMem() const
00068                 {
00069                         ValidateType( key );
00070                         ValidateType( data );
00071                 }
00072                 virtual void ValidateMem() const
00073                 {
00074                         ValidateType( key );
00075                         ValidateType( data );
00076                 }
00077         #endif
00078         };
00079         
00080         void Resize()
00081         {
00082                 if (__hashtableSizes[m_tablesize+1] == -1)
00083                 {
00084                         return;
00085                 }
00086                 m_tablesize++;
00087                 Vector<List<_Kthashitem *> *> vlold(m_valueLists);
00088                 m_valueLists.Clear();
00089                 m_valueLists = Vector<List<_Kthashitem *> *>(TableSize());
00090                 _Clear(m_valueLists);
00091                 m_count = 0;
00092                 
00093                 int x;
00094                 int count = vlold.Count();
00095                 for ( x = 0; x < count; x++ )
00096                 {
00097                         List<_Kthashitem *> *list = vlold.ElementAt(x);
00098                         if ( list != NULL )
00099                         {
00100                                 typename List<_Kthashitem *>::Iterator iter = list->Begin();
00101                                 while ( iter.Next() )
00102                                 {
00103                                         this->Set(iter.Current()->key, iter.Current()->data);
00104                                 }
00105                         }
00106                 }
00107                 _Clear(vlold);
00108         }
00109 
00110         inline void CheckForResize()
00111         {
00112                 if ((double)m_count / (double)TableSize() > 0.749)
00113                 {
00114                         Resize();
00115                 }
00116         }
00117                 
00118 protected:
00119         Vector<List<_Kthashitem *> *> m_valueLists;
00120         int m_tablesize;
00121         int m_count;
00122         
00123 public:
00124         class Iterator : public IIterator<T>
00125         {
00126         private:
00127                 const Vector<List<_Kthashitem *> *> *m_valueLists;
00128                 typename Vector<List<_Kthashitem *> *>::Iterator m_valueListsPos;
00129                 typename List<_Kthashitem *>::Iterator m_listPos;
00130 
00131         public:
00132                 Iterator(const Vector<List<_Kthashitem *> *> *valueLists)
00133                 : m_valueLists(valueLists), m_valueListsPos(valueLists->Begin()), m_listPos()
00134                 {
00135                 }
00136 
00137                 Iterator(const Iterator& hki)
00138                 : m_valueLists(hki.m_valueLists), m_valueListsPos(hki.m_valueListsPos), m_listPos(hki.m_listPos)
00139                 {
00140                 }
00141 
00142                 virtual bool Next( )
00143                 {
00144                         if (m_listPos.Next())
00145                         {
00146                                 return true;
00147                         }
00148                         while (m_valueListsPos.Next())
00149                         {
00150                                 if (NULL != m_valueListsPos.Current())
00151                                 {
00152                                         m_listPos = m_valueListsPos.Current()->Begin();
00153                                         if (m_listPos.Next())
00154                                         {
00155                                                 return true;
00156                                         }
00157                                 }
00158                         }
00159 
00160                         return false;
00161                 }
00162 
00163                 virtual bool Prev( )
00164                 {
00165                         throw new NotImplementedException();
00166                 }
00167 
00168                 virtual T Current()
00169                 {
00170                         return m_listPos.Current()->data;
00171                 }
00172 
00173                 virtual T& CurrentRef()
00174                 {
00175                         return m_listPos.Current()->data;
00176                 }
00177 
00178                 virtual K CurrentKey()
00179                 {
00180                         return m_listPos.Current()->key;
00181                 }
00182 
00183                 virtual K& CurrentKeyRef()
00184                 {
00185                         return m_listPos.Current()->key;
00186                 }
00187         };
00188 
00189 protected:
00190         inline List<_Kthashitem *> *FindList( const K& key ) const
00191         {
00192                 int hash = Math::Hash(key) % TableSize();
00193                 ASSERT( hash > -1 );
00194                 ASSERT( m_valueLists.Count() >  hash );
00195                 return m_valueLists.ElementAt( hash );
00196         }
00197         
00198         inline List<_Kthashitem *> *AddList( const K& key )
00199         {
00200                 List<_Kthashitem *> *list = new List<_Kthashitem *>();
00201                 m_valueLists.SetElementAt( list, Math::Hash(key) % TableSize() );
00202                 ASSERT( m_valueLists.Count() > Math::Hash(key) % TableSize() );
00203                 return list;
00204         }
00205         
00206         inline bool FindItem(typename List<_Kthashitem *>::Iterator& list, const K& key) const
00207         {
00208                 while ( list.Next() )
00209                 {
00210                         if ( Compare::Equals(list.Current()->key, key) )
00211                         {
00212                                 return true;
00213                         }
00214                 }
00215                 return false;
00216         }
00217         
00218         virtual RefCountPtr<IIterator<T> > IteratorPtr()
00219         {
00220                 return RefCountPtr<IIterator<T> >(new Iterator(&m_valueLists));
00221         }
00222 
00223         inline int TableSize() const
00224         {
00225                 return __hashtableSizes[m_tablesize];
00226         }
00227         
00228         void _Clear(Vector<List<_Kthashitem *> *>& valueLists)
00229         {
00230                 int x;
00231                 int count = valueLists.Count();
00232                 for ( x = 0; x < count; x++ )
00233                 {
00234                         List<_Kthashitem *> *list = valueLists.ElementAt(x);
00235                         if ( list != NULL )
00236                         {
00237                                 typename List<_Kthashitem *>::Iterator iter = list->Begin();
00238                                 while ( iter.Next() )
00239                                 {
00240                                         delete iter.Current();
00241                                 }
00242                                 delete list;
00243                         }
00244                 }
00245                 valueLists.Clear();
00246 
00247                 for ( x = 0; x < TableSize(); x++ )
00248                 {
00249                         valueLists.Add( NULL );
00250                 }
00251         }
00252 
00253 public:
00254         Hashtable(  )
00255         : m_count(0), m_tablesize(0), m_valueLists(__hashtableSizes[0])
00256         {
00257                 ASSERT(Math::IsPrime(TableSize()));
00258                 Clear();
00259         }
00260 
00261         Hashtable( const Hashtable &ht )
00262         : m_count(ht.m_count), m_tablesize(ht.m_tablesize), m_valueLists(__hashtableSizes[ht.m_tablesize])
00263         {
00264                 Clear();
00265                 
00266                 int count = ht.m_valueLists.Count();
00267                 for ( int x = 0; x < count; x++ )
00268                 {
00269                         List<_Kthashitem *> *list = ht.m_valueLists.ElementAt(x);
00270                         if ( list != NULL )
00271                         {
00272                                 int lcount = list->Count();
00273                                 for ( int y = 0; y < lcount; y++ )
00274                                 {
00275                                         _Kthashitem *item = list->ElementAt(y);
00276                                         ASSERT_MEM( item, sizeof(_Kthashitem) );
00277                                         Set( item->key, item->data );
00278                                 }
00279                         }
00280                 }
00281         }
00282 
00283         virtual ~Hashtable()
00284         {
00285                 int x;
00286                 int count = m_valueLists.Count();
00287                 for ( x = 0; x < count; x++ )
00288                 {
00289                         List<_Kthashitem *> *list = m_valueLists.ElementAt(x);
00290                         if ( list != NULL )
00291                         {
00292                                 typename List<_Kthashitem *>::Iterator iter = list->Begin();
00293                                 while ( iter.Next() )
00294                                 {
00295                                         delete iter.Current();
00296                                 }
00297                                 delete list;
00298                         }
00299                 }
00300         }
00301 
00302         Hashtable<K, T>& operator =(const Hashtable<K, T>& ht)
00303         {
00304                 int x;
00305 
00306                 Clear();
00307 
00308                 m_count = ht.m_count;
00309 
00310                 if ( m_tablesize != ht.m_tablesize )
00311                 {
00312                         m_tablesize = ht.m_tablesize;
00313                         m_valueLists.Clear();
00314 
00315                         for ( x = 0; x < TableSize(); x++ )
00316                         {
00317                                 m_valueLists.Add( NULL );
00318                         }
00319                 }
00320 
00321                 for ( x = 0; x < TableSize(); x++ )
00322                 {
00323                         List<_Kthashitem *> *list = ht.m_valueLists.ElementAt(x);
00324                         if ( list != NULL )
00325                         {
00326                                 int lcount = list->Count();
00327                                 for ( int y = 0; y < lcount; y++ )
00328                                 {
00329                                         _Kthashitem *item = list->ElementAt(y);
00330                                         ASSERT_MEM( item, sizeof(_Kthashitem) );
00331                                         Set( item->key, item->data );
00332                                 }
00333                         }
00334                 }
00335                 return *this;
00336         }
00337 
00338         bool ContainsKey( const K& key ) const
00339         {
00340                 ASSERT( m_valueLists.Count() > Math::Hash(key) % TableSize() );
00341                 List<_Kthashitem *> *list = FindList( key );
00342                 if ( NULL == list )
00343                 {
00344                         return false;
00345                 }
00346                 typename List<_Kthashitem *>::Iterator iter = list->Begin();
00347                 return FindItem( iter, key );
00348         }
00349         
00350         T Get( const K& key ) const
00351         {
00352                 ASSERT( m_valueLists.Count() > Math::Hash(key) % TableSize() );
00353                 List<_Kthashitem *> *list = FindList( key );
00354                 if ( NULL == list )
00355                 {
00356                         return T();
00357                 }
00358                 typename List<_Kthashitem *>::Iterator iter = list->Begin();
00359                 if ( ! FindItem( iter, key ) )
00360                 {
00361                         return T();
00362                 }
00363                 return iter.Current()->data;
00364         }
00365         
00366         T& GetRef( const K& key ) const
00367         {
00368                 ASSERT( m_valueLists.Count() > Math::Hash(key) % TableSize() );
00369                 List<_Kthashitem *> *list = FindList( key );
00370                 if ( NULL == list )
00371                 {
00372                         throw new IndexOutOfBoundsException("key not found");
00373                 }
00374                 typename List<_Kthashitem *>::Iterator iter = list->Begin();
00375                 if ( ! FindItem( iter, key ) )
00376                 {
00377                         throw new IndexOutOfBoundsException("key not found");
00378                 }
00379                 return iter.Current()->data;
00380         }
00381         
00382         inline T& operator[] (const K& key) const
00383         {
00384                 return GetRef(key);
00385         }
00386 
00387         void Set( K key, T val )
00388         {
00389                 List<_Kthashitem *> *list = FindList( key );
00390                 if ( NULL == list )
00391                 {
00392                         list = AddList( key );
00393                         ASSERT( m_valueLists.Count() > Math::Hash(key) % TableSize() );
00394                         m_count++;
00395                 }
00396                 else
00397                 {
00398                         typename List<_Kthashitem *>::Iterator iter = list->Begin();
00399                         if ( FindItem( iter, key ) )
00400                         {
00401                                 _Kthashitem *item = iter.Current();
00402                                 list->RemoveCurrent(iter);
00403                                 delete item;
00404                         }
00405                         else
00406                         {
00407                                 m_count++;
00408                         }
00409                 }
00410                 _Kthashitem *item = new _Kthashitem();
00411                 if ( NULL == item )
00412                 {
00413                         throw OutOfMemoryException();
00414                 }
00415                 item->key = key;
00416                 item->data = val;
00417                 list->Add( item );
00418                 
00419                 ASSERT( m_valueLists.Count() > Math::Hash(key) % TableSize() );
00420                 
00421                 CheckForResize();
00422         }
00423 
00424         void Remove( const K& key )
00425         {
00426                 List<_Kthashitem *> *list = FindList( key );
00427                 if ( NULL == list )
00428                 {
00429                         return;
00430                 }
00431                 typename List<_Kthashitem *>::Iterator iter = list->Begin();
00432                 if ( ! FindItem( iter, key ) )
00433                 {
00434                         return;
00435                 }
00436                 _Kthashitem *item = iter.Current();
00437                 list->RemoveCurrent(iter);
00438                 delete item;
00439                 m_count--;
00440                 
00441                 ASSERT( m_valueLists.Count() > Math::Hash(key) % TableSize() );
00442         }
00443 
00444         RefCountPtr<Vector<K> > Keys() const
00445         {
00446                 RefCountPtr<Vector<K> > vect(new Vector<K>());
00447                 int count = m_valueLists.Count();
00448                 for ( int x = 0; x < count; x++ )
00449                 {
00450                         List<_Kthashitem *> *list = m_valueLists.ElementAt(x);
00451                         if ( NULL == list )
00452                         {
00453                                 continue;
00454                         }
00455                         ASSERT_MEM(list, sizeof(List<_Kthashitem *>));
00456                         list->ValidateMem();
00457 
00458                         typename List<_Kthashitem *>::Iterator iter = list->Iterator();
00459                         while(iter.Next())
00460                         {
00461                                 vect->Add(iter.Current()->key);
00462                         }
00463                 }
00464                 ASSERT(m_count == vect->Count());
00465                 return vect;
00466         }
00467         
00468         inline Iterator Begin() const
00469         {
00470                 return Iterator(&m_valueLists);
00471         }
00472 
00473         inline void ForEachKey(IDelegateOneParameter<K&>& func)
00474         {
00475                 Iterator iter = Begin();
00476                 while(iter.Next())
00477                 {
00478                         func.Call(iter->Current(iter.CurrentRef()));
00479                 }
00480         }
00481 
00482         RefCountPtr<Vector<T> > Values() const
00483         {
00484                 RefCountPtr<Vector<T> > vect(new Vector<T>());
00485                 int count = m_valueLists.Count();
00486                 for ( int x = 0; x < count; x++ )
00487                 {
00488                         List<_Kthashitem *> *list = m_valueLists.ElementAt(x);
00489                         if ( NULL == list )
00490                         {
00491                                 continue;
00492                         }
00493                         ASSERT_MEM(list, sizeof(List<_Kthashitem *>));
00494                         list->ValidateMem();
00495 
00496                         typename List<_Kthashitem *>::Iterator iter = list->Begin();
00497                         while(iter.Next())
00498                         {
00499                                 vect->Add(iter.Current()->data);
00500                         }
00501                 }
00502                 ASSERT(m_count == vect->Count());
00503                 return vect;
00504         }
00505 
00506         inline void Clear()
00507         {
00508                 _Clear(m_valueLists);
00509                 m_count = 0;
00510         }
00511 
00512         inline int Count() const
00513         {
00514                 return m_count;
00515         }
00516 
00517 #ifdef DEBUG
00518         virtual void ValidateMem() const
00519         {
00520                 m_valueLists.ValidateMem();
00521                 int count = m_valueLists.Count();
00522                 for ( int x = 0; x < count; x++ )
00523                 {
00524                         List<_Kthashitem *> *list = m_valueLists.ElementAt(x);
00525                         if ( list != NULL )
00526                         {
00527                                 ASSERT_MEM( list, sizeof(List<_Kthashitem *>) );
00528                                 list->ValidateMem();
00529                         }
00530                 }
00531         }
00532 
00533         virtual void CheckMem() const
00534         {
00535                 m_valueLists.CheckMem();
00536                 int count = m_valueLists.Count();
00537                 for ( int x = 0; x < count; x++ )
00538                 {
00539                         List<_Kthashitem *> *list = m_valueLists.ElementAt(x);
00540                         if ( list != NULL )
00541                         {
00542                                 DEBUG_NOTE_MEM( list );
00543                                 list->CheckMem();
00544                         }
00545                 }
00546         }
00547 #else
00548         inline void ValidateMem() const {}
00549         inline void CheckMem() const {}
00550 #endif
00551 };
00552 
00553 REGISTER_TYPEOF2( 182, Hashtable<String,String> );
00554 REGISTER_TYPEOF2( 183, Hashtable<String,StringPtr> );
00555 REGISTER_TYPEOF2( 184, Hashtable<String,Vector<String> > );
00556 REGISTER_TYPEOF2( 185, Hashtable<String,Vector<StringPtr> > );
00557 REGISTER_TYPEOF2( 186, Hashtable<String,List<String> > );
00558 REGISTER_TYPEOF2( 187, Hashtable<String,List<StringPtr> > );
00559 REGISTER_TYPEOF2( 188, Hashtable<String,int> );
00560 
00563 #endif