42 #ifndef TEUCHOS_HASHSET_H 43 #define TEUCHOS_HASHSET_H 69 inline HashSet(
int capacity=19);
75 inline void put(
const Key& key);
78 inline void remove(
const Key& key);
81 inline int size()
const {
return count_;}
90 inline std::string
toString()
const ;
96 inline int nextPrime(
int newCap)
const ;
101 mutable Key mostRecentKey_;
109 std::ostream& operator<<(std::ostream& os, const HashSet<Key>& h);
111 template<
class Key>
inline 115 template<
class Key>
inline 117 : data_(), count_(0), capacity_(
HashUtils::nextPrime(capacity))
119 data_.resize(capacity_);
122 template<
class Key>
inline 126 = data_[hashCode(key) % capacity_];
128 for (
int i=0; i<candidates.
length(); i++)
130 const Key& c = candidates[i];
139 template<
class Key>
inline 142 int index = hashCode(key) % capacity_;
147 for (
int i=0; i<local.
length(); i++)
159 if (count_ > capacity_)
161 capacity_ = HashUtils::nextPrime(capacity_+1);
164 index = hashCode(key) % capacity_;
167 data_[index].append(key);
172 template<
class Key>
inline 177 for (
int i=0; i<data_.length(); i++)
179 for (
int j=0; j<data_[i].length(); j++)
181 int newIndex = hashCode(data_[i][j]) % capacity_;
182 tmp[newIndex].
append(data_[i][j]);
189 template<
class Key>
inline 195 for (
int i=0; i<data_.length(); i++)
197 for (
int j=0; j<data_[i].length(); j++)
206 template<
class Key>
inline 211 for (
int i=0; i<data_.length(); i++)
213 for (
int j=0; j<data_[i].length(); j++)
220 template<
class Key>
inline 223 std::string rtn =
"HashSet[";
227 for (
int i=0; i<data_.length(); i++)
229 for (
int j=0; j<data_[i].length(); j++)
231 if (!first) rtn +=
", ";
233 rtn += Teuchos::toString(data_[i][j]);
241 template<
class Key>
inline 246 "HashSet<Key>::remove: key " 247 << Teuchos::toString(key)
248 <<
" not found in HashSet" 252 int h = hashCode(key) % capacity_;
255 for (
int i=0; i<candidates.
length(); i++)
257 if (candidates[i] == key)
267 template<
class Key>
inline 268 std::ostream& operator<<(std::ostream& os, const HashSet<Key>& h)
276 #endif // TEUCHOS_HASHSET_H void remove(int i)
Remove the i-th element from the array, with optional boundschecking.
void reserve(size_type n)
Utilities for generating hashcodes. This is not a true hash ! For all ints and types less than ints i...
Array< T > & append(const T &x)
Add a new entry at the end of the array.
#define TEUCHOS_TEST_FOR_EXCEPTION(throw_exception_test, Exception, msg)
Macro for throwing an exception with breakpointing to ease debugging.
Teuchos header file which uses auto-configuration information to include necessary C++ headers...
bool containsKey(const Key &key) const
Check for the presence of a key.
Templated hashtable-based set.
std::string toString() const
Write to a std::string.
void resize(size_type new_size, const value_type &x=value_type())
HashSet(int capacity=19)
Create an empty HashSet.
void put(const Key &key)
Put a new object into the table.
Array< Key > arrayify() const
Get list of keys in Array form.
Templated array class derived from the STL std::vector.
The Teuchos namespace contains all of the classes, structs and enums used by Teuchos, as well as a number of utility routines.
int length() const
Return number of elements in the array.
int size() const
Get the number of elements in the table.
Utilities for generating hashcodes.
void remove(const Key &key)
Remove from the table the element given by key.
Replacement for std::vector that is compatible with the Teuchos Memory Management classes...