MimIR 0.1
MimIR is my Intermediate Representation
Loading...
Searching...
No Matches
indexset.h
Go to the documentation of this file.
1#pragma once
2
3#include "mim/util/vector.h"
4
5namespace mim {
6
7template<class Indexer, class Key> class IndexSet {
8public:
9 class reference {
10 private:
11 reference(uint64_t& word, uint64_t pos)
12 : word_(word)
13 , pos_(pos) {}
14
15 public:
16 reference operator=(bool b) noexcept {
17 if (b)
18 word_ |= uint64_t(1) << pos_;
19 else
20 word_ &= ~(uint64_t(1) << pos_);
21 return *this;
22 }
23 operator bool() const { return word_ & (uint64_t(1) << pos_); }
24
25 private:
26 uint64_t word() const { return word_; }
27
28 uint64_t& word_;
29 uint64_t pos_;
30
31 friend class IndexSet;
32 };
33
34 // TODO write iterators
35 // TODO add size
36
37 IndexSet(const Indexer& indexer)
38 : indexer_(indexer)
39 , bits_((capacity() + 63u) / 64u) {}
40 IndexSet(const IndexSet& other)
41 : indexer_(other.indexer())
42 , bits_(other.bits_) {}
43 IndexSet(IndexSet&& other) noexcept
44 : indexer_(std::move(other.indexer_))
45 , bits_(std::move(other.bits_)) {}
46 IndexSet& operator=(IndexSet other) noexcept { return swap(*this, other), *this; }
47
48 const Indexer& indexer() const { return indexer_; }
49 size_t capacity() const { return indexer().size(); }
50 size_t next(size_t pos = 0) {
51 for (size_t i = pos, e = capacity(); i != e; ++i)
52 if (bits_[i]) return i;
53 return pos;
54 }
56 auto i = indexer().index(key);
57 assert(i != size_t(-1));
58 return reference(bits_[i / 64u], i % 64u);
59 }
60 bool operator[](Key key) const { return (*const_cast<IndexSet<Indexer, Key>*>(this))[key]; }
61
62 /// Depending on @p flag this method either inserts (true) or removes (false) @p key and returns true if successful.
63 template<bool flag> bool set(Key key) {
64 auto ref = (*this)[key];
65 auto old = ref.word();
66 ref = flag;
67 return old != ref.word();
68 }
69 bool insert(Key key) { return set<true>(key); } ///< Inserts \p key and returns true if successful.
70 bool erase(Key key) { return set<false>(key); } ///< Erase \p key and returns true if successful.
71 bool contains(Key key) const { return (*this)[key]; }
72 void clear() { std::ranges::fill(bits_, 0u); }
73
74 template<class Op> IndexSet& transform(const IndexSet& other, Op op) {
75 assert(this->size() == other.size());
76 for (size_t i = 0, e = capacity(); i != e; ++i) this->bits_[i] = op(this->bits_[i], other.bits_[i]);
77 return *this;
78 }
79 IndexSet& operator&=(const IndexSet& other) { return transform(other, std::bit_and<uint64_t>()); }
80 IndexSet& operator|=(const IndexSet& other) { return transform(other, std::bit_or<uint64_t>()); }
81 IndexSet& operator^=(const IndexSet& other) { return transform(other, std::bit_xor<uint64_t>()); }
82 friend void swap(IndexSet& set1, IndexSet& set2) noexcept {
83 using std::swap;
84 assert(&set1.indexer() == &set2.indexer());
85 swap(set1.bits_, set2.bits_);
86 }
87
88private:
89 const Indexer& indexer_;
90 Vector<uint64_t> bits_;
91};
92
93/// @name IndexSet visit
94///@{
95template<class Indexer, class Key> bool visit(IndexSet<Indexer, Key>& set, const Key& key) { return !set.insert(key); }
96
97template<class Indexer, class Key> void visit_first(IndexSet<Indexer, Key>& set, const Key& key) {
98 assert(!set.contains(key));
99 visit(set, key);
100}
101///@}
102
103} // namespace mim
reference operator=(bool b) noexcept
Definition indexset.h:16
reference operator[](Key key)
Definition indexset.h:55
IndexSet & operator=(IndexSet other) noexcept
Definition indexset.h:46
size_t capacity() const
Definition indexset.h:49
void clear()
Definition indexset.h:72
IndexSet & operator|=(const IndexSet &other)
Definition indexset.h:80
IndexSet & transform(const IndexSet &other, Op op)
Definition indexset.h:74
IndexSet & operator&=(const IndexSet &other)
Definition indexset.h:79
const Indexer & indexer() const
Definition indexset.h:48
IndexSet(const Indexer &indexer)
Definition indexset.h:37
bool set(Key key)
Depending on flag this method either inserts (true) or removes (false) key and returns true if succes...
Definition indexset.h:63
bool contains(Key key) const
Definition indexset.h:71
friend void swap(IndexSet &set1, IndexSet &set2) noexcept
Definition indexset.h:82
IndexSet(IndexSet &&other) noexcept
Definition indexset.h:43
IndexSet(const IndexSet &other)
Definition indexset.h:40
size_t next(size_t pos=0)
Definition indexset.h:50
bool erase(Key key)
Erase key and returns true if successful.
Definition indexset.h:70
bool insert(Key key)
Inserts key and returns true if successful.
Definition indexset.h:69
IndexSet & operator^=(const IndexSet &other)
Definition indexset.h:81
bool operator[](Key key) const
Definition indexset.h:60
This is a thin wrapper for absl::InlinedVector<T, N, / A> which in turn is a drop-in replacement for ...
Definition vector.h:16
Definition cfg.h:11
bool visit(IndexSet< Indexer, Key > &set, const Key &key)
Definition indexset.h:95
void visit_first(IndexSet< Indexer, Key > &set, const Key &key)
Definition indexset.h:97