#include <stdio.h>
#include <math.h>
#include "ping.h"
#include "abwm.h"


  double divergeThreshhold = 0.0002;
  int maxIteration = 3;

  double bwLow, bwHigh;
  double intervalStep;
  double interval;    // the time interval btw probing msgs of current round
  int reqID;     // sequence number for the probing msg
  double bwAvailble;  // the estimated results
  double bwPrevious;  // previous round's measurement result
  double errorMargin; // how precise we want it to be
  int probingResponderID;
  int iteration;
  int tableCount = 1;
  double iterationEndTime;

  boolean roundNotFinished = false;
  boolean alighFlag = false;
  boolean reportValid = true;
  boolean resultFlag = false;
  double result;
  int refPkID = 1;    
  //to indicate which packet is used as reference pk for diverge comparison


     int  *trendBeginPoint;
     int  *trendEndPoint;
     double *absGapDiffDirivative;
     double *ABWArray;
     double *bandwidthReq;
     double variance=0.0;
     double stdVar;

extern int debug;
extern  double bwrUpperBound, bwrLowerBound;
extern  int msgSize, noOfMsgs;
extern  BWRange curBWR;
extern  BWRange bwr;
extern double sendingTime[MAX_PROBES];      /* sending time of each packet */
extern double receivingTime[MAX_PROBES];    /* receiving time of each packet */
extern double receivingTimeAA[MAX_PROBES];  /* receiving time of each packet */
extern double sendingTimeGap[MAX_PROBES];  /* sending time gap of each packet */
extern double absSendingTimeGap[MAX_PROBES];/* absolute sending time gap */
extern double receivingTimeGap[MAX_PROBES];  
extern double absReceivingTimeGap[MAX_PROBES];
extern double gapDifference[MAX_PROBES];
extern double absGapDifference[MAX_PROBES];


void
bwrangeInit(){
     int i;

if(debug) printf("\nentering timesubbwrangeInit()\n");

    
     trendBeginPoint = (int *) malloc((noOfMsgs+1)*sizeof(int));
     trendEndPoint = (int *) malloc((noOfMsgs+1)*sizeof(int));
     ABWArray = (double *) malloc((noOfMsgs+1)*sizeof(double));
     bandwidthReq = (double *) malloc((noOfMsgs+1)*sizeof(double));

     absGapDiffDirivative = (double *) malloc((noOfMsgs+1)*sizeof(double));
     bwr.upperBound = bwrUpperBound;
     bwr.lowerBound = bwrLowerBound;
     curBWR.upperBound = bwrUpperBound;
     curBWR.lowerBound = bwrLowerBound;
     if (debug) {
         printf("bwrUpperBound=%g, bwrLowerBound=%g\n",
            bwrUpperBound, bwrLowerBound);
         printf("bwr.upperBound=%g, bwr.lowerBound=%g\n",
            bwr.upperBound, bwr.lowerBound);
     } 
     for (i=1; i<noOfMsgs; i++) {
        ABWArray[i] = 0.0;
     }
     
}

double max(double v1, double v2){

if(debug) printf("\nentering max()\n");

   if (v1 > v2) return v1;
   else return v2;
}

