/*

* Copyright (c) 2001-2006 Nokia Corporation and/or its subsidiary(-ies).

* All rights reserved.

* This component and the accompanying materials are made available

* under the terms of the License "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:  EAP and WLAN authentication protocols.

*

*/

#if !defined(_EAP_SORT_H_)

#define _EAP_SORT_H_

#include "eap_am_memory.h"

#include "eap_tools.h"

#include "eap_am_tools.h"

#include "eap_automatic_variable.h"

/** @file */

//--------------------------------------------------

/**

 * This template function copies array of objects from first to last

 * to array of objects ending to result.

 * Parameter first point to the first object of the source array.

 * Parameter last points the next address after the last object of source array.

 * Parameter result points the next address after the last object of the result array.

 */

template <class Type>

void eap_sort_copy_backward(

	const Type * const first,

	const Type *last,

	Type *result )

{

	while (first != last)

	{

		*--result = *--last;

	}

}

//--------------------------------------------------

/**

 * 

 */

template <class Type>

void eap_sort_unguarded_linear_insert(

	Type *last,

	const Type inserted_object,

	bool (*compare_first_is_smaller)(

		const Type * const first,

		const Type * const second,

		abs_eap_am_tools_c * const m_am_tools),

	abs_eap_am_tools_c * const m_am_tools)

{

	Type *next = last;

	--next;

	while(compare_first_is_smaller(&inserted_object, next, m_am_tools) == true)

	{

		*last = *next;

		last = next--;

	}

	*last = inserted_object;

}

//--------------------------------------------------

template <class Type>

void eap_sort_linear_insert(

	Type * const first,

	Type * const last,

	bool (*compare_first_is_smaller)(

		const Type * const first,

		const Type * const second,

		abs_eap_am_tools_c * const m_am_tools),

	abs_eap_am_tools_c * const m_am_tools)

{

	const Type value = *last;

	if(compare_first_is_smaller(&value, first, m_am_tools) == true)

	{

		eap_sort_copy_backward(first, last, last+1);

		*first = value;

	}

	else

	{

		eap_sort_unguarded_linear_insert(last, value, compare_first_is_smaller, m_am_tools);

	}

}

//--------------------------------------------------

template <class Type>

void eap_sort_insert_sort_area(

	Type * const first,

	const Type *last,

	bool (*compare_first_is_smaller)(

		const Type * const first,

		const Type * const second,

		abs_eap_am_tools_c * const m_am_tools),

	abs_eap_am_tools_c * const m_am_tools)

{

	Type *tmp;

	++last;

	for( tmp = first+1; tmp < last; tmp++ )

	{

		eap_sort_linear_insert( first, tmp, compare_first_is_smaller, m_am_tools);

	}

}

//------------------------------------------------------------

template <class Type>

Type *eap_sort_divide_area(

	Type *start,

	Type *finish,

	bool (*compare_first_is_smaller)(

		const Type * const first,

		const Type * const second,

		abs_eap_am_tools_c * const m_am_tools),

	abs_eap_am_tools_c * const m_am_tools)

{

	// selects the boundary object.

	const Type boundary = *(start+((finish - start)/2));

	Type change;

	start--;

	finish++;

	// Boundary is used as a middle object.

	for(;;)

	{

		// Examine from begin to end is ++start smaller than boundary.

		while(compare_first_is_smaller(++start, &boundary, m_am_tools) == true)

		{

			// Nothing to do.

		}

		// Examine from end to begin is --finish bigger than boundary.

		while(compare_first_is_smaller(&boundary, --finish, m_am_tools) == true)

		{

			// Nothing to do.

		}

		if( start < finish )

		{

			// In case boundary isn't reached, it intent that two

			// atom mutual side of boundary are in wrong order,

			// so swap them.

			change = *start;

			*start = *finish;

			*finish = change;

		}

		else

		{

			// Start and finish pointers are overlapping.

			// Terminate loop and return pointer to finish.

			return( finish );

		}

	} // for()

}

//--------------------------------------------------

/**

 * This function does quick-sort with non-recurvive alorithm.

 * Parameter array is pointer to array including objects of type Type.

 * Parameter object_count is count of objects in the array.

 * Parameter compare_first_is_smaller is pointer to a function that compares objects of type Type.

 */

template <class Type>

eap_status_e eap_sort_array(

	Type * const array,

	const u32_t object_count,

	bool (*compare_first_is_smaller)(

		const Type * const first,

		const Type * const second,

		abs_eap_am_tools_c * const m_am_tools),

	abs_eap_am_tools_c * const m_am_tools)

{

	EAP_TRACE_BEGIN(m_am_tools, TRACE_FLAGS_DEFAULT);

	eap_status_e status = eap_status_ok; // Note original_array may be empty or it includes only one object, then sort will not be run. 

	if (object_count < 2ul)

	{

		EAP_TRACE_END(m_am_tools, TRACE_FLAGS_DEFAULT);

		return EAP_STATUS_RETURN(m_am_tools, status);

	}

	const u32_t quicksort_finish = 10ul;

	// When there are atoms in the array fewer than quicksort_finish,

	// then the array is sorted directly by eap_sort_insert_sort_area() function.

	if (object_count >= quicksort_finish)

	{

		Type ** const sort_array = new Type *[object_count+1];

		eap_automatic_array_variable_c<Type *> automatic_sort_array(m_am_tools, sort_array);

		if (sort_array == 0)

		{

			EAP_TRACE_END(m_am_tools, TRACE_FLAGS_DEFAULT);

			return EAP_STATUS_RETURN(m_am_tools, eap_status_allocation_error);

		}

		// first atom

		Type *start = array;

		// last point to the first address after the last atom.

		Type *last = array+object_count;

		Type *finish = last - 1;

		sort_array[finish-array] = finish;

		// We continue until start come real array's end.

		while (last != start)

		{

			if (static_cast<u32_t>(finish - start) > quicksort_finish)

			{

				Type *upper = eap_sort_divide_area(start, finish , compare_first_is_smaller, m_am_tools);

				// When is at least two unit in beginning.

				// Divide sorting area under upper address.

				// Upper areas end points are saved to sort_array.

				sort_array[upper+1-array] = finish;

				// New sorting area.

				// New start address is the same as start pointer of previous sort area.

				// New finish address is preceding address of upper address.

				finish = upper;

			}

			else

			{

				eap_sort_insert_sort_area(start, finish , compare_first_is_smaller, m_am_tools);

				start = ++finish;

				finish = sort_array[start-array];

			}

		} // while ( last != start )

	}

	else

	{

		eap_sort_insert_sort_area(array, array+(object_count-1), compare_first_is_smaller, m_am_tools);

	}

	EAP_TRACE_END(m_am_tools, TRACE_FLAGS_DEFAULT);

	return EAP_STATUS_RETURN(m_am_tools, status);

}

//--------------------------------------------------

#endif //#if !defined(_EAP_SORT_H_)

//--------------------------------------------------

// End.