Teuchos_HashSet.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_HASHSET_H
00030 #define TEUCHOS_HASHSET_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 
00044 
00051   template<class Key> class HashSet
00052     {
00053     public:
00054 
00056       inline HashSet(int capacity=19);
00057 
00059       inline bool containsKey(const Key& key) const ;
00060 
00062       inline void put(const Key& key);
00063 
00065       inline void remove(const Key& key);
00066 
00068       inline int size() const {return count_;}
00069 
00071       inline Array<Key> arrayify() const ;
00072 
00074       inline void arrayify(Array<Key>& keys) const ;
00075 
00077       inline std::string toString() const ;
00078 
00079     private:
00081       inline void rehash();
00083       inline int nextPrime(int newCap) const ;
00084 
00085       Array<Array<Key> > data_;
00086       int count_;
00087       int capacity_;
00088       mutable Key mostRecentKey_;
00089     };
00090 
00091 
00095   template<class Key>
00096     std::ostream& operator<<(std::ostream& os, const HashSet<Key>& h);
00097 
00098   template<class Key> inline
00099     std::string toString(const HashSet<Key>& h) {return h.toString();}
00100 
00101 
00102   template<class Key> inline
00103     HashSet<Key>::HashSet(int capacity)
00104     : data_(), count_(0), capacity_(HashUtils::nextPrime(capacity))
00105     {
00106       data_.resize(capacity_);
00107     }
00108 
00109   template<class Key> inline
00110     bool HashSet<Key>::containsKey(const Key& key) const
00111     {
00112       const Array<Key>& candidates
00113         = data_[hashCode(key) % capacity_];
00114 
00115       for (int i=0; i<candidates.length(); i++)
00116         {
00117           const Key& c = candidates[i];
00118           if (c == key)
00119             {
00120               return true;
00121             }
00122         }
00123       return false;
00124     }
00125 
00126   template<class Key> inline
00127     void HashSet<Key>::put(const Key& key)
00128     {
00129       int index = hashCode(key) % capacity_;
00130 
00131       Array<Key>& local = data_[index];
00132 
00133       // check for duplicate key
00134       for (int i=0; i<local.length(); i++)
00135         {
00136           if (local[i] == key)
00137             {
00138               return;
00139             }
00140         }
00141 
00142       // no duplicate key, so increment element count by one.
00143       count_++;
00144 
00145       // check for need to resize.
00146       if (count_ > capacity_)
00147         {
00148           capacity_ = HashUtils::nextPrime(capacity_+1);
00149           rehash();
00150           // recaluate index
00151           index = hashCode(key) % capacity_;
00152         }
00153 
00154       data_[index].append(key);
00155     }
00156 
00157 
00158 
00159   template<class Key> inline
00160     void HashSet<Key>::rehash()
00161     {
00162       Array<Array<Key> > tmp(capacity_);
00163 
00164       for (int i=0; i<data_.length(); i++)
00165         {
00166           for (int j=0; j<data_[i].length(); j++)
00167             {
00168               int newIndex = hashCode(data_[i][j]) % capacity_;
00169               tmp[newIndex].append(data_[i][j]);
00170             }
00171         }
00172 
00173       data_ = tmp;
00174     }
00175 
00176   template<class Key> inline
00177     Array<Key> HashSet<Key>::arrayify() const
00178     {
00179       Array<Key> rtn;
00180       rtn.reserve(size());
00181 
00182       for (int i=0; i<data_.length(); i++)
00183         {
00184           for (int j=0; j<data_[i].length(); j++)
00185             {
00186               rtn.append(data_[i][j]);
00187             }
00188         }
00189 
00190       return rtn;
00191     }
00192 
00193   template<class Key> inline
00194     void HashSet<Key>::arrayify(Array<Key>& rtn) const
00195     {
00196       rtn.resize(0);
00197 
00198       for (int i=0; i<data_.length(); i++)
00199         {
00200           for (int j=0; j<data_[i].length(); j++)
00201             {
00202               rtn.append(data_[i][j]);
00203             }
00204         }
00205     }
00206 
00207   template<class Key>  inline
00208     std::string HashSet<Key>::toString() const
00209     {
00210       std::string rtn = "HashSet[";
00211 
00212       bool first = true;
00213 
00214       for (int i=0; i<data_.length(); i++)
00215         {
00216           for (int j=0; j<data_[i].length(); j++)
00217             {
00218               if (!first) rtn += ", ";
00219               first = false;
00220               rtn += Teuchos::toString(data_[i][j]);
00221             }
00222         }
00223       rtn += "]";
00224       return rtn;
00225     }
00226 
00227 
00228   template<class Key> inline
00229     void HashSet<Key>::remove(const Key& key)
00230     {
00231       TEST_FOR_EXCEPTION(!containsKey(key),
00232                          std::runtime_error,
00233                          "HashSet<Key>::remove: key " 
00234                          << Teuchos::toString(key) 
00235                          << " not found in HashSet"
00236                          << toString());
00237 
00238       count_--;
00239       int h = hashCode(key) % capacity_;
00240       Array<Key>& candidates = data_[h];
00241 
00242       for (int i=0; i<candidates.length(); i++)
00243         {
00244           if (candidates[i] == key)
00245             {
00246               candidates.remove(i);
00247               break;
00248             }
00249         }
00250     }
00251 
00252 
00253 
00254   template<class Key>  inline
00255     std::ostream& operator<<(std::ostream& os, const HashSet<Key>& h)
00256     {
00257       return os << h.toString();
00258     }
00259 
00260 
00261 }
00262 
00263 #endif // TEUCHOS_HASHSET_H

Generated on Wed May 12 21:40:32 2010 for Teuchos - Trilinos Tools Package by  doxygen 1.4.7