/* HEAP BASED TOP-K */
#ifndef __WDONG_TOPK__
#define __WDONG_TOPK__

#include <stdlib.h>

typedef struct {
	uint32_t key;
	uint32_t index;
} itopk_t;

typedef struct {
	float key;
	uint32_t index;
} ftopk_t;

/* prefix_ge (type a, type b) is needed */

#define QUICKSORT_PROTOTYPE(prefix, type)					\
void prefix##_qsort(type *, cass_size_t)

#define QUICKSORT_GENERATE(prefix, type)					\
static void prefix##_qsort_help(type *numbers, cass_size_t left, cass_size_t right)	\
{										\
  cass_size_t pivot, l_hold, r_hold;							\
  type pivot_v;									\
  l_hold = left;								\
  r_hold = right;								\
  pivot_v = numbers[left];							\
  while (left < right) {							\
    while (prefix##_ge(numbers[right], pivot_v) && (left < right)) right--;	\
    if (left != right) {							\
      numbers[left] = numbers[right];						\
      left++;									\
    }										\
    while (prefix##_ge(pivot_v, numbers[left]) && (left < right)) left++;	\
    if (left != right) {							\
      numbers[right] = numbers[left];						\
      right--;									\
    }										\
  }										\
  numbers[left] = pivot_v;							\
  pivot = left;									\
  if (l_hold < pivot) prefix##_qsort_help(numbers, l_hold, pivot-1);		\
  if (r_hold > pivot) prefix##_qsort_help(numbers, pivot+1, r_hold);		\
}										\
										\
void prefix##_qsort(type* numbers, cass_size_t array_size) {				\
  prefix##_qsort_help(numbers, 0, array_size - 1);				\
}

/**
  The top-k package works on an array of structures.  The structure has an field 'key',
  which can be compared by ">".

  The struct need not necessarily be itopk_t or ftopk_t.
  */


/* Initialize a top-k array.  The array should have k elements.  The value "minimal"
   is considered -inf, and should not be used by a real array element. */
#define TOPK_INIT(array, key, k, minimal)		\
	do {						\
		int iiii;				\
		for (iiii = 0; iiii < (k); iiii++) {	\
			(array)[iiii].key = (minimal);	\
		}					\
	} while (0)					\

#define TOPK_INSERT_MAX(array, key, k, el)		\
	({						\
	int inserted = 0;				\
	do {						\
		int iiii, llll, rrrr;			\
		if ((el).key < (array)[0].key) break;	\
		iiii = 0;				\
		for (;;) {				\
			llll = (iiii << 1) + 1;		\
			if (llll >= (k)) break;		\
			rrrr = llll + 1;		\
			if ((rrrr < (k)) && ((array)[rrrr].key < (array)[llll].key)) { \
				llll = rrrr;		\
			}				\
			if ((el).key < (array)[llll].key) break;	\
			(array)[iiii] = (array)[llll];	\
			iiii = llll;			\
		}					\
		(array)[iiii] = (el);			\
	 	inserted = 1;				\
	} while (0);					\
	inserted;					\
	})

#define TOPK_INSERT_MIN(array, key, k, el)		\
	do {						\
		int iiii, llll, rrrr;			\
		if ((el).key > (array)[0].key) break;	\
		iiii = 0;				\
		for (;;) {				\
			llll = (iiii << 1) + 1;		\
			if (llll >= (k)) break;		\
			rrrr = llll + 1;		\
			if ((rrrr < (k)) && ((array)[rrrr].key > (array)[llll].key)) { \
				llll = rrrr;		\
			}				\
			if ((el).key > (array)[llll].key) break;	\
			(array)[iiii] = (array)[llll];	\
			iiii = llll;			\
		}					\
		(array)[iiii] = (el);			\
	} while (0)

#define TOPK_INSERT_MIN_UNIQ(array, key, index, k, el)	\
	 do {						\
	 	int iiii, jjjj;				\
	 	iiii = jjjj = 0;			\
	 	while (iiii < k) {			\
	 		if ((el).key > (array)[iiii].key) break; \
	 		if ((el).index == (array)[iiii].index) { jjjj = 1; break; } \
	 		iiii++;				\
	 	}					\
	 	if (jjjj) break;			\
	 	if (iiii == 0) break;			\
		for (jjjj = 0; jjjj < iiii-1; jjjj++)	\
			(array)[jjjj] = (array)[jjjj+1];\
		(array)[jjjj] = el;			\
	 } while(0)

#define TOPK_INSERT_MIN_UNIQ_DO(array, key, index, k, el, stmt) \
	 do {						\
	 	int iiii, jjjj;				\
	 	iiii = jjjj = 0;			\
	 	while (iiii < k) {			\
	 		if ((el).key > (array)[iiii].key) break; \
	 		if ((el).index == (array)[iiii].index) { jjjj = 1; break; } \
	 		iiii++;				\
	 	}					\
	 	if (jjjj) break;			\
	 	if (iiii == 0) break;			\
		for (jjjj = 0; jjjj < iiii-1; jjjj++)	\
			(array)[jjjj] = (array)[jjjj+1];\
		(array)[jjjj] = el;			\
		 { stmt; }				\
	 } while(0)

#define TOPK_SORT_MIN(array, type, key, k)		\
	do {						\
 		int __last = k;				\
	 	type __el;				\
	 	int iiii, llll, rrrr;			\
	 	while (__last > 0) {			\
	 		__last--;			\
			__el = (array)[__last];		\
			(array)[__last] = (array)[0];	\
			iiii = 0;			\
			for (;;) {			\
				llll = (iiii << 1) + 1;	\
				if (llll >= __last) break;	\
				rrrr = llll + 1;	\
				if ((rrrr < __last) && ((array)[rrrr].key > (array)[llll].key)) { \
					llll = rrrr;	\
				}			\
				if (__el.key > (array)[llll].key) break;\
				(array)[iiii] = (array)[llll];	\
				iiii = llll;		\
			}				\
			(array)[iiii] = __el;		\
	 	}					\
	 } while (0)


QUICKSORT_PROTOTYPE(ftopk, ftopk_t);

QUICKSORT_PROTOTYPE(ftopk_rev, ftopk_t);

QUICKSORT_PROTOTYPE(itopk, itopk_t);

QUICKSORT_PROTOTYPE(itopk_rev, itopk_t);

#endif