/*
								+----------------------------------+
								|                                  |
								|     ***  STL utilities  ***      |
								|                                  |
								|   Copyright © -tHE SWINe- 2008   |
								|                                  |
								|            StlUtils.h            |
								|                                  |
								+----------------------------------+
*/

#pragma once
#ifndef __STL_UTILS_INCLUDED
#define __STL_UTILS_INCLUDED

/**
 *	@file StlUtils.h
 *	@date 2008
 *	@author -tHE SWINe-
 *	@brief STL utilities
 *
 *	@date 2008-12-22
 *
 *	added typename keyword in Reserve_NMore() so it now compiles with g++
 *
 *	@date 2009-01-13
 *
 *	added Format() function and StlUtils.cpp to keep it's body (it's not template)
 *
 *	@date 2009-03-24
 *
 *	added Assign and Append, accepting std::string as second argument,
 *	should allow assigning and appending strings with different character
 *	types as well (no conversion or error handling though).
 *
 *	(there was just const char* before; it was possible to use these versions
 *	to append std::string to std::string using c_str() function, but it
 *	would expectably yield worse performance)
 *
 *	@date 2009-05-04
 *
 *	stl_ut::Swap() was removed in favor of std::swap
 *
 *	added __STL_UTILS_ENABLE_EXCEPTIONS macro, controlling between exception-
 *	based and null-pointer based errors on operator new()
 *
 *	written documentation comments
 *
 *	@date 2009-10-11
 *
 *	added Resize_To_N(), Resize_Add_1More() and Resize_Add_NMore() functions
 *	to help avoiding unhandled std::bad_alloc in container::resize()
 *
 *	added AssignWCStr(), AppendWCStr() and FormatW() to support wide character
 *	strings, can disable them by defining __STL_UTILS_NO_WIDE_STRINGS macro
 *
 *	added __STL_UT_CATCH_BAD_ALLOC macro, containing catch(std::bad_alloc&)
 *	(in case __STL_UTILS_ENABLE_EXCEPTIONS is not defined)
 *
 *	@date 2009-10-20
 *
 *	fixed some warnings when compiling under VC 2005, implemented "Security
 *	Enhancements in the CRT" for VC 2008. compare against MyProjects_2009-10-19_
 *
 *	@date 2010-02-12
 *
 *	added __stl_ut_try, __stl_ut_catch and __stl_ut_catch_bad_alloc aliases
 *
 *	@date 2010-08-09
 *
 *	fixed error in stl_ut::Resize_Add_NMore(), which didn't resize container
 *	in case it had sufficient capacity (regardless of size)
 *
 *	@date 2011-07-18
 *
 *	Added the stl_ut::Split() function for splitting a string to a list
 *	of substrings by a separator.
 *
 *	@date 2012-06-19
 *
 *	Moved multiple inclusion guard before file documentation comment.
 *
 *	@date 2013-12-10
 *
 *	Decided to add TrimSpace() and ReadFile() functions. These are not quite versatile,
 *	as TrimSpace() only handles us-english whitespaces and not unicode, and ReadFile()
 *	will run into problems when using large files, but they are still useful for most
 *	of the applications.
 *
 */

/**
 *	@def __STL_UTILS_NO_WIDE_STRINGS
 *	@brief If defined, AssignWCStr(), AppendWCStr() and FormatW() won't be
 *		compiled (this may be needed in environments where wchar_t.h is not
 *		available and/or wcslen() or vsnwprintf() not defined).
 */
//#define __STL_UTILS_NO_WIDE_STRINGS

/*#if !defined(_WIN32) && !defined(_WIN64) && !defined(__STL_UTILS_NO_WIDE_STRINGS)
#define __STL_UTILS_NO_WIDE_STRINGS // unix has no vsnwsprintf but it has vswprintf
#endif // !_WIN32 && !_WIN64 && !__STL_UTILS_NO_WIDE_STRINGS*/

/**
 *	@def __STL_UTILS_ENABLE_EXCEPTIONS
 *	@brief if defined, it is expected that std::container::reserve() throws
 *		std::bad_alloc once it runs out of memory
 *
 *	The other model would be not increasing storage capacity,
 *	detected by comparing std::container::capacity() with requested
 *	number. This happens when operator new() returns 0 when there's
 *	not enough memory (patched versions of STL for MSVC 6.0 and older).
 */
#define __STL_UTILS_ENABLE_EXCEPTIONS

#ifdef __STL_UTILS_ENABLE_EXCEPTIONS
#define __STL_UT_TRY try
#define __STL_UT_CATCH(CException) catch(CException)
#else // __STL_UTILS_ENABLE_EXCEPTIONS
#define __STL_UT_TRY if(true)
#define __STL_UT_CATCH(CException) if(false)
#endif // __STL_UTILS_ENABLE_EXCEPTIONS

