#include "BSprivate.h"

/* ************************************************************** */
/* A set of sorting routines based on heap sort                   */
/* ************************************************************** */
/*+ BSheap_sort0 - Sort keys from lowest to highest

    Input Parameters:
.   n - the number of keys
.   key - the keys to sort

    Output Parameters:
.   key - the sorted keys

    Returns:
    void

+*/
void BSheap_sort0(int n, int *key)
{
	int i;
	int	lheap, rheap;
	int	mid, m, x;

	/* heapify this array */
	mid = n/2;
	for (i=mid-1;i>=0;i--) {
		x = key[i];
		lheap = i;
		rheap = n-1;
		m = (lheap*2)+1;
		while (m <= rheap) {
			if (m < rheap) {
				if (key[m] < key[m+1]) {
					m++;
				}
			}
			if (x >= key[m]) {
				m = rheap+1;
			} else {
				key[lheap] = key[m];
				lheap = m;
				m = (2*lheap)+1;
			}
		}
		key[lheap] = x;
	}

	for (i=n-1;i>0;i--) {
		x = key[i];
		key[i] = key[0];
		lheap = 0;
		rheap = i-1;
		m = 1;
		while (m <= rheap) {
			if (m < rheap) {
				if (key[m] < key[m+1]) {
					m++;
				}
			}
			if (x >= key[m]) {
				m = rheap+1;
			} else {
				key[lheap] = key[m];
				lheap = m;
				m = (2*lheap)+1;
			}
		}
		key[lheap] = x;
	}
}

/*+ BSheap_sort1 - Sort keys from lowest to highest (with 1 data)

    Input Parameters:
.   n - the number of keys
.   key - the keys to sort
.   data1 - the data to sort by key

    Output Parameters:
.   key - the sorted keys
.   data1 - the data sorted by key

    Returns:
    void

+*/
void BSheap_sort1(int n, int *key, int *data1)
{
	int i;
	int	lheap, rheap;
	int	mid, m, x;
	int	xd1;

	/* heapify this array */
	mid = n/2;
	for (i=mid-1;i>=0;i--) {
		x = key[i];
		xd1 = data1[i];
		lheap = i;
		rheap = n-1;
		m = (lheap*2)+1;
		while (m <= rheap) {
			if (m < rheap) {
				if (key[m] < key[m+1]) {
					m++;
				}
			}
			if (x >= key[m]) {
				m = rheap+1;
			} else {
				key[lheap] = key[m];
				data1[lheap] = data1[m];
				lheap = m;
				m = (2*lheap)+1;
			}
		}
		key[lheap] = x;
		data1[lheap] = xd1;
	}

	for (i=n-1;i>0;i--) {
		x = key[i];
		xd1 = data1[i];
		key[i] = key[0];
		data1[i] = data1[0];
		lheap = 0;
		rheap = i-1;
		m = 1;
		while (m <= rheap) {
			if (m < rheap) {
				if (key[m] < key[m+1]) {
					m++;
				}
			}
			if (x >= key[m]) {
				m = rheap+1;
			} else {
				key[lheap] = key[m];
				data1[lheap] = data1[m];
				lheap = m;
				m = (2*lheap)+1;
			}
		}
		key[lheap] = x;
		data1[lheap] = xd1;
	}
}

/*+ BSheap_sort2 - Sort keys from lowest to highest (with 2 data)

    Input Parameters:
.   n - the number of keys
.   key - the keys to sort
.   data1 - the data to sort by key
.   data2 - the data to sort by key

    Output Parameters:
.   key - the sorted keys
.   data1 - the data sorted by key
.   data2 - the data sorted by key

    Returns:
    void

+*/
void BSheap_sort2(int n, int *key, int *data1, int *data2)
{
	int i;
	int	lheap, rheap;
	int	mid, m, x;
	int	xd1, xd2;

	/* heapify this array */
	mid = n/2;
	for (i=mid-1;i>=0;i--) {
		x = key[i];
		xd1 = data1[i];
		xd2 = data2[i];
		lheap = i;
		rheap = n-1;
		m = (lheap*2)+1;
		while (m <= rheap) {
			if (m < rheap) {
				if (key[m] < key[m+1]) {
					m++;
				}
			}
			if (x >= key[m]) {
				m = rheap+1;
			} else {
				key[lheap] = key[m];
				data1[lheap] = data1[m];
				data2[lheap] = data2[m];
				lheap = m;
				m = (2*lheap)+1;
			}
		}
		key[lheap] = x;
		data1[lheap] = xd1;
		data2[lheap] = xd2;
	}

	for (i=n-1;i>0;i--) {
		x = key[i];
		xd1 = data1[i];
		xd2 = data2[i];
		key[i] = key[0];
		data1[i] = data1[0];
		data2[i] = data2[0];
		lheap = 0;
		rheap = i-1;
		m = 1;
		while (m <= rheap) {
			if (m < rheap) {
				if (key[m] < key[m+1]) {
					m++;
				}
			}
			if (x >= key[m]) {
				m = rheap+1;
			} else {
				key[lheap] = key[m];
				data1[lheap] = data1[m];
				data2[lheap] = data2[m];
				lheap = m;
				m = (2*lheap)+1;
			}
		}
		key[lheap] = x;
		data1[lheap] = xd1;
		data2[lheap] = xd2;
	}
}

