#ifndef LINKED_LIST_TEMPLATE_CLASS_HPP
#define LINKED_LIST_TEMPLATE_CLASS_HPP
#pragma once
 
#include <iterator>
 
//This class will be referenced in the LinkedList class so it need to be declared before it can be used...
//    it uses the LinkedList class in its implementation so it can not be defined first.
template<typename T, typename T_REF, typename T_PTR> class LinkedListIterator;
 
//We want the LinkedList Class to work for multiple different types of objects...
//So we will create a template
template <typename T>
class LinkedList {
    //This will simplify things when we need to refer to the current class's type...
    typedef LinkedList<T> _ThisType;
 
    // First let us define the inner classes use: 
    //     LinkedListNode - protected (because the LinkedList Class and its decendants are the only classes that should use it)
    //     LinkedListIterator - public because other classes will use it to interact with the linked list.
    protected:
    //inner class... Associate an element with a pointer to the next element...
    struct LinkedListNode {
        T data;
        LinkedListNode *next;
 
        //Constructors useful for initializing members
        explicit LinkedListNode(const T &element) : data(element), next(NULL) { } //Make sure that next defaults to NULL...
        LinkedListNode(const T &element, LinkedListNode *nxt) : data(element), next(nxt) { } //Make sure that next defaults to NULL...
        //Special function for appending a node to the current node.
        LinkedListNode& insertNext(LinkedListNode *nxt) { 
            if (nxt!=NULL) {
                LinkedListNode *temp = next;
                next = nxt;
                nxt->next = temp;
            }
            return *this;
        }
        //get the data 
        operator T() { return data; }        
    };
 
 
    public:
 
    //Define the iterator class as friend (much easier than making it nested...)
    // note that these definitions illistrate why the iterator template uses three parameters.
    friend class LinkedListIterator<T, T&, T*>;
    friend class LinkedListIterator<T, const T&, const T*>; //Here we want the reference and pointers to be const, but not the data!
 
    //define some friendly names for various versions of the iterator class
    typedef LinkedListIterator<T, T&, T*> iterator;
    typedef LinkedListIterator<T, const T&, const T*> const_iterator;
 
    //Allow access to the the template type.. 
    typedef T value_type; 
    typedef unsigned int size_t;
 
    protected:
    //Each linked list has a root node pointer...
    LinkedListNode *root;
    //Keeping track of the last node will speed some operations up...
    LinkedListNode *lastNode;
 
    //Private function to update the lastNode
    void setLastNode() { 
        if(lastNode == NULL) { lastNode = root; }
        while(lastNode->next) { lastNode = lastNode->next; }
    }
 
    public:
    //Default constructor... set root to null!
    LinkedList() : root(NULL), lastNode(NULL) { }
 
    //constructor to initialize with a given number of nodes using value_type's default constructor.
    explicit LinkedList(size_t size) : root(NULL), lastNode(NULL) {
        for(size_t i=0; i < size; ++i) {
            push_top(value_type());
        }
    }
 
    //constructor to initialize with a given number of nodes with a default value.
    //   value_type must have a copy constructor... is this constructor necessary?
    LinkedList(size_t size, value_type defValue) : root(NULL), lastNode(NULL) {
        for(size_t i=0; i < size; ++i) {
            push_top(value_type(defValue));
        }
    }
 
    //Deconstructor... We need to scroll though the list and "delete" any nodes we find.
    ~LinkedList() {
        LinkedListNode *ptr = root;
        while (ptr) {
            //********* Debugging line *************
            //std::cout << "killing: " << ptr->data << (ptr->next ? "-->next": "-->NULL") << std::endl;
            root = ptr->next;
            delete ptr;
            ptr = root;
        }
 
    }
 
    //Note that if you need a deconstructor, you generally also need a copy constructor and an assignment operator...
    // This is a copy constructor that will make a copy of a LinkedList by coping over all of the data...
    LinkedList(const LinkedList<T>& rhs) { 
        LinkedListNode *ptr = rhs.root;
        if(ptr) {
            root = new LinkedListNode(ptr->data);
            ptr = ptr->next;
            lastNode = root;
            //****** debug ****
            //std::cout <<"(copy) created: " <<root->data << (ptr->next ? "-->next": "-->NULL") << std::endl;
            while(ptr) {
                lastNode->next = new LinkedListNode(ptr->data);
                lastNode = lastNode->next; 
                //****** debug****
                //std::cout <<"(copy) created: " <<thisptr->data << (ptr->next ? "-->next": "-->NULL") <<std::endl;
                ptr = ptr->next;
            }
        }
    }
 
