/* 10. Write a C++ program to create a class LIST (linked list), with add and subtract member functions to add and subtract two long integers of atleast 12 digits. Demonstrate the implementation by displaying the status and content of the list after every operation. (The number of digits to be held in each node can be decided by the student himself/herself.) */

#include<iostream.h>
#include<stdlib.h>
#include<conio.h>
struct node
{
    int info;
    struct node *next;
};
typedef struct node clist;
clist *last = NULL;
class LLIST
{
    public:
        clist* ccreate(clist *start);
        void insert(clist **s, int x);
        clist* add(clist *p, clist *q);
        void LLIST::cdisplay(clist **start);
};

/* FUNCTION TO CREATE A CIRCULAR LINKED LIST */
clist* LLIST::ccreate(clist *start)
{
    clist *temp, *head; /* head IS A HEADER NODE WHICH CONTAINS 0 DATA */
    int item;
    start = NULL;
    head = new node;
    head->info = 0;
    head->next = head;
    cout<<"\nEnter a digit or -999 to stop : ";
    cin>>item;
    while (item != -999)
    {    
        temp = new node;
        temp->info = item;
        if (start == NULL)
        {
            temp->next = head;
            head->next = temp;
            start = temp;
        }
        else
        {
            temp->next = head;
            start->next = temp;
            start = temp;
        }
        cout<<"\nEnter a digit or -999 to stop : ";
        cin>>item;
    }
    return head;
}
/* FUNCTION TO INSERT THE ADDED DIGIT TO THE FINAL LIST */
void LLIST::insert(clist **s, int x)
{
    clist *t;
    t = new node;
    t->info = x;
    t->next = (*s)->next;
    (*s)->next = t;
}
/* FUNCTION TO ADD DIGITS OF GIVEN TWO NUMBERS */
clist* LLIST::add(clist *p, clist *q)
{
    int cr=0, num=0, sum=0;
    clist *s, *x, *y;
    x = p;
    y = q;
    s = new node;
    s->info = 0;
    s->next = s;
    p = p->next;
    q = q->next;
    while ((p != x) || (q != y))
    { /* ADD TILL BOTH NUMBERS HAVE SAME DIGITS*/
        if ((p != x) && (q != y))
        {
            sum = p->info + q->info + cr;
            num = sum % 10;
            cr = sum / 10;
            insert(&s, num);
            s = s->next;
            p = p->next;
            q = q->next;
        }
        else if (p != x) /* IF FIRST NUMBER IS BIGGER THAN SECOND */
        {
            insert(&s,(p->info + cr));
            cr = 0;
            s = s->next;
            p = p->next;
        }
        else if (q != y) /* IF SECOND NUMBER IS BIGGER THAN FIRST */
        {
            insert(&s,(q->info + cr));
            cr = 0;
            s = s->next;
            q = q->next;
        }
    }
    if (cr == 1)
    {
        insert(&s, cr);
        s = s->next;
    }
    p = x; /* RESAVE THE STARTING ADDRESSES */
    q = y;
    return s->next;
}
/* FUNCTION TO DISPLAY THE CONTENT OF A LIST */
void LLIST::cdisplay(clist **start)
{
    clist *temp;
    int a[30], i=0;
    if (*start == NULL)
        cout<<"\nList is empty";
    else
    {
        temp = (*start)->next;
        do {
                a[i++] = temp->info;
                temp = temp->next;
             } while (temp != (*start));
        for (i=i-1; i>=0; i--)
            cout<<a[i];
    }
}
/* MAIN PROGRAM */
void main()
{
    LLIST x;
    clist *s, *s1, *s2, *s3;
    clrscr();
    cout<<"\nEnter the first number one digit at a time :\n";
    s1 = x.ccreate(s);
    cout<<"\nThe content of the first number is :\n";
    x.cdisplay(&s1);
    cout<<"\nEnter the second number one digit at a time :\n";
    s2 = x.ccreate(s);
    cout<<"\nThe content of the second number is :\n";
    x.cdisplay(&s2);
    s3 = x.add(s1, s2);
    cout<<"\nThe content of added number is : \n";
    x.cdisplay(&s3);
    getch();
}