Teuchos_HashSet.hpp
Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
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
00134 for (int i=0; i<local.length(); i++)
00135 {
00136 if (local[i] == key)
00137 {
00138 return;
00139 }
00140 }
00141
00142
00143 count_++;
00144
00145
00146 if (count_ > capacity_)
00147 {
00148 capacity_ = HashUtils::nextPrime(capacity_+1);
00149 rehash();
00150
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