#include <iostream>

template<typename T>
class KDeque;

template<typename T>
class IsUniqueVisitor
{
public:
    void visit(KDeque<T>& deq)
    {
        std::set<T> st;
        for (auto it = deq.begin(); it != deq.end(); ++it) {
            st.insert(*it);
        }
        result = st.size() == deq.size();
    }

    void getResult()
    {
        if (result)
            std::cout << "Your deque has unique elements\n";
        else
            std::cout << "Your deque doesn't have unique elements\n";
        std::cout << std::endl;
    }
private:
    bool result;
};

template<typename T>
class KDeque
{
private:
    class Node
    {
    public:

        T value;
        Node *prev, *next;
        Node() : value(0), prev(NULL), next(NULL) {}
        Node(T& value) : value(value), prev(NULL), next(NULL) {}
    };
    Node *head, *tail;
    int _size;

public:
    class KIterator
    {
    public:
        KIterator(Node* other);
        KIterator operator++();
        T& operator*() const;
        bool operator!=(const KIterator& other);
        Node* node;
    };
    friend class KIterator;
    //typedef KIterator<T> iterator;
    KDeque();
    KDeque(std::initializer_list<T> args);
    KDeque(KDeque<T>&& other);
    KDeque(const KDeque<T>& other);
    ~KDeque();

    bool isEmpty() const;
    int size() const;
    void clear();
    T& front() const;
    T& back() const;
    void pushFront(T& element);
    void pushBack(T element);
    void popBack();
    void popFront();
    void swap(KDeque<T>& other);

    template<typename TT>
    friend std::ostream& operator<<(std::ostream& out, KDeque<TT>& other);
    bool operator==(const KDeque<T>& other) const;
    bool operator!=(const KDeque<T>& other) const;
    KDeque<T>& operator=(const KDeque<T>& other);
    KDeque<T>& operator=(KDeque<T>&& other);
    KDeque<T>& operator+=(const KDeque<T>& other);
    KDeque<T> operator+(const KDeque<T>& other);

    KIterator begin();
    KIterator end();

    void accept(IsUniqueVisitor<T>& visitor);
};


template<typename T>
void KDeque<T>::accept(IsUniqueVisitor<T>& visitor)
{
    visitor.visit(*this);
}

template<typename T>
KDeque<T>::KDeque()
{
    this->_size = 0;
    head = tail = NULL;
}

template<typename T>
KDeque<T>::KDeque(std::initializer_list<T> args) : KDeque()
{
    for (auto x : args)
        pushBack(x);
}

template<typename T>
KDeque<T>::KDeque(KDeque<T>&& other) : _size(other._size), head(other.head), tail(other.tail)
{
    other.head = other.tail = nullptr;
    other._size = 0;
}

template<typename T>
KDeque<T>::KDeque(const KDeque<T>& other) : KDeque()
{
    auto *cur = other.head;
    while (cur != NULL) {
        pushBack(cur->value);
        cur = cur->next;
    }
}

template<typename T>
KDeque<T>::~KDeque()
{
    clear();
}

template<typename T>
bool KDeque<T>::isEmpty() const
{
    return this->_size == 0;
}

template<typename T>
int KDeque<T>::size() const
{
    return this->_size;
}

template<typename T>
void KDeque<T>::clear()
{
    KDeque<T>::Node *nxt;
    for (int i = 0; i < this->_size; i++) {
        nxt = head->next;
        delete head;
        head = nxt;
    }
    head = tail = NULL;
    this->_size = 0;
}

template<typename T>
T& KDeque<T>::front() const
{
    std::cout << "Your deque is empty!\n";
    return head->value;
}

template<typename T>
T& KDeque<T>::back() const
{
    std::cout << "Your deque is empty!\n";
    return tail->value;
}

template<typename T>
void KDeque<T>::pushFront(T& element)
{
    KDeque<T>::Node* newHead = new KDeque<T>::Node(element);
    if (this->_size) {
        head->prev = newHead;
    }
    else {
        tail = newHead;
    }
    newHead->next = head;
    head = newHead;
    ++this->_size;
}

