// algorithm standard header
#pragma once
#ifndef _ALGORITHM_
#define _ALGORITHM_
#ifndef RC_INVOKED
#include <memory>

 #pragma pack(push,_CRT_PACKING)
 #pragma warning(push,3)
 #pragma warning(disable: 4244)

_STD_BEGIN
		// COMMON SORT PARAMETERS
const int _ISORT_MAX = 32;	// maximum size for insertion sort

		// TEMPLATE FUNCTION for_each
template<class _InIt,
	class _Fn1> inline
	_Fn1 _For_each(_InIt _First, _InIt _Last, _Fn1 _Func)
	{	// perform function for each element
	for (; _First != _Last; ++_First)
		_Func(*_First);
	return (_Func);
	}

template<class _InIt,
	class _Fn1> inline
	_Fn1 for_each(_InIt _First, _InIt _Last, _Fn1 _Func)
	{	// perform function for each element
	_DEBUG_RANGE(_First, _Last);
	_DEBUG_POINTER(_Func);
	return (_For_each(_Unchecked(_First), _Unchecked(_Last), _Func));
	}

		// TEMPLATE FUNCTION find
template<class _InIt,
	class _Ty> inline
	_InIt _Find(_InIt _First, _InIt _Last, const _Ty& _Val)
	{	// find first matching _Val
	for (; _First != _Last; ++_First)
		if (*_First == _Val)
			break;
	return (_First);
	}

inline const char *_Find(const char *_First, const char *_Last, int _Val)
	{	// find first char that matches _Val
	_First = (const char *)_CSTD memchr(_First, _Val, _Last - _First);
	return (_First == 0 ? _Last : _First);
	}

inline const signed char *_Find(const signed char *_First,
	const signed char *_Last, int _Val)
	{	// find first signed char that matches _Val
	_First = (const signed char *)_CSTD memchr(_First, _Val,
		_Last - _First);
	return (_First == 0 ? _Last : _First);
	}

inline const unsigned char *_Find(const unsigned char *_First,
	const unsigned char *_Last, int _Val)
	{	// find first unsigned char that matches _Val
	_First = (const unsigned char *)_CSTD memchr(_First, _Val,
		_Last - _First);
	return (_First == 0 ? _Last : _First);
	}

template<class _InIt,
	class _Ty> inline
	_InIt find(_InIt _First, _InIt _Last, const _Ty& _Val)
	{	// find first matching _Val
	_DEBUG_RANGE(_First, _Last);
	return (_Rechecked(_First,
		_Find(_Unchecked(_First), _Unchecked(_Last), _Val)));
	}

		// TEMPLATE FUNCTION find_if
template<class _InIt,
	class _Pr> inline
	_InIt _Find_if(_InIt _First, _InIt _Last, _Pr _Pred)
	{	// find first satisfying _Pred
	for (; _First != _Last; ++_First)
		if (_Pred(*_First))
			break;
	return (_First);
	}

template<class _InIt,
	class _Pr> inline
	_InIt find_if(_InIt _First, _InIt _Last, _Pr _Pred)
	{	// find first satisfying _Pred
	_DEBUG_RANGE(_First, _Last);
	_DEBUG_POINTER(_Pred);
	return (_Rechecked(_First,
		_Find_if(_Unchecked(_First), _Unchecked(_Last), _Pred)));
	}

		// TEMPLATE FUNCTION adjacent_find
template<class _FwdIt> inline
	_FwdIt _Adjacent_find(_FwdIt _First, _FwdIt _Last)
	{	// find first matching successor
	if (_First != _Last)
		for (_FwdIt _Firstb; (_Firstb = _First), ++_First != _Last; )
			if (*_Firstb == *_First)
				return (_Firstb);
	return (_Last);
	}

template<class _FwdIt> inline
	_FwdIt adjacent_find(_FwdIt _First, _FwdIt _Last)
	{	// find first matching successor
	_DEBUG_RANGE(_First, _Last);
	return (_Rechecked(_First,
		_Adjacent_find(_Unchecked(_First), _Unchecked(_Last))));
	}

		// TEMPLATE FUNCTION adjacent_find WITH PRED
