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/safe-int.h>
24 #include <hilti/rt/types/set_fwd.h>
25 #include <hilti/rt/types/vector_fwd.h>
26 #include <hilti/rt/util.h>
27 
28 namespace hilti::rt {
29 
30 namespace set {
31 
32 template<typename T>
33 class Iterator {
34  using S = Set<T>;
35 
36  std::weak_ptr<S*> _control;
37  typename S::V::iterator _iterator;
38 
39 public:
40  Iterator() = default;
41 
42  typename S::reference operator*() const {
43  if ( auto&& l = _control.lock() ) {
44  // Iterators to `end` cannot be dereferenced.
45  if ( _iterator == static_cast<const std::set<T>&>(**l).end() )
46  throw IndexError("iterator is invalid");
47 
48  return *_iterator;
49  }
50 
51  throw IndexError("iterator is invalid");
52  }
53 
54  Iterator& operator++() {
55  if ( ! _control.lock() )
56  throw IndexError("iterator is invalid");
57 
58  ++_iterator;
59  return *this;
60  };
61 
62  Iterator operator++(int) {
63  auto ret = *this;
64  ++(*this); // Ensures the iterator is valid.
65  return ret;
66  }
67 
68  friend bool operator==(const Iterator& a, const Iterator& b) {
69  if ( a._control.lock() != b._control.lock() )
70  throw InvalidArgument("cannot compare iterators into different sets");
71 
72  return a._iterator == b._iterator;
73  }
74 
75  friend bool operator!=(const Iterator& a, const Iterator& b) { return ! (a == b); }
76 
77 protected:
78  friend class Set<T>;
79 
80  Iterator(typename S::V::iterator iterator, const typename S::C& control)
81  : _control(control), _iterator(std::move(iterator)) {}
82 };
83 
84 } // namespace set
85 
107 template<typename T>
108 class Set : protected std::set<T> {
109 public:
110  using V = std::set<T>;
111  using C = std::shared_ptr<Set<T>*>;
112 
113  C _control = std::make_shared<Set<T>*>(this);
114 
115  using reference = const T&;
116  using const_reference = const T&;
117 
118  using iterator = typename set::Iterator<T>;
119  using const_iterator = typename set::Iterator<T>;
120 
121  using key_type = T;
122  using value_type = T;
123 
124  using size_type = integer::safe<uint64_t>;
125 
126  Set() = default;
127  Set(const Set&) = default;
128  Set(Set&&) noexcept = default;
129  Set(const Vector<T>& l) : std::set<T>(l.begin(), l.end()) {}
130  Set(std::initializer_list<T> l) : std::set<T>(std::move(l)) {}
131  ~Set() = default;
132 
133  Set& operator=(const Set&) = default;
134  Set& operator=(Set&&) noexcept = default;
135 
141  bool contains(const T& t) const { return this->count(t); }
142 
143  auto begin() const { return iterator(static_cast<const V&>(*this).begin(), empty() ? nullptr : _control); }
144  auto end() const { return iterator(static_cast<const V&>(*this).end(), empty() ? nullptr : _control); }
145 
146  size_type size() const { return V::size(); }
147 
155  size_type erase(const key_type& key) {
156  // Update control block to invalidate all iterators previously created from it.
157  _control = std::make_shared<Set<T>*>();
158 
159  return static_cast<V&>(*this).erase(key);
160  }
161 
166  void clear() {
167  // Update control block to invalidate all iterators previously created from it.
168  _control = std::make_shared<Set<T>*>();
169 
170  return static_cast<V&>(*this).clear();
171  }
172 
179  iterator insert(iterator hint, const T& value) {
180  auto it = V::insert(hint._iterator, value);
181  return iterator(it, _control);
182  }
183 
184  // Methods of `std::set`. These methods *must not* cause any iterator invalidation.
185  using V::empty;
186  using V::insert;
187 
188  friend bool operator==(const Set& a, const Set& b) { return static_cast<const V&>(a) == static_cast<const V&>(b); }
189  friend bool operator!=(const Set& a, const Set& b) { return ! (a == b); }
190 
191  friend set::Iterator<T>;
192 };
193 
194 namespace set {
196 class Empty : public Set<bool> {};
197 
198 inline bool operator==(const Empty& /*unused*/, const Empty& /*unused*/) { return true; }
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 
210 inline bool operator!=(const Empty& /*unused*/, const Empty& /*unused*/) { return false; }
211 
212 template<typename T>
213 inline bool operator!=(const Set<T>& v, const Empty& /*unused*/) {
214  return ! v.empty();
215 }
216 
217 template<typename T>
218 inline bool operator!=(const Empty& /*unused*/, const Set<T>& v) {
219  return ! v.empty();
220 }
221 } // namespace set
222 
223 namespace detail::adl {
224 template<typename T>
225 inline std::string to_string(const Set<T>& x, adl::tag /*unused*/) {
226  return fmt("{%s}", rt::join(rt::transform(x, [](const T& y) { return rt::to_string(y); }), ", "));
227 }
228 
229 inline std::string to_string(const set::Empty& x, adl::tag /*unused*/) { return "{}"; }
230 
231 template<typename T>
232 inline std::string to_string(const set::Iterator<T>& /*unused*/, adl::tag /*unused*/) {
233  return "<set iterator>";
234 }
235 } // namespace detail::adl
236 
237 template<typename T>
238 inline std::ostream& operator<<(std::ostream& out, const Set<T>& x) {
239  out << to_string(x);
240  return out;
241 }
242 
243 inline std::ostream& operator<<(std::ostream& out, const set::Empty& x) {
244  out << to_string(x);
245  return out;
246 }
247 
248 namespace set {
249 template<typename T>
250 inline std::ostream& operator<<(std::ostream& out, const Iterator<T>& x) {
251  out << to_string(x);
252  return out;
253 }
254 } // namespace set
255 } // namespace hilti::rt
iterator insert(iterator hint, const T &value)
Definition: set.h:179
std::string to_string(T &&x)
Definition: extension-points.h:26
size_type erase(const key_type &key)
Definition: set.h:155
auto transform(const C &x, F f)
Definition: util.h:362
Definition: set.h:196
Definition: any.h:7
Definition: set.h:108
bool contains(const T &t) const
Definition: set.h:141
void clear()
Definition: set.h:166
Definition: set.h:33
std::string join(const T &l, const std::string &delim="")
Definition: util.h:312
Definition: vector.h:256
std::string fmt(const char *fmt, const Args &... args)
Definition: fmt.h:13