#define __STL_UT_CATCH_BAD_ALLOC __STL_UT_CATCH(std::bad_alloc&)

#define __stl_ut_try __STL_UT_TRY
#define __stl_ut_catch __STL_UT_CATCH
#define __stl_ut_catch_bad_alloc __STL_UT_CATCH_BAD_ALLOC
// allow small letters here

#include <string>
#include <vector>

/**
 *	@brief STL uttilities
 */
namespace stl_ut {

/**
 *	@brief reserves space for N elements in a container
 *
 *	@tparam CContainer is container type
 *
 *	@param[in,out] r_vec is container to reserve space in
 *	@param[in] n is number of elements to reserve space for (n elements, not for n more)
 *
 *	@return Returns true on success, false in case there's not enough memory.
 */
template <class CContainer>
inline bool Reserve_N(CContainer &r_vec, size_t n) throw()
{
	__STL_UT_TRY {
		r_vec.reserve(n);
		return r_vec.capacity() >= n;
		// reserve and check
	} __STL_UT_CATCH_BAD_ALLOC {
		return false;
		// not enough memory
	}
}

/**
 *	@brief resizes a container to N elements
 *
 *	@tparam CContainer is container type
 *
 *	@param[in,out] r_vec is container to be resized
 *	@param[in] n is number of elements to allocate space for (n elements, not for n more)
 *
 *	@return Returns true on success, false in case there's not enough memory.
 */
template <class CContainer>
inline bool Resize_To_N(CContainer &r_vec, size_t n) throw()
{
	__STL_UT_TRY {
		r_vec.resize(n);
		return true;
		// just resize
	} __STL_UT_CATCH_BAD_ALLOC {
		return false;
		// not enough memory
	}
}

/**
 *	@brief resizes a container to N elements
 *
 *	@tparam CContainer is container type
 *	@tparam CElem is initializer type (may be different from element type)
 *
 *	@param[in,out] r_vec is container to be resized
 *	@param[in] n is number of elements to allocate space for (n elements, not for n more)
 *	@param[in] r_t_initializer is initializer value for newly added elements
 *
 *	@return Returns true on success, false in case there's not enough memory.
 */
template <class CContainer, class CElem>
inline bool Resize_To_N(CContainer &r_vec, size_t n, const CElem &r_t_initializer) throw()
{
	__STL_UT_TRY {
		r_vec.resize(n, r_t_initializer);
		return true;
		// just resize
	} __STL_UT_CATCH_BAD_ALLOC {
		return false;
		// not enough memory
	}
}

/**
 *	@brief reserves space for 1 more element in a container
 *	@tparam CContainer is container type
 *	@param[in,out] r_vec is container to reserve space in
 *	@return Returns true on success, false in case there's not enough memory.
 */
template <class CContainer>
inline bool Reserve_1More(CContainer &r_vec) throw()
{
	__STL_UT_TRY {
		if(r_vec.capacity() == r_vec.size()) {
			r_vec.reserve((r_vec.size() <= r_vec.max_size() / 2)?
				(r_vec.size() * 2) | 1 : r_vec.max_size());
			// watch out for requested capacity overflow
			return r_vec.capacity() > r_vec.size();
		}
		return true;
	} __STL_UT_CATCH_BAD_ALLOC {
		// not enough memory
		return r_vec.size() < r_vec.max_size() && Reserve_N(r_vec, r_vec.size() + 1);
		// try allocating exactly one more (in case there's some memory left,
		// but not enough for twice as long vector)
	}
}

/**
 *	@brief allocates space for 1 more element in a container
 *	@tparam CContainer is container type
 *	@param[in,out] r_vec is container to allocate space in
 *	@return Returns true on success, false in case there's not enough memory.
 */
template <class CContainer>
inline bool Resize_Add_1More(CContainer &r_vec) throw()
{
	if(r_vec.size() == r_vec.max_size())
		return false;
	__STL_UT_TRY {
		/*if(r_vec.capacity() == r_vec.size()) {
			r_vec.reserve((r_vec.size() <= r_vec.max_size() / 2)?
				(r_vec.size() * 2) | 1 : r_vec.max_size());
			// watch out for requested capacity overflow
		}*/
		r_vec.resize(r_vec.size() + 1);
		return true;
	} __STL_UT_CATCH_BAD_ALLOC {
		return false;
		// not enough memory
		//return r_vec.size() < r_vec.max_size() && Resize_To_N(r_vec, r_vec.size() + 1);
		// try allocating exactly one more (in case there's some memory left,
		// but not enough for twice as long vector)
	}
}

/**
 *	@brief allocates space for 1 more element in a container
 *
 *	@tparam CContainer is container type
 *	@tparam CElem is initializer type (may be different from element type)
 *
 *	@param[in,out] r_vec is container to reserve space in
 *	@param[in] r_t_initializer is initializer value for newly added element
 *
 *	@return Returns true on success, false in case there's not enough memory.
 */
template <class CContainer, class CElem>
inline bool Resize_Add_1More(CContainer &r_vec, const CElem &r_t_initializer) throw()
{
	__STL_UT_TRY {
		/*if(r_vec.capacity() == r_vec.size()) {
			r_vec.reserve((r_vec.size() <= r_vec.max_size() / 2)?
				(r_vec.size() * 2) | 1 : r_vec.max_size());
			// watch out for requested capacity overflow
		}
		r_vec.resize(r_vec.size() + 1, r_t_initializer);*/
		r_vec.push_back(r_t_initializer); // this already contains code above (sgi version of stl)
		return true;
	} __STL_UT_CATCH_BAD_ALLOC {
		return false;
		// not enough memory
		/*return r_vec.size() < r_vec.max_size() &&
			Resize_To_N(r_vec, r_vec.size() + 1, r_t_initializer);*/ // will not succeed
		// try allocating exactly one more (in case there's some memory left,
		// but not enough for twice as long vector)
	}
}

/**
 *	@brief reserves space for N more element in a container
 *
 *	@tparam CContainer is container type
 *
 *	@param[in,out] r_vec is container to reserve space in
 *	@param[in] n is number of elements to allocate space for (n more elements, not for n)
 *
 *	@return Returns true on success, false in case there's not enough memory.
 */
template <class CContainer>
inline bool Reserve_NMore(CContainer &r_vec, size_t n) throw()
{
	const typename CContainer::size_type n_max = r_vec.max_size();
	// get maximal size of container

	if(r_vec.size() > n_max - n)
		return false;
	// see if n items can be inserted

	typename CContainer::size_type n_min_new_capa = r_vec.size() + n;
#if 1
	return Reserve_N(r_vec, n_min_new_capa);
#else // 1
	if(r_vec.capacity() < n_min_new_capa) {
#if 0
		typename CContainer::size_type n_new_capa = r_vec.capacity();
		while(n_new_capa < n_min_new_capa) {
			if(n_new_capa >= n_max / 2) {
				n_new_capa = n_max;
				break;
			}
			// watch out for overflow

			n_new_capa *= 2;
			n_new_capa |= 1;
		}
		// calculate new capacity, scale by factor of two
#else // 0
		typename CContainer::size_type n_new_capa = (r_vec.capacity() * 2) | 1;

		if(n_new_capa < n_min_new_capa)
			n_new_capa = n_min_new_capa;
		else if(n_new_capa > n_max)
			n_new_capa = n_max;
		// scale by factor of two, do it more simple (sufficient in most cases)
#endif // 0

		__STL_UT_TRY {
			r_vec.reserve(n_new_capa);
			return r_vec.capacity() >= n_min_new_capa;
			// reserve and check
		} __STL_UT_CATCH_BAD_ALLOC {
			// not enough memory
			return Reserve_N(r_vec, n_min_new_capa);
		}
	}
	return true;
#endif // 1
}

/**
 *	@brief allocates space for N more element in a container
 *
 *	@tparam CContainer is container type
 *
 *	@param[in,out] r_vec is container to allocate space in
 *	@param[in] n is number of elements to allocate space for (n more elements, not for n)
 *
 *	@return Returns true on success, false in case there's not enough memory.
 */
template <class CContainer>
inline bool Resize_Add_NMore(CContainer &r_vec, size_t n) throw()
{
	const typename CContainer::size_type n_max = r_vec.max_size();
	// get maximal size of container

	if(r_vec.size() > n_max - n)
		return false;
	// see if n items can be inserted

	typename CContainer::size_type n_min_new_capa = r_vec.size() + n;
	/*if(r_vec.capacity() < n_min_new_capa) {
		typename CContainer::size_type n_new_capa = (r_vec.capacity() * 2) | 1;

		if(n_new_capa < n_min_new_capa)
			n_new_capa = n_min_new_capa;
		else if(n_new_capa > n_max)
			n_new_capa = n_max;
		// scale by factor of two, do it more simple (sufficient in most cases)

		__STL_UT_TRY {
			r_vec.reserve(n_new_capa);
			r_vec.resize(n_min_new_capa);
			return true;
			// reserve and check
		} __STL_UT_CATCH_BAD_ALLOC {
			// not enough memory
			//return Resize_To_N(r_vec, n_min_new_capa); // just fall trough
		}
	}*/
	return Resize_To_N(r_vec, n_min_new_capa); // just very simple function, safe to call here
}

/**
 *	@brief allocates space for N more element in a container
 *
 *	@tparam CContainer is container type
 *	@tparam CElem is initializer type (may be different from element type)
 *
 *	@param[in,out] r_vec is container to allocate space in
 *	@param[in] n is number of elements to allocate space for (n more elements, not for n)
 *	@param[in] r_t_initializer is initializer value for newly added elements
 *
 *	@return Returns true on success, false in case there's not enough memory.
 */
template <class CContainer, class CElem>
inline bool Resize_Add_NMore(CContainer &r_vec, size_t n, const CElem &r_t_initializer) throw()
{
	const typename CContainer::size_type n_max = r_vec.max_size();
	// get maximal size of container

	if(r_vec.size() > n_max - n)
		return false;
	// see if n items can be inserted

	typename CContainer::size_type n_min_new_capa = r_vec.size() + n;
	/*if(r_vec.capacity() < n_min_new_capa) {
		typename CContainer::size_type n_new_capa = (r_vec.capacity() * 2) | 1;

		if(n_new_capa < n_min_new_capa)
			n_new_capa = n_min_new_capa;
		else if(n_new_capa > n_max)
			n_new_capa = n_max;
		// scale by factor of two, do it more simple (sufficient in most cases)

		__STL_UT_TRY {
			r_vec.reserve(n_new_capa);
			r_vec.resize(n_min_new_capa, r_t_initializer);
			return true;
			// reserve and check
		} __STL_UT_CATCH_BAD_ALLOC {
			// not enough memory
			//return Resize_To_N(r_vec, n_min_new_capa, r_t_initializer); // just fall trough
		}
	}*/
	return Resize_To_N(r_vec, n_min_new_capa, r_t_initializer); // just very simple function, safe to call here
}

/**
 *	@brief assigns one std::string to other, permitting character type conversions
 *
 *	@tparam CDestString is destination string type
 *	@tparam CSrcString is source string type
 *
 *	@param[out] r_s_dest is destination string (overwritten by the source string upon successful return)
 *	@param[in] r_s_src is source string
 *
 *	@return Returns true on success, false on failure.
 */
template <class CDestString, class CSrcString>
bool Assign(CDestString &r_s_dest, const CSrcString &r_s_src) throw()
{
	r_s_dest.erase(); // avoid copying in reallocation
	if(r_s_src.length() >= r_s_dest.max_size() || !Reserve_N(r_s_dest, r_s_src.length() + 1))
		return false;
	// make sure there's space in the string, also for the terminating null so that c_str() won't throw

	//r_s_dest.assign(r_s_src);
	__STL_UT_TRY {
		r_s_dest.insert(r_s_dest.begin(), r_s_src.begin(), r_s_src.end()); // permits character conversions
	} __STL_UT_CATCH_BAD_ALLOC {
		return false;
		// might still throw, e.g. if allocating one extra character for null-termination for c_str()
	}
	// assign

	return true;
}

/**
 *	@brief assigns null-terminated "C" string to a std::string
 *
 *	@tparam CDestString is destination string type
 *	@tparam CChar is "C" string character type
 *
 *	@param[out] r_s_dest is destination string (overwritten by the source string upon successful return)
 *	@param[in] p_s_src is source null-terminated "C" string
 *
 *	@return Returns true on success, false on failure.
 */
template <class CDestString, class CChar>
bool AssignCStr(CDestString &r_s_dest, CChar *p_s_src) throw()
{
	r_s_dest.erase(); // avoid copying in reallocation
	size_t n = strlen(p_s_src);
	if(n >= r_s_dest.max_size() || !Reserve_N(r_s_dest, n + 1))
		return false;
	// make sure there's space in the string, also for the terminating null so that c_str() won't throw

	//r_s_dest.assign(p_s_src);
	__STL_UT_TRY {
		r_s_dest.insert(r_s_dest.end(), p_s_src, p_s_src + n); // permits character conversions
	} __STL_UT_CATCH_BAD_ALLOC {
		return false;
		// might still throw, e.g. if allocating one extra character for null-termination for c_str()
	}
	// append

	return true;
}

/**
 *	@brief appends one std::string to other, permitting character type conversions
 *
 *	@tparam CDestString is destination string type
 *	@tparam CSrcString is source string type
 *
 *	@param[out] r_s_dest is destination string (appended with source string upon successful return)
 *	@param[in] r_s_src is source string
 *
 *	@return Returns true on success, false on failure.
 */
template <class CDestString, class CSrcString>
bool Append(CDestString &r_s_dest, const CSrcString &r_s_src) throw()
{
	if(r_s_src.length() >= r_s_dest.max_size() - r_s_dest.length() ||
	   !Reserve_N(r_s_dest, r_s_dest.length() + r_s_src.length() + 1))
		return false;
	// make sure there's space in the string, also for the terminating null so that c_str() won't throw

	//r_s_dest.append(r_s_src);
	__STL_UT_TRY {
		r_s_dest.insert(r_s_dest.end(), r_s_src.begin(), r_s_src.end()); // permits character conversions
	} __STL_UT_CATCH_BAD_ALLOC {
		return false;
		// might still throw, e.g. if allocating one extra character for null-termination for c_str()
	}
	// append

	return true;
}

/**
 *	@brief appends null-terminated "C" string to std::string, permitting character type conversions
 *
 *	@tparam CDestString is destination string type
 *	@tparam CChar is "C" string character type
 *
 *	@param[out] r_s_dest is destination string (appended with source string upon successful return)
 *	@param[in] p_s_src is source null-terminated "C" string
 *
 *	@return Returns true on success, false on failure.
 */
template <class CDestString, class CChar>
bool AppendCStr(CDestString &r_s_dest, CChar *p_s_src) throw()
{
	size_t n = strlen(p_s_src);
	if(n >= r_s_dest.max_size() - r_s_dest.length() || !Reserve_N(r_s_dest, n + r_s_dest.length() + 1))
		return false;
	// make sure there's space in the string, also for the terminating null so that c_str() won't throw

	//r_s_dest.append(p_s_src);
	__STL_UT_TRY {
		r_s_dest.insert(r_s_dest.end(), p_s_src, p_s_src + n); // permits character conversions
	} __STL_UT_CATCH_BAD_ALLOC {
		return false;
		// might still throw, e.g. if allocating one extra character for null-termination for c_str()
	}
	// append

	return true;
}

#include <string>

/**
 *	@brief equivalent of standard "C" library sprintf function, working with std::string output
 *
 *	@param[out] r_s_result is reference to the output string
 *	@param[in] p_s_fmt is standard printf format string
 *	@param[in] ... is additional arguments, corresponding to the format string
 *
 *	@return Returns true on success, false on failure (not enough memory).
 *
 *	@note This is safe against output buffer overrun, but is still susceptible to ill-formated
 *		format string (p_s_fmt) and bad arguments (not enough of them / not corresponding
 *		to tags in the format string). but as the first one being run-time error and the
 *		latter one compile-time error, this brings enought improvement.
 */
bool Format(std::string &r_s_result, const char *p_s_fmt, ...);

/**
 *	@brief equivalent of standard "C" library sprintf function, working with std::string output
 *
 *	@param[out] p_s_result is pointer to a buffer to store the output string
 *	@param[in] n_buffer_size is size of the output buffer, in bytes
 *	@param[in] p_s_fmt is standard printf format string
 *	@param[in] ... is additional arguments, corresponding to the format string
 *
 *	@return Returns true on success, false on failure (not enough memory).
 *
 *	@note This is safe against output buffer overrun, but is still susceptible to ill-formated
 *		format string (p_s_fmt) and bad arguments (not enough of them / not corresponding
 *		to tags in the format string). but as the first one being run-time error and the
 *		latter one compile-time error, this brings enought improvement.
 */
bool Format(char *p_s_result, size_t n_buffer_size, const char *p_s_fmt, ...);

/**
 *	@brief reads line form a file
 *
 *	@param[out] r_s_line is output string, containing one line read from a file
 *	@param[in] p_fr is pointer to a file
 *
 *	@return Returns true on success, false on failure (not enough memory / input error).
 *
 *	@note In case file is at it's end, output lines are empty, but the function still succeeds.
 *	@note Output lines may contain carriage-return character(s), for example if the file
 *		is opened for binary reading. Line-feed character marks end of line and is never
 *		included.
 */
bool ReadLine(std::string &r_s_line, FILE *p_fr);

/**
 *	@brief reads entire file into a string
 *
 *	@param[out] r_s_output is string to contain the file
 *	@param[in] p_s_filename is filename
 *
 *	@return Returns true on success, false on failure (not enough memory / input error).
 */
bool ReadFile(std::string &r_s_output, const char *p_s_filename);

/**
 *	@brief removes heading and trailing whitespace from a line
 *
 *	@param[in,out] r_s_string is string to have whitespace removed
 */
void TrimSpace(std::string &r_s_string);

/**
 *	@brief splits a string by a separator
 *
 *	@param[out] r_s_dest is destination vector for substrings
 *	@param[in] r_s_string is the input string
 *	@param[in] p_s_separator is the separator
 *	@param[in] n_thresh is minimal output string threshold
 *		(only strings longer than threshold are stored in r_s_dest)
 *
 *	@return Returns true on success, false on failure (not enough memory).
 */
bool Split(std::vector<std::string> &r_s_dest, const std::string &r_s_string,
	const char *p_s_separator, int n_thresh = -1);

/**
 *	@brief splits a string by several single-char separators
 *
 *	@param[out] r_s_dest is destination vector for substrings
 *	@param[in] r_s_string is the input string
 *	@param[in] p_s_separators is null-terminated string, containing the separators
 *	@param[in] n_thresh is minimal output string threshold
 *		(only strings longer than threshold are stored in r_s_dest)
 *
 *	@return Returns true on success, false on failure (not enough memory).
 */
bool SplitByMultiple(std::vector<std::string> &r_s_dest, const std::string &r_s_string,
	const char *p_s_separators, int n_thresh = -1);

#ifndef __STL_UTILS_NO_WIDE_STRINGS

#include <wchar.h>

/**
 *	@brief assigns wide null-terminated "C" string to a std::string
 *
 *	@tparam CDestString is destination string type
 *	@tparam CChar is "C" string character type
 *
 *	@param[out] r_s_dest is destination string (overwritten by the source string upon successful return)
 *	@param[in] p_s_src is source null-terminated "C" string
 *
 *	@return Returns true on success, false on failure.
 */
template <class CDestString, class CChar>
bool AssignWCStr(CDestString &r_s_dest, CChar *p_s_src) throw()
{
	r_s_dest.erase(); // avoid copying in reallocation
	size_t n = wcslen(p_s_src);
	if(n >= r_s_dest.max_size() || !Reserve_N(r_s_dest, n + 1))
		return false;
	// make sure there's space in the string, also for the terminating null so that c_str() won't throw

	//r_s_dest.assign(p_s_src);
	__STL_UT_TRY {
		r_s_dest.insert(r_s_dest.end(), p_s_src, p_s_src + n); // permits character conversions
	} __STL_UT_CATCH_BAD_ALLOC {
		return false;
		// might still throw, e.g. if allocating one extra character for null-termination for c_str()
	}
	// append

	return true;
}

/**
 *	@brief appends null-terminated "C" string to std::string, permitting character type conversions
 *
 *	@tparam CDestString is destination string type
 *	@tparam CChar is "C" string character type
 *
 *	@param[out] r_s_dest is destination string (appended with source string upon successful return)
 *	@param[in] p_s_src is source null-terminated "C" string
 *
 *	@return Returns true on success, false on failure.
 */
template <class CDestString, class CChar>
bool AppendWCStr(CDestString &r_s_dest, CChar *p_s_src) throw()
{
	size_t n = wcslen(p_s_src);
	if(n >= r_s_dest.max_size() - r_s_dest.length() || !Reserve_N(r_s_dest, n + r_s_dest.length() + 1))
		return false;
	// make sure there's space in the string, also for the terminating null so that c_str() won't throw

	//r_s_dest.append(p_s_src);
	__STL_UT_TRY {
		r_s_dest.insert(r_s_dest.end(), p_s_src, p_s_src + n); // permits character conversions
	} __STL_UT_CATCH_BAD_ALLOC {
		return false;
		// might still throw, e.g. if allocating one extra character for null-termination for c_str()
	}
	// append

	return true;
}

/**
 *	@brief equivalent of standard "C" library sprintf function, working with std::string output
 *
 *	@param[out] r_s_result is reference to the output string
 *	@param[in] p_s_fmt is standard printf format string
 *	@param[in] ... is additional arguments, corresponding to the format string
 *
 *	@return Returns true on success, false on failure (not enough memory).
 *
 *	@note This is safe against output buffer overrun, but is still susceptible to ill-formated
 *		format string (p_s_fmt) and bad arguments (not enough of them / not corresponding
 *		to tags in the format string). but as the first one being run-time error and the
 *		latter one compile-time error, this brings enought improvement.
 */
bool FormatW(std::basic_string<wchar_t> &r_s_result, const wchar_t *p_s_fmt, ...);

/**
 *	@brief equivalent of standard "C" library sprintf function, working with std::string output
 *
 *	@param[out] p_s_result is pointer to a buffer to store the output string
 *	@param[in] n_buffer_size is size of the output buffer, in bytes
 *	@param[in] p_s_fmt is standard printf format string
 *	@param[in] ... is additional arguments, corresponding to the format string
 *
 *	@return Returns true on success, false on failure (not enough memory).
 *
 *	@note This is safe against output buffer overrun, but is still susceptible to ill-formated
 *		format string (p_s_fmt) and bad arguments (not enough of them / not corresponding
 *		to tags in the format string). but as the first one being run-time error and the
 *		latter one compile-time error, this brings enought improvement.
 */
bool FormatW(wchar_t *p_s_result, size_t n_buffer_size, const wchar_t *p_s_fmt, ...);

#endif // __STL_UTILS_NO_WIDE_STRINGS

/**
 *	@brief function onjects that scalar-deletes pointers
 *	@tparam CType is data type being pointed to
 */
template <class CType>
struct CDefaultDelete {
	/**
	 *	@brief function operator; deletes a given pointer
	 *	@param[in] p_pointer is pointer to be deleted
	 */
	inline void operator ()(CType *p_pointer) const
	{
		if(p_pointer)
			delete p_pointer;
	}
};

/**
 *	@brief unique pointer class
 *
 *	@tparam TType is scalar type to be pointed to (not the pointer type)
 *	@tparam TDestructor is edstructor type; must implement function operator,
 *		taking the pointer (default CDefaultDelete)
 */
template <class TType, class TDestructor = CDefaultDelete<TType> >
class CUniquePtr {
public:
	typedef TType CType; /**< @brief scalar type (not pointer) */
	typedef TDestructor CDestructor; /**< @brief destructor type */

protected:
	CType *m_p_pointer; /**< @brief the managed pointer */

public:
	/**
	 *	@brief default constructor; sets pointer to a specified value
	 *	@param[in] p_pointer is pointer to become managed (default null pointer)
	 *	@note The specified pointer will be deleted automatically.
	 */
	explicit inline CUniquePtr(CType *p_pointer = 0)
		:m_p_pointer(p_pointer)
	{}

