w3hello.com logo
Home PHP C# C++ Android Java Javascript Python IOS SQL HTML videos Categories
Merging two different lists of datetime intervals

Because the lists are sorted than complexity is simply O(N) where N is number of merged list entries...

I thing i coded it correctly. Coded in bds2006 C++. Static allocation only. If you want to use it in different IDE than you must change AnsiString to any other string type. Also for better functionality you can add dynamic allocation for output list ... Here is my code (it generates exact same output as you provided, but would be better to test it with larger inputs):

//---------------------------------------------------------------------------
// lists types
struct _list_in  { AnsiString beg,end; int val; };
struct _list_out { AnsiString beg,end; double val1,val0; };

// helper functions
int str2tim(AnsiString s) 
    {
    int t=0,i=1;
    if (s.Length()!=10) return t;
    t*=10; t+=(s[i]-'0'); i++;
    t*=10; t+=(s[i]-'0'); i++;
    t*=10; t+=(s[i]-'0'); i++;
    t*=10; t+=(s[i]-'0'); i++;
                          i++;
    t*=10; t+=(s[i]-'0'); i++;
    t*=10; t+=(s[i]-'0'); i++;
                          i++;
    t*=10; t+=(s[i]-'0'); i++;
    t*=10; t+=(s[i]-'0'); i++;
    return t;
    }
AnsiString tim2str(int t)
    {
    int i=10;
    AnsiString s="0000-00-00";
    s[i]=char((t%10)+'0'); t/=10; i--;
    s[i]=char((t%10)+'0'); t/=10; i--;
                                  i--;
    s[i]=char((t%10)+'0'); t/=10; i--;
    s[i]=char((t%10)+'0'); t/=10; i--;
                                  i--;
    s[i]=char((t%10)+'0'); t/=10; i--;
    s[i]=char((t%10)+'0'); t/=10; i--;
    s[i]=char((t%10)+'0'); t/=10; i--;
    s[i]=char((t%10)+'0'); t/=10; i--;
    return s;
    }
int timinc(int t) // increment day
    {
    int dat[2][13]= {{ 0,31,28,31,30,31,30,31,31,30,31,30,31 },
                     { 0,31,29,31,30,31,30,31,31,30,31,30,31 }};
    int dd=t%100; t/=100;
    int mm=t%100; t/=100;
    int yy=t,k=0;
    if (yy%  4==0) k=1;
    if (yy%100==0) k=0;
    if (yy%400==0) k=1;
    dd++;
    if (dd>dat[k][mm])
        {
        dd=1; mm++;
        if (mm>12) { mm=1; yy++; }
        }
    return dd+(100*mm)+(10000*yy);
    }

