#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;
}