#include<stdio.h>
#include<stdlib.h>

typedef struct soldier
{
    int data;
    struct soldier *prev, *next;
} soldier;

soldier *start, *last;

int DelListDoubly(int item);
soldier* create_soldier(int sequence);
soldier* create_reverse_circle(int n);
soldier* rearrange_circle(soldier *head);

soldier* create_soldier(int sequence){
    soldier *temp;
    temp=(soldier *) malloc(sizeof(soldier));
    temp->data = sequence;
    return temp;
}

soldier* create_reverse_circle(int n){
    soldier *head;
    soldier *tmp;
    for(int i=0;n>i;n--){
        if(start==NULL){
            head = create_soldier(n);
            head->next = head->prev = head;
            start=head;
            tmp=head;
        }
        else{
            tmp->next=create_soldier(n);
            tmp = tmp->next;
            tmp->next = head;
        }
    }
    start = head;
    last = tmp;
    head->prev=tmp;
    return head;
}

soldier* rearrange_circle(soldier *head){
    soldier *curr, *next, *tmp, *newStart, *newLast;
    newLast = start;
    newStart = last;
    curr = head;
    do
    {
        printf("%d", curr->data);
        next = curr->next;
        tmp = curr->prev;
        curr->prev = curr->next;
        curr->next = tmp;
        curr = next;
    } while(curr != head);
    display(curr);
    last = newLast;
    start = newStart;
    return curr;
}

void display(soldier* head){
    if(head==NULL){
        printf("No Input\n");
        return;
    }
    printf("List = ");
    printf("%d ", head->data);
    while(head->next!=start){
        head = head->next;
        printf("%d ", head->data);
    }
    printf("\n");
}

int kill(soldier* head, int n, int k){

}

int main()
{
	start=NULL;
	soldier *mainList;
	int ch,ele,v;
	while(1)
	{
		printf("Menu: 1\nExit: 2\n: ");
	    scanf("%d",&ch);
		if(ch==2)
		{
			printf("\nGOOD BYE.\n");
			break;
		}
        if(ch==1)
		{
		    printf("\nEnter information(an integer): ");
			scanf("%d",&ele);
            mainList = create_reverse_circle(ele);
		    display(mainList);
		    mainList = rearrange_circle(mainList);
            display(mainList);
			break;
		}

		/*
		if(ch==1)
		{
			printf("\nEnter information(an integer): ");
			scanf("%d",&ele);
			insert_front(ele);
			printf("\nPrinting ur link list.......");
			t=root;
			while(t!=NULL)
			{
				printf("%d ",t->data);
				t=t->next;
			}
		}
		if(ch==2)
		{
			printf("\nEnter information(an integer): ");
			scanf("%d",&ele);
			insert_end(ele);
			printf("\nPrinting your link list.......");
			t=root;
			while(t!=NULL)
			{
				printf("%d ",t->data);
				t=t->next;
			}
		}
	   if(ch==3)
	   {
		 printf("\nEnter info which u want to DELETE: ");
		 scanf("%d",&ele);
		 v=DelListDoubly(ele);
		 if(v==1)
		 {
			printf("\nDeleting....");
			t=root;
			while(t!=NULL)
			{
				printf("%d ",t->data);
				t=t->next;
			}
		 }
		  else if(v==0)
			printf("\nThat info does not exist in the list");


	   }
	   */
	}
	return 0;
}

int DelListDoubly(int item)
{
	soldier *t;
	soldier *temp;
	if(start==NULL)
		return 0;
	if(temp->data==item)
	{
		temp=start;
		start=temp->next;
		if (start != NULL) //new condition for doubly
            temp -> prev = NULL;
		free(temp);
		return 1;
	}
	t=start;
	while(t->next!=NULL && t->next->data != item)
		t=t->next;
	if(t->next==NULL)
		return 0;
	temp=t->next;
	t->next=t->next->next;
    if (t->next)               //new condition for doubly
       t->next->prev = t;

	free(temp);
	return 1;
}