// this is what you wanted
// l is output list
// l0,l1 are your input lists
// n is number of used entries in l
// max is allocated size of l
void list_merge(_list_out *l,int &n,int max,_list_in *l0,_list_in *l1) 
// l[n]=i0[]+i1[]
    {
    double all=0.0;         // default value for missing time entry
    double va0,va1,vb0,vb1,vt0,vt1; // values ... coresponding to a01 / a23
or b01 / b23
    int a0,a1,a2,a3;        // times (beg,end) (beg,end) from last 2 tested
entries of l0[]
    int b0,b1,b2,b3;        // times (beg,end) (beg,end) from last 2 tested
entries of l1[]
    int t0,t1,tt;           // actual exported times (beg,end) to l[] , tt
= temp
    // prepare variables
    for (;;)
        {
        if (l0->beg=="ALL") { all=l0->val; l0++; continue; }
        if (l0->beg=="") break;
        a0=str2tim(l0->beg);
        a1=str2tim(l0->end);
        va0=l0->val;
        l0++;
        break;
        }
    for (;;)
        {
        if (l0->beg=="ALL") { all=l0->val; l0++; continue; }
        if (l0->beg=="") break;
        a2=str2tim(l0->beg);
        a3=str2tim(l0->end);
        va1=l0->val;
        l0++;
        break;
        }
    for (;;)
        {
        if (l1->beg=="") break;
        b0=str2tim(l1->beg);
        b1=str2tim(l1->end);
        vb0=l1->val;
        l1++;
        break;
        }
    for (;;)
        {
        if (l1->beg=="") break;
        b2=str2tim(l1->beg);
        b3=str2tim(l1->end);
        vb1=l1->val;
        l1++;
        break;
        }
    // merge lists
    for (n=0,t0=0,t1=0;;)
        {
        t0=t1;
             if ((t0>b0)&&(t0<b1)) t0=timinc(t0);
        else if ((t0>b2)&&(t0<b3)) t0=timinc(t0);
        else{
            if (a1<t1)
             if (l0->beg!="")
                {
                if (l0->beg=="ALL") { all=l0->val; l0++; continue; }
                a0=a2; a1=a2; va0=va1;
                a2=str2tim(l0->beg);
                a3=str2tim(l0->end);
                va1=l0->val;
                l0++;
                }
            if (b1<t1)
             if (l1->beg!="")
                {
                b0=b2; b1=b2; vb0=vb1;
                b2=str2tim(l1->beg);
                b3=str2tim(l1->end);
                vb1=l1->val;
                l1++;
                }
            tt=100000000;
            if ((t1<a0)&&(tt>a0)) tt=a0;
            if ((t1<a1)&&(tt>a1)) tt=a1;
            if ((t1<a2)&&(tt>a2)) tt=a2;
            if ((t1<a3)&&(tt>a3)) tt=a3;
            if ((t1<b0)&&(tt>b0)) tt=b0;
            if ((t1<b1)&&(tt>b1)) tt=b1;
            if ((t1<b2)&&(tt>b2)) tt=b2;
            if ((t1<b3)&&(tt>b3)) tt=b3;
            t0=tt;
            }
        tt=100000000;
        if ((t0<a0)&&(tt>a0)) tt=a0;
        if ((t0<a1)&&(tt>a1)) tt=a1;
        if ((t0<a2)&&(tt>a2)) tt=a2;
        if ((t0<a3)&&(tt>a3)) tt=a3;
        if ((t0<b0)&&(tt>b0)) tt=b0;
        if ((t0<b1)&&(tt>b1)) tt=b1;
        if ((t0<b2)&&(tt>b2)) tt=b2;
        if ((t0<b3)&&(tt>b3)) tt=b3;
        t1=tt;
        if ((t0>=100000000)&&(t1>=100000000)) break;
        vt0=all;
        if ((t0>=a0)&&(t0<=a1)) vt0=va0;
        if ((t1>=a0)&&(t1<=a1)) vt0=va0;
        if ((t0>=a2)&&(t0<=a3)) vt0=va1;
        if ((t1>=a2)&&(t1<=a3)) vt0=va1;
        if ((t0>=b0)&&(t0<=b1)) vt1=vb0;
        if ((t1>=b0)&&(t1<=b1)) vt1=vb0;
        if ((t0>=b2)&&(t0<=b3)) vt1=vb1;
        if ((t1>=b2)&&(t1<=b3)) vt1=vb1;
        l->beg =tim2str(t0);
        l->end =tim2str(t1);
        l->val0=vt0;
        l->val1=vt1;
        l++; n++; if (n>=max) break;
        }
    };
//---------------------------------------------------------------------------
// here is usage:
//---------------------------------------------------------------------------
_list_in in0[]=
    {
    "ALL"       , "ALL"       , 2,
    "2013-11-24", "2013-11-30", 4,
    "2013-12-24", "2014-01-01", 3,
    "","",0 // end
    };
_list_in in1[]=
    {
    "2013-07-08", "2013-08-29", 1800.00,
    "2013-08-30", "2013-09-06", 1800.00,
    "2013-10-01", "2013-10-31", 1500.00,
    "2013-11-24", "2013-12-03",  400.00,
    "2013-12-24", "2014-01-03",  500.00,
    "","",0 // end
    };
const int _max=32;
_list_out out[_max]; int outs=0;
//---------------------------------------------------------------------------
void main()
    {
    list_merge(out,outs,_max,in0,in1);
    }
//---------------------------------------------------------------------------




© Copyright 2018 w3hello.com Publishing Limited. All rights reserved.