CVC3  2.4.1
hash_set.h
Go to the documentation of this file.
1 /*****************************************************************************/
2 /*!
3  *\file hash_set.h
4  *\brief hash map implementation
5  *
6  * Author: Alexander Fuchs
7  *
8  * Created: Thu Oct 19 11:04:00 2006
9  *
10  * <hr>
11  *
12  * License to use, copy, modify, sell and/or distribute this software
13  * and its documentation for any purpose is hereby granted without
14  * royalty, subject to the terms and conditions defined in the \ref
15  * LICENSE file provided with this distribution.
16  *
17  * <hr>
18  */
19 /*****************************************************************************/
20 
21 /*
22  * Copyright (c) 1996,1997
23  * Silicon Graphics Computer Systems, Inc.
24  *
25  * Permission to use, copy, modify, distribute and sell this software
26  * and its documentation for any purpose is hereby granted without fee,
27  * provided that the above copyright notice appear in all copies and
28  * that both that copyright notice and this permission notice appear
29  * in supporting documentation. Silicon Graphics makes no
30  * representations about the suitability of this software for any
31  * purpose. It is provided "as is" without express or implied warranty.
32  *
33  *
34  * Copyright (c) 1994
35  * Hewlett-Packard Company
36  *
37  * Permission to use, copy, modify, distribute and sell this software
38  * and its documentation for any purpose is hereby granted without fee,
39  * provided that the above copyright notice appear in all copies and
40  * that both that copyright notice and this permission notice appear
41  * in supporting documentation. Hewlett-Packard Company makes no
42  * representations about the suitability of this software for any
43  * purpose. It is provided "as is" without express or implied warranty.
44  *
45  */
46 
47 // this implementation is in essence a subset of the SGI implementation:
48 // http://www.sgi.com/tech/stl/stl_hash_set.h
49 
50 #ifndef _cvc3__hash__hash_set_h_
51 #define _cvc3__hash__hash_set_h_
52 
53 
54 #include "hash_fun.h"
55 #include "hash_table.h"
56 
57 namespace Hash {
58 
59  // identity is an extension taken from the SGI
60  // implementation of the STL file functional:
61  // http://www.sgi.com/tech/stl/stl_function.h
62  template <class _Tp>
63  struct _Identity : public std::unary_function<_Tp,_Tp> {
64  const _Tp& operator()(const _Tp& __x) const { return __x; }
65  };
66 
67 
68  /*! hash set implementation based on the sgi interface:
69  http://www.sgi.com/tech/stl/hash_set.html
70 
71  _Key: hash key type
72  _HashFcn: functional class providing a hash function: size_type (_Key)
73  _EqualKey: functional class providing a comparison function: bool(_Key, _Key)
74  returns true iff two keys are considered to be equal
75  */
76  template <class _Key, class _HashFcn = hash<_Key>,
77  class _EqualKey = std::equal_to<_Key> >
78  class hash_set {
79 
80  /// types
81  protected:
83 
84  public:
85  // typedefs as custom for other implementations
87  typedef typename _hash_table::key_type key_type;
89  typedef typename _hash_table::hasher hasher;
91 
92  public:
93  // iterators
94  typedef typename _hash_table::iterator iterator;
96 
97 
98 
99  /// variables
100 
101  protected:
102  // the hash table
104 
105 
106  /// methods
107 
108  public:
109  /// constructors
110 
111  // default size is 16 buckets
113  d_table()
114  { };
115 
116  // specifiy initial number of buckets - must be positive
117  hash_set(size_type initial_capacity) :
118  d_table(initial_capacity)
119  { };
120 
121  // specifiy initial number of buckets and hash function
122  hash_set(size_type initial_capacity, const _HashFcn& hash) :
123  d_table(initial_capacity, hash)
124  { };
125 
126  // specifiy initial number of buckets, hash and equal function
127  hash_set(size_type initial_capacity,
128  const _HashFcn& hash, const _EqualKey& equal) :
129  d_table(initial_capacity, hash, equal)
130  { };
131 
132  // copy hash map.
133  hash_set(const hash_set& other) :
134  d_table(other.d_table)
135  { };
136 
137  // assign hash map
138  hash_set& operator=(const hash_set& other) {
139  if (this != &other) {
140  d_table = other.d_table;
141  }
142 
143  return *this;
144  }
145 
146  void swap(hash_set& other) {
147  d_table.swap(other.d_table);
148  }
149 
150  // removes all entries, number of buckets is not reduced.
151  void clear() {
152  d_table.clear();
153  };
154 
155 
156 
157  /// operations
158 
159 
160  // returns end iterator if key was not bound
161  iterator find(const key_type& key) {
162  return d_table.find(key);
163  }
164 
165  // const version of find
166  const_iterator find(const key_type& key) const {
167  return d_table.find(key);
168  }
169 
170 
171  // adds the mapping from key to data, if key is still unbound
172  // otherwise returns false
173  std::pair<iterator, bool> insert(const value_type& entry) {
174  return d_table.insert(entry);
175  }
176 
177  // removes binding of key
178  // returns number of keys removed,
179  // i.e. 1 if key was bound, 0 if key was not bound.
180  size_type erase(const key_type& key) {
181  return d_table.erase(key);
182  }
183 
184 
185 
186  /// status
187 
188  // is the key bound?
189  bool contains(const key_type& key) const {
190  return d_table.contains(key);
191  }
192 
193  // returns the number of times a key is bound,
194  // i.e. 0 or 1
195  size_type count(const _Key& key) const {
196  return d_table.count(key);
197  }
198 
199  // is the hash map empty?
200  bool empty() const {
201  return d_table.empty();
202  }
203 
204  // the number of elements in the hash map
205  size_type size() const {
206  return d_table.size();
207  }
208 
209  // the number of buckets in the hash map
211  return d_table.bucket_count();
212  }
213 
214  // returns the average number of elements per bucket
215  float load_factor() const {
216  return d_table.load_factor();
217  }
218 
219 
220 
221  /// iterators
222 
223  // returns forward iterator to iterate over all key/data pairs
225  return d_table.begin();
226  }
227 
228  // const version of begin
230  return d_table.begin();
231  }
232 
233 
234  // returns end iterator
236  return d_table.end();
237  }
238 
239  // const version of end
240  const_iterator end() const {
241  return d_table.end();
242  }
243  };
244 
245 }
246 
247 #endif