29 #ifndef Foam_HashTable_C 30 #define Foam_HashTable_C 39 template<
class T,
class Key,
class Hash>
46 template<
class T,
class Key,
class Hash>
56 table_ =
new node_type*[capacity_];
57 for (label i=0; i < capacity_; ++i)
65 template<
class T,
class Key,
class Hash>
68 HashTable<
T, Key, Hash>(ht.capacity_)
70 for (const_iterator iter = ht.cbegin(); iter != ht.cend(); ++iter)
72 insert(iter.key(), iter.val());
77 template<
class T,
class Key,
class Hash>
82 capacity_(rhs.capacity_),
91 template<
class T,
class Key,
class Hash>
94 std::initializer_list<std::pair<Key, T>> list
99 for (
const auto& keyval : list)
101 set(keyval.first, keyval.second);
108 template<
class T,
class Key,
class Hash>
121 template<
class T,
class Key,
class Hash>
124 List<Key> list(size_);
127 for (const_iterator iter =
cbegin(); iter !=
cend(); ++iter)
129 list[
count++] = iter.key();
136 template<
class T,
class Key,
class Hash>
139 List<Key> list(this->
toc());
146 template<
class T,
class Key,
class Hash>
147 template<
class Compare>
160 template<
class T,
class Key,
class Hash>
168 for (const_iterator iter =
cbegin(); iter !=
cend(); ++iter)
179 template<
class T,
class Key,
class Hash>
187 template<
class T,
class Key,
class Hash>
195 for (iterator iter =
begin(); iter !=
end(); ++iter)
197 result.set(
count++, iter.node());
207 template<
class T,
class Key,
class Hash>
208 template<
class UnaryPredicate>
211 const UnaryPredicate& pred,
218 for (const_iterator iter =
cbegin(); iter !=
cend(); ++iter)
222 list[
count++] = iter.key();
233 template<
class T,
class Key,
class Hash>
234 template<
class UnaryPredicate>
237 const UnaryPredicate& pred,
244 for (const_iterator iter =
cbegin(); iter !=
cend(); ++iter)
248 list[
count++] = iter.key();
259 template<
class T,
class Key,
class Hash>
260 template<
class BinaryPredicate>
263 const BinaryPredicate& pred,
270 for (const_iterator iter =
cbegin(); iter !=
cend(); ++iter)
274 list[
count++] = iter.key();
285 template<
class T,
class Key,
class Hash>
286 template<
class UnaryPredicate>
289 const UnaryPredicate& pred,
295 for (const_iterator iter =
cbegin(); iter !=
cend(); ++iter)
307 template<
class T,
class Key,
class Hash>
308 template<
class UnaryPredicate>
311 const UnaryPredicate& pred,
317 for (const_iterator iter =
cbegin(); iter !=
cend(); ++iter)
329 template<
class T,
class Key,
class Hash>
330 template<
class BinaryPredicate>
333 const BinaryPredicate& pred,
339 for (const_iterator iter =
cbegin(); iter !=
cend(); ++iter)
351 template<
class T,
class Key,
class Hash>
352 template<
class... Args>
355 const bool overwrite,
365 const label index = hashKeyIndex(
key);
367 node_type* curr =
nullptr;
368 node_type* prev =
nullptr;
370 for (node_type* ep = table_[index]; ep; ep = ep->next_)
372 if (
key == ep->key())
384 new node_type(table_[index],
key, std::forward<Args>(
args)...);
387 if (
double(size_)/capacity_ > 0.8 && capacity_ < maxTableSize)
402 if (!node_type::stores_value())
407 node_type* ep = curr->next_;
414 ep =
new node_type(ep,
key, std::forward<Args>(
args)...);
439 template<
class T,
class Key,
class Hash>
447 iterator& it =
const_cast<iterator&
>(iter);
449 return iterator_erase(it.entry_, it.index_);
453 template<
class T,
class Key,
class Hash>
461 template<
class T,
class Key,
class Hash>
462 template<
class InputIter>
473 const label nTotal = this->size();
474 changed < nTotal && first != last;
478 if (this->
erase(*first))
488 template<
class T,
class Key,
class Hash>
491 std::initializer_list<Key> keys
494 return erase(keys.begin(), keys.end());
498 template<
class T,
class Key,
class Hash>
509 template<
class T,
class Key,
class Hash>
519 template<
class T,
class Key,
class Hash>
520 template<
class AnyType,
class AnyHash>
526 const label nTotal = this->size();
529 if (other.
size() <= nTotal)
535 auto iter = other.
cbegin();
536 changed < nTotal && iter != other.
cend();
540 if (
erase(iter.key()))
551 iterator iter =
begin();
552 changed < nTotal && iter !=
end();
567 template<
class T,
class Key,
class Hash>
568 template<
class AnyType,
class AnyHash>
574 const label nTotal = this->size();
587 for (iterator iter =
begin(); iter !=
end(); ++iter)
600 template<
class T,
class Key,
class Hash>
603 const label newCapacity = HashTableCore::canonicalSize(sz);
604 const label oldCapacity = capacity_;
606 if (newCapacity == oldCapacity)
614 else if (!newCapacity)
620 <<
"HashTable contains " << size_ <<
" cannot resize(0)" <<
nl;
638 auto oldTable = table_;
639 capacity_ = newCapacity;
641 table_ =
new node_type*[capacity_];
642 for (label i=0; i < capacity_; ++i)
650 for (label i=0; nMove && i < oldCapacity; ++i)
652 for (node_type* ep = oldTable[i]; ep; )
654 node_type* next = ep->next_;
658 const label newIdx = hashKeyIndex(ep->key());
660 ep->next_ = table_[newIdx];
667 oldTable[i] =
nullptr;
677 template<
class T,
class Key,
class Hash>
680 for (label i=0; size_ && i<capacity_; ++i)
682 for (node_type* ep = table_[i]; ep; )
684 node_type* next = ep->next_;
696 template<
class T,
class Key,
class Hash>
704 template<
class T,
class Key,
class Hash>
712 std::swap(size_, rhs.size_);
713 std::swap(capacity_, rhs.capacity_);
714 std::swap(table_, rhs.table_);
718 template<
class T,
class Key,
class Hash>
731 template<
class T,
class Key,
class Hash>
732 template<
class UnaryPredicate>
735 const UnaryPredicate& pred,
741 for (iterator iter =
begin(); iter !=
end(); ++iter)
746 (pred(iter.key()) ? pruning : !pruning)
758 template<
class T,
class Key,
class Hash>
759 template<
class UnaryPredicate>
762 const UnaryPredicate& pred,
768 for (iterator iter =
begin(); iter !=
end(); ++iter)
773 (pred(iter.val()) ? pruning : !pruning)
785 template<
class T,
class Key,
class Hash>
786 template<
class BinaryPredicate>
789 const BinaryPredicate& pred,
795 for (iterator iter =
begin(); iter !=
end(); ++iter)
800 (pred(iter.key(), iter.val()) ? pruning : !pruning)
814 template<
class T,
class Key,
class Hash>
817 const HashTable<T, Key, Hash>& rhs
835 for (const_iterator iter = rhs.
cbegin(); iter != rhs.
cend(); ++iter)
842 template<
class T,
class Key,
class Hash>
845 std::initializer_list<std::pair<Key, T>> rhs
858 for (
const auto& keyval : rhs)
860 set(keyval.first, keyval.second);
865 template<
class T,
class Key,
class Hash>
868 HashTable<T, Key, Hash>&& rhs
880 template<
class T,
class Key,
class Hash>
887 if (size() != rhs.
size())
892 for (const_iterator iter = rhs.
cbegin(); iter != rhs.
cend(); ++iter)
894 const const_iterator other(this->cfind(iter.key()));
896 if (!other.good() || other.val() != iter.val())
906 template<
class T,
class Key,
class Hash>
916 template<
class T,
class Key,
class Hash>
923 if (rhs.
size() ||
this != &rhs)
927 for (const_iterator iter = rhs.
cbegin(); iter != rhs.
cend(); ++iter)
929 insert(iter.key(), iter.val());
label countValues(const UnaryPredicate &pred, const bool invert=false) const
Count the number of values that satisfy the unary predicate.
label find(const ListType &input, const UnaryPredicate &pred, const label start=0)
Same as ListOps::find_if.
List< Key > tocKeys(const UnaryPredicate &pred, const bool invert=false) const
The table of contents (the keys) selected according to the unary predicate applied to the keys...
const_iterator cend() const noexcept
Return const_iterator to end traversing the constant UList.
patchWriters resize(patchIds.size())
label filterValues(const UnaryPredicate &pred, const bool pruning=false)
Generalized means to filter table entries based on their values.
A 1D vector of objects of type <T> with a fixed length <N>.
void resize(const label len)
Adjust allocated size of list.
label retain(const HashTable< AnyType, Key, AnyHash > &other)
Retain table entries given by keys of the other hash-table.
bool found(const Key &key) const
True if hashed key is found in table.
A 1D array of objects of type <T>, where the size of the vector is known and used for subscript bound...
srcOptions insert("case", fileName(rootDirSource/caseDirSource))
constexpr char nl
The newline '\n' character (0x0a)
UPtrList< const node_type > csorted() const
Const access to the hash-table contents in sorted order (sorted by keys).
label size() const noexcept
The number of elements in table.
void resize(const label sz)
Resize the hash table for efficiency.
const T * set(const label i) const
Return const pointer to element (can be nullptr), or nullptr for out-of-range access (ie...
List< Key > tocEntries(const BinaryPredicate &pred, const bool invert=false) const
The table of contents (the keys) selected according to the binary predicate applied to the keys and v...
label countEntries(const BinaryPredicate &pred, const bool invert=false) const
Count the number of entries that satisfy the binary predicate.
void swap(HashTable< T, Key, Hash > &rhs)
Swap contents into this table.
unsigned int count(const UList< bool > &bools, const bool val=true)
Count number of 'true' entries.
label filterEntries(const BinaryPredicate &pred, const bool pruning=false)
Generalized means to filter table entries based on their key/value.
#define DebugInFunction
Report an information message using Foam::Info.
void sort(UList< T > &list)
Sort the list.
void clear()
Clear all entries from table.
constexpr auto cend(const C &c) -> decltype(c.end())
Return const_iterator to the end of the container c.
label countKeys(const UnaryPredicate &pred, const bool invert=false) const
Count the number of keys that satisfy the unary predicate.
A HashTable similar to std::unordered_map.
A list of pointers to objects of type <T>, without allocation/deallocation management of the pointers...
A 1D vector of objects of type <T>, where the size of the vector is known and can be used for subscri...
bool empty() const noexcept
True if the hash table is empty.
constexpr auto end(C &c) -> decltype(c.end())
Return iterator to the end of the container c.
HashTable()
Default construct with default (128) table capacity.
constexpr auto cbegin(const C &c) -> decltype(c.begin())
Return const_iterator to the beginning of the container c.
const_iterator cbegin() const noexcept
Return const_iterator to begin traversing the constant FixedList.
bool erase(const iterator &iter)
Erase an entry specified by given iterator.
labelList invert(const label len, const labelUList &map)
Create an inverse one-to-one mapping.
Bits that are independent of HashTable template parameters.
#define WarningInFunction
Report a warning using Foam::Warning.
Hash function class. The default definition is for primitives. Non-primitives used to hash entries on...
auto key(const Type &t) -> typename std::enable_if< std::is_enum< Type >::value, typename std::underlying_type< Type >::type >::type
List< Key > sortedToc() const
The table of contents (the keys) in sorted order.
void transfer(HashTable< T, Key, Hash > &rhs)
Transfer contents into this table.
UPtrList< const node_type > sorted() const
Const access to the hash-table contents in sorted order (sorted by keys).
label filterKeys(const UnaryPredicate &pred, const bool pruning=false)
Generalized means to filter table entries based on their keys.
const_iterator cbegin() const noexcept
Return const_iterator to begin traversing the constant UList.
const_iterator cend() const noexcept
Return const_iterator to end traversing the constant FixedList.
List< Key > toc() const
The table of contents (the keys) in unsorted order.
tmp< faMatrix< Type > > operator==(const faMatrix< Type > &, const faMatrix< Type > &)
const_iterator cbegin() const
const_iterator set to the beginning of the HashTable
Foam::argList args(argc, argv)
constexpr auto begin(C &c) -> decltype(c.begin())
Return iterator to the beginning of the container c.
List< label > toc(const UList< bool > &bools)
Return the (sorted) values corresponding to 'true' entries.
constexpr const_iterator cend() const noexcept
const_iterator to signal the end (for any HashTable)
void clearStorage()
Clear the table entries and the table itself.
List< Key > tocValues(const UnaryPredicate &pred, const bool invert=false) const
The table of contents (the keys) selected according to the unary predicate applied to the values...