#include "stdafx.h"
#include "math.h"
#include "stdlib.h"
#include "search.h"
#include "memory.h"
#include "string.h"
#include "windows.h"

typedef unsigned long DWORD;
#define MAX_N (50)

#define TRUE 1
#define FALSE 0


typedef struct 
{
        DWORD bitMap;
        DWORD sum;
}SQRT_SUM;


typedef struct 
{
        DWORD bitMap1;
        DWORD bitMap2;
        double sum;
}SQRT_SUM_RST;


double g_sqrt_arr[MAX_N];
SQRT_SUM *pTab1=NULL;
SQRT_SUM *pTab2=NULL;

DWORD  mask_arr[]=
{
        1,                1<<1,        1<<2,        1<<3,        1<<4,
        1<<5,        1<<6,        1<<7,        1<<8,        1<<9,
        1<<10,        1<<11,        1<<12,        1<<13,        1<<14,
        1<<15,        1<<16,        1<<17,        1<<18,        1<<19,
        1<<20,        1<<21,        1<<22,        1<<23,        1<<24
};

double g_half_sum;


int __cdecl ItemCmp( const void *element1, const void *element2 )
{
        SQRT_SUM *p1,*p2;
        p1=(SQRT_SUM *)element1;
        p2=(SQRT_SUM *)element2;
        
        if (p1->sum > p2->sum )
                return 1;
        else if (p1->sum <p2->sum )
                return -1;
        else
                return 0;
}

   
int  InitData()
{
        DWORD i,j;
        DWORD key,t;
        double s=0.00;
        
        for ( i=0;i<MAX_N;i++)
        {
                g_sqrt_arr[i]= sqrt((double)(i+1));
                s+=g_sqrt_arr[i];
        }
        printf("\nsum=%.16f\n",s);
        g_half_sum =s * 0.5;
        
        pTab1=new SQRT_SUM[ 1<<25 ];
        pTab2=new SQRT_SUM[ 1<<25 ];
        
        if ( pTab1==NULL ||  pTab2==NULL )
        {
                printf("No memrory");
                return FALSE;
        }
        //---------------
        
        for (key=0; key < (1 << 25); key++)
        {
                
                for (s=0.00,j=0; j<25;j++)
                {
                        if (key & mask_arr[j] )
                        {
                                s+= g_sqrt_arr[j];
                        }
                }
                pTab1[key].bitMap=key;
                pTab1[key].sum= (DWORD)(s* 8388608.00+0.5);
        }

        for (key=0; key < (1 << 25); key++)
        {
                
                s=0;
                for (j=0; j<25;j++)
                {
                        if (key & mask_arr[j] )
                        {
                                s+= g_sqrt_arr[j+25];
                        }
                }
                pTab2[key].bitMap=key;
                pTab2[key].sum= (DWORD)(s* 8388608.00+0.5);
        }
        //----------------------------------
        t=GetTickCount();
        qsort( (void *)pTab1, (size_t)(1<<25), sizeof( SQRT_SUM), ItemCmp );
        qsort( (void *)pTab2, (size_t)(1<<25), sizeof( SQRT_SUM), ItemCmp );
        t=GetTickCount()-t;

        printf("It take %d ms for sort 2 arrays\n",t);
        
        return TRUE;
}

void  unInitData()
{
        if ( pTab1 !=NULL)
        {
                delete[] pTab1; pTab1=NULL;
        }

        if ( pTab2 !=NULL)
        {
                delete[] pTab2; pTab2=NULL;
        }
}

int binSearch( const SQRT_SUM* pTab, DWORD n, int end, int *pLow, int *pHigh)
{
        int low,high,mid;
        //-----------------
        low=0;
        high=end;
        while (1)
        {
                if (high-low<=1)
                {
                        break;
                }
                else
                {
                        mid=(low+high)/2;
                        if (n>=pTab[mid].sum)
                                low=mid; 
                        else
                                high=mid-1;
                }
        }

        if ( pTab[low].sum >= n-1)
                low--;
        low++;
        if ( pTab[high].sum <= n+1)
                high++;
        high--;
        *pLow=low;
        *pHigh=high;
        return (low<=high);
}

double getDouble( int tabNo, DWORD key)
{
        double r;
        int i;

        for (r=0.00,i=0;i<25;i++)
        {
                if (key & mask_arr[i] )
                {
                        if (tabNo==0)
                                r+= g_sqrt_arr[i];
                        else
                            r+= g_sqrt_arr[i+25];
                }
        }
        return r;
}

double printfArray(DWORD key1,DWORD key2)
{
        int i;
        double s=0;
        
        printf("[");
        for (i=0;i<25;i++)
        {
                if (key1 & mask_arr[i] )
                {
                        printf("%d,",i+1);
                        s+= sqrt( (double)(i+1));
                }
                
        }
        for (i=0;i<25;i++)
        {
                if (key2 & mask_arr[i] )
                {
                        printf("%d,",i+26);
                        s+= sqrt( (double)(i+26));
                }
                
        }
        printf("]");
        return s;
}

void search(int lmt,int *pIdx1,int *pIdx2)
{
        int i,j,end;
        double minDiff=1000000;
        int idx1,idx2;
        
        end=(1<<25)-1;
        for (i=0;i< (1<<25) ; i++)
        {
                double f1,f2;
                DWORD n1;
                int high,low;

                n1= pTab1[i].sum;
                if ( binSearch(pTab2,lmt-n1,end,&low,&high) )
                {
                        f1=getDouble( 0, pTab1[i].bitMap);

                        for (j=low;j<=high;j++)
                        {
                                f2=getDouble( 1, pTab2[j].bitMap);
                                if  ( fabs( f1+ f2 - g_half_sum)<minDiff)
                                {
                                        minDiff=fabs( f1+ f2 - g_half_sum);
                                        idx1=i;
                                        idx2=j;
                                }
                                
                        }
                        if (high<end)
                                end=high;
                }
        }
        *pIdx1=idx1;
        *pIdx2=idx2;
}

int main(int argc, char* argv[])
{
        double s;
        DWORD t1,t2,lmt;
        int idx1,idx2;
        
        t1=GetTickCount();
        InitData();
        lmt= (DWORD)(g_half_sum *  8388608.00+0.5);
        
        search(lmt,&idx1,&idx2);
        printf("\narray1 is:\n");
        s=printfArray(pTab1[idx1].bitMap,pTab2[idx2].bitMap);
        printf("\nThe sum is %.16f\n",s);

        unInitData();
        t2=GetTickCount()-t1;
        printf("\nIt take %u ms\n",t2);

        return 0;
}

}