// C++ Program to Solve Josephus Problem using Linked List 
#include <iostream>
#include <fstream>
#include <string>
#include <cstdlib>
using namespace std;

struct node
{
    string name;
    node*  next;
};
typedef node* nptr;

void create(nptr& tail, int& number);
void display(nptr head);
string survivor(nptr tail, int skip);

int main()
{
    nptr head;
    int skip, number;
    string survive;

    create(head, number);
    cout << "The " << number << " persons in the circular list are:" << endl;
    display(head);

    cout << "Enter the number of persons to be skipped: ";
    cin >> skip;

    survive = survivor(head, skip);
    cout << "The winner is : " << survive << endl;

    return 0;
}

string survivor(nptr tail, int skip)
{
    nptr tag, prev;
    prev = tail;
    tag = tail->next;
    while (tag->next != tag)
    {
        for (int i = 1; i < skip; i++)
        {
            prev = tag;
            tag = tag->next;
        }
        cout << tag->name << " has been eliminated." << endl;
        system("sleep 1");
        prev->next = tag->next;
        delete tag;
        tag = prev->next;
    }
    return tag->name;
}

void create(nptr& tail, int& number)
{
    nptr head = nullptr;
    ifstream input;
    input.open("names.dat");
    string name;
    nptr curr = nullptr, prev = nullptr;

    head = tail = nullptr;
    number = 0;

    input >> name;
    if (input)
    {
        head = tail = new node;
        number++;
        head->name = name;
        head->next = head;
        prev = head;
        input >> name;
        while (input)
        {
            curr = new node;
            number++;
            curr->name = name;
            curr->next = head;
            prev->next = curr;
            prev = curr;
            input >> name;
        }
        tail = prev;
    }
    input.close();
}

void display(nptr head)
{
    int serial = 0;
    if (head == nullptr)
        return;
    nptr curr = head;
    do
    {
        cout << ++serial << " " << curr->name << endl;
        curr = curr->next;
    } while (curr != head);
    cout << endl;
}