josephus.cpp

Josephus Problem implementation.

// Josephus.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <iostream>
#include <string>
using namespace std;

class dll
{
	string *name;
	dll *prev,*next;
public:
	string* c_str_()
	{
		return name;
	}
	int append(dll**,string),del(dll**,int),disp(dll*,int);
};
int dll::append(dll** head,string str_name)
{
	dll *temp=(dll*)malloc(sizeof(dll)),*counter=*head;
	if(temp==NULL)
	{
		cout<<"\nNo memory !! Heap exhausted!!"<<endl;
		delete temp;
		exit(-1);
	}
	temp->name=new string();
	temp->name->assign(str_name);
	if(*head==NULL)//start condition
	{
		temp->next=temp->prev=temp;
		*head=temp;
	}
	else
	{
		do
		{
			counter=counter->next;
		}while(counter->next!=*head);
		counter->next=temp;
		temp->next=*head;
		temp->prev=counter;
		(*head)->prev=temp;
	}
	cout<<"\nData Appended!!"<<endl;
	return 0;
}
int dll::del(dll** head,int count)
{
	dll *ctr=*head;
	for(;count;ctr=ctr->next,count--);
	ctr->prev->next=ctr->next;
	ctr->next->prev=ctr->prev;
	cout<<"\nSoldier Eliminated is :"<<*ctr->c_str_()<<endl;
	*head=ctr->next;
	//delete ctr->c_str_();
	free(ctr);
	return 0;
}
inline int dll::disp(dll* head,int switcher)
{
	int no_of_nodes=0;
	dll *counter=head;
	if(switcher)
		cout<<"\n\nSoldiers are :"<<endl;
	do
	{
		if(switcher)
			cout<<*counter->c_str_()<<"  ";
		no_of_nodes++;
		counter=counter->next;
	}while(counter!=head);
	return no_of_nodes;
}
int main()
{
	dll *head=NULL,h;
	cout<<"\nJosephus Problem:"<<endl;
	char choice;
	int count=1,ccount;
	string str_name;
	do
	{
		cout<<"\nEnter the name of soldier "<<count<<" :";
		cin>>str_name;
		h.append(&head,str_name);
		count++;
		cout<<"\n\nDo u want to enter another soldier's name(y/n) :";
		cin>>choice;
	}while(choice=='y' || choice=='Y');
	cout<<"\nNo of soldiers are :"<<h.disp(head,1)<<endl;
	cout<<"\n\nEnter the Circular count :";
	cin>>ccount;
	ccount-=1;
	while(count!=1)
	{
		if(ccount >= count)
				h.del(&head,ccount%count);
		else
			h.del(&head,ccount);

		count=h.disp(head,1);
		cout<<"\nTotal Soldiers in Comp. as of now :"<<count;
	}
	cout<<"\n\n"<<*head->c_str_()<<" is the last soldier standing!!"<<endl<<endl;
	return 0;
}