#ifndef dll_h
#define dll_h
#include <iostream>
using namespace std;
template <class ItemType>
struct NodeType
{
    ItemType info;
    NodeType* next;
    NodeType* back;
};


template <class ItemType>
class DoublyLinkedList
{
public:
    DoublyLinkedList();     // Class constructor.
    ~DoublyLinkedList();    // Class destructor.

    ////////// implement these functions //////////
    DoublyLinkedList(DoublyLinkedList<ItemType>& );
    void InsertItem(ItemType item);
    void DeleteItem(ItemType item);
    void reverseDoublyLinkedList();


    void FindItem(NodeType<ItemType>* listData, ItemType item, NodeType<ItemType>*& location, bool& found);
    int LengthIs() const;
    void MakeEmpty();
    void RetrieveItem(ItemType& item, bool& found);
    void ResetList();
    void GetNextItem(ItemType& item);

private:
    NodeType<ItemType>* listData;
    int length;
    NodeType<ItemType>* currentPos;
};
#endif

#include "DLL.h"
template<class ItemType>
DoublyLinkedList<ItemType>::DoublyLinkedList()
{
    listData = NULL;
    length =0;
    currentPos = NULL;

}
template<class ItemType>
void DoublyLinkedList<ItemType>::FindItem(NodeType<ItemType>* listData, ItemType item,
                                          NodeType<ItemType>*& location, bool& found)
// Assumption: ItemType is a type for which the operators "<" and
//  "==" are defined-either an appropriate built-in type or a
//  class that overloads these operations.
// Pre:  List is not empty.
// Post: If there is an element someItem whose key matches item's
//       key, then found = true; otherwise, found = false.
//       If found, location contains the address of someItem;
//       otherwise, location contains the address of the logical
//       successor of item.
{
    bool moreToSearch = true;

    location = listData;
    found = false;
    while (moreToSearch && !found)
    {
        if (item < location->info)
            moreToSearch = false;
        else if (item == location->info)
            found = true;
        else
        {
            location = location->next;
            moreToSearch = (location != NULL);
        }
    }
}


template <class ItemType>
int DoublyLinkedList<ItemType>::LengthIs() const
{
    return length;
}

template <class ItemType>
void DoublyLinkedList<ItemType>::MakeEmpty()
// Post: List is empty; all items have been deallocated.
{
    NodeType<ItemType>* tempPtr;

    while (listData != NULL)
    {
        tempPtr = listData;
        listData = listData->next;
        delete tempPtr;
    }
    length = 0;
}

template <class ItemType>
void DoublyLinkedList<ItemType>::ResetList()
{
    currentPos = NULL;
}

template <class ItemType>
void DoublyLinkedList<ItemType>::GetNextItem(ItemType& item)
{
    if (currentPos == NULL)
        currentPos = listData;
    else
        currentPos = currentPos->next;
    item = currentPos->info;
}

template <class ItemType>
void DoublyLinkedList<ItemType>::RetrieveItem(ItemType& item,
                                              bool& found)
{
    bool moreToSearch;
    NodeType<ItemType>* location;

    location = listData;
    found = false;
    moreToSearch = (location != NULL);

    while (moreToSearch && !found)
    {
        if (location->info < item)
        {
            location = location->next;
            moreToSearch = (location != NULL);
        }
        else if (item == location->info)
        {
            found = true;
            item = location->info;
        }
        else
            moreToSearch = false;
    }
}

template <class ItemType>
DoublyLinkedList<ItemType>:: ~DoublyLinkedList()    // Class destructor.
{
    MakeEmpty();
}

template <class ItemType>
void DoublyLinkedList<ItemType>::InsertItem(ItemType item)
{
    NodeType<ItemType>* node = new NodeType<ItemType>;
    node->info = item;
    if(!length)
    {
        listData = node;
        node->next = NULL;
        node->back = NULL;
        length++;
        return;
    }
    NodeType<ItemType>* temp =listData;
    while(temp->next != NULL && node->info > temp->next->info)
        temp=temp->next;
    node->back = temp;
    node->next = temp->next;
    if(temp->next != NULL)
        node->next->back = node;
    temp->next = node;
    length++;
}


template <class ItemType>
void DoublyLinkedList<ItemType>::DeleteItem(ItemType item)
{
    NodeType<ItemType>* node = listData;
    if(node == NULL)
        return;
    while(node != NULL && node->info != item)
        node = node->next;
    if(node == NULL)
        return;
    if(node->back != NULL)
        node->back->next = node->next;
    if(node->next != NULL)
        node->next->back = node->back;
    delete node;
    length--;
}

template <class ItemType>
DoublyLinkedList<ItemType>::DoublyLinkedList(DoublyLinkedList<ItemType>& original)
{
    length = original.length;
    if(original.listData == NULL)
    {
        listData = NULL;
        currentPos = NULL;
        return;
    }
    listData = new NodeType<ItemType>;
    NodeType<ItemType> *tempB, *tempN, *node = listData;
    NodeType<ItemType>* copy = original.listData;
    node->back = NULL;
    while(copy != NULL)
    {
        if(original.currentPos == copy)
            currentPos = node;
        node->info = copy->info;
        tempB = node;
        tempN = new NodeType<ItemType>;
        copy = copy->next;
        node->next = tempN;
        node=node->next;
        node->back = tempB;
    }
    node->next = NULL;
}

template<class ItemType>
void DoublyLinkedList<ItemType>::reverseDoublyLinkedList()
{
    if(listData == NULL)
        return;
    if(listData->next == NULL)
        return;
    NodeType<ItemType> *node, *first, *newNode, *tempB, *tempN;
    node = listData;
    while(node->next != NULL)
        node = node->next;
    first = node;
    newNode = new NodeType<ItemType>;
    newNode->back = NULL;
    while(node != NULL);
    {
        if(currentPos == node)
            currentPos = newNode;
        newNode->info = node->info;
        tempB = newNode;
        tempN = new NodeType<ItemType>;
        node = node->back;
        newNode->next = tempN;
        newNode = newNode->next;
        newNode->back = tempB;
    }
    newNode->next = NULL;
    listData = first;
}

#include <iostream>
#include "dll.h"
#include "dll.cpp"

int main()
{
    DoublyLinkedList<int> s;
    s.InsertItem(3);
    s.InsertItem(4);
    s.InsertItem(1);
    s.DeleteItem(2);
    s.DeleteItem(4);
    cout<<"Length of s: "<<s.LengthIs()<<endl;
    DoublyLinkedList<int> t = s;
    cout<<"Length of t: "<<t.LengthIs()<<endl;
    s.InsertItem(5);
    s.InsertItem(8);
    s.InsertItem(10);
    s.InsertItem(1);
    int a;
    for(int i=0;i<s.LengthIs();i++)
    {
        s.GetNextItem(a);
        cout<<"Item #"<<i<<": "<<a<<endl;
    }
    for(int i=0;i<s.LengthIs();i++)
    {
        s.GetNextItem(a);
        cout<<"Item #"<<i<<": "<<a<<endl;
    }
    cout<<endl;
}