Teuchos_Hashtable.hpp

Go to the documentation of this file.
00001 // @HEADER
00002 // ***********************************************************************
00003 // 
00004 //                    Teuchos: Common Tools Package
00005 //                 Copyright (2004) Sandia Corporation
00006 // 
00007 // Under terms of Contract DE-AC04-94AL85000, there is a non-exclusive
00008 // license for use of this work by or on behalf of the U.S. Government.
00009 // 
00010 // This library is free software; you can redistribute it and/or modify
00011 // it under the terms of the GNU Lesser General Public License as
00012 // published by the Free Software Foundation; either version 2.1 of the
00013 // License, or (at your option) any later version.
00014 //  
00015 // This library is distributed in the hope that it will be useful, but
00016 // WITHOUT ANY WARRANTY; without even the implied warranty of
00017 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00018 // Lesser General Public License for more details.
00019 //  
00020 // You should have received a copy of the GNU Lesser General Public
00021 // License along with this library; if not, write to the Free Software
00022 // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
00023 // USA
00024 // Questions? Contact Michael A. Heroux (maherou@sandia.gov) 
00025 // 
00026 // ***********************************************************************
00027 // @HEADER
00028 
00029 #ifndef TEUCHOS_HASHTABLE_H
00030 #define TEUCHOS_HASHTABLE_H
00031 
00036 #include "Teuchos_ConfigDefs.hpp"
00037 #include "Teuchos_Array.hpp"
00038 #include "Teuchos_HashUtils.hpp"
00039 
00040 namespace Teuchos
00041 {
00042   using std::string;
00043 
00047   template<class Key, class Value> class HashPair
00048     {
00049     public:
00051       inline HashPair() : key_(), value_() {;}
00053       inline HashPair(const Key& key, const Value& value)
00054         : key_(key), value_(value) {;}
00055 
00057       Key key_;
00059       Value value_;
00060     };
00061 
00067   template<class Key, class Value> class Hashtable
00068     {
00069     public:
00070 
00072       inline Hashtable(int capacity=101, double rehashDensity = 0.8);
00073 
00075       inline bool containsKey(const Key& key) const ;
00076 
00078       inline const Value& get(const Key& key) const ;
00079 
00081       inline void put(const Key& key, const Value& value);
00082 
00084       inline void remove(const Key& key);
00085 
00087       inline int size() const {return count_;}
00088 
00090       inline void arrayify(Array<Key>& keys, Array<Value>& values) const ;
00091 
00093       inline double avgDegeneracy() const {return avgDegeneracy_;}
00094 
00096       inline double density() const {return ((double)count_)/((double) capacity_);}
00097 
00099       inline void setRehashDensity(double rehashDensity);
00100 
00102       inline std::string toString() const ;
00103 
00104     private:
00105 
00106       inline void rehash();
00107       inline int nextPrime(int newCap) const ;
00108       inline void accumulateAvgFill(int n) const ;
00109 
00110 
00111       Array<Array<HashPair<Key, Value> > > data_;
00112       int count_;
00113       int capacity_;
00114       mutable Value mostRecentValue_;
00115       mutable Key mostRecentKey_;
00116 
00117       mutable size_t nHits_;
00118       mutable double avgDegeneracy_;
00119       double rehashDensity_;
00120     };
00121 
00122   template<class Key, class Value>
00123   std::string toString(const Hashtable<Key, Value>& h);
00124 
00128   template<class Key, class Value>
00129   std::ostream& operator<<(std::ostream& os, const Hashtable<Key, Value>& h);
00130 
00131   template<class Key, class Value> inline
00132     Hashtable<Key, Value>::Hashtable(int capacity, double rehashDensity)
00133     : data_(), count_(0), capacity_(HashUtils::nextPrime(capacity)),
00134     nHits_(0), avgDegeneracy_(0), rehashDensity_(rehashDensity)
00135     {
00136       data_.resize(capacity_);
00137     }
00138 
00139   template<class Key, class Value> inline
00140     bool Hashtable<Key, Value>::containsKey(const Key& key) const
00141     {
00142       const Array<HashPair<Key, Value> >& candidates
00143         = data_[hashCode(key) % capacity_];
00144       
00145       for (int i=0; i<candidates.length(); i++)
00146         {
00147           const HashPair<Key, Value>& c = candidates[i];
00148           if (c.key_ == key)
00149             {
00150               //          (Key&) mostRecentKey_ = key;
00151               //(Value&) mostRecentValue_ = c.value_;
00152               return true;
00153             }
00154         }
00155       return false;
00156     }
00157 
00158   template<class Key, class Value> inline
00159     void Hashtable<Key, Value>::put(const Key& key, const Value& value)
00160     {
00161       int index = hashCode(key) % capacity_;
00162       
00163       Array<HashPair<Key, Value> >& local = data_[index];
00164       
00165       // check for duplicate key
00166       for (int i=0; i<local.length(); i++)
00167         {
00168           if (local[i].key_ == key)
00169             {
00170               local[i].value_ = value;
00171               return;
00172             }
00173         }
00174       
00175       // no duplicate key, so increment element count by one.
00176       count_++;
00177       
00178       // check for need to resize.
00179       if ((double) count_ > rehashDensity_ * (double) capacity_)
00180         {
00181           capacity_ = HashUtils::nextPrime(capacity_+1);
00182           rehash();
00183           // recaluate index
00184           index = hashCode(key) % capacity_;
00185         }
00186       
00187       data_[index].append(HashPair<Key, Value>(key, value));
00188     }
00189 
00190 
00191 
00192   template<class Key, class Value> inline
00193     void Hashtable<Key, Value>::rehash()
00194     {
00195       Array<Array<HashPair<Key, Value> > > tmp(capacity_);
00196 
00197       for (int i=0; i<data_.length(); i++)
00198         {
00199           for (int j=0; j<data_[i].length(); j++)
00200             {
00201               int newIndex = hashCode(data_[i][j].key_) % capacity_;
00202               tmp[newIndex].append(data_[i][j]);
00203             }
00204         }
00205       
00206       data_ = tmp;
00207     }
00208 
00209 
00210   template<class Key, class Value> inline
00211     void Hashtable<Key, Value>::arrayify(Array<Key>& keys, Array<Value>& values) const
00212     {
00213       keys.reserve(size());
00214       values.reserve(size());
00215 
00216       for (int i=0; i<data_.length(); i++)
00217         {
00218           for (int j=0; j<data_[i].length(); j++)
00219             {
00220               keys.append(data_[i][j].key_);
00221               values.append(data_[i][j].value_);
00222             }
00223         }
00224     }
00225 
00226   template<class Key, class Value>  inline
00227   std::string Hashtable<Key, Value>::toString() const 
00228   {
00229     Array<Key> keys;
00230     Array<Value> values;
00231     arrayify(keys, values);
00232     
00233     std::string rtn = "[";
00234     for (int i=0; i<keys.length(); i++)
00235       {
00236         rtn += "{" + Teuchos::toString(keys[i]) + ", " + Teuchos::toString(values[i])
00237           + "}";
00238         if (i < keys.length()-1) rtn += ", ";
00239       }
00240     rtn += "]";
00241     
00242     return rtn;
00243   }
00244 
00245   template<class Key, class Value>  inline
00246     std::string toString(const Hashtable<Key, Value>& h)
00247     {
00248       Array<Key> keys;
00249       Array<Value> values;
00250       h.arrayify(keys, values);
00251 
00252       std::string rtn = "[";
00253       for (int i=0; i<keys.length(); i++)
00254         {
00255           rtn += "{" + Teuchos::toString(keys[i]) + ", " + Teuchos::toString(values[i])
00256             + "}";
00257           if (i < keys.length()-1) rtn += ", ";
00258         }
00259       rtn += "]";
00260 
00261       return rtn;
00262     }
00263 
00264   template<class Key, class Value> inline
00265     const Value& Hashtable<Key, Value>::get(const Key& key) const
00266     {
00267       TEST_FOR_EXCEPTION(!containsKey(key),
00268                          std::runtime_error,
00269                          "Hashtable<Key, Value>::get: key " 
00270                          << Teuchos::toString(key) 
00271                          << " not found in Hashtable"
00272                          << toString());
00273       
00274       const Array<HashPair<Key, Value> >& candidates
00275         = data_[hashCode(key) % capacity_];
00276 
00277       accumulateAvgFill(candidates.length());
00278       
00279       for (int i=0; i<candidates.length(); i++)
00280         {
00281           const HashPair<Key, Value>& c = candidates[i];
00282           if (c.key_ == key)
00283             {
00284               return c.value_;
00285             }
00286         }
00287       return mostRecentValue_;
00288     }
00289 
00290 
00291   template<class Key, class Value> inline
00292     void Hashtable<Key, Value>::remove(const Key& key)
00293     {
00294       TEST_FOR_EXCEPTION(!containsKey(key),
00295                          std::runtime_error,
00296                          "Hashtable<Key, Value>::remove: key " 
00297                          << Teuchos::toString(key) 
00298                          << " not found in Hashtable"
00299                          << toString());
00300 
00301       count_--;
00302       int h = hashCode(key) % capacity_;
00303       const Array<HashPair<Key, Value> >& candidates = data_[h];
00304 
00305       for (int i=0; i<candidates.length(); i++)
00306         {
00307           const HashPair<Key, Value>& c = candidates[i];
00308           if (c.key_ == key)
00309             {
00310               data_[h].remove(i);
00311               break;
00312             }
00313         }
00314     }
00315 
00316   template<class Key, class Value> inline
00317   void Hashtable<Key, Value>::accumulateAvgFill(int n) const
00318   {
00319     avgDegeneracy_ = ((double) nHits_)/(nHits_ + 1.0) * avgDegeneracy_ + ((double) n)/(nHits_ + 1.0);
00320     nHits_++;
00321     }
00322 
00323   template<class Key, class Value>  inline
00324     std::ostream& operator<<(std::ostream& os, const Hashtable<Key, Value>& h)
00325     {
00326       return os << toString(h);
00327     }
00328 
00329 
00330 }
00331 
00332 #endif // TEUCHOS_HASHTABLE_H
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines
Generated on Wed Apr 13 09:57:29 2011 for Teuchos Package Browser (Single Doxygen Collection) by  doxygen 1.6.3