/* 9. Write a C++ program to create a class DLIST (Doubly Linked List) with member functions, insert at a specified position, and delete from a specified position. Demonstrate the implementation by displaying the status and content of the list after every operation. */

#include<iostream.h>
#include<conio.h>
#include<stdlib.h>
struct node 
{
    int info;
    struct node *next,*back;
};
typedef struct node *dlist;
class LIST 
{
    dlist start;

    public:
        LIST()
        {
            start = NULL;
        }    
        void InsPos();
        void DelPos();
        void Display();
};
void LIST::Display()
{
    dlist temp,prev;
    if (start == NULL)
        cout<<"\nList is empty";
    else
    {
        temp = start;
        cout<<"\nThe Doubly linked list content is :\nFORWARD\nROOT ->";
        while (temp != NULL)
        {
            cout<<temp->info<<" -> ";
            prev = temp;
            temp = temp->next;
        }
        cout<<"NULL";
        temp = prev;
        cout<<"\n\nBACKWARD\nNULL";
        while (temp != NULL)
        {
            cout<<" <- "<<temp->info;
            temp = temp->back;
        }
        cout<<" <- ROOT";
    }
}
void LIST::InsPos()
{
    int pos,item;
    dlist newnode,temp;
    cout<<"\nEnter the item to be inserted into the list : ";
    cin>>item;
    newnode = new node;
    newnode->next = NULL;
    newnode->info = item;
    newnode->back = NULL;
    cout<<"\nEnter the position : ";
    cin>>pos;
    if (start == NULL)
        if ((pos > 1) || (pos < 1))
            cout<<"\nError : Invalid position specified.";
        else
            start = newnode;
    else
    {
        int count=2;
        dlist temp;
        temp = start;
        if (pos == 1)
        {
            newnode->next = start;
            start->back = newnode;
            start = newnode;
            return;    
        }
        while (count < pos)
        {
            temp = temp->next;
            if (temp == NULL)
            {
                cout<<"\n\nItem cannot be inserted at specified position";
                return;
            }
            count++;
        }
        newnode->next = temp->next;
        temp->next = newnode;
        newnode->back = temp;
        if (newnode->next != NULL)
            newnode->next->back = newnode;
    }
}
void LIST::DelPos()
{
    int item,count=2,pos;
    dlist prev,temp;
    if (start == NULL)
        cout<<"\nError : List is empty";
    else
    {
        cout<<"\nEnter the position of the node to be deleted : ";
        cin>>pos;
        temp = start;
        if (pos == 1)
        {
            item = temp->info;
            start = start->next;
            if (start != NULL)
                start->back = NULL;
            cout<<"\nDeleted item is "<<item;
            delete temp;
            return;
        }
        while (count <= pos)
        {
            prev = temp;
            temp = temp->next;
            if (temp == NULL)
            {
                cout<<"\nUnable to delete at %d position"<<pos;
                return;
            }
            count++;
        }        
        prev->next = temp->next;
        if (temp->next != NULL)
            temp->next->back = prev;
        item = temp->info;
        cout<<"\nDeleted item is "<<item;
    }
}
void main()
{
    LIST DLL;
    int ch;
    while(1)
    {
        cout<<"\nMENU\n1. Insert\n2.Delete\n3. Display\n4. Exit\nYour Choice = ? ";
        cin>>ch;
        switch(ch)
        {
            case 1:
                DLL.InsPos();
                break;

            case 2:
                DLL.DelPos();
                break;

            case 3:
                DLL.Display();
                break;

            case 4:
                exit(0);

            default:
                cout<<"\nInvalid choice selection. Try again";
       }
    }
    getch();
}