#ifndef CONTAINERS_H_
#define CONTAINERS_H_

#include <utility>
#include <vector>
#include <cassert>

namespace containers {

// --------------------------------------------------------------------------

template <typename T>
class BiDirectionalList {
 public:
  struct Node{
    T value;
   private:
    Node* pvl = nullptr;
    Node* nvl = nullptr;

    Node(Node*, const T&, bool);
    explicit Node(const T* val) : value(val) {}
    Node(const Node&);
    explicit Node(T val) : value(val) {}
    friend class BiDirectionalList;
  };

  BiDirectionalList() = default;
  BiDirectionalList(const std::initializer_list<T>&);

  int Size() const;
  bool IsEmpty() const;

  void PushFront(const T& value);
  void PushBack(const T& value);

  Node* Front();
  Node* Back();

  const Node* Front() const;
  const Node* Back() const;

  void PopFront();
  void PopBack();

  std::vector<T> ToVector() const;

  int Find(const T& value) const;
  std::vector<int> FindAll(const T& value) const;

  Node* operator[](int);
  const Node* operator[](int) const;

  void InsertBefore(Node* element, const T& value);
  void InsertAfter(Node* element, const T& value);

  void Erase(Node* element);

  bool operator==(const BiDirectionalList<T>&) const;
  bool operator!=(const BiDirectionalList<T>&) const;

  BiDirectionalList(const BiDirectionalList<T>&);
  BiDirectionalList& operator=(const BiDirectionalList<T>&);

  BiDirectionalList(BiDirectionalList<T>&&);
  BiDirectionalList& operator=(BiDirectionalList<T>&&);

  ~BiDirectionalList();

