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);
90 inline std::string
toString()
const ;
111 template<
class Key>
inline
115 template<
class Key>
inline
117 : data_(), count_(0), capacity_(
HashUtils::nextPrime(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_)
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 +=
", ";
241 template<
class Key>
inline
246 "HashSet<Key>::remove: 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
Templated array class derived from the STL std::vector.
Teuchos header file which uses auto-configuration information to include necessary C++ headers.
Utilities for generating hashcodes.
Replacement for std::vector that is compatible with the Teuchos Memory Management classes.
void reserve(size_type n)
int length() const
Return number of elements in the array.
void remove(int i)
Remove the i-th element from the array, with optional boundschecking.
void resize(size_type new_size, const value_type &x=value_type())
Array< T > & append(const T &x)
Add a new entry at the end of the array.
Templated hashtable-based set.
std::string toString() const
Write to a std::string.
int size() const
Get the number of elements in the table.
int nextPrime(int newCap) const
Array< Array< Key > > data_
Array< Key > arrayify() const
Get list of keys in Array form.
void put(const Key &key)
Put a new object into the table.
HashSet(int capacity=19)
Create an empty HashSet.
bool containsKey(const Key &key) const
Check for the presence of a key.
void remove(const Key &key)
Remove from the table the element given by key.
Utilities for generating hashcodes. This is not a true hash ! For all ints and types less than ints i...
static int nextPrime(int newCapacity)
#define TEUCHOS_TEST_FOR_EXCEPTION(throw_exception_test, Exception, msg)
Macro for throwing an exception with breakpointing to ease debugging.
std::ostream & operator<<(std::ostream &os, BigUInt< n > a)
std::string toString(const HashSet< Key > &h)