DynamicArray.h

Go to the documentation of this file.

#ifndef INCLUDE_MOLASSEMBLER_TEMPLE_DYNAMIC_ARRAY_H
#define INCLUDE_MOLASSEMBLER_TEMPLE_DYNAMIC_ARRAY_H

#include "Molassembler/Temple/Preprocessor.h"
#include <array>
#include <cstddef>
#include <type_traits>
#include <utility>

namespace Scine {
namespace Molassembler {
namespace Temple {

template<typename T, std::size_t nItems>
class DynamicArray {
public:
  // Forward-declare the iterator types
  class iterator;
  class const_iterator;

  constexpr DynamicArray() : items_ {} {}

  template<std::size_t ... Inds>
  constexpr DynamicArray(
    const DynamicArray& other,
    std::index_sequence<Inds...> /* inds */
  ) :items_ {other[Inds]...},
     count_(other.count_)
  {}

  constexpr DynamicArray(const DynamicArray& other)
    : DynamicArray(other, std::make_index_sequence<nItems>{}) {}

  /* @brief Helper to the move constructor
   *
   * Delegate move constructor to directly form the array mem-initializer with
   * a parameter pack expansion
   */
  template<std::size_t ... Inds>
  constexpr DynamicArray(
    DynamicArray&& other,
    std::index_sequence<Inds...> /* inds */
  ) :items_ {std::move(other[Inds])...},
     count_(other.count_)
  {}

  constexpr DynamicArray(DynamicArray&& other) noexcept
    : DynamicArray(std::move(other), std::make_index_sequence<nItems>{}) {}

  constexpr DynamicArray& operator = (const DynamicArray& other) {
    for(unsigned i = 0; i < other.count_; ++i) {
      items_[i] = other.items_[i];
    }
    count_ = other.count_;
    return *this;
  }

  constexpr DynamicArray& operator = (DynamicArray&& other) noexcept {
    for(unsigned i = 0; i < other.count_; ++i) {
      items_[i] = std::move(other.items_[i]);
    }
    count_ = other.count_;
    return *this;
  }

  ~DynamicArray() = default;


  template<
    template<typename, std::size_t> class ArrayType,
    std::size_t N,
    std::size_t ... Inds
  > constexpr DynamicArray(
    const ArrayType<T, N>& other,
    std::index_sequence<Inds...> /* inds */
  ) : items_ {other.at(Inds)...},
      count_(N)
  {}

  template<
    template<typename, std::size_t> class ArrayType,
    std::size_t N
  > constexpr DynamicArray(
    const ArrayType<T, N>& other,
    std::enable_if_t<(N <= nItems)>* /* f */ = 0 // Only possible for some sizes
  ) : DynamicArray(other, std::make_index_sequence<N>{})
  {}

  template<typename ...Args>
  constexpr DynamicArray(Args... args)
    : items_ {static_cast<T>(args)...},
      count_(sizeof...(args))
  {}


  constexpr void push_back(const T& item) {
    if(count_ < nItems) {
      items_[count_] = item;
      count_ += 1;
    } else {
      throw "Dynamic array is already full!";
    }
  }

  constexpr void push_back(T&& item) {
    if(count_ < nItems) {
      items_[count_] = std::move(item);
      count_ += 1;
    }
  }

  constexpr void pop_back() {
    if(count_ > 0) {
      count_ -= 1;
    }
  }

  constexpr void pop_back(const unsigned numberToPop) {
    if(count_ > numberToPop) {
      count_ -= numberToPop;
    }
  }

  constexpr DynamicArray<T, nItems> splice(const unsigned fromIndex) {
    DynamicArray<T, nItems> spliced;

    for(unsigned i = fromIndex; i < count_; ++i) {
      spliced.push_back(std::move(items_[i]));
    }

    pop_back(count_ - fromIndex);

    return spliced;
  }


  PURITY_WEAK constexpr bool validIndex(const unsigned index) const noexcept {
    return (index < count_);
  }

  PURITY_WEAK constexpr std::size_t size() const noexcept {
    return count_;
  }


  PURITY_WEAK constexpr T& operator[] (const unsigned index) noexcept {
    // Defined behavior instead of UB
    if(!validIndex(index)) {
      return back();
    }

    return items_[index];
  }

  PURITY_WEAK constexpr const T& operator[] (const unsigned index) const noexcept {
    if(!validIndex(index)) {
      return back();
    }

    return items_[index];
  }

  PURITY_WEAK constexpr T& at(const unsigned index) noexcept {
    // Not strong purity because items_ is just a pointer!
    return this->operator[](index);
  }

  PURITY_WEAK constexpr const T& at(const unsigned index) const noexcept {
    // Not strong purity because items_ is just a pointer!
    return this->operator[](index);
  }

  PURITY_WEAK constexpr T& front() noexcept {
    return items_[0];
  }

  PURITY_WEAK constexpr const T& front() const noexcept {
    return items_[0];
  }

