DoublyLinkedList

// Main.cpp

#include <cstdlib>
#include <ctime>
#include <iostream>
#include "DoublyLinkedList.hpp"

using namespace std;

int Compare(int a,int b)
{
    return a - b;
}

int main(int argc, char *argv[])
{
    int k,n,m;
    DoublyLinkedList<int> L;
    srand(time(NULL));
    cin>>n>>m;
    for(k = 1;k <= n;k++)
       L.insertLast(rand()%m);
    L.displayForward();
    L.displayBackward();
    L.MergeSort(Compare);
    L.displayForward();
    L.displayBackward();
    while(!L.isEmpty())
       L.deleteFirst();
    system("PAUSE");
    return EXIT_SUCCESS;
}

// Link.hpp

template<class T>
class Link
{
      private:
              T data;
              Link<T> *next;
              Link<T> *previous;
      public:
             Link(T data);
             void displayLink();
             T getData();
             void setData(T data);
             Link<T> *getNext();
             void setNext(Link<T> *next);
             Link<T> *getPrevious();
             void setPrevious(Link<T> *previous);
             template<class U> friend std::ostream& operator<< (std::ostream& print, Link<U>& obj);

};

template<class T>
Link<T>::Link(T data)
{
     setData(data);
     setNext(NULL);
     setPrevious(NULL);

}

template<class T>
void Link<T>::displayLink()
{
     std::cout<<getData()<<" ";
}

template<class T>
T Link<T>::getData()
{
     return data;
}

template<class T>
void Link<T>::setData(T data)
{
     this->data = data;
}

template<class T>
Link<T> *Link<T>::getNext()
{
      return next;
}

template<class T>
void Link<T>::setNext(Link<T> *next)
{
      this->next = next;
}

template<class T>
Link<T> *Link<T>::getPrevious()
{
      return previous;
}

template<class T>
void Link<T>::setPrevious(Link<T> *previous)
{
      this->previous = previous;
}


template <class U>
std::ostream& operator<<(std::ostream& print, Link<U> & L)
{
        print << L.getData();
        return print;
}

//DoublyLinkedList.hpp


#include "Link.hpp"

template<class T>
class DoublyLinkedList
{
      private:
              Link<T> *first;
              Link<T> *last;
              Link<T> *headdel();
              void tailins(Link<T> *p);
      public:
             DoublyLinkedList();
             ~DoublyLinkedList();
             Link<T> *getFirst();
             void setFirst(Link<T> *first);
             Link<T> *getLast();
             void setLast(Link<T> *first);
             bool isEmpty();
             Link<T> *find(T key);
             void insertFirst(T dd);
             void insertLast(T dd);
             void deleteFirst();
             void deleteLast();
             bool insertAfter(T key,T dd);
             void deleteKey(T key);
             void displayForward();
             void displayBackward();
             bool Split(DoublyLinkedList<T> &A,DoublyLinkedList<T> &B,int (*Compare)(T,T));
             void Merge(DoublyLinkedList<T> &A,DoublyLinkedList<T> &B,int (*Compare)(T,T));
             void MergeSort(int (*Compare)(T,T));
};

template<class T>
DoublyLinkedList<T>::DoublyLinkedList()
{
    setFirst(NULL);
    setLast(NULL);
}

template<class T>
DoublyLinkedList<T>::~DoublyLinkedList()
{
    while(!isEmpty())
    {
        deleteFirst();
    }
}

template<class T>
Link<T> *DoublyLinkedList<T>::getFirst()
{
       return first;
}

template<class T>
void DoublyLinkedList<T>::setFirst(Link<T> *first)
{
     this->first = first;
}

template<class T>
Link<T> *DoublyLinkedList<T>::getLast()
{
       return last;
}

template<class T>
void DoublyLinkedList<T>::setLast(Link<T> *last)
{
     this->last = last;
}

template<class T>
bool DoublyLinkedList<T>::isEmpty()
{
     return getFirst()==NULL;
}

template<class T>
 Link<T> *DoublyLinkedList<T>::find(T key)
 {
         Link<T> *current = getFirst();
         while(current != NULL && !(current->getData == key))
               current = current->getNext();
         return current;
 }

 template<class T>
 void DoublyLinkedList<T>::insertFirst(T dd)
 {
      Link<T> *newLink = new Link<T>(dd);
      if(isEmpty())
           setLast(newLink);
      else
          getFirst()->setPrevious(newLink);
      newLink->setNext(getFirst());
      setFirst(newLink);
 }

 template<class T>
 void DoublyLinkedList<T>::insertLast(T dd)
 {
      Link<T> *newLink = new Link<T>(dd);
      if(isEmpty())
      {
          setFirst(newLink);
      }
      else
      {
          getLast()->setNext(newLink);
          newLink->setPrevious(getLast());
      }
      setLast(newLink);
 }

 template<class T>
 void DoublyLinkedList<T>::deleteFirst()
 {
      if(isEmpty())
           return;
      Link<T> *temp = getFirst();
      if(getFirst()->getNext() == NULL)
            setLast(NULL);
      else
         getFirst()->getNext()->setPrevious(NULL);
      setFirst(getFirst()->getNext());
      delete temp;
 }

 template<class T>
 void DoublyLinkedList<T>::deleteLast()
 {
      if(isEmpty())
         return;
      Link<T> *temp = getLast();
      if(getFirst()->getNext() == NULL)
             setFirst(NULL);
      else
          getLast()->getPrevious()->setNext(NULL);
      setLast(getLast()->getPrevious());
      delete temp;
 }

 template<class T>
 bool DoublyLinkedList<T>::insertAfter(T key,T dd)
 {
      Link<T> *current = find(key);
      if(current == NULL)
             return false;
      Link<T> *newLink = new Link<T>(dd);
      if(current->getNext() == NULL)
      {
           newLink->setNext(NULL);
           setLast(newLink);
      }
      else
      {
          newLink->setNext(current->getNext());
          current->getNext()->setPrevious(newLink);
      }
      newLink->setPrevious(current);
      current->setNext(newLink);
      return true;
 }

 template<class T>
 void DoublyLinkedList<T>::deleteKey(T key)
 {
      Link<T> *current = find(key);
      if(current==NULL)
           return;
      if(current->getPrevious() == NULL)
             setFirst(current->getNext());
      else
             current->getPrevious()->setNext(current->getNext());
      if(current->getNext() == NULL)
             setLast(current->getPrevious());
      else
             current->getNext()->setPrevious(current->getPrevious());
      delete current;
 }

 template<class T>
 void DoublyLinkedList<T>::displayForward()
 {
      std::cout<<"List (first-->last): ";
      Link<T> *current = getFirst();
      while(current != NULL)
      {
         current->displayLink();
         current = current->getNext();
      }
      std::cout<<"\n";
 }

 template<class T>
 void DoublyLinkedList<T>::displayBackward()
 {
      std::cout<<"List (last-->first): ";
      Link<T> *current = getLast();
      while(current != NULL)
      {
         current->displayLink();
         current = current->getPrevious();
      }
      std::cout<<"\n";
 }

