StaticVector.hpp

#pragma once

#include <algorithm>
#include <initializer_list>
#include <numeric>
#include <memory>
#include <new>
#include <stdexcept>
#include <cstdint>
#include <cstddef>

namespace shouth
{
namespace internal
{
  template <typename Iterator>
  inline constexpr bool is_forward_iterator_v =
    std::is_base_of_v<std::forward_iterator_tag, typename std::iterator_traits<Iterator>::iterator_category>;
}

template <typename T, std::size_t Capacity>
class StaticVector {
public:
  using value_type = T;
  using reference = value_type &;
  using const_reference = const value_type &;
  using pointer = value_type *;
  using const_pointer = const value_type *;
  using iterator = pointer;
  using const_iterator = const_pointer;
  using reverse_iterator = std::reverse_iterator<iterator>;
  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
  using size_type = std::size_t;
  using difference_type = std::ptrdiff_t;

  StaticVector() noexcept
  { }

  explicit StaticVector(size_type size)
  { _construct_back(size); }

  explicit StaticVector(size_type size, const_reference value)
  { _construct_back(size, value); }

  StaticVector(const StaticVector &that)
  { _construct_back(that.begin(), that.size()); }

  StaticVector(StaticVector &&that)
  { _construct_back(std::move_iterator{ that.begin() }, that.size()); }

  template <
    typename ForwardIterator,
    typename = std::enable_if_t<internal::is_forward_iterator_v<ForwardIterator>>>
  StaticVector(ForwardIterator first, ForwardIterator last)
  { _construct_back(first, std::distance(first, last)); }

  StaticVector(std::initializer_list<value_type> list)
  { _construct_back(list.begin(), list.size()); }

  ~StaticVector()
  { clear(); }

  auto operator=(const StaticVector &that) -> StaticVector &
  {
    if (this != &that) {
      assign(that.begin(), that.end());
    }
    return *this;
  }

  auto operator=(StaticVector &&that) -> StaticVector &
  {
    if (this != &that) {
      assign(std::move_iterator{ that.begin() }, std::move_iterator{ that.end() });
    }
    return *this;
  }

  auto operator=(std::initializer_list<value_type> list) -> StaticVector &
  {
    assign(list.begin(), list.end());
    return *this;
  }

  [[nodiscard]]
  auto begin() noexcept -> iterator
  { return _begin_ptr(); }

  [[nodiscard]]
  auto begin() const noexcept -> const_iterator
  { return _begin_ptr(); }

  [[nodiscard]]
  auto end() noexcept -> iterator
  { return _end_ptr(); }

  [[nodiscard]]
  auto end() const noexcept -> const_iterator
  { return _end_ptr(); }

  [[nodiscard]]
  auto cbegin() const noexcept -> const_iterator
  { return begin(); }

  [[nodiscard]]
  auto cend() const noexcept -> const_iterator
  { return end(); }

  [[nodiscard]]
  auto rbegin() noexcept -> reverse_iterator
  { return reverse_iterator{ end() }; }

  [[nodiscard]]
  auto rbegin() const noexcept -> const_reverse_iterator
  { return const_reverse_iterator{ end() }; }

  [[nodiscard]]
  auto rend() noexcept -> reverse_iterator
  { return reverse_iterator{ begin() }; }

  [[nodiscard]]
  auto rend() const noexcept -> const_reverse_iterator
  { return const_reverse_iterator{ begin() }; }

  [[nodiscard]]
  auto crbegin() const noexcept -> const_reverse_iterator
  { return rbegin(); }

  [[nodiscard]]
  auto crend() const noexcept -> const_reverse_iterator
  { return rend(); }

  [[nodiscard]]
  auto size() const noexcept -> size_type
  { return _size; }

  [[nodiscard]]
  auto max_size() const noexcept -> size_type
  { return Capacity; }

  [[nodiscard]]
  auto capacity() const noexcept -> size_type
  { return Capacity; }

  [[nodiscard]]
  auto empty() const noexcept -> bool
  { return size() == 0; }

  [[nodiscard]]
  auto full() const noexcept -> bool
  { return size() == capacity(); }

  [[nodiscard]]
  auto operator[](size_type index) noexcept -> reference
  { return _begin_ptr()[index]; }

  [[nodiscard]]
  auto operator[](size_type index) const noexcept -> const_reference
  { return _begin_ptr()[index]; }

  [[nodiscard]]
  auto at(size_type index) -> reference
  {
    _check_index(index);
    return (*this)[index];
  }

  [[nodiscard]]
  auto at(size_type index) const -> const_reference
  {
    _check_index(index);
    return (*this)[index];
  }

  [[nodiscard]]
  auto data() noexcept -> pointer
  { return _begin_ptr(); }

