#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;

struct nod {
   int info;
   struct nod *next;
   struct nod *prev;
}*start, *last;

int count = 0;
class CircularDoubleLinkedList {
   public:
      nod *create_node(int);
      void insert_begin();
      void insert_end();
      void insert_pos();
      void delete_pos();
      void search();
      void update();
      void display();
      void reverse();
      void deleteNum(int);
      CircularDoubleLinkedList() {
         start = NULL;
         last = NULL;
      }
};

int main() {
   int c;
   bool loop = true;
   CircularDoubleLinkedList cdll;
   while (loop) {
      cout<<"1.Insert at Beginning"<<endl;
      cout<<"2.Insert at End"<<endl;
      cout<<"3.Insert at Position"<<endl;
      cout<<"4.Delete at Position"<<endl;
      cout<<"5.Update Node"<<endl;
      cout<<"6.Search Element"<<endl;
      cout<<"7.Display List"<<endl;
      cout<<"8.Reverse List"<<endl;
      cout<<"9.Exit"<<endl;
      cout<<"Enter your choice : ";
      cin>>c;
      switch(c) {
         case 1:
            cdll.insert_begin();
         break;
         case 2:
            cdll.insert_end();
         break;
         case 3:
            cdll.insert_pos();
         break;
         case 4:
            cdll.delete_pos();
         break;
         case 5:
            cdll.update();
         break;
         case 6:
            cdll.search();
         break;
         case 7:
            cdll.display();
         break;
         case 8:
            cdll.reverse();
         break;
         case 9:
            exit(1);
         default:
            cout<<"Wrong choice"<<endl;
      }
   }
   return 0;
}
nod* CircularDoubleLinkedList::create_node(int v) {
   count++;
   struct nod *t;
   t = new(struct nod);
   t->info = v;
   t->next = NULL;
   t->prev = NULL;
   return t;
}
void CircularDoubleLinkedList::insert_begin() {
   int v;
   cout<<endl<<"Enter the element to be inserted: ";
   cin>>v;
   struct nod *t;
   t = create_node(v);
   if (start == last && start == NULL) {
      cout<<"Element inserted in empty list"<<endl;
      start = last = t;
      start->next = last->next = NULL;
      start->prev = last->prev = NULL;
   } else {
      t->next = start;
      start->prev = t;
      start = t;
      start->prev = last;
      last->next = start;
      cout<<"Element inserted"<<endl;
   }
}
void CircularDoubleLinkedList::insert_end() {
   int v;
   cout<<endl<<"Enter the element to be inserted: ";
   cin>>v;
   struct nod *t;
   t = create_node(v);
   if (start == last && start == NULL) {
      cout<<"Element inserted in empty list"<<endl;
      start = last = t;
      start->next= last->next = NULL;
      start->prev = last->prev= NULL;
   } else {
      last->next= t;
      t->prev= last;
      last = t;
      start->prev = last;
      last->next= start;
   }
}
void CircularDoubleLinkedList::insert_pos() {
   int v, pos, i;
   cout<<endl<<"Enter the element to be inserted: ";
   cin>>v;
   cout<<endl<<"Enter the position of element inserted: ";
   cin>>pos;
   struct nod *t, *s, *ptr;
   t = create_node(v);
   if (start == last && start == NULL) {
      if (pos == 1) {
         start = last = t;
         start->next = last->next = NULL;
         start->prev = last->prev = NULL;
      } else {
         cout<<"Position out of range"<<endl;
         count--;
         return;
      }
   } else {
      if (count < pos) {
         cout<<"Position out of range"<<endl;
         count--;
         return;
      }
      s = start;
      for (i = 1;i <= count;i++) {
         ptr = s;
         s = s->next;
         if (i == pos - 1) {
            ptr->next = t;
            t->prev= ptr;
            t->next= s;
            s->prev = t;
            cout<<"Element inserted"<<endl;
            break;
         }
      }
   }
}
void CircularDoubleLinkedList::delete_pos() {
   int pos, i;
   nod *ptr, *s;
   if (start == last && start == NULL) {
      cout<<"List is empty, nothing to delete"<<endl;
      return;
   }
   cout<<endl<<"Enter the position of element to be deleted: ";
   cin>>pos;
   if (count < pos) {
      cout<<"Position out of range"<<endl;
      return;
   }
   s = start;
   if(pos == 1) {
      count--;
      last->next = s->next;
      s->next->prev = last;
      start = s->next;
      free(s);
      cout<<"Element Deleted"<<endl;
      return;
   }
   for (i = 0;i < pos - 1;i++ ) {
      s = s->next;
      ptr = s->prev;
   }
   ptr->next = s->next;
   s->next->prev = ptr;
   if (pos == count) {
      last = ptr;
   }
   count--;
   free(s);
   cout<<"Element Deleted"<<endl;
}
void CircularDoubleLinkedList::update() {
   int v, i, pos;
   if (start == last && start == NULL) {
      cout<<"The List is empty, nothing to update"<<endl;
      return;
   }
   cout<<endl<<"Enter the position of node to be updated: ";
   cin>>pos;
   cout<<"Enter the new value: ";
   cin>>v;
   struct nod *s;
   if (count < pos) {
      cout<<"Position out of range"<<endl;
      return;
   }
   s = start;
   if (pos == 1) {
      s->info = v;
      cout<<"Node Updated"<<endl;
      return;
   }
   for (i=0;i < pos - 1;i++) {
      s = s->next;
   }
   s->info = v;
   cout<<"Node Updated"<<endl;
}
void CircularDoubleLinkedList::search() {
   int pos = 0, v, i;
   bool flag = false;
   struct nod *s;
   if (start == last && start == NULL) {
      cout<<"The List is empty, nothing to search"<<endl;
      return;
   }
   cout<<endl<<"Enter the value to be searched: ";
   cin>>v;
   s = start;
   for (i = 0;i < count;i++) {
      pos++;
      if (s->info == v) {
         cout<<"Element "<<v<<" found at position: "<<pos<<endl;
         flag = true;
      }
      s = s->next;
   }
   if (!flag)
      cout<<"Element not found in the list"<<endl;
}
void CircularDoubleLinkedList::display() {
   int i;
   struct nod *s;
   if (start == last && start == NULL) {
      cout<<"The List is empty, nothing to display"<<endl;
      return;
   }
   s = start;
   for (i = 0;i < count-1;i++) {
      cout<<s->info<<"<->";
      s = s->next;
   }
   cout<<s->info<<endl;
}
void CircularDoubleLinkedList::reverse() {
   if (start == last && start == NULL) {
      cout<<"The List is empty, nothing to reverse"<<endl;
      return;
   }
   struct nod *p1, *p2;
   p1 = start;
   p2 = p1->next;
   p1->next = NULL;
   p1->prev= p2;
   while (p2 != start) {
      p2->prev = p2->next;
      p2->next = p1;
      p1 = p2;
      p2 = p2->prev;
   }
   last = start;
   start = p1;
   cout<<"List Reversed"<<endl;
}