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