HashSet.H
Go to the documentation of this file.
1/*---------------------------------------------------------------------------*\
2 ========= |
3 \\ / F ield | OpenFOAM: The Open Source CFD Toolbox
4 \\ / O peration |
5 \\ / A nd | www.openfoam.com
6 \\/ M anipulation |
7-------------------------------------------------------------------------------
8 Copyright (C) 2011-2016 OpenFOAM Foundation
9 Copyright (C) 2016-2021 OpenCFD Ltd.
10-------------------------------------------------------------------------------
11License
12 This file is part of OpenFOAM.
13
14 OpenFOAM is free software: you can redistribute it and/or modify it
15 under the terms of the GNU General Public License as published by
16 the Free Software Foundation, either version 3 of the License, or
17 (at your option) any later version.
18
19 OpenFOAM is distributed in the hope that it will be useful, but WITHOUT
20 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
21 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
22 for more details.
23
24 You should have received a copy of the GNU General Public License
25 along with OpenFOAM. If not, see <http://www.gnu.org/licenses/>.
26
27Class
28 Foam::HashSet
29
30Description
31 A HashTable with keys but without contents that is similar to
32 \c std::unordered_set.
33
34 The entries are considered \a unordered since their placement
35 depends on the method used to generate the hash key index, the
36 table capacity, insertion order etc. When the key order is
37 important, use the sortedToc() method to obtain a list of sorted
38 keys and use that for further access.
39
40Note
41 The HashSet iterator dereferences to the key, so the following
42 range-for works as expected:
43 \code
44 labelHashSet someLabels{10, 20, 30, 40, ...};
45 for (const label i : someLabels)
46 {
47 Info<< "val:" << i << nl;
48 }
49 \endcode
50
51Typedef
52 Foam::wordHashSet
53
54Description
55 A HashSet with word keys and string hasher.
56
57Typedef
58 Foam::labelHashSet
59
60Description
61 A HashSet with label keys and label hasher.
62
63\*---------------------------------------------------------------------------*/
64
65#ifndef HashSet_H
66#define HashSet_H
67
68#include "HashTable.H"
69#include "IndirectList.H"
70
71// * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
72
73namespace Foam
74{
75
76// Forward Declarations
77template<class T> class MinMax;
78template<class Key, class Hash> class HashSet;
79
80// Common hash-set types
81
82//- A HashSet of words, uses string hasher.
84
85//- A HashSet of labels, uses label hasher.
87
88
89/*---------------------------------------------------------------------------*\
90 Class HashSet Declaration
91\*---------------------------------------------------------------------------*/
92
93template<class Key, class Hash=Foam::Hash<Key>>
94class HashSet
95:
96 public HashTable<zero::null, Key, Hash>
97{
98 // Private Member Functions
99
100 //- Assign from the input iterator range
101 template<class InputIter>
102 inline label assignMany
103 (
104 const label nItems,
105 InputIter first,
106 InputIter last
107 );
108
109
110public:
111
112 //- The template instance used for this HashSet
114
115 //- The template instance used for the parent HashTable
117
118 //- An iterator, returning reference to the key
119 using iterator = typename parent_type::key_iterator;
120
121 //- A const_iterator, returning reference to the key
123
124
125 // Constructors
126
127 //- Default construct with default (128) table capacity
128 HashSet()
129 :
131 {}
132
133 //- Copy construct
134 HashSet(const this_type& rhs)
135 :
136 parent_type(rhs)
137 {}
138
139 //- Move construct
140 HashSet(this_type&& rhs)
141 :
142 parent_type(std::move(rhs))
143 {}
144
145 //- Construct given initial table capacity
146 explicit HashSet(const label size)
147 :
149 {}
150
151 //- Construct from Istream with default table capacity
152 explicit HashSet(Istream& is)
153 :
154 parent_type(is)
155 {}
156
157 //- Construct from FixedList of Key
158 template<unsigned N>
159 explicit HashSet(const FixedList<Key, N>& list);
160
161 //- Construct from UList of Key
162 explicit HashSet(const UList<Key>& list);
163
164 //- Construct from an indirect list
165 template<class Addr>
166 explicit HashSet(const IndirectListBase<Key, Addr>& list);
167
168 //- Construct from an initializer list of Key
169 HashSet(std::initializer_list<Key> list);
170
171 //- Construct from the keys of another HashTable,
172 //- the type of values held is arbitrary.
173 template<class AnyType, class AnyHash>
174 explicit HashSet(const HashTable<AnyType, Key, AnyHash>& tbl);
175
176
177 // Member Functions
178
179 //- Same as found() - return true if key exists in the set.
180 // Method name compatibility with bitSet and boolList.
181 bool test(const Key& key) const noexcept
182 {
183 return found(key);
184 }
185
186
187 // Edit
188
189 //- Insert a new entry, not overwriting existing entries.
190 // \return True if the entry inserted, which means that it did
191 // not previously exist in the set.
192 bool insert(const Key& key)
193 {
194 return this->parent_type::emplace(key);
195 }
196
197 //- Same as insert (no value to overwrite)
198 bool set(const Key& key)
199 {
200 return insert(key);
201 }
202
203 //- Unset the specified key - same as erase
204 // \return True if the entry existed and was removed
205 bool unset(const Key& key)
206 {
207 return this->parent_type::erase(key);
208 }
209
210
211 // Convenience
212
213 //- Insert keys from the input iterator range
214 // \return The number of new elements inserted
215 template<class InputIter>
216 inline label insert(InputIter first, InputIter last);
217
218 //- Insert keys from a initializer list of Key
219 // \return The number of new elements inserted
220 inline label insert(std::initializer_list<Key> list);
221
222 //- Insert keys from the list of Key
223 // \return The number of new elements inserted
224 template<unsigned N>
225 inline label insert(const FixedList<Key, N>& list);
226
227 //- Insert keys from the list of Key
228 // \return The number of new elements inserted
229 inline label insert(const UList<Key>& list);
230
231 //- Insert keys from the list of Key
232 // \return The number of new elements inserted
233 template<class Addr>
234 inline label insert(const IndirectListBase<Key, Addr>& list);
235
236 //- Same as insert (no value to overwrite)
237 template<class InputIter>
238 inline label set(InputIter first, InputIter last)
239 {
240 return insert(first, last);
241 }
242
243 //- Same as insert (no value to overwrite)
244 inline label set(std::initializer_list<Key> list)
245 {
246 return insert(list);
247 }
248
249 //- Same as insert (no value to overwrite)
250 template<unsigned N>
251 inline label set(const FixedList<Key, N>& list)
252 {
253 return insert(list);
254 }
255
256 //- Same as insert (no value to overwrite)
257 inline label set(const UList<Key>& list)
258 {
259 return insert(list);
260 }
261
262 //- Same as insert (no value to overwrite)
263 template<class Addr>
264 inline label set(const IndirectListBase<Key, Addr>& list)
265 {
266 return insert(list);
267 }
268
269 //- Same as insert (no value to overwrite)
270 // \note Method name compatibility with bitSet
271 template<class InputIter>
272 inline label setMany(InputIter first, InputIter last)
273 {
274 return insert(first, last);
275 }
276
277 //- Unset the keys listed in the input iterator range
278 // \return The number of items removed
279 template<class InputIter>
280 inline label unset(InputIter first, InputIter last);
281
282 //- Unset the listed keys - same as erase
283 // \return The number of items removed
284 inline label unset(std::initializer_list<Key> list);
285
286 //- Unset the listed keys - same as erase
287 // \return The number of items removed
288 template<unsigned N>
289 inline label unset(const FixedList<Key, N>& list);
290
291 //- Unset the listed keys - same as erase
292 // \return The number of items removed
293 inline label unset(const UList<Key>& list);
294
295 //- Unset the listed keys - same as erase
296 // \return The number of items removed
297 template<class Addr>
298 inline label unset(const IndirectListBase<Key, Addr>& list);
299
300
301 // STL iterators
302
303 inline iterator begin();
304 inline const_iterator begin() const;
305 inline const_iterator cbegin() const;
306
307 inline iterator end() noexcept;
308 inline const_iterator end() const noexcept;
309 inline constexpr const_iterator cend() const noexcept;
310
311
312 // Writing
313
314 //- Write unordered keys (list), with line-breaks
315 //- when length exceeds shortLen.
316 // Using '0' suppresses line-breaks entirely.
317 Ostream& writeList(Ostream& os, const label shortLen=0) const
318 {
319 return this->writeKeys(os, shortLen);
320 }
321
322
323 // Member Operators
324
325 //- Return true if the entry exists, same as found()
326 // \note this allows use of HashSet as a predicate test
327 inline bool operator()(const Key& key) const noexcept;
328
329 //- Return true if the entry exists, same as found().
330 inline bool operator[](const Key& key) const noexcept;
331
332 //- Copy assign
333 void operator=(const this_type& rhs)
334 {
336 }
337
338 //- Move assign
339 void operator=(this_type&& rhs)
340 {
341 parent_type::operator=(std::move(rhs));
342 }
343
344
345 // Comparison
346
347 //- Sets are equal if all keys are equal,
348 //- independent of order or underlying storage size.
349 bool operator==(const this_type& rhs) const;
350
351 //- The opposite of the equality operation.
352 bool operator!=(const this_type& rhs) const;
353
354
355 // Assignment
356
357 //- Assignment from a UList of keys
358 void operator=(const UList<Key>& rhs);
359
360 //- Assignment from a FixedList of keys
361 template<unsigned N>
362 void operator=(const FixedList<Key, N>& rhs);
363
364 //- Assignment from an initializer list of keys
365 void operator=(std::initializer_list<Key> rhs);
366
367
368 // Logical and set operations
369
370 //- Add entries to this HashSet
371 this_type& operator|=(const this_type& rhs);
372
373 //- Only retain entries found in both HashSets
374 inline this_type& operator&=(const this_type& rhs);
375
376 //- Only retain unique entries (xor)
377 this_type& operator^=(const this_type& rhs);
378
379 //- Add entries to this HashSet. Same as the '|=' operator
380 inline this_type& operator+=(const this_type& rhs);
381
382 //- Remove entries from this HashSet. Uses erase()
383 inline this_type& operator-=(const this_type& rhs);
384
385
386 // Housekeeping
387
388 //- Not applicable for HashSet
389 template<class UnaryPredicate>
390 List<Key> tocValues(const UnaryPredicate&, const bool) = delete;
391
392 //- Not applicable for HashSet
393 template<class BinaryPredicate>
394 List<Key> tocEntries(const BinaryPredicate&, const bool) = delete;
395
396 //- Not applicable for HashSet
397 template<class UnaryPredicate>
398 label countValues(const UnaryPredicate&, const bool) = delete;
399
400 //- Not applicable for HashSet
401 template<class BinaryPredicate>
402 label countEntries(const BinaryPredicate&, const bool) = delete;
403
404 //- Not applicable for HashSet
405 template<class UnaryPredicate>
406 label filterValues(const UnaryPredicate&, const bool) = delete;
407
408 //- Not applicable for HashSet
409 template<class BinaryPredicate>
410 label filterEntries(const BinaryPredicate&, const bool) = delete;
411};
412
413
414// * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
415
416// Global Functions
417
418//- Find the min value in labelHashSet, optionally limited by second argument.
419// For an empty set, returns the second argument (eg, labelMax).
420label min(const labelHashSet& set, label minValue = labelMax);
421
422//- Find the max value in labelHashSet, optionally limited by second argument.
423// For an empty set, returns the second argument (eg, labelMin).
424label max(const labelHashSet& set, label maxValue = labelMin);
425
426//- Find the min/max values of labelHashSet
428
429
430// Global Operators
431
432//- Write the list of HashSet keys
433template<class Key, class Hash>
435
436
437//- Combine entries (OR) for two HashSets
438// See HashSet::operator|= for more details.
439template<class Key, class Hash>
440HashSet<Key, Hash> operator|
441(
442 const HashSet<Key, Hash>& a,
443 const HashSet<Key, Hash>& b
444);
445
446//- Subset (AND) intersection of two HashSet
447// See HashSet::operator&= for more details.
448template<class Key, class Hash>
449HashSet<Key, Hash> operator&
450(
451 const HashSet<Key, Hash>& a,
452 const HashSet<Key, Hash>& b
453);
454
455//- Create a HashSet that only contains unique entries (XOR)
456// See HashSet::operator^= for more details.
457template<class Key, class Hash>
458HashSet<Key, Hash> operator^
459(
460 const HashSet<Key, Hash>& a,
461 const HashSet<Key, Hash>& b
462);
463
464//- Subset difference of two HashSets
465// See HashSet::operator-= for more details.
466template<class Key, class Hash>
467HashSet<Key, Hash> operator-
468(
469 const HashSet<Key, Hash>& a,
470 const HashSet<Key, Hash>& b
471);
472
473
474// * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
475
476} // End namespace Foam
477
478// * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
479
480#ifdef NoRepository
481 #include "HashSet.C"
482#endif
483
484// * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
485
486#endif
487
488// ************************************************************************* //
scalar maxValue
scalar minValue
bool found
A 1D vector of objects of type <T> with a fixed length <N>.
Definition: FixedList.H:81
A HashTable with keys but without contents that is similar to std::unordered_set.
Definition: HashSet.H:96
HashTable< zero::null, Key, Hash > parent_type
The template instance used for the parent HashTable.
Definition: HashSet.H:115
bool operator[](const Key &key) const noexcept
Return true if the entry exists, same as found().
Definition: HashSet.C:245
Ostream & writeList(Ostream &os, const label shortLen=0) const
Definition: HashSet.H:316
bool operator()(const Key &key) const noexcept
Return true if the entry exists, same as found()
Definition: HashSet.C:238
label set(std::initializer_list< Key > list)
Same as insert (no value to overwrite)
Definition: HashSet.H:243
iterator end() noexcept
Definition: HashSet.C:479
label set(const UList< Key > &list)
Same as insert (no value to overwrite)
Definition: HashSet.H:256
label set(InputIter first, InputIter last)
Same as insert (no value to overwrite)
Definition: HashSet.H:237
bool insert(const Key &key)
Insert a new entry, not overwriting existing entries.
Definition: HashSet.H:191
label countEntries(const BinaryPredicate &, const bool)=delete
Not applicable for HashSet.
this_type & operator|=(const this_type &rhs)
Add entries to this HashSet.
Definition: HashSet.C:303
HashSet(Istream &is)
Construct from Istream with default table capacity.
Definition: HashSet.H:151
List< Key > tocValues(const UnaryPredicate &, const bool)=delete
Not applicable for HashSet.
label insert(InputIter first, InputIter last)
Insert keys from the input iterator range.
label set(const FixedList< Key, N > &list)
Same as insert (no value to overwrite)
Definition: HashSet.H:250
label unset(InputIter first, InputIter last)
Unset the keys listed in the input iterator range.
typename parent_type::key_iterator iterator
An iterator, returning reference to the key.
Definition: HashSet.H:118
void operator=(this_type &&rhs)
Move assign.
Definition: HashSet.H:338
bool operator==(const this_type &rhs) const
Definition: HashSet.C:274
typename parent_type::const_key_iterator const_iterator
A const_iterator, returning reference to the key.
Definition: HashSet.H:121
bool unset(const Key &key)
Unset the specified key - same as erase.
Definition: HashSet.H:204
const_iterator cbegin() const
Definition: HashSet.C:468
iterator begin()
Definition: HashSet.C:446
HashSet(const label size)
Construct given initial table capacity.
Definition: HashSet.H:145
HashSet< Key, Hash > this_type
The template instance used for this HashSet.
Definition: HashSet.H:112
constexpr const_iterator cend() const noexcept
Definition: HashSet.C:495
label filterEntries(const BinaryPredicate &, const bool)=delete
Not applicable for HashSet.
label insert(const IndirectListBase< Key, Addr > &list)
Insert keys from the list of Key.
HashSet()
Default construct with default (128) table capacity.
Definition: HashSet.H:127
label unset(const IndirectListBase< Key, Addr > &list)
Unset the listed keys - same as erase.
bool test(const Key &key) const noexcept
Same as found() - return true if key exists in the set.
Definition: HashSet.H:180
this_type & operator-=(const this_type &rhs)
Remove entries from this HashSet. Uses erase()
Definition: HashSet.C:355
label insert(const FixedList< Key, N > &list)
Insert keys from the list of Key.
label set(const IndirectListBase< Key, Addr > &list)
Same as insert (no value to overwrite)
Definition: HashSet.H:263
this_type & operator&=(const this_type &rhs)
Only retain entries found in both HashSets.
Definition: HashSet.C:317
HashSet(const this_type &rhs)
Copy construct.
Definition: HashSet.H:133
label countValues(const UnaryPredicate &, const bool)=delete
Not applicable for HashSet.
HashSet(this_type &&rhs)
Move construct.
Definition: HashSet.H:139
this_type & operator^=(const this_type &rhs)
Only retain unique entries (xor)
Definition: HashSet.C:326
bool set(const Key &key)
Same as insert (no value to overwrite)
Definition: HashSet.H:197
void operator=(const this_type &rhs)
Copy assign.
Definition: HashSet.H:332
label setMany(InputIter first, InputIter last)
Same as insert (no value to overwrite)
Definition: HashSet.H:271
List< Key > tocEntries(const BinaryPredicate &, const bool)=delete
Not applicable for HashSet.
bool operator!=(const this_type &rhs) const
The opposite of the equality operation.
Definition: HashSet.C:295
label unset(const FixedList< Key, N > &list)
Unset the listed keys - same as erase.
label filterValues(const UnaryPredicate &, const bool)=delete
Not applicable for HashSet.
this_type & operator+=(const this_type &rhs)
Add entries to this HashSet. Same as the '|=' operator.
Definition: HashSet.C:347
A HashTable similar to std::unordered_map.
Definition: HashTable.H:123
Ostream & writeKeys(Ostream &os, const label shortLen=0) const
Definition: HashTableIO.C:97
key_iterator_base< iterator > key_iterator
Forward iterator returning the key.
Definition: HashTable.H:918
key_iterator_base< const_iterator > const_key_iterator
Forward const iterator returning the key.
Definition: HashTable.H:921
label size() const noexcept
The number of elements in table.
Definition: HashTableI.H:52
bool erase(const iterator &iter)
Erase an entry specified by given iterator.
Definition: HashTable.C:440
void operator=(const this_type &rhs)
Copy assign.
bool emplace(const Key &key, Args &&... args)
Emplace insert a new entry, not overwriting existing entries.
Definition: HashTableI.H:157
Base for lists with indirect addressing, templated on the list contents type and the addressing type....
An Istream is an abstract base class for all input systems (streams, files, token lists etc)....
Definition: Istream.H:64
A 1D array of objects of type <T>, where the size of the vector is known and used for subscript bound...
Definition: List.H:77
A min/max value pair with additional methods. In addition to conveniently storing values,...
Definition: MinMax.H:128
An Ostream is an abstract base class for all output systems (streams, files, token lists,...
Definition: Ostream.H:62
A 1D vector of objects of type <T>, where the size of the vector is known and can be used for subscri...
Definition: UList.H:94
OBJstream os(runTime.globalPath()/outputName)
Namespace for OpenFOAM.
label max(const labelHashSet &set, label maxValue=labelMin)
Find the max value in labelHashSet, optionally limited by second argument.
Definition: hashSets.C:47
constexpr label labelMin
Definition: label.H:60
constexpr label labelMax
Definition: label.H:61
Ostream & operator<<(Ostream &, const boundaryPatch &p)
Write boundaryPatch as dictionary entries (without surrounding braces)
Definition: boundaryPatch.C:83
MinMax< label > minMax(const labelHashSet &set)
Find the min/max values of labelHashSet.
Definition: hashSets.C:61
label min(const labelHashSet &set, label minValue=labelMax)
Find the min value in labelHashSet, optionally limited by second argument.
Definition: hashSets.C:33
const direction noexcept
Definition: Scalar.H:223
HashSet< word, Hash< word > > wordHashSet
A HashSet of words, uses string hasher.
Definition: HashSet.H:82
HashSet< label, Hash< label > > labelHashSet
A HashSet of labels, uses label hasher.
Definition: HashSet.H:85
volScalarField & b
Definition: createFields.H:27