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