/* Marzullo implmentation *//* Written by Kin Sun Ho (ksho@cse) *//* Last Modified: 05 September 2005 */includes Sasha;module MarzulloM{  provides interface Marzullolib;  provides interface StdControl;  uses {    interface Leds;  }}implementation{  struct Mote **info; // resizeable array of Mote Info  struct Marzullo *sort[NUM_UNITS*3]; // array to sort Marzullo end points  int8_t Nmotes; // number of motes received  int8_t Mmotes; // number of space allocated in memory  command result_t Marzullolib.add_mote(CLNNMsg *rmsg) {    int16_t mote_id;    int8_t i;    // find if new mote pkt    mote_id = rmsg->src;    for(i=0; i<Nmotes; i++) {      if(mote_id == info[i]->mote)	break;    }    if(i != Nmotes)      return FAIL; // drop if not new pkt       // drop pkt when full    if(Nmotes == Mmotes)      return FAIL;        // if new store result    atomic {      info[Nmotes]->mote = mote_id;      info[Nmotes]->min  = rmsg->min;      info[Nmotes]->max  = rmsg->max;      info[Nmotes]->percent = rmsg->percent;      info[Nmotes]->s2   = rmsg->s2;      Nmotes++;    }    return SUCCESS;  }  /* Quicksort Algorithms     adapted from http://linux.wku.edu/~lamonml/algor/sort/quick.html  */  void quickSort(int left, int right) {    int8_t t_left, t_right;    int16_t p1;    int8_t p2;    int8_t pivot;        atomic {      t_left = left;      t_right = right;      p1 = sort[left]->endpt;      p2 = sort[left]->type;    }        while (left < right) {            while ((sort[right]->endpt > p1 || (sort[right]->endpt == p1 && 	      sort[right]->type >= p2)) && (left < right))	right--;            if (left != right) {	atomic {	  sort[left]->endpt = sort[right]->endpt;	  sort[left]->type  = sort[right]->type;	}	left++;      }            while ((sort[left]->endpt < p1 || (sort[left]->endpt == p1 && 	      sort[left]->type < p2)) && (left < right))	left++;            if (left != right) {	atomic {	  sort[right]->endpt = sort[left]->endpt;	  sort[right]->type  = sort[left]->type;	}	right--;      }    }        atomic {      sort[left]->endpt = p1;      sort[left]->type  = p2;    }    pivot = left;    left  = t_left;    right = t_right;    if (left < pivot)      quickSort(left, pivot-1);    if (right > pivot)      quickSort(pivot+1, right);  }  // do Simon's Version of Marzullo  command CLNNMsg * Marzullolib.doMarzullo(CLNNMsg *result) {    int8_t k;    int8_t f,i,c;    uint32_t low,high;    uint32_t interval;    uint32_t prob;    int8_t j=0;    uint32_t mean_sum;    uint32_t s2;    uint32_t sd;    uint32_t limit;    uint16_t tmp;    low=0;    high=0;    mean_sum = 0;    s2=0;    tmp = 0;        atomic {      for(k=0; k<Nmotes; k++) {	sort[j]->endpt  = info[k]->min;	sort[j++]->type = M_START;	sort[j]->endpt  = (info[k]->min+info[k]->max)/2;	mean_sum += sort[j]->endpt;	s2 += info[k]->s2;	sort[j++]->type = M_MID;	sort[j]->endpt  = info[k]->max;	sort[j++]->type = M_END;      }    }    if(Nmotes < 2) {      return NULL;    }        quickSort(0,j-1);    // Marzullo: refer to CLNNM for more comments    for(f=0; f<(j/3); f++) {      // c checks the number of mean learnt not in intersection      // i checks the value of the end point determinant            c = 0; i = 0;             // loop from start of the list      for(k=0; k<j; k++) {	i -= sort[k]->type; // the first endpt gets i=1 since endpt->type = -1	low = sort[k]->endpt; // set this as the lower bound	if(i >= (j/3)-f) break; // break if we have passed N-f of the min endpt	if(sort[k]->type == 0) c++; // check # of centers not in intersection       }            i=0; // reset i=0      // loop from end of the list      for(k=j-1; k>=0; k--) {	i += sort[k]->type; // the first endpt gets i=1 since endpt->type = 1	high = sort[k]->endpt; // set this as the upper bound	if(i >= (j/3)-f) break; // break if we have passed N-f of max endpt	if(sort[k]->type == 0) c++;      }            // interval found break      if(c <= f)	break;    }        atomic {      // set the results      /*      for(k=0; k<Nmotes; k++) {      tmp = (info[k]->min+info[k]->max)/2;            if(tmp < low)      low = tmp;      if(tmp > high)      high = tmp;      }      */      result->min   = low;      result->max   = high;      result->f     = f;      interval = high-low;      prob = 0;            call Leds.yellowToggle();    }    atomic {      result->percent = 0; // unused      result->mean    = mean_sum/Nmotes;      sd = sqrt(s2);      result->s2 = s2;            // 1.96 for 95% CI, change the value for other % of CI            limit = 1.96*sd/sqrt(Nmotes*10*MAX_TRAIN);      result->limit = limit;    }    return result;  }  command result_t Marzullolib.reset() {    Nmotes = 0;    return SUCCESS;  }  command result_t StdControl.init() {    int8_t i;    dbg(DBG_USR1,"Marzullo init called\n");    call Leds.init();        Mmotes = MAX_MOTES;    Nmotes = 0;    for(i=0; i<Mmotes*3; i++) {      sort[i] = (struct Marzullo*) malloc(sizeof(struct Marzullo));    }    info = (struct Mote**) malloc(Mmotes*sizeof(struct Mote *));        for(i=0; i<Mmotes; i++) {      info[i] = (struct Mote*)malloc(sizeof(struct Mote));      info[i]->mote = i;    }        for(i=0; i<Mmotes; i++) {      dbg(DBG_USR1,"i: %d, array: %d \n",i,info[i]->mote);    }        return SUCCESS;  }  command result_t StdControl.start() {    return SUCCESS;  }    command result_t StdControl.stop() {    return SUCCESS;  }}