    //If you need a copy constructor, you also need an assignment operator...
    // This will delete the current contents of the list, and copy over the data from the other list...
    _ThisType &operator=(const LinkedList<T>& rhs) {
        //self-assignment is ignored...
        if (&rhs == this) { return *this; }
        //first of all, get rid of any data currently in the list...
        while (pop_top()) { /* do nothing */ }
        //Next construct a new list from the data in the rhs...
        LinkedListNode *ptr = rhs.root;
        if(ptr) {
            root = new LinkedListNode(ptr->data); 
            //****** debug ****
            //std::cout <<"(assign) created: " <<root->data <<std::endl;
            ptr = ptr->next;
            lastNode = root;
            while(ptr) {
                lastNode->next = new LinkedListNode(ptr->data);
                lastNode = lastNode->next; 
                //****** debug****
                //std::cout <<"(assign) created: " <<thisptr->data << (ptr->next ? "-->next": "-->NULL") <<std::endl;
                ptr = ptr->next;
            }
        }
        return *this;   
    }
 
 
    // Add elements to the top/front of the list (i.e. create a new root element)
    _ThisType &push_top(value_type element = value_type()) {
        //first check if root is null... if it is then this is where we add the element....
        if (!root) {
            root = new LinkedListNode(element);
            lastNode = root;
        } else { // else we create a new root and push everything else down the line...
            LinkedListNode *temp = root;
            root = new LinkedListNode(element, temp);
        }
        return *this;
    }
 
    // Add elements to the bottom/back of the list (i.e. append a new node)
    // Scroll though the list looking for the place where "next" is NULL
    _ThisType &push_back(value_type element = value_type()) {
        //first check if root is null... if it is then this is where we add the element....
        if (!root) {
            root = new LinkedListNode(element);
            lastNode = root;
        } else { // else we need to look for ptr->next == null...
            lastNode->insertNext(new LinkedListNode(element));
            lastNode = lastNode->next;
        }
        return *this;
    }
 
 
    bool pop_top() {
        if(root) {
            LinkedListNode* temp = root;
            root = root->next; //node is no longer part of the list...
            delete temp;
            if (root == NULL) { lastNode = NULL; }
            return true;
        }
        return false;
    }
 
    bool pop_top(int n) {
        bool retVal = true;
        while (n-- > 0 && retVal) { retVal = pop_top(); }
        return retVal;
    }
 
    bool pop_back() {
        if(root) {
            if(root==lastNode) { 
                delete root;
                root = NULL;
                lastNode = NULL;
                return true;
            }
            LinkedListNode* ptr = root;
            while(ptr->next != lastNode) { ptr = ptr->next; } //after this loop ptr will be the second to last node
            //lastNode is the last node, ptr is the next-to-last node...
            ptr->next = NULL;
            delete lastNode;
            lastNode = ptr;
            return true;
        }
        return false;
    }
 
    bool pop_back(int n) {
        bool retVal = true;
        while (n-- > 0 && retVal) { retVal = pop_back(); }
        return retVal;
    }
 
 
    //inserts
    _ThisType& insertAfter(iterator here, const value_type &item) {
        if (here) {
            LinkedListNode* newNode = new LinkedListNode(item, here.current_node->next);
            if (here.hasParent()) {
                if (here.current_node == here.getPtrToParent()->lastNode) { here.getPtrToParent()->lastNode = newNode; }
            }
            here.current_node->next = newNode;
        } else {
            if (here.hasParent()) { here.getPtrToParent()->push_back(item); } else { push_back(item); }
        }
        return *this;
    }
 
    _ThisType& insert(iterator here, const value_type &item) {
        //std::cout << "parent: " << here.parent << " list: " << this << std::endl;
        if (!here) { 
            if (here.hasParent()) { 
                here.getPtrToParent()->push_back(item); 
            } else { 
                push_back(item); 
            }
        } else {
            if (here.getPtrToParent() == this) { //does this belong to the current list? If we 
                if (here.current_node == root) { 
                    push_top(item); 
                } else {
                    LinkedListNode* ptr = root;
                    while(ptr->next!=here.current_node) { ptr=ptr->next; } //find the node before here.current_node
                    ptr->next = new LinkedListNode(item, here.current_node); // insert the node
                    if(ptr==lastNode) { lastNode = lastNode->next; }
                }
            } else {
                if(here.hasParent()) { here.getPtrToParent()->insert(here, item); } else { push_back(item); }
            }
        }
        return *this;
    }
 
    _ThisType &operator+=(const _ThisType &list) {
        const_iterator theEnd = list.end();
        for(const_iterator iter = list.begin(); iter != theEnd; ++iter) {
            push_back(*iter);
        }
        return *this;
    }
 
    iterator find(const value_type &item) {
        iterator iter = begin();
        iterator theEnd = end();
        for(; iter!=theEnd; ++iter) {
            if(*iter == item) { return iter; }
        }
    }
 
    const_iterator find(const value_type &item) const {
        const_iterator iter = begin();
        const_iterator theEnd = end();
        for(; iter!=theEnd; ++iter) {
            if(*iter == item) { return iter; }
        }
    }
 