template<class _FwdIt,
	class _Pr> inline
	_FwdIt _Adjacent_find(_FwdIt _First, _FwdIt _Last, _Pr _Pred)
	{	// find first satisfying _Pred with successor
	if (_First != _Last)
		for (_FwdIt _Firstb; (_Firstb = _First), ++_First != _Last; )
			if (_Pred(*_Firstb, *_First))
				return (_Firstb);
	return (_Last);
	}

template<class _FwdIt,
	class _Pr> inline
	_FwdIt adjacent_find(_FwdIt _First, _FwdIt _Last, _Pr _Pred)
	{	// find first satisfying _Pred with successor
	_DEBUG_RANGE(_First, _Last);
	_DEBUG_POINTER(_Pred);
	return (_Rechecked(_First,
		_Adjacent_find(_Unchecked(_First), _Unchecked(_Last), _Pred)));
	}

		// TEMPLATE FUNCTION count
template<class _InIt,
	class _Ty> inline
	typename iterator_traits<_InIt>::difference_type
		_Count(_InIt _First, _InIt _Last, const _Ty& _Val)
	{	// count elements that match _Val
	typename iterator_traits<_InIt>::difference_type _Count = 0;

	for (; _First != _Last; ++_First)
		if (*_First == _Val)
			++_Count;
	return (_Count);
	}

template<class _InIt,
	class _Ty> inline
	typename iterator_traits<_InIt>::difference_type
		count(_InIt _First, _InIt _Last, const _Ty& _Val)
	{	// count elements that match _Val
	_DEBUG_RANGE(_First, _Last);
	return (_Count(_Unchecked(_First), _Unchecked(_Last), _Val));
	}

		// TEMPLATE FUNCTION count_if
template<class _InIt,
	class _Pr> inline
	typename iterator_traits<_InIt>::difference_type
		_Count_if(_InIt _First, _InIt _Last, _Pr _Pred)
	{	// count elements satisfying _Pred
	typename iterator_traits<_InIt>::difference_type _Count = 0;

	for (; _First != _Last; ++_First)
		if (_Pred(*_First))
			++_Count;
	return (_Count);
	}

template<class _InIt,
	class _Pr> inline
	typename iterator_traits<_InIt>::difference_type
		count_if(_InIt _First, _InIt _Last, _Pr _Pred)
	{	// count elements satisfying _Pred
	_DEBUG_RANGE(_First, _Last);
	_DEBUG_POINTER(_Pred);
	return (_Count_if(_Unchecked(_First), _Unchecked(_Last), _Pred));
	}

 #if _HAS_CPP0X
		// TEMPLATE FUNCTION all_of
template<class _InIt,
	class _Pr> inline
	bool _All_of(_InIt _First, _InIt _Last, _Pr _Pred)
	{	// test if all elements satisfy _Pred
	for (; _First != _Last; ++_First)
		if (!_Pred(*_First))
			return (false);
	return (true);
	}

template<class _InIt,
	class _Pr> inline
	bool all_of(_InIt _First, _InIt _Last, _Pr _Pred)
	{	// test if all elements satisfy _Pred
	_DEBUG_RANGE(_First, _Last);
	_DEBUG_POINTER(_Pred);
	return (_All_of(_Unchecked(_First), _Unchecked(_Last), _Pred));
	}

		// TEMPLATE FUNCTION any_of
template<class _InIt,
	class _Pr> inline
	bool _Any_of(_InIt _First, _InIt _Last, _Pr _Pred)
	{	// test if any element satisfies _Pred
	for (; _First != _Last; ++_First)
		if (_Pred(*_First))
			return (true);
	return (false);
	}

template<class _InIt,
	class _Pr> inline
	bool any_of(_InIt _First, _InIt _Last, _Pr _Pred)
	{	// test if any element satisfies _Pred
	_DEBUG_RANGE(_First, _Last);
	_DEBUG_POINTER(_Pred);
	return (_Any_of(_Unchecked(_First), _Unchecked(_Last), _Pred));
	}

		// TEMPLATE FUNCTION none_of
template<class _InIt,
	class _Pr> inline
	bool _None_of(_InIt _First, _InIt _Last, _Pr _Pred)
	{	// test if no elements satisfy _Pred
	for (; _First != _Last; ++_First)
		if (_Pred(*_First))
			return (false);
	return (true);
	}