	/**
	 *	@brief copy-constructor
	 *	@param[in,out] r_other is unique pointer to copy from (it will lose ownership of the pointer)
	 */
	inline CUniquePtr(/*const*/ CUniquePtr &r_other)
		:m_p_pointer(/*const_cast<CUniquePtr&>*/(r_other).p_YieldOwnership())
	{}

	/**
	 *	@brief destructor; deletes the currently owned pointer, if any
	 */
	inline ~CUniquePtr()
	{
		CDestructor()(m_p_pointer);
	}

	/**
	 *	@brief copy operator; deletes the currently owned pointer, if any
	 *	@param[in,out] r_other is unique pointer to copy from (it will lose ownership of the pointer)
	 *	@return Returns reference to this.
	 */
	inline CUniquePtr &operator =(/*const*/ CUniquePtr &r_other)
	{
		CDestructor()(m_p_pointer);//Destroy();
		m_p_pointer = /*const_cast<CUniquePtr&>*/(r_other).p_YieldOwnership();
		return *this;
	}

	/**
	 *	@brief deletes the currently owned pointer, if any
	 */
	inline void Destroy()
	{
		CDestructor()(m_p_pointer);//this->~CUniquePtr();
		m_p_pointer = 0;
	}

	/**
	 *	@brief yields ownership of the pointer, which is to be no longer managed
	 *	@return Returns the currently owned pointer. This object owns no pointer upon return.
	 *	@note This would be usually called "Release" but in some contexts that refers to
	 *		destroying an object and the meaning would be misleading.
	 */
	inline CType *p_YieldOwnership()
	{
		CType *p_result = m_p_pointer;
		m_p_pointer = 0;
		return p_result;
	}

