Teuchos Package Browser (Single Doxygen Collection) Version of the Day
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 // Redistribution and use in source and binary forms, with or without
00011 // modification, are permitted provided that the following conditions are
00012 // met:
00013 //
00014 // 1. Redistributions of source code must retain the above copyright
00015 // notice, this list of conditions and the following disclaimer.
00016 //
00017 // 2. Redistributions in binary form must reproduce the above copyright
00018 // notice, this list of conditions and the following disclaimer in the
00019 // documentation and/or other materials provided with the distribution.
00020 //
00021 // 3. Neither the name of the Corporation nor the names of the
00022 // contributors may be used to endorse or promote products derived from
00023 // this software without specific prior written permission.
00024 //
00025 // THIS SOFTWARE IS PROVIDED BY SANDIA CORPORATION "AS IS" AND ANY
00026 // EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
00027 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
00028 // PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL SANDIA CORPORATION OR THE
00029 // CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
00030 // EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
00031 // PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
00032 // PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
00033 // LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
00034 // NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
00035 // SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00036 //
00037 // Questions? Contact Michael A. Heroux (maherou@sandia.gov)
00038 //
00039 // ***********************************************************************
00040 // @HEADER
00041 
00042 #ifndef TEUCHOS_HASHTABLE_H
00043 #define TEUCHOS_HASHTABLE_H
00044 
00049 #include "Teuchos_ConfigDefs.hpp"
00050 #include "Teuchos_Array.hpp"
00051 #include "Teuchos_HashUtils.hpp"
00052 
00053 namespace Teuchos
00054 {
00055   using std::string;
00056 
00060   template<class Key, class Value> class HashPair
00061     {
00062     public:
00064       inline HashPair() : key_(), value_() {;}
00066       inline HashPair(const Key& key, const Value& value)
00067         : key_(key), value_(value) {;}
00068 
00070       Key key_;
00072       Value value_;
00073     };
00074 
00080   template<class Key, class Value> class Hashtable
00081     {
00082     public:
00083 
00085       inline Hashtable(int capacity=101, double rehashDensity = 0.8);
00086 
00088       inline bool containsKey(const Key& key) const ;
00089 
00091       inline const Value& get(const Key& key) const ;
00092 
00094       inline void put(const Key& key, const Value& value);
00095 
00097       inline void remove(const Key& key);
00098 
00100       inline int size() const {return count_;}
00101 
00103       inline void arrayify(Array<Key>& keys, Array<Value>& values) const ;
00104 
00106       inline double avgDegeneracy() const {return avgDegeneracy_;}
00107 
00109       inline double density() const {return ((double)count_)/((double) capacity_);}
00110 
00112       inline void setRehashDensity(double rehashDensity);
00113 
00115       inline std::string toString() const ;
00116 
00117     private:
00118 
00119       inline void rehash();
00120       inline int nextPrime(int newCap) const ;
00121       inline void accumulateAvgFill(int n) const ;
00122 
00123 
00124       Array<Array<HashPair<Key, Value> > > data_;
00125       int count_;
00126       int capacity_;
00127       mutable Value mostRecentValue_;
00128       mutable Key mostRecentKey_;
00129 
00130       mutable size_t nHits_;
00131       mutable double avgDegeneracy_;
00132       double rehashDensity_;
00133     };
00134 
00135   template<class Key, class Value>
00136   std::string toString(const Hashtable<Key, Value>& h);
00137 
00141   template<class Key, class Value>
00142   std::ostream& operator<<(std::ostream& os, const Hashtable<Key, Value>& h);
00143 
00144   template<class Key, class Value> inline
00145     Hashtable<Key, Value>::Hashtable(int capacity, double rehashDensity)
00146     : data_(), count_(0), capacity_(HashUtils::nextPrime(capacity)),
00147     nHits_(0), avgDegeneracy_(0), rehashDensity_(rehashDensity)
00148     {
00149       data_.resize(capacity_);
00150     }
00151 
00152   template<class Key, class Value> inline
00153     bool Hashtable<Key, Value>::containsKey(const Key& key) const
00154     {
00155       const Array<HashPair<Key, Value> >& candidates
00156         = data_[hashCode(key) % capacity_];
00157       
00158       for (int i=0; i<candidates.length(); i++)
00159         {
00160           const HashPair<Key, Value>& c = candidates[i];
00161           if (c.key_ == key)
00162             {
00163               //          (Key&) mostRecentKey_ = key;
00164               //(Value&) mostRecentValue_ = c.value_;
00165               return true;
00166             }
00167         }
00168       return false;
00169     }
00170 
00171   template<class Key, class Value> inline
00172     void Hashtable<Key, Value>::put(const Key& key, const Value& value)
00173     {
00174       int index = hashCode(key) % capacity_;
00175       
00176       Array<HashPair<Key, Value> >& local = data_[index];
00177       
00178       // check for duplicate key
00179       for (int i=0; i<local.length(); i++)
00180         {
00181           if (local[i].key_ == key)
00182             {
00183               local[i].value_ = value;
00184               return;
00185             }
00186         }
00187       
00188       // no duplicate key, so increment element count by one.
00189       count_++;
00190       
00191       // check for need to resize.
00192       if ((double) count_ > rehashDensity_ * (double) capacity_)
00193         {
00194           capacity_ = HashUtils::nextPrime(capacity_+1);
00195           rehash();
00196           // recaluate index
00197           index = hashCode(key) % capacity_;
00198         }
00199       
00200       data_[index].append(HashPair<Key, Value>(key, value));
00201     }
00202 
00203 
00204 
00205   template<class Key, class Value> inline
00206     void Hashtable<Key, Value>::rehash()
00207     {
00208       Array<Array<HashPair<Key, Value> > > tmp(capacity_);
00209 
00210       for (int i=0; i<data_.length(); i++)
00211         {
00212           for (int j=0; j<data_[i].length(); j++)
00213             {
00214               int newIndex = hashCode(data_[i][j].key_) % capacity_;
00215               tmp[newIndex].append(data_[i][j]);
00216             }
00217         }
00218       
00219       data_ = tmp;
00220     }
00221 
00222 
00223   template<class Key, class Value> inline
00224     void Hashtable<Key, Value>::arrayify(Array<Key>& keys, Array<Value>& values) const
00225     {
00226       keys.reserve(size());
00227       values.reserve(size());
00228 
00229       for (int i=0; i<data_.length(); i++)
00230         {
00231           for (int j=0; j<data_[i].length(); j++)
00232             {
00233               keys.append(data_[i][j].key_);
00234               values.append(data_[i][j].value_);
00235             }
00236         }
00237     }
00238 
00239   template<class Key, class Value>  inline
00240   std::string Hashtable<Key, Value>::toString() const 
00241   {
00242     Array<Key> keys;
00243     Array<Value> values;
00244     arrayify(keys, values);
00245     
00246     std::string rtn = "[";
00247     for (int i=0; i<keys.length(); i++)
00248       {
00249         rtn += "{" + Teuchos::toString(keys[i]) + ", " + Teuchos::toString(values[i])
00250           + "}";
00251         if (i < keys.length()-1) rtn += ", ";
00252       }
00253     rtn += "]";
00254     
00255     return rtn;
00256   }
00257 
00258   template<class Key, class Value>  inline
00259     std::string toString(const Hashtable<Key, Value>& h)
00260     {
00261       Array<Key> keys;
00262       Array<Value> values;
00263       h.arrayify(keys, values);
00264 
00265       std::string rtn = "[";
00266       for (int i=0; i<keys.length(); i++)
00267         {
00268           rtn += "{" + Teuchos::toString(keys[i]) + ", " + Teuchos::toString(values[i])
00269             + "}";
00270           if (i < keys.length()-1) rtn += ", ";
00271         }
00272       rtn += "]";
00273 
00274       return rtn;
00275     }
00276 
00277   template<class Key, class Value> inline
00278     const Value& Hashtable<Key, Value>::get(const Key& key) const
00279     {
00280       TEST_FOR_EXCEPTION(!containsKey(key),
00281                          std::runtime_error,
00282                          "Hashtable<Key, Value>::get: key " 
00283                          << Teuchos::toString(key) 
00284                          << " not found in Hashtable"
00285                          << toString());
00286       
00287       const Array<HashPair<Key, Value> >& candidates
00288         = data_[hashCode(key) % capacity_];
00289 
00290       accumulateAvgFill(candidates.length());
00291       
00292       for (int i=0; i<candidates.length(); i++)
00293         {
00294           const HashPair<Key, Value>& c = candidates[i];
00295           if (c.key_ == key)
00296             {
00297               return c.value_;
00298             }
00299         }
00300       return mostRecentValue_;
00301     }
00302 
00303 
00304   template<class Key, class Value> inline
00305     void Hashtable<Key, Value>::remove(const Key& key)
00306     {
00307       TEST_FOR_EXCEPTION(!containsKey(key),
00308                          std::runtime_error,
00309                          "Hashtable<Key, Value>::remove: key " 
00310                          << Teuchos::toString(key) 
00311                          << " not found in Hashtable"
00312                          << toString());
00313 
00314       count_--;
00315       int h = hashCode(key) % capacity_;
00316       const Array<HashPair<Key, Value> >& candidates = data_[h];
00317 
00318       for (int i=0; i<candidates.length(); i++)
00319         {
00320           const HashPair<Key, Value>& c = candidates[i];
00321           if (c.key_ == key)
00322             {
00323               data_[h].remove(i);
00324               break;
00325             }
00326         }
00327     }
00328 
00329   template<class Key, class Value> inline
00330   void Hashtable<Key, Value>::accumulateAvgFill(int n) const
00331   {
00332     avgDegeneracy_ = ((double) nHits_)/(nHits_ + 1.0) * avgDegeneracy_ + ((double) n)/(nHits_ + 1.0);
00333     nHits_++;
00334     }
00335 
00336   template<class Key, class Value>  inline
00337     std::ostream& operator<<(std::ostream& os, const Hashtable<Key, Value>& h)
00338     {
00339       return os << toString(h);
00340     }
00341 
00342 
00343 }
00344 
00345 #endif // TEUCHOS_HASHTABLE_H
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines