#ifndef FLOATING_ARRAY_H_INCLUDED_
#define FLOATING_ARRAY_H_INCLUDED_

struct origin_tag {
  std::ptrdiff_t value = 0;
  explicit operator ptrdiff_t() const { return value; }
};

template <typename I>
using is_input_iterator =
    std::is_convertible<std::input_iterator_tag,
                        typename std::iterator_traits<I>::iterator_category>;
template <typename I>
constexpr bool is_input_iterator_v = is_input_iterator<I>::value;

template <typename T, typename Allocator = std::allocator<T>>
class floating_array : private std::deque<T, Allocator> {
 private:
  using BC = std::deque<T, Allocator>;

 public:
  /* Boilerplate stuff */
  using value_type = typename BC::value_type;
  using allocator_type = typename BC::allocator_type;
  using size_type = typename BC::size_type;
  using index_type = std::ptrdiff_t;
  using difference_type = typename BC::difference_type;
  using reference = typename BC::reference;
  using const_reference = typename BC::const_reference;
  using pointer = typename BC::pointer;
  using const_pointer = typename BC::const_pointer;
  using iterator = typename BC::iterator;
  using const_iterator = typename BC::const_iterator;
  using reverse_iterator = typename BC::reverse_iterator;
  using const_reverse_iterator = typename BC::const_reverse_iterator;

  floating_array() = default;
  explicit floating_array(const Allocator& alloc) : BC(alloc) {}
  floating_array(size_type count, const T& value = T(),
                 const Allocator& alloc = Allocator())
      : BC(count, value, alloc) {}
  explicit floating_array(size_type count, const Allocator& alloc = Allocator())
      : BC(count, alloc) {}
  template <typename InputIt,
            typename = std::enable_if_t<is_input_iterator_v<InputIt>>>
  floating_array(InputIt first, InputIt last,
                 const Allocator& alloc = Allocator())
      : BC(first, last, alloc) {}
  floating_array(const floating_array& other) = default;
  floating_array(const floating_array& other, const Allocator& alloc)
      : BC(static_cast<const BC&>(other), alloc), offset(other.offset) {}
  floating_array(floating_array&& other) = default;
  floating_array(floating_array&& other, const Allocator& alloc)
      : BC(static_cast<BC&&>(other), alloc), offset(other.offset) {}
  floating_array(std::initializer_list<T> init,
                 const Allocator& alloc = Allocator())
      : BC(init, alloc) {}

  explicit floating_array(origin_tag o, const Allocator& alloc = Allocator())
      : BC(alloc), offset(o) {}
  floating_array(origin_tag o, size_type count, const T& value = T(),
                 const Allocator& alloc = Allocator())
      : BC(count, value, alloc), offset(o) {}
  template <typename InputIt,
            typename = std::enable_if_t<is_input_iterator_v<InputIt>>>
  floating_array(origin_tag o, InputIt first, InputIt last,
                 const Allocator& alloc = Allocator())
      : BC(first, last, alloc), offset(o) {}
  floating_array(origin_tag o, std::initializer_list<T> init,
                 const Allocator& alloc = Allocator())
      : BC(init, alloc), offset(o) {}

  floating_array& operator=(const floating_array& other) = default;
  floating_array& operator=(floating_array&& other) noexcept(
      std::allocator_traits<Allocator>::is_always_equal::value) = default;
  floating_array& operator=(std::initializer_list<T> ilist) {
    BC::operator=(ilist);
    offset = 0;
    return *this;
  }

  void assign(size_type count, const T& value) {
    BC::assign(count, value);
    offset = 0;
  }
  template <typename InputIt,
            typename = std::enable_if_t<is_input_iterator_v<InputIt>>>
  void assign(InputIt first, InputIt last) {
    BC::assign(first, last);
    offset = 0;
  }
  void assign(std::initializer_list<T> ilist) {
    BC::assign(ilist);
    offset = 0;
    return *this;
  }

  void assign(origin_tag o, size_type count, const T& value) {
    BC::assign(count, value);
    offset = o.value;
  }
  template <typename InputIt,
            typename = std::enable_if_t<is_input_iterator_v<InputIt>>>
  void assign(origin_tag o, InputIt first, InputIt last) {
    BC::assign(first, last);
    offset = o.value;
  }
  void assign(origin_tag o, std::initializer_list<T> ilist) {
    BC::assign(ilist);
    offset = o.value;
    return *this;
  }

