#pragma once

#include<iostream>
using std::cout;
using std::cerr;

template<typename T>
struct List;

template<typename T>
class DNode {
private:
    DNode<T> *next, *prev;
public:
    T data;

    DNode<T>(const T& v, DNode<T>* n = nullptr, DNode<T>* p = nullptr)
        : data(v), next(n), prev(p) { }

    DNode<T>* insert(List<T>& l, DNode* n);                         // insert n before this object
    DNode<T>* add(DNode<T>* n);                                     // insert n after this object
    DNode<T>* erase(List<T>& l);                                   // remove this object from the list
    DNode<T>* find(const List<T>& l, const T& x);             // find s in list
    const DNode<T>* find(const List<T>& l, const T& x) const; // find s in const list

    DNode<T>* advance(int n) const; // move n positions in list

    DNode<T>* getNext() const { return next; }
};

template<typename T>
struct List {
    List() : first_DNode(nullptr) { } //default ctor
    List(DNode<T>* n) : first_DNode(n) { }
    DNode<T>* first_DNode;
};

// insert n before this object
template<typename T>
DNode<T>* DNode<T>::insert(List<T>& l, DNode* n) {
    if (n == nullptr) return this;
    if (this == nullptr) return n;
    n->next = this;
    if (l.first_DNode == this) {
        l.first_DNode = n;
        return n;
    }
    DNode* p = l.first_DNode;
    while (p->next != this)
        p = p->next;
    p->next = n;
    return n;
}

// insert n after this object
template<typename T>
DNode<T>* DNode<T>::add(DNode* n) {
    if (n == 0) return this;
    if (this == 0) return n;
    n->next = next;
    next = n;
    return n;
}

// erase this object, return nextessor
template<typename T>
DNode<T>* DNode<T>::erase(List<T>& l) {
    if (this == 0) return 0;
    if (l.first_DNode == this) {
        l.first_DNode = next;
    }
    DNode* p = l.first_DNode;
    while (p->next != this)
        p = p->next;
    p->next = next;
    return next;
}

// find s in list; return 0 for "not found"
template<typename T>
DNode<T>* DNode<T>::find(const List<T>& l, const T& x) {
    DNode<T>* p = l.first_DNode;
    while (p) {
        if (p->data == x) return p;
        p = p->next;
    }
    return 0;
}

// find s in const list; return 0 for "not found"
template<typename T>
const DNode<T>* DNode<T>::find(const List<T>& l, const T& x) const {
    const DNode<T>* p = l.first_DNode;
    while (p) {
        if (p->data == x) return p;
        p = p->next;
    }
    return nullptr;
}

// move n positions in list, return 0 for "not found"
// positive n moves forward
template<typename T>
DNode<T>* DNode<T>::advance(int n) const {
    if (this == 0) return 0;
    DNode<T>* p = const_cast<DNode<T>*>(this);  // UGLY
    if (0 <= n) {
        while (n--) {
            if (p->next == 0) return 0;
            p = p->next;
        }
    }
    else cerr << "must advance by a positive number";
    return p;
}


template<typename T>
void print_all(const List<T>& l)
{
    cout << "{ ";
    DNode<T>* p = l.first_DNode;
    while (p) {
        cout << p->data;
        if (p = p->getNext()) cout << ", ";
    }
    cout << " }";
}

template<typename T>
void print_all(DNode<T>* n)
{
    cout << "{ ";
    while (n) {
        cout << n->data;
        if (n = n->getNext()) cout << ", ";
    }
    cout << " }";
}