/*
 * TLGB_BinSearch.c
 *
 *  Created on: 22/dic/2015
 *      Author: gozzini.davide
 */


//==============================================================================
// Include files

#include "limits.h"
#include "string.h"

#include "TLGB/TLGB_BinSearch.h"

//==============================================================================
// Constants

//==============================================================================
// Types

//==============================================================================
// Static global variables

//==============================================================================
// Static functions

//==============================================================================
// Global variables

//==============================================================================
// Global functions

int ShortCompare(void *a, void *b)
{
    if (*(short *)a < *(short *)b) return -1;
    if (*(short *)a > *(short *)b) return  1;
    return 0;
}

int IntCompare(void *a, void *b)
{
   if (*(int *)a < *(int *)b) return -1;
   if (*(int *)a > *(int *)b) return  1;
   return 0;
}

int FloatCompare(void *a, void *b)
{
   if (*(float *)a < *(float *)b) return -1;
   if (*(float *)a > *(float *)b) return  1;
   return 0;
}

int DoubleCompare(void *a, void *b)
{
   if (*(double *)a < *(double *)b) return -1;
   if (*(double *)a > *(double *)b) return  1;
   return 0;
}

int CStringCompare(void *a, void *b)
{
    return strcmp(*(char **)a, *(char **)b);
}

//  Used to compare list elements by their raw data contents
int ListMemBlockCmp(void *a, void *b, unsigned int size)
{
    return memcmp(a, b, size);
}

/// HIFN Performs a binary search in an array of numberOfElements items of size elementSize.
/// HIFN Important: The binary search algorithm assumes that the array is already sorted in ascending order.
/// HIFN This function is like the C Library bsearch function except that this function returns the index where the item should be placed if it is not found.
/// HIPAR *array/Pass the array of items that BinSearch will search.
/// HIPAR *array/Important: The binary search algorithm assumes that the array is already sorted in ascending order.
/// HIPAR numElements/Pass the number of items in the array.
/// HIPAR elementSize/Pass the item size (in bytes) for the items in the array.
/// HIPAR *itemPtr/Pass a pointer to the item to search for in the array.
/// HIPAR compareFunction/Pass a comparison function that BinSearch should use to compare items in the array to the item pointed to by itemPointer.
/// HIPAR compareFunction/The comparison function should have the following prototype:
/// HIPAR compareFunction/int CVICALLBACK CompareFunction (void *item1, void *item2);
/// HIPAR compareFunction/The comparison function should return a negative number if item1 is less than item2, it should return 0 if item1 is equal to item2, and it should return a positive number if item1 is greater than item2. When the comparison function is called, item1 is always the item pointer passed to BinSearch and item2 is always a pointer to an element in the array passed to BinSearch.
/// HIPAR compareFunction/This instrument driver provides several commonly useful comparison functions:
/// HIPAR compareFunction/ShortCompare
/// HIPAR compareFunction/IntCompare
/// HIPAR compareFunction/FloatCompare
/// HIPAR compareFunction/DoubleCompare
/// HIPAR compareFunction/CStringCompare
/// HIPAR compareFunction/CStringNoCaseCompare
/// HIRET result ssize_t Returns the index of the array element that matches the item (from 0 to numberOfElements – 1).
/// HIRET If no match is found, it returns where the item should be placed if it were to be inserted in order, –i – 1 where i is the index (0 to numElements).
long BinSearch(const void *array, unsigned int numElements, unsigned int elementSize, const void *itemPtr, CompareFunction compareFunction)
{
    int	 cmp;
	long low;
	long high;
	long mid;
	long retVal;
    void *arrayItemPtr;

	if (numElements > INT_MAX)
	{
		return -1;
	}

    for(low=0, high= (long)numElements-1, mid=0, cmp= -1; low <= high; )
    {
        mid = (low + high) >> 1;

        arrayItemPtr = (void *) (((char *)array) + (mid*elementSize));

        if(compareFunction)
		{
			cmp = compareFunction((void *)itemPtr, arrayItemPtr);
		}
		else
		{
			cmp = ListMemBlockCmp((void *)itemPtr, arrayItemPtr, elementSize);
		}

        if (cmp == 0)
        {
            return mid;
        }
        else if (cmp < 0)
		{
			high= mid - 1;
		}
		else if (cmp > 0)
		{
			low= mid + 1;
		}
    }

    if (cmp > 0)
    {
        mid++;
    }

	retVal = -mid - 1;
	return retVal;
}

