#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
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;
}
template<class T>
class DoublyLinkedList
{
private:
Link<T> *first;
Link<T> *last;
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();
void BSTinsert(Link<T> *&root,Link<T> *z);
void BSTtoDLL(Link<T> *root,DoublyLinkedList<T> &L);
void BSTSort();
};
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>
void DoublyLinkedList<T>::BSTinsert(Link<T> *&root,Link<T> *z)
{
Link<T> *y = NULL;
Link<T> *x = root;
while(x != NULL)
{
y = x;
if(z->getData() < x->getData())
x = x->getPrevious();
else
x = x->getNext();
}
if(y == NULL)
root = z;
else if(z->getData() < y->getData())
y->setPrevious(z);
else
y->setNext(z);
}
template<class T>
void DoublyLinkedList<T>::BSTtoDLL(Link<T> *root,DoublyLinkedList<T> &L)
{
if(root != NULL)
{
BSTtoDLL(root->getPrevious(),L);
if(L.isEmpty())
L.setFirst(root);
else
L.getLast()->setNext(root);
root->setPrevious(L.getLast());
L.setLast(root);
BSTtoDLL(root->getNext(),L);
}
}
template<class T>
void DoublyLinkedList<T>::BSTSort()
{
Link<T> *temp;
Link<T> *root = NULL;
while(!isEmpty())
{
temp = getFirst();
if(getFirst()->getNext() == NULL)
setLast(NULL);
else
getFirst()->getNext()->setPrevious(NULL);
setFirst(getFirst()->getNext());
temp->setPrevious(NULL);
temp->setNext(NULL);
BSTinsert(root,temp);
}
BSTtoDLL(root,*this);
}
int main(int argc, char *argv[])
{
DoublyLinkedList<int> A;
int k,n,m;
srand(time(NULL));
cin>>n>>m;
for(k = 0;k < n;k++)
A.insertLast(rand()%m);
A.displayForward();
A.displayBackward();
A.BSTSort();
A.displayForward();
A.displayBackward();
while(!A.isEmpty())
A.deleteFirst();
return EXIT_SUCCESS;
}