1 // This is free and unencumbered software released into the public domain.
3 // Anyone is free to copy, modify, publish, use, compile, sell, or
4 // distribute this software, either in source code form or as a compiled
5 // binary, for any purpose, commercial or non-commercial, and by any
8 // -------------------------------------------------------
9 // Written by Clifford Wolf <clifford@clifford.at> in 2014
10 // -------------------------------------------------------
22 const int hashtable_size_trigger
= 2;
23 const int hashtable_size_factor
= 3;
25 // The XOR version of DJB2
26 inline unsigned int mkhash(unsigned int a
, unsigned int b
) {
27 return ((a
<< 5) + a
) ^ b
;
30 // traditionally 5381 is used as starting value for the djb2 hash
31 const unsigned int mkhash_init
= 5381;
33 // The ADD version of DJB2
34 // (use this version for cache locality in b)
35 inline unsigned int mkhash_add(unsigned int a
, unsigned int b
) {
36 return ((a
<< 5) + a
) + b
;
39 inline unsigned int mkhash_xorshift(unsigned int a
) {
44 } else if (sizeof(a
) == 8) {
49 throw std::runtime_error("mkhash_xorshift() only implemented for 32 bit and 64 bit ints");
53 template<typename T
> struct hash_ops
{
54 static inline bool cmp(const T
&a
, const T
&b
) {
57 static inline unsigned int hash(const T
&a
) {
64 static inline bool cmp(T a
, T b
) {
69 template<> struct hash_ops
<int32_t> : hash_int_ops
71 static inline unsigned int hash(int32_t a
) {
75 template<> struct hash_ops
<int64_t> : hash_int_ops
77 static inline unsigned int hash(int64_t a
) {
78 return mkhash((unsigned int)(a
), (unsigned int)(a
>> 32));
82 template<> struct hash_ops
<std::string
> {
83 static inline bool cmp(const std::string
&a
, const std::string
&b
) {
86 static inline unsigned int hash(const std::string
&a
) {
94 template<typename P
, typename Q
> struct hash_ops
<std::pair
<P
, Q
>> {
95 static inline bool cmp(std::pair
<P
, Q
> a
, std::pair
<P
, Q
> b
) {
98 static inline unsigned int hash(std::pair
<P
, Q
> a
) {
99 return mkhash(hash_ops
<P
>::hash(a
.first
), hash_ops
<Q
>::hash(a
.second
));
103 template<typename
... T
> struct hash_ops
<std::tuple
<T
...>> {
104 static inline bool cmp(std::tuple
<T
...> a
, std::tuple
<T
...> b
) {
107 template<size_t I
= 0>
108 static inline typename
std::enable_if
<I
== sizeof...(T
), unsigned int>::type
hash(std::tuple
<T
...>) {
111 template<size_t I
= 0>
112 static inline typename
std::enable_if
<I
!= sizeof...(T
), unsigned int>::type
hash(std::tuple
<T
...> a
) {
113 typedef hash_ops
<typename
std::tuple_element
<I
, std::tuple
<T
...>>::type
> element_ops_t
;
114 return mkhash(hash
<I
+1>(a
), element_ops_t::hash(std::get
<I
>(a
)));
118 template<typename T
> struct hash_ops
<std::vector
<T
>> {
119 static inline bool cmp(std::vector
<T
> a
, std::vector
<T
> b
) {
122 static inline unsigned int hash(std::vector
<T
> a
) {
123 unsigned int h
= mkhash_init
;
125 h
= mkhash(h
, hash_ops
<T
>::hash(k
));
130 struct hash_cstr_ops
{
131 static inline bool cmp(const char *a
, const char *b
) {
132 for (int i
= 0; a
[i
] || b
[i
]; i
++)
137 static inline unsigned int hash(const char *a
) {
138 unsigned int hash
= mkhash_init
;
140 hash
= mkhash(hash
, *(a
++));
145 struct hash_ptr_ops
{
146 static inline bool cmp(const void *a
, const void *b
) {
149 static inline unsigned int hash(const void *a
) {
154 struct hash_obj_ops
{
155 static inline bool cmp(const void *a
, const void *b
) {
159 static inline unsigned int hash(const T
*a
) {
160 return a
? a
->hash() : 0;
165 inline unsigned int mkhash(const T
&v
) {
166 return hash_ops
<T
>().hash(v
);
169 inline int hashtable_size(int min_size
)
171 static std::vector
<int> zero_and_some_primes
= {
172 0, 23, 29, 37, 47, 59, 79, 101, 127, 163, 211, 269, 337, 431, 541, 677,
173 853, 1069, 1361, 1709, 2137, 2677, 3347, 4201, 5261, 6577, 8231, 10289,
174 12889, 16127, 20161, 25219, 31531, 39419, 49277, 61603, 77017, 96281,
175 120371, 150473, 188107, 235159, 293957, 367453, 459317, 574157, 717697,
176 897133, 1121423, 1401791, 1752239, 2190299, 2737937, 3422429, 4278037,
177 5347553, 6684443, 8355563, 10444457, 13055587, 16319519, 20399411,
178 25499291, 31874149, 39842687, 49803361, 62254207, 77817767, 97272239,
179 121590311, 151987889, 189984863, 237481091, 296851369, 371064217
182 for (auto p
: zero_and_some_primes
)
183 if (p
>= min_size
) return p
;
185 if (sizeof(int) == 4)
186 throw std::length_error("hash table exceeded maximum size. use a ILP64 abi for larger tables.");
188 for (auto p
: zero_and_some_primes
)
189 if (100129 * p
> min_size
) return 100129 * p
;
191 throw std::length_error("hash table exceeded maximum size.");
194 template<typename K
, typename T
, typename OPS
= hash_ops
<K
>> class dict
;
195 template<typename K
, int offset
= 0, typename OPS
= hash_ops
<K
>> class idict
;
196 template<typename K
, typename OPS
= hash_ops
<K
>> class pool
;
197 template<typename K
, typename OPS
= hash_ops
<K
>> class mfp
;
199 template<typename K
, typename T
, typename OPS
>
204 std::pair
<K
, T
> udata
;
208 entry_t(const std::pair
<K
, T
> &udata
, int next
) : udata(udata
), next(next
) { }
209 entry_t(std::pair
<K
, T
> &&udata
, int next
) : udata(std::move(udata
)), next(next
) { }
212 std::vector
<int> hashtable
;
213 std::vector
<entry_t
> entries
;
217 static inline void do_assert(bool) { }
219 static inline void do_assert(bool cond
) {
220 if (!cond
) throw std::runtime_error("dict<> assert failed.");
224 int do_hash(const K
&key
) const
226 unsigned int hash
= 0;
227 if (!hashtable
.empty())
228 hash
= ops
.hash(key
) % (unsigned int)(hashtable
.size());
235 hashtable
.resize(hashtable_size(entries
.capacity() * hashtable_size_factor
), -1);
237 for (int i
= 0; i
< int(entries
.size()); i
++) {
238 do_assert(-1 <= entries
[i
].next
&& entries
[i
].next
< int(entries
.size()));
239 int hash
= do_hash(entries
[i
].udata
.first
);
240 entries
[i
].next
= hashtable
[hash
];
245 int do_erase(int index
, int hash
)
247 do_assert(index
< int(entries
.size()));
248 if (hashtable
.empty() || index
< 0)
251 int k
= hashtable
[hash
];
252 do_assert(0 <= k
&& k
< int(entries
.size()));
255 hashtable
[hash
] = entries
[index
].next
;
257 while (entries
[k
].next
!= index
) {
259 do_assert(0 <= k
&& k
< int(entries
.size()));
261 entries
[k
].next
= entries
[index
].next
;
264 int back_idx
= entries
.size()-1;
266 if (index
!= back_idx
)
268 int back_hash
= do_hash(entries
[back_idx
].udata
.first
);
270 k
= hashtable
[back_hash
];
271 do_assert(0 <= k
&& k
< int(entries
.size()));
274 hashtable
[back_hash
] = index
;
276 while (entries
[k
].next
!= back_idx
) {
278 do_assert(0 <= k
&& k
< int(entries
.size()));
280 entries
[k
].next
= index
;
283 entries
[index
] = std::move(entries
[back_idx
]);
294 int do_lookup(const K
&key
, int &hash
) const
296 if (hashtable
.empty())
299 if (entries
.size() * hashtable_size_trigger
> hashtable
.size()) {
300 ((dict
*)this)->do_rehash();
304 int index
= hashtable
[hash
];
306 while (index
>= 0 && !ops
.cmp(entries
[index
].udata
.first
, key
)) {
307 index
= entries
[index
].next
;
308 do_assert(-1 <= index
&& index
< int(entries
.size()));
314 int do_insert(const K
&key
, int &hash
)
316 if (hashtable
.empty()) {
317 entries
.push_back(entry_t(std::pair
<K
, T
>(key
, T()), -1));
321 entries
.push_back(entry_t(std::pair
<K
, T
>(key
, T()), hashtable
[hash
]));
322 hashtable
[hash
] = entries
.size() - 1;
324 return entries
.size() - 1;
327 int do_insert(const std::pair
<K
, T
> &value
, int &hash
)
329 if (hashtable
.empty()) {
330 entries
.push_back(entry_t(value
, -1));
332 hash
= do_hash(value
.first
);
334 entries
.push_back(entry_t(value
, hashtable
[hash
]));
335 hashtable
[hash
] = entries
.size() - 1;
337 return entries
.size() - 1;
341 class const_iterator
: public std::iterator
<std::forward_iterator_tag
, std::pair
<K
, T
>>
347 const_iterator(const dict
*ptr
, int index
) : ptr(ptr
), index(index
) { }
350 const_iterator
operator++() { index
--; return *this; }
351 bool operator<(const const_iterator
&other
) const { return index
> other
.index
; }
352 bool operator==(const const_iterator
&other
) const { return index
== other
.index
; }
353 bool operator!=(const const_iterator
&other
) const { return index
!= other
.index
; }
354 const std::pair
<K
, T
> &operator*() const { return ptr
->entries
[index
].udata
; }
355 const std::pair
<K
, T
> *operator->() const { return &ptr
->entries
[index
].udata
; }
358 class iterator
: public std::iterator
<std::forward_iterator_tag
, std::pair
<K
, T
>>
364 iterator(dict
*ptr
, int index
) : ptr(ptr
), index(index
) { }
367 iterator
operator++() { index
--; return *this; }
368 bool operator<(const iterator
&other
) const { return index
> other
.index
; }
369 bool operator==(const iterator
&other
) const { return index
== other
.index
; }
370 bool operator!=(const iterator
&other
) const { return index
!= other
.index
; }
371 std::pair
<K
, T
> &operator*() { return ptr
->entries
[index
].udata
; }
372 std::pair
<K
, T
> *operator->() { return &ptr
->entries
[index
].udata
; }
373 const std::pair
<K
, T
> &operator*() const { return ptr
->entries
[index
].udata
; }
374 const std::pair
<K
, T
> *operator->() const { return &ptr
->entries
[index
].udata
; }
375 operator const_iterator() const { return const_iterator(ptr
, index
); }
382 dict(const dict
&other
)
384 entries
= other
.entries
;
393 dict
&operator=(const dict
&other
) {
394 entries
= other
.entries
;
399 dict
&operator=(dict
&&other
) {
405 dict(const std::initializer_list
<std::pair
<K
, T
>> &list
)
407 for (auto &it
: list
)
411 template<class InputIterator
>
412 dict(InputIterator first
, InputIterator last
)
417 template<class InputIterator
>
418 void insert(InputIterator first
, InputIterator last
)
420 for (; first
!= last
; ++first
)
424 std::pair
<iterator
, bool> insert(const K
&key
)
426 int hash
= do_hash(key
);
427 int i
= do_lookup(key
, hash
);
429 return std::pair
<iterator
, bool>(iterator(this, i
), false);
430 i
= do_insert(key
, hash
);
431 return std::pair
<iterator
, bool>(iterator(this, i
), true);
434 std::pair
<iterator
, bool> insert(const std::pair
<K
, T
> &value
)
436 int hash
= do_hash(value
.first
);
437 int i
= do_lookup(value
.first
, hash
);
439 return std::pair
<iterator
, bool>(iterator(this, i
), false);
440 i
= do_insert(value
, hash
);
441 return std::pair
<iterator
, bool>(iterator(this, i
), true);
444 int erase(const K
&key
)
446 int hash
= do_hash(key
);
447 int index
= do_lookup(key
, hash
);
448 return do_erase(index
, hash
);
451 iterator
erase(iterator it
)
453 int hash
= do_hash(it
->first
);
454 do_erase(it
.index
, hash
);
458 int count(const K
&key
) const
460 int hash
= do_hash(key
);
461 int i
= do_lookup(key
, hash
);
462 return i
< 0 ? 0 : 1;
465 int count(const K
&key
, const_iterator it
) const
467 int hash
= do_hash(key
);
468 int i
= do_lookup(key
, hash
);
469 return i
< 0 || i
> it
.index
? 0 : 1;
472 iterator
find(const K
&key
)
474 int hash
= do_hash(key
);
475 int i
= do_lookup(key
, hash
);
478 return iterator(this, i
);
481 const_iterator
find(const K
&key
) const
483 int hash
= do_hash(key
);
484 int i
= do_lookup(key
, hash
);
487 return const_iterator(this, i
);
492 int hash
= do_hash(key
);
493 int i
= do_lookup(key
, hash
);
495 throw std::out_of_range("dict::at()");
496 return entries
[i
].udata
.second
;
499 const T
& at(const K
&key
) const
501 int hash
= do_hash(key
);
502 int i
= do_lookup(key
, hash
);
504 throw std::out_of_range("dict::at()");
505 return entries
[i
].udata
.second
;
508 T
at(const K
&key
, const T
&defval
) const
510 int hash
= do_hash(key
);
511 int i
= do_lookup(key
, hash
);
514 return entries
[i
].udata
.second
;
517 T
& operator[](const K
&key
)
519 int hash
= do_hash(key
);
520 int i
= do_lookup(key
, hash
);
522 i
= do_insert(std::pair
<K
, T
>(key
, T()), hash
);
523 return entries
[i
].udata
.second
;
526 template<typename Compare
= std::less
<K
>>
527 void sort(Compare comp
= Compare())
529 std::sort(entries
.begin(), entries
.end(), [comp
](const entry_t
&a
, const entry_t
&b
){ return comp(b
.udata
.first
, a
.udata
.first
); });
533 void swap(dict
&other
)
535 hashtable
.swap(other
.hashtable
);
536 entries
.swap(other
.entries
);
539 bool operator==(const dict
&other
) const {
540 if (size() != other
.size())
542 for (auto &it
: entries
) {
543 auto oit
= other
.find(it
.udata
.first
);
544 if (oit
== other
.end() || !(oit
->second
== it
.udata
.second
))
550 bool operator!=(const dict
&other
) const {
551 return !operator==(other
);
554 void reserve(size_t n
) { entries
.reserve(n
); }
555 size_t size() const { return entries
.size(); }
556 bool empty() const { return entries
.empty(); }
557 void clear() { hashtable
.clear(); entries
.clear(); }
559 iterator
begin() { return iterator(this, int(entries
.size())-1); }
560 iterator
element(int n
) { return iterator(this, int(entries
.size())-1-n
); }
561 iterator
end() { return iterator(nullptr, -1); }
563 const_iterator
begin() const { return const_iterator(this, int(entries
.size())-1); }
564 const_iterator
element(int n
) const { return const_iterator(this, int(entries
.size())-1-n
); }
565 const_iterator
end() const { return const_iterator(nullptr, -1); }
568 template<typename K
, typename OPS
>
571 template<typename
, int, typename
> friend class idict
;
580 entry_t(const K
&udata
, int next
) : udata(udata
), next(next
) { }
583 std::vector
<int> hashtable
;
584 std::vector
<entry_t
> entries
;
588 static inline void do_assert(bool) { }
590 static inline void do_assert(bool cond
) {
591 if (!cond
) throw std::runtime_error("pool<> assert failed.");
595 int do_hash(const K
&key
) const
597 unsigned int hash
= 0;
598 if (!hashtable
.empty())
599 hash
= ops
.hash(key
) % (unsigned int)(hashtable
.size());
606 hashtable
.resize(hashtable_size(entries
.capacity() * hashtable_size_factor
), -1);
608 for (int i
= 0; i
< int(entries
.size()); i
++) {
609 do_assert(-1 <= entries
[i
].next
&& entries
[i
].next
< int(entries
.size()));
610 int hash
= do_hash(entries
[i
].udata
);
611 entries
[i
].next
= hashtable
[hash
];
616 int do_erase(int index
, int hash
)
618 do_assert(index
< int(entries
.size()));
619 if (hashtable
.empty() || index
< 0)
622 int k
= hashtable
[hash
];
624 hashtable
[hash
] = entries
[index
].next
;
626 while (entries
[k
].next
!= index
) {
628 do_assert(0 <= k
&& k
< int(entries
.size()));
630 entries
[k
].next
= entries
[index
].next
;
633 int back_idx
= entries
.size()-1;
635 if (index
!= back_idx
)
637 int back_hash
= do_hash(entries
[back_idx
].udata
);
639 k
= hashtable
[back_hash
];
641 hashtable
[back_hash
] = index
;
643 while (entries
[k
].next
!= back_idx
) {
645 do_assert(0 <= k
&& k
< int(entries
.size()));
647 entries
[k
].next
= index
;
650 entries
[index
] = std::move(entries
[back_idx
]);
661 int do_lookup(const K
&key
, int &hash
) const
663 if (hashtable
.empty())
666 if (entries
.size() * hashtable_size_trigger
> hashtable
.size()) {
667 ((pool
*)this)->do_rehash();
671 int index
= hashtable
[hash
];
673 while (index
>= 0 && !ops
.cmp(entries
[index
].udata
, key
)) {
674 index
= entries
[index
].next
;
675 do_assert(-1 <= index
&& index
< int(entries
.size()));
681 int do_insert(const K
&value
, int &hash
)
683 if (hashtable
.empty()) {
684 entries
.push_back(entry_t(value
, -1));
686 hash
= do_hash(value
);
688 entries
.push_back(entry_t(value
, hashtable
[hash
]));
689 hashtable
[hash
] = entries
.size() - 1;
691 return entries
.size() - 1;
695 class const_iterator
: public std::iterator
<std::forward_iterator_tag
, K
>
701 const_iterator(const pool
*ptr
, int index
) : ptr(ptr
), index(index
) { }
704 const_iterator
operator++() { index
--; return *this; }
705 bool operator==(const const_iterator
&other
) const { return index
== other
.index
; }
706 bool operator!=(const const_iterator
&other
) const { return index
!= other
.index
; }
707 const K
&operator*() const { return ptr
->entries
[index
].udata
; }
708 const K
*operator->() const { return &ptr
->entries
[index
].udata
; }
711 class iterator
: public std::iterator
<std::forward_iterator_tag
, K
>
717 iterator(pool
*ptr
, int index
) : ptr(ptr
), index(index
) { }
720 iterator
operator++() { index
--; return *this; }
721 bool operator==(const iterator
&other
) const { return index
== other
.index
; }
722 bool operator!=(const iterator
&other
) const { return index
!= other
.index
; }
723 K
&operator*() { return ptr
->entries
[index
].udata
; }
724 K
*operator->() { return &ptr
->entries
[index
].udata
; }
725 const K
&operator*() const { return ptr
->entries
[index
].udata
; }
726 const K
*operator->() const { return &ptr
->entries
[index
].udata
; }
727 operator const_iterator() const { return const_iterator(ptr
, index
); }
734 pool(const pool
&other
)
736 entries
= other
.entries
;
745 pool
&operator=(const pool
&other
) {
746 entries
= other
.entries
;
751 pool
&operator=(pool
&&other
) {
757 pool(const std::initializer_list
<K
> &list
)
759 for (auto &it
: list
)
763 template<class InputIterator
>
764 pool(InputIterator first
, InputIterator last
)
769 template<class InputIterator
>
770 void insert(InputIterator first
, InputIterator last
)
772 for (; first
!= last
; ++first
)
776 std::pair
<iterator
, bool> insert(const K
&value
)
778 int hash
= do_hash(value
);
779 int i
= do_lookup(value
, hash
);
781 return std::pair
<iterator
, bool>(iterator(this, i
), false);
782 i
= do_insert(value
, hash
);
783 return std::pair
<iterator
, bool>(iterator(this, i
), true);
786 int erase(const K
&key
)
788 int hash
= do_hash(key
);
789 int index
= do_lookup(key
, hash
);
790 return do_erase(index
, hash
);
793 iterator
erase(iterator it
)
795 int hash
= do_hash(*it
);
796 do_erase(it
.index
, hash
);
800 int count(const K
&key
) const
802 int hash
= do_hash(key
);
803 int i
= do_lookup(key
, hash
);
804 return i
< 0 ? 0 : 1;
807 int count(const K
&key
, const_iterator it
) const
809 int hash
= do_hash(key
);
810 int i
= do_lookup(key
, hash
);
811 return i
< 0 || i
> it
.index
? 0 : 1;
814 iterator
find(const K
&key
)
816 int hash
= do_hash(key
);
817 int i
= do_lookup(key
, hash
);
820 return iterator(this, i
);
823 const_iterator
find(const K
&key
) const
825 int hash
= do_hash(key
);
826 int i
= do_lookup(key
, hash
);
829 return const_iterator(this, i
);
832 bool operator[](const K
&key
)
834 int hash
= do_hash(key
);
835 int i
= do_lookup(key
, hash
);
839 template<typename Compare
= std::less
<K
>>
840 void sort(Compare comp
= Compare())
842 std::sort(entries
.begin(), entries
.end(), [comp
](const entry_t
&a
, const entry_t
&b
){ return comp(b
.udata
, a
.udata
); });
848 iterator it
= begin();
854 void swap(pool
&other
)
856 hashtable
.swap(other
.hashtable
);
857 entries
.swap(other
.entries
);
860 bool operator==(const pool
&other
) const {
861 if (size() != other
.size())
863 for (auto &it
: entries
)
864 if (!other
.count(it
.udata
))
869 bool operator!=(const pool
&other
) const {
870 return !operator==(other
);
874 unsigned int hashval
= mkhash_init
;
875 for (auto &it
: entries
)
876 hashval
^= ops
.hash(it
.udata
);
880 void reserve(size_t n
) { entries
.reserve(n
); }
881 size_t size() const { return entries
.size(); }
882 bool empty() const { return entries
.empty(); }
883 void clear() { hashtable
.clear(); entries
.clear(); }
885 iterator
begin() { return iterator(this, int(entries
.size())-1); }
886 iterator
element(int n
) { return iterator(this, int(entries
.size())-1-n
); }
887 iterator
end() { return iterator(nullptr, -1); }
889 const_iterator
begin() const { return const_iterator(this, int(entries
.size())-1); }
890 const_iterator
element(int n
) const { return const_iterator(this, int(entries
.size())-1-n
); }
891 const_iterator
end() const { return const_iterator(nullptr, -1); }
894 template<typename K
, int offset
, typename OPS
>
897 pool
<K
, OPS
> database
;
900 typedef typename pool
<K
, OPS
>::const_iterator const_iterator
;
902 int operator()(const K
&key
)
904 int hash
= database
.do_hash(key
);
905 int i
= database
.do_lookup(key
, hash
);
907 i
= database
.do_insert(key
, hash
);
911 int at(const K
&key
) const
913 int hash
= database
.do_hash(key
);
914 int i
= database
.do_lookup(key
, hash
);
916 throw std::out_of_range("idict::at()");
920 int at(const K
&key
, int defval
) const
922 int hash
= database
.do_hash(key
);
923 int i
= database
.do_lookup(key
, hash
);
929 int count(const K
&key
) const
931 int hash
= database
.do_hash(key
);
932 int i
= database
.do_lookup(key
, hash
);
933 return i
< 0 ? 0 : 1;
936 void expect(const K
&key
, int i
)
938 int j
= (*this)(key
);
940 throw std::out_of_range("idict::expect()");
943 const K
&operator[](int index
) const
945 return database
.entries
.at(index
- offset
).udata
;
948 void swap(idict
&other
)
950 database
.swap(other
.database
);
953 void reserve(size_t n
) { database
.reserve(n
); }
954 size_t size() const { return database
.size(); }
955 bool empty() const { return database
.empty(); }
956 void clear() { database
.clear(); }
958 const_iterator
begin() const { return database
.begin(); }
959 const_iterator
element(int n
) const { return database
.element(n
); }
960 const_iterator
end() const { return database
.end(); }
963 template<typename K
, typename OPS
>
966 mutable idict
<K
, 0, OPS
> database
;
967 mutable std::vector
<int> parents
;
970 typedef typename idict
<K
, 0, OPS
>::const_iterator const_iterator
;
972 int operator()(const K
&key
) const
974 int i
= database(key
);
975 parents
.resize(database
.size(), -1);
979 const K
&operator[](int index
) const
981 return database
[index
];
984 int ifind(int i
) const
988 while (parents
[p
] != -1)
992 int next_k
= parents
[k
];
1000 void imerge(int i
, int j
)
1009 void ipromote(int i
)
1014 int next_k
= parents
[k
];
1022 int lookup(const K
&a
) const
1024 return ifind((*this)(a
));
1027 const K
&find(const K
&a
) const
1029 int i
= database
.at(a
, -1);
1032 return (*this)[ifind(i
)];
1035 void merge(const K
&a
, const K
&b
)
1037 imerge((*this)(a
), (*this)(b
));
1040 void promote(const K
&a
)
1042 int i
= database
.at(a
, -1);
1047 void swap(mfp
&other
)
1049 database
.swap(other
.database
);
1050 parents
.swap(other
.parents
);
1053 void reserve(size_t n
) { database
.reserve(n
); }
1054 size_t size() const { return database
.size(); }
1055 bool empty() const { return database
.empty(); }
1056 void clear() { database
.clear(); parents
.clear(); }
1058 const_iterator
begin() const { return database
.begin(); }
1059 const_iterator
element(int n
) const { return database
.element(n
); }
1060 const_iterator
end() const { return database
.end(); }
1063 } /* namespace hashlib */