  constexpr T& back() noexcept {
    /* No UB in constexpr functions allowed, so we must return something within
     * the array, which is always an initialized value
     */
    if(count_ == 0) {
      return front();
    }

    return items_[count_ - 1];
  }

  PURITY_WEAK constexpr const T& back() const noexcept {
    /* NO UB in constexpr functions allowed, so we must return something within
     * the array, which is always an initialized value
     */
    if(count_ == 0) {
      return front();
    }

    return items_[count_ - 1];
  }


  constexpr void clear() {
    count_ = 0;
  }

  constexpr void copyIn(const DynamicArray<T, nItems>& other) {
    if(other.size() + size() > nItems) {
      throw "DynamicArray to be copied in has too many elements to fit!";
    }

    for(auto it = other.begin(); it != other.end(); ++it) {
      push_back(*it);
    }
  }

  constexpr void insertAt(
    iterator insertPositionIter,
    const T& item
  ) {
    // In case there is no object larger than the one being inserted, add to end
    if(insertPositionIter == end()) {
      push_back(item);
    } else {
      moveElementsRightUntil_(insertPositionIter);

      // Copy in the item
      *insertPositionIter = item;
    }
  }

  constexpr void insertAt(
    iterator insertPositionIter,
    T&& item
  ) {
    // In case there is no object larger than the one being inserted, add to end
    if(insertPositionIter == end()) {
      push_back(item);
    } else {
      moveElementsRightUntil_(insertPositionIter);

      // Move in the item
      *insertPositionIter = std::move(item);
    }
  }

  constexpr void removeAt(iterator insertPositionIter) {
    if(insertPositionIter == end()) {
      throw "Cannot remove item at end iterator!";
    }

    // Rename for clarity
    auto& leftIter = insertPositionIter;
    auto rightIter = insertPositionIter + 1;

    while(rightIter != end()) {
      *leftIter = std::move(*rightIter);

      ++leftIter;
      ++rightIter;
    }

    pop_back();
  }


  PURITY_WEAK constexpr bool operator == (const DynamicArray& other) const noexcept {
    if(count_ != other.count_) {
      return false;
    }

    for(unsigned i = 0; i < count_; ++i) {
      if(items_[i] != other.items_[i]) {
        return false;
      }
    }

    return true;
  }

  PURITY_WEAK constexpr bool operator != (const DynamicArray& other) const noexcept {
    return !(*this == other);
  }

  PURITY_WEAK constexpr bool operator < (const DynamicArray& other) const noexcept {
    if(count_ < other.count_) {
      return true;
    }

    for(unsigned i = 0; i < count_; ++i) {
      if(items_[i] < other.items_[i]) {
        return true;
      }

      if(items_[i] > other.items_[i]) {
        return false;
      }
    }

    return false;
  }

  PURITY_WEAK constexpr bool operator > (const DynamicArray& other) const noexcept {
    return (other < *this);
  }


  class iterator {
  public:
    using iterator_category = std::random_access_iterator_tag;
    using value_type = T;
    using difference_type = std::ptrdiff_t;
    using pointer = const T*;
    using reference = T&;

    constexpr explicit iterator(
      DynamicArray& instance,
      unsigned&& initPosition
    ) : baseRef_(instance),
        position_(initPosition)
    {}

    constexpr iterator(const iterator& other)
      : baseRef_(other.baseRef_),
        position_(other.position_)
    {}

    constexpr iterator& operator = (const iterator& other) {
      baseRef_ = other.baseRef_;
      position_ = other.position_;

      return *this;
    }

    constexpr iterator& operator ++ () {
      position_ += 1;
      return *this;
    }

    constexpr iterator operator ++ (int) {
      iterator retval = *this;
      ++(*this);
      return retval;
    }

    constexpr iterator& operator --() {
      position_ -= 1;
      return *this;
    }

    constexpr iterator operator -- (int) {
      iterator retval = *this;
      --(*this);
      return retval;
    }

    constexpr iterator operator + (const int& increment) {
      iterator retval = *this;
      retval += increment;
      return retval;
    }

    constexpr iterator operator - (const int& increment) {
      iterator retval = *this;
      retval -= increment;
      return retval;
    }

    constexpr iterator& operator += (const int& increment) {
      position_ += increment;
      return *this;
    }

    constexpr iterator& operator -= (const int& increment) {
      position_ -= increment;
      return *this;
    }

    PURITY_WEAK constexpr std::ptrdiff_t operator - (const iterator& other) const noexcept {
      return (
        static_cast<std::ptrdiff_t>(position_)
        - static_cast<std::ptrdiff_t>(other.position_)
      );
    }

    PURITY_WEAK constexpr bool operator == (const iterator& other) const noexcept {
      return (
        &baseRef_ == &other.baseRef_
        && position_ == other.position_
      );
    }

    PURITY_WEAK constexpr bool operator != (const iterator& other) const noexcept {
      return !(
        *this == other
      );
    }

    PURITY_WEAK constexpr reference operator * () const noexcept {
      return baseRef_[position_];
    }

  private:
    DynamicArray& baseRef_;
    unsigned position_;
  };