	/**
	 *	@brief conversion to pointer
	 *	@return Returns the currently owned pointer (may be a null pointer).
	 *	@note This does not yield ownership of the pointer (it stays managed).
	 */
	inline CType *p_Get() const
	{
		return m_p_pointer;
	}

	/**
	 *	@brief conversion to bool
	 *	@return Returns true if the owned pointer is not null, otherwise returns false.
	 */
	inline operator bool() const
	{
		return m_p_pointer != 0;
	}

	/**
	 *	@brief const indirection operator
	 *	@return Returns the currently owned pointer (may be a null pointer).
	 *	@note This does not yield ownership of the pointer (it stays managed).
	 */
	inline const CType &operator *() const
	{
		return *m_p_pointer;
	}

	/**
	 *	@brief indirection operator
	 *	@return Returns the currently owned pointer (may be a null pointer).
	 *	@note This does not yield ownership of the pointer (it stays managed).
	 */
	inline CType &operator *()
	{
		return *m_p_pointer;
	}

	/**
	 *	@brief const member access operator
	 *	@return Returns the currently owned pointer (may be a null pointer).
	 *	@note This does not yield ownership of the pointer (it stays managed).
	 */
	inline const CType *operator ->() const
	{
		return m_p_pointer;
	}

	/**
	 *	@brief member access operator
	 *	@return Returns the currently owned pointer (may be a null pointer).
	 *	@note This does not yield ownership of the pointer (it stays managed).
	 */
	inline CType *operator ->()
	{
		return m_p_pointer;
	}

