static long int lcm(long int a, long int b);
static int getmax(token_num* token_info, int n);

static poly polycut(poly poly_old,long int time_start,long int time_end)
{
    poly result;
    int poly_num,index=0;
    poly_num = poly_old.getn();
    while(poly_old.getdata()[index].getd()<=time_start) index++;
    while(poly_old.getdata()[index].getd()<=time_end && index<poly_num)
        result = oplus(result,poly_old.getdata()[index++]);
    return result;
}

static poly serie2poly(serie serie_old, long int time_start, long int time_end)
{
    poly temp,temp_add,result,serie_p,serie_q;
    gd serie_r;
    int index,gd_p_num,gd_q_num,gd_t_num;
    if(time_start>=time_end)
        return result;
    serie_p = serie_old.getp();
    serie_q = serie_old.getq();
    serie_r = serie_old.getr();
    gd_p_num = serie_p.getn();
    gd_q_num = serie_q.getn();
    temp = oplus(serie_p,serie_q);
    temp_add = serie_q;
    index = 0;
    while(true)
    {
        gd_t_num = temp.getn();
        for(;index<gd_t_num;index++)
            if(temp.getdata()[index].getd()>time_start) break;
        if(index == gd_t_num)
        {
            if(serie_r.getd()!=0)
            {
                temp_add = otimes(temp_add,serie_r);
                std::cout<<"fff:"<<temp_add<<std::endl;
                temp = oplus(temp,temp_add);
            }
            else return result;
        }
        else break;
    }
    while(true)
    {
        gd_t_num = temp.getn();
        for(;index<gd_t_num;index++)
            if(temp.getdata()[index].getd()>time_end) break;
            else
                result = oplus(result,temp.getdata()[index]);
        if(index == gd_t_num)
        {
            if(serie_r.getd()!=0)
            {
                temp_add = otimes(temp_add,serie_r);
                temp = oplus(temp,temp_add);
            }
            else break;
        }
        else break;
    }
    temp.init(result.getdata()[result.getn()-1].getg(),infinity);
    result = oplus(result,temp);
    return result;
}

serie fracodotflat(serie serie_a,serie serie_b)
{
    float niu_a,niu_b;
    poly a_p,a_q,b_p,b_q,result_p,result_q,poly1,poly2;
    serie result,temp_serie;
    gd a_r,b_r,result_r;
    long int period_lcm,period_start_time;
    a_p = serie_a.getp();
    b_p = serie_b.getp();
    a_q = serie_a.getq();
    b_q = serie_b.getq();
    a_r = serie_a.getr();
    b_r = serie_b.getr();
    if(a_r.getd() != 0)
        niu_a = a_r.getg()/a_r.getd();
    else niu_a = 0;
    if(b_r.getd() != 0)
        niu_b = b_r.getg()/b_r.getd();
    else niu_b = 0;
    if(niu_a == 0 && niu_b == 0)            //if serie a and b are all not periodic
    {
        poly1 = oplus(a_p,a_q);
        poly2 = oplus(b_p,b_q);
        poly1 = fracodotflat(poly1,poly2);
        return poly1;
    }
    if(niu_a < niu_b)
        return result;
    else
    {
        period_lcm = lcm(a_r.getd(),b_r.getd());
        period_start_time = (a_q.getdata()[0].getd()>b_q.getdata()[0].getd())?a_q.getdata()[0].getd():b_q.getdata()[0].getd();
        poly1 = serie2poly(serie_a,-1,period_start_time+period_lcm);
        std::cout<<"poly1: "<<std::endl<<poly1<<std::endl;
        poly1 = serie2poly(serie_b,-1,period_start_time+period_lcm);
        std::cout<<"poly1: "<<std::endl<<poly1<<std::endl;
        poly1 = fracodotflat(serie2poly(serie_a,-1,period_start_time+period_lcm),serie2poly(serie_b,-1,period_start_time+period_lcm));
        std::cout<<"result1: "<<std::endl<<poly1<<std::endl;
        temp_serie.init(epsilon,poly1,e);
        result_p = serie2poly(temp_serie,-1,period_start_time);
        poly1 = fracodotflat(serie2poly(serie_a,period_start_time,period_start_time+2*period_lcm),serie2poly(serie_b,period_start_time,period_start_time+2*period_lcm));
        std::cout<<"poly1: "<<std::endl<<poly1<<std::endl;
        temp_serie.init(epsilon,poly1,e);
        result_q = serie2poly(temp_serie,period_start_time,period_start_time+period_lcm);
        result_r.init(a_r.getg()*period_lcm/a_r.getd()-b_r.getg()*period_lcm/b_r.getd(),period_lcm);
        result.init(result_p,result_q,result_r);
        return result;
    }
}

