#include <algorithm>
#include <cstdio>
#include <iostream>
#include <iterator>
#include <memory>
#include <stdexcept>
#include <type_traits>

namespace phundrak {
using size_type = std::size_t;
using difference_type = std::ptrdiff_t;

template <class T, class Allocator = std::allocator<T>> class vector {

public:
  class iterator;
  class const_iterator;
  class reverse_iterator;
  class const_reverse_iterator;

private:
  void double_capacity() {
    if (data_) {
      T *olddata = data_;
      capacity_ <<= 1;
      data_ = new T[capacity_];
      for (size_t i = 0; i < size_; ++i)
        data_[i] = olddata[i];
      delete[] olddata;
    } else {
      data_ = new T[1];
      capacity_ = 1;
    }
  }

  T *data_ = nullptr;
  size_t size_ = 0;
  size_t capacity_ = 0;
  Allocator alloc_ = Allocator{};

public:
  ///////////////////////////////////////////////////////////////////////////
  //                            Member functions                           //
  ///////////////////////////////////////////////////////////////////////////

  // constructor ////////////////////////////////////////////////////////////

  vector() noexcept(noexcept(Allocator())) {}

  explicit vector(const Allocator &alloc) noexcept : alloc_{alloc} {}

  vector(size_type count, const T &value, const Allocator &alloc = Allocator())
      : vector{alloc} {
    for (size_t i = 0; i < count; ++i)
      push_back(value);
  }

  explicit vector(size_type count, const Allocator &alloc = Allocator())
      : alloc_{alloc} {
    for (size_type i = 0; i < count; ++i)
      push_back(T{});
  }

  template <class InputIt>
  vector(InputIt first, InputIt last, const Allocator &alloc = Allocator())
      : alloc_{alloc} {
    for (; first != last; ++first)
      push_back(*first);
  }

  // Copy constructor ///////////////////////////////////////////////////////

  vector(const vector<T> &other)
      : data_{new T[other.size_]}, size_{other.size_},
        capacity_{other.capacity_}, alloc_{other.alloc_} {
    if (!alloc_) {
      alloc_ = std::allocator_traits<Allocator>::
          select_on_container_copy_construction(other.get_allocator());
    }
    for (size_type i = 0; i < size_; ++i)
      data_[i] = other.data_[i];
  }

  vector(const vector &other, const Allocator &alloc)
      : data_{new T[other.size_]}, size_{other.size},
        capacity_{other.capacity_}, alloc_{alloc} {
    try {
      if (alloc_ != other.alloc_)
        throw 20;
    } catch (int error) {
      std::cout << "Error in phundrak::vector(const vector &other, const "
                   "Allocator &alloc) :\nThe allocator "
                << alloc
                << " passed as argument is different from other’s allocator "
                << other.alloc_ << "\nAborting...\n";
      std::terminate();
    }

    for (size_type i = 0; i < size_; ++i)
      data_[i] = other.data_[i];
  }

  // Move constructor ///////////////////////////////////////////////////////

  vector(vector<T> &&other) noexcept {
    std::swap(data_, other.data_);
    std::swap(size_, other.size_);
    std::swap(capacity_, other.capacity_);
    std::swap(alloc_, other.alloc_);
  }

  vector(vector &&other, const Allocator &alloc) {
    if (alloc != other.alloc_) {
      std::swap(capacity_, other.capacity_);
      std::swap(size_, other.size_);
      data_ = new T[capacity_];
      alloc_ = alloc;
      for (size_type i = 0; i < size_; ++i)
        data_[i] = std::move(other.data_[i]);
    } else {
      std::swap(capacity_, other.capacity);
      std::swap(size_, other.size);
      std::swap(data_, other.data_);
      std::swap(alloc_, other.alloc_);
    }
  }

  // Constructor by initializer list //////////////////////////////////////////
  vector(std::initializer_list<T> init, const Allocator &alloc = Allocator())
      : vector{alloc} {
    for (auto &elem : init)
      push_back(std::move(elem));
  }

  // Destructor ///////////////////////////////////////////////////////////////

  virtual ~vector() noexcept {
    if (data_)
      delete[] data_;
  }

  // Copy assignment operator /////////////////////////////////////////////////

  vector &operator=(const vector &other) {
    delete[] data_;
    size_ = other.size_;
    capacity_ = other.capacity_;
    data_ = new T[capacity_];
    for (size_type i = 0; i < size_; ++i)
      data_[i] = other.data_[i];
    return *this;
  }

  vector &operator=(vector &&other) noexcept {
    std::swap(alloc_, other.alloc_);
    std::swap(size_, other.size_);
    std::swap(capacity_, other.capacity_);
    std::swap(data_, other.data_);
    return *this;
  }

  vector &operator=(std::initializer_list<T> ilist) {
    delete[] data_;
    size_ = ilist.size();
    capacity_ = size_;
    data_ = new T[capacity_];
    size_type i = 0;
    std::for_each(std::begin(ilist), std::end(ilist), [&i, this](T &elem) {
      data_[i] = std::move(elem);
      ++i;
    });

    return *this;
  }

  // assign ///////////////////////////////////////////////////////////////////

  void assign(size_t count, const T &value) {
    clear();
    reserve(count);
    for (size_t i = 0; i < count; ++i)
      push_back(value);
  }

  template <typename InputIt,
            typename std::enable_if_t<!std::is_integral<InputIt>::value,
                                      InputIt> * = nullptr>
  void assign(InputIt first, InputIt last) {
    clear();
    capacity_ = std::distance(first, last);
    size_ = capacity_;
    data_ = new T[capacity_];
    for (int i = 0; first != last, i < size_; ++first, ++i)
      data_[i] = *first;
  }

  void assign(std::initializer_list<T> ilist) {
    delete[] data_;
    size_ = ilist.size();
    capacity_ = ilist.size();
    data_ = new T[size_];
    size_type i = 0;
    for (auto pos = ilist.begin(); pos != ilist.end(); ++pos, ++i)
      data_[i] = std::move(*pos);
  }

  // get_allocator ////////////////////////////////////////////////////////////

  Allocator get_allocator() const { return alloc_; }

  /////////////////////////////////////////////////////////////////////////////
  //                              Element access                             //
  /////////////////////////////////////////////////////////////////////////////

  // at ///////////////////////////////////////////////////////////////////////

  T &at(size_t pos) {
    try {
      if (pos >= size_)
        throw std::out_of_range("Out of range");
    } catch (const std::out_of_range &e) {
      std::cout << e.what() << " in phundrak::vector " << this << '\n';
      std::terminate();
    }
    return data_[pos];
  }

  const T &at(size_t pos) const {
    try {
      if (pos >= size_ || pos < 0)
        throw std::out_of_range("Out of range");
    } catch (const std::out_of_range &e) {
      std::cout << e.what() << " in phundrak::vector " << this << '\n';
      std::terminate();
    }

    return data_[pos];
  }

  // operator[] ///////////////////////////////////////////////////////////////

  T &operator[](size_type pos) { return data_[pos]; }
  const T &operator[](size_type pos) const { return data_[pos]; }

  // front ////////////////////////////////////////////////////////////////////

  T &front() { return data_[0]; }
  const T &front() const { return data_[0]; }

  // back /////////////////////////////////////////////////////////////////////

  T &back() { return data_[size_ - 1]; }
  const T &back() const { return data_[size_ - 1]; }

  // data /////////////////////////////////////////////////////////////////////

  T *data() noexcept { return data_; }
  const T *data() const noexcept { return data_; }

  /////////////////////////////////////////////////////////////////////////////
  //                                Iterators                                //
  /////////////////////////////////////////////////////////////////////////////

  // begin ////////////////////////////////////////////////////////////////////

  iterator begin() noexcept { return iterator{data_}; }
  const_iterator begin() const noexcept { return const_iterator{data_}; }

  const_iterator cbegin() const noexcept { return const_iterator{data_}; }

  // end //////////////////////////////////////////////////////////////////////

  iterator end() noexcept { return iterator{&data_[size_]}; }
  const_iterator end() const noexcept { return const_iterator{&data_[size_]}; }

  const_iterator cend() const noexcept { return const_iterator{&data_[size_]}; }

  // rbegin ///////////////////////////////////////////////////////////////////

  reverse_iterator rbegin() noexcept {
    return reverse_iterator{&data_[size_ - 1]};
  }
  const_reverse_iterator rbegin() const noexcept {
    return const_reverse_iterator{data_[size_ - 1]};
  }

  const_reverse_iterator crbegin() const noexcept {
    return const_reverse_iterator{&data_[size_ - 1]};
  }

  // rend /////////////////////////////////////////////////////////////////////

  reverse_iterator rend() noexcept {
    reverse_iterator ret{data_};
    ++ret;
    return ret;
  }
  const_reverse_iterator rend() const noexcept {
    const_reverse_iterator ret{data_};
    ++ret;
    return ret;
  }

  const_reverse_iterator crend() const noexcept {
    const_reverse_iterator ret{data_};
    ++ret;
    return ret;
  }

  /////////////////////////////////////////////////////////////////////////////
  //                                 Capacity                                //
  /////////////////////////////////////////////////////////////////////////////

  bool empty() const noexcept { return (size_ == 0) ? true : false; }

  size_t size() const noexcept { return size_; }

  void reserve(size_t new_cap) {
    while (capacity_ < new_cap)
      double_capacity();
  }

  size_t capacity() const noexcept { return capacity_; }

  void shrink_to_fit() {
    T *olddata = data_;
    capacity_ = size_;
    data_ = new T[capacity_];
    for (size_t i = 0; i < size_; ++i)
      data_[i] = olddata[i];
    delete[] olddata;
  }

  /////////////////////////////////////////////////////////////////////////////
  //                                Modifiers                                //
  /////////////////////////////////////////////////////////////////////////////

  // clear ////////////////////////////////////////////////////////////////////

  void clear() noexcept {
    delete[] data_;
    data_ = new T[capacity_];
    size_ = 0;
  }

  // insert ///////////////////////////////////////////////////////////////////

  iterator insert(const_iterator pos, const T &value) {
    if (size_ == capacity_)
      double_capacity();
    ++size_;
    T prev = value;
    auto end = cend();
    for (; pos != end; ++pos) {
      T temp = *pos;
      *pos = prev;
      prev = temp;
    }
    return pos;
  }

  iterator insert(const_iterator pos, T &&value) {
    if (size_ == capacity_)
      double_capacity();
    ++size_;
    T prev = std::move(value);
    iterator ret = pos;
    auto end = cend();
    for (; pos != end; ++pos) {
      T temp = std::move(*pos);
      *pos = std::move(prev);
      prev = std::move(temp);
    }
    return ++ret;
  }

  iterator insert(const_iterator pos, size_type count, const T &value) {
    for (size_type i = 0; i < count; ++i, ++pos) {
      insert(pos, value);
    }
  }

  template <typename InputIT,
            typename std::enable_if_t<!std::is_integral<InputIT>::value,
                                      InputIT> * = nullptr>
  iterator insert(const_iterator pos, InputIT first, InputIT last) {
    for (; first != last; ++first) {
      insert(pos, *first);
    }
  }

  iterator insert(const_iterator pos, std::initializer_list<T> ilist) {
    for (const T elem : ilist) {
      insert(pos, elem);
      ++pos;
    }
  }

  // emplace //////////////////////////////////////////////////////////////////

  template <class... Args>
  iterator emplace(const_iterator pos, Args &&... args) {
    if (size_ == capacity_)
      double_capacity();
    auto ptr1 = rbegin();
    ++ptr1;
    auto ptr2 = rbegin();
    printf("ptr1 : %d\nptr2: %d\n", *ptr1, *ptr2);
    for (; ptr2 != pos; ++ptr2, ++ptr1)
      std::swap(*ptr2, *ptr1);
    std::swap(*ptr2, *ptr1);
    *ptr1 = T(std::forward<Args>(args)...);

    // *pos = T(std::forward<Args>(args)...);
    ++size_;
    return pos;
  }

  // erase ////////////////////////////////////////////////////////////////////

  iterator erase(const_iterator pos) {}

  iterator erase(const_iterator first, const_iterator last) {}

  // push_back ////////////////////////////////////////////////////////////////

  void push_back(const T &value) {
    ++size_;
    reserve(size_);
    data_[size_ - 1] = value;
  }

  void push_back(T &&value) {
    ++size_;
    reserve(size_);
    data_[size_ - 1] = std::move(value);
  }

  // emplace_back /////////////////////////////////////////////////////////////

  // pop_back /////////////////////////////////////////////////////////////////

  void pop_back() {
    if (size_ > 0)
      --size_;
  }

  // resize ///////////////////////////////////////////////////////////////////

  void resize(size_t count, T value = T()) {
    if (count < size_)
      size_ = count;
    else if (count > size_)
      reserve(count);
    while (size_ < count)
      push_back(value);
  }

  // swap /////////////////////////////////////////////////////////////////////

  void swap(vector<T> &other) {
    std::swap(capacity_, other.capacity_);
    std::swap(size_, other.size_);
    std::swap(data_, other.data_);
  }

  /////////////////////////////////////////////////////////////////////////////
  //                                                                         //
  //                                                                         //
  //                              ITERATOR CLASS                             //
  //                                                                         //
  //                                                                         //
  /////////////////////////////////////////////////////////////////////////////

  class iterator {

  protected:
    T *it;

  public:
    using iterator_category = std::forward_iterator_tag;

    iterator() : it{nullptr} {}
    explicit iterator(T *point) : it{point} {}

    iterator(const iterator &other) : it{other.it} {}
    explicit iterator(const_iterator &other) : it{other.it} {}

    iterator(iterator &&other) { std::swap(it, other.it); }

    iterator &operator=(T *point) {
      *it = *point;
      return *this;
    }
    iterator &operator=(const iterator &other) {
      *it = *other.it;
      return *this;
    }
    iterator &operator=(iterator &&other) {
      std::swap(*it, *other.it);
      return *this;
    }

    ~iterator() {
      // delete it;
    }

    iterator &operator++() { // ++i
      ++it;
      return *this;
    }
    iterator operator++(int) { // i++
      // iterator t;
      // t.it = it;
      iterator t{*this};
      ++it;
      return t;
    }

    iterator &operator+(int i) {
      for (; i > 0; --i)
        ++it;
      return *this;
    }

    iterator &operator--() { // --i
      --it;
      return *this;
    }

    iterator operator--(int) { // i--
      // iterator t;
      // t.it = it;
      iterator t{it};
      --it;
      return t;
    }

    iterator &operator-(int i) {
      for (; i > 0; --i)
        --it;
      return *this;
    }

    bool operator==(T *point) { return point == it; }
    bool operator==(const iterator &other) { return other.it == it; }
    bool operator==(iterator &&other) { return other.it == it; }

    bool operator!=(T *point) { return point != it; }
    bool operator!=(const iterator &other) { return other.it != it; }
    bool operator!=(iterator &&other) { return other.it != it; }

    T &operator*() { return *it; }

    friend class vector;
  };

  class const_iterator : public iterator {
  public:
    using iterator_category = std::forward_iterator_tag;

    const_iterator() : iterator() {}
    explicit const_iterator(T *point) : iterator{point} {}
    explicit const_iterator(const iterator &other) : iterator{other} {}
    const_iterator(const const_iterator &other) : iterator{other} {}
    explicit const_iterator(iterator &&other) : iterator{std::move(other)} {}
    const_iterator(const_iterator &&other) : iterator{std::move(other)} {}

    const T &operator*() const { return *this->it; }
  };

  class reverse_iterator : public iterator {
  public:
    reverse_iterator() : iterator() {}
    explicit reverse_iterator(T *point) : iterator(point) {}
    reverse_iterator(const reverse_iterator &other) : iterator(other) {}
    reverse_iterator(reverse_iterator &&other) : iterator(std::move(other)) {}

    reverse_iterator &operator++() {
      --this->it;
      return *this;
    }

    reverse_iterator operator++(int) {
      reverse_iterator t{*this};
      --this->it;
      return t;
    }

    reverse_iterator &operator--() {
      ++this->it;
      return *this;
    }

    reverse_iterator operator--(int) {
      reverse_iterator t{*this};
      ++this->it;
      return t;
    }

    ~reverse_iterator() {}
  };

  class const_reverse_iterator : public reverse_iterator {
  public:
    const_reverse_iterator() : reverse_iterator() {}
    explicit const_reverse_iterator(T *point) : reverse_iterator{point} {}
    explicit const_reverse_iterator(const reverse_iterator &other)
        : reverse_iterator{other} {}
    const_reverse_iterator(const const_reverse_iterator &other)
        : reverse_iterator{other} {}
    explicit const_reverse_iterator(reverse_iterator &&other)
        : reverse_iterator{other} {}
    const T &operator*() const { return *this->it; }
    virtual ~const_reverse_iterator() { this->~reverse_iterator(); }
  };

protected:
};

} // namespace phundrak