typedef struct token_num
{
    int token_num;
    long int time;
}token_num;

static int getmin(token_num* token_info, int info_length, long int window_size, long int end_time);

void print(token_num* token_info,int n)
{
    int index;
    for(index=0;index<n;index++)
        std::cout<<(token_info+index)->token_num<<":"<<(token_info+index)->time<<std::endl;
}

token_num* ominus(poly poly_a, poly poly_b,int *n)
{
    int gda_index,gdb_index,polynum_a,polynum_b,token_index;
    long int time_point = 0;
    token_num* token_info;
    polynum_a = poly_a.getn();
    polynum_b = poly_b.getn();
    gda_index = gdb_index = token_index = 0;
    token_info = (token_num*)calloc(sizeof(token_num),polynum_a+polynum_b);
    while(gda_index != polynum_a || gdb_index != polynum_b)
    {
        if(poly_a.getdata()[gda_index].getd() == 2147483647 && poly_b.getdata()[gdb_index].getd() == 2147483647)
        {
            (token_info + token_index)->time = poly_b.getdata()[gdb_index].getd();
            (token_info + token_index)->token_num = poly_a.getdata()[gda_index].getg() - poly_b.getdata()[gdb_index].getg();
            token_index++; break;
        }
        else if(poly_a.getdata()[gda_index].getd() == poly_b.getdata()[gdb_index].getd())
        {
            (token_info + token_index)->time = poly_b.getdata()[gdb_index].getd();
            (token_info + token_index)->token_num = poly_a.getdata()[gda_index].getg() - poly_b.getdata()[gdb_index].getg();
            token_index++; gda_index++; gdb_index++;
        }
        else if(gda_index == polynum_a || poly_a.getdata()[gda_index].getd() > poly_b.getdata()[gdb_index].getd())
        {
            (token_info + token_index)->time = poly_b.getdata()[gdb_index].getd();
            (token_info + token_index)->token_num = poly_a.getdata()[gda_index].getg() - poly_b.getdata()[gdb_index].getg();
            token_index++; gdb_index++;
        }
        else if(gdb_index == polynum_b || poly_a.getdata()[gda_index].getd() <= poly_b.getdata()[gdb_index].getd())
        {
            (token_info + token_index)->time = poly_a.getdata()[gda_index].getd();
            (token_info + token_index)->token_num = poly_a.getdata()[gda_index].getg() - poly_b.getdata()[gdb_index].getg();
            token_index++; gda_index++;
        }
    }
    *n = token_index;
    return token_info;
}

token_num* window(token_num* token_info,int n, long int window_size, int* window_length)
{
    long int time_point = 0;
    token_num* result;
    int index=0,moved_index=0;
    int window_index=0,index_temp;
    result = (token_num*)calloc(sizeof(token_num),n*2);
    while((token_info+moved_index)->time<window_size && (moved_index-1)<n) moved_index++;
    while(index !=n || moved_index != n)
    {
        if((token_info+index)->time == 2147483647 && (token_info+moved_index)->time == 2147483647)
        {
            (result+window_index)->time = 2147483647;
            (result+window_index)->token_num = (token_info+index)->token_num;
            window_index++;index++,moved_index++;
        }
        else if((token_info+index)->time < (token_info+moved_index)->time-window_size || moved_index == n)
        {
            (result+window_index)->time = (token_info+index)->time;
            (result+window_index)->token_num = getmin(token_info,n,window_size,(token_info+index)->time);
            window_index++;index++;
        }
        else if((token_info+index)->time > (token_info+moved_index)->time-window_size || index == n)
        {
            (result+window_index)->time = (token_info+moved_index)->time-window_size;
            (result+window_index)->token_num = getmin(token_info,n,window_size,(token_info+moved_index)->time-window_size);
            window_index++;moved_index++;
        }
        else
        {
            (result+window_index)->time = (token_info+index)->time;
            (result+window_index)->token_num = getmin(token_info,n,window_size,(token_info+index)->time);
            window_index++;index++;moved_index++;
        }
    }
    *window_length = window_index;
    for(window_index = 1;window_index<*window_length;window_index++)
    {
        if((result+window_index)->token_num == (result+window_index - 1)->token_num)
        {
            for(index_temp = window_index;index_temp<*window_length;index_temp++)
            {
                (result+index_temp - 1)->time = (result+index_temp)->time;
                (result+index_temp - 1)->token_num = (result+index_temp)->token_num;
            }
            (*window_length)--;
            window_index--;
        }
    }
    return result;
}

static int getmin(token_num* token_info, int info_length, long int window_size, long int end_time)
{
    int start_index=0,end_index=0,index;
    int min_number = 32767;
    while((token_info+start_index)->time < end_time && (start_index-1)<info_length)
        start_index++;
    while((token_info+end_index)->time < end_time + window_size && (start_index-1)<info_length)
        end_index++;
    for(index = start_index;index<=end_index;index++)
        min_number = ((token_info+index)->token_num<min_number)?(token_info+index)->token_num:min_number;
    return min_number;
}