 protected:
  int size_ = 0;
  Node* first_ = nullptr;
  Node* last_ = nullptr;
};
template<typename T>
BiDirectionalList<T>::Node::Node(
    BiDirectionalList<T>::Node* el,
    const T& val,
    bool flag) : value(val) {
  if (flag) {
    nvl = el->nvl;
    pvl = el;
    if (el->nvl != nullptr)
      el->nvl->pvl = this;  //  -Требует дорабодки, как и многое другое
    el->nvl = this;
  } else {
    nvl = el;
    pvl = el->pvl;
    if (el->pvl != nullptr)
      el->pvl->nvl = this;
    el->pvl = this;
  }
}

template<typename T>
BiDirectionalList<T>::Node::Node(
    const BiDirectionalList<T>::Node& n) : value(n.value),
    nvl(n.nvl), pvl(n.pvl) {
}

template<typename T>
BiDirectionalList<T>::BiDirectionalList(const std::initializer_list<T>& list) {
  if (list.size() == 0) {
    first_ = nullptr;
    last_ = nullptr;
    size_ = 0;
    return;
  }
  first_ = new Node(*list.begin());
  size_ = list.size();
  Node* prev = first_;
  auto beg = list.begin();
  beg++;
  for (auto i = beg; i != list.end(); i++) {
    prev = new Node(prev, *i, true);
  }
  last_ = prev;
}

template<typename T>
BiDirectionalList<T>::~BiDirectionalList() {
  Node* next = last_;
  first_ = nullptr;
  last_ = nullptr;
  while (next != nullptr) {
    Node* now = next;
    next = next->pvl;
    now->pvl = nullptr;
    now->nvl = nullptr;
    delete now;
  }
}

template<typename T>
int BiDirectionalList<T>::Size() const {
  return size_;
}

template<typename T>
bool BiDirectionalList<T>::IsEmpty() const {
  return size_ == 0;
}

template<typename T>
void BiDirectionalList<T>::PushFront(const T& value) {
  size_++;
  if (size_ == 1) {
    first_ = new Node(value);
    last_ = first_;
    return;
  }
  first_ = new Node(first_, value, false);
}

template<typename T>
void BiDirectionalList<T>::PushBack(const T& value) {
  size_++;
  if (size_ == 1) {
    first_ = new Node(value);
    last_ = first_;
    return;
  }
  last_ = new Node(last_, value, true);
}
template<typename T>
typename BiDirectionalList<T>::Node*
BiDirectionalList<T>::Front() {
  return first_;
}
template<typename T>
typename BiDirectionalList<T>::Node*
BiDirectionalList<T>::Back() {
  return last_;
}
template<typename T>
void BiDirectionalList<T>::PopFront() {
  if (size_ > 1) {
    Node* buf = first_;
    first_ = buf->nvl;
    first_->pvl = nullptr;
    delete buf;
    size_ -= 1;
    return;
  }
  if (size_ == 1) {
    Node* buf = first_;
    delete buf;
    first_ = nullptr;
    last_ = nullptr;
    size_ = 0;
  }
}

template<typename T>
void BiDirectionalList<T>::PopBack() {
  if (size_ > 1) {
    Node* buf = last_;
    last_ = buf->pvl;
    last_->nvl = nullptr;
    delete buf;
    size_ -= 1;
    return;
  }
  if (size_ == 1) {
    Node* buf = first_;
    delete buf;
    first_ = nullptr;
    last_ = nullptr;
    size_ = 0;
  }
}

template<typename T>
std::vector<T> BiDirectionalList<T>::ToVector() const {
  std::vector<T> ans;
  Node* el = first_;
  while (el != nullptr) {
    ans.push_back(el->value);
    el = el->nvl;
  }
  return ans;
}

template<typename T>
int BiDirectionalList<T>::Find(const T& value) const {
  int ans = 0;
  Node* el = first_;
  while (el != nullptr) {
    if (el->value == value) {
      return ans;
    }
    el = el->nvl;
    ans += 1;
  }
  return -1;
}

template<typename T>
std::vector<int> BiDirectionalList<T>::FindAll(
    const T& value) const {
  std::vector<int> ans;
  int i = 0;
  Node* el = first_;
  while (el != nullptr) {
    if (el->value == value) {
      ans.push_back(i);
    }
    i++;
    el = el->nvl;
  }
  return ans;
}
template<typename T>
typename BiDirectionalList<T>::Node*
BiDirectionalList<T>::operator[](int x) {
  Node* ans = first_;
  if (x > size_) {
    return nullptr;
  }
  if (x == 0) {
    return first_;
  }
  for (int i = 0; i < x; i++) {
    ans = ans->nvl;
  }
  return ans;
}
template<typename T>
void BiDirectionalList<T>::InsertBefore(
    BiDirectionalList<T>::Node* element,
    const T& value) {
  size_++;
  if (element == first_) {
    PushFront(value);
    return;
  }
  new Node(element, value, false);
}
template<typename T>
void BiDirectionalList<T>::InsertAfter(
    BiDirectionalList<T>::Node* element,
    const T& value) {
  size_++;
  if (element == last_) {
    PushBack(value);
    return;
  }
  new Node(element, value, true);
}
template<typename T>
void BiDirectionalList<T>::Erase(
    BiDirectionalList<T>::Node* element) {
  if (element == first_) {
    PopFront();
    return;
  }
  if (element == last_) {
    PopBack();
    return;
  }
  element->nvl->pvl = element->pvl;
  element->pvl->nvl = element->nvl;
  size_--;
  delete element;
}
template<typename T>
const typename BiDirectionalList<T>::Node*
BiDirectionalList<T>::operator[](int x) const {
  Node* ans = first_;
  if (x > size_) {
    return nullptr;
  }
  for (int i = 0; i < x; i++) {
    ans = ans->nvl;
  }
  const Node* answer(ans);
  return answer;
}
template<typename T>
const typename BiDirectionalList<T>::Node*
BiDirectionalList<T>::Front() const {
  const Node* ans(first_);
  return ans;
}

template<typename T>
const typename BiDirectionalList<T>::Node*
BiDirectionalList<T>::Back() const {
  const Node* ans(last_);
  return ans;
}
template<typename T>
bool BiDirectionalList<T>::operator==(
    const BiDirectionalList<T>& list) const {
  if (size_ != list.size_) {
    return false;
  }
  Node* el1 = first_;
  Node* el2 = list.first_;
  while (el1 != nullptr) {
    if (el1->value != el2->value) {
      return false;
    }
    el1 = el1->nvl;
    el2 = el2->nvl;
  }
  return true;
}
template<typename T>
bool BiDirectionalList<T>::operator!=(
    const BiDirectionalList<T>& list) const {
  return !(*this == list);
}
template<typename T>
BiDirectionalList<T>::BiDirectionalList(
    const BiDirectionalList<T>& list) : size_(list.size_) {
  if (list.size_ == 0) {
    first_ = nullptr;
    last_ = nullptr;
    return;
  }
  Node* elem = list.first_;
  first_ = new Node(*list.first_);
  Node* coper = first_;
  while (elem != nullptr) {
    coper = new Node(coper, *elem, true);
    elem = elem->nvl;
  }
  last_ = coper;
}
template<typename T>
BiDirectionalList<T>& BiDirectionalList<T>::operator=(
    const BiDirectionalList<T>& list) {
  if (this == &list) {
    return *this;
  }
  // Удалям то, что было раньше
  Node* next = first_;
  Node* now = nullptr;
  while (next != nullptr) {
    now = next;
    next = now->nvl;
    delete now;
  }
  // Пишем в массив новые значения
  size_ = list.size_;
  if (size_ == 0) {
    first_ = nullptr;
    last_ = nullptr;
  }
  Node* elem = list.first_;
  first_ = new Node(*list.first_);
  Node* coper = first_;
  while (elem != nullptr) {
    coper = new Node(coper, *elem, true);
    elem = elem->nvl;
  }
  last_ = coper;
  return *this;
}
template<typename T>
BiDirectionalList<T>::BiDirectionalList(
    BiDirectionalList<T>&& list) : size_(list.size_),
                                   first_(list.first_),
                                   last_(list.last_) {
  list.last_ = nullptr;
  list.first_ = nullptr;
}
template<typename T>
BiDirectionalList<T>& BiDirectionalList<T>::operator=(
    BiDirectionalList<T>&& list) {
  if (this = &list) {
    return *this;
  }
  // Удалям то, что было раньше
  Node* next = first_;
  Node* now = nullptr;
  while (next != nullptr) {
    now = next;
    next = now->nvl;
    delete now;
  }
  // Копируем все в массив
  size_ = list.size_;
  first_ = list.size_;
  last_ - list.size_;
  list.last_ = nullptr;
  list.first_ = nullptr;

  return *this;
}
// --------------------------------------------------------------------------

// Тут следует расположить код решения задачи 2 (Queue / Stack).
template <typename T>
class Queue {
 public:
    Queue() = default;
    Queue(const std::initializer_list<T>&);
    void Push(const T&);
    void Pop();
    T& Get();
    int Size();
    bool IsEmpty();
    bool operator==(const Queue<T>&);
    bool operator!=(const Queue<T>&);
 private:
    BiDirectionalList<T> mas;
};
template<typename T>
void Queue<T>::Push(const T& x) {
  mas.PushBack(x);
}
template<typename T>
void Queue<T>::Pop() {
  mas.PopFront();
}
template<typename T>
T& Queue<T>::Get() {
  return mas.Front()->value;
}
template<typename T>
int Queue<T>::Size() {
  return mas.Size();
}
template<typename T>
bool Queue<T>::IsEmpty() {
  return mas.IsEmpty();
}
template<typename T>
bool Queue<T>::operator==(const Queue<T>& obj) {
  return mas == obj.mas;
}
template<typename T>
bool Queue<T>::operator!=(const Queue<T>& obj) {
  return mas != obj.mas;
}
template<typename T>
Queue<T>::Queue(const std::initializer_list<T>& list) : mas(list) {
}

// --------------------------------------------------------------------------

// Раскоментируйте нужные строки ниже для выбора варианта

enum class Variant {
  kQueue,
  kStack,
};

Variant GetVariant() {
  return Variant::kQueue;
  // return Variant::kStack;
}

template<typename T>
using Container = Queue<T>;

// template<typename T>
// using Container = Stack<T>;

// --------------------------------------------------------------------------

}  // namespace containers

#endif  // CONTAINERS_H_