21 #ifndef FST_BI_TABLE_H_ 22 #define FST_BI_TABLE_H_ 24 #include <sys/types.h> 31 #include <type_traits> 32 #include <unordered_set> 38 #include <unordered_map> 39 #include <unordered_set> 68 template <
class I,
class T,
class H = std::hash<T>,
class E = std::equal_to<T>>
76 entry2id_(table_size, hash_func_, hash_equal_) {
77 if (table_size) id2entry_.reserve(table_size);
81 : hash_func_(table.hash_func_),
82 hash_equal_(table.hash_equal_),
83 entry2id_(table.entry2id_.begin(), table.entry2id_.end(),
84 table.entry2id_.size(), hash_func_, hash_equal_),
85 id2entry_(table.id2entry_) {}
87 I
FindId(
const T &entry,
bool insert =
true) {
89 const auto it = entry2id_.find(entry);
90 return it == entry2id_.end() ? -1 : it->second - 1;
92 I &id_ref = entry2id_[entry];
94 id2entry_.push_back(entry);
95 id_ref = id2entry_.size();
102 I
Size()
const {
return id2entry_.size(); }
113 std::unordered_map<T, I, H, E> entry2id_;
114 std::vector<T> id2entry_;
121 template <
class K,
class H,
class E, HSType HS>
122 struct HashSet :
public std::unordered_set<K, H, E, PoolAllocator<K>> {
124 using Base = std::unordered_set<K, H, E, PoolAllocator<K>>;
136 template <
class I,
class T,
class H = std::hash<T>,
class E = std::equal_to<T>,
139 static_assert(HS ==
HS_STL || HS == HS_FLAT,
"Unsupported hash set type");
142 friend class HashFunc;
143 friend class HashEqual;
150 compact_hash_func_(*this),
151 compact_hash_equal_(*this),
152 keys_(table_size, compact_hash_func_, compact_hash_equal_) {
153 if (table_size) id2entry_.reserve(table_size);
157 : hash_func_(table.hash_func_),
158 hash_equal_(table.hash_equal_),
159 compact_hash_func_(*this),
160 compact_hash_equal_(*this),
161 id2entry_(table.id2entry_),
162 keys_(table.keys_.begin(), table.keys_.end(), table.keys_.size(),
163 compact_hash_func_, compact_hash_equal_) {}
165 I
FindId(
const T &entry,
bool insert =
true) {
166 current_entry_ = &entry;
168 auto [iter, was_inserted] = keys_.insert(kCurrentKey);
169 if (!was_inserted)
return *iter;
172 I key = id2entry_.size();
173 const_cast<I &
>(*iter) = key;
174 id2entry_.push_back(entry);
177 const auto it = keys_.find(kCurrentKey);
178 return it == keys_.end() ? -1 : *it;
183 I
Size()
const {
return id2entry_.size(); }
187 if (n < 0 || n >= id2entry_.size()) {
190 }
else if (n == id2entry_.size() - 1) {
197 I key = id2entry_.size() - 1;
199 id2entry_.pop_back();
206 static_assert(std::is_signed_v<I>,
"I must be a signed type");
210 static constexpr I kCurrentKey = -1;
216 size_t operator()(I k)
const {
217 if (k >= kCurrentKey) {
218 return (ht_->hash_func_)(ht_->Key2Entry(k));
232 bool operator()(I k1, I k2)
const {
235 }
else if (k1 >= kCurrentKey && k2 >= kCurrentKey) {
236 return (ht_->hash_equal_)(ht_->Key2Entry(k1), ht_->Key2Entry(k2));
248 const T &Key2Entry(I k)
const {
249 if (k == kCurrentKey) {
250 return *current_entry_;
258 HashFunc compact_hash_func_;
259 HashEqual compact_hash_equal_;
260 std::vector<T> id2entry_;
262 const T *current_entry_;
269 template <
class I,
class T,
class FP>
273 explicit VectorBiTable(
const FP &fp = FP(),
size_t table_size = 0) : fp_(fp) {
274 if (table_size) id2entry_.reserve(table_size);
278 : fp_(table.fp_), fp2id_(table.fp2id_), id2entry_(table.id2entry_) {}
280 I
FindId(
const T &entry,
bool insert =
true) {
281 ssize_t fp = (fp_)(entry);
282 if (fp >= fp2id_.size()) fp2id_.resize(fp + 1);
283 I &id_ref = fp2id_[fp];
286 id2entry_.push_back(entry);
287 id_ref = id2entry_.size();
297 I
Size()
const {
return id2entry_.size(); }
303 std::vector<I> fp2id_;
304 std::vector<T> id2entry_;
312 template <
class I,
class T,
class S,
class FP,
class H = std::hash<T>,
316 friend class HashFunc;
317 friend class HashEqual;
320 const H &h = H(),
size_t vector_size = 0,
321 size_t entry_size = 0)
327 keys_(0, hash_func_, hash_equal_) {
328 if (vector_size) fp2id_.reserve(vector_size);
329 if (entry_size) id2entry_.reserve(entry_size);
333 : selector_(table.s_),
336 id2entry_(table.id2entry_),
337 fp2id_(table.fp2id_),
340 keys_(table.keys_.size(), hash_func_, hash_equal_) {
341 keys_.insert(table.keys_.begin(), table.keys_.end());
344 I
FindId(
const T &entry,
bool insert =
true) {
345 if ((selector_)(entry)) {
346 uint64_t fp = (fp_)(entry);
347 if (fp2id_.size() <= fp) fp2id_.resize(fp + 1, 0);
348 if (fp2id_[fp] == 0) {
350 id2entry_.push_back(entry);
351 fp2id_[fp] = id2entry_.size();
356 return fp2id_[fp] - 1;
358 current_entry_ = &entry;
359 if (
const auto it = keys_.find(kCurrentKey); it != keys_.end()) {
363 I key = id2entry_.size();
364 id2entry_.push_back(entry);
376 I
Size()
const {
return id2entry_.size(); }
385 static constexpr I kCurrentKey = -1;
391 size_t operator()(I k)
const {
392 if (k >= kCurrentKey) {
393 return (ht_->h_)(ht_->Key2Entry(k));
407 bool operator()(I k1, I k2)
const {
408 if (k1 >= kCurrentKey && k2 >= kCurrentKey) {
409 return ht_->Key2Entry(k1) == ht_->Key2Entry(k2);
421 const T &Key2Entry(I k)
const {
422 if (k == kCurrentKey) {
423 return *current_entry_;
433 std::vector<T> id2entry_;
434 std::vector<I> fp2id_;
439 HashEqual hash_equal_;
441 const T *current_entry_;
448 template <
class I,
class T,
class F>
453 I
FindId(
const T &entry,
bool insert =
true) {
454 I &id_ref = entry2id_[entry];
457 id2entry_.push_back(entry);
458 id_ref = id2entry_.size() + first_;
466 const T &
FindEntry(I s)
const {
return id2entry_[s - first_]; }
468 I
Size()
const {
return id2entry_.size(); }
471 auto &ref = id2entry_[s - first_];
472 entry2id_.erase(ref);
474 while (!id2entry_.empty() && id2entry_.front() == empty_entry_) {
475 id2entry_.pop_front();
481 std::unordered_map<T, I, F> entry2id_;
482 std::deque<T> id2entry_;
483 const T empty_entry_;
489 #endif // FST_BI_TABLE_H_
VectorHashBiTable(const VectorHashBiTable< I, T, S, FP, H, HS > &table)
I FindId(const T &entry, bool insert=true)
const T & FindEntry(I s) const
const T & FindEntry(I s) const
const S & Selector() const
I FindId(const T &entry, bool insert=true)
VectorBiTable(const FP &fp=FP(), size_t table_size=0)
const FP & Fingerprint() const
const T & FindEntry(I s) const
VectorHashBiTable(const S &s=S(), const FP &fp=FP(), const H &h=H(), size_t vector_size=0, size_t entry_size=0)
HashBiTable(const HashBiTable< I, T, H, E > &table)
const T & FindEntry(I s) const
const FP & Fingerprint() const
HashBiTable(size_t table_size=0, const H &h=H(), const E &e=E())
I FindId(const T &entry, bool insert=true)
VectorBiTable(const VectorBiTable< I, T, FP > &table)
I FindId(const T &entry, bool insert=true)
const T & FindEntry(I s) const
CompactHashBiTable(size_t table_size=0, const H &h=H(), const E &e=E())
const H & HashFunction() const
CompactHashBiTable(const CompactHashBiTable &table)
I FindId(const T &entry, bool insert=true)