#include "apstring.h"
#include <iostream.h>
#include <ctype.h>

// initialize the node
struct node;
typedef node *nodeptr;
struct node
{
int coeff;
nodeptr next;
};

// function prototypes
void getcoeff(nodeptr &first);
void print(nodeptr first);
nodeptr add_sub(nodeptr first, nodeptr second, char ch);
int lenlist(nodeptr first);
void suicide(int n, int m, nodeptr c);
nodeptr circle (int n);

int main()
{
// vars
nodeptr first=new node, second=new node;
int a, N, M;
char ch;

// start polynomial program
getcoeff(first);
do
{
cout << "+ or -?\n";
cin >> ch;
getcoeff(second);
cout << " ";
print(first);
cout << endl << ch;
print(second);
cout << "\n--------------------------\n";
// set the first l.l. as the resultant l.l.
first = add_sub(first, second, ch);
print (first);
cout << "\n\nDo you wish to enter more polynomials?\n"
<< "Enter nonzero integer to continue\n";
cin >> a;
if (a !=0)
{
cout << "\n(C)ontinue adding and subtracting from before?\n"
<< "Or (s)tart over?\n";
cin >> ch;
// if start over, then reset the first ll
// otherwise, the ll representing the result of the first two
// will be the first ll in the next operation
if(toupper(ch)== 'S')
getcoeff(first);
}
// if a is not zero, then the input will continue
}
while(a != 0);

// start josephus program
do
{
cout <<"This is the Mass Suicide Program to help you commit mass suicide.\n"
<< "Please input the number of people who wish to commit suicide.\n";
cin >> N;
cout << "Please input the Mth number person who will kill
somebody.\n";
cin >> M;
first = circle(N);
suicide(N,M, first);
cout << "Try again? Nonzero integer continues.\n";
cin >> a;
}
while(a!=0);
return a;
}

//gets the coefficients into ll form
void getcoeff(nodeptr &first)
{
int a;
nodeptr ref=first, second=new node;
do
{
// input
cout << "Input the next coefficient of a polynomial.\n(-99999 to
quit)\n";
cin >> a;
// save next coefficient
ref -> coeff = a;
ref = ref->next;
}
while(a != -99999);
}

// returns the integer length of the ll
int lenlist(nodeptr first)
{
int cnt=0;
nodeptr ref=first;
// find the length
while (ref->coeff != NULL)
{
cnt++;
ref = ref -> next;
}
return cnt;
}

// prints the ll in form of a polynomial
void print(nodeptr first)
{
int len,j;
nodeptr ref=first;
len = lenlist(first);
for(j=len-1; j >= 0; j--)
{
// ax^2 + bx + c format of printout
if(j !=0)
cout << first->coeff << "x^" << j << " + ";
else
cout << first->coeff;
first = first -> next;
}
}

// returns the ll of coefficients after performing desired operation
nodeptr add_sub(nodeptr first, nodeptr second, char ch)
{
nodeptr f=first, s=second, sum=new node;
bool larger;
int flen, slen, j, cnt;
char c=ch;

flen = lenlist(f);
slen = lenlist(s);
// compare the lengths of the lls
larger = flen > slen;
if (larger)
cnt = flen;
else
cnt = slen;
// chose whether to add or subtract
if(c == '+')
{
for(j = cnt; j > 0; j--)
{
if ((s->coeff != NULL) && (f->coeff != NULL))
{
sum -> coeff = s -> coeff + f -> coeff;
s = s -> next;
f = f -> next;
}
else if (s->coeff == NULL)
{
sum -> coeff = f -> coeff;
f = f -> next;
}
else if (f->coeff == NULL)
{
sum -> coeff = s -> coeff;
s = s -> next;
}
sum=sum->next;
}

}
else if (c == '-')
{
for(j = cnt; j > 0; j--)
{
if ((s->coeff != NULL) && (f->coeff != NULL))
{
sum -> coeff = f -> coeff - s -> coeff;
s = s -> next;
f = f -> next;
}
else if (s->coeff == NULL)
{
sum -> coeff = f -> coeff;
f = f -> next;
}
else if (f->coeff == NULL)
{
sum -> coeff = 0 - s -> coeff;
s = s -> next;
}
sum=sum->next;
}
}
else
{
cout << "Wrong input! Try again!\n";
add_sub (f, s, c);
}
return sum;
}

nodeptr circle(int n)
{
int j;
nodeptr root, prev, first;
for(j=1; j<=n; j++)
{
root = new node;
root->coeff=j;
if(j==1)
first = root;
else
prev -> next = root;
prev = root;

}
root->next = first;
return first;
}

void suicide(int n, int m, nodeptr c)
{
nodeptr circle=c;
int j;
for(j=1; j<=m; j++)
{
// check if list is empty, if it is, exit loop
if (circle == NULL)
j = m;
// has reached the mth person, so check if circle is empty,
// then print out the mth person to die, remove person from
// list
else if (j==m)
{
cout << j << ", ";
remove(j, circle); // remove j from circle
}
// if the next node is not empty, move on to it
if (circle->next !=NULL)
circle = circle->next;
}
}