#include "RndList.h"

#include <string.h>
#include <stdlib.h>

#include "WimpLib:Exception.h"
#include "WimpLib:mem.h"

typedef struct RndElem
{
	const char* value;
	uint32_t    index;
} RndElem;

// Array of RndElem, sorted by address for dichotomic search
struct RndList
{
	uint32_t   count;
	RndElem*   parray;
};

/**
 *  Returns a new RndList.
 */
RndList* throw_New_RndList(void)
{
	RndList* This = throw_mem_alloc(sizeof(*This));
	RndElem* pElem;

	try
	{
		This->parray = throw_mem_alloc(sizeof(RndElem));
	}
	catch
	{
		mem_free(This);
		throw_current();
	}
	catch_end

	// Insert NULL ptr first
	pElem = This->parray;
	pElem->value = NULL;
	pElem->index = 0;

	This->count = 1;

	return This;
}

/**
 * Deletes an RndList.
 */
void Delete_RndList(RndList* This)
{
	if (This)
	{
		mem_free(This->parray);
		mem_free(This);
	}
}

// Compare callback for qsort
static int compare(const void* pa, const void* pb)
{
	const RndElem* pra = pa;
	const RndElem* prb = pb;

	return pra->value - prb->value;
}

/**
 * Adds an ordered set to the list and in randomized order if necessary.
 */
void throw_RndList_AddSet(RndList* This, const OrderedSet* pSet, bool rnd)
{
	int count = OrderedSet_Count(pSet);
	int old_count = This->count;
	if (!count) return;

	RndElem* pElem = throw_mem_alloc(sizeof(RndElem) * (old_count + count));
	OrderedNode* pNode;
	int i;

	memcpy(pElem, This->parray, sizeof(RndElem) * old_count);
	mem_free(This->parray);
	This->parray = pElem;

	for ( pNode = OrderedSet_GetSuccessor(pSet, NULL)
	      , pElem = This->parray + old_count
	      , i = old_count
	    ; pNode != NULL
	    ; pNode = OrderedSet_GetSuccessor(pSet, pNode)
	      , pElem++
	      , i++)
	{
		pElem->value = OrderedSet_GetNodeData(pSet, pNode);
		pElem->index = i;
	}

	This->count = i;

	if (rnd)
	{
		for (i = old_count; i < This->count; i++)
		{
			float jj = ((float) rand()) / RAND_MAX;
			int j = old_count + (int) (jj * count);
			uint32_t k = This->parray[i].index;
			if (j >= This->count) j = This->count - 1;
			This->parray[i].index = This->parray[j].index;
			This->parray[j].index = k;
		}
	}

	qsort(This->parray, This->count, sizeof(This->parray[0]), compare);
}

/**
 * Adds an array of pointers to the list and in randomized order if necessary.
 */
void throw_RndList_AddArray(RndList* This, const void** parray, int count, bool rnd)
{
	int old_count = This->count;
	if (!count) return;

	RndElem* pElem = throw_mem_alloc(sizeof(RndElem) * (old_count + count));
	int i;

	memcpy(pElem, This->parray, sizeof(RndElem) * old_count);
	mem_free(This->parray);
	This->parray = pElem;
	This->count += count;

	for ( pElem = This->parray + old_count
	      , i = old_count
	    ; i < This->count
	    ; parray++
	      , pElem++
	      , i++)
	{
		pElem->value = *parray;
		pElem->index = i;
	}

	if (rnd)
	{
		for (i = old_count; i < This->count; i++)
		{
			float jj = ((float) rand()) / RAND_MAX;
			int j = old_count + (int) (jj * count);
			uint32_t k = This->parray[i].index;
			if (j >= This->count) j = This->count - 1;
			This->parray[i].index = This->parray[j].index;
			This->parray[j].index = k;
		}
	}

	qsort(This->parray, This->count, sizeof(This->parray[0]), compare);
}

/**
 * Finds an element by performing a dichotomic search on its address
 * and return its associated order.
 *
 * @param  pValue  Value to look up.
 *
 * @returns Order.
 */
uint32_t RndList_GetOrder(const RndList* This, const void* pValue)
{
	int i = 0;
	int k = This->count - 1;
	int j = (i + k) / 2;
	int val = This->parray[j].value - (const char*) pValue;

	while (i < j)
	{
		if (!val) return This->parray[j].index;
		else if (val > 0) k = j;
		else i = j;

	    j = (i + k) / 2;
		val = This->parray[j].value - (const char*) pValue;
	}

	if (!val) return This->parray[j].index;

	val = This->parray[k].value - (const char*) pValue;
	if (!val) return This->parray[k].index;

	// Not found
	return This->count;
}