/*+ BSheap_sorthl1 - Sort keys from highest to lowest (with 1 data)

    Input Parameters:
.   n - the number of keys
.   key - the keys to sort
.   data1 - the data to sort by key

    Output Parameters:
.   key - the sorted keys
.   data1 - the data sorted by key

    Returns:
    void

+*/
void BSheap_sorthl1(int n, int *key, int *data1)
{
	int i;
	int	lheap, rheap;
	int	mid, m, x;
	int	xd1;

	/* heapify this array */
	mid = n/2;
	for (i=mid-1;i>=0;i--) {
		x = key[i];
		xd1 = data1[i];
		lheap = i;
		rheap = n-1;
		m = (lheap*2)+1;
		while (m <= rheap) {
			if (m < rheap) {
				if (key[m] > key[m+1]) {
					m++;
				}
			}
			if (x <= key[m]) {
				m = rheap+1;
			} else {
				key[lheap] = key[m];
				data1[lheap] = data1[m];
				lheap = m;
				m = (2*lheap)+1;
			}
		}
		key[lheap] = x;
		data1[lheap] = xd1;
	}

	for (i=n-1;i>0;i--) {
		x = key[i];
		xd1 = data1[i];
		key[i] = key[0];
		data1[i] = data1[0];
		lheap = 0;
		rheap = i-1;
		m = 1;
		while (m <= rheap) {
			if (m < rheap) {
				if (key[m] > key[m+1]) {
					m++;
				}
			}
			if (x <= key[m]) {
				m = rheap+1;
			} else {
				key[lheap] = key[m];
				data1[lheap] = data1[m];
				lheap = m;
				m = (2*lheap)+1;
			}
		}
		key[lheap] = x;
		data1[lheap] = xd1;
	}
}

/* sort from lowest to highest, the data is floating point */
/*+ BSheap_sort1d - Sort keys from lowest to highest (with 1 DP data)

    Input Parameters:
.   n - the number of keys
.   key - the keys to sort
.   data1 - the data to sort by key

    Output Parameters:
.   key - the sorted keys
.   data1 - the data sorted by key

    Returns:
    void

+*/
void BSheap_sort1d(int n, int *key, FLOAT *data1)
{
	int i;
	int	lheap, rheap;
	int	mid, m, x;
	FLOAT xd1;

	/* heapify this array */
	mid = n/2;
	for (i=mid-1;i>=0;i--) {
		x = key[i];
		xd1 = data1[i];
		lheap = i;
		rheap = n-1;
		m = (lheap*2)+1;
		while (m <= rheap) {
			if (m < rheap) {
				if (key[m] < key[m+1]) {
					m++;
				}
			}
			if (x >= key[m]) {
				m = rheap+1;
			} else {
				key[lheap] = key[m];
				data1[lheap] = data1[m];
				lheap = m;
				m = (2*lheap)+1;
			}
		}
		key[lheap] = x;
		data1[lheap] = xd1;
	}

	for (i=n-1;i>0;i--) {
		x = key[i];
		xd1 = data1[i];
		key[i] = key[0];
		data1[i] = data1[0];
		lheap = 0;
		rheap = i-1;
		m = 1;
		while (m <= rheap) {
			if (m < rheap) {
				if (key[m] < key[m+1]) {
					m++;
				}
			}
			if (x >= key[m]) {
				m = rheap+1;
			} else {
				key[lheap] = key[m];
				data1[lheap] = data1[m];
				lheap = m;
				m = (2*lheap)+1;
			}
		}
		key[lheap] = x;
		data1[lheap] = xd1;
	}
}

