struct Polynomial

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

#define ZERO  1e-10

struct Polynomial {
    int deg;
    double* coeff;
};

void findDeg(struct Polynomial* p) {
    for (int i = p->deg; i >= 0; i--) {
        if (fabs(p->coeff[i]) > ZERO) {
            p->deg = i;
            return ;
        }
    }
    p->deg = 0;
}


struct Polynomial* addPolynomials(struct Polynomial* a, struct Polynomial* b) {
    int newDeg = a->deg > b->deg ? a->deg : b->deg;
    struct Polynomial* n = malloc(sizeof(*n));
    n->coeff = malloc((newDeg + 1) * sizeof(*n->coeff));

    for (int i = newDeg - abs(a->deg - b->deg); i >= 0; i--) {
         n->coeff[i] = a->coeff[i] + b->coeff[i];
    }

    if (a->deg > b->deg) {
        for (int i = a->deg; i > a->deg - abs(a->deg - b->deg); i--) {
            n->coeff[i] = a->coeff[i];
        }
    } else {
        for (int i = b->deg; i > b->deg - abs(a->deg - b->deg); i--) {
            n->coeff[i] = b->coeff[i];
        }
    }

    for (int i = newDeg; i >= 0; i--) {
        if (n->coeff[i] != 0.0) {
              n->deg = i;
              return n;
        }
    }
    n->deg = 0;
    return n;
}

struct Polynomial* substractPolynomials(struct Polynomial* a, struct Polynomial* b) {
    int newDeg = a->deg > b->deg ? a->deg : b->deg;
    struct Polynomial* n = malloc(sizeof(*n));
    n->coeff = malloc((newDeg + 1) * sizeof(*n->coeff));

    for (int i = newDeg - abs(a->deg - b->deg); i >= 0; i--) {
         n->coeff[i] = a->coeff[i] - b->coeff[i];
    }

    if (a->deg > b->deg) {
        for (int i = a->deg; i > a->deg - abs(a->deg - b->deg); i--) {
            n->coeff[i] = a->coeff[i];
        }
    } else {
        for (int i = b->deg; i > b->deg - abs(a->deg - b->deg); i--) {
            n->coeff[i] = -b->coeff[i];
        }
    }

    for (int i = newDeg; i >= 0; i--) {
        if (n->coeff[i] != 0.0) {
              n->deg = i;
              return n;
        }
    }
    n->deg = 0;
    return n;
}

struct Polynomial* multiplyPolynomials(struct Polynomial* a, struct Polynomial* b) {
    struct Polynomial* n = malloc(sizeof(*n));
    n->deg = a->deg + b->deg;
    n->coeff = calloc((a->deg + b->deg + 1), sizeof(*n->coeff));

    for (int i = 0; i < a->deg + 1; i++) {
        for (int j = 0; j < b->deg + 1; j++) {
            n->coeff[i + j] += a->coeff[i] * b->coeff[j];
        }
    }

    return n;
}

struct Polynomial* dividePolynomials(struct Polynomial* a, struct Polynomial* b, struct Polynomial* r) {
    struct Polynomial* q = malloc(sizeof(*q));
    if (a->deg < b->deg)
    {
        q->deg = 0;
        q->coeff = malloc((q->deg + 1) * sizeof(*q->coeff));
        q->coeff[0] = 0.0;
        r->deg = a->deg;
        for(int i=r->deg;i>=0;i--)
           r->coeff[i] = a->coeff[i];
        return q;
    }
    struct Polynomial* temp = malloc(sizeof(*temp));

    temp->coeff = malloc((a->deg + 1) * sizeof(*temp->coeff));
    temp->deg = a->deg;

    q->coeff = malloc((a->deg + 1) * sizeof(*q->coeff));
    q->deg = a->deg;

    for (int i = 0; i < a->deg + 1; i++) {
        temp->coeff[i] = a->coeff[i];
        q->coeff[i] = 0.0;
    }

    for (int i = a->deg - b->deg; i >= 0; i--) {
        q->coeff[i] = temp->coeff[b->deg + i] / b->coeff[b->deg];
        for (int j = b->deg + i - 1; j >= i; j--) {
            temp->coeff[j] -= q->coeff[i] * b->coeff[j - i];
        }
    }

    for (int i = 0; i < b->deg; i++) {
        r->coeff[i] = temp->coeff[i];
    }

    if (r->deg < a->deg) {
        for (int i = b->deg; i < r->deg + 1; i++) {
            r->coeff[i] = 0.0;
        }
    } else {
        for (int i = b->deg; i < a->deg + 1; i++) {
            r->coeff[i] = 0.0;
        }
    }

    free(temp->coeff);
    free(temp);

    findDeg(r);
    findDeg(q);

    return q;
}


struct Polynomial *GCD(struct Polynomial* a, struct Polynomial* b)
{
       struct Polynomial * temp = malloc(sizeof(*temp));
       while(b->deg != 0 || fabs(b->coeff[0]) > ZERO)  // Negujemy warunek b->deg == 0 && b->coeff[0] == 0.0 korzystajac z prawa De Morgana
       {
             temp->deg = a->deg;
             temp->coeff = malloc((temp->deg+1)*sizeof(*temp->coeff));
             for(int i=0;i <= a->deg;i++)
             {
                 temp->coeff[i] = a->coeff[i];
             }
             free(a->coeff);
             a->deg = b->deg;
             a->coeff = malloc((a->deg+1)*sizeof(*a->coeff));
             for(int i = 0;i <= a->deg;i++)
             {
                   a->coeff[i] = b->coeff[i];
             }
             dividePolynomials(temp,b,b);
             free(temp->coeff);
       }
       findDeg(a);
       free(temp);
       return a;
}


void printPolynomial(struct Polynomial* c) {
    int s=0;
    for (int i = c->deg; i >= 0; i--) {
        if (c->coeff[i] < 0.0) {
            printf(" -%lfx^%d ", -c->coeff[i], i);
            s = 1;
        } else if (c->coeff[i] > 0.0) {
            s = 1;
            printf(" +%lfx^%d ", c->coeff[i], i);
        }
    }
    if(s == 0)
         printf("%lfx^%d ",c->coeff[0],0);
    printf("\n");
}

int main(int argc, char** argv) {
    struct Polynomial* a = malloc(sizeof(*a));
    struct Polynomial* b = malloc(sizeof(*b));
    struct Polynomial* c = malloc(sizeof(*c));
    struct Polynomial* r = malloc(sizeof(*r));
    printf("Podaj stopien wielomianu a\n");
    scanf("%d",&a->deg);
    r->deg = a->deg;
    r->coeff = malloc((a->deg + 1) * sizeof(*r->coeff));
    a->coeff = malloc((a->deg + 1) * sizeof(*a->coeff));

    printf("Podaj stopien wielomianu b\n");
    scanf("%d",&b->deg);
    b->coeff = malloc((b->deg + 1) * sizeof(*b->coeff));


    for(int i=a->deg;i>=0;i--)
    {
        printf("a[%d]=",i);
        scanf("%lf",&a->coeff[i]);
    }

    for(int i=b->deg;i>=0;i--)
    {
        printf("b[%d]=",i);
        scanf("%lf",&b->coeff[i]);
    }


    //c = dividePolynomials(a, b, b);
    c = GCD(a, b);

    //printf("\n%d\n", c->deg);

    printPolynomial(c);
    printf("\n");
   // printPolynomial(b);
    //for (int i = 0; i < b->deg; i++) printf("%lf", b->coeff[i]);
    printf("\n%d", c->deg);
    printf("\n%d", b->deg);

    system("PAUSE");
}