// Copyright (c) 1997-2009 Nokia Corporation and/or its subsidiary(-ies).

// All rights reserved.

// This component and the accompanying materials are made available

// under the terms of "Eclipse Public License v1.0"

// which accompanies this distribution, and is available

// at the URL "http://www.eclipse.org/legal/epl-v10.html".

//

// Initial Contributors:

// Nokia Corporation - initial contribution.

//

// Contributors:

//

// Description:

// Map ANSI bsearch and qsort onto EPOC32 functions

// 

//

#include <e32std.h>

#include <stdlib.h>

NONSHARABLE_CLASS(TAnsiKey) : public TKey

	{

public:

	TAnsiKey(const TAny* key, const TAny* base, TInt length, TInt (*compar)(const TAny*, const TAny*))

		: iSearchKey(key), iCmp(compar)

		{ SetPtr(base); iKeyLength=length; }

	virtual TInt Compare(TInt aLeft,TInt aRight) const;

	virtual TAny *At(TInt anIndex) const;

private:

	const TAny* iSearchKey;

	TInt (*iCmp)(const TAny*, const TAny*);

	};

TInt TAnsiKey::Compare (TInt aLeft,TInt aRight) const

	{

	if (aRight==KIndexPtr)

		return (*iCmp)(At(aLeft),iSearchKey);

	else

		return (*iCmp)(At(aLeft),At(aRight));

	}

TAny* TAnsiKey::At (TInt aPos) const

	{

	return (TUint8*)iPtr+(aPos*iKeyLength);

	}

NONSHARABLE_CLASS(TAnsiSwap) : public TSwap

	{

public:

	TAnsiSwap(const TAny* base, TInt length) : iPtr(base), iLength(length) {}

	virtual void Swap(TInt aLeft,TInt aRight) const;

private:

	TUint8* At(TInt aPos) const {return (TUint8*)iPtr+(aPos*iLength);}

	const TAny* iPtr;

	TInt  iLength;

	};

void TAnsiSwap::Swap(TInt aLeft,TInt aRight) const

	{

	TUint8* left=At(aLeft);

	TUint8* right=At(aRight);

	TUint8 tmp;

	for (TInt i=iLength; i>0; i--)

		{

		tmp=*left;

		*left++=*right;

		*right++=tmp;

		}

	}

extern "C" {

/*

FUNCTION

<<bsearch>>---binary search

INDEX

	bsearch

ANSI_SYNOPSIS

	#include <stdlib.h>

	void *bsearch(const void *<[key]>, const void *<[base]>,

		size_t <[nmemb]>, size_t <[size]>,

		int (*<[compar]>)(const void *, const void *));

TRAD_SYNOPSIS

	#include <stdlib.h>

	char *bsearch(<[key]>, <[base]>, <[nmemb]>, <[size]>, <[compar]>)

	char *<[key]>;

	char *<[base]>;

	size_t <[nmemb]>, <[size]>;

	int (*<[compar]>)();

DESCRIPTION

<<bsearch>> searches an array beginning at <[base]> for any element

that matches <[key]>, using binary search.  <[nmemb]> is the element

count of the array; <[size]> is the size of each element.

The array must be sorted in ascending order with respect to the

comparison function <[compar]> (which you supply as the last argument of

<<bsearch>>).

You must define the comparison function <<(*<[compar]>)>> to have two

arguments; its result must be negative if the first argument is

less than the second, zero if the two arguments match, and

positive if the first argument is greater than the second (where

``less than'' and ``greater than'' refer to whatever arbitrary

ordering is appropriate).

RETURNS

Returns a pointer to an element of <[array]> that matches <[key]>.  If

more than one matching element is available, the result may point to

any of them. Returns NULL if no matching element is found.

PORTABILITY

<<bsearch>> is ANSI.

No supporting OS subroutines are required.

*/

/**

searches an array beginning at <[base]> for any element

that matches <[key]>, using binary search

@return a pointer to an element of <[array]> that matches <[key]>.  If

more than one matching element is available, the result may point to

any of them. Returns NULL if no matching element is found.

@param key

@param base

@param nmemb

@param size

*/

EXPORT_C void* bsearch (const void* key, const void* base, size_t nmemb, size_t size,

	int (*compar)(const void*, const void*))

	{

	TAnsiKey searchMe(key, base, size, compar);

	TInt result=KIndexPtr;

	TInt r=User::BinarySearch(nmemb, searchMe, result);

	if (r==0)

		return searchMe.At(result);

	else

		return NULL;

	}

/*

FUNCTION

<<qsort>>---sort an array

INDEX

	qsort

ANSI_SYNOPSIS

	#include <stdlib.h>

	void qsort(void *<[base]>, size_t <[nmemb]>, size_t <[size]>,

		   int (*<[compar]>)(const void *, const void *) );

TRAD_SYNOPSIS

	#include <stdlib.h>

	qsort(<[base]>, <[nmemb]>, <[size]>, <[compar]> )

	char *<[base]>;

	size_t <[nmemb]>;

	size_t <[size]>;

	int (*<[compar]>)();

DESCRIPTION

<<qsort>> sorts an array (beginning at <[base]>) of <[nmemb]> objects.

<[size]> describes the size of each element of the array.

You must supply a pointer to a comparison function, using the argument

shown as <[compar]>.  (This permits sorting objects of unknown

properties.)  Define the comparison function to accept two arguments,

each a pointer to an element of the array starting at <[base]>.  The

result of <<(*<[compar]>)>> must be negative if the first argument is

less than the second, zero if the two arguments match, and positive if

the first argument is greater than the second (where ``less than'' and

``greater than'' refer to whatever arbitrary ordering is appropriate).

The array is sorted in place; that is, when <<qsort>> returns, the

array elements beginning at <[base]> have been reordered.

RETURNS

<<qsort>> does not return a result.

PORTABILITY

<<qsort>> is required by ANSI (without specifying the sorting algorithm).

*/

/**

Sort an array.

@param base 

@param nmemb

@param size describes the size of each element of the array

*/

EXPORT_C void qsort (void* base, size_t nmemb, size_t size,

	int (*compar)(const void*, const void*))

	{

	TAnsiKey  searchMe(NULL, base, size, compar);

	TAnsiSwap swapUs(base,size);

	User::QuickSort(nmemb, searchMe, swapUs);

	return;

	}

} // extern "C"