Molassembler  3.0.0
Molecule graph and conformer library
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
DynamicArray.h
Go to the documentation of this file.
1 
12 #ifndef INCLUDE_MOLASSEMBLER_TEMPLE_DYNAMIC_ARRAY_H
13 #define INCLUDE_MOLASSEMBLER_TEMPLE_DYNAMIC_ARRAY_H
14 
16 #include <array>
17 #include <cstddef>
18 #include <type_traits>
19 #include <utility>
20 
21 namespace Scine {
22 namespace Molassembler {
23 namespace Temple {
24 
25 template<typename T, std::size_t nItems>
26 class DynamicArray {
27 public:
28  // Forward-declare the iterator types
29  class iterator;
30  class const_iterator;
31 
35  constexpr DynamicArray() : items_ {} {}
36 
42  template<std::size_t ... Inds>
43  constexpr DynamicArray(
44  const DynamicArray& other,
45  std::index_sequence<Inds...> /* inds */
46  ) :items_ {other[Inds]...},
47  count_(other.count_)
48  {}
49 
58  constexpr DynamicArray(const DynamicArray& other)
59  : DynamicArray(other, std::make_index_sequence<nItems>{}) {}
60 
61  /* @brief Helper to the move constructor
62  *
63  * Delegate move constructor to directly form the array mem-initializer with
64  * a parameter pack expansion
65  */
66  template<std::size_t ... Inds>
67  constexpr DynamicArray(
68  DynamicArray&& other,
69  std::index_sequence<Inds...> /* inds */
70  ) :items_ {std::move(other[Inds])...},
71  count_(other.count_)
72  {}
73 
81  constexpr DynamicArray(DynamicArray&& other) noexcept
82  : DynamicArray(std::move(other), std::make_index_sequence<nItems>{}) {}
83 
88  constexpr DynamicArray& operator = (const DynamicArray& other) {
89  for(unsigned i = 0; i < other.count_; ++i) {
90  items_[i] = other.items_[i];
91  }
92  count_ = other.count_;
93  return *this;
94  }
95 
104  constexpr DynamicArray& operator = (DynamicArray&& other) noexcept {
105  for(unsigned i = 0; i < other.count_; ++i) {
106  items_[i] = std::move(other.items_[i]);
107  }
108  count_ = other.count_;
109  return *this;
110  }
111 
112  ~DynamicArray() = default;
114 
115 
119  template<
120  template<typename, std::size_t> class ArrayType,
121  std::size_t N,
122  std::size_t ... Inds
123  > constexpr DynamicArray(
124  const ArrayType<T, N>& other,
125  std::index_sequence<Inds...> /* inds */
126  ) : items_ {other.at(Inds)...},
127  count_(N)
128  {}
129 
131  template<
132  template<typename, std::size_t> class ArrayType,
133  std::size_t N
134  > constexpr DynamicArray(
135  const ArrayType<T, N>& other,
136  std::enable_if_t<(N <= nItems)>* /* f */ = 0 // Only possible for some sizes
137  ) : DynamicArray(other, std::make_index_sequence<N>{})
138  {}
139 
141  template<typename ...Args>
142  constexpr DynamicArray(Args... args)
143  : items_ {static_cast<T>(args)...},
144  count_(sizeof...(args))
145  {}
147 
150 
157  constexpr void push_back(const T& item) {
158  if(count_ < nItems) {
159  items_[count_] = item;
160  count_ += 1;
161  } else {
162  throw "Dynamic array is already full!";
163  }
164  }
165 
167  constexpr void push_back(T&& item) {
168  if(count_ < nItems) {
169  items_[count_] = std::move(item);
170  count_ += 1;
171  }
172  }
173 
178  constexpr void pop_back() {
179  if(count_ > 0) {
180  count_ -= 1;
181  }
182  }
183 
188  constexpr void pop_back(const unsigned numberToPop) {
189  if(count_ > numberToPop) {
190  count_ -= numberToPop;
191  }
192  }
193 
201  constexpr DynamicArray<T, nItems> splice(const unsigned fromIndex) {
202  DynamicArray<T, nItems> spliced;
203 
204  for(unsigned i = fromIndex; i < count_; ++i) {
205  spliced.push_back(std::move(items_[i]));
206  }
207 
208  pop_back(count_ - fromIndex);
209 
210  return spliced;
211  }
213 
216 
220  PURITY_WEAK constexpr bool validIndex(const unsigned index) const noexcept {
221  return (index < count_);
222  }
223 
228  PURITY_WEAK constexpr std::size_t size() const noexcept {
229  return count_;
230  }
232 
235 
242  PURITY_WEAK constexpr T& operator[] (const unsigned index) noexcept {
243  // Defined behavior instead of UB
244  if(!validIndex(index)) {
245  return back();
246  }
247 
248  return items_[index];
249  }
250 
252  PURITY_WEAK constexpr const T& operator[] (const unsigned index) const noexcept {
253  if(!validIndex(index)) {
254  return back();
255  }
256 
257  return items_[index];
258  }
259 
261  PURITY_WEAK constexpr T& at(const unsigned index) noexcept {
262  // Not strong purity because items_ is just a pointer!
263  return this->operator[](index);
264  }
265 
267  PURITY_WEAK constexpr const T& at(const unsigned index) const noexcept {
268  // Not strong purity because items_ is just a pointer!
269  return this->operator[](index);
270  }
271 
276  PURITY_WEAK constexpr T& front() noexcept {
277  return items_[0];
278  }
279 
284  PURITY_WEAK constexpr const T& front() const noexcept {
285  return items_[0];
286  }
287 
293  constexpr T& back() noexcept {
294  /* No UB in constexpr functions allowed, so we must return something within
295  * the array, which is always an initialized value
296  */
297  if(count_ == 0) {
298  return front();
299  }
300 
301  return items_[count_ - 1];
302  }
303 
309  PURITY_WEAK constexpr const T& back() const noexcept {
310  /* NO UB in constexpr functions allowed, so we must return something within
311  * the array, which is always an initialized value
312  */
313  if(count_ == 0) {
314  return front();
315  }
316 
317  return items_[count_ - 1];
318  }
320 
323 
327  constexpr void clear() {
328  count_ = 0;
329  }
330 
335  constexpr void copyIn(const DynamicArray<T, nItems>& other) {
336  if(other.size() + size() > nItems) {
337  throw "DynamicArray to be copied in has too many elements to fit!";
338  }
339 
340  for(auto it = other.begin(); it != other.end(); ++it) {
341  push_back(*it);
342  }
343  }
344 
350  constexpr void insertAt(
351  iterator insertPositionIter,
352  const T& item
353  ) {
354  // In case there is no object larger than the one being inserted, add to end
355  if(insertPositionIter == end()) {
356  push_back(item);
357  } else {
358  moveElementsRightUntil_(insertPositionIter);
359 
360  // Copy in the item
361  *insertPositionIter = item;
362  }
363  }
364 
370  constexpr void insertAt(
371  iterator insertPositionIter,
372  T&& item
373  ) {
374  // In case there is no object larger than the one being inserted, add to end
375  if(insertPositionIter == end()) {
376  push_back(item);
377  } else {
378  moveElementsRightUntil_(insertPositionIter);
379 
380  // Move in the item
381  *insertPositionIter = std::move(item);
382  }
383  }
384 
390  constexpr void removeAt(iterator insertPositionIter) {
391  if(insertPositionIter == end()) {
392  throw "Cannot remove item at end iterator!";
393  }
394 
395  // Rename for clarity
396  auto& leftIter = insertPositionIter;
397  auto rightIter = insertPositionIter + 1;
398 
399  while(rightIter != end()) {
400  *leftIter = std::move(*rightIter);
401 
402  ++leftIter;
403  ++rightIter;
404  }
405 
406  pop_back();
407  }
409 
412 
416  PURITY_WEAK constexpr bool operator == (const DynamicArray& other) const noexcept {
417  if(count_ != other.count_) {
418  return false;
419  }
420 
421  for(unsigned i = 0; i < count_; ++i) {
422  if(items_[i] != other.items_[i]) {
423  return false;
424  }
425  }
426 
427  return true;
428  }
429 
431  PURITY_WEAK constexpr bool operator != (const DynamicArray& other) const noexcept {
432  return !(*this == other);
433  }
434 
439  PURITY_WEAK constexpr bool operator < (const DynamicArray& other) const noexcept {
440  if(count_ < other.count_) {
441  return true;
442  }
443 
444  for(unsigned i = 0; i < count_; ++i) {
445  if(items_[i] < other.items_[i]) {
446  return true;
447  }
448 
449  if(items_[i] > other.items_[i]) {
450  return false;
451  }
452  }
453 
454  return false;
455  }
456 
458  PURITY_WEAK constexpr bool operator > (const DynamicArray& other) const noexcept {
459  return (other < *this);
460  }
462 
465 
468  class iterator {
469  public:
470  using iterator_category = std::random_access_iterator_tag;
471  using value_type = T;
472  using difference_type = std::ptrdiff_t;
473  using pointer = const T*;
474  using reference = T&;
475 
476  constexpr explicit iterator(
477  DynamicArray& instance,
478  unsigned&& initPosition
479  ) : baseRef_(instance),
480  position_(initPosition)
481  {}
482 
483  constexpr iterator(const iterator& other)
484  : baseRef_(other.baseRef_),
485  position_(other.position_)
486  {}
487 
488  constexpr iterator& operator = (const iterator& other) {
489  baseRef_ = other.baseRef_;
490  position_ = other.position_;
491 
492  return *this;
493  }
494 
495  constexpr iterator& operator ++ () {
496  position_ += 1;
497  return *this;
498  }
499 
500  constexpr iterator operator ++ (int) {
501  iterator retval = *this;
502  ++(*this);
503  return retval;
504  }
505 
506  constexpr iterator& operator --() {
507  position_ -= 1;
508  return *this;
509  }
510 
511  constexpr iterator operator -- (int) {
512  iterator retval = *this;
513  --(*this);
514  return retval;
515  }
516 
517  constexpr iterator operator + (const int& increment) {
518  iterator retval = *this;
519  retval += increment;
520  return retval;
521  }
522 
523  constexpr iterator operator - (const int& increment) {
524  iterator retval = *this;
525  retval -= increment;
526  return retval;
527  }
528 
529  constexpr iterator& operator += (const int& increment) {
530  position_ += increment;
531  return *this;
532  }
533 
534  constexpr iterator& operator -= (const int& increment) {
535  position_ -= increment;
536  return *this;
537  }
538 
539  PURITY_WEAK constexpr std::ptrdiff_t operator - (const iterator& other) const noexcept {
540  return (
541  static_cast<std::ptrdiff_t>(position_)
542  - static_cast<std::ptrdiff_t>(other.position_)
543  );
544  }
545 
546  PURITY_WEAK constexpr bool operator == (const iterator& other) const noexcept {
547  return (
548  &baseRef_ == &other.baseRef_
549  && position_ == other.position_
550  );
551  }
552 
553  PURITY_WEAK constexpr bool operator != (const iterator& other) const noexcept {
554  return !(
555  *this == other
556  );
557  }
558 
559  PURITY_WEAK constexpr reference operator * () const noexcept {
560  return baseRef_[position_];
561  }
562 
563  private:
564  DynamicArray& baseRef_;
565  unsigned position_;
566  };
567 
568  PURITY_WEAK constexpr iterator begin() noexcept {
569  return iterator(*this, 0);
570  }
571 
572  PURITY_WEAK constexpr iterator end() noexcept {
573  return iterator(*this, count_);
574  }
575 
580  private:
581  const DynamicArray& baseRef_;
582  unsigned position_;
583 
584  public:
585  using iterator_category = std::random_access_iterator_tag;
586  using value_type = T;
587  using difference_type = std::ptrdiff_t;
588  using pointer = const T*;
589  using reference = const T&;
590 
591  constexpr explicit const_iterator(
592  const DynamicArray& instance,
593  unsigned&& initPosition
594  ) : baseRef_(instance),
595  position_(initPosition)
596  {}
597 
598  constexpr const_iterator(const const_iterator& other)
599  : baseRef_(other.baseRef_),
600  position_(other.position_)
601  {}
602 
603  constexpr const_iterator& operator = (const const_iterator& other) {
604  if(baseRef_ != other.baseRef_) {
605  throw "Trying to assign const_iterator to other base DynamicArray!";
606  }
607 
608  position_ = other.position_;
609 
610  return *this;
611  }
612 
613  constexpr const_iterator& operator ++ () {
614  position_ += 1;
615  return *this;
616  }
617 
618  constexpr const_iterator operator ++ (int) {
619  const_iterator retval = *this;
620  ++(*this);
621  return retval;
622  }
623 
624  constexpr const_iterator& operator --() {
625  position_ -= 1;
626  return *this;
627  }
628 
629  constexpr const_iterator operator -- (int) {
630  const_iterator retval = *this;
631  --(*this);
632  return retval;
633  }
634 
635  constexpr const_iterator operator + (const int& increment) {
636  const_iterator retval = *this;
637  retval += increment;
638  return retval;
639  }
640 
641  constexpr const_iterator operator - (const int& increment) {
642  const_iterator retval = *this;
643  retval -= increment;
644  return retval;
645  }
646 
647  constexpr const_iterator& operator += (const int& increment) {
648  position_ += increment;
649  return *this;
650  }
651 
652  constexpr const_iterator& operator -= (const int& increment) {
653  position_ -= increment;
654  return *this;
655  }
656 
657  PURITY_WEAK constexpr std::ptrdiff_t operator - (const const_iterator& other) const noexcept {
658  return (
659  static_cast<std::ptrdiff_t>(position_)
660  - static_cast<std::ptrdiff_t>(other.position_)
661  );
662  }
663 
664  PURITY_WEAK constexpr bool operator == (const const_iterator& other) const noexcept {
665  return (
666  &baseRef_ == &other.baseRef_
667  && position_ == other.position_
668  );
669  }
670 
671  PURITY_WEAK constexpr bool operator != (const const_iterator& other) const noexcept {
672  return !(
673  *this == other
674  );
675  }
676 
677  PURITY_WEAK constexpr reference operator * () const noexcept {
678  return baseRef_[position_];
679  }
680  };
681 
682  PURITY_WEAK constexpr const_iterator begin() const noexcept {
683  return const_iterator(*this, 0);
684  }
685 
686  PURITY_WEAK constexpr const_iterator end() const noexcept {
687  return const_iterator(*this, count_);
688  }
690 
694  PURITY_WEAK constexpr operator std::array<T, nItems> () const noexcept {
695  return makeArray(std::make_index_sequence<nItems>{});
696  }
698 
699 private:
702  T items_[nItems];
703  std::size_t count_ = 0;
705 
708  template<std::size_t ... Inds>
709  std::array<T, nItems> makeArray(std::index_sequence<Inds...> /* inds */) {
710  return {{
711  items_[Inds]...
712  }};
713  }
714 
715  constexpr void moveElementsRightUntil_(const iterator& position) {
716  // Add the last element in the array onto the end
717  push_back(
718  back()
719  );
720 
721  // Move everything up to and including the lower bound back
722  auto rightIter = end();
723  rightIter -= 2;
724  auto leftIter = rightIter - 1;
725 
726  while(rightIter != position) {
727  *rightIter = std::move(*leftIter);
728 
729  --leftIter;
730  --rightIter;
731  }
732  }
734 };
735 
739 template<
740  template<typename, std::size_t> class ArrayType,
741  typename T,
742  std::size_t N,
743  class BinaryFunction
744 > constexpr DynamicArray<
745  DynamicArray<T, N>,
746  N
748  const ArrayType<T, N>& data,
749  BinaryFunction&& equalityComparator
750 ) {
751  // Maximal dimensions if all equal is 1xN, if all unequal Nx1
752  DynamicArray<
754  N
755  > groups;
756 
757  for(auto iter = data.begin(); iter != data.end(); ++iter) {
758  bool foundEqual = false;
759 
760  for(auto& group : groups) {
761  if(equalityComparator(*iter, *group.begin())) {
762  group.push_back(*iter);
763  foundEqual = true;
764  break;
765  }
766  }
767 
768  if(!foundEqual) {
769  groups.push_back(
770  DynamicArray<T, N> {*iter}
771  );
772  }
773  }
774 
775  return groups;
776 }
777 
778 template<typename T, std::size_t N>
779 DynamicArray<T, N> merge(
780  const DynamicArray<T, N>& a,
781  const DynamicArray<T, N>& b
782 ) {
783  if(a.size() + b.size() > N) {
784  throw "DynamicArrays to be merged have too many elements!";
785  }
786 
787  DynamicArray<T, N> merged {a};
788  merged.copyIn(b);
789  return merged;
790 }
791 
792 } // namespace Temple
793 } // namespace Molassembler
794 } // namespace Scine
795 
796 #endif
constexpr DynamicArray(const DynamicArray &other, std::index_sequence< Inds...>)
Helper to the copy constructor.
Definition: DynamicArray.h:43
auto at(Container &&container)
Make functor calling at on arguments.
Definition: Functor.h:58
#define PURITY_WEAK
Definition: Preprocessor.h:36
Definition: DynamicArray.h:26
unsigned size(Shape shape)
Fetch the number of vertices of a shape.
constexpr DynamicArray< DynamicArray< T, N >, N > groupByEquality(const ArrayType< T, N > &data, BinaryFunction &&equalityComparator)
Definition: DynamicArray.h:747
Defines a set of useful preprocessor macros.
constexpr DynamicArray(DynamicArray &&other) noexcept
Move constructor.
Definition: DynamicArray.h:81
constexpr DynamicArray()
Default constructor.
Definition: DynamicArray.h:35
count_(other.count_)
Default constructor.
Definition: DynamicArray.h:71
Nonmodifiable data iterator.
Definition: DynamicArray.h:579
constexpr DynamicArray(const ArrayType< T, N > &other, std::enable_if_t<(N<=nItems)> *=0)
Construct from any size of other array-like classes.
Definition: DynamicArray.h:134
constexpr DynamicArray(const DynamicArray &other)
Copy constructor.
Definition: DynamicArray.h:58
constexpr DynamicArray(const ArrayType< T, N > &other, std::index_sequence< Inds...>)
Construct from any-size array-like container using same trick as copy ctor.
Definition: DynamicArray.h:123