template <class T>
Link<T> *DoublyLinkedList<T>::headdel()
{
        Link<T> *temp = getFirst();
        if(!isEmpty())
        {
           if(getFirst()->getNext() == NULL)
               setLast(NULL);
           else
               getFirst()->getNext()->setPrevious(NULL);
           setFirst(getFirst()->getNext());
        }
        return temp;
}

template <class T>
void DoublyLinkedList<T>::tailins(Link<T> *p)
{
     p->setNext(NULL);
     if(isEmpty())
     {
         p->setPrevious(NULL);
         setFirst(p);
     }
     else
     {
         getLast()->setNext(p);
         p->setPrevious(getLast());
     }
     setLast(p);
}

template <class T>
bool DoublyLinkedList<T>::Split(DoublyLinkedList<T> &A,DoublyLinkedList<T> &B,int (*Compare)(T,T))
{
     bool isEmptyB,swapLists;
     Link<T> *currNode = NULL;
     Link<T> *prevNode = NULL;
     isEmptyB = true;
     swapLists = true;
     if(!isEmpty())
     {
         currNode = headdel();
         A.tailins(currNode);
         prevNode = currNode;
     }
     while(!isEmpty())
     {
         currNode = headdel();
         if(Compare(prevNode->getData(),currNode->getData()) > 0)
            swapLists = !swapLists;
         if(swapLists)
           A.tailins(currNode);
         else
         {
             B.tailins(currNode);
             isEmptyB = false;
         }
         prevNode = currNode;
     }
     return isEmptyB;
}

template <class T>
void DoublyLinkedList<T>::Merge(DoublyLinkedList<T> &A,DoublyLinkedList<T> &B,int (*Compare)(T,T))
{
     Link<T> *tmpA = NULL;
     Link<T> *tmpB = NULL;
     Link<T> *poprzedniZtmpA = NULL;
     Link<T> *poprzedniZtmpB = NULL;
     bool koniecSeriiWtmpA, koniecSeriiWtmpB;
     if(!A.isEmpty())
     {
         tmpA = A.headdel();
     }
     if(!B.isEmpty())
     {
         tmpB = B.headdel();
     }
     koniecSeriiWtmpA = (tmpA == NULL);
     koniecSeriiWtmpB = (tmpB == NULL);
     while(tmpA != NULL || tmpB != NULL)
     {
         while(!koniecSeriiWtmpA && !koniecSeriiWtmpB)
            if(Compare(tmpA->getData(),tmpB->getData()) <= 0)
            {
                tailins(tmpA);
                poprzedniZtmpA = tmpA;
                tmpA = A.headdel();
                if(tmpA == NULL || Compare(poprzedniZtmpA->getData(),tmpA->getData()) > 0)
                     koniecSeriiWtmpA = true;
            }
            else
            {
                tailins(tmpB);
                poprzedniZtmpB = tmpB;
                tmpB = B.headdel();
                if(tmpB == NULL || Compare(poprzedniZtmpB->getData(),tmpB->getData()) > 0)
                     koniecSeriiWtmpB = true;
            }
          while(!koniecSeriiWtmpA)
          {
               tailins(tmpA);
               poprzedniZtmpA = tmpA;
               tmpA = A.headdel();
               if(tmpA == NULL || Compare(poprzedniZtmpA->getData(),tmpA->getData()) > 0)
                    koniecSeriiWtmpA = true;
          }
          while(!koniecSeriiWtmpB)
          {
                tailins(tmpB);
                poprzedniZtmpB = tmpB;
                tmpB = B.headdel();
                if(tmpB == NULL || Compare(poprzedniZtmpB->getData(),tmpB->getData()) > 0)
                     koniecSeriiWtmpB = true;
          }
          koniecSeriiWtmpA = (tmpA == NULL);
          koniecSeriiWtmpB = (tmpB == NULL);
          poprzedniZtmpA = NULL;
          poprzedniZtmpB = NULL;
     }
}

template <class T>
void DoublyLinkedList<T>::MergeSort(int (*Compare)(T,T))
{
     bool isEmptyB = false;
     DoublyLinkedList<T> L1,L2;
     while(!isEmptyB)
     {
         isEmptyB = Split(L1,L2,Compare);
         if(!isEmptyB)
            Merge(L1,L2,Compare);
     }
     setFirst(L1.getFirst());
     setLast(L1.getLast());
}