/*+ BSiheap_sort2 - Sort keys from lowest to highest using 2 indirect keys

    Input Parameters:
.   n - the number of keys
.   key - the keys to sort
.   ikey1 - the primary indirect key to sort by
.   ikey2 - the secondary indirect key to sort by

    Output Parameters:
.   key - the sorted keys

    Returns:
    void

+*/
void BSiheap_sort2(int n, int *key, int *ikey1, int *ikey2)
{
	int i;
	int	lheap, rheap;
	int	mid, m, x;

	/* heapify this array */
	mid = n/2;
	for (i=mid-1;i>=0;i--) {
		x = key[i];
		lheap = i;
		rheap = n-1;
		m = (lheap*2)+1;
		while (m <= rheap) {
			if (m < rheap) {
				/* if (key[m] < key[m+1]) */
				if ((ikey1[key[m]] < ikey1[key[m+1]]) || 
					((ikey1[key[m]] == ikey1[key[m+1]]) && 
					(ikey2[key[m]] < ikey2[key[m+1]]))) {
					m++;
				}
			}
			/* if (x >= key[m]) */
			if (!((ikey1[x] < ikey1[key[m]]) || 
				((ikey1[x] == ikey1[key[m]]) && 
				(ikey2[x] < ikey2[key[m]])))) {
				m = rheap+1;
			} else {
				key[lheap] = key[m];
				lheap = m;
				m = (2*lheap)+1;
			}
		}
		key[lheap] = x;
	}

	for (i=n-1;i>0;i--) {
		x = key[i];
		key[i] = key[0];
		lheap = 0;
		rheap = i-1;
		m = 1;
		while (m <= rheap) {
			if (m < rheap) {
				/*if (key[m] < key[m+1]) */
				if ((ikey1[key[m]] < ikey1[key[m+1]]) || 
					((ikey1[key[m]] == ikey1[key[m+1]]) && 
					(ikey2[key[m]] < ikey2[key[m+1]]))) {
					m++;
				}
			}
			/*if (x >= key[m]) */
			if (!((ikey1[x] < ikey1[key[m]]) || 
				((ikey1[x] == ikey1[key[m]]) && 
				(ikey2[x] < ikey2[key[m]])))) {
				m = rheap+1;
			} else {
				key[lheap] = key[m];
				lheap = m;
				m = (2*lheap)+1;
			}
		}
		key[lheap] = x;
	}
}

/*+ BSiheap_sort1 - Sort keys from lowest to highest using 1 indirect key

    Input Parameters:
.   n - the number of keys
.   key - the keys to sort
.   ikey1 - the primary indirect key to sort by

    Output Parameters:
.   key - the sorted keys

    Returns:
    void

+*/
void BSiheap_sort1(int n, int *key, int *ikey1)
{
	int i;
	int	lheap, rheap;
	int	mid, m, x;

	/* heapify this array */
	mid = n/2;
	for (i=mid-1;i>=0;i--) {
		x = key[i];
		lheap = i;
		rheap = n-1;
		m = (lheap*2)+1;
		while (m <= rheap) {
			if (m < rheap) {
				/* if (key[m] < key[m+1]) */
				if (ikey1[key[m]] < ikey1[key[m+1]]) {
					m++;
				}
			}
			/* if (x >= key[m]) */
			if (ikey1[x] >= ikey1[key[m]]) {
				m = rheap+1;
			} else {
				key[lheap] = key[m];
				lheap = m;
				m = (2*lheap)+1;
			}
		}
		key[lheap] = x;
	}

	for (i=n-1;i>0;i--) {
		x = key[i];
		key[i] = key[0];
		lheap = 0;
		rheap = i-1;
		m = 1;
		while (m <= rheap) {
			if (m < rheap) {
				/*if (key[m] < key[m+1]) */
				if (ikey1[key[m]] < ikey1[key[m+1]]) {
					m++;
				}
			}
			/*if (x >= key[m]) */
			if (ikey1[x] >= ikey1[key[m]]) {
				m = rheap+1;
			} else {
				key[lheap] = key[m];
				lheap = m;
				m = (2*lheap)+1;
			}
		}
		key[lheap] = x;
	}
}