Molassembler  3.0.0
Molecule graph and conformer library
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
TinySet.h
Go to the documentation of this file.
1 
11 #ifndef INCLUDE_MOLASSEMBLER_TEMPLE_TINY_SETS_H
12 #define INCLUDE_MOLASSEMBLER_TEMPLE_TINY_SETS_H
13 
14 #include <vector>
15 #include <algorithm>
16 
17 namespace Scine {
18 namespace Molassembler {
19 namespace Temple {
20 
32 template<typename T>
37  using UnderlyingContainer = std::vector<T>;
39  using value_type = T;
41  using reference = T&;
43  using const_reference = const T&;
45  using iterator = typename std::vector<T>::iterator;
47  using const_iterator = typename std::vector<T>::const_iterator;
49 
55 
60  static_assert(
61  std::is_same<T, typename std::decay<T>::type>::value,
62  "Tiny sets can only contain non-cv qualified types"
63  );
64  }
65 
67  TinyUnorderedSet(std::initializer_list<T> list)
68  : data(std::forward<std::initializer_list<T>>(list))
69  {
70  static_assert(
71  std::is_same<T, typename std::decay<T>::type>::value,
72  "Tiny sets can only contain non-cv qualified types"
73  );
74  }
76 
79 
87  static bool checked_insert(std::vector<T>& set, T a) {
88  if(!contains(set, a)) {
89  set.push_back(std::move(a));
90  return false;
91  }
92 
93  return true;
94  }
95 
106  template<typename ... Args>
107  static void checked_emplace(std::vector<T>& set, Args&& ... args) {
108  set.emplace_back(std::forward<Args>(args)...);
109 
110  if(
111  std::find(
112  std::begin(set),
113  std::end(set) - 1,
114  set.back()
115  ) != std::end(set) - 1
116  ) {
117  set.pop_back();
118  }
119  }
120 
129  static bool linear_search(std::vector<T>& set, const T& value) {
130  return std::find(
131  std::begin(set),
132  std::end(set),
133  value
134  ) != std::end(set);
135  }
137 
141  void clear() {
142  data.clear();
143  }
144 
149  void insert(T a) {
150  data.push_back(std::move(a));
151  }
152 
158  template<typename ... Args>
159  void emplace(Args&& ... args) {
160  data.emplace_back(std::forward<Args>(args)...);
161  }
162 
164  template<typename It>
165  void erase(It a) {
166  auto backIterator = --end();
167 
168  if(a == backIterator) {
169  data.erase(a);
170  } else {
171  std::iter_swap(a, backIterator);
172  data.erase(backIterator);
173  }
174  }
175 
177  template<typename It>
178  void insert(It a, const It& b) {
179  while(a != b) {
180  if(count(*a) == 0) {
181  insert(*a);
182  }
183  ++a;
184  }
185  }
186 
188  void reserve(std::size_t size) {
189  data.reserve(size);
190  }
192 
196  unsigned count(T a) const {
197  return std::find(
198  std::begin(data),
199  std::end(data),
200  a
201  ) != std::end(data);
202  }
203 
205  std::size_t size() const {
206  return data.size();
207  }
208 
210  bool empty() const {
211  return size() == 0;
212  }
214 
219  return std::begin(data);
220  }
221 
224  return std::end(data);
225  }
226 
229  return std::begin(data);
230  }
231 
233  const_iterator end() const {
234  return std::end(data);
235  }
236 
239  return std::cbegin(data);
240  }
241 
244  return std::cend(data);
245  }
247 };
248 
260 template<typename T>
261 struct TinySet {
265  using UnderlyingContainer = std::vector<T>;
267  using value_type = T;
269  using reference = T&;
271  using const_reference = const T&;
273  using iterator = typename std::vector<T>::iterator;
275  using const_iterator = typename std::vector<T>::const_iterator;
277 
283 
288  static_assert(
289  std::is_same<T, typename std::decay<T>::type>::value,
290  "Tiny sets can only contain non-cv qualified types"
291  );
292  }
294  TinySet(std::initializer_list<T> list)
295  : data(std::forward<std::initializer_list<T>>(list))
296  {
297  static_assert(
298  std::is_same<T, typename std::decay<T>::type>::value,
299  "Tiny sets can only contain non-cv qualified types"
300  );
301  }
303 
306  static iterator find(std::vector<T>& set, const T& a) {
307  return std::lower_bound(
308  std::begin(set),
309  std::end(set),
310  a
311  );
312  }
313 
314  static const_iterator find(const std::vector<T>& set, const T& a) {
315  return std::lower_bound(
316  std::begin(set),
317  std::end(set),
318  a
319  );
320  }
321 
322  static void checked_insert(std::vector<T>& set, T a) {
323  iterator findIter = find(set, a);
324 
325  /* Condition lifted directly from std::binary_search. If the element equals
326  * a, then the set already contains the element. In that case, do nothing.
327  */
328  if(findIter != std::end(set) && !(a < *findIter)) {
329  return;
330  }
331 
332  set.insert(std::move(findIter), std::move(a));
333  }
334 
350  template<typename ... Args>
351  static void checked_emplace(std::vector<T>& set, Args&& ... args) {
352  // In-place construct the element at the back of the set
353  set.emplace_back(std::forward<Args>(args)...);
354 
355  iterator lastElementIter = std::end(set) - 1;
356 
357  // Search the range before it for an identical element
358  iterator findIter = std::lower_bound(
359  std::begin(set),
360  lastElementIter,
361  set.back()
362  );
363 
364  if(findIter != lastElementIter && !(set.back() < *findIter)) {
365  // Remove the element again
366  set.pop_back();
367  } else {
368  // Rotate in the new element
369  std::rotate(
370  findIter,
371  lastElementIter,
372  std::end(set)
373  );
374  }
375  }
376 
385  static bool binary_search(const std::vector<T>& set, const T& value) {
386  return std::binary_search(
387  std::begin(set),
388  std::end(set),
389  value
390  );
391  }
393 
397  void clear() {
398  data.clear();
399  }
400 
402  template<typename It>
403  void erase(It a) {
404  data.erase(a);
405  }
406 
408  void reserve(std::size_t size) {
409  data.reserve(size);
410  }
411 
413  iterator find(const T& a) {
414  return std::lower_bound(
415  std::begin(data),
416  std::end(data),
417  a
418  );
419  }
420 
425  void insert(T a) {
426  data.insert(
427  find(a),
428  std::move(a)
429  );
430  }
431 
436  template<typename It>
437  void insert(It a, const It& b) {
438  while(a != b) {
439  if(count(*a) == 0) {
440  insert(*a);
441  }
442  ++a;
443  }
444  }
445 
451  void emplace(T a) {
452  insert(std::move(a));
453  }
454 
459  TinySet& operator = (std::initializer_list<T> init) {
460  data.clear();
461  for(const auto& value : init) {
462  insert(value);
463  }
464 
465  return *this;
466  }
468 
472  unsigned count(T a) const {
473  return std::binary_search(
474  std::begin(data),
475  std::end(data),
476  a
477  );
478  }
479 
481  bool empty() const {
482  return size() == 0;
483  }
484 
486  std::size_t size() const {
487  return data.size();
488  }
490 
495  return data.front();
496  }
497 
500  return data.back();
501  }
502 
504  const_reference at(std::size_t position) const {
505  return data.at(position);
506  }
508 
513  return std::begin(data);
514  }
515 
518  return std::end(data);
519  }
520 
523  return std::begin(data);
524  }
525 
527  const_iterator end() const {
528  return std::end(data);
529  }
530 
533  return std::cbegin(data);
534  }
535 
538  return std::cend(data);
539  }
541 
545  bool operator == (const TinySet& other) const {
546  return data == other.data;
547  }
548 
550  bool operator != (const TinySet& other) const {
551  return !(*this == other);
552  }
554 };
555 
556 } // namespace Temple
557 } // namespace Molassembler
558 } // namespace Scine
559 
560 #endif
UnderlyingContainer data
The owned underlying linear memory container.
Definition: TinySet.h:281
TinySet()
Default constructor.
Definition: TinySet.h:287
typename std::vector< T >::iterator iterator
Iterator type.
Definition: TinySet.h:45
TinyUnorderedSet(std::initializer_list< T > list)
Initializer-list constructor.
Definition: TinySet.h:67
static iterator find(std::vector< T > &set, const T &a)
Emplaces an element in an ordered vector if the element is not contained.
Definition: TinySet.h:306
void insert(It a, const It &b)
Inserts all elements contained in a range.
Definition: TinySet.h:437
const_iterator cbegin() const
Yields a begin const iterator.
Definition: TinySet.h:238
const_reference front() const
Yields a const reference to the first element in the set.
Definition: TinySet.h:494
iterator end()
Yields an end iterator.
Definition: TinySet.h:517
static void checked_emplace(std::vector< T > &set, Args &&...args)
Emplaces an element in an ordered vector if the element is not contained.
Definition: TinySet.h:351
void erase(It a)
Erases a position in the set.
Definition: TinySet.h:165
T value_type
What types this container stores.
Definition: TinySet.h:39
bool operator==(const TinySet &other) const
Lexicographically compare two sets.
Definition: TinySet.h:545
void erase(It a)
Erases an element marked by a position in the set.
Definition: TinySet.h:403
static void checked_insert(std::vector< T > &set, T a)
Emplaces an element in an ordered vector if the element is not contained.
Definition: TinySet.h:322
void insert(T a)
Inserts an element into the set.
Definition: TinySet.h:149
std::size_t size() const
Returns the number of contained elements.
Definition: TinySet.h:486
TinyUnorderedSet()
Default constructor.
Definition: TinySet.h:59
T & reference
Reference to a value_type.
Definition: TinySet.h:269
const T & const_reference
Const reference to a value type.
Definition: TinySet.h:271
std::size_t size() const
Returns the number of elements in the set.
Definition: TinySet.h:205
void clear()
Empties the set.
Definition: TinySet.h:141
const_iterator end() const
Yields an end const iterator.
Definition: TinySet.h:527
typename std::vector< T >::const_iterator const_iterator
Const iterator type.
Definition: TinySet.h:275
TinySet(std::initializer_list< T > list)
Initializer-list constructor.
Definition: TinySet.h:294
An adapter class for std::vector that acts like an ordered set and stores its data in the underlying ...
Definition: TinySet.h:261
typename std::vector< T >::iterator iterator
Iterator type.
Definition: TinySet.h:273
An adapter class for std::vector that acts like an unordered set and stores its data in the underlyin...
Definition: TinySet.h:33
void emplace(T a)
Insert an element.
Definition: TinySet.h:451
static bool binary_search(const std::vector< T > &set, const T &value)
Binary search for a value in an ordered set.
Definition: TinySet.h:385
const_iterator begin() const
Yields a begin const iterator.
Definition: TinySet.h:228
const T & const_reference
Const reference to a value type.
Definition: TinySet.h:43
void clear()
Empties the set.
Definition: TinySet.h:397
unsigned count(T a) const
Count the number of occurrences of an element.
Definition: TinySet.h:472
iterator begin()
Yields a begin iterator.
Definition: TinySet.h:218
const_reference back() const
Yields a const reference to the last element in the set.
Definition: TinySet.h:499
iterator end()
Yields an end iterator.
Definition: TinySet.h:223
void reserve(std::size_t size)
Reserves space in memory.
Definition: TinySet.h:408
void emplace(Args &&...args)
Emplaces an element into the set.
Definition: TinySet.h:159
void insert(It a, const It &b)
Inserts all elements contained in a range.
Definition: TinySet.h:178
bool operator!=(const TinySet &other) const
Invertes operator==.
Definition: TinySet.h:550
static void checked_emplace(std::vector< T > &set, Args &&...args)
Checked emplace of an element into a set.
Definition: TinySet.h:107
static bool linear_search(std::vector< T > &set, const T &value)
Linear search for a value.
Definition: TinySet.h:129
std::vector< T > UnderlyingContainer
The type of the underlying container with linear memory.
Definition: TinySet.h:265
bool empty() const
Returns whether the set is empty.
Definition: TinySet.h:210
T & reference
Reference to a value_type.
Definition: TinySet.h:41
iterator find(const T &a)
Finds an element in the set.
Definition: TinySet.h:413
std::vector< T > UnderlyingContainer
The type of the underlying container with linear memory.
Definition: TinySet.h:37
const_reference at(std::size_t position) const
Yields a const reference to an element in the set.
Definition: TinySet.h:504
typename std::vector< T >::const_iterator const_iterator
Const iterator type.
Definition: TinySet.h:47
const_iterator begin() const
Yields a begin const iterator.
Definition: TinySet.h:522
iterator begin()
Yields a begin iterator.
Definition: TinySet.h:512
bool empty() const
Returns whether the set is empty.
Definition: TinySet.h:481
unsigned count(T a) const
Counts the number of occurrences of an element.
Definition: TinySet.h:196
void reserve(std::size_t size)
Reserves space in memory.
Definition: TinySet.h:188
const_iterator cend() const
Yields an end const iterator.
Definition: TinySet.h:537
const_iterator end() const
Yields an end const iterator.
Definition: TinySet.h:233
UnderlyingContainer data
The owned underlying linear memory container.
Definition: TinySet.h:53
void insert(T a)
Inserts an element into the set.
Definition: TinySet.h:425
static const_iterator find(const std::vector< T > &set, const T &a)
Emplaces an element in an ordered vector if the element is not contained.
Definition: TinySet.h:314
const_iterator cend() const
Yields an end const iterator.
Definition: TinySet.h:243
const_iterator cbegin() const
Yields a begin const iterator.
Definition: TinySet.h:532
TinySet & operator=(std::initializer_list< T > init)
Assign from an initializer list.
Definition: TinySet.h:459
auto find(const Container &container, const T &needle)
std::find shorthand
Definition: Functional.h:346
T value_type
What types this container stores.
Definition: TinySet.h:267
static bool checked_insert(std::vector< T > &set, T a)
Inserts an element only if the element is not already in the set.
Definition: TinySet.h:87