serie fracodotsharp(serie serie_a,serie serie_b)
{
    token_num* token_info;
    int token_length;
    float niu_a,niu_b;
    poly a_p,a_q,b_p,b_q,result_p,result_q,poly1,poly2,temp_result;
    serie result,temp_serie;
    gd a_r,b_r,result_r;
    long int period_lcm,period_start_time;
    int index,max_number,temp;
    poly1 = serie2poly(serie_a,-1,100);
    poly2 = serie2poly(serie_b,-1,100);
    token_info = ominus(poly1,poly2,&token_length);
    print(token_info,token_length);
    a_p = serie_a.getp();
    b_p = serie_b.getp();
    a_q = serie_a.getq();
    b_q = serie_b.getq();
    a_r = serie_a.getr();
    b_r = serie_b.getr();
    if(a_r.getd() != 0)
        niu_a = a_r.getg()/a_r.getd();
    else niu_a = 0;
    if(b_r.getd() != 0)
        niu_b = b_r.getg()/b_r.getd();
    else niu_b = 0;
    if(niu_a == 0 && niu_b == 0)            //if serie a and b are all not periodic
    {
        poly1 = oplus(a_p,a_q);
        poly2 = oplus(b_p,b_q);
        poly1 = fracodotsharp(poly1,poly2);
        return poly1;
    }
    else if(niu_a < niu_b)
    {
        period_start_time = (a_q.getdata()[0].getd()>b_q.getdata()[0].getd())?a_q.getdata()[0].getd():b_q.getdata()[0].getd();
        period_lcm = lcm(a_r.getd(),b_r.getd());
        index = 1;
        while(true)
        {
            poly1 = serie2poly(serie_a,-1,period_start_time+index*period_lcm);
            poly2 = serie2poly(serie_b,-1,period_start_time+index*period_lcm);
            temp_result = fracodotsharp(poly1,poly2);
            if(result_q == temp_result)
            {
                result.init(epsilon,result_q,e);
                return result;
            }
            else
            {
                result_q = temp_result;
                index++;
            }
        }
    }
    else
    {
        period_start_time = (a_q.getdata()[0].getd()>b_q.getdata()[0].getd())?a_q.getdata()[0].getd():b_q.getdata()[0].getd();
        period_lcm = lcm(a_r.getd(),b_r.getd());
        std::cout<<period_start_time<<"::"<<period_lcm<<std::endl;
        poly1 = serie2poly(serie_a,-1,period_start_time + period_lcm);
        poly2 = serie2poly(serie_b,-1,period_start_time + period_lcm);
        token_info = ominus(poly1,poly2,&token_length);
        max_number = getmax(token_info,token_length);
        index = 1;
        while(true)
        {
            poly1 = serie2poly(serie_a,index*period_lcm,(index+1)*period_lcm);
            poly2 = serie2poly(serie_b,index*period_lcm,(index+1)*period_lcm);
            token_info = ominus(poly1,poly2,&token_length);
            index++;
            if(max_number<getmax(token_info,token_length)) break;
        }
        poly1 = serie2poly(serie_a,-1,period_start_time+index*period_lcm);
        poly2 = serie2poly(serie_b,-1,period_start_time+index*period_lcm);
        poly1 = fracodotsharp(poly1,poly2);
        std::cout<<"poly1: "<<std::endl<<poly1<<std::endl;
        result_q = polycut(poly1,(index-1)*period_lcm,index*period_lcm);
        std::cout<<"result_q: "<<std::endl<<result_q<<std::endl;
        result_p = polycut(poly1,-1,period_start_time+(index-1)*period_lcm);
        std::cout<<"result_p: "<<std::endl<<result_p<<std::endl;
        result_r.init(a_r.getg()*period_lcm/a_r.getd()-b_r.getg()*period_lcm/b_r.getd(),period_lcm);
        result.init(result_p,result_q,result_r);
        return result;
    }
}

static long int lcm(long int a, long int b)
{
    long int c,copy_a,copy_b;
    copy_a = a;
    copy_b = b;
    while(true)
    {
        c = copy_a % copy_b;
        if(c==0)
            return (a*b/copy_b);
        else
        {
            copy_a = copy_b;
            copy_b = c;
        }
    }
}

static int getmax(token_num* token_info, int n)
{
    int result = 0,index;
    for(index=0;index<n;index++)
        if((token_info+index)->token_num>result)
            result = (token_info+index)->token_num;
    return result;
}