template<class _InIt,
	class _Pr> inline
	bool none_of(_InIt _First, _InIt _Last, _Pr _Pred)
	{	// test if no elements satisfy _Pred
	_DEBUG_RANGE(_First, _Last);
	_DEBUG_POINTER(_Pred);
	return (_None_of(_Unchecked(_First), _Unchecked(_Last), _Pred));
	}

		// TEMPLATE FUNCTION find_if_not
template<class _InIt,
	class _Pr> inline
	_InIt _Find_if_not(_InIt _First, _InIt _Last, _Pr _Pred)
	{	// find first element that satisfies !_Pred
	for (; _First != _Last; ++_First)
		if (!_Pred(*_First))
			break;
	return (_First);
	}

template<class _InIt,
	class _Pr> inline
	_InIt find_if_not(_InIt _First, _InIt _Last, _Pr _Pred)
	{	// find first element that satisfies !_Pred
	_DEBUG_RANGE(_First, _Last);
	_DEBUG_POINTER(_Pred);
	return (_Rechecked(_First,
		_Find_if_not(_Unchecked(_First), _Unchecked(_Last), _Pred)));
	}

		// TEMPLATE FUNCTION copy_if
template<class _InIt,
	class _OutIt,
	class _Pr> inline
	_OutIt _Copy_if(_InIt _First, _InIt _Last, _OutIt _Dest,
		_Pr _Pred)
	{	// copy each satisfying _Pred
	for (; _First != _Last; ++_First)
		if (_Pred(*_First))
			*_Dest++ = *_First;
	return (_Dest);
	}

 #if _ITERATOR_DEBUG_LEVEL == 0
template<class _InIt,
	class _OutIt,
	class _Pr> inline
	_OutIt copy_if(_InIt _First, _InIt _Last, _OutIt _Dest,
		_Pr _Pred)
	{	// copy each satisfying _Pred
	return (_Copy_if(_Unchecked(_First), _Unchecked(_Last),
		_Dest, _Pred));
	}

 #else /* _ITERATOR_DEBUG_LEVEL == 0 */
template<class _InIt,
	class _OutIt,
	class _Pr> inline
	_OutIt _Copy_if(_InIt _First, _InIt _Last, _OutIt _Dest,
		_Pr _Pred, _STD tr1::true_type)
	{	// copy each satisfying _Pred, checked dest
	return (_Copy_if(_First, _Last,
		_Dest, _Pred));
	}

template<class _InIt,
	class _OutIt,
	class _Pr> inline
_SCL_INSECURE_DEPRECATE
	_OutIt _Copy_if(_InIt _First, _InIt _Last, _OutIt _Dest,
		_Pr _Pred, _STD tr1::false_type)
	{	// copy each satisfying _Pred, unchecked dest
	return (_Copy_if(_First, _Last,
		_Dest, _Pred));
	}

template<class _InIt,
	class _OutIt,
	class _Pr> inline
	_OutIt copy_if(_InIt _First, _InIt _Last, _OutIt _Dest,
		_Pr _Pred)
	{	// copy each satisfying _Pred
	_DEBUG_RANGE(_First, _Last);
	_DEBUG_POINTER(_Dest);
	_DEBUG_POINTER(_Pred);
	return (_STD _Copy_if(_Unchecked(_First), _Unchecked(_Last),
		_Dest, _Pred, _Is_checked(_Dest)));
	}

template<class _InIt,
	class _OutTy,
	size_t _OutSize,
	class _Pr> inline
	_OutTy *copy_if(_InIt _First, _InIt _Last, _OutTy (&_Dest)[_OutSize],
		_Pr _Pred)
	{	// copy each satisfying _Pred, array dest
	return (_Unchecked(
		_STD copy_if(_First, _Last,
			_Array_iterator<_OutTy, _OutSize>(_Dest), _Pred)));
	}

 #endif /* _ITERATOR_DEBUG_LEVEL == 0 */

		// TEMPLATE FUNCTION partition_copy
template<class _InIt,
	class _OutIt1,
	class _OutIt2,
	class _Pr> inline
	_STD pair<_OutIt1, _OutIt2>
		_Partition_copy(_InIt _First, _InIt _Last,
			_OutIt1 _Dest1, _OutIt2 _Dest2, _Pr _Pred)
	{	// copy true partition *_Dest1++, false to *_Dest2++
	for (; _First != _Last; ++_First)
		if (_Pred(*_First))
			*_Dest1++ = *_First;
		else
			*_Dest2++ = *_First;
	return (_STD pair<_OutIt1, _OutIt2>( _Dest1, _Dest2));
	}

 #if _ITERATOR_DEBUG_LEVEL == 0
