Spicy
set.h
1 // Copyright (c) 2020-2021 by the Zeek Project. See LICENSE for details.
2 
12 #pragma once
13 
14 #include <algorithm>
15 #include <initializer_list>
16 #include <memory>
17 #include <set>
18 #include <string>
19 #include <utility>
20 
21 #include <hilti/rt/extension-points.h>
22 #include <hilti/rt/iterator.h>
23 #include <hilti/rt/types/set_fwd.h>
24 #include <hilti/rt/types/vector_fwd.h>
25 #include <hilti/rt/util.h>
26 
27 namespace hilti::rt {
28 
29 namespace set {
30 
31 template<typename T>
32 class Iterator {
33  using S = Set<T>;
34 
35  std::weak_ptr<S*> _control;
36  typename S::V::iterator _iterator;
37 
38 public:
39  Iterator() = default;
40 
41  typename S::reference operator*() const {
42  if ( auto&& l = _control.lock() ) {
43  // Iterators to `end` cannot be dereferenced.
44  if ( _iterator == static_cast<const std::set<T>&>(**l).end() )
45  throw IndexError("iterator is invalid");
46 
47  return *_iterator;
48  }
49 
50  throw IndexError("iterator is invalid");
51  }
52 
53  Iterator& operator++() {
54  if ( ! _control.lock() )
55  throw IndexError("iterator is invalid");
56 
57  ++_iterator;
58  return *this;
59  };
60 
61  Iterator operator++(int) {
62  auto ret = *this;
63  ++(*this); // Ensures the iterator is valid.
64  return ret;
65  }
66 
67  friend bool operator==(const Iterator& a, const Iterator& b) {
68  if ( a._control.lock() != b._control.lock() )
69  throw InvalidArgument("cannot compare iterators into different sets");
70 
71  return a._iterator == b._iterator;
72  }
73 
74  friend bool operator!=(const Iterator& a, const Iterator& b) { return ! (a == b); }
75 
76 protected:
77  friend class Set<T>;
78 
79  Iterator(typename S::V::iterator iterator, const typename S::C& control)
80  : _control(control), _iterator(std::move(iterator)) {}
81 };
82 
83 } // namespace set
84 
106 template<typename T>
107 class Set : protected std::set<T> {
108 public:
109  using V = std::set<T>;
110  using C = std::shared_ptr<Set<T>*>;
111 
112  C _control = std::make_shared<Set<T>*>(this);
113 
114  using reference = const T&;
115  using const_reference = const T&;
116 
117  using iterator = typename set::Iterator<T>;
118  using const_iterator = typename set::Iterator<T>;
119 
120  using key_type = T;
121  using value_type = T;
122 
123  using size_type = uint64_t;
124 
125  Set() = default;
126  Set(const Set&) = default;
127  Set(Set&&) noexcept = default;
128  Set(const Vector<T>& l) : std::set<T>(l.begin(), l.end()) {}
129  Set(std::initializer_list<T> l) : std::set<T>(std::move(l)) {}
130  ~Set() = default;
131 
132  Set& operator=(const Set&) = default;
133  Set& operator=(Set&&) noexcept = default;
134 
140  bool contains(const T& t) const { return this->count(t); }
141 
142  auto begin() const { return iterator(static_cast<const V&>(*this).begin(), empty() ? nullptr : _control); }
143  auto end() const { return iterator(static_cast<const V&>(*this).end(), empty() ? nullptr : _control); }
144 
145  size_type size() const { return V::size(); }
146 
154  size_type erase(const key_type& key) {
155  // Update control block to invalidate all iterators previously created from it.
156  _control = std::make_shared<Set<T>*>();
157 
158  return static_cast<V&>(*this).erase(key);
159  }
160 
165  void clear() {
166  // Update control block to invalidate all iterators previously created from it.
167  _control = std::make_shared<Set<T>*>();
168 
169  return static_cast<V&>(*this).clear();
170  }
171 
172  // Methods of `std::set`. These methods *must not* cause any iterator invalidation.
173  using V::empty;
174  using V::insert;
175 
176  friend bool operator==(const Set& a, const Set& b) { return static_cast<const V&>(a) == static_cast<const V&>(b); }
177  friend bool operator!=(const Set& a, const Set& b) { return ! (a == b); }
178 
179  friend set::Iterator<T>;
180 };
181 
182 namespace set {
184 class Empty : public Set<bool> {};
185 
186 inline bool operator==(const Empty& /*unused*/, const Empty& /*unused*/) { return true; }
187 
188 template<typename T>
189 inline bool operator==(const Set<T>& v, const Empty& /*unused*/) {
190  return v.empty();
191 }
192 
193 template<typename T>
194 inline bool operator==(const Empty& /*unused*/, const Set<T>& v) {
195  return v.empty();
196 }
197 
198 inline bool operator!=(const Empty& /*unused*/, const Empty& /*unused*/) { return false; }
199 
200 template<typename T>
201 inline bool operator!=(const Set<T>& v, const Empty& /*unused*/) {
202  return ! v.empty();
203 }
204 
205 template<typename T>
206 inline bool operator!=(const Empty& /*unused*/, const Set<T>& v) {
207  return ! v.empty();
208 }
209 } // namespace set
210 
211 namespace detail::adl {
212 template<typename T>
213 inline std::string to_string(const Set<T>& x, adl::tag /*unused*/) {
214  return fmt("{%s}", rt::join(rt::transform(x, [](const T& y) { return rt::to_string(y); }), ", "));
215 }
216 
217 inline std::string to_string(const set::Empty& x, adl::tag /*unused*/) { return "{}"; }
218 
219 template<typename T>
220 inline std::string to_string(const set::Iterator<T>& /*unused*/, adl::tag /*unused*/) {
221  return "<set iterator>";
222 }
223 } // namespace detail::adl
224 
225 template<typename T>
226 inline std::ostream& operator<<(std::ostream& out, const Set<T>& x) {
227  out << to_string(x);
228  return out;
229 }
230 
231 inline std::ostream& operator<<(std::ostream& out, const set::Empty& x) {
232  out << to_string(x);
233  return out;
234 }
235 
236 template<typename T>
237 inline std::ostream& operator<<(std::ostream& out, const set::Iterator<T>& x) {
238  out << to_string(x);
239  return out;
240 }
241 
242 } // namespace hilti::rt
std::string to_string(T &&x)
Definition: extension-points.h:26
size_type erase(const key_type &key)
Definition: set.h:154
Definition: set.h:184
Definition: any.h:7
auto transform(const std::vector< X > &x, F f)
Definition: util.h:299
Definition: set.h:107
bool contains(const T &t) const
Definition: set.h:140
void clear()
Definition: set.h:165
Definition: set.h:32
std::string join(const T &l, const std::string &delim="")
Definition: util.h:281
Definition: vector.h:249
std::string fmt(const char *fmt, const Args &... args)
Definition: fmt.h:13