19 #ifndef __TPIE_HASHMAP_H__
20 #define __TPIE_HASHMAP_H__
32 #include <tpie/hash.h>
43 template <
typename value_t,
typename hash_t,
typename equal_t,
typename index_t>
46 static const float sc;
95 inline value_t &
get(
size_t idx) {
return buckets[idx].value;}
101 inline const value_t &
get(
size_t idx)
const {
return buckets[idx].value;}
108 for (
size_t i=0; i < buckets.
size(); ++i) {
109 buckets[i].value =
unused;
110 buckets[i].next =
static_cast<index_t
>(i+1);
113 *i = std::numeric_limits<index_t>::max();
122 size_t x=
static_cast<size_t>(99+
static_cast<double>(z)*sc)|1;
138 const equal_t & equal): h(hash), e(equal),
size(0),
unused(u) {
resize(ee);};
144 if (
size == 0)
return buckets.
size();
145 for(
size_t i=0;
true; ++i)
146 if (buckets[i].value !=
unused)
return i;
152 inline size_t end()
const {
return buckets.
size();}
158 inline size_t find(
const value_t & value)
const {
159 size_t v = list[h(value) % list.
size()];
160 while (v != std::numeric_limits<index_t>::max()) {
161 if (e(buckets[v].value, value))
return v;
164 return buckets.
size();
173 inline std::pair<size_t, bool>
insert(
const value_t & val) {
175 size_t hv = h(val) % list.
size();
177 while (v != std::numeric_limits<index_t>::max()) {
178 if (e(buckets[v].value, val))
return std::make_pair(v,
false);
183 first_free = buckets[v].next;
184 buckets[v].value = val;
185 buckets[v].next = list[hv];
188 return std::make_pair(v,
true);
195 inline void erase(
const value_t & val) {
196 size_t hv = h(val) % list.
size();
197 size_t cur = list[hv];
198 size_t prev = std::numeric_limits<size_t>::max();
200 while (!e(buckets[cur].value, val)) {
202 cur = buckets[cur].next;
205 if (prev == std::numeric_limits<size_t>::max())
206 list[hv] = buckets[cur].next;
208 buckets[prev].next = buckets[cur].next;
210 buckets[cur].next = first_free;
211 buckets[cur].value =
unused;
224 template <
typename value_t,
typename hash_t,
typename equal_t,
typename index_t>
227 static const float sc;
269 size_t x=(99+
static_cast<size_t>(
static_cast<float>(element_count)*sc))|1;
279 const hash_t &
hash,
const equal_t & equal):
286 inline size_t find(
const value_t & value)
const {
287 size_t v = h(value) % elements.
size();
288 while (elements[v] !=
unused) {
289 if (e(elements[v], value))
return v;
290 v = (v + 1) % elements.
size();
292 return elements.
size();
300 inline size_t end()
const {
return elements.
size();}
307 if (
size == 0)
return elements.
size();
308 for(
size_t i=0;
true; ++i)
309 if (elements[i] !=
unused)
return i;
316 value_t &
get(
size_t idx) {
return elements[idx];}
322 const value_t &
get(
size_t idx)
const {
return elements[idx];}
328 inline std::pair<size_t, bool>
insert(
const value_t & val) {
329 size_t v = h(val) % elements.
size();
330 while (elements[v] !=
unused) {
331 if (e(elements[v],val)) {
return std::make_pair(v,
false);}
332 v = (v + 1) % elements.
size();
336 return std::make_pair(v,
true);
343 inline void erase(
const value_t & val) {
344 size_t slot =
find(val);
345 size_t cur = (slot+1) % elements.
size();
347 while (elements[cur] !=
unused) {
348 size_t x = h(elements[cur]) % elements.
size();
349 if (x <= slot && (cur > slot || x > cur)) {
350 elements[slot] = elements[cur];
353 cur = (cur+1) % elements.
size();
370 template <
typename key_t,
372 typename hash_t=hash<key_t>,
373 typename equal_t=std::equal_to<key_t>,
374 typename index_t=size_t,
375 template <
typename,
typename,
typename,
typename>
class table_t = chaining_hash_table
379 typedef std::pair<key_t, data_t> value_t;
386 key_equal_t(
const equal_t & equal): e(equal) {}
387 inline bool operator()(
const value_t & a,
const value_t & b)
const {
388 return e(a.first, b.first);
397 key_hash_t(
const hash_t &
hash): h(hash) {}
398 inline size_t operator()(
const value_t & a)
const {
403 typedef table_t<value_t, key_hash_t, key_equal_t, index_t> tbl_t;
410 template <
typename IT>
415 iter_base(IT & t,
size_t c): tbl(t), cur(c) {};
419 inline const key_t & key()
const {
return tbl.get(cur).first;}
420 inline const data_t & value()
const {
return tbl.get(cur).second;}
421 inline const value_t & operator*()
const {
return tbl.get(cur);}
422 inline const value_t * operator->()
const {
return &tbl.get(cur);}
424 template <
typename IIT>
425 inline bool operator==(
const iter_base<IIT> & o)
const {
return o.cur == cur;}
426 template <
typename IIT>
427 inline bool operator!=(
const iter_base<IIT> & o)
const {
return o.cur != cur;}
428 inline void operator++() {
430 while (cur != tbl.end()) {
431 if (tbl.get(cur) != tbl.unused)
break;
445 typedef iter_base<tbl_t> p_t;
447 inline iterator(tbl_t & tbl,
size_t cur): p_t(tbl, cur) {}
451 inline key_t & key() {
return tbl.get(cur)->first;}
452 inline data_t & value() {
return tbl.get(cur)->second;}
453 inline value_t & operator*() {
return tbl.get(cur);}
454 inline value_t * operator->() {
return &tbl.get(cur);}
456 inline bool operator==(
const const_iterator & o)
const {
return o.cur == cur;}
457 inline bool operator!=(
const const_iterator & o)
const {
return o.cur != cur;}
466 return tbl_t::memory_coefficient();
474 return tbl_t::memory_overhead() -
sizeof(tbl_t) +
sizeof(
hash_map);
485 const equal_t & equal=equal_t(),
487 tbl(
size, u, key_hash_t(
hash), key_equal_t(equal)) {}
499 inline void erase(
const key_t & key) {
500 tbl.erase(value_t(key, tbl.unused.second));
514 inline bool insert(
const key_t & key,
const data_t & data) {
515 return tbl.insert(value_t(key, data)).second;
524 return tbl.get(tbl.insert(value_t(key, tbl.unused.second)).first).second;
532 return tbl.get(tbl.find(key))->second;
540 return iterator(tbl, tbl.find(value_t(key, tbl.unused.second)));
548 return const_iterator(tbl, tbl.find(value_t(key, tbl.unused.second)));
557 return tbl.find(value_t(key, tbl.unused.second)) != tbl.end();
593 inline size_t size()
const {
return tbl.size;}
610 template <
typename key_t,
611 typename hash_t=hash<key_t>,
612 typename equal_t=std::equal_to<key_t>,
613 typename index_t=size_t,
614 template <
typename,
typename,
typename,
typename>
class table_t=linear_probing_hash_table>
617 typedef table_t<key_t, hash_t, equal_t, index_t> tbl_t;
619 typedef key_t value_t;
624 template <
typename IT>
629 iter_base(IT & t,
size_t c): tbl(t), cur(c) {};
633 inline const value_t & operator*()
const {
return tbl.get(cur);}
634 inline const value_t * operator->()
const {
return &tbl.get(cur);}
635 inline bool operator==(iter_base & o)
const {
return o.cur == cur;}
636 inline bool operator!=(iter_base & o)
const {
return o.cur != cur;}
637 inline void operator++() {
638 while (cur != tbl.end()) {
640 if (tbl.get(cur) != tbl.unused)
break;
653 typedef iter_base<tbl_t> p_t;
655 inline iterator(tbl_t & tbl,
size_t cur): p_t(tbl, cur) {}
659 inline value_t & operator*() {
return tbl.get(cur);}
660 inline value_t * operator->() {
return &tbl.get(cur);}
662 inline bool operator==(
const const_iterator & o)
const {
return o.cur == cur;}
663 inline bool operator!=(
const const_iterator & o)
const {
return o.cur != cur;}
672 return tbl_t::memory_coefficient();
680 return tbl_t::memory_overhead() -
sizeof(tbl_t) +
sizeof(
hash_set);
691 const hash_t &
hash=hash_t(),
const equal_t & equal=equal_t(),
705 inline void erase(
const key_t & key) {tbl.erase(key);}
718 return tbl.insert(key).second;
726 return iterator(tbl, tbl.find(key));
742 inline bool contains(
const key_t & key)
const {
return tbl.find(key) != tbl.end();}
777 inline size_t size()
const {
return tbl.size;}
782 inline void clear()
const {tbl.clear();}
786 template <
typename value_t,
typename hash_t,
typename equal_t,
typename index_t>
787 const float linear_probing_hash_table<value_t, hash_t, equal_t, index_t>::sc = 2.0f;
789 template <
typename value_t,
typename hash_t,
typename equal_t,
typename index_t>
790 const float chaining_hash_table<value_t, hash_t, equal_t, index_t>::sc = 2.f;
793 #endif //__TPIE_HASHMAP_H__
Hash table handling hash collisions by chaining.
void erase(const iterator &iter)
Erase entry from hash set by iterator.
static double memory_overhead()
Return the memory overhead of the structure.
const_iterator begin() const
Return const iterator to beginning of map.
static double memory_overhead()
Return the memory overhead of the structure.
bool is_prime(size_type i)
Check if i is a prime.
void resize(size_t size)
Resize hash map to given size and remove all entries.
const_iterator find(const key_t &key) const
Get const iterator to element.
void clear() const
Clear hash set.
Base class of data structures with linear memory usage.
static double memory_coefficient()
Return the memory coefficient of the structure.
linear_probing_hash_table(size_t ee, value_t u, const hash_t &hash, const equal_t &equal)
Construct a hash table.
iterator end()
Return iterator to end of set.
Hash map implementation backed by a template parameterized hash table.
iterator begin()
Return iterator to beginning of set.
void resize(size_t element_count)
Resize table to given number of buckets and clear contents.
size_t begin()
Return first bucket entry in use.
static double memory_coefficient()
Return the memory coefficient of the structure.
static double memory_coefficient()
Return the memory coefficient of the structure.
const_iterator cbegin() const
Return const iterator to beginning of set.
data_t & operator[](const key_t &key)
Look up data by key, creating an unused entry if it does not exist.
size_t begin() const
Return first bucket entry in use.
bool contains(const key_t &key) const
Search for key.
size_t size() const
Return number of keys in set.
hash_map(size_t size=0, const hash_t &hash=hash_t(), const equal_t &equal=equal_t(), value_t u=default_unused< value_t >::v())
Construct hash map.
void erase(const key_t &key)
Erase entry from hash map by key.
Generic internal array with known memory requirements.
bool contains(const key_t &key) const
Search for element with key.
iterator find(const key_t &key)
Get iterator to element.
const data_t & operator[](const key_t &key) const
Look up data by key.
const_iterator cend() const
Return const iterator to end of map.
Default tabulation-hashing function for integral (size_t-castable) types.
chaining_hash_table(size_t ee, value_t u, const hash_t &hash, const equal_t &equal)
Construct a hash table.
iterator end()
Return iterator to end of map.
static double memory_overhead()
Return the memory overhead of the structure.
void erase(const value_t &val)
Erase value from table.
size_t end() const
Return index greater than any buckets in use.
void clear()
Clear contents of hash table.
const_iterator end() const
Return const iterator to end of set.
Hash set implementation backed by a template parameterized hash table.
iterator begin()
Return iterator to beginning of map.
void clear()
Clear contents of hash table.
bool insert(const key_t &key)
Insert key into set.
void erase(const iterator &iter)
Erase entry from hash map by iterator.
Computations related to prime numbers.
value_t unused
Special constant indicating an unused table entry.
static double memory_coefficient()
Return the memory coefficient of the structure.
void erase(const value_t &val)
Erase value from table.
void clear()
Clear hash map.
std::pair< size_t, bool > insert(const value_t &val)
Insert value into hash table.
void resize(size_t size, const T &elm)
Change the size of the array.
std::pair< size_t, bool > insert(const value_t &val)
Insert value into hash table.
void erase(const key_t &key)
Erase entry from hash set by key.
size_t size
Number of buckets in hash table.
iter_base< const tbl_t > const_iterator
Const iterator type.
static double memory_overhead()
Return the memory overhead of the structure.
iter_base< const tbl_t > const_iterator
Const iterator type.
static double memory_coefficient()
Return the memory coefficient of the structure.
size_t find(const value_t &value) const
Find bucket entry containing given value, or end() if not found.
const_iterator begin() const
Return const iterator to beginning of set.
hash_set(size_t size=0, const hash_t &hash=hash_t(), const equal_t &equal=equal_t(), value_t u=default_unused< value_t >::v())
Construct hash set.
Hash table handling hash collisions by linear probing.
const_iterator cbegin() const
Return const iterator to beginning of map.
iterator end()
Return an iterator to the end of the array.
const_iterator end() const
Return const iterator to end of map.
size_t size
Number of buckets in hash table.
iterator begin()
Return an iterator to the beginning of the array.
size_type size() const
Return the size of the array.
iterator find(const key_t &key)
Get iterator to element.
static double memory_overhead()
Return the memory overhead of the structure.
const_iterator find(const key_t &key) const
Get iterator to element.
size_t find(const value_t &value) const
Find bucket entry containing given value, or end() if not found.
size_t end() const
Return index greater than any buckets in use.
value_t unused
Special constant indicating an unused table entry.
size_t size() const
Return number of elements in map.
bool insert(const key_t &key, const data_t &data)
Insert data into the hash map.
const_iterator cend() const
Return const iterator to end of set.
void resize(size_t z)
Resize table to given number of buckets and clear contents.
void resize(size_t size)
Resize hash set to given size and remove all entries.
Default special unused values for standard types.