  [[nodiscard]]
  auto data() const noexcept -> const_pointer
  { return _begin_ptr(); }

  [[nodiscard]]
  auto front() noexcept -> reference
  { return *_begin_ptr(); }

  [[nodiscard]]
  auto front() const noexcept -> const_reference
  { return *_begin_ptr(); }

  [[nodiscard]]
  auto back() noexcept -> reference
  { return *(_end_ptr() - 1); }

  [[nodiscard]]
  auto back() const noexcept -> const_reference
  { return *(_end_ptr() - 1); }

  auto resize(size_type len) -> void
  {
    if (len < size()) {
      _destruct_back(_begin_ptr() + len);
    } else if (len > size()) {
      _construct_back(len - size());
    }
  }

  auto resize(size_type len, const_reference value) -> void
  {
    if (len < size()) {
      _destruct_back(_begin_ptr() + len);
    } else if (len > size()) {
      _construct_back(len - size(), value);
    }
  }

  template <typename ForwardIterator>
  auto assign(ForwardIterator first, ForwardIterator last)
    -> std::enable_if_t<internal::is_forward_iterator_v<ForwardIterator>>
  {
    size_type len = static_cast<size_type>(std::distance(first, last));
    if (len > size()) {
      ForwardIterator middle = first;
      std::advance(middle, size());
      _construct_back(middle, len - size());
      len = size();
    }
    std::copy_n(first, len, _begin_ptr());
  }

  auto assign(size_type len, const_reference value) -> void
  {
    if (len > size()) {
      _construct_back(len - size(), value);
      len = size();
    }
    std::fill_n(_begin_ptr(), len, value);
  }

  auto assign(std::initializer_list<value_type> list) -> void
  { assign(list.begin(), list.end()); }

  auto push_back(const_reference value) -> void
  { _construct_one_back(value); }

  auto push_back(value_type &&value) -> void
  { _construct_one_back(std::move(value)); }

  template <typename ...Args>
  auto emplace_back(Args &&...args) -> reference
  {
    _construct_one_back(std::forward<Args>(args)...);
    return back();
  }

  auto pop_back() -> void
  { _destruct_one_back(); }

  auto insert(const_iterator position, const_reference value) -> iterator
  {
    pointer p = _begin_ptr() + (position - cbegin());
    if (p == _end_ptr()) {
      _construct_one_back(value);
    } else {
      value_type tmp(value);
      _shift_backward(p, _end_ptr(), p + 1);
      *p = std::move(tmp);
    }
    return p;
  }

  auto insert(const_iterator position, value_type &&value) -> iterator
  {
    pointer p = _begin_ptr() + (position - cbegin());
    if (p == _end_ptr()) {
      _construct_one_back(std::move(value));
    } else {
      value_type tmp(std::move(value));
      _shift_backward(p, _end_ptr(), p + 1);
      *p = std::move(tmp);
    }
    return p;
  }

  template <typename ...Args>
  auto emplace(const_iterator position, Args &&...args) -> iterator
  {
    pointer p = _begin_ptr() + (position - cbegin());
    if (p == _end_ptr()) {
      _construct_one_back(std::forward<Args>(args)...);
    } else {
      value_type tmp(std::forward<Args>(args)...);
      _shift_backward(p, _end_ptr(), p + 1);
      *p = std::move(tmp);
    }
    return p;
  }

  auto insert(const_iterator position, size_type len, const_reference value) -> iterator
  {
    pointer p = _begin_ptr() + (position - cbegin());
    if (len > 0) {
      size_type pre_size = len;
      pointer pre_last = _end_ptr();
      if (len > _end_ptr() - p) {
        len = _end_ptr() - p;
        _construct_back(pre_size - len, value);
      }
      if (len > 0) {
        value_type tmp(value);
        _shift_backward(p, pre_last, p + pre_size);
        std::fill_n(p, len, tmp);
      }
    }
    return p;
  }

  template <typename ForwardIterator>
  auto insert(const_iterator position, ForwardIterator first, ForwardIterator last)
    -> std::enable_if_t<internal::is_forward_iterator_v<ForwardIterator>, iterator>
  {
    pointer p = _begin_ptr() + (position - cbegin());
    difference_type len = std::distance(first, last);
    if (len > 0) {
      size_type pre_len = static_cast<size_type>(len);
      pointer pre_last = _end_ptr();
      ForwardIterator middle = last;
      if (len > _end_ptr() - p) {
        middle = first;
        len = _end_ptr() - p;
        std::advance(middle, len);
        _construct_back(middle, pre_len - len);
      }
      if (len > 0) {
        _shift_backward(p, pre_last, p + pre_len);
        std::copy(first, middle, p);
      }
    }
    return p;
  }

  auto insert(const_iterator position, std::initializer_list<value_type> list) -> iterator
  { return insert(position, list.begin(), list.end()); }

