/**************************************************************************
 function:  BMedian35 (short* lpSource, short* lpDest, short cx)
 purpose:		compute moving median
 parameters:	input array + nb of points to compute
 returns:		output array with median value
 comments:
 source:	L. Fiore, G. Corsini, L. Geppetti (1997) Application of non-linear
	filters based on the median filter to experimental and simulated
	multiunit neural recordings. J Neurosci Meth 70: 177-184.
 **************************************************************************/

void CWaveBuf::BMedian35(short* lpSource, short* lpDest, short cx)
{	
	short offsetnextpoint = m_waveFormat.scan_count;// number of chans within source buffer
	short nbspan = TransformBufferSpan[13];	// nb of points within moving windows /2
	// usually we use = 30; ie 61 points total. Our spikes are defined over 60 points.
	short offsetspan = offsetnextpoint * nbspan;	// offset between center of window & end
	short NN = nbspan*2 +1;			// nb of points within window
	short *parray = new short[NN];		// temporary array 
	
	// init parray = consecutive points (image of the data points)	
	int i=0;					// index variable
	short* lp = lpSource;			// pointer to origin of source buffer
	lp -= offsetspan;				// first point of the moving window
	for (i = 0; i < NN; lp += offsetnextpoint, i++)	// load parray
		*(parray+i) = *lp;			// with buffer values

	// sort parray into ascending order using heapsort algorithm
	// cf Numerical recipes Press et al.1986, pp 231
	// "l"= index which will be decremented from initial value down to 0 during
	// 'hiring' (heap creation) phase. Once it reaches 0, the index "ir" will be 
	// decremented from its initial value down to 0 during the 'retirement-and-
	// promotion' (heap selection) phase.
	int l = nbspan + 1;				// temp index
	int ir = NN - 1;				// temp index
	int j;					// temp index
	short val;					// temp storage	

	for (;;)					// pseudo-loop over parray
	{
		// -------------------------
		if (l > 0)				// still in hiring phase
		{
			l--;
			val = *(parray + l);
		}
		else				// in retirement-and-promotion phase
		{
			val = *(parray+ir);		// clear a space at the end of the array
			*(parray+ir) = *(parray);	// retire the top of the heap into it
			ir--;			// decrease the size of the corporation
			if (ir == 0)		// done with the last promotion
			{
				*(parray) = val;	// the least competent worker of all
				break;		// exit the sorting algorithm
			}
		}
		// -------------------------
		i = l + 1;				// wether we are in the hiring or promotion, we
		j = i + i;				// here set up to sift down element raa to its 
						// proper level
		while (j-1 <= ir)
		{			
			if (j-1 < ir)				
				if (*(parray+j-1) < *(parray+j))
					j++;	// compare to the better underlining
			if (val < *(parray+j-1))	// demote val
			{
				*(parray+i-1) = *(parray+j-1);
				i = j;
				j = j + j;
			}			// this is val's level. Set j to terminate the
			else			// sift-down
				j = ir + 2;
		}
		*(parray+i-1) = val;			// put val into its slot
	}

	// end of initial sort

	short newvalue;				// temp variable used in the loop
	short oldval;				// temp variable used in the loop
	short offset2span = 2*offsetspan+offsetnextpoint;// offset first to last pt/window
	lp= lpSource + offsetspan;


	for (cx; cx>0; cx--, lp += offsetnextpoint, lpDest++)
	{
		newvalue = *lp;			// new value to insert into array
		oldval = *(lp-offset2span);		// value to discard from array

		// locate position of old value to discard
		// use bisection - cf Numerical Recipes pp 90
		// on exit, j= index of oldval

		// binary search
		// Herbert Schildt: C the complete reference McGraw Hill, 1987, pp 488
		int jhigh = NN-1;			// upper index
		int jlow = 0;			// mid point index
		while (jlow <= jhigh)
		{
			j = (jlow+jhigh)/2;			
			if (oldval > *(parray+j))
				jlow = j +1;
			else if (oldval < *(parray+j))
				jhigh = j-1;
			else
				break;
		}

		// insert new value in the correct position

		// case 1: search (and replace) towards higher values
		if (newvalue > *(parray + j))
		{	
			for (j; newvalue > *(parray + j); j++)
			{								
				if (j == NN)
					break;
				*(parray+ j) = *(parray + j + 1);
			} 
			*(parray + j-1) = newvalue;
		}

		// case 2: search (and replace) towards lower values
		else if (newvalue < *(parray + j))
		{
			for (j; newvalue < *(parray + j); j--)
			{
				if (j == 0)
				{
					if (newvalue < *parray)
						j--;
					break;
				}
				*(parray + j)  = *(parray + j -1);
			}
			*(parray + j+1) = newvalue;
		}

		// case 3: already found!
		else
			*(parray + j) = newvalue;


		// save median value in the output array
		// m_waveFormat.binzero : binary value of the zero volt. For ex, for 12 bits binary encoded data, zero is
		// encoded as 2048.
		*lpDest = *(lp-offsetspan) - *(parray+nbspan) + (short) m_waveFormat.binzero;
	}

	delete parray;
}