template<class _InIt,
	class _OutIt1,
	class _OutIt2,
	class _Pr> inline
	_STD pair<_OutIt1, _OutIt2>
		partition_copy(_InIt _First, _InIt _Last,
			_OutIt1 _Dest1, _OutIt2 _Dest2, _Pr _Pred)
	{	// copy true partition *_Dest1++, false to *_Dest2++
	return (_STD pair<_OutIt1, _OutIt2>(
		_Partition_copy(_Unchecked(_First), _Unchecked(_Last),
			_Dest1, _Dest2, _Pred)));
	}

 #else /* _ITERATOR_DEBUG_LEVEL == 0 */
template<class _InIt,
	class _OutIt1,
	class _OutIt2,
	class _Pr> inline
	_STD pair<_OutIt1, _OutIt2>
		_Partition_copy(_InIt _First, _InIt _Last,
			_OutIt1 _Dest1, _OutIt2 _Dest2, _Pr _Pred,
			_STD tr1::true_type, _STD tr1::true_type)
	{	// copy true partition *_Dest1++, false to *_Dest2++, checked dest
	return (_STD pair<_OutIt1, _OutIt2>(
		_Partition_copy(_First, _Last,
			_Dest1, _Dest2, _Pred)));
	}

template<class _InIt,
	class _OutIt1,
	class _OutIt2,
	class _Pr> inline
_SCL_INSECURE_DEPRECATE
	_STD pair<_OutIt1, _OutIt2>
		_Partition_copy(_InIt _First, _InIt _Last,
			_OutIt1 _Dest1, _OutIt2 _Dest2, _Pr _Pred,
			_STD tr1::true_type, _STD tr1::false_type)
	{	// copy true partition *_Dest1++, false to *_Dest2++, unchecked dest
	return (_STD pair<_OutIt1, _OutIt2>(
		_Partition_copy(_First, _Last,
			_Dest1, _Dest2, _Pred)));
	}

template<class _InIt,
	class _OutIt1,
	class _OutIt2,
	class _Pr> inline
_SCL_INSECURE_DEPRECATE
	_STD pair<_OutIt1, _OutIt2>
		_Partition_copy(_InIt _First, _InIt _Last,
			_OutIt1 _Dest1, _OutIt2 _Dest2, _Pr _Pred,
			_STD tr1::false_type, _STD tr1::true_type)
	{	// copy true partition *_Dest1++, false to *_Dest2++, unchecked dest
	return (_STD pair<_OutIt1, _OutIt2>(
		_Partition_copy(_First, _Last,
			_Dest1, _Dest2, _Pred)));
	}

template<class _InIt,
	class _OutIt1,
	class _OutIt2,
	class _Pr> inline
_SCL_INSECURE_DEPRECATE
	_STD pair<_OutIt1, _OutIt2>
		_Partition_copy(_InIt _First, _InIt _Last,
			_OutIt1 _Dest1, _OutIt2 _Dest2, _Pr _Pred,
			_STD tr1::false_type, _STD tr1::false_type)
	{	// copy true partition *_Dest1++, false to *_Dest2++, unchecked dest
	return (_STD pair<_OutIt1, _OutIt2>(
		_Partition_copy(_First, _Last,
			_Dest1, _Dest2, _Pred)));
	}

template<class _InIt,
	class _OutIt1,
	class _OutIt2,
	class _Pr> inline
	_STD pair<_OutIt1, _OutIt2>
		partition_copy(_InIt _First, _InIt _Last,
			_OutIt1 _Dest1, _OutIt2 _Dest2, _Pr _Pred)
	{	// copy true partition *_Dest1++, false to *_Dest2++
	_DEBUG_RANGE(_First, _Last);
	_DEBUG_POINTER(_Dest1);
	_DEBUG_POINTER(_Dest2);
	_DEBUG_POINTER(_Pred);
	return (_STD pair<_OutIt1, _OutIt2>(
		_STD _Partition_copy(_Unchecked(_First), _Unchecked(_Last),
			_Dest1, _Dest2, _Pred,
			_Is_checked(_Dest1), _Is_checked(_Dest2))));
	}