/*COP 3502C Midterm Assignment Two
This program is written by: Ariana Muresan*/

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

typedef struct soldier{

struct soldier* next;
struct soldier* previous;

int data;
    int num;

}soldier;


int count = 0;


soldier *head, *lastnode;

soldier* create_soldier(int sequence);
soldier* create_reverse_circle(int n);
soldier* rearrange_circle(soldier* head);
void display(soldier* head);
int kill(soldier* head, int n, int k);


soldier* create_soldier(int sequence) {

struct soldier* ptr, *temp;

ptr=(struct soldier*)malloc(sizeof(soldier));

if(ptr == NULL) {

return NULL;

}

else {

}

}

/////////////////////////////////////////////////////////////////////////////////////////

soldier* create_reverse_circle(int n) {

for(int i = 1; i <= n; i++) {

head->next = create_soldier(i);

}

return head;

}

/////////////////////////////////////////////////////////////////////////////////////////

soldier* rearrange_circle(soldier* head) { //done?

    struct soldier *Rhead, *next2, *t;

	t = head -> next;
	Rhead = head;
	Rhead -> next = Rhead;
	Rhead -> previous = Rhead;

    while (t != head)
{
	next2 = t -> next;
	t -> next = Rhead;
	t -> previous = Rhead -> previous;
	Rhead -> previous -> next = t;
	Rhead -> previous = t;
	Rhead = t;

	t = next2;
}
return Rhead;

}


/////////////////////////////////////////////////////////////////////////////////////////

void display(soldier* head) { //done?

soldier* s;

s = head;


if(head == NULL) {

return;

}

while(s->next != head) {

printf("%d", s->data);

s = s->next;

    }
}
/////////////////////////////////////////////////////////////////////////////////////////

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

    struct soldier *Rhead, *t;

	int counter = 0;

    if(n == 1)
	return head -> num;

	t = head;

	for (counter = 0; counter < k-1; counter++)
	{
		t = t -> next;
	}
	Rhead = t -> next;
	t -> next -> previous = t -> previous;
	t -> previous -> next = t -> next;

	n--;

	printf("%d", t -> num);
	if (n != 1)

	return kill(Rhead, n, k);
}


/////////////////////////////////////////////////////////////////////////////////////////

int main() {
	struct soldier *circle;
	int safe;
	int skip;
	int amtofsoldiers;
    int n, k;

	printf("Input: \n");
	scanf("%d %d", &n, &k);
	circle = create_reverse_circle(amtofsoldiers);

	printf("List: ");
	display(circle);
	circle = rearrange_circle(circle);

	printf("After ordering: ");
	display(circle);

    safe = kill (circle, amtofsoldiers, skip);
	printf("\n\nSurvived: %d\n\n", safe);

	return 0;
}