MorphoGraphX
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
SetVector.hpp
1 #ifndef UTIL_SET_VECTOR_H
2 #define UTIL_SET_VECTOR_H
3 
4 #include <Config.hpp>
5 
6 #include <algorithm>
7 #include <functional>
8 #include <vector>
9 
10 #ifdef USE_CXX11
11 # include <initializer_list>
12 # define NOEXCEPT noexcept
13 # define STD_FORWARD(T, V) std::forward<T>(V)
14 #else
15 # define NOEXCEPT
16 # define STD_FORWARD(T, V) (V)
17 #endif
18 
19 namespace mgx {
20 namespace util {
21 
27 template <typename Key, typename Compare = std::less<Key>, class Allocator = std::allocator<Key> >
29  typedef std::vector<Key, Allocator> content_t;
30  content_t _content;
31  Compare _compare;
32 
33 public:
34  typedef Key key_type;
35  typedef Key value_type;
36  typedef Compare key_compare;
37  typedef Compare value_compare;
38  typedef Allocator allocator_type;
39  typedef value_type& reference;
40  typedef const value_type& const_reference;
41 
42 #ifdef USE_CXX11
43  typedef typename std::allocator_traits<allocator_type>::pointer pointer;
44  typedef typename std::allocator_traits<allocator_type>::const_pointer const_pointer;
45 #else
46  typedef typename allocator_type::pointer pointer;
47  typedef typename allocator_type::const_pointer const_pointer;
48 #endif
49 
50  typedef typename content_t::const_iterator iterator;
51  typedef typename content_t::const_iterator const_iterator;
52  typedef typename content_t::size_type size_type;
53  typedef typename content_t::difference_type difference_type;
54 
55  typedef std::reverse_iterator<iterator> reverse_iterator;
56  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
57 
59  explicit multiset_vector(const Compare& comp = Compare(), const Allocator& alloc = Allocator())
61  : _content(alloc)
62  , _compare(comp)
63  {
64  }
65 
66  template <typename InputIterator>
67  multiset_vector(InputIterator first, InputIterator last, const Compare& comp = Compare(),
68  const Allocator& alloc = Allocator())
69  : _content(first, last, alloc)
70  , _compare(comp)
71  {
72  sort();
73  }
74 
75 #ifdef USE_CXX11
76  multiset_vector(const multiset_vector&) = default;
77  multiset_vector(multiset_vector&&) = default;
78 #else
79  multiset_vector(const multiset_vector& copy)
80  : _content(copy._content)
81  , _compare(copy._compare)
82  {
83  }
84 #endif
85 
86  explicit multiset_vector(const Allocator& alloc)
87  : _content(alloc)
88  , _compare()
89  {
90  }
91 
92  multiset_vector(const multiset_vector& copy, const Allocator& alloc)
93  : _content(copy._content, alloc)
94  , _compare(copy._compare)
95  {
96  }
97 
98 #ifdef USE_CXX11
99  multiset_vector(multiset_vector&& copy, const Allocator& alloc)
100  : _content(std::move(copy), alloc)
101  , _compare(std::move(copy._compare))
102  {
103  }
104 
105  multiset_vector(std::initializer_list<value_type> values, const Compare& comp = Compare(),
106  const Allocator& alloc = Allocator())
107  : multiset_vector(values.begin(), values.end(), comp, alloc)
108  {
109  }
110 #endif
111 
112  ~multiset_vector() {
113  }
114 
115 #ifdef USE_CXX11
116  multiset_vector& operator=(const multiset_vector&) = default;
117  multiset_vector& operator=(multiset_vector&&) = default;
118  multiset_vector& operator=(std::initializer_list<value_type> content)
119  {
120  _content.assign(content.begin(), content.end());
121  sort();
122  return *this;
123  }
124 #else
125  multiset_vector& operator=(const multiset_vector& copy)
126  {
127  _content = copy._content;
128  _compare = copy._compare;
129  return *this;
130  }
131 #endif
132 
133  allocator_type get_allocator() const NOEXCEPT {
134  return _content.get_allocator();
135  }
136 
138 
139 
141  iterator begin() NOEXCEPT {
142  return _content.begin();
143  }
144  iterator end() NOEXCEPT {
145  return _content.end();
146  }
147 
148  const_iterator begin() const NOEXCEPT {
149  return _content.begin();
150  }
151  const_iterator end() const NOEXCEPT {
152  return _content.end();
153  }
154 
155  reverse_iterator rbegin() NOEXCEPT {
156  return _content.rbegin();
157  }
158  reverse_iterator rend() NOEXCEPT {
159  return _content.rend();
160  }
161 
162  const_reverse_iterator rbegin() const NOEXCEPT {
163  return _content.rbegin();
164  }
165  const_reverse_iterator rend() const NOEXCEPT {
166  return _content.rend();
167  }
168 
169  const_iterator cbegin() const NOEXCEPT {
170  return _content.begin();
171  }
172  const_iterator cend() const NOEXCEPT {
173  return _content.end();
174  }
175 
176  const_reverse_iterator crbegin() const NOEXCEPT {
177  return _content.rbegin();
178  }
179  const_reverse_iterator crend() const NOEXCEPT {
180  return _content.rend();
181  }
182 
184 
186 
188  const_reference operator[](size_type i) const {
189  return _content[i];
190  }
191 
192  const_reference at(size_type i) const {
193  return _content.at(i);
194  }
195 
196  const_pointer data() const NOEXCEPT {
197  return _content.data();
198  }
199 
200  const_reference front() const {
201  return _content.front();
202  }
203 
204  const_reference back() const {
205  return _content.back();
206  }
207 
209  const content_t& vector() const {
210  return _content;
211  }
212 
214 
216 
218  bool empty() const NOEXCEPT {
219  return _content.empty();
220  }
221  size_type size() const NOEXCEPT {
222  return _content.size();
223  }
224  size_type max_size() const NOEXCEPT {
225  return _content.max_size();
226  }
227 
228 #ifdef USE_CXX11
229  void shrink_to_fit() {
230  _content.shrink_to_fit();
231  }
232 #endif
233 
234  void reserve(size_type n) {
235  _content.reserve(n);
236  }
237 
239 
240 
242 #ifdef USE_CXX11
243  template <typename ... Args> iterator emplace(Args&& ... args)
244  {
245  auto value = value_type(std::forward<Args>(args) ...);
246  return this->_insert(std::move(value));
247  }
248  template <typename ... Args> iterator emplace_hint(const_iterator hint, Args&& ... args)
249  {
250  auto value = value_type(std::forward<Args>(args) ...);
251  return this->_insert_hint(hint, std::move(value));
252  }
253 
254  iterator insert(value_type&& value) {
255  return this->_insert(std::move(value));
256  }
257 
258  iterator insert(const_iterator pos, value_type&& value) {
259  return this->_insert_hint(pos, value);
260  }
261 
262  void insert(std::initializer_list<value_type> values)
263  {
264  for(const value_type& v : values)
265  this->_insert(v);
266  }
267 
268 #endif
269 
270  iterator insert(const value_type& value) {
271  return this->_insert(value);
272  }
273 
274  iterator insert(const_iterator pos, const value_type& value) {
275  return this->_insert_hint(pos, value);
276  }
277 
278  template <typename InputIterator> void insert(InputIterator first, InputIterator last)
279  {
280  if(this->empty()) {
281  _content.assign(first, last);
282  this->sort();
283  } else {
284  for(InputIterator it = first; it != last; ++it)
285  this->_insert(*it);
286  }
287  }
288 
289  iterator erase(const_iterator position) {
290  return _content.erase(this->remove_iterator_const(position));
291  }
292 
293  size_type erase(const key_type& x)
294  {
295  const_iterator low = this->lower_bound(x);
296  const_iterator up = this->upper_bound(x);
297  if(low != up) {
298  size_type n = std::distance(low, up);
299  this->erase(low, up);
300  return n;
301  }
302  return 0u;
303  }
304 
305  iterator erase(const_iterator first, const_iterator last)
306  {
307  return _content.erase(remove_iterator_const(first), remove_iterator_const(last));
308  }
309 
310  void swap(multiset_vector& other)
311  {
312  using std::swap;
313  swap(_content, other._content);
314  }
315 
316  void clear() NOEXCEPT {
317  _content.clear();
318  }
319 
321 
322 
324  key_compare key_comp() const {
325  return _compare;
326  }
327  value_compare value_comp() const {
328  return _compare;
329  }
330 
332 
334 
336  iterator find(const key_type& k)
337  {
338  return this->remove_iterator_const(const_cast<const multiset_vector*>(this)->find(k));
339  }
340 
341  const_iterator find(const key_type& k) const
342  {
343  const_iterator pos = std::lower_bound(this->begin(), this->end(), k, this->key_comp());
344  if(pos != this->end() and this->equiv_keys(*pos, k))
345  return pos;
346  return this->end();
347  }
348 
349  size_type count(const key_type& k) const
350  {
351  const_iterator low = this->lower_bound(k);
352  const_iterator up = this->upper_bound(k);
353  return std::distance(low, up);
354  }
355 
356  iterator lower_bound(const key_type& k)
357  {
358  return this->remove_iterator_const(const_cast<const multiset_vector*>(this)->lower_bound(k));
359  }
360 
361  const_iterator lower_bound(const key_type& k) const
362  {
363  return std::lower_bound(this->begin(), this->end(), k, this->key_comp());
364  }
365 
366  iterator upper_bound(const key_type& k)
367  {
368  return this->remove_iterator_const(const_cast<const multiset_vector*>(this)->upper_bound(k));
369  }
370 
371  const_iterator upper_bound(const key_type& k) const
372  {
373  return std::upper_bound(this->begin(), this->end(), k, this->key_comp());
374  }
375 
376  std::pair<iterator, iterator> equal_range(const key_type& k)
377  {
378  typedef std::pair<const_iterator, const_iterator> const_result_t;
379  const_result_t res = const_cast<const multiset_vector*>(this)->equal_range(k);
380  typedef std::pair<iterator, iterator> result_t;
381  return result_t(this->remove_iterator_const(res.first), this->remove_iterator_const(res.second));
382  }
383 
384  std::pair<const_iterator, const_iterator> equal_range(const key_type& k) const
385  {
386  typedef std::pair<const_iterator, const_iterator> result_t;
387  return result_t(this->lower_bound(k), this->upper_bound(k));
388  }
389 
390  friend bool operator==(const multiset_vector& v1, const multiset_vector& v2)
391  {
392  if(v1.size() != v2.size())
393  return false;
394  for(const_iterator it1 = v1.begin(), it2 = v2.begin(); it1 != v1.end(); ++it1, ++it2)
395  if(v1.differ_keys(*it1, *it2))
396  return false;
397  return true;
398  }
399 
400  friend bool operator!=(const multiset_vector& v1, const multiset_vector& v2) {
401  return not (v1 == v2);
402  }
403 
404  friend bool operator<(const multiset_vector& v1, const multiset_vector& v2)
405  {
406  const_iterator it1 = v1.begin(), it2 = v2.begin();
407  const_iterator last_v1 = v1.end(), last_v2 = v2.end();
408  for(; it1 != last_v1 and it2 != last_v2; ++it1, ++it2) {
409  if(v1.compare(*it1, *it2))
410  return true;
411  else if(v1.compare(*it2, *it1))
412  return false;
413  }
414  if(it2 != last_v2)
415  return true;
416  return false;
417  }
418 
419  friend bool operator>(const multiset_vector& v1, const multiset_vector& v2)
420  {
421  const_iterator it1 = v1.begin(), it2 = v2.begin();
422  const_iterator last_v1 = v1.end(), last_v2 = v2.end();
423  for(; it1 != last_v1 and it2 != last_v2; ++it1, ++it2) {
424  if(v1.compare(*it1, *it2))
425  return false;
426  else if(v1.compare(*it2, *it1))
427  return true;
428  }
429  if(it1 != last_v1)
430  return true;
431  return false;
432  }
433 
434  friend bool operator<=(const multiset_vector& v1, const multiset_vector& v2) {
435  return not (v1 > v2);
436  }
437 
438  friend bool operator>=(const multiset_vector& v1, const multiset_vector& v2) {
439  return not (v1 < v2);
440  }
441 
442 protected:
443  typename content_t::iterator remove_iterator_const(const_iterator it) {
444  return _content.begin() + (it - begin());
445  }
446 
447  void sort()
448  {
449  if(_content.size() == 0)
450  return;
451  std::sort(_content.begin(), _content.end(), this->key_comp());
452  }
453 
454  iterator _find_insert_range(const_iterator first, const_iterator last, const value_type& value) const
455  {
456  return std::upper_bound(first, last, value, this->key_comp());
457  }
458 
459  const_iterator _find_insert_hint(const_iterator hint, const value_type& value)
460  {
461  if(hint == this->end()) {
462  if(size() > 0) {
463  if(this->compare(this->back(), value))
464  return this->end();
465  else
466  return this->_find_insert_range(this->begin(), this->end(), value);
467  }
468  return this->end();
469  }
470  if(this->compare(value, *hint)) { // Try just before
471  if(hint == this->begin())
472  return hint;
473  const_iterator before = hint;
474  if(this->compare(*(--before), value))
475  return hint;
476  return this->_find_insert_range(this->begin(), before, value);
477  } else if(this->compare(*hint, value)) { // Try just after
478  const_iterator after = hint;
479  if(++after == this->end() or this->compare(value, *after))
480  return after;
481  return this->_find_insert_range(after, this->end(), value);
482  } else
483  return hint;
484  }
485 
486  template <typename T>
487 #ifdef USE_CXX11
488  iterator _insert_vector(const_iterator it, T&& value)
489 #else
490  iterator _insert_vector(const_iterator it, const T& value)
491 #endif
492  {
493  return _content.insert(this->remove_iterator_const(it), STD_FORWARD(T, value));
494  }
495 
496  template <typename T>
497 #ifdef USE_CXX11
498  iterator _insert(T&& value)
499 #else
500  iterator _insert(const T& value)
501 #endif
502  {
503  iterator found = this->_find_insert_range(this->begin(), this->end(), value);
504  return this->_insert_vector(found, STD_FORWARD(T, value));
505  }
506 
507  template <typename T>
508 #ifdef USE_CXX11
509  iterator _insert_hint(const_iterator hint, T&& value)
510 #else
511  iterator _insert_hint(const_iterator hint, const T& value)
512 #endif
513  {
514  iterator found = this->_find_insert_hint(hint, value);
515  return this->_insert_vector(found, STD_FORWARD(T, value));
516  }
517 
518  bool equiv_keys(const key_type& k1, const key_type& k2) const
519  {
520  return not (this->compare(k1, k2) or this->compare(k2, k1));
521  }
522 
523  bool differ_keys(const key_type& k1, const key_type& k2) const
524  {
525  return this->compare(k1, k2) or this->compare(k2, k1);
526  }
527 
528  bool compare(const key_type& k1, const key_type& k2) const {
529  return _compare(k1, k2);
530  }
531 };
532 
533 template <typename Key, typename Compare, typename Allocator>
534 void swap(multiset_vector<Key, Compare, Allocator>& v1, multiset_vector<Key, Compare, Allocator>& v2)
535 {
536  v1.swap(v2);
537 }
538 
544 template <typename Key, typename Compare = std::less<Key>, class Allocator = std::allocator<Key> >
545 class set_vector : public multiset_vector<Key, Compare, Allocator> {
547 
548 public:
549  typedef typename super_type::key_type key_type;
550  typedef typename super_type::value_type value_type;
551  typedef typename super_type::key_compare key_compare;
552  typedef typename super_type::value_compare value_compare;
553  typedef typename super_type::allocator_type allocator_type;
554  typedef typename super_type::reference reference;
556 
557  typedef typename super_type::pointer pointer;
558  typedef typename super_type::const_pointer const_pointer;
559 
560  typedef typename super_type::iterator iterator;
561  typedef typename super_type::const_iterator const_iterator;
562  typedef typename super_type::size_type size_type;
563  typedef typename super_type::difference_type difference_type;
564 
565  typedef typename super_type::reverse_iterator reverse_iterator;
566  typedef typename super_type::const_reverse_iterator const_reverse_iterator;
567 
569  explicit set_vector(const Compare& comp = Compare(), const Allocator& alloc = Allocator())
571  : super_type(comp, alloc)
572  {
573  }
574 
575  template <typename InputIterator>
576  set_vector(InputIterator first, InputIterator last, const Compare& comp = Compare(),
577  const Allocator& alloc = Allocator())
578  : super_type(first, last, comp, alloc)
579  {
580  this->clean();
581  }
582 
583 #ifdef USE_CXX11
584  set_vector(const set_vector&) = default;
585  set_vector(set_vector&&) = default;
586 #else
587  set_vector(const set_vector& copy)
588  : super_type(copy)
589  {
590  }
591 #endif
592 
593  explicit set_vector(const Allocator& alloc)
594  : super_type(alloc)
595  {
596  }
597 
598  set_vector(const set_vector& copy, const Allocator& alloc)
599  : super_type(copy, alloc)
600  {
601  }
602 
603 #ifdef USE_CXX11
604  set_vector(set_vector&& copy, const Allocator& alloc)
605  : super_type(std::move(copy), alloc)
606  {
607  }
608 
609  set_vector(std::initializer_list<value_type> values, const Compare& comp = Compare(),
610  const Allocator& alloc = Allocator())
611  : set_vector(values.begin(), values.end(), comp, alloc)
612  {
613  }
614 #endif
615 
616  ~set_vector() {
617  }
618 
619 #ifdef USE_CXX11
620  set_vector& operator=(const set_vector&) = default;
621  set_vector& operator=(set_vector&&) = default;
622  set_vector& operator=(std::initializer_list<value_type> content)
623  {
624  super_type::operator=(content);
625  this->clean();
626  return *this;
627  }
628 #else
629  set_vector& operator=(const set_vector& copy)
630  {
631  super_type::operator=(copy);
632  return *this;
633  }
634 #endif
635 
637 
639 
641 #ifdef USE_CXX11
642  template <typename ... Args> std::pair<iterator, bool> emplace(Args&& ... args)
643  {
644  auto value = value_type(std::forward<Args>(args) ...);
645  return this->_insert(std::move(value));
646  }
647  template <typename ... Args> std::pair<iterator, bool> emplace_hint(const_iterator hint, Args&& ... args)
648  {
649  auto value = value_type(std::forward<Args>(args) ...);
650  return this->_insert_hint(hint, std::move(value));
651  }
652 
653  std::pair<iterator, bool> insert(value_type&& value) {
654  return this->_insert(std::move(value));
655  }
656 
657  std::pair<iterator, bool> insert(const_iterator pos, value_type&& value) {
658  return this->_insert_hint(pos, value);
659  }
660 
661  void insert(std::initializer_list<value_type> values)
662  {
663  for(const value_type& v : values)
664  this->_insert(v);
665  }
666 
667 #endif
668 
669  std::pair<iterator, bool> insert(const value_type& value) {
670  return this->_insert(value);
671  }
672 
673  std::pair<iterator, bool> insert(const_iterator pos, const value_type& value)
674  {
675  return this->_insert_hint(pos, value);
676  }
677 
678  template <typename InputIterator> void insert(InputIterator first, InputIterator last)
679  {
680  for(InputIterator it = first; it != last; ++it)
681  this->_insert(*it);
682  }
683 
684  using super_type::erase;
685 
686  size_type erase(const key_type& x)
687  {
688  const_iterator it = std::lower_bound(this->begin(), this->end(), x, this->key_comp());
689  if(it != this->end() and this->equiv_keys(*it, x)) {
690  this->erase(it);
691  return 1u;
692  }
693  return 0u;
694  }
695 
696  void swap(set_vector& other) {
697  super_type::swap(other);
698  }
699 
701 
702 private:
703  void clean()
704  {
705  size_type s = this->size();
706  if(s == 0)
707  return;
708  for(size_t i = s - 1; i > 0; --i) {
709  if(this->equiv_keys((*this)[i], (*this)[i - 1]))
710  this->erase(this->begin() + i);
711  }
712  }
713 
714  std::pair<iterator, bool> _find_insert_range(const_iterator first, const_iterator last,
715  const value_type& value) const
716  {
717  typedef std::pair<const_iterator, bool> result_t;
718  const_iterator pos = std::lower_bound(first, last, value, this->key_comp());
719  return result_t(pos, (pos == last or this->differ_keys(*pos, value)));
720  }
721 
722  std::pair<const_iterator, bool> _find_insert_hint(const_iterator hint, const value_type& value)
723  {
724  typedef std::pair<iterator, bool> result_t;
725  if(hint == this->end()) {
726  if(this->size() > 0) {
727  if(this->compare(this->back(), value))
728  return result_t(this->end(), true);
729  else
730  return _find_insert_range(this->begin(), this->end(), value);
731  }
732  return result_t(this->end(), value);
733  }
734  if(this->compare(value, *hint)) { // Try just before
735  if(hint == this->begin())
736  return result_t(hint, true);
737  const_iterator before = hint;
738  if(this->compare(*(--before), value))
739  return result_t(hint, true);
740  return this->_find_insert_range(this->begin(), before, value);
741  } else if(this->compare(*hint, value)) { // Try just after
742  const_iterator after = hint;
743  if(++after == this->end() or this->compare(value, *after))
744  return result_t(after, true);
745  return this->_find_insert_range(after, this->end(), value);
746  } else
747  return result_t(hint, false);
748  }
749 
750 #ifdef USE_CXX11
751  template <typename T> std::pair<iterator, bool> _insert(T&& value)
752 #else
753  std::pair<iterator, bool> _insert(const value_type& value)
754 #endif
755  {
756  std::pair<iterator, bool> found = this->_find_insert_range(this->begin(), this->end(), value);
757  if(found.second)
758  found.first = this->_insert_vector(found.first, STD_FORWARD(T, value));
759  return found;
760  }
761 
762 #ifdef USE_CXX11
763  template <typename T> std::pair<iterator, bool> _insert_hint(const_iterator hint, T&& value)
764 #else
765  std::pair<iterator, bool> _insert_hint(const_iterator hint, const value_type& value)
766 #endif
767  {
768  std::pair<iterator, bool> found = this->_find_insert_hint(hint, value);
769  if(found.second)
770  found.first = this->_insert_vector(found.first, STD_FORWARD(T, value));
771  return found;
772  }
773 };
774 
775 template <typename Key, typename Compare, typename Allocator>
777 {
778  v1.swap(v2);
779 }
780 
781 #undef STD_FORWARD
782 #undef NOEXCEPT
783 } // namespace util
784 } // namespace mgx
785 #endif // UTIL_SET_VECTOR_H
Implementation of a set using a sorted vector as container.
Definition: SetVector.hpp:545
Implementation of a multiset using a sorted vector as container.
Definition: SetVector.hpp:28
const content_t & vector() const
Return the underlying vector.
Definition: SetVector.hpp:209