#pragma once

////////////****************DLList.h*********************************
#include <iostream>
//using namespace std;

template<class T>
class DLLNode {
public:
    DLLNode() {
        next = prev = nullptr;
    }
    DLLNode(const T& el, DLLNode *n = 0, DLLNode *p = 0) {
        data = el; next = n; prev = p;
    }
    T data;
    DLLNode *next, *prev;
};

template <class T>
class DLList {
public:
    DLList() {
        head = new DLLNode<T>;
        tail = new DLLNode<T>;
        head->next = tail;
        tail->prev = head;
    }
    //void addToDLLTail(const T&);
    //void insertAtTail(const T&);
    T deleteDLLTail();
    void insertInMiddle(const T&);
    void printDll() const;
    //void add(DLLNode<T> *, const T& );
    void addTail(const T&);
    void addHead(const T&);

    //...............
private:
    DLLNode<T> *head, *tail;
protected:
    void add(DLLNode<T> *v, const T&);
};

/*template <class T>
void DLList<T>::addToDLLTail(const T& thing) {
    if (tail != 0) { // not an empty list
        tail = new DLLNode<T>(thing,0,tail);
        tail->prev->next = tail;
    }
    else       // add to empty list
        head = tail = new DLLNode<T>(thing);
}*/

// insert a new node containing x before v
template <class T>
void DLList<T>::add(DLLNode<T> *v, const T& x) {
    DLLNode<T> *u = new DLLNode<T>; //create a new node for x
    u->data = x;  //put the data in the node
    u->next = v; // link u in between v
    u->prev = v->prev; //...and v->prev
    v->prev->next = v->prev = u;
}

template <class T>
void DLList<T>::addHead(const T& x) { // add to front of list
    add(head->next, x);
}

template <class T>
void DLList<T>::addTail(const T& x) {// add to back of list
    add(tail, x);
}

/*template <class T>
void DLList<T>::insertAtTail(const T& entry) {
    DLLNode<T> *newNode = new DLLNode<T>(entry, NULL, tail);
    if (tail)
        tail->next = newNode;
    tail = newNode;
    //++node_count;
}*/


template <class T>
T DLList<T>::deleteDLLTail() {
    T datum = tail->data;
    if (head == tail) {// only one thing in list
        delete head;
        head = tail = nullptr;
    }
    else { // more than one item in the list
        tail = tail->prev;
        delete tail->next;
        tail->next = nullptr;
    }
    return datum; //you might want that for something?
}

template <class T>
void DLList<T>::printDll() const {
    for (DLLNode<T> *tmp = head->next; tmp->next != 0; tmp = tmp->next)
        cout << tmp->data << " ";
    cout << endl;
}

template<class T>
void DLList<T>::insertInMiddle(const T& thing) {
    if (head != 0) {
        if (head->next != 0) { //at least two items on the list
            int N = 1;  //counter
            DLLNode<T> *tmp = head; // persistence
            for (; tmp->next != 0; N++, tmp = tmp->next);
            // tmp starts at the head and pushes to the middle
            for (tmp = head, N = N / 2; N; N--, tmp = tmp->next);
            // tmp is at the middle, create a new DLLNode with next and prev
            add(tmp, thing);
            //tmp->prev = tmp->prev->next = new DLLNode<T>(thing,tmp,tmp->prev);
        }
        // there's only one element so the middle is the end
        else addTail(thing);
        //head->next = tail = new DLLNode<T>(thing,0,head);
    } // empty list, so insert new element.
    else addHead((thing));
}

#endif // DLList