    bool isEmpty() const { return root == NULL; }
    iterator begin()  { return iterator(root, *this); }
    iterator end()    { return NULL; }
    iterator last()   { return iterator(lastNode, *this); }
    const_iterator begin() const { return const_iterator(root, *this); }
    const_iterator end() const   { return NULL; }
    const_iterator last() const  { return const_iterator(lastNode, *this); }
};
 
template<typename T, typename T_REF, typename T_PTR>
class LinkedListIterator: public std::iterator<std::forward_iterator_tag, T> {
    friend class LinkedList<T>;
    typedef typename LinkedList<T>::LinkedListNode ListNode;
    typedef LinkedListIterator<T, T_REF, T_PTR> _ThisType;
    ListNode *current_node;
    LinkedList<T> *parent;
 
    public:
    typedef T value_type;       
    LinkedListIterator() : current_node(NULL), parent(NULL) { }
    LinkedListIterator(ListNode* node) : current_node(node), parent(NULL) { }
    LinkedListIterator(ListNode* node, const LinkedList<T>& parentList) : current_node(node), parent(const_cast<LinkedList<T>*>(&parentList)) { }
    LinkedListIterator(const _ThisType& iter) : current_node(iter.current_node), parent(iter.parent) { }
 
    bool operator==(const _ThisType& rhs) const {
        return current_node == rhs.current_node;
    }
 
    bool operator!=(const _ThisType& rhs) const {
        return current_node != rhs.current_node;
    }
 
    _ThisType& operator++() {
        if(current_node!=NULL) {
            current_node = current_node->next;
        }
        return *this;
    }
 
    _ThisType operator++(int) {
        //we want to ensure the iter++ operator returns the current value, and THEN updates...
        _ThisType temp = *this; //so we create a temp and assign the current iterator
        if(current_node!=NULL) {
            current_node = current_node->next; //increment this.
        }
        return temp; //return the copy...
    }
 
 
    T_REF operator*() const { return current_node->data; }
    T_PTR operator->() const { return &(operator*()); }
 
    bool isValid() { return current_node!=NULL; }
    bool isLast() { return (current_node!=NULL) ? current_node->next == NULL : true; }
    operator void*() { return current_node; }
 
    LinkedList<T> *getPtrToParent(){ return parent; }
    bool hasParent() { return parent!=NULL; }
    void setParent(const LinkedList<T>& parentList) { 
        if (this->parent != &parentList) {
            this->parnet = &parentList;
            current_node = parentList.begin();
        }
    }
 
};
 
#endif

#include <iostream>
#include <string>
#include "LinkedListTemplate.hpp"
 
template<typename T>
std::ostream& operator<<(std::ostream& out, const LinkedList<T> &list) {
    typename LinkedList<T>::const_iterator iter = list.begin();
    typename LinkedList<T>::const_iterator theEnd = list.end();
    if (iter==theEnd) { 
        out << "NULL"; 
    } else {
        while(!iter.isLast()) {
            out << *iter++ << " --> ";
        }
        out << *iter << " --> NULL.";
    }
    return out;
}
 
int main() {
    //Lets make sure things work with another type...
    LinkedList<int> listOfInts;
    LinkedList<int> listOfInts2;
    listOfInts.push_back(1).push_back(2).push_back(3).push_back(4);
    std::cout << "List of ints: " << listOfInts << std::endl;
    //Lets make sure the assignment operator works...
    listOfInts2 = listOfInts;
    std::cout << "Assignment: " << listOfInts2 << std::endl;
    listOfInts2.pop_back(); 
    listOfInts2.pop_top();
    std::cout << "remove First and Last: " << listOfInts2 << std::endl;
    LinkedList<int> listOfInts3;
    listOfInts3.push_top(1).push_top(2).push_top(3).push_top(4);
    std::cout << "push top: " << listOfInts3 << std::endl;
    listOfInts3.pop_top();
    std::cout << "pop top: " << listOfInts3 << std::endl;
 
    listOfInts3.pop_back();
    std::cout << "pop back: " << listOfInts3 << std::endl;
    listOfInts3.insertAfter(listOfInts3.begin(), 8);
    std::cout << "insertAfter begin(): " << listOfInts3 << std::endl;
    listOfInts3.insertAfter(listOfInts3.end(), 10);
    std::cout << "insertAfter end(): " << listOfInts3 << std::endl;
 
    listOfInts3.insert(listOfInts3.begin(), 5);
    std::cout << "insert begin(): " << listOfInts3 << std::endl;
    listOfInts3.insert(++listOfInts3.begin(), 6);
    std::cout << "insert ++begin(): " << listOfInts3 << std::endl;
 
 
    listOfInts3 += listOfInts2;
    std::cout << "insert ++begin(): " << listOfInts3 << std::endl;
 
    return 0;
}