Teuchos Package Browser (Single Doxygen Collection) Version of the Day
Loading...
Searching...
No Matches
Teuchos_HashSet.hpp
Go to the documentation of this file.
1// @HEADER
2// ***********************************************************************
3//
4// Teuchos: Common Tools Package
5// Copyright (2004) Sandia Corporation
6//
7// Under terms of Contract DE-AC04-94AL85000, there is a non-exclusive
8// license for use of this work by or on behalf of the U.S. Government.
9//
10// Redistribution and use in source and binary forms, with or without
11// modification, are permitted provided that the following conditions are
12// met:
13//
14// 1. Redistributions of source code must retain the above copyright
15// notice, this list of conditions and the following disclaimer.
16//
17// 2. Redistributions in binary form must reproduce the above copyright
18// notice, this list of conditions and the following disclaimer in the
19// documentation and/or other materials provided with the distribution.
20//
21// 3. Neither the name of the Corporation nor the names of the
22// contributors may be used to endorse or promote products derived from
23// this software without specific prior written permission.
24//
25// THIS SOFTWARE IS PROVIDED BY SANDIA CORPORATION "AS IS" AND ANY
26// EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
27// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
28// PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL SANDIA CORPORATION OR THE
29// CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
30// EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
31// PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
32// PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
33// LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
34// NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
35// SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
36//
37// Questions? Contact Michael A. Heroux (maherou@sandia.gov)
38//
39// ***********************************************************************
40// @HEADER
41
42#ifndef TEUCHOS_HASHSET_H
43#define TEUCHOS_HASHSET_H
44
50#include "Teuchos_Array.hpp"
51#include "Teuchos_HashUtils.hpp"
52
53namespace Teuchos
54{
55 using std::string;
56
57
64 template<class Key> class HashSet
65 {
66 public:
67
69 inline HashSet(int capacity=19);
70
72 inline bool containsKey(const Key& key) const ;
73
75 inline void put(const Key& key);
76
78 inline void remove(const Key& key);
79
81 inline int size() const {return count_;}
82
84 inline Array<Key> arrayify() const ;
85
87 inline void arrayify(Array<Key>& keys) const ;
88
90 inline std::string toString() const ;
91
92 private:
94 inline void rehash();
96 inline int nextPrime(int newCap) const ;
97
99 int count_;
102 };
103
104
108 template<class Key>
109 std::ostream& operator<<(std::ostream& os, const HashSet<Key>& h);
110
111 template<class Key> inline
112 std::string toString(const HashSet<Key>& h) {return h.toString();}
113
114
115 template<class Key> inline
117 : data_(), count_(0), capacity_(HashUtils::nextPrime(capacity))
118 {
119 data_.resize(capacity_);
120 }
121
122 template<class Key> inline
123 bool HashSet<Key>::containsKey(const Key& key) const
124 {
126 = data_[hashCode(key) % capacity_];
127
128 for (int i=0; i<candidates.length(); i++)
129 {
130 const Key& c = candidates[i];
131 if (c == key)
132 {
133 return true;
134 }
135 }
136 return false;
137 }
138
139 template<class Key> inline
140 void HashSet<Key>::put(const Key& key)
141 {
142 int index = hashCode(key) % capacity_;
143
144 Array<Key>& local = data_[index];
145
146 // check for duplicate key
147 for (int i=0; i<local.length(); i++)
148 {
149 if (local[i] == key)
150 {
151 return;
152 }
153 }
154
155 // no duplicate key, so increment element count by one.
156 count_++;
157
158 // check for need to resize.
159 if (count_ > capacity_)
160 {
161 capacity_ = HashUtils::nextPrime(capacity_+1);
162 rehash();
163 // recaluate index
164 index = hashCode(key) % capacity_;
165 }
166
167 data_[index].append(key);
168 }
169
170
171
172 template<class Key> inline
174 {
175 Array<Array<Key> > tmp(capacity_);
176
177 for (int i=0; i<data_.length(); i++)
178 {
179 for (int j=0; j<data_[i].length(); j++)
180 {
181 int newIndex = hashCode(data_[i][j]) % capacity_;
182 tmp[newIndex].append(data_[i][j]);
183 }
184 }
185
186 data_ = tmp;
187 }
188
189 template<class Key> inline
191 {
193 rtn.reserve(size());
194
195 for (int i=0; i<data_.length(); i++)
196 {
197 for (int j=0; j<data_[i].length(); j++)
198 {
199 rtn.append(data_[i][j]);
200 }
201 }
202
203 return rtn;
204 }
205
206 template<class Key> inline
208 {
209 rtn.resize(0);
210
211 for (int i=0; i<data_.length(); i++)
212 {
213 for (int j=0; j<data_[i].length(); j++)
214 {
215 rtn.append(data_[i][j]);
216 }
217 }
218 }
219
220 template<class Key> inline
221 std::string HashSet<Key>::toString() const
222 {
223 std::string rtn = "HashSet[";
224
225 bool first = true;
226
227 for (int i=0; i<data_.length(); i++)
228 {
229 for (int j=0; j<data_[i].length(); j++)
230 {
231 if (!first) rtn += ", ";
232 first = false;
233 rtn += Teuchos::toString(data_[i][j]);
234 }
235 }
236 rtn += "]";
237 return rtn;
238 }
239
240
241 template<class Key> inline
242 void HashSet<Key>::remove(const Key& key)
243 {
244 TEUCHOS_TEST_FOR_EXCEPTION(!containsKey(key),
245 std::runtime_error,
246 "HashSet<Key>::remove: key "
247 << Teuchos::toString(key)
248 << " not found in HashSet"
249 << toString());
250
251 count_--;
252 int h = hashCode(key) % capacity_;
253 Array<Key>& candidates = data_[h];
254
255 for (int i=0; i<candidates.length(); i++)
256 {
257 if (candidates[i] == key)
258 {
259 candidates.remove(i);
260 break;
261 }
262 }
263 }
264
265
266
267 template<class Key> inline
268 std::ostream& operator<<(std::ostream& os, const HashSet<Key>& h)
269 {
270 return os << h.toString();
271 }
272
273
274}
275
276#endif // TEUCHOS_HASHSET_H
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.
int size(const Comm< Ordinal > &comm)
Get the number of processes in the communicator.
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)
Concrete serial communicator subclass.
#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)