  auto erase(const_iterator position) -> iterator
  {
    pointer p = _begin_ptr() + (position - cbegin());
    _destruct_back(std::move(p + 1, _end_ptr(), p));
    return p;
  }

  auto erase(const_iterator first, const_iterator last) -> iterator
  {
    pointer p = _begin_ptr() + (first - cbegin());
    if (first != last) {
      _destruct_back(std::move(last, _end_ptr(), first));
    }
    return p;
  }

  auto swap(StaticVector &that) -> void
  {
    if (size() <= that.size()) {
      iterator middle = that.begin() + size();
      size_type len = static_cast<size_type>(end() - middle);
      std::swap_ranges(begin(), end(), that.begin());
      _construct_back(std::move_iterator(middle), len);
      that._destruct_back(middle);
    } else {
      that.swap(*this);
    }
  }

  auto clear() -> void
  { _destruct_back(_begin_ptr()); }

private:
  [[nodiscard]]
  auto _begin_ptr() noexcept -> pointer
  { return _storage; }

  [[nodiscard]]
  auto _begin_ptr() const noexcept -> const_pointer
  { return _storage; }

  [[nodiscard]]
  auto _end_ptr() noexcept -> pointer
  { return _begin_ptr() + size(); }

  [[nodiscard]]
  auto _end_ptr() const noexcept -> const_pointer
  { return _begin_ptr() + size(); }

  auto _check_index(size_type index) -> void
  {
    if (index >= size()) {
      throw std::out_of_range("StaticVector: index is out of range");
    }
  }

  template <typename ...Args>
  auto _construct_one_back(Args &&...args) -> void
  {
    if (size() < capacity()) {
      new (_end_ptr()) T(std::forward<Args>(args)...);
      ++_size;
    }
  }

  auto _construct_back(size_type len) -> void
  {
    len = std::min(len, capacity() - size());
    std::uninitialized_value_construct_n(_end_ptr(), len);
    _size += len;
  }

  auto _construct_back(size_type len, const_reference value) -> void
  {
    len = std::min(len, capacity() - size());
    std::uninitialized_fill_n(_end_ptr(), len, value);
    _size += len;
  }

  template <typename ForwardIterator>
  auto _construct_back(ForwardIterator first, size_type len)
    -> std::enable_if_t<internal::is_forward_iterator_v<ForwardIterator>, void>
  {
    len = std::min(len, capacity() - size());
    std::uninitialized_copy_n(first, len, _end_ptr());
    _size += len;
  }

  auto _destruct_one_back() -> void
  {
    --_size;
    std::destroy_at(_end_ptr());
  }

  auto _destruct_back(pointer first) -> void
  {
    std::destroy(first, _end_ptr());
    _size -= static_cast<size_type>(_end_ptr() - first);
  }

  auto _shift_backward(pointer first, pointer last, pointer result) -> void
  {
    size_type shift_len = static_cast<size_type>(last - first);
    size_type init_len = static_cast<size_type>(_end_ptr() - result);
    pointer pre_last = _end_ptr();
    if (shift_len > init_len) {
      size_type uninit_len = std::min(shift_len - init_len, capacity() - size());
      std::uninitialized_move_n(first + init_len, uninit_len, _end_ptr());
      _size += uninit_len;
    }
    std::move_backward(first, first + init_len, pre_last);
  }

  union { value_type _storage[Capacity]; };
  size_type _size = 0;
};

template <typename T, size_t Capacity, size_t OtherCapacity>
auto operator==(const StaticVector<T, Capacity> &x, const StaticVector<T, OtherCapacity> &y) -> bool
{ return std::equal(x.begin(), x.end(), y.begin(), y.end()); }

template <typename T, size_t Capacity, size_t OtherCapacity>
auto operator!=(const StaticVector<T, Capacity> &x, const StaticVector<T, OtherCapacity> &y) -> bool
{ return !(x == y); }

template <typename T, size_t Capacity, size_t OtherCapacity>
auto operator<(const StaticVector<T, Capacity> &x, const StaticVector<T, OtherCapacity> &y) -> bool
{ return std::lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); }

template <typename T, size_t Capacity, size_t OtherCapacity>
auto operator>(const StaticVector<T, Capacity> &x, const StaticVector<T, OtherCapacity> &y) -> bool
{ return y < x; }

template <typename T, size_t Capacity, size_t OtherCapacity>
auto operator<=(const StaticVector<T, Capacity> &x, const StaticVector<T, OtherCapacity> &y) -> bool
{ return !(y > x); }

template <typename T, size_t Capacity, size_t OtherCapacity>
auto operator>=(const StaticVector<T, Capacity> &x, const StaticVector<T, OtherCapacity> &y) -> bool
{ return !(y < x); }
} // namespace shouth