//------------------------------------------------------------------------------
//	Copyright (C) 2007, 2009 Humboldt-Universitaet zu Berlin
//
//	This library is free software; you can redistribute it and/or
//	modify it under the terms of the GNU Lesser General Public
//	License as published by the Free Software Foundation; either
//	version 2.1 of the License, or (at your option) any later version.
//
//	This library is distributed in the hope that it will be useful,
//	but WITHOUT ANY WARRANTY; without even the implied warranty of
//	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
//	Lesser General Public License for more details.
//
//	You should have received a copy of the GNU Lesser General Public
//	License along with this library; if not, write to the Free Software
//	Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
//------------------------------------------------------------------------------

/**
 * @file ListInSort.h
 * @author Ronald Kluth
 * @date created at 2007/11/08
 * @brief Declaration and Implementation of odemx::ListInSort
 * @since 2.1
 */

#ifndef ODEMX_UTIL_LISTINSORT_INCLUDED
#define ODEMX_UTIL_LISTINSORT_INCLUDED

#include <list>
#include <algorithm>

namespace odemx {

/**
	\brief Function template for sorted insertion in std::list<> container

	\param list
		reference to std::list<> container

	\param newElement
		the element to be sorted into the given list

	\param cmp
		the chosen comparison functor by which the list is ordered

	\param fifo
		use FIFO or LIFO strategy

	ListInSort is used for insertion of Sched objects into a
	std::list< Sched* >	container by the ExecutionList. It is also
	employed to sort a ProcessQueue of type std::list< Process* >
	using a user-defined predicate as sorting criterion.

	\sa DefaultCmp, QPriorityCmp
*/
template < typename ListElementType, typename ComparisonFunctorType >
typename std::list< ListElementType >::iterator
inline ListInSort( std::list< ListElementType >& l,
				   ListElementType newElement,
				   ComparisonFunctorType& cmp,
				   bool fifo = true )
{
	// an iterator to store the position
	// where the new element should be inserted
	typename std::list< ListElementType >::iterator insertLocation;

	// according to fifo or lifo, the new element is inserted
	// either at the end or at the beginning of the possible range
	// the insert location is determined by standard algorithms
	if( fifo )
		insertLocation = std::upper_bound( l.begin(), l.end(), newElement, cmp );
	else // lifo
		insertLocation = std::lower_bound( l.begin(), l.end(), newElement, cmp );

	// insert returns an iterator to the location
	// where the new element was placed in the list
	return l.insert( insertLocation, newElement );
}

} // namespace odemx

#endif /* ODEMX_UTIL_LISTINSORT_INCLUDED */