void  
findBWRange() {

     int divergePoint = noOfMsgs+1;

     boolean notDiverge = true;
     boolean refNotFound = true;
     boolean abnormal = false;
     boolean foundFlag = false;
     int nearestPoint1;
     int nearestPoint2;
     double abs, abs1;
     double ABW1, ABW2;

     int i;
     int k;
     int trend=1;

if(debug) printf("\nentering findBWRange()\n");

     bandwidthReq[1] = curBWR.lowerBound;
     for(i=2; i<=noOfMsgs-1; i++)
        bandwidthReq[i] = msgSize*8/sendingTimeGap[i-1];
     for (i=1; i<noOfMsgs; i++) 
        if (debug) printf("bandwidthReq[%d]=%f\n", i, bandwidthReq[i]);
     i=1;
        // while(i <= sendingTime.length-1 & alighFlag == false)  {
        while(i <= noOfMsgs-1 & alighFlag == false)  {
           // System.out.println("absGapDiff["+i+"]"+absGapDifference[i]);
           // Chow: this is a bug?   absGapDifference has not being computed yet!
           // printf("absGapDifference[%d]=%f\n", i, absGapDifference[i]);
           if(absGapDifference[i] < -0.0002)  {
              alighFlag = true;
           }
           i++;
        }

        for (k=1; k<=noOfMsgs; k++) {
           if (debug) printf("sendingTime[%d]=%f, receivingTime[%d]=%f\n", 
                   k, sendingTime[k], k, receivingTime[k]);
        }

        i = 1;
        // while (i<=sendingTime.length-2 & refNotFound)  {   
        while (i<=noOfMsgs-2 & refNotFound)  {   
                //if the points don't diverge until 10th packet, 
                //   then refPkID = 10, divergePoint = 11

           for (k=1; k<=noOfMsgs-1; k++)  {
              absReceivingTimeGap[k] = receivingTime[k] - receivingTime[i];
              absSendingTimeGap[k] = sendingTime[k] - sendingTime[i];
              absGapDifference[k] =absReceivingTimeGap[k]-absSendingTimeGap[k];
              if (debug) printf("i=%d, absRcvTimeGap[%d]=%f, absSendTimeGap[%d]=%f, absGapDifference[%d]=%f\n",
                     i, k, absReceivingTimeGap[k], k, absSendingTimeGap[k], k, absGapDifference[k]);
           }
           
           if (absGapDifference[i+1] >= 0)  {
              k=i+1;
              while(k<=noOfMsgs-1 & refNotFound)  {
                 if(absGapDifference[k] > divergeThreshhold)  {
                    if(k <= noOfMsgs-2)   {                    
                          //to see whether the trend keep for at least 2 packets, 
                          // if not, it's not a divergent point
                       if (absGapDifference[k+1] >= absGapDifference[k])   {
                           //              divergePoint = k;
                          refNotFound = false;
                          refPkID = i;
                       }
                    }
                    else  {  //k=9 or 10
                             //           divergePoint = k;
                       refNotFound = false;
                       refPkID = i;
                    }
                 }
                 k++;
              }
           }
           i++;
        }//end of while (

        for(k=2; k<=noOfMsgs-1; k++)      //2, 10
           absGapDiffDirivative[k]=absGapDifference[k]-absGapDifference[k-1];

        trendBeginPoint[1] = refPkID;
        for(k=refPkID+1; k<=noOfMsgs-2; k++)  { //2, 9
           if(absGapDiffDirivative[k]>0 && absGapDiffDirivative[k+1] <= 0)  {   
               //trend finish
              trendEndPoint[trend] = k;
              trend++;
              trendBeginPoint[trend] = k+1;
           }
           if(k == noOfMsgs-2)
              trendEndPoint[trend] = k+1;
        }

        for(i=1; i<=trend; i++)  {
           // net.println("trend "+i+" start from "+trendBeginPoint[i]+
           //             " and end at "+trendEndPoint[i]);
           if (debug) printf("trend %d start from %d and end at %d\n",
                  i, trendBeginPoint[i], trendEndPoint[i]);
           notDiverge = true;
           k=trendBeginPoint[i];
           while(k<=trendEndPoint[i] & notDiverge)  {
              if(absGapDiffDirivative[k] > 0)   {
                 notDiverge = false;
                 divergePoint = k;
              }
              k++;
           }
           if(!notDiverge)   {
              if (debug) printf("Diverge Point=%d\n", divergePoint);
              for(k=trendBeginPoint[i]; k<=trendEndPoint[i]; k++)   {
                 if(divergePoint == 2)
                    ABWArray[k] = (curBWR.lowerBound+msgSize*8/sendingTimeGap[divergePoint-1])/2;
                 else
                    ABWArray[k] = ( msgSize*8/sendingTimeGap[divergePoint-2] + msgSize*8/sendingTimeGap[divergePoint-1] ) / 2;
              }
           }
           else  //only possible in the last trend
              if (debug) printf("Not diverge in last trend, need another iteration.\n");

        }

        if(refPkID > 1)   {  //handle the points before refPk
           for(i=1; i<=noOfMsgs-1; i++)
              if (debug) printf("absGapDifference[%d] = %f\n",
                     i, absGapDifference[i]);
           for(i=1; i<refPkID; i++)  {
              foundFlag = false;


              k=trendBeginPoint[1];

              abs=fabs(absGapDifference[i]-absGapDifference[k]);
              nearestPoint1 = trendBeginPoint[1];
              nearestPoint2 = trendBeginPoint[1];

              while(k<=trendEndPoint[trend]) {
                 abs1 = fabs(absGapDifference[i]-absGapDifference[k]);
                 if(  abs1 < abs)  {
                    abs = abs1;
                    nearestPoint1 = nearestPoint2;
                    nearestPoint2 = k;
                 }
                 k++;
              }
              if (debug) printf("The absGapDifference of packet %d is between %d and %d\n",
                     i, nearestPoint1, nearestPoint2);
              ABW1=max( (ABWArray[nearestPoint1]-(bandwidthReq[nearestPoint1]-bandwidthReq[i])), 0.0);
              ABW2=max( (ABWArray[nearestPoint2]-(bandwidthReq[nearestPoint2]-bandwidthReq[i])), 0.0);
              ABWArray[i] = (ABW1+ABW2)/2;
              if (debug) printf("ABWArray[%d] = %f\n", i, ABWArray[i]);
           }  //end of for (i=1; i<refPkID
        }  //end of if(refPkID > 1)

        for(i=1;i<=noOfMsgs-1;i++)
           if (debug) printf("ABWArray[%d]=%f\n", i, ABWArray[i]);

        if (notDiverge)  {           
           //if the last trend is not diverged, that means the result is not valid
           bwr.upperBound = 2*curBWR.upperBound;
           bwr.lowerBound = curBWR.upperBound/2;
           bwr.reportValid = false;
        } else {
           bwr.reportValid = true;
        }


        for(i=1; i<=noOfMsgs-1; i++)
           bwr.reportValue += (1/(noOfMsgs+0.0))*ABWArray[i];

        if (debug) printf("report Value = %f\n", bwr.reportValue);
        if (bwr.reportValid) {
           if (debug) printf("reportValid is true\n");
        } else {
           if (debug) printf("reportValid is false\n");
        }
        for(i=1; i<=noOfMsgs-1; i++)
           variance += (ABWArray[i] - bwr.reportValue) * (ABWArray[i] -bwr.reportValue);
        stdVar = sqrt(variance/(noOfMsgs-2));

        bwr.accuracy = stdVar/bwr.reportValue;
        if (debug) printf("Accuracy is %f\n", bwr.accuracy);

        i=1;
        foundFlag = false;
        while( i<=noOfMsgs-2 & foundFlag==false)   {
           if(bwr.reportValue>=bandwidthReq[i] && bwr.reportValue<bandwidthReq[i+1]) {
              foundFlag = true;

              if(i < 2)  bwr.lowerBound = bandwidthReq[1];

              else  bwr.lowerBound = bandwidthReq[i-1];

              if(i >= noOfMsgs-2) bwr.upperBound = bandwidthReq[noOfMsgs];
/* Chow: error here  should be bandwidthReq[i+1] narrower 
              else  bwr.upperBound = bandwidthReq[i+2];
*/
              else  bwr.upperBound = bandwidthReq[i+1];
           } 
           i++;

        }
        if (debug) printf("!! iteration=%d, next round bwr.upperBound=%f,lowerBound=%f\n", 
               iteration, bwr.upperBound, bwr.lowerBound);
        bwrLowerBound = bwr.lowerBound;
        bwrUpperBound = bwr.upperBound;

  }