  using BC::get_allocator;

  reference at(index_type i) { return BC::at(i - offset); }
  const_reference at(index_type i) const { return BC::at(i - offset); }
  reference operator[](index_type i) { return BC::operator[](i - offset); }
  const_reference operator[](index_type i) const {
    return BC::operator[](i - offset);
  }

  using BC::back;
  using BC::front;

  using BC::begin;
  using BC::cbegin;
  using BC::cend;
  using BC::crbegin;
  using BC::crend;
  using BC::end;
  using BC::rbegin;
  using BC::rend;

  // If the range spans zero, returns an iterator to [0].
  // Otherwise, returns end()
  iterator zero() {
    if (low() < 0 && high() > 0) {
      return begin() - low();
    }
    return end();
  }
  const_iterator zero() const {
    if (low() < 0 && high() > 0) {
      return begin() - low();
    }
    return end();
  }

  const_iterator czero() const { return zero(); }
  reverse_iterator rzero() { return reverse_iterator(zero()); }
  const_reverse_iterator rzero() const {
    return const_reverse_iterator(zero());
  }
  const_reverse_iterator crzero() const { return rzero(); }

  using BC::empty;
  using BC::max_size;
  using BC::shrink_to_fit;
  using BC::size;

  index_type high() const { return size() + offset; }
  index_type low() const { return offset; }

  void clear() noexcept {
    BC::clear();
    offset = 0;
  }

  // no insert, emplace, or erase

  using BC::emplace_back;
  using BC::pop_back;
  using BC::push_back;

  void push_front(const T& value) {
    BC::push_front(value);
    --offset;
  }
  void push_front(T&& value) {
    BC::push_front(value);
    --offset;
  }

  template <typename... Args>
  reference emplace_front(Args&&... args) {
    BC::emplace_front(std::forward<Args>(args)...);
    --offset;
  }

  void pop_front() {
    BC::pop_front();
    ++offset;
  }

  void swap(floating_array& other) noexcept(
      std::allocator_traits<Allocator>::is_always_equal::value) {
    using std::swap;
    swap(static_cast<BC&>(*this), static_cast<BC&>(other));
    swap(offset, other.offset);
  }

  friend bool operator==(const floating_array&, const floating_array&);

 private:
  difference_type offset{0};
};

template <typename T, typename Alloc>
bool operator==(const floating_array<T, Alloc>& lhs,
                const floating_array<T, Alloc>& rhs) {
  return (lhs.low() == rhs.low()) && (static_cast<std::deque<T, Alloc>&>(lhs) ==
                                      static_cast<std::deque<T, Alloc>&>(rhs));
}

template <typename T, typename Alloc>
bool operator!=(const floating_array<T, Alloc>& lhs,
                const floating_array<T, Alloc>& rhs) {
  return !(lhs == rhs);
}

template <typename T, typename Alloc>
bool operator<(const floating_array<T, Alloc>& lhs,
               const floating_array<T, Alloc>& rhs) {
  return std::lexicographical_compare(lhs.begin(), lhs.end(), rhs.begin(),
                                      rhs.end());
}

template <typename T, typename Alloc>
bool operator<=(const floating_array<T, Alloc>& lhs,
                const floating_array<T, Alloc>& rhs) {
  return (lhs == rhs) || std::lexicographical_compare(lhs.begin(), lhs.end(),
                                                      rhs.begin(), rhs.end());
}

template <typename T, typename Alloc>
bool operator>(const floating_array<T, Alloc>& lhs,
               const floating_array<T, Alloc>& rhs) {
  return std::lexicographical_compare(rhs.begin(), rhs.end(), lhs.begin(),
                                      lhs.end());
}

template <typename T, typename Alloc>
bool operator>=(const floating_array<T, Alloc>& lhs,
                const floating_array<T, Alloc>& rhs) {
  return (lhs == rhs) || std::lexicographical_compare(rhs.begin(), rhs.end(),
                                                      lhs.begin(), lhs.end());
}

template <typename T, typename Alloc>
void swap(floating_array<T, Alloc>& lhs, floating_array<T, Alloc>& rhs) {
  lhs.swap(rhs);
}

#endif //FLOATING_ARRAY_H_INCLUDED_