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