	/**
	 *	@brief swaps two unique handles
	 *	@param[in,out] r_other is pointer to swap with
	 */
	inline void Swap(CUniquePtr &r_other)
	{
		std::swap(r_other.m_p_pointer, m_p_pointer);
	}
};

/**
 *	@brief exclusive prefix sum function
 *
 *	@tparam CForwardIterator is forward iterator type
 *
 *	@param[in] p_begin_it is iterator pointing to the first element of the sequence
 *	@param[in] p_end_it is iterator pointing to one past the last element of the sequence
 */
template <class CForwardIterator>
void ExclusiveScan(CForwardIterator p_begin_it, CForwardIterator p_end_it)
{
	_ASSERTE(p_begin_it <= p_end_it);
	typename std::iterator_traits<CForwardIterator>::value_type n_sum = 0; // t_odo - figure out how to get that from CRandomIterator also in case it i
	for(; p_begin_it != p_end_it; ++ p_begin_it) {
		typename std::iterator_traits<CForwardIterator>::value_type n = *p_begin_it;
		*p_begin_it = n_sum;
		n_sum += n;
	}
}

/**
 *	@brief inclusive prefix sum function
 *
 *	@tparam CForwardIterator is forward iterator type
 *
 *	@param[in] p_begin_it is iterator pointing to the first element of the sequence
 *	@param[in] p_end_it is iterator pointing to one past the last element of the sequence
 */
template <class CForwardIterator>
void InclusiveScan(CForwardIterator p_begin_it, CForwardIterator p_end_it)
{
	_ASSERTE(p_begin_it <= p_end_it);
	if(p_begin_it == p_end_it)
		return;
	typename std::iterator_traits<CForwardIterator>::value_type n_prev = *p_begin_it;
	for(++ p_begin_it; p_begin_it != p_end_it; ++ p_begin_it)
		n_prev = *p_begin_it += n_prev;
}

/**
 *	@brief generates a sequence of increasing values
 *
 *	@tparam CForwardIterator is forward iterator type
 *	@tparam CValue is value type (must be convertible to type the iterators
 *		point to, and must be incrementable)
 *
 *	@param[in] p_begin_it is iterator pointing to the first element of the sequence
 *	@param[in] p_end_it is iterator pointing to one past the last element of the sequence
 *	@param[in] t_first is value of the first element of the sequence
 */
template <class CForwardIterator, class CValue>
void IOTA(CForwardIterator p_begin_it, CForwardIterator p_end_it, CValue t_first)
{
	_ASSERTE(p_begin_it <= p_end_it);
	for(; p_begin_it != p_end_it; ++ p_begin_it, ++ t_first)
		*p_begin_it = t_first;
}

/**
 *	@brief generates a sequence of increasing values, starting at zero
 *
 *	@tparam CForwardIterator is forward iterator type
 *
 *	@param[in] p_begin_it is iterator pointing to the first element of the sequence
 *	@param[in] p_end_it is iterator pointing to one past the last element of the sequence
 */
template <class CForwardIterator>
void IOTA(CForwardIterator p_begin_it, CForwardIterator p_end_it)
{
	_ASSERTE(p_begin_it <= p_end_it);
	typename std::iterator_traits<CForwardIterator>::value_type v = 0;
	for(; p_begin_it != p_end_it; ++ p_begin_it, ++ v)
		*p_begin_it = v;
}

/**
 *	@brief comparison object for std::pair, comparing only the first member
 */
struct CCompareFirst {
	/**
	 *	@brief function operator; performs the comparison
	 *
	 *	@tparam CPair is specialization of std::pair
	 *
	 *	@param[in] a is the first pair to compare
	 *	@param[in] b is the second pair to compare
	 *
	 *	@return Returns true if the first pair is ordered before the second pair.
	 */
	template <class CPair>
	inline bool operator ()(const CPair &a, const CPair &b) const
	{
		return a.first < b.first;
	}
};

/**
 *	@brief comparison object for std::pair, comparing only the second member
 */
struct CCompareSecond {
	/**
	 *	@brief function operator; performs the comparison
	 *
	 *	@tparam CPair is specialization of std::pair
	 *
	 *	@param[in] a is the first pair to compare
	 *	@param[in] b is the second pair to compare
	 *
	 *	@return Returns true if the first pair is ordered before the second pair.
	 */
	template <class CPair>
	inline bool operator ()(const CPair &a, const CPair &b) const
	{
		return a.second < b.second;
	}
};

/**
 *	@brief comparison object for std::pair, implementing reversed lexicographical comparison
 */
struct CCompareSecond_then_First {
	/**
	 *	@brief function operator; performs the comparison
	 *
	 *	@tparam CPair is specialization of std::pair
	 *
	 *	@param[in] a is the first pair to compare
	 *	@param[in] b is the second pair to compare
	 *
	 *	@return Returns true if the first pair is ordered before the second pair.
	 */
	template <class CPair>
	inline bool operator ()(const CPair &a, const CPair &b) const
	{
		return a.second < b.second ||
			(a.second == b.second && a.first < b.first);
	}
};

} // ~stl_ut

namespace std {

/**
 *	@brief swaps two unique pointers
 *
 *	@param[in,out] r_a is the first pointer to swap
 *	@param[in,out] r_b is the second pointer to swap
 */
template <class TType, class TDestructor>
inline void swap(stl_ut::CUniquePtr<TType, TDestructor> &r_a,
	stl_ut::CUniquePtr<TType, TDestructor> &r_b)
{
	r_a.Swap(r_b);
}

} // ~std

#endif // !__STL_UTILS_INCLUDED