  PURITY_WEAK constexpr iterator begin() noexcept {
    return iterator(*this, 0);
  }

  PURITY_WEAK constexpr iterator end() noexcept {
    return iterator(*this, count_);
  }

  class const_iterator {
  private:
    const DynamicArray& baseRef_;
    unsigned position_;

  public:
    using iterator_category = std::random_access_iterator_tag;
    using value_type = T;
    using difference_type = std::ptrdiff_t;
    using pointer = const T*;
    using reference = const T&;

    constexpr explicit const_iterator(
      const DynamicArray& instance,
      unsigned&& initPosition
    ) : baseRef_(instance),
        position_(initPosition)
    {}

    constexpr const_iterator(const const_iterator& other)
      : baseRef_(other.baseRef_),
        position_(other.position_)
    {}

    constexpr const_iterator& operator = (const const_iterator& other) {
      if(baseRef_ != other.baseRef_) {
        throw "Trying to assign const_iterator to other base DynamicArray!";
      }

      position_ = other.position_;

      return *this;
    }

    constexpr const_iterator& operator ++ () {
      position_ += 1;
      return *this;
    }

    constexpr const_iterator operator ++ (int) {
      const_iterator retval = *this;
      ++(*this);
      return retval;
    }

    constexpr const_iterator& operator --() {
      position_ -= 1;
      return *this;
    }

    constexpr const_iterator operator -- (int) {
      const_iterator retval = *this;
      --(*this);
      return retval;
    }

    constexpr const_iterator operator + (const int& increment) {
      const_iterator retval = *this;
      retval += increment;
      return retval;
    }

    constexpr const_iterator operator - (const int& increment) {
      const_iterator retval = *this;
      retval -= increment;
      return retval;
    }

    constexpr const_iterator& operator += (const int& increment) {
      position_ += increment;
      return *this;
    }

    constexpr const_iterator& operator -= (const int& increment) {
      position_ -= increment;
      return *this;
    }

    PURITY_WEAK constexpr std::ptrdiff_t operator - (const const_iterator& other) const noexcept {
      return (
        static_cast<std::ptrdiff_t>(position_)
        - static_cast<std::ptrdiff_t>(other.position_)
      );
    }

    PURITY_WEAK constexpr bool operator == (const const_iterator& other) const noexcept {
      return (
        &baseRef_ == &other.baseRef_
        && position_ == other.position_
      );
    }

    PURITY_WEAK constexpr bool operator != (const const_iterator& other) const noexcept {
      return !(
        *this == other
      );
    }

    PURITY_WEAK constexpr reference operator * () const noexcept {
      return baseRef_[position_];
    }
  };

  PURITY_WEAK constexpr const_iterator begin() const noexcept {
    return const_iterator(*this, 0);
  }

  PURITY_WEAK constexpr const_iterator end() const noexcept {
    return const_iterator(*this, count_);
  }

  PURITY_WEAK constexpr operator std::array<T, nItems> () const noexcept {
    return makeArray(std::make_index_sequence<nItems>{});
  }

private:
  T items_[nItems];
  std::size_t count_ = 0;

  template<std::size_t ... Inds>
  std::array<T, nItems> makeArray(std::index_sequence<Inds...> /* inds */) {
    return {{
      items_[Inds]...
    }};
  }

  constexpr void moveElementsRightUntil_(const iterator& position) {
    // Add the last element in the array onto the end
    push_back(
      back()
    );

    // Move everything up to and including the lower bound back
    auto rightIter = end();
    rightIter -= 2;
    auto leftIter = rightIter - 1;

    while(rightIter != position) {
      *rightIter = std::move(*leftIter);

      --leftIter;
      --rightIter;
    }
  }
};

template<
  template<typename, std::size_t> class ArrayType,
  typename T,
  std::size_t N,
  class BinaryFunction
> constexpr DynamicArray<
  DynamicArray<T, N>,
  N
> groupByEquality(
  const ArrayType<T, N>& data,
  BinaryFunction&& equalityComparator
) {
  // Maximal dimensions if all equal is 1xN, if all unequal Nx1
  DynamicArray<
    DynamicArray<T, N>,
    N
  > groups;

  for(auto iter = data.begin(); iter != data.end(); ++iter) {
    bool foundEqual = false;

    for(auto& group : groups) {
      if(equalityComparator(*iter, *group.begin())) {
        group.push_back(*iter);
        foundEqual = true;
        break;
      }
    }

    if(!foundEqual) {
      groups.push_back(
        DynamicArray<T, N> {*iter}
      );
    }
  }

  return groups;
}

template<typename T, std::size_t N>
DynamicArray<T, N> merge(
  const DynamicArray<T, N>& a,
  const DynamicArray<T, N>& b
) {
  if(a.size() + b.size() > N) {
    throw "DynamicArrays to be merged have too many elements!";
  }

  DynamicArray<T, N> merged {a};
  merged.copyIn(b);
  return merged;
}

} // namespace Temple
} // namespace Molassembler
} // namespace Scine

#endif