template<typename T>
void KDeque<T>::pushBack(T element)
{
    KDeque<T>::Node* newTail = new KDeque<T>::Node(element);
    if (this->_size)
        tail->next = newTail;
    else
        head = newTail;
    newTail->prev = tail;
    tail = newTail;
    ++this->_size;
}

template<typename T>
void KDeque<T>::popBack()
{
    if (this->_size > 1) {
        KDeque<T>::Node* newTail = tail->prev;
        delete tail;
        tail = newTail;
        tail->next = NULL;
        _size--;
    }
    else if (this->_size == 1) {
        delete tail;
        head = tail = NULL;
        _size--;
    }
    else {
        std::cout << "Nothing to pop. KDeque<T> is empty\n";
    }
}

template<typename T>
void KDeque<T>::popFront()
{
    if (this->_size > 1) {
        KDeque<T>::Node* newHead = head->next;
        delete head;
        head = newHead;
        head->prev = NULL;
        _size--;
    }
    else if (this->_size == 1) {
        delete head;
        head = tail = NULL;
        _size--;
    }
    else {
        std::cout << "Nothing to pop. KDeque<T> is empty\n";
    }
}

template<typename T>
void KDeque<T>::swap(KDeque<T>& other)
{
    std::swap(head, other.head);
    std::swap(tail, other.tail);
    std::swap(_size, other._size);
}

template<typename T>
std::ostream& operator<<(std::ostream& out, KDeque<T>& other)
{
    auto cur = other.head;
    while (cur != NULL) {
        out << cur->value << " ";
        cur = cur->next;
    }
    out << std::endl;
    return out;
}

template<typename T>
bool KDeque<T>::operator==(const KDeque<T>& other) const {
    KDeque<T>::Node *f = this->head,
        *s = other.head;
    if (this->_size != other._size)
        return false;

    while (f != NULL && s != NULL) {
        if (f->value != s->value)
            return false;
        f = f->next;
        s = s->next;
    }
    return true;
}

template<typename T>
bool KDeque<T>::operator!=(const KDeque<T>& other) const {
    return !((*this) == other);
}

template<typename T>
KDeque<T>& KDeque<T>::operator=(const KDeque<T>& other)
{
    if (this != &other) {
        clear();
        KDeque<T>::Node *cur = other.head;
        while (cur != NULL) {
            pushBack(cur->value);
            cur = cur->next;
        }
    }
    return (*this);
}

template<typename T>
KDeque<T>& KDeque<T>::operator=(KDeque<T>&& other)
{
    if (this != &other) {
        clear();
        _size = other._size;
        head = other.head;
        tail = other.tail;
        other.head = other.tail = nullptr;
        other._size = 0;
    }
    return *this;
}

template<typename T>
KDeque<T>& KDeque<T>::operator+=(const KDeque<T>& other)
{
    KDeque<T>::Node *cur = other.head;
    while (cur != NULL) {
        pushBack(cur->value);
        cur = cur->next;
    }
    return (*this);
}

template<typename T>
KDeque<T> KDeque<T>::operator+(const KDeque<T>& other)
{
    KDeque *result = new KDeque;
    (*result) = (*this);
    (*result) += other;
    return (*result);
}



template<typename T>
KDeque<T>::KIterator::KIterator(KDeque<T>::Node* other)
{
    node = other;
}

template<typename T>
typename KDeque<T>::KIterator KDeque<T>::KIterator::operator++()
{
    node = node->next;
    return *this;
}

template<typename T>
T& KDeque<T>::KIterator::operator*() const
{
    return node->value;
}

template<typename T>
typename KDeque<T>::KIterator KDeque<T>::begin()
{
    return typename KDeque<T>::KIterator::KIterator(head);
}

template<typename T>
typename KDeque<T>::KIterator KDeque<T>::end()
{
    return typename KDeque<T>::KIterator::KIterator(tail->next);
}

template<typename T>
bool KDeque<T>::KIterator::operator!=(const KDeque<T>::KIterator& other)
{
    return this->node != other.node;
}