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

#include "adc.h"
#include "macrodef.h"

#ifdef UNIX
/* 
#include <fcntl.h>
#include <sys/file.h>
*/
#include <unistd.h>
#endif

uint32 NumberOfOnes(uint64 s);
void swap8(void *a);
void SetOneBit(uint64 *s, int32 pos){ uint64 ob = MLB; ob >>= pos; *s |= ob;}
void SetOneBit32(uint32 *s, uint32 pos){ 
   uint32 ob = 0x80000000;
   ob >>= pos; 
   *s |= ob;
}
uint32 Mlo32(uint32 x){
   uint32 om = 0x80000000;
   uint32 i;
   uint32 k;
              
   for ( k = 0, i = 0; i < 32; i++ ) {
       if (om&x) break;
       om >>= 1;
       k++;
   } 
   return(k);   
}
int32 mro32(uint32 x){
   uint32 om = 0x00000001;
   uint32 i;
   uint32 k;
              
   for ( k = 32, i = 0; i < 32; i++ ) {
       if (om&x) break;
       om <<= 1;
       k--;
   } 
   return(k);   
}
uint32 setLeadingOnes32(uint32 n){
    int32 om = 0x80000000;
   uint32 x;
   uint32 i;
         
   for ( x = 0, i = 0; i < n; i++ ) {
         x |= om;
         om >>= 1;
   } 
   return (x);
}
int32 DeleteOneFile(const char * file_name) {
#  ifdef WINNT
      return(remove(file_name));
#  else
      return(unlink(file_name));
#  endif
}
void WriteOne32Tuple(char * t, uint32 s, uint32 l, FILE * logf) {
  uint64 ob = MLB32;
  uint32 i;
            
  fprintf(logf, "\n %s", t);
  for ( i = 0; i < l; i++ ) {
    if (s&ob) fprintf(logf, "1"); else fprintf(logf, "0");
    ob >>= 1;
  }
}
uint32 NumOfCombsFromNbyK( uint32 n, uint32 k ){
  uint32 l, combsNbyK;
  if ( k > n ) return 0;
  for(combsNbyK=1, l=1;l<=k;l++)combsNbyK = combsNbyK*(n-l+1)/l;
  return  combsNbyK;
}
void JobPoolUpdate(ADC_VIEW_CNTL *avp){
   uint32 l = avp->nv;
   uint32 k;
  
   k = avp->lpp[l].layerIndex + avp->lpp[l].layerCurrentPopulation;
   avp->jpp[k].grpb = avp->groupby;
   avp->jpp[k].nv = l;
   avp->jpp[k].nRows = avp->nViewRows;
   avp->jpp[k].viewOffset = avp->accViewFileOffset;
   avp->lpp[l].layerCurrentPopulation++;
} 
int32 GetParent(ADC_VIEW_CNTL *avp, uint32 binRepTuple){
   uint32 level, levelPop, i;
   uint32 ig;
   uint32 igOfSmallestParent;
   uint32 igOfPrefixedParent;
   uint32 igOfSharedSortParent;
   uint32 spMinNumOfRows;
   uint32 pfMinNumOfRows;
   uint32 ssMinNumOfRows;
   uint32 tgrpb;
   uint32 pg;
   uint32 pfm;
   uint32 mlo = 0;
   uint32 lom;
   uint32 l = NumberOfOnes(binRepTuple);
   uint32 spFound;
   uint32 pfFound;
   uint32 ssFound;
   uint32 found;
   uint32 spFt;
   uint32 pfFt;   
   uint32 ssFt;

   found = noneParent;
   pfm = setLeadingOnes32(mro32(avp->groupby));
   SetOneBit32(&mlo, Mlo32(avp->groupby));
   lom = setLeadingOnes32(Mlo32(avp->groupby)); 

   for(spFound=pfFound=ssFound=0, level=l;level<=avp->nTopDims;level++){
      levelPop = avp->lpp[level].layerCurrentPopulation;
      
      if(levelPop != 0);
      {
           for ( spFt = pfFt = ssFt = 1, ig = avp->lpp[level].layerIndex,
                 i = 0; i < levelPop; i++ )
           {
               tgrpb = avp->jpp[ig].grpb;
               if ( (avp->groupby & tgrpb) == avp->groupby ) { 
                  spFound = 1;
                  if (spFt) { spMinNumOfRows = avp->jpp[ig].nRows; 
                              igOfSmallestParent = ig; spFt = 0; }
                  else   if ( spMinNumOfRows > avp->jpp[ig].nRows ) 
                            { spMinNumOfRows = avp->jpp[ig].nRows; 
                              igOfSmallestParent = ig; }

				  pg = tgrpb & pfm;
				  if (pg == binRepTuple) {
                     pfFound = 1;
                     if (pfFt) { pfMinNumOfRows = avp->jpp[ig].nRows; 
                                 igOfPrefixedParent = ig; pfFt = 0; }
                     else   if ( pfMinNumOfRows > avp->jpp[ig].nRows) 
                               { pfMinNumOfRows = avp->jpp[ig].nRows; 
                                 igOfPrefixedParent = ig; }
				  }

				  if ( (tgrpb & mlo) && !(tgrpb & lom)) {
                     ssFound = 1;
                     if (ssFt) { ssMinNumOfRows = avp->jpp[ig].nRows; 
                                 igOfSharedSortParent = ig; ssFt = 0; }
                     else   if ( ssMinNumOfRows > avp->jpp[ig].nRows) 
                               { ssMinNumOfRows = avp->jpp[ig].nRows; 
                                 igOfSharedSortParent = ig; }
				  }
               }
               ig++;
           }
      }
      if (pfFound) found = prefixedParent;
      else if (ssFound) found = sharedSortParent;
           else if (spFound) found = smallestParent;

      switch(found){
         case prefixedParent:
           avp->smallestParentLevel = level;
           avp->viewOffset      = avp->jpp[igOfPrefixedParent].viewOffset;
           avp->nParentViewRows = avp->jpp[igOfPrefixedParent].nRows;
           avp->parBinRepTuple  = avp->jpp[igOfPrefixedParent].grpb;
           break;
         case sharedSortParent:
           avp->smallestParentLevel = level;
           avp->viewOffset	    = avp->jpp[igOfSharedSortParent].viewOffset;
           avp->nParentViewRows = avp->jpp[igOfSharedSortParent].nRows;
           avp->parBinRepTuple  = avp->jpp[igOfSharedSortParent].grpb;
           break;
         case smallestParent:
           avp->smallestParentLevel = level;
           avp->viewOffset	    = avp->jpp[igOfSmallestParent].viewOffset;
           avp->nParentViewRows = avp->jpp[igOfSmallestParent].nRows;
           avp->parBinRepTuple  = avp->jpp[igOfSmallestParent].grpb;
           break;
         default: break;
      }
      if(   found == prefixedParent 
         || found == sharedSortParent 
	 || found == smallestParent) break;
   }
  return found;
} 
uint32 GetSmallestParent(ADC_VIEW_CNTL *avp, uint32 binRepTuple){
   uint32 found, level, levelPop, i, ig, igOfSmallestParent;
   uint32 minNumOfRows;
   uint32 tgrpb;
   uint32 ft;
   uint32 l = NumberOfOnes(binRepTuple);
  
   for(found=0, level=l; level<=avp->nTopDims;level++){
      levelPop = avp->lpp[level].layerCurrentPopulation;
      if(levelPop){
        for(ft=1, ig=avp->lpp[level].layerIndex, i=0;i<levelPop;i++){
          tgrpb = avp->jpp[ig].grpb;
          if ( (avp->groupby & tgrpb) == avp->groupby ) { 
            found = 1;
            if(ft){
	      minNumOfRows=avp->jpp[ig].nRows;
	      igOfSmallestParent = ig; 
	      ft = 0;
	    }else if(minNumOfRows > avp->jpp[ig].nRows){ 
	      minNumOfRows = avp->jpp[ig].nRows;
	      igOfSmallestParent = ig;
	    }
          }
          ig++;
        }
      }
      if( found ){      
         avp->smallestParentLevel = level;
         avp->viewOffset = avp->jpp[igOfSmallestParent].viewOffset;
         avp->nParentViewRows = avp->jpp[igOfSmallestParent].nRows;
         avp->parBinRepTuple = avp->jpp[igOfSmallestParent].grpb;
         break;
      }
   }
   return found;
} 
int32 GetPrefixedParent(ADC_VIEW_CNTL *avp, uint32 binRepTuple){
   uint32 found, level, levelPop, i, ig, igOfSmallestParent;
   uint32 minNumOfRows;
   uint32 tgrpb;
   uint32 ft;
   uint32 pg, tm;
   uint32 l = NumberOfOnes(binRepTuple);
   
   tm = setLeadingOnes32(mro32(avp->groupby));

   for(found=0, level=l; level<=avp->nTopDims; level++){
      levelPop = avp->lpp[level].layerCurrentPopulation;
  
      if (levelPop != 0);
      {
           for(ft = 1, ig = avp->lpp[level].layerIndex, 
                i = 0; i < levelPop; i++ ) {
               tgrpb = avp->jpp[ig].grpb;
               if ( (avp->groupby & tgrpb) == avp->groupby ) { 
				  pg = tgrpb & tm;
				  if (pg == binRepTuple) {
                     found = 1;
                     if (ft) { minNumOfRows = avp->jpp[ig].nRows; 
                               igOfSmallestParent = ig; ft = 0; }
                     else if ( minNumOfRows > avp->jpp[ig].nRows) 
                             { minNumOfRows = avp->jpp[ig].nRows; 
                               igOfSmallestParent = ig; }
				  }
               }
               ig++;
           }
      }
      if ( found ) {      
         avp->smallestParentLevel = level;
         avp->viewOffset = avp->jpp[igOfSmallestParent].viewOffset;
         avp->nParentViewRows = avp->jpp[igOfSmallestParent].nRows;
         avp->parBinRepTuple = avp->jpp[igOfSmallestParent].grpb;
         break;
      }
   }
  return found;
} 
void JobPoolInit(JOB_POOL *jpp, uint32 n, uint32 nd){
  uint32 i;

  for ( i = 0; i < n; i++ ) {
      jpp[i].grpb = 0;
	  jpp[i].nv = 0;  
      jpp[i].nRows = 0;
      jpp[i].viewOffset = 0;
  }    
}
void WriteOne64Tuple(char * t, uint64 s, uint32 l, FILE * logf){
   uint64 ob = MLB;
   uint32 i;
            
   fprintf(logf, "\n %s", t);
   for ( i = 0; i < l; i++ ) {
      if (s&ob) fprintf(logf, "1"); else fprintf(logf, "0");
      ob >>= 1;
   }
}
uint32 NumberOfOnes(uint64 s){
   uint64 ob = MLB;
   uint32 i;
   uint32 nOnes;

   for ( nOnes = 0, i = 0; i < 64; i++ ) {
      if (s&ob) nOnes++;
      ob >>= 1;
   }
   return nOnes;
}
void GetRegTupleFromBin64(
           uint64 binRepTuple, 
	       uint32 *selTuple,
	       uint32 numDims, 
	       uint32 *numOfUnits){
   uint64 oc = MLB;
   uint32 i;
   uint32 j;
  
   *numOfUnits = 0;  
   for( j = 0, i = 0; i < numDims; i++ ) {
     if (binRepTuple & oc) { selTuple[j++] = i+1; (*numOfUnits)++;}  
     oc >>= 1;
   }    
}
void getRegTupleFromBin32(
           uint32 binRepTuple, 
	       uint32 *selTuple,
	       uint32 numDims, 
	       uint32 *numOfUnits){
   uint32 oc = MLB32;
   uint32 i;
   uint32 j;
  
   *numOfUnits = 0;
   for( j = 0, i = 0; i < numDims; i++ ) {
     if (binRepTuple & oc) { selTuple[j++] = i+1; (*numOfUnits)++;}  
     oc >>= 1;
   }    
}
void GetRegTupleFromParent(
               uint64 bin64RepTuple,
               uint32 bin32RepTuple, 
	       uint32 *selTuple,
	       uint32 nd){
   uint32 oc = MLB32;
   uint32 i, j, k;
   uint32 ut32; 
  
   ut32 = (uint32)(bin64RepTuple>>(64-nd)); 
   ut32 <<= (32-nd);
   
   for ( j = 0, k = 0, i = 0; i < nd; i++ ) {
     if (bin32RepTuple & oc) k++;
     if (bin32RepTuple & oc && ut32 & oc) selTuple[j++] = k; 
     oc >>= 1;
   }    
}
void CreateBinTuple(uint64 *binRepTuple, uint32 *selTuple, uint32 numDims){
   uint32 i;

   *binRepTuple = 0;
   for(i = 0; i < numDims; i++ ){
     SetOneBit( binRepTuple, selTuple[i]-1 );
   }    
}
void d32v( char * t, uint32 *v, uint32 n){
   uint32 i;
   
   fprintf(stderr,"\n%s ", t);
   for ( i = 0; i < n; i++ ) fprintf(stderr," %d", v[i]);
}
void WriteOne64Tuple(char * t, uint64 s, uint32 l, FILE * logf);
int32 Comp8gbuf(const void *a, const void *b){
   if ( a < b ) return -1;
   else if (a > b) return 1;
   else return 0;
}
void restore(TUPLE_VIEWSIZE x[], uint32 f, uint32 l ){ 
   uint32 j, m, tj, mm1, jm1, hl;
   uint64 iW;
   uint64 iW64;

   j = f;
   hl = l>>1;
   while( j <= hl ) {
      tj = j*2;
      if (tj < l && x[tj-1].viewsize < x[tj].viewsize) m = tj+1;
      else m = tj;
      mm1 = m - 1;
      jm1 = j - 1;
      if ( x[mm1].viewsize > x[jm1].viewsize ) {
         iW = x[mm1].viewsize; 
	 x[mm1].viewsize = x[jm1].viewsize; 
	 x[jm1].viewsize = iW;  
         iW64 = x[mm1].tuple; 
	 x[mm1].tuple = x[jm1].tuple; 
	 x[jm1].tuple = iW64;  
         j = m;
      }else j = l;
   }
}
void vszsort( TUPLE_VIEWSIZE x[], uint32 n){
  int32 i, im1;
  uint64 iW;
  uint64 iW64;
  
  for ( i = n>>1; i >= 1; i-- ) restore( x, i, n );
  for ( i = n; i >= 2; i-- ) {
     im1 = i - 1;
     iW = x[0].viewsize; x[0].viewsize = x[im1].viewsize; x[im1].viewsize = iW;  
     iW64 = x[0].tuple; x[0].tuple = x[im1].tuple; x[im1].tuple = iW64;  
     restore( x, 1, im1);
  }
}
uint32 countTupleOnes(uint64 binRepTuple, uint32 numDims){
  uint32 i, cnt = 0;
  uint64 ob = 0x0000000000000001; 

  for(i = 0; i < numDims; i++ ){
    if ( binRepTuple&ob) cnt++;
    ob <<= 1;
  }    
  return cnt;
}
void restoreo( TUPLE_ONES x[], uint32 f, uint32 l ){ 
   uint32 j, m, tj, mm1, jm1, hl;
   uint32 iW;
   uint64 iW64;

   j = f;
   hl = l>>1;
   while( j <= hl ) {
      tj = j*2;
      if (tj < l && x[tj-1].nOnes < x[tj].nOnes) m = tj+1;
      else m = tj;
      mm1 = m - 1; jm1 = j - 1;
      if ( x[mm1].nOnes > x[jm1].nOnes ){
         iW = x[mm1].nOnes;
	     x[mm1].nOnes = x[jm1].nOnes; 
	     x[jm1].nOnes = iW;  
         iW64 = x[mm1].tuple; 
	     x[mm1].tuple = x[jm1].tuple; 
	     x[jm1].tuple = iW64;  
         j = m;
      }else j = l;
   }
}
void onessort( TUPLE_ONES x[], uint32 n){
   int32 i, im1;
  uint32 iW;
  uint64 iW64;
  
  for ( i = n>>1; i >= 1; i-- ) restoreo( x, i, n );
  for ( i = n; i >= 2; i-- ) {
     im1 = i - 1;
     iW = x[0].nOnes; 
     x[0].nOnes = x[im1].nOnes; 
     x[im1].nOnes = iW;  
     iW64 = x[0].tuple; 
     x[0].tuple = x[im1].tuple; 
     x[im1].tuple = iW64;  
     restoreo( x, 1, im1);
  }
}
uint32 MultiFileProcJobs( TUPLE_VIEWSIZE *tuplesAndSizes, 
		                          uint32 nViews, 
                           ADC_VIEW_CNTL *avp ){
   uint32 i;
    int32 ii; /* it should be int */
   uint32 j;
   uint32 pn;
   uint32 direction = 0;
   uint32 dChange = 0;
   uint32 gbi;
   uint32 maxn;
   uint64 *gbuf;
   uint64      vszs[MAX_NUMBER_OF_TASKS];
   uint32 nGroupbys[MAX_NUMBER_OF_TASKS];
   TUPLE_ONES *toptr;

   gbuf = (uint64*) &avp->memPool[0];

   for(i = 0; i < avp->nTasks; i++ ){ nGroupbys[i] = 0; vszs[i] = 0; }

   for(pn = 0, gbi = 0, ii = nViews-1; ii >= 0; ii-- ){
     if(pn == avp->taskNumber) gbuf[gbi++]=tuplesAndSizes[ii].tuple;
     nGroupbys[pn]++;
     vszs[pn] += tuplesAndSizes[ii].viewsize; 
     if(direction == 0 && pn == avp->nTasks-1 ) { 
       direction = 1; 
       dChange = 1; 
     }
     if(direction == 1 && pn == 0 ){ 
       direction = 0; 
       dChange = 1; 
     }
     if (!dChange){ if (direction) pn--; else pn++;}
     dChange = 0;
   }
   for(maxn = 0, i = 0; i < avp->nTasks; i++) 
     if (nGroupbys[i] > maxn) maxn = nGroupbys[i];

   toptr = (TUPLE_ONES*) malloc(sizeof(TUPLE_ONES)*maxn);
   if(!toptr) return 1; 

   for(i = 0; i < avp->nTasks; i++ ){
     if(i == avp->taskNumber){
       for(j = 0; j < nGroupbys[i]; j++ ){
         toptr[j].tuple = gbuf[j];
         toptr[j].nOnes  = countTupleOnes(gbuf[j], avp->nTopDims);
       }
       qsort((void*)gbuf,  nGroupbys[i], 8, Comp8gbuf );
       onessort(toptr, nGroupbys[i]);

       for(j = 0; j < nGroupbys[i]; j++){
         toptr[nGroupbys[i]-1-j].tuple <<= (64-avp->nTopDims);
         swap8(&toptr[nGroupbys[i]-1-j].tuple);
         fwrite(&toptr[nGroupbys[i]-1-j].tuple, 8, 1, avp->groupbyFile);
       }
     }
   }
   FSEEK(avp->groupbyFile, 0L, SEEK_SET);
   if (toptr) free(toptr);
   return 0;
}
int32 PartitionCube(ADC_VIEW_CNTL *avp){
    TUPLE_VIEWSIZE *tuplesAndSizes;
    uint32 it = 0;
    uint64 sz;
    uint32 sel[64];
    uint32 k;
    uint64 tx;
    uint32 i;
      char inps[256];
      
    tuplesAndSizes = 
       (TUPLE_VIEWSIZE*) malloc(avp->nViewLimit*sizeof(TUPLE_VIEWSIZE));
    if(tuplesAndSizes == NULL){
       fprintf(stderr," PartitionCube(): memory allocation failure'\n");
       return ADC_MEMORY_ALLOCATION_FAILURE;
    }
    k = 0;
    while( fscanf(avp->adcViewSizesFile, "%s", inps) != EOF ){
       if( strcmp(inps, "Selection:") == 0 ) {
         while ( fscanf(avp->adcViewSizesFile, "%s", inps)) {
           if ( strcmp(inps, "View") == 0 ) break; 
           sel[k++] = atoi(inps);	
         }
       }
       if( strcmp(inps, "Size:") == 0 ){
         fscanf(avp->adcViewSizesFile, "%s", inps);
         sz = atoi(inps);
         CreateBinTuple(&tx, sel, k);
         if (sz > avp->nInputRecs) sz = avp->nInputRecs;
         tuplesAndSizes[it].viewsize = sz;
         tuplesAndSizes[it].tuple = tx; 
         it++;
         k = 0;
       }  
    }
    vszsort(tuplesAndSizes, it);
    for( i = 0; i < it; i++){
        tuplesAndSizes[i].tuple >>= (64-avp->nTopDims);
    }
    if(MultiFileProcJobs( tuplesAndSizes, it, avp )){
       fprintf(stderr, "MultiFileProcJobs() is failed \n");
       fprintf(avp->logf, "MultiFileProcJobs() is failed.\n");
       fflush(avp->logf);
       return 1;
    }
    FSEEK(avp->adcViewSizesFile, 0L, SEEK_SET);
    free(tuplesAndSizes);
    return 0;
}