Teuchos - Trilinos Tools Package  Version of the Day
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
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 
49 #include "Teuchos_ConfigDefs.hpp"
50 #include "Teuchos_Array.hpp"
51 #include "Teuchos_HashUtils.hpp"
52 
53 namespace 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 
98  Array<Array<Key> > data_;
99  int count_;
100  int capacity_;
101  mutable Key mostRecentKey_;
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
116  HashSet<Key>::HashSet(int capacity)
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  {
125  const Array<Key>& candidates
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
173  void HashSet<Key>::rehash()
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  {
192  Array<Key> rtn;
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
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.
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...